\section{The concentration threshold}\label{sec:threshold}

This section proves \cref{thm:A}. The upper bound is uniform sampling; its cost is governed by how much
weight a single key can receive. The lower bounds show that under \cref{hyp:ldov} this cost cannot be improved
by a polynomial factor at any spread, and that once the spread allows one key to outweigh all others together,
constant precision already needs quadratic time.

\subsection{Sampling}\label{sec:sampling}

\begin{restatable}[Sampling]{proposition}{thmsampling}\label[proposition]{thm:sampling}
Consider an attention instance with $n$ queries, $n'$ keys, dimension $d$ and $d_v$ value coordinates.
Let $F\ge1$ satisfy $F\ge n'\pi_{ij}$ for all $i,j$, and let $\eps,\delta\in(0,1]$. There is a randomized
algorithm that, with probability at least $1-\delta$, outputs $\tilde o_i$ with
$\|\tilde o_i-o_i\|_\infty\le\eps$ for all $i$, using $O(nm(d+d_v))$ operations with
\[
m=\Bigl\lceil 40\,F\ln\bigl(2n(1+d_v)/\delta\bigr)/\eps^2\Bigr\rceil .
\]
Every instance with spread at most $\Spread$ satisfies the hypothesis with $F=e^{\Spread}$.
\end{restatable}

The algorithm samples $m$ keys uniformly with replacement for each query and returns the
self-normalized average $\sum_s e^{\ell_{ij_s}}v_{j_s}/\sum_s e^{\ell_{ij_s}}$. Bernstein's inequality
controls numerator and denominator, because the variance of a weight is at most its mean times its
maximum (\cref{app:sampling}). The quantity $n'\max_j\pi_{ij}$ is the factor by which the largest
attention weight exceeds the uniform weight $1/n'$, so the cost is $n^2$ times the largest attention
weight, up to the factor $(d+d_v)\log n/\eps^2$.

\begin{corollary}\label[corollary]{cor:sampling}
For every $\kappa\in[0,1]$ and $\eps\in(0,1]$, $\ATT(n,d,\kappa\ln n,\eps)$ can be solved in time
$O(n^{1+\kappa}d\log(nd)/\eps^2)$. The same holds for instances in which every attention weight is at most
$n^{\kappa-1}$.
\end{corollary}

\begin{proof}
Apply \cref{thm:sampling} with $n'=n$, $\delta=1/3$, $d_v\le d$ and $F=e^{\kappa\ln n}=n^{\kappa}$,
respectively $F=n\cdot n^{\kappa-1}$.
\end{proof}

Sampling keys is the idea behind several practical attention approximations, such as
KDEformer~\cite{ZHDK23} and HyperAttention~\cite{HJKMWZ24}, whose guarantees are stated in terms of
column norms of the attention matrix and stable ranks. \Cref{thm:sampling} is the simplest member of this
family, and under \cref{hyp:ldov}, \cref{cor:exponent} below shows that its exponent is optimal in terms of the
spread.

\subsection{Quadratic time above the threshold}\label{sec:ldov-lb}

\begin{restatable}[Hardness above the threshold]{theorem}{thmldovlb}\label{thm:ldovlb}
Assume \cref{hyp:ldov}. For all $\gamma\in(0,1)$ and $\theta\in(0,1]$ there is a constant $C\ge1$ such that for
every $\eps\in(0,1/2)$, $\ATT(n,\lceil C\log n\rceil,(1+\theta)\ln n,\eps)$ cannot be solved in time
$O(n^{2-\gamma})$. This holds already for instances with $d_v=1$, values in $\{0,1\}$, and all logits in
$[0,(1+\theta)\ln n]$.
\end{restatable}

For values in $\{0,1\}$, precision $1/2$ is trivial: output $1/2$ everywhere. For such values,
\cref{thm:ldovlb} therefore covers every nontrivial constant precision. The proof gives a constant $C$ that is
polynomial in $1/\theta$, with a degree that depends on $\gamma$ and on the constant of \cref{hyp:ldov}; so in a
fixed dimension $C\log n$ the hardness holds at spread $(1+C^{-\Omega_\gamma(1)})\ln n$.

\begin{proof}[Proof idea]
Take the gap instances of \cref{fact:chen} with $\tau\ge4/\theta$: every inner product lies in $[0,T]$,
a YES instance has a pair at $T$, and a NO instance has all pairs at most $T/\tau$. Let $\eta=(1-2\eps)/4$.
Scale the vectors by $\lambda\approx(\ln n+2\ln(1/\eta))/((1-1/\tau)T)$ and add one dummy key whose logit sits
$\ln((1-\eta)/\eta)$ below the top value $\lambda T$. If some key of a row is at $\lambda T$, the real keys of
that row carry at least $1-\eta$ of its weight. In a NO instance they carry at most $\eta$, because each lies
$\lambda T(1-1/\tau)$ below the top. All logits lie in $[0,\lambda T]$, and $\lambda T\le(1+\theta)\ln n$ for
large $n$. Each of the at most $2n^{\gamma/4}$ instances takes $O(\log n)$ attention calls, so an
$O(n^{2-\gamma})$ algorithm gives an $O(n^{2-\gamma/2})$ algorithm for $\OV$. \Cref{app:ldov-lb} gives the
details.
\end{proof}

\Cref{fact:chen} allows the gap $\tau$ to grow with $n$. With $\tau=\lceil\log n\rceil$ the same proof gives an
additive version, at the price of polylogarithmic dimension.

\begin{restatable}[Additive version]{corollary}{corladditive}\label[corollary]{cor:additive}
Assume \cref{hyp:ldov}. For all $\gamma\in(0,1)$ and $\eps\in(0,1/2)$ there is $C\ge1$ such that
$\ATT\bigl(n,\lceil(\log n)^C\rceil,\ln n+2\ln\frac{4}{1-2\eps}+2,\eps\bigr)$ cannot be solved in time
$O(n^{2-\gamma})$. For $\eps=1/6$ the spread is below $\ln n+6$. This holds already for instances with $d_v=1$ and values
in $\{0,1\}$.
\end{restatable}

\begin{remark}[Values in $\{-1,1\}$]\label[remark]{rem:pm}
Replacing every value $v$ by $2v-1$ maps an attention instance with values in $\{0,1\}$ to an instance with the same
logits and values in $\{-1,1\}$, and every output $o$ to $2o-1$. So an algorithm with precision $\eps$ on the new
instances gives one with precision $\eps/2$ on the old ones, at the cost of $O(n)$ further operations when $d_v=1$.
Hence \cref{thm:ldovlb}, and \cref{thm:curve,thm:belowtwo} below, hold for every $\eps\in(0,1)$ on instances with values
in $\{-1,1\}$, and so does \cref{cor:additive} with spread $\ln n+2\ln\frac{4}{1-\eps}+2$. With values in $[-1,1]$, precision
$1$ is trivial: output $0$ everywhere. So these results cover every nontrivial constant precision.
\end{remark}

\subsection{The exponent below the threshold}\label{sec:curve}

Below the threshold, splitting the keys into groups gives a matching lower bound at every spread.

\begin{restatable}[Hardness below the threshold]{theorem}{thmcurve}\label{thm:curve}
Assume \cref{hyp:ldov}. For all $\alpha\in(0,1]$, $\gamma\in(0,\alpha)$ and $\theta\in(0,1]$ there is a constant
$C\ge1$ such that for every $\eps\in(0,1/2)$, $\ATT(n,\lceil C\log n\rceil,(1+\theta)\alpha\ln n,\eps)$ cannot be
solved in time $O(n^{1+\alpha-\gamma})$. This holds already for instances with $d_v=1$, values in $\{0,1\}$, and all
logits in $[0,(1+\theta)\alpha\ln n]$.
\end{restatable}

\begin{proof}[Proof idea]
Under \cref{hyp:ldov}, $\OV$ with $n$ vectors on one side and $n^{\alpha}$ on the other needs time
$n^{1+\alpha-o(1)}$, because splitting one side of a balanced instance into $n^{1-\alpha}$ groups gives $n^{1-\alpha}$
such instances. The gadget of \cref{thm:ldovlb}, applied to one group through the vector-by-vector form of
\cref{fact:chen}, has $n^{\alpha}$ real keys, so a top logit $\alpha\ln n+O(1)$ above the others suffices. Copying
every key, the dummy key included, about $n^{1-\alpha}$ times multiplies every term of the numerator and of the
denominator of the softmax by the same factor, so it leaves the outputs and the spread unchanged and brings the
number of keys to between $n$ and $2n$. An algorithm faster than
$n^{1+\alpha-\gamma}$ on these instances would solve all groups in time $n^{2-\Omega(\gamma)}$. \Cref{app:curve}
gives the details.
\end{proof}

\begin{corollary}[The exponent]\label[corollary]{cor:exponent}
Fix $\eps\in(0,1)$ and $\kappa>0$. Then $\ATT(n,d,\kappa\ln n,\eps)$ can be solved in time
$n^{1+\min\{\kappa,1\}+o(1)}$ for every $d\le n^{o(1)}$. Under \cref{hyp:ldov}, for every $\gamma>0$ there is $C$
such that $\ATT(n,d,\kappa\ln n,\eps)$ has no $O(n^{1+\min\{\kappa,1\}-\gamma})$ algorithm for any $d$ with
$\lceil C\log n\rceil\le d\le n^{o(1)}$. This holds already for instances with $d_v=1$ and values in $\{-1,1\}$, and with
values in $\{0,1\}$ if $\eps<1/2$.
\end{corollary}

\begin{proof}
Let $\kappa'=\min\{\kappa,1\}$. For $\kappa<1$ the first part is \cref{cor:sampling}; for $\kappa\ge1$ direct computation
takes $O(n^2d)$ operations, with the exponentials evaluated as in step \sref{1}{6} of the proof of \cref{thm:sampling}.
For the second part it suffices to treat $\gamma<\kappa'/2$: for larger $\gamma$, the constant $C$ for $\kappa'/4$ works,
since an $O(n^{1+\kappa'-\gamma})$ algorithm is an $O(n^{1+\kappa'-\kappa'/4})$ algorithm. Choose $\theta\in(0,1]$ with
$\kappa'/(1+\theta)\ge\kappa'-\gamma/2$ and let $\alpha=\kappa'/(1+\theta)$. Then $\gamma/2<\kappa'/4<\alpha$, and for $\eps<1/2$,
\cref{thm:curve} for $\alpha$, $\gamma/2$ and $\theta$ gives $C$ such that spread $(1+\theta)\alpha\ln n=\kappa'\ln n$ has no
$O(n^{1+\alpha-\gamma/2})$ algorithm in dimension $\lceil C\log n\rceil$, already for $d_v=1$ and values in $\{0,1\}$. Since
$1+\alpha-\gamma/2\ge1+\kappa'-\gamma$ and $\kappa'\le\kappa$, this proves the claim in that dimension. For every $\eps\in(0,1)$
and values in $\{-1,1\}$, the same $C$ works by \cref{rem:pm} at precision $\eps/2$; the further $O(n)$ operations are
absorbed, since $1+\kappa'-\gamma>1$. Padding with zero coordinates preserves logits, and for $d\le n^{o(1)}$ writing the
padded instance takes $n^{1+o(1)}$ operations, which are absorbed too. So the bound holds for every $d$ with
$\lceil C\log n\rceil\le d\le n^{o(1)}$.
\end{proof}

So under \cref{hyp:ldov}, at every nontrivial constant precision and in every dimension between $\omega(\log n)$ and $n^{o(1)}$, the time
exponent of attention with spread $\kappa\ln n$ is exactly $1+\min\{\kappa,1\}$: up to factors $n^{o(1)}$ the cost is $n\cdot e^{\Spread}$ until
it reaches $n^2$, and uniform sampling is optimal. The transition to quadratic time sits at $\Spread=\ln n$, the
spread at which a single key can first outweigh all others together. At spread $(1-\theta)\ln n$ every attention
weight is at most $e^{\Spread}/n=n^{-\theta}$, and sampling sees enough keys. At spread $(1+\theta)\ln n$ a row can put
almost all of its weight on the keys at the top logit, and deciding whether such a row exists is as hard as $\OV$. For each $\gamma>0$ the lower bounds
hold in dimension $C\log n$ for a constant $C$ that depends on $\kappa$ and $\gamma$; in polylogarithmic dimension,
\cref{cor:additive} reaches spread $\ln n+O(1)$. Below dimension $C\log n$ the dimension matters: for constant $d$,
Gupta et al.~\cite{GHSXY25} compute attention in time $\tilde O(n^{2-1/d})$ at every spread.

The spread is a worst-case parameter. A single key with a large logit in every row, such as an attention sink,
makes the spread large while the other keys remain cheap to sample, and methods such as
HyperAttention~\cite{HJKMWZ24} find and remove such keys first. In the instances of \cref{thm:ldovlb} the
difficulty is to decide whether some row has a key at the top logit; Haverbeck et
al.~\cite[Theorem~5.1]{HAPTP26} show directly that finding the keys that carry most of the weight is hard.

\paragraph{Comparison with the bounded-entry threshold.}
In the normalization of Alman and Song, \cref{cor:sampling} applies whenever $B\le\sqrt{(1-\theta)\ln n/2}$,
because $\Spread\le 2B^2$. \Cref{thm:ldovlb} gives instances with $B=O_{\gamma,\theta,\eps}(\sqrt{\log n})$
(\cref{rem:entries}), so the threshold $B=\Theta(\sqrt{\log n})$ of~\cite{AS23} holds at constant
precision, under \cref{hyp:ldov}. In terms of $B$ the constant remains open: $2B^2$ bounds the spread only up to a
factor that depends on how many coordinates of the vectors are nonzero. In terms of the spread it is exact. Haverbeck et al.~\cite[Theorem~3.7]{HAPTP26} prove hardness at every nontrivial constant precision
(additive error below $1/2$ for values in $[0,1]$, relative error below $1$) with
$d=C_d\log n$ and $B=C_B\sqrt{\log n}$, for constants $C_d,C_B$ that depend on the precision and are not
specified; their reduction also goes through Rubinstein's gap problem, so it rests on \cref{hyp:ldov} as well.
Gupta et al.~\cite[Theorem~5.7]{GHSXY25} give hardness at $d=\Theta(\log n)$ with entries $\ln2$ in the
unnormalized form, that is, with spread $\Theta(\log n)$ and polynomial precision.