acceptodds
Withdrawn from ICLR 2027

What Is Agent Memory? Definition, Storage, and Performance Prediction

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Memory ability (the capacity to store and recall information) is required by large language model (LLM) and reinforcement learning (RL) agents to complete complex tasks. While episodic and semantic memory are widely recognized as critical by psychology, neuroscience, and AI researchers, current analysis of LLM agents primarily describes the typical content stored in each type. However, analyzing content alone fails to capture the structural constraints that dictate deployment success. To address this, we propose a theory of episodic and semantic memory for AI agents, detailing the time and space complexity constraints of each. We prove that these memory types require fundamentally different storage structures with opposing efficiency requirements; for instance, simultaneously supporting fast () look-up for episodic tasks and minimal () space complexity for semantic tasks is mathematically impossible. Applying this theory, we analyze six popular memory mechanisms (including RAG, long-context transformers, and graph-based memory), categorizing their task-specific performance to provide practitioners with a tool for predicting deployment success and making efficient design choices. Finally, a meta-analysis of existing benchmarks demonstrates that correctly matching the memory mechanism to the task's requirements explains 11% of performance variance.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
memory, agents, LLM, LLM agents memory, semantic memory, episodic memory

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_64oFOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The authors investigate, both theoretically and empirically, how the structure of agent memory affects performance, rather than focusing on what content should be stored. They define episodic and semantic memory, theoretically characterize the tasks on which each operates optimally, and show that each can be suboptimal when applied to tasks suited to the other. They evaluate their theoretical analysis through 32 experimental configurations and conduct a meta-analysis of previously published results from various memory-based systems to examine whether the predicted trends hold.

Critical strengths
  • The paper clearly describes the memory structures using mathematical formulations and theoretically analyzes their behavior on different types of tasks.
  • The authors design experiments around the memory structures considered in their theoretical analysis to examine whether the predicted behavior is observed empirically.
  • The meta-analysis of results across multiple benchmarks provides additional evidence for their claims beyond the controlled experimental setting.
Critical weaknesses
  • Limited insight from the theoretical analysis of broadly defined memory structures. The paper considers episodic memory for episodic tasks that can be solved by retrieving a single element, and semantic memory that aggregates information across multiple memories. It then establishes that each is optimal for its corresponding task type and suboptimal for the other. However, these assumptions appear to describe rather trivial cases, making it difficult to identify what new insight the analysis provides.

  • Limited experimental evidence and an unclear connection to the theoretical analysis. The results in Section 6 do not clearly support the theoretical analysis. For example, HippoRAG with attributes, categorized as semantic memory, performs well on episodic benchmark tasks. Moreover, the assumed memory structures are defined so broadly that, even if a trend is observed, it is unclear whether it validates the paper’s theoretical claims or reflects other characteristics of the evaluated memory systems.

Questions for authors
  1. Why is the problem formulated as a POMDP? Is this intended to build on the settings in reinforcement learning where memory has traditionally been necessary?
  2. What motivates the conditions in Definition 2 as defining properties of stateful memory?
  3. The rendering of Equation (1) appears to need correction.
  4. In Figure 1(b), HippoRAG with attributes performs well on the episodic tasks. Do the authors have an analysis explaining this result?
  5. In Table 1, mechanism–task alignment appears particularly pronounced on LongMemEval_S. Do the authors have an analysis explaining why?
2 comments
AuthorsOpenReview ↗

Reply to Reviewer 64oF (1/2)

We thank the reviewer for the careful reading and for engaging with both the theory and the experiments.

"These assumptions appear to describe rather trivial cases, making it difficult to identify what new insight the analysis provides."

It is intuitive that a lookup structure suits lookup queries and an aggregating structure suits aggregation. We believe the framework still yields several predictions that do not follow from that intuition alone:

  1. Mismatch depends on scale. A mismatched mechanism is not uniformly worse. It can match an aligned mechanism until its cost exceeds the deployment budget, and only then fail (Lemma 6). This is the pattern in Fig. 1b and Fig. 4: semantic mechanisms match episodic ones at L1–L2, then degrade or run out of memory at L3–L4. One consequence is that benchmarks with short horizons can hide architectural mismatch entirely.
  2. Composite scores can hide regime effects. Memory AgentBench aggregates conflicting episodic and semantic sub-tasks into one score. It is the only benchmark in our meta-analysis with no alignment effect (Table 1), consistent with the framework's prediction.
  3. Transfer is asymmetric. An episodic mechanism that is optimal on one episodic task stays optimal across episodic tasks (Theorem 4). By contrast, we argue that no single semantic mechanism is optimal across all relational structures, even within the semantic regime (Theorem 5). The experiments show this asymmetry: context-based mechanisms do well on the FIFO/LIFO tasks but degrade on Shortest Path, while HippoRAG with Attributes improves graph tracking (Section 6.1).

We also note that, as discussed in our response to Reviewer g9FA, some of our formal results (notably Theorem 2) need to be restated. We do not rely on them here.

"HippoRAG with attributes, categorized as semantic memory, performs well on episodic benchmark tasks." and "Do the authors have an analysis explaining this result?"

Yes. Our mechanism definitions (Definitions 6 and 7) are defined over how a mechanism stores the task’s sufficient statistic A = (A₁, …, Aₙ) (Section 3.3), not over the mechanism’s architecture alone. A mechanism is semantic for a task when it maintains a joint encoding of that task’s Aᵢ, and episodic when it stores each Aᵢ in isolation under its key. On Edge Presence and Inventory Ledger (Snapshot), HippoRAG with Attributes stores the sufficient statistic in isolation, so on these tasks it acts as an episodic mechanism:

  • Edge Presence. The sufficient statistic is the current presence or absence of each node pair’s edge. HippoRAG with Attributes stores each edge as a graph edge between the two entity nodes, and it answers a query by matching the two queried nodes as retrieval seeds and checking whether that edge exists. Node values are never queried, so the attribute binding plays no role. The query is a lookup of a single stored element.
  • Inventory Ledger (Snapshot). The sufficient statistic is each item’s current quantity and status, and every observation supplies it directly. HippoRAG with Attributes writes these values as attributes on the item’s node, overwriting the previous ones. It answers a query by matching the item node and reading its attributes. This is an isolated keyed update followed by an isolated keyed lookup.

In both tasks the stored variables are independent and every query is a single-key lookup, so a joint encoding has no dependence to exploit, and the mechanism performs like the episodic mechanisms. Its memory footprint also stays flat (Fig. 4), so it never exceeds its budget and incurs no penalty (Lemma 6). When the task’s sufficient statistic does carry relational structure, as in the graph tasks, the attribute binding matters, and HippoRAG with Attributes improves on base HippoRAG (Fig. 1a).

We will update Section 6 to explain this result more clearly.

"The assumed memory structures are defined so broadly that, even if a trend is observed, it is unclear whether it validates the paper's theoretical claims or reflects other characteristics of the evaluated memory systems."

Definitions 6 and 7 are stated as complexity conditions on storage and per-operation cost, not as informal descriptions. Appendix I.4 classifies each evaluated mechanism by its storage layout and retrieval cost rather than by its name or intended use.

The HippoRAG vs. HippoRAG-with-Attributes comparison is our closest control for other system characteristics. The two share the same graph, knowledge base, retrieval procedure and hyperparameters, and differ only in whether numeric values are stored as edges to literal nodes or as node attributes. They diverge on the relational graph tasks (Fig. 1a).

We acknowledge that the remaining comparisons between mechanisms involve other differences too, and that a fully controlled test of every mechanism is beyond the current experiments.

AuthorsOpenReview ↗

Reply to Reviewer 64oF (2/2)

"Why is the problem formulated as a POMDP? Is this intended to build on the settings in reinforcement learning where memory has traditionally been necessary?"

Yes. POMDPs are the standard setting in which memory is formally necessary: under full observability, a memoryless policy is sufficient. The formalism also covers both RL agents and LLM agents (where each incoming message is an observation) without committing to a particular policy class. This is what allows us to define when a task is memory solvable (Definition 1) and to analyze the memory mechanism separately from the policy.

"What motivates the conditions in Definition 2 as defining properties of stateful memory?"

Stateful memory is meant to capture the minimum memory a task requires. Defining it as the smallest bit-length that makes the task memory solvable rules out trivial over-provisioning, for example a 100-bit memory vector when 1 bit suffices, as in the T-maze. It also gives a precise threshold for what counts as a memory task (at least one bit of stateful memory). Anything below that threshold can be handled by parametric memory (Definition 3).

"The rendering of Equation (1) appears to need correction."

Thank you. This is a rendering error and will be corrected.

"In Table 1, mechanism–task alignment appears particularly pronounced on LongMemEval_S. Do the authors have an analysis explaining why?"

We hypothesize that this is a scale effect. LongMemEval_S requires substantially more context than the other benchmarks we analyze. Many of its questions also depend on information concentrated in specific turns, so answering them requires retrieving that information rather than combining evidence across sessions. The framework predicts that a mismatch matters most once a mechanism's cost exceeds its budget. A mechanism that keeps the full context without compression should therefore pay the largest penalty on the benchmark with the longest context, which matches the scale-dependent pattern in our controlled experiments (Section 6.2). We have not yet tested this hypothesis directly against the per-sub-task data.

Reviewer_g9FAOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies how an agent’s memory structure aligns with the information requirements and query patterns of a task. It formalizes stateful memory within the POMDP framework and distinguishes episodic tasks from semantic tasks. Its main contribution is an information-theoretic and computational complexity framework that connects these distinctions to storage and access costs. Empirically, the authors compare the accuracy and memory usage of six memory mechanisms across 32 controlled task configurations and analyze published results from five existing benchmarks.

Critical strengths

The paper raises a valuable question about how well an agent’s memory structure fits its tasks. Rather than classifying memory solely by its content, it considers dependencies between information items and the ways they are queried. This is an interesting perspective. The controlled experiments examine differences between memory requirements. Using a fixed backbone, the authors compare multiple mechanisms on factual lookup, state tracking, and graph reasoning tasks, measuring both accuracy and resource consumption. These experiments provide empirical support for discussing the alignment between memory structures and tasks.

Critical weaknesses

However, the paper has the following weaknesses. First, the core theoretical conclusions are not sufficiently established. The paper attempts to derive general constraints on storage space and access efficiency from statistical dependencies between information items, but several key steps require clearer assumptions and justification. Theorem 2 infers from large total multi-information that each isolated query must access a growing number of shared memory cells. However, global redundancy does not determine the access requirements of an individual query. For example, consider independent random variables, each duplicated in a pair. Storing one value per pair achieves space corresponding to the joint entropy, while any original variable can still be recovered with a single memory access. This satisfies the theorem’s high multi-information condition but contradicts its claim that constant-time lookup is impossible. Theorem 3 combines individually optimal costs from different workloads into requirements for a single dynamic task. Theorem 5 directly applies a lower bound for prefix-sum select to kth-smallest queries without providing the necessary reduction. Lemma 6 further infers that insufficient resources necessarily cause task-relevant information loss and a strict decrease in return, without establishing the conditions needed for these implications. Second, the correspondence between the theoretical framework and practical memory systems is unclear. The paper classifies RAG, long-context models, and graph-based memory methods according to its proposed definitions, but does not adequately establish why these systems satisfy the corresponding theoretical conditions. The experiments demonstrate performance differences across methods and tasks, but do not clearly establish that these differences arise from the structural limitations described by the theory.

Questions for authors
  1. To what extent do the theoretical conclusions depend on the proposed episodic/semantic definitions? Do the theorems establish general limitations of memory systems, or properties that hold under this particular categorization and its assumptions?
  2. What new insights into agent memory follow from the claim that no universally optimal memory mechanism exists? Does it provide more specific design guidance than the observation that different tasks require different structures?
  3. The theory primarily concerns asymptotic time and space complexity. How does it explain accuracy differences at finite task scales? Do the experiments validate the theoretical conclusions, or mainly demonstrate phenomena consistent with their underlying intuition?
1 comment
AuthorsOpenReview ↗

Reply to Reviewer g9FA

We thank the reviewer for an exceptionally careful review. Regarding the counterexample to Theorem 2: defining the stored variables as a minimal sufficient statistic would collapse duplicated values to their unique elements, removing the multi-information in the reviewer's construction. However, we agree that this does not repair the theorem. Correlated but non-duplicated variables can still have ω(w) multi-information while uncompressed storage achieves O(H(A)) space with O(1) lookup, for example, a Markov chain whose every element is queried. We also agree that the issues raised with Theorems 3 and 5 and Lemma 6 are substantive. For completeness, we respond briefly to the points that are independent of these results.

"The paper classifies RAG, long-context models, and graph-based memory methods… but does not adequately establish why these systems satisfy the corresponding theoretical conditions."

We agree. The classifications in Appendix I.4 are qualitative and rely on some assumptions we did not state. For example, constant-cost retrieval in RAG assumes an approximate-nearest-neighbor index. A future version will state these assumptions and support the classifications with measured costs.

"The experiments… do not clearly establish that these differences arise from the structural limitations described by the theory."

Two comparisons in the paper hold implementation fixed:

  • Inventory Ledger, delta vs. snapshot mode. The tasks are identical except for whether each observation states the item's current state.
  • HippoRAG vs. HippoRAG with Attributes. The mechanisms are identical except for how numeric values are stored.

The memory measurements in Fig. 4 are also independent of the proofs. A future version will additionally report per-operation costs, namely tokens read per query and tokens rewritten per update, so that accuracy changes can be tied to measured costs.

"How does [the theory] explain accuracy differences at finite task scales?"

The experiments show patterns consistent with accuracy declining once a mechanism's cost exceeds the available budget. Given the issues identified, they do not constitute validation of the formal results.

"What new insights into agent memory follow…?"

The meta-analysis results do not depend on the proofs. Mechanism–task alignment explains a significant share of performance variance on four of the five benchmarks. The one null result, Memory AgentBench, aggregates episodic and semantic sub-tasks into a single score. A full analysis would need to control for task difficulty.

We thank the reviewer again for feedback that will substantially improve this work.

Reviewer_foQWOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes a theoretical framework for episodic and semantic agent memory, supported by synthetic experiments and a meta-analysis of existing benchmarks.

Critical strengths

The paper offers an interesting structural perspective on agent memory by connecting information dependencies and query requirements to storage and operation costs. This perspective could help make memory evaluation more task-specific.

Critical weaknesses
  1. The modeling choices require stronger justification regarding their applicability to practical agent memory systems. Although the framework provides formal definitions, the correspondence between these definitions and the evaluated tasks and mechanisms is not sufficiently established. In particular, the assumed connections between semantic memory, inter-variable redundancy, and compressed storage require stronger justification. Consequently, the theoretical conclusions appear highly dependent on this particular formalization, and their applicability beyond the authors’ definitions remains unclear.
  2. The experiments do not isolate the proposed distinction between episodic and semantic memory, and their coverage is limited. The evaluation compares six architectures that differ in retrieval budgets, task-specific prompting, and state-update procedures. It is therefore unclear whether the observed performance differences arise from the proposed memory categories or from these implementation choices. The results mainly demonstrate that particular architectures perform differently across tasks, without clearly establishing the explanatory value of the proposed distinction. Furthermore, the evaluation covers only eight simplified synthetic task families at four scales with one generative backbone, providing limited support for the paper’s broad conclusions.
Questions for authors
  1. Although Definitions 4–7 provide formal classification criteria, how are their statistical and computational conditions verified for the evaluated tasks and mechanisms? In particular, what evidence establishes the required multi-information and space-complexity properties beyond the qualitative arguments in Appendices I.2 and I.4?
  2. How do the experiments distinguish the effect of episodic versus semantic memory from differences in retrieval budgets, task-specific prompts, and state-update procedures? Are there controlled comparisons showing that the proposed memory distinction explains the results beyond these implementation choices?
  3. What evidence supports extending the conclusions beyond the eight synthetic task families and the fixed Qwen3-4B backbone?
2 comments
AuthorsOpenReview ↗

Reply to Reviewer foQW (1/2)

We thank the reviewer for the careful critique, and especially for the precise questions about how our definitions are verified and how the experiments isolate the proposed distinction.

"The modeling choices require stronger justification… the assumed connections between semantic memory, inter-variable redundancy, and compressed storage require stronger justification."

We do not claim to model human semantic memory. As stated in lines 52–53, the paper draws intuition from the biological distinction, but its contribution is strictly computational. We use the terms "episodic" and "semantic" because they convey a useful intuition: isolated, specific facts versus synthesized, interdependent knowledge.

On the link between redundancy and compressed storage, we agree with the reviewer that this needs more care. As we discuss in our response to Reviewer g9FA, Theorem 2 as stated does not hold in general, because global redundancy does not determine the access cost of an individual query. We are restating this result. The behaviour we observe empirically is better characterized by how many observations a query's answer depends on than by redundancy among the stored variables.

"The theoretical conclusions appear highly dependent on this particular formalization, and their applicability beyond the authors' definitions remains unclear."

We chose our modeling assumptions to be as general as possible:

  • POMDPs cover any agent acting under partial observability, whether RL-based or LLM-based.
  • The cell-probe model gives lower bounds that hold for any implementation, because it charges only for memory accesses.
  • Stateful memory is defined over arbitrary finite bit vectors, which covers context windows, vector stores, graphs, and any other digitally implementable memory mechanism.

The episodic/semantic split is one useful way to partition tasks, not the only one. The underlying trade-off between O(1) isolated operations and O(H(A)) joint storage does not depend on that choice. Appendix I.4 shows that the framework covers the mechanisms most widely used in practice. We also acknowledge (see our response to 64oF) that some mechanisms fall into different regimes depending on the task.

"The experiments do not isolate the proposed distinction… six architectures that differ in retrieval budgets, task-specific prompting, and state-update procedures." (and Q2)

We address each confounder in turn, then point to two comparisons in the paper that hold implementation choices fixed.

  • Prompting. All agents share the same backbone, decoding parameters, observation format and probe prompts. The one exception is Specialized-in-Context, whose task-specific structural hint is part of the mechanism itself: it tells the model which state to maintain (Appendix I.3).
  • Retrieval budgets and update procedures. These are intrinsic to each mechanism. The theory is concerned with how each mechanism's cost grows with task scale, not with constant settings such as top-k = 5. Fig. 4 shows that memory footprints follow the predicted growth patterns: flat for the isolated stores and for state-rewriting, and super-linear for uncompressed context.
  • Comparisons that hold implementation fixed.
    1. Inventory Ledger, delta vs. snapshot mode. The items, operations, scale, mechanisms and prompts are identical. The only difference is whether each observation includes the item's authoritative current state. Episodic mechanisms transfer across the episodic tasks, including snapshot mode, but degrade sharply in delta mode (Section 6.1).
    2. HippoRAG vs. HippoRAG with Attributes. The two share the same graph, knowledge base, retrieval procedure and hyperparameters. They differ only in whether numeric values are stored as edges to literal nodes or as node attributes, and they diverge on the relational graph tasks (Fig. 1a).

"The results mainly demonstrate that particular architectures perform differently across tasks, without clearly establishing the explanatory value of the proposed distinction."

The experiments test specific predictions stated before the results:

  1. Episodic mechanisms transfer across episodic tasks.
  2. Episodic mechanisms degrade on semantic tasks as horizons grow.
  3. Semantic mechanisms match episodic ones at small scale, then hit budget limits.
  4. No semantic mechanism wins across all relational structures.

Section 6 reports results consistent with each of these. Section 7 then tests explanatory value on five external benchmarks that were built without our taxonomy in mind. Alignment between mechanism and task explains a statistically significant share of the variance on four of the five.

AuthorsOpenReview ↗

Reply to Reviewer foQW (2/2)

"Only eight simplified synthetic task families at four scales with one generative backbone." (and Q3)

We agree this is a limitation. The synthetic tasks are deliberately simple so that differences can be attributed cleanly, without pretraining or domain confounders. Evidence for generality beyond them comes from the meta-analysis, which spans five external benchmarks and many different backbones (Table 1). Because the analysis concerns the memory mechanism rather than the policy, we expect backbone scale to change absolute accuracy more than the relative ordering of mechanisms. We acknowledge, however, that we have not tested this directly.

"How are the statistical and computational conditions of Definitions 4–7 verified for the evaluated tasks and mechanisms?" (Q1)

For the tasks, the conditions hold by construction of the generators. In the episodic tasks, each fact is sampled independently, and every probe asks for one specific stored value, so the queries are pure lookups. In the semantic tasks, the answer is a function of many observations and no single observation contains it, so any sufficient memory must combine information across them.

The reviewer is right that we argue these properties qualitatively and do not compute the information quantities. For the mechanisms, classification follows each one's storage layout and per-operation cost (Appendix I.4):

  • RAG and HippoRAG write each chunk or triple to its own entry and retrieve a fixed top-k.
  • Everything-in-Context and Attention Sink keep the observation sequence in context and attend over it jointly.
  • Specialized-in-Context and HippoRAG with Attributes maintain a joint state, either by rewriting it or by binding values to entities.

Comments on the paper

1 comment

We thank the reviewers for their valuable time and for providing detailed feedback. We especially thank reviewer g9FA for finding a mistake in Theorem 2. We believe this mistake is critical, and we withdraw our paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.