Measuring in-context algorithmic reasoning in language models against an exact Bayes-optimal standard

• URL: http://arxiv.org/abs/2608.01575v1
• Date: Mon, 03 Aug 2026 01:21:44 GMT
• Title: Measuring in-context algorithmic reasoning in language models against an exact Bayes-optimal standard
• Abstract summary: F-ICL is an in-context-learning benchmark for correct inductive inference.<n>We exhaustively enumerate all 1.5 billion programs of length $Lle13$ and compute the Bayes-optimal posterior in closed form.<n>Models answer up to 92% of queries correctly, yet 45 of 46 models yield distributions farther from the optimum than a keystroke reference.
• Score: 0.010742675209112621
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• When Does Few-Shot Prompting Help? A Systematic Empirical Study of Shot-Count Effects Across Model Scale, Architecture, and Output Parsing Robustness [0.0]
  Few-shot prompting, the practice of prepending a small number of input-output demonstration pairs to a query before presenting it to a large language model, is widely adopted in NLP.<n>Yet little systematic work investigates how shot count interacts with model scale, architecture, and output format compliance in classification performance.
  arXiv  Detail & Related papers  (2026-07-25T00:31:40Z)
• What Does a Discrete Diffusion Model Learn? [71.03603607324338]
  discrete diffusion model learns: a denoiser, a score ratio, or a bridge plug-in predictor.<n>We start with a rigorous derivation of the continuous-time Markov chain (CTMC) ELBO for any noising process.<n>Every identity is verified numerically, without approximation, on an exactly solvable model.
  arXiv  Detail & Related papers  (2026-07-06T17:56:11Z)
• The Capability Frontier: Benchmarks Miss 82% of Model Performance [7.258179693117413]
  Existing benchmarks typically report accuracy for a single model on a single run.<n>This systematically understates real-world LLM capabilities, particularly under heterogeneous data distributions.
  arXiv  Detail & Related papers  (2026-06-25T10:20:47Z)
• Automated Proving of Shannon-Type Entropy Inequalities via Fine-Tuned Language Models and Guided Tree Search [50.16356451328644]
  Proving Shannon-type entropy inequalities is a fundamental task in information theory.<n>We investigate whether small-scale large language models, fine-tuned on atomic proof steps, can automate this process.<n>We show that GPT-5.5 solves 1.7% samples under zero-shot prompting while Psitip solves 33.3% samples.
  arXiv  Detail & Related papers  (2026-06-04T05:43:12Z)
• Direct Bethe Free Energy Minimization for Bayesian Neural Network [0.0]
  We propose training Bayesian neural networks by directly minimizing the Bethe free energy rather than maximizing a variational lower bound.<n>On tree-structured factor graphs the Bethe free energy is exact; deterministic layers drop out of the objective and are trained by standard backpropagation.<n>All variants admit a closed-form predictive at MAP-equivalent inference cost, in contrast to ensemble and sampling-based methods.
  arXiv  Detail & Related papers  (2026-05-08T20:12:48Z)
• The Surprising Universality of LLM Outputs: A Real-Time Verification Primitive [0.0]
  CPU-only scoring primitive runs at 2.6 microseconds per token.<n> token rank-frequency distributions converge to the same two- parameter Mandelbrot ranking distribution.<n>We derive a single-pass scoring primitive that composes with model log probabilities when available and degrades to a rank-only mode usable on closed APIs.
  arXiv  Detail & Related papers  (2026-04-28T13:35:31Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  Federated learning enables machine learning models with privacy of participants.<n>There is no differentially private distributed method for training, non-feedback problems.<n>We introduce a new distributed algorithm $alpha$-$sf NormEC$ with provable convergence guarantees.
  arXiv  Detail & Related papers  (2025-02-19T07:10:32Z)
• ProofAug: Efficient Neural Theorem Proving via Fine-grained Proof Structure Analysis [50.020850767257095]
  We propose ProofAug, a procedure that equips LLMs with automation methods at various granularities.<n>Our method is validated on the miniF2F benchmark using the open-source deep-math-7b-base model and the Isabelle proof assistant.<n>We also implement a Lean 4 version of ProofAug that can improve the pass@1 performance of Kimina-Prover-seek-Distill-1.5B from 44.3% to 50.4%.
  arXiv  Detail & Related papers  (2025-01-30T12:37:06Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.