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 SunarXiv 2026 · arXiv

TL;DR

MemDerive is a new diagnostic benchmark designed to evaluate how AI agents manage "derived state"—information that isn't explicitly recorded but must be computed from an evolving history of interactions. The study reveals a sobering reality: current state-of-the-art memory systems often perform worse than simple keyword search (BM25) because they fail to gather all the necessary intermediate facts required for complex, multi-step reasoning.

What Problem Does This Paper Address?

As we move toward long-running autonomous agents, "memory" is becoming a critical component. However, most current benchmarks focus on simple recall (e.g., "What is Nate's favorite color?") or explicit updates. In reality, an agent's most important knowledge is often derived state.

Consider an agent managing a user's schedule. To answer "What can I play to relax away from competitive gaming?", the agent must retrieve all games the user has played, identify which ones were part of tournaments, and then calculate the difference. No single record contains the answer; it must be derived.

Figure 1: Comparison between simple record retrieval and task-driven state computation.

Existing benchmarks only score the final answer. If an agent fails, you don't know if it forgot a specific event, used an outdated record, or failed the logical composition. MemDerive addresses this by providing a "glass-box" evaluation that can pinpoint exactly where the derivation chain broke.

Methods

The authors built MemDerive using a rigorous, symbolic-first approach:

  1. Symbolic Specification: Scenarios are defined using Datalog rules. This ensures an "exact ground truth" for every intermediate step of a query.
  2. Gold Derivation DAGs: For every query, the benchmark generates a Directed Acyclic Graph (DAG) that links the final answer back through intermediate states to the specific supporting events (witnesses).
  3. Natural Language Rendering: To ensure the agent relies on memory rather than pre-trained knowledge, symbolic facts are rendered into natural language using fictional entities (e.g., imaginary cities and people).
  4. Diagnostic Probing: When a system fails a query, MemDerive "probes" the nodes of the derivation DAG. It asks the system about intermediate states to determine if the failure was due to poor retrieval (ungathered), missing facts (unretrievable), or faulty logic (misderived).
  5. Maintenance Tracking: The benchmark evaluates "continuous correctness" by asking the same queries at different points in time as new events arrive, specifically looking for how systems handle implicit changes (where a state changes because its dependencies changed, even if the state itself wasn't mentioned).

Datasets

The paper introduces the MemDerive suite, which includes:

  • 10 Scenarios across three domains: TripOps (travel/reimbursement), ShopOps (orders/spending), and EduOps (degree planning/prerequisites).
  • 4,692 events and 1,503 queries.
  • Difficulty is controlled along three dimensions: Access (how hard it is to find the facts), Evolution (how much the facts change over time), and Composition (how many logical steps are required).

The authors also evaluated systems on existing benchmarks like LoCoMo and LongMemEval to show that high performance on those does not guarantee success on derived state tasks.

Key Insights and Ideas

  • The Gathering Bottleneck: The primary reason memory systems fail isn't that the LLM can't reason; it's that the memory system fails to provide the right "context." When given the exact supporting events (the "Oracle" condition), accuracy jumps to over 96%.
  • Memory Systems vs. BM25: Surprisingly, sophisticated memory systems like Mem0 and Cognee often trail simple BM25 retrieval on derived state. This is because many memory systems try to "summarize" or "extract" salient facts at ingestion, often discarding the "boring" details that turn out to be crucial for later derivations.
  • Implicit Changes are the Silent Killer: Systems are relatively good at updating a fact when a new record explicitly contradicts an old one. They are much worse at updating derived states that change implicitly (e.g., a "total spend" changing because one item in a past order was refunded).
  • Rules are First-Class Citizens: Most memory systems focus on storing facts. However, derived state requires rules. The authors argue that rules must be versioned and stored just like facts to handle evolving logic.
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.

Key Results

  • Reliability Gap: On MemDerive, memory systems achieved only 30.41–48.30% accuracy, significantly lower than BM25 at 58.28%.
  • Failure Diagnosis: 61–85% of wrong answers contained an "ungathered" state—meaning the system could answer a direct question about the intermediate fact, but failed to retrieve it when it was needed as part of a larger query.
  • Maintenance: While systems preserved ~92% of unchanged answers, they only successfully refreshed 41.1% of implicit changes, compared to ~82% for explicit changes.
  • Cost vs. Benefit: Memory systems shift the computational cost to the ingestion phase (extracting facts), but this work currently "buys neither accuracy nor refresh" for derived state tasks.

Limitations and Future Work

The authors acknowledge that MemDerive focuses on logical and deterministic derivation. It does not currently cover:

  • Subjective Preferences: "What kind of games does Nate usually like?"
  • Open-Ended Planning: "Plan a trip for Nate based on his history."
  • Natural Language Nuance: While the history is in natural language, the underlying logic is strictly symbolic.

The paper concludes with a call for memory systems to adopt principles from database theory, specifically incremental view maintenance and dependency tracking, to ensure that derived states remain accurate and accessible as an agent's history grows.

Summary updated

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.
BibTeX
@misc{gao2026memderive,
  author = {Sen Gao and Yongan Li and Han Chen and Bingsheng He and Ming Wu and Jason Zeng and Michael Heinrich and Shixuan Sun},
  title = {{MemDerive: A Diagnostic Benchmark for Agent Memory over Evolving Data}},
  year = {2026},
  eprint = {2610.25373},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.25373},
}
Figure