A transformer with L layers, H attention heads per layer, and input length N has a natural computational cost: for each layer, each head performs an attention operation that scales as N² (or Nω for large embeddings, where ω is the matrix multiplication exponent). Computing all heads independently costs L × H times the single-head cost. The question is whether computing them jointly — exploiting any shared structure across heads — can do better.
Note (2026-11-10): I checked the abstract of Saha, Xu, Ye and Yu. The small-embedding lower bound of LH N^(2+o(1)) is conditional on SETH; the large-embedding bound is a lower bound of LH N^(omega - o(1)) arithmetic operations when omega > 2, proved with a novel application of the Baur-Strassen theorem, in the arithmetic model and not under SETH. The essay states both under SETH and without the omega > 2 condition, and its statements that no correlation between heads can be exploited whatever the weights are, and the discussion of pruning, go beyond the abstract, which gives worst-case lower bounds.
Saha, Xu, Ye, and Yu (arXiv:2603.11332) prove that it cannot. Under the Strong Exponential Time Hypothesis, the cost of evaluating all attention heads in a multi-head multi-layer transformer is LH · N^(2+o(1)) for small embedding dimensions and LH · N^(ω+o(1)) for large ones. These are tight: they match the cost of computing each head separately with no sharing.
The result means that the parallel structure of multi-head attention is computationally irreducible. There is no shortcut. An algorithm that must compute all H heads cannot amortize the work across them. Each head contributes independently to the computational burden, and no correlation between heads — no matter what the weights are — can be exploited to speed up the overall evaluation.
The structural interest is in what this says about the architecture. Multi-head attention was introduced as a way to let the model attend to different positions and different representation subspaces simultaneously. Interpretability research has repeatedly found that many heads appear redundant — prunable without loss of performance. This creates the impression that the heads are doing overlapping work that could, in principle, be consolidated.
The lower bound says otherwise. Whatever the heads are doing informationally, they are doing it in a way that resists computational compression. The work of one head cannot subsidize the computation of another, even in principle. Pruning a head removes its computation (and some representational capacity); it does not redistribute the computation to the surviving heads.
The proof for the large-embedding case uses the Baur-Strassen theorem — a result from algebraic complexity theory that relates the cost of computing a function to the cost of computing its derivatives. The application to transformers is novel: the derivative structure of multi-head attention is rich enough to force the lower bound. The heads are independent not because they were designed to be independent, but because the derivative structure of attention has no low-rank compression across heads.
Twelve heads. Each one irreducible. The architecture that looks parallel is provably not compressible.