Sparse attention only visits a small number of keys, but locating those keys can still demand scoring every key against every indexer head. A new research paper, DoSA (Dots Sparse Attention), proposes a lossless way to make that computation conditional while preserving exact token selection.
The method rests on a simple observation: Top-K selection needs enough evidence to reject a candidate, not necessarily its full score. DoSA builds a seed set that supplies a lower bound on the winning threshold, then uses nonnegative head projections and joint residual bounds to upper-bound positive contributions. Activation-informed aggregation bounds the magnitude subtracted by negative heads.
Together these form a certificate that directs full scoring only toward candidates still eligible, while exact-score filtering further reduces writeback and selection work. The authors establish the certificate and its exact-selection conditions, and analyze how geometry and selection margins govern its effectiveness.
On GPU, the implementation accelerates the complete Indexer by up to 2.74x over SGLang and 1.69x over LiteTopK across English, Chinese, and code workloads. End-to-end evaluation on GLM-5.2 and DeepSeek-V3.2 reports up to 1.94x and 1.50x time-to-first-token speedups over the two baselines, respectively.