acceptodds
Under review as a conference paper at ICLR 2027

Stratified Sparse Attention: Reducing the Sparse-to-Dense Gap at Extreme Sparsity

Abstract

Large Language Model inference over long contexts is increasingly bottlenecked by the cost of attending to a growing Key-Value (KV) cache. Sparse attention reduces this cost by accessing only a fraction of the cache, but existing methods face a trade-off between deterministic retrieval, which captures high-scoring tokens but discards residual attention mass, and sampling, which improves coverage at the cost of higher variance. Hybrid methods combine top- retrieval with uniform sampling, yet still exhibit a substantial gap from dense attention at aggressive sparsity. We introduce *Stratified Sparse Attention (SSA)*, a unified framework combining deterministic retrieval with score-guided sampling. SSA deterministically attends to high-scoring tokens while sampling the residual using proxy attention scores and correcting for their inclusion probabilities, thereby recovering attention mass beyond the retrieval set. SSA encompasses top-, top-, and hybrid top-+sampling as special cases. Across RULER, LongBench, LOFT, and AIME, and five models ranging from 3B to 27B parameters, SSA consistently improves over the baselines at matched sparsity. On RULER-HARD, SSA improves accuracy over the strongest baseline from 72.5% to 83.7% at 32K and from 69% to 76.8% at 128K over the strongest baseline under sparsity, recovering 94% and 91% of dense-attention performance, respectively. With optimized CUDA kernels, SSA achieves up to decode speedup over FlashInfer at 1M context, demonstrating that its accuracy gains translate into practical long-context inference acceleration.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Importance Sampling, Weighted Probability Proportional to Size, Sparse Attention, Inference

Reviews

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

This paper proposes Stratified Sparse Attention (SSA), which combines deterministic top-k retrieval with score-guided importance sampling to better approximate dense attention at high sparsity. The method uses inverse-probability weighting and provides theoretical error bounds and optimized CUDA kernels. Experiments on RULER, LongBench, LOFT, and AIME demonstrate improved accuracy over existing sparse attention methods, with up to 2.96× decode attention speedup over FlashInfer at 1M context length.

Critical strengths

1. Strong accuracy at extreme sparsity. SSA consistently improves over top-k retrieval and uniform sampling, with particularly notable gains on AIME under aggressive sparsity.

2. Theoretical and practical contributions. The paper provides theoretical error bounds and optimized CUDA kernels, supported by evaluations across multiple models and benchmarks.

Critical weaknesses

1. Incomplete and non-standard RULER evaluation. The paper evaluates only 6 of the standard 13 RULER tasks, using 100 samples per task instead of the default 500. The selection criteria for the non-standard RULER-HARD subset are also unclear, limiting comparability and raising concerns about the generalizability of the results.

2. Limited practical efficiency and unsupported end-to-end speedup claims. SSA achieves meaningful speedups mainly at extremely long contexts and aggressive sparsity levels, and is slower than FlashInfer at 128K. More importantly, although the Introduction explicitly claims end-to-end decoding speedups, Figure 3 and Table 3 report only attention-level latency. No end-to-end generation results or direct latency comparisons with Quest [1] and PQCache [2] are provided, leaving the practical efficiency claims insufficiently supported.

[1] Tang J, Zhao Y, Zhu K, et al. Quest: Query-aware sparsity for efficient long-context llm inference[J]. arXiv preprint arXiv:2406.10774, 2024.

[2] Zhang H, Ji X, Chen Y, et al. Pqcache: Product quantization-based kvcache for long context llm inference[J]. Proceedings of the ACM on Management of Data, 2025, 3(3): 1-30.

Questions for authors

1. RULER evaluation completeness. Why does the paper evaluate only 6 RULER tasks with 100 samples each? Could the authors clarify the definition of RULER-HARD and provide results on the complete standard RULER benchmark?

2. End-to-end efficiency. Could the authors provide actual end-to-end generation latency or throughput measurements, along with comparisons against Quest and PQCache under matched settings? More importantly, could the authors compare accuracy at matched speedup levels to demonstrate whether SSA offers a better accuracy–efficiency trade-off than existing methods?

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

This paper proposes SSA (stratified sparse attention), which combines deterministic top-k/top-p KV retrieval with importance-guided sampling. SSA first retrieves a certain amount of top KVs, and then uses important-score-guided sampling for the remaining residual KVs based on their inclusion probabilities. The paper presents both empirical experiments to show SSA outperforms previous work in terms of the accuracy at the same sparsity level, and also theoretical proofs on the approximation error bound.

Critical strengths
  • The paper presents both empirical and theoretical results.
  • The evaluation includes many SOTA baselines, models, and datasets.
Critical weaknesses
  • The contribution is somewhat incremental. The hybrid scheme with classic top-k/top-p and sampling has been used in previous work (e.g., vAttention), and importance sampling is also explored before (e.g., MagicPIG). The paper is conceptually a direct combination of the two.
  • The evaluation is somewhat unfair. It mainly compares with traditional top-k/top-p methods at a fixed high sparsity level, which does not represent the typical working conditions of these baselines. Also, the same sparsity does not imply the same runtime performance because of the different overheads. A better comparison way should be a direct iso-accuracy speedup comparison.
  • The evaluation only shows the speedup of SSA over the dense case, but misses sparse baselines. This is critical because the overhead of SSA is likely higher than previous baselines due to the more complex sampling process. So at the same sparsity level, SSA is likely to be slower than the sparse baselines. Justifying this overhead is important.
  • While the paper claims that SSA can encompass top-k, top-p, and hybrid top-k+sampling, I do not see how it directly models top-p from the theoretical analysis.
Questions for authors
  1. SSA seems an incremental improvement of vAttention by replacing its uniform sampling with importance-guided sampling, which has also been explored in MagicPIG. So how is SSA fundamentally different from this combination of vAttention+MagicPIG? Can you also show some quantitative comparison results?

  2. The main results of the paper show that SSA outperforms PQ, Quest, MagicPIG, etc. in terms of accuracy at the same sparsity. But this is unfair. The very high sparsity level (2%, or 50x) limits these baselines to only include very few tokens, while SSA has the sampling part to cover more. So this high sparsity biases SSA. Can you show the accuracy comparison at the typical sparsity levels of these baselines? Because sampling has higher overheads than these non-sampling designs, increasing the sparsity levels for these baselines does not imply worse speedups. See the next question for performance comparison.

  3. Could you show runtime performance comparison with some sparse baselines, such as vAttention, Quest, and MagicPIG?

  4. Could you explain how the theoretical formalization of SSA in 4.2 also captures top-p as special case, as claimed in the introduction?

1 comment
AuthorsOpenReview ↗

Gentle Reminder

Dear Reviewer riR8,

Thank you for your thoughtful review. With the discussion period ending shortly on Nov 18 (AoE), we would deeply appreciate it if you could take a look at our rebuttal and follow-up comments.

Please let us know if you have any remaining concerns. Thank you for your time and consideration!

Sincerely,

The Authors

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

This paper proposes Stratified Sparse Attention (SSA), a sparse attention framework that combines deterministic retrieval of high-attention tokens with score-guided importance sampling over the remaining KV cache. It provides approximation bounds and optimized CUDA kernels, with experiments across several models and long-context benchmarks.

Critical strengths

S1. SSA achieves substantial accuracy improvements at extreme sparsity. On RULER-HARD 32K with Llama-3.1-8B, accuracy improves from 72.51 to 83.67 at 50× sparsity.

S2. Theoretical analysis and practical GPU implementation are both provided, and 2.96× acceleration is achieved for one attention layer, compared to dense FlashInfer.

Critical weaknesses

W1. Limited runtime comparison. While the paper demonstrates the efficiency by comparing to dense FlashInfer, it does not show how efficient SSA is against other state-of-the-art sparse attention implementations (e.g., PQCache, vAttention). Full-model decoding performance is also not reported, making the practical efficiency advantage less clear.

W2. Theoretical study and practical design are not well-matched. The theoretical algorithm uses adaptive budget allocation, whereas the optimized implementation adopts a fixed heavy fraction and clips small inclusion probabilities. While Table 13 shows similar empirical accuracy, the impact of these modifications on the theoretical guarantees and the bias introduced by probability clipping are not fully analyzed.

Questions for authors

How do the fixed heavy fraction and inclusion-probability clipping affect the theoretical guarantees? Can the authors quantify the bias introduced by probability clipping?

How does SSA compare with optimized PQCache and vAttention in latency and full-model decoding throughput under matched conditions?

1 comment
AuthorsOpenReview ↗

Gentle Reminder

Dear Reviewer nREH,

Thank you for your thoughtful review. With the discussion period ending shortly on Nov 18 (AoE), we would deeply appreciate it if you could take a look at our rebuttal and follow-up comments.

Please let us know if you have any remaining concerns. Thank you for your time and consideration!

Sincerely,

The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Genereal Response (Summary of Contributions and Rebuttal Phase Discussion)

We thank all the reviewers for their constructive feedback and thoughtful questions. Below, we provide a concise summary highlighting the key strengths highlighted by the reviewers, the concerns addressed and clarifications provided during the rebuttal period, and emphasizing the novelty of our work.

Strengths

1. [nREH, riR8, EnSe]: acknowledged the strength of combining theoretical analysis with extensive empirical evaluations, highlighting the paper's theoretical error bounds and practical implementation.

2. [nREH, EnSe]: recognized SSA's substantial accuracy improvements at extreme sparsity, particularly on challenging long-context benchmarks such as RULER-HARD and AIME.

3. [nREH, EnSe]: highlighted the practical significance of SSA's GPU implementation.

4. [riR8]: appreciated the comprehensive evaluation across multiple state-of-the-art baselines, language models, and datasets.

5. [nREH, EnSe]: praised the clarity and presentation of the manuscript, describing it as clear and easy to follow.

Concerns Addressed

1. [nREH, riR8, EnSe]: requested end-to-end decoding throughput and latency comparisons against sparse attention baselines. In response, we provided full-model decoding throughput and latency results against PQCache and Quest under matched-accuracy settings. These results demonstrate that SSA at 100$\times$ sparsity achieves higher decoding throughput than Quest and PQCache at 10$\times$ sparsity while maintaining comparable accuracy, highlighting SSA's superior accuracy-efficiency trade-off. Reviewer EnSe acknowledged these additional experiments and clarifications, noting that they addressed most of their concerns regarding practical efficiency.

2. [nREH]: requested clarification on how the fixed heavy fraction and inclusion-probability clipping affect SSA's theoretical guarantees. In response, we provided a detailed mathematical derivation demonstrating that fixing the heavy fraction introduces no additional error term and preserves the form of the theoretical guarantees. We further clarified that probability clipping does not introduce bias, as SSA uses the clipped inclusion probabilities for reweighting. Thus, the estimates remain unbiased, and the theoretical guarantees continue to hold. We also acknowledged and corrected the inaccurate statement regarding clipping-induced bias in the revised manuscript.

3. [EnSe]: requested clarification on the completeness of our RULER evaluation. For completeness, we additionally evaluated the remaining 7 RULER tasks across 32K, 64K, and 128K contexts, demonstrating that most methods achieve near-perfect accuracy on these tasks, offering limited discriminatory value. The reviewer acknowledged our additional experiments and expressed satisfaction with the clarification.

4. [riR8]: requested clarifications regarding SSA's novelty relative to vAttention and MagicPIG, fairness of sparsity comparisons, runtime efficiency, and theoretical connection to top-pp attention. In response, we clarified SSA's theoretical and algorithmic novelty, emphasizing its unified theoretical framework based on weighted sampling that integrates deterministic token retention with residual estimation. We also highlighted SSA's extensibility to arbitrary top-kk scoring methods and its ability to leverage these scores for both deterministic selection and importance-guided residual estimation. We further clarified that all methods operate under identical KV-access budgets, demonstrated SSA's accuracy improvements at both moderate (10$\times$-20$\times$) and extreme (50$\times$) sparsity. Finally, we established the theoretical connection to top-pp through adaptive budget selection and probabilistic output-error guarantees.

Novelty of Our Work

SSA provides a unified theoretical framework based on weighted sampling that integrates deterministic token retention with importance-guided residual estimation. Unlike vAttention and MagicPIG, SSA explicitly accounts for the mismatch between estimated importance scores and their true values, provides insights into optimal sampling budget allocation, and offers a generic recipe that can leverage the scoring function of any top-kk sparse attention method. Most importantly, SSA substantially narrows the accuracy gap between sparse and dense attention, even at extreme sparsity levels, demonstrating significant improvements over existing approaches.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.