Source-linked AI summary
What Eviction Destroys: A Restore-Counterfactual Audit of Forgetting in Agent Memory
Chen Shen
TL;DR
Budget–accuracy frontiers do not distinguish evidence destroyed by eviction from evidence retained but missed by retrieval. The paper introduces a per-question restore counterfactual that reinstates gold evidence and reruns the same reader, finding that restoration-based error decomposition identifies different failure sources while showing retrieval-regime dependence and benchmark-limited scope.
Problem
Existing budget–accuracy analyses quantify accuracy loss under tighter memory budgets but do not distinguish irreversible eviction losses from recoverable retrieval failures.
Method
The restore counterfactual reinstates each question’s gold evidence in read-time context, reruns the frozen reader, and combines correctness change with evidence retention to classify errors.
Results
At matched accuracy, no difference in irreversible rate is detected among tested policy pairs at a resolution of 1.2–6 percentage points.
Takeaways & Limitations
Budget–accuracy frontiers are not directly comparable unless their read-time retrieval regimes are reported, and the instrument identifies limiting components without ranking policies.
Takeaways & Limitations
The audit uses one benchmark, two readers, one primary judge, gold labels, and an oracle-answerable filter, limiting its scope to benchmark analysis.
Abstract
from arXiv · showhide
Agent memory systems must discard stored information when their history exceeds a fixed token budget. Existing budget-accuracy frontiers quantify the resulting loss in accuracy, but do not distinguish irreversible losses caused by eviction from recoverable retrieval failures. We introduce the restore counterfactual, a per-question paired intervention that reinstates the question's gold evidence in the read-time context and reruns the same reader. Combining the change in correctness with whether the evidence was retained after eviction classifies each oracle-answerable error as recoverable, irreversible, or residual; in the residual case, the answer remains incorrect after restoration. We evaluate FIFO, random, redundancy-aware, and LLM-importance eviction on LongMemEval-S at three budgets and under two retrieval regimes, using GPT-4o-mini as the primary reader and judge and GPT-5.4-mini as a robustness reader. Under top-k retrieval at an 80k-token budget, the irreversible share among errors corrected by restoration is 0.67-0.73 for FIFO, random, and redundancy-aware eviction, compared with 0.60 for LLM-importance. At 8k tokens, it reaches 1.00 for all four policies. Recoverable errors occur under top-k retrieval at 80k tokens but are absent under forced-gold injection by construction, so budget-accuracy results are not directly comparable unless the retrieval regime is reported. An exploratory matched-accuracy analysis detects no difference in irreversible rate among accuracy-matched policy pairs at a resolution of 1.2-6 percentage points. The same analysis detects the deliberately destructive control. To our knowledge, this is the first per-item, per-question restore-counterfactual audit of eviction for external agent-memory stores on a standard conversational benchmark.
1 Introduction
The paper addresses a gap in budget–accuracy analyses: they measure lost accuracy without distinguishing eviction-destroyed evidence from retrieval misses. It introduces a restore counterfactual that reinstates gold evidence and uses the result to decompose oracle-answerable errors.
- Budget–accuracy studies quantify accuracy loss under tighter memory budgets but do not characterize its composition.
- A frontier can conflate irreversible errors caused by eviction with recoverable errors caused by missed retrieval, despite their opposite remedies.
- The restore counterfactual reinstates question-specific gold evidence in read-time context and reruns the same reader.
- Combining restoration’s correctness change with evidence retention classifies oracle-answerable errors as recoverable, irreversible, or residual.
- The study evaluates this decomposition across four eviction policies, three budgets, and two retrieval regimes on LongMemEval-S.
2 Related work
Prior work studies budgeted retention, memory accuracy, and aggregate failure stages, but does not provide a per-question restore audit of eviction. This paper positions its intervention as an operational attribution of whether capacity-bounded forgetting caused downstream loss.
- Budgeted-memory studies propose retention methods or report accuracy–cost frontiers, but neither distinguishes irreversible losses from recoverable ones.
- Aggregate decompositions and retrieval-versus-utilization diagnostics locate failure stages, but do not attribute errors to a capacity-bounded eviction decision per item.
- The restore intervention reinstates an item and measures the resulting change, connecting this paper to leave-one-out context attribution and counterfactual memorization.
- The paper claims the first application of this intervention class to eviction from an external agent-memory store with end-task accuracy as outcome.
- Prior systems using serving-time restores or internal retrieval repair do not measure irreversible task loss caused by eviction.
- Because retained evidence can be missed by a frozen retriever, eviction effects must be interpreted under controlled retrieval conditions.
3 The restore counterfactual
The restore counterfactual compares a frozen reader’s policy answer with its answer after injecting the question’s full gold evidence. Evidence retention and restoration outcomes then separate destruction, retrieval misses, and residual reader failures under explicit assumptions.
- Estimator: The estimator reinstates the full gold evidence set Gq into read-time context after eviction and re-answers with a frozen pipeline.
- Estimator: Holding reader, prompt, decoding, judge, and ranker fixed makes restore gain measure the correctness effect of restoring Gq.
- Three-bin decomposition: A positive restoration flip is irreversible when at least one gold unit was evicted, and recoverable when all gold units survived.
- Denominator: The denominator contains oracle-answerable policy errors: questions correct under clean full-gold injection but incorrect under the policy.
- Three-bin decomposition: Residual errors remain incorrect after gold restoration and indicate that the reader failed to use the evidence.
- Inference: The decomposition reports stacked policy-by-budget shares with clustered bootstrap confidence intervals and separates residual reader-use failures.
- Assumptions: Interpretation relies on oracle-answerability, judge validity, and restore-tightness assumptions, including that full-gold restoration upper-bounds destruction.
4 Experimental setup
The evaluation uses LongMemEval-S histories under four eviction policies, three binding memory budgets, and two read-time retrieval regimes. It compares realistic top-k retrieval with forced-gold injection while using deterministic paired model judgments and a pre-specified bootstrap protocol.
- Design: The study evaluates four eviction policies at three budgets and under two retrieval regimes on one benchmark.
- Data: LongMemEval-S contains approximately 102k-token multi-session histories, 470 evidence-labeled questions, and excludes abstention questions.
- Policies: The policies are FIFO, random, redundancy-aware, and LLM-importance, alongside no-evict and a destructive control that evicts gold at approximately 3× baseline rate.
- Budgets: The store caps are 8k, 30k, and 80k tokens, all binding for the approximately 102k-token histories.
- Retrieval regimes: Forced-gold injection isolates destruction, whereas frozen top-k retrieval allows surviving gold evidence to be missed.
- Models: GPT-4o-mini is the deterministic reader and judge, with structural replication using GPT-5.4-mini as a reasoning reader.
5 Results
Under realistic top-k retrieval, eviction errors are dominated by destroyed evidence: irreversible shares exceed 0.5 at 80k tokens and reach 1.00 at 8k, while forced-gold restoration makes the two-bin share 1.00 by construction. Retrieval regime therefore changes the interpretation of budget–accuracy results, and matched-accuracy comparisons find no policy dissociation while detecting the destructive control.
- 5.1 Destruction is the majority component (R1): 1.00 is the forced-gold two-bin share across all 12 evicting/control cells because the recoverable bin is empty by construction.This construct reference isolates destruction but is an algebraic identity rather than evidence.
- 5.1 Destruction is the majority component (R1): 0.71, 0.73, and 0.67 are the 80k irreversible shares for FIFO, random, and redundancy-aware eviction, respectively.Each exceeds 0.5, whereas LLM-importance is 0.60 with a confidence interval spanning 0.5.
- 5.1 Destruction is the majority component (R1): 1.00 is the irreversible share at 8k for all four eviction policies, as tighter budgets destroy evidence rather than leave it unretrieved.At 80k, recoverable errors remain under top-k retrieval but are absent under forced-gold injection.
- 5.2 The two retrieval regimes are not interchangeable (R2): 4 of 12 evicting cells reject the recoverable-share gap between top-k and forced-gold retrieval after Holm correction.The gap concentrates at 80k; the rejection count is reproduced with GPT-5.4-mini.
- 5.3 At matched accuracy, no policy dissociates — and the test has power (R3): 0 of 9 accuracy-matched baseline pairs dissociate in irreversible rate, with |∆rate| ≤0.036 and every confidence interval spanning 0.The deliberately destructive control differs significantly in all 9 contrasts, showing that the statistic registers a large destructive difference.
- 5.4 Residual is reader-utilization failure (R4): 59→28 residual cases occur for no-evict at 80k under forced-gold injection with the stronger reader, showing that residual mass depends on the reader.Residual errors remain after full-gold restoration and are concentrated in cross-session aggregation.
6 Discussion
The measured error composition identifies which memory component needs improvement, but the audit does not select a best policy. Its conclusions are bounded by the tested benchmark, readers, judges, policy classes, budgets, and privacy-sensitive settings.
- 6 Discussion: Under tight budgets, improving retention takes priority over improving retrieval because better retrieval offers little benefit until more evidence is retained.The recoverable component is nonzero but depends on the retrieval regime.
- 6 Discussion: At matched accuracy, no difference in irreversible rate is detected among tested policy pairs at a resolution of 1.2–6 percentage points.The null is specific to the tested policies and budgets.
- 6 Discussion: The study is limited to one benchmark, two readers, one primary judge, policy classes rather than published systems, and an audit requiring gold labels and oracle-answerable filtering.The audit judge shares its provider, and the residual is reader-dependent.
- 6 Discussion: The instrument quantifies task costs of forgetting without prescribing retention, because deployment may require deletion for privacy or data-protection reasons.Required deletion can be audited for recoverable or irreversible task loss.
7 Conclusion
The restore counterfactual separates oracle-answerable memory errors into eviction destruction, retrieval misses, and reader non-use. These sources require different remedies, and the instrument does not rank policies.
- 7 Conclusion: The restore counterfactual separates oracle-answerable policy errors into what eviction destroyed, what retrieval missed, and what the reader failed to use.The decomposition applies under a memory budget.
- 7 Conclusion: Budget–accuracy frontiers are not comparable unless the read-time retrieval regime is reported.The conclusion frames the contribution as an analysis instrument rather than a policy ranking.
A Protocol constants & reproducibility
The protocol fixes readers, dataset, budgets, retrieval, restoration, seeds, and denominator construction to support reproducible comparisons. Restoration forces gold evidence and then fills remaining capacity with ranked retained snippets.
- A Protocol constants & reproducibility: GPT-4o-mini is the deterministic primary reader and judge, while GPT-5.4-mini is the robustness reader on LongMemEval-S.The dataset contains 470 evidence-labeled questions with approximately 102k-token histories.
- A Protocol constants & reproducibility: The study uses 80k, 30k, and 8k token store budgets, top-k retrieval of 60, a 2000-token restore cap, and three seeds.Deterministic policies use seed 0.
- A Protocol constants & reproducibility: The top-k ranker is frozen deterministic BM25-lite, while one regime forces surviving gold and the other uses pure top-k retrieval.The same ranker is used for every arm with recency tie-breaking.
- A Protocol constants & reproducibility: Restoration forces the full gold set, skips duplicate ids, and adds ranked snippets that fit within the remaining 2000-token injection cap.Final injected snippets are ordered chronologically.
- A Protocol constants & reproducibility: The baseline oracle-answerable denominator is N=336, the later LLM-importance grid uses N=332, and paired tests use approximately 329 shared question ids.Question-cluster bootstrap keeps all seed replicates of a sampled question together.
B Extended results & artifact
The extended artifact reports the full evaluation grid, including retrieval regimes, readers, bootstrap intervals, and per-question records. Table 1 provides headline counts for realistic top-k retrieval, while forced-gold injection serves as a construct reference.
- B Extended results & artifact: Table 1 reports headline per-cell counts for the primary reader under the realistic top-k retrieval regime.The full artifact includes both retrieval regimes and both readers.
- B Extended results & artifact: The artifact includes per-cell bootstrap confidence intervals, per-question records, and the complete grid across retrieval regimes and readers.It covers GPT-4o-mini and GPT-5.4-mini.
- B Extended results & artifact: Under forced-gold injection, recoverable errors are zero by construction and the two-bin share equals 1.00.This regime is the construct reference for the decomposition.
- B Extended results & artifact: The public release contains evaluation code, per-question records, bootstrap confidence intervals, calibration reports, and figure-generation scripts.The release also includes policy, restore, and decomposition implementations.
C Reader robustness, residual analysis & the restore-tightness ablation
The stronger reader preserves the study’s structural results while reducing residual reader-utilization failures. Tightness checks bound the restore counterfactual’s interpretation, and an independent judge audit supports binary grading reliability across models.
- Reader robustness: GPT-5.4-mini preserves the structural results, including identical Holm counts and the same per-policy ordering of two-bin shares.The residual bin is the only component that changes.
- Residual analysis: 1,922 residual records are predominantly reader arithmetic failures despite gold evidence being present, especially in cross-session counting and summation.A conservative heuristic estimates that at most 20% may reflect judge strictness; gold insufficiency is negligible.
- Residual analysis: The residual bin more than halves under GPT-5.4-mini at no-evict@80k, changing from 59 to 28.The stronger reader correctly resolves the cited $185 cross-session sum that the weaker reader answers as $65.
- Restore-tightness ablation: 7 cases, or 0.3%, become recoverable when only surviving gold is restored, while restoring old chronological placement flips 8.3% wrong answers to correct.The placement placebo is non-annotated rather than guaranteed semantically irrelevant, and the 8.3% bounds combined presentation and unannotated-evidence effects.
- Restore-tightness ablation: The full-gold restore is a tight upper bound on destruction, while GPT-5.5 agrees with GPT-4o-mini judging at 95.7% with Cohen’s κ=0.90.The independent audit included 393 completed grades after excluding 3 errored calls; a different-provider judge or human annotation would be a stronger check.
D Prompts
The prompts specify deterministic reader, judge, and importance-scoring procedures. They constrain answering to supplied memory, define binary grading criteria, and score snippet importance independently of the question and gold labels.
- Implementation: Decoding uses temperature 0, with maximum tokens of 600 for the reader, 16 for the judge, and 4 for the importance scorer.Session ids are hidden from both reader and judge, and injected units are rendered as newline-joined snippets.
- Reader prompt: The reader must answer using only supplied memory snippets and return “I don’t know” when those snippets truly lack the answer.It is instructed to provide a direct, concise but complete answer and compute elapsed days from today’s date when required.
- Reader prompt: The reader prompt supplies today’s date, memory snippets from earlier conversations, and the question before requesting an answer.The snippets are injected as the read-time context.
- Judge prompt: The judge returns exactly CORRECT or INCORRECT, requiring matching key facts and exact values for dates and numbers.For list answers, every reference item must appear; order matters only when the question asks for order.
- Importance-scoring prompt: The LLM-importance scorer rates a single snippet from 1 for trivial small talk to 10 for a durable user fact, preference, or commitment.It never sees the question or gold labels.