- 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
-
The benefit of the proposed risk score is not sufficiently established. The paper lacks comparisons against simpler alternatives, such as 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.
-
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
-
How is the refinement threshold 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?
-
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.
-
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
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 RULER | Llama HELMET | Llama LongBench | Qwen RULER | Qwen HELMET | Qwen LongBench | ||
|---|---|---|---|---|---|---|---|
| Full Attention | Quality | 73.37 | 69.10 | 48.86 | 65.88 | 54.57 | 49.34 |
| RefineKV, | Quality | 70.19 | 68.43 | 48.87 | 65.28 | 54.48 | 49.23 |
| Speedup, both CUDA Graph | 1.56× | 1.43× | 1.55× | 1.19× | 1.13× | 1.18× | |
| Speedup, both eager | 1.49× | 1.37× | 1.49× | 1.15× | 1.10× | 1.15× | |
| RefineKV, | Quality | 62.58 | 56.80 | 48.95 | 60.35 | 52.83 | 49.13 |
| Speedup, both CUDA Graph | 1.67× | 1.56× | 1.67× | 1.27× | 1.23× | 1.27× | |
| Speedup, both eager | 1.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 , so every main result reflects the selection criterion alone. Results with anchors () 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.
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:
as a quality–time threshold. RefineKV uses the bound only to derive the form of , i.e., how attention mass, deviation and value norm combine, and uses only to rank clusters and expand those most likely to cause large error. Accordingly, 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] | TPOT | Speedup | |
|---|---|---|---|---|
| Full Attention | 72.96 | — | 40.98 ms | 1.00× |
| RefineKV τ = .01 | 71.97 | −0.99 [−2.88, +1.04] | 29.56 ms | 1.39× |
| RefineKV τ = .1 | 69.19 | −3.78 [−6.72, −0.91] | 26.49 ms | 1.55× |
| SnapKV 25% | 68.44 | −4.52 [−7.50, −1.64] | 28.33 ms | 1.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.
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 RC 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 RC from attention mass. The partial Spearman correlation given p^C reflects that RC 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 / .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 or p^CVC) 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.
Definition of the correlation target. For a cluster C and query q, let
oC=Z1∑i∈Ceq⊤ki/dvi,o^C=p^CvˉC,p^C=∑C′∣C′∣eq⊤kˉC′/d∣C∣eq⊤kˉC/d,
where Z is the Full Attention softmax normalizer. oC is C’s contribution to the Full Attention output and o^C its contribution to the output in which every cluster is replaced by its representative, so ∑C(oC−o^C) is exactly that approximation’s error and ∥oC−o^C∥ is C’s share of it.
Correlation analysis. We find that 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, which measures what a score adds beyond attention mass. RC does carry information beyond mass (partial ρ=.49), more than a Quest-style bound (.32), and oracle delta is (.81). The deviation term is therefore the ingredient that separates RC from an importance score.
Revision: We add ablation study in Section 5.3, Table 2. And we add partial correlation analysis in Appendix B.3.