MISA: Mixture of Indexer Sparse Attention for Long-Context LLM Inference

• URL: http://arxiv.org/abs/2605.07363v1
• Date: Fri, 08 May 2026 07:19:34 GMT
• Title: MISA: Mixture of Indexer Sparse Attention for Long-Context LLM Inference
• Abstract summary: We propose a drop-in replacement for the DSA indexer that treats its indexer heads as a pool of mixture-of-experts.<n> MISA matches the dense DSA indexer on LongBench across DeepSeek-V3.2 and GLM-5 while running with eight and four times fewer indexer heads respectively.<n>Our TileLang kernel delivers roughly a 3.82 times speedup over DSA's original indexer kernel on a single NVIDIA H200 GPU.
• Score: 75.41426145782751
• License: http://creativecommons.org/licenses/by/4.0/
• 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 most relevant ones for the main attention. To remain expressive, the indexer uses many query heads (for example, 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 (Mixture of Indexer Sparse Attention), a drop-in replacement for the DSA indexer that treats its indexer heads as a pool of mixture-of-experts. A lightweight router uses cheap block-level statistics to pick a query-dependent subset of only a few 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 scoring every prefix token with every head to scoring it with only a handful of routed heads, plus a negligible router term computed on a small set of pooled keys. We further introduce a hierarchical variant of MISA that uses the routed pass to keep an enlarged candidate set and then re-ranks it with the original DSA indexer to recover the final selected tokens almost exactly. With only eight active heads and no additional training, MISA matches the dense DSA indexer on LongBench across DeepSeek-V3.2 and GLM-5 while running with eight and four times fewer indexer heads respectively, and outperforms HISA on average. It also preserves fully green Needle-in-a-Haystack heatmaps up to a 128K-token context and recovers more than 92% of the tokens selected by the DSA indexer per layer. Our TileLang kernel delivers roughly a 3.82 times speedup over DSA's original indexer kernel on a single NVIDIA H200 GPU.

Related papers

• PIVOT: Efficient Query-Group Indexing for Token-Level Sparse Attention [19.844672835223676]
  Token-level sparse attention, as implemented by DeepSeek S Attention (DSA) in production systems, makes the downstream attention efficient but shifts the bottleneck to the indexer that feeds it.<n>We exploit these properties in PIVOT, Proxy Indexing Via One full-parse Traversal, a training-free, drop-in replacement for the DSA indexer.<n>On DeepSeek-V3.2 and GLM-5.1 across LongBench and RULER, PIVOT matches the accuracy of the dense DSA indexer while accelerating it by up to 4x and reducing end-to-end latency by
  arXiv  Detail & Related papers  (2026-07-27T15:58:07Z)
• StreamIndex: Memory-Bounded Compressed Sparse Attention via Streaming Top-k [0.0]
  DeepSeek-V3.2 and V4 introduce Compressed Sparse Attention (CSA): a lightning indexer (a learned scoring projection over compressed keys) scores them, the top-k are selected per query, and a sparse attention kernel reads only those.<n>We present StreamIndex, a Triton implementation of the CSA pipeline whose central component is a chunked partition-merge top-k driver that never materializes the full intermediate.<n>Our contribution targets the indexer step; we make no claim of a faster attention kernel or of real-checkpoint end-to-end behavior.
  arXiv  Detail & Related papers  (2026-05-04T13:19:29Z)
• HISA: Efficient Hierarchical Indexing for Fine-Grained Sparse Attention [62.79085204939384]
  HISA (Hierarchical Indexed Sparse Attention) rewrites the search path from a flat token scan into a two-stage hierarchical procedure.<n>On kernel-level benchmarks, HISA achieves up to speedup at 64K context.
  arXiv  Detail & Related papers  (2026-03-30T13:59:51Z)
• IndexCache: Accelerating Sparse Attention via Cross-Layer Index Reuse [68.18308357205586]
  Longcontext agentic have emerged as a defining use case for large language models.<n>Sparse attention addresses this challenge effectively, and DeepSeek Sparse Attention (DSA) is a representative production-grade solution.<n>We present IndexCache, which exploits cross-layer redundancy by partitioning layers into a small set of Full layers that run their own indexers and a majority of Shared layers that simply reuse the nearest Full layer's top-k indices.
  arXiv  Detail & Related papers  (2026-03-12T17:27:21Z)
• Rethinking ANN-based Retrieval: Multifaceted Learnable Index for Large-scale Recommendation System [46.70111672855811]
  MultiFaceted Learnable Index (MFLI) is a scalable, real-time retrieval paradigm that learns multifaceted item embeddings and indices within a unified framework.<n>MFLI improves recall on engagement tasks by up to 11.8%, cold-content delivery by up to 57.29%, and semantic relevance by 13.5% compared with prior state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-02-18T01:31:29Z)
• SCOPE: Saliency-Coverage Oriented Token Pruning for Efficient Multimodel LLMs [59.415473779171315]
  We propose a novel visual token pruning strategy called textbfSaliency-textbfCoverage textbfOriented token textbfPruning for textbfEfficient MLLMs.
  arXiv  Detail & Related papers  (2025-10-28T09:29:37Z)
• Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Index [110.90283601829724]
  We present infini-gram mini, a system that can make petabyte-level text corpora searchable.<n>Based on the FM-index data structure, our system creates indexes with size only 44% of the corpus.<n>We show one important use case in a large-scale analysis of benchmark contamination.
  arXiv  Detail & Related papers  (2025-06-13T21:13:57Z)
• Semi-Parametric Retrieval via Binary Bag-of-Tokens Index [71.78109794895065]
  SemI-parametric Disentangled Retrieval (SiDR) is a bi-encoder retrieval framework that decouples retrieval index from neural parameters.<n>SiDR supports a non-parametric tokenization index for search, achieving BM25-like indexing complexity with significantly better effectiveness.
  arXiv  Detail & Related papers  (2024-05-03T08:34:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.