TEPA: When Memory Needs a Delete Key, Not Just a Save Button

Paper: 2608.07429 Authors: Yan Zhou, Yue Ouyang, Kaiyang Zheng, Suncheng Xiang Categories: cs.AI

The Gap

Everyone building long-term memory for agents has converged on roughly two designs. The first is append-only: every observation, reflection, or summary gets embedded and dumped into a vector store, and retrieval is top-k similarity. This is the Generative Agents / MemoryBank / most-RAG-over-chat-logs lineage. The second is last-write-wins (LWW): maintain a key-value cache of “current facts,” and when a new fact arrives for an existing key, overwrite it. This is what most production assistant memories actually do with user preferences.

Both make the same silent assumption: that a stored memory is true until something more relevant comes along. Append-only makes staleness a ranking problem — the obsolete fact is still in the index, still semantically close to the query, and often still wins top-k because it was stated more explicitly than its replacement. LWW makes staleness a destruction problem — it fixes the retrieval set but throws away the history, so the agent can never explain why it believes what it believes, and can never re-adopt an old value if the world flips back.

The paper’s framing is the sharp part: memory persistence creates a falsifiability problem. An agent that cannot mark a memory as false is an agent whose beliefs cannot be corrected, only outvoted. And the headline evidence is the kind of result that makes you sit up: under full reversal of the environment, both memory systems scored *worse than having no memory at all (0.210 for both, versus 0.309 for a memory-free agent). Memory became a liability.

  [ agent stores fact F under world state W0 ]
                     |
                     v
       [ world moves to W1, F is now false ]
                     |
                     v
   [ F is still active + still retrievable + still fluent ]
                     |
                     v
      *problem*: "memory pollution" -- worse than no memory
                     |
    assumption: validity is a STATE of a memory record,
                not a side effect of recency or rank
                     |
                     v
     method: keyed precedents + explicit revocation
             read path sees active only
             audit path sees everything
                     |
        +------------+-------------+---------------+
        |            |             |               |
        v            v             v               v
  hidden-regime  real file    MemAgentBench   multi-hop /
  drift, 50 seed  exec drift     SH-6k         long ctx
   .950 vs .210  .950 vs .203  ties with LWW   both fail
        |            |             |               |
        +------------+-------------+---------------+
                     |
                     v
   conclusion: revocation is a first-class memory op,
   alongside write() and read() -- but it only fixes
   fact-level validity, not retrieval chains

The Increment

One sentence: Before, agent memory had write and read and hoped conflicts would sort themselves out at ranking time; after, memory has a revoke operation and a validity flag, so conflicts are resolved at write time and the stale record survives for audit instead of being either retrieved or destroyed.

Core Mechanism

TEPA stores observations as keyed precedents. A precedent is not just an embedded string; it is a record with a key (the slot the claim is about), a value (the claim), the evidence that produced it (a tool call, a file read, a user utterance), a timestamp, and — the load-bearing addition — a status in {active, revoked}. The key is what makes conflict detectable: two claims collide not because they are semantically similar, but because they are answers to the same question.

The write path does the work. A new observation gets a key extracted, then the store is checked for an active precedent under that same key. If none exists, insert as active. If one exists and the new evidence contradicts it, the old precedent’s status flips from active to revoked — it is not deleted, its evidence and the reason for revocation stay attached — and the new precedent is inserted as active. The read path is then almost trivially simple: retrieval filters on status == active, so a superseded fact is structurally incapable of entering the prompt. Two other paths fall out for free: an audit path that reads the full table including revoked rows, and re-promotion, where a revoked precedent can be flipped back to active if the evidence supporting it returns.

That last piece is what distinguishes this from soft deletion as a convenience. The claim is that in drifting environments, knowledge does not just decay — it oscillates. A deployment reverts, a config rolls back, a user changes their mind and then changes it back. If your only tools are append (keeps both, confuses retrieval) and overwrite (keeps one, forgets the other existed), you handle oscillation badly in both directions.

              new observation + evidence
                          |
                          v
                 [ key extraction ]
              key = (entity, attribute, scope)
                          |
                          v
            [ conflict check under SAME key ]
                    |            |
              no active       active + contradicts
              precedent            |
                    |              v
                    |     [ revoke old precedent ]
                    |      status: active -> revoked
                    |      keep: evidence, time, reason
                    |              |
                    +------+-------+
                           |
                           v
                 [ insert new as active ]
                           |
                           v
      +-------------------------------------------------+
      |              precedent store                    |
      | key   value   status    t    evidence           |
      | k1    v_new   active    t3   file:cfg.yaml      |
      | k1    v_old   REVOKED   t1   chat turn 4        |
      | k2    v_a     active    t2   tool:search        |
      +-------------------------------------------------+
           |                              |
           | read path                    | audit path
           v                              v
   filter status == active         read ALL rows,
           |                       replay belief history
           v                              |
     prompt context                       v
   (stale row cannot                 re-promote:
    appear here)                REVOKED -> active if
                                 evidence returns

Think of it as common law, which is clearly where the authors got their vocabulary. Each stored observation is a decided case. The key is the legal question the case answers — “what is the deploy target for service X?” — and the value is the holding. When a new case comes before the court on the *same question with contradicting evidence, the court does not shred the old ruling; it overrules it. The old case stays in the reporter, fully readable, with a note explaining what overruled it and when. But it is no longer *citable — a lawyer writing a brief today (the retrieval step assembling a prompt) may only cite good law.

The metaphor pays for itself on the two features that would otherwise seem arbitrary. Why keep revoked records instead of deleting them? Because a legal system whose overruled cases vanished could not explain its own reasoning, and neither can an agent that has to justify a decision after the fact. Why allow re-promotion? Because courts do revive overruled doctrines when circumstances return, and that is exactly the “regime flips back” case that breaks both baselines. And it clarifies the failure modes too: append-only memory is a law library where every ruling ever made is equally citable, so the brief is incoherent. LWW is a library that physically destroys overruled cases, so there is no appellate record at all.

Key Concepts

• Memory pollution: The counterintuitive fact that memory can make an agent *worse than amnesia. Imagine you ask a colleague where the standup meeting is. Someone who has never been told anything says “I don’t know, check the calendar” — mildly useless, but harmless. Someone who was told six months ago “Room 4B” and never updated says “Room 4B” with total confidence, and you walk to an empty room. The no-memory agent falls back to reasoning or fresh lookup; the polluted agent short-circuits that with a fluent wrong answer. That is exactly the 0.210-below-0.309 result: the stale memory doesn’t just fail to help, it actively suppresses the recovery behavior the agent would otherwise have used.

• Keying (and why it’s the real work): A “key” is a canonical name for the question a memory answers. The hard part is not storing the flag, it is deciding that “we deploy to us-east-1” and “the production region is Virginia” are answers to the same question, while “the staging region is Virginia” is not. Get keying too coarse and you revoke facts that were both true; too fine and conflicts go undetected and you’re back to append-only. Everything in this paper’s write path routes through key extraction, which is why I’d want to see it stress-tested more than the abstract suggests it was.

• Validity as state vs. recency as proxy: Most systems approximate validity with a timestamp — newer is truer. That breaks in ordinary cases. A high-confidence measurement from Tuesday should not be overturned by a user’s offhand guess on Wednesday; a tool result that just returned “file not found” because of a transient permission error should not revoke a verified fact. Making validity an explicit, writable state means the *decision to invalidate becomes a place you can put policy, logging, and later, confidence thresholds. Recency gives you no such seam.

Framework Shift

Before (mainstream approach):          After (this paper):

  observation stream                    observation stream
        |                                     |
        v                                     v
  [ embed + append ]                   [ extract key ]
        |                                     |
        v                                     v
  +-----------------+                  [ conflict? revoke ]
  | m1  m2  m3  m4  |  all equal             |
  | m5  m6  m7 ...  |  citizens              v
  +-----------------+                 +------------------------+
        |                             | k1 v1 ACTIVE           |
        v                             | k1 v0 revoked <-+      |
  top-k similarity                    | k2 v2 ACTIVE    |      |
        |                             +-----------------|------+
        v                                   |           |
  prompt holds BOTH                    read filter      |
  old and new claims                   (active only)    |
        |                                   |        audit /
        v                                   v        re-promote
  LLM must referee                    prompt holds
  the contradiction                   ONE current claim
  at inference time
                                      conflict was settled
  (or LWW: overwrite m_old,           at WRITE time, and
   history gone, no audit,            history survives
   no way back)                       read-only

From ranking to lifecycle: the core shift is moving conflict resolution out of the retriever’s scoring function and into the memory record’s state machine, so “is this still true?” stops being something the LLM has to infer from a polluted context window.

Expert Assessment

Problem choice: Real gap, and well-named. Anyone who has run a memory-enabled assistant for more than a few weeks has watched it confidently repeat a preference the user revised, or a project detail that changed. The field has spent its energy on *what to store (summarization, reflection, hierarchy) and how to find it (embeddings, graphs, hybrid search), and comparatively little on when to stop believing it. The “worse than no memory” measurement is the paper’s best contribution as a framing device — it converts a vague annoyance into a falsifiable regression. It sits naturally in the trajectory from RAG-as-lookup toward memory-as-database, and it borrows the right prior art conceptually even if it doesn’t seem to name it: this is essentially MVCC plus tombstones plus time-travel queries, applied to agent memory.

Method maturity: Honestly, thin. Soft-delete with a validity flag and a keyed upsert is a design pattern, not a discovery — any engineer who has built an audit-logged CRUD system has shipped this. The paper’s own strongest counter-evidence is in its own abstract: on clean MemoryAgentBench SH-6k, TEPA *ties last-write-wins, and the authors concede “current-key replacement is the decisive operation.” So the novel component — keeping revoked rows and allowing re-promotion — buys auditability and reversal handling, not accuracy on standard benchmarks. That’s a legitimate contribution, but it’s a systems/observability contribution wearing a mechanism paper’s clothes. What’s genuinely underexplored: the conflict-detection policy. When does new evidence contradict rather than merely differ? Confidence-weighted revocation, evidence-source priority, revocation that requires corroboration — those are the interesting open problems, and the abstract suggests the paper treats detection as given.

Experimental integrity: The numbers are where I’d push hardest. Append-only and LWW scoring *identically (0.210) under full reversal is suspicious, because those systems have different retrieval sets by construction — identical scores usually mean the metric has saturated at a floor, i.e. both fail every reversed item and the task is effectively binary. Symmetrically, TEPA hitting exactly 0.950 in two structurally different experiments (synthetic drift and real file-backed execution) smells like a ceiling determined by the task generator rather than a measured capability. That doesn’t make the direction wrong, but it means the effect size (0.21 to 0.95) is a property of the benchmark design, not a transferable improvement estimate. The deeper question the abstract doesn’t answer: why does LWW fail at 0.210 during reversal if it also does current-key replacement? The only consistent explanation is that the drift benchmark presents conflicting facts under keys LWW does not recognize as identical, in which case the headline gap is measuring the key-extraction module, not revocation. If so, the paper’s title is pointing at the wrong component. Credit where due: reporting failures on multi-hop and long-context settings, and reporting that the ablation-like SH-6k comparison is a tie, is more honesty than most papers in this area offer.

Writing quality: The abstract never expands the acronym, which is a small tell about polish. The bigger gap is that the mechanism is described in outcome language (“revokes active precedents when fresh evidence contradicts them”) rather than operational language — what counts as contradiction, how keys are derived, who decides, what happens on ambiguous or low-confidence evidence. Rewriting the method section to specify the conflict-detection predicate and the key function, with failure cases and an honest cost accounting (extra LLM calls per write? latency? storage growth?), would elevate the whole paper, because that section is currently doing the least work relative to its importance. A close second: a paragraph reconciling the 0.210 baselines with the SH-6k tie would preempt the exact objection every reviewer will raise.

Verdict: borderline — the problem framing and the “memory worse than no memory” result deserve to be in the literature, but the mechanism is standard database hygiene and the headline gap appears to be attributable to a component the paper doesn’t foreground.

Takeaways

Things worth stealing regardless of what you think of the paper:

• Ship a revoke operation in your memory API, not just write and read. Even if your conflict detection is dumb, having validity be an explicit column gives you a place to hang policy, logging, and debugging later. Retrofitting this into an append-only vector store is painful; adding the column on day one is nearly free.
• Separate the read path from the audit path. Retrieval filters to active records; incident review reads everything. This one split gives you “why did the agent say that?” for free, which is the question you will actually be asked in production.
• Benchmark against no-memory as a baseline. This is the paper’s most transferable methodological move. If your memory system can’t beat amnesia on a drifting task, you have a regression, and you would never see it comparing memory variants to each other. Add a reversal phase to your eval set: state a fact, use it, contradict it, then ask again.
• Test the flip-back case. Preferences and configs oscillate. Systems that only handle monotone updates silently fail here, and it’s cheap to test.
• The corollary the paper implies but doesn’t say loudly: if your fix for stale memory is “the LLM will notice the contradiction in context,” you have outsourced a database problem to a probabilistic reasoner. Settle conflicts at write time where the decision is auditable and cheap.

What not to take: the specific numbers. Treat 0.950 as “the mechanism works on a task designed to require it,” not as an expected improvement in your system.