Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors
Abstract
Why large language models trained via log-loss minimization over massive and diverse datasets exhibit broad capabilities and generalizable skills is not yet fully understood. Grau-Moya et al. (ICML 2024) offer a conceptual explanation through the lens of meta-learning: if sequence-generating environments ν are drawn from a prior wν, minimizing population log-loss recovers the corresponding Bayesian mixture predictor ξ=∑νwνν. In the idealized limit in which w is a universal prior, the optimal predictor corresponds to Solomonoff universal induction. Practical machine learning algorithms, however, generally produce only \emph{approximately} optimal predictors. This raises a natural question: \emph{Does the prediction performance remain robust under approximation}? In this paper, we first provide a tight bound on the worst-case effect of approximation on prediction error. We show any predictor ρ satisfying DKL(ξ|ρ)≤ η retains bounded cumulative-expected-squared prediction error. However, while the Bayesian mixture predictor ξ has error O(log(1/wμ)) in an environment μ, we establish a tight Θ(η/wμ) bound on the excess error of ρ relative to ξ. Thus, approximation can substantially degrade performance in environments assigned small prior probability. In sharp contrast, when environments are averaged according to prior w, we prove that the excess prediction error is only O(η). Furthermore, we establish a distribution-shift theorem for dominated shifts from a training prior w to a test prior w', interpolating our average-case and worst-case guarantees. Finally, we extend our robustness analysis to a finite-sampling setting relevant to learning universal predictors with neural networks and Transformers, where DKL(ξ|ρ) could be unbounded. [For the full abstract, see the paper.]
Related
- Four Extensions of the Universal Law of Robustness: Log-Concave Covariates, Heterogeneous Mixtures, Vector-Valued Predictors, and Markovian Data
- Solomonoff Induction and Singular Integrals
- What Can Language Models Inherit from Solomonoff Induction? Limits, Attainable Properties, and What Served Conditionals Reveal
- Solomonoff induction of selected bits and online classification
- Universal recovery in approximate quantum error correction
BibTeX
@misc{li2026approximate,
title = {{Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors}},
author = {Qian Li and Shang-Hua Teng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29289},
eprint = {2610.29289},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29289},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors
AU - Qian Li
AU - Shang-Hua Teng
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29289
UR - https://arxiv.org/abs/2610.29289
AB - Why large language models trained via log-loss minimization over massive and diverse datasets exhibit broad capabilities and generalizable skills is not yet fully understood. Grau-Moya et al. (ICML 2024) offer a conceptual explanation through the lens of meta-learning: if sequence-generating environments ν are drawn from a prior w_ν, minimizing population log-loss recovers the corresponding Bayesian mixture predictor ξ=∑_νw_νν. In the idealized limit in which w is a universal prior, the optimal predictor corresponds to Solomonoff universal induction. Practical machine learning algorithms, however, generally produce only \emph{approximately} optimal predictors. This raises a natural question: \emph{Does the prediction performance remain robust under approximation}? In this paper, we first provide a tight bound on the worst-case effect of approximation on prediction error. We show any predictor ρ satisfying D_KL(ξ|ρ)≤ η retains bounded cumulative-expected-squared prediction error. However, while the Bayesian mixture predictor ξ has error O(log(1/w_μ)) in an environment μ, we establish a tight Θ(η/w_μ) bound on the excess error of ρ relative to ξ. Thus, approximation can substantially degrade performance in environments assigned small prior probability. In sharp contrast, when environments are averaged according to prior w, we prove that the excess prediction error is only O(η). Furthermore, we establish a distribution-shift theorem for dominated shifts from a training prior w to a test prior w', interpolating our average-case and worst-case guarantees. Finally, we extend our robustness analysis to a finite-sampling setting relevant to learning universal predictors with neural networks and Transformers, where D_KL(ξ|ρ) could be unbounded. [For the full abstract, see the paper.]
ER -