\section{Precision and dimension move the threshold}\label{sec:precision}

The threshold $\Spread=\ln n$ is a statement about constant precision. Precision $1/\poly(n)$, as
in~\cite{AS23}, keeps errors small when attention layers are composed. At that precision the picture changes:
there is no single constant, higher precision makes smaller spreads hard, and, unlike at constant precision,
the dimension matters. This section proves \cref{thm:B}. We write the precision as $n^{-\beta}$.

\subsection{Counting modulo \texorpdfstring{$r+1$}{r+1}}\label{sec:parity}

Gupta et al.~\cite[Theorem~5.7 and Lemma~5.8]{GHSXY25} observed that attention with logits $(\ln2)\ip ab$ and
precision $n^{-O(1)}$ reveals the parity of the number of orthogonal partners of $a$. The point is that
$\sum_b2^{\ip ab}$ is an integer whose parity is the parity of the number of $b$ with $\ip ab=0$. We make two
changes. The base $1+1/r$ instead of $2$ makes the logits $\ln(1+1/r)\ip ab$ small, while
$r^m\sum_b(1+1/r)^{\ip ab}$ is still an integer that determines the number of orthogonal partners modulo $r+1$.
And counting intersecting \emph{blocks} instead of intersecting coordinates reduces the number of digits
that must be resolved, at the price of dimension. For a partition of $[m]$ into $K$ blocks, let
\[
F(a,b)=\bigl|\{t\le K:\ a\text{ and }b\text{ share a one in block }t\}\bigr|.
\]
Then $F(a,b)=0$ exactly when $a\perp b$, and $F(a,b)=\ip{\phi(a)}{\psi(b)}$ for vectors of dimension
$\sum_t(2^{|B_t|}-1)$, by inclusion--exclusion inside each block (\cref{app:parity}).

\begin{restatable}[Precision lower bound]{theorem}{thmparity}\label{thm:parity}
Assume \cref{hyp:ldov}. For every $\gamma\in(0,1)$ there is an integer $c\ge1$ with the following property.
Let $r,w:\N\to\N$ be computable in time $O(n)$, with $r(n),w(n)\ge1$ for all $n$, and $r(n)\le n$ and
$w(n)\le\frac12\log n$ for all large $n$. Let
\[
K=\bigl\lceil\lceil c\log n\rceil/w\bigr\rceil,\qquad d=K(2^w-1),\qquad \Spread=K\ln(1+1/r),\qquad
\eps=\frac{1}{64\,n\,(r+1)^{2K}},
\]
with $r=r(n)$ and $w=w(n)$. Then $\ATT(n,d,\Spread,\eps)$ cannot be solved in time $O(n^{2-\gamma})$. This holds
already for $d_v=1$, values in $\{0,1\}$, and all logits in $[0,\Spread]$.
\end{restatable}

Here $w$ is the size of the blocks. With $w=1$ the blocks are single coordinates, $F(a,b)=\ip ab$, and the
dimension is $K=\lceil c\log n\rceil$.

\begin{proof}[Proof idea]
Fix $a\in A$, keep each $b\in B$ with probability $1/2$, and replace the dropped vectors by the all-ones
vector, which shares a one with every $a\ne0$. The queries are $\lambda\phi(a)$ with $\lambda\approx\ln(1+1/r)$,
the keys are $\psi$ of the kept vectors, and $n$ further keys equal to $0$ carry value $1$. The output of $a$
is $n/(n+S_a)$ with $S_a=\sum_b(1+1/r)^{F(a,b)}$. If the vectors of the $\OV$ instance have $K_0\le K$ blocks,
precision $\eps$ recovers the integer $r^{K_0}S_a$ exactly. Modulo $r+1$, every term with $F\ge1$ vanishes, so
$r^{K_0}S_a\equiv r^{K_0}N_a$, where $N_a$ is the number of kept orthogonal partners of $a$, and $r^{K_0}$ is
invertible modulo $r+1$. If $a$ has an orthogonal partner, then $N_a\not\equiv0\pmod{r+1}$ with probability at
least $1/2$. Four rounds detect an orthogonal pair with probability $15/16$. \Cref{app:parity} gives the
details.
\end{proof}

Three choices of the parameters give the following.

\begin{corollary}\label[corollary]{cor:parity}
Assume \cref{hyp:ldov}, and let $\gamma\in(0,1)$ and $c$ be as in \cref{thm:parity}. None of the following can be
solved in time $O(n^{2-\gamma})$.
\begin{enumerate}[label=(\alph*)]
\item \emph{Dimension $\lceil c\log n\rceil$.} For every $\kappa>0$: spread $\kappa\ln n$ at precision
\[
\frac{1}{64\,(c_\kappa+3)^2\,n^{1+2c\log(c_\kappa+3)}},\qquad c_\kappa=\frac{c}{\kappa\ln2};
\]
and spread $1$ at precision $n^{-O(c\log(c\log n))}$.
\item \emph{Polylogarithmic dimension.} For every rational $C'>0$: dimension $(\log n)^{1+C'}$, spread at most
$\frac{c\ln2}{C'}\cdot\frac{\log n}{\log\log n}+1$, and precision $n^{-1-\zeta}$ with
$\zeta=O(c/(C'\log\log n))$.
\item \emph{Polynomial dimension.} For every rational $\delta\in(0,1/2]$: dimension $(c/\delta+2)n^{\delta}$, spread
$(c/\delta+2)\ln2$, precision $1/(64\cdot4^{c/\delta+2}n)$.
\end{enumerate}
\end{corollary}

\begin{proof}
All statements are for large $n$. Where the formulas below give $r$ or $w$ a value below $1$, which happens only
for small $n$, we use $1$ instead; then $r(n)\le n$ and $w(n)\le\frac12\log n$ hold for all large $n$. For (a),
take $w=1$, so $K=\lceil c\log n\rceil\le c\log n+1$ and $\eps\ge1/(64(r+1)^2n^{1+2c\log(r+1)})$. With the constant
$r=\lceil c_\kappa\rceil+1$, the spread is at most $(c\log n+1)/r\le\kappa\ln n$ for $n\ge e^{1/\kappa}$, because
$r\kappa\ln n\ge c\log n+\kappa\ln n$, and $r+1\le c_\kappa+3$. With $r(n)=\lceil c\log n\rceil$, the spread is
at most $K/r=1$ and $\eps=n^{-O(c\log(c\log n))}$. For (b), take $r=1$ and $w=\lceil C'\log\log n\rceil$: then
$K\le(c\log n+1)/(C'\log\log n)+1$, the spread is $K\ln2$, the dimension is at most $2K(\log n)^{C'}\le(\log n)^{1+C'}$,
and $\eps=1/(64n4^K)$. For (c), take $r=1$ and $w=\lfloor\delta\log n\rfloor$: then $K\le c/\delta+2$, the dimension is
at most $K\,n^{\delta}$, and $\eps=1/(64n4^K)$.
\end{proof}

\begin{remark}[Bounded entries]\label[remark]{rem:entries2}
In the normalization of~\cite{AS23}, case (a) with $r(n)=\lceil c\log n\rceil$ has bounded entries. There $w=1$,
$\phi(a)=a$ and $\psi(b)=b$, so an instance of size $n$ in the proof of \cref{thm:parity} has dimension
$d=K=\lceil c\log n\rceil=r$, queries $\lambda'a$ with $0<\lambda'\le\ln(1+1/r)\le1/d$, and keys in $\{0,1\}^d$ after
padding. Rescaling the queries by a rational $s\in[\sqrt{d/\lambda'},2\sqrt{d/\lambda'}]$ and the keys by $d/s$, as in
\cref{rem:entries}, writes the same logits as $\ip qk/d$ with all entries bounded by $2\sqrt{d\lambda'}\le2$. So entries
bounded by $2$ are already hard at precision $n^{-O(c\log(c\log n))}$.
\end{remark}

\subsection{The polynomial method}\label{sec:polymethod}

On the algorithmic side, the polynomial method of Alman and Song~\cite{AS23} replaces $e^x$ by a
polynomial on the range of the logits. For dimension $O(\log n)$ and precision $n^{-\beta}$ it handles every
spread below a constant multiple of $\ln n$, with a constant that tends to $0$ as $\beta$ grows.

\begin{restatable}[Polynomial method]{proposition}{thmpoly}\label[proposition]{thm:poly}
For all $C\ge1$, $\beta\ge1$ and $\eta\in(0,1)$ there is $\kappa=\kappa(C,\beta,\eta)>0$ such that the following
holds for all sufficiently large $n$. Every attention instance with $n$ queries, $n$ keys, dimension
$d\le C\log n$, $d_v\le d$ value coordinates and spread at most $\kappa\ln n$ can be solved to precision $n^{-\beta}$
deterministically with $O(n^{1+\eta})$ arithmetic operations on rationals of $O(\log^2n)$ bits.
\end{restatable}

This is the method of~\cite{AS23} with the dependence on $\beta$ and on the spread made explicit. The proof first
shifts each row by its first logit, through one extra coordinate equal to $-\ip{q_i}{k_1}$ in
$q_i$ and to $1$ in every key, so that all logits lie in $[-\kappa\ln n,\kappa\ln n]$, and rounds the entries to a
grid of $O(\log n)$ bits; then a Taylor polynomial of degree $g=\Theta(\beta\log n/\log(\beta/\kappa))$ has rank
$\binom{d+g}{g}=n^{O(\eta)}$ (\cref{app:polymethod}).

\begin{corollary}[Precision decides the threshold]\label[corollary]{cor:precision}
Assume \cref{hyp:ldov}. For every $\gamma\in(0,1)$ there is $C_\gamma$ such that the following holds for instances
of dimension at most $C_\gamma\log n$. For every $\beta\ge1$ there is $\kappa_{\mathrm{easy}}(\beta)>0$ such that spread
$\kappa_{\mathrm{easy}}(\beta)\ln n$ at precision $n^{-\beta}$ can be solved in time $O(n^{2-\gamma})$. For every $\kappa>0$
there is $\beta_{\mathrm{hard}}(\kappa)=O(C_\gamma\log(2+C_\gamma/\kappa))$ such that spread $\kappa\ln n$ at precision
$n^{-\beta_{\mathrm{hard}}(\kappa)}$ cannot. So the largest spread, in units of $\ln n$, that can be handled in time
$O(n^{2-\gamma})$ at precision $n^{-\beta}$ is positive for every $\beta$ and tends to $0$ as $\beta\to\infty$.
\end{corollary}

\begin{proof}
Let $c$ be the integer of \cref{thm:parity} for $\gamma$, and $C_\gamma=c+1$. The first claim is \cref{thm:poly}
with $C=C_\gamma$ and $\eta=(1-\gamma)/2$, since $O(n^{1+\eta})$ operations on $O(\log^2n)$-bit numbers take time
$O(n^{2-\gamma})$. The second is \cref{cor:parity}(a), whose precision is $n^{-O(c\log(2+c/\kappa))}$. Every fixed
$\kappa>0$ is therefore hard at precision $n^{-\beta_{\mathrm{hard}}(\kappa)}$, so the largest solvable spread at precision
$n^{-\beta}$ is below $\kappa\ln n$ once $\beta\ge\beta_{\mathrm{hard}}(\kappa)$.
\end{proof}

\subsection{Dimension matters at high precision}\label{sec:dimension}

At constant precision the dimension does not affect the exponent once it is at least $C\log n$:
\cref{thm:sampling} works in every dimension, and \cref{thm:ldovlb,thm:curve} need only $C\log n$. At precision
about $1/n$ it matters a great deal. In dimension $O(\log n)$ and at precision $n^{-1-O(1/\log\log n)}$, the boundary
between easy and hard spreads is $\Theta(\log n)$: spread $\kappa\ln n$
is easy for some $\kappa>0$ by \cref{thm:poly} with $\beta=2$, and spread $(1+\theta)\ln n$ is hard by
\cref{thm:ldovlb}, because hardness at constant precision carries over to every finer precision. By
\cref{cor:parity}, the hard spread falls to $O(\log n/\log\log n)$ in dimension $(\log n)^{1+C'}$ for every $C'>0$,
and to $O(1)$ in dimension $n^{\delta}$. The mechanism is a trade-off between three parameters of
\cref{thm:parity}: blocks of size $w$ divide the number $K$ of digits, and with it the spread $K\ln(1+1/r)$, by $w$,
and take the $w$-th root of the excess $(r+1)^{2K}$ in the precision, while the dimension $K(2^w-1)$ grows
exponentially in $w$.

The upper bound of \cref{thm:poly} degrades with the dimension as well.

\begin{restatable}[Polynomial method in higher dimension]{proposition}{proppolyhigh}\label[proposition]{prop:polyhigh}
Let $C>1$, $\beta\ge1$ and $\eta\in(0,1)$ with $4(\beta+5)(C-1)<\eta$, and let $a\in(4(\beta+5)(C-1)/\eta,\,1]$. For all
sufficiently large $n$, every attention instance with $n$ queries, $n$ keys, dimension $d\le(\log n)^C$, $d_v\le d$
value coordinates and spread at most $(\log n)^{1-a}$ can be solved to precision $n^{-\beta}$ deterministically with
$O(n^{1+\eta})$ arithmetic operations on rationals of $O(\log^2n)$ bits.
\end{restatable}

The proof (\cref{app:dimension}) is that of \cref{thm:poly} with a Taylor polynomial of degree
$g=\lceil2(\beta+5)\ln n/(a\ln\ln n)\rceil$, which has $n^{(1+o(1))2(\beta+5)(C-1)/a}$ monomials in dimension
$(\log n)^C$. So in dimension $(\log n)^C$ with $C<1+\eta/(4(\beta+5))$, the method handles spread $(\log n)^{1-a}$ for
every $a\in(4(\beta+5)(C-1)/\eta,1]$, below the spread $O(\log n/\log\log n)$ that \cref{cor:parity}(b) makes hard at every
precision $n^{-\beta}$ with $\beta>1$. For $C\ge1+\eta/(4(\beta+5))$ the proposition gives nothing.
\Cref{prob:dimension} asks where the threshold lies. Padding with zero coordinates preserves
logits, so every lower bound transfers to every larger dimension $d$ for which $nd$ stays below its time bound.