DoSA: Dots Sparse Attention

arXiv:2610.13990 · cs.LG · Submitted 2026-09-26 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "DoSA: Dots Sparse Attention".

Jane: The gist The DOSA method introduces a lossless way to make computation conditional while preserving exact token selection in sparse attention,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we’re looking at this paper called "DoSA: Dots Sparse Attention." Basically, they’re tackling a problem where you only look at a few keys in sparse attention, but finding those specific keys still seems to require calculating every single key with every indexer head.

Jane: That sounds like a real bottleneck for performance when you're dealing with very long contexts or huge models. So what is the main idea behind DoSA? What are they claiming?

Tom: The core thesis is that they introduce a lossless method to make that computation conditional—meaning you can skip parts of the scoring—while still getting an exact token selection. They argue that you don't need the full score to decide if a candidate is good enough for the Top-K list.

Lu: What they observe is that Top-K selection actually only needs enough evidence to reject a candidate, not necessarily its entire score, and DoSA provides that evidence through a seed set.

Meng: So they're trying to find a way to bound the winning threshold using just some initial information rather than calculating everything upfront. How do they establish those bounds?

Jane: They use a seed set to give them a lower bound on the actual winning threshold, and then they use nonnegative head projections and joint residual bounds to set upper bounds on positive contributions.

Tom: And they also use activation-informed aggregation to bound how much you subtract when you consider negative heads, which helps with the filtering part. It’s a certificate that directs the full scoring toward candidates that are already eligible.

Lalam: The certificate works by saying a token cannot even enter the Top-K if its upper bound on the score falls below a lower bound on what the actual Top-K threshold should be.

Jane: That sounds like they're setting up a strict separation between where you *can* stop calculating and where you *must* continue calculating. Can you unpack that a bit more for someone who isn't deep in the math?

Tom: They establish a score certificate, which is basically saying that the upper bound on your token score, Ui, is strictly less than some lower bound on the true threshold, τK. This separation certifies the rejection of candidates without needing to calculate their full scores.

Meng: So if I understand this right, they are using these bounds to prune a massive amount of unnecessary writeback and selection work while still guaranteeing that the exact Top-K selection is preserved?

Tom: Exactly. The certificate component allows them to do that exact-score filtering which reduces both writeback and selection work. They prove the exact-selection conditions through propositions regarding positive head projection bounds and negative head support bounds, which shows the method is valid.

Paper summary: Lu: The cost analysis they provide shows that this screening saves logical dot products only when m is less than one minus r plus da over H, which connects the savings directly to your query geometry and the head budget <ref:2610.13990#pg2>.

Jane: That means how much work you save depends heavily on how the query looks and how many heads you have available for computation. And what does that imply for a user running this?

Tom: The GPU implementation of DoSA actually speeds up the complete Indexer by up to two point seven four times over SGLang and one point six nine times over LiteTopK across English, Chinese, and code workloads.

Meng: That is a significant speedup when you’re talking about serving models at scale. So how does that translate to real-world latency gains for someone running this system?

Jane: They show end-to-end evaluation on GLM-five point two achieves up to one point nine four times and one point five zero times speedups in time-to-first-token, which is a big deal for user experience during prefill.

Lu: The context length drives the gain more strongly than the query chunk size, suggesting that reducing work along the long key dimension is where this method really shines.

Tom: They also note that screening alone reduces latency by thirty-seven point four percent, and sparse writeback alone reduces it by twenty-three point four percent <ref:2610.13990#pg2>. Combined, they reduce retrieval latency by forty-seven point three percent, leading to a total speedup of about one point nine zero times over the base system.

Jane: It sounds like DoSA is showing that you can achieve significant performance improvements just by being smarter about how you compute those intermediate scores, even when the underlying attention mechanism is inherently complex.

Meng: But what’s the catch? The paper points out that this method still scans every key, and if your context is short or your bounds are too loose, you might not see much savings. That's a real limitation to keep in mind for deployment.

Tom: That’s right. The cost of obtaining that certificate is explicit through head-budget analysis, which tells you exactly how much work you need to certify as unnecessary before it pays off.

Lu: Future work suggested by the authors involves extending these per-key certificates to key-block bounds using compact summaries, trying to find a way to summarize larger chunks of keys more efficiently.

Jane: So, while DoSA is very effective for getting that speedup with long contexts and specific geometric setups, it still has those boundary conditions where the savings might not be enough for every single scenario.

Tom: The main thing we learn from "DoSA: Dots Sparse Attention" is that exact token selection can require less total work than computing every token’s full score if you use a certificate to guide the computation away from unnecessary paths.

Jane: It really shows that by connecting the geometry of your query to the head budget, you can explicitly manage how much computation is actually required for selecting those few important keys.

Conclusion: Jane: So, to wrap up this segment, we’re looking at DoSA: Dots Sparse Attention by Tom and Jane Miller, and what that actually means for how we process huge amounts of text in AI models.

Tom: Yeah, so essentially they've figured out a way to make those massive scoring computations conditional. They found a loss-less method to condition the computation while keeping the exact token selection intact in sparse attention.

Lu: What they're pointing out is that you don't need every single key to have its full score before you decide if it makes the Top-K list; you just need enough evidence to reject it.

Meng: From a deployment standpoint, I’m interested in how much work this actually saves on our servers, and the paper talks about how this certificate directs the scoring toward candidates that are already eligible.

Lalam: I can confirm what the authors say: they use a certificate where a token can't even enter Top-K if its upper bound on the score is lower than a lower bound on what the true Top-K threshold should be.

Jane: That sounds complicated, so for someone just listening, it means they’re using some initial information—a seed set—to create a rule that lets them skip calculating the full scores of lots of keys.

Tom: Exactly. It’s about proving that the certificate directs the full scoring toward candidates that remain eligible, which then allows for exact-score filtering to reduce writeback and selection work.

Lu: The core idea is this score certificate: the upper bound on your token score is strictly less than some lower bound on the true threshold. This separation proves they can skip calculations without messing up the final selection.

Meng: I wonder about the cost, though, because I’m thinking about what breaks at scale; does this save enough logical dot products for a real production system?

Tom: The analysis shows that this screening only saves logical dot products when m is less than one minus r plus da over H; it depends heavily on your query geometry and your head budget.

Jane: So, the big implication here is that we can do less computation even when working with those super long contexts that are currently a bottleneck.

Lu: The context length drives the gain more strongly than the query chunk size, which means this method is most effective when you're dealing with very long sequences.

Meng: But the authors were clear about a limitation: this method still scans every key, and if your context is short or your bounds are too loose, you might not see enough savings to make it worthwhile.

Tom: That’s the caveat; they show that avoiding score computation improves serving latency even after scoring and selection have already been fused, but it’s not a free ride for every single scenario.

Jane: So, DoSA is a way to get those performance gains in sparse attention while maintaining exact accuracy, but you have to be careful about the context length and the bounds you set.

Fanxu Meng, Taosong Fang

Dots Studio · Xiaohongshu Inc.

cs.LG

Submitted: 2026-09-26

Updated: 2026-09-26

Code: https://github.com/llm-sys/flash-indexer

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: The gist The DOSA method introduces a lossless way to make computation conditional while preserving exact token selection in sparse attention, which addresses the bottleneck where finding selected

Key concepts

Top-K Selection: This is the process of selecting only the top K most relevant keys from a large set of potential keys. The DOSA method aims to achieve this selection exactly without needing to compute the full score for every single key, which is computationally expensive in sparse attention scenarios.
Certificate: A mathematical proof that guarantees a certain condition holds true. In DOSA, the certificate ensures that a token cannot be selected if its upper bound on its score falls below a lower bound established by the true Top-K threshold. This allows for skipping full scoring for ineligible tokens.
Score Bounds: These are calculated mathematical limits placed on the scores of candidate tokens. The method uses seed sets and projection bounds to establish a lower bound ($ au_K$) for the true Top-K threshold and an upper bound ($U_i$) for individual token scores. These bounds form the basis of the certificate to determine eligibility.

Terminology

Sparse Attention — 1× in this paper · explained in 5 episodes

Summary

The gist The DOSA method introduces a lossless way to make computation conditional while preserving exact token selection in sparse attention, which addresses the bottleneck where finding selected keys still requires scoring every key with every indexer head

How it works

DOSA is a lossless method for making this computation conditional while preserving exact token selection Its central observation is that Top-K selection requires sufficient evidence to reject a candidate, not necessarily its full score. A seed set supplies a lower bound on the winning threshold Nonnegative head projections and joint residual bounds upper-bound positive contributions, while activation-informed aggregation bounds the magnitude subtracted by negative heads. The certificate directs full scoring toward candidates that remain eligible; exact-score filtering further reduces writeback and selection work.

The Certificate

The principle is simple: a token cannot enter Top-K if its score upper bound falls below a lower bound on the true Top-K threshold. A subset of at least K visible keys supplies the latter through its Equal contribution. Thus τK(S) is a lower bound on the true Top-K threshold, and Ui is an upper bound on the token score.

Score Bounds and Candidate Refinement

The combined certificate gives a score certificate: Ui = Xj∈Rwej q⊤j ki + EP∥ki∥2 - a⊤Ak+, si ≤ Ui < τ One aggregate direction replaces arbitrarily many omitted negative heads. This procedure preserves exact Top-K selection; Appendix A gives the complete algorithm, formal guarantee (Theorem 1), and proof.

GPU Implementation and Performance

The GPU implementation accelerates the complete Indexer by up to 2.74× over SGLang and 1.69× over LiteTopK across English, Chinese, and code workloads. End-to-end evaluation on GLM-5.2 and DeepSeek-V3.2 achieves up to 1.94× and 1.50× time-to-first-token speedups over the two baselines, respectively.

Experimental Analysis

Context length drives the gain more strongly than query chunk size. DOSA gains most from reducing work along the long key dimension, while remaining effective across prefill batching choices. The growing Indexer share explains why the end-to-end gain strengthens with context length. Screening alone reduces latency by 37.4%, and sparse writeback alone by 23.4% (Figure 7). Together, they reduce retrieval latency by 47.3%, yielding a 1.90× speedup over Base.

Limitations and Conclusion

DOSA shows that exact token selection can require less work than computing every token’s full score. Query geometry determines how much work can be certified unnecessary; the head-budget analysis makes the cost of obtaining that certificate explicit. DOSA still scans every key, and short contexts or loose bounds can leave insufficient savings to offset screening. Future work could extend our per-key certificates to key-block bounds using compact summaries.

The paper establishes a certificate tailored to the signed DSA score, an analysis connecting its slack to selection margins and head budgets, and a GPU realization that turns certified rejection into reduced computation and traffic. The certificate validity is proven through propositions regarding positive-head projection bounds and negative-head support bounds. The final result is that this procedure preserves exact Top-K selection under valid seed thresholds. The computational cost analysis shows that screening saves logical dot products only when m < 1 − (r + da)/H. This method achieves up to 2.74× complete-Indexer speedup over SGLang and 1.94× TTFT speedup over GLM-5.2. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.65% to 95.06%. This method achieves up to 2.74× complete-Indexer speedup and 1.94× TTFT speedup over SGLang. The work demonstrates that avoiding score computation improves serving latency even after scoring and selection have been fused. The certificate component ablation shows that removing the negative aggregate raises candidate survival from 2.

Improvements for AI systems

Improved Indexer Efficiency via DOSA: The system can achieve up to 2.74× complete-Indexer speedup over SGLang and 1.69× over LiteTopK across English, Chinese, and code workloads by making this computation conditional while preserving exact token selection.
Reduced End-to-End Latency for Long Contexts: By accelerating the Indexer, the system can achieve 1.86× and 1.94× time-to-first-token (TTFT) speedups over SGLang on GLM-5.2 and DeepSeek-V3.2, respectively, nearly halving end-to-end latency at approximately 1M tokens.
Certified Rejection of Ineligible Keys: The system can avoid full-head scoring for keys that cannot enter this set by using a certificate to ensure a token cannot enter Top-K if its score upper bound falls below a lower bound on the true Top-K threshold.
Optimized Computational Cost via Certificate Components: The system can dynamically adjust computation based on geometry by utilizing Positive-head projection and bounding omitted negative contributions, allowing it to exploit residual geometry without additional key reads.
Precise Selection Margin Control: The system can maintain exact token selection by ensuring that keys rejected during screening satisfy the condition where no discarded key can belong to the full-domain Top-K, even when using a fixed seed threshold.

Abstract

Sparse attention visits few keys, yet finding them can still require scoring every key with every indexer head. We introduce DoSA (Dots Sparse Attention), a lossless method for making this computation conditional while preserving exact token selection. Its central observation is that Top-K selection requires sufficient evidence to reject a candidate, not necessarily its full score. A seed set supplies a lower bound on the winning threshold. Nonnegative head projections and joint residual bounds upper-bound positive contributions, while activation-informed aggregation bounds the magnitude subtracted by negative heads. The certificate directs full scoring toward candidates that remain eligible; exact-score filtering further reduces writeback and selection work. We establish the certificate and its exact-selection conditions, and analyze how geometry and selection margins govern its effectiveness. Our GPU implementation accelerates the complete Indexer by up to 2.74 times over SGLang and 1.69 times over LiteTopK across English, Chinese, and code workloads. 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.