acceptodds
Withdrawn from ICLR 2027

MemState: Dynamic Memory State Graph Construction and Agentic State Graph Retrieval

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

Abstract

Existing long-term memory systems often assume that the latest value of a memory fully captures the relevant facts. However, this assumption does not hold for multi-hop retrospective reasoning and complex state queries. Questions such as “What happened before?”, “Why did things become this way?”, and “What was the final outcome?” require access to the complete trajectory of an evolving matter and its current state, rather than a single final value retained after earlier states have been overwritten. We propose MemState, a long-term memory management framework that replaces memory overwriting and deletion with a dynamic state graph. MemState comprises two core modules: Dynamic Memory State Graph Construction (DMSG) and Agentic State Graph Retrieval (ASGR). DMSG preserves successive states of the same matter and organizes them into a dynamic evolution graph through relations of different semantic strengths. This allows historical states, direct state transitions, and related context to coexist without being overwritten by subsequent information. ASGR treats retrieved memories as partial observations of the underlying state graph and enables an agent to actively trace historical paths, subsequent changes, and the latest state through multiple rounds of tool calls. It thereby transforms static similarity-based retrieval into an active retrieval process guided by state evolution. We evaluate MemState on long-term memory benchmarks including RHELM, LoCoMo, and LongMemEval, comparing it with vector retrieval, memory compression, and update-based memory management methods. The results show that MemState more reliably retrieves evidence of key state transitions and actual outcomes into the context, demonstrating stronger state retrieval capabilities under constrained retrieval budgets.

Primary area:
foundation or frontier models, including LLMs
Keywords:
long-term memory, dynamic state graphs, state evolution, agentic retrieval, large language models

Reviews

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

The paper proposes MemState, a long-term memory framework for agents that keeps every successive state of a "matter" instead of overwriting it. At construction time (DMSG), an LLM attaches each new memory to a matter using both local nodes and a running chain summary, and labels relations as strong (state transition, kept acyclic) or weak (context). At query time (ASGR), initial hybrid retrieval results are grouped into per-matter units, a unit is flagged stale if its retrieved frontier has unseen strong-edge successors, and an agent issues up to four DAG_Search calls (forward/backward, latest/history/branch) to fill in the missing states. On RHELM, LoCoMo and LongMemEval-S the method roughly matches Zep/Graphiti, with 1 to 3 point gains on temporal and update subsets. On a separate state-focused evaluation it reports 76 CER and 85 history recall versus 65 and 72 for A-MEM, plus many construction ablations, robustness tests and cost accounting.

Critical strengths

Strength 1. The problem framing is useful. Separating "latest-only memory loses history" from "static retrieval misses later updates" (Figure 1) is a helpful way to think about memory for evolving matters, and the frontier/staleness definition in Eqs. (6) and (7) is simple and gives the agent a concrete signal for when to keep traversing.

Strength 2. The set of controls is well chosen in principle: a compute-matched multi-round text search (Table 16), a graph-structure by traversal factorial (Table 14), round-limit sweeps, edge and timestamp perturbations, and per-record construction cost. If these numbers hold up, the compute-matched comparison (82 vs 86 QA at the same 21K tokens) is the most convincing evidence that the graph matters and not just the extra agent calls.

Critical weaknesses

Weakness 1. The state-focused evaluation, which carries most of the claims, is not specified.** The headline numbers in the abstract (76 CER, 85 history recall, +11/+13 over A-MEM) come from Table 2, but I could not find where these questions come from. Section 4.1 says "state-focused QA uses a shared binary rubric, macro-averaged over query types and then over datasets", and Table 12 mentions "independently annotated supporting content", but there is no description of how gold latest/history evidence, transition paths and branches were annotated on RHELM/LoCoMo/LongMemEval-S, how many questions there are, or who annotated them. The same is true for the 32-hop chain test, the lexically-similar-matters test (1000 decisions) and the 100K-record scaling test. Without this I cannot judge whether the evaluation favours a system that builds exactly this kind of chain graph. I might be wrong here, but it looks like a custom benchmark was built around the method's own notion of matters and transitions.

Weakness 2. Baselines and statistics.** Zep/Graphiti is the strongest system in every native benchmark row (Table 1), and MemState only ties it on overall LoCoMo and LongMemEval-S accuracy (one point on RHELM). Yet Zep and MemU are absent from the state-evidence, trajectory and update-density tables, which is exactly where the claimed advantage lies. Zep is a temporal knowledge graph, so it is the natural comparator for "preserving state evolution". Also, three seeds are listed but every number is a rounded integer with no variance or significance test, so 1 to 3 point native-benchmark gains cannot be separated from noise. Hybrid RAG in Table 2 is literally MemState with zero rounds (identical rows in Tables 13 to 15), so it is not an independent baseline.

Other. The supplementary README states that the model-backed pipeline is not included and that the reported_results files are author-supplied summaries marked "independently_verified: false", with no per-question outputs or logs. So the numbers cannot be checked. Table 32's ASGR latency (36s p50, 80s p95, versus 10s for baselines) deserves more discussion than it gets.

Questions for authors
  1. How was the state-focused QA set constructed (source dialogues, number of matters and questions per type, annotation procedure, annotator agreement on the gold evidence itself)? Was any of it written or filtered with the same LLM used in DMSG?

  2. Can you report Zep/Graphiti (and MemU) on Tables 2, 11, 12 and 26 under the same reader and budget?

  3. Please give per-seed results or confidence intervals for Table 1 and Table 2. With temperature 0, what exactly do the three seeds vary?

  4. How does DMSG behave when the matter boundary is genuinely ambiguous in the raw conversation (e.g. LoCoMo, where matters are not pre-segmented)? Is component purity measured against gold matter labels on the native benchmarks or only on the constructed test sets?

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

This paper proposes MemState, a long-term memory system for questions about how a matter changes over time. Its construction component preserves successive records in a graph, distinguishes state transitions from contextual relations, and maintains matter-level summaries. At query time, an agent starts from retrieved records and makes further graph-search calls to recover missing history or later outcomes.

Critical strengths

The paper addresses a meaningful problem: a retrieved record may describe an outdated intermediate state, while retaining only the latest state can lose the history needed to answer a question. The distinction between state-transition and contextual edges gives the proposed system a clear design. The authors also evaluate evidence recovery directly and provide construction ablations, retrieval-round experiments, and a compute-matched multi-round text-search control. The reported gains over A-MEM on complete-evidence and history recall are substantial.

Critical weaknesses

My main concern is that the novelty and benefit relative to the closest existing temporal-memory systems are not clearly established. Zep/Graphiti (https://arxiv.org/html/2501.13956v1) already preserves historical information in a temporal graph, while Hindsight (https://aclanthology.org/2026.acl-demo.27/) also combines structured temporal memory with graph-based retrieval. The related-work discussion acknowledges these systems but does not explain in enough detail which capability is unavailable in them and is supplied by MemState’s particular graph structure and retrieval policy.

The experimental comparison leaves the same question unresolved. Zep/Graphiti appears in the standard benchmark tables, where MemState’s gains are generally small or absent: for example, overall RHELM accuracy is 35 versus 34, and overall LongMemEval-S accuracy is tied at 88. Yet Zep/Graphiti is omitted from the state-evidence table, where the paper reports its largest and most directly relevant gains. Hindsight is also absent from that comparison. Consequently, the 76% complete-evidence recall and 85% history recall do not establish an advantage over the closest temporal-graph alternatives.

The quality gains should also be considered alongside cost. The paper reports approximately 21,000 online model tokens and a median latency of 36 seconds per question for MemState, compared with approximately 8,400 tokens and 10 seconds for A-MEM. The compute-matched text-search control is helpful, but a comparison with a temporal-graph method under the same evidence and compute budgets would be more decisive.

Questions for authors

Can Zep/Graphiti, and if feasible Hindsight, be evaluated on the same complete-evidence, historical-state, and state-focused QA metrics?

Can the authors compare quality against query-time tokens or latency, so the benefit of additional graph-search calls is clear?

Which gain comes specifically from MemState’s graph representation, rather than giving an existing temporal graph the same multi-round retrieval procedure?

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

This paper proposes MemState, a long-term memory framework for LLM agents designed to preserve and retrieve the evolving states of the same matter across extended interactions. MemState consists of two main components: Dynamic Memory State Graph Construction (DMSG) and Agentic State Graph Retrieval (ASGR). DMSG incrementally organizes memory records into a graph containing strong state-transition edges and weak contextual relationships, while maintaining chain-level summaries to improve matter assignment and reduce semantic drift. ASGR performs multi-round graph retrieval by grouping initially retrieved memories into matter-level units, identifying potentially outdated frontiers, and dynamically exploring historical states, subsequent updates, and related branches through graph-search tools. The authors evaluate MemState on RHELM, LoCoMo, and LongMemEval-S, reporting improvements in state evidence completeness, historical recall, and selected temporal reasoning tasks.

Critical strengths
  • Its proposed method to preserve historical states while identifying the latest valid information. Distinguishing state transitions from contextual associations is a reasonable design choice.
  • The experimental analysis, which includes construction and retrieval ablations, factorial comparisons between graph structures and retrieval strategies, compute-matched baselines, and robustness evaluations is useful.
Critical weaknesses
  • The methodological novelty appears relatively limited compared with existing structured and temporal memory systems. Related systems such as Zep [1] already supports temporal knowledge graphs and historical fact tracking, while A-MEM [2] and other graph-based memory systems incorporate dynamic memory linking and evolving representations.
  • The experimental results do not convincingly demonstrate that the proposed memory representation is the primary driver of performance improvement. In the graph-structure and retrieval factorial experiment in Table 14, both the local temporal chain and DMSG achieve exactly 70% QA under static retrieval. Introducing ASGR improves the local temporal chain to 81%, while combining ASGR with DMSG reaches 86%.
  • The broader performance claims are not adequately supported by the native benchmark results. Table 1 shows that MemState improves overall accuracy on RHELM by only one percentage point and matches the strongest baseline on LongMemEval-S, while LoCoMo results show only marginal improvements in multi-hop and temporal F1, with no improvement in single-hop F1 and a decrease in open-domain F1. These results contrast with the substantially larger gains reported on the paper's state-focused evidence recall metrics.
  • The proposed retrieval mechanism relies on structural assumptions whose validity in realistic memory environments is insufficiently established. In Section 3.3, a state unit is considered stale when its retrieved frontier has an unseen successor in the full graph. The perturbation experiments demonstrate substantial sensitivity to graph errors, with QA dropping from 86% to 76% after adding 10% incorrect strong edges.

[1] Rasmussen et al. Zep: A Temporal Knowledge Graph Architecture for Agent Memory. 2025

[2] Xu et al. A-MEM: Agentic Memory for LLM Agents. NeurIPS 2025

Questions for authors
  • How does MemState distinguish a genuine transition in the state of a matter from an observation that merely describes an existing or historical state?
  • What additional information does the frontier-based staleness signal provide beyond directly retrieving the most recent reachable state from the graph?
  • Why multi-round LLM-guided exploration is necessary instead of applying deterministic forward/backward traversal or directly selecting terminal states within the relevant component?
  • How does the framework recover when an incoming memory is incorrectly assigned to an existing matter or when two semantically related but distinct matters are merged?
  • To what extent are the reported improvements attributable to access to explicit graph metadata rather than better identification of relevant evidence?

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

Related papers

Discussion (0)

Sign in to comment.