An I/O Lower Bound for Exact Attention

Abstract

Every bounded deterministic real-arithmetic program that computes exact softmax attention on Q, K, V ∈ ℝ^{n×d} requires Ω(nd + n²/M) transfers between slow memory and an M-word cache, for n ≥ 2, d ≥ 2, and M ≥ d². 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 4M² 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} + n²d^{σ−2}/M) transfers, where σ = log₂ 7. This prefix can occur in a correct O(n²d)-work program, yet on a parameter sequence it costs o(nd + n²d/M). It computes an auxiliary vector, not attention. We also prove the full Ω(nd + n²d²/M) bound when 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.