Attention Is More Than You Need: Spectral Redundancy in Multi-Head Routing

Recent direct-sum hardness results show that computing multi-head attention by evaluating each head independently is essentially optimal under standard complexity assumptions, but leave open whether the key-value sharing in modern MQA and GQA architectures can circumvent this barrier. We prove that it cannot: even one-layer MQA with a single shared key-value head requires one full quadratic routing computation per query head in the worst case. To quantify how far practice departs from this worst case, we develop a calibration-stacked spectral framework that measures the effective number of independent routing-message directions in a layer, carefully separating signed, stochastic, and softmax-realizable compression; we also prove tight error-compounding bounds and NP-hardness of the natural route-merging compiler problem. Empirically, across fourteen open-weight GQA checkpoints from four model families (0.6B-70B parameters), eight shared routes capture over 90% of the routing-message energy in every model, and larger models use a progressively smaller fraction of their theoretical routing capacity, revealing a substantial and widening gap between worst-case hardness and the redundancy present in deployed transformers.