\section{Introduction}\label{sec:intro}

A transformer that learns in context receives labeled examples of a task and predicts the label of a
query, with no update of its weights. A widely used explanation of this ability is Bayesian: pretraining
on a distribution of tasks teaches the model to predict like the posterior of that distribution, given
the examples in its context~\cite{XRLM22,PAG24}. Prior-fitted networks are trained for exactly this
purpose~\cite{MHPGH22}. Other work shows that transformers can implement learning algorithms in context,
such as least squares, ridge regression and gradient descent~\cite{GTLV22,ASA+23,vONR+23,BCW+23}, and
experiments find that models trained on diverse task families leave the Bayes estimator of their
pretraining prior and follow such algorithms instead~\cite{RPCG23}.

This paper asks what Bayes-optimality in context costs, and how the cost compares with that of learning
in context at all. We answer the question in exact exponents for a natural class of discrete task
families. In these families there are $2^N$ tasks, and the posterior is a sum over all of them. The
answer turns on the recent refutations of the Exponential Time Hypothesis (ETH) by OpenAI and
Anthropic~\cite{OAI26,Cla26}. Both count the satisfying assignments of a $k$-CNF on $n$ variables in
time $2^{n/(\log n)^{1/2-o(1)}}$. The companion paper~\cite{Li26} determined what these algorithms mean for
proper learning. Here they supply the upper bounds for Bayesian prediction, and the hypotheses that
survive them, CNF-SETH and a length form of ETH, supply the lower bounds.

\subsection{The model}\label{sec:intro-model}

A class $\cH=\{h_w:w\in\{0,1\}^N\}$ is \emph{$\kappa$-local} if for each input $x$ the label $h_w(x)$
depends only on at most $\kappa$ bits of $w$~\cite{Li26}. Quantized models on sparse data are local. A
binarized perceptron $x\mapsto\ind[\langle\sigma,x\rangle\ge0]$ with $\sigma\in\{\pm1\}^N$ is $k$-local on
$k$-sparse inputs, and so are literal disjunctions, quantized embedding models on bags of $k$ tokens, and
Goldreich's random local functions~\cite{Gol00}.

An \emph{episode} draws a task $w$ uniformly from $\{0,1\}^N$, inputs $x_1,\dots,x_{m+1}$ independently
from a distribution $\cD$, and labels $y_i=h_w(x_i)$, each flipped independently with probability
$\eta<1/2$. An \emph{in-context learner} sees the context $S=((x_1,y_1),\dots,(x_m,y_m))$ and the query
$x_{m+1}$ and predicts $y_{m+1}$; its \emph{risk} is its error probability. The \emph{Bayes in-context
predictor} predicts $1$ when the posterior predictive $p_S(x_{m+1})=\Pr[h_w(x_{m+1})=1\mid S]$ is at least
$1/2$. It has the least risk of all in-context learners. We call the computation of $p_S(x)$ for given
$S$ and $x$ \emph{Bayesian inference in context}.

\subsection{Results}\label{sec:intro-results}

\begin{figure}[t]
\centering
\begin{tikzpicture}[x=1cm,y=1cm,
  reg/.style={font=\footnotesize,align=center,text width=#1},
  tk/.style={font=\footnotesize,anchor=north},
  ttl/.style={font=\small\bfseries,anchor=south west,inner sep=0pt}]
% ---------- row 1: worst case, locality ----------
\node[ttl] at (0,7.45) {Bayesian inference in context, worst case, by locality $\kappa$};
\fill[easy!30] (0,6.4) rectangle (4.6,7.2);
\fill[open!25] (4.6,6.4) rectangle (9.6,7.2);
\fill[hard!30] (9.6,6.4) rectangle (15.2,7.2);
\draw[thin,black!50] (0,6.4) rectangle (15.2,7.2);
\node[reg=4.4cm] at (2.3,6.8) {$2^{o(N)}$, unconditional};
\node[reg=4.8cm] at (7.1,6.8) {equivalent to $\#k$-SAT\\ with $k=(\log N)^{\Theta(1)}$};
\node[reg=5.4cm] at (12.4,6.8) {$2^{(1-\gamma)N}$ under CNF-SETH};
\node[tk,anchor=north west] at (0,6.35) {$1$};
\node[tk] at (4.6,6.35) {$(\log N)^{1/4-o(1)}$};
\node[tk] at (9.6,6.35) {$K\log N$};
\draw[easy,very thick,decorate,decoration={brace,amplitude=4pt,mirror}] (0,5.75) -- (2.4,5.75);
\node[font=\footnotesize,align=left,anchor=north west] at (0,5.5) {constant $\kappa\ge3$: exponent\\ $N/\polylog N$ under $\lenETH{C}$};
\node[font=\footnotesize,align=left,anchor=north west] at (5.0,5.75) {PAC in-context learning of the same families (binarized\\ perceptrons, literal disjunctions): polynomial time for every\\ $\kappa$ (\cref{thm:lp}).};
% ---------- row 2: average case, context length ----------
\node[ttl] at (0,3.85) {Random local functions of arity $k$, average case, by context length $m$};
\fill[hard!30] (0,2.8) rectangle (5.6,3.6);
\fill[open!25] (5.6,2.8) rectangle (10.0,3.6);
\fill[easy!30] (10.0,2.8) rectangle (15.2,3.6);
\draw[thin,black!50] (0,2.8) rectangle (15.2,3.6);
\node[reg=5.4cm] at (2.8,3.2) {no polynomial-time learner reaches\\ risk below $1/6$ under $\LPRG_s$};
\node[reg=4.2cm] at (7.8,3.2) {open};
\node[reg=5.0cm] at (12.6,3.2) {polynomial time\\ by regression in context};
\node[tk,anchor=north west] at (0,2.75) {$m=\Theta(N)$};
\node[tk] at (5.6,2.75) {$N^{s}$};
\node[tk] at (10.0,2.75) {$O(N^{k})$};
\draw[hard,very thick,decorate,decoration={brace,amplitude=4pt,mirror}] (0,2.15) -- (2.6,2.15);
\node[font=\footnotesize,align=left,anchor=north west] at (0,1.9) {time $2^{N/\polylog N}$: Bayes predictor,\\ matching under $\lenLPRG{c}$};
\node[font=\footnotesize,align=left,anchor=north west] at (5.0,2.15) {Bayes risk at most $N/(m+1)$ at every context length\\ (\cref{thm:risk}).};
% ---------- legend ----------
\fill[easy!30] (0.0,0.35) rectangle (0.35,0.65); \node[anchor=west,font=\footnotesize] at (0.4,0.5) {polynomial or subexponential, unconditional};
\fill[open!25] (7.0,0.35) rectangle (7.35,0.65); \node[anchor=west,font=\footnotesize] at (7.4,0.5) {open};
\fill[hard!30] (8.6,0.35) rectangle (8.95,0.65); \node[anchor=west,font=\footnotesize] at (9.0,0.5) {hard under a stated hypothesis};
\end{tikzpicture}
\caption{The price of Bayes-optimality. Row~1: exact or approximate (within $1/4$) Bayesian inference in
context for $\kappa$-local families (\cref{thm:bayesalg,thm:hardness}); the middle window is the locality
window of~\cite{Li26}. Row~2: in-context learning of Goldreich's random local functions
(\cref{thm:regimes,cor:regimes}). The regimes are not drawn to scale.}
\label{fig:regimes}
\end{figure}

Three theorems make the comparison. \Cref{fig:regimes} summarizes them.

\begin{headline}[Bayesian inference in context is counting; \cref{thm:bayesalg,thm:hardness}]\label{thm:A}
Let $\cH$ be $\kappa$-local with $N$-bit descriptions, under the uniform prior.
\begin{enumerate}[label=(\arabic*)]
\item Without label noise, the posterior predictive and exact posterior samples can be computed in time
$\poly(N,m)\cdot2^{O(\kappa^2N\log\log N/\sqrt{\log N})}$ for contexts of every length $m$. With a rational
noise rate $a/b$ they take time $\poly(N,m,\log b)\cdot2^{O(\kappa m/\sqrt{\log m})}$ for $m\ge\max\{\kappa,2\}$.
Exact Bayesian inference in context is equivalent to $\#\kappa$-SAT, up to a factor $2$ in the locality.
\item Under CNF-SETH, for every $\gamma>0$ there is $K$ such that no algorithm approximates the posterior
predictive within $1/4$ in time $O(2^{(1-\gamma)N})$ for binarized perceptrons, or for literal
disjunctions, on $(K\log N)$-sparse data. The hard contexts have polynomial size and are consistent.
\item Under the length form $\lenETH{C}$ of ETH, for literal disjunctions on $3$-sparse data no algorithm
does so in time $2^{N/(\log N)^{C+\theta}}$ on contexts of $O(N^2)$ examples, for every $\theta>0$. At constant
locality, Bayesian inference in context is SAT parameterized by formula length, up to polylogarithmic
factors in the exponent.
\end{enumerate}
\end{headline}

Part~(1) is the version-space and error-profile machinery of~\cite{Li26} applied to prediction. The
lower bounds come from one gadget. For a CNF $F$, add a variable $a$ to every clause as $\neg a$, and add
clauses that set every other variable to $0$ when $a$ is false; add one free variable for $a$ true. The
satisfying assignments are $2\#F$ assignments with $a=1$ and one with $a=0$. As a context, this formula is
consistent for every $F$, and the posterior probability that $a=1$ is $2\#F/(2\#F+1)$, which is $0$ or at
least $2/3$ according to whether $F$ is satisfiable. So the difficulty is not consistency, which is
trivial here, but the posterior.

\begin{headline}[Learning in context is cheap; \cref{thm:risk,thm:lp,thm:linear,thm:regression}]\label{thm:B}
\begin{enumerate}[label=(\arabic*)]
\item For every class with $N$-bit descriptions and every input distribution, the Bayes risk after $m$
examples is at most $N/(m+1)$, and at most $\eta+(1-2\eta)N/((1-\Hb(\eta))(m+1))$ with label noise $\eta$,
where $\Hb$ is the binary entropy.
\item For binarized perceptrons and literal disjunctions on $k$-sparse data, for every $k$, a linear
program is a polynomial-time in-context learner with error at most $\eps$, with probability at least
$1-\delta$, from $O((N\log(1/\eps)+\log(1/\delta))/\eps)$ examples, for every input distribution and every
task.
\item Every $\kappa$-local class is linear over $D_\kappa=\sum_{j\le\kappa}\binom Nj$ local Fourier features.
Regression in context learns it, also agnostically, to error $\eps$ with probability $1-\delta$, in time
$\poly(N,D_\kappa,1/\eps,\log(1/\delta))$ from $O((D_\kappa+\log(1/\delta))/\eps^2)$ examples.
\end{enumerate}
\end{headline}

Parts (2) and \cref{thm:A}(2) concern the same families on the same contexts. At locality $K\log N$, the
Bayes predictor needs time $2^{(1-\gamma)N}$ under CNF-SETH, while a linear program learns the family in
polynomial time with the sample efficiency of the Bayes predictor up to a logarithmic factor. The expensive
part of Bayes-optimal in-context learning is the Bayes-optimality, not the learning.

The hard contexts of \cref{thm:A} are atypical for the prior: every label in them is positive. The third
theorem works in the average case, over the task distribution itself. Goldreich's function with predicate
$P\colon\{0,1\}^k\to\{0,1\}$ maps $w$ and random $k$-tuples $\tau_1,\dots,\tau_m$ of indices to the bits
$P(w_{\tau_j})$~\cite{Gol00,App16}. As a task family, its tasks are $w\in\{0,1\}^N$ and its inputs are
$k$-tuples.

\begin{headline}[Random local functions; \cref{thm:regimes,cor:regimes}]\label{thm:C}
For the random local functions of a predicate of arity $k$, under the uniform distribution on
$k$-tuples:
\begin{enumerate}[label=(\arabic*)]
\item the Bayes risk is at most $N/(m+1)$, and the Bayes predictor runs in time
$\poly(m)\cdot2^{O(N\log\log N/\sqrt{\log N})}$;
\item regression in context has risk at most $\eps$ from $O(N^k\log(1/\eps)/\eps)$ examples, in polynomial
time;
\item every in-context learner $A$ yields a distinguisher for Goldreich's generator with $m+1$ outputs that
runs in the time of $A$ plus $O(mk\log N)$ and has advantage exactly $|1/2-R_m(A)|$.
\end{enumerate}
So under a local pseudorandom generator hypothesis $\LPRG_s$ with stretch $N^s$, no polynomial-time
in-context learner has risk below $1/6$, for large $N$, at a context length $m(N)\le\lceil N^s\rceil-1$ computable
in polynomial time, although at $m=\lceil N^s\rceil-1$ the Bayes risk is at most $N^{1-s}$. Under its length form
$\lenLPRG{c}$ at linear stretch, an in-context learner needs time more than $2^{N/(\log N)^c-1}$ to reach risk
below $1/6$ from $\lceil\alpha N\rceil-1$ examples, for a large enough constant $\alpha$, and the Bayes predictor of~(1) reaches
risk $1/\alpha$ in time $2^{N/(\log N)^{1/2-o(1)}}$. The hypothesis $\lenLPRG{c}$ is false for $c<1/2$, by the new
algorithms, and open for $c\ge1/2$.
\end{headline}

\paragraph{Consequences for transformers.}
A polynomial-size transformer whose weights are computed in polynomial time, for example by a
polynomial-time training procedure, and that writes a chain of thought of length $L$ can be simulated in
time polynomial in $L$ and the context. The lower bounds above therefore bound $L$ from below. Under
CNF-SETH, such a transformer that outputs the Bayes prediction for every context of binarized perceptrons on
$(K\log N)$-sparse data needs $L=2^{\Omega(N)}$ for infinitely many $N$, and under $\lenETH{C}$ already locality $3$
needs $L=2^{N/\polylog N}$ for infinitely many $N$. Under $\LPRG_s$, no such transformer with a polynomial chain of
thought reaches risk below $1/6$ on random local functions, for large $N$, at a context length $m(N)\le\lceil
N^s\rceil-1$ computable in polynomial time (\cref{cor:transformers}). Regression in context, the efficient alternative of \cref{thm:B}, is the kind of
algorithm that transformers are known to implement~\cite{ASA+23,vONR+23,BCW+23}. For discrete task families
with local structure, these results separate the Bayesian explanation of in-context learning from the
algorithmic one, and they are consistent with the departure from the Bayes estimator that~\cite{RPCG23}
observe on diverse task families (\cref{sec:transformers}).

\subsection{Techniques}\label{sec:techniques}

\paragraph{Prediction as a ratio of counts.} Without noise, the posterior is uniform on the version space,
and $p_S(x)$ is the number of consistent descriptions that label $x$ positive divided by the number of all
consistent descriptions. For local classes both are counts of $\kappa$-CNFs~\cite{Li26}. With noise, two
error profiles, of the context and of the context with $(x,1)$ added, determine the profile of the
descriptions that label $x$ positive, and the posterior predictive is a ratio of two polynomials evaluated
at $\eta/(1-\eta)$.

\paragraph{The gadget.} The two-variable construction above keeps the context consistent and moves the
whole difficulty into the posterior. It needs only one more variable than the formula, and one more for the
factor $2$, so the width reduction of~\cite{Sch05,CIP06} in the form of~\cite{Li26} turns it into a
$2^{(1-\gamma)N}$ lower bound. For the length form, fresh variables split the clauses, and clauses that
force them to $0$ when $a$ is false keep the branch $a=0$ a single assignment.

\paragraph{The Bayes risk.} Each mistake of the Bayes predictor at least halves the posterior mass, so
there are at most $N$ mistakes in any episode; this is the halving argument~\cite{BF72,Lit88} with posterior
weights. The Bayes risk does not increase with the context length, because the posterior predictive of a
fixed query is a martingale and the error of the Bayes decision is a concave function of it. Together the
two facts give $N/(m+1)$. With noise, the cumulative log-loss regret of the Bayes mixture, which is at
most $N$, bounds the mistakes through a Kullback--Leibler divergence.

\paragraph{Local Fourier features.} For each input $x$, the label $h_w(x)$ is a function of the at most
$\kappa$ bits of $w$ in $R(x)$, so its Fourier expansion has at most $2^\kappa$ terms, all of degree at most
$\kappa$. Hence $h_w(x)=\langle\Phi(w),\Psi(x)\rangle$ with $\Phi(w)\in\{\pm1\}^{D_\kappa}$, and the class is a
linear class over the features $\Psi$. Linear algebra learns it in the realizable case, and $\ell_1$
regression~\cite{KKMS08} in the agnostic case. For binarized perceptrons and literal disjunctions a halfspace
in the original coordinates suffices.

\paragraph{Next-bit prediction.} An in-context learner for random local functions predicts the last
output of Goldreich's generator from the earlier outputs. By Yao's argument~\cite{Yao82}, its advantage over
$1/2$ is the advantage of a distinguisher.

\subsection{What is new}\label{sec:new}
The realizable Bayes risk bound is classical~\cite{HKS94}, the linearization is the Fourier expansion of a
local function, and next-bit prediction is Yao's. The posterior algorithms use only the statements
of~\cite{Li26}, which in turn use the refutations~\cite{OAI26,Cla26} as black boxes. New are the gadget and
the fine-grained lower bounds for Bayesian inference in context, the comparison with polynomial-time
learning of the same families on the same contexts, the noisy Bayes risk bound in this form, the sample
bound for regression on local Fourier features, the three regimes for random local functions with the
hypothesis $\lenLPRG{c}$ and its refutation below rate $1/2$, and the consequences for transformers.

\subsection{Organization}\label{sec:organization}
\Cref{sec:prelim} fixes the model and imports the results of~\cite{Li26}. \Cref{sec:bayes} gives the
algorithms for Bayesian inference in context and the bound on the Bayes risk. \Cref{sec:hardness} proves the
lower bounds. \Cref{sec:efficient} gives the efficient in-context learners. \Cref{sec:average} treats random
local functions, and \cref{sec:transformers} draws the consequences for transformers. \Cref{sec:related}
discusses related work, and \cref{sec:open} lists open problems. The appendix contains all proofs in
structured form.

\paragraph{AI disclosure.}
This paper was written with Claude Opus~5.5 (Anthropic), working as an agent in Claude Code. The author asked
Claude to propose questions that build on~\cite{Li26}. Claude chose one of them, proved the results and wrote
the text. The gadgets, the linearization and the risk bounds were checked by brute force
on small instances, and separate Claude agents checked the citations and audited the proofs. The author is
responsible for the content.