Memory is Reconstructed, Not Retrieved: Graph Memory for LLM Agents

Despite recent progress, LLM agents still struggle with reasoning over long interaction histories. While current memory-augmented agents rely on a static ``retrieve-then-reason'' paradigm, this rigid pipeline design prevents them from dynamically adapting memory access to intermediate evidence discovered during inference. To bridge this gap, we propose MRAgent, a framework that combines an associative memory graph with an active reconstruction mechanism. We represent memory as a Cue–Tag–Content graph, where associative tags serve as semantic bridges connecting fine-grained cues to memory contents. Operating on this structure, our active reconstruction mechanism integrates LLM reasoning directly into memory access, allowing the agent to iteratively explore and prune retrieval paths based on accumulated evidence. This ensures that memory retrieval is dynamically adapted to the reasoning context while avoiding combinatorial explosion caused by unconstrained expansion. Experiments on the LoCoMo benchmark and LongMemEval benchmark demonstrate significant improvements over strong baselines (up to $23\\%$), while substantially reducing retrieval cost, highlighting the effectiveness of active and associative reconstruction for long-horizon memory reasoning.

AI assistants powered by large language models reason well but remember poorly. Once a conversation grows long, they lose track of what was said earlier. To cope, they store past information externally and look it up when needed. But today's systems search only once, based on the question, and work with whatever comes back, even when the first search misses the answer. Human memory works differently. One clue triggers another, and we reconstruct a memory step by step. We built MRAgent to work this way. Instead of searching once, it explores its memory in several steps, using what it finds to decide where to look next, and storing memories as a network of linked clues rather than a flat list. On long conversations, MRAgent answered questions more accurately than existing methods, especially hard ones that require connecting scattered details, while using far less computation. This points toward AI assistants that can reason reliably over everything a user has told them before.