HEXAGONbeta

The Price of Bayes-Optimal In-Context Learning

Primarily AI-generated textHuman understanding: some partscs.CC — Computational Complexitycs.AI — Artificial Intelligencecs.DS — Data Structures and Algorithmsstat.TH — Statistics Theory

Contributed by Xiaoyu Li ↗

Version 1 / Nov 06, 2026 / CC BY 4.0

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. Bayesian inference in context is counting. For κ\kappa-local task families with NN-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)⋅2o(N)\mathrm{poly}(m)\cdot 2^{o(N)} on contexts of every length mm when κ=o((log⁡N)1/4/log⁡log⁡N)\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)2\#F/(2\#F+1) for a CNF FF. So approximating the posterior predictive within 1/41/4 needs time 2(1−γ)N2^{(1-\gamma)N} at locality O(log⁡N)O(\log N) under CNF-SETH, and time 2N/polylog N2^{N/\mathrm{polylog}\,N} at locality 33 under a length form of ETH. At constant locality, Bayesian inference in context is SAT parameterized by formula length. Learning in context is cheap. The Bayes risk of any class with NN-bit descriptions is at most N/(m+1)N/(m+1) after mm 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 ∑j≤κ(Nj)\sum_{j\le\kappa}\binom{N}{j} local Fourier features, so regression in context learns it from NO(κ)N^{O(\kappa)} examples, in time polynomial in NκN^\kappa and the inverse accuracy. The average case. For Goldreich's random local functions, the Bayes risk is at most N/(m+1)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/21/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/21/2, the Bayes predictor of the refutations is optimal up to polylogarithmic factors in the exponent. 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.

Provenance statement

This work was produced on 30 October 2026 with Claude Opus 5.5 (Anthropic), working as an agent in Claude Code, and revised on 6 November 2026. The submitting contributor asked Claude to propose questions that build on the contributor's paper "What Does the Refutation of the Exponential Time Hypothesis Mean for Learning Theory?" (hexagon:2610.00613) and left the choice among them to Claude. Claude chose the question, proved the results and wrote the text. Separate Claude agents searched the literature, checked the citations against their sources, and audited every proof; the audit's findings, on the hypotheses of the average-case and transformer sections and on the context sizes in Theorem 4.4(b), were applied. The gadgets, the linearization and the risk bounds were checked by brute force on small instances; the scripts are in anc/. The paper uses the refutations of ETH by OpenAI and Anthropic, and the results of the contributor's earlier paper, only through statements quoted as Imported Theorems. No part of this paper is formally verified.

Tools used

Anthropic
Claude OpusVersion 5.5
Python
Python 3 with NumPy and SciPy (checks in anc/)

References

  1. Benny Applebaum. Cryptographic hardness of random local functions: S urvey. Computational Complexity , 25(3):667--722, 2016.
  2. Ekin Aky ü rek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? I nvestigations with linear models. In 11th International Conference on Learning Representations (ICLR) , 2023.
  3. Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: P rovable in-context learning with in-context algorithm selection. In Advances in Neural Information Processing Systems 36 (NeurIPS) , 2023.
  4. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the V apnik-- C hervonenkis dimension. Journal of the ACM , 36(4):929--965, 1989.
  5. J. M. Barzdin and R. V. Freivald. On the prediction of general recursive functions. Doklady Akademii Nauk SSSR , 206(3):521--524, 1972. English translation in Soviet Mathematics Doklady 13:1224--1228.
  6. Deep Bhattacharjee. Subexponential weighted counting and exact optimisation. Hexagon preprint hexagon:2610.00594v1, dated October 29, 2026. https://hexagonmath.org/2610.00594v1, 2026.hexagon
  7. Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM , 50(4):506--519, 2003.
  8. Satwik Bhattamishra, Arkil Patel, Phil Blunsom, and Varun Kanade. Understanding in-context learning in transformers and LLM s by learning to learn discrete functions. In 12th International Conference on Learning Representations (ICLR) , 2024.
  9. Nicol ò Cesa-Bianchi and G á bor Lugosi. Prediction, Learning, and Games . Cambridge University Press, 2006.
  10. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT . In 21st Annual IEEE Conference on Computational Complexity (CCC) , pages 252--260, 2006.
Show all 38 referencesShow fewer references
  1. Claude (Anthropic) . A 2o(n)2^{o(n)} time algorithm for 3- SAT . Hexagon preprint hexagon:2610.00577v1, dated October 26, 2026. https://hexagonmath.org/2610.00577v1. Lean development at https://github.com/anthropics/formal-math/tree/main/eth, 2026.hexagon
  2. Lijie Chen, Ron D. Rothblum, Roei Tell, and Eylon Yogev. On exponential-time hypotheses, derandomization, and circuit lower bounds. Journal of the ACM , 70(4):1--62, 2023.
  3. Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. More data speeds up training time in learning halfspaces over sparse vectors. In Advances in Neural Information Processing Systems 26 (NIPS) , 2013.
  4. Amit Daniely and Gal Vardi. From local pseudorandom generators to hardness of learning. In 34th Conference on Learning Theory (COLT) , volume 134 of PMLR , pages 1358--1394, 2021.
  5. Vitaly Feldman, Will Perkins, and Santosh Vempala. On the complexity of random satisfiability problems with planted solutions. SIAM Journal on Computing , 47(4):1294--1338, 2018.
  6. Oded Goldreich. Candidate one-way functions based on expander graphs. Technical Report TR00-090, Electronic Colloquium on Computational Complexity, 2000.
  7. Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? A case study of simple function classes. In Advances in Neural Information Processing Systems 35 (NeurIPS) , 2022.
  8. David Haussler, Michael Kearns, and Robert E. Schapire. Bounds on the sample complexity of B ayesian learning using information theory and the VC dimension. Machine Learning , 14(1):83--113, 1994.
  9. Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science , 43:169--188, 1986.
  10. Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing , 37(6):1777--1805, 2008.
  11. Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP . In 49th Annual ACM Symposium on Theory of Computing (STOC) , pages 132--145, 2017.
  12. Leslie Lamport. How to write a proof. The American Mathematical Monthly , 102(7):600--608, 1995.
  13. Xiaoyu Li. What does the refutation of the E xponential T ime H ypothesis mean for learning theory? Hexagon preprint hexagon:2610.00613v2. https://hexagonmath.org/2610.00613v2, 2026.hexagon
  14. Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning , 2(4):285--318, 1988.
  15. Samuel M ü ller, Noah Hollmann, Sebastian Pineda Arango, Josif Grabocka, and Frank Hutter. Transformers can do B ayesian inference. In 10th International Conference on Learning Representations (ICLR) , 2022.
  16. William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In 12th International Conference on Learning Representations (ICLR) , 2024.
  17. Ryan O'Donnell. Analysis of B oolean Functions . Cambridge University Press, 2014.
  18. OpenAI . The E xponential T ime H ypothesis is false. OpenAI Math Release preprint, dated October 17, 2026, revised October 25, 2026, released October 26, 2026. https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf, 2026.link
  19. Ryan O'Donnell and David Witmer. Goldreich's PRG : E vidence for near-optimal polynomial stretch. In 29th IEEE Conference on Computational Complexity (CCC) , pages 1--12, 2014.
  20. Madhur Panwar, Kabir Ahuja, and Navin Goyal. In-context learning through the B ayesian prism. In 12th International Conference on Learning Representations (ICLR) , 2024.
  21. Jorge P é rez, Pablo Barcel ó , and Javier Marinkovic. Attention is T uring-complete. Journal of Machine Learning Research , 22(75):1--35, 2021.
  22. Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. Journal of the ACM , 35(4):965--984, 1988.
  23. Allan Ravent ó s, Mansheej Paul, Feng Chen, and Surya Ganguli. Pretraining task diversity and the emergence of non- B ayesian in-context learning for regression. In Advances in Neural Information Processing Systems 36 (NeurIPS) , 2023.
  24. Rainer Schuler. An algorithm for the satisfiability problem of formulas in conjunctive normal form. Journal of Algorithms , 54(1):40--44, 2005.
  25. Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms . Cambridge University Press, 2014.
  26. Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, Jo ã o Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In 40th International Conference on Machine Learning (ICML) , volume 202 of PMLR , pages 35151--35174, 2023.
  27. Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit B ayesian inference. In 10th International Conference on Learning Representations (ICLR) , 2022.
  28. Andrew C. Yao. Theory and applications of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 80--91, 1982.

Version history

  1. v1 · 37 pagesSubmitted by Xiaoyu LiInitial depositCurrentNov 05, 2026