MEME: When LLM Agents Forget What They Just Learned

Paper: 2605.12477 Authors: Seokwon Jung, Alexander Rubinstein, Arnas Uselis, Sangdoo Yun, Seong Joon Oh Categories: cs.LG, cs.CL

The Gap

Existing memory benchmarks for LLM agents (MemoryBank, Memorag) test only single-entity updates: “Alice moved to Boston” or “Bob’s phone changed.” They measure whether the agent can retrieve the new fact. But real persistent environments demand more: when Alice moves, her old address becomes invalid. When Bob quits the company, his access credentials should be revoked. Prior work never tested whether agents understand these dependency chains or can reason about what’s no longer true.

Prior benchmarks:
  Single entity update --> Can you retrieve it? --> Done
                                                     
This paper's insight:
  Multi-entity world --> Update propagates --> What else changed?
                    \                      \
                     --> Entity removed --> What's now absent?
                                       \
                                        --> Cascade effects?
                                        
  Problem: Agents retrieve facts but don't reason about implications
       |
       v
  Hypothesis: Dependency reasoning (Cascade/Absence) will collapse
       |
       v
  Method: MEME benchmark with 6 tasks spanning multi-entity × evolving axes
       |
       v
  Evidence: All systems score 1-3% on Cascade/Absence vs 60-80% on retrieval
       |
       v
  Conclusion: Current memory paradigms lack dependency reasoning capability

The Increment

One sentence: Before MEME, we knew agents could store facts; after MEME, we know they cannot reason about what those facts imply for other entities or what becomes false when entities are removed.

Core Mechanism

MEME defines a 2×3 task grid. The first axis: single-entity vs multi-entity (does an update affect one entity or propagate to others?). The second axis: static, evolving, deletion (does the world stay fixed, change over time, or lose entities?). This creates six task types. Three were covered by prior work (single-entity static/evolving/deletion). Three are new: multi-entity evolving (Cascade), multi-entity deletion (Absence), and a harder variant of single-entity deletion that tests post-removal state.

Each episode runs 100 turns. The agent receives updates (“Alice joined project X,” “Bob manages Alice,” “Project X was cancelled”) and must answer queries that require chaining facts (“Who manages people on active projects?”) or recognizing absences (“Is Alice still on any project?”). The benchmark controls for confounds: filler noise (irrelevant updates), retrieval difficulty (how many hops), and entity count.

Episode structure:
  
  Turn 1-100:
    Update --> Memory system --> Query --> Agent response
      |            |              |            |
      v            v              v            v
    Facts      Store/Index    Retrieve     Reason --> Answer
    
  Memory system types tested:
    - Semantic (vector DB)
    - Episodic (conversation history)
    - File-based (structured storage)
    
  Query types:
    Static:    "What is X's current state?"
    Cascade:   "After Y changed, what else changed?"
    Absence:   "What is no longer true about Z?"

Think of MEME as a stress test for a librarian. Prior benchmarks asked: “Can you find the book I just shelved?” MEME asks: “The author died—which books are now out of print? Which co-authored works are affected? If I remove this book, what references in other books become broken?” The librarian can locate individual books (retrieval works) but has no system for tracking these dependency chains. When you ask “what’s affected?”, they stare blankly because their index only maps titles to locations, not implications to consequences.

Key Concepts

• Cascade reasoning: When entity A changes, what happens to entities B, C, D that depend on A? Example: Alice leaves the company. Her direct reports now have no manager. Projects she led are now leaderless. Her access badges are invalid. The agent must trace these dependency edges and update its understanding of all affected entities. Current systems retrieve “Alice left” but don’t propagate the implications—they answer queries about Alice’s reports as if nothing changed.

• Absence reasoning: After entity X is deleted, what facts about X are no longer true? This isn’t just “X doesn’t exist”—it’s recognizing that all relationships involving X are now void. If project X is cancelled, “Alice works on X” becomes false, “X has deadline March 1” becomes meaningless, “X depends on Y” is no longer a constraint. The agent must actively recognize these absences rather than hallucinating stale facts. Current systems often retrieve old facts about deleted entities because deletion doesn’t trigger a cleanup pass through dependent facts.

• Multi-entity vs single-entity: Single-entity updates are local (“Alice’s phone number changed”). Multi-entity updates have ripple effects (“Alice became Bob’s manager” affects both Alice’s and Bob’s state, plus anyone querying the management chain). The distinction matters because multi-entity updates require the memory system to maintain a graph of relationships, not just a bag of facts. When you update one node, you must traverse edges to find what else needs updating. Current vector databases don’t model these edges—they embed facts independently.

Framework Shift

Before (prior benchmarks):              After (MEME):

  Update                                  Update
    |                                       |
    v                                       v
  Store fact                              Store fact
    |                                       |
    v                                       +---> Propagate to dependents
  Query                                     |         |
    |                                       |         v
    v                                       |     Update B, C, D
  Retrieve fact --> Answer                  |         |
                                            v         v
  [Treats memory as key-value store]      Query   Retrieve + Reason
                                            |         |
                                            v         v
                                          Answer   "What changed?"
                                          
  [Treats memory as dependency graph]

From isolated fact storage to relational reasoning, the core shift is recognizing that memory is not a database of independent entries but a web of implications that must be maintained under updates.

Expert Assessment

Problem choice: Real gap. LLM agents are being deployed in persistent environments (customer service, personal assistants, enterprise tools) where they must track evolving state across sessions. The fact that all current systems collapse on dependency reasoning (1-3% accuracy) while maintaining decent retrieval (60-80%) is a smoking gun—we’ve been optimizing the wrong thing. This sits at the intersection of two active research threads: long-context reasoning and agentic memory systems.

Method maturity: The benchmark design is clean. The 2×3 task grid is well-motivated, the controlled episodes avoid confounds, and the evaluation metrics are appropriate. However, the paper doesn’t propose a solution—it’s purely diagnostic. The file-based agent with Claude Opus 4.7 partially closes the gap but at 70× cost, which the authors correctly flag as impractical. The lack of a scalable fix is honest but leaves the reader wanting more. A follow-up proposing a dependency-aware memory architecture would be the natural next step.

Experimental integrity: Baselines are fair—six memory systems spanning three paradigms (semantic, episodic, file-based) with multiple LLM backbones. The ablations (prompt optimization, deeper retrieval, reduced noise, stronger LLMs) systematically rule out easy fixes. The 100-episode sample size is adequate for the controlled setting. One concern: the tasks are synthetic (generated entity graphs), so it’s unclear how results transfer to real-world messiness where dependencies are implicit and noisy. The paper acknowledges this but doesn’t test on naturalistic data.

Writing quality: The abstract and introduction are crisp. The related work section is thorough. The results section is dense with tables—Figure 3 (the cascade/absence failure modes) should be moved earlier to motivate the problem viscerally. The discussion of why current systems fail is too brief (one paragraph on page 7)—this deserves a full subsection with error analysis and failure case walkthroughs. The conclusion punts on solutions, which is defensible for a benchmark paper but feels incomplete.

Verdict: weak accept — Identifies a real, underexplored failure mode in deployed systems with rigorous evaluation, but lacks actionable insights beyond “current approaches don’t work.”

Takeaways

If you’re building an LLM agent with persistent memory, steal these ideas:

1. Test dependency reasoning explicitly: Don’t just check if your agent retrieves updated facts—test if it understands what else changed. Add synthetic cascade queries to your eval suite.

2. Model relationships as first-class entities: Vector embeddings of isolated facts won’t cut it. You need an explicit graph (even a simple adjacency list) tracking which entities depend on which. When entity A updates, traverse edges to find affected entities.

3. Implement deletion as active cleanup: When an entity is removed, don’t just mark it deleted—walk the dependency graph and invalidate all facts involving it. Otherwise, your agent will hallucinate stale relationships.

4. The file-based agent’s partial success suggests a path: Structured storage (JSON, SQL) where relationships are explicit outperforms vector DBs on dependency reasoning. The tradeoff is retrieval speed and flexibility, but for high-stakes applications (medical records, financial systems), correctness trumps convenience.

5. Prompt engineering won’t save you: The paper tried prompt optimization and it barely moved the needle. This is an architectural problem, not a prompting problem. If your memory system doesn’t track dependencies, no amount of “think step by step” will make the agent infer them reliably.