MISA: Mixture of Indexer Sparse Attention for Long-Context LLM Inference
Ruijie Zhou, Fanxu Meng, Yufei Xu, Tongxuan Liu, Guangming Lu, Muhan Zhang, Wenjie Pei · 2026
Read MISA: Mixture of Indexer Sparse Attention for Long-Context LLM Inference by Ruijie Zhou, Fanxu Meng, Yufei Xu, Tongxuan Liu, Guangming Lu, Muhan Zhang, Wenjie Pei (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07363.txt.
Introduction
Ruijie Zhou and six co-authors cut the cost of sparse attention for long-context language models. The leading sparse design uses a learned indexer with many query heads to pick relevant earlier tokens, but that indexer itself dominates cost on long inputs. MISA treats the indexer heads like a pool of experts and activates only a few per query.
A light router using block-level statistics chooses the active heads, which then do the heavy token scoring. With only eight active heads and no extra training, MISA matches the full indexer on long-document benchmarks across two model families. A specialized kernel runs several times faster than the original indexer implementation.
Catalog record
| CREATOR | Ruijie Zhou, Fanxu Meng, Yufei Xu, Tongxuan Liu, Guangming Lu, Muhan Zhang, Wenjie Pei |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.07363
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
MISA: Mixture of Indexer Sparse Attention for Long-Context LLM Inference Ruijie Zhou, Fanxu Meng, Yufei Xu, Tongxuan Liu, Guangming Lu, Muhan Zhang, Wenjie Pei Abstract DeepSeek Sparse Attention (DSA) sets the state of the art for fine-grained inference-time sparse attention by introducing a learned token-wise indexer that scores every prefix token and selects the top- k k for the main attention. To remain expressive, the indexer uses H I H^{I} query heads (e.g. 64 64 on DeepSeek-V3.2) that share the same selected token set; this multi-head design is precisely what makes the indexer the dominant cost on long contexts. We propose MISA ( M ixture of I ndexer S parse A ttention), a drop-in replacement for the DSA indexer that treats its H I H^{I} heads as a pool of mixture-of-experts: a lightweight router uses cheap block-level statistics to pick a query-dependent subset of h ≪ H I h\ll H^{I} active heads, and only those heads run the heavy token-level scoring. This preserves the diversity of the original indexer pool while reducing the per-query cost from 𝒪 ( H I L ) \mathcal{O}(H^{I}L) to 𝒪 ( h L + H I M ) \mathcal{O}(hL+H^{I}M) with M = ⌈ L / B ⌉ ≪ L M=\lceil L/B\rceil\ll L pooled keys. Following HISA, we further introduce a hierarchical variant, MISA † , that uses the MoE-routed pass to keep an enlarged candidate set and then re-ranks it with the original DSA indexer to recover the final top- k k almost exactly. With h = 8 h=8 active heads and no additional training , MISA matches the dense DSA indexer on LongBench across DeepSeek-V3.2 and GLM-5 while running with 8 × 8\times and 4 × 4\times fewer indexer heads, respectively, and outperforms HISA on average; it preserves fully green Needle-in-a-Haystack heatmaps up to 128K context and recovers more than 92 % 92\% of the tokens selected by the DSA indexer per layer. Our TileLang kernel delivers roughly a 3.82 × 3.82\times speedup over DSA’s original indexer kernel on a single NVIDIA H200 GPU. These results show that indexer-head-axis routing is a practical and complementary axis of efficiency for fine-grained sparse attention, on top of the existing token-axis hierarchies. 1 Introduction (a) DSA (b) MISA Figure 1 : Comparison of the DSA and MISA indexers. (a) DSA scores every prefix token with all H^{I} indexer heads in parallel before the Top- k Selector picks the final tokens. (b) MISA introduces a lightweight Router that uses block-pooled indexing keys \tilde{\mathbf{k}}_{b}^{I} (cf. Eq. 4 ) to choose a query-dependent subset of h\ll H^{I} active heads, and only those heads compute the per-token score. Both designs feed the same Sparse Multi-Head Latent Attention operator and produce a top- k token set of identical size, so MISA is a drop-in replacement for the DSA indexer. Frontier large language models such as Qwen3 [ 25 ] , Kimi K2 [ 18 ] , GLM-5 [ 28 ] , and DeepSeek-V3.2 [ 7 ] now routinely process prefixes of hundreds of thousands of tokens in a single forward pass, and the latest releases—GPT-5.5 [ 19 ] , Claude Opus 4.7 [ 1 ] , Gemini 3 [ 11 ] , MiniMax-01 [ 15 ] , and DeepSeek-V4 [ 8 ] —push this to the million-token regime. At these lengths, dense attention becomes the dominant cost of both prefill and decode, motivating a wave of sparse attention techniques that select only a small subset \mathcal{T}_{t} of past tokens for each query position [ 5 , 3 , 27 , 23 , 30 , 16 , 21 , 22 , 4 , 10 , 17 , 26 , 24 ] . Among them, DeepSeek Sparse Attention (DSA) [ 7 ] stands out as the best-performing fine-grained variant in production: rather than selecting whole blocks of tokens with handcrafted patterns, DSA introduces a lightweight learned indexer that scores every prefix token and feeds the top- k tokens into the main attention. Its dominance carries into the next generation: DeepSeek-V4’s Compressed Sparse Attention (CSA) [ 8 ] is, at its core, DSA applied on top of a 4\times compressed (block-level) KV stream, confirming that learned token-wise indexing remains the strongest building block even when the underlying KV is itself compressed. By contrast, block-level inference-time alternatives such as MoBA [ 17 ] consistently lag behind DSA on retrieval-style benchmarks because their per-block scores cannot localise the relevant content within a block. A central design choice of DSA is that the indexer itself is multi-head: although the main attention in DeepSeek-V3.2 has H=128 query heads, all of them share the same selected token set \mathcal{T}_{t} (the sparse MLA operates in MQA mode with a single key/value entry per token), so a single indexer is sufficient—yet DSA still uses H^{I}=64 indexer heads. The reason is expressiveness: each head specialises in a different relevance pattern (recency, syntactic role, lexical or semantic similarity, …), and the aggregated score I_{t,s}=\sum_{j}w_{t,j}^{I}\,\mathrm{ReLU}(\mathbf{q}_{t,j}^{I}\!\cdot\!\mathbf{k}_{s}^{I}) benefits from this diversity, with measurable retrieval degradation as H^{I} shrinks. The unfortunate consequence is that scoring each of the L prefix tokens with all H^{I} heads is precisely what makes the indexer the dominant cost on long contexts. Two recent improvements try to reduce this indexer cost without touching the head axis. IndexCache [ 2 ] retains only a small set of layers as full indexer layers and lets the remaining shared layers reuse their top- k , amortising the cost across layers ; HISA [ 24 ] attacks the cost from the token axis with a hierarchical block-to-token search. Both still keep every one of the H^{I} heads active inside the kernel, and both step away from DSA’s strict per-token, per-layer scoring—tokens outside HISA’s selected blocks and entire shared layers in IndexCache no longer receive a fresh fine-grained score, sacrificing part of the granularity that makes DSA strong. This paper takes the orthogonal view that the bottleneck is the head axis. Our key observation is that, while diversity across heads is essential when aggregated over a large pool, only a few heads are actually informative for any given query: the relevant set changes slowly along the prefix and can be identified from cheap block-level statistics. We turn this observation into MISA ( M ixture of I ndexer S parse A ttention), an indexer that treats the H^{I} heads as a pool of MoE experts, routes a query-dependent subset of h\ll H^{I} active heads via a block-pooled scorer, and runs the heavy token-level scan with only those heads. The router itself operates on M=\lceil L/B\rceil\ll L pooled keys, so its overhead is negligible, and the per-query indexer cost is reduced from \mathcal{O}(H^{I}L) to \mathcal{O}(hL+H^{I}M) . MISA preserves the full diversity of the indexer pool because every head remains available; routing simply chooses which ones to consult on each token. We further show that MISA can be plugged into a coarse-to-fine pipeline (MISA † ) that uses an enlarged routed candidate set followed by a token-level DSA refinement, recovering the dense indexer’s selections almost exactly. Contributions. (i) We identify the indexer’s per-token head–token products as the dominant cost of DSA on long contexts and introduce head-axis routing as an axis of efficiency that is complementary