- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper introduces KVgrad, a query-agnostic KV-cache eviction method that scores cached values by their estimated global influence on the model’s final hidden representation rather than only their local attention contribution. Using a first-order Taylor approximation and the chain rule, KVgrad combines a local value contribution with downstream gradient sensitivity, and further stabilizes the score through magnitude-aware scoring and probe-specific max aggregation. The authors also distill the expensive gradient-based scores into lightweight per-layer MLPs for low-overhead, on-the-fly eviction. Experiments on RULER and LongBench across four language models show an average near-lossless compression ratio of 5.9×, improving over query-agnostic baselines such as KVzip+, while the MLP variant retains much of the benefit at negligible scoring cost. Runtime measurements report up to 5.6× lower attention latency and 1.7× faster end-to-end generation at 8× compression. Ablations validate the proposed scoring components, and preliminary experiments on image and video vision-language benchmarks suggest transferability to multimodal KV-cache compression.
Critical strengths
KVgrad addresses a meaningful limitation of existing KV eviction methods by estimating each cache entry’s downstream effect on the final model representation, rather than relying only on local attention statistics. The Taylor and chain-rule formulation gives the method a clear motivation, and the magnitude-aware and probe-specific components make the proposed score more robust in practice.
The paper provides strong empirical and practical validation. Across four language models and two long-context benchmarks, KVgrad achieves a higher near-lossless compression ratio than KVzip+, while the distilled MLP surrogate substantially reduces scoring overhead. Runtime measurements and preliminary vision-language experiments further show that the approach can improve inference efficiency and extend beyond text-only models.
Critical weaknesses
Exact KVgrad is substantially more expensive than the methods it seeks to replace. At a 256K context, its scoring phase takes about 872 s and requires higher peak memory than prefill, because it combines repeat-probe computation with a backward pass. The lightweight MLP surrogate reduces this overhead but loses part of the exact method’s performance, so the claimed inference benefits depend heavily on contexts being reused enough times to amortize scoring.
The global score is derived from a first-order gradient approximation to a reconstruction-style probe objective and a chosen final hidden-state target, rather than from the actual downstream user task. The strong aggregate results are encouraging, but the reported near-lossless compression ratio is a geometric mean over selected RULER and LongBench settings, with noticeable task- and model-level variation. Evidence for robustness to different prompts, generation objectives, model architectures, and genuinely query-specific workloads remains limited, making the broad generality claims less fully supported.
Questions for authors
-
What is the break-even reuse count at which exact KVgrad’s scoring cost is recovered by faster decoding? Please report end-to-end latency and throughput for different numbers of queries sharing the same compressed context, batch sizes, and context lengths.
-
How sensitive are KVgrad scores to the repeat-reconstruction probe design, including probe length, chunk size, instruction wording, and the number of probes? Do the same scores remain effective when the future workload differs substantially from context reconstruction?
-
Can the authors quantify how well the first-order gradient approximation predicts actual output changes after evicting a KV entry? Comparisons with finite-difference perturbations or stronger attribution methods would clarify whether the proposed score is measuring causal importance or only a local proxy.
-
The 5.9× near-lossless compression ratio is a geometric mean over models and benchmarks. Could the authors report confidence intervals and per-task results at the () threshold, including the frequency and severity of failures hidden by the aggregate metric?
-
For KVgrad, how much training data, compute, and additional memory are required, and how does the surrogate generalize to unseen context lengths, domains, models, and modalities? Since the MLP is the practical deployment variant, these details materially affect the generality of the claims.
5 comments
Q3: Can the authors quantify how well the first-order gradient approximation predicts actual output changes after evicting a KV entry? Comparisons with finite-difference perturbations or stronger attribution methods would clarify whether the proposed score is measuring causal importance or only a local proxy.
Stronger attribution methods. While stronger attribution methods such as Integrated Gradients [2] and SmoothGrad [3] could be considered, they require multiple forward and backward passes, rendering them computationally infeasible for KV cache eviction. If the reviewer has specific single-pass attribution methods in mind, we would be very happy to explore them.
Direct deletion test correlates best with KVgrad. We deleted each KV entry individually, with attention renormalized as in real eviction, and ranked the entries by the resulting output change (larger change, higher rank). We then compare this ranking with the ranking given by each importance score (KVzip, KVzip+, KVgrad), using Spearman rank correlation. The results show that KVgrad achieves the highest correlation with the actual deletion test.
| Deletion ranking by | KVzip | KVzip+ | KVgrad |
|---|---|---|---|
| Repeat () | 0.80 | 0.76 | 0.81 |
| Repeat (KL) | 0.78 | 0.76 | 0.84 |
| Answer (KL) | 0.32 | 0.37 | 0.45 |
Setup
- Model: Qwen3-0.6B
- Dataset: RULER 4K, 39 requests (13 tasks 3)
- KV entries: 300 KVs per request
- 150 uniformly at random
- 150 from the union of the top 1% entries of KVzip, KVzip+, and KVgrad.
- Output change (full KV vs. one entry deleted):
- Repeat (): Absolute changes in the last hidden upon single-entry deletion, averaged over reconstruction tokens.
- Repeat (KL): KL divergence of the LM head output distribution between full KV and single-entry-deleted KV. Averaged over reconstruction tokens.
- Answer (KL): Same as above, averaged over answer tokens.
W2-2: The strong aggregate results are encouraging, but the reported near-lossless compression ratio is a geometric mean over selected RULER and LongBench settings, with noticeable task- and model-level variation.
Q4: The 5.9× near-lossless compression ratio is a geometric mean over models and benchmarks. Could the authors report confidence intervals and per-task results at the 2% threshold, including the frequency and severity of failures hidden by the aggregate metric?
To complement the geometric-mean NL-CR, we report both bootstrap confidence intervals and a single-setting tolerance analysis across 113 model-task pairs. We will include these results into our revised manuscript, including the abstract.
Bootstrap 95% confidence intervals. KVgrad shows non-overlapping bounds at and distinct separation at , highlighting that KVgrad's performance gains are statistically significant.
| τ=2 | τ=5 | |
|---|---|---|
| KVzip+ | 4.73 [4.06, 5.54] | 6.46 [5.72, 7.40] |
| KVgrad | 5.92 [4.99, 7.06] | 8.69 [7.59, 10.02] |
Single-setting tolerance. We measure the percentage of the model-task pairs that remain within tolerance ( / ) at fixed compression ratios (2:1, 4:1, and 8:1). KVgrad keeps the most tasks within tolerance (), and the gap widens with compression.
| Ratio | KVzip | KVzip+ | KVgrad | KVgrad (MLP) |
|---|---|---|---|---|
| 2:1 | 89% / 97% | 89% / 97% | 90% / 98% | 84% / 94% |
| 4:1 | 67% / 84% | 72% / 88% | 74% / 96% | 69% / 89% |
| 8:1 | 28% / 45% | 35% / 54% | 50% / 65% | 46% / 55% |
Worst-case analysis. No method keeps every task within 2% or 5% at any ratio above 1:1; at 5%, KVgrad misses only LongBench TREC and SAMSum at 2:1.
Setup
- Task: 113 model-task pairs (4 models$\times$ (13 RULER + 16 LongBench) = 116 model-task pairs, excluding 3 low-baseline tasks)
- Confidence interval (bootstrap): We generated 10,000 replicates by resampling model-task pairs with replacement. We recomputed the headline NL-CR for each replicate and reported the 2.5th and 97.5th percentiles.
W2-3: Evidence for robustness to different prompts, generation objectives, model architectures, and genuinely query-specific workloads remains limited, making the broad generality claims less fully supported.
We believe that our experiments already cover these aspects. We would be glad to run additional experiments if you have any particular datasets in mind.
- Different prompts: Please refer to responses for Q2.
- Generation objective: We evaluated KVgrad across diverse generation objectives using LongBench (single-/multi-document QA, long-form summarization, few-shot learning, code completion).
- Model architecture: We evaluated KVgrad on a diverse set of models, including Qwen3 (0.6B/4B/8B), Llama-3.1-8B, Ministral-3-14B, and Qwen3-VL (2/4/8B).
- Query-specific workloads: We evaluated KVgrad on the RULER retrieval tasks (multi-key/multi-value/multi-query NIAH), where only the needle matching the query answers it among same-format distractors.
Q2: Sensitivity to probe design and workload mismatch
Q2: How sensitive are KVgrad scores to the repeat-reconstruction probe design, including probe length, chunk size, instruction wording, and the number of probes? Do the same scores remain effective when the future workload differs substantially from context reconstruction?
- Chunk size: Appendix A.4.3 reports an ablation with varying chunk sizes of 256, 512, and 1024. Accuracy varies by at most 1.3 points across all compression ratios.
- Probe length / Number of probes: The probe reconstructs the full context, so its length is set by the context. Our results span contexts from 4K to 240K tokens (RULER-4K/16K, LongBench, LongBench-v2). The number of probe chunks is set by the chunk size, covered above.
- Future workload mismatch: Our evaluation is exactly this mismatch setting. The scores come from reconstruction, while the downstream tasks in RULER and LongBench differ from it. LongBench includes summarization, code completion, and multi-document QA, which differ from copying the context. LongBench-v2 adds a larger gap: multi-step CoT reasoning (median ~500 generated tokens) over contexts longer than 128K.
(LongBench-v2 [4], questions longer than 128K tokens, ~500 tokens of 0-shot CoT , Ministral-3-14B [5], Compression ratio 4:1)
| Method | Acc. |
|---|---|
| Full KV | 44.5 |
| KVgrad | 45.0 |
| KVgrad-MLP | 46.5 |
- Instruction wording: We evaluated five alternative probe instructions on 10% of RULER-4K with Qwen3-4B. As shown in the table, the average accuracy over the paraphrases stays close to that of the default instruction for both KVzip+ and KVgrad, indicating that neither method is sensitive to the instruction wording.
| Method | Instruction | 8:1 | 16:1 | 32:1 |
|---|---|---|---|---|
| KVzip+ | Default | 88.11 | 63.16 | 20.45 |
| KVzip+ | Paraphrases (avg.) | 88.58 ± 0.26 | 64.26 ± 0.79 | 20.92 ± 0.46 |
| KVgrad | Default | 90.49 | 78.63 | 53.95 |
| KVgrad | Paraphrases (avg.) | 90.37 ± 0.20 | 77.89 ± 0.56 | 52.29 ± 1.09 |
Five phrases: "Copy the text above word for word.", "Please reproduce the preceding passage verbatim.", "Output the context you were given, without any changes.", "Rewrite the context above exactly as it was written.", and "What was the previous context? Answer by repeating it verbatim."
Q5: Surrogate training cost and generalization
Q5: For KVgrad, how much training data, compute, and additional memory are required, and how does the surrogate generalize to unseen context lengths, domains, models, and modalities?
For KVgrad MLP surrogates, we followed the training recipe in [6], which is detailed in Appendix A.2. We summarize the question as follows:
- Training data: 2,322 prompt (0.75K-1.25K tokens) from Nemotron-Pretraining-Dataset-sample, sampling 500 positions per prompt.
- Compute: 50 minutes on a single A100 GPU
- Additional memory: 67M parameters for Qwen3-8B, increasing peak inference memory by only ~0.5GB
- Generalization: The MLP models trained under 1.25K tokens are utilized to evaluate longer contexts (RULER and LongBench) with different domains (Figure 5).
- Model and Modality generalization: Because representation spaces differ, a separate surrogate should be trained per model.
[1] Kim et al. KVzip: Query-Agnostic KV Cache Compression with Context Reconstruction. NeurIPS 2025.
[2] Sundararajan et al. Axiomatic Attribution for Deep Networks. ICML 2017.
[3] Smilkov et al. SmoothGrad: Removing Noise by Adding Noise. arXiv 2017.
[4] Bai et al. LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks. ACL 2025.
[5] Rastogi et al. Ministral 3. arXiv 2026.
[6] Jégou and Jeblick. KVzap: Fast, Adaptive, and Faithful KV Cache Pruning. arXiv 2026.
We thank the reviewer for the thoughtful and constructive feedback. In addition to the responses below, the common response includes new results on (1) a vLLM integration of KVgrad and (2) video understanding, which we kindly encourage the reviewer to read.
W1: Break-even reuse count and throughput measurement
In the results below, we extend the break-even analysis of Appendix A.3 to more batch sizes and context lengths and add a throughput analysis, comparing Full KV with exact KVgrad (8:1) on Llama-3.1-8B (RTX PRO 6000, 8K-token outputs).
Break-even reuse count. Consider one context shared by N queries. The context is prefilled P and scored S once, and the queries are then decoded from the compressed cache in batches of B, where each decode step takes d(B) and yields one token per query. With G output tokens per query, the time per query is
and KVgrad is faster once N>N∗=B⋅S/(G⋅(dFull(B)−dKVgrad(B))).
Throughput by number of queries. Gain = KVgrad throughput / Full KV throughput (= Full KV time / KVgrad time per query); many queries = dFull(B)/dKVgrad(B).
W2: Proxy and approximation justification, and robustness of NL-CR