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 O(L) at context length L; hierarchical selection reduces it to O(logL), 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 k candidates, so each query has O(logL) selection cost and reads O(logL) 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
Figure 1: RULER score and decoding latency from 32K to 2M. (b) End-to-end latency on one H200 GPU with batch size 1; Dense uses FlashAttention in the same framework. At 1M and 2M, host memory holds the exact tokens of RecSA (§ 4.3 ) and the part of the Dense KV cache beyond GPU memory; hollow markers indicate offloading. Arrows mark off-scale values. Percentages show the token budget of RecSA as a fraction of the context length.
Figure 2: One attention layer of RecSA ( 220 tokens, C=16 , k=256 , three levels). (a) The pooler computes the key Ki of a node from the keys of its 16 children; its value Vi is the mean of their values. (b) s is the score of each candidate for the query qt (Eq. ( 2 )); levels 2 and 1 each select 256 candidates by this score, whose children form the next candidate list, and level 0 has no selection; pruned nodes are not candidates. (c) Summaries and exact tokens share one softmax, with output ot .
Figure 3: Relative distance to the query qt , the last of 64 tokens. (a) RoPE and ReRoPE ( Su, 2023 ) ; gray bars stand for runs of tokens. (b) Candidate-local RoPE on an example tree with C=4 children per node and k=2 selected nodes per level: each selected node is drawn above its children, and at every level the distances stay below Ck=8 . Dashed spans mark parts of the sequence skipped between candidates; they receive no positions.
Figure 4: Prefill and decoding of RecSA . (a) Prefill: rows correspond to the 16 adjacent queries of one thread block and columns to the union of the parent nodes they selected; numbers give the slot m of the parent node for the query of the row. The black frame marks one block (the 16 children of a parent node), loaded once per pass and shared by the queries that selected its parent. (b) Decoding with KV offloading: blue indicates selected nodes and blocks, light orange unselected candidates (summaries) and gray other nodes.
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
Table 1: RULER score (average over the 13 tasks) by context length. Token budget: entries the query at the last position attends to (for RecSA , exact tokens plus summaries), matched across the sparse methods. Best results are in bold.
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
Table 2: RULER score per task at 131K and 1M. Retrieval: needle-in-a-haystack tasks with a single needle (S1–S3), multiple keys (MK1–MK3), multiple values (MV) or multiple queries (MQ). VT: variable tracking. CWE: common words extraction. FWE: frequent words extraction. QA1: SQuAD ( Rajpurkar et al., 2016 ) . QA2: HotpotQA ( Yang et al., 2018 ) . Best results in each column at each length are in bold. Appendix B gives the scores at all lengths.
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
Table 3: Perplexity on nine PG-19 books ( Rae et al., 2020 ) by context length. Sparse methods use the token budgets of Table 1 . InfLLM and InfiniteHiP are not listed because their key selection during prefill is not causal. Best results are in bold.
Figure 5: Efficiency on one H200 GPU with batch size 1. (a) Prefill time per token of RecSA and of Dense with FlashAttention in the same framework; hollow markers indicate RecSA with offloading (§ 4.3 ), and arrows mark values above the axis range. (b) Time breakdown of one decoding step of RecSA . Non-attention: the remaining step time, including the projections, the MLPs and the idle time between kernels. Gather: gathering the selected exact tokens from host memory and from the GPU cache (§ 4.3 ).
Figure 6: RULER score in the ablation experiments. (a) Position encoding. Standard RoPE applies RoPE at absolute token positions and is evaluated with and without YaRN beyond 32K. (b) Pooler. KL and the shift penalty are the losses of Eqs. ( 6 ) and ( 7 ), and LM loss trains the MLP term with the language modeling loss. Backbone frozen: each pooler is trained on the original model and evaluated with it at 32K, 131K and 524K. Backbone trained: for KL + shift penalty and w/o MLP term, the backbone is then trained as in Stage 2. KL + shift penalty is the pooler of RecSA . (c) RecSA evaluated with k=128 , 256 and 512. Appendix F gives all scores.
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
Table 4: Scores on short-context benchmarks and long-document tasks. LongBench ( Bai et al., 2024 ) : average score over 12 English tasks and 2 code tasks. En.MC: multiple-choice questions about full-length novels from InfiniteBench ( Zhang et al., 2024 ) , with inputs of 70K–746K tokens; Qwen3-4B uses YaRN for context extension on En.MC. Best results in each row are in bold.
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
Appendix
Table A.1: The MLP term on needle nodes, the nodes that contain evidence for the answer. 131K, 28 RULER samples, queries of the first four answer tokens; w/o MLP term: W2=0 . α : the sum of the weights of the level-1 needle nodes among the 16 children of a level-2 needle node (0.14 if all children had equal weight). LSE: LogSumExp of the token scores below a node; the row LSE − node score is for level-2 needle nodes; scores are centered over the nodes of each query. Recall: fraction of queries for which a level-2 needle node is among the top 1/8 of the level-2 nodes (0.635 when nodes are ranked by LSE).
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
Appendix
Table B.1: RULER score per task, 32K–262K. The best Avg among the methods of Table 1 is in bold.
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
Appendix
Table B.2: RULER score per task, 524K–2M (continued from Table B.1 ). The best Avg among the methods of Table 1 is in bold. † : the first 4 of the 20 samples of each task.
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
Appendix
Table C.1: Scores of the original Qwen3-4B, the Dense backbone and RecSA . Dense is trained from Qwen3-4B with the settings of Stage 2 on the same sequences as RecSA (Section 5.1). Best results in each row are in bold.
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
Appendix
Table C.2: En.MC scores. The last four columns group the questions by input length, with the number of questions in parentheses. Best results in each column are in bold.
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
Appendix
Table C.3: The nine PG-19 books. Tokens: length of the whole book.
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
Appendix
Table D.1: Prefill time (s) and decoding latency (ms per token) of RecSA and Dense. At 1M and 2M, host memory holds the exact tokens of RecSA and, in decoding, the part of the Dense KV cache that does not fit on the GPU.
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
Appendix
Table D.2: Time breakdown (ms) of one decoding step of RecSA (Figure 5b). The time of a kernel that serves two adjacent levels is split between them in proportion to the time of the work of each level run alone. –: the part does not occur at this length.
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
1.1×
1.2×
1.3×
1.4×
1.9×
Appendix
Table D.3: Decoding latency (ms per token) of RecSA and of a two-level variant, which scores every level-1 node at each step, measured as in Appendix D.1 . Up to 65,536 tokens, RecSA uses at most two levels. At 1M and 2M, both store the exact tokens in host memory.
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
Appendix
Table E.1: Training data. Pool: sequences available for training. Stage 1 and Stage 2: sequences read by each run. Length: tokens per sequence in the pool, chat template included.
Stage 1
First part
Second part
Stage 2
Parameters
w , τ , g
W1 , b1 , W2
backbone
Count
4,680
887,040
4.02B
Loss
LKL+0.1Laux
LKL+10Lshift
LM
k
64
64
256
Learning rate
10−2
3×10−3
2.5×10−6
Appendix
Table E.2: Hyperparameters of RecSA training. Each run trains only the listed parameters; all other parameters are frozen. LKL : the KL terms of each part, with the query positions and weights of Appendix E.3 . Laux : auxiliary cross-entropy. Lshift : shift penalty (Eq. (7)), with weight λ=10 . LM: language modeling loss. Learning rate: peak value. Batch size: sequences per optimizer step. Accumulation: gradient accumulation steps. Time: wall-clock time of the training loop, including checkpointing.
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
Appendix
Table E.3: Settings of the baselines at each context length. Token budget: entries the query at the last position attends to under RecSA (Table 1); DSA uses it as k . MoBA: selected blocks of 128 tokens, the current block included. InfLLM: initial tokens, local window and retrieved blocks of 128 tokens. InfiniteHiP: sink tokens, sliding window and selected tokens. YaRN: scaling factor s ; –: not applied.
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- k 128
94.3
77.6
69.7
67.4
52.7
66.9
Appendix
Table F.1: RULER score in the ablation experiments (average over the 13 tasks). Avg: average over the four lengths from 131K to 1M. –: not evaluated.