Recursive Sparse Attention: Million-Token Length Extrapolation at Logarithmic Cost
Organizations: University of California, San Diego · Carnegie Mellon University
Abstract
At context lengths of about 1M tokens, dense attention is costly in prefill and decoding, and training typically relies on long documents, which become scarcer as the target length increases. Most sparse attention methods score all preceding blocks or tokens, so their selection cost per query is at context length ; hierarchical selection reduces it to , but prior trainable hierarchical methods report accuracy only within their training length. We propose RecSA (Recursive Sparse Attention), which builds a tree over the KV cache in which each node summarizes its subtree with one key and one mean-pooled value. The keys come from one pooler per layer, shared by all levels and distilled from dense attention. Each level above the tokens selects at most candidates, so each query has selection cost and reads entries; the summaries of unselected candidates share one softmax with the exact tokens. Each entry's RoPE position is its index among the candidates of its level, so at any length every relative distance stays within the range seen during training. Initialized from Qwen3-4B and trained on 0.62B tokens at the original model's 32K training length, RecSA outperforms all baselines on RULER at every length from 131K to 2M; at 1M, it scores 60.5, compared with 40.0 for the best baseline, Dense + DCA. With our optimized kernels, RecSA is faster than dense attention in end-to-end prefill and decoding from 64K to 2M; at 524K on one H200 GPU, it accelerates prefill by 3.2x and decoding by 3.8x.
Figures & tables
| Method | 32K | 131K | 262K | 524K | 1M | 2M |
|---|---|---|---|---|---|---|
| Token budget | 5,888 | 8,192 | 8,704 | 9,728 | 11,575 | 11,990 |
| % of context | 18.0 | 6.25 | 3.32 | 1.86 | 1.16 | 0.60 |
| Training-free | ||||||
| InfLLM | 45.0 | 29.3 | 29.2 | 27.4 | 25.7 | 24.2 |
| InfiniteHiP | 79.6 | 63.7 | 57.7 | 49.4 | 36.6 | 34.0 |
| Trained at 32K | ||||||
| Retrieval | Tracing | Aggregation | QA | |||||||||||
| Method | S1 | S2 | S3 | MK1 | MK2 | MK3 | MV | MQ | VT | CWE | FWE | QA1 | QA2 | Avg |
| 131K | ||||||||||||||
| InfLLM | 100.0 | 7.1 | 0.0 | 5.4 | 57.1 | 0.0 | 7.6 | 3.6 | 60.0 | 36.4 | 86.3 | 8.9 | 8.9 | 29.3 |
| InfiniteHiP | 100.0 | 91.1 | 91.1 | 73.2 | 32.1 | 0.0 | 76.3 | 86.6 | 57.1 | 55.9 | 86.3 | 55.4 | 23.2 | 63.7 |
| Dense + YaRN | 100.0 | 100.0 | 98.2 | 94.6 | 64.3 | 41.1 | 91.5 | 94.6 | 95.7 | 70.7 | 85.7 | 58.9 | 44.6 | 80.0 |
| Dense + DCA | 100.0 | 98.2 | 100.0 | 78.6 | 73.2 | 41.1 | 81.7 | 94.6 | 90.4 | 79.3 | 90.5 | 60.7 | 32.1 | 78.5 |
| Method | 32K | 131K | 262K | 524K | 1M |
|---|---|---|---|---|---|
| Trained at 32K | |||||
| Dense + YaRN | 11.17 | 11.81 | 16.96 | 60.94 | 211.33 |
| Dense + DCA | 11.17 | 11.27 | 12.20 | 13.39 | 14.57 |
| MoBA + YaRN | 12.11 | 13.51 | 20.43 | 122.30 | 414.69 |
| MoBA + DCA | 12.11 | 12.87 | 14.85 | 17.12 | 19.18 |
| DSA + YaRN | 11.15 | 11.81 | 15.23 | 25.88 | 54.42 |
| Benchmark | Qwen3-4B | RecSA |
|---|---|---|
| MMLU (5-shot) | 70.1 | 70.5 |
| ARC-C (0-shot) | 87.2 | 88.1 |
| GSM8K (0-shot, CoT) | 91.5 | 90.7 |
| IFEval (prompt, strict) | 79.1 | 78.6 |
| HumanEval (0-shot, pass@1) | 82.3 | 81.7 |
| MBPP (0-shot, pass@1) | 63.6 | 61.8 |
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
| w/o MLP term | RecSA | |
|---|---|---|
| on level-1 needle nodes | 0.23 | 0.52 |
| LSE node score | 1.21 | 0.34 |
| Recall | 0.468 | 0.625 |
| 32K | S1 | S2 | S3 | MK1 | MK2 | MK3 | MV | MQ | VT | CWE | FWE | QA1 | QA2 | Avg |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| InfLLM | 100.0 | 17.9 | 32.1 | 32.1 | 67.9 | 10.7 | 29.0 | 36.6 | 57.1 | 56.1 | 81.0 | 39.3 | 25.0 | 45.0 |
| InfiniteHiP | 100.0 | 98.2 | 100.0 | 96.4 | 58.9 | 19.6 | 95.1 | 99.6 | 53.2 | 76.2 | 82.7 | 87.5 | 67.9 | 79.6 |
| Dense + YaRN | 100.0 | 98.2 | 100.0 | 100.0 | 94.6 | 100.0 | 99.6 | 100.0 | 99.3 | 93.2 | 89.9 | 87.5 | 66.1 | 94.5 |
| Dense + DCA | 100.0 | 98.2 | 100.0 | 100.0 | 96.4 | 100.0 | 99.6 | 100.0 | 99.3 | 93.4 | 89.9 | 87.5 | 66.1 | 94.6 |
| MoBA + YaRN | 100.0 | 71.4 | 96.4 | 76.8 | 76.8 | 89.3 | 67.0 | 72.3 | 94.6 | 86.6 | 90.5 | 82.1 | 57.1 | 81.6 |
| MoBA + DCA | 100.0 | 71.4 | 91.1 | 78.6 | 80.4 | 87.5 | 64.7 | 77.7 | 95.4 | 85.7 | 91.1 | 82.1 | 57.1 | 81.8 |
| 524K | S1 | S2 | S3 | MK1 | MK2 | MK3 | MV | MQ | VT | CWE | FWE | QA1 | QA2 | Avg |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| InfLLM | 100.0 | 10.0 | 0.0 | 10.0 | 25.0 | 0.0 | 2.5 | 3.8 | 68.0 | 10.0 | 81.7 | 30.0 | 15.0 | 27.4 |
| InfiniteHiP | 95.0 | 75.0 | 80.0 | 65.0 | 10.0 | 0.0 | 55.0 | 63.8 | 50.0 | 10.5 | 83.3 | 35.0 | 20.0 | 49.4 |
| Dense + YaRN | 10.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 31.7 | 0.0 | 5.0 | 3.6 |
| Dense + DCA | 100.0 | 85.0 | 90.0 | 55.0 | 70.0 | 0.0 | 67.5 | 55.0 | 76.0 | 12.0 | 88.3 | 35.0 | 20.0 | 58.0 |
| MoBA + YaRN | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 11.7 | 0.0 | 0.0 | 0.9 |
| MoBA + DCA | 85.0 | 0.0 | 5.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 38.0 | 6.0 | 76.7 | 10.0 | 15.0 | 18.1 |
| Benchmark | Qwen3-4B | Dense | RecSA |
|---|---|---|---|
| MMLU (5-shot) | 70.1 | 70.3 | 70.5 |
| ARC-C (0-shot) | 87.2 | 86.9 | 88.1 |
| GSM8K (0-shot, CoT) | 91.5 | 90.9 | 90.7 |
| IFEval (prompt, strict) | 79.1 | 79.5 | 78.6 |
| HumanEval (0-shot, pass@1) | 82.3 | 81.1 | 81.7 |
| MBPP (0-shot, pass@1) | 63.6 | 60.8 | 61.8 |
| Method | All (229) | 70K–131K (79) | 131K–262K (106) | 262K–524K (40) | 524K–746K (4) |
|---|---|---|---|---|---|
| Qwen3-4B + YaRN | 34.5 | 64.6 | 20.8 | 15.0 | 0.0 |
| InfiniteHiP | 66.4 | 67.1 | 68.9 | 57.5 | 75.0 |
| Dense + DCA | 62.4 | 69.6 | 64.2 | 45.0 | 50.0 |
| DSA + DCA | 62.0 | 64.6 | 65.1 | 52.5 | 25.0 |
| RecSA (ours) | 66.8 | 74.7 | 66.0 | 55.0 | 50.0 |
| Title | Gutenberg ID | Tokens |
|---|---|---|
| Modern Machine-Shop Practice, Vols. I and II | 39225 | 1,261,044 |
| The Bible, King James Version | 30 | 1,405,554 |
| History of the United Netherlands, 1584–1609 | 4885 | 1,003,719 |
| The Anatomy of Melancholy | 10800 | 1,000,033 |
| The Complete Memoirs of Jacques Casanova de Seingalt | 2981 | 1,531,970 |
| The History of England, Vol. II (Smollett) | 19217 | 1,099,801 |
| Prefill (s) | Decoding (ms) | |||
| Context length | RecSA | Dense | RecSA | Dense |
| 32K | 1.59 | 1.46 | 4.88 | 5.29 |
| 64K | 3.87 | 4.66 | 5.99 | 6.41 |
| 131K | 13.5 | 16.8 | 6.04 | 8.56 |
| 262K | 34.2 | 65.0 | 6.06 | 13.3 |
| 524K | 79.8 | 257 | 6.15 | 23.4 |
| Context length | 32K | 131K | 262K | 524K | 1M | 2M |
|---|---|---|---|---|---|---|
| Tree levels | 2 | 3 | 3 | 3 | 3 | 4 |
| Non-attention | 3.26 | 3.35 | 3.35 | 3.35 | 3.41 | 3.40 |
| Tree update | 0.25 | 0.39 | 0.39 | 0.39 | 0.63 | 0.87 |
| Top level | 0.89 | 0.73 | 0.80 | 0.91 | 1.24 | 0.70 |
| Intermediate levels | – | 1.03 | 0.98 | 0.96 | 0.98 | 2.01 |
| Gather | – | – | – | – | 1.55 | 3.07 |
| Context length | 131K | 262K | 524K | 1M | 2M |
|---|---|---|---|---|---|
| RecSA tree levels | 3 | 3 | 3 | 3 | 4 |
| Level-1 nodes | 8,192 | 16,384 | 32,768 | 62,500 | 125,000 |
| RecSA | 6.04 | 6.06 | 6.15 | 8.35 | 10.7 |
| Two-level variant | 6.37 | 7.11 | 7.83 | 11.5 | 20.5 |
| Speedup of RecSA |
| Data | Pool | Stage 1 | Stage 2 | Length |
| Task data | ||||
| Synthetic retrieval | 5,500 | 4,769 | 4,760 | 32,060–32,456 |
| Document QA | 958 | 831 | 840 | 32,749–32,787 |
| General data | ||||
| Books and code | 420 | 295 | 295 | 32,741–32,768 |
| Instructions | 588 | 398 | 398 | 32,768 |
| Stage 1 | |||
| First part | Second part | Stage 2 | |
| Parameters | , , | , , | backbone |
| Count | 4,680 | 887,040 | 4.02B |
| Loss | LM | ||
| 64 | 64 | 256 | |
| Learning rate | |||
| 32K | 131K | 262K | 524K | 1M | 2M | |
| Token budget | 5,888 | 8,192 | 8,704 | 9,728 | 11,575 | 11,990 |
| MoBA blocks | 46 | 64 | 68 | 76 | 90 | 93 |
| InfLLM | ||||||
| Initial | 128 | 128 | 128 | 256 | 256 | 256 |
| Local | 3,840 | 5,376 | 5,760 | 6,272 | 7,479 | 7,766 |
| Blocks | 15 | 21 | 22 | 25 | 30 | 31 |
| Variant | 32K | 131K | 262K | 524K | 1M | Avg |
|---|---|---|---|---|---|---|
| RecSA | 94.7 | 83.3 | 75.9 | 69.7 | 60.5 | 72.3 |
| w/o summaries | 94.5 | 81.8 | 73.6 | 67.5 | 58.5 | 70.4 |
| w/o MLP term | 94.8 | 80.0 | 64.4 | 50.4 | 37.1 | 58.0 |
| standard RoPE + YaRN | 95.2 | 66.2 | 22.1 | 1.9 | 1.9 | 23.0 |
| standard RoPE | 95.2 | 1.0 | 0.0 | 0.0 | 0.0 | 0.3 |
| top- 128 | 94.3 | 77.6 | 69.7 | 67.4 | 52.7 | 66.9 |
Sparse Attention
Sparse attention reduces the token interactions computed by Transformers to lower the cost of long-context modeling and inference.
See all 271 papers