arXiv AI

Large Language Models As Shannon Lossy Compressors Not Solomonoff Induction Estimators: The Singularity Is Not Near Without Symbolic Model Synthesis

The paper argues that Large Language Models (LLMs) do not function as Solomonoff induction estimators because their training objectives—cross‑entropy, negative log‑likelihood, and next‑token prediction—optimize fit to a supplied conditional distribution rather than a program‑weighted universal mixture. It further contends that additional computation alone does not transform these models into optimal predictors without external hyper‑parameter or architectural changes. The authors suggest that neurosymbolic machine learning, exemplified by models such as Fable and Astra, represents a shift toward symbolic model synthesis, moving beyond purely statistical LLMs.

arXiv AI
Aug 12

On Solomonoff Induction in Large Language Models and the Limits of Self-Improving: The Singularity Is Not Near Without Symbolic Model Synthesis

arXiv:2601. 05280v3 Announce Type: replace-cross Abstract: On the one hand, the question of whether large language models (LLMs) are Solomonoff induction estimators has become an explicit question at the intersection of Algorithmic Information Theory (AIT) and Machine Learning (ML) of great interest.

By Hector Zenil
arXiv Machine Learning
Oct 22

Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors

The paper investigates how well practical machine‑learning algorithms approximate Solomonoff’s universal predictor when trained by minimizing log‑loss over diverse datasets. It establishes tight bounds on the worst‑case increase in prediction error caused by approximating the Bayesian mixture predictor, showing that while the excess error can be large in low‑prior environments, it remains bounded on average and under distribution shifts. The authors also extend their analysis to finite‑sample settings relevant to neural networks and Transformers.

By Qian Li, Shang-Hua Teng
arXiv AI
Oct 9

Language Modeling is Monotone Compression

The paper investigates the relationship between large language models (LLMs) and compression, showing that LLMs, modeled as next‑token predictors, are equivalent to monotone (order‑preserving) compression algorithms with an error gap of at most 2. It further proves that this monotonicity is necessary for the equivalence only if cryptographic one‑way functions exist, and derives a cryptographic corollary linking next‑bit pseudoentropy to monotone incompressibility.

By Noam Mazor, Andrew Morgan, Rafael Pass
arXiv Machine Learning
Sep 29

Mentored Decoding: Faster Inference meets Boosting

The paper introduces mentored decoding, a formal framework for lossy speculative decoding that can accelerate inference of autoregressive language models while potentially improving output quality. It connects this inference technique to boosting theory and extends it to all f‑divergences, revealing geometric insights for total variation, simple approximations tied to boosting compliance, and a divergence‑independent data structure enabling efficient optimal parameter queries and mentored distribution construction.

By Vivien Tran-Thien, Richard Nock
arXiv AI
Aug 25

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

The paper introduces F-ICL, a benchmark that measures in‑context algorithmic reasoning in language models by exhaustively enumerating 86 million valid programs of length ≤13 on a Turing‑complete machine and computing the exact posterior under a bounded Levin–Solomonoff prior. Unlike typical benchmarks, F‑ICL provides a distributional reference rather than just answers, allowing the evaluation of models’ inductive priors. Across 105 configurations of models ranging from 0.8 B to 675 B parameters, models achieve up to 92 % accuracy, yet many still deviate from the Bayes‑optimal reference, and the study derives theoretical bounds on cumulative loss for predictors with positive prior weight on the reference.

By Luan Ozelim, Hector Zenil
arXiv Machine Learning
Nov 5

Understanding the Out-of-Distribution Generalization of Chain-of-Thought Reasoning in LLMs

The paper investigates how Chain-of-Thought (CoT) reasoning enables Large Language Models to generalize to out-of-distribution (OOD) tasks by composing reusable in-distribution (ID) atomic steps. It provides a theoretical framework showing that OOD risk depends on the sum of ID sub-task risks, scaled by a factor independent of the number of reasoning steps, and that the estimation error grows sub-linearly with the number of steps. Experiments on Atom-Task and GSM8K datasets confirm that CoT supports short-to-long and compositional generalization, and that explicit state tracking is essential.

By Nuo-Jing Liang, Xiao-Tong Yuan, Pan Zhou