acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 from fewer than about times the conversations CAT needs. On LongMemEval, certifying only the harmed-query rate at leaves the concentration of harm uncertified, and % of test streams contain an eviction that harms multiple queries; certifying CAT at jointly guarantees this share, which is % on test streams, at the cost of deleting % instead of % of memory. On memories extracted by Mem0, the joint rule certifies deleting % of memories with % of held-out streams affected. At the thresholds certified by CAT () at and , question-answering accuracy changes by about one point on average; above them, answers to queries that lost evidence turn from correct to wrong times for every reverse changes.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Agent Memory, Tail-Risk Control, Distribution-Free Certification。

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_XhdeOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how a single memory-eviction action can remove evidence needed by multiple future queries. It defines this effect as the action’s blast radius and shows that action-level tail risk can be non-monotone in the deletion threshold. The proposed framework uses independent conversations to calibrate a threshold that jointly controls large-blast-radius events and the overall rate of evidence loss. Experiments on LoCoMo, LongMemEval, and Mem0-extracted memories evaluate the risk–deletion tradeoff, with separate QA experiments checking the effect on answers.

Critical strengths
  1. The theoretical argument is clear and internally coherent. The paper connects risk definitions, attribution drift, conversation-level calibration, and threshold selection into a complete methodological argument. The sample-complexity analysis also explains which risk targets can realistically be certified with limited data.

  2. The evaluation connects statistical certification with practical outcomes. The paper reports memory deletion, evidence loss, QA changes, and abstention, making the tradeoffs explicit. The additional scorers, Mem0 experiments, and replay audits provide useful checks beyond the main configuration.

Critical weaknesses

The practical need to control blast-radius concentration is not sufficiently established. The experiments show that CAT and overall evidence loss capture different properties, but provide limited evidence that more concentrated harm causes worse downstream outcomes when overall evidence loss is comparable. The QA evaluation mainly links evidence deletion to answer degradation. Table 1 also shows that a tighter harmed-query constraint achieves similar observed deletion and CAT rates to CAT certification, despite providing a different guarantee. Why controlling concentration deserves an additional constraint therefore remains insufficiently justified.

Questions for authors

What concrete downstream failure motivates controlling CAT in addition to the harmed-query rate? Do any existing results show that concentrating a comparable amount of evidence loss in fewer eviction actions leads to worse task outcomes?

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

The paper studies the concentration of harm in long-term agent memory eviction: a single batch eviction may remove evidence needed for several future queries at the same time, but conventional “harmful eviction frequency” and “harmed-query rate” cannot characterize this severity. The authors define the blast radius of a single eviction action (how many future queries lose required evidence because of it), and further propose the catastrophe probability CAT, the within-conversation tail measure E-Tail, and the conversation-mixture measure MIX-CVaR. The paper analyzes attribution drift, in which increasing the eviction threshold may redistribute harm among different actions and cause nonmonotonicity of action-level tail risk. Using entire i.i.d. conversations rather than correlated actions as calibration units, the authors construct distribution-free risk certificates by combining Clopper–Pearson, betting bounds, and fixed-sequence testing, and prove a sample requirement lower bound for MIX-CVaR on zero-harm samples.

The experiments include synthetic streams, LoCoMo, LongMemEval, and Mem0-extracted memories. In the main LongMemEval setting, controlling CAT(z*=2)≤0.20 permits deletion of 15.8% of memories, with a test CAT event rate of 8.5%; when a method controlling only the harmed-query rate at ≤0.25 deletes 38.3%, 24.3% of test streams contain at least one instance of multi-query harm. The paper also reports QA changes, emphasizing that the certificates constrain predefined evidence-loss metrics, not a theoretical guarantee about final QA errors.

Critical strengths
  1. Concentration of harm is a meaningful risk perspective, and attribution drift has a clear mechanism. Proposition 2 shows that a more aggressive threshold may redistribute the same three harmful query outcomes from one action to two actions, reducing the maximum blast radius from 3 to 2 without reducing the total query harm. This shows that tail risk cannot simply be assumed monotonic and provides a reasonable motivation for fixed-sequence testing; corresponding nonmonotone steps also exist on LoCoMo.

  2. The reporting of theory and diagnostic boundaries is substantial. Proposition 3 gives a zero-event sample lower bound for MIX-CVaR at high tail levels; Appendices B/C provide complete certificate constructions and proofs, and synthetic experiments examine coverage and abstention behavior. The authors also use QA controls to show the relationship between evidence loss and final answer errors; for example, at λ=0.50 there are 31 changes from correct to incorrect and 2 changes in the reverse direction.

Critical weaknesses
  1. Positive compression results depend on simplified streams, while the practical certification benefit nearly disappears in the tested full-distractor long-stream setting. The main LongMemEval experiment organizes questions by source session into 50 streams and retains only answer-relevant sessions, with 136–300 turns per stream (Appendices E.1/G.1). Under this construction, the CAT rule can certify deletion of 15.8%. However, after retaining distractors in Appendix E.8, each stream reaches 2,851–5,015 turns, and the CAT(z*=2) and harmed-query-rate rules can certify deletion of only 3.9%. In Appendix E.9, the embedding scorer already loses considerable evidence at its minimum threshold, and the corresponding rules abstain for all splits. The 27.8% deletion result for Mem0 is also based on short streams and one-time pre-extracted memories, without closed-loop simulation of how eviction affects subsequent memory extraction. This does not invalidate safe abstention or the mathematical validity of the certificates, but the value for practical long-term memory compression has not yet been sufficiently demonstrated.

  2. The stability of risk labels and action granularity has not been validated. Equation (2) records harm whenever a specified required evidence item is removed, without requiring the answer to actually become incorrect. Whether a nearest-neighbor-matched memory in Mem0 is truly semantically irreplaceable has not been adequately verified. In Appendix E.7, shadow-memory top-5/top-10 retrieval covers at least one gold evidence item only 68.9%/82.9% of the time, so the risk bounds for proxy labels cannot directly be transferred into risk bounds for real evidence. Moreover, Proposition 5 proves that splitting one eviction into several operations can reduce the default action-level CAT while producing the same harmed queries. Although window blast radius is proposed, the main results lack sensitivity analysis with fixed windows and compaction granularity. This affects the interpretation of the metric as a deployable safety objective.

Questions for authors
  1. Without changing the prespecified (α,δ,z*), could the authors apply a reasonable length-adaptive scorer to long-memory streams that retain all distractors and demonstrate a practically meaningful nonzero safe deletion rate, along with corresponding QA changes? Please also test the closed loop of “eviction–new memory extraction–retrieval–answering” on continuously updated real pipelines such as Mem0. If these results are robust, the practical significance of the paper would increase substantially.

  2. Could the authors validate gold evidence, Mem0 nearest-neighbor evidence, shadow-retrieval proxies, and actual QA errors side by side on the same trajectories, and report results using fixed-window CAT? In particular, please indicate whether retrieval-proxy risk has provable one-sided conservativeness, rather than merely a low violation rate in a fixed empirical population. This determines the interpretability of the certified risk.

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

The work studies the effect of eviction in a bounded memory store for LLM memory systems. The key object of study is how evicting a memory can affect future downstream queries that rely on it. The work defines a "blast radius" metric which is the number of downstream queries that fail as a result of the eviction. The main contribution is a formal framework defining how different thresholds of eviction (after giving each memory a score) affect the blast radius.

  • Several tail-risk metrics based on blast radius, mainly catastrophe probability (CAT), which measures the chance that an eviction harms at least z* queries. They also define two CVaR-style metrics (E-Tail and MIX-CVaR).
  • Theoretical results showing these metrics are only loosely related. Increasing the threshold can cause earlier evictions and shift harm between actions (“attribution drift”), making tail risk non-monotone and standard risk-control methods hard to apply.
  • A distribution-free framework that bounds each metric using conversations as i.i.d. calibration samples, then uses Learn-then-Test to pick a threshold despite non-monotone risk. They also show MIX-CVaR needs roughly 1/(1−η) times more conversations than CAT, even with no observed harm. Experiments use LoCoMo, LongMemEval, and Mem0 memories, demonstrating that the empirical results using a simple eviction policy based on word overlap and recency demonstrating that the theory aligns with empirics.
Critical strengths
  • The paper defines a new metric, "blast radius," which is reasonably well motivated and seems useful
  • The theoretical results are mostly interesting: notably Prop. 2 which shows that using the fraction of actions that harm some future query is a bad metric, and can be decreased without actually improving the number of queries that are solved correctly
Critical weaknesses
  • The contribution is limited: most of the theoretical insights seems to be geared towards justifying that blast radius is a better metric than alternatives; the actual theoretical results are a fairly routine application of well known statistical results, just for this particular metric; hence, the contribution is really limited to proposing and analyzing this one metric
  • On a related note, the empirical results are weak; its unclear what the real use case of this metric is, and what this means for SOTA LLM memory systems
Questions for authors
  1. In Table 1 the CAT rule deletes much less memory than the harmed-query-rate rule (15.8% vs 38.3%), so the 5.1% vs 15.9% comparison of numbers of harmed queries seems confounded, so this seems to be at different memory bank capacities. Is there a setting where certifying CAT gives a better tradeoff?
  2. Can the authors show that this framework can actually be used with existing memory systems that natively do deletion to improve their performance? This would make the contribution of the work much stronger.
Reviewer_bj1WOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the downstream harm caused by deleting persistent memories in LLM agents. It defines the blast radius of an eviction as the number of future queries that lose required evidence, and calibrates deletion thresholds using independent conversations. The framework controls catastrophe probability (CAT) jointly with the harmed-query rate, accommodates non-monotone risk, and explains the greater calibration cost of mixture CVaR. Experiments use synthetic data, LoCoMo conversations, and streams constructed from LongMemEval, with additional evaluation on Mem0 memories and downstream question answering.

Critical strengths

The paper identifies a meaningful limitation of harmful-decision frequency: one harmful eviction can affect several future queries. The analysis of attribution drift is useful, since changing the threshold can redistribute the same query losses across actions and alter the measured severity. This gives a concrete reason to examine the risk target and threshold-selection procedure carefully.

Using each conversation as the calibration unit is appropriate for the dependence within a memory stream. The main arguments appear sound under the stated assumptions. The sample-size analysis also helps explain why some tail-risk targets are difficult to certify with limited calibration data.

The experiments are fairly thorough for the scope of the paper. They include different retention scorers, memories extracted by Mem0, and actual question answering. The results support the proposed risk formulation and show that evidence loss is related to answer degradation. The paper also reports settings where certification becomes conservative or fails to return a threshold, which makes its limitations clear.

Critical weaknesses

The statistical machinery largely builds on established confidence bounds and Learn then Test (Angelopoulos et al., 2025). The main contribution is therefore the formulation and analysis of memory-eviction risk, with a more limited methodological advance in risk control itself.

The evidence for practical memory savings is weaker on long streams with background sessions. The main LongMemEval construction keeps only answer sessions. When distractors are retained, CAT certifies only about 3.9% deletion with the lexical scorer and returns no certified threshold with the embedding scorer under the reported settings (Appendices E.8 and E.9). This leaves some uncertainty about how useful the current policy family is when substantial memory reclamation is needed.

Questions for authors

Can the authors clarify how much of the limited deletion in the long-stream setting is due to the retention scorer and its recency scale? A focused discussion or a small check within the existing setting would help establish the practical scope of the framework.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.