\section{Introduction}\label{sec:intro}

Attention computes, for each of $n$ queries, an average of $n$ value vectors weighted by the softmax of
the query's inner products with $n$ keys. The standard algorithm takes time $\Theta(n^2d)$. Alman and
Song~\cite{AS23} found that whether one can do better depends on the size of the entries. With head
dimension $d=O(\log n)$ and entries bounded by $B$, attention can be approximated to precision $1/\poly(n)$ in
time $n^{1+o(1)}$ if $B=o(\sqrt{\log n})$, and it needs time $n^{2-o(1)}$ if $B=\Theta(\sqrt{\log n})$, assuming
the Strong Exponential Time Hypothesis (SETH). The threshold has been extended to the gradient used in
training~\cite{AS24grad}, to tensor attention~\cite{AS24tensor}, to large entries in head dimension
$2^{\Theta(\log^*n)}$~\cite{GHSXY25}, to every nontrivial constant precision~\cite{HAPTP26}, and to multi-head and
multi-layer transformers~\cite{SXYY26}, under SETH or hypotheses derived from it, and it underlies lower bounds
for many transformer variants (\cref{sec:ledger}).

In October 2026 two works refuted the Exponential Time Hypothesis~\cite{OAI26,Cla26}. For every constant $k$,
both count the satisfying assignments of a $k$-CNF on $N$ variables in time $2^{N/(\log N)^{1/2-o(1)}}$. SETH
implies ETH, so SETH is false, and the attention bounds lose the hypothesis they were proved from. The lower
bounds themselves are not contradicted: the new algorithms say nothing about Orthogonal Vectors ($\OV$), or its
$k$-party version, the problems these reductions start from. What the refutation removes is the derivation of
the bounds from satisfiability. SETH implied the hardness of $\OV$ in dimension $c\log n$ through the
sparsification lemma, and this route now starts from a false statement, since CNF-SAT with linearly many
clauses is subexponential~\cite[Proposition~6.1]{Li26}. The hardness of $\OV$ in dimension $c\log n$, the
low-dimensional $\OV$ hypothesis (LDOV), is now a hypothesis of its own. The form of SETH that survives,
CNF-SETH, gives through Williams' reduction the hardness of $\OV$ in dimension $(\log n)^{O(1)}$, and no reduction
to dimension $O(\log n)$ is known. The ledger of~\cite[Section~6]{Li26} records that the attention thresholds now
rest on LDOV. Within the same month, the 3SUM and APSP hypotheses were refuted as well~\cite{AVW26}.

This paper determines, under LDOV, the time exponent of attention at constant precision at every spread and in
every dimension between $\omega(\log n)$ and $n^{o(1)}$, and the hypotheses on which each part of the answer rests. The answer is sharper than the original
threshold, and it separates two readings of it that used to be the same.

\subsection{Results}\label{sec:results}

We measure an attention instance by its \emph{spread} $\Spread$: the largest difference between two logits
in the same row. The spread is the normalization-free form of the entry bound: in the normalization of
Alman and Song, $\Spread\le2B^2$. It also has a direct meaning. A row with spread $\Spread$ gives every key at
most $e^{\Spread}/n$ of its weight, so a single key can carry constant weight only when $\Spread\ge\ln n-O(1)$.
Precision is additive, and the values lie in $[-1,1]$.

\begin{headline}[The exponent at constant precision; \cref{cor:sampling,thm:ldovlb,rem:pm,thm:curve,cor:exponent}]\label{thm:A}
Fix a precision $\eps\in(0,1)$ and $\kappa>0$.
\begin{enumerate}[label=(\roman*)]
\item In every dimension $d\le n^{o(1)}$, time $n^{1+\min\{\kappa,1\}+o(1)}$ suffices for attention with spread $\kappa\ln n$:
uniform sampling of keys if $\kappa<1$, direct computation otherwise.
\item Under LDOV, for every $\gamma>0$ there is $C$ such that in dimension $C\log n$, attention with spread
$\kappa\ln n$ needs time $n^{1+\min\{\kappa,1\}-\gamma}$, already for values in $\{-1,1\}$, and for values in $\{0,1\}$ if
$\eps<1/2$.
\end{enumerate}
\end{headline}

So under LDOV, at constant precision and in every dimension between $\omega(\log n)$ and $n^{o(1)}$, the cost of
attention is $n\cdot e^{\Spread}$ up to factors $n^{o(1)}$ until it reaches $n^2$, and uniform sampling is optimal. The
transition to quadratic time sits at $\Spread=\ln n$, the spread at
which one key can first outweigh all others: for every $\theta>0$, spread $(1-\theta)\ln n$ takes time
$n^{2-\theta+o(1)}$, while under LDOV spread $(1+\theta)\ln n$ has no $O(n^{2-\gamma})$ algorithm for any $\gamma>0$,
already in dimension $C_{\gamma,\theta}\log n$ and at every nontrivial constant precision (\cref{thm:ldovlb,rem:pm}); in
dimension $(\log n)^{O(1)}$, spread $\ln n+O(1)$ suffices (\cref{cor:additive}). Alman and Song proved hardness at
precision $1/\poly(n)$, and Haverbeck, Amo Alonso, Posada-Moreno, Trimpe and Pavone~\cite{HAPTP26} at every
nontrivial constant precision, both with an unspecified constant $C'$ in $B=C'\sqrt{\log n}$.

\begin{headline}[Precision and dimension move the threshold; \cref{cor:parity,cor:precision}]\label{thm:B}
Assume LDOV, and let $\gamma\in(0,1)$.
\begin{enumerate}[label=(\roman*)]
\item In dimension $O_\gamma(\log n)$ and at precision $n^{-\beta}$, spread $\kappa\ln n$ can be handled in time
$O(n^{2-\gamma})$ for some $\kappa=\kappa_\gamma(\beta)>0$, while for every $\kappa>0$ it needs more once
$\beta\ge O_\gamma(\log(2+1/\kappa))$. Spread $1$, and even entries bounded by $2$ in the normalization
of~\cite{AS23} (\cref{rem:entries2}), need time $n^{2-\gamma}$ at precision $n^{-O_\gamma(\log\log n)}$.
\item For every $C'>0$, at precision $n^{-1-O_{\gamma,C'}(1/\log\log n)}$, spread $O_{\gamma,C'}(\log n/\log\log n)$ needs
time $n^{2-\gamma}$ in dimension $(\log n)^{1+C'}$, and for every $\delta\in(0,1/2]$, at precision $\Theta_{\gamma,\delta}(1/n)$,
spread $O_{\gamma,\delta}(1)$ needs it in dimension $O_{\gamma,\delta}(n^{\delta})$.
\end{enumerate}
\end{headline}

So the constant $\ln n$ belongs to constant precision. At polynomial precision the threshold is $\Theta(\log n)$
in dimension $O(\log n)$, with a constant that tends to zero as the precision grows, and, unlike at constant
precision, the dimension moves it further: in dimension $O(\log n)$ every spread $o(\log n)$ is easy at every
polynomial precision (\cref{thm:poly}), while under LDOV, in every dimension between $(\log n)^{1+\Omega(1)}$ and
$n^{o(1)}$ and at every precision $n^{-\beta}$ with $\beta>1$, spread $O(\log n/\log\log n)$ is hard (\cref{cor:parity}(b) and padding). The lower
bounds count orthogonal partners modulo $r+1$ through the integer $r^K\sum_b(1+1/r)^{F(a,b)}$, where $F(a,b)$ counts
the blocks of coordinates in which $a$ and $b$ intersect. This generalizes the parity argument of Gupta et
al.~\cite{GHSXY25}, and the blocks trade dimension for precision.

The next two results concern satisfiability. Both depend on the \emph{clause exponent}: CNF-SETH with
exponent $c_0$ asserts that CNF formulas with $N$ variables and $N^{c_0}$ clauses need time $2^{(1-\gamma)N}$ for
every $\gamma>0$. Exponent $1$ is refuted~\cite{Li26}, and every exponent $c_0>1$ is open.

\begin{headline}[What satisfiability supports; \cref{thm:cnfseth,thm:belowtwo,rem:pm}]\label{thm:C}
\leavevmode
\begin{enumerate}[label=(\roman*)]
\item Under CNF-SETH, for every $\gamma>0$, attention at precision $1/6$ needs time $n^{2-\gamma}$ in dimension
$d=(\log n)^{C_\gamma}$ with spread $d\ln(16n)$. This combines the exact embedding of~\cite[Lemma~5.6]{GHSXY25}
with Williams' reduction.
\item Under CNF-SETH with clause exponent $c_0<2$, for all $\gamma,\theta>0$ and every nontrivial constant precision,
attention with spread $(1+\theta)\ln n$ needs time $n^{2-\gamma}$ in dimension $n^{o(1)}$.
\end{enumerate}
\end{headline}

\begin{headline}[A barrier for the entry bound; \cref{thm:barrier,cor:barrier}]\label{thm:D}
Let a reduction map each vector of an $\OV$ instance in dimension $D$, for each of $2^p$ values of an index, to a
query or key vector, and separate orthogonal from non-orthogonal pairs by a gap $\Delta$ in the logits. Let $\sigma$
be the product of the largest Euclidean norms of the query vectors and of the key vectors; in the normalization
of~\cite{AS23} with entries bounded by $B$, $\sigma\le B^2$. Then $(\sigma/\Delta)^2\log(2+\sigma/\Delta)\ge\Omega(D/(p+1))$. In
particular, for $D=(\log n)^{c_0}$ with $c_0>1$, polynomial blowup and $\Delta=\Omega(\log n)$, such reductions need
$B\ge(\log n)^{(1+c_0)/4-o(1)}$.
\end{headline}

The proof turns such a reduction into a Merlin--Arthur protocol for disjointness, in which Merlin names the copy
and the players estimate the inner product from random-sign projections, and applies Klauck's lower
bound~\cite{Kla03}. Taken together, \cref{thm:C,thm:D} say that the two readings of the threshold come apart.
Measured by the spread, hardness at $(1+\theta)\ln n$ follows, in dimension $n^{o(1)}$, from a hypothesis about
satisfiability with clause exponent below $2$, and the construction behind it, which builds one gap instance for
each proof of a one-message Merlin--Arthur protocol for disjointness (\cref{lem:magap}), needs clause exponent below $2$
for every such protocol (\cref{rem:forced}). Measured by the entry bound, reductions of this kind with polynomial blowup and gap
$\Omega(\log n)$ cannot derive $B=\Theta(\sqrt{\log n})$ from $\OV$ in dimension $(\log n)^{1+\Omega(1)}$; for them, the
entry form of the threshold needs LDOV. \Cref{tab:summary} collects the picture.

\begin{table}[t]
\centering\small
\begin{tabular}{@{}L{3.0cm}L{4.4cm}L{6.7cm}@{}}
\toprule
Regime & Upper bound (unconditional) & Lower bound, for every $\gamma>0$ (time $n^{2-\gamma}$ unless noted)\\
\midrule
constant precision, $C\log n\le d\le n^{o(1)}$ & spread $\kappa\ln n$: time $n^{1+\min\{\kappa,1\}+o(1)}$
(\cref{cor:exponent}) & spread $\kappa\ln n$: time $n^{1+\min\{\kappa,1\}-\gamma}$, LDOV, $d=O(\log n)$
(\cref{cor:exponent}); spread $(1+\theta)\ln n$: LDOV, $d=O(\log n)$ (\cref{thm:ldovlb}), or CNF-SETH$_{c_0}$ with $c_0<2$,
$d=n^{o(1)}$ (\cref{thm:belowtwo}); spread $\ln n+O(1)$: LDOV, $d=(\log n)^{O(1)}$ (\cref{cor:additive}); spread
$d\ln(16n)$ at precision $1/6$: CNF-SETH, $d=(\log n)^{O(1)}$ (\cref{thm:cnfseth})\\
\addlinespace
precision $n^{-\beta}$, $d=O(\log n)$ & spread $\le\kappa\ln n$ with $\kappa=\kappa(C,\beta,\eta)$: $O(n^{1+\eta})$
operations on $O(\log^2n)$-bit rationals (\cref{thm:poly}) & spread $\kappa\ln n$ once $\beta\ge O(\log(2+1/\kappa))$: LDOV
(\cref{cor:precision})\\
\addlinespace
precision about $1/n$, $d\ge(\log n)^{1+\Omega(1)}$ & see the next row (\cref{prop:polyhigh}) & spread
$O(\log n/\log\log n)$ at precision $n^{-1-O(1/\log\log n)}$; spread $O(1)$ at $d=O(n^{\delta})$ and precision
$\Theta(1/n)$: LDOV (\cref{cor:parity})\\
\addlinespace
precision $n^{-\beta}$, $d=(\log n)^{C}$, $C>1$ & spread $\le(\log n)^{1-a}$ for $a\in(4(\beta+5)(C-1)/\eta,1]$:
$O(n^{1+\eta})$ operations (\cref{prop:polyhigh}) & spread $O(\log n/\log\log n)$ for $\beta>1$: LDOV (\cref{cor:parity});
the gap is \cref{prob:dimension}\\
\addlinespace
entry bound $B$, normalization of~\cite{AS23} & $B^2\le(1-\theta)\ln n/2$ at constant precision (\cref{cor:sampling},
since $\Spread\le2B^2$) &
$B^2=O(\log n)$: LDOV (\cref{rem:entries}). Barrier: gap embeddings from $\OV$ in dimension $(\log n)^{c_0}$, $c_0>1$,
with $p=O(\log n)$ and $\Delta=\Omega(\log n)$ need $B^2\ge(\log n)^{(1+c_0)/2-o(1)}$ (\cref{cor:barrier})\\
\bottomrule
\end{tabular}
\caption{Fast attention after the refutation of SETH. The spread is the largest difference of two logits in a
row; $\theta,\kappa,\eta,\delta,\beta,a>0$, $C$, $c_0$ and the exponent in $(\log n)^{1+\Omega(1)}$ are constants, and
the constants in the lower bounds depend on $\gamma$ and on them.}
\label{tab:summary}
\end{table}

\begin{figure}[t]
\centering
\begin{tikzpicture}[x=1.15cm,y=3.0cm]
  % hard region (orange), easy region (green), open band (gray)
  \fill[hard!25] (0,1) -- (3.5,1) .. controls (4.5,1) and (5,0.5) .. (6.5,0.3)
       .. controls (7.5,0.2) and (8.5,0.15) .. (9,0.14) -- (9,1.4) -- (0,1.4) -- cycle;
  \fill[easy!30] (0,0) -- (0,1) -- (1.5,0.08) .. controls (3,0.05) and (6,0.03) .. (9,0.02) -- (9,0) -- cycle;
  \fill[open!20] (0,1) -- (1.5,0.08) .. controls (3,0.05) and (6,0.03) .. (9,0.02) -- (9,0.14)
       .. controls (8.5,0.15) and (7.5,0.2) .. (6.5,0.3) .. controls (5,0.5) and (4.5,1) .. (3.5,1) -- cycle;
  % axes
  \draw[->] (0,0) -- (9.3,0) node[below left,font=\footnotesize] {higher precision $n^{-\beta}$ $\longrightarrow$};
  \draw[->] (0,0) -- (0,1.5) node[above,font=\footnotesize] {spread $W/\ln n$};
  \draw (0,1) -- (-0.08,1) node[left,font=\footnotesize] {$1$};
  \draw (0,0) node[below,font=\footnotesize] {constant};
  \draw (1.5,0) -- (1.5,-0.03) node[below,font=\footnotesize] {$n^{-1/2}$};
  \fill (0,1) circle (1.6pt);
  % labels
  \node[font=\footnotesize,align=center] at (0.55,0.3) {$n^{2-\Omega(1)}$};
  \node[font=\footnotesize,align=center] at (7.2,0.78) {$n^{2-\gamma}$ under LDOV\\[-1pt](\cref{thm:ldovlb,cor:precision})};
  \node[font=\footnotesize,text=black!70] at (6.9,0.15) {open};
  \draw[<-,thin] (0.06,1.03) -- (0.8,1.22) node[right,font=\footnotesize] {constant precision: sharp at $W=\ln n$ (\cref{thm:A})};
  \draw[<-,thin] (0.75,0.48) -- (2.1,0.55) node[right,font=\footnotesize] {sampling};
  \draw[<-,thin] (3.0,0.045) -- (3.4,0.3) node[above,font=\footnotesize] {polynomial method};
\end{tikzpicture}
\caption{Schematic phase diagram in dimension $O(\log n)$, not to scale; the dimension constant depends on
$\gamma$, and at constant precision also on $\theta$. At constant precision the easy and hard regions meet at spread
$\ln n$, and below it the exponent is $1+W/\ln n$ (\cref{cor:exponent}). At precision $n^{-\beta}$ and spread
$(1-2\beta-\xi)\ln n$, for a constant $\xi>0$, sampling takes time $n^{2-\xi+o(1)}$; beyond $\beta=1/2$ the polynomial
method takes over. At precision
$n^{-\beta}$ both boundaries are $\Theta_\beta(\ln n)$ and tend to $0$ as $\beta$ grows. Under CNF-SETH alone we prove
hardness at spread $d\ln(16n)$ in dimension $d=(\log n)^{O(1)}$ (\cref{thm:cnfseth}).}
\label{fig:phase}
\end{figure}

\subsection{What is new}\label{sec:new}

The ledger of~\cite[Section~6, group~(6)]{Li26} states two facts: the quadratic attention bounds rest on LDOV
after the refutation, and bounds proved for every $d=\omega(\log n)$ hold under CNF-SETH in dimension
$\polylog n$. This paper turns the first statement into a characterization: at constant precision the exponent is
determined at every spread and in every dimension between $\omega(\log n)$ and $n^{o(1)}$, and the constant $\ln n$ of
the threshold is exact (\cref{thm:A}). It makes the second explicit for attention (\cref{thm:C}(i)); under the
stronger hypothesis of clause exponent below $2$ it obtains the lower bound at spread $(1+\theta)\ln n$ in dimension
$n^{o(1)}$ (\cref{thm:C}(ii)), and it shows that its construction, one gap instance for each proof of a
Merlin--Arthur protocol, needs clause exponent below $2$ for every such protocol (\cref{rem:forced}). The dependence on precision and dimension (\cref{thm:B}) and the barrier
(\cref{thm:D}) are new. Relative to the attention literature, \cref{thm:A} locates the threshold exactly in the
spread, at $(1\pm\theta)\ln n$, and gives the exponent below it, where~\cite{AS23,HAPTP26} give hardness at
$B=C'\sqrt{\log n}$ with $C'$ unspecified; in the entry form the constant remains open (\cref{sec:ldov-lb}).
\Cref{thm:B} shows why the threshold of~\cite{AS23} has no single constant at polynomial precision, and that
dimension, which does not affect the exponent at constant precision between $C\log n$ and $n^{o(1)}$, matters there.
\Cref{sec:ledger} maps the conditional lower bounds for attention in the literature, most of them SETH-based, to
the hypotheses that now support them; two families turn out to rest on refuted hypotheses, one of them in part of
its parameter range.

The upper bounds are uniform sampling and the polynomial method of~\cite{AS23}. The lower bounds use the
distributed PCP of Abboud, Rubinstein and Williams~\cite{ARW17} in the efficient form of
Rubinstein~\cite{Rub18}, as packaged by Chen~\cite{Che18}, the counting argument of~\cite{GHSXY25} in a general base
and over blocks, and Williams' reduction~\cite{Wil05}. The barrier uses random-sign projections, Klauck's
rectangle argument~\cite{Kla03} and Razborov's corruption bound~\cite{Raz92}.

\paragraph{Organization.}
\Cref{sec:prelim} defines the problem and states the hypotheses and imported theorems.
\Cref{sec:threshold,sec:precision,sec:sat} prove \cref{thm:A,thm:B}, and \cref{thm:C,thm:D}, with full proofs
in \cref{app:threshold,app:precision,app:sat}, written as structured proofs in the style of Lamport~\cite{Lam95,Lam12}.
\Cref{app:roadmap} is a roadmap of these proofs, and \cref{fig:dependency} there shows how the results depend on each other.
The subsections of the appendices follow those of the body: \cref{app:curve}, for example, holds the proofs for
\cref{sec:curve}.
\Cref{sec:ledger} is the ledger, and \cref{sec:outlook} discusses related work and open problems.

\paragraph{AI disclosure.}
This paper was written with Claude Opus~5.5 (Anthropic), working as an agent in Claude Code. The author
posed the question and directed the presentation. Claude chose the results, proved them, wrote the text and drew the figures.
Separate Claude agents searched the literature, audited the proofs and reviewed the paper as referees, and
the paper was revised to address their findings. At the author's request, ChatGPT (OpenAI) then reviewed the
proofs and the tables of prior results and found no fatal or major problems; Claude checked each of its minor
findings against the proofs and the cited sources, and corrected the text without changing any proof. The gadgets, the counting identities and the reductions
for the precision bounds were tested on small random instances, the identities in exact arithmetic. The author
is responsible for the content.