acceptodds
Under review as a conference paper at ICLR 2027

A Surrogate Distribution Perspective on Key-Value Cache Merging

Abstract

Merging entries in the key-value (KV) cache of large language models is a promising approach for managing GPU memory and throughput, and hence scaling to larger context windows. However, naively merging entries changes the scaled dot-product attention output at each layer, and if done aggressively seriously degrades accuracy on retrieval and reasoning tasks. In this paper we observe that the exact contribution of a merged cluster to attention is the cumulant generating function of the distribution of its constituent keys, together with the mean value under the exponential tilting of that distribution induced by the query. Compensating for a merge is therefore a question of which surrogate distribution to substitute for the cluster, and we show that a two-atom surrogate matching the cluster's first two key-norm moments yields closed-form corrections to both the attention score and the merged value, at a cost of two scalars and one vector per merged cache slot. We include in our analysis the Gaussian surrogate implicit in a second-order Taylor expansion of the attention score function. The resulting corrections are exact for two-token merges and for every query, and reduce exactly to standard attention for entries that have never been merged. Moreover, the statistics that our corrections depend on are invariant to the order in which merges are performed, so clusters can grow online as new tokens are processed. Experiments validate our theory by measuring fidelity of the induced corrections and sweeping performance on standard reasoning and retrieval tasks against merge threshold.

Primary area:
foundation or frontier models, including LLMs
Keywords:
key-value cache, large language model, merging

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_k9UKOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
2(+1)
Read review
Paper summary

This paper presents a surrogate-distribution framework for correcting the attention approximation introduced by KV cache merging. The authors conclude that existing methods can be understood within a common framework, where different correction strategies use different surrogate distributions. To handle cases where keys are not aligned, the authors introduce an additional correction in logit space. Experiments demonstrate improved approximation fidelity over the one-atom baseline.

Critical strengths
  1. The paper presents rigorous score and value corrections formulas and establishes exactness for two-token merges under keyalignment. The appendix further provides error bounds for larger clusters and show that the error does not grow linearly with the number of merged clusters. The logit-space variance decomposition into parallel and orthogonal components demonstrates careful considerations of the attention structure.

  2. The surrogate-distribution perspective provides a unified framework for understanding KV cache merging correction methods. It shows that KeepKV’s count-based correction corresponds to a one-atom surrogate, while Taylor expansion corresponds to a Gaussian surrogate. While the two-atom surrogate achieves exact merging for two tokens, it is under the strong key-alignment assumption. The correction formulas proposed in this paper may extend existing methods based on the key-alignment assumption to scenarios with misaligned keys.

Critical weaknesses
  1. The research problem is not clearly presented. No measurement data or illustrative figure is given to help justify the limitation of existing works. The paper organization is also strange: the introduction is too short, and there is not clear summarization of the key design challenges and insights. It is hard to grasp the novelty of this paper.

  2. All experiments cover only two 7B–8B models on a single H100 GPU. Although the results show that the proposed corrections are effective on the evaluated benchmarks, it remains unclear how robust the approximation and its performance are across different model sizes, attention configurations, and context lengths. A more comprehensive sensitivity study would strengthen the method’s generality.

  3. The two-atom surrogate’s exactness property relies on the simplification of key-alignment assumption. Although the correction in logit space introduced by the authors partially addresses misaligned keys, the paper neither provides systematic analysis of how frequently this assumption is violated in practice nor quantifies the degradation when this assumption fails. A clear characterization of the relationship between the degree of key misalignment and the approximation error would strengthen the paper

Questions for authors

See the above weakness points.

2 comments

Thank you for the review, and for recognising the rigour of the corrections and the unifying value of the surrogate-distribution view. We would like to address the soundness concern directly and worry that this has led to the Clear Reject recommendation, since the whole aim of the paper is to put KV-cache merging on a sound footing, and believe that our surrogate distribution formulation does that cleanly.

Problem statement and presentation. We accept that the introduction is too short and does not make the challenges and insights explicit. In the revised version we have restructured it around three points: (i) the problem, that an averaged merged slot has the probability mass of one token and a fixed value, whereas the true contribution is query dependent; (ii) the challenge, that the correction must hold for queries not seen at merge time, from a constant amount of storage per slot; and (iii) the insight, that the exact contribution is a cumulant generating function, so that every correction is derived analytically from the choice of surrogate distribution.

On justifying the limitation of existing work: Figure 1 shows on a controlled cluster that the one-atom surrogate (the KeepKV correction) cannot represent the curvature of the true score, and Figure 2 measures the same failure on real Llama-3.1-8B activations. The uncorrected and count-corrected variants have the largest score and value errors at every threshold. We have pointed to both figures from the revised introduction.

Model sizes, attention configurations and context lengths. Please see our replies to Reviewer oLmh on model size and Reviewer zSZg on context length.

How often key alignment is violated, and the cost when it is. This is the question Figure 2 is designed to answer. Every two-token cluster formed at threshold tt has key cosine of at least tt in every head, so the threshold sets the worst-case violation. At m=2m = 2 the two-atom corrections are exact for aligned keys (Props. 3.2 and 3.3), so the residual plotted at each threshold is the error due to misalignment alone, and it falls monotonically as alignment tightens. The logit-space variant, which drops the assumption, removes most of the score residual. We will state this reading of Figure 2 explicitly.

Thank you for the detailed response and the revised manuscript. The restructured introduction now states the problem, the requirements a valid correction must meet, and the key insight clearly, and the pointers to Figs. 1–2 make the limitation of existing corrections concrete. Your reading of Fig. 2 also answers part of my question on key alignment: the merge threshold bounds the worst-case misalignment, and at m = 2 the residual error is attributable to angular spread alone. I raise my score accordingly from 1 to 2.

Two concerns remain. First, the evaluation is still limited to two 7–8B models, with RULER accuracy reported only at 16K. Second, the alignment analysis covers m = 2, whereas the distribution of within-cluster misalignment and of cluster sizes at practical thresholds is not reported. Together with the observation that the better-approximating two-atom variants are not more accurate per byte of cache, the practical benefit over existing merging and eviction methods remains limited.

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

This paper tries to reduce the difference in attention outputs before and after KV cache merging by using statistical information collected from merged KV clusters. Specifically, statistics such as the mean, variance, and covariance of keys and values are used. A surrogate-distribution framework is introduced and closed-form corrections to compensate for the information loss caused by KV merging is derived, without requiring additional training.

Critical strengths
  1. The paper provides a new perspective for understanding attention errors caused by KV cache merging.
  2. Strong theoretical analysis. The proposed two-atom corrections have closed-form expressions, exactness guarantees under specific conditions, and theoretical error bounds.
  3. No training is needed for the error correction.
Critical weaknesses
  1. The current results are only compared with TOVA, more comparisons with KV compression methods should be addressed.
  2. Only two models are used to demonstrate the effect of the proposed methods, leaving the effectiveness on recent and lager models unclear.
Questions for authors
  1. The paper only focus on the conpensation of the error caused by the KV merging. But what kind of KV can be regarded as a cluster? And how to evaluate the similarity between each K? Scan over all key may not be a good solution. What is the overhead of the proposed method?
  2. Can the proposed method be used with KV eviction together? Additional experiments evaluating such a combination would be helpful to demonstrate the generalizability and practical applicability of the proposed method.
1 comment

Thank you for the positive assessment and the specific questions.

Comparisons beyond TOVA. Figure 3 compares against three published methods, not only TOVA. Variant 1 is plain merging without correction (Wang et al., 2024) and Variant 2 is the count correction of KeepKV (Tian et al., 2026), the strongest published merge correction. TOVA is included as a state-of-the-art eviction reference. In the revised version we will add H2O as a second eviction baseline on all three tasks and both models.

Larger and more recent models. We agree that results on larger and more recent models would strengthen the empirical section. Sweeping every variant and baseline over the full range of thresholds on all three tasks is costly, so we kept the evaluation to two 7-8B models. The contribution of our paper is the principled formulation and the closed-form analysis that follows from it (see the general response), and nothing in that derivation depends on model size.

What is a cluster, how is similarity measured, and is a full scan needed? A token joins a cluster when the cosine similarity of its key to the slot's key exceeds the merge threshold tt, taken as the worst case over heads (Section 3, footnote 1). We do not scan the whole cache. Merging runs online over chunks of incoming tokens, and each token is compared only against slots inside a bounded search window. Because the statistics are additive power sums (Section 3.3), merging a token into a slot is a single vector addition, and Prop. A.12 shows the result does not depend on merge order.

Overhead. Memory: Table 2 lists the storage per merged slot. The variant we deploy (Variant 6) stores three scalars beyond the key and value, i.e., (2d+3)/2d(2d + 3)/2d, or about 1.2% per merged slot at d=128d = 128. Unmerged tokens incur no overhead. The cache-size axis of Figure 3 includes this cost. Compute: the corrections are evaluated inside fused Triton attention kernels. App. A.10 reports prefill and decode throughput against the unmodified model from 16k to 128k context; at aggressive thresholds merged decoding is faster than the unmodified model at every context length measured.

Combining with eviction. Yes. The corrections act on how a slot is scored and read, not on which slots are kept, so a merged slot can be evicted by any policy like any other entry, and eviction can be applied after merging. However, we have not run this combination.

Reviewer_zSZgOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes a critical idea that a merged KV entry should return a query-dependent score and value, so it behaves more like the original tokens. The authors proves these corrections by approximating the distribution of keys within each merged group. The authors also clarified the reason that why ordinary averaging fails. The experiments reveal an important trade-off, across two models and three benchmarks. The corrections improve approximation of the original attention computation. Merging two tokens saves roughly 25%, versus roughly 49% for the practical logit-space variant. This paper has a deep analysis of the KV cache merging with detailed proves and experiments are also extensive.

Critical strengths
  1. This paper provides a clear and principled formulation of KV merging. The analysis of why ordinary averaging fails is meaningful. Averaging keys and values loses attention mass and value selection. The explanation is straightforward and reasonable.

  2. The authors show a closed-form corrections with meaningful guarantees. The method corrects both attention scores and values without training or calibration. This makes the method easy-use.

  3. The paper also provides memory-aware evaluation. The accuracy comparisons show the extra statistics in bytes. This is very valuable.

Critical weaknesses
  1. There is a gap between the theory and the practical variant. The exactness guarantees requires perfectly aligned keys. Real clusters do not follow this assumption. The practical variant estimates angular effects isotropically and ignores the full value correction because the covariance matrix is too expensive. Therefore, the behavior is only partially explained by the main guarantees.

  2. Experimental scope could be extended. There are only two 7-8B models and three tasks. And RULER is only measured at 16k context. More models, tasks and longer context would be helpful. And throughput comparison uses unmodified HuggingFace as the baseline. SGLang or vLLM implementation is much more solid to show the results.

  3. Based on Figure 3 better approximation does not consistently lead to better accuracy per byte. The authors could provide a zoom-in version to show detailed results.

Questions for authors

It would be helpful if the authors could provide a accuracy-speed curve, where the x-axis is the end-to-end decode tokens/s and the y-axis is the accuracy on various benchmarks. This would show the efficiency of method in practical applications.

2 comments

Thank you for the detailed review and for recognising the value in our formulation, the closed-form corrections and the memory-aware evaluation.

Gap between theory and the practical variant. We agree that the guarantees hold under key alignment and that real clusters violate it; please see the general response for how we position this. We would add two points. First, the framework is what lets us measure the violation: at m=2m = 2, Props. 1 and 2 make the two-atom correction exact for aligned keys, so any residual in Figure 2 is due to angular spread alone, and it falls monotonically as the threshold tightens. Second, the logit-space variant (ID 6) is the framework applied without the alignment assumption, and it recovers most of that residual on the score side. The remaining gap, the full value correction, is a storage limitation that the framework identifies precisely (the d×dd \times d statistic Σvk\Sigma_{vk}), not an unexplained effect.

Experimental scope. We agree that more models and longer contexts would strengthen the paper although we don't expect the overall message to change. The throughput experiments (App. A.10) already run Llama-3.1-8B on RULER at 16k, 32k, 64k and 128k tokens, and we will report accuracy in the final version of the paper when we have more time for compute.

Baseline implementation. We agree that vLLM or SGLang would give a different measure of runtime overhead compared to HuggingFace. Our corrections need a modified attention kernel, and porting it into a paged-attention serving stack was beyond the scope of this paper. To make the HuggingFace comparison fair, both the merged and the unmodified model run their decode step as a captured CUDA graph, so the comparison is like for like. We will state this explicitly in App. A.10.

Figure 3. We agree that better approximation does not consistently give better accuracy per byte, and we make this clear in Section 4.2. Specifically, the two-atom variants carry an extra dd-vector per slot, which the byte axis measures. We have added zoomed-in panels of Figure 3 to the appendix.

Accuracy–speed curve. Thank you for the suggestion. We have added this to the appendix.

Thanks for your detailed reply. The rebuttal has resolved most of my concerns. Thus, I improved rate to weak acceptance.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Response to All Reviewers

We thank the reviewers for their thoughtful comments, and for recognising the paper's "clear and principled formulation" (zSZg), "strong theoretical analysis" (oLmh) and "unified framework" (k9UK). Existing merge corrections are justified empirically, or are exact only for the query seen at merge time. We start instead from an exact identity: that a merged cluster's contribution to attention is the cumulant generating function of its constituents' key-norm (or logit) distribution up to log⁡m\log m. Compensating for a merge is therefore a choice of surrogate distribution, and each choice gives a closed-form correction: KeepKV's count correction is the one-atom surrogate and the Taylor expansion is the Gaussian one. Our two-atom surrogate is exact for two-token merges under every query, and its logit-space version replaces the key-alignment assumption with an isotropic approximation of the angular spread. The statistics are additive, so merging is order-invariant and online, and the error bounds (App. A.6) show that errors do not accumulate across clusters.

We do not claim that the theory fully explains the empirical results. The exactness guarantees assume aligned keys, which real clusters violate, and better approximation does not translate monotonically into better accuracy per byte (Section 4.2, Figure 3). The framework is still a step forward since it makes the assumptions behind each correction explicit and measurable. Figure 2, for example, isolates the error at m=2m = 2 that is due to key misalignment alone. A heuristic correction gives no such analytical ability.

In the revised version we have addressed comments from the reviewers, including adding an accuracy-versus-decode-throughput figure from existing runs (zSZg), additional eviction baselines (e.g., H2O), zoomed-in panels of Figure 3, and a restructured introduction that clearly states the problem, challenges and insights (k9UK). Changes in the reviews are highlighted in blue. Detailed responses to reviewers are given below.

Area_Chair_UGroOpenReview ↗

Discussion Phase

As the discussion period is rapidly coming to a close (Nov 18 AoE), I would like to remind the reviewers to please participate in discussion and acknowledge any comments posted by the authors. A secondary, important reminder: full disclosure of any AI usage is required and the reviewer must include their own human-written assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.