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.
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.