Measuring in-context algorithmic reasoning in language models against an exact Bayes-optimal standard
2026-08-03 • Machine Learning
Machine LearningArtificial Intelligence
AI summaryⓘ
The authors created a new test called F-ICL to check if large language models truly do algorithmic reasoning or just guess based on patterns. They used a huge set of simple computer programs and a perfect mathematical way to know the best answer for each test. When they checked many language models, they found that although models got many answers right, they didn’t match the perfect reasoning pattern and sometimes got more confused with more examples. The authors also noticed that bigger models or newer versions didn’t get closer to perfect reasoning. They made F-ICL available for others to use and test their models.
large language modelsalgorithmic reasoningin-context learningBayes-optimal posteriorLevin-Solomonoff priorTuring-complete machineinductive inferencebenchmarkalgorithmic mixturemodel evaluation
Authors
Hector Zenil, Luan Ozelim
Abstract
Whether large language models perform genuine algorithmic reasoning or mere pattern completion is hard to test, because most benchmarks lack a ground truth for correct inductive inference. We introduce F-ICL, an in-context-learning benchmark that supplies one exactly. Using the Turing-complete machine F, complement-symmetrised into sF to remove output-polarity bias, we exhaustively enumerate all 1.5 billion programs of length $L\le13$ and compute the Bayes-optimal posterior in closed form under a bounded universal (Levin--Solomonoff) prior; models are scored by how closely their served distributions approach it at matched evidence. Each task is paired with its bitwise complement, on which the optimum scores identically, so an original-twin gap isolates the model's inductive bias. Across 105 serving configurations spanning 37 open models (0.8B--675B) and frontier systems from four laboratories, models answer up to 92\% of queries correctly, yet 45 of 46 models yield distributions farther from the optimum than a keystroke reference, and their behaviour is bracketed by low-order prefix statistics fitted only on visible evidence. That reference is itself an algorithmic mixture, induced by a print-only machine with no loops, so the panel's implied measure sits closer to a loop-free mixture than to the loop-bearing optimum, independently of the reference machine. Updating is also non-monotone, which no prior explains: a Bayes-rational solved set can only grow in this realisable, noiseless setting, yet added examples produce $6{,}545$ solved-to-unsolved transitions against $13{,}702$ gains. The gap is not predicted by accuracy (Spearman $ρ=-0.19$, $p=0.21$), does not close with scale or across frontier generations in the serving modes that expose distributions, and is widened by instruction and reasoning post-training. F-ICL is released as an open, reproducible benchmark and toolkit.