Five Invariants Govern Attention Expressivity: A Completeness Theorem

Dozens of impossibility and separation theorems now record what one attention variant can do and another cannot, each proved on its own terms. We ask whether they share a structure, and prove that on the canonical tasks they do. We identify five structural invariants of a single-head attention architecture, namely kernel-rank, piecewise-degree, boundedness, symmetry, and recurrent-state, and prove a completeness theorem about them. Each invariant is an obstruction on its own class of tasks. On the associative-recall, averaging, counting, and indexing tasks the five are also jointly sufficient. For the realization regimes covered by the theorem, every cost gap beyond polylogarithmic factors on these tasks has an invariant witness. Under a matrix-dimension cost measure, budgeted invariant profiles determine each canonical task's cost up to polylogarithmic factors. We tabulate that cost for softmax, hard, average-hard, polynomial, sigmoid, causal, and position-free attention, as well as state-space architectures, on every canonical task. Two consequences stand out. Single-layer linear attention needs width at least $N$ on associative recall over $N$ keys, at any head count, against $O(\log N)$ for softmax. The single-layer polynomial kernels form a strict hierarchy in the degree.