PIVOT: Efficient Query-Group Indexing for Token-Level Sparse Attention
- URL: http://arxiv.org/abs/2607.24593v1
- Date: Mon, 27 Jul 2026 15:58:07 GMT
- Title: PIVOT: Efficient Query-Group Indexing for Token-Level Sparse Attention
- Abstract summary: 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
- Score: 19.844672835223676
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Token-level sparse attention, as implemented by DeepSeek Sparse Attention (DSA) in production systems, makes the downstream attention efficient but shifts the bottleneck to the indexer that feeds it. To select the top-k tokens for each query, the indexer must still score every preceding token, incurring a cost of O(L^2) per layer for a sequence of length L. We observe that this per-query scan is largely redundant: nearby queries select highly overlapping top-k tokens, and the indexer scores are long-tailed along the key axis. We exploit these properties in PIVOT, Proxy Indexing Via One full-prefix Traversal, a training-free, drop-in replacement for the DSA indexer that shares one prefix scan across a group of nearby queries. PIVOT aggregates a group into a single proxy query, performs one shared full-prefix scan to obtain a candidate set, and then selects a top-k for each query from that set. Two variants trade speed for fidelity: PIVOT-Reuse shares the proxy top-k across the group for maximum speed, whereas PIVOT-Refine re-scores the candidate set with the indexer of each query and then selects an individual top-k, matching the dense indexer at a small additional cost. A single algorithm covers both inference phases, differing only in how groups are formed: fixed-size groups of consecutive queries in prefill, and the queries decoded together in one multi-token prediction (MTP) step in decode. 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 up to 1.6x at long context.
Related papers
- 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) - 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) - 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) - 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.