Coarse Semantic Blocks for Efficient Training-Free Sparse Attention
Organizations: Preferred Networks
Abstract
We introduce a training-free sparse attention method that builds a prompt-specific key index to accelerate both prefill and decoding. The method clusters the keys into large semantic blocks that group tokens from noncontiguous positions. Each query position selects blocks by scoring their centroids and attends to the original keys and values within them. Queries that select the same block are processed together, so prefill stays fast even though each query chooses its own blocks. Large blocks make centroid scoring and this grouped processing cheap, so each query can attend to more tokens in the same time. Larger blocks with a larger token budget can thus be both faster and more accurate on long-context tasks than smaller blocks with a smaller budget. We evaluate two hybrid LLMs, Qwen3.5-4B and 35B-A3B, on one NVIDIA H200. Including the cost of building and using the index, whole-model wall-clock speedups over dense attention are 2.3-2.4x for prefill and 1.7-2.0x for decoding at 512K tokens, and 2.9-3.0x for prefill at 1M. The 35B-A3B model stays close to dense attention on five RULER tasks through 1M, on LongBench-v2 overall, and on MRCR through 256K. The 4B model loses accuracy mainly on multi-key retrieval, yet outperforms dense Qwen3.5-2B, whose latency is similar at 512K, on all three benchmarks.
Figures & tables
| RULER-5 | MRCR-8 | LongBench-v2 | Prefill (s) | |||||||
| 256K | 512K | 1M | 128K | 256K | 512K | 256K | 256K | all | 1M | |
| 35B-A3B, dense | 85.7 | 84.4 | 73.2 | 0.846 | 0.655 | 0.564 | 64.4 | 66.2 | 64.7 | 173.5 |
| 35B-A3B, ours | 84.5 | 84.2 | 73.9 | 0.844 | 0.668 | 0.504 | 63.1 | 64.7 | 63.3 | 57.4 |
| 4B, dense | 84.7 | 82.8 | 63.2 | 0.797 | 0.574 | 0.412 | 54.3 | 64.2 | 55.7 | 144.1 |
| 4B, ours | 82.7 | 81.8 | 55.2 | 0.788 | 0.561 | 0.399 | 53.9 | 57.7 | 54.5 | 49.3 |
| 2B, dense | 77.7 | 66.5 | 48.9 | 0.726 | 0.414 | 0.198 | 36.7 | 34.3 | 36.4 | 56.2 |
| Centroids fitted on | MK-3 | MK-2 | Hotpot | CWE |
|---|---|---|---|---|
| Dense attention | 96.0 | 99.0 | 56.0 | 63.0 |
| Each prompt (ours) | 92.7 | 95.0 | 57.0 | 64.3 |
| Each prompt’s first 64K | 95.0 | 95.0 | 56.0 | 66.1 |
| A raw-text corpus | 1.0 | 12.0 | 51.0 | failed |
| RULER-5 examples | 91.0 | 90.0 | 55.0 | 64.6 |
Appendix figures & tables48 assets
Supplementary material from the paper’s appendix.
Appendix
| Prompt length | Clusters | Mean block size | Keys used to fit |
|---|---|---|---|
| 128K | 128 | 1,024 | 8,192 |
| 256K | 128 | 2,048 | 8,192 |
| 512K | 256 | 2,048 | 8,192 |
| 1M | 512 | 2,046 | 16,384 |
| Quantity | Value |
|---|---|
| Replaced layers | Eight full-attention layers of 32 |
| Query / KV heads | 16 / 4, head dimension 256 |
| Routing | Pre-RoPE Q/K, whole-vector normalization, identity map |
| Target mean block size | , which sets the cluster count of Table 3 |
| Clustering | Eight iterations, sampled keys. The main RULER results average seeds 0–2, and other results use seed 0 unless stated otherwise (Appendix C.4 ) |
| Score parameters | , |
| Dense attention, chunked | Ours, single-pass | Ours, sliced |
| for each 16K-token chunk: for each layer: Q, K, V <- project(chunk) attend(chunk, KV so far) feed-forward(chunk) | for each layer: Q, K, V <- project(all) fit index on all keys for each 8K query chunk: select, attend feed-forward(all) | for each layer: for each 32K slice: K, V <- project(slice) fit index on all keys for each 32K slice: Q <- project(slice) for each 8K query chunk: select, attend feed-forward(slice) |
| Method | Length / schedule | Weights | KV cache etc. | Transient | Total |
|---|---|---|---|---|---|
| Dense (derived) | 512K / chunked | 8.35 | 16.00 | 1.58 | 25.93 |
| Ours (measured) | 512K / single-pass | 8.35 | 20.84 | 53.50 | 82.69 |
| Ours (measured) | 512K / sliced | 8.35 | 20.84 | 11.91 | 41.09 |
| Ours, prefix index (measured) | 512K / chunked | 8.35 | 20.86 | 6.43 | 35.64 |
| Dense (derived) | 1M / chunked | 8.35 | 31.97 | 1.58 | 41.90 |
| Ours (measured) | 1M / sliced | 8.35 | 39.65 | 22.37 | 70.37 |
| Model | Task | Length | Seeding | Mean (s.d.) |
|---|---|---|---|---|
| Qwen3.5-4B | MK-2 | 512K | random | 95.0 (1.0) |
| farthest | 92.7 (1.5) | |||
| -means++ | 91.7 (1.5) | |||
| MK-3 | 512K | random | 92.7 (0.6) | |
| farthest | 94.3 (1.5) | |||
| -means++ | 92.0 (3.6) |
| Prompt | MK-3 | MK-2 | MV | CWE | HotpotQA | RULER-5 |
|---|---|---|---|---|---|---|
| 128K | 100.0 (0.0) | 98.7 (1.5) | 99.8 (0.3) | 78.3 (0.5) | 57.3 (1.2) | 86.8 (0.3) |
| 256K | 97.7 (0.6) | 91.0 (2.0) | 99.3 (0.4) | 70.3 (1.4) | 55.0 (1.0) | 82.7 (0.1) |
| 512K | 92.7 (0.6) | 95.0 (1.0) | 100.0 (0.0) | 64.3 (0.9) | 57.0 (1.0) | 81.8 (0.5) |
| 1M | 28.3 (1.5) | 68.0 (2.0) | 100.0 (0.0) | 29.4 (1.2) | 50.0 (1.0) | 55.2 (0.8) |
| S1 | S2 | S3 | MK-1 | MK-2 ∗ | MK-3 ∗ | MQ | MV ∗ | VT | CWE ∗ | FWE | SQuAD | Hotpot ∗ | Mean | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Prompt (K tokens) | 524 | 524 | 524 | 524 | 524 | 523 | 524 | 524 | 524 | 523 | 476 | 523 | 517 | |
| Dense | 100.0 | 100.0 | 100.0 | 100.0 | 99.0 | 96.0 | 99.8 | 100.0 | 100.0 | 63.0 | 99.3 | 76.1 | 56.0 | 91.5 |
| Ours | 100.0 | 100.0 | 99.0 | 100.0 | 95.0 | 92.7 | 100.0 | 100.0 | 100.0 | 64.3 | 99.0 | 79.1 | 57.0 | 91.2 |
| Ours, | 100.0 | 100.0 | 99.0 | 99.0 | 76.7 | 82.7 | 99.5 | 99.5 | 100.0 | 63.2 | 93.7 | 74.3 | 52.0 | 87.7 |
| Prompt | Method | Multi-key-3 | Multi-key-2 | Multi-value | Common-word | HotpotQA | Mean | |
|---|---|---|---|---|---|---|---|---|
| Qwen3.5-4B | ||||||||
| 128K | 8,192 | Dense | 100.0 | 100.0 | 100.0 | 78.7 | 58.0 | 87.3 |
| Ours | 100.0 | 98.7 | 99.8 | 78.3 | 57.3 | 86.8 | ||
| 2B dense | 100.0 | 100.0 | 99.8 | 77.8 | 52.0 | 85.9 | ||
| 256K | 16,384 | Dense | 100.0 | 100.0 | 100.0 | 68.3 | 55.0 | 84.7 |
| Ours | 97.7 | 91.0 | 99.3 | 70.3 | 55.0 | 82.7 | ||
| Configuration | MK-3 | MK-2 | MV |
| Dense, no extension | 56.0 | 91.0 | 98.8 |
| Dense, YaRN | 89.0 | 94.0 | 99.5 |
| Dense, YaRN | 74.0 | 95.0 | 100.0 |
| Dense, , interp only | 77.0 | 98.0 | 100.0 |
| Dense, interpolation only | 96.0 | 99.0 | 100.0 |
| Ours, no extension | 46.0 | 66.0 | 99.8 |
| RULER-5 | Tasks at 512K | ||||||||
| Method | 128K | 256K | 512K | 1M | MK-3 | MK-2 | MV | CWE | HotpotQA |
| Qwen3.5-4B | |||||||||
| Dense | 87.3 | 84.7 | 82.8 | 63.2 | 96.0 | 99.0 | 100.0 | 63.0 | 56.0 |
| Ours | 86.8 | 82.7 | 81.8 | 55.2 | 92.7 | 95.0 | 100.0 | 64.3 | 57.0 |
| Ours with initial block | 87.0 | 83.6 | 82.5 | 56.6 | 95.0 | 94.7 | 99.2 | 66.2 | 57.3 |
| Qwen3.5-35B-A3B | |||||||||
| MRCR-8 | LongBench-v2 | |||||
| Method | 128K | 256K | 512K | 256K | 256K | all |
| Qwen3.5-4B | ||||||
| Dense | 0.797 (0.053) | 0.574 (0.010) | 0.412 (0.027) | 54.3 (1.1) | 64.2 (2.6) | 55.7 (0.7) |
| Ours | 0.788 (0.056) | 0.561 (0.029) | 0.399 (0.013) | 53.9 (1.0) | 57.7 (2.3) | 54.5 (0.6) |
| Ours with initial block | 0.783 (0.024) | 0.561 (0.068) | 0.415 (0.022) | 55.5 (0.9) | 57.2 (3.1) | 55.7 (0.4) |
| Qwen3.5-35B-A3B | ||||||
| Prefill (s) | Decode (ms/token) | |||||||
| Whole model | Attention layers (8) | Whole model | Attention layers (8) | |||||
| Prompt | Dense | Ours | Dense | Ours | Dense | Ours | Dense | Ours |
| 128K | 4.18 | 3.11 | 1.92 | 0.84 | 4.87 | 4.07 | 1.29 | 0.34 |
| 256K | 12.37 | 7.06 | 7.75 | 2.34 | 6.14 | 4.16 | 2.41 | 0.43 |
| 512K | 40.69 | 17.39 | 31.81 | 8.18 | 8.69 | 4.41 | 5.00 | 0.66 |
| 1M | 144.08 | 49.30 | 125.47 | 29.79 | 13.93 | 4.84 | 10.51 | 1.03 |
| Dense | Ours | |
|---|---|---|
| Attention (8 attention layers) | 31.4 | 6.4 |
| selected blocks | 4.02 | |
| dense prefix | 2.02 | |
| current chunk | 0.34 | |
| Scoring, selection, index build (ours) | 0.0 | 0.3 |
| score the centroids and select | 0.24 |
| GPU seconds of one 512K prefill | Accuracy (%) | ||||||||
| Setting | Selected blocks | Dense prefix | Own chunk | Attention | Scoring | Gather, merge | Total | MK-3 | MK-2 |
| Dense attention | — | — | — | 31.44 | — | — | 40.30 | 96.0 | 99.0 |
| (ours) | 4.02 | 2.03 | 0.34 | 6.38 | 0.24 | 1.48 | 17.07 | 96.0 | 97.0 |
| 5.02 | 0.53 | 0.40 | 5.95 | 0.27 | 1.81 | 17.03 | 94.0 | 94.0 | |
| 5.65 | 0.16 | 0.43 | 6.24 | 0.29 | 2.10 | 17.64 | 93.0 | 93.0 | |
| Execution | Prefill (s) | Decode (ms/token) |
|---|---|---|
| Dense attention | 40.69 | 9.27 |
| Ours: KV-outer over one cluster-ordered copy | 18.51 | 4.49 |
| Selected blocks gathered from prompt order every chunk | 20.24 | 4.45 |
| Same selection, Q-outer instead of KV-outer | 47.56 | 4.29 |
| Selection by a GEMM and a sort | 19.09 | 4.56 |
| 64 generated | 65,536 generated | |
|---|---|---|
| Dense | 15.39 | 16.06 |
| Ours | 4.81 | 7.85 |
| Ours, flushed every 8K ( ) | 4.83 | 5.09 |
| Ours, flushed every 1K ( ) | 4.82 | 4.82 |
| Dense | Ours | Ours, flushed | |
|---|---|---|---|
| 256K (403 items) | 53.1 | 54.8 | 53.8 |
| 256K (67 items) | 65.7 | 61.2 | 58.2 |
| All (470) | 54.9 | 55.7 | 54.5 |
| Routing key | MK-3 | MK-2 | MV |
|---|---|---|---|
| Dense | 96.0 | 99.0 | 100.0 |
| Whole key, normalized, (ours) | 92.7 | 95.0 | 100.0 |
| Whole key after RoPE, normalized, | 93.0 | 94.0 | 100.0 |
| Non-rotary 192 dimensions, normalized, | 93.0 | 95.7 | 99.5 |
| Raw key, Euclidean -means, | 91.0 | 93.0 | 99.3 |
| Raw key, Euclidean -means, | 95.0 | 96.0 | 100.0 |
| MK-2 (%) at | Prefill (s) at | |||||||
|---|---|---|---|---|---|---|---|---|
| 8K | 16K | 32K | 64K | 8K | 16K | 32K | 64K | |
| Dense | 99.0 | 40.69 | ||||||
| 4,096 | 32.0 | 62.0 | 90.0 | 100.0 | 12.66 | 14.05 | 16.78 | 23.47 |
| 2,048 | 40.0 | 75.0 | 95.0 | 99.0 | 13.40 | 14.98 | 17.86 | 24.30 |
| 1,024 | 56.0 | 87.0 | 97.0 | 100.0 | 15.30 | 17.31 | 20.42 | 26.14 |
| 512 | 73.0 | 86.0 | 97.0 | 99.0 | 18.97 | 22.21 | 25.59 | 30.05 |
| MK-3 (%) at | MK-2 (%) at | Prefill (s) at | ||||||||||
| 8K | 16K | 32K | 64K | 8K | 16K | 32K | 64K | 8K | 16K | 32K | 64K | |
| Qwen3.5-4B | ||||||||||||
| Dense | 96.0 | 99.0 | 40.69 | |||||||||
| 4,096 | 31.0 | 76.0 | 91.0 | 94.0 | 32.0 | 62.0 | 90.0 | 100.0 | 12.66 | 14.05 | 16.78 | 23.47 |
| 2,048 | 58.0 | 88.0 | 92.7 | 97.0 | 40.0 | 75.0 | 95.0 | 99.0 | 13.40 | 14.98 | 17.86 | 24.30 |
| 1,024 | 81.0 | 87.0 | 94.0 | – | 56.0 | 87.0 | 97.0 | 100.0 | 15.30 | 17.31 | 20.42 | 26.14 |
| Prompt | Dense | ||||
|---|---|---|---|---|---|
| 256K | 100 (12.4 s) | 97 (1.36 ) | 97.7 (1.74 ) | 88 (1.86 ) | 42 (1.98 ) |
| 512K | 96 (40.7 s) | 95 (1.62 ) | 92.7 (2.25 ) | 89 (2.68 ) | 57 (2.98 ) |
| 1M | 40 (144.1 s) | 32 (1.83 ) | 28.3 (2.84 ) | 24 (3.68 ) | 18 (4.33 ) |
| MK-3 (%), initial block | MK-2 (%), initial block | ||||||
| Index | Without | With | Without | With | Prefill (s) | ||
| Positional, shared | 2,048 | 64 | 7 | 4 | – | – | 15.6 |
| 128 | 64 | 27 | 32 | – | – | 16.2 | |
| 32 | 64 | 51 | 64 | 24 | 24 | 18.4 | |
| 16 | 64 | 63 | 79 | 32 | 36 | 21.5 | |
| 8 | 64 | 77 | 92 | 51 | 53 | 27.5 | |
| Index | MK-3 (%) | MK-2 (%) | Prefill (s) | ||
| Positional, shared | 16 | 64 | 78 | 58 | 30.8 |
| 32 | 32 | 84 | 63 | 22.5 | |
| 16 | 32 | 93 | 66 | 27.4 | |
| 8 | 32 | 99 | 84 | 37.1 | |
| Positional, per query | 128 | 1 | 55 | 47 | 34.4 |
| Ours, per query | – | 1 | 99 | 97 | 20.4 |
| MK-3 (%), initial block | MK-2 (%), initial block | ||||||
| Index | Without | With | Without | With | Prefill (s) | ||
| Positional, shared | 16 | 32 | 71 | 83 | 32 | 36 | 22.1 |
| 8 | 64 | 61 | 81 | 39 | 48 | 26.8 | |
| 8 | 32 | 72 | 88 | 49 | 60 | 32.0 | |
| 4 | 32 | 64 | 79 | 58 | 62 | 51.5 | |
| Positional, per query | 32 | 1 | 68 | 69 | 47 | 50 | – |
| Accuracy (%) | Time at 512K (s) | ||||
| Method | Engine | MK-3 | MK-2 | MK-3 run | MK-2 run |
| Dense attention | vLLM | 96.0 | 99.0 | 40.18 | |
| Ours, | vLLM | 88.0 | 75.0 | 14.98 | |
| Ours, | vLLM | 93.0 | 94.0 | 17.86 | |
| Ours, | vLLM | 97.0 | 99.0 | 24.30 | |
| Ours, , initial block | vLLM | 95.0 | 94.7 | 18.69 | |
| Prompt attention retained (%) | ||||
|---|---|---|---|---|
| Task | Our scores | Dense-ranked clusters | Dense-ranked tokens | |
| MK-2 | 77.4 | 80.8 | 90.4 | |
| MK-2 | 84.6 | 87.3 | 94.3 | |
| MK-3 | 76.9 | 80.5 | 91.9 | |
| MK-3 | 84.0 | 86.8 | 95.1 | |
| MRCR-8 | 86.3 | 88.2 | 94.2 | |
| Selection | MK-3 | MK-2 |
|---|---|---|
| Dense attention | 96.0 | 98.0 |
| Centroid scores | 93.3 (1.2) | 96.0 (0.0) |
| Dense attention mass | 94.0 | 98.0 |
| Objective | Rule | 512K | RULER-5 | MRCR-8 | |||||
|---|---|---|---|---|---|---|---|---|---|
| Configuration | KL | mass at | MK-3 | MK-2 | 256K | 512K | 512K | ||
| Dense attention | – | – | – | – | 96.0 | 99.0 | 84.7 | 82.8 | 0.381 |
| Identity map (ours) | 1.07 | 0.674 | 0.10 | 0.25 | 92.7 (0.6) | 95.0 (1.0) | 82.7 (0.1) | 81.8 (0.5) | 0.405 |
| Learned | 0.31 | 0.695 | 0.036 | 0 | 91.0 (1.0) | 94.7 (0.6) | 83.1 (0.2) | 81.5 (0.4) | 0.402 |
| 128K | 512K | ||||
|---|---|---|---|---|---|
| Adapters | MK-2 | MK-3 | MK-2 | MK-3 | MRCR-8 |
| Dense | 100 | 100 | 99 | 96 | 0.381 |
| Ours, no training | 98 | 100 | 94 | 93 | 0.405 |
| Attention | 99 | 99 | 92 | 91 | 0.298 |
| +MLP+GDN | 100 | 99 | 95 | 90 | 0.291 |
| Whole model | Attention layers (10) | ||||
| Prompt | Configuration | Prefill (s) | Decode (ms) | Prefill (s) | Decode (ms) |
| 128K | Dense | 4.75 | 5.72 | 2.41 | 0.92 |
| 128K | Ours | 3.31 | 4.91 | 0.96 | 0.30 |
| 256K | Dense | 14.77 | 6.64 | 9.58 | 1.56 |
| 256K | Ours | 7.76 | 4.98 | 2.69 | 0.37 |
| 512K | Dense | 49.19 | 8.68 | 39.25 | 2.98 |
| Configuration | 64 | 65,536 |
|---|---|---|
| Dense | 12.90 | 13.42 |
| Ours | 5.57 | 9.21 |
| Ours, flushed every 1K ( ) | 5.55 | 5.49 |
| Ours, flushed every 8K ( ) | 5.57 | 5.91 |
| MRCR-8 | LongBench-v2 | |||||
|---|---|---|---|---|---|---|
| 128K | 256K | 512K | 256K | 256K | all | |
| Dense | 0.849 | 0.644 | 0.500 | 65.3 | 65.7 | 65.3 |
| Ours, | 0.835 | 0.596 | 0.463 | 64.3 | 65.7 | 64.5 |
| Ours, | 0.839 | 0.682 | 0.437 | 62.3 | 64.2 | 62.6 |
| Ours, , flushed | – | – | – | 63.0 | 71.6 | 64.3 |
| Routing representation | MK-3 |
|---|---|
| Dense | 100 |
| Uncentered keys | 20 |
| Centered, 32 iterations, 128 samples per centroid | 100 |
| Whitened | 40 |
| Whitened, -means++ seeding, 32 iterations | 35 |
| Whole model | Attention layers (6) | |||||
| Prompt | Configuration | MK-3 (%) | Prefill (s) | Decode (ms) | Prefill (s) | Decode (ms) |
| 256K | Dense | 100 | 11.07 | 3.92 | 6.91 | 0.51 |
| 256K | Ours, | 73 | 6.15 | 3.39 | 1.94 | 0.17 |
| 256K | Ours, | 93 | 6.82 | 3.38 | 2.34 | 0.18 |
| 256K | Ours, | 98 | 7.68 | 3.42 | 3.07 | 0.22 |
| 256K | Ours, , | 96 | 7.59 | 3.44 | 3.15 | 0.22 |
| MK-3 (%) at | MK-2 (%) at | Prefill (s) at | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 8K | 16K | 32K | 64K | 8K | 16K | 32K | 64K | 8K | 16K | 32K | 64K | |
| Dense | 100.0 | 99.0 | 35.72 | |||||||||
| 4,096 | 3.0 | 19.0 | 60.0 | 89.0 | 6.0 | 14.0 | 32.0 | 62.0 | 11.30 | 12.46 | 14.80 | 19.96 |
| 2,048 | 11.0 | 35.0 | 84.0 | 90.0 | 7.0 | 20.0 | 49.0 | 81.0 | 11.98 | 13.26 | 15.72 | 20.75 |
| 1,024 | 25.0 | 65.0 | 87.0 | 94.0 | 17.0 | 33.0 | 72.0 | 91.0 | 12.95 | 14.55 | 17.21 | 22.24 |
| 512 | 56.0 | 79.0 | 93.0 | 97.0 | 34.0 | 62.0 | 83.0 | 95.0 | 14.81 | 16.83 | 20.09 | 25.09 |
| Method | Learned components | Sparse phases | Hybrid model | Whole-model time |
|---|---|---|---|---|
| MInference ( Jiang et al., 2024 ) | None | Prefill | No | Yes |
| FlexPrefill ( Lai et al., 2025 ) | None | Prefill | No | No |
| FlashPrefill / V2 ( Fan et al., 2026a ; Fan et al., 2026c ) | None | Prefill | No | Yes |
| QuoKA ( Jones et al., 2026 ) | None | Prefill, decode | No | Yes |
| Quest ( Tang et al., 2024 ) | None | Decode | No | Yes |
| Squeezed ( Hooper et al., 2025 ) | None | Prefill, decode | No | No |
Sparse Attention
Sparse attention reduces the token interactions computed by Transformers to lower the cost of long-context modeling and inference.
See all 274 papers