- 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?
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