\section{Preliminaries}\label{sec:prelim}

We write $\log$ for $\log_2$, $\ln$ for the natural logarithm, and $[n]=\{1,\dots,n\}$. For
$a,b\in\{0,1\}^D$ the inner product $\ip ab$ counts common ones; $a$ and $b$ are \emph{orthogonal} if
$\ip ab=0$.

\subsection{Attention and its parameters}\label{sec:attention}

\begin{definition}[Attention]\label[definition]{def:attention}
An \emph{attention instance} consists of queries $q_1,\dots,q_{n}\in\R^d$, keys $k_1,\dots,k_{n'}\in\R^d$
and values $v_1,\dots,v_{n'}\in[-1,1]^{d_v}$. The \emph{logits} are $\ell_{ij}=\ip{q_i}{k_j}$, the
\emph{attention weights} are $\pi_{ij}=e^{\ell_{ij}}/\sum_{j'}e^{\ell_{ij'}}$, and the \emph{output} of
query $i$ is $o_i=\sum_j\pi_{ij}v_j\in[-1,1]^{d_v}$. The \emph{spread} of row $i$ is
$\max_j\ell_{ij}-\min_j\ell_{ij}$, and the spread $\Spread$ of the instance is the largest spread of a
row.
\end{definition}

Matrix notation writes the output as $D^{-1}AV$ with $A=\exp(QK^\top)$ and $D=\mathrm{diag}(A\ind)$.
Every normalization used in the literature is a rescaling of the queries. Alman and Song~\cite{AS23} use
$A=\exp(QK^\top/d)$ with all entries of $Q,K$ in $[-B,B]$, so every logit lies in $[-B^2,B^2]$ and
$\Spread\le2B^2$. Gupta, Huang, Saha, Xu and Ye~\cite{GHSXY25} use $A=\exp(QK^\top)$ with entries in
$[-B,B]$, so $\Spread\le 2dB^2$. Transformers use $A=\exp(QK^\top/\sqrt d)$. We state all results for the
spread of the logits that enter the softmax. It does not depend on how a normalization is split between the
queries, the keys and a factor such as $1/d$, and it is invariant under adding a constant to all logits of a
row.

\begin{definition}[Approximate attention]\label[definition]{def:att}
$\ATT(n,d,\Spread,\eps)$ is the following problem. The input is an attention instance with $n$ queries,
$n$ keys, dimension $d$, $d_v\le d$ value coordinates, and spread at most $\Spread$. The goal is to
output vectors $\tilde o_i$ with $\|\tilde o_i-o_i\|_\infty\le\eps$ for all $i$. A randomized algorithm
solves it if it succeeds with probability at least $2/3$.
\end{definition}

An instance with fewer queries, or with dimension below $d$, is an instance of the larger size after padding:
zero queries add rows we ignore, and zero coordinates leave every logit unchanged. Inputs are rational
numbers of $O(\log(n/\eps))$ bits, and the algorithms of \cref{sec:threshold} use arithmetic operations on
numbers of this length, including the exponential function evaluated to relative precision $\eps/100$; the
polynomial method of \cref{sec:precision} uses exact rational arithmetic on numbers of $O(\log^2n)$ bits. The
following stability fact is used throughout.

\begin{restatable}[Logit perturbation]{lemma}{lemperturb}\label[lemma]{lem:perturb}
Let two instances share their values and have logits $\ell_{ij}$ and $\ell'_{ij}$ with
$|\ell_{ij}-\ell'_{ij}|\le\eta$ for all $j$ and a fixed row $i$. Then
$\|o_i-o'_i\|_\infty\le e^{2\eta}-1$.
\end{restatable}

\subsection{Hypotheses after the refutation}\label{sec:hyp}

\emph{Orthogonal Vectors} ($\OV_{n,D}$) asks whether two given lists $A$ and $B$ of $n$ vectors each in
$\{0,1\}^D$ contain an orthogonal pair. Repetitions are allowed, and the size of a list counts its entries; all
collections of vectors in this paper, such as the instances of \cref{fact:williams,fact:chen,lem:magap}, are lists in
this sense, and $a\in A$ ranges over the entries of $A$. Brute force takes time $O(n^2D)$. For $D=c\log n$ the best algorithm takes time
$n^{2-1/O(\log c)}$~\cite{AWY15,CW16}. All hypotheses below are about randomized algorithms with error
probability at most $1/3$.

\begin{hypothesis}[Low-dimensional OV hypothesis, LDOV]\label[hypothesis]{hyp:ldov}
For every $\gamma>0$ there is an integer $c\ge1$ such that $\OV_{n,\lceil c\log n\rceil}$ cannot be solved
in time $O(n^{2-\gamma})$.
\end{hypothesis}

\begin{hypothesis}[CNF-SETH]\label[hypothesis]{hyp:cnfseth}
For every $\gamma>0$ there is $c_0\ge1$ such that satisfiability of CNF formulas with $N$ variables and at
most $N^{c_0}$ clauses cannot be decided in time $O(2^{(1-\gamma)N})$.
\end{hypothesis}

\begin{hypothesis}[CNF-SETH with clause exponent $c_0$]\label[hypothesis]{hyp:cnfsethc}
For a constant $c_0\ge1$, the hypothesis $\mathrm{CNF\text{-}SETH}_{c_0}$ states that for every
$\gamma>0$, satisfiability of CNF formulas with $N$ variables and at most $N^{c_0}$ clauses cannot be
decided in time $O(2^{(1-\gamma)N})$.
\end{hypothesis}

$\mathrm{CNF\text{-}SETH}_{c_0}$ implies CNF-SETH, and it gets stronger as $c_0$ decreases. Williams'
reduction~\cite{Wil05} connects these hypotheses to $\OV$.

\begin{restatable}[Williams~\cite{Wil05}]{fact}{factwilliams}\label[fact]{fact:williams}
A CNF formula with $N$ variables, $N$ even, and $M$ clauses can be transformed in time
$2^{N/2}\poly(N,M)$ into an instance of $\OV_{n,M}$ with $n=2^{N/2}$ that has an orthogonal pair if and
only if the formula is satisfiable.
\end{restatable}

So CNF-SETH implies that for every $\gamma>0$ there is $c_0$ such that $\OV_{n,D}$ with
$D=\lceil(2\log n)^{c_0}\rceil$ has no $O(n^{2-\gamma})$ algorithm, and $\mathrm{CNF\text{-}SETH}_{c_0}$ gives
the same with one exponent $c_0$ for all $\gamma$. Before the refutation, SETH implied
\cref{hyp:ldov} through the sparsification lemma~\cite{IPZ01}, which reduces $k$-SAT to $k$-SAT with
linearly many clauses. This route is closed: CNF-SAT with $O(N)$ clauses of arbitrary width is solvable
in time $O(2^{\eps N})$ for every $\eps>0$~\cite[Proposition~6.1]{Li26}, so
$\mathrm{CNF\text{-}SETH}_1$ is false, and no hypothesis about satisfiability that is still open is known to
imply \cref{hyp:ldov}. $\mathrm{CNF\text{-}SETH}_{c_0}$ is open for every $c_0>1$. The same applies to the
$k$-party version: SETH implied that $k$-OV in dimension $c\log n$ needs time $n^{k-o(1)}$, while CNF-SETH,
by splitting the variables into $k$ parts, gives this in dimension $(\log n)^{O(1)}$.

\subsection{Imported theorems}\label{sec:imported}

Three results are used as black boxes. The first packages the distributed PCP of Abboud, Rubinstein and
Williams~\cite{ARW17}, made efficient by Rubinstein~\cite{Rub18} with algebraic-geometry codes, as stated by
Chen~\cite{Che18}. The \emph{Boolean Max-IP} problem asks for the largest inner product between a vector
of one list and a vector of another, each of $n$ vectors in $\{0,1\}^d$.

\begin{fact}[{\cite[Lemma~3.3 and its proof in Appendix~D]{Che18}}]\label[fact]{fact:chen}
For every integer $c\ge1$ and real $\eps\in(0,1]$ there is $n_0$ such that for all $n\ge n_0$ and every real
$\tau\in[4,n]$, an instance $(A,B)$ of $\OV_{n,\lceil c\log n\rceil}$ can be mapped to at most $2n^{\eps}$
instances $(A_\psi,B_\psi)$ of Boolean Max-IP, each with $n$ vectors per side in a dimension
$d_{\mathrm C}\le\tau^{\poly(c/\eps)}\log n$, and to an integer $T$ with $c\log n\le T\le d_{\mathrm C}$, such that:
\begin{enumerate}[label=(\roman*)]
\item every inner product between a vector of $A_\psi$ and a vector of $B_\psi$ lies in $[0,T]$;
\item if $(A,B)$ has an orthogonal pair, then some instance has a pair with inner product $T$;
\item otherwise every pair in every instance has inner product at most $T/\tau$;
\item the map works vector by vector: there are maps $x(\psi,\cdot)$ and $y$, which depend only on $n$, $c$,
$\eps$ and $\tau$, with $A_\psi=(x(\psi,a))_{a\in A}$ and $B_\psi=(y(b))_{b\in B}$, and for all
$a,b\in\{0,1\}^{\lceil c\log n\rceil}$, $\ip{x(\psi,a)}{y(b)}=T$ for some $\psi$ if $\ip ab=0$, and
$\ip{x(\psi,a)}{y(b)}\le T/\tau$ for all $\psi$ if $\ip ab\ge1$.
\end{enumerate}
The instances can be computed in time $n^{1+\eps}d_{\mathrm C}\poly(\log n)$.
\end{fact}

Items (i) and (iv), the integer $T$ and the running time are read off the proof. There, $T=2^r$ is the number
of random strings of an amplified protocol, and $\psi$ ranges over Merlin's proofs. The vector $y(b)$ has
exactly one coordinate equal to $1$ in each of the $T$ blocks indexed by the random strings, at Bob's message
for $b$, which depends only on $b$ and the random string~\cite[Definition~2.6]{Che18}; so $T\le d_{\mathrm C}$. The
coordinates of $x(\psi,a)$ record whether Alice, holding $a$ and the proof $\psi$, accepts a given message on a
given random string, so $\ip{x(\psi,a)}{y(b)}$ is the number of random strings on which Alice accepts, and (iv) is
the completeness and soundness of the protocol. Every coordinate is a predicate of the computationally efficient
protocol of~\cite{Rub18}. The base protocol is the unrepeated one inside Rubinstein's proof
of~\cite[Theorem~3.1]{Rub18}: with $s$ a constant depending on $c/\eps$, it uses $\log m+O(1)$ coins, has perfect
completeness and soundness at most $9/10$. An expander walk of length $O(\log\tau)$ brings the soundness to $1/\tau$
with $\log m+O(\log\tau)$ coins; Chen~\cite[Lemma~D.2]{Che18} carries this out from soundness $1/2$, and the hitting
property of expander walks gives the same from soundness $9/10$. Padding the protocol with $O(1)$ unused coins makes
$T\ge m$ and multiplies the dimension by a constant. This is why $T=O(\tau^{O(1)}\log n)$ and the dimension stays
$O(\log n)$ for constant $\tau$. Chen states the lemma for
every $\tau\ge2$ and applies it with $\tau$ a function of $n$~\cite[Corollary~3.4]{Che18}; in the construction,
$n_0$ comes only from the parameters of Rubinstein's protocol, which depend on $c$ and $\eps$ but not on $\tau$. For dimensions $D=\omega(\log n)$ we use the underlying protocol directly. In a
\emph{one-message MA protocol} for disjointness, Merlin sends a proof to Alice, Alice and Bob share uniformly
random coins, Bob sends one message to Alice, and Alice accepts or rejects.

\begin{fact}[{\cite[Theorem~3.1]{Rub18}}]\label[fact]{fact:rub}
There are absolute constants $a_1,a_2,a_3$ such that for all integers $m$ and $s\in[2,m]$ there is a
computationally efficient one-message MA protocol for disjointness of $X,Y\subseteq[m]$ in which
Merlin sends Alice at most $a_1(m/s)\log s$ bits, Alice and Bob share at most $a_2\log m$ uniform coins, and
Bob sends Alice at most $a_3s\log s$ bits that depend only on $Y$ and the coins. If
$X\cap Y=\emptyset$, some proof makes Alice accept for all coins. If $X\cap Y\ne\emptyset$, Alice
accepts with probability at most $1/2$ for every proof.
\end{fact}

The third result is Razborov's corruption bound for disjointness. Write $\DISJ_D(x,y)=1$ if
$x,y\in\{0,1\}^D$ are disjoint, that is, orthogonal.

\begin{fact}[Razborov~\cite{Raz92}]\label[fact]{fact:razborov}
There are absolute constants $\alpha_1,\eps_1>0$ and, for every $D\ge1$, a distribution $\mu$ on
$\{0,1\}^D\times\{0,1\}^D$ with $\mu(\DISJ_D^{-1}(1))=3/4$ such that every rectangle $X\times Y$
satisfies
$\mu\bigl((X\times Y)\cap\DISJ_D^{-1}(0)\bigr)\ge\alpha_1\,\mu\bigl((X\times Y)\cap\DISJ_D^{-1}(1)\bigr)-2^{-\eps_1 D}$.
\end{fact}

Razborov proves this for $D=4\ell-1$; for other $D$, place the distribution on the first $4\ell-1\ge D-4$
coordinates and decrease $\eps_1$, and for $D\le6$ take any distribution with the stated mass and a small
$\eps_1$. The direction matters: rectangles that are mostly disjoint must be small. The converse fails, since
$\{x\ni i\}\times\{y\ni i\}$ contains only intersecting pairs.