DoSA: Don't Score All, Certified Sparse Attention Indexing

Sparse attention visits few keys, yet finding them can still require scoring every key with every indexer head, leaving a dense computation bottleneck inside the attention module. We introduce DoSA (Don't Score All), a lossless optimization that makes token selection conditional while preserving exact Top-$K$ results. Its central observation is that rejecting a candidate requires a sufficiently tight score bound, rather than its full score. A seed set supplies a lower bound on the selection threshold. Nonnegative head projections and joint residual bounds upper-bound positive contributions, while activation-informed aggregation bounds the magnitude subtracted by negative heads. These certificates eliminate unnecessary full-head scoring, and sparse writeback further reduces memory traffic and selection work. We establish the conditions for exact selection and analyze how score geometry and selection margins determine pruning effectiveness. Across English, Chinese, and code workloads, our GPU implementation accelerates the complete Indexer by up to $2.74\times$ over SGLang and $1.69\times$ over LiteTopK. End-to-end evaluation on GLM-5.2 and DeepSeek-V3.2 achieves up to $1.94\times$ and $1.50\times$ time-to-first-token speedups over the two baselines, respectively. By extending conditional computation to token selection, DoSA takes a step toward scalable attention.