OpenAttention: One Percent Is Enough with Tail Proxies

Hyunwoo Yu; Jongbeom Lee; Hyunbin Kim; Sungjun Park; Jaemin Choi; Jincheol Yang; Seunghun Moon; Bongjoon Hyun

cs.LGOct 22, 2026

OpenAttention: One Percent Is Enough with Tail Proxies

Authors: Hyunwoo Yu, Jongbeom Lee, Hyunbin Kim, Sungjun Park, Jaemin Choi, Jincheol Yang, Seunghun Moon, Bongjoon Hyun,

Organizations: Sogang University · Samsung Electronics · Pusan National University

Abstract

Sparse attention reads only a small subset of the key-value cache, and how to treat the unread tail remains a key challenge. Discarding the tail biases the output, and sampling it as previous approaches do fails at reads of 5% and below, where the tail likely holds heavy hitters the selector missed. Our key observation is that the simplest possible proxy, one token that folds the entire tail into its count-aware mean, already yields lower output error than a sample at every read behind a practical selector. We further show in closed form that at low reads sampling nearly doubles the weight error of discarding while a single proxy stays below it. Building on these findings, we explore approximating the dense attention distribution with a few proxies that target the tail. We propose OpenAttention, a pipeline of clustering, ErrorGate and top-k selection followed by a count-aware mean proxy. To implement clustering and selection both efficiently and effectively, we design training-free Query-Geometry Clustering (QGC) and a Query-Geometry Selector (QGS), which compress the keys while respecting the query directions. Additionally, unlike prior methods that rank clusters by centroid alone, ErrorGate allocates the exact read by the estimated weight error of each cluster. On RULER-32K HARD with Llama-3.1-8B, OpenAttention retains 99% of dense accuracy at a 1% read. It also achieves state-of-the-art accuracy across models, context lengths and datasets. Our customized attention kernel for OpenAttention runs the decode attention stage 10 $\times$ faster than dense attention at a 1% read.

Figures & tables

Figure 1: OpenAttention against sparse attention baselines on RULER-32K HARD with Llama-3.1-8B. (a) Per-task accuracy at a 1% read. (b) Mean accuracy against the total per-query read. (c) Decode attention-stage speedup over dense attention at batch 32 and 32K context.

Figure 2: Three treatments of the tail for sparse attention. (a) Approximate top-k relies on top-k accuracy and ignores the tail. (b) Top-k with sampling misses heavy hitters at low density. (c) Ours clusters and represents the tail by proxies built with a method that minimizes the weight error.

Figure 3: Relative attention-output error versus total tokens read for four tail treatments on two RULER-32K HARD attention heads, using oracle top-

k

(a,b) or HashAttention (c,d).

Figure 4: Weight-discrepancy comparison behind HashAttention and oracle top-

k

. Panels show the tail share, logit spread, sample/tail sizes, and the predicted and measured discrepancies of Eq. ( 2 ).

Figure 5: Overview of OpenAttention. (a) QGC clusters the cache once per request. ErrorGate reads the top tokens of high-error clusters via the QGS, and the rest of each cluster becomes one count-aware mean logit proxy. (b) QGC clusters the keys projected onto the query eigenvectors. (c) QGS scores the top- $k$ with low-bit projections of the keys and query.

Figure 6:

|\cos|

of a decode query with the leading eigenvector of

M

, another decode query and a random direction.

clustering	dim	avg
token position	–	84.37
$k$ -means on keys only	128	85.42
QGC (ours)	16	86.30

Table 1: RULER-32K HARD mean accuracy by clustering method at a 1% read (

C{=}64

selector	$16\times$	$32\times$	ms
SparQ	0.96	0.94	0.29
Loki	0.84	0.75	0.18
Quest	0.77	0.66	0.33
Double Sparsity	0.97	0.95	0.50
Squeezed Attention	0.92	0.86	0.23
HashAttention	0.74	0.63	0.24

Table 2: Top-32 logit recall at

1/16

and

1/32

reads and selection time per layer on one H100.

ranking statistic	avg
mean logit (mass)	85.99
variance	84.81
estimated error (ours)	86.30

Table 3: ErrorGate ranking ablation at a 1% read on RULER-32K HARD.

Figure 7: ErrorGate estimates from diagonal and full within-cluster logit variance on 137,216 decode rows.

Figure 8: RULER-32K HARD with Llama-3.1-8B-Instruct at matched total per-query reads of 10%, 5%, 3%, and 1%, including the proxy stream. Each panel shows per-task accuracy relative to dense (grey, 100%), with mean accuracy below. Dense has a mean of 87.04 on RULER hard. MagicPIG realises reads of 10.0%, 5.1%, 2.9%, and 1.1%. Per-task results are in App. E .

Table 12

Table 13

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

selector	read	$\tau_{\mathrm{s}}$	$\tau_{\mathrm{p}}$	$\sigma_{z}$	$m$	$\mathcal{E}_{\mathrm{s}}$ (f / m)	$\mathcal{E}_{\mathrm{p}}$ (f / m)	$\mathcal{E}_{\mathrm{d}}$ (f / m)
HashAttention	10%	0.212	0.176	2.36	1585	0.401 / 0.398	0.173 / 0.171	0.176 / 0.176
	5%	0.245	0.212	2.41	791	0.477 / 0.480	0.208 / 0.206	0.212 / 0.212
	3%	0.268	0.236	2.43	473	0.527 / 0.530	0.233 / 0.230	0.236 / 0.236
	1%	0.315	0.286	2.47	156	0.628 / 0.623	0.282 / 0.280	0.286 / 0.286
	0.5%	0.345	0.316	2.48	76	0.687 / 0.684	0.312 / 0.310	0.316 / 0.316
	0.1%	0.406	0.386	2.50	13	0.812 / 0.855	0.381 / 0.380	0.386 / 0.385

Appendix

Table 8: Inputs and outputs of Fig. 4 .

\mathcal{E}

is the exact-normalizer-scaled unnormalised weight discrepancy. Predictions (f) are plug-in values from aggregate tail statistics, whereas measurements (m) are averages computed from raw decode rows; they are therefore not rowwise-paired. The proxy prediction additionally uses the Gaussian population model.

Figure 9: Quality and error versus read density on representative RULER-32K, LongBench, and LooGLE tasks.

Figure 10: One pass over 137,216 RULER-32K HARD decode rows (Llama-3.1-8B, all layers and heads of 21 requests) against the total read. (a) Recall of the exact top-

k

by the HashAttention signature and by the deployed QGS (64 vs. 32 bits/token/head at the same per-step cost,

0.84

vs.

0.82

ms at

B{=}32

), with the captured mass in faint lines. (b) Median share of the unread mass held by its largest token, annotated with the residual’s participation ratio. (c) Probability that vAttention’s sample contains that token, and the relative error of the tail mass it estimates. (d) Median relative output error of four treatments of the same residual at the same read, which discard it, sample it, aggregate it into clusters, or apply the deployed OpenAttention. The protocol is given in App. B.2 .

method	kernel	$B{=}1$	$B{=}32$	$B{=}1$	$B{=}32$
	custom	1% read		3% read
dense attention (fused SDPA)	–	0.06	1.20	0.06	1.22
HashAttention	$\times$	0.12	0.54	0.11	1.65
vAttention (lower bound)	$\times$	0.37	0.67	0.35	1.75
MagicPIG (lower bound)	$\times$	0.13	0.55	0.11	1.65
OpenAttention, unfused gather	$\times$	0.29	0.46	0.27	1.26

Appendix

Table 9: Decode attention step per layer (ms, H100 NVL, 32K, bf16) at 1% and 3% reads with no ErrorGate expansion (

E{=}0

), as in Fig. 1 (c). The vAttention/MagicPIG rows are lower bounds charging only their gathers and estimator arithmetic; selection, ErrorGate scoring and residual-statistics updates are excluded for every method. The three models of § 4.3 share these attention shapes. The speedup reported here is therefore of the attention stage and not of the decode step as a whole (see below).

$\rho$	$C$	$E$	$t$	proxy	avg	qa_1	qa_2	vt	fwe	mk_2	mk_3	mv
10%	512	2493	32	23%	86.59	78.0	49.5	95.2	92.7	95.0	99.5	96.2
10%	256	2877	32	12%	86.85	78.0	50.5	95.0	94.2	94.5	99.5	96.2
5%	256	1238	32	23%	86.51	76.5	51.0	94.9	93.2	94.5	99.5	96.0
5%	192	1335	32	18%	86.98	79.0	50.5	95.1	93.5	95.0	99.5	96.2
5%	128	1431	32	12%	86.83	78.5	50.0	95.2	94.3	95.0	99.5	95.2
10%	384	2685	32	18%	86.60	77.5	50.0	95.1	93.0	95.0	99.5	96.1

Appendix

Table 10: Per-budget grid over the split between the proxy stream and the expansion (RULER-32K HARD, 200 samples per task; “proxy” is

1.5C/\rho n

, the share of the read the cluster statistics take). Everything but

(C,E,t)

is held fixed. The chosen row is the one Figure 8 reports.

budget	method	read	avg	qa_1	qa_2	vt	fwe	mk_2	mk_3	mv
100%	dense	100%	87.04	79.0	50.0	95.2	93.3	95.0	100.0	96.8
10%	MagicPIG	10.0%	52.52	51.0	39.0	90.2	88.8	30.0	3.5	65.1
	HashAttention	10.0%	81.23	70.5	45.5	87.9	89.8	88.0	91.0	95.9
	vAttention	10.0%	83.08	73.0	46.0	91.3	92.2	92.5	91.0	95.6
	OpenAttention (ours)	10.0%	87.08	79.0	51.0	95.3	92.7	95.0	100.0	96.6
5%	MagicPIG	5.1%	34.42	36.0	33.5	71.5	88.3	2.5	0.0	9.1

Appendix

Table 11: RULER-32K HARD, Llama-3.1-8B-Instruct, 200 samples per task, at a matched total per-query read from 10% to 1% (“read” counts the exact rows plus, for OpenAttention, the proxy stream of 1.5 rows per cluster, and for vAttention, whose sample is adaptive, the measured read); the averages are Figure 8 . Baselines use the HashAttention selector.

proxies	ErrorGate	QGS	avg	qa_1	qa_2	vt	fwe	mk_2	mk_3	mv
$\times$	$\times$	$\times$	67.35	62.0	45.5	84.0	91.7	63.0	31.5	93.8
✓	$\times$	$\times$	77.91	74.5	45.5	91.8	92.8	82.5	63.0	95.2
✓	✓	$\times$	85.90	78.5	49.0	95.6	92.2	94.0	96.0	96.0
✓	$\times$	✓	86.73	78.0	51.0	95.6	92.0	94.5	99.5	96.5
✓	✓	✓	86.82	78.5	50.5	95.8	92.2	94.5	99.5	96.8

Appendix

Table 12: Per-task accuracy for the component ablation of Table 5 at a matched 5% total read on RULER-32K HARD (200 requests per task).

configuration	realised read	output error
target read 1% : 14 of 40 configurations within $1.05\times$ the target
$\epsilon{=}\delta{=}0.3$ , nominal 1.0%, sampling share 0.50 (chosen)	1.00%	0.470
$\epsilon{=}\delta{=}0.2$ , nominal 0.8%, sampling share 0.50	0.90%	0.579
$\epsilon{=}\delta{=}0.1$ , nominal 0.4%, sampling share 0.25	0.83%	0.628
$\epsilon{=}\delta{=}0.05$ , nominal 0.4%, sampling share 0.25 (none fits: smallest read)	3.16%	0.489
$\epsilon{=}\delta{=}0.025$ , nominal 0.4%, sampling share 0.25 (none fits: smallest read)	9.32%	0.383

Appendix

Table 13: vAttention parameter probe per target read (4 requests). For each

\epsilon{=}\delta

the table lists the lowest-error configuration that meets the target, its realised read and its output error against dense attention; the chosen configuration is bold.

target read	fixed ( $\epsilon{=}\delta{=}0.25$ , 50/50)	protocol-chosen	measured read
1%	37.36	36.29	1.0%
3%	57.15	55.74	3.0%
5%	68.70	68.86	5.0%
10%	82.26	83.08	10.0%

Appendix

Table 14: vAttention on RULER-32K HARD (mean accuracy), comparing the fixed

\epsilon{=}\delta{=}0.25

, 50/50 configuration with the protocol-chosen one of Table 13 , with the measured read of the latter.

method (3% read)	gov_rep.	multi_news	LB-v2
dense	36.08	26.61	30.00
HashAttention	35.34	22.09	23.30
vAttention	31.05	16.33	–
OpenAttention (static only)	35.53	26.80	33.30

Appendix

Table 15: Beyond RULER at a 3% read, on LongBench summarisation (no question chunk; ROUGE-L ( Lin, 2004 ) , 30 requests/task) and LongBench-v2 ( Bai et al., 2025 ) (0-shot accuracy, 60 requests). Absolute scores are low for dense attention too, a property of metric and benchmark, not of sparsity; OpenAttention reads no question tokens. App. G gives details.

method	gov_report (ROUGE-L)	multi_news (ROUGE-L)
dense	36.08	26.61
HashAttention	35.34	22.09
vAttention	31.05	16.33
OpenAttention (HashAttention selector, static-metric partition)	35.95	26.99
OpenAttention (static metric only: selector and partition)	35.53	26.80
OpenAttention (static $+$ instruction tokens as question)	34.68	26.93

Appendix

Table 16: LongBench summarisation tasks (no question chunk), 3% read, 30 requests per task, ROUGE-L. “static metric only” uses no question at all (selector and partition from the calibrated

M

; the row of Table 15 ); the last row treats the instruction tokens as the question.

method	avg	qa_1	qa_2	vt	fwe	mk_2	mk_3	mv
dense attention	87.04	79.0	50.0	95.2	93.3	95.0	100.0	96.8
StreamingLLM (2048)	28.00	50.5	37.5	5.3	88.3	5.0	5.0	4.4
+ OpenAttention at 10%	28.28	52.0	37.5	5.4	88.7	5.0	5.0	4.4
SnapKV (2048)	69.98	77.5	49.0	88.6	82.2	93.5	3.0	96.1
+ OpenAttention at 10%	69.49	76.0	48.0	87.7	83.5	93.5	2.5	95.2
PyramidKV (2048)	70.34	78.0	49.5	90.6	82.5	93.5	2.0	96.2

Appendix

Table 17: Table 7 per task (RULER-32K HARD, Llama-3.1-8B-Instruct, 200 samples per task).

context	method	read	avg	qa_1	qa_2	vt	fwe	mk_2	mk_3	mv
16K	dense	100%	87.14	86.0	51.0	93.2	91.0	95.0	98.0	95.8
	MagicPIG	3.0%	46.91	49.0	32.0	83.2	79.7	14.0	0.0	70.5
	HashAttention	3.0%	67.41	84.0	53.0	78.4	83.0	62.0	20.0	91.5
	vAttention	3.0%	52.69	60.0	41.0	73.4	83.7	21.0	1.0	88.8
	OpenAttention (ours)	3.0%	87.49	86.0	54.0	94.0	89.7	95.0	98.0	95.8
32K	dense	100%	87.75	83.0	50.0	95.2	93.3	96.0	100.0	96.8

Appendix

Table 18: Table 7 per task, with the total per-query read (measured for vAttention, MagicPIG and OpenAttention).

Efficient Attention

Efficient attention reduces the compute, memory traffic, and cache costs of Transformer attention while preserving useful long-range interactions.

See all 138 papers

SpotAttention: Plug-In Block-Sparse Routing for Pretrained Long-Context Transformers
Jun 22, 2026Huzama Ahmad, Se-Young YunSparse Attention Block-Sparse Attention
KAIST
Certified Sparse Attention via Perturbed Retrieval
Oct 18, 2026Runguo LiSparse Attention LLM Inference Acceleration
University of Illinois Urbana-Champaign
Keyless Attention: Value-Space Routing and Value-Only Caching for Efficient Transformers
Jun 20, 2026Xin GaoTransformer Inference KV Caching
Department of Mathematics and Statistics York University Toronto, M3J 1P3

Jun 22, 2026J/K move · Enter open · S save

SpotAttention: Plug-In Block-Sparse Routing for Pretrained Long-Context Transformers

Huzama Ahmad, Se-Young Yun

KAIST

Sparse Attention Block-Sparse Attention Attention-Guided Distillation Long-Context Language Model Inference LLM Inference Acceleration Memory-Efficient Attention+2

Open paper AskPDF arXiv

Long contexts have become standard in pretrained LLMs, yet they remain expensive to run: prefill compute grows quadratically with sequence length, and every decode step re-reads a key-value cache that grows linearly with it. Sparse attention cuts these costs by attending only to a relevant subset of past tokens, but selecting that subset is itself expensive. We present SpotAttention, a lightweight selector that attaches to a frozen pretrained transformer and learns by KL distillation to estimate its attention distribution. The selector picks the top-K keys each query attends to, and because its estimate is a calibrated distribution, a dual top-p rule reads the per-query, per-layer budget directly from it. Across Qwen3 (dense, 4B-32B) and Qwen3.5 (hybrid linear/full attention, 4B-9B), SpotAttention matches dense accuracy at contexts up to 128K tokens, eight times the training length. Decode at L=128K runs 3.9x faster than FlashAttention and 1.8x faster than Twilight, the strongest training-free baseline. Quantizing the selector's K-cache to INT4 or FP4 microscale shrinks it 3.5x at no accuracy cost.

Abstract

Efficient Attention

Explore similar work

SpotAttention: Plug-In Block-Sparse Routing for Pretrained Long-Context Transformers

Certified Sparse Attention via Perturbed Retrieval

Keyless Attention: Value-Space Routing and Value-Only Caching for Efficient Transformers