- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper studies whether the prediction guarantees of ideal Bayesian predictors remain robust under approximation. Using Bayesian sequential prediction and Solomonoff induction as theoretical frameworks, it derives guarantees for approximate predictors.
Critical strengths
This paper goes beyond the idealized assumption of exact Bayesian prediction by explicitly accounting for approximation error. Section 5 also presents a seemingly interesting result, showing that the expected squared prediction error can remain controlled even when expected KL divergence is infinite.
Critical weaknesses
Overall, the authors position this paper as a theoretical work, yet it falls far below the expected bar for such a contribution. I could not identify a new analytical framework, interesting findings, or general and substantive theorems. The assumptions are classical and clearly unsuitable for modeling LLMs, while the conclusions are largely incremental, can be found even in many classical machine learning textbooks, and are clearly not unique to LLMs. Even I am not an expert in machine learning thoery, I am quite confident that the paper should be rejected.
The presentation is also far below the expected bar. I cannot determine what the authors intend to convey from the abstract, and the introduction further adds to the confusion through uninformative, ambiguous, and excessively verbose language.
The discussion also lacks conceptual precision. For example, semi-supervised learning, PAC learning, and reinforcement learning are presented in parallel as comparable “classical learning frameworks.” PAC learning is a theoretical framework, whereas semi-supervised learning and reinforcement learning refer to different learning paradigms or settings.
Although the paper is motivated by LLMs, its analysis is based on a Bayesian framework that assumes the learned model is close to the Bayesian optimum. This framework does not appear suitable for characterizing overparameterized models, and I seldom see such a Bayesian assumption used in serious LLM-related theoretical work. It is also uncommon to model complex LLM tasks using universal Turing machines.
I interpret Theorem 1 as showing that, even though the overall error is small, the error on a particular task can be large. I believe that general nonasymptotic theory, such as concentration inequalities, has already established this phenomenon in statistics. The extension of Hutter’s original theory is also incremental and relies on an additional Bayesian assumption that is itself questionable.
Theorem 2 also does not seem to provide a substantive new result, since the Solomonoff prior is defined to assign smaller prior probabilities to more complex environments. This prior was not proposed by the authors and should instead be viewed as an assumption. I am also concerned about whether it is an appropriate assumption for LLMs.
I also did not find any particularly novel findings in Theorems 3–6. The existence of corner cases, lower average-case error, and the impact of distribution shifts have been widely discussed in classical machine learning. I cannot identify any adjustment specifically made for LLMs or any findings that are unique to LLMs. I further examined Section 5 and likewise found no particularly interesting results.
The authors suggest replaying pretraining data during fine-tuning to mitigate forgetting. First, much of the pretraining data may be of low quality, so it is unclear why such information should be preserved. Could replaying the pretraining data make fine-tuning ineffective? Second, the connection between this suggestion and the main claim of the paper is unclear. This further raises questions about the feasibility of the Bayesian assumption adopted in the analysis.
Questions for authors
Please see the Critical Weaknesses above
4 comments
Thank you for the response. After reading it and the revised paper, my concerns remain, and I am inclined to keep my original rating.
First, the response has deepened my concern about why LLMs are discussed at all. The authors now state that their goal is not to claim that practical LLMs implement Solomonoff induction. However, the revised paper still frames itself around LLMs throughout: the abstract opens with LLMs, the introduction is motivated by LLM pretraining, and the implications are drawn for LLM fine-tuning and training-data design. The results themselves are general statements about approximate Bayesian sequential prediction, and I still cannot identify any assumption, analysis, or finding that is specific to LLMs. My concern that this Bayesian framework is unsuitable for overparameterized models is also not addressed.
Second, many of my questions are left unanswered. These include (numbering as in the original submission) whether the phenomenon in Theorem 1 is already established by general nonasymptotic theory, why the extension of Hutter's theory is more than incremental, why Theorem 2 is a substantive result rather than a consequence of the assumed prior, what is novel in the remaining theorems, and the questions on replaying pretraining data during fine-tuning.
Instead of answering these points, the response mainly restates the motivation and the main results. I therefore do not consider it a reasonable rebuttal.
Thank you for your further feedback. We acknowledge that our previous response focused too much on summarizing the results rather than directly addressing your specific concerns. We apologize for this and respond to your questions point by point below.
Q1: Connections to LLMs
A1: This paper studies the LLM pretraining paradigm, rather than specific LLM neural architectures.
Following Grau-Moya et al. (ICML 2024), under idealized assumptions (sufficient model capacity, perfect optimization, and unlimited training data), pretraining (minimizing next-token log loss) recovers the Bayesian mixture predictor. In particular, if the training data are generated by a universal Turing machine with random input bits, then the idealized LLM pretraining paradigm yields a model that implements Solomonoff universal induction.
By "our goal is not to claim that practical LLMs implement Solomonoff induction," we mean that we do not claim that practical LLM training data can produce Solomonoff universal induction.
Our work studies the robustness of this idealized pretraining paradigm under imperfect learning conditions.
Q2: My concern that this Bayesian framework is unsuitable for overparameterized models is also not addressed.
A2: Bayesian framework does not impose any restriction on the number of model parameters. The fact that the Bayesian mixture minimizes population log loss over all predictors holds independently of the model architecture or parameter count.
Of course, overparameterization alone does not guarantee that minimizing empirical log loss yields a predictor close to the Bayesian optimum. This is precisely why we study approximation errors. Moreover, our new Theorem 7 explicitly accounts for representation error, optimization error, and finite-sample effects.
Q3 The presentation is also far below the expected bar. I cannot determine what the authors intend to convey from the abstract, and the introduction further adds to the confusion through uninformative, ambiguous, and excessively verbose language.
A3: We have substantially revised the abstract and the "Our Main Contributions" subsection. We hope the revised version is clearer. The two main messages are:
- Even with unlimited training data, compared with perfection optimization, an arbitrarily small approximation gap can substantially weaken the task-wise prediction performance.
- In contrast, average-case prediction performance remains robust under approximation, even with limited training data.
Q4: The discussion also lacks conceptual precision. For example, semi-supervised learning, PAC learning, and reinforcement learning are presented in parallel as comparable “classical learning frameworks.” PAC learning is a theoretical framework, whereas semi-supervised learning and reinforcement learning refer to different learning paradigms or settings.
A4: Revised as suggested.
Q5: Although the paper is motivated by LLMs, its analysis is based on a Bayesian framework that assumes the learned model is close to the Bayesian optimum.
A5: We do not assume that the approximation gap is small. Instead, we treat it as a variable and study how prediction performance depends on .
We acknowledge that assuming finite can be restrictive for predictors learned from finite data. Therefore, we have added a new finite-data analysis (Section 4.3), which establishes an average-case guarantee without requiring the finite KL assumption.
Q6: I seldom see such a Bayesian assumption used in serious LLM-related theoretical work.
A6: There is an established line of theoretical research studying LLM in-context learning through Bayesian inference. See "Genewein et al. Algorithmic compression via pretrained neural networks. Entropy 2026" for a survey. They demonstrated that Bayesian prediction is a suitable theoretical framework for studying LLM pretraining and in-context learning.
Q7: It is also uncommon to model complex LLM tasks using universal Turing machines.
A7: Universal Turing machines are used here as idealized data generators, rather than as literal models of how real-world LLM training data are generated. By the Church–Turing thesis, they can represent any computable sequence-generating process.
In particular, Grau-Moya et al. (ICML 2024) explicitly studied meta-training neural networks, including Transformers, using UTM-generated data, and analyzed their convergence toward Solomonoff prediction under idealized assumptions.
Q8: I interpret Theorem 1 as showing that, even though the overall error is small, the error on a particular task can be large. I believe that general nonasymptotic theory, such as concentration inequalities, has already established this phenomenon in statistics.
A8: We are not aware of a classical concentration inequality that directly Theorem 1 (in the original version).
Q9: The extension of Hutter’s original theory is also incremental and relies on an additional Bayesian assumption that is itself questionable.
A9: We have substantially revised this part of the paper. Our main finding is that even with unlimited training data, an arbitrarily small approximation gap can substantially degrade the environment-wise prediction guarantee.
Theorem 1 (Theorem 3 in the revised paper) is not our main contribution; rather, it serves to establish the tightness of our analysis by providing a matching upper bound.
Q10: Theorem 2 also does not seem to provide a substantive new result, since the Solomonoff prior is defined to assign smaller prior probabilities to more complex environments. This prior was not proposed by the authors and should instead be viewed as an assumption. I am also concerned about whether it is an appropriate assumption for LLMs.
Q10: We agree that the Solomonoff prior is classical and is not our contribution.
Q11: I also did not find any particularly novel findings in Theorems 3–6. The existence of corner cases, lower average-case error, and the impact of distribution shifts have been widely discussed in classical machine learning. I cannot identify any adjustment specifically made for LLMs or any findings that are unique to LLMs.
A11: We agree that average-case analysis and distribution shift are classical topics in machine learning. However, our contributions are the quantitative guarantees for LLM pretraining paradigm, rather than the introduction of these concepts.
As clarified earlier, our analysis concerns the LLM pretraining paradigm, rather than specific LLM architectures.
Q12: I further examined Section 5 and likewise found no particularly interesting results.
A12: We have substantially strengthened the finite-data analysis (now Section 4.3, Theorem 7), establishing guarantees for predictors learned by approximately minimizing regularized empirical log loss. Please see our response to Reviewer 1, "New Finite-Data Result (Section 4.3, Theorem 7)," for details.
Q13: The authors suggest replaying pretraining data during fine-tuning to mitigate forgetting. First, much of the pretraining data may be of low quality, so it is unclear why such information should be preserved. Could replaying the pretraining data make fine-tuning ineffective? Second, the connection between this suggestion and the main claim of the paper is unclear. This further raises questions about the feasibility of the Bayesian assumption adopted in the analysis.
A13: Our fine-tuning discussion is a population-level analysis showing how replaying pretraining data can preserve average prediction performance on the original task distribution.
We agree that replaying low-quality data may not be desirable and that excessive replay could weaken adaptation to target tasks. In fact, we explicitly characterized the trade-off between target-task performance and original-task performance through the mixing parameter .
We acknowledge that practical fine-tuning is more complicated, particularly when considering computational efficiency, data quality, and data efficiency. Our result provides a theoretical explanation rather than an unconditional recommendation to replay pretraining data.
Finally, regarding the soundness concerns raised in your original review, we would appreciate it if you could identify any specific theorem or proof step that you believe is incorrect. We would be happy to address such concerns directly.
Thank you for your feedback. We recognize that the original presentation may not have communicated the motivation and significance of our results clearly enough. We have substantially revised the paper to clarify the connection to LLMs and the central theoretical message.
1. Motivation: Why is Bayesian prediction relevant to LLMs?
The standard recipe of LLM pretraining is quite simple: just minimizing next-token log loss over massive and diverse datasets. A natural theoretical question is to understand how such a simple pretraining paradigm can produce a general-purpose reasoning engine.
Following the meta-learning framework of Grau-Moya et al. (ICML 2024), consider training sequences generated by first sampling an environment/task ν from a prior w, and then sampling a sequence from ν. Exactly minimizing population log loss recovers the Bayesian mixture predictor
$ \xi=\sum_\nu w_\nu\nu. $
This predictor performs Bayesian adaptation through its in-context learning. With a universal prior, it provides the idealized framework of Solomonoff induction.
Rather, limited model capacity, imperfect optimization, and finite training data motivate our central question: To what extent do the prediction guarantees of the ideal Bayesian predictor carry over to practical learned predictors?
2. Main findings: A sharp contrast between worst-case and average-case prediction.
Our results reveal two fundamentally different behaviors:
We further quantify robustness under distribution shift, showing how prediction guarantees depend on the coverage of the test distribution under the training prior.
3. Significance.
These results provide a quantitative explanation, within the Bayesian meta-learning framework, of how small aggregate prediction error can coexist with severe failures on rare tasks.
Our goal is not to claim that practical LLMs implement Solomonoff induction, but to establish which guarantees of ideal Bayesian prediction survive approximation and finite-data learning. We have reorganized the paper to make this distinction and its implications clearer.