The premise and promise of KV (cache) eviction is simple: higher throughput can be achieved by evicting some entries from the KV cache, at a negligible cost to quality. This holds empirically for many existing methods, though most rely on creative heuristics for selecting which entries to drop. Despite recent advances, the problem of KV eviction has remained informal in the literature. This paper aims to properly formalize this problem through the lens of probabilistic reasoning and reveal what can be learned from this perspective. Concretely, we (1) formalize the problem of KV eviction and, unfortunately, prove that it is computationally hard, (2) show that by framing it probabilistically, KV eviction reduces to the problem of expectation estimation, which can be approximated through sampling, (3) show that through this probabilistic interpretation, correcting for evicted entries during decoding---a previously ignored problem---becomes feasible, and (4) reveal that existing methods in the literature are zero-variance biased estimators that can be easily adapted in order to enable decode time correction. In practice, we show that this probabilistic version of KV eviction coupled with decode time correction is more robust to different tasks compared to existing eviction methods and achieves competitive performance at the same compression budget.
Figures & tables
Figure 1: Correction can attenuate the effects of eviction at decode time. Evicting entries deforms the distribution and biases the expectation, as the normalizing constant is altered by the evicted entries. Existing eviction methods deterministically evict the top- k scored entries, which although zero-variance, may have arbitrarily large bias. Probabilistic eviction addresses this unintended deformation through self-normalized importance sampling, whose error is upper bounded by O(m−1) , where m is the number of samples.
Figure 2: KV eviction is a game of trading bias for variance and vice versa. The plot shows mean absolute error ( y -axis) of the attention values for the first token after an evicted prompt on Llama3 averaged across all heads (see Appendix E for details) for different compression ratios ( x -axis). Bias and variance are low at lower r , since m (number of samples) is high. As r increases, m decreases, causing variance to increase more than bias. Higher importance weight temperatures τ decrease the variance, causing the error to decrease at extremely high r ’s.
Figure 3: Probabilistic eviction achieves competitive performance. Probabilistic eviction with correction performs best at lower to middle ranges, when there are enough samples to achieve a lower variance and bias. Solid lines show our approach, dashed lines show existing eviction methods.
Figure 4: Probabilistic eviction can make eviction more robust for different tasks. Win score values for four proposals ( πH2O,πH2O-h,πmin,πmin-h ) and five top- k estimators (H2O, K-norm, SnapKV, StreamingLLM, TOVA). πmin-h achieves best ranking across datasets and models, showing more robustness when minimizing variance and lowering bias.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Scores for each individual dataset split on Llama3 . Solid lines show the score for the four proposals defined in Section 7 . Dashed lines show the five top- k eviction methods.
Figure 6: Scores for each individual dataset split on Qwen3 . Solid lines show the score for the four proposals defined in Section 7 . Dashed lines show the five top- k eviction methods.
Mean effective r ( ± std)
Target r
πH2O
πH2O-h
πmin
πmin-h
0.1
0.0999 ± 0.0003
0.1000 ± 0.0003
0.1000 ± 0.0002
0.0999 ± 0.0003
0.3
0.2999 ± 0.0004
0.3001 ± 0.0004
0.3000 ± 0.0004
0.2999 ± 0.0005
0.5
0.4999 ± 0.0004
0.5000 ± 0.0004
0.5000 ± 0.0004
0.5001 ± 0.0004
0.7
0.6999 ± 0.0004
0.7000 ± 0.0004
0.7000 ± 0.0004
0.7001 ± 0.0004
0.9
0.9000 ± 0.0003
0.9000 ± 0.0002
0.8999 ± 0.0002
0.9000 ± 0.0002
Appendix
Table 1: Difference between target and effective compression ratio is insignificant for Llama3 on the RULER dataset. Results are similar for Qwen3 and LongBench.
Figure 7: Importance sampling temperature scaling pairwise win scores. Llama3 (top) and Qwen3 (bottom) pairwise win scores at different importance sampling temperature scale values τ .
Figure 8: Importance sampling temperature scaling average total scores. Llama3 (top) and Qwen3 (bottom) average total scores at different importance sampling temperature scale values τ .
Figure 9: Pattern of average compression ratio per layer when probabilistically evicting. Each solid curve shows the average effective compression ratio when given a target compression ratio r . The target compression ratio is shown as a dashed dark gray line. The average of all points in a solid curve equals to the target r . This pattern shows that lower layers (closer to input) tend to evict less, while higher layers (closer to output) evict more.
Key-value (KV) cache growth is a major bottleneck in autoregressive decoding, as memory and bandwidth scale linearly with context length. Existing KV eviction methods often rely on static heuristics or proxy scores, which poorly track future token utility and cause brittle eviction as relevance shifts. To address this, we introduce KVpop, which learns a fixed-budget KV eviction policy by directly supervising the keep-or-drop decision. The scorer is trained against a novel future-attention target, computed efficiently without materializing dense attention maps. We further introduce a delayed memory-based scorer that, uniquely among learned eviction methods, defers scoring for a fixed number of steps to exploit near-future context. On AIME and HMMT mathematical reasoning, KVpop retains 98% of full-attention performance on Qwen3-4B at 75% KV cache compression and 97% at 88% compression, consistently outperforming established eviction baselines. Qwen3-8B shows even stronger results, reaching near-full teacher performance. These results show that supervising eviction with future-attention signals cuts memory costs while maintaining quality.
Most KV-cache eviction methods ask, in effect, which memory appeared important while reading the prompt? We instead ask which memory will matter while answering? Since decoding queries are unavailable at eviction time, prior future-aware methods rely on pseudo-responses or synthetic future-query estimates. We cast fixed-budget future-aware eviction as distributional estimation over plausible model-conditional query trajectories and introduce LORE-KV (Lookahead Output-perturbation with Reliability-weighted Ensembles for Key-Value caches), a training-free method that samples short autoregressive continuations from the frozen target model and uses their response-side query states to estimate prompt-token utility. Tokens are scored by projected leave-one-out attention-output deletion cost and aggregated across sampled futures with optional trajectory weighting. The temporary continuations are discarded before final decoding, requiring no auxiliary model or training. Ablations isolate the mechanism: at B=128, a single response-side continuation recovers about 89% of the gain over the prompt-window control, while additional futures provide smaller improvements. At B=128, LORE-KV raises the LongBench average on Qwen2.5-14B from 45.49 to 48.24 (+2.75) and the 16K RULER average on Mistral-7B from 45.20 to 51.05 (+5.85); on Llama-3.1-8B, the RULER margin over AnDPro widens to +8.13 and +11.65 points at 64K and 128K contexts. Gains diminish at larger cache budgets and coexist with task-level regressions. LORE-KV incurs 1.46-2.77x AnDPro's per-sample wall-clock time as a one-time compression overhead across six dense and hybrid-attention backbones. Project webpage: https://ahsanbilal7.github.io/train_free_kv/
Ahsan Bilal, Muhammad Ahmed Mohsin, Muhammad Umer +5
University of Oklahoma · Stanford University · University of Houston +3
KV-cache eviction is typically evaluated through average quality-memory trade-offs, yet a small average loss can hide requests whose utility degrades materially. We reformulate eviction as a deployment risk-control problem: a material degradation occurs when eviction lowers task utility by more than a deployment-specified tolerance relative to full-KV inference on the same request, and deployment risk is the population frequency of such events. Given a reliability contract specifying a target risk level and confidence requirement, we use a compressor-agnostic post-hoc certification procedure to select a retention policy from calibration data with a finite-sample guarantee, falling back to full KV when no compressed policy is certified. Across multiple eviction methods, Llama and Mistral models, and LongBench and RULER-32K, the same contract supports substantially different levels of eviction: on Llama, it certifies SnapKV at 75% retention on LongBench but no tested compressed policy on RULER-32K, triggering full-KV fallback. Policies with empirical degradation rates below the 5% target can still fail finite-sample certification; on Llama LongBench, empirical thresholding selects uncertified policies that retain 5-10 percentage points less cache across fixed-budget methods. The proposed framework converts a deployment-level reliability requirement into a KV-memory operating point.
Beomgu Kang, SoJin Yun, Hojoon Kim +1
Department of Artificial Intelligence, Korea University, Republic of Korea