- 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:
- 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.
- Monotonicity. Violations occur only among swapped-back entries, so one sweep plus replay of those entries evaluates every threshold.
- 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:
- 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.)
- 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.)
- 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:
- 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.)
- Do the main findings (schedule effect, prospective gains, violations) hold on naturally interleaved queries rather than constructed schedules? (This addresses W2.)
- 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.