cs.CC — Computational Complexity

Fast Attention after SETH: The Exact Exponent and the Hypotheses Behind It

Contributed by Xiaoyu Li

Alman and Song showed that attention with head dimension $O(\log n)$ can be approximated in almost linear time when the entries are $o(\sqrt{\log n})$, and needs quadratic time at $\Theta(\sqrt{\log n})$ under the Strong Exponential Time Hypothesis. In October 2026 the Exponential Time Hypothesis was refuted, and with it SETH. The quadratic lower bound now rests on the hardness of Orthogonal Vectors in dimension $c\log n$ (LDOV), which no open hypothesis about satisfiability is known to imply. We measure an instance by its spread $W$, the largest gap between two logits of a row. At every nontrivial constant precision and in every dimension between $\omega(\log n)$ and $n^{o(1)}$, we show that under LDOV the time exponent of attention is exactly $1+\min\{W/\ln n,1\}$: uniform sampling of keys is optimal, the cost is $\min\{n\,e^{W},n^2\}$ up to factors $n^{o(1)}$, and the transition to quadratic time sits at $W=\ln n$, the spread at which one key can outweigh all others. At polynomial precision and in dimension $O(\log n)$ the threshold becomes $\Theta(\log n)$, with a constant that tends to zero as the precision grows, and the dimension moves it: at precision $n^{-1-O(1/\log\log n)}$, spread $O(\log n/\log\log n)$ is hard in dimension $(\log n)^{1+\Omega(1)}$ but easy in dimension $O(\log n)$. From satisfiability we obtain hardness at spread $(1+\theta)\ln n$ in dimension $n^{o(1)}$, provided the hard CNF formulas have $N^{c_0}$ clauses for some $c_0<2$, and we show that the construction behind this bound, which builds one instance for each proof of a Merlin–Arthur protocol for disjointness, needs $c_0<2$ for every such protocol. For the entry bound, every reduction that embeds Orthogonal Vectors vector by vector, with polynomial blowup and logit gap $\Omega(\log n)$, yields a Merlin–Arthur protocol for disjointness; by Klauck's lower bound, such reductions cannot derive $B=\Theta(\sqrt{\log n})$ from Orthogonal Vectors in dimension $(\log n)^{1+\Omega(1)}$. We also map the conditional lower bounds for attention in the literature to the hypotheses that now support them, and find two families whose hypotheses are false, one of them in part of its parameter range.