@inproceedings{zhang-etal-2026-s2o,
    title = "{S}2{O}: Early Stopping for Sparse Attention via Online Permutation",
    author = "Zhang, Yu  and
      Liu, Songwei  and
      Yan, Chenqian  and
      Linsheng  and
      Ning, Beichen  and
      Chen, Fangmin  and
      Wang, Xing",
    editor = "Liakata, Maria  and
      Moreira, Viviane P.  and
      Zhang, Jiajun  and
      Jurgens, David",
    booktitle = "Proceedings of the 64th Annual Meeting of the {A}ssociation for {C}omputational {L}inguistics (Volume 1: Long Papers)",
    month = jul,
    year = "2026",
    address = "San Diego, California, United States",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-acl/2026.acl-long.351/",
    pages = "7737--7751",
    ISBN = "979-8-89176-390-6",
    abstract = "Attention scales quadratically with sequence length, fundamentally limiting long-context inference.Existing block-granularity sparsification can reduce latency, but coarse blocks impose an intrinsic sparsity ceiling, making further improvements difficult even with carefully engineered designs.We present \textbf{S2O}, which performs early \textbf{s}topping for \textbf{s}parse attention via \textbf{o}nline permutation.Inspired by virtual-to-physical address mapping in memory systems, S2O revisits and factorizes FlashAttention execution, enabling inference to load non-contiguous tokens rather than a contiguous span in the original order.Motivated by fine-grained structures in attention heatmaps, we transform explicit permutation into an online, index-guided, discrete loading policy; with extremely lightweight preprocessing and index-remapping overhead, it concentrates importance on a small set of high-priority blocks.Building on this importance-guided online permutation for loading, S2O further introduces an early-stopping rule: computation proceeds from high to low importance; once the current block score falls below a threshold, S2O terminates early and skips the remaining low-contribution blocks, thereby increasing effective sparsity and reducing computation under a controlled error budget.As a result, S2O substantially raises the practical sparsity ceiling.On \textbf{Llama-3.1-8B} under a \textbf{128K} context, S2O reduces single-operator MSE by \textbf{3.82$\times$} at matched sparsity, and reduces prefill compute density by \textbf{3.31$\times$} at matched MSE; meanwhile, it preserves end-to-end accuracy and achieves \textbf{7.51$\times$} attention and \textbf{3.81$\times$} end-to-end speedups."
}