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.
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:
- Symbolic Specification: Scenarios are defined using Datalog rules. This ensures an "exact ground truth" for every intermediate step of a query.
- 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).
- 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).
- 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).
- 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.
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