\section{Consequences for transformers}\label{sec:transformers}

The lower bounds above hold for every algorithm. This section states them for transformers that write a
chain of thought, and it compares the two explanations of in-context learning.

\subsection{Chains of thought}\label{sec:cot}

We model a trained transformer only by its cost. A \emph{sequence model} with $p$ parameters maps a sequence
of $\ell$ tokens to a next token. We assume that this map can be computed in time $(p+\ell)^{c_M}$ for a
constant $c_M$, as it can for a transformer with $p$ parameters of polynomial precision and polynomially many
layers and heads. The model answers a context and a query, encoded with $\poly(N)$ tokens per example, after
generating a \emph{chain of thought} of at most $L$ tokens. Generating $L$ tokens from a prompt of $\ell$
tokens takes time at most $(L+1)(p+\ell+L)^{c_M}\le(p+\ell+L)^{c_M+1}$.

The hypotheses we use are statements about algorithms, so the models must be produced by an algorithm too.
A family $(M_N)$ of sequence models is \emph{uniform} if a fixed deterministic algorithm outputs the parameters
of $M_N$ in time polynomial in $N$, for example a polynomial-time training procedure run with a fixed random
seed. Let $L(N)$ be the
largest length of a chain of thought of $M_N$ on the inputs under consideration.

\begin{restatable}[Chain-of-thought lengths]{corollary}{cortransformers}\label[corollary]{cor:transformers}
Let $(M_N)$ be a uniform family of sequence models with $p(N)\le N^{O(1)}$ parameters, as above.
\begin{enumerate}[label=(\alph*)]
\item\label{it:tseth} Assume \cref{hyp:cnfseth}, and let $\gamma,K,c_\gamma$ be as in
\cref{thm:hardness}\ref{it:seth}. If $M_N$ outputs $\Bayes(S,x)$ for every consistent context of at most
$N^{c_\gamma}$ examples of $\BP_{\lceil K\log N\rceil}$ in dimension $N$ and every query, then
$L(N)>2^{(1-\gamma)N/(c_M+1)}-N^{O(1)}$ for infinitely many $N$. So $L(N)=2^{\Omega(N)}$ for infinitely many $N$.
\item\label{it:tlen} Assume $\lenETH{C}$ and let $\theta>0$. If $M_N$ outputs $\Bayes(S,x)$ for every consistent
context of at most $36N^2$ examples of $\LD_3$ in dimension $N$ and every query, then
$L(N)\ge2^{N/(\log N)^{C+\theta}}$ for infinitely many $N$.
\item\label{it:tprg} Assume $\LPRG_s$ with predicate $P$, and let $m(N)\le\lceil N^s\rceil-1$ be computable in time
polynomial in $N$. If $L(N)\le N^{O(1)}$, then $M$ has risk at least $1/6$ on $(\RL_P,\cD_k)$ at context length
$m(N)$ for all sufficiently large $N$.
\item\label{it:tlenprg} Assume $\lenLPRG{c}$ with predicate $P$, and let $\alpha$ and $m(N)$ be as in
\cref{cor:regimes}\ref{it:clen}. If $L(N)\le2^{N/((c_M+2)(\log N)^{c})}$ for all sufficiently large $N$, then $M$
has risk at least $1/6$ on $(\RL_P,\cD_k)$ at context length $m(N)$ for all sufficiently large $N$.
\end{enumerate}
\end{restatable}

\begin{proof}[Proof sketch]
Computing the parameters and then simulating $M_N$ is an algorithm of time $N^{O(1)}+(p+\ell+L)^{c_M+1}$, and
on the inputs considered the prompt length $\ell$ is polynomial in $N$. In~\ref{it:tseth} and~\ref{it:tlen}, an
algorithm that computes $\Bayes(S,x)$ on all these contexts is excluded below the times of
\cref{thm:hardness}; solving for $L$ gives the bounds. Parts~\ref{it:tprg} and~\ref{it:tlenprg} are
\cref{cor:regimes} for the simulation (\cref{app:average}).
\end{proof}

For families with arbitrary trained weights, parts~\ref{it:tprg} and~\ref{it:tlenprg} hold under the versions of
the generator hypotheses that allow non-uniform distinguishers, such as circuits of the stated size, and
parts~\ref{it:tseth} and~\ref{it:tlen} would need non-uniform versions of CNF-SETH and $\lenETH{C}$.
Conversely, transformers that generate a chain of thought can simulate Turing machines~\cite{PBM21,MS24}, so the
algorithm of
\cref{thm:bayesalg} can in principle run in a chain of thought of subexponential length for locality
$o((\log N)^{1/4}/\sqrt{\log\log N})$. Before the refutation of ETH, the best known algorithms for the Bayes
prediction of $\LD_3$ took time $2^{\Omega(N)}$; under $\lenETH{C}$, a uniform family that computes it needs
chains of thought of length $2^{N/(\log N)^{C+\theta}}$ for infinitely many $N$.

\subsection{Bayesian and algorithmic in-context learning}\label{sec:twoviews}

Two explanations of in-context learning are current. The Bayesian one holds that a model trained on a task
distribution predicts like its posterior~\cite{XRLM22,MHPGH22,PAG24}. The algorithmic one holds that the model
runs a learning algorithm on its context, such as least squares, ridge regression or gradient
descent~\cite{GTLV22,ASA+23,vONR+23,BCW+23}. Raventós, Paul, Chen and Ganguli~\cite{RPCG23} find both in one
setting: trained on few regression tasks, a transformer follows the Bayes estimator of its pretraining
distribution; trained on many, it leaves that estimator and follows ridge regression, which lets it solve new
tasks.

For discrete task families with local structure, our results give the computational side of this picture.
The Bayes estimator over $2^N$ tasks is a counting problem: computing it on all contexts costs time
$2^{N/\polylog N}$ at constant locality and $2^{(1-\gamma)N}$ at logarithmic locality under the surviving
hypotheses (\cref{thm:hardness}), and on random local functions no efficient learner reaches the Bayes risk at
the context lengths where the Bayes estimator does (\cref{cor:regimes}). The algorithmic alternative is
efficient: least squares over local Fourier features learns every $\kappa$-local family from $N^{O(\kappa)}$
examples (\cref{thm:regression}), and for binarized perceptrons and literal disjunctions a linear program
learns from $O(N\log(1/\eps)/\eps)$ examples (\cref{thm:lp}). In-context least squares and ridge regression are
known to be implementable by transformers~\cite{ASA+23,BCW+23}, here with $\Psi(x)$ as the representation of
an input. A polynomial-size model produced by a polynomial-time training procedure can therefore be an
efficient in-context learner for such a family, but, unless the hypotheses fail, not a Bayes estimator for it.

The setting of~\cite{RPCG23} differs from ours: its discrete pretraining distributions are explicit lists of
regression tasks, for which the Bayes estimator is a finite mixture whose cost is linear in the number of
tasks. Our results concern exponentially many tasks with local structure, where the cost of the mixture is
the cost of counting.