Exact Softmax Attention Has the Rectangular Matrix-Multiplication Exponent in Extended Arithmetic Circuits

Standard softmax attention explicitly forms all query–key scores, even when each query produces only a single scalar output. This raises a fundamental question: can exact attention avoid the arithmetic complexity of the underlying rectangular matrix multiplication? We show that it cannot. For $N$ queries and keys of width $d=\lceil N^a\rceil$, with fixed $0<a\le 1$, the minimum size of an exact-real circuit with $+,-,\times ,/,\exp ,\ln$ gates is $N^{\omega (1,a,1)+o(1)}$, even with only one scalar value per key. This matches standard exact evaluation and closes the previous single-head gap between $\omega (1,a,a)$ and $\omega (1,a,1)$. Our main technical contribution is an exp–log span theorem showing that, modulo additive constants, all within-row score differences lie in the $\mathbb{Q}$-linear span of the circuit's exponential inputs and logarithm outputs. Combined with mixed-coefficient extraction, this recovers the rectangular matrix-multiplication tensor and yields the lower bound. The same theorem also exactly characterizes transcendental complexity, giving $n(m-1)$ exp/log gates for dense independently parameterized attention.