On the Computational Hardness of Transformers

The transformer architecture has revolutionized modern AI across language, vision, and beyond. It consists of L layers of multi-head attention, where each layer runs H attention heads in parallel and feeds the combined output to the subsequent layer. In attention, each token within an input of length N is represented by an embedding vector of dimension m. Computationally, an attention mechanism primarily involves multiplying three N × m matrices, while applying a softmax operation to the intermediate product of the first two matrices. A significant body of work has been devoted to analyzing the time complexity of attention, leading to several recent advances.

On the other hand, known algorithms for transformers compute each attention head independently. This raises a fundamental question that has recurred throughout theoretical computer science under the guise of "direct sum" problems: can multiple instances of the same problem be solved more efficiently than solving each instance separately? Many answers to this question, both positive and negative, have arisen in fields spanning communication complexity and algorithm design. Thus, a key challenge in understanding the computational hardness of transformers is to determine whether their computation can be performed more efficiently than LH independent evaluations of attention.

In this paper, we resolve this question in the negative, and give the first non-trivial computational lower bounds for multi-head multi-layer transformers. In the small embedding regime (m = N o(1) ), computing LH attention heads separately takes LHN 2+o(1) time. We establish that this is essentially optimal under the Strong Exponential Time Hypothesis (SETH). In the large embedding regime (m = N ), one can compute LH attention heads separately using LHN ω+o(1) arithmetic operations (plus exponents), where ω is the matrix multiplication exponent. We establish that this is optimal, by showing that LHN ω-o(1) arithmetic operations are necessary when ω > 2. Our lower bound in the large embedding regime relies on a novel application of the Baur-Strassen theorem, a powerful algorithmic tool underpinning the famous backpropagation algorithm.