acceptodds
Under review as a conference paper at ICLR 2027

How Does KV-Cache Eviction Shape Output Divergence?

Abstract

KV-cache eviction reduces inference memory while altering subsequent generation. Across the interventions studied, lower cumulative token mismatch with full-cache continuations is associated mainly with later and less frequent first divergence; exposure-weighted post-divergence mismatch rates are also lower but remain high. Under a specified stepwise maximal coupling, we decompose the expected mismatch fraction into a first-mismatch term plus post-divergence exposure multiplied by its mismatch rate. Across an exploratory cohort and an independent 90%-retention cohort of two language models, exposure accounts for approximately 85–92% of six pooled mismatch-gap point estimates, including matched-byte selector comparisons at 50% and 90% retention. In the 90% cohort, prespecified comparisons within fixed early-divergence cohorts show higher total variation in late than early post-divergence windows for both models and selectors. We characterize the sharp range of cumulative mismatch compatible with an exact profile of finite divergence-aligned observations over unrestricted autoregressive kernel pairs and construct unbiased estimators via conditional Monte Carlo.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV-cache eviction, autoregressive language models, output divergence, trajectory analysis, maximal coupling

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_2yhyOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how KV-cache eviction changes autoregressive generation. It decomposes token mismatch into first-divergence effects and post-divergence disagreement, proves a sharp partial-identification result for finite divergence-aligned observations, and proposes an unbiased conditional Monte Carlo estimator. Experiments with Llama-3.1-8B-Instruct and Qwen2.5-7B-Instruct find that delaying or avoiding divergence explains most of the mismatch reduction from SnapKV relative to recent-token eviction.

Critical strengths

Provides a clear, mathematically grounded decomposition of cumulative disagreement. The partial-identification theorem precisely characterizes what finite observations can establish. Uses an independent 90%-retention cohort and document-level uncertainty estimates to support key empirical findings. Carefully distinguishes divergence-aligned behavior from averages over generation positions.

Critical weaknesses

Practical significance remains unclear. Token mismatch and next-token total variation do not directly establish differences in task accuracy, semantic quality, or user-perceived output quality. Experiments cover only two language models, a horizon of 128 generated tokens, and a specific sampling setup, limiting generalizability. The central findings depend on a specified maximal-coupling construction; the implications for other ways of comparing model outputs are not established. The conditional Monte Carlo method is theoretically justified, but its practical computational advantage for full-scale Transformer inference remains insufficiently demonstrated.

Questions for authors
  1. How well do the proposed divergence metrics correlate with downstream task performance or semantic quality?
  2. Do the main findings hold across longer generation horizons, additional models, and different sampling temperatures?
  3. What is the wall-clock and compute-normalized benefit of the conditional Monte Carlo estimator on full-scale models?
2 comments
AuthorsOpenReview ↗

Response to Reviewer 2yhy (Part 1)

Thank you for the valuable feedback. We are particularly encouraged by your comments appreciating our motivation and experiments. Below, we address your questions in detail.

W1. “Practical significance remains unclear. Token mismatch and next-token total variation do not directly establish differences in task accuracy, semantic quality, or user-perceived output quality.”

We thank the reviewer for this observation. Task-native LongBench scores reveal a different selector ranking on Qwen. We evaluate Qasper, HotpotQA, and GovReport (568 questions from 518 context parents per model). Mismatch comes from the 128-step coupled rollouts, and the LongBench mean equally weights the three task-native scores (Table 2). The final column gives the mean change from FullKV in points, with pointwise 95% paired context-parent bootstrap intervals (Table 15).

Model / selectorMismatch (%)LongBench meanChange [95% CI]
Llama / FullKV—45.24—
Llama / Recent85.2540.81−4.43 [−5.91, −2.97]
Llama / SnapKV64.2444.25−0.99 [−1.41, −0.54]
Llama / CriticalKV62.5944.60−0.65 [−1.08, −0.21]
Qwen / FullKV—45.20—
Qwen / Recent87.5740.26−4.94 [−6.46, −3.41]
Qwen / SnapKV70.2944.86−0.34 [−0.86, +0.17]
Qwen / CriticalKV69.2544.61−0.59 [−1.12, −0.09]

On Qwen, CriticalKV has the lowest mismatch, while SnapKV has the highest task-score point estimate among compressed selectors.

Q1. “How well do the proposed divergence metrics correlate with downstream task performance or semantic quality?”

We thank the reviewer for this question. Timing metrics improve pooled retrospective prediction of content-score changes. On saved 128-step HELMET and RULER trajectories, adding divergence probability and exposure reduces document-grouped out-of-fold MSE from 0.04061 to 0.03703 (8.8%). The baseline includes cumulative mismatch, fixed-history TV, and covariates. The 95% document-bootstrap interval for the MSE reduction is [0.00210, 0.00545].

In the split-half analysis described in Appendix F.1, we compute trajectory features from 32 of the 64 rollouts and content-score changes from the other 32. The pooled MSE reduction is 0.00361 when features come from the first half and 0.00327 when the halves are reversed. In the full-sample analysis, MSE improves in all three RULER strata and worsens in all three HELMET strata by point estimate. The MAE reduction interval spans zero.

W2. “Experiments cover only two language models, a horizon of 128 generated tokens, and a specific sampling setup, limiting generalizability.”

We thank the reviewer for this comment. We extend the generation horizon from 128 to 512 steps using the original sampling protocol (§5.1). We retain both checkpoints and temperature-one coupling and follow each selector's early-divergence cohort into later windows. Q2 below reports the paired early-to-late TV contrasts for all three selectors. Figure 7 shows the full branch profiles.

Q2. “Do the main findings hold across longer generation horizons, additional models, and different sampling temperatures?”

We thank the reviewer for this question. Late branch TV falls on Llama and rises on Qwen. At 512 steps we compare three selectors at matched bytes (50% retention, 72 documents, six strata, K = 16). Mean TV is for trajectories diverging by step 64. Intervals are pointwise 95% paired document-bootstrap intervals (Table 13).

Model / selectorLags 49–64Lags 433–448Change [95% CI]
Llama / SnapKV0.90960.6855−0.2241 [−0.2547, −0.1930]
Llama / CriticalKV0.89530.6825−0.2128 [−0.2518, −0.1739]
Llama / Recent0.94080.7270−0.2138 [−0.2447, −0.1839]
Qwen / SnapKV0.94870.9877+0.0391 [+0.0187, +0.0722]
Qwen / CriticalKV0.94900.9831+0.0341 [+0.0168, +0.0583]
Qwen / Recent0.98050.9897+0.0092 [+0.0032, +0.0163]

Figure 7 shows the full profiles. Llama's decline also appears in the pre-EOS summaries (Appendix E.1).

Together, the LongBench scores and longer rollouts show that selector rankings can vary with the evaluation objective and that late branch evolution differs by model.

AuthorsOpenReview ↗

Response to Reviewer 2yhy (Part 2)

W3. “The central findings depend on a specified maximal-coupling construction; the implications for other ways of comparing model outputs are not established.”

We thank the reviewer for this observation. The coupling preserves both marginal generation laws. Common-token probabilities fix the first-divergence law across stepwise maximal couplings, while residual pairings can change histories after divergence. At each history pair, the conditional mismatch probability equals the total variation between the two next-token distributions (§3.1).

W4. “The conditional Monte Carlo method is theoretically justified, but its practical computational advantage for full-scale Transformer inference remains insufficiently demonstrated.”

We thank the reviewer for this comment. The estimator integrates out the zero-loss event of full agreement. It weights the sampled suffix by the total first-divergence mass along the auxiliary overlap path. Proposition 4.1 establishes unbiasedness and variance at most that of one ordinary coupled replicate for cumulative mismatch. Wall time includes the scan, replay, and suffix costs (Section 4).

Q3. “What is the wall-clock and compute-normalized benefit of the conditional Monte Carlo estimator on full-scale models?”

We thank the reviewer for this question. The measured error–time trade-off differs by model. At H = 128, we evaluate 48 documents per model and three SnapKV budgets. The SWRB-to-ordinary ratios of the mean per-replicate product of squared error and estimator wall time are 2.38 on Llama-3.1-8B and 0.897 on Qwen3-8B, favoring ordinary sampling for Llama and SWRB for Qwen3. Squared error is measured against an independent 16-replicate SWRB reference mean, and timing covers estimator execution after prefill and initial cache compaction (Appendix C.1).

Taken together, the results specify the law used to compare trajectories and show how the variance guarantee and measured efficiency answer different questions.

Reviewer_43qQOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies how KV-cache eviction changes autoregressive generation relative to full-cache inference. Using stepwise maximal coupling, it measures token-level disagreement and decomposes cumulative mismatch into the occurrence and timing of the first mismatch, subsequent exposure, and the post-divergence mismatch rate. Experiments on Llama-3.1-8B and Qwen2.5-7B suggest that SnapKV’s advantage over recent-token eviction mainly comes from delaying or avoiding the first mismatch, while trajectories that have already diverged continue to exhibit high and increasing discrepancy. The paper also presents a partial-identification bound for finite observation windows and a conditional Monte Carlo estimator for reducing measurement variance.

Critical strengths
  1. The paper provides a clear conceptual distinction between delaying the first mismatch and reducing disagreement after the first mismatch.
  2. The experiments include two models, several context-length strata, matched-cache-budget comparisons, and an independent 90%-retention cohort.
  3. The conditional Monte Carlo estimator is theoretically unbiased and has lower per-replicate variance than ordinary coupled sampling.
Critical weaknesses
  1. The main conclusion is intuitive, while much of the theory formalizes it through a largely algebraic decomposition rather than providing new explanatory insight.
  2. The experiments mainly compare SnapKV with recent-token retention on two models, which is insufficient to support general conclusions about KV-cache eviction.
  3. The Monte Carlo estimator reduces variance per sample, but the paper does not demonstrate better compute-normalized efficiency on real Transformers.
  4. Token disagreement does not necessarily imply semantic or task-level degradation, and token agreement does not imply identical reasoning states.
  5. The paper describes when divergence occurs but does not separate the direct effect of KV removal from autoregressive history feedback, EOS behavior, or task-specific effects.
  6. The paper uses excessive notation and complex formulas to present a relatively simple idea, making it unnecessarily difficult to follow.
Questions for authors

Refer weaknesses.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 43qQ (Part 1)

We thank the reviewer for the valuable comments. And we also thank the reviewer for the opportunity to clarify the paper's contribution and the evidence supporting its main findings. Below, we address the reviewer's concerns in detail.

W1. “The main conclusion is intuitive, while much of the theory formalizes it through a largely algebraic decomposition rather than providing new explanatory insight.”

We thank the reviewer for this observation. Which contribution dominates is an empirical question. In Figure 1a, two interventions have identical first-divergence laws and sequence total variation (TV), yet their expected mismatch fractions are ε/H\varepsilon/H and ε\varepsilon.

Given the first-divergence law over the full horizon and exact mismatch probabilities for the first LL positions of each divergence-aligned branch, Theorem 3.2 identifies the exact range of compatible full-horizon risks over unrestricted kernel pairs. Mismatch accounted for by the observed window gives the lower endpoint. The interval width is the fraction of positions beyond the window on each branch, weighted by its first-divergence probability and summed over branches. In Figure 8, the mismatch measured beyond L=32L = 32 occupies 94.994.9–98.298.2\\% of the estimated remaining capacity across six SnapKV model–budget settings. Even exact measurements within the window can leave substantial disagreement in the unobserved tail.

In the original 128128-step studies, reduced exposure accounts for approximately 8585–9292\\% of the six pooled mismatch gaps. Figure 3 gives the following point estimates for exposure's share of each gap.

ContrastLlamaQwen
SnapKV-512 − SnapKV-half86.386.3\\%89.989.9\\%
Recent-half − SnapKV-half84.784.7\\%87.387.3\\%
Recent-90 − SnapKV-9088.688.6\\%92.192.1\\%

SnapKV-512 retains 512512 tokens. The suffixes half and 9090 denote 5050\\% and 9090\\% retention.

W2. “The experiments mainly compare SnapKV with recent-token retention on two models, which is insufficient to support general conclusions about KV-cache eviction.”

We thank the reviewer for raising this point. CriticalKV-on-SnapKV reduces pooled mismatch against both baselines at matched bytes. At 5050\\% retention, we evaluate 288288 documents per model across six HELMET/RULER strata. Entries are changes in cumulative mismatch in percentage points, with pointwise 9595\\% paired document-bootstrap intervals (Table 14).

ModelCriticalKV − SnapKVCriticalKV − Recent
Llama−1.65-1.65 [−2.53,−0.82][-2.53, -0.82]−22.66-22.66 [−24.35,−20.97][-24.35, -20.97]
Qwen−1.03-1.03 [−1.98,−0.05][-1.98, -0.05]−18.32-18.32 [−20.03,−16.52][-20.03, -16.52]

On Qwen, the CriticalKV-minus-SnapKV point estimates are positive at HELMET-16K (+0.47+0.47 pp [−1.25,+2.18][-1.25, +2.18]) and RULER-32K (+2.22+2.22 pp [−0.33,+4.78][-0.33, +4.78]). Both intervals span zero. Against Recent, all 1212 pointwise 9595\\% intervals for the CriticalKV exposure–rate contribution difference favor exposure (10,00010{,}000 paired document-bootstrap draws, Appendix E.3).

Together, the theory identifies what can be inferred from a finite branch profile, and the matched-byte experiments show how much of the observed mismatch gap comes from exposure.

AuthorsOpenReview ↗

Response to Reviewer 43qQ (Part 2)

W3. “The Monte Carlo estimator reduces variance per sample, but the paper does not demonstrate better compute-normalized efficiency on real Transformers.”

We thank the reviewer for this question. For cumulative mismatch, per-replicate variance is at most that of ordinary coupled sampling (Proposition 4.1). In the real-model experiment, we multiply each replicate's squared error relative to a Monte Carlo reference by estimator wall time and average the products. The conditional estimator (SWRB) to ordinary-sampling ratio is 2.382.38 on Llama-3.1-8B and 0.8970.897 on Qwen3-8B, favoring ordinary sampling on Llama and SWRB on Qwen3 (Appendix C.1).

W4. “Token disagreement does not necessarily imply semantic or task-level degradation, and token agreement does not imply identical reasoning states.”

We thank the reviewer for this observation. We measure task quality directly on LongBench. Table 2 reports cumulative mismatch against FullKV from coupled rollouts and task scores under task-native decoding. The LongBench mean equally weights Qasper, HotpotQA, and GovReport.

SelectorLlama LongBench meanQwen LongBench meanQwen mismatch (%)
FullKV45.2445.2445.2045.20Reference
Recent40.8140.8140.2640.2687.5787.57
SnapKV44.2544.2544.8644.8670.2970.29
CriticalKV44.6044.6044.6144.6169.2569.25

On both models, SnapKV and CriticalKV score closer to FullKV than Recent. On Qwen, CriticalKV has the lowest mismatch and SnapKV has the highest LongBench mean among compressed selectors by point estimate. The coupling measures output agreement along paired histories (§3.1). Those histories retain the first mismatch even when a later token matches (§5.3).

W5. “The paper describes when divergence occurs but does not separate the direct effect of KV removal from autoregressive history feedback, EOS behavior, or task-specific effects.”

We thank the reviewer for this thoughtful question. The shared-history comparison holds the full-cache token history fixed for both caches. It measures how their next-token distributions differ under the same token input. The paired-history comparison feeds each cache its own generated history and measures disagreement along those two histories (Appendix B.1). In the example in Appendix A.3, the reference always emits zero and the intervention emits one with a fixed probability, independently of history. As the horizon grows, nearly all mismatch occurs after the first disagreement even though both kernels ignore history. Controlled replay varying the cache intervention and token history would address causal attribution.

At 9090\\% retention, the Recent-minus-SnapKV gap narrows over generation positions in every HELMET stratum and widens in every RULER stratum (Figure 6a). Within early-divergence cohorts, all 2424 late-minus-early pre-EOS branch contrasts have positive pointwise 9595\\% lower bounds, with a minimum of 2.472.47 percentage points (Figure 6b). At 512512 steps, Llama's later decline also appears before either sequence reaches EOS. Both sequences have reached EOS at only 1.31.3–2.42.4\\% of possible late-window cohort steps, depending on the selector (Appendix E.1).

W6. “The paper uses excessive notation and complex formulas to present a relatively simple idea, making it unnecessarily difficult to follow.”

We thank the reviewer for this feedback. We revised the presentation around the key equations. In §3.1, the prose immediately after Equation 6 now explains the exposure term as a change in time after divergence and the rate term as a change in disagreement per available position. In §5.3, Figure 4 provides a visual guide to the two averaging operations before the mixture identity in Equation 13. We also condensed the discussion of high retention and observation depth (§§5.4–5.5). The branch-profile notation in §3.2 specifies which lags are observed after each first divergence, making the inputs to the sharp-bound theorem explicit.

Reviewer_43qQOpenReview ↗

Thanks for the rebuttal

Thank you for the additional experiments and clarifications. Two major concerns remain:

The paper still does not provide a mechanistic explanation of the observed divergence. The shared- and paired-history analyses are descriptive, and the authors themselves acknowledge that controlled replay would be needed to separate the direct effect of KV removal from autoregressive history feedback.

The practical significance remains unclear. The added LongBench results do not establish mismatch as a reliable proxy for task quality, while the compute-normalized results for SWRB are mixed-worse on Llama and only slightly better on Qwen. Therefore, neither the metric nor the estimator has yet demonstrated broad practical value.

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

This paper decomposes the cumulative token mismatch of kv cache eviction methods into a first-divergence term and a post-divergence term. Empirically, the authors find that better policies win mainly by diverging later and less often, while post-divergence mismatch stays high and shows no sign of recovery.

Critical strengths

This paper offers a novel theoretical insight and may, to some extent, inform the design of future KV-cache eviction policies.

Critical weaknesses

The experimental evaluation is insufficient. The baseline method are relatively outdated, even though the paper cites more recent eviction methods. In addition, only a limited number of datasets are used, and widely adopted long-context benchmarks such as LongBench are not covered.

Questions for authors

Recent KV-cache compression methods [1,2] have begun to model eviction from the perspective of constraining the output perturbation, which appears closely related to the focus of this paper. Could the authors discuss whether they would change the empirical findings?

  1. CriticalKV: Optimizing KV Cache Eviction from an Output Perturbation Perspective

  2. OBCache: Optimal Brain KV Cache Pruning for Efficient Long-Context LLM Inference

2 comments
AuthorsOpenReview ↗

Response to Reviewer hwXf

Thank you for the valuable feedback. We are particularly encouraged by your comments appreciating our motivation and experiments. Below, we address your questions in detail.

W1. “The baseline method are relatively outdated, even though the paper cites more recent eviction methods.”

We thank the reviewer for this observation. We add the official uniform-head CriticalKV selector with SnapKV scores. We compare three selectors at 50% retention and exactly matched persistent-cache bytes, using 288 documents per model across six HELMET/RULER strata (H = 128, K = 32). The trajectory columns from Table 2 give cumulative mismatch (R) and the exposure-weighted post-divergence mismatch rate (C). Appendix E.2 details the comparison.

SelectorLlama R (%)Llama C (%)Qwen R (%)Qwen C (%)
Recent85.2593.8687.5796.23
SnapKV64.2489.9370.2993.69
CriticalKV62.5989.3669.2593.74

W2. “In addition, only a limited number of datasets are used, and widely adopted long-context benchmarks such as LongBench are not covered.”

We thank the reviewer for this constructive suggestion. The task-native scores show where selector rankings differ. LongBench-v1 supplies 568 questions from 518 context parents per model. We use greedy decoding with task-specific caps, normalized F1 for QA, and ROUGE-L for GovReport. The last column gives equal-task mean changes from FullKV in points, with pointwise 95% paired context-parent bootstrap intervals (Table 15).

Model / selectorQasperHotpotQAGovReportMean change [95% CI]
Llama / FullKV43.6357.5434.56—
Llama / Recent37.3054.1231.02−4.43 [−5.91, −2.97]
Llama / SnapKV42.9857.2232.54−0.99 [−1.41, −0.54]
Llama / CriticalKV43.2457.4133.14−0.65 [−1.08, −0.21]
Qwen / FullKV44.4057.7733.44—
Qwen / Recent37.8951.4731.43−4.94 [−6.46, −3.41]
Qwen / SnapKV45.0657.3232.20−0.34 [−0.86, +0.17]
Qwen / CriticalKV43.7957.4532.61−0.59 [−1.12, −0.09]

CriticalKV is closer to FullKV than Recent in mean score on both models. On Qwen, SnapKV leads CriticalKV on Qasper, while CriticalKV leads on HotpotQA and GovReport by point estimate.

Q1. “Recent KV-cache compression methods [1,2] have begun to model eviction from the perspective of constraining the output perturbation, which appears closely related to the focus of this paper. Could the authors discuss whether they would change the empirical findings?”

We thank the reviewer for this question. CriticalKV reduces mismatch primarily through lower pooled exposure, with an additional rate reduction on Llama. The table gives CriticalKV minus SnapKV contrasts in percentage points, with pointwise 95% paired document-bootstrap intervals (Table 14).

ModelTotal mismatchExposure contributionRate contribution
Llama−1.65 [−2.53, −0.82]−1.25 [−1.98, −0.56]−0.40 [−0.72, −0.07]
Qwen−1.03 [−1.98, −0.05]−1.07 [−1.99, −0.14]+0.04 [−0.29, +0.35]

CriticalKV's branch TV at lags 49–64 exceeds TV at lags 1–16 on both models, including before EOS (Appendix E.2).

Against Recent, all 12 pointwise 95% intervals for the CriticalKV exposure–rate contribution difference favor exposure. Against SnapKV, exposure contributes more in both HELMET-4K comparisons after adjustment across 12 contrasts. The pointwise HELMET-32K intervals span zero on both models (10,000 paired document-bootstrap draws, Appendix E.3 and Figure 12). In the 512-step early-divergence cohorts, late TV declines on Llama and averages near 1 on Qwen (Figure 7). OBCache also targets attention-output perturbation. The same decomposition would quantify its effects on exposure and the post-divergence rate.

Together, the matched-byte comparisons locate CriticalKV's main gain in reduced exposure, while LongBench and the branch profiles show how that gain coexists with task-specific rankings and persistent disagreement.

Thanks for the response! I will maintain my positive score and encourage the authors to incorporate the discussion into the revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.