MEME Benchmark Reveals Critical Flaws in LLM Memory Systems: Dependency Reasoning Accuracy Below 50%

Why Memory Has Become the Core Bottleneck for AI Agents

As large language models increasingly operate as intelligent agents engaging in multi-turn, cross-session interactions with users, the ability to accurately store, update, and reason over past interaction information has become a key metric for measuring agent capability.

Current AI Agent memory systems generally fall into three technical paradigms: RAG (Retrieval-Augmented Generation) based on vector retrieval, which encodes historical conversations as vectors and recalls them through similarity matching; structured memory based on LLM summary extraction, where the model actively extracts key facts from conversations and stores them in a knowledge base; and agent-based memory using file systems, where the LLM reads and writes memory files like documents. Each paradigm has its strengths and weaknesses, but they all face a common challenge: how to maintain memory consistency and accuracy in a dynamic environment where information is constantly being updated.

Here's an intuitive example: when a user tells their AI assistant they've just moved to a new city, the assistant not only needs to record the new address but also realize that information previously associated with the old address—such as commute times or supermarket recommendations near the old home—is now invalid and shouldn't be used to answer questions. This seemingly simple scenario actually places extremely high demands on memory systems.

New research from KAST University of Tübingen and Never AI Lab proposes the MEME (Multi-Entity Evolving Memory Evaluation) benchmark, which for the first time systematically evaluates the dependency reasoning performance of mainstream memory systems—with quite surprising results: even the best-performing system achieves less than half accuracy.

Three Blind Spots in Existing LLM Memory Evaluation Systems

The Evolution of Memory Evaluation

Memory evaluation has gone through several generations of iteration: the earliest were single-turn long-context benchmarks testing whether models could remember information from long texts in one pass; these evolved into multi-session static fact retention tests; then came benchmarks with dynamic updates, testing whether entity values could be promptly updated when they changed across sessions.

But all these evaluations share a common blind spot: they only test independent entity updates and completely ignore dependency reasoning between entities.

Three Key Capabilities That Have Never Been Tested

The paper identifies three categories of tasks entirely missing from existing benchmarks:

1. Cascade Effect: When upstream entity information is modified, do downstream facts that depend on it automatically update? The concept of cascade effects originates from research in Knowledge Editing. Knowledge editing aims to modify specific facts stored internally in large models without affecting other knowledge, but researchers early on discovered that modifying one fact often triggers chain reactions—for example, after changing "the capital of France" from Paris to Marseille, can the model automatically infer that "the city where the Eiffel Tower is located" should also be updated? This cascade consistency problem has been widely discussed in parameter-level knowledge editing, but has barely been systematically evaluated in external memory systems. MEME is the first to extend this problem from model internals to external memory architecture.
2. Missing Reasoning: When upstream values change but there's no corresponding update rule, can the system correctly output "uncertain"?
3. Deletion Verification: After a user explicitly requests deletion of a fact, does the system truly stop mentioning it?

Compared to well-known benchmarks like ROAR, Nolima, LoCoMo, and LongMemEval, they cover at most three tasks—exact recall, aggregation, and tracking—while deletion, cascade, and missing tasks are completely absent. MEME is the first evaluation benchmark to comprehensively cover all six tasks.

MEME's Two-Dimensional Evaluation Framework Design

Entity Scope and Temporal Dynamics: Two Orthogonal Dimensions

The paper proposes a clear two-dimensional evaluation framework:

• Entity scope dimension: Divided into single-entity and multi-entity, analogous to single-hop and multi-hop reasoning in question answering. Single-hop reasoning only requires locating one information source to answer, while multi-hop reasoning requires extracting and combining information from multiple sources, with difficulty increasing exponentially.
• Temporal dynamics dimension: Divided into static and evolving, corresponding to the cascade effect problem in knowledge editing. In static scenarios, information never changes once written, while in evolving scenarios, the same entity's value updates repeatedly over time, and the system must always track the latest state.

These two dimensions were previously studied separately, but in real interaction scenarios they coexist. Updating one entity's information may propagate changes along dependency chains to affect multiple downstream entities, making joint evaluation essential for practical relevance.

Detailed Breakdown of Six Evaluation Tasks

Based on the two-dimensional framework, MEME defines six representative tasks:

Retrieval tasks (static dimension):

• Exact Recall: Verbatim reproduction of a single static entity's information, such as accurately stating a user's birthday
• Aggregation: Integrating information about multiple static entities scattered across different sessions

State management tasks (single-entity dynamic):

• Tracking: Reconstructing the complete modification history of a single entity in chronological order
• Deletion: After a user requests fact removal, the system no longer reports that information

Dependency reasoning tasks (multi-entity dynamic):

• Cascade: Inferring downstream entities' new values based on dependency rules and upstream updates
• Missing: Correctly outputting "uncertain" when upstream values change but no corresponding rule exists

Dataset Construction: Verifiable Design Based on DAG Knowledge Graphs

Knowledge Graph-Driven Data Generation

MEME's dataset is generated based on Directed Acyclic Graph (DAG) knowledge graphs covering two domains. A DAG is a directed graph structure without cycles, widely used in computer science to represent dependencies—for example, module dependencies in build systems or prerequisite relationships in task scheduling. In the MEME benchmark, DAGs model dependency chains between entities: nodes represent entities (such as a user's address or commute method), and directed edges represent dependencies (commute time depends on home address and workplace). This structure naturally supports topological sorting, enabling precise calculation of which downstream nodes need synchronous updates when upstream nodes change, thereby providing verifiable gold answers for cascade and missing tasks.

The two specific domains covered are:

• Personal life scenarios: 39 entities, 34 dependency edges
• Software project scenarios: 51 entities, 27 dependency edges

A total of 100 evaluation episodes were generated, each containing approximately 35,000 tokens of conversational context, producing 694 post-change evaluation questions in total. All entity values use fictitious names to prevent LLM parametric knowledge from interfering with evaluation results.

Five-Step Construction Pipeline

Each evaluation episode strictly follows a five-step construction process: select entity set → assign initial values with consistency checks → assign tasks based on topological roles → generate natural conversations through a mixed approach → insert distractor content. Conversation generation uses GPT-4O self-chat, dependency rules are inserted directly via templates to ensure accuracy, followed by two-layer LLM verification (GPT-4O annotation + Gemini 2.5 Flash semantic review).

This design ensures all task gold answers are verifiable, especially for cascade and missing tasks—answers don't appear directly in conversations but are computed through DAG rule propagation.

Experimental Results: All 6 Mainstream Memory Systems Fail Comprehensively

No System Is Spared

The paper evaluates 6 mainstream memory systems covering three major technical paradigms:

• Raw retrieval: BM25, Text Embedding 3 Small. BM25 is a classic information retrieval algorithm based on term frequency statistics, belonging to sparse retrieval methods. It ranks documents by computing lexical overlap between query terms and documents, performing well on exact keyword matching but lacking semantic understanding. In contrast, Text Embedding methods belong to dense retrieval, mapping text to high-dimensional vector spaces and measuring semantic proximity through metrics like cosine similarity, capturing synonyms and semantic associations but potentially underperforming BM25 on exact matching.
• LLM-processed memory: Memo-Me, GraphTD. These systems use large models to process raw conversations during information ingestion, extracting structured facts or building knowledge graphs, attempting to organize and relate information at the storage stage.
• File-agent based: Carp-Wiki, MD-Flat. These systems give LLMs file operation capabilities, letting them create, edit, and query Markdown files or Wiki pages like humans managing notes, theoretically offering maximum flexibility.

All systems uniformly use GPT-4 Mini as both the internal LLM and answer LLM, eliminating interference from model capability differences.

The results are striking: the best-performing MD-Flat achieves an overall accuracy of only 0.42. Dependency reasoning tasks collapse entirely—cascade tasks average only 0.3 accuracy, and missing tasks drop to 0.1, far below static task performance levels.

The Compounding Effect of Multi-Entity + Evolving Scenarios

• From single-entity to multi-entity: average accuracy drops by 0.31
• From static to evolving: average accuracy drops by 0.228
• When both dimensions apply simultaneously (multi-entity + evolving): accuracy drops directly to 0.2

This is precisely the most common real-world scenario—multiple related entities changing continuously over time—and existing systems almost completely fail in this setting.

Root Cause Analysis: Retrieval Bottlenecks and Reasoning Breakdowns

Retrieval Stage Is the Core Bottleneck

The paper decomposes memory systems into encoding, maintenance, and retrieval stages for tracking analysis, finding that most systems actually perform fine during encoding and maintenance—rules and change events are properly stored. The problems concentrate at the retrieval stage:

• GraphTD: Change event edges rank outside TopK and aren't retrieved
• Carp-Wiki: The query agent only reads old files and doesn't open new log files containing change events
• BM25: Change events rank too low because keywords in change descriptions don't exactly match query phrasing, resulting in low term-frequency matching scores
• A few systems (Text Embedding, Memo-Me) do retrieve change events, but the answer LLM still uses old values, exposing reasoning deficits when models face conflicts between new and old information

Five Intervention Approaches Almost All Fail

The authors attempted five interventions without changing the architecture:

Intervention	Effect
Prompt optimization (DSPY-SIM)	Cascade and missing accuracy remain near floor
Increased retrieval depth (TopK→40)	Cascade still near 0, missing improves slightly then drops
Stronger answer LLM (Claude Sonnet 4)	Only slight improvement on missing task
Reduced distractor content	Completely ineffective
Stronger internal LLM (Claude Opus 4)	Only effective approach, but costs 70x baseline

The DSPY-SIM approach uses Stanford's DSPY declarative framework, which allows developers to define input/output signatures and modular reasoning steps, then uses a compiler to automatically search for optimal prompt combinations and few-shot examples. However, experimental results show that even with automatic optimization, prompt-level improvements provide extremely limited gains for dependency reasoning tasks, indicating the root problem lies at the architectural level rather than the instruction level.

The only effective solution is MD-Flat paired with Claude Opus 4—during the Ingest phase, it proactively scans dependency entries and writes propagated new values directly to storage, bypassing the retrieval bottleneck. But the 70x cost makes it impractical for real-world deployment.

Future Directions: From Recall Optimization to Dependency Propagation Mechanisms

The MEME benchmark is the first to comprehensively expose the structural deficits of current LLM memory systems in dependency reasoning. The core findings can be summarized in three points:

1. The bottleneck is retrieval, not storage: Information is stored correctly but can't be retrieved, or is retrieved but reasoned about incorrectly
2. Traditional tuning approaches are essentially ineffective: Prompt optimization, increased retrieval depth, and other conventional methods show almost no improvement for dependency reasoning tasks
3. Architectural innovation is needed: For example, proactive dependency propagation during the Ingest phase, or optimized retrieval ranking logic that prioritizes change events over old values

Proactive dependency propagation during the Ingest phase is essentially a "propagate-on-write" strategy, similar to materialized view update mechanisms in databases—when an upstream entity change is detected, it immediately computes all downstream entities' new values along the dependency chain and writes them to storage, shifting computational cost from query time to write time, trading space and write cost for query-time accuracy. This approach provides an important reference for next-generation memory system architecture design.

Previously, the industry focused more on memory recall rates. Now MEME tells us: dependency propagation is the more critical pain point. This points the way for next-generation memory system design—systems must not only remember well but also "reason through" the implications.

Key Takeaways

• MEME is the first complete evaluation benchmark covering six memory tasks including cascade, missing, and deletion, filling the gap in dependency reasoning testing left by existing benchmarks
• All six mainstream memory systems fail comprehensively: the best MD-Flat achieves only 0.42 accuracy, cascade tasks average only 0.3, and missing tasks drop to 0.1
• In real-world scenarios with multi-entity + dynamic evolution, accuracy drops to 0.2—existing systems essentially fail in the most common scenarios
• Root causes concentrate at the retrieval stage rather than storage, with traditional interventions like prompt optimization and increased retrieval depth proving almost ineffective
• The only effective solution is proactive dependency propagation during the Ingest phase (Claude Opus 4), but at 70x baseline cost, pointing toward future architectural innovation directions