PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Shuo Ji, Yibo Li, Bryan Hooi

arXiv:2606.06036v1cs.AIcs.IR

TL;DR

LLM agents struggle to reason over long interaction histories because limited context windows constrain memory retention. MRAgent uses active reconstruction over a Cue–Tag–Content graph and consistently outperforms baselines, including a 23.3% relative gain in overall J under Gemini.

  • Problem

    Limited context windows constrain interaction-history retention, contributing to deficient long-term memory in extended LLM-agent tasks.

  • Method

    MRAgent integrates LLM reasoning into memory access, using a Cue–Tag–Content graph to explore, route, and prune retrieval paths based on accumulated evidence.

  • Results

    MRAgent consistently outperforms baselines across question types and backbones, improving overall J by 23.3% relative under Gemini and by 32% over the strongest baseline on MEMEVAL.

  • Takeaways & Limitations

    The results support active, associative reconstruction as an effective and token- and runtime-efficient approach for long-horizon memory reasoning.

  • Takeaways & Limitations

    Passive retrieval remains limited by fixed aggregation, dependence on pre-constructed structures, and inability to revise strategies from intermediate evidence.

Abstract

from arXiv · show

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 token and runtime cost, highlighting the effectiveness of active and associative reconstruction for long-horizon memory reasoning.

1. Introduction

LLM agents struggle with long-horizon memory because limited context windows restrict retention of interaction history, while passive retrieval cannot adapt access to intermediate evidence. MRAgent addresses these challenges through active reconstruction over an associative Cue–Tag–Content memory graph, with theoretical and empirical evidence of improved capability and efficiency.

  • Motivation: Long-horizon tasks expose LLMs’ limited long-term memory, while constrained context windows restrict their ability to retain interaction history.These limitations affect interactive assistance and decision-support systems operating over extended interactions.
  • Challenges: The introduction identifies active multi-step reconstruction and associative memory organization as the two central challenges for LLM-based memory systems.The framework must progressively reveal information across reasoning steps and support guided exploration across semantically and structurally dependent items.
  • MRAgent: MRAgent integrates LLM reasoning into memory access, exploring candidate retrieval paths, pruning irrelevant branches, and selecting next steps by information gain.This makes memory search dynamically responsive to intermediate evidence rather than fixed after an initial retrieval.
  • MRAgent: The Cue–Tag–Content memory graph uses associative tags to mediate retrieval between cues and content, enabling promising-path exploration and irrelevant-branch pruning.The graph provides the structured memory representation needed for associative reconstruction.
  • Evidence: MRAgent’s active retrieval policies are theoretically strictly more expressive than passive retrieval, and experiments show improved token and runtime efficiency over strong baselines.The introduction presents both a theoretical analysis and extensive empirical evaluation as evidence for the framework’s effectiveness.

2. Problem Setting: Active Memory Access

The section formulates memory retrieval as sequential selection from external memory and contrasts passive query-conditioned retrieval with active access conditioned on accumulated evidence. It shows that static similarity retrieval and fixed graph expansion introduce noise, miss disconnected evidence, and cannot revise strategies during reasoning.

  • Sequential Memory Access: Memory access sequentially selects units from external memory over T steps while accumulating evidence S(t).The formulation distinguishes memory access policies by whether selection depends only on the query or on evolving evidence.
  • Passive Retrieval: Passive retrieval selects memory units solely from the query, making memory a static context provider with a fixed relevance function.Similarity-based systems such as Memory-Bank and Mem0 exemplify this paradigm.
  • Similarity-based Retrieval: Similarity-based retrieval can return many surface-relevant events while adding substantial noise and missing the correct evidence.The example retrieves events related to “video game tournament” but fails to find the needed evidence.
  • Graph-based Memory Retrieval: Fixed N-hop graph expansion alleviates some multi-hop challenges but requires explicit links, adds irrelevant neighbors, and misses disconnected evidence.In the example, expansion fails to recover information about Caroline because she is not directly connected.
  • Active Memory Reconstruction: Active reconstruction integrates LLM reasoning into memory access, infers retrieval cues from intermediate findings, and adapts traversal using accumulated evidence.This enables retrieval constraints to be revised during access and can recover evidence unreachable under passive policies.

3. Associative Memory System

MRAgent organizes memory as a heterogeneous Cue–Tag–Content graph in which typed associative tags connect fine-grained cues to specific memory contents. Its multi-granular layers and two-stage tag-conditioned retrieval support selective, reconstructive access across episodic events, semantic knowledge, and topic abstractions.

  • Unified Memory System: MRAgent models memory as a heterogeneous graph M = (C, V, R) containing fine-grained cue nodes and content nodes storing specific memory items.Cues include entities or attributes, while contents represent individual memory items.
  • Unified Memory System: Typed relations R ⊆C×G×V connect each cue to a content node through an associative Tag that summarizes their semantic or relational link.Tags serve as explicit intermediates between cues and content units.
  • Associative Tags: Two-stage retrieval first selects relevant tags and then retrieves content conditioned on the selected cue–tag pair, decoupling associative reasoning from content-level access.The operators ϕc→g and ϕ(c,g)→v make selective retrieval tractable in large graphs.
  • Associative Tags: Tags guide traversal and enable branch pruning, avoiding the combinatorial explosion and irrelevant-memory inclusion caused by unconstrained n-hop expansion.This allows the agent to evaluate associative paths before processing full episodic content.
  • Multi-Granular Memory Layers: The memory graph spans episodic, semantic, and abstraction layers that respectively support event-specific reasoning, stable knowledge access, and top-down topic-to-episode navigation.Episodes are time-organized, semantic nodes encode stable attributes or facts, and topics summarize recurring patterns across episodes.

4. MRAgent: Reconstructive Memory Agent

MRAgent treats memory access as active reconstruction over a structured graph, using explicit states, LLM-selected traversal, and evidence-based routing. Its theory shows that active retrieval is strictly more expressive than passive retrieval for budgets T ≥2.

  • Reconstruction State: MRAgent maintains an explicit reconstruction state whose active memory elements guide traversal and whose accumulated context conditions subsequent directions.The active set contains cues, tags, and contents; the reconstructed context contains evidence accumulated in previous steps.
  • Traversal Actions: Traversal actions compose forward and reverse mappings across Cue–Tag–Content relations, enabling memory expansion, refinement, and redirection.Actions include Cue→Tag, (Cue,Tag)→Content, and Content→(Cue,Tag).
  • Memory Reconstruction Process: Given a query, MRAgent initializes cues and iteratively uses LLM reasoning to select promising traversal actions conditioned on the current state and accumulated evidence.Conditioning on H(t) allows discovery of new cues and dynamic adjustment of the reasoning trajectory.
  • Memory Reconstruction Process: The system generates candidates through selected operators, then routes among them to retain relevant content, prune irrelevant branches, and determine whether further exploration is needed.This avoids exhaustive graph expansion while keeping accumulated context concise and focused.
  • Memory Reconstruction Process: MRAgent integrates LLM reasoning directly into multi-turn reconstruction, using selective evidence expansion to reduce noise and flexibly adjust the reasoning trajectory.The process adapts memory access based on intermediate evidence rather than relying on predefined traversal.
  • Expressivity Analysis: For any retrieval budget T ≥2, the passive hypothesis class is strictly contained in the active hypothesis class.Active retrieval can implement every function available to passive retrieval, but passive retrieval cannot implement every active function.

5. Experiments

Experiments on LoCoMo and LongMemEval show that MRAgent consistently improves memory reasoning over representative baselines while reducing token consumption. Ablations and multi-turn analyses attribute these gains to associative memory structure, active reasoning, and adaptive evidence-guided reconstruction.

  • Experimental Setup: MRAgent is evaluated on LoCoMo and LongMemEval against RAG, LangMem, A-Mem, MemoryOS, and Mem0 using Gemini-2.5-Flash and Claude-Sonnet-4.5.Evaluation reports F1, GPT-4o-mini LLM-Judge scores, and evidence recall.
  • Overall Performance: 84.21 overall J under Gemini improves over 68.31, a 23.3% relative gain; Claude yields a 12.4% improvement, while LongMemEval improves 32% over the strongest baseline.The reported gains hold across question types and backbones.
  • Overall Performance: MRAgent’s Cue–Tag–Content graph uses associative tags to guide semantically relevant retrieval, while LLM reasoning adaptively reconstructs evidence through focused retrieval paths.This combines semantic guidance with evidence-guided traversal rather than passive retrieval.
  • Computational Cost: 118k prompt tokens versus A-Mem’s 632k demonstrates MRAgent’s information-efficiency advantage through lightweight construction and query-specific, on-demand relation building.Selective access avoids expensive processing of irrelevant episodic content.
  • Ablation Study: Reasoning variants consistently outperform structure-only variants, while performance without reasoning improves monotonically from CE to CTE to CTC and removing semantic memory degrades results.The ablation identifies active traversal, associative tags, and complementary episodic-semantic layers as important components.
  • Multi-Turn Reasoning: Multi-hop recall improves by over 30% across successive reasoning steps, and Max Valid Turns closely matches Average Turns, indicating adaptive continuation and termination.Single-hop and temporal queries reach near-perfect recall within approximately three turns.

6. Related Work

Prior work advances retrieval-augmented generation, graph-based memory, and persistent memory organization, but these approaches differ in how they structure memory and adapt retrieval during reasoning.

  • Retrieval-Augmented Generation: RAG uses similarity search over an unstructured vector store for one-shot query-time top-k retrieval, while GraphRAG adds graph structures, community summaries, and neighborhood expansion.These variants target improved global and multi-hop reasoning over flat similarity search.
  • Retrieval-Augmented Generation: Agentic RAG moves retrieval inside the reasoning loop, issuing on-demand queries when knowledge gaps appear and refining documents before integrating them into reasoning.Search-o1 uses this mechanism, while Search-R1 trains multi-turn query generation through reinforcement learning.
  • Graph-based Memory: Graph-based memory systems organize agent memory as graphs that capture structural dependencies among memory units through relation extraction, temporal tracking, or seed-based neighborhood expansion.A-Mem uses LLM-assisted relation extraction, and Zep maintains a bi-temporal knowledge graph that invalidates outdated edges.
  • Hierarchical and Persistent Memory Systems: Hierarchical and persistent memory systems continually update long-lived memory across interactions using temporal hierarchies, salient-fact operations, or topically coherent segments.MemoryOS separates short-, mid-, and long-term memory; Mem0 performs add, update, and delete operations; SeCom stores topical segments.

7. Conclusion and Discussion

MRAgent treats memory access as an active, multi-step reconstruction process over a structured memory graph, shifting complex relational modeling to retrieval. This targeted, state-dependent exploration supports more complex queries with lower computational cost, while using a relatively simple memory construction strategy.

  • Conclusion and Discussion: MRAgent formulates memory access as active, multi-step reconstruction over a structured memory graph.This is the framework’s central design choice.
  • Conclusion and Discussion: Shifting complex relational dependency modeling to retrieval enables targeted, state-dependent exploration for resolving more complex queries with lower computational cost.The approach adapts exploration to the retrieval state rather than relying solely on memory construction.
  • Conclusion and Discussion: The current implementation adopts a relatively simple memory construction strategy.This follows from moving complex relational modeling to the retrieval stage.

Impact Statement

The work advances long-horizon memory reasoning through an active, reconstructive paradigm, with potential benefits for reliable, context-aware AI assistants. Persistent memory also raises privacy, data-governance, and responsible-deployment concerns.

  • The active, reconstructive paradigm could improve reliable, context-aware AI assistants for personal assistance, decision support, and long-term human–AI interaction.These applications depend on accurate recall and reasoning over past information.
  • Persistent storage and reasoning over long-term interaction data require attention to privacy, data governance, and responsible deployment.The concerns apply broadly to memory-augmented AI systems, not specifically to this method.

A. Detailed Analysis of Passive Retrieval

Existing memory systems use passive retrieval procedures that return fixed or predefined memory selections, with access mechanisms coupled to their underlying representations. These methods include similarity-based, graph-based, and hierarchical retrieval, but do not adapt traversal to intermediate inference evidence.

  • Unified Retrieval Formulation: The unified formulation distinguishes passive retrieval, which returns a fixed set πp(x), from active reconstruction, which selects memory units sequentially through a stateful policy.Memory access operates over external memory M with units V = {v1, . . . , vN}.
  • Similarity-Based Retrieval: RAG performs single-shot similarity search over a vector-store memory and retrieves the top-k items most similar to query x.It computes relevance between x and every memory unit v ∈V.
  • Graph-Based Retrieval: A-Mem selects a similarity-based seed memory item and expands its predefined graph neighborhood.The neighborhood operator returns nodes directly connected to the seed set.
  • Hierarchical Retrieval: MemoryOS performs hierarchical retrieval by combining short-term context, mid-term topic memories, and long-term persona information.Its hierarchy comprises STM, MTM, and LPM; LPM represents persona information and query-conditioned long-term factual memory.
  • Limitations of Passive Retrieval: Existing systems primarily design memory representations while coupling retrieval to those structures through fixed similarity or graph-based procedures that do not adapt to intermediate evidence.The conclusion characterizes these retrieval processes as passive because traversal operators are predefined and fixed.

B. Implementation and Execution Details … C.5. A separating task family: Binary-Tree Needle-in-a-Haystack

MRAgent constructs a heterogeneous memory graph from episodic, semantic, and topic-level abstractions, then actively reconstructs relevant context through LLM-controlled traversal. Theoretical analysis formalizes adaptive retrieval and proves its strict advantage over passive retrieval using a binary-tree task family.

  • B.1. Memory Construction Pipeline: Raw dialogue is rewritten to resolve dependencies, normalized temporally, segmented into episodes, and converted into Cue–Tag–Episode triplets with associative tags and fine-grained cues.RLLM processes the text; TLLM summarizes episode-level patterns; KLLM extracts entities, attributes, and salient descriptors.
  • B.1. Memory Construction Pipeline: Semantic memory adds stable facts and attributes as Cue–Tag–Semantic units, linking entity-level cues and aspect-level tags within the same graph.SLLM identifies stable information, summarizes semantic content, and assigns entity-level cues before graph insertion.
  • B.1. Memory Construction Pipeline: Topic nodes summarize recurring semantic patterns across episodes and connect to associated episodes, enabling higher-level reasoning when fine-grained traversal is unnecessary.Topics provide a higher-level organization for multi-granular reasoning.
  • B.2. Executable Memory Reconstruction: MRAgent executes LLM-determined traversal actions through a specialized toolkit that progressively explores the graph, accumulates evidence, and switches from Navigate to Answer mode.The agent generates its final response after sufficient evidence is collected and the context is reconstructed.
  • B.2. Executable Memory Reconstruction: Typed traversal tools let the LLM control memory-access direction and granularity, composing sequential or parallel invocations according to the evidence gathered so far.This replaces retrieval of a fixed memory set with progressive context reconstruction.
  • C.1. Setup: The theory models a heterogeneous KG with typed nodes, textual payloads, labeled relations, and a node-retrieval operator returning payloads plus at most B outgoing neighbors.The setup generalizes MRAgent’s cue–tag–episode memory to arbitrary heterogeneous knowledge graphs.
  • C.2. Population risk and approximation error: Population risk and approximation error are defined under 0–1 loss, with εY representing the minimum error achievable from the label prior alone.This prior-only quantity serves as the baseline when retrieval provides no additional information.
  • C.3. Active vs. passive retrieval; C.4. Main theorem: active retrieval is strictly more powerful than passive: Active policies condition each retrieval query on the full history, whereas passive policies condition queries only on the original query; for any T ≥2, active retrieval strictly contains passive retrieval.The theorem establishes a strictly larger predictor class for adaptive retrieval, while passive policies remain representable as history-ignoring active policies.

C.6. Active retrieval achieves zero error … D.5. Detailed Results on LONGMEMEVAL

The theoretical results show that active retrieval can achieve zero error with a linear retrieval budget, whereas passive retrieval has irreducible error unless its budget is exponential. Experiments evaluate long-term memory systems on LoCoMo and LongMemEval using judge-based answer metrics and detailed LongMemEval settings.

  • C.6. Active retrieval achieves zero error: Active retrieval reaches the target leaf in at most d + 1 retrievals and is correct for every sample under Dn,d.The strategy follows retrieved next-bit values to select each child before reading the target payload.
  • C.7. Passive retrieval has irreducible error unless the budget is exponential: Passive policies choose retrieval nodes from x alone, so they cannot identify the uniformly hidden target leaf without sufficient coverage.If the target payload is not retrieved, the transcript is independent of y and prediction incurs error at least εY.
  • C.8. Strictness and approximation-theoretic separation: Active hypothesis classes strictly contain passive classes for every T ≥2, because active retrieval can attain zero error where passive retrieval retains a strict gap.Passive policies are a special case of active policies whose query functions ignore retrieval history.
  • D.1. Datasets: LoCoMo evaluates long-term conversational memory across 50 conversations spanning up to 35 sessions, with approximately 300 turns and 200 question–answer pairs per conversation.Its questions include single-hop, multi-hop, temporal, and open-domain categories.
  • D.1. Datasets: LongMemEval-S contains approximately 500 questions paired with chat histories of around 115K tokens, testing recall and reasoning over timestamped sessions.Each evaluation instance ends with a question requiring reasoning over the interaction history.
  • D.2. Baselines: The baselines span vector retrieval, graph-based memory, hierarchical memory, and LLM-managed memory systems, including RAG, A-Mem, MemoryOS, LangMem, and Mem0.Their retrieval procedures use similarity search, graph-neighbor expansion, hierarchical access, summarization, or fact-based memory updates.
  • D.3. Evaluation Metric: Evaluation uses an LLM judge for semantic answer correctness, reports F1 from judge decisions, and measures Evidence Recall for retrieved supporting evidence.Evidence Recall evaluates retrieval effectiveness independently of final answer generation.
  • D.4. Implementation / D.5. Detailed Results on LONGMEMEVAL: Each method is evaluated three times with GPT-4o-mini at temperature 0.0, while reasoning is capped at 8 turns per query and 10 tool invocations per turn.Table 5 reports detailed LONGMEMEVAL results under different settings using F1 and LLM-Judge.

D.6. Budget Sensitivity Analysis of Multi-step Reconstruction … E. Prompt

The ablations show that deeper multi-step reconstruction matters more than wider single-turn retrieval, while operator specialization and structured prompting support evidence-driven memory reasoning. Case-study evidence illustrates how iterative associative, semantic, and temporal exploration resolves cross-session questions.

  • D.6. Budget Sensitivity Analysis of Multi-step Reconstruction: Reasoning depth improves multi-hop LOCOMO accuracy monotonically across retrieval budgets, whereas increasing per-turn parallel retrieval yields limited, quickly saturating gains.The analysis varies reasoning turns T and per-turn retrieval budget K under fixed settings.
  • D.6. Budget Sensitivity Analysis of Multi-step Reconstruction: Parallel exploration broadens retrieval within one reasoning turn but cannot substitute for deeper reconstruction.Performance is evaluated on multi-hop LOCOMO queries under the Claude backbone using LLM-Judge.
  • D.7. Evidence Coverage by Retrieval Operators: Retrieval operators specialize by question structure: temporal questions primarily use conversation time, while multi-hop questions rely on tag and topic events.The coverage analysis aggregates each tool’s evidence coverage by question category on LOCOMO.
  • D.7. Evidence Coverage by Retrieval Operators: Open-domain questions show more balanced coverage across retrieval operators.Table 6 reports individual-operator coverage rates under the Claude backbone.
  • D.8. Case Studies: MRAgent reconstructs cross-session evidence by traversing tag associations, expanding event context and keywords, and querying semantic and temporal information.The case study concerns identifying Joanna’s screenplays rejected by production companies.
  • D.8. Case Studies: After five reasoning steps, MRAgent correctly infers that Joanna’s first and third screenplays were rejected.The example combines associative expansion with semantic and temporal verification.
  • E. Prompt: The QA prompt directs the agent to answer when evidence is sufficient and otherwise navigate memory tools, using question-specific output rules and confidence-bearing JSON.It specifies formats for yes/no, location, counting, and other questions, including supporting evidence identifiers.
  • E. Prompt: The preprocessing prompts enforce explicit, structured memory representations through exact keyword extraction, pronoun resolution, concrete tags, normalized dates, topics, and origin-preserving IDs.Dialogue processing also preserves sentences, merges adjacent answered questions, and extracts normalized personal facts.
Loading 2606.06036v1…