MemoryArena (He et al., 2026) showed that state-of-the-art long-term memory systems for LLM agents fail when memory must support sequential decision-making across interdependent multi-session tasks, and framed that failure as a POMDP belief-tracking problem: memory should preserve the task-relevant sufficient statistics from past sessions so the agent can act as if the task were fully observed. The follow-up literature since its release — direct MemoryArena evaluations, belief-style and state-tracking memory methods, a trainable memory-update environment, and a formal theory of agent memory — does not close the core: designing and jointly training memory that preserves belief-sufficient state in multi-session agentic tasks, together with evaluation that measures belief fidelity directly, remains open — travel planning in MemoryArena still sits at zero success for every evaluated system.

Background

Large language model (LLM) agents act in an environment by issuing tool calls and receiving observations over many steps. To operate across sessions, they rely on long-term memory systems — external stores such as MemGPT, Mem0, or retrieval-augmented generation (RAG) pipelines that compress, consolidate, and retrieve past interaction traces, instead of keeping the full history in the model's context window. Existing benchmarks evaluate either memorization (recall of past conversations, e.g. LoCoMo — a long-term conversational-memory benchmark of Maharana et al., 2024) or single-session action, but not their coupling.

MemoryArena (He et al., 2026) is a benchmark of human-crafted agentic tasks split into interdependent subtasks delivered across multiple sessions, spanning bundled web shopping, preference-constrained group travel planning, progressive web search, and sequential formal reasoning. Because later subtasks depend on latent state accumulated in earlier sessions (e.g. which products were already bought, which group-member constraints were stated), the multi-session loop is naturally a partially observable Markov decision process (POMDP): a decision problem in which the agent never directly observes the full task state, only partial observations. In a POMDP, an optimal policy can be expressed over the belief state — the posterior distribution over the latent state given the full interaction history — which yields the belief-MDP reduction: acting optimally over the belief state is equivalent to acting in a fully observed problem. A statistic of the history is sufficient if it supports exactly this reduction; the paper's idealization is a memory that "returns all and only the information necessary to infer the current belief state", i.e. the task-relevant sufficient statistics from past sessions.

Empirically, MemoryArena reports that all evaluated paradigms — long-context agents (full verbatim history in the prompt), external-memory systems, and RAG systems — achieve low Task Success Rate (SR, the fraction of tasks fully solved) and Process Score (PS, the fraction of subtasks completed), with SR decaying as subtask depth grows; the paper interprets this decay as belief drift: small errors in the agent's implicit state estimate accumulate across sessions and eventually dominate downstream decisions. External memory, optimized for generic recall, compression, or semantic-similarity retrieval, does not reliably preserve and update the task-relevant state variables needed for belief tracking (a memory-side bottleneck), and task agents are not trained to query, interpret, and integrate retrieved memory as structured cues for belief updates (an agent-side bottleneck). A classical precedent for the theory exists — Toro Icarte et al. (2020) studied finite external-memory classes (e.g. k-bit memories) in small discrete POMDPs and left open which memory classes help which partially observable problems — but that line predates LLM agents and does not address the interdependent multi-session setting. MemoryArena also measures execution latency: external-memory agents incur the highest per-subtask latency, yet memory-operation complexity does not predict end-to-end latency, so effectiveness and latency must be traded off explicitly.

Problem Statement

In the setting of MemoryArena — agentic tasks composed of interdependent subtasks delivered across multiple sessions, where later subtasks depend on latent state accumulated in earlier ones — design and validate memory systems that make external memory support belief-state estimation, so that a memory-augmented agent approaches the performance of an agent acting with an oracle memory (a memory given direct access to the accumulated ground-truth task state). The paper's idealized criterion is that memory returns all and only the task-relevant sufficient statistics from past sessions, enabling the agent policy to act as if the task were fully observed (the belief-MDP reduction). Concretely, the problem comprises four jointly required, scientifically linked components, all of which must be addressed: (1) memory representations together with update, consolidation, and retrieval algorithms that preserve and correctly revise the task-relevant state variables needed for belief tracking under each task's dependency structure, with an operational or formal criterion of when stored content is sufficient for the current belief state; (2) training regimes in which the task agent and the memory mechanism are optimized jointly, so that the agent learns effective query strategies and integrates retrieved or compressed memory as structured cues for belief updates rather than under- or mis-using them; (3) evaluation and learning objectives that measure belief fidelity directly — diagnosing belief drift across sessions rather than only end-task success rate and process score; and (4) treatment of the trade-off between memory effectiveness and execution latency under repeated session access. The research target additionally requires empirically validating all four components — (1) the algorithms together with the sufficiency criterion they implement, (2) the joint training regime, (3) the objective that measures belief fidelity directly, and (4) the measured effectiveness-versus-latency comparison — and demonstrating a strictly positive, reproducible improvement in Task Success Rate over the full-interaction-history reference on the MemoryArena suite, aggregated across its domains with per-domain results, that is, a positive fraction of the oracle-versus-full-history gap rather than merely reproducing that reference; the gain must be attributable to the mechanism rather than to incidental scale or context length, by at least one empirical instrument: belief-fidelity metrics or controlled interventions such as ablations. Approaching the oracle-memory (fully observed) upper bound is the aspirational target.

References

  1. He, Zexue; Wang, Yu; Zhi, Churan; Hu, Yuanzhe; Chen, Tzu-Ping; Yin, Lang; Chen, Ze; Wu, Tong Arthur; Ouyang, Siru; Wang, Zihan; Pei, Jiaxin; McAuley, Julian; Choi, Yejin; Pentland, Alex (2026). "MemoryArena: Benchmarking Agent Memory in Interdependent Multi-Session Agentic Tasks." arXiv:2602.16313, DOI 10.48550/arxiv.2602.16313. https://arxiv.org/abs/2602.16313
  2. Chen, Yaoqi; Lai, Haibin; Feng, Yuru; Han, Chuyu; Zhang, Qianxi; Lu, Baotong; Li, Menghao; Wang, Xinjiang; Wang, Zhirui; Xu, Shusen; Li, Zengzhong; Jin, Zewen; Wu, Hao; Li, Cheng; Chen, Qi (2026). "Beyond Semantic Organization: Memory as Execution State Management for Long-Horizon Agents." arXiv:2606.06090, DOI 10.48550/arxiv.2606.06090. https://arxiv.org/abs/2606.06090
  3. Zhan, Chaoqun; Zhou, Qiang; Li, Guannan; Huang, Zhenqiang; Wang, Qianjin (2026). "MemoryLake on MemoryArena: A Matched Study of Agent Memory Backends." arXiv:2608.13883, DOI 10.48550/arxiv.2608.13883. https://arxiv.org/abs/2608.13883
  4. Liao, Junfeng; Wang, Qizhou; Zhu, Jianing; Du, Bo; Yan, Rui; Chen, Xiuying (2026). "Belief Memory: Agent Memory Under Partial Observability." arXiv:2605.05583, DOI 10.48550/arxiv.2605.05583. https://arxiv.org/abs/2605.05583
  5. Fan, Xinyi; Liu, Miri; Yang, Ruozhen; Ouyang, Siru; Han, Jiawei (2026). "Can Agent Memory Systems Track Evolving State?" arXiv:2608.19652, DOI 10.48550/arxiv.2608.19652. https://arxiv.org/abs/2608.19652
  6. Patel, Vedant (2026). "Supersede: Diagnosing and Training the Memory-Update Gap in LLM Agents." arXiv:2606.27472, DOI 10.48550/arxiv.2606.27472. https://arxiv.org/abs/2606.27472
  7. Tang, Hongyao (2026). "Towards a Formal Definition of Agent Memory: Basis, Span, Optimality, and the Sequential Memory Problem." arXiv:2608.11654, DOI 10.48550/arxiv.2608.11654. https://arxiv.org/abs/2608.11654
  8. Toro Icarte, Rodrigo; Valenzano, Richard; Klassen, Toryn Q.; Christoffersen, Phillip; Farahmand, Amir-massoud; McIlraith, Sheila A. (2020). "The act of remembering: a study in partially observable reinforcement learning." arXiv:2010.01753, DOI 10.48550/arxiv.2010.01753. https://arxiv.org/abs/2010.01753
  9. Maharana, Adyasha; Lee, Dong-Ho; Tulyakov, Sergey; Bansal, Mohit; Barbieri, Francesco; Fang, Yuwei (2024). "Evaluating Very Long-Term Conversational Memory of LLM Agents." arXiv:2402.17753, DOI 10.48550/arxiv.2402.17753. https://arxiv.org/abs/2402.17753
  10. Zhao, Yujie; Yuan, Boqin; Huang, Junbo; Yuan, Haocheng; Yu, Zhongming; Xu, Haozhou; Hu, Lanxiang; Shankarampeta, Abhilash; Huang, Zimeng; Ni, Wentao; Tian, Yuandong; Zhao, Jishen (2026). "AMA-Bench: Evaluating Long-Horizon Memory for Agentic Applications." arXiv:2602.22769, DOI 10.48550/arxiv.2602.22769. https://arxiv.org/abs/2602.22769