Agent Memory Eviction Has a Blast Radius: Distribution-Free Tail-Risk Certificates

Large language model (LLM) agents rely on persistent memory for long-term tasks, and limited storage makes memory eviction inevitable. One eviction action can remove evidence needed by many future queries, a magnitude that harmful-decision frequency does not record. We define the blast radius of an eviction action as the number of future queries that lose required evidence because of it, and introduce a distribution-free framework that treats each conversation as one calibration unit, allowing arbitrary dependence among its actions. Across independent and identically distributed (i.i.d.) conversations, the framework certifies an eviction threshold for catastrophe probability (CAT), the probability that some eviction harms at least a chosen number of queries, jointly with the harmed-query rate, and remains valid when attribution drift makes risk non-monotone in the threshold. We prove that, even when no eviction harms any query, no valid conversation-level bound certifies mixture conditional value-at-risk (MIX-CVaR) at tail level $\eta$ from fewer than about $1/(1-\eta )$ times the conversations CAT needs. On LongMemEval, certifying only the harmed-query rate at $.25$ leaves the concentration of harm uncertified, and $24.3$% of test streams contain an eviction that harms multiple queries; certifying CAT at $.20$ jointly guarantees this share, which is $8.5$% on test streams, at the cost of deleting $15.8$% instead of $38.3$% of memory. On memories extracted by Mem0, the joint rule certifies deleting $27.8$% of memories with $8.0$% of held-out streams affected. At the thresholds certified by CAT ($z^{\ast }=2$) at $.10$ and $.20$, question-answering accuracy changes by about one point on average; above them, answers to queries that lost evidence turn from correct to wrong $31$ times for every $2$ reverse changes.