PaperlayerView exact revision on arXiv

Source-linked AI summary

Memex(RL): Scaling Long-Horizon LLM Agents via Indexed Experience Memory

Zhenting Wang, Huancheng Chen, Jiayun Wang, Wei Wei

arXiv:2603.04257v1cs.CLcs.LG

TL;DR

Long-horizon agents struggle with finite context windows because accumulated tool interactions become too long, while truncation and summaries can lose evidence. Memex pairs compact indexed summaries with full-fidelity external memory, and MemexRL learns compression and retrieval behavior. Across challenging long-horizon tasks, the trained agent improves success while using a smaller working context.

  • Problem

    Finite context windows make growing long-horizon trajectories difficult to retain and use, while truncation and lossy summaries can discard past evidence.

  • Method

    Memex stores compact indexed summaries in context and full-fidelity artifacts externally, while MemexRL learns when to write, archive, index, and retrieve experience.

  • Results

    MemexRL improves task success while using a significantly smaller working context across challenging long-horizon tasks.

  • Takeaways & Limitations

    Indexed experience memory provides a less lossy long-horizon memory mechanism by recovering exact archived evidence through bounded explicit dereferencing.

Abstract

from arXiv · show

Large language model (LLM) agents are fundamentally bottlenecked by finite context windows on long-horizon tasks. As trajectories grow, retaining tool outputs and intermediate reasoning in-context quickly becomes infeasible: the working context becomes prohibitively long, eventually exceeds the context budget, and makes distant evidence harder to use even when it is still present. Existing solutions typically shorten context through truncation or running summaries, but these methods are fundamentally lossy because they compress or discard past evidence itself. We introduce Memex, an indexed experience memory mechanism that instead compresses context without discarding evidence. Memex maintains a compact working context consisting of concise structured summaries and stable indices, while storing full-fidelity underlying interactions in an external experience database under those indices. The agent can then decide when to dereference an index and recover the exact past evidence needed for the current subgoal. We optimize both write and read behaviors with our reinforcement learning framework MemexRL, using reward shaping tailored to indexed memory usage under a context budget, so the agent learns what to summarize, what to archive, how to index it, and when to retrieve it. This yields a substantially less lossy form of long-horizon memory than summary-only approaches. We further provide a theoretical analysis showing the potential of the Memex loop to preserve decision quality with bounded dereferencing while keeping effective in-context computation bounded as history grows. Empirically, on challenging long-horizon tasks, Memex agent trained with MemexRL improves task success while using a significantly smaller working context.

1. Introduction

Long-horizon agents outgrow finite context windows, while truncation and lossy summaries discard or obscure evidence. Memex instead keeps compact indexed summaries in context and archives recoverable details externally, with MemexRL learning when to compress and retrieve.

  • Long-horizon workflows accumulate observations, tool outputs, and reasoning until prompts become inefficient or exceed finite context budgets.
  • Truncation and summarization reduce working context but can discard substantial interaction history or make past evidence difficult to recover faithfully.
  • Memex replaces long trajectories with compact indexed summaries while archiving full-fidelity artifacts in an external key–value store for later dereferencing.
  • The agent can explicitly retrieve exact archived content when a past result becomes relevant, separating compact working context from external experience.
  • MemexRL treats writing summaries, archiving artifacts, and dereferencing indices as decision actions whose benefits may appear many steps later.
  • Theoretical analysis characterizes bounded dereferencing and bounded effective in-context computation as potentially sufficient for accurate decisions as histories grow.

2. Related Work

Prior LLM memory systems organize and compress information beyond immediate context, but preserving salient information during efficient compression and retrieval remains unresolved for long-horizon agents.

  • LLM memory research aims to store, organize, and retrieve information beyond models’ immediate context.
  • Early frameworks such as MemGPT and MemoryBank organize dialogue history, accumulate experience, and update memory across interactions.
  • Long-term LLM-agent memory is broadly categorized into factual memory and experiential memory.
  • A central challenge is preserving salient information while enabling efficient compression and retrieval.
  • Finite context windows make accumulated long-horizon trajectories inefficient or infeasible and increase difficulty using distant information.

3. Memex Agent

Memex maintains a compact indexed working context alongside an external archive of exact experience blocks, then compresses and retrieves those blocks through explicit memory operations. Its training setup handles changing prefixes after compression and supports both authored summaries and verbatim span extraction.

  • 3.1. Overview: Indexed Experience Memory keeps compact actionable state in context while preserving full-fidelity artifacts in an external store under stable indices.
  • 3.2. Indexed Experience Memory: The indexed summary combines compact progress state with index–description pairs that point to archived content.
  • 3.2. Indexed Experience Memory: The external store maps stable indices to archived blocks such as tool outputs, traces, and code snippets, accessible through explicit dereferencing.
  • 3.2. Indexed Experience Memory: CompressExperience writes memory blocks to the external store and rewrites the working context to the fixed anchors plus an indexed summary.
  • 3.2. Indexed Experience Memory: ReadExperience retrieves an indexed block and appends it to the working context as a new message.
  • 3.2. Indexed Experience Memory: Memory blocks support direct authoring of notes or anchor-based extraction that archives matched spans verbatim for precise artifacts.
  • 3.3. MemexRL: Segmented trajectory processing treats post-compression segments as independent training samples because compression changes the conditioning prefix.

4. Theoretical Analysis of Why the Memex Loop Scales to Long-Horizon Agents

The theoretical analysis characterizes when indexed summaries and bounded dereferencing can preserve full-context decision quality while keeping effective in-context computation bounded as history grows. These guarantees require decision-sufficient summaries and bounded archive reads at each step.

  • Property 1: Preserving decision quality with bounded dereferencing: A B-bounded decision-sufficient summary lets an index selector recover the optimal action using at most B archived evidence blocks.The summary need not contain all past evidence; it must identify the small subset relevant to the current decision.
  • Property 1: Preserving decision quality with bounded dereferencing: Under this sufficiency assumption, a Memex policy can match the expected return of a full-context optimal policy while conditioning only on the indexed summary and bounded dereferences.The policy selects indices, reads the corresponding archive blocks, and applies the decision function to the summary and retrieved evidence.
  • Property 2: Keeping working context bounded as trajectory grows: Memex keeps the working context to the indexed summary plus the blocks read at the current step rather than the full message history.The external experience store retains archived content while the in-context state contains the summary and dereferenced blocks.
  • Property 2: Keeping working context bounded as trajectory grows: If summary length, dereferenced indices, and retrieved-block sizes are bounded, the working context remains bounded as full history grows, implying bounded effective in-context computation.The conclusion relies on a compact summary and only a bounded number of explicitly retrieved archive blocks at each step.
  • Empirical training dynamics: During training, task success rises from approximately 20% to over 90%, while total penalty improves from −0.4 to approximately −0.1.These rollout trends are reported as evidence that the agent learns task execution and working-context management.

5. Empirical Results for MemexRL

On modified ALFWorld, MemexRL improves long-horizon task performance while reducing peak working context. The learned policy uses memory more selectively, relying increasingly on retrieval rather than repeated compression.

  • Effectiveness: 24.2% to 85.6%: task success rate improves while peak working context falls from 16,934 to 9,634 tokens.The post-training context length approaches the 8,000-token penalty threshold.
  • Experiments Setup: MemexRL is evaluated against a non-RL Memex agent on the modified ALFWorld benchmark.The environment is a harder version of ALFWorld designed to evaluate long-horizon memory agents.
  • Effectiveness: During training, rollout task success rises from approximately 20% to over 90%, while total penalty improves from around −0.4 to approximately −0.1.These trends indicate simultaneous improvement in task completion and working-context management.
  • Effectiveness: The results indicate that MemexRL learns indexed-memory usage that supports downstream reasoning under a constrained context budget, rather than merely compressing more aggressively.The policy shifts from repeatedly rewriting context toward dereferencing reusable indexed experience.
  • Effectiveness: CompressExperience calls decrease from about 6.5 to 3, while ReadExperience calls increase from about 1 to around 6–7 after training.The learned behavior is selective compression combined with explicit retrieval of previously observed evidence.

6. Conclusion

Memex separates compact indexed summaries from full-fidelity external artifacts, while MemexRL learns when to compress, index, and retrieve them. Across challenging long-horizon tasks, this improves task success with a smaller working context.

  • Conclusion: Memex separates compact in-context indexed summaries from full-fidelity artifacts stored under stable indices in an external experience database.The agent keeps actionable state in context and dereferences exact evidence when needed.
  • Conclusion: MemexRL learns compression and retrieval behaviors through reward shaping tailored to indexed memory usage and segmented trajectory processing.The framework addresses episodes containing multiple compressions.
  • Conclusion: Across challenging long-horizon tasks, Memex improves task success while using a significantly smaller working context.The conclusion presents learning to summarize, index, and dereference experience as a complementary scaling axis for LLM agents.

A. Additional Proofs for Theoretical Analysis

The appendix provides full proofs formalizing Memex’s two central theoretical properties: bounded dereferencing can preserve decision quality, while working context remains bounded as history grows.

  • Additional Proofs for Theoretical Analysis: The appendix gives full proofs for the two theoretical results introduced in the main paper.These results concern decision quality and working-context boundedness.
  • Additional Proofs for Theoretical Analysis: The theoretical results formalize preserving decision quality through bounded explicit dereferencing.The property is stated as part of Memex’s theoretical analysis.
  • Additional Proofs for Theoretical Analysis: The theoretical results formalize keeping working context bounded even as the full message history grows.This is the second central property emphasized in the main paper.

A.1. Proof of Optimality Equivalence with Bounded Dereferences (Proposition 1)

Under the B-bounded decision-sufficiency assumption, a Memex policy can retrieve at most B indexed blocks per step and reproduce the optimal full-context policy’s decisions and expected return.

  • Proof of Optimality Equivalence with Bounded Dereferences: A selector g chooses an index set I_t from the Memex state with |I_t| ≤ B, and the corresponding archived blocks form R_t.The assumption supplies the bounded set of dereferences used for decision making.
  • Proof of Optimality Equivalence with Bounded Dereferences: The Memex policy selects g(σ_t), reads the associated archived blocks, and applies the decision function μ to the compact state and retrieved content.This constructs π_IEM from the bounded selector and the decision rule.
  • Proof of Optimality Equivalence with Bounded Dereferences: The constructed Memex policy induces exactly the same action distribution as the optimal full-context policy for all reachable states.The equality is established under the stated decision-sufficiency assumptions.
  • Proof of Optimality Equivalence with Bounded Dereferences: Equal action distributions imply equal trajectory distributions under the same environment dynamics and equal expected return, J(π_IEM) = J(π*).The proof transfers policy equivalence to expected performance.
  • Proof of Optimality Equivalence with Bounded Dereferences: The Memex policy uses at most B ReadExperience calls per step while matching the optimal full-context policy’s performance.The dereference bound follows directly from |g(σ_t)| ≤ B.

A.2. Proof of Bounded Working Context (Proposition 2)

Under bounded indexed-summary length, dereference count, and retrieved-block size, Memex keeps working-context length uniformly bounded as message history grows without bound. Consequently, its compression ratio grows and effective in-context computation remains bounded.

  • Proof: The proof bounds working-context length by separately bounding indexed-summary length, dereferenced blocks, and each retrieved block.The assumptions are |σ_t| ≤ τ_σ, |I_t| ≤ B, and retrieved-block length at most L.
  • Proof: Working-context length is uniformly bounded for all t.
  • Compression ratio: The compression ratio grows at least linearly with the full message history length.
  • Compression ratio: As total message history grows without bound, the compression ratio satisfies ρ_t→∞ while working context remains bounded.
  • Effective computation: Because the system prompt and task instruction are fixed, bounded working context also implies bounded effective in-context computation.

B. Details of the Used Prompts

The prompts define an interactive household-task agent that must manage context through compression and indexed retrieval while avoiding context overflow and redundant actions. They specify how to store summaries and precise content, retrieve archived experience, and navigate ALFWorld tasks.

  • Task setting: The prompt frames the agent as completing household tasks by navigating rooms, interacting with objects, and manipulating them appropriately.
  • Task execution: ALFWorld instructions cover navigation, object manipulation, opening containers, and systematic movement from object discovery to placement.
  • Interaction protocol: Every response must contain a tool call, and execute_action is required for environment interactions, with finish reserved for task completion.
  • Context management: The agent must keep working context below a threshold, monitor context status after observations, compress before overflow, and avoid redundant identical tool calls.
  • Compression and retrieval: CompressExperience replaces prior messages with a summary while storing content blocks under indices for later retrieval.
  • Compression and retrieval: The summary contains a short index map, while db_blocks store precise details such as exact IDs and values needed later.
  • Compression and retrieval: The prompts include manual summaries or anchor-based extraction, with short unique start, middle, and end anchors required for automatic extraction.
  • Compression and retrieval: After compression, the agent must use ReadExperience with an exact index to recover archived information instead of rerunning tools.
Loading 2603.04257v1…