acceptodds
Under review as a conference paper at ICLR 2027

RefineKV: Query-Adaptive KV Cache Compression via Attention-Error Bounds

14 views

Abstract

Repeatedly accessing the full key–value (KV) cache is a major bottleneck in long-context language model decoding. We find that small query-specific subsets can accurately approximate full attention, yet their union covers nearly the entire cache, motivating query-adaptive access for the KV cache. A natural approach is to split the KV cache into clusters, using compact representatives for clusters that incur negligible error while expanding the rest to their original KV entries. We derive a principled selection criterion, an upper bound on attention-output error, which reveals two complementary factors governing the error: importance measures the impact of a cluster, while distortion measures how faithfully the cluster can be represented. Based on this criterion, we propose RefineKV, a decoding-time query-adaptive KV compression method. Experiments on two models and three benchmarks demonstrate that RefineKV retains near-full-attention quality while achieving up to speedup in the attention phase and faster decoding, establishing a new quality–latency Pareto frontier.

Primary area:
generative models
Keywords:
KV compression, Efficient decoding, Efficient attention

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

This paper studies query-adaptive KV cache compression through an upper bound on attention-output error. The bound captures two factors: global importance and local distortion. Based on this analysis, the authors propose REFINEKV, a decoding-time method that computes exact attention for selected clusters and approximates the remaining clusters using representatives. Experiments on two models and three benchmarks show promising trade-offs between quality and decoding efficiency.

Critical strengths

The paper is well written and easy to follow. The proposed selection criterion considers both cluster importance and approximation error, which is a reasonable motivation for query-adaptive refinement. The experiments also report actual decoding latency, which is more informative than reporting only the KV-access budget.

Critical weaknesses
  1. The benefit of the proposed risk score is not sufficiently established. The paper lacks comparisons against simpler alternatives, such as p^C\hat p_C and p^CVC\hat p_C V_C, at matched KV-access budgets. The correlation in Figure 2 does not establish that the full score makes better refinement decisions than these alternatives. Since this score is central to the methodological contribution, the missing ablations leave its practical value insufficiently supported.

  2. The latency comparisons may be confounded by differences in execution mode. Appendix B.2 describes full-step CUDA Graph capture for REFINEKV, whereas Appendix C.2.3 describes eager execution for Full Attention and some baselines. Without clarification and comparisons under matched execution conditions, it is difficult to attribute the reported speedups to the proposed method. This uncertainty directly weakens the paper’s central claim of an improved quality–efficiency trade-off.

Questions for authors
  1. How is the refinement threshold τ\tau selected? The same thresholds are evaluated on two models, but it remains unclear how reliably they transfer across model sizes, context lengths, and cluster sizes. Could the authors clarify when retuning is necessary and how it should be performed?

  2. The evaluation covers only two similarly sized models, Llama-3.1-8B and Qwen2.5-7B. Could the authors include a moderately larger model, such as Qwen2.5-14B, to better assess generalization across model sizes? Reporting both quality and latency, together with any necessary threshold adjustments, would strengthen this evaluation.

  3. Could REFINEKV also be applied to vision-language models? Since the proposed error bound does not depend on the modality of the KV entries, it would be helpful to discuss whether visual tokens introduce additional challenges, such as requiring different clustering strategies or risk thresholds.

8 comments
AuthorsOpenReview ↗

Part 1: weakness 1

Thank you for your thorough and insightful review! Here are our response:

Weakness1

W1.1: The benefit of the proposed risk score is not sufficiently established. The paper lacks comparisons against simpler alternatives, such hatpC as pcvc and , at matched KV-access budgets. The correlation in Figure 2 does not establish that the full score makes better refinement decisions than these alternatives. Since this score is central to the methodological contribution, the missing ablations leave its practical value insufficiently supported.

Response: We conduct the selection rule ablation. The matched-budget ablation shows that RCR_C outperforms importance-only selection by 16–20 points and a Quest-style bound by 3.6–4.9 points at the same budget. Correlation alone cannot separate RCR_C from attention mass. The partial Spearman correlation given p^C\hat p_C reflects that RCR_C provide the additional information beyond attention mass.

Selection Rule Ablation. We keep the per-head token quota are fixed(same number of expanded clusters), and everything else fixed, only change the decode selection score. Experiment done on Llama-3.1-8B on RULER-128K, 260 samples per arm, no anchors, at the controlled same budgets. For box bound, it correspond to τ=.01\tau = .01 / .1.1.(≈9% / 3.6% of the KV cache per step).

We find: (1) The box bound is better than the ellipsoid bound. We therefore use the box bound in all main experiments. (2) At a matched per-head budget on RULER-128K, R_C outperforms importance-only selection (p^C\hat p_C or p^CVC\hat p_C V_C) by 11–21 points and a Quest-style bound by 3.7–3.9 points. Deviation alone is even worse (23–42 points lower), so neither mass nor deviation alone comes close, and the gain comes from combining them in R_C.

Scoreτ=0.01 Acc.Δτ=0.1 Acc.Δ
Ours (RCR_C)70.27—62.58—
RCR_C, ellipsoid68.90−1.3757.29−5.28
Quest-style66.38−3.8858.87−3.71
p^CVC\hat p_C V_C58.78−11.4941.38−21.19
p^C\hat p_C59.35−10.9242.87−19.71
δC\delta_C47.23−23.0420.68−41.90
RCR_C, exact δC\delta_C (oracle)72.00+1.7369.06+6.49
Full attention73.37+3.1073.37+10.79

Definition of the correlation target. For a cluster CC and query qq, let

oC=1Z∑i∈Ceq⊤ki/d vi,o^C=p^C vˉC,p^C=∣C∣ eq⊤kˉC/d∑C′∣C′∣ eq⊤kˉC′/d,o_C = \frac{1}{Z}\sum_{i\in C} e^{q^\top k_i/\sqrt d}\, v_i, \qquad \hat o_C = \hat p_C\, \bar v_C, \qquad \hat p_C = \frac{|C|\, e^{q^\top \bar k_C/\sqrt d}}{\sum_{C'} |C'|\, e^{q^\top \bar k_{C'}/\sqrt d}},

where ZZ is the Full Attention softmax normalizer. oCo_C is CC’s contribution to the Full Attention output and o^C\hat o_C its contribution to the output in which every cluster is replaced by its representative, so ∑C(oC−o^C)\sum_C (o_C - \hat o_C) is exactly that approximation’s error and ∥oC−o^C∥\lVert o_C - \hat o_C\rVert is CC’s share of it.

Correlation analysis. We find that p^C\hat p_C alone reaches a Spearman correlation of .975 with the target, which confirms the reviewer’s point. We therefore also report the partial correlation given p^C\hat p_C, which measures what a score adds beyond attention mass. RCR_C does carry information beyond mass (partial ρ=.49\rho = .49), more than a Quest-style bound (.32), and oracle delta is (.81). The deviation term is therefore the ingredient that separates RCR_C from an importance score.

ScoreSpearman with ∥oC−o^C∥\lVert o_C - \hat o_C \rVertPartial Spearman given p^C\hat p_C
p^C\hat p_C.975—
p^C⋅VC\hat p_C \cdot V_C.975.06
Quest-style UCU_C.864.32
RCR_C (box δC\delta_C).975.49
RCR_C (exact δC\delta_C, oracle).990.81

Revision: We add ablation study in Section 5.3, Table 2. And we add partial correlation analysis in Appendix B.3.

AuthorsOpenReview ↗

Part 2: weakness 2

Weakness2

The latency comparisons may be confounded by differences in execution mode. Appendix B.2 describes full-step CUDA Graph capture for REFINEKV, whereas Appendix C.2.3 describes eager execution for Full Attention and some baselines. Without clarification and comparisons under matched execution conditions, it is difficult to attribute the reported speedups to the proposed method. This uncertainty directly weakens the paper’s central claim of an improved quality–efficiency trade-off.

Response: Thank you for pointing this out. We update full attention and baselines with CUDA graph version to ensure fair comparison.

CUDA Graph. In the submission, RefineKV was timed with CUDA Graph while Full Attention and the baselines were timed eagerly, which favored RefineKV. We have removed this inconsistency. Full Attention, RefineKV, all eviction baselines (SnapKV, PyramidKV, StreamingLLM) and Double-P are now timed with CUDA Graph.

Llama RULERLlama HELMETLlama LongBenchQwen RULERQwen HELMETQwen LongBench
Full AttentionQuality73.3769.1048.8665.8854.5749.34
RefineKV, τ=.01\tau = .01Quality70.1968.4348.8765.2854.4849.23
Speedup, both CUDA Graph1.56×1.43×1.55×1.19×1.13×1.18×
Speedup, both eager1.49×1.37×1.49×1.15×1.10×1.15×
RefineKV, τ=.1\tau = .1Quality62.5856.8048.9560.3552.8349.13
Speedup, both CUDA Graph1.67×1.56×1.67×1.27×1.23×1.27×
Speedup, both eager1.59×1.47×1.59×1.23×1.18×1.22×

Anchors are removed from all main experiments. All three benchmarks (RULER, HELMET, LongBench) on both models now use Q=0Q = 0, so every main result reflects the selection criterion alone. Results with anchors (Q=32Q = 32) are moved to the appendix as an optional add-on.

Revisions. We update main figure and all the result table in the paper, with fair comparison.

AuthorsOpenReview ↗

Part 3: Questions 1 and 2

Questions 1

How is the refinement threshold (\tau) selected? The same thresholds are evaluated on two models, but it remains unclear how reliably they transfer across model sizes, context lengths, and cluster sizes. Could the authors clarify when retuning is necessary and how it should be performed?

Response:

τ\tau as a quality–time threshold. RefineKV uses the bound only to derive the form of RCR_C, i.e., how attention mass, deviation and value norm combine, and uses RCR_C only to rank clusters and expand those most likely to cause large error. Accordingly, τ\tau is not an error tolerance but a threshold that trades quality against time.

How τ is chosen. τ is a quality–cost threshold on the selection score R_C, not a calibrated error tolerance (see our response to R1 W1). We did not tune it per model or benchmark: we use a fixed log-spaced grid, τ ∈ {0.1, 0.01}, plus τ = 0.001 added in the rebuttal. The same values were used for every model, benchmark and cluster size below.

Transfer across model size. On Qwen2.5-14B (RULER-128K), with no retuning, τ = .01 gives −0.99 [−2.88, +1.04] vs Full at 1.39×, and τ = .1 gives −3.78 [−6.72, −0.91] at 1.55×. On Qwen2.5-7B the corresponding losses are −0.60 and −5.53. The loss at each τ is therefore similar across the two sizes. Across model families (Llama-3.1-8B, Qwen2.5-7B), τ = .01 is within the CI of Full on 4 of 6 panels.

Transfer across cluster size. On Llama RULER-128K (Q = 0, τ = .01), |C| = 16 / 32 / 64 give 70.36 / 70.19 / 70.34. Neither alternative differs from |C| = 32 (+0.17 [−1.00, +1.29], +0.15 [−1.88, +2.21]), so τ does not need to be rescaled with |C|. |C| = 32 is the fastest of the three (1.56× vs 1.54× / 1.51×).

How to retune. We recommend τ = .01 as the default and τ = .001 for workloads dominated by exact multi-key retrieval. To retune, evaluate τ ∈ {.1, .01, .001} on a small development set and pick the largest τ whose loss is within the target. Each value costs one decode pass, with no retraining and no rebuilding of the cluster summaries.

Questions2

The evaluation covers only two similarly sized models, Llama-3.1-8B and Qwen2.5-7B. Could the authors include a moderately larger model, such as Qwen2.5-14B, to better assess generalization across model sizes? Reporting both quality and latency, together with any necessary threshold adjustments, would strengthen this evaluation.

Response: Thank you for this advice. We add experiments for Qwen2.5-14B.

We added Qwen2.5-14B-Instruct (48 layers, 40 query / 8 KV heads) on RULER-128K (13 tasks × 20 samples). We used the same thresholds as for the 7B/8B models with no retuning, and the same CUDA Graph timing protocol: 130,944 input / 128 output tokens, steady-state TPOT, with Full Attention and RefineKV timed in the same batch.

AccuracyΔ vs Full [95% CI]TPOTSpeedup
Full Attention72.96—40.98 ms1.00×
RefineKV τ = .0171.97−0.99 [−2.88, +1.04]29.56 ms1.39×
RefineKV τ = .169.19−3.78 [−6.72, −0.91]26.49 ms1.55×
SnapKV 25%68.44−4.52 [−7.50, −1.64]28.33 ms1.45×

Threshold adjustment. None was needed. At τ = .01 the loss is within the CI of Full, as on Qwen2.5-7B (−0.60). At τ = .1 the loss is similar to 7B (−3.78 vs −5.53).

Latency. The speedup is larger than on 7B (1.39× / 1.55× vs 1.19× / 1.27×). The 14B model has 8 KV heads instead of 4 and 48 layers instead of 28, so the KV cache is a larger share of the memory traffic per decode step, and that is the part RefineKV reduces.

Revision: We add this experiment in Appendix C.5.

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

RefineKV retains the full KV cache but adaptively accesses it through contiguous clusters. A cluster-wise score derived from a single-head attention-error bound determines whether to load original entries or use a size-corrected mean representative. The method includes a sparse Triton implementation, GQA aggregation, and optional prompt-query anchors. Results on two models and three benchmark suites suggest a useful quality–decode-latency trade-off.

Critical strengths
  1. The paper starts from output approximation error and separates cluster importance from within-cluster distortion. The detailed derivation and computable geometric bounds make the selection criterion more interpretable than an unexplained routing heuristic.

  2. The implementation description addresses practical GQA access, representative multiplicity, and GPU-resident selection without full-cache scoring or temporary gathers. The evaluation includes both eviction and query-adaptive baselines, as well as per-task results and anchor ablations.

Critical weaknesses
  1. Table 2 contradicts an exact limiting case of the method. When |C|=1, each representative is the original KV pair, the log-count correction is zero, and the logit deviation is zero. The mixed representation should therefore recover Full Attention regardless of whether a singleton is expanded. Nevertheless, accuracy drops from 73.35 to 28.74. Please explain the actual configuration behind this column and provide an attention-output equivalence check for singleton clusters and for all clusters expanded.

  2. Appendix B.2 captures the proposed full decoding step in a CUDA Graph, whereas C.2.3 specifies eager decoding for Full Attention and several baselines. LongBench quality is also paired with latency measured on separate standardized 128K prompts. Please compare methods with the same graph/eager policy and report quality and latency on the same prompt distribution. Include 128K/128-token prefill, summary, and anchor costs.

Questions for authors
  1. What speedup remains when Full Attention and the proposed method both use CUDA Graphs, and when both use eager execution?

  2. At the same measured KV access and with the same anchor mask, how do importance-only, distortion-only, and full-risk selection compare in attention-output error, quality, and TPOT? Can a bound for the selected mixed representation be reported after expansion, rather than interpreting τ as a global error tolerance?

  3. Can you provide the RULER paired per-example results, HELMET task counts, and confidence intervals for the full-versus-compressed differences? Which tasks require τ=0.001 to meet a stated quality-loss target, and what is the corresponding matched-protocol latency?

6 comments
AuthorsOpenReview ↗

Part1: weakness

Thank you for your thorough and insightful review! Here are our response:

Weakness 1:

Table 2 contradicts an exact limiting case of the method. When |C|=1, each representative is the original KV pair, the log-count correction is zero, and the logit deviation is zero. The mixed representation should therefore recover Full Attention regardless of whether a singleton is expanded. Nevertheless, accuracy drops from 73.35 to 28.74. Please explain the actual configuration behind this column and provide an attention-output equivalence check for singleton clusters and for all clusters expanded.

Response: Thank you for raising this question, we believe this is a misunderstanding.

Table 2 does not contain a |C| = 1 column. The 28.74 entry is the threshold τ = 1. The table groups three thresholds (τ = 0.001, 0.1, 1), two cluster sizes (|C| = 16, 64; default 32) and the GQA reduction. At τ = 1 almost no cluster is refined: the decode budget is about 3.37% of the KV cache and nearly all attention is served from representatives, which explains both the accuracy drop and the lowest TPOT in the table (14.38 ms).

The limiting cases hold by construction, and we verified them on real decode states (Llama-3.1-8B, first sample of each of the 13 RULER-128K tasks, all 32 layers and heads, against FP32 exact attention). With all clusters expanded, our production kernel’s max output error is 9.7e-3, no larger than that of the BF16 SDPA kernel used for Full Attention (9.7e-3). With |C| = 1, the representative of each cluster is bit-identical to its token (δ_C = 0, log|C| = 0), and the mixed output matches exact attention to 3.8e-6.

Revision: In the revision we extend this ablation into Table 3, where each column group is labeled explicitly (e.g. “Threshold τ = 1”, “Cluster size |C| = 16”), so the columns cannot be confused.

Weakness 2:

Appendix B.2 captures the proposed full decoding step in a CUDA Graph, whereas C.2.3 specifies eager decoding for Full Attention and several baselines. LongBench quality is also paired with latency measured on separate standardized 128K prompts. Please compare methods with the same graph/eager policy and report quality and latency on the same prompt distribution. Include 128K/128-token prefill, summary, and anchor costs.

Response: Thank you for pointing this out. We update full attention and baselines with CUDA graph version to ensure fair comparison. Prompt-query anchors are removed from all main experiments (Q=0Q = 0) and moved to the appendix.

CUDA Graph. In the submission, RefineKV was timed with CUDA Graph while Full Attention and the baselines were timed eagerly, which favored RefineKV. We have removed this inconsistency. Full Attention, RefineKV, all eviction baselines (SnapKV, PyramidKV, StreamingLLM) and Double-P are now timed with CUDA Graph.

Llama RULERLlama HELMETLlama LongBenchQwen RULERQwen HELMETQwen LongBench
Full AttentionQuality73.3769.1048.8665.8854.5749.34
RefineKV, τ=.01\tau = .01Quality70.1968.4348.8765.2854.4849.23
Speedup, both CUDA Graph1.56×1.43×1.55×1.19×1.13×1.18×
Speedup, both eager1.49×1.37×1.49×1.15×1.10×1.15×
RefineKV, τ=.1\tau = .1Quality62.5856.8048.9560.3552.8349.13
Speedup, both CUDA Graph1.67×1.56×1.67×1.27×1.23×1.27×
Speedup, both eager1.59×1.47×1.59×1.23×1.18×1.22×

Anchors are removed from all main experiments. All three benchmarks (RULER, HELMET, LongBench) on both models now use Q=0Q = 0, so every main result reflects the selection criterion alone. Results with anchors (Q=32Q = 32) are moved to the appendix as an optional add-on.

Revisions. We update main figure and all the result table in the paper, with fair comparison.

AuthorsOpenReview ↗

Part 2: Question 1 and 2

Questions 1:

What speedup remains when Full Attention and the proposed method both use CUDA Graphs, and when both use eager execution?

Response: We provide rebuttal for this in weakness2.

Questions2:

At the same measured KV access and with the same anchor mask, how do importance-only, distortion-only, and full-risk selection compare in attention-output error, quality, and TPOT? Can a bound for the selected mixed representation be reported after expansion, rather than interpreting τ as a global error tolerance?

Response: The matched-budget ablation shows that RCR_C outperforms importance-only selection by 11–21 points and a Quest-style bound by 3.7–3.9 points at the same budget. We explain the mixed representation and the role of tau.

Selection Rule Ablation. We keep the per-head token quota are fixed(same number of expanded clusters), and everything else fixed, only change the decode selection score. Experiment done on Llama-3.1-8B on RULER-128K, 260 samples per arm, no anchors, at the controlled same budgets. For box bound, it correspond to τ=.01\tau = .01 / .1.1.(≈9% / 3.6% of the KV cache per step).

We find: (1) The box bound is better than the ellipsoid bound. We therefore use the box bound in all main experiments. (2) At a matched per-head budget on RULER-128K, R_C outperforms importance-only selection (p^C\hat p_C or p^CVC\hat p_C V_C) by 11–21 points and a Quest-style bound by 3.7–3.9 points. Deviation alone is even worse (23–42 points lower), so neither mass nor deviation alone comes close, and the gain comes from combining them in R_C.

Scoreτ=0.01 Acc.Δτ=0.1 Acc.Δ
Ours (RCR_C)70.27—62.58—
RCR_C, ellipsoid68.90−1.3757.29−5.28
Quest-style66.38−3.8858.87−3.71
p^CVC\hat p_C V_C58.78−11.4941.38−21.19
p^C\hat p_C59.35−10.9242.87−19.71
δC\delta_C47.23−23.0420.68−41.90
RCR_C, exact δC\delta_C (oracle)72.00+1.7369.06+6.49
Full attention73.37+3.1073.37+10.79

From all-approximated to partially expanded clusters. RefineKV scores all clusters once, in the state where every cluster is approximated, and selects the clusters with RC>τR_C > \tau in a single pass. Because clusters are coupled through the softmax normalizer, expanding one cluster changes the contribution of all others, so the RCR_C of the remaining clusters are not the exact error terms of the mixed output. The model itself, however, can covers this case. Eq. 4 holds for any partition of the keys, and an expanded cluster of size 32 is simply 32 clusters of size 1 with δ=0\delta = 0. Substituting them into Eq. 4 gives a bound on the output RefineKV actually computes. Tracking the mixed state exactly means re-scoring after expansions, One-shot selection is a deliberate choice on this time trade-off; multi-round re-scoring is a direction we will discuss as future work.

The value of the bound. Same as analysis in W1.1, RefineKV uses the bound only to derive the form of RCR_C, i.e., how attention mass, deviation and value norm combine, and uses RCR_C only to rank clusters and expand those most likely to cause large error. A meaningful bound on the model’s output is hard to achieve. Eq. 4 bounds the attention output of one head in one layer, and that perturbation propagates through later layers, residual connections, normalizations and MLPs, whose scales differ across layers. No per-layer bound therefore translates into control of the output distribution, so we do not aim to derive one.

τ\tau as a quality–time threshold. Accordingly, τ\tau is not an error tolerance but a threshold that trades quality against time. In practice τ=.01\tau = .01 stays within the CI of Full Attention on 4 of 6 panels and transfers to Qwen2.5-14B without retuning.

Revision: We add this ablation in section 5.3, Table 2.

AuthorsOpenReview ↗

Part 3: Question 3

Questions3:

Can you provide the RULER paired per-example results, HELMET task counts, and confidence intervals for the full-versus-compressed differences? Which tasks require τ=0.001 to meet a stated quality-loss target, and what is the corresponding matched-protocol latency?

Response: We add experiments and analysis for these questions.

Task Counts. HELMET uses 16 non-citation tasks with 20 source samples each, which expand to 700 prediction records after the official placement variants. RULER uses 13 tasks × 20 = 260 samples; LongBench uses 3,750 samples.

Paired results and CIs. All full-versus-compressed differences are paired on identical samples, with 95% CIs from 2,000 task-stratified bootstrap resamples. HELMET uses 16 non-citation tasks with 20 source samples each, which expand to 700 prediction records after the official placement variants. RULER uses 13 tasks × 20 = 260 samples; LongBench uses 3,750 samples.

Panel (τ = .01)FullRefineKVΔ [95% CI]per-example W / T / LSpeedup
Llama RULER73.3770.19−3.17 [−5.44, −1.02]7 / 236 / 171.56×
Qwen RULER65.8865.28−0.60 [−2.23, +1.07]11 / 236 / 131.19×
Llama HELMET69.1068.43−0.67 [−2.16, +0.77]22 / 658 / 201.43×
Qwen HELMET54.5754.48−0.09 [−1.68, +1.52]26 / 647 / 271.13×
Llama LongBench48.8648.87+0.01 [−0.11, +0.13]348 / 3099 / 3031.55×
Qwen LongBench49.3449.23−0.11 [−0.23, −0.00]302 / 3128 / 3201.18×

Which tasks need τ = 0.001. With a target of at most 5 points lost per task (one sample in 20), τ = .01 meets the target on every Qwen task. On Llama, four tasks miss it, all multi-key needle retrieval with near-identical distractors. τ = 0.001 recovers all four:

TaskFullτ=.01τ=.001TPOT at τ=.001 (speedup)
RULER niah_multikey_270.055.070.019.83 ms (1.23×)
RULER niah_multikey_355.025.060.019.11 ms (1.28×)
HELMET icl_trec_fine35.025.035.019.52 ms (1.14×)
HELMET ruler_niah_mk_390.080.090.018.27 ms (1.17×)

At τ = 0.001, the overall scores match Full: RULER 73.63 (+0.27 [−0.49, +1.21]) at 1.28× and HELMET 69.49 (+0.39 [−0.14, +1.19]) at 1.18×. All timings use the same matched protocol: CUDA Graph for both methods, 128K input, steady-state TPOT, on the same GPU model.

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

The paper targets the cost of reading the full KV cache at every decoding step in long-context LLM inference. A motivating analysis on Llama-3.1-8B (WikiText-2) finds that each query needs only a small top-p subset of KV entries (17.6% at p=90%), while the union of these subsets across queries covers 96.4% of the cache, and that oracle query-adaptive top-k beats query-independent eviction in perplexity vs. KV access. The authors partition the prompt cache into contiguous 32-token clusters represented by mean keys/values, split the attention-output error into inter-cluster mass redistribution and intra-cluster value distortion, and upper-bound it using each cluster's approximate attention mass p_C, value-norm statistics, and a computable bound delta_C^bound on the within-cluster logit deviation (Eq. 4, App. A). Each cluster's term of this bound is used as a risk score R_C; RefineKV expands clusters with R_C > tau to exact tokens and represents the rest by their means, with GQA-any aggregation, prompt-query anchors on RULER/HELMET, and custom Triton kernels. Experiments on Llama-3.1-8B-Instruct and Qwen2.5-7B-Instruct at up to 128K context (LongBench, RULER, HELMET) compare against SnapKV, StreamingLLM, PyramidKV, Quest and a reimplemented Double-P using measured TPOT, reporting near-full quality at tau=0.01 with up to 1.76x lower TPOT, an attention-phase speedup of 11.22x (BF16) / 11.76x (FP8) in a latency breakdown, and ablations over tau, cluster size, GQA aggregation and the number of anchors.

Critical strengths
  1. The error analysis is clean and, as far as I can check, correct. I went through the decomposition (Eq. 3), the source-wise regrouping of the mass-redistribution term (Lemma A.1), the bounds m_C <= cosh(delta_C) (Lemma A.2) and sum_i |w_i - 1/n_C| <= 2 tanh(delta_C/2) (Lemma A.3), their combination (Eq. 35), and the two computable bounds on delta_C (App. A.7), and found no errors. The analysis makes explicit why a cluster's attention mass and its query-dependent internal dispersion should be considered jointly, and other mixed-resolution attention methods could reuse it.

  2. The method is practical and non-destructive, with real measured gains. Because the full cache is kept and non-expanded clusters still contribute through representatives, RefineKV avoids the failures of eviction on retrieval-heavy workloads (e.g., Qwen RULER-NIAH 74.4 at 1.2x vs. at most 51.2 for SnapKV/PyramidKV at 1.2-1.3x; Llama HELMET Rec./Rank. 76.3 vs. at most 74.4 at 1.4-1.5x; Table 1), while giving actual end-to-end TPOT reductions at 128K (1.73x BF16, 2.13x FP8 on Llama; Fig. 5). Per-task results are reported for every method (Tables 6-8), including unfavorable settings such as tau=0.1 on NIAH.

Critical weaknesses
  1. The bound does not deliver the error control claimed for it (Sec. 3.2-3.3, Eq. 4, Figs. 2-3, Table 2). Figs. 2 (left) and 3 show delta_C^bound of roughly 15-23. In that range tanh(delta/2) > 0.99999 and cosh(delta) > 1e6, so if most clusters are in this range, the right-hand side of Eq. 4 is about 2 V_max + 2 sum_C p_C V_C. That is larger than the trivial bound ||o - o_hat|| <= 2 V_max, since both outputs are convex combinations of vectors with norm at most V_max. Up to constants, the second term of R_C then reduces to p_C V_C (estimated attention mass times value norm), and the first term to V_max times a softmax over clusters of (log p_C + delta_C^bound), i.e., a relative share that shrinks whenever other clusters have larger p * exp(delta^bound). In addition, R_C splits a bound derived for the configuration where every cluster is approximated, and its normalizer includes clusters that are later expanded, so the derivation does not bound the error of the mixed output RefineKV actually computes. Consistent with this, tau behaves like an uncalibrated knob (Table 2: 73.5 / 70.9 / 61.1 / 28.7 accuracy for tau = 0.001 / 0.01 / 0.1 / 1). Since an error-driven criterion is what the paper says distinguishes it from Quest, Multipole Attention and Double-P (Sec. 6), statements such as "principled selection criterion" and "the KV access budget emerges naturally from error control" are not supported as written.

  2. The contribution of R_C itself is not isolated, and a separate heuristic carries much of the gain (Fig. 2 right, Tables 2, 3, 7, App. B.1). There is no ablation that keeps clustering, kernel and budget fixed while replacing R_C by an importance-only rule (threshold or top-p on p_C, as in the mixed-resolution methods the paper contrasts itself with), by p_C V_C, or by a Quest-style bound. The correlation in Fig. 2 (right) spans about six orders of magnitude, over which any score proportional to p_C would also correlate strongly, and the target ||o_C - o_hat_C|| is not precisely defined. Meanwhile, the RULER/HELMET results use prompt-query anchors, which are a query-independent, SnapKV-like selection from the last 32 prompt queries kept expanded for the whole decode, and these are turned off for LongBench. Without anchors, RefineKV gets 67.01 at 1.75x on Llama RULER-128K (Table 3), which is about the same as SnapKV-10% (about 66.8 at 1.7x) and PyramidKV-10% (about 66.6) computed from Table 7. With anchors, the margin over SnapKV-25% / PyramidKV-25% (about 69.8 / 70.3 at 1.5x) is roughly one point. The gains on Qwen are much larger, but on Llama I do not see evidence that the error-bound criterion, rather than the anchors, drives the improvement.

Questions for authors
  1. With clusters, kernel, anchors and decode budget fixed, how does R_C compare with (a) a threshold or top-p on p_C alone, (b) p_C V_C, (c) a Quest-style upper-bound score, and (d) R_C with the box bound instead of the ellipsoid bound, on RULER-128K and HELMET? Please also report Fig. 2 (right) for these alternatives, or the partial correlation of R_C with the error given p_C. A clear advantage for R_C would largely resolve Weaknesses 1-2 and is the result most likely to raise my rating.

  2. What is the distribution of delta_C^bound vs. the exact delta_C across layers and heads, and how does the bound, evaluated for the mixed configuration actually used, compare with the realized ||o - o_hat|| and with 2 V_max? How exactly is ||o_C - o_hat_C|| in Fig. 2 defined? If the bound is non-vacuous for a substantial fraction of heads, Weakness 1 becomes much weaker; otherwise the method should be presented as a bound-inspired heuristic.

  3. Are Full attention and every baseline timed with the same CUDA Graph / static cache protocol as RefineKV, and why is Quest slower than Full at a budget of at most 4K? Can you report quality vs. measured KV traffic (including representatives and metadata) for Quest, Double-P and RefineKV, or run their selection rules inside your kernel? This determines whether the Pareto-frontier claim against query-adaptive methods holds.

  4. Does the 11.22x / 11.76x attention speedup in Fig. 5 include the selection kernel, and which configuration (tau, anchors, prompt) is shown? "97.0% of the headroom" implies an accessed fraction near 9%, which matches Q=0 (9.03%, Table 3) rather than the default Q=32 (19.41%). Does "budget" count representatives and metadata? This decides whether the headline numbers in the abstract apply to the evaluated configurations.

7 comments
AuthorsOpenReview ↗

Rebuttal part I: Weakness 1.1

Thank you very much for your thorough and insightful review! Your feedback demonstrates a profound understanding of the field as well as an in-depth familiarity with our work, and we truly value your comments. Please find our responses below:

Weakness 1

W1.1: The bound does not deliver the error control claimed for it (Sec. 3.2-3.3, Eq. 4, Figs. 2-3, Table 2). Figs. 2 (left) and 3 show delta_C^bound of roughly 15-23. In that range tanh(delta/2) > 0.99999 and cosh(delta) > 1e6, so if most clusters are in this range, the right-hand side of Eq. 4 is about 2 V_max + 2 sum_C p_C V_C. That is larger than the trivial bound ||o - o_hat|| <= 2 V_max, since both outputs are convex combinations of vectors with norm at most V_max. ****Up to constants, the second term of R_C then reduces to p_C V_C (estimated attention mass times value norm), and the first term to V_max times a softmax over clusters of (log p_C + delta_C^bound), i.e., a relative share that shrinks whenever other clusters have larger p * exp(delta^bound).

Response summary: With the exact δ, Eq. 4 is well below the trivial bound 2 V_max. The loose bound comes from the cheap δ_C^bound estimate. In practice, R_C reduces to the reviewer’s simplified form, which still captures the joint effect of importance and deviation, and remain valid and meaningful.

Simplification of R_C with large delta. When δC\delta_C is large, cosh⁡(x)≈ex/2\cosh(x) \approx e^{x}/2 and tanh⁡(x)≈1\tanh(x) \approx 1, RCR_C can be simplified as:

2Vmax⁡ softmax⁡C (log⁡p^C+δC)+2p^CVC2V_{\max}\,\operatorname{softmax}_C  (\log \hat p_C+\delta_C)+2\hat p_C V_C

Setting. Llama-3.1-8B, RULER-128K, Q=0Q = 0, GQA-any, block size 32. We record every layer and query head of 26 prompts (2 per task), at τ=.01\tau = .01 and .1.1. “Same set as simplified“ is the fraction of KV heads for which the simplified score selects exactly the same clusters as RCR_C at the same τ\tau. ”Cluster Jaccard“ is ∣A∩B∣/∣A∪B∣|A \cap B| / |A \cup B| between the two selected cluster sets, averaged over KV heads. Eq. 4 >2Vmax⁡> 2V_{\max} is the fraction of heads for which Eq. 4 exceeds the trivial bound 2Vmax⁡2V_{\max}.

Results. With the oracle deviation, Eq. 4 is well below the trivial bound. In practice, with box or ellipsoid bound, the original RCR_C and the simplified score select the same clusters on 96–98% of KV heads.

δ_Cδ meanδ stdSame set as simplified (τ=.01 / .1)Cluster Jaccard (τ=.01 / .1)Eq. 4 > 2V_max (τ=.01 / .1)
Box21.925.3196.4% / 97.7%0.9999 / 0.999199.5% / 99.7%
Diag. ellipsoid23.487.5996.4% / 97.7%0.9998 / 0.998299.7% / 99.8%
Oracle4.171.792.2% / 38.4%0.918 / 0.9451.7% / 5.0%

Simplified R_C does not invalidate RefineKV. RefineKV never uses the value of the bound, and Eq. 4 only motivates the form of the per-cluster score RCR_C, and the method uses RCR_C only through the ranking it over clusters. The simplified form, keeps the intuition behind RefineKV: we want to jointly capture Importance p^C\hat p_C and Distortion δC\delta_C. Both signals enter jointly through softmaxC(log⁡p^C+δC)\mathrm{softmax}_C(\log \hat{p}_C + \delta_C), and a mass-weighted value term p^CVC\hat{p}_C V_C is added.

Oracle delta / simplified R_C selection ablation. we expand the exact same number of clusters as δCbound\delta_C^{bound}, but use oracle deltaCdelta_C / simplified RCR_C to select clusters. The comparison below fixes the per-head token budget (Llama-3.1-8B, RULER-128K, 260 samples, no anchors). Using the oracle delta gives the best selection in every setting, by up to +15.8 points over the ellipsoid and +9.8 over the box at the lower budget. The simplified form of R_C performs essentially the same as the original form, even with the oracle delta: every difference is within 0.5 points and all paired 95% CIs include zero.

RCR_CδC\delta_CQ=0, τ=.01Q=0, τ=.1
originalellipsoid67.0149.63
simplifiedellipsoid67.0848.83
originalbox70.5755.66
simplifiedbox70.5755.66
originaloracle71.3565.46
simplifiedoracle71.3565.90
Full Attention—73.3773.37

We keep the original form , for the following reasons:

  • It is the expression the derivation gives, and it holds for any δ. The simplified form is its large-δ limit. Using it means adding an approximation step and an assumption about the operating regime. For smaller cluster size, and situation where part of clusters are expanded, δ\delta can be smaller.
  • It costs nothing. The TPOT difference is below 0.3%, because selection is dominated by reading the summaries, not by evaluating cosh/tanh.

Revisions. We add the simplification analysis and ablation experiment result Appendix C.4. We mark better approximation for delta as an important future direction.

AuthorsOpenReview ↗

Rebuttal part 2: Weakness 1.2

W1.2: In addition, R_C splits a bound derived for the configuration where every cluster is approximated, and its normalizer includes clusters that are later expanded, so the derivation does not bound the error of the mixed output RefineKV actually computes. Consistent with this, tau behaves like an uncalibrated knob (Table 2: 73.5 / 70.9 / 61.1 / 28.7 accuracy for tau = 0.001 / 0.01 / 0.1 / 1). Since an error-driven criterion is what the paper says distinguishes it from Quest, Multipole Attention and Double-P (Sec. 6), statements such as "principled selection criterion" and "the KV access budget emerges naturally from error control" are not supported as written.

Response summary: Below we set out where the theory ends and where the algorithm’s approximations begin. This model extends naturally to partially expanded clusters, at a cost in time. RefineKV does not use the value of the bound, and a meaningful bound across layers is hard to achieve. τ\tau therefore controls the trade-off between quality and time. We have revised the inappropriate wording.

The bound naturally extends to partially expanded clusters. RefineKV scores all clusters once, in the state where every cluster is approximated, and selects the clusters with RC>τR_C > \tau in a single pass. Because clusters are coupled through the softmax normalizer, expanding one cluster changes the contribution of all others, so the RCR_C of the remaining clusters are not the exact error terms of the mixed output. The model itself, however, can covers this case. Eq. 4 holds for any partition of the keys, and an expanded cluster of size 32 is simply 32 clusters of size 1 with δ=0\delta = 0. Substituting them into Eq. 4 gives a bound on the output RefineKV actually computes. This is also why we keep the full form of RCR_C: For a single token cluster, it gives zero risk, while the simplified form cannot. Tracking the mixed state exactly means re-scoring after expansions, One-shot selection is a deliberate choice on this time trade-off; multi-round re-scoring is a direction we will discuss as future work.

The value of the bound. Same as analysis in W1.1, RefineKV uses the bound only to derive the form of RCR_C, i.e., how attention mass, deviation and value norm combine, and uses RCR_C only to rank clusters and expand those most likely to cause large error. A meaningful bound on the model’s output is hard to achieve. Eq. 4 bounds the attention output of one head in one layer, and that perturbation propagates through later layers, residual connections, normalizations and MLPs, whose scales differ across layers. No per-layer bound therefore translates into control of the output distribution, so we do not aim to derive one.

τ\tau as a quality–time threshold. Accordingly, τ\tau is not an error tolerance but a threshold that trades quality against time. In practice τ=.01\tau = .01 stays within the CI of Full Attention on 4 of 6 panels and transfers to Qwen2.5-14B without retuning.

Revisions. We agree that the two quoted phrases may suggest an error guarantee that the method does not provide. We modify the wording and add multi-step re-scoring as future work.

AuthorsOpenReview ↗

Part 3: Weakness 2.1, weakness 2.2

Weakness2:

W2.1: The contribution of R_C itself is not isolated, and a separate heuristic carries much of the gain (Fig. 2 right, Tables 2, 3, 7, App. B.1). There is no ablation that keeps clustering, kernel and budget fixed while replacing R_C by an importance-only rule (threshold or top-p on p_C, as in the mixed-resolution methods the paper contrasts itself with), by p_C V_C, or by a Quest-style bound.

Response summary: The matched-budget ablation shows that RCR_C outperforms importance-only selection by 16–20 points and a Quest-style bound by 3.6–4.9 points at the same budget.

Selection Rule Ablation. We keep the per-head token quota are fixed(same number of expanded clusters), and everything else fixed, only change the decode selection score. Experiment done on Llama-3.1-8B on RULER-128K, 260 samples per arm, no anchors, at the controlled same budgets. For box bound, it correspond to τ=.01\tau = .01 / .1.1.(≈9% / 3.6% of the KV cache per step).

We find: (1) The box bound is better than the ellipsoid bound. We therefore use the box bound in all main experiments. (2) At a matched per-head budget on RULER-128K, R_C outperforms importance-only selection (p^C\hat p_C or p^CVC\hat p_C V_C) by 11–21 points and a Quest-style bound by 3.7–3.9 points. Deviation alone is even worse (23–42 points lower), so neither mass nor deviation alone comes close, and the gain comes from combining them in R_C.

Scoreτ=0.01 Acc.Δτ=0.1 Acc.Δ
Ours (RCR_C)70.27—62.58—
RCR_C, ellipsoid68.90−1.3757.29−5.28
Quest-style66.38−3.8858.87−3.71
p^CVC\hat p_C V_C58.78−11.4941.38−21.19
p^C\hat p_C59.35−10.9242.87−19.71
δC\delta_C47.23−23.0420.68−41.90
RCR_C, exact δC\delta_C (oracle)72.00+1.7369.06+6.49
Full attention73.37+3.1073.37+10.79

Revision: We add this ablation in section 5.3, Table 2.

W2.2: The correlation in Fig. 2 (right) spans about six orders of magnitude, over which any score proportional to p_C would also correlate strongly, and the target ||o_C - o_hat_C|| is not precisely defined.

Response summary: Correlation alone cannot separate RCR_C from attention mass. The partial Spearman correlation given p^C\hat p_C reflects that RCR_C provide the additional information beyond attention mass. Oracle delta, shows the highest partial Spearman correlation.

Definition of the target. For a cluster CC and query qq, let

oC=1Z∑i∈Ceq⊤ki/d vi,o^C=p^C vˉC,p^C=∣C∣ eq⊤kˉC/d∑C′∣C′∣ eq⊤kˉC′/d,o_C = \frac{1}{Z}\sum_{i\in C} e^{q^\top k_i/\sqrt d}\, v_i, \qquad \hat o_C = \hat p_C\, \bar v_C, \qquad \hat p_C = \frac{|C|\, e^{q^\top \bar k_C/\sqrt d}}{\sum_{C'} |C'|\, e^{q^\top \bar k_{C'}/\sqrt d}},

where ZZ is the Full Attention softmax normalizer. oCo_C is CC’s contribution to the Full Attention output and o^C\hat o_C its contribution to the output in which every cluster is replaced by its representative, so ∑C(oC−o^C)\sum_C (o_C - \hat o_C) is exactly that approximation’s error and ∥oC−o^C∥\lVert o_C - \hat o_C\rVert is CC’s share of it.

Correlation analysis. We find that p^C\hat p_C alone reaches a Spearman correlation of .975 with the target, which confirms the reviewer’s point. We therefore also report the partial correlation given p^C\hat p_C, which measures what a score adds beyond attention mass. RCR_C does carry information beyond mass (partial ρ=.49\rho = .49), more than a Quest-style bound (.32), and oracle delta is (.81). The deviation term is therefore the ingredient that separates RCR_C from an importance score.

ScoreSpearman with ∥oC−o^C∥\lVert o_C - \hat o_C \rVertPartial Spearman given p^C\hat p_C
p^C\hat p_C.975—
p^C⋅VC\hat p_C \cdot V_C.975.06
Quest-style UCU_C.864.32
RCR_C (box δC\delta_C).975.49
RCR_C (exact δC\delta_C, oracle).990.81

Revision: We make definition more clear in paper, and provide partial correlation analysis in Appendix B.3.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of update made

Q1: Lack matched-budget selection score comparison. (All reviewers)

A1: We keep the per-head token quota are fixed(same number of expanded clusters), and everything else fixed, only change the decode selection score. R_C outperforms importance-only selection (p^C\hat p_C or p^CVC\hat p_C V_C) by 11–21 points and a Quest-style bound by 3.7–3.9 points. We add ablation Result in Table 2.

Q2: Unfair latency comparisons across CUDA Graph and eager execution. (All reviewers)

A2: Full Attention, RefineKV, all baselines (SnapKV, PyramidKV, StreamingLLM) and Double-P are now timed with CUDA Graph, under fully aligned settings. We update main Table, main result Figure(Fig 4) and Speedup Figure(Fig 5). We add eager to eager comparison in Appendix C.6 as well.

Q3: Are the gains driven by prompt-query anchors rather than by the selection score R_C?(Reviewer 7nbs, W2) A3: Anchors are removed from all main experiments. All three benchmarks (RULER, HELMET, LongBench) on both models now use Q=0Q = 0, so every main result reflects the selection criterion alone. Results with anchors (Q=32Q = 32) are moved to the appendix as an optional add-on. The gains remain significant without anchors. Selection score ablation(QA1) is also done on No-anchors(Q=0Q = 0).

Q4: Flawed correlation analysis in Fig 2 right. Correlation might be dominated by attention mass.(Reviewer 7nbs, Q2; Reviewer gxtp W1)

A4: We find that p^C\hat p_C alone reaches a Spearman correlation of .975 with the target, which confirms the reviewer’s point. We therefore also report the partial correlation given p^C\hat p_C, which measures what a score adds beyond attention mass. RCR_C does carry information beyond mass (partial ρ=.49\rho = .49), more than a Quest-style bound (.32), and oracle delta is (.81). We provide partial correlation analysis in Appendix B.3.

Q5: Estimation of δ is large. Approximated form of R_C under large δ go beyond trivial bound 2V_max. Can R_C be simplified? Does this simplification invalidate RefineKV? (Reviewer 7nbs, W1)

A5: With the exact δ\delta, Eq. 4 is well below the trivial bound 2 V_max. The loose bound comes from the cheap δCbound\delta_C^{bound} estimate. In practice, R_C reduces to the reviewer’s simplified form, which still captures the joint effect of importance and deviation, and remain valid and meaningful. The simplified form, keeps the intuition behind RefineKV: we want to jointly capture Importance p^C\hat p_C and Distortion δC\delta_C. Both signals enter jointly through softmaxC(log⁡p^C+δC)\mathrm{softmax}_C(\log \hat{p}_C + \delta_C), and a mass-weighted value term p^CVC\hat{p}_C V_C is added. We add the simplification analysis and ablation experiment result Appendix C.4. We mark better approximation for delta as an important future direction.

Q6: What’s the role of τ\tau? How is τ\tau selected? Does tau generalize across cluster size and (Reviewer 7nbs, W1; Reviewer getp, Q1) A6: τ\tau as a quality–time threshold. RefineKV uses the bound to derive the form of RCR_C, i.e., how attention mass, deviation and value norm combine, and uses RCR_C only to rank clusters and expand those most likely to cause large error. Accordingly, τ\tau is not an error tolerance but a threshold that trades quality against time. We did not tune it per model or benchmark: we use a fixed log-spaced grid, τ ∈ {0.1, 0.01}, plus τ = 0.001 added in the rebuttal. The same values were used for every model, benchmark and cluster size below.

Q7: Does RefineKV work for larger models? Does τ\tau generalized to larger model?(Reviewer gxtp, Q2)

A7: Yes. We add experiment for Qwen-2.5 14B. None threshold adjustment was needed. At τ = .01 the loss is within the CI of Full, as on Qwen2.5-7B (−0.60). At τ = .1 the loss is similar to 7B (−3.78 vs −5.53). The speedup is larger than on 7B (1.39× / 1.55× vs 1.19× / 1.27×). We add this experiment in Appendix C.5.

Q8: Task counts. Confident interval of results. (Reviewer 1Fvn, Q3)

A8: We add task count on Appnedix C.2.2. We add CI analysis on Appendix C.8.

Q9: Does acceleration in Fig 5 include selection? (Reviewer 7nbs,Q4)

A9: We update Fig 5. Now it depicts the speedup with selection kernel included, and measured under Q=0.

Q10: Lack ablation for different context length.(Reviewer gxtp, followup; Reviewer 1Fvn, followup)

A10: We add this ablation. At a fixed τ, the expanded fraction falls steadily with length: This is because τ bounds the per-step attention-output error rather than fixing a budget. In RULER, most of the context is distractor text , and longer inputs mainly add more of it. Such tokens receive little attention and are well approximated by their cluster summaries, so the number of expanded entries need not grow linearly with length. This is consistent with what we observe. Since RefineKV’s TPOT stays nearly flat while full attention’s grows with the cache, the speedup increases with length. We add context length ablation study in Appendix C.7.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.