acceptodds
Under review as a conference paper at ICLR 2027

KVgrad: Query-Agnostic KV Cache Eviction via Gradient-based Global Importance Scoring

13 views

Abstract

Key-Value (KV) cache eviction mitigates the memory overhead of Large Language Models (LLMs) by discarding cached KV pairs that are less relevant to future token generation. However, existing eviction methods typically rely on local heuristics, scoring cached entries by their immediate contribution to the attention output of the same layer, while overlooking their downstream impact across subsequent layers. To address this, we propose KVgrad, a query-agnostic eviction method that scores each cache entry by its global impact on the model's final outputs. Based on a simple analysis using a first-order Taylor approximation and the chain rule, KVgrad factorizes the impact of cached value into a linear local component and a gradient-based downstream sensitivity term. Then, we apply a magnitude-aware scoring scheme to stabilize the importance score. Evaluations on RULER and LongBench demonstrate that KVgrad achieves an average maximum compression ratio of 5.9x with negligible performance loss (<2%), significantly outperforming strong local-only state-of-the-art baselines. Furthermore, we demonstrate that our signal is highly amenable to distillation; by training a lightweight MLP to predict KVgrad scores from local hidden-state features, we enable high-fidelity, on-the-fly compression at negligible computational cost. Finally, we demonstrate the transferability of KVgrad to vision-language models; evaluations on image and long-context video benchmarks suggest a unified path for importance-aware KV cache compression.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large language models, Inference Efficiency, KV cache compression

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_c8EhOpenReview ↗
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
  1. 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.

  2. 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?

  3. 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.

  4. 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%\tau=2\%) threshold, including the frequency and severity of failures hidden by the aggregate metric?

  5. 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

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

W1: 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.

Q1: 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.

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

  • Full KV: P/N+G⋅dFull(B)/BP / N + G · d_{Full}(B) / B
  • KVgrad: (P+S)/N+G⋅dKVgrad(B)/B(P + S) / N + G · d_{KVgrad}(B) / B

and KVgrad is faster once N>N∗=B⋅S/(G⋅(dFull(B)−dKVgrad(B)))N > N* = B · S / (G · (d_{Full}(B) − d_{KVgrad}(B))).

ContextBatchP(s)P (s)S(s)S (s)dFull/dKVgradd_{Full} / d_{KVgrad} (ms/step)N*
128K12822725.4 / 16.93.3
42822745.4 / 21.54.6
256K110387837.7 / 18.75.7
410387876.3 / 25.78.5

Throughput by number of queries. Gain = KVgrad throughput / Full KV throughput (= Full KV time / KVgrad time per query); many queries = dFull(B)/dKVgrad(B)d_{Full}(B) / d_{KVgrad}(B).

ContextBatchN = 1N = 4N = 8N = 16N → ∞
128K10.60×1.06×1.24×1.36×1.50×
40.40×0.93×1.27×1.58×2.11×
256K10.36×0.84×1.16×1.47×2.01×
40.25×0.61×0.96×1.43×2.96×

W2: Proxy and approximation justification, and robustness of NL-CR

W2-1: 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.

  • We agree that our scoring relies on proxy reconstruction and gradient approximation, as both are structurally unavoidable in query-agnostic eviction.
    • Justification of reconstruction. In query-agnostic eviction, the downstream query is unknown at compression time, so some proxy objective (e.g., reconstruction and summarization) is required, and we adopt the reconstruction technique from KVzip [1]. KVzip further analyzes in Fig. 6 (KVzip paper) that important KV pairs across diverse subtasks (e.g., QA, summarization, and reasoning) are well-captured by those identified through reconstruction.
    • Necessity of approximation. KV eviction removes entries jointly, so finding the optimal subset is an intractable combinatorial problem (50% eviction from 100 tokens (=28,800 KVs) admits ≈108666\approx 10^{8666} subsets), making approximation unavoidable. Although single-entry deletion tests are themselves an approximation to joint removal, we performed them to directly address the reviewer's concern in R3-Q3.

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 byKVzipKVzip+KVgrad
Repeat (∣ΔΦ∣\lvert\Delta\Phi\rvert)0.800.760.81
Repeat (KL)0.780.760.84
Answer (KL)0.320.370.45

Setup

  • Model: Qwen3-0.6B
  • Dataset: RULER 4K, 39 requests (13 tasks ×\times 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 (∣ΔΦ∣|\Delta \Phi|): 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 τ=5%\tau = 5\% and distinct separation at τ=2%\tau = 2\%, highlighting that KVgrad's performance gains are statistically significant.

τ=2τ=5
KVzip+4.73 [4.06, 5.54]6.46 [5.72, 7.40]
KVgrad5.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 (τ=2%\tau=2\% / τ=5%\tau=5\%) at fixed compression ratios (2:1, 4:1, and 8:1). KVgrad keeps the most tasks within tolerance (τ=2/τ=5\tau=2/\tau=5), and the gap widens with compression.

RatioKVzipKVzip+KVgradKVgrad (MLP)
2:189% / 97%89% / 97%90% / 98%84% / 94%
4:167% / 84%72% / 88%74% / 96%69% / 89%
8:128% / 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)

MethodAcc.
Full KV44.5
KVgrad45.0
KVgrad-MLP46.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.
MethodInstruction8:116:132:1
KVzip+Default88.1163.1620.45
KVzip+Paraphrases (avg.)88.58 ± 0.2664.26 ± 0.7920.92 ± 0.46
KVgradDefault90.4978.6353.95
KVgradParaphrases (avg.)90.37 ± 0.2077.89 ± 0.5652.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.

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

KVgrad scores cached key-value entries using repeat-reconstruction probes. It multiplies attention-weighted projected value magnitude by the norm of a downstream gradient and takes the maximum over probe positions. The gradient target is the summed squared norm of the final pre-normalization hidden states. A per-layer MLP can distill this expensive score for request-time compression. Experiments cover four language models, RULER, LongBench, and preliminary image/video applications.

Critical strengths
  1. The downstream sensitivity factor is a meaningful extension of existing local scoring rules. Section 3.2 clearly distinguishes the exact chain-rule factorization from the subsequent heuristic relaxations; Table 2 and Appendix A.4 test the magnitude and probe-aggregation choices rather than presenting the final rule without analysis.
  2. The empirical comparison is broad across models and tasks, with per-task results in Appendix A.6. The matched training recipe for KVgrad and KVzip+ MLPs is particularly useful because it isolates the supervision target from the distillation architecture and training data.
  3. The cost discussion distinguishes exact offline scoring from MLP deployment, reports peak as well as persistent memory, and includes a multi-query amortization calculation (Figure 3 and Appendix A.3). The paper also tests surrogate transfer to longer contexts and held-out domains in Appendix A.2.3.
Critical weaknesses
  1. The evidence does not fully isolate the proposed probe-dependent downstream sensitivity from changes in layer/head budget allocation. Relative to KVzip+, Eq. 8 replaces the residual-norm factor as well as adding gradient information, and pruning pools entries across layers and heads (pp. 4-7). Table 2 tests MAS and PSP, but does not include a control that preserves each layer/head's gradient-norm distribution while shuffling it across probes, with the same global allocation rule. Since Appendix A.4.1 explicitly observes changed first-layer retention, such a control matters for the interpretation that global sensitivity, rather than mainly a better allocation scale, drives the gains.
  2. The practical accuracy-latency frontier is less established than the separate quality and cost results. The 256K-context/8K-generation speedups use the MLP variant (p. 8), while the main accuracy results use much shorter contexts; Appendix A.2.3 extends to 64K but does not validate this 256K operating point. Moreover, the MLP can lose substantial task-specific quality: for Qwen3-4B on LCC at 4:1, Table 24 reports 47.6 versus 60.8 for Full KV and 64.4 for exact KVgrad. This is acknowledged qualitatively, but is important when interpreting the surrogate as retaining most of the exact method's benefit. A representative quality-matched wall-clock comparison would make the deployment claim stronger.
  3. The headline near-lossless compression ratio is a summary of each subtask's largest passing ratio, rather than a single ratio that preserves every task (Table 1 and footnote 1). Its numerical precision is sensitive to the relative threshold, coarse ratio grid, and low-baseline tasks; for example, Qwen3-0.6B has a 0.4 Full-KV score on RULER CWE (Table 11). Appendix A.6 helpfully gives per-task results at both 2% and 5% tolerance. Aggregating both thresholds and reporting sampling uncertainty would clarify how robust the headline 5.9x versus 4.7x advantage is.
Questions for authors
  1. With the same global allocation rule, what happens if the gradient norms are shuffled across probes within each layer/head, preserving their distribution? This would help distinguish probe-specific downstream information from a change in allocation scale.
  2. Can you pair the reported long-context latency operating point with task accuracy, and report total wall-clock time with the sparse-prefill contribution quantified? Please also clarify the model's context-extension settings at 256K.
  3. Can the aggregate NL-CR be reported for the existing 2% and 5% per-task results, with uncertainty or low-baseline tasks reported separately?
3 comments

We are grateful to the reviewer for the careful review and for raising important points. Along with responses below, we also would like to kindly invite the reviewer to see the common response for the new (1) vLLM integration and (2) video results

W1 & Q1: Shuffled-gradient control for allocation vs. probe-specific ranking

W1: The evidence does not fully isolate the proposed probe-dependent downstream sensitivity from changes in layer/head budget allocation. [...]

Q1: With the same global allocation rule, what happens if the gradient norms are shuffled across probes within each layer/head, preserving their distribution? This would help distinguish probe-specific downstream information from a change in allocation scale.

Prerequisite for effective global scoring. The coupling of probe-dependent downstream sensitivity and budget allocation is not only intentional by design, but also a prerequisite for effective global scoring. This sets apart KVgrad from KVzip, which relies on local attention weights normalized within each head, inherently preventing global ranking from being meaningful across layers and heads.

Downstream sensitivity governs intra-head selection. To directly investigate the reviewer's concern, we randomly permuted the downstream sensitivity values across probe positions within each layer while keeping the A∣vWo∣A|\mathbf{v}\mathbf{W_o}| term fixed. We interpreted "with the same global allocation rule" in two ways: (1) re-applying the global top-k rule to the permuted scores, and (2) retaining the exact per-head budgets of the original KVgrad and using the permuted scores only to rank KVs within each head, which is what we believe the reviewer intended.

*(Qwen3-4B, RULER-4K, 650 samples (10% subset), chunk 256, 3 seeds).

Method8:116:132:1
KVzip+88.1163.1620.45
KVgrad90.4978.6353.95
Permuted (1)88.93 ± 0.3363.91 ± 1.2028.21 ± 0.11
Permuted (2)90.07 ± 0.0674.40 ± 1.0834.00 ± 0.81

Both Permuted (1) and (2) result in significant performance degradation, demonstrating that the downstream sensitivity term provides essential probe-specific information for intra-head ranking, rather than merely dictating global budget allocation.


W2-1 & Q2: Quality-matched accuracy and wall-clock at >128K context

W2: The practical accuracy-latency frontier is less established than the separate quality and cost results. ... A representative quality-matched wall-clock comparison would make the deployment claim stronger.

Q2: Can you pair the reported long-context latency operating point with task accuracy, and report total wall-clock time with the sparse-prefill contribution quantified?

Following your suggestion, we measured accuracy and end-to-end wall-clock time (prefill, scoring, and decode) together in a long-context, long-generation setting: LongBench-v2 [1] questions longer than 128K tokens (n = 200) with 0-shot CoT reasoning (median ~500 generated tokens), Ministral-3-14B [2], sparse prefill for every method including Full KV; wall-clock on 48 randomly sampled questions.

MethodCompression ratioAcc.E2E Wall-clock gain (single batch)E2E Wall-clock gain (vLLM, batched)
Full KV–44.51.00×1.00×
KVgrad4:145.0~0.07×–
8:143.5~0.07×–
KVgrad-MLP4:146.51.26×1.47×
8:135.51.39×1.58×

At matched quality, KVgrad-MLP reduces total wall-clock time, while exact KVgrad remains the more accurate scorer at high compression:

  • Quality-matched (4:1): KVgrad-MLP matches Full KV accuracy and reduces total wall-clock time in every setting, most in batched serving, where the smaller cache lets more requests run at once.
  • High compression (8:1): As noted in the paper, exact KVgrad is more accurate, staying close to Full KV where KVgrad-MLP drops. Its gradient scoring, however, makes it more than 14× slower than Full KV, so it suits offline compression rather than request-time serving.

Orthogonality to sparse prefill. Sparse prefill shortens prefill for every method alike, so it is orthogonal to KV eviction and outside our scope. In the paper, we use it to show Amdahl’s law: compression speeds up only decoding, so the end-to-end gain is bounded by prefill, the largest cost it leaves unchanged. Here, we also use it for all methods to fit the >128K-token, long-generation runs within the rebuttal period. Compression saves the same decoding time with or without it; a shorter shared prefill only raises the ratio.

W2-2: Task-specific loss of the MLP surrogate

W2: Moreover, the MLP can lose substantial task-specific quality: for Qwen3-4B on LCC at 4:1, Table 24 reports 47.6 versus 60.8 for Full KV and 64.4 for exact KVgrad. This is acknowledged qualitatively, but is important when interpreting the surrogate as retaining most of the exact method's benefit.

We acknowledge that on LCC at 4:1, KVgrad (MLP) scores 47.6, compared to 60.8 for Full KV and 64.4 for exact KVgrad. We will state this in the Limitations section and revise the text so that it does not imply the surrogate keeps the exact method's benefit on every task. The loss is not specific to KVgrad (MLP): KVzip+ (MLP) drops further to 34.9. This suggests a limitation of the current surrogate training rather than of the KVgrad score. We adopted the recipe of [3] as is, without searching over the architecture, training data, or objective. Improving the surrogate is a promising direction for future work.


Q2: Context-extension setting at 256K

Q2: Please also clarify the model's context-extension settings at 256K

Llama-3.1-8B was used solely for latency benchmarking, so we did not use any context extension. In contrast, Ministral-3-14B—which natively supports 256K tokens—was used to evaluate 256K accuracy. We will clarify this in the revised manuscript.


W3 & Q3: Robustness of NL-CR

W3: The headline near-lossless compression ratio is a summary of each subtask's largest passing ratio, rather than a single ratio that preserves every task. [...] Aggregating both thresholds and reporting sampling uncertainty would clarify how robust the headline 5.9x versus 4.7x advantage is.

Q3: Can the aggregate NL-CR be reported for the existing 2% and 5% per-task results, with uncertainty or low-baseline tasks reported separately?

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 in our revised manuscript, including the abstract.

Bootstrap 95% confidence intervals. KVgrad shows non-overlapping bounds at τ=5%\tau = 5\% and distinct separation at τ=2%\tau = 2\%, highlighting that KVgrad's performance gains are statistically significant.

τ=2τ=5
KVzip+4.73 [4.06, 5.54]6.46 [5.72, 7.40]
KVgrad5.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 (τ=2%\tau=2\% / τ=5%\tau=5\%) at fixed compression ratios (2:1, 4:1, and 8:1). KVgrad keeps the most tasks within tolerance (τ=2/τ=5\tau=2/\tau=5), and the gap widens with compression.

RatioKVzipKVzip+KVgradKVgrad (MLP)
2:189% / 97%89% / 97%90% / 98%84% / 94%
4:167% / 84%72% / 88%74% / 96%69% / 89%
8:128% / 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.

Its numerical precision is sensitive to the relative threshold, coarse ratio grid, and low-baseline tasks; for example, Qwen3-0.6B has a 0.4 Full-KV score on RULER CWE (Table 11).

Sensitivity of NL-CR We agree that the headline ratio is sensitive to the threshold, the ratio grid, and low-baseline tasks; this follows from its definition. It is a representative summary for the introduction, not a guarantee, and the paper states its scope (benchmarks, threshold, grid; Table 1, footnote 1). Each choice has a reason: (i) the grid is coarse because each ratio requires a full evaluation run, and (ii) low-baseline tasks are excluded because a relative threshold on a near-floor score is not a reliable signal.

[1] Bai et al. LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks. ACL 2025.

[2] Rastogi et al. Ministral 3. arXiv 2026.

[3] Jégou and Jeblick. KVzap: Fast, Adaptive, and Faithful KV Cache Pruning. arXiv 2026.

Reviewer_7sthOpenReview ↗

Follow-up on the rebuttal

Thank you for the additional experiments and clarifications. They substantially strengthen the evidence behind the method.

The shuffled-gradient control directly addresses my first concern. In particular, preserving KVgrad's original per-head budgets while permuting the sensitivity values lowers the 32:1 score from 53.95 to 34.00. This supports the value of probe-specific information beyond allocation alone. The effect is smaller at 8:1, so I would scope the conclusion to the tested model/subset and emphasize the stronger evidence at aggressive compression.

The new >128K LongBench-v2 evaluation is a useful practical addition. At 4:1, KVgrad-MLP reports comparable accuracy to Full KV (46.5 versus 44.5) with 1.26× single-batch and 1.47× batched wall-clock speedups. At 8:1, however, MLP accuracy falls to 35.5, whereas exact KVgrad reaches 43.5 but runs approximately 14× slower than Full KV. These results clarify the two variants' different use cases. Please keep the accuracy set (200 questions), timing subset (48 questions), and shared sparse-prefill configuration explicit. This is evidence for a new Ministral operating point, rather than quality validation of the original Llama 256K/8K latency benchmark. A prefill/scoring/decode breakdown from the existing timing runs would also help interpret the total gains.

The fixed-ratio tolerance coverage and results at both thresholds address much of my NL-CR concern. One statistical clarification remains: at the 2% threshold, the reported marginal intervals overlap. This neither establishes nor rules out significance of the difference. Could you report a paired bootstrap interval for the KVgrad-versus-KVzip+ difference or ratio, using the same resampled model-task pairs, and identify the three excluded low-baseline pairs? Please distinguish this variability across model-task pairs from uncertainty in individual task accuracies or training runs.

Overall, I maintain my weak-accept recommendation. The remaining requests concern interpretation and reporting of the existing results.

Comments on the paper

5 comments

We are grateful to the reviewer for the careful review and for raising important points. We have also added new results to the common response: (1) a vLLM integration of KVgrad and (2) results on video understanding, and we kindly invite the reviewer to read them.

W1 & Q1: Score–output link under real KV deletion

W1: The link between the score and actual output changes is still indirect. [...] A direct deletion test would make the main explanation stronger.

Q1: Does KVgrad score predict the output change from real KV deletion better than local scores, for example in output-distribution distance or loss?

  • 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 byKVzipKVzip+KVgrad
Repeat (∣ΔΦ∣\lvert\Delta\Phi\rvert)0.800.760.81
Repeat (KL)0.780.760.84
Answer (KL)0.320.370.45
  • RMSNorm. While the concern regarding the normalization effect is valid, our empirical results show that the pre-norm target outperforms the post-norm target (Table 3). The deletion test further supports this, as the correlation between Repeat (KL) is higher than that with Repeat (∣ΔΦ∣\lvert\Delta \Phi\rvert).

Setup

  • Model: Qwen3-0.6B
  • Dataset: RULER 4K, 39 requests (13 tasks ×\times 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 (∣ΔΦ∣|\Delta \Phi|): 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-1 & Q2: Quality, wall-clock, and memory under shared documents

W2: The best quality and lowest scoring cost come from different versions. In Figure 3, [...]

Q2: On a shared-document, multiple-query workload, how do exact KVgrad and the MLP compare in quality, full wall-clock time, and peak memory, including scoring?

To evaluate the quality, wall-clock time, and peak memory of KVgrad and KVgrad-MLP under a shared-document, multi-query workload, we use LongBench-v2 [1], where some documents are shared by 2–5 questions (Ministral-3-14B [2], 0-shot CoT, single batch, RTX PRO 6000). Since only part of the benchmark shares documents, we report accuracy on all questions longer than 128K tokens (n = 200) for a stable estimate, and end-to-end (prefill, scoring, decoding) wall-clock time and peak memory with questions that share a document, with each document prefilled and compressed once.

MethodCompression ratioAcc.Scoring / documentE2E Wall-clock, shared documentsPeak mem, prefill / decode (GiB)
Full KV–44.5–1.00×62.3 / 32.6
KVgrad4:145.0384–834 s0.10×65.8 / 20.8
8:143.5384–834 s0.10×65.8 / 17.9
KVgrad-MLP4:146.50.2 s1.22×62.3 / 20.8
8:135.50.2 s1.44×62.3 / 17.9

Both KVgrad and KVgrad-MLP cut decode memory (32.6 → 20.8 / 17.9 GiB at 4:1 / 8:1) while adding little peak memory during prefill (includes scoring), and the two scorers suit different regimes in accuracy and latency, consistent with the cost analysis in Section 4.3:

  • KVgrad: near-lossless even at 8:1, but its gradient pass makes it 10× slower than Full KV even with scoring shared across questions; it suits contexts compressed once offline and then reused across many queries.
  • KVgrad-MLP: matches KVgrad at 4:1 while running 1.22× faster than Full KV, but loses 9.0 points at 8:1; it suits request-time compression at moderate ratios.
  • Speed-up bound: Note that speedups are bounded by Amdahl's law, where the fixed prefill and non-attention decode portions cap the maximum gains.

W2-2: Single-setting tolerance and confidence intervals of NL-CR

W2: The 5.9x headline is also an average of task-specific ratios, not one setting that meets the 2% limit on every task.

To complement the geometric-mean NL-CR, we report both single-setting tolerance analysis and bootstrap confidence intervals across 113 model-task pairs. We will include these results in our revised manuscript, including the abstract.

Single-setting tolerance. We measure the percentage of the model-task pairs that remain within tolerance (τ=2%\tau=2\% / τ=5%\tau=5\%) at fixed compression ratios (2:1, 4:1, and 8:1). KVgrad keeps the most tasks within tolerance (τ=2/τ=5\tau=2/\tau=5), and the gap widens with compression.

RatioKVzipKVzip+KVgradKVgrad (MLP)
2:189% / 97%89% / 97%90% / 98%84% / 94%
4:167% / 84%72% / 88%74% / 96%69% / 89%
8:128% / 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.

Bootstrap 95% confidence intervals. KVgrad shows non-overlapping bounds at τ=5%\tau = 5\% and distinct separation at τ=2%\tau = 2\%, highlighting that KVgrad's performance gains are statistically significant.

τ=2τ=5
KVzip+4.73 [4.06, 5.54]6.46 [5.72, 7.40]
KVgrad5.92 [4.99, 7.06]8.69 [7.59, 10.02]

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.

[1] Bai et al. LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks. ACL 2025.

[2] Rastogi et al. Ministral 3. arXiv 2026.

AuthorsOpenReview ↗

General Response: Additional Results

We thank all reviewers for their constructive feedback. To address the limitations discussed in L1112-L1121, we obtained additional results on vLLM integration and video understanding, which we summarize below.

1. vLLM Integration

Setup

  • Model: Llama-3.1-8B-Instruct (w/ sparse prefill [1]), bf16 KV cache; KVgrad-MLP (4:1).
  • Engine: fork of vLLM 0.32.0. HF denotes our kvpress-based implementation used in the paper (HF Transformers).
  • GPU: 1× RTX PRO 6000 Blackwell Max-Q (96 GB); vLLM is given 81 GiB or 38 GiB of GPU memory.
  • Workloads: all requests submitted at once, outputs not capped.
    • RULER-4K: 2K–4K context, generation ≤ 128.
    • LongBench: 0.2K–65K context (median 8.6K), generation 32–512 (accuracy only).
    • Synth1: 8K–33K context, generation 256–2K (median 830).
    • Synth2: 37K–98K context, generation 1K–7K (median 3.4K).

Results

  1. Freed KV memory becomes throughput once the per-step overhead is removed: KVgrad-MLP is 1.46× / 1.88× faster than stock vLLM on Synth1 / Synth2 with 81 GiB, and 1.63× / 2.06× with 38 GiB. Naive head paging and KVgrad-MLP integration (second row) loses most of this gain to per-step CPU overhead on Synth1 with 81 GiB (1.03×); our optimizations (third row) recover it. RULER-4K is compute-bound (2K–4K contexts and outputs ≤ 128 tokens, so each request's KV cache is small and prefill dominates), so freed memory brings no gain and head paging costs 10% (0.90×).
  2. vLLM reproduces the paper's accuracy: all scores are within 0.3 points of HF (< 1% relative); the small differences come from kernel numerics, which flip a few near-tied top-k selections.

Together, these show that KVgrad-MLP's gains carry over to a production serving engine without changing its accuracy.

Latency (wall-clock s, speedup vs. stock vLLM)

GPU memory 81 GiBGPU memory 38 GiB
RULER-4KSynth1Synth2RULER-4KSynth1Synth2
Stock vLLM (Full KV)81.7 (1.00×)363.1 (1.00×)708.8 (1.00×)80.7 (1.00×)449.4 (1.00×)978.8 (1.00×)
+ head paging [1] & KVgrad-MLP94.6 (0.86×)354.1 (1.03×)459.6 (1.54×)94.7 (0.85×)348.4 (1.29×)524.6 (1.87×)
+ custom optimization90.4 (0.90×)248.7 (1.46×)376.3 (1.88×)89.9 (0.90×)275.6 (1.63×)474.1 (2.06×)

Accuracy (HF score, Δ = vLLM − HF, per compression ratio)

MethodBenchmark2:14:18:116:132:1
KVgrad-MLPRULER-4K95.40 (0.00)94.94 (+0.01)93.02 (−0.04)84.98 (−0.28)53.67 (+0.08)
LongBench46.83 (−0.10)45.58 (+0.11)43.34 (+0.07)37.69 (+0.06)32.17 (−0.29)
KVgradRULER-4K95.47 (+0.03)95.09 (+0.06)92.94 (+0.01)84.30 (−0.03)58.74 (−0.09)
LongBench45.95 (−0.13)45.75 (−0.02)45.81 (−0.28)43.31 (−0.04)36.42 (−0.04)

[1] Jiang et al. MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention. NeurIPS 2024.

[2] Rehg. KV-Compress: Paged KV-Cache Compression with Variable Compression Rates per Attention Head. arXiv 2024.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.