CompKV is a training-free sparse-attention method from a September 2026 arXiv paper. At each decoding step it reads a small budget of KV-cache blocks exactly and replaces every other block by its mean key and mean value. It chooses which blocks to read by the **estimated error the mean stand-in would leave**, which the paper shows is roughly attention mass times within-block logit variance.

Why not just read the blocks with the most attention?

Because a block whose tokens all have nearly the same logit is already approximated well by its mean, even if it carries a lot of attention. Reading it exactly spends budget without reducing error. The paper derives that the leftover error of a skipped, mean-compensated block grows with **mass times variance**, so a lighter block with uneven logits can be the better read.

How does CompKV relate to Quest?

Quest ranks blocks by an upper bound on their attention score and drops the rest. The CompKV paper shows that, for a single query head, removing the mean compensation from its objective reduces the selection rule to ranking by attention mass, so mass-style selection fits the case where skipped blocks contribute nothing. On RULER at 32K with a 512-token budget, the paper reports Qwen3-32B at 75.7 with Quest and 91.0 with CompKV.

LLM· 2026-09-24

CompKV sparse attention paper — Compensation-aware KV block selection — What does it mean?

Q: How fast is CompKV?

The paper reports **up to a 6.85× speedup** over full attention for a single attention layer in a CPU-offload setup on one H100 at batch size one, across 32K to 128K tokens and 512 to 2,048-token budgets. That is a per-layer attention measurement, not an end-to-end serving speedup.

TL;DR

What is it: The CompKV paper (arXiv, September 2026) introduces compensation-aware KV block selection: a sparse-attention decoder reads only a few blocks of the KV cache exactly, and it chooses those blocks by how badly a cheap block average would stand in for them, which depends on both the attention a block receives and how uneven its scores are.
Why it’s needed: Long-context decoding is limited by reading the whole KV cache from memory at every step, so sparse attention reads only a fixed budget of blocks, and the choice of which blocks fill that budget decides how much accuracy the shortcut costs.
vs previous: Earlier block-sparse methods rank blocks by predicted attention mass and then either drop the rest (Quest) or patch them with a summary afterwards; CompKV shows that a heavy block whose tokens all score alike is already well patched by its mean, so the read budget is better spent on blocks whose scores vary.

Jargon

KV cache: The stored Key and Value vectors of every earlier token, kept so the model never recomputes the past. It grows with context length, and dense decoding reads all of it at every step. Background: KV Cache → Memory Cost.
Sparse attention (query-aware): At each decoding step, compute exact attention over only a selected subset of cached tokens, chosen for the current query, instead of over the whole cache.
KV block: A run of consecutive cached tokens handled as one unit. CompKV and the baselines it is compared with use 16-token blocks.
Logit: The raw score between the query and one key, q·k/√d, before softmax turns all scores into attention weights.
Attention mass: The share of the total attention weight that falls on one block: the sum of its tokens' softmax weights.
Mean compensation: A cheap stand-in for a skipped block: every logit in the block is replaced by the block's mean logit, and its value by the mean value, so the block still contributes without its keys being read.
Logit variance (within a block): How far the individual logits in one block sit from the block's mean logit. Zero variance means the mean is an exact stand-in.
Attention sink: The first block of the context, which receives a large attention weight regardless of content. CompKV always reads it, together with the two most recent blocks.

The news. On September 22, 2026, researchers from Tsinghua University and the Harbin Institute of Technology posted CompKV on arXiv. The method is training-free: it replaces skipped KV blocks with their mean, and it picks the blocks to read exactly with that replacement in mind. On the RULER long-context benchmark at 32K tokens with a 512-token read budget, the paper reports Qwen3-32B at an average of 91.0 with CompKV versus 93.7 with full attention, while the Quest baseline drops to 75.7. Read the paper →

Picture the inspector with a time budget: there are two thousand crates on the dock, and there is time to open only a few dozen. Every sealed crate gets priced as its count times one average apple. For a crate of identical apples, that estimate is exact, no matter how heavy the crate is. For a crate that mixes tiny and huge apples, the same estimate is wrong, and it is more wrong the more that crate is worth. The old rule opens the heaviest crates; the better rule opens the crates where the average price would be most wrong. A heavy crate of identical apples is a wasted opening, because the average already priced it correctly.

The same situation happens at every decoding step of a long-context model. With dense attention, the new token's query attends over every cached key, and at 32K or 128K tokens decoding is often limited by reading the cache from memory rather than by arithmetic. Block-sparse attention splits the cache into blocks, reads a small budget of them exactly, and until recently simply dropped the rest. Newer methods compensate for the dropped blocks with a compact summary instead, so the skipped part of the context still contributes something to the weighted sum of values.

CompKV asks what that summary leaves out. Mean compensation replaces each logit in a skipped block by the block's mean logit. The exponential inside softmax curves upward: one logit above the mean adds more weight than one equally far below the mean takes away. So replacing a block's logits by their mean gives the block less total weight than it really has, unless all its logits are equal, and the gap grows with the spread. The paper approximates that gap and finds that the error a skipped block leaves behind is roughly one half times its attention mass times its logit variance. The best blocks to read exactly are therefore the ones with the largest mass × variance, not simply the largest mass. The paper also shows that, for a single query head, removing the compensation from the objective turns the same derivation into the familiar rule: top-K by attention mass. Mass-only selection fits the case where nothing stands in for the skipped blocks.

The difficulty is that computing a block's logit variance exactly means reading its keys, which is the traffic sparse attention exists to avoid. CompKV stores a small summary per block instead: the mean key, the mean value, and the key variance averaged over a few groups of coordinates (4 groups in the main results). That is 2d + r + 1 numbers, or 261 numbers for a 128-dimension head, against 4,096 for the block's full keys and values. From the query and this summary, CompKV estimates both factors of the score. The same variance estimate also corrects the mass estimate, and in the paper's test that removes one piece at a time, this correction adds 1.96 to 3.39 RULER points over an estimate without it. In the prototype, the full 16-bit cache lives in CPU memory; only the selected blocks travel to the GPU over PCIe, while the compensation for the skipped blocks runs at the same time on a second GPU work queue (a CUDA stream).

Where the read budget actually goes

Hold the setup of the paper's RULER runs fixed: a 32K-token context, 16-token blocks, and a 512-token read budget. That is 2,048 blocks, of which 32 are read exactly. Three of the 32 are mandatory (the sink block and the two most recent blocks), so the selector decides only 29 slots, about 1.4% of the cache. Now look at one of those slots with two candidates (illustrative numbers). Block A has mass 0.30 but nearly identical logits, variance 0.02, so its mean stand-in leaves an error of about ½ × 0.30 × 0.02 = 0.003. Block B has only mass 0.10 but a variance of 1.0, so its stand-in leaves about ½ × 0.10 × 1.0 = 0.05. A mass rule reads A and leaves B's 0.05 behind. CompKV reads B and leaves only A's 0.003: about 17 times less error from the same single read.

How the selection rules compare on RULER

Method	How it ranks blocks	Skipped blocks	RULER avg, Llama-3.1-8B	RULER avg, Qwen3-32B	Source
Full attention	reads every block	none	87.0	93.7	paper, Table 1
Quest	upper bound on the block's attention score	dropped	77.0	75.7	paper, Table 1
InfLLM	query-aware block relevance	dropped	73.1	82.5	paper, Table 1
Quest + RESA	Quest's score	reconstructed from a low-rank logit prior	78.2	75.6	paper, Table 1
CompKV	estimated mass × logit variance	mean key and mean value	83.2	91.0	paper, Table 1

All scores in the table are at 32K context with a 512-token budget. The largest gap is on RULER's hardest multi-key retrieval task: with Qwen3-32B, Quest scores 2.4 and CompKV scores 93.0. The gain is not universal. On the common-word extraction task, every sparse method stays far below full attention, and with Llama-3.1-8B CompKV scores 0.5 against Quest's 1.7. The headline up to 6.85× speedup is the best case from a narrow measurement: one attention layer, in the CPU-offload setup, on one H100 at batch size one, across 32K to 128K tokens and 512 to 2,048-token budgets. It is not an end-to-end serving number. The approximation behind the score also assumes the logits inside a block are not spread very far apart. The durable lesson is the rule itself: once skipped blocks are summarized instead of dropped, spend exact reads where the summary is worst, not where attention is largest.

Goes deeper in: LLM Internals → KV Cache → Memory Cost

Related explainers

MiniMax M3 — MiniMax Sparse Attention (MSA) — another block-sparse attention design: score blocks, read only the chosen ones, drop the rest
FlashMemory — Lookahead Sparse Attention — a trained selector that keeps KV chunks, where CompKV's rule needs no training
Tangram — per-head KV cache budgets — a different question about the same budget: how much cache each head gets, not which blocks

Continue in trackLLM Internals — KV Cache & Memory Cost

Frequently Asked Questions

Check what you knowMap your AI & GPU knowledge across every track — free, role-based