\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage[titles]{tocloft}
\setlength{\cftbeforesecskip}{0.25em}
\setlength{\cftbeforetoctitleskip}{0pt}
\setlength{\cftaftertoctitleskip}{0.8em}
\usepackage{enumitem}
\usepackage{booktabs}
\usepackage{array}
\newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}}
\usepackage{graphicx}
\usepackage{xcolor}
\definecolor{citewarm}{HTML}{B5403B}
\definecolor{refcool}{HTML}{2C5AA0}
\definecolor{easy}{HTML}{1B9E77}
\definecolor{open}{HTML}{9A9A9A}
\definecolor{hard}{HTML}{D95F02}
\usepackage{tikz}
\usetikzlibrary{positioning,decorations.pathreplacing,calc}
\usepackage[colorlinks=true,linkcolor=refcool,citecolor=citewarm,urlcolor=refcool]{hyperref}
\usepackage[capitalise,nameinlink]{cleveref}
\usepackage{environ}

\setlist{itemsep=1pt,parsep=0pt,topsep=3pt,partopsep=0pt}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Imported Theorem}
\newtheorem{headline}{Theorem}
\renewcommand{\theheadline}{\Alph{headline}}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{hypothesis}[theorem]{Hypothesis}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}{Open Problem}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\crefname{fact}{Imported Theorem}{Imported Theorems}

% ---------- restatable results: \begin{restatable}[title]{env}{name} ... \end{restatable},
% restated later by \name* with the same number and without labels ----------
\makeatletter
\theoremstyle{plain}
\newcommand{\rst@thename}{}
\newtheorem*{rst@plain}{\rst@thename}
\def\rst@name@theorem{Theorem}
\def\rst@name@lemma{Lemma}
\def\rst@name@corollary{Corollary}
\def\rst@name@proposition{Proposition}
\NewEnviron{restatable}[3][]{%
  \def\rst@tmptitle{#1}%
  \ifx\rst@tmptitle\@empty\begin{#2}\BODY\end{#2}\else\begin{#2}[#1]\BODY\end{#2}\fi
  \expandafter\xdef\csname rst@num@#3\endcsname{\csname the#2\endcsname}%
  \expandafter\global\expandafter\let\csname rst@body@#3\endcsname\BODY
  \expandafter\gdef\csname rst@title@#3\endcsname{#1}%
  \expandafter\xdef\csname rst@env@#3\endcsname{#2}%
  \expandafter\gdef\csname #3\endcsname{\@ifstar{\rst@do{#3}}{\rst@do{#3}}}}
\newcommand{\rst@do}[1]{%
  \begingroup
  \edef\rst@tmpenv{\csname rst@env@#1\endcsname}%
  \edef\rst@thename{\csname rst@name@\rst@tmpenv\endcsname\space\csname rst@num@#1\endcsname}%
  \renewcommand{\label}[2][]{}%
  \expandafter\let\expandafter\rst@b\csname rst@body@#1\endcsname
  \expandafter\let\expandafter\rst@t\csname rst@title@#1\endcsname
  \ifx\rst@t\@empty\begin{rst@plain}\rst@b\end{rst@plain}%
  \else\begin{rst@plain}[\rst@t]\rst@b\end{rst@plain}\fi
  \endgroup}
\makeatother
\crefname{hypothesis}{Hypothesis}{Hypotheses}
\crefname{problem}{Open Problem}{Open Problems}
\crefname{claim}{Claim}{Claims}
\crefname{headline}{Theorem}{Theorems}

% ---------- Lamport-style structured proofs (L. Lamport, "How to Write a Proof", 1995) ----------
\newcommand{\pflab}[2]{\ensuremath{\langle#1\rangle}#2}
\newenvironment{steps}{\begin{list}{}{%
    \setlength{\leftmargin}{2.1em}\setlength{\labelwidth}{1.9em}\setlength{\labelsep}{0.2em}%
    \setlength{\itemsep}{2pt}\setlength{\parsep}{1pt}\setlength{\topsep}{2pt}\setlength{\partopsep}{0pt}%
    \renewcommand{\makelabel}[1]{##1\hfil}}}{\end{list}}
\newcommand{\step}[2]{\item[\pflab{#1}{#2}.]}
\newcommand{\qedstep}[2]{\item[\pflab{#1}{#2}.]\textsc{q.e.d.}}
\newcommand{\pf}{\par\textsc{Proof:}\ }
\newcommand{\sref}[2]{\pflab{#1}{#2}}
\newcommand{\Assume}{\textsc{Assume:}\ }
\newcommand{\Prove}{\textsc{Prove:}\ }
\newcommand{\Let}{\textsc{Let:}\ }
\newcommand{\Suffices}{\textsc{Suffices:}\ }
\newcommand{\Case}{\textsc{Case:}\ }

% ---------- macros ----------
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\VS}{\mathrm{VS}}
\newcommand{\err}{\mathrm{err}}
\newcommand{\opt}{\mathrm{OPT}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\LD}{\mathsf{LD}}
\newcommand{\BP}{\mathsf{BP}}
\newcommand{\RL}{\mathsf{RL}}
\newcommand{\ind}{\mathbf{1}}
\newcommand{\eps}{\varepsilon}
\newcommand{\Bayes}{\mathsf{B}}
\newcommand{\Gibbs}{\mathsf{G}}
\newcommand{\Alp}{\mathsf{A}_{\mathrm{LP}}}
\newcommand{\Alin}{\mathsf{A}_{\mathrm{lin}}}
\newcommand{\Aone}{\mathsf{A}_{\ell_1}}
\newcommand{\Hb}{\mathrm{h}}
\newcommand{\KL}{\mathrm{KL}}
\newcommand{\Bern}{\mathrm{Bern}}
\newcommand{\lenETH}[1]{\mathrm{ETH}^{\mathrm{len}}_{#1}}
\newcommand{\LPRG}{\mathrm{LPRG}}
\newcommand{\lenLPRG}[1]{\mathrm{LPRG}^{\mathrm{len}}_{#1}}
\newcommand{\mVC}{m_{\mathrm{VC}}}
\newcommand{\mUC}{m_{\mathrm{UC}}}
\DeclareMathOperator*{\argmin}{arg\,min}

\title{The Price of Bayes-Optimal In-Context Learning}
\hypersetup{pdftitle={The Price of Bayes-Optimal In-Context Learning},
  pdfauthor={Xiaoyu Li}}
\author{Xiaoyu Li\thanks{University of New South Wales, \texttt{xiaoyulics@gmail.com}}}
\date{}

\begin{document}
\maketitle

\begin{abstract}
In-context learning is often explained as implicit Bayesian inference: given labeled examples of a task
drawn from a prior, the learner predicts like the posterior. We determine the computational price of
this explanation for task families whose labels depend on few bits of the task description, such as
quantized models on sparse data, and we compare it with the price of merely learning. The comparison
uses the recent refutations of the Exponential Time Hypothesis by OpenAI and Anthropic.
\begin{itemize}[leftmargin=1.2em]
\item \textbf{Bayesian inference in context is counting.} For $\kappa$-local task families with $N$-bit
descriptions under the uniform prior, the posterior predictive and posterior sampling reduce to
$\#\kappa$-SAT. Without label noise they run in time $\poly(m)\cdot2^{o(N)}$ on contexts of every length $m$
when $\kappa=o((\log N)^{1/4}/\sqrt{\log\log N})$, and label noise is handled by error profiles. A two-variable
gadget gives contexts that are always consistent and whose posterior predictive is $2\#F/(2\#F+1)$ for a
CNF $F$. So approximating the posterior predictive within $1/4$ needs time $2^{(1-\gamma)N}$ at locality
$O(\log N)$ under CNF-SETH, and time $2^{N/\polylog N}$ at locality $3$ under a length form of ETH. At
constant locality, Bayesian inference in context is SAT parameterized by formula length.
\item \textbf{Learning in context is cheap.} The Bayes risk of any class with $N$-bit descriptions is at
most $N/(m+1)$ after $m$ examples. For binarized perceptrons and literal disjunctions on sparse data, the
very families of the lower bounds, a linear program is a polynomial-time in-context learner with
essentially the same sample efficiency. Every $\kappa$-local family is linear over $\sum_{j\le\kappa}\binom
Nj$ local Fourier features, so regression in context learns it from $N^{O(\kappa)}$ examples, in time
polynomial in $N^\kappa$ and the inverse accuracy.
\item \textbf{The average case.} For Goldreich's random local functions, the Bayes risk is at most
$N/(m+1)$, while every in-context learner yields a distinguisher for Goldreich's generator, with the same
running time up to a linear term, whose advantage is $1/2$ minus the risk. Under a local pseudorandom
generator hypothesis with polynomial stretch, polynomial-time in-context learners need polynomially more
examples than the Bayes predictor. Under its length form at linear stretch, which the new algorithms refute
below rate $1/2$, the Bayes predictor of the refutations is optimal up to polylogarithmic factors in the
exponent.
\end{itemize}
For transformers, these bounds limit the length of a chain of thought that computes the posterior
predictive, and they separate Bayes-optimal in-context learning from the regression-type in-context
learning that transformers are known to implement.
\end{abstract}

\newpage
\setcounter{tocdepth}{2}
{\small\tableofcontents}
\newpage

\input{sec1_intro}
\input{sec2_prelim}
\input{sec3_bayes}
\input{sec4_hardness}
\input{sec5_efficient}
\input{sec6_average}
\input{sec7_transformers}
\input{sec8_related}
\input{sec9_open}

\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{vONR{\etalchar{+}}23}

\bibitem[App16]{App16}
Benny Applebaum.
\newblock Cryptographic hardness of random local functions: {S}urvey.
\newblock {\em Computational Complexity}, 25(3):667--722, 2016.

\bibitem[ASA{\etalchar{+}}23]{ASA+23}
Ekin Aky{\"u}rek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou.
\newblock What learning algorithm is in-context learning? {I}nvestigations with
  linear models.
\newblock In {\em 11th International Conference on Learning Representations
  (ICLR)}, 2023.

\bibitem[BCW{\etalchar{+}}23]{BCW+23}
Yu~Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei.
\newblock Transformers as statisticians: {P}rovable in-context learning with
  in-context algorithm selection.
\newblock In {\em Advances in Neural Information Processing Systems 36
  (NeurIPS)}, 2023.

\bibitem[BEHW89]{BEHW89}
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred~K. Warmuth.
\newblock Learnability and the {V}apnik--{C}hervonenkis dimension.
\newblock {\em Journal of the ACM}, 36(4):929--965, 1989.

\bibitem[BF72]{BF72}
J.~M. Barzdin and R.~V. Freivald.
\newblock On the prediction of general recursive functions.
\newblock {\em Doklady Akademii Nauk SSSR}, 206(3):521--524, 1972.
\newblock English translation in Soviet Mathematics Doklady 13:1224--1228.

\bibitem[Bha26]{Bha26}
Deep Bhattacharjee.
\newblock Subexponential weighted counting and exact optimisation.
\newblock Hexagon preprint hexagon:2610.00594v1, dated October 29, 2026.
  \url{https://hexagonmath.org/2610.00594v1}, 2026.

\bibitem[BKW03]{BKW03}
Avrim Blum, Adam Kalai, and Hal Wasserman.
\newblock Noise-tolerant learning, the parity problem, and the statistical
  query model.
\newblock {\em Journal of the ACM}, 50(4):506--519, 2003.

\bibitem[BPBK24]{BPBK24}
Satwik Bhattamishra, Arkil Patel, Phil Blunsom, and Varun Kanade.
\newblock Understanding in-context learning in transformers and {LLM}s by
  learning to learn discrete functions.
\newblock In {\em 12th International Conference on Learning Representations
  (ICLR)}, 2024.

\bibitem[CBL06]{CBL06}
Nicol{\`o} Cesa-Bianchi and G{\'a}bor Lugosi.
\newblock {\em Prediction, Learning, and Games}.
\newblock Cambridge University Press, 2006.

\bibitem[CIP06]{CIP06}
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi.
\newblock A duality between clause width and clause density for {SAT}.
\newblock In {\em 21st Annual IEEE Conference on Computational Complexity
  (CCC)}, pages 252--260, 2006.

\bibitem[{Cla}26]{Cla26}
{Claude (Anthropic)}.
\newblock A $2^{o(n)}$ time algorithm for 3-{SAT}.
\newblock Hexagon preprint hexagon:2610.00577v1, dated October 26, 2026.
  \url{https://hexagonmath.org/2610.00577v1}. Lean development at
  \url{https://github.com/anthropics/formal-math/tree/main/eth}, 2026.

\bibitem[CRTY23]{CRTY23}
Lijie Chen, Ron~D. Rothblum, Roei Tell, and Eylon Yogev.
\newblock On exponential-time hypotheses, derandomization, and circuit lower
  bounds.
\newblock {\em Journal of the ACM}, 70(4):1--62, 2023.

\bibitem[DLSS13]{DLSS13}
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz.
\newblock More data speeds up training time in learning halfspaces over sparse
  vectors.
\newblock In {\em Advances in Neural Information Processing Systems 26 (NIPS)},
  2013.

\bibitem[DV21]{DV21}
Amit Daniely and Gal Vardi.
\newblock From local pseudorandom generators to hardness of learning.
\newblock In {\em 34th Conference on Learning Theory (COLT)}, volume 134 of
  {\em PMLR}, pages 1358--1394, 2021.

\bibitem[FPV18]{FPV18}
Vitaly Feldman, Will Perkins, and Santosh Vempala.
\newblock On the complexity of random satisfiability problems with planted
  solutions.
\newblock {\em SIAM Journal on Computing}, 47(4):1294--1338, 2018.

\bibitem[Gol00]{Gol00}
Oded Goldreich.
\newblock Candidate one-way functions based on expander graphs.
\newblock Technical Report TR00-090, Electronic Colloquium on Computational
  Complexity, 2000.

\bibitem[GTLV22]{GTLV22}
Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant.
\newblock What can transformers learn in-context? {A} case study of simple
  function classes.
\newblock In {\em Advances in Neural Information Processing Systems 35
  (NeurIPS)}, 2022.

\bibitem[HKS94]{HKS94}
David Haussler, Michael Kearns, and Robert~E. Schapire.
\newblock Bounds on the sample complexity of {B}ayesian learning using
  information theory and the {VC} dimension.
\newblock {\em Machine Learning}, 14(1):83--113, 1994.

\bibitem[JVV86]{JVV86}
Mark~R. Jerrum, Leslie~G. Valiant, and Vijay~V. Vazirani.
\newblock Random generation of combinatorial structures from a uniform
  distribution.
\newblock {\em Theoretical Computer Science}, 43:169--188, 1986.

\bibitem[KKMS08]{KKMS08}
Adam~Tauman Kalai, Adam~R. Klivans, Yishay Mansour, and Rocco~A. Servedio.
\newblock Agnostically learning halfspaces.
\newblock {\em SIAM Journal on Computing}, 37(6):1777--1805, 2008.

\bibitem[KMOW17]{KMOW17}
Pravesh~K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer.
\newblock Sum of squares lower bounds for refuting any {CSP}.
\newblock In {\em 49th Annual ACM Symposium on Theory of Computing (STOC)},
  pages 132--145, 2017.

\bibitem[Lam95]{Lam95}
Leslie Lamport.
\newblock How to write a proof.
\newblock {\em The American Mathematical Monthly}, 102(7):600--608, 1995.

\bibitem[Li26]{Li26}
Xiaoyu Li.
\newblock What does the refutation of the {E}xponential {T}ime {H}ypothesis
  mean for learning theory?
\newblock Hexagon preprint hexagon:2610.00613v2.
  \url{https://hexagonmath.org/2610.00613v2}, 2026.

\bibitem[Lit88]{Lit88}
Nick Littlestone.
\newblock Learning quickly when irrelevant attributes abound: A new
  linear-threshold algorithm.
\newblock {\em Machine Learning}, 2(4):285--318, 1988.

\bibitem[MHA{\etalchar{+}}22]{MHPGH22}
Samuel M{\"u}ller, Noah Hollmann, Sebastian~Pineda Arango, Josif Grabocka, and
  Frank Hutter.
\newblock Transformers can do {B}ayesian inference.
\newblock In {\em 10th International Conference on Learning Representations
  (ICLR)}, 2022.

\bibitem[MS24]{MS24}
William Merrill and Ashish Sabharwal.
\newblock The expressive power of transformers with chain of thought.
\newblock In {\em 12th International Conference on Learning Representations
  (ICLR)}, 2024.

\bibitem[O'D14]{ODo14}
Ryan O'Donnell.
\newblock {\em Analysis of {B}oolean Functions}.
\newblock Cambridge University Press, 2014.

\bibitem[{Ope}26]{OAI26}
{OpenAI}.
\newblock The {E}xponential {T}ime {H}ypothesis is false.
\newblock OpenAI Math Release preprint, dated October 17, 2026, revised October
  25, 2026, released October 26, 2026.
  \url{https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf},
  2026.

\bibitem[OW14]{OW14}
Ryan O'Donnell and David Witmer.
\newblock Goldreich's {PRG}: {E}vidence for near-optimal polynomial stretch.
\newblock In {\em 29th IEEE Conference on Computational Complexity (CCC)},
  pages 1--12, 2014.

\bibitem[PAG24]{PAG24}
Madhur Panwar, Kabir Ahuja, and Navin Goyal.
\newblock In-context learning through the {B}ayesian prism.
\newblock In {\em 12th International Conference on Learning Representations
  (ICLR)}, 2024.

\bibitem[PBM21]{PBM21}
Jorge P{\'e}rez, Pablo Barcel{\'o}, and Javier Marinkovic.
\newblock Attention is {T}uring-complete.
\newblock {\em Journal of Machine Learning Research}, 22(75):1--35, 2021.

\bibitem[PV88]{PV88}
Leonard Pitt and Leslie~G. Valiant.
\newblock Computational limitations on learning from examples.
\newblock {\em Journal of the ACM}, 35(4):965--984, 1988.

\bibitem[RPCG23]{RPCG23}
Allan Ravent{\'o}s, Mansheej Paul, Feng Chen, and Surya Ganguli.
\newblock Pretraining task diversity and the emergence of non-{B}ayesian
  in-context learning for regression.
\newblock In {\em Advances in Neural Information Processing Systems 36
  (NeurIPS)}, 2023.

\bibitem[Sch05]{Sch05}
Rainer Schuler.
\newblock An algorithm for the satisfiability problem of formulas in
  conjunctive normal form.
\newblock {\em Journal of Algorithms}, 54(1):40--44, 2005.

\bibitem[SSBD14]{SSBD14}
Shai Shalev-Shwartz and Shai Ben-David.
\newblock {\em Understanding Machine Learning: From Theory to Algorithms}.
\newblock Cambridge University Press, 2014.

\bibitem[vONR{\etalchar{+}}23]{vONR+23}
Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, Jo{\~a}o Sacramento,
  Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov.
\newblock Transformers learn in-context by gradient descent.
\newblock In {\em 40th International Conference on Machine Learning (ICML)},
  volume 202 of {\em PMLR}, pages 35151--35174, 2023.

\bibitem[XRLM22]{XRLM22}
Sang~Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma.
\newblock An explanation of in-context learning as implicit {B}ayesian
  inference.
\newblock In {\em 10th International Conference on Learning Representations
  (ICLR)}, 2022.

\bibitem[Yao82]{Yao82}
Andrew~C. Yao.
\newblock Theory and applications of trapdoor functions.
\newblock In {\em 23rd Annual Symposium on Foundations of Computer Science
  (FOCS)}, pages 80--91, 1982.

\end{thebibliography}

\clearpage
\appendix
\input{app_a_bayes}
\input{app_b_hardness}
\input{app_c_efficient}
\input{app_d_average}

\end{document}