- 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
- 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?
- What motivates the conditions in Definition 2 as defining properties of stateful memory?
- The rendering of Equation (1) appears to need correction.
- In Figure 1(b), HippoRAG with attributes performs well on the episodic tasks. Do the authors have an analysis explaining this result?
- In Table 1, mechanism–task alignment appears particularly pronounced on LongMemEval_S. Do the authors have an analysis explaining why?
2 comments
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.
Reply to Reviewer 64oF (1/2)
We thank the reviewer for the careful reading and for engaging with both the theory and the experiments.
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:
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.
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:
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.
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.