HISA: Efficient Hierarchical Indexing for Fine-Grained Sparse Attention

• URL: http://arxiv.org/abs/2603.28458v3
• Date: Mon, 06 Apr 2026 09:47:34 GMT
• Title: HISA: Efficient Hierarchical Indexing for Fine-Grained Sparse Attention
• Abstract summary: 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.
• Score: 62.79085204939384
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Token-level sparse attention mechanisms, exemplified by DeepSeek Sparse Attention (DSA), achieve fine-grained key selection by scoring every historical key for each query through a lightweight indexer, then computing attention only on the selected subset. While the downstream sparse attention itself scales favorably, the indexer must still scan the entire prefix for every query, introducing an per-layer bottleneck that grows prohibitively with context length. We propose HISA (Hierarchical Indexed Sparse Attention), a plug-and-play replacement for the indexer that rewrites the search path from a flat token scan into a two-stage hierarchical procedure: (1) a block-level coarse filtering stage that scores pooled block representations to discard irrelevant regions, followed by (2) a token-level refinement stage that applies the original indexer exclusively within the retained candidate blocks. HISA preserves the identical token-level top-sparse pattern consumed by the downstream Sparse MLA operator and requires no additional training. On kernel-level benchmarks, HISA achieves up to speedup at 64K context. On Needle-in-a-Haystack and LongBench, we directly replace the indexer in DeepSeek-V3.2 and GLM-5 with our HISA indexer, without any finetuning. HISA closely matches the original DSA in quality, while substantially outperforming block-sparse baselines.

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)
• ColBERTSaR: Sparsified ColBERT Index via Product Quantization [23.59576017606267]
  ColBERT is an effective neural retrieval architecture, but it requires a heavy index structure to support candidate set retrieval.<n>We propose an embedding quantization approach that turns a ColBERT index into a true inverted index.
  arXiv  Detail & Related papers  (2026-06-04T01:28:45Z)
• MISA: Mixture of Indexer Sparse Attention for Long-Context LLM Inference [75.41426145782751]
  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.
  arXiv  Detail & Related papers  (2026-05-08T07:19:34Z)
• 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)
• Multi-Vector Index Compression in Any Modality [73.7330345057813]
  Late interaction has emerged as a dominant paradigm for information retrieval in text, images, visual documents, and videos.<n>We introduce four approaches for index compression: sequence resizing, memory tokens, hierarchical pooling, and a novel attention-guided clustering (AGC)<n>AGC uses an attention-guided mechanism to identify the most semantically salient regions of a document as cluster centroids and to weight token aggregation.
  arXiv  Detail & Related papers  (2026-02-24T18:57:33Z)
• Curator: Efficient Vector Search with Low-Selectivity Filters [12.774238654446032]
  Graph-based indexes achieve state-of-the-art performance on unfiltered ANNS but encounter connectivity breakdown on low-selectivity filtered queries.<n>Recent research proposes specialized graph indexes that address this issue by expanding graph degree.<n>We present Curator, a partition-based index that complements existing graph-based approaches for low-selectivity filtered ANNS.
  arXiv  Detail & Related papers  (2026-01-03T21:35:01Z)
• 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)
• HAKES: Scalable Vector Database for Embedding Search Service [16.034584281180006]
  We build a vector database that achieves high throughput and high recall under concurrent read-write workloads.<n>Our index outperforms index baselines in the high recall region and under concurrent read-write workloads.<n>namesys is scalable and achieves up to $16times$ higher throughputs than the baselines.
  arXiv  Detail & Related papers  (2025-05-18T19:26:29Z)
• RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval [24.472784635757016]
  RetrievalAttention is a training-free approach to both accelerate attention computation and reduce GPU memory consumption.<n>We show that RetrievalAttention achieves near full attention accuracy while only requiring access to 1--3% of the data.
  arXiv  Detail & Related papers  (2024-09-16T17:59:52Z)
• 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)
• End-to-End Learning to Index and Search in Large Output Spaces [95.16066833532396]
  Extreme multi-label classification (XMC) is a popular framework for solving real-world problems. In this paper, we propose a novel method which relaxes the tree-based index to a specialized weighted graph-based index. ELIAS achieves state-of-the-art performance on several large-scale extreme classification benchmarks with millions of labels.
  arXiv  Detail & Related papers  (2022-10-16T01:34:17Z)
• Dynamic Focus-aware Positional Queries for Semantic Segmentation [94.6834904076914]
  We propose a simple yet effective query design for semantic segmentation termed Dynamic Focus-aware Positional Queries. Our framework achieves SOTA performance and outperforms Mask2former by clear margins of 1.1%, 1.9%, and 1.1% single-scale mIoU with ResNet-50, Swin-T, and Swin-B backbones.
  arXiv  Detail & Related papers  (2022-04-04T05:16:41Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)

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.