acceptodds
Under review as a conference paper at ICLR 2027

Reprieve: What Survives When Memory Eviction Becomes Reversible

Abstract

Long-horizon agents increasingly keep evicted memories in a cold tier from which they can be swapped back before deletion, as paging systems do. Standard eviction analysis assumes removal is final; which of its tools survive reversibility? We study this with Reprieve, a minimal live–cold–dead abstraction, and show that the answer is governed by locality: when demotion is entry-local and recovery requests do not depend on tier states, every entry is an independent automaton, and three properties survive at the level of entry trajectories. The unit that repairs a failure is the exile run, the sub-threshold decisions after the entry's last rescue, not a single demotion; used prospectively, run lengths set a protection horizon without harm labels that cuts LoCoMo failures by 41–48% under oracle requests, on par with tuned access-aware cache policies and at least twice what lowering the threshold buys. Threshold monotonicity fails only on re-inserted entries, for any retriever; with exogenous requests one sweep plus replay of that set evaluates every threshold. Tombstones make failed recoveries observable, yielding certificates whose resolution is set by the number of independent conversations. We also map where locality ends: capacity triggers and retrievers that skip expired keys. Across three corpora the query schedule alone changes swap-in demand up to , and reversibility pays only when cold storage is cheaper than live storage.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agent memory, memory eviction / reversible eviction, tiered memory paging, causal attribution, monotonicity of threshold gates, distribution-free risk control

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_BpGKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Agent memories increasingly demote evicted entries to a cold tier, from which they can be swapped back before deletion. The paper asks which tools of irreversible-eviction analysis still hold once eviction is reversible. Reprieve models each entry as live, cold or dead:

  • an entry is demoted when its score drops below a threshold λ;
  • a request for a cold entry swaps it back in ("rescue");
  • after a cold lifetime θ the entry dies and leaves a key behind (a "tombstone").

Under two conditions (demotion depends only on the entry itself, and requests do not depend on tier states), every entry evolves independently (Prop. 1). Three results follow:

  1. Attribution. Suppressing the "exile run" (the sub-threshold decisions after the last rescue) always repairs a failure, whereas blaming a single demotion repairs only 10–54%. A protection horizon set from run lengths cuts LoCoMo failures by 41–48% under oracle requests.
  2. Monotonicity. Violations occur only among swapped-back entries, so one sweep plus replay of those entries evaluates every threshold.
  3. Certification. Tombstones make failures observable, and per-conversation losses permit standard risk bounds, whose resolution is limited by the number of independent conversations.

Experiments are deterministic replays on LoCoMo (10 conversations), PerLTQA (31 streams) and LongMemEval-S, plus a small LLM end-task check.

Critical strengths

S1. A rigorous, honestly scoped framework with exemplary reproducibility.

  • Every result is paired with a counterexample marking where it breaks (capacity trigger, retrievers that skip expired keys, non-monotone suppression), and those boundaries are then measured on real corpora.
  • The replays are deterministic and released, and the end-task protocol was frozen in advance.
  • The paper positions itself honestly against caching precedents and reports negative results plainly.

S2. Methodological findings that matter for memory evaluation.

  • The query schedule alone changes swap-in demand by 3.3–4.4×, and end-of-stream schedules provably hide re-demotion (Prop. 6).
  • Blaming a single decision repairs only 22–39% of failures even under destructive eviction.
  • LongMemEval's grouped histories share sessions and are therefore not independent units.
Critical weaknesses

W1. Limited significance: the results are largely by construction or classical, and their practical payoff is small in the paper's own experiments.

  • By construction or classical.
  • The exile run is defined so that suppressing it prevents the failure.
  • A never-swapped entry behaves exactly as under deletion (Lemma 1), so violations must involve swapped-back entries.
  • Tombstones make failures observable by design.
  • Thm. 4 states that i.i.d. conversations give i.i.d. losses (a two-sentence proof); Cor. 3 is the classical zero-numerator bound; Definition 6 and Thm. 4 read more naturally as remarks.
  • Several experiments only re-verify proven statements ("every violation in W," "replay exact in 18/18").
  • Small payoff.
  • Violations are rare (7 of 359 harmed pairs on LoCoMo; none on PerLTQA), and a full replay takes 1.1 s, so Cor. 2 is "a structural statement … rather than a speed-up."
  • Certificates certify nothing on LoCoMo and only α = 0.2 on PerLTQA. They reach α = 0.02 only on an author-built LongMemEval variant, where the certified configuration still keeps 99.2% of storage.
  • End-task differences are not significant (+4.0 and +1.0, with intervals containing 0), and PerLTQA is 13.1 points worse at the exact storage match.
  • Novelty and fit. By the paper's own related work, the framework is caching theory: stack inclusion, exclusive two-level caches, TTL, and ghost entries. Nothing is learned and LLMs appear only in the end-task check, so the paper may fit a systems venue (e.g., SIGMETRICS) better than ICLR.

W2. The headline "41–48% without harm labels, on par with tuned cache policies" is weaker than stated.

  • The gain is not specific to exile runs. A frequency boost and the best fixed horizon match it at equal storage (Table 14), and the authors concede "the gain belongs to access-aware retention in general." Only the choice of k is new.
  • "Without harm labels" fails under oracle requests. The 41–48% uses oracle requests, so the calibration failures are tombstone hits on gold-evidence requests, which is effectively harm supervision.
  • The comparison is not like for like. The baselines are read off hindsight-tuned frontiers, while the run rule uses leave-one-conversation-out calibration. Choosing k from harm labels is better in 2 of 3 oracle settings.
  • Limited conditions. There is no gain on PerLTQA, and the LoCoMo schedule is author-constructed as "the extreme most favourable to observing re-insertion."
Questions for authors

Clarifications. These can be answered from existing results:

  1. Under oracle requests, the calibration failures are tombstone hits on gold-evidence requests. Isn't this harm supervision? Which signal calibrates the run rule in the BM25 rows of Table 14? (If only BM25 is label-free, the headline claim in W2 must be restated.)
  2. What harm-versus-storage weighting produces "k tuned on harm," and why does it pick k = 0 under BM25? (This determines whether exile runs add anything over harm-based tuning.)
  3. Beyond "interleave queries" and "count independent conversations," what design decision does the framework enable that existing caching analyses would miss? (This bears directly on significance, W1.)

Additional evidence that could change my rating:

  1. With the frequency boost and fixed horizon tuned leave-one-conversation-out on the same observable signals as the run rule, does the run rule still match or beat them? (This addresses W2.)
  2. Do the main findings (schedule effect, prospective gains, violations) hold on naturally interleaved queries rather than constructed schedules? (This addresses W2.)
  3. Is there a realistic setting where the certificate certifies a configuration with meaningful storage savings, and how many conversations would it need? (This addresses W1.)

Suggestions (not affecting my score):

  • Rewrite the abstract in plain terms.
  • Define "tier state," "entry-local," "exogenous," "measured boundary," α, δ and monotonicity before first use, and split Definition 3 into numbered conditions.
  • Present Def. 6 and Thm. 4 as remarks, and state the i.i.d.-conversation assumption explicitly.
Reviewer_c1b6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work argue that in memory eviction in LLM agents where removed memories can be stored in a cold tier and recovered later. The paper's main finding is that memory failures are often caused by a sequence of eviction decisions rather than a single decision. They also show that some theoretical properties still hold under certain assumptions. Experiments on LoCoMo, PerLTQA, and LongMemEval to support their analysis.

Critical strengths

The idea of using an exile run to explain memory failures is interesting, since a single eviction decision may not be enough to explain why a memory is lost. The paper also evaluates its findings on three datasets and discusses when its theoretical results may not hold. The proposed exile run provides a way to understand and potentially prevent memory failures. The authors also show that protecting memories based on past failures can reduce future failures without requiring harm labels.

Critical weaknesses

Most experiments use oracle retrieval, where the system already knows which memories are needed for each question. This is different from real LLM agents, where the retriever may fail to find relevant memories. Although the authors include some BM25 experiments, it is still unclear how well the findings apply to more realistic retrieval systems.

The improvement in actual question-answering performance is limited. Section 8.4 reports only 1–4 percentage points of improvement, and the confidence intervals include zero. This makes it difficult to tell whether reversible eviction actually improves the final performance of LLM agents.

The theoretical results depend on several assumptions, such as independent memory entries and requests that do not depend on memory states. However, real memory systems often have limited capacity and interactions between entries. The paper discusses some of these cases, but it is unclear how useful the main results are in practical memory systems.

Questions for authors

Can the authors evaluate Reprieve with a stronger learned retriever instead of mainly using oracle retrieval and BM25?

Why does the improvement in memory failure rate not lead to a clear improvement in question answering accuracy?

How well would the proposed analysis work in a real memory system with limited storage capacity and more complex memory update rules?

Reviewer_RRGyOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the memory management in the long-horizon agent systems. It introduces the exile run as a sufficient intervention for repairing evidence-loss failures, characterizes when threshold monotonicity fails, and develops efficient evaluation under locality assumptions. It also uses tombstones to observe failed recovery requests and applies conversation-level risk certification. Experiments across three datasets examine failure attribution, query scheduling, protection policies, and storage–risk trade-offs.

Critical strengths
  • The paper provides a clear framework connecting memory lifecycle dynamics with failure attribution, threshold analysis, and risk certification.
  • The controlled experiments help explain the mechanisms behind the theoretical results, particularly protection-window resets and query scheduling.
  • The paper explicitly examines the boundaries of its assumptions, including capacity-triggered eviction and retrievers that exclude expired entries.
Critical weaknesses
  • The applicability of the efficient analysis is restricted. Independent replay and threshold sweeps rely on entry-local eviction and exogenous requests. Practical memory systems often couple entries through capacity constraints and retrieval over available content. Although the paper examines such exceptions, it remains unclear how much of the proposed analytical efficiency survives in a deployed agent with these interactions.
  • Evidence of improved downstream task performance is limited. Most experiments use deterministic replay with oracle evidence requests, which isolates eviction but abstracts away retrieval and generation errors. On 100 randomly sampled LoCoMo questions, the reported accuracy improvements are only 4 and 1 percentage points, with both confidence intervals including zero. Larger evaluations with realistic retrieval and multiple readers would strengthen the practical claims.
Questions for authors

See the weaknesses part.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.