An I/O Lower Bound for Exact Attention

Every bounded deterministic real-arithmetic program that computes exact softmax attention on Q, K, V ∈ ℝn×d requires Ω(nd + n2/M) transfers between slow memory and an M-word cache, for n ≥ d2, d ≥ 2, and M ≥ d2. The allowed operations are +, −, ×, ÷, exp; recomputation and finite branching are permitted. No pairwise intermediate value is prescribed. The proof adjoins the entries of each epoch’s local Jacobian to a field that retains all earlier such entries. An epoch contributes at most 4M2 generators, whereas the output derivatives determine n(n − 1) algebraically independent kernel ratios. The bound is tight for each fixed d. We also show why field containment does not recover the uniform dependence on d. For powers of two d ≥ 8 dividing n, a Strassen-based prefix reaches the entire attention coefficient field after O(ndσ−1 + n2dσ−2/M) transfers, where σ = log2 7. This prefix can occur in a correct O(n2d)-work program, yet on a parameter sequence it costs o(nd + n2d/M). It computes an auxiliary vector, not attention. A separate numerical compression theorem gives Ω(nd + n2d2/M) when the epochs recover all pair scores or kernels; that recovery hypothesis is not part of the unrestricted lower bound.