Skip to content

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

🕒 Published (v1): 2026-06-04 00:00 UTC · Source: HuggingFace · link

Why this paper was selected

Bryan Hooi (NUS); dynamic graph memory challenges static retrieve-then-reason paradigm fundamentally

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

MRAgent replaces the static "retrieve-then-reason" pipeline with an active, iterative memory reconstruction process inspired by cognitive neuroscience. It organizes memory as a Cue–Tag–Content heterogeneous graph and lets an LLM dynamically select traversal actions, pruning irrelevant branches at each step. On LoCoMo and LongMemEval benchmarks it outperforms all baselines by up to 23% while consuming fewer tokens than most competitors.

Problem

Existing memory-augmented LLM agents rely on passive retrieval—either similarity-based top-\(k\) over flat stores or fixed \(N\)-hop neighbor expansion on knowledge graphs. Both are stateless: retrieval paths are fully determined by the initial query and cannot be revised based on intermediate evidence. This causes (i) inability to infer new retrieval cues mid-reasoning (e.g., inferring a temporal anchor like "July"), (ii) noise accumulation from fixed aggregation, and (iii) retrieval failures when relevant evidence is not directly connected to seed nodes.

Method

MRAgent frames memory access as a sequential decision process over a Cue–Tag–Content (CTC) heterogeneous graph. Memory nodes are divided into cues \(c \in C\) (fine-grained keywords/entities), tagged relations \(g \in G\) (associative summaries), and contents \(v \in V\) (episodic events, semantic facts, or topic abstractions). Two induced operators decouple associative reasoning from content retrieval:

\[\phi_{c \to g}(c) \triangleq \{g \mid (c,g,\cdot) \in R\}, \quad \phi_{(c,g)\to v}(c,g) \triangleq \{v \mid (c,g,v) \in R\}\]

At inference, MRAgent maintains a reconstruction state \(S^{(t)} = (Z^{(t)}, H^{(t)})\) where \(Z^{(t)}\) is the active candidate set and \(H^{(t)}\) is the accumulated evidence context. Each iteration the LLM (i) selects traversal actions (forward: Cue→Tag→Content; reverse: Content→Cue/Tag), (ii) expands candidates via the corresponding operators, and (iii) prunes irrelevant branches via an LLM routing function \(f_\text{route}\). The loop terminates when a sufficiency criterion is met. The memory graph is populated offline via LLM-based distillation that extracts episodic units, tags, and cues from raw dialogues, plus topic-level summaries.

Key Contributions

  • Formalization of active vs. passive retrieval as distinct policy classes, with a proof that active retrieval is strictly more expressive (Theorem 4.1: \(H^\text{LM}_\text{passive}(T) \subsetneq H^\text{LM}_\text{active}(T)\) for any budget \(T \geq 2\)).
  • The Cue–Tag–Content memory graph with multi-granular layers (episodic, semantic, topic abstraction) enabling selective, noise-aware traversal.
  • An iterative LLM-driven reconstruction loop with forward and reverse traversal actions and explicit state tracking.
  • Demonstrated efficiency: lowest token consumption (118k tokens/sample) and second-lowest runtime among all evaluated baselines on LongMemEval.

Results

  • LoCoMo (Gemini backbone): Overall LLM-Judge score 84.21 vs. 68.31 for best baseline (Mem0), a +23.3% relative gain; multi-hop J score 75.17 vs. 68.79 (Mem0); temporal J score 80.37 vs. 61.68.
  • LoCoMo (Claude backbone): Overall J score 88.32 vs. 78.61 (LangMem), +12.4% relative gain.
  • LongMemEval (Gemini backbone): Overall J score 72.95 vs. 54.92 (MemoryOS), +32% relative gain; multi-session 68.42 vs. 56.39.
  • LongMemEval (cross-backbone MRAgent*): 86.76 overall J using Claude for retrieval with Gemini-constructed memories.
  • Token efficiency: MRAgent uses 118k tokens/sample vs. 632k (A-Mem), 273k (MemoryOS), 3,268k (LangMem), 245k (Mem0); runtime 586s vs. up to 3,135s (A-Mem).

Limitations

  • Memory graph construction requires LLM inference over the full dialogue stream, adding offline distillation cost not fully accounted in the retrieval-only comparison.
  • The reconstruction loop depth \(T\) is a budget parameter; performance on very sparse or ambiguous queries (where cue matching fails at initialization) is not thoroughly analyzed.
  • Experiments use only two LLM backbones (Gemini-2.5-Flash, Claude-Sonnet-4.5); generalization to smaller or open-weight models is unexamined.
  • The theoretical guarantee (Theorem 4.1) covers expressivity but not sample efficiency or worst-case retrieval complexity under adversarial graph structures.

Relevance to Agentic AI / LLM Agents

This work directly addresses a core bottleneck in long-horizon LLM agents: the inability to reason and retrieve concurrently. By proving that active retrieval policies are strictly more expressive than passive ones, it provides formal grounding for why current RAG-based agents hit a ceiling on multi-hop and temporal queries. The Cue–Tag–Content graph and iterative reconstruction loop are immediately applicable to any agent architecture requiring persistent episodic memory across sessions—dialogue assistants, task agents with long action histories, or personal AI with preference tracking. The efficiency result (lowest token cost among evaluated systems) makes deployment practical, and the cross-backbone transferability of the memory graph (MRAgent* result) supports modular agent design where memory construction and retrieval use different models.