Reprieve: What Survives When Memory Eviction Becomes Reversible

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 $4.4\times$, and reversibility pays only when cold storage is cheaper than live storage.