Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors

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 $\nu$ are drawn from a prior $w_{\nu }$, minimizing population log-loss recovers the corresponding Bayesian mixture predictor $\xi ={\sum }_{\nu }{w}_{\nu }\nu$. 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 approximately optimal predictors. This raises a natural question: 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 $\rho$ satisfying $D_{KL}(\xi \Vert \rho )\le \eta$ retains bounded cumulative-expected-squared prediction error. However, while the Bayesian mixture predictor $\xi$ has error $O(\log (1/w_{\mu }))$ in an environment $\mu$, we establish a tight $\Theta (\eta /w_{\mu })$ bound on the excess error of $\rho$ relative to $\xi$. 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 in fact only $O(\eta )$. Furthermore, we establish a distribution-shift theorem for dominated shifts from a training prior $w$ to a test prior $w^{\prime }$, 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}(\xi \Vert \rho )$ could be unbounded. Our theory extends the classical theory of Bayesian and Solomonoff Induction to approximate predictors and characterizes a broad spectrum of prediction behavior. It helps explain the sharp gap between strong empirical benchmark performance and poor worst-case performance in rare environments, while providing quantitative justification for targeted sampling and synthetic data generation designed to protect important but underrepresented task families.