  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.
