MemDerive: A Diagnostic Benchmark for Agent Memory over Evolving Data

Sen Gao; Yongan Li; Han Chen; Bingsheng He; Ming Wu; Jason Zeng; Michael Heinrich; Shixuan Sun

cs.DBOct 18, 2026

MemDerive: A Diagnostic Benchmark for Agent Memory over Evolving Data

Authors: Sen Gao, Yongan Li, Han Chen, Bingsheng He, Ming Wu, Jason Zeng, Michael Heinrich, Shixuan Sun

Organizations: National University of Singapore, Singapore, Singapore · Shanghai Jiao Tong University, Shanghai, China · Zero Gravity Labs, Singapore, Singapore

Abstract

Long-running agents rely on memory of their past interactions for task state, such as what has been completed and which conditions still hold. Such state is usually a derived state. No record states it, and it must be computed by rules from multiple records of an evolving history. Existing memory benchmarks score only the final answer, with no reference for the intermediate states behind it. A wrong answer therefore cannot be traced to the state that was missed, and a state that silently became outdated goes undetected. We present MemDerive, a diagnostic benchmark for agent memory over evolving data. It specifies each scenario symbolically, derives exact gold answers with Datalog, records the gold derivation DAG and the supporting events of every query, and renders the history in natural language with fictional entities and distractors. Its 10 scenarios contain 4,692 events and 1,503 queries whose difficulty varies along access, evolution, and composition. On this ground truth, MemDerive evaluates answer reliability, diagnoses failures by probing the nodes of the gold derivation DAG, and tracks whether answers stay correct as events arrive. Our evaluation of four memory systems reveals failures that final-answer benchmarks hide. On derived state, every memory system falls behind simple BM25 retrieval, although the same answer model reaches 96.01% when given the supporting events. Most failures are ungathered, as a system holds the missing intermediate state but does not retrieve it for the question that needs it. Memory systems also rarely propagate implicit changes, which no new record states. These results suggest three principles for memory design. Gather inputs along the derivation, store rules with their versions, and maintain derived states through recorded dependencies.

Figures & tables

Figure 1. An original question and a state question over the same LoCoMo history. (a) One record states the answer. (b) The answer is computed from two states, each gathered from several records of the history. Nate asks for games to play away from competitive gaming. Agent memory computes the difference between played games and games with recorded tournament participation, supplying four candidates for a response.

Figure 2. Accuracy on LoCoMo and LongMemEval histories. A state question asks for an answer that no single record states and that must be computed from several records.

Symbol	Meaning	Sec.
$e=(t_{e},r_{e},A_{e})$	event: observation time, record, actions	2.1
$O$ , $O_{\leq\tau}$	history, events observed up to cutoff $\tau$	2.1
$B_{\tau}$	resolved state, latest version of each fact and rule	2.1
$P_{\tau}$ , $C_{\tau}$	derivation program, closure	2.2
$q=(\theta,\tau)$	query with target $\theta$ and cutoff $\tau$	2.2
$z(q)=(\ell_{q},y_{q})$	gold answer, label and answer	2.2

Table 1. Notation and defining sections.

Panel of Figure 3 — Figure 3. Gold derivation DAG of Example 2.9 , layered by the three workload dimensions. The gold derivation DAG of the running example in three bands. Events at the bottom form the Access layer, resolved facts in the middle the Evolution layer, and derived states at the top the Composition layer. The count depends on the foreign-trip set and on the completeness of the trip list. The obsolete event e7 is crossed out, e10 supersedes it in July and changes the count from 3 to 2, and e11 is a distractor. Resolved facts for Trip-Anser, Trip-Ibex, and Ashfell are drawn as their events.

Panel of Figure 4 — Figure 4. Construction and evaluation pipeline of MemDerive . Construction and evaluation of one scenario. A symbolic specification of events, rules, queries, operator families, and difficulty controls feeds two lanes. In the lane that the SUT sees, rendering produces faithful records with invented entities, lexical gaps, and distractors, and the SUT ingests the history and returns a context from which the answer model gives an answer, a label, and citations. In the lane that the benchmark keeps, reference evaluation computes gold answers, derivation DAGs, support, and witnesses, and compilation derives state probes, checkpoints, and gold trajectories. The outputs feed Q1 answer reliability, Q2 failure diagnosis, and Q3 derived-state maintenance, each with its measures.

Family	Construct	Queries	Witness	Obs. %	Height	Width
			Access	Evol.	Composition
$\mathsf{temporal}$	version selection	191	1.1	51	3.0	2.3
$\mathsf{semantic}$	category mapping	327	5.6	35	3.5	15.1
$\mathsf{closure}$	recursion	208	2.2	28	3.3	7.9
$\mathsf{rules}$	negation	312	4.1	65	3.6	9.8
$\mathsf{set\_quant}$	aggregation	465	5.9	49	3.8	20.7

Table 2. Operator families and the workload dimensions of their queries.

				Labels			Witness
Domain	Scen.	Events	Queries	Ans.	Zero	Unk.	Med.	Max
TripOps	4	1,817	561	409	77	75	3	69
ShopOps	3	1,462	473	344	42	87	2	31
EduOps	3	1,413	469	423	18	28	3	20
All	10	4,692	1,503	1,176	137	190	3	69

Table 3. Suite statistics by domain. Scen. is the number of scenarios. Labels are

\mathsf{answerable}

\mathsf{justified\text{-}zero}

, and

\mathsf{unknown}

. Witness sizes are medians and maxima in events.

Panel of Figure 5 — Figure 5. Diagnosis of Example 4.3 . Diagnosis of the running example on one DAG. Node colors show the probe answers in the inherited context: the count, the foreign-trip set, and the country of Trip-Grus are wrong. Localization runs top-down to two frontier nodes: the destination of Trip-Grus, answered Halewick also in the targeted context and labeled unretrievable, and the country of Corby, missing in the inherited context but answered Corvia in the targeted context and labeled ungathered. Tags beside each failing node show the states that self-evidence recovery and gold-evidence recovery compute bottom-up: self evidence leaves the country of Trip-Grus unknown and the count wrong, gold evidence yields Corvia and a count of 2.

Figure 6. Answer and citation quality on all queries. Six panels compare answer accuracy, witnessed accuracy, answerability accuracy, citation precision, citation recall, and citation F1 for the SUTs and reference conditions.

Figure 7. Answer accuracy under context budgets. Answer accuracy as the context budget grows, for session- and event-level retrieval (left) and four memory systems (right).

Figure 8. Answer accuracy and obsolete citations along the workload dimensions.

Figure 9. Answer accuracy by the height and width of $\mathcal{G}_{q}$ . Answer accuracy for nine conditions grouped by the height and width of the gold derivation DAG.

Figure 10. Answer accuracy by operator family. Answer accuracy grouped by the operator family of each query.

Figure 11. Answer accuracy on three memory benchmarks. Answer accuracy on MemDerive, LoCoMo, and LongMemEval, shown in separate panels for the same conditions.

	Targeted accuracy				Failure class			Recovery
SUT	Fact	Rule	Compl.	Deriv.	Ung.	Unr.	Mis.	Self	Gold
BM25	94	92	87	61	67	62	38	62	67
Embed	90	73	93	43	76	62	24	38	67
Mem0	90	17	99	46	78	56	22	33	39
Cognee	93	84	95	50	70	57	30	52	65
MemoryOS	80	76	75	27	85	65	15	35	50

Table 4. Failure diagnosis of the six SUTs (%).

Figure 12. Failure diagnosis of the six SUTs on the diagnostic queries: contexts, recovery, and the first correct state.

	Explicit		Implicit
SUT	Refresh	Stale	Refresh	Stale
BM25	75	28	61	9
BM25-E	78	22	37	19
Embed	83	6	81	6
Embed-E	100	6	55	19
Mem0	90	17	56	19

Table 5. Refresh and stale answers by kind of change (%).

Figure 13. Maintenance across consecutive checkpoints.

Figure 14. Continuous correctness of the tracked queries. The share of tracked queries answered correctly at every checkpoint up to the displayed one.

Figure 15. Ingestion cost and retrieval latency of the SUTs as the histories grow. Cumulative ingestion cost and median retrieval latency as the histories grow.

Figure 16. Token and API cost of ingestion and answering. Input and output tokens and estimated API cost, separated into ingestion and answering over all queries.

	Scoring		Tests
Benchmark	Answer	Evidence	Version updates	State maintenance	Derived-state probes
LoCoMo ( Maharana et al., 2024 )	exact	retrieval	–	–	–
LongMemEval ( Wu et al., 2025 )	judge	retrieval	✓	–	–
MemoryAgentBench ( Hu et al., 2026 )	mixed	–	✓	–	–
MemTrace ( Long et al., 2026 )	judge	retrieval	✓	✓	–
Ground Truth First ( Spencer, 2026 )	judge	facts	✓	✓	–

Table 6. Evaluation properties of memory benchmarks, as reported in the cited papers.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Family	Operators (queries)
$\mathsf{temporal}$	$\mathsf{update}$ (71), $\mathsf{refund}$ (23), $\mathsf{correction}$ (19), $\mathsf{rebooking}$ (12), $\mathsf{expiration}$ (8)
$\mathsf{semantic}$	$\mathsf{upward\_abstraction}$ (160), $\mathsf{cancellation}$ (61), $\mathsf{scope}$ (37), $\mathsf{containment}$ (32), $\mathsf{personal\_exclusion}$ (28), $\mathsf{custom\_category}$ (20), $\mathsf{derived\_category}$ (8), $\mathsf{type\_rule\_propagation}$ (8), $\mathsf{role\_chain}$ (6)
$\mathsf{closure}$	$\mathsf{prerequisite\_chain}$ (112), $\mathsf{dependency\_chain}$ (23), $\mathsf{role\_inheritance}$ (11), $\mathsf{renewal}$ (9)
$\mathsf{rules}$	$\mathsf{rule\_update}$ (153), $\mathsf{exception}$ (138), $\mathsf{custom\_taxonomy}$ (86), $\mathsf{threshold}$ (78), $\mathsf{rule\_selection}$ (56), $\mathsf{conversion}$ (8), $\mathsf{rule\_override}$ (7)
$\mathsf{set\_quant}$	$\mathsf{aggregation}$ (374), $\mathsf{set\_construction}$ (169), $\mathsf{exclusions}$ (162), $\mathsf{comparison}$ (42), $\mathsf{stale\_exclusion}$ (33), $\mathsf{set\_difference}$ (32), $\mathsf{gating}$ (14), $\mathsf{conjunction}$ (4)
shared	$\mathsf{closed\_world}$ (186), $\mathsf{lookup}$ (160), $\mathsf{incomplete}$ (141), $\mathsf{negative}$ (79)

Appendix

Table 7. Operators by family, with the number of queries that use each.

Agent Memory

Agent memory lets AI systems retain, update, and use facts, experiences, and skills across sessions and long-horizon tasks.

See all 191 papers

Can Agent Memory Systems Track Evolving State?
Aug 20, 2026Xinyi Fan, Miri Liu, Ruozhen Yang +2Agent Memory LLM Agent Memory
University of Illinois Urbana-Champaign
Beyond Downstream QA: Rethinking How We Evaluate Agent Memory
Oct 15, 2026Sebastian-Antonio Toma, Jean de Kernier, Mike Ply +1Agent Memory LLM Agent Memory
Amazon Web Services · Technical University of Cluj-Napoca, Romania
MEME: Multi-entity & Evolving Memory Evaluation
May 12, 2026Seokwon Jung, Alexander Rubinstein, Arnas Uselis +2Agent Memory Persistent Memory for Language Models
1KAIST AI · 2Tübingen AI Center, University of Tübingen · 3NAVER AI Lab

Aug 20, 2026J/K move · Enter open · S save

Can Agent Memory Systems Track Evolving State?

Xinyi Fan, Miri Liu, Ruozhen Yang, Siru Ouyang+1

University of Illinois Urbana-Champaign

Agent Memory LLM Agent Memory State Tracking Long-Term Conversational Memory Memory Agent Benchmarks

Open paper AskPDF arXiv

As LLM-based agents are deployed for longer and higher-stakes tasks, their memory systems continue to have crucial gaps. While existing memory benchmarks focus largely on recall-shaped tasks, we argue an effective memory system must track the evolving state of the world; as facts, constraints, and decisions are revised over a long interaction, answers must reflect the current state and not a superseded one. We define this capability as state tracking and instantiate it in StateMemBench, a benchmark of 234 multi-session scenarios spanning two conversation-length regimes. Its closed-pool grading scores whether an answer reflects the current state, the superseded state, or fails otherwise, separating state-tracking failures from other errors by construction. Our analysis shows that this task is challenging for existing memory systems, retrieval-augmented baselines, and long-context baselines. We then present StateMem, a state-first memory method that explicitly tracks supersession and relational dependencies, and show it improves current-state accuracy over the strongest same-backbone baseline by 1.8x (0.205 -> 0.363) on DeepSeek-V4-Flash and over the strongest memory system by 1.6x (0.149 -> 0.233) on Qwen-3.5-9B, while remaining competitive with the long-context baselines. Finally, we show the same state approach can be applied as a lightweight single-call wrapper over existing memory systems, lifting current-state accuracy by +32 to +67 points on StateMemBench across six memory and retrieval backends. A length- and cost-matched control attributes +15 to +32 of those points to state structure rather than added context.

Abstract

Agent Memory

Explore similar work

Can Agent Memory Systems Track Evolving State?

Beyond Downstream QA: Rethinking How We Evaluate Agent Memory

MEME: Multi-entity & Evolving Memory Evaluation