acceptodds
Under review as a conference paper at ICLR 2027

CompKV: Compensation-Aware KV Selection for Long-Context LLM Inference

Abstract

Despite their strong performance, large language models (LLMs) are bottlenecked by KV cache memory traffic during long-context inference. Sparse attention is widely used to accelerate LLM inference by computing exact attention over a selected subset of tokens. To recover the contribution of tokens excluded from exact attention, recent methods apply coarse-grained compensation to the omitted attention tail. However, existing methods typically select tokens based on attention mass and only then compensate for the unselected tokens. This decoupled design overlooks their interaction: selection should prioritize tokens that would leave the largest compensation error if omitted. To address this limitation, we introduce CompKV, the first compensation-aware sparse attention framework that divides tokens into blocks and explicitly optimizes selection for the downstream compensation mechanism. Our theoretical analysis shows that the residual left by block-level mean compensation is governed by both block attention mass and within-block logit variation. We approximate this residual using compact block-level statistics, yielding a deployable selection criterion. We further develop an efficient asynchronous implementation. Experiments on RULER and LongBench-Pro show that CompKV performs best among the evaluated sparse baselines while delivering up to a self-attention speedup over full attention.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Efficient LLM Inference, Sparse Attention, KV cache

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 3 reviews, above 85% of the others.
Reviewer_LTnXOpenReview ↗
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
  1. The paper is well-written and easy to follow.
  2. The idea of this paper is novel and interesting. The selection–compensation mismatch is valid and well illustrated.
  3. 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.
  4. 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
  1. 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.
  2. The theory's regime contradicts the method's behavior. The derivation requires σg,bσ_{g,b} → 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 σg,bσ_{g,b}, magnitude of RgR_g 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.
  3. 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
  1. 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.
  2. What is the empirical distribution of σg,bσ_{g,b}? Is the small-variance regime satisfied on the blocks CompKV actually selects?
  3. 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.
  4. 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.
  5. Please measure Quest+RESA latency directly instead of citing the original paper.
13 comments
AuthorsOpenReview ↗

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 RgR_g, 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.


Weakness 1: The central narrative outruns the ablations. Table 3 and Appendix B.1 suggest that the selection–compensation coupling contributes at most ~1 point of CompKV's 5–15-point lead over Quest+RESA, with the rest attributable to the variance-corrected mass estimator and the Mean compensator.

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)\rho_{g,b}=p_{g,b}(1-|b|e^{\bar z_{g,b}}/Z_{g,b}), the block's mass times the fraction that Mean fails to recover. The outer σ^2\widehat\sigma^2 estimates this fraction. The mass factor needs the variance as well: the mean-key weight ∣b∣ezˉg,b|b|e^{\bar z_{g,b}} is exactly the part of Zg,bZ_{g,b} that Mean recovers, so p^(1)\widehat 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)\widehat p^{(2)} removes this bias. We do not claim that it helps only under Mean, since p^(2)\widehat 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)\widehat 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)\widehat p^{(2)} only share the Mean compensator, exact-attention path, mandatory blocks, and budgets (MK3 columns: Llama / Qwen3-8B):

Selection + compensatorLlama 256Llama 512Qwen3-8B 256Qwen3-8B 512MK3 at 256MK3 at 512
Quest + RESA72.078.253.575.87.6 / 0.029.4 / 4.8
Quest + Mean72.278.159.377.57.4 / 0.029.2 / 6.0
p^(1)\widehat p^{(1)} + Mean74.080.075.582.325.2 / 19.655.4 / 43.2
p^(1)σ^2\widehat p^{(1)}\widehat\sigma^2 + Mean76.181.277.583.831.8 / 25.661.0 / 54.0
p^(2)\widehat p^{(2)} + Mean78.182.879.785.139.0 / 32.270.4 / 65.4
CompKV78.683.280.986.041.4 / 41.273.0 / 75.0
p^(2)\widehat p^{(2)} only (no compensation)75.681.879.283.529.0 / 25.063.6 / 43.4

Changing one factor at a time:

ChangeLlama 256Llama 512Qwen3-8B 256Qwen3-8B 512
(a) RESA → Mean, Quest selection+0.2−0.1+5.8+1.7
(b) Quest bound → p^(1)\widehat p^{(1)}, no variance+1.8+1.9+16.2+4.8
(c) add within-block variance: p^(1)\widehat p^{(1)}+Mean → CompKV+4.6+3.2+5.4+3.7
Total: CompKV over Quest+RESA+6.6+5.0+27.4+10.2
  • The compensator does not explain the lead. Step (a) is −0.1/+1.7 at 512, and the +5.8 for Qwen3-8B at 256 occurs where Quest's selection itself fails (59.3 even with Mean, versus 80.9 for CompKV). Quest+RESA already compensates, so the lead over it comes from the selection score: with Mean fixed, CompKV leads Quest+Mean by 5.1–21.6 points, and by 43.8/69.0 on MK3 at 512.
  • Within-block variance is the main source. Step (c) is the largest step on Llama at both budgets and is worth 16.2–31.8 points on MK3. On Qwen3-8B, step (b) dominates at 256, where Quest's selection fails, and the two are comparable at 512 (4.8 vs. 3.7).
  • The ~1 point is the gain of the outer factor once the mass is corrected: 0.4–1.2 points on average, positive in all four settings, and 2.4–9.6 on MK3. Correcting the mass on top of p^(1)σ^2\widehat p^{(1)}\widehat\sigma^2+Mean adds 2.0–3.4 points, and the two uses together give step (c).

Appendix B.1 compares two oracles, exact mass and exact residual ranking on the same Full states, without σ^2\widehat\sigma^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.

AuthorsOpenReview ↗

Response to Reviewer LTnX (2/5): Weaknesses 2–3

Weakness 2: The theory's regime contradicts the method's behavior. The derivation requires σg,b→0\sigma_{g,b}\to0, yet the criterion selects the largest-σ² blocks, where the second-order expansion and the linearization −log⁡(1−R)≈R-\log(1-R)\approx R are least reliable, and the paper does not check the distribution of σg,b\sigma_{g,b} or the magnitude of RgR_g.

σ is not small on real blocks, so the literal σ→0\sigma\to0 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 r=4r=4 at 512):

Block roleBlocksMassResidualMedian σ, by countMedian σ, residual-weighted
Mandatory (sink + 2 recent)0.15%67.5%70.2%1.782.98
Selected by CompKV1.45%15.0%14.0%1.392.11
Unselected (Mean)98.4%17.5%15.8%1.411.92

A 256-token budget gives nearly the same statistics. At such σ, the fraction that Mean leaves unrecovered is at most 1, whereas 12σ2\tfrac12\sigma^2 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):

  1. One head, exact. L=−log⁡(1−Rg)\mathcal L=-\log(1-R_g) with Rg=∑b∉Sρg,bR_g=\sum_{b\notin\mathcal S}\rho_{g,b}, and ρg,b\rho_{g,b} does not depend on S\mathcal S. Since −log⁡(1−R)-\log(1-R) is increasing, Top-K by exact ρ\rho is optimal for any logits, without any expansion. Under Drop, the same argument yields Top-K by mass (Appendix A.5).
  2. Shared selection under GQA. Ranking by ∑gρg,b\sum_g\rho_{g,b} exactly minimizes ∑gRg\sum_g R_g. The linearization acts on each head's total unselected residual, not on individual blocks, and drops only the relative head weights 1/(1−Rg)1/(1-R_g). RgR_g sums over unselected blocks only, and since ρ≤p\rho\le p, it is at most the unselected mass, 17.5% on average (1/(1−R)=1.211/(1-R)=1.21).
  3. Estimable form. Only this step uses ρ≈12pσ2\rho\approx\tfrac12p\sigma^2, 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 r=4r=4, 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 p^(2)\widehat p^{(2)} from the same statistics, and its capture is higher in seven of eight layer means. At r=128r=128, 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); p^(2)\widehat p^{(2)} only → p^(2)\widehat p^{(2)}+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.

AuthorsOpenReview ↗

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 placementContextFullQuestQuest+RESACompKV
GPU-resident32K68.439.139.135.5
GPU-resident64K118.747.847.842.3
GPU-resident128K216.064.864.855.4
CPU offload32K2547598657535
CPU offload64K5034913974842
CPU offload128K9991154516161469

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 placementContextFullQuestQuest+RESACompKV
GPU-resident32K10.349.289.319.35
GPU-resident64K11.959.619.709.60
GPU-resident128K14.9610.2910.3510.00
CPU offload32K89.7726.6627.1523.08
CPU offload64K169.8436.8537.3333.00
CPU offload128K329.5657.1257.5052.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.

Reviewer_JgyaOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes CompKV, a compensation-aware sparse attention method for efficient long-context LLM inference. Unlike conventional methods that primarily select KV blocks based on attention mass, CompKV prioritizes blocks that are difficult to reconstruct through mean compensation.

The authors provide a theoretical analysis showing that the compensation residual depends on both attention mass and within-block logit variance. Based on this observation, they develop a selection criterion using compact block-level statistics and an asynchronous CPU-offload implementation.

Experiments on RULER and LongBench-Pro across three language models demonstrate consistent improvements over the evaluated sparse attention baselines, with up to a 6.85× speedup in CPU-offloaded attention computation.

Critical strengths
  1. Interesting motivation. The paper introduces a meaningful perspective on sparse attention by considering the interaction between KV selection and downstream compensation, rather than treating them as independent components.

  2. Solid theoretical motivation. The proposed selection criterion is supported by a detailed mathematical derivation, providing a principled explanation for incorporating both attention mass and logit variance.

  3. Promising experimental results. CompKV achieves strong performance across different models and long-context benchmarks. The authors also provide efficiency measurements and ablation studies to evaluate the proposed components.

Critical weaknesses
  1. Complexity versus practical benefits. The method introduces several approximations and additional components, including grouped variance estimation, second-order attention-mass estimation, mean compensation, and an asynchronous execution pipeline. While these components are individually motivated, the overall method is relatively complex. In particular, the ablation results suggest that the independent improvement from compensation-aware selection over a simpler mass-based selection with the same compensation mechanism is relatively modest. I am not fully convinced that the additional complexity is justified by the incremental gains.

  2. Potential limitations of the theoretical approximations. The proposed selection criterion relies on a second-order approximation of the compensation residual and a grouped diagonal approximation of key covariance. Moreover, the theoretical objective focuses on attention distribution divergence rather than the final attention output error, which also depends on the value vectors. Although the empirical results are promising, it remains unclear how robust these approximations are across different attention distributions and deployment scenarios.

  3. Limited evaluation of general deployment efficiency. The reported efficiency improvements are measured in a CPU-offload, single-layer attention setting with batch size one. While these measurements include the relevant attention and data-transfer operations, they do not directly establish end-to-end inference speedups. Given the additional implementation complexity, a broader evaluation of practical deployment performance would strengthen the paper.

Questions for authors
  1. The ablation studies show that compensation-aware selection provides relatively modest improvements over estimated attention-mass selection with mean compensation. Could the authors further clarify whether these gains justify the additional complexity, particularly in terms of the accuracy–latency trade-off?

  2. Since the theoretical criterion is based on attention KL divergence and logit variance, how well does it correlate with the actual attention output error? Have the authors considered the effect of within-block value variation or the limitations of the small-variance approximation?

  3. Could the authors provide end-to-end inference throughput or latency results across different batch sizes and context lengths? It would also be interesting to understand how CompKV performs when the KV cache is GPU-resident rather than CPU-offloaded.

8 comments
AuthorsOpenReview ↗

Response to Reviewer Jgya (1/5): Weakness 1

We thank the reviewer for the careful assessment. All three concerns can be tested by experiment, so we added same-compensator baselines whose scores use no within-block variance, measured σ on real blocks and the correlation of attention KL with the actual output error, and extended the efficiency evaluation to GPU-resident KV, end-to-end decoding, and batch sizes up to 8. The main changes in the revised PDF are marked in blue.


Weakness 1: The method adds grouped variance estimation, second-order mass estimation, mean compensation, and an asynchronous pipeline, and the ablations suggest only modest gains over simpler mass-based selection with the same compensation, so the complexity may not be justified.

We agree that once the mass estimate includes the second-order correction (p^(2)\widehat p^{(2)}), the outer σ^2\widehat\sigma^2 factor adds only 0.4–1.2 points on average. That increment, however, is not what the listed components pay for: p^(2)\widehat p^{(2)}+Mean already uses the grouped variances, the second-order mass estimate, and Mean compensation, and the outer factor adds one multiplication per (head, block). A selector that avoids this complexity must use no within-block variance, and the revised Table 3 adds two such baselines. All rows below share CompKV's Mean compensator, exact-attention path, block size, mandatory blocks, and budgets:

Score (+ Mean)Llama 256Llama 512Qwen3-8B 256Qwen3-8B 512MK3 at 256MK3 at 512
Quest (min/max bound)72.278.159.377.57.4 / 0.029.2 / 6.0
p^(1)\widehat p^{(1)} (mean-key mass)74.080.075.582.325.2 / 19.655.4 / 43.2
p^(1)σ^2\widehat p^{(1)}\widehat\sigma^276.181.277.583.831.8 / 25.661.0 / 54.0
p^(2)\widehat p^{(2)} (variance-corrected mass)78.182.879.785.139.0 / 32.270.4 / 65.4
CompKV (p^(2)σ^2\widehat p^{(2)}\widehat\sigma^2)78.683.280.986.041.4 / 41.273.0 / 75.0

The first two scores use no within-block variance. Removing both of its uses (p^(1)\widehat p^{(1)}+Mean) costs 3.2–5.4 AVG points and 16.2–31.8 MK3 points; using Quest's bound as well costs 5.1–21.6 in total, with MK3 at 512 falling from 73.0/75.0 to 29.2/6.0.

Both uses of the variance belong to one residual estimate. CompKV estimates the post-compensation residual ρg,b=pg,b(1−∣b∣ezˉg,b/Zg,b)\rho_{g,b}=p_{g,b}(1-|b|e^{\bar z_{g,b}}/Z_{g,b}), the block's mass times the fraction that Mean fails to recover. The outer σ^2\widehat\sigma^2 estimates this fraction. The mass factor needs the variance as well: the mean-key weight ∣b∣ezˉg,b|b|e^{\bar z_{g,b}} is exactly the part of Zg,bZ_{g,b} that Mean recovers, so p^(1)\widehat 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)\widehat p^{(2)} removes this bias. The modest increment is therefore the marginal gain of the outer factor once the mass is corrected (0.4–1.2 points, and 2.4–9.6 on MK3); conversely, correcting the mass on top of p^(1)σ^2\widehat p^{(1)}\widehat\sigma^2+Mean adds 2.0–3.4. Within-block variance comes from this residual analysis, and existing selectors do not maintain it.

Runtime cost.

  • The score is one formula, Sb=∑gp^g,bσ^g,b2S_b=\sum_g\widehat p_{g,b}\widehat\sigma^2_{g,b}: each query head computes σ^g,b2\widehat\sigma^2_{g,b} once from r=4r=4 grouped key variances and uses it in the exponent of p^g,b\widehat p_{g,b} and as the outer factor. The scorer reads d+r+1d+r+1 scalars per block, versus 2d2d for Quest, so scoring takes 5.0 vs. 8.4 µs at 32K and 12.2 vs. 32.3 µs at 128K. Relative to p^(2)\widehat p^{(2)} selection, the outer factor adds one multiplication per (head, block) and reads no extra data.
  • Summaries take 1,044 bytes per block and KV head, versus 1,024 for Quest's min/max; they are built once after prefill in under 1% of that layer's dense prefill attention, and decoding updates only the active block.
  • The asynchronous pipeline is not part of the selection method: both placements run the same kernels, and the pipeline only moves the transfer of mean values off the critical path under offload.

No latency is traded for this. CompKV has the lowest single-layer attention latency of all methods in all 24 measured settings. Please see Question 1 for the accuracy–latency comparison.

Revisions. Table 3 adds Quest+Mean and p^(1)\widehat p^{(1)}+Mean, Appendix C.3 specifies both variants and lists MK3 for all rows, and Section 5.4 reports the same-compensator comparisons and both increments, the larger one from correcting the mass. Sections 4.1–4.3 and Appendices E.4–E.5 cover the reuse of σ^2\widehat\sigma^2, the summary size and construction cost, and the stage breakdown.

AuthorsOpenReview ↗

Response to Reviewer Jgya (2/5): Weakness 2

Weakness 2: Potential limitations of the approximations. The criterion relies on a second-order approximation of the compensation residual and a grouped diagonal approximation of key covariance, and the objective is attention-distribution divergence rather than the output error, which also depends on the values. How robust these approximations are across attention distributions and deployments remains unclear.

The approximations are not exact on real blocks: the median σ of unselected blocks is 1.41, and at such σ the second-order expansion is not a numerical approximation of the residual, as new Appendix B.3 states. The selection principle, however, does not rely on the expansion; the combined loss of the expansion, the grouped diagonal approximation, and the compression into rr statistics is measured against exact residual ranking; and the KL objective bounds the output error for any value vectors, with a measured correlation of 0.81.

Where each approximation enters.

  1. One head, exact. L=−log⁡(1−Rg)\mathcal L=-\log(1-R_g) with Rg=∑b∉Sρg,bR_g=\sum_{b\notin\mathcal S}\rho_{g,b}, and ρg,b\rho_{g,b} does not depend on the selected set S\mathcal S. Since −log⁡(1−R)-\log(1-R) is increasing, Top-K by the exact residual is optimal for any logits, with no small-variance assumption.
  2. Shared selection under GQA. Ranking by ∑gρg,b\sum_g\rho_{g,b} exactly minimizes ∑gRg\sum_gR_g. The linearization acts on each head's total unselected residual and drops only the relative head weights 1/(1−Rg)1/(1-R_g). Since ρ≤p\rho\le p, RgR_g is at most the unselected mass, 17.5% on average at 512, i.e. 1/(1−R)=1.211/(1-R)=1.21.
  3. Estimable form. Only this step uses ρ≈12pσ2\rho\approx\tfrac12p\sigma^2 and the grouped diagonal covariance, to turn the residual into a quantity that mean keys and rr grouped variances can estimate.

The loss of step 3 is measured directly, in appendix B.2, already in the original submission. The reference is exact residual ranking by Tb=∑gρg,bT_b=\sum_g\rho_{g,b}, which involves no Taylor expansion. At r=4r=4, CompKV reaches a Spearman correlation of 0.86, and its selected blocks carry 81.5% of the residual that exact residual selection captures; the estimated mass p^(2)\widehat p^{(2)}, computed from the same statistics, reaches 0.85 and 81.2%, and CompKV's capture is higher in seven of eight layer means. At r=128r=128, the per-coordinate diagonal, CompKV reaches 0.88 and 85.6%; the remaining gap combines expansion error and off-diagonal covariance. The effect of the grouping granularity is also measured: accuracy generally improves with larger rr, and r=4r=4 trails r=128r=128 by 1.87/1.08 points with 1/32 of the variance metadata.

Measured σ, new in Appendix B.3, Table 5, Figure 7. The criterion does not target the largest-variance blocks: selected and unselected blocks have almost the same σ distribution, and mass separates them, since 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, and the expansion enters only for unselected blocks, which carry 17.5% of each head's mass.

The KL objective and the output error. The Mean-compensated output is exactly EP^g[v]\mathbb E_{\widehat P_g}[v], so Pinsker's inequality gives ∥o^g−og∥2≤max⁡j∥vj−c∥22DKL(P^g∥Pg)\Vert\widehat o_g-o_g\Vert_2\le\max_j\Vert v_j-c\Vert_2\sqrt{2D_{\mathrm{KL}}(\widehat P_g\Vert P_g)} for any constant vector cc. The KL objective therefore bounds the output error for any values, whose dispersion enters only through the constant. Per query head, the measured Spearman correlation between KL and the relative output L2L_2 is 0.81, detailed in Question 2.

Across distributions and deployments. Without estimation error, exact residual ranking lowers KL relative to exact mass ranking in all 13 RULER tasks and all eight sampled layers. In accuracy, CompKV has the highest average among the evaluated sparse methods on RULER and on the 11 primary task types of LongBench-Pro (8K–128K) for all three models in Tables 1, 2, and remains best at most budgets of 128–1,024 tokens. Selection depends only on queries, keys, and summaries, so offloaded and GPU-resident layers select identical blocks. The diagnostics of Appendix B cover Llama-3.1-8B-Instruct only; for the Qwen3 models, the evidence is accuracy.

Revisions. Section 3.1 adds the Pinsker bound, and Section 3.2 is rewritten into the three steps above, citing the fidelity measured in B.2. Appendices A.2 and A.3 restrict the expansion condition to the unselected blocks of a given selected set, new Appendix A.6 derives the bound from attention KL to output error, and new Appendix B.3 reports σ and states that these deviations are not small, so the expansions serve only to rank blocks. B.1 adds the correlation between KL and output error.

AuthorsOpenReview ↗

Response to Reviewer Jgya (3/5): Weakness 3

Weakness 3: Limited evaluation of general deployment efficiency. The reported gains are measured in a CPU-offload, single-layer attention setting with batch size one, which does not directly establish end-to-end speedups; a broader evaluation of deployment performance would strengthen the paper.

We agree. The revision covers both KV placements, GPU-resident and CPU offload, single-layer attention and end-to-end decoding, and batch sizes from 1 to 8, with Quest+RESA and InfLLM measured directly. The single-layer offload speedup barely changes after remeasurement, while the GPU-resident and end-to-end speedups are smaller, and we report them as measured.

Setup. Pretrained Llama-3.1-8B-Instruct on one H100, 256-step decoding windows, and 3 seeds × 5 independent processes per case. Both placements run the same GPU kernels, and all methods share one FlashInfer kernel for exact attention.

Single layer. At a 512-token budget, CompKV is faster than Full by 1.92/2.81/3.90× with GPU-resident KV and by 4.76/5.98/6.80× under offload (32K/64K/128K). It has the lowest single-layer latency of all methods in all 24 settings in Tables 7 and 8.

End-to-end, batch size 1 in Table 9. Time per output token (TPOT) in ms, with all 32 layers using the method at a 512-token budget:

KVContextFullQuestQuest+RESAInfLLMCompKVFull/CompKV
GPU-resident32K10.349.289.3110.209.351.11×
GPU-resident64K11.959.619.7010.849.601.24×
GPU-resident128K14.9610.2910.3512.2310.001.50×
CPU offload32K89.7726.6627.1538.5923.083.89×
CPU offload64K169.8436.8537.3358.8633.005.15×
CPU offload128K329.5657.1257.5099.2652.896.23×
  • With GPU-resident KV, about 8.3 ms of non-attention computation per step, identical across methods, dilutes the end-to-end speedup; the longer the context, the larger the attention share and the speedup.
  • Under offload, Full transfers the entire KV cache in every layer and step, so the end-to-end speedup approaches the single-layer one.

Batched decoding. With GPU-resident KV, Full/CompKV grows with the batch size, reaching 1.77× at 128K with two sequences; see our response to Question 3.

Memory. With GPU-resident KV, CompKV uses only 14.2% more GPU memory than Full, mostly for FP32 summaries, and 1.5% more than Quest, detailed in Table 11.

Reported as measured. With GPU-resident KV at 32K, Quest has the lowest TPOT and CompKV is 0.8% slower, because of its costlier per-step summary update. For batch sizes above one, the sparse methods process the requests of a batch one after another within a single CUDA graph, as we have no multi-sequence sparse kernel. Batched decoding under offload, continuous batching, and integration into a serving framework are not covered.

Revisions. The abstract reports single-layer speedups of up to 3.9× with GPU-resident KV and 6.8× under offload, and the introduction also gives the per-step speedups of 1.5× and 6.2×. The conclusion keeps 3.9×/6.8× per layer and describes the end-to-end behavior qualitatively. Section 5.3 is rewritten and Figure 4 now covers both placements and includes Quest+RESA. Appendix E.1 gives the implementation, E.2 the protocol and all single-layer results, E.3 end-to-end and batched decoding, E.4 memory, and E.5 the stage breakdown.

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

The KV cache has become a major bottleneck for modern LLMs. Existing sparse attention methods treat block selection and compensation as independent processes. However, some blocks with high attention mass may be easy to compensate for, while others with lower attention mass may be difficult to compensate for. This paper proposes CompKV, which unifies block selection and compensation. By scoring blocks based on both variation and attention mass, CompKV selects blocks that are difficult to compensate for or have high value, and uses compensation for the rest. Combined with offloading, CompKV achieves high accuracy and faster inference.

Critical strengths
  • A solid theoretical analysis establishes the need for compensation-aware selection and provides a natural derivation of the scoring function.

  • Detailed evaluations demonstrate substantial performance gains.

  • The proposed method keeps additional overhead to a minimum.

Critical weaknesses
  • Missing important Quest+Mean-comp baseline
Questions for authors

Thanks for submitting the paper. The discussion in sections 3 and 4 is very solid and insightful. I appreciate that. However, I still have some concerns about the paper.

  1. What is the additional memory overhead of the block summaries, and how long does it take to compute them? Why is FP32 used?
  2. How does the CPU offloading component differ from HiSparse for DSA? Why is offloading necessary, and how important is it to achieving CompKV's performance gains? In evaluation, is full attention assumed to require transferring the entire KV cache from CPU memory to GPU memory?
  3. Why does the evaluation not compare CompKV against Quest + Mean-compensate?
  4. For GQA, top-K selection is performed after pooling the scores from different query heads. Could this leave some heads with too few relevant tokens?
  5. In the performance evaluation, why is CompKV faster than Quest despite doing more work?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 7y4V (1/3): Weakness 1 and Question 1

We sincerely thank the reviewer for the kind words on Sections 3 and 4 and for the concrete questions, which helped us add several comparisons that were missing from the original submission. We respond to each point below, and the main changes in the revised PDF are marked in blue.


Weakness 1: Missing the Quest+Mean-compensation baseline.

Thank you for pointing this out. This comparison should indeed be there, and we have added it to Table 3 of the revision. Quest+Mean keeps Quest's min/max scores and hands the unselected blocks to our Mean compensator. It shares CompKV's compensator and exact-attention path, as well as the block size, mandatory blocks, and budgets, so only the score differs. RULER-32K averages over the 13 tasks are:

Score (all + Mean)Llama 256Llama 512Qwen3-8B 256Qwen3-8B 512
Quest72.278.159.377.5
p^(1)\widehat p^{(1)} (mean-key mass, no within-block variance)74.080.075.582.3
CompKV78.683.280.986.0

With the same compensator, CompKV still leads Quest+Mean by 5.1–21.6 points. The gap is largest on MK3, where the distractor keys share the needle's format: at a 512-token budget, Quest+Mean scores 29.2 / 6.0 on Llama / Qwen3-8B, and CompKV scores 73.0 / 75.0. Conversely, replacing the compensator of Quest+RESA with Mean changes its score by only −0.1 / +1.7 at 512. On RULER-32K, CompKV's lead therefore comes mainly from selection rather than from the compensator. The middle row further splits the selection gain: estimating mass from mean keys alone, without the variance, already improves on Quest's bound, and adding the within-block variance gives another 3.2–5.4 points.


Question 1: What is the additional memory overhead of the block summaries, how long do they take to compute, and why is FP32 used?

  • Memory. Each block stores {∣b∣,kˉb,Dˉb,vˉb}\lbrace|b|,\bar k_b,\bar D_b,\bar v_b\rbrace per KV head, i.e., 2d+r+12d+r+1 scalars. With d=128d=128, r=4r=4, and FP32, this is 1,044 bytes, or 12.7% of the 8,192 bytes of BF16 K/V for the block's 16 tokens. Quest's FP32 min/max takes 1,024 bytes, so the two are comparable. With GPU-resident KV, CompKV's measured total GPU memory is 14.2% above Full, versus 12.5% for Quest (Appendix E.4, Table 11).
  • Time. Summaries are built once after prefill, taking 0.19–0.74 ms per layer from 32K to 128K, less than 1% of that layer's dense prefill attention. During decoding, only the current active block is updated, at about 7.0 µs per layer and step (Table 12).
  • FP32. It is mainly for precision, a conservative implementation choice rather than a requirement of the method. The score passes through exp⁡(zˉ+σ^2/2)\exp(\bar z+\widehat\sigma^2/2), so an error in the summaries becomes a multiplicative error in the mass estimate, and vˉ\bar v is accumulated with weights over thousands of blocks. Since the summaries are only about one eighth of the KV cache, we did not compress them. We have not yet ablated BF16 storage, which would reduce the overhead to about 6.4% and is a worthwhile optimization.
AuthorsOpenReview ↗

Response to Reviewer 7y4V (2/3): Questions 2–3

Question 2: How does the CPU offloading differ from HiSparse for DSA? Why is offloading necessary, and how important is it to CompKV's gains? Is Full attention assumed to transfer the entire KV cache from CPU to GPU memory?

  • Difference from HiSparse. HiSparse targets DSA-style models, whose sparse indexer is learned in training, and manages the KV cache at the system level: inactive KV stays in host memory, while the GPU keeps a hot buffer and swaps entries in on demand, without handling the unselected tokens. CompKV is a training-free selection-and-compensation method for pretrained dense-attention GQA models. Our offload pipeline is a reference implementation whose role is to keep the vˉ\bar v needed for compensation off the critical path. The two work at different levels and could in principle be combined, e.g., with a HiSparse-style hot buffer caching the blocks that CompKV selects, although we have not implemented this. Section 2 of the revision now discusses HiSparse.
  • Offloading is not a required part of CompKV. None of the accuracy results depend on where the KV cache resides: both placements run the same GPU kernels and, given the same inputs, select exactly the same blocks in every layer (Appendix E.1). Offloading targets settings where the KV cache does not fit in GPU memory. For Llama-3.1-8B at 128K, the BF16 KV cache alone is 16 GiB per sequence.
  • Full under offloading. Yes. With offloading, Full copies all valid KV pages to the GPU at every step, since dense attention on the GPU reads the entire KV cache at every step. You are right that reporting only this ratio overstates the gain, so the revision adds GPU-resident results, in which Full transfers nothing. At a 512-token budget, CompKV's single-layer attention is still 1.92–3.90× faster, and each end-to-end decoding step is 1.11–1.50× faster; under offloading, these become 4.76–6.80× and 3.89–6.23×. Offloading thus enlarges the ratio over Full, but CompKV's speedup does not depend on it. The abstract and introduction now report the two placements separately.

Question 3: Why does the evaluation not compare CompKV against Quest + Mean compensation?

The main table of the original submission included only published methods, and Quest+RESA is the published combination of Quest selection with compensation, so we did not construct Quest+Mean separately at the time. You are right, however, that separating the contributions of selection and compensation requires a same-compensator comparison. The revision adds it to Table 3 as an ablation; please see our response to Weakness 1 for the results.

AuthorsOpenReview ↗

Response to Reviewer 7y4V (3/3): Questions 4–5

Question 4: Under GQA, top-K selection is performed after pooling the scores of different query heads. Could this leave some heads with too few relevant tokens?

Thank you for this insightful question, which we had not measured in the original submission. It can happen, but the cost is small. A shared selection is a constraint of GQA itself: the query heads of a group read the same KV, and selecting per head would multiply the KV read under the same budget by up to GG. Quest and InfLLM also share the selection within a group. To mitigate the issue, we normalize the mass estimate within each head before summing over the group, so that heads with larger logit scales do not dominate the selection. Unselected blocks also pass through Mean compensation, so no head simply loses them.

To answer this question, we added Appendix B.4 on the same Llama states as Appendix B. It takes each head's own optimal selected set as the reference and measures how much the worst head in each group obtains. At a 512-token budget:

  • Sharing itself costs little: with the shared set chosen by the exact residual, the worst head reaches 86% of its own optimum on average, and only 4.4% of groups fall below one half.
  • The case you raised does occur: with CompKV, the worst head reaches 65% on average, and 24.8% of groups fall below one half.
  • Compared with unnormalized summation and the group maximum, per-head normalization is best for the worst head, though by a small margin (0.01–0.02). The remaining gap comes mainly from the estimation error of the r=4r=4 summaries rather than from pooling itself.

Question 5: In the performance evaluation, why is CompKV faster than Quest despite doing more work?

CompKV does more work in total, but its critical path is shorter. Scoring during decoding is memory-bound: per block, CompKV reads only the count, the mean key, and rr grouped variances, d+r+1=133d+r+1=133 scalars, whereas Quest reads the min and max keys, 2d=2562d=256 scalars. At 128K, scoring takes 12.2 vs. 32.3 µs (Appendix E.5, Table 12). Of the extra work, per-head normalization is fused into the selection kernel, and the Mean term runs on an auxiliary stream in parallel with selection and exact attention. The same idea applies under CPU offloading: Quest must wait for all of its min/max bounds to arrive before scoring, whereas CompKV first transfers only its selection statistics, about half of its summary bytes, and the transfer of vˉ\bar v overlaps with selection and CPU gathering.

CompKV is not faster everywhere, though. Its per-step summary update is more expensive (7.0 vs. 3.9–5.8 µs per layer), and this step lies outside the single-layer timing. In end-to-end decoding with GPU-resident KV, Quest therefore has a slightly lower TPOT at 32K (9.28 vs. 9.35 ms), while CompKV is faster at 128K (10.00 vs. 10.29 ms).


We sincerely thank you again for your thoughtful feedback. The Quest+Mean comparison and the GQA analysis have made the paper more complete. Hope our responses address your concerns, and we are happy to discuss any further questions, Thank you!

Comments on the paper

5 comments
AuthorsOpenReview ↗

Summary of the Discussion for the Area Chair

Dear Area Chair,

Thank you for handling our submission, and for encouraging the reviewers to join the discussion. We would like to briefly summarize where the discussion stands.

CompKV selects the KV blocks that the compensator cannot reconstruct well, rather than the blocks with the largest attention mass, and compensates the remaining blocks with their means.

What the reviewers valued. All three reviewers found the core idea well motivated. 7y4V wrote that the theoretical analysis "establishes the need for compensation-aware selection" and found the discussion in Sections 3 and 4 "very solid and insightful". Jgya called the interaction between selection and compensation "a meaningful perspective on sparse attention" with a principled derivation, and LTnX found the idea "novel and interesting" and the selection–compensation mismatch "valid and well illustrated". The reviewers also recognized the evaluation: 7y4V noted "substantial performance gains" with overhead kept to a minimum, Jgya noted strong results across models and long-context benchmarks, and LTnX highlighted the matched settings across methods, the per-factor ablations and budget sweeps. LTnX further described the asynchronous CPU-offload pipeline as "a real implementation contribution".

Resolved concerns. The three reviews raised largely the same questions, and we answered them with new experiments in the revised PDF. Reviewer LTnX engaged over two rounds, confirmed that most of the concerns are resolved, and raised the score to 3. These resolved points are also the main concerns of Reviewers 7y4V and Jgya:

  • Selection or compensation. All three reviewers asked for Quest-style selection with the same Mean compensator as CompKV, and the revision adds it together with a mass-based score that uses no within-block variance. With the compensator fixed, CompKV leads Quest by 5 to 22 points on RULER, while swapping RESA for Mean under Quest's selection barely changes its score. The gain therefore comes from selection, and removing within-block variance from the score alone already costs 3 to 5 points. This also answers Jgya's question on whether the added components pay off, since they all serve this one score. LTnX wrote that this ablation "settles it".
  • The small-variance approximation. We now report the measured within-block variance and state plainly that it is not small. The selection principle does not depend on this approximation: for a single head, ranking by the exact residual is optimal for any logits, and the expansion is used only to make the score estimable from compact statistics. The practical score still closely follows exact residual ranking, and attention KL tracks the actual output error, as detailed in Appendix B. LTnX considered this question settled.
  • Where the two rankings differ. LTnX asked whether residual ranking matters when attention is peaky. Outside the mandatory blocks, attention is diffuse, and residual and mass ranking choose different blocks in most cases. LTnX accepted this answer.
  • Efficiency beyond CPU offload. Jgya asked how CompKV performs when the KV cache stays on the GPU, 7y4V asked how much the speedup depends on offloading, and LTnX asked for direct measurements of Quest+RESA. The revision adds GPU-resident KV, end-to-end decoding and batch sizes up to 8, and measures Quest+RESA on both placements, as shown in Section 5.3 and Appendix E. With GPU-resident KV, CompKV's single-layer attention is still up to 3.9 times faster than full attention and faster than Quest+RESA in every setting. LTnX noted that this "is what I asked for".

The remaining questions from 7y4V, on summary memory, GQA sharing and why CompKV is faster than Quest, are answered in Appendices B.4 and E. Reviewers 7y4V and Jgya have not yet responded, and we hope this overview helps when reading their threads.

We also want to be clear about two points. With GPU-resident KV at 32K, CompKV is slightly slower than Quest end to end, since its per-step summary update costs more. It is faster at longer contexts and under CPU offload. LTnX's one remaining question asked which blocks drive the gain of the variance factor on the hardest retrieval task. New Appendix B.5 traces it to the blocks that hold the queried value and that Mean compensation reconstructs poorly.

We are also grateful to all three reviewers for their careful reading and insightful suggestions, which led directly to the new ablations, analyses and measurements in the revision. We sincerely thank you again for your time and for your help during the discussion.

Respectfully,

The Authors

~Simon_Mia2OpenReview ↗

Related works on second-order block statistics (COBS, CCQ)

Thank you to the authors and reviewers for a very informative discussion, and in particular for the added ablations separating p^(2)\hat{p}^{(2)} from the outer σ^2\hat{\sigma}^{2} factor. Before the discussion period closes, I wanted to note a closely related line of recent work that is currently missing from the manuscript and rebuttal, as it bears directly on the positioning of the second-order mass estimator.

Most directly, COBS: Cumulant Order Block Sparse Attention (arXiv:2607.09052, July 2026) derives essentially the same second-order block-mass estimator via a cumulant expansion of each block's log-partition function, exp⁡(q⊤kˉ+12q⊤Σq)\exp(q^{\top}\bar{k} + \frac{1}{2}q^{\top}\Sigma q), together with the same per-head-normalized GQA group aggregation. To approximate the block covariance Σ\Sigma, COBS caches a compressed per-block summary (a rank-4 subspace eigenvector descriptor) and reports substantial gains on 32K RULER. In a closely related mathematical vein, CCQ (Don't Read Everything: A Curvature-Conditioned Query for Linear Attention, arXiv:2606.01294, EMNLP 2026 Best Paper) independently develops the same second-order Taylor/cumulant correction of the softmax log-partition function using running key covariance (and on the dual query side, Expected Attention, arXiv:2510.00636, applies a Gaussian moment-generating expansion to estimate attention mass from query covariance for training-free KV compression).

In light of COBS in particular, the statement in the rebuttal that "existing selectors do not maintain [within-block variance]" appears overstated. Given that Table 3 shows p^(2)\hat{p}^{(2)} accounts for a large portion of the RULER improvement over p^(1)\hat{p}^{(1)}, addressing this connection explicitly would make the paper's narrative much more accurate. Since COBS was released shortly before the submission deadline, it is of course best viewed as concurrent work; moreover, CompKV differs meaningfully in being training-free with a much lighter-weight 4-group diagonal variance approximation (requiring only 4 scalars per block rather than COBS's trained rank-4 subspace eigenvectors and NoPE), in introducing the outer σ^2\hat{\sigma}^{2} residual weighting under Mean compensation (which proves helpful on MK3), and in its asynchronous GPU/CPU-offload implementation. Citing and contrasting these works in the next revision would give readers and the Area Chair a much clearer picture of the paper's contributions.

Thank you for pointing us to these works.

COBS appeared on arXiv in July 2026, about two months before the submission deadline, and we developed CompKV independently. Both methods correct the mean-key estimate of block mass with the second-order term of the block's log-partition function and normalize it per query head before aggregating over a GQA group. In CompKV, this correction has been part of the method since its initial formulation, where the same expansion of a block's partition function around its mean logit yields both the mass estimate and the compensation residual. The statement in our rebuttal that existing selectors do not maintain within-block variance applies to Quest's min/max summary. Beyond this shared estimate, the two methods differ in what the second-order term is used for and in how it is obtained.

COBS ranks blocks by attention mass, and its covariance term serves to estimate that mass. In our formulation, ranking by mass is the optimal rule when unselected blocks are dropped, as shown in Appendix A.5. CompKV addresses the case where unselected blocks are compensated by their mean keys and values within the same softmax. The attention KL then reduces to the part of each block's partition function that Mean compensation fails to recover, ρg,b=pg,b(1−∣b∣ezˉg,b/Zg,b)\rho_{g,b}=p_{g,b}(1-|b|e^{\bar z_{g,b}}/Z_{g,b}), and the within-block logit variance is the leading-order measure of this unrecovered fraction. The variance therefore enters CompKV twice, as the correction to the mass factor and as the outer factor that measures what compensation leaves behind. A block with high mass but nearly constant logits ranks high under a mass criterion, whereas CompKV deprioritizes it because Mean already reconstructs it; with exact statistics, residual ranking lowers both attention KL and output error relative to mass ranking, as shown in Appendix B.1. COBS also keeps NSA's compression branch, but its selector does not take into account what that branch recovers. Coupling selection to the compensator is the central idea of CompKV.

The two methods also obtain the variance differently. COBS is a trained method within NSA: the selector is trained together with the model, RoPE is removed from the selection and compression branches, and each block stores the top-rr scaled eigenvectors of its key covariance, computed by an eigendecomposition once the block fills and, in the main configuration, projected onto a query subspace and quantized to FP4. CompKV is applied to pretrained RoPE models without training or calibration. It keeps a grouped diagonal of the key covariance: each block stores r=4r=4 average coordinate variances over consecutive RoPE frequency bands, updated incrementally as new keys enter the block, and each query head weights the bands by its own energy in them. The selector thus reads d+r+1d+r+1 scalars per block, which lets the CPU-offload pipeline transfer the selection statistics first and the mean values while selection runs. The residual objective does not depend on which summary estimates the variance, so a covariance descriptor such as that of COBS could also supply both factors of the CompKV score.

CCQ and Expected Attention apply the same second-order expansion to different problems. CCQ maintains the running key covariance of a linear-attention layer and uses it to contract the query at read time. Expected Attention models future queries as Gaussian and uses the moment-generating function to score individual KV pairs for eviction. Neither selects blocks for exact reading, and neither involves a compensator.

Thank you again for the constructive comment. We will cite and discuss COBS, CCQ and Expected Attention in the related work of the final version.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.