Technical Summary: TEPA - Revoking Stale Memories for Conflict-Robust Language Agents

1. Problem Formulation: Memory Pollution

The paper identifies a critical failure mode in long-term language agents termed memory pollution. While persistent memory allows agents to reuse facts, preferences, and task experiences, it introduces a falsifiability problem: when the environment or user preferences change, stale memories may remain retrievable and dominate the prompt, leading to incorrect actions.

Unlike general concept drift, this issue is specific to language agents where "stale objects" are textual evidence inserted directly into the prompt. The authors define stale-conflict consolidation as the scenario where later observations supersede earlier values under the same key (e.g., a user changing a preference or a tool regime shifting). The core challenge is determining whether persistent memory remains useful when its own evidence must be falsified.

The paper quantifies this failure using a Memory Pollution Index (MPI). If a method's success rate ($S_{m,\phi}$) in a reversal phase falls below the success rate of an agent with no memory ($S_{NoMem,\phi}$), the memory is considered polluting ($MPI > 0$). The authors hypothesize that append-only memory, which keeps all evidence active, can become worse than having no memory at all when stale evidence is retrieved alongside current facts.

2. Methodology: TEPA (Revocable Evidence-Memory)

The authors propose TEPA, a mechanism that treats memory validity as an explicit state rather than a static repository.

Core Mechanism

TEPA represents observations as keyed precedents ($p = (k, v, s, f, \sigma, \tau)$), where:

• $k$: Conflict key (e.g., a preference slot or tool regime).
• $v$: Asserted value.
• $s, f$: Support and conflict counts.
• $\sigma$: Lifecycle state ($Hypothesis$, $Active$, or $Revoked$).
• $\tau$: Creation time.

Lifecycle Transitions

1. Conflict Detection: When new evidence $(k_t, v_t)$ arrives, TEPA checks for active precedents sharing the same key $k_t$.
2. State Updates:
   • If the value matches, the support count ($s$) increases.
   • If the value conflicts, the conflict count ($f$) increases.
3. Revocation: A precedent is moved from the Active set to the Revoked archive if:
   • Its posterior mean validity (estimated via a Beta-Bernoulli model) falls below a threshold $\theta_{rev}$ after a minimum number of observations ($n_{min}$).
   • OR, its recent success rate falls below $\theta_{rec}$ given sufficient recent outcomes.
4. Promotion: New candidates enter a Hypothesis state. They are promoted to Active only if their posterior validity exceeds $\theta_{pro}$ or if they pass trial validation.

TEPA Variants

• TEPA-Rev (Default): Uses the lifecycle state transitions described above.
• TEPA-Full: Adds a trial-by-execution step before promotion. A candidate precedent is tested on support, counterfactual, and contamination tasks. It is promoted only if it passes a majority of trials (e.g., $\ge 60\%$ positive) and succeeds in at least one support trial. This variant is specifically used for preference-update streams.

Retrieval

The retriever only accesses the Active set ($A_t$). Revoked precedents ($R_t$) are excluded from the prompt but preserved in an archive for audit and potential re-promotion.

3. Experimental Setup

The evaluation spans four distinct settings to test robustness against hidden regime drift and preference changes:

1. Controlled Hidden-Regime Drift: Simulates tool-regime reversals where the correct action changes.
2. Real File-Backed Executable Drift: Tests the mechanism with actual file I/O and tool execution.
3. Preference-Update Stream: Simulates corrections to long-term user profiles based on fresh session feedback.
4. MemoryAgentBench: Uses the SH-6k benchmark for single-hop fact consolidation, with MH-6k and long-context variants for boundary testing.

Baselines include:

• No Memory: Agent has no access to past evidence.
• Append-Only: All evidence remains active.
• Last-Write-Wins (LWW): Only the most recent successful same-key experience is kept.
• Temporal/Reactive Forgetting: Various sliding window and failure-based clearing mechanisms.
• Oracle Reset: A diagnostic upper bound that knows phase boundaries.

4. Key Results

Memory Pollution in Reversal Phases

In both Controlled and Executable drift benchmarks, append-only and Last-Write-Wins (LWW) memory systems collapsed during full reversal phases:

• Append-Only/LWW Success: $\approx 0.210$ (Controlled) and $0.203$ (Executable).
• No Memory Success: $\approx 0.309$ (Controlled) and $0.298$ (Executable).
• Result: Append-only memory performed worse than having no memory, confirming the existence of memory pollution (MPI $\approx 0.31$).

TEPA Performance

TEPA successfully prevented this collapse by revoking stale precedents:

• TEPA Success: 0.950 in both Controlled and Executable reversal phases.
• Comparison: TEPA significantly outperformed append-only memory (difference $\approx 0.74$, $p < 0.001$) and matched the performance of an Oracle Reset in terms of adaptation speed after the initial transition cost.

Preference Updates

In preference-update streams, where semantic similarity might keep stale profiles active:

• Append-Only: Collapsed to $0.138$ success.
• TEPA-Full: Achieved 0.910 overall success, statistically indistinguishable from the "No Memory" baseline ($0.837$) in the absence of pollution, but significantly better than baselines that failed to revoke.
• Insight: Validation (TEPA-Full) and lifecycle revocation play complementary roles; validation filters candidates, while revocation clears active but superseded preferences.

MemoryAgentBench (Single-Hop)

On the SH-6k benchmark (clean single-hop fact consolidation):

• TEPA-Rev: 0.890 (substring exact match).
• Last-Write-Wins: 0.890.
• TEPA-NoRev: 0.630.
• Conclusion: For single-hop facts where the latest fact is directly observed, current-key replacement (LWW) is decisive. TEPA's lifecycle machinery is most critical in drift and preference settings where updates must be inferred from interaction outcomes.

Boundary Conditions

TEPA's effectiveness degrades in complex retrieval scenarios:

• SH-32k: 0.680 success.
• MH-6k (Multi-hop): 0.040 success.
• SH-262k (Long Context): 0.000 success.
• Implication: Fact-level revocation solves single-hop conflicts, but multi-hop chain construction and long-context selection remain unsolved architectural challenges.

5. Significance and Contributions

The paper makes three primary contributions:

1. Problem Definition: It formally characterizes memory pollution as a validity-state failure where persistent memory degrades agent performance below the "no memory" baseline.
2. Mechanism Proposal: It introduces TEPA, a revocable evidence-memory mechanism that explicitly tracks the lifecycle state (Hypothesis, Active, Revoked) of precedents, allowing for the removal of contradictory evidence while preserving it for audit.
3. Empirical Validation: It demonstrates that revocation is a necessary operation for agents operating in dynamic environments. The results show that without explicit revocation, agents can be actively harmed by their own memories.

Authors' Claims on Significance

The authors conclude that persistent memory must track validity alongside relevance. A memory item can be relevant and recent but still wrong if its value has been superseded. TEPA establishes lifecycle revocation as a core memory operation, enabling agents to falsify, audit, and re-promote evolving knowledge. The work suggests that while single-hop fact consolidation is solved by key replacement, future work must address retrieval-chain construction and context selection for multi-hop and long-context scenarios.