HISA: Efficient Hierarchical Indexing for Fine-Grained Sparse Attention

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 $\mathcal{O}(L^2)$ 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 token-level top-$k$ index interface consumed by the downstream Sparse MLA operator and requires no additional training. In end-to-end serving with DeepSeek-V3.2, HISA improves throughput by $1.65\times$ and time to first token by $1.70\times$ over the official DSA implementation, despite the HISA-specific operators being implemented in TileLang/Triton while the official DSA baseline uses highly optimized hand-tuned CUDA kernels. With matched TileLang implementations of both indexers, controlled microbenchmarks show up to $3.75\times$ indexer 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.