- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper tackles query-aware sparse attention for long-context LLM decoding. The authors observe that existing methods address the problem in two decoupled stages: blocks are first selected by predicted attention mass, and the omitted "tail" is only then compensated. The key insight of this paper is that selection should account for reconstructability: a high-mass block with near-constant logits is well approximated by mean compensation, while a lower-mass block with high within-block logit variation leaves a larger residual, so exact-read budget should prioritize the latter. The paper formalizes this under block-mean compensation: the KL divergence between compensated and full attention reduces to a log-partition gap and a second-order expansion shows each omitted block's contribution is approximately attention mass × logit variance. This yields a Top-K selection rule. Since exact mass/variance require reading all keys, CompKV estimates both from compact per-block statistics (mean key/value plus r grouped key-variance statistics) and scores blocks. An asynchronous CPU-offload implementation overlaps compensation with KV gathering and exact attention. Experimental results on multiple benchmarks show CompKV achieving the best average scores among the sparse baselines (Quest, InfLLM, Quest+RESA), with up to 6.85× single-layer attention speedup over full attention.
Critical strengths
- The paper is well-written and easy to follow.
- The idea of this paper is novel and interesting. The selection–compensation mismatch is valid and well illustrated.
- Multiple experiments on three different LLM models and two benchmarks are conducted. Extensive studies are performed: matched block size/sink/window/budget across methods, per-factor ablations, budget sweeps, latency and so on.
- Non-trivial engineering. The asynchronous CPU-offload pipeline (overlapping compensation with KV gather/transfer/exact attention on separate streams) is a real implementation contribution.
Critical weaknesses
- The paper's central narrative outruns its own ablations. The "compensation-aware selection" story claims the σ² factor drives the wins, but Table 3 and Appendix B.1 jointly imply the coupling contributes at most ~1 point of CompKV's 5–15 point lead over Quest+RESA; the remainder is attributable to the variance-corrected mass estimator and the mean compensator. The headline gains appear driven by better mass estimation and by adding compensation, not by the selection–compensation coupling the paper sells.
- The theory's regime contradicts the method's behavior. The derivation requires → 0 with fixed block size, yet the criterion deliberately selects the largest-σ² blocks — precisely where the second-order expansion and the −log(1−R) ≈ R linearization are least reliable. The paper never checks whether real blocks satisfy the regime (distribution of , magnitude of on selected blocks). 3.The main comparisons confound selection with compensation. Quest has no compensator, so CompKV-vs-Quest bundles "better selection" with "adding compensation." Quest+RESA doesn't resolve this because RESA is a different compensator (low-rank logit prior vs. mean summaries). The decisive ablation — Quest-style mass selection + CompKV's mean compensation — is absent, so neither contribution is isolated.
- Quest+RESA, the closest conceptual competitor, is excluded from latency on the basis of a citation, not a measurement. The 6.85× speedup is over CPU-offload full attention that re-transfers the entire KV cache per step.
Questions for authors
- Real attention is typically peaky. Is CompKV pactically useful? If mass is concentrated, ranking by p·σ² ≈ ranking by p; if mass is diffuse, selection itself matters little.
- What is the empirical distribution of ? Is the small-variance regime satisfied on the blocks CompKV actually selects?
- On what fraction of (query, layer, head) triples does residual-based ranking disagree with mass-based ranking, and how much of the total accuracy gain comes from those cases? This directly tests the regime story in Weakness 1.
- Please add the missing ablation: mass-based (Quest-style) selection + mean compensation, to isolate the selection contribution. Your Table 3 suggests the σ² factor is worth 0.4–0.9 points — please confirm against a mass-selection baseline with the same compensator.
- Please measure Quest+RESA latency directly instead of citing the original paper.
13 comments
Response to Reviewer LTnX (2/5): Weaknesses 2–3
Weakness 2: The theory's regime contradicts the method's behavior. The derivation requires , yet the criterion selects the largest-σ² blocks, where the second-order expansion and the linearization are least reliable, and the paper does not check the distribution of or the magnitude of .
σ is not small on real blocks, so the literal regime does not hold. The criterion, however, does not rely on this regime and does not target the largest-σ² blocks. New Appendix B.3 reports the measured σ (Llama-3.1-8B-Instruct on the states of Appendix B, CompKV with at 512):
| Block role | Blocks | Mass | Residual | Median σ, by count | Median σ, residual-weighted |
|---|---|---|---|---|---|
| Mandatory (sink + 2 recent) | 0.15% | 67.5% | 70.2% | 1.78 | 2.98 |
| Selected by CompKV | 1.45% | 15.0% | 14.0% | 1.39 | 2.11 |
| Unselected (Mean) | 98.4% | 17.5% | 15.8% | 1.41 | 1.92 |
A 256-token budget gives nearly the same statistics. At such σ, the fraction that Mean leaves unrecovered is at most 1, whereas already approaches 1 at the median, so the expansion is not a numerical approximation of the residual. We use it only to obtain a ranking score, whose fidelity is measured below.
The criterion does not target the largest σ. The score is mass times variance. Selected and unselected blocks have nearly the same σ (median 1.39 vs. 1.41). Mass separates them: selected blocks are 1.45% of all blocks but carry 15.0% of the mass. The largest σ occur in the mandatory blocks, which are always read exactly and never ranked.
Only one step of the derivation needs small σ (revised Section 3.2):
- One head, exact. with , and does not depend on . Since is increasing, Top-K by exact is optimal for any logits, without any expansion. Under Drop, the same argument yields Top-K by mass (Appendix A.5).
- Shared selection under GQA. Ranking by exactly minimizes . The linearization acts on each head's total unselected residual, not on individual blocks, and drops only the relative head weights . sums over unselected blocks only, and since , it is at most the unselected mass, 17.5% on average ().
- Estimable form. Only this step uses , to turn the residual into a quantity that mean keys and grouped variances can estimate.
The cost of this step is measured directly. Appendix B.2 compares the scores with exact residual ranking, which involves no expansion. At , CompKV reaches a Spearman correlation of 0.86 and a residual capture of 81.5%, against 0.85 and 81.2% for the estimated mass from the same statistics, and its capture is higher in seven of eight layer means. At , CompKV reaches 0.88 and 85.6%. Appendix B.1 uses the exact KL, logarithm included.
Revisions. Section 3.2 is rewritten into these three steps, Appendices A.2 and A.3 restrict the expansion condition to the unselected blocks of a given selected set, and new Appendix B.3 (Table 5, Figure 7) reports σ and states that the expansions serve only to rank blocks.
Weakness 3: The main comparisons confound selection with compensation, and the decisive ablation, Quest-style mass selection with CompKV's Mean compensation, is missing.
The revised Table 3 includes Quest+Mean, which keeps Quest's min/max scores, summed within each KV group, and replaces RESA with our Mean compensator. All other settings match CompKV (Appendix C.3). The full table is in our response to Weakness 1. The two comparisons that separate the factors are (AVG for Llama 256/512 and Qwen3-8B 256/512):
- Same compensator, different selection. Quest+Mean → CompKV: +6.4/+5.1/+21.6/+8.5. On MK3 at 512, accuracy rises from 29.2/6.0 to 73.0/75.0 (Llama/Qwen3-8B).
- Same selection, different compensation. Quest → Quest+Mean: +1.1/+1.0 at 512 (Llama/Qwen3-8B); only → +Mean: +2.5/+1.0/+0.5/+1.6. Under Quest's selection, replacing RESA with Mean changes AVG by only −0.1/+1.7 at 512.
Both contributions are positive, and selection contributes considerably more. The revisions are those listed for Weakness 1.
Response to Reviewer LTnX (3/5): Weakness 4
Weakness 4: Quest+RESA is excluded from the latency evaluation by citation rather than measurement, and the 6.85× speedup is measured against CPU-offloaded full attention that transfers the entire KV cache at every step.
The revision measures Quest+RESA directly and adds GPU-resident KV alongside CPU offload, reporting single-layer attention and end-to-end decoding for both placements. The sentence excluding Quest+RESA by citation is removed. Setup (Appendix E.2): Llama-3.1-8B-Instruct on one H100, batch size 1, 256-step decoding windows, and 3 seeds × 5 independent processes per case. All methods share one FlashInfer kernel for exact attention, the sparse methods share one radix Top-K kernel, and Quest+RESA uses λ = 0.25 with the prior built from prefill query and key means.
Single-layer attention latency (µs at a 512-token budget; Tables 7 and 8 cover 256–2,048):
| KV placement | Context | Full | Quest | Quest+RESA | CompKV |
|---|---|---|---|---|---|
| GPU-resident | 32K | 68.4 | 39.1 | 39.1 | 35.5 |
| GPU-resident | 64K | 118.7 | 47.8 | 47.8 | 42.3 |
| GPU-resident | 128K | 216.0 | 64.8 | 64.8 | 55.4 |
| CPU offload | 32K | 2547 | 598 | 657 | 535 |
| CPU offload | 64K | 5034 | 913 | 974 | 842 |
| CPU offload | 128K | 9991 | 1545 | 1616 | 1469 |
Quest+RESA matches Quest with GPU-resident KV (at most 6% slower) and is 3–18% slower under offload, where its prior must be appended, read, and merged. Across budgets of 256–2,048, CompKV is 1.09–1.18× faster than Quest+RESA with GPU-resident KV and 1.09–1.27× under offload.
End-to-end decoding (TPOT in ms at 512, all 32 layers using the method; Table 9):
| KV placement | Context | Full | Quest | Quest+RESA | CompKV |
|---|---|---|---|---|---|
| GPU-resident | 32K | 10.34 | 9.28 | 9.31 | 9.35 |
| GPU-resident | 64K | 11.95 | 9.61 | 9.70 | 9.60 |
| GPU-resident | 128K | 14.96 | 10.29 | 10.35 | 10.00 |
| CPU offload | 32K | 89.77 | 26.66 | 27.15 | 23.08 |
| CPU offload | 64K | 169.84 | 36.85 | 37.33 | 33.00 |
| CPU offload | 128K | 329.56 | 57.12 | 57.50 | 52.89 |
CompKV is slower only with GPU-resident KV at 32K, where it trails Quest by 0.8% and Quest+RESA by 0.4% because of its costlier per-step summary update (Appendix E.3).
The 6.85× speedup. Dense decoding reads the entire KV cache at every step, so under offload Full must transfer all of it. This cost is inherent, not a choice of our implementation. Offloading is needed precisely when the cache does not fit: at 128K with batch size 4, the KV cache alone takes 64 GiB, and with about 15 GiB of BF16 weights, an 80 GB H100 has less than 1 GiB left for activations and workspaces. Remeasured, the speedup is 6.80×. Because this number does not describe the case where the cache fits, the revision adds GPU-resident results: CompKV is 1.74–3.93× faster than FlashInfer dense decoding per layer and 1.11/1.24/1.50× faster per step at 32K/64K/128K, rising to 1.77× at 128K with two sequences (Table 10). About 8.3 ms per step of non-attention computation, identical across methods, dilutes the end-to-end speedup.
Revisions. Section 5.3 and Figure 4 cover both placements and include Quest+RESA; the abstract reports up to 3.9× per layer with GPU-resident KV and 6.8× under offload, and the introduction adds 1.5× and 6.2× per step; Appendices E.2, E.3, and E.5 give the full results.
Response to Reviewer LTnX (1/5): Weakness 1
We thank the reviewer for the careful review. Several of the concerns can be tested directly by experiment, so we added a mass-based baseline with the same compensator, a score without within-block variance, measurements of σ and Rg, the disagreement rate between the two exact rankings, and direct latency measurements of Quest+RESA. The main changes in the revised PDF are marked in blue.
The original ablations were incomplete, which made this reading reasonable. With the missing comparisons added, the lead does not come from the compensator but from within-block variance in the score, and the ~1 point is the marginal gain of one of its two uses.
Both uses of variance belong to one residual estimate. CompKV estimates the post-compensation residual ρg,b=pg,b(1−∣b∣ezˉg,b/Zg,b), the block's mass times the fraction that Mean fails to recover. The outer σ2 estimates this fraction. The mass factor needs the variance as well: the mean-key weight ∣b∣ezˉg,b is exactly the part of Zg,b that Mean recovers, so p(1) underestimates the mass most for the blocks that Mean reconstructs worst, which are the blocks the residual should select. The correction in p(2) removes this bias. We do not claim that it helps only under Mean, since p(2) only already beats Quest. Our claim is that within-block variance comes from the residual analysis and that existing selectors do not maintain it.
The decisive ablations therefore remove both uses (p(1)+Mean) and fix the compensator under Quest's selection (Quest+Mean). The revised Table 3 adds both rows. All rows except p(2) only share the Mean compensator, exact-attention path, mandatory blocks, and budgets (MK3 columns: Llama / Qwen3-8B):
Changing one factor at a time:
Appendix B.1 compares two oracles, exact mass and exact residual ranking on the same Full states, without σ2, and measures per-step local error. It therefore cannot be combined with Table 3 into an upper bound on the effect of variance. It shows that, without estimation error, residual ranking lowers attention KL in every task and layer (by 0.42% and 0.66% at 256 and 512).
Revisions. Table 3 adds the two rows, with a caption on the compensator; Appendix C.3 specifies both variants and lists MK3 for all rows; Section 5.4 reports the same-compensator comparisons, the removal of both uses of variance, and the two increments; Section 5.2 cites Quest+Mean for MK3.