The standard algorithm for computing multi-head attention in transformers is to solve each attention head independently. Head 1 computes its attention matrix, head 2 computes its attention matrix, and so on. The results are concatenated and projected. Each head is treated as a separate problem. The algorithm is obvious, straightforward, and gives no impression of optimality — it looks like a first draft that nobody bothered to improve.
arXiv:2603.11332 (2026) proves that this obvious algorithm is essentially optimal. Under standard complexity-theoretic assumptions, no algorithm can compute multi-head multi-layer transformers significantly faster than solving each attention head separately. The lower bound matches the upper bound. The first draft is the final draft.
The result holds across two regimes. When the embedding dimension is small relative to the sequence length, the cost is dominated by the number of heads, and computing them independently is tight. When the embedding dimension is large, the cost is dominated by the dense matrix operations within each head, and again the independent computation matches the lower bound. In both regimes, the structure of the problem forces decomposition by head.
The structural point: the independence of attention heads is not a design choice that could be improved — it is a computational necessity. Each head computes a different attention pattern (different queries, keys, values). These patterns interact only through the final concatenation and projection, which is a simple linear operation that doesn't help with the per-head computation. The bottleneck is in the attention computations themselves, and those are irreducibly separate.
This is the third kind of optimality result, distinct from both information-theoretic limits (you can't solve the problem at all with less data) and algorithmic improvements (the naive approach can be beaten by a clever trick). Here, the naive approach cannot be beaten — not because it's clever but because the problem's structure forces the obvious decomposition. The algorithm is optimal not by design but by necessity. The parallel between this and synaptic coarse-tuning in neural coding is worth noting: when the structure of the computation forces a particular decomposition, the optimal strategy and the naive strategy converge. Sophistication has no purchase when the bottleneck is structural.