acceptodds
Under review as a conference paper at ICLR 2027

CalibKV: Calibrated Budgets for Long-Context Attention

Abstract

Sparse attention must decide which cached keys to use and how many to retain. Fixed budgets cannot adapt to each request, while sound score bounds in our measurements admit much of the cache. We propose CalibKV, which estimates a per-head retention budget from the request's keys and selects keys by exact score at decode. A learned query subspace and a separate calibration bank set the budget during prefill; the current query determines the selected keys. We establish pairwise residual coverage under exchangeability and evaluate quality and cost at the resulting budgets. On book-passage language modeling tasks using three War and Peace segments, mean relative to Dense ranges from to over 8K to 128K contexts, while the mean budget falls from 31.2% to 2.1%. LongBench macro scores are within points of Dense on Llama and Qwen. On MATH-500, CalibKV chooses a 99.87% budget and scores 46.6%, compared with 44.6% for Dense. At long contexts, its single-layer attention calculation is faster than Dense.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV cache, sparse attention

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_9HXQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CalibKV, a method for adaptive sparse attention budgeting. It learns per-head query subspaces and calibration banks offline, estimates request-specific attention budgets during prefill, and selects top-ranked keys using exact attention scores during decoding. A rank-m screening variant is also introduced to reduce full-dimensional score computation. Experiments on language modeling and downstream benchmarks show that CalibKV maintains near-dense quality while attending to a small fraction of cached keys.

Critical strengths

1. Adaptive budget estimation. CalibKV introduces a calibration-based approach to estimating per-request, per-head attention budgets, separating budget estimation from query-dependent token selection.

2. Promising quality retention. CalibKV maintains near-dense language modeling quality with relatively small attention budgets.

Critical weaknesses

1. Limited novelty. The motivation of CalibKV substantially overlaps with Twilight [1], which already proposes adaptive attention budgets based on attention distributions. Although CalibKV adopts a different calibration approach, its advantages over existing methods remain unclear, and no direct comparison with Twilight is provided.

2. Insufficient experimental evaluation.

  • Incomplete benchmark coverage. LongBench includes only 10 of the 21 datasets, while RULER covers only a small subset of its 13 tasks, with just 100 examples for variable tracking. This limits the generalizability of the results.

  • Unfair budget comparisons. Baselines operate at substantially different sparsity levels (e.g., 0.2% for Quest vs. 3.1% for CalibKV at 64K). Without matched-budget comparisons or quality–budget trade-off curves, the reported improvements are difficult to interpret.

  • Limited efficiency benefits. At 128K, its decoding latency increases from 48.05 to 53.05 ms/token compared with Dense, and its end-to-end latency is also higher. Moreover, efficiency is evaluated only at batch size 1.

[1] Lin C, Tang J, Yang S, et al. Twilight: Adaptive attention sparsity with hierarchical top-$ p $ pruning[J]. Advances in Neural Information Processing Systems, 2026, 38: 119406-119432.

Questions for authors

1. Novelty. What are the key advantages of CalibKV over Twilight? Can the authors provide a direct comparison?

2. Benchmark coverage. Why are only 10 LongBench datasets and a small subset of RULER tasks evaluated? Can the authors provide results on the complete benchmarks?

3. Fair comparisons. Can the authors provide matched-budget comparisons or quality–budget trade-off curves? How are candidate fractions and actual attention budgets distinguished across methods?

4. Efficiency. Can the authors provide a breakdown of computational overhead and results under batched decoding?

Reviewer_wjA3OpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes the CalibKV method, which separates how much to retain from what problem to use it for. The method learns a low-rank subspace for each query head offline and independently stores calibration queries. In the prefill stage, it estimates the budget for each head based on the keys of the current request, and in the decode stage it computes exact scores for all keys and completes the entire attention computation according to the budget. The paper tests on instruct models such as Llama3.1-8B and Qwen2.5-7B, and experiments show that CalibKV achieves a Δ\DeltaNLL close to full computation with a relatively low budget, and also performs well on downstream task tests.

Critical strengths
  1. The models covered in the paper are relatively sufficient, and the disclosed limitations, such as the speed issue, are clear.

  2. Separating the retained budget from the actual selection computation makes the method's motivation clear.

Critical weaknesses
  1. The paper is poorly written and difficult to read. For example, the setting part in Section 3 overlaps with the notation part in Section 4, symbols in the main text and concepts at their first appearance lack explanation, and the citation of Theorem 1 does not state that it is located in the appendix.

  2. The end-to-end results reported in the paper show that, because each decode step precisely scans all keys, the current method is actually slower in wall-clock computation time than dense computation. The explanations of the budget, retention ratio, and computation ratio in the tables remain unclear, making intuitive reproduction difficult.

  3. The baselines compared in the paper may be not enough; it would be worth conducting a clearer survey of and comparison with current related work, such as ada-KV , dynamic KV, etc.

Questions for authors

see weakness

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

The paper studies how many cached keys sparse attention should attend to at each decode step, treating this separately from which keys to attend to. It first measures several sound score-bound filters (Quest page bounds, Louver's ball bounds, Cauchy-Schwarz projection bands) and finds that they admit a large fraction of the cache at top-k thresholds. It then proposes CalibKV, a per-query selection method that keeps the full KV cache. An offline low-rank query subspace and a bank of calibration queries are used at prefill to estimate a per-head budget from the request's keys. At decode, the current query scores all keys exactly and attends to the top-budget keys plus sink, recent and outlier keys. A cheaper rank-m variant instead screens keys with approximate scores before exact reranking. The paper also gives a conformal-style coverage result under an exchangeability assumption. 

Experiments cover teacher-forced NLL on book passages, needle retrieval, LongBench, RULER and MATH-500 on models from 7B to 70B. The exact-score path stays close to Dense in quality, and its budget fraction decreases as context grows. Its single-layer attention time is lower than Dense at long contexts, but end-to-end time is slightly higher because of the extra prefill calibration and full-cache scoring at decode.

Critical strengths
  1. Separating "how many" keys to attend to from "which" keys, with a budget set per request and per head, is a sensible idea, and the budget behaves as expected. It shrinks as the context grows (from about 31% to 2% of the cache on Llama-8B) while quality stays close to Dense, and it does not force sparsity where it hurts: on MATH-500 it keeps nearly the full cache and matches Dense, while fixed top-128 methods drop noticeably. I see this as the main strength of the paper.
Critical weaknesses
  1. The method does not reduce cost. CalibKV keeps the full KV cache, and at each decode step it still scores all keys exactly before selecting the top BhB_h, so key reads and QK computation are the same as Dense; only softmax and value aggregation are reduced. Prefill also adds the calibration step. As a result, end-to-end time is higher than Dense at all tested lengths (Table 3). The cheaper rank-m path is not timed, has clearly worse quality, and under GQA does not even read fewer bytes at the rank used (Theorem 3). Since saving compute or memory is the purpose of sparse attention, this is the main reason for my score.

  2. The budget BhB_h is not well motivated as a measure of how many keys attention needs. By construction, it grows with the approximation error: if the subspace were exact (m = d), the residual allowance would be zero and BhB_h would fall to k = 128, turning the method into the top-128 Oracle, which has worse quality in Table 1. This suggests that the budget is driven mainly by how inexact the rank-64 approximation is, rather than by the attention demand of the request. The budget also depends heavily on the source of the calibration queries (Section 4.3). More importantly, the paper does not directly show that BhB_h is the right size. For example, it does not report how much of the Dense attention weight is covered by the selected BhB_h keys, or the attention-output error at BhB_h compared with fixed budgets.

  3. There are no results with larger budgets for top-k selection. Oracle (exact top-k), Quest and Louver all attend to only 128 keys per step, while CalibKV attends to up to a few thousand. I could not find results for exact top-K with a larger K, especially K equal to CalibKV's average budget, so it is unclear whether the gains come from the estimated budget or simply from attending to more keys.

Questions for authors
  1. The exact-score path still scores every key and keeps the full KV cache, so I don't see where a real speedup could come from. Have you timed the rank-m path? What about KV memory and batch size > 1?

  2. How do you know BhB_h is enough? I would like to see how much of the dense attention weight the selected BhB_h keys cover, or the attention output error, compared with fixed budgets.

  3. Can you add exact top-K with larger K (e.g., 512 to 4K), and especially K equal to CalibKV's average budget? Right now all top-k baselines use 128 keys, so it's hard to tell whether the gain comes from the estimated budget or just from attending to more keys.

  4. Where do the calibration queries for LongBench, RULER and MATH-500 come from? Same bank as the book experiments, or one per task?

  5. On MATH-500 the budget is 99.87%. Is this mostly heads falling back to dense?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.