Elamur Research⌕
☰
home / papers / 2026 / S2O: Early Stopping for Sparse Attention via Online Permutation

S2O: Early Stopping for Sparse Attention via Online Permutation

Paper · 2026 · Yu Zhang, Songwei Liu, Chenqian Yan et al.

Summary

Long-context LLM inference is held back by attention, whose cost grows quadratically with sequence length. Block-sparse attention built on FlashAttention reduces this cost. The authors argue that fixed-size blocks impose a sparsity ceiling. Real attention maps are made of thin vertical, horizontal and diagonal stripes, so even well-chosen blocks contain many near-zero entries.

S2O tackles this without physically moving tensors. Borrowing the idea of logical-to-physical address mapping, it builds lightweight index arrays: a segment-local query ordering and a global key/value ordering ranked by stripe-level mean pooling. The kernel uses these indices to fetch scattered tokens into SRAM. Blocks are then processed from most to least important. Computation stops once a block's score falls under a threshold τ, skipping the low-value tail within a controlled error budget. The authors report indexing overhead typically below 10%.

On Llama-3.1-8B at 128K tokens, S2O achieves lower operator error at equal sparsity, preserves end-to-end accuracy, and accelerates both attention and full inference. This suggests that reorder-aware, fine-grained sparsity can move past block-granularity limits.

Key points

  • At 128K context on Llama-3.1-8B, S2O gives the following results versus FlashAttention-based baselines:
    • 3.82× lower single-operator MSE at matched sparsity.
    • 3.31× lower prefill compute density at matched MSE.
    • Up to 7.51× attention speedup and 3.81× end-to-end speedup.
  • In the 128K latency comparison, S2O reaches sparsity 0.933 with MSE 9.50e-05. This beats XAttn (2.74×), PBS-Attn (3.00×) and FlexPrefill (3.43×) in end-to-end speedup.
  • Hyperparameter ablations were run on Qwen3-8B at 128K.
    • The threshold τ dominates the speed–accuracy trade-off. With S=2048, raising τ from 0.001 to 0.020 lifts sparsity from 0.721 to 0.944 and MSE from 0.00058 to 0.00876.
    • Segment length S (1024–4096) has little effect on error.
  • In the component ablation, query permutation (Q perm) raises sparsity from 0.796 to 0.852 at similar error. Keeping only the dense local window produces much higher MSE (about 1.84×10⁻³).
  • Limitations include:
    • Extra hyperparameters that may need re-tuning.
    • Evaluation only on the prefill stage of decoder-only LLMs.
    • Experiments on a single GPU and software stack.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Xiamen UniversityXiamen · China24 works · 2,317 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksComputer Vision and Pattern Recognition · 3,486 works

Cite

Cite as Yu Zhang, Songwei Liu, Chenqian Yan, Linsheng, Beichen Ning, Fangmin Chen and Xing Wang. 2026. S2O: Early Stopping for Sparse Attention via Online Permutation. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-long.351

@inproceedings{zhang2026s2o,
  title = {{S2O: Early Stopping for Sparse Attention via Online Permutation}},
  author = {Yu Zhang, Songwei Liu, Chenqian Yan, Linsheng, Beichen Ning, Fangmin Chen and Xing Wang},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.351},
  url = {https://doi.org/10.18653/v1/2026.acl-long.351}
}

References

32 references, 12 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Yushi Bai, Shangqing Tu, Jiajie Zhang, Hao Peng, Xiaozhi Wang, Xin Lv, Shulin Cao, Jiazheng Xu, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. 2024. Longbench v2: Towards deeper understanding and reasoning on realistic long-context multitasks. arXiv preprint arXiv:2412.15204.
  2. Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, Yang Zhang, and Boris Ginsburg. 2024. Ruler: What’s the real context size of your long-context language models? arXiv preprint arXiv:2404.06654.
  3. Huiqiang Jiang, Yucheng Li, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin Ahn, Zhenhua Han, Amir H. Abdi, Dongsheng Li, Chin-Yew Lin, Yuqing Yang, and Lili Qiu. 2024. MInference 1.0: Accelerating pre-filling for long-context LLMs via dynamic sparse attention. In The Thirty-eighth Annual Conferen…
  4. Kumara Kahatapitiya, Haozhe Liu, Sen He, Ding Liu, Menglin Jia, Chenyang Zhang, Michael S. Ryoo, and Tian Xie. 2024. Adaptive caching for faster video generation with diffusion transformers. Preprint, arXiv:2411.02397. — [arXiv:2411.02397](https://arxiv.org/abs/2411.02397) find
  5. Xunhao Lai, Jianqiao Lu, Yao Luo, Yiyuan Ma, and Xun Zhou. 2025. Flexprefill: A context-aware sparse attention mechanism for efficient long-sequence inference. In The Thirteenth International Conference on Learning Representations. find
  6. Iz Beltagy, Matthew E. Peters, and Arman Cohan. 2020. Longformer: The long-document transformer. Preprint, arXiv:2004.05150.
  7. Yucheng Li, Huiqiang Jiang, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin Ahn, Amir H Abdi, Dongsheng Li, Jianfeng Gao, Yuqing Yang, and Lili Qiu. 2025. MMIference: Accelerating pre-filling for long-context vlms via modality-aware permutation sparse attention. In Forty-second International Confe… find
  8. Tri Dao. 2024. FlashAttention-2: Faster attention with better parallelism and work partitioning. In International Conference on Learning Representations (ICLR).
  9. Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, Xingyu Dang, and Song Han. 2023. Awq: Activation-aware weight quantization for llm compression and acceleration. arXiv. find
  10. Vage Egiazarian, Andrei Panferov, Denis Kuznedelev, Elias Frantar, Artem Babenko, and Dan Alistarh. 2024. Extreme compression of large language models via additive quantization. Preprint, arXiv:2401.06118.
  11. Akide Liu, Jing Liu, Zizheng Pan, Yefei He, Gholamreza Haffari, and Bohan Zhuang. 2024a. Minicache: Kv cache compression in depth dimension for large language models. Preprint, arXiv:2405.14366. — [arXiv:2405.14366](https://arxiv.org/abs/2405.14366) find
  12. Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, and 542 o… — The Llama 3 Herd of Models
  13. Youping Gu, Xiaolong Li, Yuhao Hu, Minqi Chen, and Bohan Zhuang. 2025. Blade: Block-sparse attention meets step distillation for efficient video generation. Preprint, arXiv:2508.10774. — [arXiv:2508.10774](https://arxiv.org/abs/2508.10774) find
  14. Zhiyuan He, Yike Zhang, Chengruidong Zhang, Huiqiang Jiang, Yuqing Yang, and Lili Qiu. 2025. Trianglemix: Accelerating prefilling via decoding-time contribution sparsity. Preprint, arXiv:2507.21526. find
  15. Songwei Liu, Chao Zeng, Lianqiang Li, Chenqian Yan, Lean Fu, Xing Mei, and Fangmin Chen. 2024b. Foldgpt: Simple and effective large language model compression scheme. arXiv preprint arXiv:2407.00928. — [arXiv:2407.00928](https://arxiv.org/abs/2407.00928) find
  16. Songwei Liu, Chao Zeng, Chenqian Yan, Xurui Peng, Xing Wang, Fangmin Chen, and Xing Mei. 2025. Error propagation mechanisms and compensation strategies for quantized diffusion. arXiv preprint arXiv:2508.12094. — [arXiv:2508.12094](https://arxiv.org/abs/2508.12094) find
  17. Xinyin Ma, Gongfan Fang, Michael Bi Mi, and Xinchao Wang. 2024. Learning-to-cache: Accelerating diffusion transformer via layer caching. Preprint, arXiv:2406.01733. — [arXiv:2406.01733](https://arxiv.org/abs/2406.01733) find
  18. Maxim Milakov and Natalia Gimelshein. 2018. Online normalizer calculation for softmax. Preprint, arXiv:1805.02867.
  19. Xurui Peng, Hong Liu, Chenqian Yan, Rui Ma, Fangmin Chen, Xing Wang, Zhihua Wu, Songwei Liu, and Mingbao Lin. 2025. Ertacache: Error rectification and timesteps adjustment for efficient diffusion. Preprint, arXiv:2508.21091. — [arXiv:2508.21091](https://arxiv.org/abs/2508.21091) find
  20. Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. 2024. Quest: Query-aware sparsity for efficient long-context llm inference. Preprint, arXiv:2406.10774.
  21. Xinghao Wang, Pengyu Wang, Dong Zhang, Chenkun Tan, Shaojun Zhou, Zhaoxiang Liu, Shiguo Lian, Fangxu Liu, Kai Song, and Xipeng Qiu. 2025. Sparser block-sparse attention via token permutation. Preprint, arXiv:2510.21270. — [arXiv:2510.21270](https://arxiv.org/abs/2510.21270) find
  22. Haocheng Xi, Shuo Yang, Yilong Zhao, Chenfeng Xu, Muyang Li, Xiuyu Li, Yujun Lin, Han Cai, Jintao Zhang, Dacheng Li, and 1 others. 2025. Sparse videogen: Accelerating video diffusion transformers with spatial-temporal sparsity. arXiv preprint arXiv:2502.01776. find
  23. Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. 2023. Efficient streaming language models with attention sinks. arXiv. find
  24. Ruyi Xu, Guangxuan Xiao, Haofeng Huang, Junxian Guo, and Song Han. 2025. Xattention: Block sparse attention with antidiagonal scoring. In Proceedings of the 42nd International Conference on Machine Learning (ICML).
  25. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, and 41 others. 2025a. Qwen3 technical report. Preprint, arXiv:2505.09388.
  26. Shuo Yang, Haocheng Xi, Yilong Zhao, Muyang Li, Jintao Zhang, Han Cai, Yujun Lin, Xiuyu Li, Chenfeng Xu, Kelly Peng, and 1 others. 2025b. Sparse videogen2: Accelerate video generation with sparse attention via semantic-aware permutation. arXiv preprint arXiv:2505.18875. find
  27. Chao Zeng, Songwei Liu, Yusheng Xie, Hong Liu, Xiaojian Wang, Miao Wei, Shu Yang, Fangmin Chen, and Xing Mei. 2025a. Abq-llm: Arbitrary-bit quantized inference acceleration for large language models. Preprint, arXiv:2408.08554. find
  28. Chao Zeng, Songwei Liu, Shu Yang, Fangmin Chen, Lean Fu, and Xing Mei. 2025b. Gqsa: Group quantization and sparsity for accelerating large language model inference. Preprint, arXiv:2412.17560. find
  29. Jintao Zhang, Chendong Xiang, Haofeng Huang, Jia Wei, Haocheng Xi, Jun Zhu, and Jianfei Chen. 2025a. Spargeattn: Accurate sparse attention accelerating any model inference. In International Conference on Machine Learning (ICML). find
  30. Yu Zhang, Dong Guo, Fang Wu, Guoliang Zhu, Dian Ding, and Yiming Zhang. 2025b. AnchorAttention: Difference-aware sparse attention with stripe granularity. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 8548–8560, Suzhou, China. Association for Comput… find
  31. Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, Yifan Du, Chen Yang, Yushuo Chen, Zhipeng Chen, Jinhao Jiang, Ruiyang Ren, Yifan Li, Xinyu Tang, Zikang Liu, and 3 others. 2025. A survey of large language models. Prepri…
  32. Chang Zou, Xuyang Liu, Ting Liu, Siteng Huang, and Linfeng Zhang. 2025. Accelerating diffusion transformers with token-wise feature caching. Preprint, arXiv:2410.05317. — [arXiv:2410.05317](https://arxiv.org/abs/2410.05317) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2026-s2o-early-stopping-sparse-attention/