PIVOT: Efficient Query-Group Indexing for Token-Level Sparse Attention
2026-07-27 • Computation and Language
Computation and Language
AI summaryⓘ
The authors address a slowdown in a token-focused attention method called DeepSeek Sparse Attention (DSA) caused by the process that selects important tokens for each query. They note that nearby queries often pick similar tokens and many scores are low, so scanning all tokens for each query is wasteful. Their solution, PIVOT, groups nearby queries together and does one shared scan to find candidate tokens, then picks the best tokens for each query from that smaller set. This approach keeps accuracy like the original method but speeds up processing by up to four times, lowering overall wait times in long-context tasks.
token-level sparse attentionDeepSeek Sparse Attention (DSA)top-k selectionindexerO(L^2) complexityproxy querymulti-token prediction (MTP)long contextinference accelerationcandidate set
Authors
Hong Liu, Yuan Cheng, Lin Niu, Yi Su, Yufei Xue, Anmin Liu, Guanghua Yu, Jianchen Zhu
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.