A tree-based method extends language models to million token contexts
Recursive Sparse Attention: Million-Token Length Extrapolation at Logarithmic Cost · arXiv:2611.07232
In plain words
Language models can struggle to use very long inputs because ordinary attention becomes costly, and training on documents as long as the inputs is difficult.
This paper introduces Recursive Sparse Attention (RecSA), which organizes stored information into a tree and searches the most relevant parts while keeping training sequences at the model’s original length.
On RULER, a set of synthetic long-context tasks, RecSA scored higher on average than the strongest other method at one million tokens. The result is for one model and one test setup.
The research
Very long inputs demand more attention computation, while training on equally long documents gets harder as the target length grows.
The result changes the expectation that a model must train on sequences as long as the contexts it later handles: this method was trained at 32,000 tokens and tested at much longer lengths.
Recursive Sparse Attention searches a tree of cache summaries to extend a language model’s context without training on longer sequences.
The study trains Recursive Sparse Attention (RecSA) from Qwen3-4B using only 32,000-token sequences, then compares it with trained and training-free alternatives across long-context lengths.
On RULER, a set of 13 synthetic tasks, the official score averages results across tasks; at one million tokens, RecSA scored 60.5 against 40.0 for the strongest other method, Dense + DCA.
A matched-budget comparison with DSA + DCA scored 36.8, showing that matched sparse token budgets and familiar relative positions alone do not explain RecSA’s higher score. The methods also differ in selection and training, so the comparison does not isolate one cause.
The experiments use Qwen3-4B, and the RULER task generators were reimplemented with several changes. These results describe that model and evaluation setup; they do not show how RecSA performs across other model families or all long documents.
What the evidence shows
- A tree for long contexts
Recursive Sparse Attention (RecSA) is a sparse attention method that organizes a language model’s stored information in a tree. This lets each query select parts of a long context without scoring every preceding token.
The paper targets two linked constraints: dense attention becomes costly at very long lengths, and documents long enough to train at those lengths become scarcer.
- The main comparison
The long-context scores show that RecSA’s advantage appears across a synthetic task set, rather than establishing performance on every long document.
On RULER, which tests 13 synthetic long-context tasks and averages their scores, Qwen3-4B with RecSA scored 60.5 at one million tokens, compared with 40.0 for Dense + DCA, the strongest other method at that length.
- What the contrast shows
The comparison with DSA + DCA tests whether keeping relative positions within the training range and matching the sparse methods’ token budgets are enough to explain RecSA’s score. They are not: DSA + DCA scored 36.8 on the same RULER average at one million tokens.
Since the methods also differ in selection, training and position handling, this contrast does not identify which difference accounts for the gap.
- A position diagnostic
A position comparison offers a diagnostic of RecSA’s candidate-local position scheme. On RULER, a test of 13 synthetic long-context tasks whose score averages results across tasks, the standard-position variant with YaRN scored 1.9 at one million tokens, compared with 60.5 for RecSA.
This points to a role for candidate-local positions in the tested setup, but the variant also used YaRN beyond the model’s 32,000-token training length, so the comparison does not isolate position assignment.
- Timing and novel questions
Together, these comparisons suggest that RecSA’s reported results extend to faster input processing in one measured setup and answering questions about full novels in a specific test. The prefill timing comes from one H200 GPU at batch size one; En. MC tests multiple-choice questions using full-novel context and covers 229 questions.
Deep
- Original paper authors
- Ruitian Wang, Xinyu Yang, Minshen Zhang, Hao Zhang
- Submitted to arXiv
- License
- CC BY 4.0