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 ≥ 2, 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. Theorem 5.5 proves the full Ω(nd + n2d2/M) bound under the restriction that each exponential argument is a polynomial in the full dot-product scores, even if no individual score is formed. A second-derivative argument bounds the dimension of arbitrary linear score mixtures recoverable from numerical summaries. Version note: v3 adds Theorem 5.5: the full Ω(nd + n2d2/M) lower bound for programs whose exponential arguments are polynomials in the full dot-product scores.