$\pi$-Attention: Online Efficient Sparse Transformers for Long-Context Modeling

Abstract:Sparse attention is crucial in long-context Transformers, which restricts each token to a limited neighborhood and thereby reduces the quadratic cost of full self-attention. Local windows capture nearby context effectively, yet they induce a receptive-field bottleneck for dependencies beyond the window, limiting long-range modeling under moderate depth. In this paper, we propose $\pi$-Attention, an \emph{online efficient} sparse attention operator: as tokens arrive, each step maintains a streaming working set of local neighbors plus a $\pi$-indexed long-range fetch, fused by an adaptive prior under a shared softmax. Rather than materializing a global sparse mask in advance, $\pi$-Attention computes attention on the live working set with hierarchy-aware IO. We analyze causal reachability and minimum depth under this online rule, and show per-step cost remains $\mathcal{O}(k)$. Experiments on language modeling, Long Range Arena, and efficiency profiling---across 4K--32K context lengths---show consistent gains over local-window and other sparse baselines, approaching dense attention quality at linear cost.

Computation and Language (cs.CL); Artificial Intelligence (cs.AI)

arXiv:2511.10696 [cs.CL]

(or arXiv:2511.10696v3 [cs.CL] for this version)

https://doi.org/10.48550/arXiv.2511.10696 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.