PaperlayerView exact revision on arXiv

Source-linked AI summary

Divergence Timing and Cumulative Disagreement under KV-Cache Eviction

Xinyue Luo, Fei Yu

arXiv:2609.16617v2cs.LG

TL;DR

The paper asks how KV-cache eviction changes cumulative disagreement when continuations diverge at different times and then mismatch to different extents. It decomposes that loss under recursive overlap–residual coupling, characterizes risks compatible with a finite divergence-aligned window, and finds that post-divergence exposure accounts for most measured aggregate mismatch gaps.

  • Problem

    KV-cache eviction perturbs conditional token distributions, but its cumulative consequences depend on both when continuations first diverge and how much they mismatch afterward.

    Source: §1 · p. 1

  • Method

    The paper decomposes mismatch under recursive overlap–residual maximal coupling and characterizes compatible risks from finite divergence-aligned profiles.

    Source: §1 · pp. 1–2, §6 · p. 17

  • Results

    85–90% of four aggregate mismatch gaps came from post-divergence exposure, and all four prespecified late-minus-early branch-TV contrasts were positive, ranging from 6.03 to 8.27 pp.

    Source: §6 · p. 17

  • Takeaways & Limitations

    Finite-window profiles identify an observed contribution and remaining capacity, while complete trajectories reveal how divergence timing, exposure, and subsequent mismatch compose cumulative comparisons.

    Source: §6 · p. 17

    Wall-clock efficiency depends on the full overlap scan, retention or replay of U<J, residual continuation, and per-replicate variance.

    Source: §4.2 · p. 9

Abstract

from arXiv · show

KV-cache eviction perturbs the conditional token distributions governing autoregressive generation. We investigate how first-divergence timing and subsequent token mismatch determine cumulative disagreement. We derive an exact decomposition under a specified stepwise maximal coupling: the expected mismatch fraction equals a first-mismatch contribution plus post-divergence exposure multiplied by its mismatch rate. An explicit construction over unrestricted autoregressive kernel pairs realizes the sharp interval of risks compatible with a finite divergence-aligned observation window. Residual-branch conditional Monte Carlo provides unbiased joint estimates of occurrence, occupation, and window/tail contributions, with per-replicate variance dominance for total token loss. Complete trajectories from Meta-Llama-3.1-8B-Instruct and Qwen2.5-7B-Instruct show that SnapKV at 50% retention enters divergence later and less often than SnapKV-512 or recent-token retention with the same 50% prompt-cache budget, while post-divergence total variation (TV) remains high. In an exploratory analysis of 288 documents, post-divergence exposure accounts for 85-90% of four aggregate mismatch gaps. On 288 independent documents at 90% retention, prespecified comparisons show higher branch-aligned TV in the late than in the early window in both models.

1 Introduction

KV-cache eviction changes retained decoding information, so continuations can agree initially, diverge later, and then spend different amounts of time mismatching. The paper separates first-divergence timing from subsequent occupation and examines how both shape cumulative disagreement.

1 Introduction

  • KV-cache eviction changes a model’s continuation by changing the information retained during decoding.Attention, retrieval structure, and forward-looking signals guide which entries to keep [1] [10] [18] [22] [31].Source: §1 · p. 1
  • Two interventions with the same first-divergence law and sequence TV ε can have expected mismatch fractions ε/H and ε, depending on subsequent occupation.This distinction gives a trajectory-level perspective on error accumulation and self-recovery in autoregressive models [2].Source: §1 · p. 1
  • Recursive overlap–residual maximal coupling compares reference and intervention kernels while preserving each continuation’s original marginal law.The resulting cumulative positional disagreement is defined in the following passage.Source: §1 · p. 1
  • Figure 1 illustrates that identical divergence laws can yield different expected losses, and that an exposed trajectory may include local matches.Its illustrative path has five exposed steps, including two local matches; the identity averages over complete trajectories.Source: Figure 1 · p. 2
  • First divergence separates mismatch at entry from subsequent occupation, which factors into post-divergence exposure and its mismatch rate.Residual-branch conditional Monte Carlo jointly estimates occurrence, occupation, and tail contributions under the same coupling.Source: §1 · p. 2
  • Post-divergence exposure accounts for 85–90% of four aggregate mismatch gaps, while SnapKV at 50% retention enters divergence later and less often than SnapKV-512 or recent-token retention at the same budget.The comparisons use complete trajectories from two language models; late-window TV also exceeds early-window TV, with the same direction in an independent 90% retention study.Source: §1 · p. 2

2 Related Work

Related work covers methods for selecting and compressing retained KV state, trajectory-level comparisons of generated sequences, and approaches to partial identification and variance reduction.

2 Related Work

  • KV-cache selection methods use attention sinks, heavy hitters, retrieval heads, observation windows, and heterogeneous budgets [9] [10] [22] [26] [33].Quantization and low-rank projection offer complementary compression axes [23], while serving evaluations study quality–memory–latency trade-offs [11].Source: §2 · p. 2
  • Sequence TV measures distance between marginal sequence laws, while maximal agreement couplings maximize agreement probability through each time [25] [32].One-step maximal coupling realizes TV as mismatch probability; token couplings also support speculative decoding [20] [30] and control generation randomness in LLM evaluation [4].Source: §2 · p. 2
  • Partial identification characterizes target values compatible with available observations, and conditional Monte Carlo reduces simulation variance by integrating out sampling randomness.The present study examines how first-divergence timing and subsequent mismatch jointly determine cumulative discrepancy under persistent KV-cache eviction.Source: §2 · p. 2

3 From Divergence Timing to Cumulative Disagreement

The paper decomposes cumulative disagreement into first-mismatch and subsequent-occupation contributions under a specified coupling, then studies what finite divergence-aligned observations identify about total risk.

3.1 Divergence timing, exposure, and occupation

  • Under recursive overlap–residual coupling, the two continuation marginals are preserved and each step’s mismatch probability equals the total variation between the compared kernels.The risk integrates local TV along paired histories, using a common prefix before divergence and both generated histories afterward.Source: §3.1 · p. 3
  • The trajectory decomposition separates mismatch at first divergence from subsequent occupation, which includes later agreements and renewed mismatches.A history-independent persistent perturbation also produces substantial occupation: for H ≥ 2, ΠH = eEH and CH = e.Source: §3.1 · pp. 3–4

3.2 Risks compatible with a finite branch window

  • For an admissible depth-L profile, compatible cumulative risks over unrestricted autoregressive kernel pairs are exactly [RL, RL + BL].RL is the observed contribution and BL the remaining probability-weighted trajectory capacity; the construction attains every value in the interval.Source: §3.2 · pp. 5–6

3.3 Consequences of the identified interval

  • For two actions, every compatible triple orders their cumulative risks by the observed contributions if and only if ra < rb.When estimating a fixed profile’s risk, the interval midpoint r + b/2 attains the minimax absolute-error bound.Source: §3.3 · p. 6

3.4 Additional information from a fixed reference

  • Fixing the complete reference kernel can strictly restrict the compatible risk set relative to [RL, RL + BL].In the supplied binary example, the fixed reference forces fair second-step intervention kernels, making the compatible set a singleton.Source: §3.4 · p. 7

4 Measuring Occurrence and Subsequent Occupation

The section develops residual-branch conditional measurement of disagreement, turning a sampled branch into joint estimates of loss components and finite-window uncertainty. In enumerable systems, it recovers risk with lower sample variance than ordinary coupling.

4.1 Conditioning on a residual branch

  • SWRB integrates out the zero-loss full-agreement event and yields unbiased estimates of occurrence, occupation, and total loss, with strict variance improvement when P(0 < M < 1) > 0.The estimates satisfy ZR = ZO + ZΠ.Source: §4 · p. 7, §4.1 · p. 8

4.2 Joint measurement of the window and tail

  • A shared residual suffix yields unbiased window, remaining-tail, and tail-capacity estimates while preserving covariance between window and tail estimates.Their expectations are RL, RH − RL, and BL, respectively.Source: §4.2 · p. 9

4.3 Sampled profiles and endpoint uncertainty

  • At confidence at least 1−α, the full-horizon risk lies in an enclosure combining unobserved-tail capacity with sampled-endpoint uncertainty for each specified action and depth.The sampled profile uses joint measurements ZL and WL.Source: §4.3 · pp. 9–10

4.4 Finite-state estimation

  • 11.1–289 was the range of naive-to-SWRB sample-variance ratios across 24 systems, with a median of 52.7.The mean kernel-pair evaluations rose by a factor of 1.37, while the ratio-of-means variance–cost advantage was 20.0.Source: Figure 4 · p. 10, §4.4 · p. 10

5 How Eviction Shapes the Disagreement Trajectory

The section pairs complete trajectories under persistent KV-cache eviction to separate divergence timing from subsequent branch mismatch. Across two language models, later or less frequent divergence coexists with high post-divergence TV, while short generation windows recover aggregate mismatch gaps with varying accuracy.

5.1 Paired trajectories and study design

  • The studies pair complete trajectories from Llama and Qwen across 288 documents at 50% retention and 288 independent documents at 90% retention, with horizon H = 128.The 50% comparisons include SnapKV, SnapKV-512, and recent-token retention at the same prompt-cache budget; the 90% study compares SnapKV with recent-token retention.Source: §5.1 · p. 11

5.2 Entry into divergence organizes cumulative differences

  • SnapKV-half delays first divergence: among trajectories diverging within the horizon, Llama mean entry time is 30.37 steps versus 11.69 for SnapKV-512 and 10.59 for recent-half.Qwen mean entry times are 29.37 versus 12.18 and 12.14 steps; on Llama, by step 128, divergence fractions are 92.29%, 98.14%, and 97.66%, respectively.Source: §5.2 · p. 12
  • Exposure contributes 86.3% and 89.9% of SnapKV-512-minus-SnapKV-half mismatch gaps on Llama and Qwen, respectively; post-divergence mismatch remains 89.74–96.20%.For equal-budget recent-half contrasts, exposure shares are 84.7% and 87.3%; every one of the 24 model–stratum–contrast decompositions has an exposure majority.Source: §5.2 · p. 12, Figure 5 · p. 12

5.3 Generation time and divergence time reveal different dynamics

  • Within fixed τ ≤64 cohorts, SnapKV-half branch TV rises from 84.45% to 91.56% on Llama and from 85.28% to 95.76% on Qwen, even as intervention gaps narrow over generation positions.The late-minus-early contrasts are positive in all 36 stratum–model–action comparisons; later entry shortens exposure to high-discrepancy branches.Source: §5.3 · pp. 12–13, Figure 6 · p. 13

5.4 Persistent branch discrepancy at higher retention

  • At 90% retention, exposure accounts for 88.6% of Llama’s 34.84-pp and 92.1% of Qwen’s 31.20-pp mismatch gaps; all four prespecified branch-TV intervals exceed zero.The independent study finds SnapKV enters divergence later and less often than recent-token retention at the same budget; early-to-late branch TV rises for both actions in both models.Source: §5.4 · pp. 13–14, Figure 7 · p. 14

5.5 EOS and the location of discrepancy

  • Most of the selector difference accrues before EOS, while strict pre-EOS late-minus-early branch TV rises by 5.94 and 6.83 pp on Llama and 8.26 and 7.51 pp on Qwen.EOS shares range from 0.86% to 3.68% on HELMET and 9.52% to 11.65% on RULER for Llama, and approximately −0.024% to 1.25% on Qwen.Source: §5.5 · pp. 14–15, Figure 7 · p. 14

5.6 Task-dependent timing and persistent branch discrepancy

  • At 90% retention, generation-clock gaps fall across later blocks in every HELMET model–length comparison but rise in every RULER comparison; all 24 branch contrasts are positive.The pooled generation-clock gaps are 37.89, 41.35, and 30.11 pp on Llama and 36.09, 37.63, and 25.53 pp on Qwen for positions 1–32, 33–64, and 65–128.Source: §5.6 · p. 15, Table 2 · p. 16

5.7 Aggregate prediction and temporal resolution

  • At generation positions 1–32, Qwen’s fixed-history cell-mean predictor meets the prespecified ±2-pp criterion for the six-stratum population-average SnapKV-512-minus-SnapKV-half gap; Llama’s ridge interval spans inside and above the margin.Short-window document-contrast MAEs were 4.09 pp on Llama and 4.92 pp on Qwen; fixed-history predictors’ MAE/RMSE were 8.73/11.04 pp on Llama and 10.03/13.18 pp on Qwen.Source: Table 3 · p. 16, §5.7 · p. 16

6 Discussion and Conclusion

Across the studied settings, post-divergence exposure accounts for most aggregate mismatch gaps, while generation-position and divergence-aligned views reveal persistent branch discrepancy alongside task-dependent aggregate dynamics.

6 Discussion and Conclusion

  • 85–90% of four aggregate mismatch gaps comes from post-divergence exposure, while discrepancy remains high within divergent branches.Lower cumulative mismatch is associated chiefly with later and less frequent entry into divergence.Source: §6 · p. 17
  • At 90% retention, generation-clock gaps narrow on HELMET and widen on RULER, while late-window branch TV increases across all studied strata.Entry-aligned measurements show persistent discrepancy beneath task-dependent aggregate dynamics.Source: §6 · p. 17
  • A finite divergence-aligned profile identifies observed contribution RL and remaining capacity BL; a construction characterizes every compatible cumulative risk over unrestricted kernel pairs.Residual-branch conditional measurement jointly estimates occurrence, occupation, and realized tail with an exact variance comparison.Source: §6 · p. 17
  • Generation positions 1–32 recover the population-average SnapKV-512 minus SnapKV-half contrast within ±2 pp in both models, with document-level contrast MAEs of 4.09 and 4.92 pp.Early observations summarize the mean effect, while complete trajectories reveal its composition.Source: §6 · p. 17

AI use

AI assistants supported code development, literature search, and checks of mathematical arguments; the authors remain responsible for the paper’s claims and presentation.

AI use

  • AI assistants supported code development.Source: AI use · p. 17
  • AI assistants supported literature search and checks of mathematical arguments.Source: AI use · p. 17
  • The authors are responsible for the claims, citations, analyses, and final presentation.Source: AI use · p. 17

Related papers

Loading 2609.16617v2…