@inproceedings{liang-etal-2025-conv,
    title = "Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers",
    author = "Liang, Yingyu  and
      Liu, Heshan  and
      Shi, Zhenmei  and
      Song, Zhao  and
      Xu, Zhuoyan  and
      Zhao, Jiale  and
      Zhuang, Zhen",
    editor = "Christodoulopoulos, Christos  and
      Chakraborty, Tanmoy  and
      Rose, Carolyn  and
      Peng, Violet",
    booktitle = "Findings of the Association for Computational Linguistics: EMNLP 2025",
    month = nov,
    year = "2025",
    address = "Suzhou, China",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/author-page-yu-wang-polytechnic/2025.findings-emnlp.363/",
    doi = "10.18653/v1/2025.findings-emnlp.363",
    pages = "6857--6894",
    ISBN = "979-8-89176-335-7",
    abstract = "The self-attention mechanism is key to the success of transformers in recent large language models (LLMs). However, the quadratic computational cost, $O(n^2)$, with respect to the input sequence length $n$ poses a significant obstacle to further improvement and scalability in longer contexts.In this work, we leverage the convolution-like structure of attention matrices to develop an efficient approximation method for attention computation using convolution matrices. We propose a $\mathsf{conv}$ basis system, analogous to the rank basis, and show that any lower triangular matrix can be decomposed as a sum of structured convolution matrices in this basis. We then design a fast algorithm to approximate the attention matrix using a sum of $k$ convolution matrices. This enables us to compute attention during \textit{inference} via Fast Fourier Transforms (FFT) in $O(knd \log n)$ time, where $d$ is the hidden dimension, achieving nearly linear time complexity, $n^{1+o(1)}$, in practical scenarios where $kd = n^{o(1)}$. Furthermore, both \textit{training forward} and \textit{backward gradient} computations can be performed in $n^{1+o(1)}$ time as well.We provide theoretical guarantees on runtime and approximation error and conduct preliminary experiments to evaluate the effectiveness of our approach. We hope this new paradigm for accelerating attention computation in transformer models facilitates their application to longer contexts."
}