\section{Related work and open problems}\label{sec:outlook}

\paragraph{Fine-grained complexity of attention.}
Keles, Wijewardena and Hegde~\cite{KWH23} gave the first SETH-based quadratic lower bounds for
self-attention, for $d=\omega(\log n)$. Alman and Song~\cite{AS23} found the bounded-entry threshold and the
polynomial-method algorithm, building on the Gaussian kernel density bounds of Aggarwal and
Alman~\cite{AA22} and the linear algebra on geometric graphs of Alman, Chu, Schild and Song~\cite{ACSS20}. The
threshold was extended to gradients~\cite{AS24grad} and to tensor attention~\cite{AS24tensor}. Gupta, Huang,
Saha, Xu and Ye~\cite{GHSXY25} gave an $\tilde O(n^{2-1/d}\polylog(B/\eps))$ algorithm for constant $d$ and showed
hardness for $d=2^{\Theta(\log^*n)}$ with large entries, through Chen's dimensionality
reduction~\cite{Che18}. Haverbeck et al.~\cite{HAPTP26} extended the bounded-entry lower bound to every nontrivial
constant precision, to algorithms that preprocess the KV cache, and to finding the keys that carry most of the
weight. Alman and Yu~\cite{AY25} proved lower bounds for subquadratic alternatives to attention, Chakrabarti,
Pitassi and Alman~\cite{CPA26} for higher-order attention, and Saha, Xu, Ye and Yu~\cite{SXYY26} for
multi-head and multi-layer transformers. Most of these lower bounds are stated under SETH; \cref{sec:ledger}
records the hypothesis of each and its current basis. Sampling-based approximations, such as
KDEformer~\cite{ZHDK23} and HyperAttention~\cite{HJKMWZ24}, come with guarantees in terms of column norms of the
attention matrix and stable ranks; \cref{thm:sampling} is the simplest guarantee of this kind, and under LDOV,
\cref{cor:exponent} shows that its exponent is optimal in terms of the spread. Hashing-based estimators beat uniform
sampling for Gaussian kernel density estimation to relative precision $\eps$. Let $\mu=\frac1n\sum_je^{-a\|q-k_j\|^2}$ be
the density at the query. Uniform sampling needs $O(\mu^{-1}\eps^{-2})$ samples per query. The query time
of~\cite{CS17} is $\mu^{-1/2}\eps^{-2}$ times a factor that grows with the diameter of the data, and that
of~\cite{CKNS20} is $\mu^{-0.173-o(1)}\eps^{-2}$ for $\mu=n^{-\Theta(1)}$ and $\eps\ge1/\polylog n$. This
density changes under transformations that leave attention unchanged: appending to every key a coordinate that
brings all keys to a common norm $R$, and a zero coordinate to every query, keeps every logit, makes the softmax
weights proportional to $e^{-\|q-k_j\|^2/2}$, and drives $\mu$ to $0$ as $R$ grows. So guarantees in terms of $\mu$ give
no bound in terms of the spread, and in terms of the spread uniform sampling cannot be improved by a polynomial
factor under LDOV.

\paragraph{Hardness of approximation in P.}
The gap instances behind \cref{thm:ldovlb} come from the distributed PCP framework of Abboud, Rubinstein and
Williams~\cite{ARW17}, made efficient by Rubinstein~\cite{Rub18} with algebraic-geometry codes; Chen~\cite{Che18}
characterized the approximability of Max-IP and connected exact Max-IP to NP$\cdot$UPP protocols, and Chen and
Williams~\cite{CW19} showed that many approximate problems in dimension $O(\log n)$ are equivalent to
$\OV$. These works turn communication protocols into reductions. \Cref{thm:barrier} goes the other way, from
reductions to protocols, and uses the lower bound of Klauck~\cite{Kla03} to limit what gap embeddings can
achieve. The non-reducibility results of Carmosino et al.~\cite{CGIMPS16} assume NSETH, which implies SETH and is
therefore false. \Cref{thm:barrier} is unconditional and covers every gap embedding, including the reduction
of~\cite{AS23} and those of \cref{thm:ldovlb,thm:curve,thm:cnfseth,thm:belowtwo}.

\paragraph{After the refutation.}
The ledger of~\cite[Section~6]{Li26} sorts the conditional lower bounds of learning theory by the
hypothesis that survives; this paper carries out the attention row of that ledger. Alman and Vassilevska
Williams~\cite{AVW26} refuted the 3SUM and APSP hypotheses in the same month, so bounds based on them need new
bases too. LDOV and $\mathrm{CNF\text{-}SETH}_{c_0}$ have different support. No open hypothesis about satisfiability is
known to imply LDOV; what supports it is the lack of algorithms, since the best algorithm for $\OV$ in dimension $c\log n$
takes time $n^{2-1/O(\log c)}$~\cite{AWY15,CW16}, and the equivalence of many approximate problems in dimension
$O(\log n)$ with $\OV$~\cite{CW19}, which makes LDOV the common basis of all of them. $\mathrm{CNF\text{-}SETH}_{c_0}$ for
$c_0\in(1,2)$ is a statement about satisfiability, and the algorithms that refuted ETH do not reach it
(\cref{sec:below-two}).

\paragraph{Open problems.}

\begin{problem}[Dimension at polynomial precision]\label[problem]{prob:dimension}
In dimension $(\log n)^C$ with $C>1$ and at precision $n^{-\beta}$ with $\beta>1$, \cref{cor:parity}(b) gives hardness at
spread $O(\log n/\log\log n)$ under LDOV, while \cref{prop:polyhigh} handles spread $(\log n)^{1-a}$ with $O(n^{1+\eta})$
operations only for $a\in(4(\beta+5)(C-1)/\eta,1]$, and nothing for $C\ge1+\eta/(4(\beta+5))$. Where is the threshold? And at precision
$n^{-1+\delta}$, coarser than the $1/n$ that counting needs, does dimension still move it?
\end{problem}

\begin{problem}[The clause exponent]\label[problem]{prob:clause}
Is $\mathrm{CNF\text{-}SETH}_{c_0}$ plausible for some $c_0\in(1,2)$? An algorithm for CNF-SAT with $N^{1+\delta}$
clauses in time $2^{(1-\Omega(1))N}$ for every $\delta>0$ would refute the hypothesis of \cref{thm:belowtwo} for every
$c_0<2$, and the threshold would again rest on LDOV alone; hardness would make it a consequence of
satisfiability.
\end{problem}

\begin{problem}[Spread-efficient embeddings]\label[problem]{prob:spread}
\Cref{thm:barrier} bounds the scale of gap embeddings, not their spread. Is there a gap embedding of
$\OV_{n,D}$ with $D=(2\log n)^2$, at most $n^{o(1)}$ copies and dimension $(\log n)^{O(1)}$, in which all logits of a
query lie within $(1+o(1))\Delta$ of each other? Such an embedding would give hardness at spread $(1+o(1))\ln n$ from
$\mathrm{CNF\text{-}SETH}_2$ in polylogarithmic dimension. By \cref{rem:forced} it cannot come from the
construction of \cref{lem:magap}. Without copies it would be a low-rank approximation of the disjointness matrix;
with copies, a Merlin--Arthur analogue of approximate rank is needed.
\end{problem}

\begin{problem}[Lower-order terms and small dimension]\label[problem]{prob:band}
Under LDOV, at constant precision the exponent at spread $\kappa\ln n$ is $1+\min\{\kappa,1\}$ (\cref{cor:exponent}), but
the lower bound loses a factor $n^{\gamma}$ and needs dimension $C\log n$ with $C\to\infty$ as $\gamma\to0$. Is the cost
$n\,e^{\Spread}(\log n)^{O(1)}$ for every $\Spread\le\ln n$? And what is the exponent in dimension $C\log n$ for a fixed $C$,
where \cref{thm:ldovlb} gives hardness only at spread $(1+C^{-\Omega_\gamma(1)})\ln n$?
\end{problem}

\begin{problem}[Gradients]\label[problem]{prob:gradient}
Does the gradient of the attention loss have the same constant-precision threshold $\ln n$? The reduction
of~\cite{AS24grad} reads the attention output through the squared Frobenius norm of the whole output matrix, a
sum over all rows, so the outputs of a NO instance must be $O(n^{-1/2})$, which raises the spread needed by the
gadget of \cref{thm:ldovlb}.
\end{problem}