OpenAttention reads 1% of the KV cache — Count-aware tail proxy — What does it mean?

The news. On October 22, 2026, a team from Sogang University, Samsung Electronics and Pusan National University posted OpenAttention. On RULER-32K HARD (a long-context benchmark) with Llama-3.1-8B-Instruct, it scores 86.30 against 87.04 for dense attention at a 1% read, while the best baseline scores 48.2. Its decode-attention kernel runs 10x faster than dense attention at batch 32 and 32K context. Read the paper →

Skipping reviews without losing the verdict

Picture a restaurant with 32,000 reviews and a reader who has time for 320. Reading only the loudest few hundred and ignoring the rest biases the verdict, because thousands of quiet reviews still add up. Sparse attention is the same trade. Decoding is bound by memory traffic over the KV cache, so a sparse method reads only a small subset of cached keys and values for each new token. The reviews it skips are the tail, and a review's weight here means its attention weight.

There are two older ways to handle that tail. Top-k methods discard it. MagicPIG and vAttention read a small random sample of it and scale the result up. OpenAttention does a third thing: it folds the whole unread tail into one count-aware mean proxy, a single averaged review card that is counted with the weight of every review it replaced.

In attention terms, the proxy is one virtual token. Its value vector is the mean of the tail's value vectors, and its logit is the tail's mean logit plus the log of the token count, so its softmax weight is the count times the weight of a token with the mean logit. Because it has the same form as an ordinary token, it enters the softmax next to the exact tokens and needs no special machinery. The proxy represents the tail's attention weight exactly when every tail token has the same logit. Otherwise, in the paper's analysis, the unnormalised weight error a proxy leaves is its mass times the spread of the weights it hides. That is a diagnostic for weights, not a certified bound on output error, and ErrorGate only estimates it.

Why one proxy beats a sample at low reads

The paper's starting observation uses two attention heads from RULER-32K HARD, in which 90% of the tail mass sits in 3,562 and 6,178 of the 32K tokens. A sample that receives half the read budget beats its top-k selector at high density, but at low density it is worse than the selector alone. A single proxy lowers the error in every setting the authors examine behind HashAttention, and behind oracle top-k at low density. A handful of random cards cannot describe a huge stack, but an average over the whole stack always covers it. In closed form, at low reads sampling nearly doubles the unnormalised weight error of discarding, while one proxy stays below it. The paper is careful that this is a weight-error result, not a factor-of-two claim for output error; the output error also depends on the sample's uncertain normaliser and on heavy hitters it misses.

Three helpers that make the proxy accurate

A proxy is only as good as how alike the logits inside it are. QGC clusters the cache once after prefill, so that each proxy hides tokens with nearly equal attention scores. It does this by projecting keys onto the top eigenvectors of the queries and running k-means there in 16 dimensions; the median cosine between a later decode query and the leading eigenvector is 0.82, so the prefill geometry stays valid. ErrorGate then splits the exact-read budget across clusters in proportion to the error each proxy would leave, using cached mean and variance tokens that cost 1.5 KV rows per cluster per query, charged to the read. Ranking by estimated error scores 86.30 at a 1% read, against 85.99 for ranking by mean logit alone. Last, the QGS selector picks the top tokens inside each cluster from low-bit projections, and the customised FlashAttention-2 kernel, OpenAttention.flash, runs exact tokens and proxies in one online softmax pass, which is where the 10x decode-attention speedup comes from.

A worked example with named numbers

Take a context of 10,000 cached tokens (illustrative). The exact read covers 100 top tokens that hold 60% of the attention mass, so the tail of 9,900 tokens holds the other 40%. Suppose one tail token, a missed heavy hitter, holds 5% of the total, and assume uniform random sampling and tail logits similar enough that the proxy's weight matches the tail's true 40% (a stipulated toy case, not a general property). Discarding drops all 40% of the tail mass, so the 100 exact tokens are renormalised and inflated by 1 / 0.60, about 1.67x. Sampling 50 of the 9,900 tail tokens sees the heavy hitter with probability 50 / 9,900, about 0.5%, so 99.5% of the time the sample misses it entirely, and in the 0.5% of cases it hits, scaling the sample up multiplies that token's weight by 9,900 / 50 = 198x. In this toy case the proxy keeps the full 40% of tail mass in the softmax every time, so the exact tokens stay at their true 60%. The cost is that the heavy hitter's value vector is averaged with 9,899 others, which is why real tails need QGC to group tokens with similar logits and ErrorGate to spend exact reads on the clusters whose proxy would leave the largest error.

Two limits matter before relying on this. The headline numbers come from one benchmark family, RULER-32K HARD with 200 samples per task, plus transfer runs at a 3% read on DeepSeek-R1-Distill-Llama-8B and Mistral-7B-Instruct, where OpenAttention scores 73.49 and 64.83 against dense 73.46 and 65.46. And the read budget counts exact rows, proxy rows and the mean and variance tokens but excludes the index scan that finds the clusters, so end-to-end latency depends on that scan too.

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

Related explainers

• Adaptive DHiSparse — Load-adaptive hierarchical sparse KV cache — another way to read less of the KV cache, by moving cold history to host memory instead of approximating it
• Sharpening Tax in Post-Training — pass@1 vs pass@K coverage — a second case where a small sample misrepresents a wide distribution