acceptodds
Under review as a conference paper at ICLR 2027

Balancing Query Coverage in KV Cache Compression

Abstract

During autoregressive decoding, the KV cache supports queries that may depend on different parts of a long context. Under a limited memory budget, selecting tokens by aggregate attention can leave some queries poorly covered even when the total retained attention is high. We study this imbalance through a distributional formulation of cache eviction, measuring query coverage by the attention probability mass assigned to retained tokens. For fixed queries and keys, restricting attention to a retained token subset is equivalent to conditioning the original attention distribution on that subset. The KL divergence from the conditioned distribution to the original distribution equals the negative logarithm of the retained probability mass, yielding an objective that maximizes the geometric mean of query coverage. Its marginal scores give greater weight to attention from queries with less retained mass. We instantiate this principle as FidKV, a lightweight online eviction policy that estimates retained attention mass from the current cache without additional training or calibration. Our analysis bounds changes in token rankings by the spread of retained mass across queries, recovering cumulative-attention rankings when coverage is uniform. Experiments on LongBench and RULER across three language-model families support this prediction. On six held-out LongBench tasks, the advantage of FidKV is most pronounced under aggressive compression: at 2% and 5% cache budgets, it outperforms the strongest evaluated baseline on most tasks, while remaining competitive at moderate budgets., respectively. Paired cache measurements further show improved coverage for the worst-served queries and reduced coverage imbalance, while deployment retains the memory and latency profile of standard KV eviction.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV Cache, Long-Context Inference, Attention Preservation

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_SbvjOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the elimination of KV cache from the perspective of unbalanced query coverage, links the divergence between the quality of retained attention and the conditional distribution, deduces the scoring rule for assigning higher weights to low-coverage queries, and implements the online elimination method FidKV. Experiments show that the complete strategy has a more obvious advantage under a tighter cache budget.

Critical strengths

1.The method deduces the scoring rules from a clear coverage target and provides an understandable explanation for why the weight of low-coverage queries needs to be increased.

2.The author provided the matching control after removing the weighted terms and reported the paired confidence intervals. Mechanism analysis indicates that under the condition of repeated elimination, weighting helps to improve the approximation of coverage targets and attention output.

Critical weaknesses

1.In Table 9 of Appendix C, the core weighting item did not lead to a significant increase in the LongBench task score under either a 10% or 20% budget. The author also pointed out that most tasks ended before the revised scores affected the next elimination, so the advantage of the complete method over other baselines cannot be directly attributed to this weighting term. 2.The most obvious task benefits of the paper occur in the 2% and 5% budgets, but these Settings still lack equally strict weighted item removal controls. The existing experiments cannot fully distinguish the contributions of the core mechanism from those of other designs such as elimination scheduling. 3.The connection between the improvement of fidelity at the mechanism level and the final task benefits remains insufficient. The teacher's forced replay experiment shows that the fidelity index has improved, but the fixed generation trajectory cannot fully reflect the error accumulation during free generation. It is suggested to supplement the analysis under the condition of free generation to explain under what circumstances the improvement of this indicator can be transformed into a stable improvement in task performance.

Questions for authors
  1. Can cumulative attention controls under the same scheduling and budget be added to the existing 2% and 5% budget experiments, only changing whether coverage weighting is used?
  2. What are the specific differences between the cumulative attention reference in Figure 2 and the matching control in Appendix C, and how should the effect differences shown by the two be explained?
3 comments
AuthorsOpenReview ↗

Response to Reviewer Sbvj

We sincerely thank the reviewer for the recognition of our work. To resolve your concerns and questions, we respond to each point below.

W1 / W2 / Q1 — cumulative-attention control at 2% and 5% under the same schedule and budget.

Thank you for the suggestion. We added this control (Table A). CumAttn removes only the 1/w^1/\hat{w} factor and keeps the schedule and budget fixed. The weight helps on tasks where queries are covered unevenly, which we measure by the dispersion of w^\hat{w} (its coefficient of variation across decoding queries). At 2%, the gain increases with this dispersion across the five short-answer tasks, and it is largest on the evidence-sparse QA tasks MFQA and 2WkMQ, which also gain at 5%. Where w^\hat{w} is nearly uniform (PC, LCC) the weight has little to re-rank and FidKV stays close to the control.

Table A. Matched control at the extreme budgets (Llama-3.1-8B, protocol of Tables 3–4), with tasks ordered by the dispersion of w^\hat{w}. CumAttn is FidKV with only the 1/w^1/\hat{w} factor removed. Gain is FidKV minus CumAttn. Avg is sample-weighted, with a paired 95% bootstrap interval for the gain. *MultiNews is the long-generation task.

PCLCCSAMSumMFQA2WkMQMNws*Avg
2% Dispersion of w^\hat{w}0.0460.0520.0540.0730.0780.150
2% CumAttn0.1614.9632.1453.8043.4022.3526.67
2% FidKV0.0915.3632.5954.3744.4222.0227.00
2% Gain−0.07+0.40+0.46+0.57+1.02−0.33+0.33 [−0.18, +0.84]
5% Dispersion of w^\hat{w}0.0300.0370.0370.0500.0520.103
5% CumAttn0.1219.9333.4454.9244.0224.4428.37
5% FidKV0.1319.5932.6255.6544.3924.6328.36
5% Gain0.00−0.34−0.82+0.73+0.38+0.19−0.01 [−0.46, +0.46]

On the schedule, the delayed first eviction is not a separate design choice but a prerequisite of the coverage estimate, since w^\hat{w} is computed from the attention of decoding queries and no token can be scored before the first one has been observed. We will state it explicitly as a component of the method.

W3 — when does the fidelity improvement turn into task improvement; analysis under free generation.

The dispersion of w^\hat{w} answers this. Dispersion shrinks as the budget grows (0.114, 0.091, 0.071, 0.047 on average at 0.5%, 1%, 2%, 5%), so at 10% and 20% the weighted and unweighted policies make nearly the same selections. Table 9 is intended to verify exactly this prediction of Proposition 1. When coverage is nearly uniform, the weight reduces to cumulative attention and preserves accuracy, while still improving the log-fidelity objective where repeated eviction occurs. Under tight budgets dispersion is high, and the fidelity improvement turns into task gains when the tokens exchanged by the weight are context evidence, that is, on evidence-sparse QA (Table A). We also ran the free-generation analysis on the three long-generation tasks (Table B). There the correction preserves accuracy, because the exchanged tokens are mostly newly generated ones rather than context evidence, which changes the summary-level score little. We will add this analysis and the dispersion measure to the paper.

Table B. FidKV − CumAttn under free generation on the three tasks with the 512-token cap (Llama-3.1-8B, F1 points, 50 paired examples per task).

Task2%5%10%20%
GovReport−0.06−0.06−0.28+0.52
QMSum+0.07+0.21+0.52−0.44
MultiNews−0.54+0.29−0.38+0.34

Q2 — Figure 2 reference vs. the Appendix C control.

They are different references. Figure 2 compares the complete FidKV policy with standard cumulative-attention eviction, which starts evicting at prefill. Appendix C uses the timing-matched control, which removes only the 1/w^1/\hat{w} factor. We will state the reference of Figure 2 explicitly in its caption and add the matched-control version of the figure.

We hope these responses resolve your concerns, and we are happy to provide any further clarification.

Reviewer_SbvjOpenReview ↗

Raised my score to 3

Thank you for the detailed response and additional experiments. My concerns have been adequately addressed, and I have raised my score to 3 accordingly.

We sincerely thank the reviewer for the valuable suggestions and for raising the score. We especially appreciate your recognition of the two aspects at the core of this work, namely the derivation of the scoring rule from a clear coverage objective and the mechanism analysis with the matched control.

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

The paper studies KV cache eviction from the perspective of per-query retained attention mass, or "fidelity" wtw_t. Since restricting attention to a retained set conditions the full attention distribution, the KL divergence equals −log⁡wt-\log w_t, which gives a log-fidelity objective; its KKT conditions yield the token score ∑tαt,j/wt\sum_t \alpha_{t,j}/w_t, which induces the same ranking as cumulative attention when all fidelities are equal. Proposition 1 bounds how much this score can re-rank tokens by the fidelity spread ρ\rho. FidKV implements the score online, estimating fidelity from a provisional top-BB set, and the paper shows that the current-cache normalizer cancels in the update. On LongBench and RULER with three models, FidKV is competitive at 1010% and 2020% budgets (margins of at most 0.60.6 points), and on six LongBench tasks with LLaMA-3.1-8B it outperforms the strongest baseline by about 55 points at 22% and 55% budgets, with small memory and latency overhead.

Critical strengths

S1: The formulation is clean and well motivated. The identity KL(qt∥pt)=−log⁡wt\mathrm{KL}(q_t \Vert p_t) = -\log w_t turns eviction into an explicit objective, the derived score has a clear interpretation and recovers cumulative attention as a special case, and Proposition 1 gives a testable prediction about when the correction can matter. The claim that the online update matches the full-history weighting is also checked numerically (residual below 1.7×10−71.7 \times 10^{-7}, Pearson correlation above 0.990.99).

S2: The method is practical and the evaluation is careful in several respects. It is training-free, keeps peak memory within about 0.30.3% of SnapKV, and runs at 0.930.93–1.08×1.08\times the speed of SnapKV. The paper reports paired bootstrap intervals for key comparisons and includes a matched control that removes only the 1/w^t1/\hat{w}_t weighting.

Critical weaknesses

W1: The empirical gains cannot be attributed to the proposed fidelity weighting. In the matched control, the F1 difference between FidKV and the same policy without the 1/w^t1/\hat{w}_t factor is −0.051-0.051 [−0.163,+0.059][-0.163, +0.059] at 1010% and −0.0004-0.0004 [−0.333,+0.276][-0.333, +0.276] at 2020%, and Appendix C states that on 1313 of 1616 tasks the two policies make nearly the same selections. Section 4.2 also notes that the first eviction, made after a single decoding query, is the only eviction for most LongBench tasks; with one query, dividing by its fidelity does not change the ranking within each head. The gains over baselines such as H2O therefore seem to come from other design choices, such as delaying the first eviction until the first decoding query is scored, which are not ablated. The matched control is also not reported for the 22% and 55% stress test, where the largest gains appear.

W2: Budget accounting and baseline coverage are not fully clear. Algorithm 1 evicts only when the cache exceeds B+ΔB + \Delta with Δ=256\Delta = 256, so the cache can hold up to 256256 extra tokens between evictions, which may be large relative to BB at 22% and 55% budgets; it is not stated whether the baselines receive the same slack. DefensiveKV is described as the closest recent method but is not compared. At moderate budgets the gains are small (at most 0.60.6 points) and come from single runs.

Questions for authors

Q1: Can you report the matched CumAttn control in the 22% and 55% stress test, together with an ablation of the eviction timing (first eviction after the first decoding query) and of the slack Δ\Delta?

Q2: Figure 2 shows large F1 differences between FidKV and the cumulative-attention reference on MFQA, while Appendix C states that the paired intervals include zero on all 1616 tasks. How does the reference in Figure 2 differ from the CumAttn control?

Q3: Do all baselines use the same slack Δ=256\Delta = 256 and the same first-eviction timing? What is BB in tokens at the 22% and 55% budgets?

Q4: On the three tasks in Table 9 where repeated eviction occurs, does the correction improve answer accuracy under normal generation, rather than only the log-fidelity objective and output error under fixed-teacher replay?

Q5: How does FidKV compare with DefensiveKV, which the paper describes as the closest recent method?

6 comments
AuthorsOpenReview ↗

Response to Reviewer Dws9 (Part 1/2)

We sincerely thank the reviewer for recognizing the theory and motivation of this work, and for the constructive suggestions. To resolve your concerns and questions, we respond to each point below.

W1 / Q1 — matched CumAttn at 2% and 5%; ablation of eviction timing and of Δ.

We thank the reviewer for these suggestions and have run all three analyses.

Matched control at 2% and 5% (Table A).

CumAttn removes only the 1/w^1/\hat{w} factor and keeps everything else fixed. The weight helps on tasks where queries are covered unevenly, which we measure by the dispersion of w^\hat{w} (its coefficient of variation across decoding queries). At 2%, the gain increases with this dispersion across the five short-answer tasks, and it is largest on the evidence-sparse QA tasks MFQA and 2WkMQ, which also gain at 5%. Where w^\hat{w} is nearly uniform (PC, LCC) the weight has little to re-rank and FidKV stays close to the control. Dispersion shrinks as the budget grows (0.114, 0.091, 0.071, 0.047 on average at 0.5%, 1%, 2%, 5%), which is why at 10% and 20% the two policies make nearly the same selections, as Proposition 1 predicts. MultiNews is the exception. It is a long-generation task, where the tokens exchanged by the weight are mostly newly generated ones rather than context evidence, so its high dispersion does not turn into a score difference.

Table A. Matched control at the extreme budgets (Llama-3.1-8B, protocol of Tables 3–4), with tasks ordered by the dispersion of w^\hat{w}. CumAttn is FidKV with only the 1/w^1/\hat{w} factor removed. Gain is FidKV minus CumAttn. Avg is sample-weighted, with a paired 95% bootstrap interval for the gain. *MultiNews is the long-generation task.

PCLCCSAMSumMFQA2WkMQMNws*Avg
2% Dispersion of w^\hat{w}0.0460.0520.0540.0730.0780.150
2% CumAttn0.1614.9632.1453.8043.4022.3526.67
2% FidKV0.0915.3632.5954.3744.4222.0227.00
2% Gain−0.07+0.40+0.46+0.57+1.02−0.33+0.33 [−0.18, +0.84]
5% Dispersion of w^\hat{w}0.0300.0370.0370.0500.0520.103
5% CumAttn0.1219.9333.4454.9244.0224.4428.37
5% FidKV0.1319.5932.6255.6544.3924.6328.36
5% Gain0.00−0.34−0.82+0.73+0.38+0.19−0.01 [−0.46, +0.46]

Eviction timing.

The delayed first eviction is not a separate design choice but a prerequisite of the coverage estimate. w^\hat{w} is computed from the attention of decoding queries, so no token can be scored, and none is evicted, before the first decoding query has been observed. It is therefore an integral part of the method in all our experiments, and we will state it explicitly as a component of FidKV in the paper.

Slack Δ (Table B).

The slack does not enlarge the retained context. Every eviction brings the cache back to exactly BB tokens, and Δ only sets how many newly generated tokens may accumulate before the next eviction is triggered. The context evidence kept after an eviction is therefore the same BB tokens for any Δ, and Δ changes only how often the cache is re-compacted during generation. To verify this empirically we reduced the slack fourfold, from Δ=256 to Δ=64, which is well below the median BB of about 237 tokens at these budgets. The results are essentially unchanged for all three methods (differences of at most 0.6 F1 in either direction), and FidKV keeps its margin over H2O and StreamingLLM. The stress-test conclusions therefore do not depend on the size of the buffer.

Table B. Slack ablation (Llama-3.1-8B; sample-weighted F1 over MFQA, 2WkMQ, MNws, SAMSum, LCC).

BudgetMethodΔ=256 (paper)Δ=64
2%FidKV32.6732.32
2%H2O26.4825.93
2%StreamingLLM26.1626.18
5%FidKV34.3134.55
5%H2O28.1628.56
5%StreamingLLM28.1728.51
AuthorsOpenReview ↗

Response to Reviewer Dws9 (Part 2/2)

W2 / Q3 — do baselines use the same slack and timing; B in tokens.

Yes. All online-eviction methods (StreamingLLM, H2O, Keyformer, Quest, FidKV) run with the same slack Δ=256. Keyformer and Quest also use the same first-eviction timing as FidKV, H2O and StreamingLLM evict from prefill as in their original design, and SnapKV, AdaKV and PyramidKV compress once at prefill with their standard observation window. At the 2% and 5% budgets the median BB is about 237 tokens, and as shown above (Table B) the size of the slack does not affect the results. We will add these details to the paper.

Q2 — reference in Figure 2 vs. the CumAttn control.

They are different references. Figure 2 compares the complete FidKV policy with standard cumulative-attention eviction, which starts evicting at prefill. Appendix C uses the timing-matched control, which removes only the 1/w^1/\hat{w} factor. We will state the reference of Figure 2 explicitly in its caption and add the matched-control version of the figure.

Q4 — answer accuracy under normal generation on the three repeated-eviction tasks.

Thank you for raising this point, which the fixed-teacher replay in the paper did not cover. We evaluated the three tasks under normal generation (Table C). The correction preserves answer accuracy on these tasks, with all differences within about half a point and intervals that include zero. Its measurable effect there is on the log-fidelity objective and the attention-output error (Table 9). In long generation the tokens exchanged by the weight are mostly newly generated ones, which changes the summary-level score little. We will add this analysis to the paper.

Table C. FidKV − CumAttn under normal generation on the three tasks with the 512-token cap (Llama-3.1-8B, F1 points, 50 paired examples per task).

Task2%5%10%20%
GovReport−0.06−0.06−0.28+0.52
QMSum+0.07+0.21+0.52−0.44
MultiNews−0.54+0.29−0.38+0.34
Macro [95% CI]−0.05 [−0.46, +0.36]+0.14 [−0.29, +0.59]

Q5 / W2 — comparison with DefensiveKV.

Thank you for the suggestion. We ran DefensiveKV, and also KVzip. At 10% and 20% (Table D) the methods are close, and FidKV has the highest average at both budgets. At the extreme budgets (Table E), where only 2% or 5% of the tokens can be kept, FidKV preserves substantially more accuracy than both methods on average and on four of the five tasks.

Table D. LongBench F1 at 10% and 20% budgets (Llama-3.1-8B). †Average over 15 tasks (TREC excluded, where our KVzip port did not reproduce the full-cache score).

BudgetMethodQasperMFQANrtvQAHpQA2WkMQMuSQGovRptQMSumMNwsTRECTrvQASAMSumPCPRLCCRB-PAvg†
10%FidKV32.5556.4031.2053.9744.5229.3337.3414.7727.3514.0849.0932.989.08100.0021.1526.6637.76
10%DefensiveKV31.9254.7331.2554.0442.9929.0236.4115.6719.8913.0048.2534.3810.13100.0020.6728.6337.20
10%KVzip31.2953.9130.8750.8835.9523.8121.9413.3323.54–47.2037.763.2244.5018.1920.3130.45
20%FidKV33.5456.6431.1454.1544.5929.7837.9215.5529.4214.1348.7533.118.83100.0023.3928.5438.36
20%DefensiveKV33.9454.7230.3853.9444.2629.7738.6616.7227.2214.5848.7333.618.25100.0024.7929.0338.27
20%KVzip33.1955.7730.2653.6239.6127.7929.6014.4628.33–46.9236.835.6295.5020.1223.1236.05

Table E. Extreme budgets (Llama-3.1-8B), same protocol as Tables 3–4. Avg is sample-weighted.

BudgetMethodMFQA2WkMQMNwsSAMSumLCCAvg
2%FidKV54.3744.4222.0232.5915.3632.67
2%DefensiveKV25.9518.031.3822.623.5513.69
2%KVzip13.1220.976.9234.830.1715.31
5%FidKV55.6544.3924.6332.6219.5934.31
5%DefensiveKV44.9140.018.5732.2610.0426.22
5%KVzip25.0622.227.3438.543.9019.11

We hope these responses resolve your concerns, and we are happy to provide any further clarification.

Thank you for the detailed answers and new experiments. Some of my concerns are now resolved, e.g. the slack and DefensiveKV comparison. But the matched control at 2% and 5% and also under normal generation shows almost no difference on average between FidKV and CumAttn. So the gains don’t seem to come from the fidelity weighting, which is the main idea of the paper. For this reason, I will keep my score.

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

The paper proposes FIDKV, an KV cache compression algorithm which is driven by the concept of query fidelity, which measures what fraction of attention score for a given query token is preserved after eviction. The authors show that KL divergence between the original attention distribution and evicted attention distribution for a given query is proportional to the negative logarithm of the query fidelity. This leads to an objective that maximizes the geometric mean of query fidelity - further leading to allocating higher weight to attention from queries with less retained mass. FIDKV is an online eviction policy based on this principle. The authors conducted experiments on LongBench and RULER benchmarks with LLaMA-8B, Mistral-7B and Qwen3-8B models at {2%, 5%, 10%, 20%, ..., 50%} cache budgets.

Critical strengths
  • Strong theoretical and analytical findings - The proposed method is based on the concept of "query fidelity" and the observation that attention reweighting does not change with retention. The theoretical background leading to the design of FIDKV is novel and insightful.

  • Principled KV compression method - FIDKV is principled on the above mentioned theoretical insights, making the method well justified. Moreover, the dual-cache analysis validates the faithfulness of the online policy.

Critical weaknesses
  • Results - Inspite of the methodological contribution, the empirical results are not very convincing for FIDKV. Table 1, 5 and 7 show that FIDKV lags behind most competitive baselines on several tasks on several configurations. The average scores on LongBench could be hugely driven by the high-performant tasks like PR, MFQA, therefore are not very reliable to establish the superiority of FIDKV. Another red flag is that the authors only consider selective 6 tasks for extreme budget tests. Having a more consistent benchmarking would increase the authenticity of the baseline comparisons. Similarly, numbers on RULER benchmarks are not very clearly visible from Fig 4, representing the results in a tabular form might help.

  • Efficiency profile - Table 8 suggests that FIDKV is not as fast as StreamingLLM or H2O or Keyformer. A more detailed discussion is needed to justify how this can be compensated.

  • Baseline coverage - Most of the baselines are from 2024 and beyond. Adding recent SOTA eviction-based KV compression method such as KVZip would increase the credibility of the paper.

Questions for authors

See above suggestions.

2 comments
AuthorsOpenReview ↗

Response to Reviewer zvXk (Part 1/2)

We sincerely thank the reviewer for the careful and encouraging review. We are glad that the reviewer found the query-fidelity formulation novel and insightful and the resulting method principled and well justified; this is exactly the contribution we hoped to convey. The suggestions on the empirical side were very helpful, and we have followed each of them. The new analyses and baselines below make the evidence stronger, and we are grateful for the guidance. To resolve your concerns, we respond to each point below.

W1a — FidKV lags on several tasks; averages may be driven by PR / MFQA.

We removed PassageRetrieval (PR) and MultiFieldQA (MFQA) and recomputed the LongBench average over the remaining 14 tasks (Table A), now also including the newly added KVzip and DefensiveKV. At 10% FidKV remains the best method, and at 20% it is on par with the best baselines.

Table A. LongBench average F1 (Llama-3.1-8B), with and without PR and MFQA. †KVzip averages exclude TREC (see Table C).

Method10%, all 1610%, w/o PR & MFQA20%, all 1620%, w/o PR & MFQA
StreamingLLM31.0526.2831.9727.43
H2O31.2926.6032.3027.80
Keyformer33.2127.9634.4529.18
SnapKV34.8228.9236.2830.35
PyramidKV34.8628.8536.4130.51
AdaKV35.1929.1936.7630.91
Quest35.8129.8736.6930.79
KVzip† (new)30.4527.5636.0529.96
DefensiveKV (new)35.6929.7336.7930.99
FidKV36.2830.2936.8430.92

We do not claim that FidKV wins on every task: the weighting changes the retained set only when query coverage is uneven. Table B shows this per task: the gain from the weight grows with the dispersion of coverage, and evidence-sparse QA tasks benefit most. We will report this dispersion measure alongside the per-task results to make clear where the advantage lies.

Table B. Gain of the 1/w^1/\hat{w} weight over the matched unweighted control at 2% budget, ordered by the dispersion of w^\hat{w} (its coefficient of variation across decoding queries).

TaskDispersion of w^\hat{w}CumAttnFidKVGain
PassageCount0.0460.160.09−0.07
LCC0.05214.9615.36+0.40
SAMSum0.05432.1432.59+0.46
MultiFieldQA0.07353.8054.37+0.57
2WikiMQA0.07843.4044.42+1.02

W1b — six tasks at extreme budgets.

The benchmarking is consistent: the six tasks are a subset of the same 16 LongBench tasks, fixed in advance as one representative per LongBench category, and all methods are evaluated on them under identical settings.

W1c — RULER in tabular form. We will add the per-task RULER numbers as a table in the appendix.

AuthorsOpenReview ↗

Response to Reviewer zvXk (Part 2/2)

W2 — efficiency.

FidKV is slower than StreamingLLM, H2O and Keyformer because it does more work at each decoding step. StreamingLLM keeps a fixed recent window and computes no scores at all, and H2O and Keyformer perform a single accumulation of the attention row. FidKV performs the same accumulation and additionally estimates the coverage of the current query. It selects the provisional top-BB set, sums each head's attention over it to obtain w^\hat{w}, and updates a second, weighted score table. This coverage estimate is the entire source of the gap, and it requires no extra forward computation, parameters or calibration.

The resulting slowdown relative to these three methods is moderate. For example, on LLaMA-3.1 at a 10% budget the full LongBench run takes 6330 s with FidKV versus 5368 s with H2O (about 18% more), and FidKV is still faster than SnapKV (6825 s), Quest (9262 s) and AdaKV (9432 s), with peak memory unchanged. In exchange, FidKV is 3.1–5.2 F1 higher on the LongBench average than the three faster methods at the same budget.

W3 — recent baselines (KVzip).

Thank you for the suggestion. We ran KVzip and also the recent DefensiveKV at 10% and 20% (Table C) and at the extreme budgets (Table D). Although FidKV is not the best on every individual task, it has the highest average at both 10% and 20%, and it leads both methods on average at 2% and 5%.

Table C. LongBench F1 at 10% and 20% budgets (Llama-3.1-8B), with the newly added baselines. †Average over 15 tasks (TREC excluded, where our KVzip port did not reproduce the full-cache score).

BudgetMethodQasperMFQANrtvQAHpQA2WkMQMuSQGovRptQMSumMNwsTRECTrvQASAMSumPCPRLCCRB-PAvg†
10%FidKV32.5556.4031.2053.9744.5229.3337.3414.7727.3514.0849.0932.989.08100.0021.1526.6637.76
10%DefensiveKV31.9254.7331.2554.0442.9929.0236.4115.6719.8913.0048.2534.3810.13100.0020.6728.6337.20
10%KVzip31.2953.9130.8750.8835.9523.8121.9413.3323.54–47.2037.763.2244.5018.1920.3130.45
20%FidKV33.5456.6431.1454.1544.5929.7837.9215.5529.4214.1348.7533.118.83100.0023.3928.5438.36
20%DefensiveKV33.9454.7230.3853.9444.2629.7738.6616.7227.2214.5848.7333.618.25100.0024.7929.0338.27
20%KVzip33.1955.7730.2653.6239.6127.7929.6014.4628.33–46.9236.835.6295.5020.1223.1236.05

Table D. Extreme budgets (Llama-3.1-8B), same protocol as Tables 3–4. Avg is sample-weighted.

BudgetMethodMFQA2WkMQMNwsSAMSumLCCAvg
2%FidKV54.3744.4222.0232.5915.3632.67
2%DefensiveKV25.9518.031.3822.623.5513.69
2%KVzip13.1220.976.9234.830.1715.31
5%FidKV55.6544.3924.6332.6219.5934.31
5%DefensiveKV44.9140.018.5732.2610.0426.22
5%KVzip25.0622.227.3438.543.9019.11

We hope these responses resolve your concerns, and we are happy to provide any further clarification.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.