Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors

Introduction

Large language models (LLMs) trained for sequential prediction have acquired a remarkable range of capabilities from vast and diverse data. In recent years, scaling model capacity, expanding the volume and breadth of training data, increasing computational resources [KMI+20], and incorporating real-world human interaction [13] have driven substantial progress, transforming LLMs into increasingly general-purpose systems for problem solving and induction. Given the substantial and rapidly growing resources required to train frontier models, understanding the benefits and limitations of further scaling has become more important than ever, raising a range of fundamental research questions.

Classical learning frameworks, such as semi-supervised learning, PAC learning, and reinforcement learning, typically analyze learning relative to a specified task, data distribution, and hypothesis class. In contrast, a single LLM trained on heterogeneous data can perform a wide range of tasks—including translation, writing, coding, and mathematical reasoning—without task-specific retraining, guided only by instructions or a few demonstrations provided in context. Although pretraining is largely driven by minimizing next-token log loss, the resulting models exhibit capabilities involving generation, abstraction, reasoning, and planning, often without explicit supervision for each capability. Moreover, once trained, such a model can be deployed at a comparatively low marginal cost per inference [2]. LLM training thus distills enormous amounts of data and computation into a reusable neural network whose fixed parameters support adaptive behavior across contexts and tasks. This phenomenon suggests that learning to predict sufficiently rich and heterogeneous sequences can give rise to broad knowledge and generalizable computational abilities. Precisely how such capabilities emerge from a seemingly simple prediction objective, however, remains incompletely understood, and is central to characterizing the fundamental power and limitations of the current LLM paradigm.

Motivating Prior Work. Meta-learning, or learning to learn, provides a conceptual framework for understanding this phenomenon [4]. Meta-learning treats the learning procedure itself as an object of optimization, using experience accumulated across tasks to improve the learning of new tasks [HAMS21]. It involves two levels of learning, either explicitly or implicitly: an inner process learns a particular task from a specified dataset and objective, while an outer process optimizes aspects of the inner process—such as the model class, initialization, or optimization rule—with the aim of reducing the data or computation required to solve new tasks.

One approach is memory-based meta-learning (MBML) [SBB+16], in which a memory-augmented model—an LLM whose context serves as memory, for example—is trained on data drawn from a distribution over tasks using a single optimization loop. The two levels of learning are realized through different mechanisms: the outer process updates the model’s parameters across training tasks, whereas the inner process adapts to an individual task through changes in the model’s memory state. At test time, the parameters remain fixed, and adaptation proceeds through memory dynamics without task-specific parameter updates. In-context learning thus emerges as a learned adaptation procedure implemented through the model’s forward computation.

This MBML framework admits a precise Bayesian characterization [OWR+19, XRLM22]. For a fixed horizon $n$, suppose that each training sequence is generated by first sampling a task $\nu$ from a prior distribution $w$, then sampling data $x_{1:n}$ from $\nu$. Suppose a sufficiently expressive model $\rho_{\theta^*}$ is trained to minimize the population log-loss objective

Then $\rho_{\theta^*}$ behaves as the Bayesian mixture predictor $\xi(x)=\sum_\nu w_\nu\cdot\nu(x)$. In particular,

where $w_\nu(x_{<t}) \propto w_\nu\cdot\nu(x_{<t})$ is the posterior probability of $\nu$. Thus, conditioned on an observed prefix $x_{<t}$, the Bayesian predictor combines the predictions of the candidate tasks according to their posterior probabilities, reflecting both their prior weights and their consistency with the observations. The appeal of the Bayesian perspective lies in its strong prediction guarantee [8]: at test time, $\rho_{\theta^*}$ can achieve efficient in-context adaptation to any task $\mu$ with positive prior weight $w_\mu> 0$:

This provides a principled explanation of in-context learning as amortized Bayesian prediction: training amortizes learning across tasks by encoding an adaptive inference procedure into the forward computation of a neural network. In particular, consider the class of all computable environments¹ endowed with the universal prior $w_\nu= \Theta(2^{-K(\nu)})$, where $K(\nu)$ denotes the Kolmogorov complexity of $\nu$. The resulting single Bayesian predictor becomes Solomonoff universal induction [Sol78, Sol86], which achieves cumulative expected squared prediction error $O(K(\mu))$ simultaneously in every computable environment $\mu$, independently of the prediction horizon. Building on this connection, [3] proposed learning increasingly general predictors by meta-training neural networks on synthetic data generated by computationally bounded environments, represented by universal Turing machines with bounded program lengths and runtimes. Progressively relaxing these bounds while increasing model capacity and training data offers a principled approach toward universal prediction, provided that the corresponding prediction objectives can be optimized sufficiently well. The paper [4] placed this framework within the broader context of algorithmic compression: minimizing sequential log loss can be understood as learning to compress observations by approximating and amortizing Bayesian prediction over their underlying generative mechanisms. Under a universal prior, the resulting predictor favors simpler computational explanations while averaging over all computable hypotheses according to both their simplicity and their consistency with the observations.

Our Main Contributions. The classical theory [Sol78, Sol86, Hut05] focuses on the exact predictor that attains the minimum population log loss. In practice, however, limited model capacity and imperfect optimization—even when training data are abundant—mean that learned models generally only approximate the ideal Bayesian predictor. As emphasized by [4], extending the Bayesian view of meta-learning beyond exact realizability and perfect optimization remains an important open direction. Motivated by this line of work, we take a first step toward understanding the fundamental gap between ideal Bayesian prediction and practical learned predictors by addressing the following central question:

To what extent do the guarantees of the ideal Bayesian predictor continue to hold when practical learning architectures can only approximate it?

In this work, we develop a theory of Bayesian and universal sequential prediction under approximation, characterizing performance and robustness across a broad range of regimes: Environment-Wise Worst-Case Robustness. We show in Theorem 1 that every approximate predictor $\rho$ with excess population log loss at most $\eta$, equivalently $D_{\mathrm{KL}}(\xi\Vert\rho) \leq\eta$, retains a finite bound on its cumulative expected squared prediction error. Specifically, for any environment $\mu$, the error of the ideal Bayesian predictor $\xi$ is $O(\log(1/w_\mu))$, whereas that of $\rho$ is bounded by $O\left(\log1/w_\mu+\eta/w_\mu\right)$. We further show in Theorem 3 that the approximation-dependent term is tight. In particular, for a universal mixture, an error of order $\eta^2_{K(\mu)}$ is attained for infinitely many computable environments $\mu$. We also extend the analysis to two other fundamental measures of prediction error: cumulative KL divergence and cumulative squared Hellinger distance.

Typical Average-Case Robustness: In sharp contrast, we prove in Theorem 4 that, when performance is averaged over environments according to the prior $w$—the canonical average-case measure—the excess prediction error due to approximation is only $O(\eta)$. We show that an analogous average-case bound holds for cumulative KL divergence but not for cumulative squared Hellinger distance.

Distribution-Shift Robustness: Furthermore, we establish a distribution-shift theorem (Theorem 5) for dominated shifts from a training prior $w$ to a test prior $w'$, where $w'_\nu\le Cw_\nu$ for every environment $\nu$ and some $C \ge1$. The resulting error bound is $O(\log C+C\eta)$, thereby interpolating between our average-case and worst-case guarantees.

Finite-Data Robustness: Finally, in § 5, we study predictors learned from finitely many training sequences. We show exponential upper-tail bounds for population KL error, yet its expectation can remain infinite when unseen events receive zero probability. Nevertheless, by using a weaker alternative measure of approximation, we extend our robustness analysis to this setting. In particular, we bound the expected average excess prediction error by the representation and optimization errors plus a finite-sample term that decays exponentially with the number of training sequences.

Taken together, these results provide a broad characterization of robustness to approximation in sequential prediction. They explain the sharp contrast between strong aggregate benchmark performance and poor worst-case performance on rare environments. This sharp distinction between worst-case and average-case behavior helps explain why approximation may have a much milder effect in practice. It may also shed light on the strong empirical performance of learned universal predictors [3, 4] and, more broadly, of LLMs across a wide range of tasks and benchmarks. Our distribution-shift theorem has several implications beyond basic transfer principle for sequential prediction. It provides a quantitative rationale for targeted sampling and synthetic data generation designed to protect important but underrepresented families of tasks. In particular, it provides a theoretical rationale for expecting that augmenting real-world datasets with Universal-Turing-Machine-generated (UTM-generated) data may improve prediction performance on practically important task families, as suggested by [3].

Notations and Preliminaries

We assume familiarity with the basic notions in probability theory and algorithmic information theory, including conditional probability and Turing machines. See, for example, [12] for background. Throughout this paper, $\log$ denotes the base-2 logarithm, while $\ln$ denotes the natural logarithm. Entropy and KL divergence are measured in bits.

Sequence measures and mixtures. Let $\mathcal{X}$ be a finite alphabet with $\lvert\mathcal{X}\rvert\ge2$. Suppose $\mu$ is a probability measures on $\mathcal{X}^{\infty}$ (representing a sequence generative model). We use $\mu(x_{1:n})$ to denote the probability that a sequence sampled from $\mu$ begins with $x_{1:n}$, and $\mu_{1:n}$ to denote the induced distribution on $\mathcal{X}^n$. We denote $x_{<t} := x_{1:t-1}$. Let $\mathcal{M} = \{\nu_1, \nu_2, \ldots\}$ be a countable class of measures. Let $\{w_i > 0\}$ be weights satisfying $\sum_i w_i = 1$. Then, define the mixture $\xi:= \sum_{i=1}^{\infty} w_i \nu_i$. When $\mu= \nu_i$ is a selected measure from $\mathcal{M}$, we write $w_\mu:= w_i$. Note that for every finite string $x$, $\xi(x) \ge w_\mu\mu(x)$.

The universal mixture. Solomonoff [Sol78, Sol86] introduced a universal prior for sequence prediction. Unless stated otherwise, we fix a universal monotone Turing machine $U$ throughout the paper. We say a measure $\nu$ is estimable if there exists a monotone Turing machine that takes an infinite sequence of independent, uniformly random bits and generates a sequence according to $\nu$. Let $K(\nu)$ denote the length of the shortest program for $\nu$ on this machine.

Let $\mathcal{M}_U$ denote the class consisting of all estimable measures. Set

The programs are described in a prefix-free fashion, so Kraft’s inequality gives $0 < Z \le1$, and $w_\nu= \Theta(2^{-K(\nu)})$. The fair-coin measure belongs to $\mathcal{M}_U$, so $\xi_U(x) > 0$ for every finite string $x$. We also use $K(x)$ for the usual prefix-free Kolmogorov complexity of a finite string or integer $x$.

KL divergence. For two measures $\mu$ and $\rho$ and $n \ge1$, define

We use the convention that $0 \log(0/q) = 0$ and $p \log(p/0) = +\infty$ for $p > 0$. The finite-horizon divergences are nondecreasing in $n$, so the supremum is also their limit. The chain rule gives that:

Cumulative prediction error. As in [Sol78], we use cumulative squared prediction error as our primary criterion for evaluating the prediction performance of $\rho$:

To examine the scope of our guarantees across different error criteria, we also consider cumulative squared Hellinger error:

and cumulative KL error:

The following inequalities relate these error criteria.

Robustness under Approximation: Task-wise Guarantee

In this section, we establish a tight task-wise prediction guarantee for a trained model $\rho$ that approximates the Bayesian predictor $\xi$ with KL gap $D_{\mathrm{KL}}(\xi\Vert\rho) \le\eta$. The KL divergence provides the most natural measure of approximation quality because the population log-loss of $\rho$ at horizon $n$ admits the following decomposition, where $H$ denotes the Shannon entropy:

Moreover, $\xi$ minimizes the population loss over all probability measures on $\mathcal{X}^{\infty}$, attaining the minimum value $H(\xi_{1:n})$. Thus, $D_{\mathrm{KL}}(\xi\Vert\rho) \le\eta\Rightarrow D_{\mathrm{KL}}^n(\xi\Vert\rho) \le\eta\Longleftrightarrow\mathcal{L}_n(\rho) \le\min_{\pi}\mathcal{L}_n(\pi) + \eta$.

Environment-Wise Guarantee: Upper Bound

We first extend the classical analysis of [8] by showing that, under a finite KL-divergence, the cumulative squared prediction error remains finite for every environment in $\mathcal{M}$.

The proof is given in Appendix § 8, which bounds the cumulative KL error for every $n$ by

Theorem 1 then follows from Lemma 1 that $S_n(\mu,\rho) \le(\ln2)D_n(\mu\Vert\rho)$ and $\operatorname{Hel}_n(\mu,\rho) \le(\ln2)D_n(\mu\Vert\rho)$. We thus also prove that, up to constant factors, this upper bound extends the cumulative squared Hellinger distance $\operatorname{Hel}(\mu,\rho)$.

Specializing to the universal mixture $\xi_U$ and using the relation $w_\mu= \Theta(2^{-K(\mu)})$, we obtain the following environment-wise prediction-error bound in terms of the Kolmogorov complexity $K(\mu)$.

Environment-Wise Guarantee: Tight Worst-Case Lower Bound

Our next theorem shows that the approximation-dependent term $\eta/w_\mu$ in Theorem 1 is unavoidable and tight up to a constant factor. Remarkably, for the universal mixture, this tightness holds for infinitely many environments in $\mathcal{M}_{\mathrm{U}}$. Throughout this subsection, we restrict attention to the binary alphabet $\mathcal{X} = \{0,1\}$.

Thus, even an arbitrarily small KL-approximation gap can coexist with a cumulative squared prediction error that grows exponentially with the Kolmogorov complexity of the environment. We now describe the high-level idea behind the proof. The complete proof is given in Appendix § 10 and formalizes the following rare-prefix construction.

Rare-prefix construction. The lower bound exploits prefixes that are unlikely under the Bayesian mixture $\xi$, but occur with probability one under a particular environment. For $z \in\{0,1\}^{\infty}$, let $\delta_z$ denote the deterministic environment that outputs $z$. Suppose $\mu= \delta_z$ and that a finite prefix $y$ of $z$ has mixture probability $q := \xi(y)$. We construct $\rho$ by replacing the next $N$ conditional predictions along $z$ after the prefix $y$ with the uniform distribution, while leaving all other predictions unchanged.

Each modified history has probability at most $q$ under $\xi$, and replacing its next-symbol distribution with the uniform distribution incurs at most one bit of conditional KL divergence. Hence, the total KL cost is at most $qN$. Under $\mu$, however, every modified history is visited with probability one, and each modified prediction contributes exactly $1/2$ to the squared prediction error. Taking $N = \lfloor\eta/q \rfloor$ yields the following lemma.

When $q = O(w_\mu)$, it yields an $\Omega(\eta/w_\mu)$ lower bound whenever $\eta/w_\mu$ is sufficiently large. The proof of Theorem 3 identifies infinitely many deterministic environments having prefixes that satisfy this condition. Since $w_\mu= \Theta(2^{-K(\mu)})$, the resulting approximation penalty is $\Omega(\eta2^{K(\mu)})$.

Finally, we can show that Lemma 2 also extends to cumulative KL and squared Hellinger errors. Then by Lemma 1, we have, for every $n \ge1$, $D_n(\mu\Vert\rho) \ge S_n(\mu,\rho)/\ln2$ and $\operatorname{Hel}_n(\mu,\rho) \ge S_n(\mu,\rho)/2$. Thus, our construction can establish similar lower bounds as in Theorem 3 for cumulative KL and squared Hellinger errors.

Robustness under Approximation: Average-Case Analysis

In this section, we show that the environment-wise prediction guarantee under approximation can be sharply improved when performance is averaged across environments. We then establish a distribution-shift theorem for moving from the training prior $w$ to a dominated test prior $w'$. The result interpolates between our average-case and environment-wise guarantees. Before stating the theorems and discussing their implications, we explain the motivation for developing an average-case theory of robustness under approximation. § 3.2 shows that the approximation-dependent term $\eta/w_\mu$ in Theorem 1 is unavoidable in the worst case. For an environment with a small prior weight $w_\mu$, this term can overwhelm the classical $O(\log(1/w_\mu))$ prediction guarantee for the ideal Bayesian predictor.

Such pessimistic worst-case guarantees, however, stand in contrast to the strong empirical performance of learned universal predictors [3, 4] and, more broadly, to the outstanding performance of LLMs across a wide range of tasks and benchmarks. This contrast raises the question of why approximation has a milder effect in practice. Empirical evaluations typically aggregate performance across many tasks or environments, whereas an environment-wise guarantee treats each environment individually. Accordingly, we first study prediction performance averaged over the same prior $w$ that defines the training mixture $\xi$. We show that, in sharp contrast to the worst-case setting, approximation has a substantially milder effect under this average-case criterion. Our distribution-shift theorem can then be used to extend this guarantee to other test distributions.

Sharp Contrast between Typical and Task-Wise Prediction Guarantees

This theorem is a consequence of the following exact average-case decomposition:

Theorem 4 matches the exact prediction-error baseline of the ideal mixture $\xi$: the average cost of replacing $\xi$ with $\rho$ is $S_n(\xi,\rho)$. Together with Theorem 3, this result shows that approximation can preserve aggregate performance while substantially degrading performance on individual tasks.

Remark 1. Note that Theorem 4 cannot be obtained simply by averaging the bound in Theorem 1. Instead, the proof exploits the mixture structure to identify the average excess error exactly. To see this, consider the case when $\mathcal{M}$ is infinite, the following average diverges:

A fundamental differentiation: The role of approximation in Theorem 4 also highlights an interesting distinction between exact Bayesian prediction and its approximate counterpart. The classical theory applies to cumulative squared prediction error, KL error, and Hellinger error. As we show in § 3.1, the task-wise guarantees under approximation extend to all three error criteria. By contrast, the average-case decomposition in Proposition 1 holds only for cumulative squared prediction error and cumulative KL error. For KL error, the chain rule immediately yields the analogous decomposition.

Hence, if $D_{\mathrm{KL}}(\xi\mathbin\Vert\rho)\le\eta$, then

For cumulative squared Hellinger error, neither the analogous decomposition nor a uniform additive $O(\eta)$ excess-error bound relative to $\xi$ holds in general. The mixture predictor $\xi$ need not minimize average squared Hellinger error; a counterexample is given in Appendix § 12.

Remark 2. Prior work has shown that the average gains of knowledge distillation can coexist with degraded performance on underrepresented subgroups and tail classes [11 WNZ+23]. By viewing $\xi$ as the teacher model and $\rho$ as the student model, our results provide a complementary explanation in Bayesian sequential prediction: a small population KL distillation loss controls the student’s average excess prediction error, but can coexist with substantial degradation relative to the teacher in rare environments.

Approximation Robustness under Distribution Shift

The preceding analysis evaluates performance under the training prior $w$. We now consider a different test prior $w'$. Our next theorem shows that the average-case guarantee remains robust when the test prior is dominated by the training prior, in the sense that $w'_\nu\le Cw_\nu$ for every environment $\nu$ and some $C\ge1$. This result has several implications beyond establishing a basic transfer principle for sequential prediction and interpolating between the worst-case and average-case analyses of robustness under approximation. One potentially significant implication is that the theory provides basic support for the argument that augmenting real-world datasets with Universal-Turing-Machine-generated (UTM-generated) data can improve prediction performance on practically important families of tasks, as suggested by [3].

Cumulative KL error satisfies a distribution-shift bound of the same order. Indeed, the KL decomposition and the domination $\xi'\le C\xi$, together with the KL transfer inequality (Lemma 3) used in the proof of Theorem 1, give

Implication I: Rare task families and targeted sampling. Theorem 5 interpolates between average-case and environment-wise guarantees. Taking $w' = w$ and $C = 1$ recovers the average-case upper bound in Theorem 4. At the other extreme, if $w'$ is concentrated on a single environment $\mu$, we may take $C = 1/w_\mu$. Then $\xi' = \mu$, and

Thus, the theorem also recovers the order of the environment-wise bound in Theorem 1.

More generally, let $A \subseteq\mathcal{M}$ be a family of environments with prior mass $w(A) > 0$, and consider evaluation under $w' = w(\cdot\mid A)$. Since $w'_\nu\le w_\nu/w(A)$, we may take $C = 1/w(A)$ and obtain

For this conditional test distribution, the guarantee depends on the total prior mass of the task family.

This suggests a way to improve coverage of an important but underrepresented family. Let $q$ be a probability distribution supported on that family, and define

where $\lambda\in(0,1)$ is the fraction of training mass allocated to $q$. Since $q_\nu\le\widetilde{w}_\nu/\lambda$, any predictor with $D_{\mathrm{KL}}(\widetilde{\xi}\mathbin{\|}\rho) \le\eta$ satisfies

The approximation guarantee for this family therefore depends on its assigned training mass $\lambda$, independently of its rarity under the original prior $w$.

Within this model, the bound provides a quantitative rationale for increasing the training probability assigned to important but underrepresented task families, for example through targeted sampling or synthetic data generation. In particular, it supports augmenting UTM-generated training data with real-world datasets to improve prediction performance on practically important task families, as suggested by [3].

Implication II: Fine-tuning with replay. Replaying pretraining data during adaptation can mitigate forgetting [1, 9]. Theorem 5 can be used to give a population-level analysis of this strategy. Interpret $q$ as the target-task distribution and $w$ as the original pretraining distribution. During fine-tuning, draw a fraction $\lambda$ of sequences from $\xi_q$ and a fraction $1-\lambda$ from $\xi$. The resulting population training distribution is $\widetilde{\xi}=(1-\lambda)\xi+\lambda\xi_q$.

Suppose the fine-tuned predictor $\rho_{\mathrm{ft}}$ approximately minimizes the population log-loss, in that

Both task distributions are dominated by the fine-tuning prior: $q_\nu\le\frac{\widetilde{w}_\nu}{\lambda}$, $w_\nu\le\frac{\widetilde{w}_\nu}{1-\lambda}$. Applying Theorem 5 to each distribution yields the simultaneous guarantees

The first bound controls prediction error on the target distribution, while the second controls error on the original distribution. Since $\xi$ minimizes average squared prediction error under $w$, the second bound also limits the possible increase in average error relative to the predictor before fine-tuning.

For fixed approximation accuracy $\eta$, increasing $\lambda$ tightens the target-distribution bound while weakening the original-distribution bound. The mixing parameter $\lambda$ therefore controls the trade-off between the performance guarantees on the target and original task distributions. Finally, we remark that these guarantees assume that the fine-tuned predictor achieves the stated population approximation accuracy $\eta$.

Implication III: Choice of reference universal Turing machine. Let $U$ and $U'$ be two universal Turing machines. By the invariance theorem, there is a constant $c_{U,U'} \ge0$ such that

for every estimable $\nu$.

Consider the universal priors $w_\nu= 2^{-K_U(\nu)}/Z_U$, $w'_\nu= 2^{-K_{U'}(\nu)}/Z_{U'}$, where $Z_V := \sum_{\nu\in\mathcal{M}}2^{-K_V(\nu)}$. Then we have $w'_\nu/w_\nu= 2^{K_U(\nu)-K_{U'}(\nu)}\cdot Z_U/Z_{U'} \le4^{c_{U,U'}}$. If training uses the mixture $\xi$ induced by $U$ and $D_{\mathrm{KL}}(\xi\Vert\rho)\le\eta$, then test under the prior induced by $U'$ satisfies

Thus, changing the reference machine preserves the form of the average-case guarantee, with constants depending only on the pair of machines, independently of the environment and prediction horizon. These constants may nevertheless be large because their dependence on the compiler overhead is exponential.

Robustness of Learning and Prediction with Finite Data

We now examine whether our prediction guarantees remain robust when the predictor is learned from finitely many samples. Fix a prediction horizon $n$, and let $\rho_m$ be learned from $m$ independent training sequences $\mathcal{D}_m\sim(\xi_{1:n})^{\otimes m}$ by minimizing the empirical log-loss over the hypothesis class $\mathcal{H}$ up to an additive optimization error $\eta_{\mathrm{opt}}\ge0$. In addition to this optimization error, the model class incurs a representation error $\eta_{\mathrm{rep}}:=\min_{\rho\in\mathcal{H}}D_{\mathrm{KL}}(\xi\Vert\rho)$. We consider $\eta_{\mathrm{rep}}+\eta_{\mathrm{opt}}>0$.

We show an exponential upper-tail bound on the population KL error: for every $\gamma>0$, there exist constants $c_\gamma,C_\gamma>0$ such that², for all $m\ge1$,

Nevertheless, this high-probability guarantee need not imply a finite expected KL error. A learned predictor may assign zero probability to an event that has positive population probability but is absent from the training data. Precisely, it is possible that

Despite this difficulty, we show that our squared prediction error guarantees remain meaningful in expectation. It follows from two observations. First, if we characterize the approximation quality with a weaker condition $S_n(\xi,\rho_m)\leq\eta$ instead of $D_{\mathrm{KL}}^n(\xi\Vert\rho_m)\leq\eta$, then there exist constants $c$ and $C$ such that for any $m\geq1$,

which means that the finite-sample contribution to the approximation error decays exponentially with the training sample size. Moreover, one can check that all of our theorems extend from the KL approximation condition to the weaker condition $S_n(\xi,\rho)\leq\eta$, with corresponding changes to the constants. In particular, Theorem 4 and (6) together imply: for any $m\geq1$,

Conclusion

We characterize how approximation affects Bayesian prediction and Solomonoff induction. Our results show that approximation can preserve average performance while substantially degrading performance on individual tasks. The analysis also extends to dominated shifts from the training prior to the test prior and is robust in the finite-sample setting.

An important direction for future work is to develop mitigation strategies that provide stronger guarantees across all tasks simultaneously. We explore initial approaches in Appendices § 15 and § 16.

Another open direction is length generalization. Our finite-sample analysis considers training and test sequences of the same length; extending these guarantees to longer test sequences remains a challenge. One possibility is to combine pretrained predictors with continual learning, using minimum description length principle [5 PH05] to guide adaptation as new observations become available.

Acknowledgments

We thank Xinyu Mao and Guangxu Yang for early discussions, and Marcus Hutter for his comments. We used AI tools for polishing the language, searching the literature, and developing and drafting all proofs. We have checked and revised all proofs and take full responsibility for the whole content of this work.

Proof of Theorem 1

Write $Q=wP+(1-w)V$ for a probability distribution $V$, and define

on the support of $Q$, with $\alpha(x)=0$ elsewhere. Then $0\le\alpha\le1$ and $\mathbb{E}_Q\alpha=w$. Introduce an auxiliary binary variable $Z$. Under $\widetilde{Q}$, let $X\sim Q$ and

Thus $\widetilde{Q}(X\in\cdot\mid Z=1)=P$. Define $\widetilde{R}$ using the same conditional law of $Z$ given $X$, but with $X\sim R$, and put

Finiteness of $D_{\mathrm{KL}}(Q\mathbin\Vert R)$ implies $0<r<1$. Let $R_1$ denote the conditional law of $X$ under $\widetilde{R}$ given $Z=1$, and define $R_0$ analogously. One can check that

The conditional kernel from $X$ to $Z$ is the same under the two joint distributions. Hence

Applying the chain rule in the other direction gives

where

is binary KL divergence. Moreover,

and therefore

Together with (8), this yields

We next use the inequality

To verify it, first observe that

If $r \ge w$, the second term is nonnegative, and (10) follows. If $r < w$, the desired inequality is equivalent to

For fixed $w$, let

This function is strictly convex on $(0,w)$, and its stationary point is

Writing $a:=1-w$, direct substitution gives

Now $G(0)=G(1)=0$ and

while

The numerator of $G''$ after taking a common denominator is affine and strictly decreasing, positive at $a=0$ and negative at $a=1$. Thus $G'$ first increases and then decreases. Since $G'(0)=0$ and $G'(a)\to-\infty$ as $a\uparrow1$, it is initially positive and then crosses zero exactly once. Hence $G$ first increases and then decreases to $G(1)=0$. It follows that $G(a)\ge0$, proving (10).

Let $c:=e/(e-1)$. Substituting (10) into (9), and using $d_B(w\mathbin{\|}r)\le D_{\mathrm{KL}}(Q\mathbin{\|}R)$, gives

Proof of Theorem 1. Fix $n$, and apply Lemma 3 to

Since $\xi\ge w_\mu\mu$,

Applying Lemma 1 and taking the supremum over $n$ gives the conclusion. □

Proof of Lemma 2

Let $m := |y|$ and set $N := \lfloor\eta/q \rfloor$. Note that

For $0 \le\ell< N$, write

We construct a measure $\rho$ on $\{0,1\}^{\infty}$ as follows: set

and let $\rho$ agree with $\xi$ at every other history of positive $\xi$-probability. At histories of zero $\xi$-probability, choose an arbitrary conditional distribution.

For any distribution $p$ on $\{0,1\}$,

where $H(p)$ is the binary entropy. Hence, for every $n$, the chain rule gives

Taking the supremum over $n$ yields

The modified conditionals occur only after the prefix $y$. Therefore, the first $m$ predictions along $z$ are unchanged, and

At each history $h_\ell$, the next-symbol distribution under $\mu= \delta_z$ is a point mass, whereas $\rho(\mathord\cdot\mid h_\ell) = \operatorname{Bern}(1/2)$. Thus

Consequently,

This finishes the proof.

Proof of Theorem 3

We remark Lemma 2 already gives a nearly exponential lower bound in the universal setting. Specifically, for every $n$, since $\sum_{h \in\{0,1\}^n} \xi_U(h) = 1$, there is a string $h_n \in\{0,1\}^n$ such that $\xi_U(h_n) \le2^{-n}$. Let $\mu_n := \delta_{h_n0^\infty}$. We have

The first inequality is by combining (i) $\xi_U(h_n) \le2^{-n}$ and (ii) $\xi_U(h_n) \ge w_{\mu_n} = \Theta(2^{-K(\mu_n)}).$ Lemma 2 therefore yields, for all sufficiently large $n$,

This matches the upper bound in Theorem 1 up to a polynomial factor. We next show that this factor can be removed.

We will make use of the following coding theorem.

Proof of Theorem 3. For $m\ge1$, define

Note that the set $C$ is prefix-free. Since $|C_m|=2^m$, a counting argument gives a string $y_m\in C_m$ satisfying $K(y_m)\ge m$. Here

is the prefix Kolmogorov complexity of the string $y$. Denote $\mu_m:=\delta_{y_m0^\infty}$ the deterministic measure outputting $y_m0^\infty$. Note that $\mu_m$ is estimable, as it can hard-code the self-delimiting program generating $y_m$ and then output zeros forever. In addition, we have $K(\mu_m)\le K(y_m)+O(1)$.

Let $M_U$ be the Solomonoff prior

which is semicomputable. Since $C$ is prefix-free, $\sum_{y\in C}M_U(y)\le1$. By letting $P(y)=M_U(y)\cdot1_{y\in C}$, Lemma 4 therefore gives

Furthermore, a standard fact in algorithmic information theory (see e.g. Section 1.2.5 in [8]) says that $\xi_U(y)=O(M_U(y))$. Thus,

In particular,

Fix $\eta>0$. Applying Lemma 2 with $\mu=\mu_m$ and $y=y_m$ gives: there exists a universal constant $C_U>0$, such that

for infinitely many $m$. □

Proof of Proposition 1

For a history $h$ with $\xi(h)>0$, let $w(\mu\mid h):=w_\mu\mu(h)/\xi(h)$ denote the posterior weight of $\mu$. For any symbol $a\in\mathcal{X}$,

The variance decomposition gives

Multiplying by $\xi(h)$ and using $\xi(h)w(\mu\mid h)=w_\mu\mu(h)$ yields

Summing over all histories $h\in\mathcal{X}^{t-1}$, all symbols $a\in\mathcal{X}$, and all $1\leq t\leq n$ gives

A counterexample for squared Hellinger error

Let $\mu_1=\delta_{1^\infty}$ and $\mu_0=\delta_{0^\infty}$, with prior weights $w_1=3/4$ and $w_0=1/4$, respectively. Write $q_r=r\mu_1+(1-r)\mu_0$, so that $\xi=q_{3/4}$. After the first symbol $x_1$, every $q_r$ with $r\in(0,1)$ predicts the remaining sequence perfectly. Thus its averaged cumulative squared Hellinger error is

This is minimized at

Hence $\xi$ is not a minimizer, ruling out the analogous decomposition into its average error and a nonnegative approximation term. Moreover, let $\rho_u=q_{3/4-u}$ for $u>0$ sufficiently small. Since $\rho_u$ and $\xi$ differ only in their first-step predictions,

However,

Thus, no finite constant $C$ can make $R(3/4-u)\leq R(3/4)+C\eta_u$ hold for all sufficiently small $u$.

Proof of Theorem 5

By Proposition 1, we have

and

In the following, we will show that

which concludes the proof.

The assumption $w'_\nu\le Cw_\nu$ implies that, for every finite history $h$,

In particular, $D_{\mathrm{KL}}^n(\xi'\|\xi)\le\log C$. Hence, by Lemma 1, we have

Next, define

Using $\xi'(h)\le C\xi(h)$ and Lemma 1, we obtain

Expanding the square, we obtain

where

By the Cauchy–Schwarz inequality,

It follows that

Together with (13) and (14), this yields (12).

Proofs for Section 5

Fix a horizon $n$. Write $P := \xi_{1:n}$, $H := H(P)$, and $a := \eta_{\mathrm{rep}} + \eta_{\mathrm{opt}}$. Let $\rho^* \in\mathcal{H}$ denote the predictor achieving $D_{\mathrm{KL}}^n(\xi\Vert\rho^*) = \eta_{\mathrm{rep}}$. Write $\widehat{R}_m$ for the empirical log-loss, so that $\widehat{R}_m(\rho_m) \le\widehat{R}_m(\rho^*) + \eta_{\mathrm{opt}}$.

Proof of (4). Let $\widehat{P}_m$ be the empirical distribution of the training sequences. For $0 < \tau< 1$, define

Write $d := |\operatorname{supp}(P)|$ and

Hoeffding’s inequality and a union bound give

Conditioned on $\overline{E}_{m,\tau}$, the nonnegativity of log-loss and approximate empirical optimality imply

Thus,

For any $\gamma>0$, choose $\tau>0$ small enough that the second term is at most $\gamma$. The claim follows with $C_\gamma=2d$ and $c_\gamma=2\tau^2p_{\min}^2$.

Example establishing (5). Take $n=1$, $P=\operatorname{Bernoulli}(1/2)$, and $\mathcal{H}$ consisting of $\rho_0:=\delta_0$ and $\rho_1:=\operatorname{Bernoulli}(1/4)$. On the event that all $m$ training observations are zero, which has probability $2^{-m}$, exact empirical log-loss minimization selects $\rho_m=\rho_0$. Since $D_{\mathrm{KL}}(P\Vert\rho_0)=+\infty$, the expected KL error is infinite for every finite $m$. Padding deterministic zeros extends the example to any fixed $n$.

Proof of (6). Recall $a=\eta_{\mathrm{rep}}+\eta_{\mathrm{opt}}$, let $\gamma_a := (1/\ln2-1)a$. By $0\le S_n\le2n$ and $S_n(\xi,\rho_m)\le(\ln2)D_{\mathrm{KL}}^n(\xi\Vert\rho_m)$, we have

Theorems 4, 5, and 1 under squared-error approximation. Suppose $S_n(\xi,\rho)\le\eta$. By Proposition 1, we have

In the proof of Theorem 5, by almost the same argument except adjusting (14) to $B_n\le C\eta$, we will get

Letting $w'$ concentrate on a single environment $\mu$, we recover Theorem 1, up to constants:

Theorem 3 under squared-error approximation. By Lemma 1,

Thus Theorem 3, applied with budget $\eta/\ln2$, implies the same infinite-horizon lower bound under squared-error approximation, up to constants.

Mitigation With Category Information

The worst-case bounds of order $\Theta(n/w_\mu)$ in Theorem 1 arise when approximation is controlled only through a single aggregate KL bound $D_{\mathrm{KL}}(\xi\|\rho) \leq\eta$. When available, training-time task category information enables separate control of approximation errors within each task category, potentially improving category-wise prediction performance. Notably, the learned predictor does not require category tags at test time.

Let $\mathcal{T} = \{T_1,\ldots,T_g\}$ be a finite set of categories, with $\operatorname{tag} : \mathcal{M} \to\mathcal{T}$ defining the partition $\mathcal{M}_j := \{\mu\in\mathcal{M} : \operatorname{tag}(\mu) = T_j\}$. Write

Thus $\xi= \sum_{j=1}^{g} p_j \xi_j$. Recall that, by Theorem 1, an aggregate approximation guarantee $D_{\mathrm{KL}}(\xi\|\rho) \leq\eta$ gives

Direct control of the category-wise KL error avoids this inverse-category-mass amplification. The following guarantee follows immediately from Lemma 1 and Proposition 1.

To control the category-wise approximation errors $D_{\mathrm{KL}}^n(\xi_j\|\rho)$, one may minimize the following worst-category excess log-loss, or a suitable surrogate:

Higher moments of sequence log-loss

One may instead minimize the following sample-only training objective:

Fix a horizon $n$. Let $q$ be the minimizer of $\mathcal{L}_p$ among all probability distributions on $\mathcal{X}^n$. Suppose the predictor $\rho$ satisfies

Proof. Let $\Omega_n := \{x \in\mathcal{X}^n : \xi(x) > 0\}$ be the support of $\xi_{1:n}$. Since $\xi\ge w_\mu\mu$, the distribution $\mu_{1:n}$ is also supported on $\Omega_n$. The minimizer $q$ assigns all its mass to $\Omega_n$, since otherwise, renormalizing its restriction to $\Omega_n$ would strictly decrease the objective. If $|\Omega_n| = 1$, then the result follows immediately from

on the unique point $x \in\Omega_n$. We henceforth assume $|\Omega_n| \ge2$. In this case, $q(x) \in(0,1)$ for every $x \in\Omega_n$.

Write $\ell(x) := -\log q(x)$. Consider the Lagrangian

Since the minimizer is an interior point, the first-order condition gives

Thus, setting $c_n := \lambda\ln2/p$, we obtain

Since $\xi(x)>0$, $\ell(x)>0$, and $q(x)>0$, we also have $c_n>0$. Summing (16) over $x$ gives

Since $u\mapsto u^{(p-1)/p}$ is concave, Jensen’s inequality gives

We next show that $q$ dominates $\xi$. If $\ell(x)\ge1$, then (16) gives

If $\ell(x)<1$, then $q(x)>1/2$, and hence

The two cases imply

We now use the approximate optimality of $\rho$. Define $z(x) := \log(q(x)/\rho(x))$. Since $\mathcal{L}_p(\rho_{1:n}) < \infty$, it has that $\rho(x) > 0$ on $\Omega_n$, and thus

For $p \ge2$ and $u,v \ge0$, we have

Indeed, when $v=u+s$ with $s\ge0$, subtracting the right-hand side from the left-hand side gives a function $F_+(s)$ satisfying $F_+(0)=0$ and

When $v=u-s$ with $0\le s\le u$, the corresponding function satisfies $F_-(0)=0$ and

Applying (18) with

we obtain

By (16),

It follows from the approximation guarantee that

Since $\xi(x)\ge w_\mu\mu(x)$, (17) and (19) imply

and

Therefore, by Holder’s inequality,

By applying Lemma 1, we obtain the lemma. □