\section{Which attention lower bounds survive}\label{sec:ledger}

Every SETH-based lower bound in \cref{tab:ledger,tab:ledger2} reduces from $\OV$, from $k$-OV, or from a gap
problem built on them. Its basis after the refutation is determined by the dimension the reduction needs
and by whether it needs a gap. Three cases cover every reduction from $\OV$ or $k$-OV in the tables.
\begin{enumerate}[label=(\Alph*)]
\item \emph{Reductions that need $\OV$ in dimension $\Theta(\log n)$.} Reductions through Rubinstein's approximate
nearest neighbor~\cite{Rub18}, the distributed PCP of~\cite{ARW17}, or Chen's dimensionality
reduction~\cite{Che18} must enumerate Merlin's proofs or Chen's residues, and stay subquadratic only from $\OV$
in dimension $c\log n$; the counting reduction of~\cite[Theorem~5.7]{GHSXY25} needs precision $2^{-\Theta(d)}$; and
some reductions, such as that of~\cite[Theorem~4.7]{SXY26}, start from $\OV$ in dimension $c\log n$ directly.
They now rest on LDOV alone.
\item \emph{The same for $k$ parties.} They rest on low-dimensional $k$-OV, which implies LDOV and which no open
hypothesis about satisfiability is known to imply.
\item \emph{Exact embeddings.} Reductions from exact $\OV$ or $k$-OV that preserve the dimension up to a
polynomial factor survive under CNF-SETH, in dimension $(\log n)^{O(1)}$ and with whatever precision the
embedding needs there (\cref{thm:cnfseth}).
\end{enumerate}
Groups (D) and (E) of \cref{tab:ledger2} collect the bounds based on other hypotheses. The statements in the
second column are as published, under SETH unless noted; the precision is additive unless noted, and $B$ is
the entry bound in the normalization used by each paper.

\begin{table}[p]
\centering\footnotesize
\begin{tabular}{@{}L{3.6cm}L{4.9cm}L{6.1cm}@{}}
\toprule
Result & Published statement & Route and status after the refutation\\
\midrule
\multicolumn{3}{@{}l}{\emph{(A) $\OV$ in dimension $\Theta(\log n)$: LDOV only}}\\
\cite[Thm.~4.6]{AS23} & attention, $d=C\log n$, $B=C_B\sqrt{\log n}$, precision $n^{-C_a}$ & Rubinstein's gap ANN; LDOV.
Constant precision and the exact constant in the spread: \cref{thm:ldovlb,cor:exponent}\\
\cite[Thm.~5.5]{AS24grad}, \cite[Thm.~5.1]{HSKSL25} & gradient, and LoRA gradients, $d=O(\log n)$,
$B=O(\sqrt{\log n}\,g(n))$ for any $g(n)=\omega(1)$ with $g(n)=o(\log n)$, precision $O(\log^{-4}n)$ & reduce from
the instance of \cite[Lemma~4.7]{AS23}, the LoRA bound through~\cite{AS24grad}; LDOV\\
\cite[Thms.~3.7, 4.1, 5.1]{HAPTP26} & every nontrivial constant precision; with KV-cache preprocessing; finding heavy keys;
$d=C\log n$, $B=C\sqrt{\log n}$ & Rubinstein's gap closest pair; LDOV\\
\cite[Thm.~5.4]{GHSXY25} & $d=2^{\Theta(\log^*n)}$, $B=\poly(n)$, constant precision & Chen's dimensionality reduction,
which needs $n^{o(1)}$ instances and hence $\OV$ in dimension $c\log n$; LDOV\\
\cite[Thm.~5.7]{GHSXY25} & $d=C\log n$, $B=\ln2$, precision $n^{-C}$ & parity of $\sum_b2^{\ip ab}$; LDOV. In dimension
$(\log n)^C$ the same argument needs precision $2^{-\Theta((\log n)^C)}$; \cref{thm:parity} generalizes it\\
\cite[Thms.~1.2, 1.3]{AY25} & most similar documents: monochromatic with $\ell=n^{c/\log\log n}$, bichromatic with
$\ell=c\log n$ & additive approximate Max-IP~\cite{Che18}; LDOV\\
\cite[Thms.~1.6, 1.8]{AG24} & Gaussian and Student KDE in dimension $o(\log n)$ & Chen's dimensionality reduction; LDOV\\
\cite[Prop.~1.8]{AA22} & batch Gaussian KDE, dimension $\alpha\log n$, error $n^{-\beta}$, squared diameter $O(\log n)$ &
approximate Hamming nearest neighbor~\cite{Rub18}; LDOV\\
\cite[Cors.~5.28, 5.30, Prop.~5.31, Thms.~8.2, 8.6]{ACSS20} & kernel matrix--vector products, sparsification and
Laplacian solving in dimension $c^{\log^*n}$ & Chen's dimensionality reduction; LDOV\\
\cite[Thm.~2.1]{HLSL24}, \cite[Thm.~3.1]{HWGLSL25}, \cite[Prop.~4.1]{HWSL24},
\cite[Thm.~4.5]{KLLSSS25}, \cite[Thm.~1.4]{AS25rope}, \cite[Thm.~6.1]{CHLSS24} & modern Hopfield
models, prompt tuning, diffusion transformers, visual autoregressive models, RoPE attention and its training, at
$d=O(\log n)$ and $B=\Theta(\sqrt{\log n})$ ($B=\omega(\sqrt{\log n})$ in~\cite{CHLSS24}) & special cases of \cite{AS23}
or \cite{AS24grad}, or Rubinstein directly; LDOV\\
\cite[Thm.~3.3]{SSWZ23} & low-rank approximation of $f(UV)$ & approximate Max-IP of~\cite{CW19}; LDOV\\
\cite[Thm.~4.7]{SXY26} & integer $\OV$ with $O(\log n)$-bit entries in every constructible dimension $D(n)=\omega(1)$,
that is, $D(n)$ computable in time $n^{o(1)}$ & from $\OV$ in dimension $c\log n$; LDOV\\
\addlinespace
\multicolumn{3}{@{}l}{\emph{(B) Low-dimensional $k$-OV only}}\\
\cite[Thm.~B.2]{AS24tensor} & tensor attention, $n^{3-o(1)}$, $d=C\log n$, $B=\Theta((\log n)^{1/3})$ & three-party gap
Max-IP; low-dimensional $3$-OV\\
\cite[Thm.~5.3]{CLSS24} & tensor attention gradients & from~\cite{AS24tensor}; low-dimensional $3$-OV\\
\cite[Thm.~E.3(1)]{CPA26} & poly-attention of degree $k$, $n^{k-o(1)}$, $B=\Omega((\log n)^{1/k})$ & gap $k$-IP in dimension
$c\log n$; low-dimensional $k$-OV\\
\bottomrule
\end{tabular}
\caption{SETH-based lower bounds for attention and related kernels that need low-dimensional $\OV$ or $k$-OV, and
their basis after October 2026.}
\label{tab:ledger}
\end{table}

\begin{table}[p]
\centering\footnotesize
\begin{tabular}{@{}L{3.6cm}L{4.9cm}L{6.1cm}@{}}
\toprule
Result & Published statement & Route and status after the refutation\\
\midrule
\multicolumn{3}{@{}l}{\emph{(C) Exact embeddings: CNF-SETH in dimension $(\log n)^{O(1)}$}}\\
\cite[Section~4 and appendix]{KWH23} & self-attention, $d=\omega(\log n)$, exact, multiplicative or additive error &
exact $\OV$, dimension $\Theta(d)$; under CNF-SETH at $d=(\log n)^C$. The additive versions need precision
$e^{-\Theta(d\log n+d^2)}$\\
\cite[Lemmas~5.1, 5.6]{GHSXY25} & $\OV$ in dimension $d$ reduces to attention with $B=O(\sqrt{\log n})$, constant precision &
exact $\OV$; under CNF-SETH at $d=(\log n)^C$ (\cref{thm:cnfseth})\\
\cite[Thms.~3.1, 3.4]{SXYY26} & with $L,H=\poly(N)$, computing $L$ layers of $H$ heads to additive error $1/(10N)$ needs
time $LHN^{2-o(1)}$ (Thm.~3.1); a transformer with linear-time embedding and MLP maps that computes $3$-OV needs
$LHm=N^{1-o(1)}$ (Thm.~3.4); $m=\Theta(\log N)$, under the $3$-OV hypothesis & exact unbalanced $3$-OV, $m=2d+2$; under
CNF-SETH at $m=(\log N)^C$\\
\cite[Thm.~1.1]{AY25} & least similar documents, $\ell=c\log n$ & exact $\OV$; under CNF-SETH at $\ell=(\log n)^C$\\
\cite[Thms.~3.2, 3.3]{AG24} & KDE for a kernel $f$ in dimension $m>C\log n$ at precision $(3n\tau(M))^{-1}$, where
$\tau(M)=\|M^{-1}\|_{\infty\to\infty}$ for the $m\times m$ counting matrix $M$ of $f$ & exact closest pair; under CNF-SETH
at $m=(\log n)^C$, at the same precision\\
\cite[Thms.~3.1, 3.2, 4.3]{SSWZ23} & low-rank approximation of $f(UV)$ (Thms.~3.1, 3.2) and computing $f(UV)z$
(Thm.~4.3) & exact $\OV$; under CNF-SETH at $r=(\log n)^C$\\
\cite[Thms.~4, 6, 8]{BIS17} & kernel SVM, kernel ridge regression and kernel PCA with the Gaussian kernel,
$d=\omega(\log n)$, multiplicative error $1+\exp(-\omega(\log^2n))$; additive error $\exp(-\omega(\log^2n))$ in the proofs of
the full version & exact bichromatic Hamming closest pair, to which $\OV$ reduces in
the same dimension~\cite[Thm.~1.4]{AW15}; under CNF-SETH at $d=(\log n)^C$, with additive error $e^{-\Omega(d\log n)}$\\
\cite[Thms.~5.14, 5.15]{ACSS20} & kernel matrix--vector products for $f(\|x-y\|^2)$ in dimension $d$ on $1.01^d$ points,
error $(\kappa(d+1))^{O(d^4)}$ & exact bichromatic Hamming nearest neighbors (Lemma~5.25); under CNF-SETH at
$d=(\log n)^C$\\
\addlinespace
\multicolumn{3}{@{}l}{\emph{(D) Refuted bases}}\\
\cite[Lemmas~1.4, 5.5, 5.9]{vBSZ24} & dynamic attention, hinted matrix--vector conjecture & refuted by~\cite{AVW26}
for $\tau<\tau_*$, where $\tau_*=\ln4/(5\ln10)=0.12041\ldots$, and not refuted by it for $\tau\ge\tau_*$; \cite[Section~5.4]{AVW26}
discusses this bound\\
\cite[Thms.~E.3(2),(3), C.10]{CPA26} & poly-attention and Strassen attention under the Sparse Max-$k$SAT and
Max-$2$SAT hypotheses &
both hypotheses are false~\cite[Corollaries~4.4 and~4.5]{Li26}; no replacement known\\
\addlinespace
\multicolumn{3}{@{}l}{\emph{(E) Not about satisfiability}}\\
\cite[Thm.~5.5]{GHSXY25} & $d=\poly(n)$ needs $T_{\mathrm{MUL}}(n,d,n)^{1-o(1)}$ & generalized high-dimensional $\OV$
hypothesis; unaffected\\
\cite[Thm.~5.1]{SXYY26}, \cite[Thm.~1.4]{AY25} & arithmetic-circuit lower bound; representational results & unconditional\\
\bottomrule
\end{tabular}
\caption{Lower bounds for attention and related kernels from exact embeddings and from other hypotheses, and their
basis after October 2026.}
\label{tab:ledger2}
\end{table}

\paragraph{Two observations.}
First, no result in the regime of the threshold, head dimension $\Theta(\log n)$ and logits of order $\log n$,
survives under a hypothesis about satisfiability: all of group (A) needs $\OV$ in dimension $\Theta(\log n)$, through
the gap machinery, through precision $2^{-\Theta(d)}$ for~\cite[Theorem~5.7]{GHSXY25}, or by starting from $\OV$ in
dimension $c\log n$, as~\cite[Theorem~4.7]{SXY26} does, and every exact embedding in group (C) pays with
polylogarithmic dimension, larger logits or superpolynomially small precision.
\Cref{thm:belowtwo} reaches the threshold spread $(1+\theta)\ln n$ at constant precision from satisfiability, at the
price of clause exponent below $2$ and dimension $n^{o(1)}$. Second, the refutation of the Sparse Max-SAT
Hypotheses~\cite[Corollaries~4.4 and~4.5]{Li26} removes the basis of the Max-SAT-based bounds for poly-attention and
Strassen attention in~\cite{CPA26}; the SETH-based part of that paper moves to group (B). Together with the
refutation of the hinted matrix--vector conjectures~\cite{AVW26}, these are the attention lower bounds whose
hypotheses are now false (for~\cite{vBSZ24}, in the range $\tau<\tau_*$) rather than unsupported.

\clearpage