cs.LGOct 18, 2026

Certified Sparse Attention via Perturbed Retrieval

Authors: Runguo Li

Organizations: University of Illinois Urbana-Champaign

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Sparse attention speeds up long-context decoding by reading few keys of the KV cache, but existing methods do not control the error of a query, and on real KV caches their errors have heavy tails. We show that perturbing the score of every key with an independent Exp(1) variable turns threshold retrieval into sampling keys with probability proportional to their attention weights. Lowering the threshold along a geometric grid gives nested samples, a Horvitz--Thompson estimate of the output at every level, and confidence bounds that hold simultaneously over all levels, so each head stops at the first level whose certificate meets the target error ε\varepsilon. With fresh perturbations at every decoding step, each certificate fails with probability at most δδ during generation. At a suitable threshold, the estimator reads O(ε−2log⁡(1/δ))O(\varepsilon^{-2}\log(1/δ)) values regardless of the context length, and no adaptive method reads fewer, up to constants. A 4-bit scan with deterministic bounds, shared across a grouped-query-attention group, generates the candidates exactly but reads every key. On three LLMs and ten settings at 16K--128K tokens, no certificate is violated, and at equal keys read our 90th-percentile error is 4.6--7.9×\times lower than that of the best of 15 baseline families. At equal bytes, the best baselines have 0.6--1.6 times our 90th-percentile error and at least 4.9 times our largest. End to end, our method stays within one point of dense attention on tasks and within 0.1% in PG-19 perplexity, and the strongest baselines at equal bytes score as well. On CPU, decoding steps at 32K--128K tokens run 1.1--1.4×\times faster than dense attention on the same 16-bit cache.

Figures & tables

Figure 1. (a) Each key ii carries a perturbation Ei∼Exp(1)E_{i}\sim\mathrm{Exp}(1) , drawn afresh at every decoding step, and is in the sample at threshold τ\tau exactly when its perturbed score lies above the line of τ\tau , which happens with probability min⁡(1,wi/τ)\min(1,w_{i}/\tau) ; lowering τ\tau only adds keys (shades give the level at which a key enters). (b) One query of a GQA group (Algorithm 1, Appendix B). The shared 4-bit scan bounds every score, so its candidates contain the sample; 8-bit refinement and exact keys decide which candidates enter S(τj)S(\tau_{j}) , and the values of sampled keys give the Horvitz–Thompson estimate. Each head stops at the first level whose error bound βj\beta_{j} (Lemma 1) meets the target, and Pr⁡[certified and ∥o^m−om∥>εM]≤δ\Pr[\text{certified and }\|\hat{o}_{m}-o_{m}\|>\varepsilon M]\leq\delta (Theorem 4). Synthetic data; logarithms in (a) are base 2.
Figure 2. 90th-percentile error/ MM versus keys read for our method ( ε∈{0.05,0.1,0.2,0.3}\varepsilon\in\{0.05,0.1,0.2,0.3\} ), its fixed-threshold variant without certificates, and the strongest baseline families (Pareto fronts of their tuning grids) on four settings (Llama LongBench 16K and RULER 128K, Qwen3 and Qwen2.5 at 32K). All ten settings are in Appendix D.
Figure 3. Per-query errors at matched keys read, and the calibration of the certificates. (a, b) Fraction of queries whose error /M/M is at least xx , for our method at ε=0.1\varepsilon=0.1 and the three best baseline families of Table 1 at their configurations in Table D.2a. The dotted line marks ε\varepsilon . (c) Observed error against the target ε\varepsilon for the value-scale and output-norm measures, as the maximum and the 90th percentile over the queries of a setting (median over the ten settings, range shaded). The dotted line is the certified bound.
Appendix figures & tables23 assets

Supplementary material from the paper’s appendix.

Appendix

ArrayLayoutBytes per tokenRead per query
Keys and valuesfp16, token-major (256 B per row)512exact keys of candidates; values of sampled keys; window
4-bit codesVNNI-interleaved per block (below)64every pool token
8-bit codestoken-major, one byte per channel128refined candidates
Perturbation EiE_{i}fp32, rewritten at every step4every pool token (and written before the scan)
Block scales ( lo\mathrm{lo} , step\mathrm{step} , step(8)\mathrm{step}^{(8)} per channel)fp32, per block12every pool token
Total 720 (+40%)floor 80 B read + 4 B written per pool token (16.4%)
Appendix
Table 4
ComponentVariantEffect
Certified adaptive stoppingFixed threshold without certificate, closest number of keys readp90 error 2.4–9.6 ×\times higher, max error 3.8–16 ×\times higher; 14% of errors exceed 0.1 at 128K
GQA-shared scanEach query head scans separatelyBytes read 2.7–4.0 ×\times higher (3.9–4.0 ×\times for G=7G=7 )
Certificate ruleUncertified CLT rule with ≥\geq 30 tail samples (CLT30)Ours reads 1.8–3.5 ×\times more keys (Llama 16K / 32K / 128K: 2.9 / 2.9 / 3.5 ×\times ; Qwen2.5: 1.8 ×\times ); CLT30’s worst layer reaches a 4.9% violation rate (denominator)
Certificate ruleOracle stopping level (IDEAL, unrealizable)Ours reads 4.1–4.9 ×\times more keys (2.7–3.0 ×\times at ε=0.2\varepsilon=0.2 )
8-bit refinementRemovedBytes −- 1% to +4%; speedup −- 3% to +6%
Appendix
Table D.0. Summary of the ablations at ε=0.1\varepsilon=0.1 (ranges over the ten settings unless noted).
Figure D.1. 90th-percentile error/ MM versus keys read on all ten settings. Each baseline family is drawn as the Pareto front of its tuning grid. Our method is shown for ε∈{0.05,0.1,0.2,0.3}\varepsilon\in\{0.05,0.1,0.2,0.3\} (solid), and the same estimator at fixed thresholds without certificates is shown dashed.
Model ⋅\cdot dataOurs: keys / p90 / maxBest three baselines
Llama ⋅\cdot LongBench 16K2.70% / 0.011 / 0.021MagicPIG (ref.) 2.75%, 0.059 / 0.83; RetroInfer 2.22%, 0.063 / 0.72; oracle top- kk 2.58%, 0.074 / 0.43
Llama ⋅\cdot RULER 32K1.35% / 0.011 / 0.025RetroInfer 1.24%, 0.058 / 0.49; MagicPIG (ref.) 1.48%, 0.066 / 1.21; oracle top- kk 1.30%, 0.085 / 0.77
Llama ⋅\cdot RULER 64K0.70% / 0.012 / 0.028RetroInfer 0.58%, 0.059 / 0.68; oracle top- kk 0.69%, 0.084 / 0.89; vAttention (oracle) 0.76%, 0.101 / 0.60
Llama ⋅\cdot LongBench-v2 64K0.61% / 0.011 / 0.021RetroInfer 0.57%, 0.051 / 0.39; oracle top- kk 0.59%, 0.068 / 0.43; oracle top- pp 0.61%, 0.101 / 0.56
Llama ⋅\cdot RULER 128K0.46% / 0.012 / 0.029RetroInfer 0.47%, 0.077 / 0.65; oracle top- kk 0.50%, 0.099 / 0.88; vAttention (oracle) 0.50%, 0.117 / 0.58
Llama ⋅\cdot LongBench-v2 128K0.42% / 0.012 / 0.022RetroInfer 0.32%, 0.069 / 0.65; oracle top- kk 0.40%, 0.078 / 0.44; vAttention (oracle) 0.43%, 0.137 / 0.85
Appendix
Table D.2a. The three best baseline families at matched keys read (at most 1.1 times ours), with keys read, 90th-percentile error and maximum error.
Figure D.2. 90th-percentile error/ MM against bytes read, relative to dense attention: ours as measured ( ε∈{0.05,0.1,0.2,0.3}\varepsilon\in\{0.05,0.1,0.2,0.3\} ) and, for each baseline family, the Pareto front of its configurations under the lower bounds of Appendix C.2, on the settings of Figure 2.
Model ⋅\cdot dataOurs2-bit, 128-token key groups4-bit, 128-token key groups8-bit, 128-token key groups2-bit, 32-token key groups4-bit, 32-token key groups
Llama ⋅\cdot LongBench 16K28.6% / 0.011 / 0.02117.5% / 0.2394 / 1.85529.8% / 0.0458 / 0.28454.5% / 0.0026 / 0.01719.8% / 0.1732 / 1.28332.1% / 0.0371 / 0.268
Llama ⋅\cdot RULER 32K22.6% / 0.011 / 0.02516.9% / 0.2363 / 2.04729.3% / 0.0464 / 0.23654.2% / 0.0026 / 0.01319.2% / 0.1749 / 1.92531.6% / 0.0381 / 0.251
Llama ⋅\cdot RULER 64K20.1% / 0.012 / 0.02816.6% / 0.2370 / 2.66129.1% / 0.0472 / 0.32554.0% / 0.0027 / 0.01819.0% / 0.1764 / 1.44831.4% / 0.0382 / 0.201
Llama ⋅\cdot LongBench-v2 64K19.9% / 0.011 / 0.02116.7% / 0.2133 / 1.26929.1% / 0.0427 / 0.25454.1% / 0.0024 / 0.01319.0% / 0.1592 / 1.41031.5% / 0.0343 / 0.170
Llama ⋅\cdot RULER 128K19.5% / 0.012 / 0.02916.5% / 0.2160 / 3.70229.0% / 0.0406 / 0.26254.0% / 0.0024 / 0.01718.9% / 0.1604 / 1.71531.4% / 0.0337 / 0.232
Llama ⋅\cdot LongBench-v2 128K19.3% / 0.012 / 0.02216.5% / 0.2069 / 1.00129.0% / 0.0377 / 0.27654.0% / 0.0022 / 0.01918.9% / 0.1397 / 1.29131.4% / 0.0299 / 0.162
Appendix
Table D.2e. Dense attention over a KIVI-style quantized KV cache (keys per channel, values per token in groups of 32 channels, fp16 scales, the last 128 tokens in 16 bits): bytes read / 90th-percentile / maximum error/ MM , against our method at ε=0.1\varepsilon=0.1 (with the 4 bytes per token written by the per-step perturbations). The key groups span 128 tokens, or 32 as in KIVI.
Model ⋅\cdot dataOurs, ε=0.1\varepsilon=0.1With replacement from the 4-bit proposalPoisson PPS on 4-bit probabilitiesPoisson PPS, one budget per setting
Llama ⋅\cdot LongBench 16K2.70% / 0.0112 / 0.0211.47% / 0.0616 / 0.6452.70% / 0.0115 / 0.1082.70% / 0.0192 / 0.093
Llama ⋅\cdot RULER 32K1.35% / 0.0114 / 0.0250.82% / 0.0630 / 0.6121.35% / 0.0117 / 0.0801.35% / 0.0187 / 0.100
Llama ⋅\cdot RULER 64K0.70% / 0.0115 / 0.0280.43% / 0.0624 / 0.6890.70% / 0.0118 / 0.0330.70% / 0.0188 / 0.090
Llama ⋅\cdot LongBench-v2 64K0.61% / 0.0112 / 0.0210.35% / 0.0626 / 0.4920.61% / 0.0116 / 0.0220.61% / 0.0171 / 0.094
Llama ⋅\cdot RULER 128K0.46% / 0.0119 / 0.0290.28% / 0.0574 / 0.7060.46% / 0.0122 / 0.0310.46% / 0.0194 / 0.094
Llama ⋅\cdot LongBench-v2 128K0.42% / 0.0117 / 0.0220.24% / 0.0553 / 0.3140.42% / 0.0120 / 0.0240.42% / 0.0177 / 0.071
Appendix
Table D.2f. Sampling with fresh randomness from the 4-bit scores (no certificate): keys read (distinct keys for sampling with replacement) / 90th-percentile / maximum error/ MM . The first two read the number of keys our method read for the same query ( ε=0.1\varepsilon=0.1 , value scale), which a method without a certificate does not know; the last reads the same number of keys for every query, our mean over the setting.
Figure D.3. Keys read per query at ε=0.1\varepsilon=0.1 (value scale). (a) Distribution over all (layer, query head, step) of four settings. (b) Median over samples and steps for each layer and query head of Llama RULER 128K, on a logarithmic color scale.
Figure D.6. (a) Keys read per query (window plus sample) on Llama against the context length, for three values of ε\varepsilon (Table D.4). Circles connected by lines are RULER at 32K–128K, squares LongBench-v2 at 64K and 128K, and diamonds LongBench at 16K; the dashed line is dense attention. (b) Change in PG-19 perplexity relative to dense attention, with 95% bootstrap intervals over books (Table D.12); our method draws fresh perturbations at every step. Oracle top- kk reads, at every layer, step and query head, as many keys as our method at ε=0.1\varepsilon=0.1 .
Figure D.4. Fraction of queries whose error /M/M is at least xx , for certified stopping at ε=0.1\varepsilon=0.1 and for the same estimator at the fixed level whose keys read are closest (Table D.5). The dotted line marks 0.1.
Figure D.5. Mean keys read of the certificate rules of Table D.7a (Llama LongBench 16K). Blue bars are certified rules, and KL4 is the rule of our kernel. CLT30 has no guarantee, and IDEAL is unrealizable.
CPUModel ⋅\cdot dataIndexing: per KV head / all heads / keys per s (1 thread)Append per step (all heads)Query: 1 / 8 / 24 threadsAppend / query (24 threads)
8555CLlama ⋅\cdot 16K0.030 s / 7.8 s / 536K0.70 ms297 / 37 / 13 ms5.2%
8555CLlama ⋅\cdot 32K0.060 s / 15.5 s / 535K0.69 ms348 / 45 / 17 ms4.1%
8555CLlama ⋅\cdot 64K0.122 s / 31.4 s / 528K0.73 ms516 / 66 / 25 ms2.9%
8555CLlama ⋅\cdot 128K0.270 s / 69.2 s / 483K0.71 ms1039 / 133 / 60 ms1.2%
8555CQwen2.5 ⋅\cdot 16K0.030 s / 3.4 s / 539K0.31 ms194 / 26 / 9 ms3.3%
8358Llama ⋅\cdot 16K0.028 s / 7.1 s / 586K0.96 ms313 / 40 / 22 ms4.3%
Appendix
Table D.10. Indexing the prompt (all KV heads of all layers) and appending one token per KV head per step, against the time of our attention query in the same step (value scale, ε=0.1\varepsilon=0.1 ). Measured on one NUMA node of an idle machine. On the 8358, 24 threads use hyper-threads.
CPU (threads) ⋅\cdot contextSteady step: SDPA / dense16 / oursAttention: SDPA / dense16 / oursRestStep speedup over dense16 / SDPAAttention speedup over dense16Ours: first stepBreak-even
8555C (26) ⋅\cdot 32K421 / 306 / 273 ms219 / 105 / 66 ms202 ms1.12 ×\times / 1.54 ×\times1.58 ×\times0.91 s18 steps
8555C (26) ⋅\cdot 64K715 / 416 / 314 ms508 / 210 / 104 ms206 ms1.32 ×\times / 2.27 ×\times2.02 ×\times1.56 s11 steps
8555C (26) ⋅\cdot 128K1192 / 629 / 439 ms976 / 412 / 218 ms217 ms1.43 ×\times / 2.72 ×\times1.89 ×\times3.15 s13 steps
8358 (32) ⋅\cdot 32K343 / 330 / 298 ms128 / 115 / 81 ms215 ms1.11 ×\times / 1.15 ×\times1.42 ×\times0.91 s18 steps
8358 (32) ⋅\cdot 64K470 / 434 / 347 ms250 / 219 / 126 ms215 ms1.25 ×\times / 1.35 ×\times1.74 ×\times1.57 s13 steps
8358 (32) ⋅\cdot 128K724 / 649 / 479 ms503 / 432 / 257 ms217 ms1.35 ×\times / 1.51 ×\times1.68 ×\times2.92 s13 steps
Appendix
Table D.11b. Whole fp32 decoding step of Llama (one RULER sequence per length; ε=0.1\varepsilon=0.1 , value scale, perturbations drawn afresh at every step). After one dense prefill, three methods decode 32 tokens each from the prompt’s cache, one after another, in five rounds: the model’s attention over its fp32 cache (SDPA), our dense kernel over the same 16-bit cache as our method (dense16), and our method. “Steady” is the median of steps 2–32 in each method’s fastest round. “Attention” is the time of all attention calls of a steady step. “Rest” is the remainder of the dense16 step (linear layers, sampling, cache update). “Break-even” is the number of steady steps after which the extra cost of our first step, which indexes the prompt, is recovered.
Figure D.7. CPU speed on Llama (value scale, ε=0.1\varepsilon=0.1 , fresh perturbations at every step). (a) Attention for all heads of one decoding step, as speedup over our dense kernel on the same 16-bit keys and values (LongBench at 16K, RULER at 32K–128K; Table D.11a). (b, c) Steady time of a whole fp32 decoding step for the model’s attention over its fp32 cache (SDPA), our dense kernel (dense16) and our method, split into attention and the rest of the step (fastest of five rounds; Table D.11b). The numbers give our step speedup over dense16.
Model ⋅\cdot dataDense (ms)Speedup, fixedSpeedup, per stepPer step ÷ fixedδ/(HT)\delta/(HT) ÷ per stepKeys: per step / δ/(HT)\delta/(HT)
Llama ⋅\cdot LongBench 16K356 / 56.8 / 38.61.09 / 1.34 / 1.541.06 / 1.27 / 1.511.04 / 1.05 / 1.041.32 / 1.32 / 1.342.75% / 4.41%
Llama ⋅\cdot RULER 32K702 / 112.8 / 81.21.37 / 1.53 / 1.771.32 / 1.47 / 1.701.06 / 1.03 / 1.041.31 / 1.31 / 1.341.68% / 2.92%
Llama ⋅\cdot RULER 64K1385 / 235 / 175.11.82 / 1.97 / 2.151.69 / 1.82 / 2.051.08 / 1.06 / 1.041.25 / 1.27 / 1.250.89% / 1.49%
Llama ⋅\cdot RULER 128K2932 / 514 / 3852.01 / 1.99 / 2.231.79 / 1.88 / 2.161.10 / 1.05 / 1.031.22 / 1.22 / 1.240.63% / 1.04%
Llama ⋅\cdot LongBench-v2 128K2927 / 521 / 3862.62 / 2.58 / 2.862.32 / 2.41 / 2.701.13 / 1.06 / 1.041.17 / 1.17 / 1.170.39% / 0.64%
Qwen3 ⋅\cdot LongBench 16K398 / 63.1 / 46.01.14 / 1.25 / 1.581.08 / 1.22 / 1.471.05 / 1.03 / 1.031.26 / 1.25 / 1.271.99% / 3.03%
Appendix
Table D.11e. Attention time of one decoding step (all layers and KV heads of one sample; value scale, ε=0.1\varepsilon=0.1 ) with perturbations fixed per KV head, drawn afresh at every step (our default) and drawn afresh with δ=0.05/(HT)\delta=0.05/(HT) , at 1 / 8 / 16 threads on one NUMA node of an 8358 machine whose other nodes were busy (samples of Table D.11a). Our dense kernel and the three configurations are timed in turn within each of 7 repetitions. Speedups over dense use the best repetition of each, and the two time ratios are medians over repetitions of the ratio within a repetition, which cancels load that changes between repetitions. Keys read are the fraction of the context.
Model ⋅\cdot context (books)Dense PPLOurs, ε=0.1\varepsilon=0.1 : keys / Δ\Delta PPL / KLOurs, ε=0.2\varepsilon=0.2 : keys / Δ\Delta PPL / KLOracle top- kk : Δ\Delta PPL / KLTop- kk , layers 0–1 dense: Δ\Delta PPL
Llama ⋅\cdot 32K (16)11.0761.79% / +0.03% [ −- 0.06, +0.13] / 0.00051.10% / +0.22% [+0.07, +0.36] / 0.0014+5.9% [+3.1, +9.3] / 0.095+5.2% [+2.3, +8.7]
Llama ⋅\cdot 64K (12)11.4870.98% / +0.07% [ −- 0.05, +0.19] / 0.00060.59% / +0.03% [ −- 0.10, +0.18] / 0.0014+4.8% [+2.7, +7.3] / 0.085+4.1% [+2.0, +6.7]
Llama ⋅\cdot 128K (8)8.7570.58% / +0.01% [ −- 0.03, +0.05] / 0.00050.34% / +0.11% [ −- 0.08, +0.31] / 0.0013+8.8% [+3.4, +18.7] / 0.106+8.5% [+3.1, +18.3]
Qwen3 ⋅\cdot 32K (16)12.5361.95% / +0.05% [ −- 0.03, +0.13] / 0.00031.26% / +0.12% [+0.01, +0.22] / 0.0007+8.4% [+4.6, +14.2] / 0.114+8.7% [+4.9, +14.6]
Qwen2.5 ⋅\cdot 32K (16)10.0712.25% / −- 0.02% [ −- 0.06, +0.02] / 0.00021.35% / −- 0.02% [ −- 0.11, +0.06] / 0.0006+11.5% [+5.7, +19.4] / 0.126+10.3% [+4.5, +18.4]
Appendix
Table D.12. PG-19 perplexity change relative to dense attention, with 95% CIs (bootstrap over books), and the mean KL divergence from dense attention’s next-token distribution. Our method draws fresh perturbations at every step; the ablation with perturbations fixed per KV head is given below the table. The top- kk control reads, per head, as many keys as our method at ε=0.1\varepsilon=0.1 .
Model ⋅\cdot context (books)MethodKeys readBytes readPerplexity vs dense [95% CI]Perplexity vs ours [95% CI]KL meanKL / ours [95% CI]
Llama ⋅\cdot 32K (16)ours, per-step perturbations1.79%26.0%+0.03 [ −- 0.06, +0.13]–0.00051
Llama ⋅\cdot 32K (16)ours, fixed perturbations1.79%25.2%+0.03 [ −- 0.08, +0.12]0.00 [ −- 0.18, +0.16]0.00091.78 ×\times [1.25, 2.40]
Llama ⋅\cdot 32K (16)ours, ε=0.2\varepsilon=0.2 , per step1.10%22.3%+0.22 [+0.07, +0.36]+0.19 [+0.06, +0.32]0.00142.83 ×\times [2.58, 3.21]
Llama ⋅\cdot 32K (16)oracle top- kk (our keys per head)1.84%oracle+5.89 [+3.09, +9.26]+5.85 [+3.09, +9.19]0.0951188 ×\times [145, 236]
Llama ⋅\cdot 32K (16)oracle top- kk , layers 0–1 dense7.80%oracle+5.20 [+2.32, +8.71]+5.17 [+2.31, +8.67]0.0911180 ×\times [136, 227]
Llama ⋅\cdot 32K (16)MagicPIG (reference), K=8K=8 , L=200L=20023.41%24.0% ( ≥\geq )+0.09 [ −- 0.02, +0.19]+0.06 [ −- 0.11, +0.21]0.00091.83 ×\times [1.67, 2.01]
Appendix
Table D.12b. PG-19 at 32K (and Llama at 64K and 128K) with the per-step method as the reference: keys and bytes read (ours with the 4 bytes per token written by per-step perturbations; baselines: lower bound), perplexity change against dense attention and against our method in percent, mean KL divergence from dense attention’s next-token distribution, and the ratio of mean KL divergences to ours, with 95% CIs from a paired bootstrap over books. Baselines whose bytes are within 0.9–1.1 times ours run at the configurations matched to our end-to-end bytes; the others run at the sparser configurations of Appendix C.6.
Model ⋅\cdot context (books)MethodKeys readBytes readPerplexity vs dense [95% CI]Perplexity vs ours [95% CI]KL meanKL / ours [95% CI]
Llama ⋅\cdot 64K (12)ours, per-step perturbations0.98%22.5%+0.07 [ −- 0.05, +0.19]–0.00061
Llama ⋅\cdot 64K (12)ours, ε=0.2\varepsilon=0.2 , per step0.59%20.2%+0.03 [ −- 0.10, +0.18]−- 0.04 [ −- 0.14, +0.06]0.00142.46 ×\times [2.05, 2.92]
Llama ⋅\cdot 64K (12)oracle top- kk (our keys per head)1.00%oracle+4.80 [+2.67, +7.32]+4.73 [+2.64, +7.19]0.0847148 ×\times [101, 214]
Llama ⋅\cdot 64K (12)oracle top- kk , layers 0–1 dense7.09%oracle+4.12 [+1.95, +6.67]+4.04 [+1.93, +6.58]0.0794138 ×\times [92.9, 203]
Llama ⋅\cdot 128K (8)ours, per-step perturbations0.58%20.6%+0.01 [ −- 0.03, +0.05]–0.00051
Llama ⋅\cdot 128K (8)ours, ε=0.2\varepsilon=0.2 , per step0.34%18.9%+0.11 [ −- 0.08, +0.31]+0.10 [ −- 0.08, +0.27]0.00132.61 ×\times [2.35, 2.90]
Appendix
Table D.12b (continued)
Model ⋅\cdot context (books)MethodKeys readBytes readPerplexity vs dense [95% CI]Perplexity vs ours [95% CI]KL meanKL / ours [95% CI]
Qwen3 ⋅\cdot 32K (16)ours, per-step perturbations1.95%30.8%+0.05 [ −- 0.03, +0.13]–0.00031
Qwen3 ⋅\cdot 32K (16)ours, fixed perturbations1.95%30.0%+0.04 [ −- 0.09, +0.17]−- 0.01 [ −- 0.15, +0.14]0.00051.57 ×\times [1.30, 1.87]
Qwen3 ⋅\cdot 32K (16)ours, ε=0.2\varepsilon=0.2 , per step1.26%26.7%+0.12 [+0.01, +0.22]+0.07 [ −- 0.01, +0.14]0.00072.59 ×\times [2.40, 2.77]
Qwen3 ⋅\cdot 32K (16)oracle top- kk (our keys per head)2.00%oracle+8.44 [+4.65, +14.18]+8.38 [+4.61, +14.05]0.1143396 ×\times [270, 598]
Qwen3 ⋅\cdot 32K (16)oracle top- kk , layers 0–1 dense7.39%oracle+8.72 [+4.90, +14.55]+8.66 [+4.88, +14.43]0.1155400 ×\times [273, 603]
Qwen3 ⋅\cdot 32K (16)MagicPIG (reference), K=9K=9 , L=300L=30018.54%19.0% ( ≥\geq )+0.18 [+0.01, +0.33]+0.13 [ −- 0.08, +0.33]0.00165.71 ×\times [4.82, 6.49]
Appendix
Table D.12b (continued)
Model ⋅\cdot context (books)MethodKeys readBytes readPerplexity vs dense [95% CI]Perplexity vs ours [95% CI]KL meanKL / ours [95% CI]
Qwen2.5 ⋅\cdot 32K (16)ours, per-step perturbations2.25%41.2%−- 0.02 [ −- 0.06, +0.02]–0.00021
Qwen2.5 ⋅\cdot 32K (16)ours, fixed perturbations2.24%40.4%+0.01 [ −- 0.06, +0.07]+0.02 [ −- 0.07, +0.12]0.00041.61 ×\times [1.44, 1.79]
Qwen2.5 ⋅\cdot 32K (16)ours, ε=0.2\varepsilon=0.2 , per step1.35%34.3%−- 0.02 [ −- 0.11, +0.06]0.00 [ −- 0.08, +0.06]0.00062.62 ×\times [2.46, 2.78]
Qwen2.5 ⋅\cdot 32K (16)oracle top- kk (our keys per head)2.30%oracle+11.49 [+5.66, +19.43]+11.51 [+5.67, +19.44]0.1257555 ×\times [318, 893]
Qwen2.5 ⋅\cdot 32K (16)oracle top- kk , layers 0–1 dense9.11%oracle+10.34 [+4.50, +18.38]+10.36 [+4.51, +18.42]0.1190525 ×\times [286, 866]
Qwen2.5 ⋅\cdot 32K (16)MagicPIG (reference), K=9K=9 , L=300L=30016.54%17.0% ( ≥\geq )+0.13 [+0.01, +0.26]+0.15 [+0.02, +0.28]0.00208.79 ×\times [5.90, 13.6]
Appendix
Table D.12b (continued)
Method (7 books)Mean KLMax KLFirst / last quarterMean KL / oursMax KL / oursNLL minus denseRepeated 4-grams minus dense (points)
dense attention—————NLL 1.1579.5%
ours, ε=0.1\varepsilon=0.14.5e-045.8e-024.0e-04 / 4.1e-0411−- 0.011 [ −- 0.125, +0.083]−- 2.3 [ −- 5.1, +0.6]
MagicPIG (reference)7.3e-044.8e-021.0e-03 / 5.3e-041.63 [1.32, 2.01]0.84 [0.68, 1.71]−- 0.024 [ −- 0.093, +0.049]+0.0 [ −- 2.1, +2.6]
RetroInfer (CPU port)1.9e-031.2e-012.1e-03 / 1.7e-034.25 [3.40, 5.43]1.99 [1.02, 7.16]−- 0.212 [ −- 0.424, −- 0.026]+5.3 [ −- 2.5, +14.6]
vAttention (HashAttention)1.7e-032.1e-012.5e-03 / 1.3e-033.89 [2.93, 5.14]3.71 [0.42, 11.82]−- 0.085 [ −- 0.254, +0.080]−- 1.8 [ −- 6.2, +2.0]
Appendix
Table D.12c. Free generation on PG-19 at 32K (Llama): 1,024 tokens per book sampled at T=0.7T=0.7 with the same Gumbel noise for every method, after a dense prefill of the preceding 31,744 tokens. The KL divergence from dense attention’s next-token distribution is measured at every step on the method’s own prefix (a dense shadow sequence fed the method’s tokens): mean and maximum per book, averaged over books, and the mean over the first and the last quarter of the steps. Ratios to ours with 95% bootstrap CIs over books. NLL: negative log-likelihood under dense attention of the tokens the method sampled, minus that of dense attention’s own samples; repeated 4-grams: share of the generated 4-grams that occurred earlier in the same continuation, minus dense attention’s. Baselines at the matched configurations of Table D.12b.
ComponentContents
Kernel and bindingcsrc/certattn/ : the C++ kernel with AVX-512 intrinsics, its pybind11 binding and a build script
Reference implementation and teststhe NumPy reference with exact scores ( attn/pps_ref.py ) and the kernel and index tests ( attn/test_certattn.py , attn/test_append_many.py )
Certificate rulesattn/certify.py and the rule comparison of Appendix D.7 ( attn/cert_ablation.py )
Operator-level evaluationKV-cache capture ( probe/capture.py ), baseline configurations and evaluation ( attn/methods.py , attn/eval_maskers.py ) with the chunked routines of Appendix C.3, the reference ports ( attn/official_ref.py , attn/retroinfer_port.py ) and SANTA ( attn/eval_santa.py )
End-to-end evaluation and perplexityattn/e2e.py with one configuration file per method, attn/e2e_stats.py and attn/ppl.py
Timingattention and whole-step timing, the append cost ( attn/bench_append.py ) and the comparison with llama.cpp ( attn/bench_dense_vs_llamacpp.py , with the llama.cpp patch)
Appendix
Table 25
ItemVersion
sparse-attention-hub (baseline maskers)xAlg-ai/sparse-attention-hub, commit 497da5b
MagicPIG referenceInfini-AI-Lab/MagicPIG, commit ac9aa36
Quest referencemit-han-lab/Quest, commit 01c1623
RetroInfer (ported)microsoft/RetrievalAttention, commit 03f912c
HashAttention weights (Llama-3.1-8B, 64K patch v1)sha256 8b496b02…
LongBench prompts and metricsTHUDM/LongBench, commit 2e00731f8d
Appendix
Table 26
More in this topic

Sparse Attention

Sparse attention reduces the token interactions computed by Transformers to lower the cost of long-context modeling and inference.

See all 244 papers

Explore similar work

CardsList

  1. Stratified Sparse Attention: Reducing the Sparse-to-Dense Gap at Extreme Sparsity

    Oct 20, 2026Sahil Joshi, Prithvi Dixit, Aryan Katiyar +5Sparse AttentionLong-Context Language Model Inference

    Department of Computer Science, Rice University, TX, USA. · Department of Electrical Engineering and Computer Sciences, UC Berkeley, CA, USA. · Department of Computer Science, Stanford University, CA, USA. +1

  2. Elastic Threshold Attention: Learned Contextual Sparsity for Long-Context Decoding

    Sep 16, 2026Themistoklis Haris, Henry Li, Maryam KarimzadehganLong-Context Language Model InferenceSparse Attention

    Google · Boston University

  3. Sparse Attention as a Range Searching Problem: Towards an Inference-Efficient Index for KV Cache

    May 7, 2026Mohsen Dehghankar, Abolfazl AsudehSelf-AttentionKV Caching

    Department of Computer Science University of Illinois Chicago