Support Basis: Fast Attention Beyond Bounded Entries

Maryam Aliakbarpour, Vladimir Braverman, Junze Yin, Haochen Zhang
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:325-333, 2026.

Abstract

Large language models (LLMs) have demonstrated remarkable performance across a wide range of tasks. However, the quadratic complexity of softmax attention remains a central bottleneck that limits their scalability. Alman and Song (NeurIPS 2023a; NeurIPS 2024a) proposed sub-quadratic time algorithms for attention inference and training, respectively, but they rely on the restrictive \textbf{bounded-entry assumption}. We show that this assumption rarely holds in practice, which significantly limits their applicability to modern LLMs. In this paper, we introduce \textbf{support-basis decomposition}, a new technique for accurate and efficient attention inference and training \textbf{without} the bounded-entry assumption. We empirically show that the entries of the query and key matrices exhibit sub-Gaussian behavior. Leveraging this widely observed property, we perform exact computation on sparse components and polynomial approximation on dense components. Without relying on restrictive assumptions, we theoretically show that our algorithm achieves sub-quadratic runtime while matching the approximation error of prior work, and we empirically validate its computational efficiency and downstream task performance. We further generalize our method to a multi-threshold setting that eliminates all distributional assumptions, providing the first theoretical justification for the empirical success of polynomial attention. Moreover, we show that softmax attention can be closely approximated by multiple polynomial attentions with significantly smaller $\ell_p$ error.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-aliakbarpour26a, title = { Support Basis: Fast Attention Beyond Bounded Entries }, author = {Aliakbarpour, Maryam and Braverman, Vladimir and Yin, Junze and Zhang, Haochen}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {325--333}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/aliakbarpour26a/aliakbarpour26a.pdf}, url = {https://proceedings.mlr.press/v300/aliakbarpour26a.html}, abstract = { Large language models (LLMs) have demonstrated remarkable performance across a wide range of tasks. However, the quadratic complexity of softmax attention remains a central bottleneck that limits their scalability. Alman and Song (NeurIPS 2023a; NeurIPS 2024a) proposed sub-quadratic time algorithms for attention inference and training, respectively, but they rely on the restrictive \textbf{bounded-entry assumption}. We show that this assumption rarely holds in practice, which significantly limits their applicability to modern LLMs. In this paper, we introduce \textbf{support-basis decomposition}, a new technique for accurate and efficient attention inference and training \textbf{without} the bounded-entry assumption. We empirically show that the entries of the query and key matrices exhibit sub-Gaussian behavior. Leveraging this widely observed property, we perform exact computation on sparse components and polynomial approximation on dense components. Without relying on restrictive assumptions, we theoretically show that our algorithm achieves sub-quadratic runtime while matching the approximation error of prior work, and we empirically validate its computational efficiency and downstream task performance. We further generalize our method to a multi-threshold setting that eliminates all distributional assumptions, providing the first theoretical justification for the empirical success of polynomial attention. Moreover, we show that softmax attention can be closely approximated by multiple polynomial attentions with significantly smaller $\ell_p$ error. } }
Endnote
%0 Conference Paper %T Support Basis: Fast Attention Beyond Bounded Entries %A Maryam Aliakbarpour %A Vladimir Braverman %A Junze Yin %A Haochen Zhang %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-aliakbarpour26a %I PMLR %P 325--333 %U https://proceedings.mlr.press/v300/aliakbarpour26a.html %V 300 %X Large language models (LLMs) have demonstrated remarkable performance across a wide range of tasks. However, the quadratic complexity of softmax attention remains a central bottleneck that limits their scalability. Alman and Song (NeurIPS 2023a; NeurIPS 2024a) proposed sub-quadratic time algorithms for attention inference and training, respectively, but they rely on the restrictive \textbf{bounded-entry assumption}. We show that this assumption rarely holds in practice, which significantly limits their applicability to modern LLMs. In this paper, we introduce \textbf{support-basis decomposition}, a new technique for accurate and efficient attention inference and training \textbf{without} the bounded-entry assumption. We empirically show that the entries of the query and key matrices exhibit sub-Gaussian behavior. Leveraging this widely observed property, we perform exact computation on sparse components and polynomial approximation on dense components. Without relying on restrictive assumptions, we theoretically show that our algorithm achieves sub-quadratic runtime while matching the approximation error of prior work, and we empirically validate its computational efficiency and downstream task performance. We further generalize our method to a multi-threshold setting that eliminates all distributional assumptions, providing the first theoretical justification for the empirical success of polynomial attention. Moreover, we show that softmax attention can be closely approximated by multiple polynomial attentions with significantly smaller $\ell_p$ error.
APA
Aliakbarpour, M., Braverman, V., Yin, J. & Zhang, H.. (2026). Support Basis: Fast Attention Beyond Bounded Entries . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:325-333 Available from https://proceedings.mlr.press/v300/aliakbarpour26a.html.

Related Material