acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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- 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 over SGLang and over LiteTopK. End-to-end evaluation on GLM-5.2 and DeepSeek-V3.2 achieves up to and time-to-first-token speedups over the two baselines, respectively. By extending conditional computation to token selection, DoSA takes a step toward scalable attention.

Primary area:
foundation or frontier models, including LLMs
Keywords:
DSA, Indexer, topk, kv cache, attention

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_dEhwOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper accelerates the DSA indexer through certified candidate screening. A seed set establishes a lower bound on the Top-K threshold, while score upper bounds allow candidates to be rejected before full-head scoring. The method combines screening, full-score refinement, and sparse writeback, and evaluates Indexer latency and time to first token.

Critical strengths

S1. The problem is clear. The indexer still requires substantial full-score computation and can become a bottleneck in sparse attention.

S2. The upper-bound screening method is reasonable and can safely reject candidates that cannot enter Top-K. The experiments show computational savings and actual speedups.

Critical weaknesses

W1. Experimental coverage and empirical correctness validation are insufficient. The main performance evaluation covers limited datasets and application scenarios. Although theoretical guarantees are provided, there are no empirical Top-K agreement checks or downstream task-quality evaluations to verify that the numerical implementation preserves the expected results. This leaves the practical reliability and generality of the method insufficiently established.

W2. Missing hardware details limit interpretation and reproducibility. The paper does not specify the GPU model and memory capacity. These are essential for assessing the reported performance and comparing it with other implementations.

W3. The ablation figures also need better layout and readability. Labels such as "Base," "Full," and "Dense" are not intuitive; "Dense" can easily be confused with dense attention.

Questions for authors

Q1. What GPU model and memory capacity were used for the microbenchmarks and model-level experiments?

Q2. Have you checked Top-K agreement against the original scorer under the actual FP8 implementation, including boundary ties and candidate-buffer recovery? If so, what were the results?

3 comments
AuthorsOpenReview ↗

Response to Reviewer dEhw

Thank you for recognizing the indexing bottleneck and the computational savings of certified screening. We appreciate your suggestions on experimental coverage, reproducibility, and presentation.

W1. Experimental coverage, GPU correctness, and downstream behavior

Our evaluation includes GLM-5.2 and DeepSeek-V3.2, English and Chinese books, and source code. The prefill workloads use InfiniteBench, Project Gutenberg, and SQLite, with contexts from 128K to approximately one million tokens. The GLM-5.2 microbenchmarks span all 21 indexer-producing layers and four prefill chunk sizes. Decoding experiments use document-analysis requests from HELMET, InfiniteBench, and LongBench v2, and code-review requests from SQLite. The SciFact example from LOFT supplies an additional retrieval workload for the scoring/writeback ablation.

We also evaluated the current DoSA kernel implementation through a replay of captured inference workloads. The captured query, key, and scoring-weight tensors cover 18,711 layer-level workload cases across context lengths and query-batch sizes. Two complete passes produced 85,050 complete calls and 74,844 output checks, all of which passed.

The actual GPU microbenchmark validation covers 77,414,400 query checks with zero selection errors and 91,342,848 individual score comparisons with 100% bitwise agreement. DoSA preserves the original scoring function and exact attention-token selection. The mathematical guarantee and these GPU checks directly address the effect of the indexing optimization on the model's attention inputs. We will present this validation prominently, describe the datasets and workload construction together, and clarify the scope of each experiment.

W2 and Q1. Hardware and reproducibility

Our experiments use the same settings as LiteTopK. All methods are evaluated on our platform with matched inputs, numerical precision, and timing scope. Model-level experiments use prefill chunks of 32K tokens for GLM-5.2 and 16K for DeepSeek-V3.2.

Complete-Indexer latency is measured with CUDA events after warmup and includes query/key preparation and any triggered recovery. Each microbenchmark case has six repetitions per method, with the median used for the reported case latency. The median relative standard deviations across cases are 1.11% for SGLang, 1.40% for LiteTopK, and 1.46% for DoSA. End-to-end time to first token is measured on individual requests with the prefix cache cleared. We will consolidate the platform comparison, software versions, parallelism, timing protocol, and memory accounting in the revised experimental setup.

W3. Readability of the ablation figures

Thank you for pointing out the ambiguity in the labels. We will replace them with descriptions of the operations performed, enlarge the labels, and make each caption specify the workload, timing scope, and aggregation.

Current labelRevised label
BaseFull scoring with all scores written
FullFull scoring with filtered writeback
DenseCertified screening with all scores written
DoSACertified screening with filtered writeback

Q2. FP8 execution, score boundaries, and candidate-buffer recovery

Yes. The output checks above run on the actual GPU implementation and compare against the original scorer on the same inputs. The current DoSA kernels also pass the following focused cases.

Focused GPU coverageCasesResult
Boundary-score completion4All passed
Candidate-buffer overflow with tied scores1Passed
Additional recovery and data-layout properties12All passed

The upper bounds account for low-precision representation and arithmetic errors. Filtering retains equality at the threshold, candidates at the selection boundary are resolved using their original full scores, and a full candidate buffer invokes exact recovery. We will add these measurements and a plain-language explanation of the lossless selection rule to the revised manuscript.

Thank you for your response and additional experiments. I will raise my rating to 3.

Thank you for considering our responses and additional experiments. We appreciate your time and constructive feedback, and will incorporate these additions into the revised manuscript.

Reviewer_PmWkOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes DoSA, an inference-time optimization for the multihead indexer used in DeepSeek Sparse Attention. It first scores a seed set to obtain a lower bound on the Top-K threshold. For each remaining key, it computes a cheaper upper bound on the indexer score and skips full multihead scoring when that bound is below the threshold. The method accounts for both positive and negative head contributions, then uses the original scores for surviving candidates. The paper reports up to 2.74× complete-indexer speedup and 1.94× time-to-first-token speedup over SGLang.

Critical strengths
  • The paper targets a meaningful bottleneck: at long context lengths, selecting keys can cost more than the sparse attention that follows.

  • The certificate is tailored to the signed, ReLU-based indexer score. The treatment of omitted negative heads is particularly important: the ablation shows that removing their aggregate nearly eliminates effective pruning.

  • The evaluation includes both indexer-level and end-to-end measurements, compares against a fused scoring and selection baseline, and reports results across two models and several input domains.

Critical weaknesses
  • The exact-selection guarantee would benefit from a direct GPU check. The proof and numerical conditions are detailed, but a measured Top-K match rate against the original indexer would make the implementation claim easier to assess.

  • The extra memory cost needs clearer reporting. Appendix mentions a capacity repair that adds 9.94 GiB of workspace. It would help to report the peak additional memory in the end-to-end experiments.

Questions for authors

See weakeness

2 comments
AuthorsOpenReview ↗

Response to Reviewer PmWk

Thank you for your positive assessment of the signed-score certificate and the evaluation across models and input domains. We appreciate the request for more direct GPU validation and clearer memory accounting.

W1. Direct GPU agreement with the original indexer

We checked the actual GPU outputs against the original indexer on identical inputs before and after timing. The paper's microbenchmark validation covers 2,520 input-and-layer cases and 77,414,400 query checks, with zero selection errors. All 91,342,848 individual score comparisons were bitwise identical to the original baseline.

We additionally evaluated the current DoSA kernel implementation through a replay of captured inference workloads. These use query, key, and scoring-weight tensors from actual model inference across layers, context lengths, and query-batch sizes. Two passes over 18,711 workload cases produced 85,050 complete Indexer calls and 74,844 output checks, all passing. Four focused boundary-score cases, one tied-score overflow case, and twelve recovery and data-layout cases also passed.

EvaluationCoverageResult
Paper GPU output validation77,414,400 query checksZero selection errors
Individual score comparisons91,342,848 comparisons100% bitwise agreement
Captured inference workload replay18,711 cases, 74,844 output checksAll passed

Every rejected token has a conservative upper bound below a threshold already attained by enough fully scored tokens to fill the selection. Remaining candidates receive their original full scores, and capacity overflow invokes exact recovery. We will present the GPU measurements together with this explanation in the main text.

W2. The 9.94 GiB workspace increase and memory reuse

The appendix value describes the extra GPU workspace allocated by the capacity repair in the layer-wise retrieval replay. For a capacity of approximately one million keys and 16,384 query rows, the additional allocation per GPU is 9.9375 GiB, rounded to 9.94 GiB in the paper.

Additional workspaceSize per GPU
Candidate key IDs6.00 GiB
Candidate-processing work lists0.1875 GiB
Score and key-ID records for exact selection3.75 GiB
Total increment9.9375 GiB

The candidate buffers and record storage are allocated once for the execution capacity and reused across query blocks, model layers, and sequential calls. Larger query chunks are processed in blocks that reuse this storage. The serving backend reserves the execution workspace before sizing the key/value cache, so the workspace occupies memory that would otherwise be available to that cache.

We will label the appendix number explicitly as the incremental allocation for this replay configuration and include its buffer sizes and lifetime. We will also add a separate end-to-end memory table reporting the execution-workspace allocation and peak GPU allocation under the model-level configurations. This will make the memory cost and its effect on cache capacity directly visible.

Dear Reviewer,

With fewer than 10 hours remaining in the discussion period, we would appreciate your feedback on our responses. Regarding your concerns about GPU correctness and memory overhead, we provided 77,414,400 query-level checks with zero selection errors and clarified the workspace breakdown and reuse. To the best of our knowledge, DoSA is the first method to guarantee exact Top-K selection for the DSA indexer while avoiding complete score computation for all candidates. We hope it will inspire further exact acceleration methods based on score upper bounds. Our optimized GPU implementation achieves up to 1.69× complete-indexer speedup over LiteTopK, which was recently merged into SGLang, and we will open-source the code after the review period.

If these results and clarifications address your concerns, would you consider raising your rating?

Thank you for your time and consideration.

Reviewer_q2VEOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes DoSA to speed up the indexer in DeepSeek-style sparse attention for long inputs. The main idea is to use a cheap upper bound to identify and skip tokens that cannot make it into the top-K, without changing the final selection.

Critical strengths
  • The paper addresses a relevant problem: as the context length increases, the indexer becomes a bottleneck during prefill.
  • Experiments show consistent speedups over both SGLang and LiteTopK.
Critical weaknesses
  • The paper proves that DoSA selects the same tokens as the original indexer, but I could not find an experiment that verifies this (only CPU checks are mentioned). Since the kernel runs in FP8, I think it is important to compare the tokens selected by DoSA and the original indexer on the same inputs.

  • For the timing results, I could not find which GPU was used, how many runs each result is based on, or how much the timings vary. The paper also does not clarify whether the timings include the fallback when the candidate buffer is full.

  • The paper also does not report how much time the screening step itself takes, even though part of the heads still needs to be computed for every token. Without this, it is difficult to understand where the speedup actually comes from.

Questions for authors
  • How are the seed tokens chosen, and how many heads are used during screening for the 32-head and 64-head models? It would also be useful to see how sensitive the speedup is to these choices.
  • Have you tested DoSA on inputs where many tokens have similar scores, for example, repetitive text? Could it be slower than the baseline in such cases?
5 comments
AuthorsOpenReview ↗

Response to Reviewer q2VE (Part 1)

Thank you for recognizing the importance of the indexing bottleneck and the consistent speedups over SGLang and LiteTopK. We appreciate your questions about the GPU implementation and experimental protocol. We address each point below.

W1. GPU verification of exact selection

We checked the actual GPU outputs against the original indexer on the same inputs before and after microbenchmark timing. Across 2,520 input-and-layer cases, we performed 77,414,400 query-level checks with zero selection errors. The validation also performed 91,342,848 individual score comparisons, all bitwise identical to the baseline. We will bring these quantitative GPU results into the main text.

GPU validationCoverageResult
Microbenchmark output checks77,414,400 query checksZero selection errors
Individual score comparisons91,342,848 comparisons100% bitwise agreement

The lossless property follows from a simple observation. We first fully score enough seed tokens to fill the selection and use their lowest selected score as a threshold. A remaining token can be skipped when its conservative upper bound falls below this threshold, because enough already-scored tokens outrank it. Every candidate that can still enter the selection receives its original full score. The bounds account for representation and arithmetic errors, equality is retained during filtering, and buffer overflow invokes exact recovery.

W2. Hardware, repetitions, timing variation, and recovery

Our experiments use the same settings as LiteTopK. We evaluate SGLang, LiteTopK, and DoSA on our platform with matched inputs, precision, and timing boundaries.

Each microbenchmark case has six measured repetitions per method after warmup, giving 45,360 timing records. We use the median latency for each case and average those case medians for the figure bars. The table summarizes run-to-run variation as the median, across cases, of sample standard deviation divided by mean latency.

MethodRepetitions per caseMedian relative standard deviation
SGLang61.11%
LiteTopK61.40%
DoSA61.46%

Complete-Indexer timing includes query/key preparation, screening, candidate processing, final selection, and recovery whenever triggered. The certificate-component ablation explicitly includes recovery when the candidate pool fills. End-to-end time to first token is measured with the prefix cache cleared between requests. We will consolidate this protocol in the experimental setup.

W3. Screening cost and the source of the speedup

Screening computes a smaller set of head contributions and two auxiliary projections for each key. Its preparation is reused across the keys of a query. Full scoring is then concentrated on the surviving candidates, with shared key loading and filtered writeback reducing subsequent memory traffic and selection work.

The existing SciFact retrieval ablation includes the cost of screening in the measured retrieval latency. It covers all 21 indexer-producing layers, with twelve repetitions of each configuration, giving 1,008 timing measurements.

Scoring and writeback configurationMean retrieval latency
Full scoring with all scores written76.20 ms
Full scoring with filtered writeback58.37 ms
Certified screening with all scores written47.67 ms
Certified screening with filtered writeback40.20 ms

Enabling screening reduces retrieval latency by 37.4% with full writeback and by a further 31.1% when filtered writeback is already enabled. Combining screening and filtered writeback reduces latency by 47.3% relative to full scoring with full writeback. These matched comparisons include the screening work and the downstream work it saves. We will make this timing scope explicit and add a stage-level breakdown in the revision.

AuthorsOpenReview ↗

Response to Reviewer q2VE (Part 2)

Q1. Seed selection, screening heads, and sensitivity

At cold start, four queries spaced across the prefill chunk score the common visible prefix. Their selected tokens vote for the seed set. Subsequent chunks reuse tokens selected frequently by recent queries. Each query recomputes the scores of its seed tokens, so the threshold always comes from its own original scores.

ModelTotal indexer headsHeads evaluated during screening
GLM-5.23214, 16, or 20
DeepSeek-V3.26414, 16, or 28

Queries are grouped by the number of positive-weight heads to choose a screening budget. Each configuration also uses two auxiliary projections that bound omitted contributions. A stronger seed raises the rejection threshold. A larger head budget can tighten the bound at additional screening cost. It pays off when the avoided full scoring outweighs that cost.

The existing component ablation illustrates this balance. Aggregating all omitted negative heads raises candidate survival from 2.65% to 4.06% and increases Indexer latency by 12.0%, showing the benefit of choosing aggregation support from activation patterns. Removing negative aggregation raises survival to 95.06% and increases latency by 9.51 times, including recovery. We will report the seed and head configurations explicitly and connect them to this ablation and the paper's analysis of bound tightness.

Q2. Similar scores, repetitive inputs, and possible slowdowns

Yes, DoSA can be slower when many candidates remain competitive. If repetition concentrates scores near the selection threshold, more candidates pass the bound and require full scoring, while screening still has a cost. The paper's analysis expresses this behavior through the score margin, the looseness of the upper bound, and the quality of the seed threshold.

Our current DoSA kernels have passed four focused boundary-score cases, one tied-score candidate-overflow case, and twelve additional recovery and data-layout cases. These exercise exact completion when score boundaries or storage limits require special handling. The paper also retains slower results in its layer-wise measurements. Across 252 comparisons per baseline, one comparison against SGLang and two against LiteTopK are slower, with 0.7%–9.0% added latency. We will explain this behavior alongside the positive results and make the boundary-test coverage explicit.

Dear Reviewer,

With approximately 24 hours remaining in the discussion period, we would appreciate your feedback on our responses, particularly the additional GPU equivalence checks and timing clarifications. If these address your concerns, we kindly ask you to consider raising your rating. We would also be happy to discuss any remaining questions.

Thank you for your time and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Contributions and Outlook

Dear Reviewers,

Thank you for your time and constructive feedback. We would like to summarize DoSA’s main contributions and the broader research direction it opens.

The widely used DeepSeek Sparse Attention (DSA) indexer can become a major bottleneck during long-context prefill. DoSA addresses this bottleneck through certified screening: rather than computing every candidate’s complete indexer score, it computes a lightweight upper bound and skips candidates that provably cannot enter the Top-K. We provide a rigorous mathematical proof that this procedure preserves the original Top-K selection. To the best of our knowledge, DoSA is the first method to guarantee exact Top-K selection for the DSA indexer while avoiding complete score computation for all candidates.

Beyond the theoretical contribution, we extensively optimize DoSA’s GPU kernels and evaluate them using the same settings as LiteTopK, against SGLang and LiteTopK—the latter was merged into SGLang on November 11, 2026. Across English, Chinese, and code workloads, our implementation accelerates the complete indexer by up to 2.74× over SGLang and 1.69× over LiteTopK. End-to-end evaluations on GLM-5.2 and DeepSeek-V3.2 achieve TTFT speedups of up to 1.94× over SGLang and 1.50× over LiteTopK. We will release the code after the review period concludes.

More broadly, DoSA demonstrates that exact indexer acceleration can be achieved by bounding scores rather than fully computing them. Our bounds separately account for positive- and negative-weight heads, but this is only one possible construction. We encourage the community to explore alternative bounds, including block-level approaches, that offer a better balance between computational cost and tightness. We hope this direction will enable further acceleration while preserving exact selection.

A recurring concern across the reviews was that the paper provided a theoretical guarantee of exact selection without sufficient empirical validation. In our responses, we have supplemented the proof with direct GPU comparisons against the original DSA indexer, showing zero selection errors across 77,414,400 query-level checks and bitwise agreement across 91,342,848 individual score comparisons. These results provide strong empirical support for DoSA’s lossless behavior. We have also clarified the hardware, timing protocol, and scope of the speed comparisons. We will incorporate these additions into the main text.

With approximately 33 hours remaining before the author–reviewer discussion closes, we would greatly appreciate your consideration of these additional results and clarifications. If they address your concerns, we kindly ask you to consider revising your assessment and raising your score accordingly. We remain available to answer any further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.