Hierarchical sparse attention: attention designed to read 10 million tokens

Why it was needed: even choosing was expensive

Attention measures how relevant every earlier token is when computing a new token. With length N there are N² pairs, so doubling the context window quadruples the computation. As a result, models that read long documents see costs rise quickly both in the prefill stage, which processes the initial prompt all at once, and in the decoding stage, which generates one token at a time.

The standard way to reduce this cost is block-sparse attention. The sequence is split into blocks of fixed size, and for each query only a few blocks that look relevant are computed exactly. The COBS study paper summarized this approach as hardware-friendly and as easing the bottleneck of reading the KV cache. Because memory is read contiguously block by block, it is easy for GPUs to handle.

The problem is the step that chooses which blocks to keep. PISA paper pointed out that existing block selection scores every query-block pair, so selection itself still scales with the square of the length. The same thing shows up in production models. AttentionIndex paper reported that even in learned sparse attention such as DeepSeek-V4 and GLM-5, where a lightweight indexer picks the keys, the indexer scores every preceding key, and at 1 million tokens this selection takes more than half of prefill time.

In the end, the question changed. It moved from 'what can we read less of' to 'how can we cheaply choose what to read'. Hierarchical sparse attention is an answer to this second question.

Core idea: how you find a book in a library

When you look for a book in a large library, you don't pull out every book on every shelf. You first pick the right floor from the floor directory, check a few shelf signs on that floor, and scan the spines only within the shelf you chose. You look at only a few things at each step, yet you end up near the book you want.

Hierarchical sparse attention works the same way. Keys (the 'lookup' vectors produced by earlier tokens) are grouped several at a time into summary keys, and those summaries are grouped again into coarser summaries. The query scores the coarsest level and keeps only the top few, then scores only the children of the kept groups at the next level. When it reaches the bottom token level, it computes exact attention only for the remaining tokens.

Why is this cheaper? If group size grows by a fixed factor at each level, the number of levels grows only with the logarithm of the length, and the number of candidates examined per level has an upper bound. PISA paper used this structure to bring overall complexity down to N log N, and RecSA paper made both the selection cost per query and the number of items read scale with the logarithm of the length.

There is a trade-off. If the library signs are wrong, you go to the wrong floor. If a summary misrepresents the actual content, a group containing important tokens is dropped at an upper level, and nothing beneath it is examined again. That is why most research in this area deals with 'how to build summaries' and 'how to group'.

How it works: five steps

First, build a summary tree. Keys accumulated in the KV cache are pooled (several vectors combined into one) a fixed number at a time to create summary keys, and this is repeated to stack multiple levels. In RecSA paper, each tree node summarizes everything beneath it with one key and one averaged value.

Second, score at the coarsest level. The relevance between the query and the summary keys is computed, and only the top k are kept. PISA paper selects candidates here by aggregating scores within a group with LogSumExp, which takes the log of a sum of exponentials.

Third, move down a level. Only the children of the kept candidates are scored again, and the top k are kept. Because the candidate set has a bounded size, the cost per level is constant. DHSA paper also uses hierarchical routing that estimates importance at the chunk level and then propagates it to the token level.

Fourth, compute exact attention on the remaining tokens. RecSA paper goes a step further here, putting the summaries of unselected candidates into the same softmax (a function that turns scores into probabilities) as the exact tokens. In effect, the discarded regions are still reflected in the result, approximately.

Fifth, fuse the whole process into a single GPU kernel. If operations that move between levels are written poorly, memory round-trips increase and the theoretical gain is lost. PISA paper combined hierarchical routing and score computation in Triton kernels for both training and inference, so that the full query-key score matrix is never materialized in memory.

Design choices: what gets traded off

What should summaries be made of? COBS paper framed block selection as a problem of ranking blocks by 'attention mass', that is, the sum of attention scores within a block. If blocks with large mass are chosen correctly, block-sparse attention can approach the quality of dense attention (which looks at every token). But computing the exact mass requires reading every key, so it must be approximated from summaries, and the study's analysis found that existing methods rely on first-order approximations such as the mean and are unreliable. Storing compressed second-order statistics (spread) for each block raised the NSA baseline's average score on the 32k RULER retrieval benchmark from 0.2999 to 0.8195; dense attention scored 0.9040.

How should position information be handled? The semantic–geometric decoupled routing study paper pointed out that existing routers pool representations after RoPE (rotary position embedding) is applied, mixing the geometric structure that comes from meaning and from position, and causing high-frequency components to cancel out so that nearby positional cues are blurred. So semantic summarization is done in the pre-RoPE space, and a positional bias is computed separately and added. It applies without training, with routing overhead under 3.4ms, and was reported to be 5.03x faster than FlashAttention at 128K.

What should be grouped together? Contiguous blocks make memory reads easy, but as PBS-Attn paper pointed out, if the important keys needed by the queries in one block are scattered across many blocks, many unnecessary blocks get read. PBS-Attn reorders tokens to increase block sparsity and achieved up to 2.75x end-to-end speedup in long-context prefill. AttentionIndex paper goes further and uses an inverted file index (a cluster-based index used in ANN search) that groups similar keys together. Its reasoning is that with a fixed candidate budget, two-stage selection over contiguous blocks misses a growing share of the keys it needs to find as length increases.

Block-level or token-level? CLSA paper summarized that structured block methods give large speedups but noticeable quality loss, while token-level methods are accurate but have small end-to-end speedups because top-k routing over the full cache is expensive. CLSA computes token-level top-k only once and lets multiple layers share the indices, reporting up to 7.6x faster decoding and up to 17.1x overall throughput at 128K. Hierarchical design is a different line of answer that tries to keep token-level precision while reducing that routing cost to the logarithmic level.

How it developed: starting-point studies from 2025–2026

Studies in 2025 each addressed a different weakness of sparse attention. ReSA paper pointed out that in sparse decoding, approximation errors accumulate and push the KV cache away from its pretraining distribution, and it bounded the error by refreshing the KV cache with dense computation at fixed intervals. It achieved up to 2.42x end-to-end speedup in 256K decoding. DHSA paper introduced chunk→token hierarchical routing that predicts sparse patterns online based on the input rather than using fixed templates. With the model itself left unchanged, it achieved 12–20% higher relative accuracy than block-sparse attention at similar prefill cost, up to 10x faster prefill at 128K, and processed 100,000 tokens with a 4-bit LLaMA-3.1-8B on a single 24GB GPU. PBS-Attn paper addressed the block boundary problem by reordering tokens.

In the first half of 2026, the focus became 'how accurately and cheaply selection can be done'. CLSA paper spread the selection cost by sharing routing indices across layers, and COBS paper formalized the selection problem as approximating attention mass and showed that the order of the summary statistics matters.

In September 2026, studies appeared that tackled summaries and hierarchy head-on. Semantic–geometric decoupled routing paper moved summaries into the pre-RoPE space, and PISA paper explicitly achieved overall N log N complexity with pyramid Top-K selection from coarse to fine levels. PISA reported that in language modeling experiments, it was on par with baselines on commonsense reasoning benchmarks and better on retrieval tasks.

These studies do not state that they build directly on one another; they attacked the same bottleneck from different angles in the same period. The map below groups them only by time period.

Where things are heading: from 1 million to 10 million tokens

Studies from October–November 2026 push hierarchical selection beyond 1 million tokens. RecSA paper builds a tree on top of the KV cache and distills a pooler (a small module that produces summary keys) shared across levels from dense attention. Its notable design is in position handling. Each item's RoPE position is assigned as 'its rank among the candidates at that level', so relative distances stay within the range seen in training no matter how long the input is. Starting from Qwen3-4B and trained on only 0.62B tokens at the original training length of 32K, it beat the baselines on RULER at every length from 131K to 2M, scoring 60.5 at 1M versus 40.0 for the best baseline (Dense + DCA).

AttentionIndex paper takes the practical route of adding a cluster index on top of a production model's indexer. It builds the index during prefill so new keys can be searched immediately, reuses earlier clustering results to lower maintenance cost, and preserves causality by letting each query see only clusters built from keys that precede it. At 1 million tokens, prefill throughput was 1.3–1.8x that of exhaustive selection in GLM-5.3 and DeepSeek-V4-Flash, and at throughput within 5% of the two-stage contiguous-block method (HiSA), it recovered 17.0 and 10.0 percentage points more of the exhaustive top-k, respectively.

LSA paper is the study behind the '10 million tokens' in the title. Motivated by the view that agentic workflows are moving toward long-horizon tasks and therefore need long contexts, it hierarchically clusters keys in a learned latent space and has queries score the cluster hierarchy instead of every key. It comes in two forms: D-LSA, which is attached to an existing model via distillation, and N-LSA, which is trained from scratch using only next-token loss. At 10 million tokens, D-LSA made single-attention-layer prefill 22.7x faster and decoding 4.6x faster than GLM-5.3-FLASH's original sparse attention, and 72.4x and 42.5x faster, respectively, than Qwen-3.8-27B with full attention. Accuracy was reported to remain comparable across multiple tasks. N-LSA matched full attention accuracy at 128k while training 1.6x faster per layer.

Putting the three studies together reveals a direction. Grouping is moving from contiguous blocks to learned or similarity-based clusters, summaries from hand-designed means to distilled summaries, and evaluation from within the training length to ranges far beyond it.

Limitations, open issues and practical judgment

Mistakes at upper levels are hard to undo. A group dropped at a coarse level is never examined beneath, so if a summary misjudges mass, important tokens are lost entirely. The limits of first-order approximation shown by COBS paper and the rising miss rate under a fixed budget pointed out by AttentionIndex paper are both instances of this problem. Putting discarded summaries into the softmax as RecSA paper does, or periodically mixing in dense computation as ReSA paper does, are mitigations, but they come at a cost.

Reported speedups also need careful reading. LSA paper's 22.7x and 72.4x are measured for a single attention layer; end-to-end serving speed also includes MLPs, communication and memory management, so the gain is smaller. The numbers also differ greatly depending on whether the comparison is against 'the original sparse attention' or 'full attention'. Accuracy results, too, lean heavily on synthetic retrieval tasks such as RULER, and RecSA's 60.5 at 1M, while better than the baseline, also means it still misses many cases.

When to use it. Most of the studies covered here report gains at 128K and above. With short contexts, the cost of building a summary tree and moving across levels can cancel out the gains, so the first step is to check the length distribution of actual traffic. If there is no capacity for new training, methods that attach without training (DHSA, semantic–geometric decoupled routing) or via distillation (D-LSA) are candidates; if designing a model from scratch, natively trained options such as N-LSA are available.

There are three common mistakes: looking only at kernel speed without checking end-to-end speed; evaluating only within the training length and assuming results hold beyond it; and looking only at average scores without separately checking tasks where sparse selection is weak, such as multi-key retrieval. Before adoption, measure together the retrieval accuracy curve by length, how much of the exhaustive top-k the selection recovers, and whether quality drops as decoding gets longer.

Further study

To get the structure first, read PISA paper. It most directly explains why block selection is still quadratic and how pyramid Top-K reaches N log N. Reading COBS paper next gives you a criterion, 'a good summary is one that approximates attention mass well', that helps you evaluate other papers.

Then look at semantic–geometric decoupled routing paper for the relationship between RoPE and summaries, and RecSA paper for the problem of extending beyond the training length. Both show how much the handling of position information matters in long contexts.

If you are curious about the 10-million-token scale and the serving perspective, read LSA paper and AttentionIndex paper. CLSA paper and ReSA paper fill in the block-versus-token trade-off and decoding-side issues; PBS-Attn paper is a good starting point for the block boundary problem, and DHSA paper for memory-constrained environments.