acceptodds
Under review as a conference paper at ICLR 2027

A Probabilistic Interpretation of KV Cache Eviction

Abstract

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 same compression budget.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
KV cache, KV cache compression, importance sampling

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

The submisson looks at the error that comes from evicting entries out of the KV cache. It chooses which entries to keep by sampling with replacement, and then reweights each kept entry in later attention using it's sampling probability and how many times it was drawn. Evicted entries are thrown away for good, and their combined contribution is estimated from the entries that remain.

I agree with the starting point. Dropping tokens affects both the weighted sum over values and the softmax normalizer, and simply keeping the tokens that look important leaves both of those shifts unaccounted for. The proposal is to keep correction weights around after eviction, and the paper checks whether doing so actually helps.

I find Fig 2 to be the most informative. It puts corrected sampling, uncorrected sampling and deterministic selection side by side on the same underlying scores, with expected compression matched seperately per attention head, so the correction is tested directly. The authors also show that under very aggressive compression there are too few samples and variance gets high. The setup is fairly narrow, it only measures attention-output error on the first generated token for Llama3.2-3B, but it does back up the proposed mechanism.

One concern is with how novelty is framed. MagicPIG (ICLR 25) already uses self-normalized importance sampling for attention. This paper evicts permanently, which is a difference and the submission's contribution which I find interesting. But it also means that head-to-head timing comparisons need to be done carefully.

Downstream, the evaluation uses Llama3.2-3B and Qwen3-4B, with 130 RULER examples plus HotpotQA, QASPER and TriviaQA from LongBench restricted to prompts under 3,000 tokens. The method is competitive and comes out ahead in aggregate rankings. That is a good sign, but with this scope it can't show that the method holds up on long contexts or on bigger models.

I'm also not sure how much of the task gain is due to the correction itself. In Fig 3 expected compression is matched over the whole cache, yet sampling shifts how much budget each attention head ends up with, so part of the gain may come from that reallocation.

I lean towards accept. The paper is relevant and the contribution is meaningful but I dont think the evidence so far shows robustness in general. The authors should state that scope more plainly and discuss or show the effect of the downstream results and how the are related to correction and allocation.

Additional related work:

MagicPIG, ICLR 2025 ManifoldKV, ICML 2026

Critical strengths

See above

Critical weaknesses

See above

Questions for authors

See above

1 comment

We thank Reviewer 8PrH for the useful feedback and suggestions. Please see the revised PDF for the plots and tables referred in the rebuttal below.

  1. [Novelty vs MagicPIG] Thank you for pointing us to MagicPIG. We were not aware of this paper. As you mention, MagicPIG has to perform self-normalized importance sampling (SNIS) for every attention computation (which can become very expensive depending on the number of samples), while our method does so only once and then reuses the correction weights to perform the correction during generation for any future time step with provable guarantees (we have added a formal proof on the bias and error upper bounds of this correction in Theorem 2, Appendix D). Moreover, our work is constrained to the KV cache eviction setting where if we discard an entry it is not cheaply recoverable, while theirs is under the sparse attention setting where deactivated entries can be activated for later steps. Finally, we believe that our correction method is completely novel: although SNIS was used before, the idea of evicting once and then correcting at all future time steps was not present in the literature. We will of course draw the connections between MagicPIG and our own work in the revised paper.
  2. [Larger models and data] We provide experiments on 8B models and larger datasets with longer contexts in Appendix P.1, P.2 and P.3. For LongBench, we show that our method does either best or second best against other methods in ELO. For RULER we show that our method does best at compression ratios 0.1, 0.3, 0.5, and come second under compression ratios 0.7 and 0.9.
  3. [Ablations on sampling and correction] Thank you for this suggestion. We have included ablation experiments in Appendix O of the revised PDF. The conclusion is that sampling-based selection itself does not account for all the improvement and we do consistently get higher performance when performing correction. The tables in Appendix O.1 show probabilistic eviction with and without correction (the latter corresponds to sampling-based selection) across models and datasets, with raw scores and ELO ratings. They show that correction consistently improves performance.

We remain available to answer any further questions.

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

This paper formalizes KV cache eviction from a probabilistic perspective, proving the problem is computationally hard and reduces to expectation estimation approximable by sampling, and shows that existing methods are essentially zero-variance biased estimators that can be readily adapted to support decode-time correction. Experiments show that this probabilistic eviction combined with decode-time correction is more robust across tasks than existing methods at the same compression budget.

Critical strengths
  1. This paper studies an important problem and the presentation of this work is good.
  2. The probabilistic formulation provides a way to address eviction correction during decoding. By formulating the correction as an expectation estimation problem and approximating the expectation through sampling, the paper develops a practical approach to correcting evicted entries at decode time, an operation that has received relatively little attention in prior work.
Critical weaknesses

The major weakness of this paper is insufficient experiments, including the scope as well as the compare baseline methods. The detailed comments are as follows.

  1. The scope of the experiments is limited. The paper only utilizes Llama3.2-3B and Qwen3-4B—both of which are small, dense models; it would be beneficial to include a larger model (e.g., around 30B parameters). Furthermore, the evaluation on RULER is restricted to only 130 samples, while the evaluation on LongBench covers just three subsets (HotpotQA, QASPER, and TriviaQA) and excludes samples with a context length reaching 3,000 tokens. It is recommended to incorporate larger models, a broader range of task types, and experiments across various longer context lengths, while reporting task performance for each compression ratio.

  2. The baseline methods are outdated and do not include comparisons with current state-of-the-art (SOTA) approaches. Methods such as SnapKV, H2O, and StreamingLLM predate 2024 and are insufficient for establishing the advantages of the proposed method over more recent, robust baselines. It is recommended to include comparisons with high-performing methods like KVzip, while ensuring consistency across actual cache budgets, context lengths, and evaluation settings.

Questions for authors
  1. What are the performance on larger models, a broader range of task types, as well as various longer context lengths?
  2. Can the proposed method outperform more recent works, for example KVzip?
2 comments

We thank reviewer ehR2 for the useful feedback and suggestions. Please see the revised PDF for the plots and tables referred in the rebuttal below.

  1. [Larger models and data] We are constrained by limited compute, and cannot fit 30B models in our GPUs. We provide experiments on 8B models and larger datasets with longer contexts in Appendix P.1, P.2 and P.3. For LongBench, we show that our method does either best or second best against other methods in ELO. For RULER we show that our method does best at compression ratios 0.1, 0.3, 0.5, and comes second under compression ratios 0.7 and 0.9.
  2. [Baseline methods] We included the standard baselines that recent papers have tested on. All of our baselines have been at the same scale of compute and memory overhead. KVZip [1] departs from that since it requires doubling the context and multiple forward passes, and Fast KVzip [2] requires offline training of small, model-specific gates. Other high-performing methods introduce similar requirements. RestoreKV requires training and an additional forward pass [3], KVzap requires training model-specific gates [4], and KVgrad requires forward and backward passes. These additional computational requirements make comparisons at the same cache budget unfair. Our method requires no additional forward passes and requires storing only a single vector of size k (the budget).

[1] https://arxiv.org/abs/2505.23416

[2] https://arxiv.org/abs/2601.17668

[3] https://arxiv.org/abs/2608.01247

[4] https://arxiv.org/abs/2601.07891

We remain available to answer any further questions.

I have carefully reviewed the revised paper and appreciate the authors' efforts to address my concerns. However, the additional experiments still do not fully address my concerns regarding the experimental evaluation. I believe the evaluation scope remains limited, particularly in terms of model scale, task diversity, and comparisons with recent SOTA methods. Overall, I still believe more comprehensive experiments are needed to sufficiently demonstrate the effectiveness and advantages of the proposed method.

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

The KV cache eviction is essential in accelerating large language models. This work formalised the KV cache eviction from a probailistic reasoning perspective and unified existing methods as special cases of zero-variance top-k estimators. The authors proposed a self-normalized importance sampling approach to sample from a proposal distribution to adjust the probabilities at the decoding time. The experimental results demonstrated the effectiveness of this type of estimators by comparing with the-state-of-art methods.

Critical strengths
  1. Formalised the KV cache eviction from a probailistic reasoning perspective and unified existing methods as special cases of zero-variance top-k estimators.
  2. Proposed a self-normalized importance sampling estimator with reasonable upper bounds on both bias and variance.
Critical weaknesses
  1. As the proposal is built from past queries, the variance constant scales with its mismatch to decode-time attention. This mismatch grows with query drift, which is the central difficulty of KV eviction and which the analysis leaves unmodelled.

  2. The empirical evidence is limited and the gains are marginal. Only small models (3B and 4B) are tested. The results in Table I show that the improvement is marginal.

Questions for authors

The method is stochastic, and a single eviction draw is fixed for the whole generation. How many random seeds were used, and what is the run-to-run variance of the scores?

The introduction states that KV eviction “has remained informal in the literature”. How does this framework relate to existing principled formulations? Examples include information-theoretic treatments that cast eviction as maximising capacity over a query distribution (e.g. Yang et al., ICML 2026).

1 comment

We thank reviewer Phqd for the useful feedback and suggestions. Please see the revised PDF for the plots and tables referred in the rebuttal below.

  1. [Query drift] Our analysis does cover query drift through the correction method of Algorithm 1. Indeed we had mentioned that the self-normalized importance sampling bounds should give upper bounds on the error between the estimated and ground-truth target expectation, however we had not formally proven these bounds. We have added Theorem 2 that explicitly shows that these O(1/m) bounds (on bias and mean squared error) hold. In fact, the constants for these nonasymptotic upper bounds are even better for our case than in the standard case. The proof is in Appendix D. We again thank the reviewer; indeed we should have provided a formal argument for the bounds, which we now do.
  2. [Informality in the literature] Thank you for pointing us out to Yang et al., 2026; we were not aware of this paper. Indeed they provide a formalization of KV cache eviction (and we will revise the wording to say that the literature has largely been informal but that there have been attempts at formalizing and then cite Yang et al., 2026), however we would like to note that although Yang et al., 2026 does give a possible more formal interpretation to KV cache eviction, they still rely on assumptions and heuristics. Crucially, they assume that queries are Gaussian distributed, which then yields a closed form solution; however this form is infeasible to compute, and so they come up with Eq. 7 in their paper which attempts to approximate the Gaussian optimization problem, with no provable guarantees on the approximation. It is very distinct from our own treatment, where in our case the target to be optimized comes from the attention mechanism itself which provides a clear goal for approximation, rather than their more high level information theoretic interpretation.
  3. [Gains and larger models] We would like to point out that Table 1 shows that proposal πH2O-h\pi_{\text{H2O-h}} achieves a 95% confidence lower confidence bound higher than any of the other methods’ ELO rating. With regards to larger models, we have added more experiments for larger models in Appendix P.1, P.2 and P.3. For LongBench, we show that our method does either best or second best against other methods. For RULER we show that our method does best at compression ratios 0.1, 0.3, 0.5, and come second under compression ratios 0.7 and 0.9.
  4. [Variance across seeds] We report variance across seeds in Appendix O.3 of the revised PDF.

We remain available to answer any further questions.

Reviewer_Fr7dOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary
  • This paper shows that KV cache eviction is NP-complete and, by interpreting attention as an expectation, reformulates eviction as an expectation estimation problem. Under this view, existing top-k methods are zero-variance but unboundedly biased estimators. The authors propose probabilistic eviction combined with importance-sampling-based decode-time correction, and claim performance comparable to existing methods with greater robustness across tasks.
Critical strengths
  • The theoretical framing is clear. The NP-completeness result, the interpretation of existing score-based methods as proposal distributions, and the identification of decode-time correction as a previously unaddressed problem form a coherent line of reasoning.
  • The paper is easy to follow thanks to its step-by-step exposition. In particular, Figure 2 shows at a glance how attention error varies with compression ratio and importance weight temperature, giving an intuitive picture of the bias–variance trade-off.
Critical weaknesses
  • The practical efficiency gains are not validated. Appendix L reports only eviction time and per-step correction time, with no end-to-end throughput, latency, or memory measurements. Moreover, the current implementation recomputes evicted entries, and efficiently handling different budgets per head would require dedicated kernels. It is therefore unclear whether eviction’s primary goal, improved efficiency, is actually achieved. The authors should report the accuracy–throughput trade-off under matched settings.
  • The source of the performance gains is not isolated. The proposed method differs from existing methods in three ways at once: (1) sampling-based selection, (2) adaptive per-head budgets, and (3) correction. Ablations against uniform per-head budgets, probabilistic eviction without correction, and top-k with adaptive budgets are needed.
Questions for authors
  • Please see the weaknesses above.
5 comments

We thank Reviewer Fr7d for the useful feedback and suggestions. Please see the revised PDF for the plots and tables referred in the rebuttal below.

  1. [Memory/time] Our contributions are primarily theoretical and algorithmic, and we consider systems-level engineering such as custom ragged-tensor kernels out of scope. Because autoregressive decoding is memory-bandwidth bound [1], wall-clock speedups will ultimately be dictated by KV cache size. We therefore consider compression ratio as the primary object of study, similar to other works [2, 3].
    • [1] Kwon, Woosuk, et al. "Efficient memory management for large language model serving with pagedattention." Proceedings of the 29th symposium on operating systems principles. 2023.
    • [2] Devoto, Alessio, et al. "A simple and effective l_2 norm-based strategy for kv cache compression." Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.
    • [3] Kim, Jang-Hyun, et al. "Kvzip: Query-agnostic kv cache compression with context reconstruction." Advances in Neural Information Processing Systems 38 (2026): 167563-167591.
  2. [Ablations on sampling and correction] Thank you for this suggestion. We have included ablation experiments in Appendix O of the revised PDF. The conclusion is that sampling-based selection itself does not account for all the improvement and we do consistently get higher performance when performing correction. The tables in Appendix O.1 show probabilistic eviction with and without correction (the latter corresponds to sampling-based selection) across models and datasets, with raw scores and ELO ratings. They show that correction consistently improves performance.
  3. [Ablations on adaptive per-head] Adaptive per-head budget also does not account for all the improvement. We ran experiments for AdaKV (a per-head budget wrapper that allow for different scoring methods, e.g. SnapKV) across SnapKV, K-norm and H2O scores (see Appendix O.2 in the revised PDF) and found that adaptive per-head eviction does not solely account for the improvement.

We remain available to answer any further questions.

I agree that decoding is memory-bandwidth bound, but wall-clock speedups also depend on the pre-/post-processing overhead the method introduces, which the rebuttal does not address. Without clearer evidence on this point, I will keep my current score, though I would not object to acceptance if the other reviewers see the contribution more favorably.

Thank you for your response. We have added a revision to the PDF including overall latency and throughput (including any overhead that might arise before and after eviction and decoding) of one of the proposals πmin-h\pi_{\text{min-h}} against SnapKV, TOVA and H2O (see Appendix M.1). Due to time constraints (the rebuttal period closes very soon) we are unable to provide full data on all competitors and proposals.

Appendix M.1 shows that despite the naïve implementation without dedicated kernels and recomputing the correction weights at every decoding time step, importance attention incurs an overhead that is comparable to other methods.

We remain available to answer any questions.

Comments on the paper

2 comments

We would like to thank all reviewers for their feedback. We summarize here our revisions and additional experiments for convenience. We have included more details in addition to the rebuttal messages in the revised PDF. Updated content in the PDF is colored blue.

  1. We prove bounds on our estimator and show that the O(1/m) bounds on the error and bias hold for our estimator. We show the proof in Appendix D.
  2. We show ablation on correction: probabilistic eviction with and without correction. We show that correction consistently improves performance over sampling-based eviction, both on raw scores and ELO ratings.
  3. We show ablation on per-head eviction: head-wise budget reallocation does not necessarily provide improvements, meaning that our method’s improvement does not come solely from per-head budget eviction.
  4. We show additional experiments with larger models (8B) and larger subsets of the data. Our methods continue to be competitive. For LongBench, we show that our method does either best or second best against other methods in ELO. For RULER we show that our method does best at compression ratios 0.1, 0.3, 0.5, and come second under compression ratios 0.7 and 0.9.

We are available to answer any further questions.

Area_Chair_s6J6OpenReview ↗

Action Required: Respond to Author Rebuttals Before the Discussion Period Ends

Dear Reviewers,

The authors have posted their rebuttals. As the author–reviewer discussion period is coming to a close soon, please read their responses and participate in the discussion.

All reviewers are expected to respond, at minimum with a brief acknowledgment confirming that the reviewers have read and considered the authors’ rebuttals. If your concerns have been addressed or remain unresolved, please briefly indicate this in your response.

Thank you for your time and effort.

Best,

Your AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.