On The Computational Complexity of Self-Attention

By Feyza Duman Keles, Pruthuvi Maheshakya Wijewardena, Chinmay Hegde. International Conference on Algorithmic Learning Theory, 2022

298 citations recorded by the source corpus.

Transformer architectures have led to remarkable progress in many state-of-art applications. However, despite their successes, modern transformers rely on the self-attention mechanism, whose time- and space-complexity is quadratic in the length of the input. Several approaches have been proposed to speed up self-attention mechanisms to achieve sub-quadratic running time; however, the large majority of these works are not accompanied by rigorous error guarantees. In this work, we establish lower bounds on the computational complexity of self-attention in a number of scenarios. We prove that the time complexity of self-attention is necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is false. This argument holds even if the attention computation is performed only approximately, and for a variety of attention mechanisms. As a complement to our lower bounds, we show that it is indeed possible to approximate dot-product self-attention using finite Taylor series in linear-time, at the cost of having an exponential dependence on the polynomial order.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/ac2e15fbfe3ea338725f5d33d17a5a687609c431

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Tri Dao
  2. Christopher R'e
  3. Atri Rudra
  4. Daniel Y. Fu
  5. Khaled Kamal Saab
  6. Armin W. Thomas
  7. Alexander J. Ratner
  8. Albert Gu

In Electrical and Electronic Engineering

  1. Christopher R'e
  2. Tri Dao

Citations in the corpus