Recursive Sparse Attention RecSA: Million-Token Context Extrapolation at Logarithmic Cost

When context length scales to the million-token level, the cost of dense attention during prefill and decoding becomes prohibitive, and long documents needed for training grow scarcer as target lengths increase. Most existing sparse attention methods require scoring all preceding blocks or tokens, causing per-query selection cost to grow linearly with context length L. Hierarchical selection can reduce cost to logarithmic scale, but prior trainable hierarchical methods only reported accuracy within the training length.

Core Idea: Compressing the KV Cache with a Tree Structure

According to the original paper, RecSA (Recursive Sparse Attention) builds a tree over the KV cache, where each node summarizes its subtree with a key and a mean-pooled value. These keys come from one pooler per layer, all layers share the same pooler, and it is distilled from dense attention.

The key to this design: each tree level selects at most k candidates, so per-query selection cost is O(log L), and the number of entries read is likewise O(log L). Summaries of unselected candidates share the same softmax with exact tokens, preserving global information while maintaining sparsity.

KV Cache is a core optimization in the Transformer decoding phase: during autoregressive generation, previously computed Key and Value vectors are cached and reused to avoid recomputing the entire history for each new token. But cache size grows linearly with context length—at a million tokens, the KV cache for a single sequence can reach tens of GB, making VRAM a hard constraint. Sparse attention's approach is to let each query read only a small subset of cache entries, reducing both memory footprint and computation. RecSA's tree structure is essentially a multi-level summary index over this cache: the bottom level holds exact tokens, upper levels hold subtree mean summaries, and queries first coarsely filter at upper levels then drill down level by level—so both the number of entries read and selection cost grow only with tree height, i.e., O(log L).

Mean pooling refers to averaging a set of vectors dimension-wise into a summary vector. In RecSA, each tree node's value is the mean of all token values in its subtree, while the key is generated by the pooler. Mean pooling lets upper-level nodes carry subtree information of arbitrary length in fixed dimensions—a prerequisite for the tree to compress the cache with depth growing logarithmically with L. Note that summary vectors lose fine-grained information, so RecSA has summaries of unselected candidates share the same softmax with exact tokens, ensuring global information is not entirely discarded.

Position Encoding Ingenuity: Making Extrapolation Possible

A clever design in RecSA lies in RoPE position handling. Each entry's RoPE position is its index among candidates at its level, not the original token position. This way, regardless of context length, all relative distances stay within the range seen during training.

This explains why RecSA can achieve length extrapolation: the model only sees 32K length during training, but at inference can handle inputs far exceeding this, because position encoding relative distances always remain within the training distribution. This approach contrasts with current mainstream long-context extrapolation methods, which often require complex interpolation or scaling strategies.

RoPE (Rotary Position Embedding) injects relative position information by applying rotations proportional to position to Query and Key vectors, and is the mainstream position encoding scheme in current large models. Its key property: attention scores depend only on the position difference (relative distance) between two tokens, not absolute positions. During training the model only sees relative distances within a limited range; once inference length far exceeds training length, relative distances fall into unseen ranges and attention distributions become distorted—this is the root of length extrapolation difficulty. Common mitigations include Position Interpolation (PI), NTK-aware scaling, YaRN, etc., which compress or remap position indices to pull ultra-long distances back into the training distribution, but often require additional tuning or fine-tuning. RecSA takes another path: it doesn't modify RoPE itself, but changes the meaning of the encoded position—each tree entry records its ordinal among same-level candidates rather than the original token position, so no matter how long the real context, relative distances involved in scoring are naturally bounded within the magnitude of per-level candidate count k.

Experimental Results: Surpassing Baselines Across the Board

RecSA is initialized from Qwen3-4B and trained on the original model's 32K training length using 0.62B tokens. On the RULER benchmark, RecSA outperforms all baselines at every length from 131K to 2M.

At 1M length, RecSA scores 60.5, while the best baseline Dense + DCA reaches only 40.0. This gap shows recursive sparse attention has significant advantages in ultra-long context scenarios.

More importantly, efficiency. With optimized kernels, RecSA's end-to-end prefill and decoding from 64K to 2M are both faster than dense attention. On a single H200 GPU, at 524K length, prefill is 3.2× faster and decoding 3.8× faster. This means million-level context is no longer a laboratory luxury but has practical deployment feasibility.

RULER is a synthetic benchmark for evaluating long-context capabilities, composed of multiple subtasks including single/multi-needle-in-a-haystack (locating specific information in long text), variable tracking, aggregation counting, and long-document QA, with scores reported per target length (e.g., 4K, 32K, 128K, 1M). It is widely adopted because its length is controllable and answers are automatically verifiable, systematically testing model retrieval and comprehension degradation beyond training length. Note that RULER overall still emphasizes "localization and extraction" capabilities, with limited coverage of tasks requiring cross-paragraph global reasoning—which is why the article notes RecSA still lacks public data on complex integration tasks.

Dense + DCA is one of the control baselines in the article: Dense refers to standard dense attention, and DCA (Dual Chunk Attention) is a class of inference-time methods that achieve training-length extrapolation by chunking and adjusting position encoding, extending context without retraining. RecSA's large lead over this baseline at 1M length (60.5 vs 40.0) shows that trainable sparse selection is more effective than pure inference-time position remapping in extrapolation scenarios.

Why This Matters for AI Applications

Long-context capability is a key competitive direction for current large models, but dense attention's quadratic complexity remains the bottleneck. RecSA's value: it uses trainable hierarchical sparse selection to solve two problems at once—first, selection cost grows logarithmically with length; second, position encoding design enables extrapolation beyond training length.

For AI applications handling ultra-long documents, code repositories, or large-scale conversation histories, this logarithmic-cost long-context approach offers a new engineering path. In particular, its ability to extrapolate from 32K training length to 2M dramatically reduces reliance on ultra-long training data—and the scarcity of long documents is precisely one of the pain points of current long-context training.

Limitations and Open Questions

The original paper mainly reports results on the RULER benchmark, which emphasizes long-context retrieval and comprehension. How RecSA performs on tasks requiring global reasoning or complex cross-paragraph integration currently lacks public data. Additionally, the impact of pooler distillation quality on final performance, and generalization across different base models, remain to be further validated.

From an engineering perspective, availability of optimized kernels is a prerequisite for RecSA's practicality. The paper mentions acceleration is achievable "with optimized kernels," meaning practical deployment has high requirements on low-level implementations.

Overall, RecSA provides a logarithmic-cost technical path for million-level context, and its design approach to length extrapolation is especially noteworthy. As long-context demand moves from niche to mainstream, such methods may become an important component of next-generation model architectures.

One-line Summary

RecSA compresses the KV cache with a tree structure, achieving context extrapolation from 32K to 2M at logarithmic cost.

Paragraph Summary

RecSA (Recursive Sparse Attention) addresses the prohibitive cost of dense attention at million-level context by building a tree over the KV cache, where each node summarizes its subtree with a key and mean-pooled value, with all levels sharing a pooler distilled from dense attention. Each level selects at most k candidates, making per-query selection and read cost O(log L). Its position encoding design sets each entry's RoPE position to its index among same-level candidates rather than the original token position, keeping relative distances within the training distribution and enabling extrapolation from 32K training length to 2M. On RULER, it outperforms baselines at every length from 131K to 2M, scoring 60.5 at 1M vs. the best baseline's 40.0; on a single H200, at 524K length, prefill is 3.2× and decoding 3.8× faster. The method initializes from Qwen3-4B and trains with only 0.62B tokens at 32K length.