In-Context Learning and Occam's Razor
Authors: Eric Elmoznino
Tom Marty
Tejas Kasetty
Leo Gagnon
Sarthak Mittal
Mahan Fathi
Dhanya Sridhar
Guillaume Lajoie
Venue: ICML 2025 poster (2025)
Keywords: generalization
complexity
compression
in-context learning
meta-learning
Primary area: general_machine_learning->transfer_multitask_and_metalearning
TL;DR: The next-datapoint prediction error objective used in models that exhibit in-context learning can be seen as a meta-objective that optimizes for learners that not only explain their training data, but do so using the simplest model.

Abstract: A central goal of machine learning is generalization. While the No Free Lunch Theorem states that we cannot obtain theoretical guarantees for generalization without further assumptions, in practice we observe that simple models which explain the training data generalize best—a principle called Occam's razor. Despite the need for simple models, most current approaches in machine learning only minimize the training error, and at best indirectly promote simplicity through regularization or architecture design. Here, we draw a connection between Occam's razor and in-context learning—an emergent ability of certain sequence models like Transformers to learn at inference time from past observations in a sequence. In particular, we show that the next-token prediction loss used to train in-context learners is directly equivalent to a data compression technique called prequential coding, and that minimizing this loss amounts to jointly minimizing both the training error and the complexity of the model that was implicitly learned from context. Our theory and the empirical experiments we use to support it not only provide a normative account of in-context learning, but also elucidate the shortcomings of current in-context learning methods, suggesting ways in which they can be improved. We make our code available at https://github.com/3rdCore/PrequentialCode.

In-Context Learning and Occam's Razor
Eric Elmoznino" $
Tom Marty" 12 Tejas Kasetty 12 Leo Gagnon' Sarthak Mittal
Mahan Fathi?
Dhanya Sridhar 12 Guillaume Lajoie 12
Abstract
poor generalization (Bishop & Nasrabadi, 2006). To enable better generalization, ML follows the principle of Occam's 's razor- the best explanation is the simplest one that explains the observations (Rathmanner & Hutter, 201 I; Sunehag & Hutter, 2014; Hutter, 2010). The intuition that simple rules that explain the data cannot simply memorize observa- tions, and must instead capture more general patterns. Con- sequently, learning algorithms usually trade off low training error and low model complexity with ad hoc approaches (e.g,, via regularization and inductive biases), motivating the need for notions of complexity that can be tractably minimized directly.
A central goal of machine learning is generaliza- tion. While the No Free Lunch Theorem states that we cannot obtain theoretical guarantees for generalization without further assumptions, in practice we observe that simple models which ex- plain the training data generalize best-a principle called Occam's 's razor. Despite the need for sim- ple models, most current approaches machine learning only minimize the training error, and best indirectly promote simplicity through regu- larization or architecture design. Here, we draw a connection between Occam's 's razor and in-context learning-an an emergent ability of certain sequence models like Transformers to learn at inference time from past observations in a sequence. In particular, show that the next-token prediction loss used to train in-context learners is directly equivalent to data compression technique called prequential coding, and that minimizing this loss amounts to jointly minimizing both the training error and the complexity of the model that was implicitly learned from context. Our theory and the empirical experiments we use to support it not only provide normative account of in-context learning, but also elucidate the shortcomings of current in in-context learning methods, suggesting ways in which they can be improved. We make our code available /tattts://githiee com/ 3rddore//Prqquential...
Although there exist mathematical notions of model com- plexity such as VC dimension (Vapník al., 1998) or Kol- mogorov complexity, these quantities cannot be directly minimized, or even tractably computed for the latter. In practice, we instead learn predictors that minimize training eтror as well as proxies of the model's complexity, such as the L1 norm of the parameters, or rely on inductive biases for Low-complexity solutions that are implicit the model class and learning algorithm. Defying this trend, however, pretrained large sequence models (such as large language models-L.I.N have surprising ability to rapidly learn and generalize from small amounts of data presented in their context (or prompt) without any parameter updates (Radford et al., 2019). This form of "model fitting at inference" falls under the category of in-context learning (ICL. which gen- erally refers to the ability of models to learn new tasks from context. Although ICL refers wide range of phenomena in the literature (Lampinen et al., 2024) such as an LLM learning a task by following instructions, here, we focus on ICL as the process where a pretrained sequence model infers a statistical model from a training dataset passed in-context, which is also called memory-based meta-learning (e.g., Xie et al., 2022: Chan et al., 2022).
1. Introduction
The goal of machine learning (ML) is to learn models that generalize to unseen data. Longstanding theory shows that minimizing training error alone can lead to overfitting and
The main contribution of this paper is provide theoretical arguments linking ICL to Occam's 's razor and a preference for simple models (Figure 1). Briefly, our theory frames ICL as a meta-learning algorithm whose next-token prediction objective is directly equivalent to a powerful compression method called prequential coding (Blier & Ollivier, 2018). Given the relationship between compression and Occam's razor, we show that the meta-objective in ICL is to find
Equal contribution 'Mila Quebec AI Institute Universitéé de Montréal 'NVIDIA. Correspondence to: Eric Elmoznino seric.elmozninode @ mila.quebec.. Guillaume Lajoie <guil- lajoee @ mila.quebec>..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

In-Context Learning and Occam's Razor
a. Learning pipeline
b. Prequential Code Length
C. Learned prediction model
NLL on next-taken
Train-risk minimization
Pe
Σ log(pa,. (Mrva maa1))
y/
Po(-|ar)
gradentt update
Gradent-booed leerner
T
log(pel i))
VS
(+.00)
(1))
(or
x
K(po)
po(+
Next-token prediction
log(po(y x))
x
mate gradient
update
Meta
7
next-token prediction meta leamms to minimize model complexily
context length
P6
Figure 1. In-context learning fits simple models to training data. a. Standard train-risk minimization fits predictors that perform well on the training data, while lettallaamer trained on next-token prediction (in-context learning) learns to infer predictors that generalize to unseen (next-token) data, mitigating overfitting. b. Prequential coding: method for estimating K (DD) using a model pe 's learning algorithm T. As the learner T' sees more data, it outputs models pe, TDD:.) that assign higher likelihood to new observations d++1. and can thus better compress them. The prequential code length ( for describing the data in this way is given by the area under the curve, and the model's complexity is related to the learner's speed of adaptation. c. Illustration of the solutions fit by each learner. Train-risk minimization produces models that overfit the training data and generalize poorly, whereas in-context learning infers simpler solutions.
learner capable of jointly minimizing both training error and model complexity across a diverse range of tasks. Our theory, along with the empirical experiments that we use to support it, explain why ICL has proven so effective in meta-learning settings, and also explain the shortcomings of current ICL methods. Namely, we find that current methods produce learning algorithms which are susceptible to under- fitting and can fail to generalize to novel tasks, suggesting principled avenues for future research.
problem in an efficient and scalable way.
2.1. Kolmogorov Complexity and Data Compression
Kolmogorov complexity (Kolmogorov, 1965; Li & Vitányi, 2008) is notion of information quantity. Intuitively, the Kolmogorov complexity (xx) of an object x is the length of the shortest program (in some programming language) that outputs x. A related notion is the conditional Kolmogorov complexity K (=lyy) of the object x given another object y. which is the length of the shortest program that takes y as input and outputs While quite abstract, this notion of complexity has deep ties to compression, making it intu- itive as measure of information quantity. The smaller and more "structured" an object is reggulaart, patterns, rules, etc.-the more easily it can be described by a short program, correspondingly having lower Kolmogorov complexity. Al- though Kolmogorov complexity is very ceneral-obeects 2, y can be datasets, programs, models it is intractable to compute. However, it can often be tractably estimated or bounded.
2. In-Context Learning and Occam's Razor
In this section, we introduce meta-learning objective that targets simple models, and then show that it is equivalent to the next-token prediction objective underlying ICL. We reach this result via four key steps:
1. We begin by formalizing both training error and model simplicity through the lens of Kolmogorov complexity, which deals with optimal data compression.
2. We then show how learning algorithms can used to compress data through technique called prequen- tial coding (Blier& & Ollivier, 2018), whose resulting "prequential code length" can be minimized to improve compression.
A quantity relevant to ML is the Kolmogorov complexity of dataset KDD), where D = (d1, ..., d,) with d, ~ p. According to (Grünwald, 2007), the dataset sufficiently large, it can be optimally compressed by first encoding the data-gent Lata-generating process p and then encoding the data under this distribution. It is well known that optimally encoding data under a distribution takes only - llgg p(D) bits (e.g.. using an arithmetic coding scheme, Witten et al., 1987). as in the case of Shannon information (Shannon, 2001). We therefore have that:
3. We then introduce the idea of finding a learning algo- rithm that minimizes prequential code length by for- malizing meta- weta-lee problem that appears difficult to optimize.
4. Finally, we show that the next-token prediction objec- tive underlying ICI. already solves this meta-learning
K(D) K(p) + K(Dpp) K(p) logg P(D), (1)
2

---

In-Context Learning and Occam's Razor
where (p) refers to the complexity of the distribution (i.e., the length of the shortest program that outputs function p D + ) This term is intractable to compute as it requires an enumeration over all programs that output p. but (Dlp) = logg p( D) is easily computed: it is simply the negative bog-likelihood of the data under p. a commonly used objective function ML. It follows that simple models which achieve lower training error better compress data. We provide further background Kolmogorov complexity in Appendix A.
an algorithm for efficiently compressing D that does not require estimating K ((po), and then we will consider how to optimize this compressor in the next section.
While K (pe) is difficult to measure directly, it turns out that we can compress D without it using an algorithm called prequential coding (illustrated in Figure 1) that leverages the learner T which produced ps (i.e., P T(D)). Con- sider an ordered dataset D {di,..., dy J. and denote D1: {d1, ...., ). Prequential coding uses the learner T to train models on increasing amounts of data. First, we train a model on just the first data point to get pe, = =d1)). Because the model is trained on a single datapoint, it will not be very accurate; however, it should be better than a random model that has seen no data at all. We can then use this model pe, to compress the next (unseen) datapoint d2. which takes - log, Pe, (d2) bits. At this point, we can train new model pe, = T(D12) Having seen more data, this model should assign higher likelihood to a new datapoint ds, which we can compress using- - llgg Pe, (da) bits. This process repeats until the entire dataset has been covered. At this point, the model po can be obtained simply by applying the learning algorithm the complete dataset pe = T(D).
As we are interested in model optimization, we henceforth consider parameterized models Pe with parameters 0. We denote a learning algorithm by a function T : P (D) - θ (where P denotes the power-set), which maps a dataset D) model Pr(D). Maximum likelihood training on iid data, which is the norm in MI, is learning algorithm 7 which minimizes:
Tml (D) = arg min-
Σ dED
logg Po (d)
(2)
or
However, Occam's razor says that we also need simple models that best compress the data-mattematiiallyy this is because the "true" model generating the data in Equation (I) optimally compresses the data. Thus, consider the leamn ing algorithm T which defines "simple" via complexity:
The total number of bits that it takes to compress D using prequential coding is the sum of how many bits it takes to compress each datapoint using a model that was trained on all previous ones. Visually, it is the area under the prequen- tial coding curve shown in Figure Ib. The length of this program is called the prequential code length Liprey (D; T) (Blier & Ollivier, 2018):
(Do(D) = arg min 0'
K(po-)
logo po (d)
(3)
DED
In reality, the Occam's 's razor learner T is intractable since K (por) cannot be computed. In practice, maximum log- likelihood training T is often enhanced with regularizers (e.g., Lz-norm of parameters) and inductive biases (e.g., re- stricting the model class) to implicitly favor low-complexity models that combat overfitting and improve generalization. For instance, deep neural networks (DNNs) trained through stochastic gradient descent (SGD) tend to be biased towards simple solutions (Blier & Ollivier, 2018; Goldblum et al., 2024; Mingard et al., 2025). However, most existing reg- ularizers at most amount to indirect methods that roughly penalize model complexity K (pp) along with training error; learning algorithms (which we will often call "learners"' for brevity) rarely directly attempt to minimize compression length of D, as T would. In what follows, we introduce learners To that have learnable parameters d estimated via meta-optimization, to approximate the ideal learner T
N-1
Lyreg (D:T) =
Σ - log, po, (d++1) 2 K(D).
(4)
( (D;T) is an upper-bound on K(D) since prequential coding is one way to compress the data. In Section 2.3 we will minimize this quantity with respect to the learner T, and thus minimize the description length of the data.
Prequential coding relates Kolmogorov complexity to intu- itions about generalization in ML: the simpler model is, the quicker it generalizes from limited amounts of training data. Although the relationship in Equation (4) offers a promis- ing way forward to operationalize Occam's 's razor, there is a problem. The prequential code length given by Equa- tion (4) conditions on the choice of a learner T. However, prequential coding also requires us to encode the learning algorithm itself. When take the description length of T into account, the quantity Lypreg (Dp + K(T) upper bounds K(D) (see Appendix B). As we describe below, we will optimize for learners T' that minimize Lpreg! (D; Ty), and will articulate how To has low complexity given mini- mization over multiple datasets.
2.2. Prequential Coding
While learner T that adheres to Occam's 's razor and solves Equation (3) by optimally compressing D would improve generalization, it is difficult to design one in practice. Even if K (po) could be computed efficiently. there is the further challenge of minimizing it. Instead, we will first describe
3

---

In-Context Learning and Occam's Razor
2.3. Minimizing Prequential Code Length
3. To meta-optimize o, it must be easy to take gradients of Expreg(; (: Ta) w.r.t. ø.
Consider a parameterized learner To that minimizes the prequential code length Lpreg Ta) of dataset D. This objective aims to optimally compress D like the idealized learner T does, but only when (Tx)) is low. This second criteria is violated if T. overfits to single dataset D. To forbid To from memorizing a single datasct, we consider a meta-dataset 9 = {D', ...., DM) coming from M different tasks and meta-learn To to minimize prequential code length on average across the meta-dataset 2. This allows us to write the following objective for the learner To:
4. 6 must parameterize an expressive class of learning algorithms, capable of minimizing prequential code length on a broad distribution of tasks and generalizing to unseen ones.
While this may appear daunting, it turns out that these desiderata are readily addressed by ICL in probabilistic sequence models. Such models are trained to predict the distribution over the next element in sequence given its past context: F(de(Dia-1). Crucially, the sequence model F is both the learner T, and the inner model Pe. Indeed, 6 corresponds to the parameters of the se- quence model F (e.g. weights in a Transfomer), and = To (o is encoded by the activations of hid- den units in the model when presented with the context Pitt-1 Thus, the predicted distribution over the next token is given by: is trained to minimize the cumulative next-token predic- tion error: ((); = Σ log (r,,.r,.-))) (dd)), which corresponds exactly to the prequential code length in Equa- tion (4).
M
((9:0)= = Σ L 2
(5) Σ K(D
By minimizing (():)) EM (D' To), we thus end up with a learner Tg. that minimizes compres- sion length in expectation over datasets, and after meta- training compresses new dataset of interest D using Txpreg (D; T>) 2 K(D) bits. The learner To- will suc- ceed in compressing D when it generalizes to that novel dataset.
= PT. (d:). The model
The learner Ta- and the Occam's razor learner Toc (= arg ming (po) - log, po (D)) are not exactly identi- cal: T compresses the data by directly minimizing model complexity and training error, whereas T compresses the data by minimizing its prequential code length. Despite these differences in compression strategy, however, the two learners are deeply related through the minimum descrip- tion length principle (Grünwald, 2007) because they both attempt to optimally compress their training data. In par- ticular, if T significantly compresses the data through prequential coding, the minimum description length princi- ple states that the model pe = To-( ( (D) which it fits is likely to generalize because optimal compression is achieved by the true generative process (Equation (1)). In this way, the learner To- implicitly fits simple models with low train- ing error, minimizing K (pe) log, (D). In Section 3, will empirically show this to be the case across diverse tasks, where pe Ta- (D) will generalize far better than the typical ML approach of minimizing training error alone.
The dual nature of the sequence model as both the learner and the learned model offers a natural solution to the con- straints above, enabling fast and differentiable evaluation of (.(.) (2 & 3 above) with respect to cumulative next- token prediction loss (1 above). Moreover, modern se- quence models can parameterize a rich class of learning algorithms, which is crucial to minimizing Equation (5) (4 above). Notably, architectures such as Transformers are known to have components which make them especially good meta-learners, such as multi-head attention (Olsson et al., 2022). It is thus no surprise that sequence models are leveraged in settings outside of the language domain (Von Oswald et al., 2023; Bauer et al., 2023; Kirsch et al., 2022), making them general-purpos meta-learners.
This predictive formulation can be used to model data which contains sequential correlations, such as language, but it is more general. Indeed, consider iid dataset D ((I1,8))... (IT, yt}} and the supervised task of learning a function = f(x). In this setting, a data point is given by the pair d: = (æt, )a), and straightforward tok- enization schemes can be used to append a novel query x= to the context D such that the predicted output j" given by the next token in the sequence. This ICL setup is well-suited for regression-type tasks (see e.g. (see e.g., Von Oswald et al., 2023; Oswald et al., 2023)) but can be used for most supervised tasks. ICL thus turns the training of a sequence model into a meta- opta-oppim problem over datasets an approach also called memory- -aasery-baeed meta- leaannen (Hochre- iter et al., 2001; Santoro et al., 2016; Ortega et al., 2019).
2.4. ICL Minimizes Prequential Code Length
In practice, solving the meta-learning problem in Equa- tion (5) involves several constraints:
1. The performance of (-(.) must be evaluated w.r.t. dataset's prequential code length.
2. (-):) must be fast to evaluate because it is iteratively called on multiple datasets.
4

---

In-Context Learning and Occam's Razor
Prequential code length is well-defined over arbitrary se- quences, our theory relating ICL to Occam's razor applies to both iid and nonstationary data, as explored in Section 3.
number of digits that are correct in value but not necessarily position. We use randomly sampled codes of length 8 with digits varying from 1..6.
Summary. We showed that sequence models trained on cumulative next-token prediction losses explicitly optimize a meta-learning objective for compression, thus jointly min- imizing training error and model complexity. This provides a normative account of ICL in terms of Occam's 's razor, and explains recent experimental findings showing that LLMs are good universal compressors (Deletang et al., 2024).
The tasks above produce iid datapoints so that we could make fair comparisons to learners that minimize training error under iid assumptions (e.g.. SGD). However in Sec- tion 3.3 we will compare prequential ICL learners with dif- ferent architectures, and we consider another, non-tid task, (4) HMM: next token prediction on synthetically -ggnerate nonstationary data from Hidden Markov Models (HMMs) that were designed to mimic the statistical properties of nat- ural language in a simplified and controlled setting. The models are evaluated on unseen HMMs with novel transition and emission matrices. See Appendix C for details.
3. Experiments
Our experiments are designed to illustrate the benefits of ICL in terms of fitting simple models that generalize. In Section 3.1, we compare ICL's standard next-token predic- tion objective to alternative that minimizes training error alone, rather than prequential code length. Section 3.2 then compares ICL to standard gradient-based learners that min- imize training error, such as SGD. Section C.2 shows the impact of regularization on gradient-based learners from a compression perspective. In Section 3.3, we explore the im- pact of learner T3 's architecture on prequential code length minimization. Section 3.4 explores the ability of To to gen- eralize to novel tasks. Experimental details not described in the main paper (e.g., precise architectures, hyperparameters, etc.) can be found in Appendix C.
3.1. Comparisons to ICL With a Train-Risk Objective
We have argued that standard ICL can be seen as a meta- learning method who's meta-objective is to minimize train- ing error and model complexity through cumulative next- token prediction (prequential code length). However, this is not the only meta-objective that one could design for ICL. In particular, we can design an alternative meta-objective that minimizes only training error simply by training To to predict past datapoints in the context rather than future unseen ones. both cases, the learner To some function that takes a context (i.c., a partial dataset) as input, and out- puts model pa capable of making predictions for arbitrary datapoints. For supervised learning, this can be represented as ig ( v) Fig) where (z, v) corresponds to an observed context, I. is the queried input, and the model py is implicitly encoded in To 's weights and latent activa- tions given the context. In standard ICL (which we will refer to as prequential ICL), the query Fy is a novel input that does not appear in the context. In the alternative form of ICL (which we will call train-risk ICL), the query Fy is a randomly-selected input that appeared previously in the context æ1.j. Note the similarities of train-risk ICL to standard objectives of learners that minimize training error: it processes some fixed-sized training set (here a context) and attempts to minimize the empirical risk on a subset of that very same data (here a single query that appeared in the context). While nobody uses train-risk ICL in practice, it serves as an ideal control to illustrate our theory of ICL and the generalization benefits of minimizing prequential code length as opposed to only training error. One can use an identical architecture for T7 in both cases and train using precisely the same methodology and loss function; the only difference is which query the loss function evaluated on.
Tasks, In line with similar work studying ICL in a con-
trolled setting (Mahankali et al., 2024; Garg et al., 2022: Akyürek al., 2023), we use synthetically-generated tasks. Each task consists of a supervised learning dataset D' (2),,)),,... (zg, }. where the labels are (potentially ey). ICL Iearn- DN).
stochastic) function of the input y =
ers To are trained on a meta-dataset Φ = where each D' is associated with a different ground-truth data-gem tata-generating function f². We primarily study three meta- datasets: (1) Linear regression problems where x E 3 and y E R. The ground truth functions f' are noisy linear mappings yj W* + +ej. where each (W b') is sam- pled from a standard Normal distribution and e, is Gaussian noise with 0² = 0.04. (2) Sinusoidal regression problems where I2 E IR and functions/ f are linear combinations " - Ei ae sin (w/rz). We use L = 3 with frequencies ~ (0,,5, 5) that are shared across tasks, varying only the amplitudes Cs ~ NN 1). (3) Mastermind: a multi-label classification problem inspired by the rode-breaking game Mastermind. Each f is associated with an underlying dis- crete code (a fixed-size sequence of digits) that needs to be inferred from random guesses that return partial informa- tion. The inputs Iy are random guesses for the code, and y = f (2z) is a tuple of two class labels where the first specifies the number of digits in Ty that are correct in terms of both position and value, and the second label specifies the
In our experiments, we parameterize T using Transformer. For the train-risk case, a standard Transformer could simply attend to the context position that matches I, and retrieve the corresponding label. To prevent this trivial solution,
5

---

In-Context Learning and Occam's Razor
Linear regression
Sinusoid regression
Mastermind
Generalization error
0.8
0.6
prequential train-risk ICL
0.6
(no meta-learning)
0.4
0.2
0.2
0.0
0.0
10
10
10
10"
10
10
10"
10"
10'
10"
10"
Datapoints seen
Datapoints seen
Datapoints seen
Figure 2. Experimental results comparing different learners. Figures show average prequential coding curves for meta-dataset, which is the mean prediction error on unseen data (generalization error, y-axis) given observed contexts of increasing length (datapoints seen, x-axis). The underneath these curves corresponds to prequential code length. ICL from next-token prediction objectives (prequential ICL, blue) yields lower prequential code lengths than ICL from past-token prediction objectives (train-risk ICL, orange), with greater effects in low-data regimes. An SGD-based learner (green) fits more complex models than prequential ICI. and performs poorly in low-data regimes, but can generalize hetter in large-data regimes on a difficult Mastermind task due to underfitingg in ICL., Error measured using MSE for linear and sinusoid regression and cross-entropy for Mastermind. Error bars show standard error across seeds (5 for ICL, 15 for SGD).
Linear regression
Cubic regression
ground truth prequential ICL* train-risk ICL
0.25
L2-norm weights
L2-norm of waights
0.3
-0.50
m
-0
0.5
-1.00
0.1
1.0
01
1.25
1.5
-1.0
-0.5
0.0
10
25
75
100
-1.0
-0.5
0,0
0.5
25
75
X
Datapoints seen
X
Datapoints seen
Figure 3. Models inferred by different learners. Visualization of inferred models for noisy linear and cubic regression tasks (leftmost and middle right). Observed data is shown in black points, ground -oound-truthh truth in gray. prequential ICL in blue, and train-risk ICL in orange. Train-risk ICL consistently overfits, while prequential-ICL. infers simpler functions closer to the ground truth. Middle left and rightmost plots show the L2-norm of inferred coefficients for polynomial orders greater than the ground-truth data-generating orders, plotted against context length. Train-ICL fits complex models using high-degree components overfit the data.
instead use bottlenecked architecture for To described in Mittal et al. (2025). In this architecture, Transformer first summarizes the context into a low-dimensional vector 2 = Trans f foreero ((z, v)):)), ). and a separate prediction head-here a multi-layer perceptron (MLP) subsequently outputs a prediction for the query ú. = MLP (x.g 2). For fair comparison, we use the same bottleneck architecture for train-risk ICL and prequential ICL in all experiments, unless otherwise stated. Figure 2 shows our comparisons between prequential ICL to train-risk ICL, where we plot the prequential coding curves for each ICL method after loss convergence on a meta-datasct. The curves are constructed inference time by evaluating the average generalization error (i.e., unseen next-token prediction loss) on unseen tasks from the meta-dataset, for varying context lengths.
This is because with significant data, optimal compression is dominated by training error (Fquation (1)), making over- fitting less likely to occur. The benefits of simple models are instead expected to be most prominent in low-data regimes where generalization is difficult, and this is precisely what we observe. Across all tasks, prequential ICL. consistently outperforms train-risk ICL in terms of generalization for short context lengths, and this performance gap extends fur- ther the more difficult the task (e.g.. it is small for linear regression, and larger for sinusoid regression and master- mind). We confirm that the performance gap widens with increasing task difficulty by fixing the function class and increasing the dimensionality of the inputs x in Appendix D, which expected given that harder tasks require more data for generalization. In Appendix FF we repeat these analy- ses a modified version of the HMM task that is more amenable to train-risk minimization and find similar trends as above for non-iid data. Lastly, in Appendix G, we com-
Findings. Two findings follow directly from our theory. The first is that for large context lengths, generalization er- ror is identical for both prequential ICI. and train-risk ICI.
6

---

In-Context Learning and Occam's Razor
Linear regression
Sinusold regression
Mastermind
HMM
Generalization error
1,0
Transformer bottleneck
0.125
1.5
3:50
Transformer w/o bottleneck
0.8
Mamba
0.100
325
0.6
Mamba
0.075
3000
0.4
0.050
0.5
775
0.2
0.025
2.50
0.0
0.000
2
10
10
10"
10 10
10
10"
10"
10"
10
10"
10
10"
10
10"
Datapoints seen
Datapoints seen
Datapoints seen
Datapoints seen
Figure 4. Sequence model architecture impacts ICL's ability to minimize prequential code length. Figures show average prequential coding curves for a meta- datasedt which is the mean prediction error on unseen data (generalization error, y-axis) given observed contexts of increasing length (datapoints seen, x-axis). The area underneath these curves corresponds to prequential code length. Error is measured using MSE for linear and sinusoid regression and cross-entropy for Mastermind and HMM. Error bars show standard error across 5 seeds.
pare the generalization performance of in-context learner trained on the full sequence of tokens versus only the latter half of the sequence. Consistent with our theory, the lack of low-data signal in the latter case results in worse prequential code length and less pressure toward simple models.
models obtained through the SGD-based learner generalize just well. In fact, on the Mastermind task, SGD performs better in large-data regimes. This result demonstrates that even though the next-token prediction objective in ICL is well-motivated from the theoretical perspective of compres- sion, the degree to which that objective can successfully be minimized strongly depends on the architecture of T. and the methods used train it. For instance, when TĄ is Transformer, the expressivity of the model it implicitly fits to the context scales with the number of activations in the network (N), whereas the expressivity of DNN trained through SGD scales with the number of weights ( (N²). Fur- thermore, the amount of compute time that T' uses to fit the context amounts to one forward pass of network, whereas the compute time that goes into fitting a dataset using SGD) can be arbitrarily large.
Visualization of learned models. To better understand the solutions learned by prequential and train-risk ICL, we visualize the inferred models for noisy linear and cubic re- gression tasks in Figure 3. We also replace the prediction head of our bottlenecked models with parameter-free free poly- nomial function, so that the bottleneck represents a vector of inferred polynomial components. Figure 3 shows that for a small context length (15) train-risk ICL overfits the data by fitting complex models with high polynomial order, whereas prequential ICL fits simple functions that are more robust to noise. Further experimental details are provided in Section C.3.
Regularized SGD. We also considered the effects of differ- ent regularization techniques that can be applied to SGD to indirectly influence the complexity of the resulting model (e.g., L2), shown in Appendix E. As expected, regulariza- tion influences prequential code length by trading off model complexity and training error varying degrees. However, all SGD regularization methods are still outperformed by prequential ICI. in low-data regimes, due to prequential ICL's direct compression objective that optimally balances model complexity and training error.
3.2. Comparisons to Gradient-Basel Learners
We next consider whether there are empirical advantages of meta-learning a learner TG to minimize prequential code length through ICL, compared to using standard out-of- the-box learning algorithms. In particular, we know that traditional SGD-based learners can optimize DNN models that generalize well across wide range of tasks, despite only explicitly minimizing training error. We consider standard SGD-based learner that fits randomly-initiall MLP to the training set until validation loss converges. We repeatedly sample a dataset from our meta-dataset, truncate it to a specified number of observed datapoints, apply the SGD-based learner to the truncated dataset, and evaluate the resulting model's generalization error on new datapoints.
3.3. Influence of the ICL Architecture
The previous section argued that the structure of Ts can influence its ability to minimize prequential code length. In this section, we further illustrate this point by considering a wider breadth of neural architectures for Ta- Since state- space models (SSMs) have recently been shown exhibit ICL (Lu et al., 2024), and Mamba 2 (Dao & Gu, 2024). We also test standard causal Transformer in addition to the bottlenecked Trans- former from previous sections. We refer to Appendix C for
Findings. Figure 2 compares this SGD-based learner to prequential (and train-risk) ICL learners. Across all tasks, the models obtained through ICI. generalize better in low- data regimes, aligning with our theory that ICL minimizes model complexity. With enough training data, however,
test Mamba 1 (Gu & Dao, 2024)
7

---

In-Context Learning and Occam's Razor
additional information about the specificity of each architec- ture.
dataset used to train To are scaled significantly, current methods for ICL can still struggle to minimize prequential code length on novel task.
Findings. Prequential code length comparisons in Figure 4 show that the architecture for To indeed plays a substan- tial role, which interacts substantially with the meta-dataset. For instance, only the Transformer without bottleneck does well on Mastermind, whereas on the HMM task it is outper- formed by SSMs. Analyzing these results in depth is out of scope for this work; only intend to show that having next-token prediction objective alone does not guarantee that prequential code length can successfully be minimized in practice through ICL.
4. Related Work
Sequence modeling and compression. The idea that probabilistic models can be used to efficiently compress data is topie widely studied in machine learning across dif- ferent modalities and settings (Ollivier, 2015; Deletang et al., 2024; Blier & Ollivier, 2018; Veness et al., 2015), specifi- cally in sequence modeling (Goyal et al., 2019; Valmeekam et al., 2023; Deletang et al., 2024) due to its close similari- ties to prequential coding (Blier & Ollivier, 2018). While Goyal et al. (2019) and Valmeekam al. (2023) claim that learned sequence models can outperform simple compres- like JPEG or gzip, they overlook model complexity in their analysis, adhering strictly to Shannon's 's notion of compression. In contrast, more recent studies from Dele- tang et al. (2024) and Bornschein et al. (2023) opted for the Kolmogorov approach, incorporating model size to account for model complexity. Deletang et al. (2024), in particular, add nuance to the claimed advantages of foundation models due to the substantial memory allocation required to store their weights. Our theory builds these works by relat- ing compression and sequence modeling to the approach of meta-learning across tasks using ICL, which we show yields simple models that adhere to Occam's 's razor.
3.4. Large Pretrained Models
A core element of our theory of ICL is that To is trained to minimize average prequential code length on meta-dataset. There no guarantee, however, that prequential code length will be small on a novel dataset at inference time: this depends on the generalization abilities of the learner To- In this section, we look at the task- sesgaeenerllization abilities of large pretrained LLM (GPT-4 Achiam et al., 2023) on the Mastermind task. We do this by prompting the LLM with a description of the task and a number of in-context examples, then obtaining the logits and prediction error for a novel example.
Mastermind
3.0
Generalization error
Pretrained LLM Naive baseline Our Transformer
ICL as Bayes-optimal prediction. One of the dominant perspectives of ICL and related meta-learning approaches is that they yield Bayes-optimal learners (Ortega et al., 2019; Mikulik al., 2020; Müller et al., 2022; Hollmann et al., 2023; Binz et al., 2023; Wang al., 2023), in the sense that they learn prior distribution over tasks during training, and then compute posterior given data presented in-context at inference time. This posterior can then be used to make predictions with minimum Bayes' risk. Various studies have tested this in controlled settings with tractable posteriors (Xie et al., 2022; Panwar et al., 2024; Genewein et al., 2023; Mittal et al., 2023). Xie et al. (2022) assume a concept la- tent that parameterizes the generation of dependent samples through an HMM and provide formal conditions for ICL to effectively approximate the Bayes-optimal predictor on the prompt. In a supervised fashion, Akyürek et al. (2023) con- struct sequence of labeled examples (æc, I fxx) and shows that under uncertainty, ICL behaves as the Bayes-optimal predictor on noisy linear regression. Additionally, they ar- gue that with limited capacity, ICL does not necessarily match the Bayes predictor but can meta-learn other learning algorithms, such as gradient- based algorithms on linear mod- els and closed-form ridge regressors (Panwar et al., 2024). Brau-Moya et al. (2024) induce a prior for model simplicity in ICL by generating tasks from short programs run on Uni-
2.0
1.5
1.0
10'
10
10"
Datapoints seen
Figure Large pretrained sequence models can fail min- imize prequential code length on novel tasks. GPT-4 (gray) performs far worse than small ICL models trained on a distribution of Mastermind tasks (blue) and naive baseline that predicts the marginal class distribution over the context (purple). Error is mea- sured using cross-entropy. Error bars show standard error across 5 seeds.
Findings. In Figure 5, we find that despite its massive pretraining across a breadth of tasks, the LLM is unable to meaningfully minimize prequential code length on Master- mind. Not only is its prequential code length substantially higher than for a much smaller model trained on a distri- bution of Mastermind tasks, but it is also higher than for a naive baseline that just predicts the empirical marginal distribution over class labels in the context. These results demonstrate that even when the size of the model and meta-
8

---

In-Context Learning and Occam's Razor
versal Turning Machines. Finally, (Raventós et al., 2024) find that under sufficiently diverse set of pretraining tasks, ICL does not yield Bayes-optimal predictors, but instead infers a more uniform prior. While the Bayesian perspective of ICL. is very useful and complementary to the Kolmogorov one that we have proposed, we argue in Appendix H that the Kolmogorov perspective generalizes the Bayesian one and more easily accounts for diverse findings in ICL (e.g.. cases where ICL does not yield Bayes-optimal predictors).
finding corroborated by Ding et al. (2024). In light of this, we hypothesize that ICL can be improved through the design of novel sequence model architectures that explicitly target prequential code length. For example, current methods learn in-context through a single forward pass of sequence model with fixed layer depth. In contrast, DNNs can be trained using gradient- bbased methods until training loss con- verges, which can take weeks and substantial compute. One improvement to ICL might therefore be augment current sequence model architectures with "layers" that use built-in optimization primitives with variable compute budgets, as was done in Oswald et al. (2023). Another promising ap- proach is to combine ICL and SGD through a "mixture of learners" that reaps their complementary benefits. ICL sample-efficiet and generalizes well in low-data regimes, while SGD-based methods that optimize the weights of a DNN excel on difficult tasks when significant training data is available. Recent work by Bornschein et al. (2024) ex- plored a simple method for combining both learners by presenting a smaller number of recent tokens in mn-context to a sequence model for ICL, while at the same time using a large number of earlier tokens to fine-tune the weights of the sequence model using gradient methods, finding significant performance gains.
ICL as direct meta-learned optimizer. Elaborating on the possibility that ICL emulates non- non-Bayesian learning algorithms, Von Oswald et al. (2023) show that k-layer lin- ear Transformers with specific weight parameterization can mimic k steps of gradient descent for a least squares loss. Ahn et al. (2023) provide a theoretical foundation for these observations, provably showing that the optimization of the parameters of a linear Transformer under certain as- sumptions about the data distribution effectively implements this learning algorithm. Concurrent studies by Zhang et al. (2024) and Mahankali et al. (2024) report similar findings, albeit under slightly different assumptions regarding weight initializatton or data generation processes. Beyond the scope of linear regression, Kirsch et al. (2022) explore this phe- nomenon on augmented natural data (MNIST, CIFARIO) and provide insightful empirical conditions for the emer- gence of ICL as general-purpose learning algorithm. Other works empirically show that Transformers can learn more complex function classes in-context, such as sinusoidal re- gression ( (Von Oswald et al., 2023), decision trees (Garg et al., 2022), and progampogre functions (Zhou et al., 2024). While prior works such as these attest to the powerful meta-learning capabilities of ICL, our work differs in that it identifies the precise meta-objective as implementation of Occam's razor.
Another challenge of ICL that follows directly from our theory is that the in-context learner must generalize to novel tasks and datasets. While we found that task generaliza- tion was successful over narrow task distributions (e.g. a distribution of linear regression tasks), we also found that task generalization was more difficult in open-ended cases, in which even large pretrained LLM was unable to learn in-context on novel task that was easily solved by a small MLP trained using SGD, One possible path forward is to have many domain-specific in-context learners that each specialize in compressing data from a given task distribu- tion. Another option is to learn simple learners that are more likely to generalize to novel tasks, which could be achieved through inductive biases, regularization, or, in- triguingly, through an additional meta-layer of ICL at the task level that would minimize the Kolmogorov complexity of the learner itself (and not only the model it fits).
5. Discussion and Future Work
In this work, we introduced novel theoretical arguments linking ICL and the next-token prediction objective Oc- cam's razor. Our theory provides normative account of the strong generalization abilities of in-context learners at infer- ence time, especially in low-data regimes when compared to traditional optimizers. These theoretical insights were supported by a number of empirical experiments, some of which also identified shortcomings of current methods for ICL that should be addressed in future work.
Finally, given that our theory generalizes to nonstationary data (where prequential coding remains strong compres- sion algorithm), many further questions arise. In particular, the ordering of data presented in-context can have a substan- tial impact on prequential code length and model complexity (Zhang et al., 2020), which can guide the design of optimal curricula for strong and data-efficient generalization.
One such shortcoming is that models learned through cur- rent ICI methods can underfit data presented in-context, which can hamper generalization in large-data regimes on difficult tasks. We also found that the degree of underfitting was highly dependent on the architecture used to parame- terize the in-context learner (i.e., the sequence model)
9

---

In-Context Learning and Occam's Razor
Acknowledgments
Dasagi, V., Gonzalez, L.,, et al. Human-timescale adapta- tion in open-ended task space. In International Con- ference Machine Learning, pp. 1887-1935. PMLR, 2023.
The authors would like to acknowledge the following re- searchers for valuable discussions and exchanges: Joao Sacramento, Johannes von Oswald, Jorg Bornschein, Mar- Hutter. All authors acknowledge unrestricted gift from Google inc. for research support. EE acknowl- edges support from Vanier Canada Graduate Scholarship #492702. SM acknowledges the support of PhD Excel- lence Scholarship from UNIQUE. DS from NSERC Discovery Grant acknowledges support and Canada-CIFAR AI Chair. GL acknowledges support from MENIN-2018-448222 the Canada Research Chair in Neural Computations and Interfacing, and CanaRa-CIFAR AI Chair.
Binz, M., Dasgupta, I., Jagadish, A. K., Botvinick, M., Wang, J. X., and Schulz, E. Meta-learned models of cognition. Behavioral and Brain Sciences, pp. 1-38, 2023.
Bishop, C. M. and Nasrabadi, N. M. Pattern recognition and machine learning, volume Springer, 2006.
NSERC Discovery Grant
Blier, L. and Ollivier, Y. The description length of deep learning models. Advances in Neurul Information Pro- cessing Systems, 2018
Impact Statement
Bornschein, J., Li, Y., and Hutter, M. Sequential learn- ing of neural networks for prequential mdl. In In- ternational Conference on Learning Representations, 2023. URL https:/ /ttp://////peeeeeeeeee/eeeeeeeee https//wwwwweeeeeeeeee net//orum? id id-dMMPUvNSYJE.
Hundreds of millions of people now use conversational agents weekly for productivity, learning, and more. These agents rely heavily on In- Cn-Context Learning (ICL) generate high-quality, contextually appropriate responses. However, as their use expands into high-stakes settings, understanding ICL's inner workings and failure modes becomes critical to ensure the safe deployment of conversational AI. Our work aims uncover some of the characteristies and limitations of a particular form of ICL, providing valuable insights for developing more robust ICL in future work. Such advance- ments are crucial for accelerating the path toward safe gen- eral artificial intelligence (AGI). The societal implications of AGI are broad and significant, and we direct readers to the field of AI safety for further discussion on these critical issues.
Bornschein, J., Li, Y., and Rannen-Triki, A. Trans- formers for supervised online continual learning. CoRR, 2024. URL httpp:://doii. wtt.oi.org11...855000 arXiv. 01554.
Chaitin, G. On the length of programs for computing finite binary sequences. Journal of the ACM, 13(4)5547-569 1966.
Chan, S., Santoro, A., Lampinen, A., Wang, J., Singh, A., Richemond, P., McClelland, J., and Hill, F. Data distri- butional properties drive emergent in-context learning in transformers. Advances in Neural Information Processing Systems, 2022.
References
Achiam, J., Adler, S., Agarwal, S., Ahmad, L.,, Akkaya, I. Aleman, F. L., Almeida, D., Altenschmidt, J., Alt- man, S., Anadkat, S., al. Gpt-4 technical report. arXiv preprint atXhv22333.08774 2023. URL https: // //aaxivv.. o abs/ 2303. 08774.
Dao, T. and Gu, A. Transformers are SSMs: Gener- alized models and efficient algorithms through struc- tured state space duality. In International Conference on Machine Learning. PMLR, 2024. URL https: //openreview.o net (oo.uummddtzt@FFFRIE.
Ahn, K., Cheng, X., Daneshmand, H., and Sra, S. Trans- formers learn implement preconditioned gradient de- scent for in-context learning. In Conference on Neural Information Processing Systems, 2023. URL https: //openreview. net wwt.:/nttt//aaee.eeo www.mmidd--iiiniae.....
Deletang, G., Ruoss, A., Duquenne, P.-.,, Catt, E., Ge- newein, T., Mattern, C., Grau-Moya, J., Wenliang, L. K., Aitchison, M., Orseau, L.., Hutter, M., and Veness, J. Lan- guage modeling compression. International Confer- ence Learning Representations, 2024. URL https: / //openreview.nee www.ooddddddnnooooooooooooo
Akyürek, E., Schuurmans, D., Andreas, J., Ma. T., and Zhou, D. What learning algorithm is in-context learning? investigations with linear models. In International Confer- ence on Learning Representations, 2023. URL https: // //operreviww.coo http:///wwe...ettooooo////ooo///
Deutsch, D. The Beginning of Infinity: Explanations That Transform the World. Penguin Books, 2012. ISBN 9780140278163. URL https::/t//// //ook//bbokk.o// google.
Bauer, J., Baumli, K., Behbahani, F., Bhoopchand, A., Fradley-cchiieg N., Chang, M., Clay, N., Collister, A.,
Ding, N., Levinboim, T., Wu, J., Goodman, S., and Soricut, CausalI is not optimal for in-context learning. In
10

---

In-Context Learning and Occam's Razor
International Conference on Learning Representations, 2024. URL https: http://ppereeeeeeeeeeeeeeemeeeea http:::/pperreeeeee...ro id=guRNebw2Bb.
Hollmann, N., Müller, S., Eggensperger, K., and Hutter, F. Tabpfn: A transformer that solves small tabular classi- fication problems in second. In International Confer- ence on Learning Representations, 2023. URL https: / //oopprrvileeee ew net/ forum? d=cp 6w8_.
forum?
Fortnow, L. Kolmogorov complexity. In Aspects of Com- plexity, NZMRI Mathematics Summer Meeting, 2000.
Hutter, M. A complete theory of everything (will be subjec- tive). Algorithms, 3(4):329-350, 2010.
Garg. S., Tsipras, D., Liang, P., and Valiant, G. What can transformers learn in-context? case study of simple function classes. In Advances in Neural Information Pro- cessing Systems, 2022. URL https::tp///. hwwpt:httpssseeeeeee htapps///ppreee pppprevee..eeeeeeeeeeeeeeeeeeeer fett/forum20 www.ooounnnnndeeeeeeeeee FNNJJ2eee..
Kingma, D. P. and Ba, J. Adam: A method for stochastic
optimization. In International Conference on Learning Representations, 2015. URL
abs 1112/412..00 698C.
Kirsch, L.,, Harrison, J., Sohl-Dickstein, J., and Metz, General-purpose in-context learning by meta-learning transformers. arXiv preprint arXiv:2212.044435 044458,, 2022. URL https::t////mmm aataariivvv... http://twww..oiaa///////////aaaa hwtp:/iw..gga.aaaoaaeaaoaaabaaaa 2212. 24452 04458.
Genewein, T., Delétang, G., Ruoss, A., Wenliang, L.. K., Catt, E., Dutordoir, V., Grau-Moya, J., Orseau, L., Hutter, M., and Veness, J. Memory-basee meta-learning on non- stationary distributions. In International Conference on Machine Learning, pp. 11173-11199 PMLR, 2023.
Kolmogorov, A. N. Three approaches to the quantitative
definition of information. Problems of Information Trans- mission, 1(1):-7,,19 1965.
Goldblum, M., Finzi, M., Rowan, K., and Wilson, A. G. Position: The no free lunch theorem, kolmogorov plexity, and the role of inductive biases in machine learn- ing. In International Conference on Machine Learning. PMLR, 2024.
Lampinen, A. K., Chan, S. C., Singh, A. K., and Shana- han, M. The broader spectrum of in-context learn- ing. arXiv preprint arXiv:2412.03782 2024. URL attps://arxiss httpaaaiiivrrirgaaaaaaaa wwg. /tt.a////442...0
Goyal, M., Tatwawadi, K., Chandak, S., and Ochoa, Deepzip: Lossless data compression using recurrent neu- ral networks. In Data Compression Conference (DCC), pp. 575, 2019. URL https: http::://doo.og///o./... 1109/ DCC 2019.001000000000 00087.
Li, M. and Vitányi, P. An Introduction to Kolmogorov Com- plexity and Its Applications. Springer, 2008
Lu, C., Schroecker, Y., Gu, A., Parisotto, E., Foerster, J., Singh, S., and Behbahani, F. Structured state space mod- els for in-context reinforcement learning. Advances in Neural Information Processing Systems, 2024.
Grau-Moya, J., Genewein, T., Hutter, M., Orseau, L., Dele- tang, G., Catt, E., Ruoss, A., Wenliang, L. K., Mattern, C.,, Aitchison, M., and Veness, J. Learning universal predic- tors. In International Conference on Machine Learning. PMLR, 2024. URL https:// https:://ppeeeeiieeeeeeee http:///pnneeeeeeeeeeeeeeee forum? (erum??d=BBajjn022kk
Mahankali, A. V., Hashimoto, T., and Ma, T. One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. In In- ternational Conference on Learning Representations, 2024. URL
wwwpeeiwwwwweeeeeeeeeee. net//orrumt forum?
id=8p3fu561kk
Grünwald, P. The Minimum Description Length Principle. MIT Press, 2007.
Mikulik, V., Delétang, G., McGrath, T., Genewein, T., Mar- tic, M., Legg. S., and Ortega, Meta-trained agents implement bayes-optimal agents. Advances in Neural Information Processing Systems, 2020.
Grünwald, P. D. and Vitányi, P. M. Kolmogorov complexity and information theory. with an interpretation terms of questions and answers. Journal of Logic, Language and Information, 12:497-529, 2003.
Mingard, C., Rees, H., Valle-Pérez, G., and Louis, A. A. Deep neural networks have an inbuilt Occam's ra- Nature Communications, 16(1):220, 2025. ISSN 2041-1723. URL https:///bd..orr/11...... s 541467-024-54813
Gu, A. and Dao, T. Mamba: Linear-time sequence modeling with selective state spaces. In Conference Language Modeling, 2024. URL https: /ttps/////eeeeeeeeeee/eo net/ forum? wdw.ddxwwYxww1.....
Mittal, S., Bracher, N. I.., Lajoie, G., Jaini, P., and Brubaker, M. A. Exploring exchangeable dataset amortization for bayesian posterior inference. In ICML Workshop on Struc- tured Probabilistic Inference & Generative Modeling, 2023.
Hochreiter, S., Younger, A. S., and Conwell, P. R. Learning to Learn Using Gradient Descent. In Artificial Neural NeCNOr pp. 87-94, 2001.

---

In-Context Learning and Occam's Razor
Mittal, S., Elmoznino, E.,, Gagnon, L.,, Bhardwaj. S., Sridhar, D., and Lajoie, G. Does learning the right latent variables necessarily improve in-contett learning? In International Conference on Machine Learning. PMLR, 2025, URL http:/ pett://arxer /tt./aiivvv//////////////////ava v. org/ abs///////// 240.. 191
Shannon, C. E. A mathematical theory of communication.
ACM SIGMOBILE Mobile Computing and Communica- tions Review, 5(1):3-55, 2001.
Shaw, P., Uszkoreit, J., and Vaswani, A. Self-attention with relative position representations, In Walker, M., Ji, H., and Stent, A. (eds.), Association for Computational Linguisties: Human Language Technologies, Volume (Short Papers), pp. 464-468, 2018. URL https:// aclanthology wrgp/11-2//////.
Müller, S., Hollmann, N., Arango, S. P., Grabocka, J., and Hutter, F. Transformers can do bayesian inference. In International Conference on Learning Representations, 2022. URL httpp:://penneeeee httpa////peeeeeeeeeeeeeeee id=KSugKcbNN9.
Solomonoff, R. J. A formal theory of inductive inference. part i. Information and Control, 7(1):1-22, 1964.
Ollivier, Y. Auto-encoders: sion, 2015. URL URL.ttts://axx.v.orrr 14403 7752.
reconstruction versus compres-
Sunehag, and Hutter, M. Intelligence as inference or
foreing occam on the world. In Conf. on Artificial General Intelligence, 2014.
Olsson, C., Elhage, N., Nanda, N., Joseph, N., DasSarma, N., Henighan, T., Mann, B., Askell, A., Bai, Y., Chen, A., et al. In-context learning and induction heads. CoRR, abs/2209.11895 2022. URL htw.s: peattps:/arxiv..oo/ abs/22053 11895.
Valmeekam, C. S. K., Narayanan, K., Kalathil, D., Cham- berland, J.-F., and Shakkottai, S. Llmzip: Lossless text compression using large language models, 2023. URL 04050.
org. /tads//230 02000.00000.0....
Ortega, P. A., Wang. J. X., Rowland, M., Genewein, T.,
Vapnik, V. N., Vapnik, V., et al. Statistical learning theory. wiley New York, 1998.
Kurth-Nelson, Z., Pascanu, R., Heess, N., Veness, J., Pritzel, A., Sprechmann, P., et al. Meta-learning of se- quential strategies. arXiv preprint arXiv: 2019. URL https:/ http//aaxxvv....//a////// 03030.
Veness, J., Bellemare, M. G., Hutter, M., Chua, A., and Desjardins, G. Compress and control. In AAAI Conference on Artificial Intelligence, pp. 5016-3023.
Oswald, J. V., Niklasson, E., Schlegel, M., Kobayashi, S., Zucchet, N., Scherrer, N., Miller, N., Sandler, M., Arcas,
AAAI Press, 2015. URL httppss//ooj...aaal org/ index. wndex.php// /At.//AAA///AAA /tt.///aticcl//eeee////aaa
B. A., Vladymyrov, M., Pascanu, R., and Sacramento, J. Uncovering mesa-optimization algorithms in trans- formers. CoRR, abs/2309.05858, 2023. URL https: //doi, ///oi.org//// 4855488555//// wtt.:iiii.......... 05858.
Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M. Transformers learn in-context by gradient descent. In In- terattoonll Conference Machine Learning, pp. 35151- 35174. PMLR, 2023. URL https:: openreviee. net / forum htt./foormmiiddtee iiettitttttiiii Qma5.
Panwar, M., Ahuja, K., and Goyal, N. In-context learning through the bayesian prism. International Conference on Learning Representations, 2024. URL https: // openreview wwt fortt//orumme wtw.urmmnidiitddddsssoooooo
Wang. X., Zhu, W., Saxon, M., Steyvers, M., and Wang, W. Y. Large language models are latent variable mod- els: Explaining and finding good demonstrations for in-context learning. In Conference on Neural Infor- mation Processing Systems, 2023. URL https:// openreview net forummidd-GGkw25ce..
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Rathmanner, S. and Hutter, M. A philosophical treatise of universal induction. Entropy, 13(6):1076- 1136, 2011.
Witten, H. Neal, R. M., and Cleary, J. G. Arithmetic coding for data compression. Communications of the ACM, 30(6):520-5400 1987.
Raventós, A., Paul, M., Chen, F., and Ganguli, S. Pretrain- ing task diversity and the emergence of non-bayesian in-context learning for regression. Advances in Neural Information Processing Systems, 2024.
Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. An ex- planation of in-context learning as implicit bayesian infer- ence. In International Conference Learning Represen- tations, 2022. URL https: openreview. .etereviieeeeee///eeeee forum? wiaiumidd-RddvecC.
Santoro, A., Bartunov, S., Botvinick, M., Wier- stra, D., and Lillicrap, T. Meta-learning with memory-augmented neural networks. In Interna- tional Conference on Machine Learning. PMLR, 2016. URL wwtphttps/// / santorol 6. .pff.
Zhang, R., Frei, S., and Bartlett, P. L. Trained transform- ers learn linear models in-context. Journal of Machine Learning Research, 25(1):49:1 149:55, 2024.
http:///pooceeen...eeee URbbtpp:/prooeddng mlr. press/v48/ stt.oeedddngg......pree///aa
12

---

In-Context Learning and Occam's Razor
Zhang, X., Li, X., Dou, D., and Wu, J. Measuring in- formation transfer in neural networks. arXiv preprint 077244 2020. URL https:/ /arxiv. org/aba 200/
Zhou, H., Bradley, A., Litwiin E., Razin, N., Saremi, O., Susskind, J. M., Bengio, S., and Nakkiran, P. What algorithms can transformers learn? study in length generalization. In International Conference on Learning Representations, 2024. URL https: : / /oppnrevie...... uet/fozee futt/ooummicc Ass
As IuHnmiXX.
13

---

In-Context Learning and Occam's Razor
A. Background on Kolmogorov complexity
Kolmogorov complexity was independently developed in the 1960s by Kolmogorov (1965), Solomonoff (1964), and Chaitin (1966), and defines a notion of "information quantity".
Intuitively, the Kolmogorov complexity of an object is the length of the shortest program (in some programming language) that outputs that object. Specifically, given some finite string 2, ((x) is the length ((r) (in bits) of the shortest binary program r that prints v and halts. Let U be a universal Turing machine that executes these programs. The Kolmogorov complexity of a is then:
((x) min(((mn:: U(r) = xrr 10,1)"}
(6)
where (0, 1)* denotes the space of finite binary strings. A related notion is the conditional Kolmogorov complexity of a string given another string y, which is the length of the shortest program that takes y as input and outputs æ:
K(rly) = min U((()) = =, E (0, 13"),
where r(y) denotes program taking y as input. Finally, we can also define a "joint" Kolmogorov complexity (( y), which denotes the length of the shortest program that jointly outputs both x and Surprisingly, joint Kolmogorov complexity is related to conditional Kolmogorov complexity (up to an additive logarithmic term, which we will ignore) by the Symmetry of Information theorem (Li & Vitányi, 2008):
K(a,y) v) K(yla) + K(x) = ((dly) + K(y).
(8)
Kolmogorov complexity has many intuitive properties that make it attractive as a measure of information quantity, and although it is less common than notions from Shannon information theory (Shannon, 2001). it strictly more general (as we will show later below). The smaller and the more "structure" object has has-regullrityy patterns, rules, etc.-the more easily it can be described by short program and the lower its Kolmogorov complexity. Kolmogorov complexity therefore is deeply rooted in the idea of compression. For instance, a sequence with repeating patterns or a dataset that spans a low-dimeniiona subspace can be significantly compressed relative to its original size, and this results in low Kolmogorov complexity. In contrast, a random string devoid of any structure cannot be compressed at all and must in effect be "hard-coded", making its Kolmogorov complexity equal to its original size in bits.
While powerful, Kolmogorov complexity has certain limitations. First and foremost, Kolmogorov is intractable compute exactly because it requires brute force search over exponentially large space of possible programs. It is therefore often of conceptual rather than practical value, although it can nevertheless be upper-bounded using more efficient compression strategies. Second, Kolmogorov complexity depends on the programming language of choice. For instance, if a programming language has a built-in primitive for the object being encoded, Kolmogorov complexity is trivially small. This concern, however, is often overblown: given any two complexity that they assign to an object is upper-bounded by constant that is independent of the object itself, because any Turing-comppi complet programming language can simulate another (Grünwald & Vitányi, 2003; Fortnow, 2000). In practice, can simply consider "reasonable" Turing-comples" programming languages that don't 't contain arbitrary object-specific primitives, in which case this simulation constant will be relatively small and the particular programming language of choice will have little effect. Finally, Kolmogorov complexity is only defined for discrete objects because no terminating program can output continuous number with infinite precision. This concern is also less consequential in practice, because we can always represent continuous objects using finite (e.g., Srating-poimt precision.
programming languages, the difference Kolmogorov
Important properties for machine learning. In ML, we are often concerned with datasets and probabilistic models. Kolmogorov complexity relates to these two concepts in several interesting ways. First, we can ask about the Kolmogorov complexity of a finite dataset X "r, where each sample drawn iid from distribution p(x). It turns out that if
14

---

In-Context Learning and Occam's Razor
have access to the true distribution p(x), optimal algorithms such as arithmetic coding (Witten et al., 1987) can encode each sample using only log2 p(x:) bits. Intuitively, this is because samples that occur more frequently be encoded using shorter codes in order to achieve overall better compression. We thus have that:
n loga p(æ,).
k(Xpp)
(9)
If instead of access to the true distribution p(x) we only have prohabilistic model of the data po (3), we have that:
K(X)pe) S
log2 po (24,,
(10)
where we have equality when = p. This insight is significant. Notice that - > loga po();) is the negative log- likelihood of the data under the model, which is a common loss function used in ML. This tells us that models with lower error better compress their data, and directly relates Kolmogorov complexity to optimization in ML. However, what if we do not have a model? What is the Kolmogorov complexity of the data itself? Intuitively, if the dataset is sufficiently large, the optimal method for encoding it should be to first specify model and then encode the data using that model as in Equation (10). Specifically, using identities in Fortnow (2000), we have:
((X)= < K pp) + (Po)).
(11)
This encoding scheme on the RHS is referred to as a 2-part code (Grünwald, 2007). We have equality when the model's description length and error are jointly minimized, which occurs when the model (2 is equivalent to the true distribution p(x):
K(X) = arg min K(X + Kpps)= = arg min Po
loga pa (z())) + ((p))
(12)
Pe
= k(X + K(p) = Σ
log, p(x,) + Kp)).
(13)
Again, we draw important connections to ML. Equation (11) says that the Kolmogorov complexity of dataset is upper-bounded by the model's error and complexity. In addition, Equations (12) and (13) tell us that the simplest model that explains the data is most likely to be the true one, which draws theoretical link between compression, maximum likelihood training, model complexity, and generalization (Goldblum et al., 2024).
Relation to Shannon information. In Shannon information theory (Shannon, 2001), the notion of information quantity is entropy. Given a random variable X ~ p(z), entropy is defined as: (X) = Ee=p(a) - (og)() Notice that the -loga (p(x)) inside the expectation is equal the quantity inside the sum of Equation (9), which specified the minimum number of bits needed to encode a sample from dataset given the distribution that sample was drawn from. This is no accident: entropy be seen as the average number of bits needed to compress events from distribution using optimal encoding scheme when the distribution p(x) is known. If we simply sum these bits for finite number of samples instead of taking an expectation, we get exactly K [(X) p) as defined in Equation (9).
As we have seen, though, the assumption about a known distribution p(x). need not be made in the Kolmogorov complexity framework. In this sense, Kolmogorov complexity a strict generalization Shannon information theory: K (X) as defined in Equation (13) is equivalent to summed entropy plus the complexity of the distribution p(z), which unknown and needs to be encoded. In the Shannon framework, it difficult to derive meaningful notion for the information quantity in the distribution p(z) because it is an individual object- function, in particular- and Shannon information is only defined for random variables (Grünwald & Vitányi, 2003). A second drawback of Shannon information is that entropy is a measure of statistical determinability of states; information is fully determined by the probability distribution on states and unrelated to the representation, structure, or content of the individual states themselves (Grünwald & Vitányi, 2003). For this current work, we require a notion of complexity that can account for representations and functions, making Kolmogorov complexity better suited to the task.
15

---

In-Context Learning and Occam's Razor
B. Prequential coding and compression without known learning algorithm
When introducing the relationship between prequential coding and optimal compression Equation (4), we mentioned that key assumption that the learning algorithm T is known. reality, then, we have that:
K(D) & K(D, = (TD + (T)
(14)
(15)
I (D:T)
(16)
Lprea (D; + (D;T)+ K(T) Z K(D),
(17)
where inequality Equation (14) appears because compressing additional objects can only take more bits, and inequality Equation (16) comes from the fact that prequential coding is not necessarily the optimal way to compress a dataset given a learning algorithm. If the learning algorithm is a short program like SGD, however, then (TT) and Lpreg (D; T) an upper-bound on K (D). For simple learning algorithms, then, Equation (4) holds.
C. Experiment and task details
In this section, we provide additional experimental details, including a comprchensive overview of the model architectures and hyperparameters used during training. All experiments were run on GPUs with at least 32 GB of RAM, and each took less than day to run on single NVIDIA V100 with all seeds stated figure captions.
C.1. Meta-learner architectures
We considered different architectures which exhibit ICL to study and compare their ability to minimize prequential code length (Section 3.3). Each architecture described here parameterizes the meta-learner Tø-
Transformer with bottleneck. We use standard causal decoder-only Transformer with 4 layers, 4 attention heads, 256 latent dimensions and a feed-forward network with 512 dimensions. Additionally, it has linear projection that bottlenecks the Transformer to 128 dimension. A 5-layer MLP with RELU activations and 256 latent dimensions used as separate prediction head.
The Transformer takes dataset D input in the format [z1, M1], [x2, ye]..... [Ty ynl (where æ; and yı are concatenated and each is token) and computes T& (D:t-1) for each context size starting from (Dia-)1 is based on the encoding of the t-th token, which attends only to tokens that appear to the left of [x,, yr] and itself. Information leakage from future tokens is prevented using a causal mask. After computing To (D we concatenate with 2e (i.e., (D zx) and pass this combined input to an MLP prediction head to predict the next y-token.
1. The computation of
Transformer without bottleneck. We use custom encoder-decoder Transformer with 4 layers, 4 attention heads, 256 latent dimensions and a feed-forward network with 512 dimensions. Also, in contrast to the previous architecture we don't tt use a separate prediction head.
To allow for parallel processing at each position r without leaking information about the corresponding y in a model without bottleneck, we augment a standard Transformer architecture in the following manner. It considers two sets of tokens, namely (a) D in the format [o. 0), [x1. 91]. [z2. 32).... ... [an ynl (where z; and y/s are concatenated for each token), and (b) X the format [m)], [122]..... [Ir]] (where each token only has information). Note that [+] describes token, and the first token in D represents empty context.
Each layer of this Transformer performs the following attention procedures:
( Attention (Query (1-1) Key ( Value ((111) Mask M
(18)
D Attention (Query ((-11) Key (1-1)) Value D(I-1) Mask MMP
(19)
16

---

In-Context Learning and Occam's Razor
where MM ensures that X x!"-1) can only attend to D/---1 and M ensures that D! can only attend to D!=") Both ( and D( go through a residual feed-forward network after the attention operations.
Note that the above operation achieves two distinct properties: (a) it prevents the token [xg] from accessing information about y/ while allowing access to all 11 and V1:--1 in making the corresponding prediction, and (b) akin to standard Transformers the [1a, We] token can attend to 3i and y1:t.
Mamba. We experiment with two state-space model (SSM) architectures, Mamba 1 and Mamba 2, both composed of 4 layers. 256 latent dimensions, state dimensions 8, and local convolution dimension of 4. Additionally, each layer includes a gated MIP with 256 latent dimensions. Similar, to the Transformer with bottleneck, the prediction model is 5-layer MLP with RELU activations and 256 latent dimensions is used as a separate prediction head.
The SSM takes a dataset D as input in the format [æ1. y1l, [22, val.................. [In, yn. (where 2; and y are concatenated and each []] is token). For each context of size t- 1, we compute the (=(D==-1) which is vector that represents the parameters of the output model obtained after processing the first t data points. After computing (o-D:sr)),, we concatenate it with Iy (i.e., [To (1a-1), 2/) and pass this combined input an MLP prediction head to predict the next y-token.
C.2. Meta-training and evaluation setup
In this section, we outline the complete set of hyperparameters and configurations used across different training objectives and model architectures in experiments.
In-context learner (prequential and train-risk). We trained both the Transformer-based meta-lcarner (with and without bottleneck) for 50 epochs and the Mamba-based meta-learners for 120 epochs. All results were averaged across 5 different random seeds to mitigate the effect of randomness in the pipeline. The training was conducted on a meta-dataset consisting of 10,000 tasks, each with 1,000 data points that serve as context. We used the Adam optimizer (Kingma & Ba, 2015) with a learning rate of 17 = 0.0001 and a batch size of 256, without any early stopping. After meta-training, we evaluated the learners on a distinct meta-dataser of 100 tasks, each with 1,000 data points.
Gradient based learner. Since gradient- based learner are off-the-shee shelf learning algorithms which don't 't require meta- training. The prediction model used is 5-layers MLP with RELU activations and latent dimensions of 64 or 256 depending on the complexity of the task. We used and validation (20%). At each step of prequential coding, we train and evaluate a model by randomly sampling a dataset of fixed size across each of the tasks, starting from 20 to 2000 datapoints. We used an early stopping criteria with minimum loss delta of 0.001 and patience of 10 epochs to avoid overfitting. On each of them, the prediction model was fit using the Adam optimizer (Kingma& & Ba, 2015) with a learning rate of 17 = 0.0001 and a batch size of 64. All results were averaged across 15 different random seeds.
dataset of 10000 tasks (with 2000 data points each) split into training (80%)
C.3. Visualization of the model inferred in-context
For a given context length, next-token loss serves as a quantitative proxy for the overfitting behavior of a learned prediction function. Beyond that metric, in experiments generating Figure 3, we visualized the kinds of models inferred by ICL on simple regression problems in a way that lets us clearly inspect their complexities. The tasks consist of noisy polynomial regression problems of the form:
f(x) = Σ Cx() +
where C2 is the i-th Chebyshev polynomial of the first kind and e N(00, o²). We use this basis of polynomials instead of the usual canonical basis for both data generation and the hypothesis class of our learned predictor, due to the favorable numerical properties (e.g.. orthogonality) of the Chebyshev basis. Specifically, when used to generate data, Chebyshev polynomials offer better coverage of different functional behaviors; and when used for function approximation, they lead to smaller approximation error and faster convergence.
We train prequential ICL and train-risk ICL for 400 epochs on a experiment with both k (linear functions) and (cubic functions). We use a bottlenecked model (Section C.1)
of 20000 functions of degree up to k. We
17

---

In-Context Learning and Occam's Razor
infer the Chebyshev polynomial coefficients E RR of the unknown function f. where make N > k that the in-context models have the capacity necessary overfit the training data. These inferred coefficients are then passed to parameter-less prediction head that, given query input Z.g, computes:
f( a) Σ a,C.(a).
Restricting the regression tasks functions of degree & N allows to compare learners in the over-parameterizeed regime, which is the most common settings in modern machine learning. Our results, shown in Figure 3, align with the trends observed in Figure 2, confirming that train-risk ICI. more frequently exploits high-degree components (i.e., degrees strictly greater than k) to overfit in-context training data, compared to prequential ICL which fits simpler models closer to the ground-truth data-generating processes.
C.4. Pretrained LLM on Mastermind
As described in Section 3.4, we evaluate the performance of a pretrained LLM on the Mastermind task using one of the latest OpenAl models GPT-4 (i.e., gpt-4o). To query the model, we used the OpenAl API with a temperature of O, ensuring that the outputs are deterministic. Along with the responses, we also obtained the log probabilities using the API for calculating the prediction error with respect each query. This was possible using logprobs (boolean) and cop.k.logprobs (integer) attributes in the API that returns log probabilities for each token in the response and the tokens with the top log probabilities corresponding each token in response. By using structured prompting technique and retry mechanism (up 10 retries in case of failure to adhere the required output format), we were able to consistently obtain appropriate responses to our queries. An example prompt, which includes the task description, context, and the query, is provided below. To calculate the prequential code length, we iteratively query novel examples with an increasing number of in-context examples and obtain the prediction errors. This process emulates the prequential ICL objective.
Example Prompt
have secret code in mind. It's a 8-digit code with each digit ranging between 0 and 5. I'll give you couple example guesses, and for each guess I'1l tell you two numbers:
First number: the number of correct correct digits at their correct position. Second number: the number of correct digits, which aren't necessarily in the correct position.
Here's a demo to show you what guess and response would look like. Imagine my secret code was:
5 2 1 3 4 2 4
And imagine the guess I presented you was:
1 1 0 2
Then, the response would be:
The response is the way it is because the first, forth and last digit were in the correct place (first response number is therefore 3) and additionally the second and sixth digit were in the guess but at the wrong position (second response number is therefore 5).
The game is about to start. I'll present you with series of guesses and guess, and you' 11
their responses. Finally, will present you with have to predict the correct response. Make sure your response is formatted the same way as in the examples (i.e., with 2 digits between 0-8, separated by a space). Let's s begin.
18

---

Response: In-Context Learning and Occam's Razor
Guess:
4
2
0 0
5
Response:
3
Guess:
1
1
5
5
0
1
Response:
Guess: 3 0
5
3
Response: 2 6
Guess: 0
2 5
0
4
2
0
1
Guess: 4
Response:
What do you think the response is for this final guess? Make sure to reply with just 2 digits between 0-8, separated by a single space character.
C.5. Hidden Markov Model task
prominent theory for why ICL emerges from the next-token prediction objective of LLMs is that sequences 21:0. in the pretraining dataset (e.g. large corpuses of text) can be interpreted as implicitly being sampled from a latent variable generative model (z T) where T are some abstract concepts underlying samples (Chan al., 2022; Xie et al., 2022). range from abstract style attributes in natural language (Xie al., 2022) lask parameters such the teacher weight matrix in linear regression ICL task (Von Oswald et al., 2023); the important part is that some latent variables can be inferred from the context and subsequently aid prediction. ICL would then emerge as the ability of performing implicit Bayesian inference (i.e. learn from the context) in order to predict Zzz
Q Ieet
Σ (1 IT), Q(T x<e))
(20)
Condition on the Latent
Infer latent
We propose to leverage this conceptual framework to devise novel generation procedure for synthetic LLM pretraining datasets. The general idea is to design family of sequence models Q (z(11)) parameterized by task latents т. leading to the latent variable generative distribution
Q IT) (x
Specifically, we use Hidden Markov Models (HMMs) as the sequences models, and we parameterize the HMMs Q (Xinn) with parameters fT) ,/ We use this function f to introduce syper-parameters & which define the whole family of sequence models; i.e. the dataset. Below, we define in details specific ad-hoc function fe(T) which generates family of HMM where each member share non-trivial structure.
C. DETAILED DESCRIPTION OF THE GENERATIVE PROCESS
HMM defines probability distribution over sequences of observations 2; E X' with discrete-time probabilistic process over hidden states 2, Z paired with a mapping + X. Both and are discrete sets. The hidden process defined by an initial state distribution (2) and transition matrix A Z| such that
Q(+122)) = Aji
Lastly, the mapping between states and observations is governed by the emission matrix B E RR [| such that
(xyy22) Byg
19

---

In-Context Learning and Occam's Razor
In the rest of the section, will explicitly define how fT( generates 1/+ (n", Az, ,")). We first give high level description.
The hyper-panne apper-parameters & will define number of building blocks which will be used to create the transition and emission matrix of all HMMs. Then T will specify a specific way to combine and manipulate these building blocks to instantiate a specific HMM Q.. For the transition matrix A", , the building blocks are pre-defined cycles; which are combined, flipped and accelerated based on т. For the emission matrix B", the building blocks are groups of sub-emission matrices which each only affect subset of [2]] which are combined and possibly internal shifted based on т. Overall, we will have
6 = (N_BASE_CYCO
L_BAS__SPEEDS N. CYCLE.FAMILIE
W.GROUU.PERR_FAT PER.PPMIE,,,, N_FAMILY FFAMILYSPPEEDS, N EMIISION.GROUPS, EMISSION GROUP, EMISSION.SHHIFT SHIFF)
and
(BASE_ID, SASE,, FAMILIES IDD; FAMILIES, SSPEED, EMISSION IDs, EMISSION_SHIFT
We will refer to the dimensions of &, T as E.. 7 to avoid clutter and discuss further details below.
Transition matrix A². We define a cycle as sequence of hidden states (co: -.el--.)) & E 2, and the following manipulation functions
DIR(C, I:) (co, 9..
.1)
if k
c
otherwise.
SPEED(C, k:) = (Co, (m(ddd [ol)> (28 lel))....)
In words, SPEED(C, k) changes the speed at which the cycle is traversed and DIR(C, k) change its direction. We finally define the transition matrix (cc) associated with cycle such that
{
if F nst (i, (Cks C4+1 m))
T(c)s)
otherwise.
Initially, we randomly generate Eo base cycles b; which go through all states 2, Further, we initialize &2 families Ea groups of cycles g): i e [Ei), j E [62]. Each HMM's transition matrix is then built from these "building blocks" cycles. Specifically.
Ex
A" = ((SPEED(DIR(O,.m)))) m1), T2))
((PPE) Ts),
T4
j=l
In words, each transition matrix is made a) one of &u base cycle, possibly sped up and flipped and b) & groups of smaller cycles (each from a pool of &a groups), possibly sped up and flipped. The number of possible speeds for the base cycle defined by & For the cycle families, defined by &
Emission matrix BT, We separate the states Z in groups h; 2 and for each group initialize &a sub-emission matrices H3 E IR. h. x|21, Then, we define the manipulation function SHIFT(H, k) which applies circular shift of & to the indices of the matrix. Finally, we have
BT Σ SHIFT(B' (TB.))
In words, each emission matrix is made of &, possibly overlapping sub-emission matrix, each picked from pool of Eo unique ones. The number possible shifts is &
Initial distribution. We always use the uniform distribution.
20

---

In-Context Learning and Occam's Razor
C.5.2. HMM CYPER-PARAMETER
For experiments in this paper, we use | 50 and |2] 20. The hyper-parameters of f. E, are given in Table C.I. This results in total of 512 different transition matrices and 24 different emission matrices, for total of 12,228 different HMMs. We show results averaged from 5 different seed.
N.BASE.CYCLES (En)
4
N-BASE_SPEEDS (51)
2
N.CYCLE.FAMILIES (E2)
3
N.GROUP_PER FAMILY (Es)
2
N_FAMILY _SPEEDS (E.)
2
L.EMISSSON.GROOPS (Es)
3
L.EMISSION.PER.GROOO (E6)
2
N.EMISSION~SHIIT (Ez)
Table C.I. HMM dataset hyper-parameters
C.5.3. TRAINING
We train on 200,000 trajectories from 60,000 unique compositions of latent variables, and evaluate on 50,000 trajectories from 13,728 held out compositions of latent variables. Training consists on next-token prediction with a cross-entropy loss. We use the same model and training hyperparameters as in Section C.I and Section C.2.
D. Effect of task difficulty on prequential code length
In Section 3.1 Figure 2, we found that a meta-learned in-context learner trained to minimize prequential code length (prequential ICL) was better able to generalize than one that only minimized training error (train-risk ICL). We further noted that the gap in generalization error between these two learners was greater low-data regimes, and that the gap extended further as a function of task difficulty (i.e., more in-context data was required close the gap going from linear regression, to sinusoid regression, to Mastermind). This result is predicted by our theory relating ICL Occam's razor. A complex task requires the algorithm to learn more complex functions successfully minimize train risk. However, learning more complex functions with very limited data leads to overfitting, which is the basis for our hypothesis that as task complexity increases, simple predictors learned by minimizing prequential code length enjoy bigger advantage over predictors learned by minimizing train risk.
To investigate the effect of task difficulty more systematically in this section, we fix the underlying meta-dataset (sinusoid regression tasks) and vary the dimensionality of the input data dim(z). We plot our results in Figure D.I, showing the difference in generalization error between train-risk ICL learners and prequential ICI. learners. As expected, ask task difficulty increases, this generalization gap extends further, and the train-risk learners must observe more data in-context in order to close it.
E. Effect of SGD regularization on prequential code length
Regularization techniques are widely used for gradient- based learners to prevent over-fitted solutions. In this experiment we fit prediction models considering different regularization techniques, namely carly-stopping combined with validation data, and weight-decns (L2 regularization). The results presented in Figure E. E.xperiments with early-stoppin halt training when the validation loss does not decrease by more than Ie 4 over 10 consecutive steps. Experiments with weight-decay consider a regularization parameter À E {0.05, 0.005] and were trained for 1000 epochs. The prediction models used are 5-layers MLPs with RELU activations and latent dimensions of 64. The different prediction models were fit using an Adam optimizer (Kingma & Ba, 2015) with a learning rate of r = 0.0001 and a batch size of 64, All results were averaged across 15 different random seeds.
21

---

In-Context Learning and Occam's Razor
Sinusold regression
Task dimensionality
Generallzer allzatioon
Datapoints seen
Figure D.I. Comparison of gap between prequential ICL. and train-risk ICL as function of task difficulty. Figure shows the difference in average prequential coding curves (i.c., generalization error for triinrrisk ICL generalization error for prequential ICL) for sinusoid regression tasks of increasing input dimensionality, Error measured using MSE. Error bars show standard error across seeds. For all task dimensionalities, the performance gap is positive: ICL from next-token prediction objectives (prequential ICL) yields lower prequential code lengths than ICL from past-token prediction objectives (train-risk ICL), with greater effects in low-data regimes. This gap in generalization error increases with task dimensionality, demonstrating that learners which minimize prequential code length generalize better in virtue of fitting simpler models, and that these simpler models are most important when generalization is difficult (i.c., when the task dimensionality is large relative the amount of training data observed).
Linear regression
Generaltzation error
Prequential Unregularized
Validation early stop
L2 (0.005)
(0.05)
10'
Datapoints seen
Figure E. Experimental results comparing different regularization techniques. Figure show average prequential coding curves obtained using both unregularized and regularized Adam optimizers on a linear regression task. Regularized learners exhibit better compression rate (i.e. lower PCL), which implies stronger incentive toward simple models according to theory. This experiment confirms the claim that regularization techniques serve as indirect Occam's 's aligned methods to learn simple models. Analogous to the meta-learning setting, PCL could be minimized with respect the hyperparameters of the regularization technique.
F. Hidden-Markoy--oode task comparisons to ICL with train-risk objective and SGD
In Section 3.1, we only considered iid tasks so that we could make fair comparisons to learners that minimize training error under tid assumptions (i.e., train-risk ICL and SGD). this section, we nevertheless attempt make these comparisons on synthetically-generaal details on this data.
nonstationary data from Hidden Markov Models (HMMs). See Appendix C for further
By default, our HMM tasks are not amenable to learners that minimize train-risk. This is because in our theory, we see individual context tokens as "datapoints" that are processed separately by train-risk model to minimize prediction error. However, on a nonstationary sequence dataset, the learnable structure is about the relationship between datapoints. While this sort of structure is ordinarily learned by minimizing next-token prediction error, this amounts to prequential ICL. train-risk bascline would somehow need be trained minimize error on previously observed tokens in the context, and there is way to query the model on such tokens training time while evaluating its predictions on the next token at inference time.
To make our HMM tasks amenable to learners that minimize train-risk, we applied a simple transformation that turned the sequence datasets into supervised learning problems. Call a sequence of HMM observations D = (Vi...., yk), where the subscript denotes the time index. We transform into a supervised learning dataset {(x1 = 1, 1/),,... (Zx = k, y/)) where y/ a model observation and z; the integer time index of that observation. In this way, we can evaluate train-risk
22

---

In-Context Learning and Occam's Razor
ICL and SGD in the same way for our iid supervised datasets, and measure prequential code length by querying the resulting models on the next timepoint 21+1- For fair comparison, prequential ICL. was also trained and evaluated used the same supervised version of the HMM task. As technical note, we embed each æ; using relative positional encodings (Shaw et al., 2018).
HMM
Ceneralization erfor
10"
prequential
train-tikk ICL SGD (no meta-leaming)
10
10'
10"
Datapoints seen
Figure F.I. Comparisons between prequential ICL, train-risk ICL, and SGD on nonstationary HMM data. Average prequential coding curve for meta-dataset sampled from HMMs, which is the mean prediction error the next unobserved token (generalization error, y-axis) given observed contexts of increasing length (datapoints seen, x-axis). The area underneath these curves corresponds to prequential code length. Error is measured using cross-entropy. Error bars show standard error across seeds (5 for ICL, 15 for SGD).
Our results are shown in Figure F.I, where we use the same models and training setup as in Section 3.1. We find that prequential ICL, as expected, minimizes prequential code length well and generalizes at all context lengths. This shows how prequential coding through ICL can fit simple models that compress not only iid, but also nonstationary data due to the baickly-adapting online nature of the learning algorithm. In contrast, both train-risk ICL and SGD fail to generalize at every context length, and are unable to predict the next token in a sequence at inference time after having only been trained to fit the earlier part of the sequence.
G. Effect of sequence length used at pretraining for HMM task: Full vs. Partial
As argued in Section 2.4, an in-context learner behaves as an effective online compression algorithm known as prequential coding. The fact that it implements such procedure lies in the fact that it is tasked iteratively make predictions on novel data given increasing numbers of datapoints in-context, starting from empty context.
Exactly we did with train-risk ICI., we could have come up with different training objective, such that the in-context learner trained on it no longer implements prequential coding, One possibility is to train an in-context learner to predict only on the last half of the context instead of the full context. Note that in both cases, the learner still observes the full context, but gradients are only computed and backpropagated for predictions made on the second half. This adjustment is made to mimic the standard way of training of LLMs, where predictions are primarily made under large-context conditions; even though early tokens in sequence initially have shorter contexts, the majority of training steps occur once the context window is sufficiently filled. While this training scheme does not correspond to any known coding algorithm for data compression, we conjecture that such learner has weaker incentive toward compression and should therefore yield worse generalization performance than its prequential ICL counterpart.
GPT
Mamba
Genera ization etror
5
Only suffix Full sequence
4
10P
10a
102
105
10a
102
Datapoints seen
Datapoints seen
Figure G.I. Impact of partial-context training on next-token prediction in HMM data. Mean next-token prediction error (generaliza- tion error, y-axis) as a function of observed context length (x-axis), comparing models meta-trained trained predict full sequences versus only the latter half of sequences. Results are shown for two architectures: GPT-2-style transformer and Mamba. For contexts longer than 100 tokens (half the maximum sequence length), there is no statistically significant difference in generalization error between the two training regimes, suggesting that the In- In-Context learner trained the prequential way does not learn simpler model in this setting.
23

---

In-Context Learning and Occam's Razor
As Figure G.1 shows, the model pre-trained on sequences for which no auto-regressive gradient was used for the first half of the sequence (shown "only suffx"") shows worse generalization than the model training to minimize the full prequential coding curve. As expected, this discrepancy is stronger in low data regimes and the gap between the two models shrinks as testing sequence length grows. Future experiments could further explore generalization properties of pre-trained learners based on accessible sequence length and on task iid requirements.
H. Advantages over the Bayesian perspective
The Bayes-optimal prediction perspective of ICL and meta-learning says that by meta-training on some set of tasks D, the learner infers some prior over latent task variables- or, equivalently, a prior over models popdelssp(ppl 9). On some novel task D, the learner then infers posterior over models that both explain the training data (i.e., assign it a high likelihood) and are consistent with the prior: p P D) = p(D(pe) )ppa 9)/2, where Z is a normalizing constant. According to the theory, subsequent predictions are then done through implicit Bayesian averaging under this posterior model distribution.
Crucial differences in our theory are that 2 does not need to be drawn from a well-defined distribution over tasks for us to reason about the meta-learning problem (the Kolmogorov framework does not require this) and minimizing Ei Lpreg (D';Ta)
EdI - (Ta)) need not induce prior probability distribution over models given 2 (although it can if this is the best way to compress the meta-dataset using the meta-leamer TT). As result, our theory generalizes the Bayesian perspective.
To see why these generalizations provide value, consider where the prior in the Bayesian framework p(pol 2 comes from. This prior is not defined explicitly in the ICL framework; instead, it is implicitly defined based on 9, the implicit initial prior p(po), and the implicit inference machinery that approximates p(po / = p( 9 (1o (p)))(()/Z. All of these implicit components make any meaningful analysis difficult, since it is difficult characterize them. However, these implicit components are all intrinsic properties of the meta-learning algorithm (the meta-learner' architecture, the meta-objective, etc.), which we do have explicit control over. Our theory only makes reference to this meta-learner T's and the description length of data under it Lpreg (D:; TT) 2 K(D), rather than to objects that are only implicitly defined (and never known). As such, we argue that our theory is more amenable to analysis and provides more explanatory value.
For example, in the Kolmogorov framework that we have proposed, it is easy to see how ICL might in some cases generalize to novel dataset D that is entirely out-o--domain with respect D. Perhaps, for instance, the tasks have compositional structure and Tg has some inductive biases for compositional generalization. In contrast, it is far more difficult to find good explanation for such a phenomenon in the Bayesian framework. The explanation would have to be in terms of some implicit initial prior p(pe) (which we never defined) and the subsequent prior p(pa ( that it induced, which can easily lead to just-so stories of the form "generalization here must have been possible because p(pe) had the right kind of structure". However, this sort of post-hoc rationale could be used to explain any outcome (positive or negative), and is therefore problematic as a scientific explanation (Deutsch, 2012).
Another problem with the Bayesian perspective is that its predictions do not always hold in practice. Notably, Raventós et al. (2024) found that when the diversity in pretraining tasks is sufficiently large, solutions emerge that are not consistent with Bayes-optimal predictor that uses the pretraining task distribution as its prior. Instead, the solution is consistent with much broader prior, which allows the learner to adapt to novel tasks that are outside of the pretraining task distribution. Our theory, in contrast, permits explanations for this phenomenon. For instance, perhaps that model used to parameterize To had insufficient capacity to encode a diverse (and potentially complex) prior over tasks, and instead learned a simpler approximation with more broad coverage over a larger space of tasks.
24


Reviews:
[{"review_id": "bdzL5UCJ9T", "reviewer": "Reviewer_dU6f", "summary": "The paper studies the problem of incontext learning(ICL) and establishes a connection between ICL and Occam's Razor, arguing that next token prediction used in training Transformers implicitly minimizes both the training error and complexity of the learned model. The authors show that this joint objective is equivalent to prequential coding and the meta-learning problem of minimizing the prequential code length is already solved by next token prediction objective used in training ICL. Through both theoretical analysis and experimental results, the authors argue that ICL implicitly favors simpler model that generalize well which is in line with the principle of Occam's Razor.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review.\n\n**Minimizing a tractable upper bound on an intractable objective is valid and common in ML**\n\n> The connection between prequential encoding and ICL meta-training is more of an upper bound rather than a direct equivalence.\n> \n\nThe reviewer is correct in pointing out the upper bound given by prequential code length (PCL). It would be ideal to directly minimize Kolmogorov complexity, though this is widely known as being intractable. \n\nIn contrast, we minimize an upper bound (with learnable parameters $T_\\phi$), following a long line of work in ML. For example, as we state in our paper (L156-159 RHS), all variational inference methods that minimize the negative evidence lower bound (ELBO)—from variational auto-encoders to diffusion models—learn via a tractable bound to an intractable quantity (the negative log likelihood). In compression too, there is longstanding work (c.f., [1]) proposing variational approximations to minimizing the complexity of deep learning models. Pushing down the upper-bound is a workable proxy for optimizing a target quantity, therefore our argument that minimizing PCL minimizes training error + model complexity is valid. Finally, even when it is not being minimized through a meta-learning objective, PCL has been found to be a strong compression algorithm in deep learning settings [2], bounding $K(D, p)$ better than other methods. We will further clarify this important point in revisions.\n\n**Prequential coding through next-token prediction with sequence models abstracts over meta-training algorithm and meta-learner architecture**\n\n> The prequential encoding does not directly suggest the specific meta-training algorithm or architectures used.\n> \n\nIt is an advantage of our theory to provide a compression-based account of ICL for sequence models without being specific to particular architecture choices: indeed, we show that the theory holds for both Transformers and state-space-models (Section 3.3). Our message is that having a PCL minimization objective—regardless of architecture or optimization details—is good practice. Further, our findings identify two significant challenges, which we highlighted in our experiments section:\n\n1. Underfitting by in-context models as a result of limited sequence model expressivity and compute power compared to training DNNs from scratch on a task (sections 3.2, 3.3)\n2. Meta-generalization of the sequence model to novel tasks (section 3.4)\n\nIn section 5, we did in fact discuss possible approaches for addressing these challenges, some of which have been explored in prior work (L385-431 RHS) and some of which are novel ideas. We believe that solving these challenges is out of scope for our current theoretical work, but that our theory is useful for both understanding and addressing them. We will further clarify these points in the discussion.\n\n**Q1**\n\nBased on our theory and results, we outlined a promising approach to the ICL underfitting problem in L385-413 RHS.\n\n**Q2**\n\nWe decided to focus on synthetic tasks for a few reasons.\n\n1. Interpretability:  For theoretical work, synthetic tasks are easier to control and results are easier to interpret, allowing us to concretely compare different objectives to illustrate the validity of our central insight: that ICL learners are more performant and efficient, especially in low-data regimes.\n2. We are in a meta-learning setting where sequence models need to be trained on a large meta-distribution of tasks in order to perform ICL. With real-world data, it is difficult to control the size of the meta-distribution over tasks or find meta-distributions that are sufficiently broad.\n3. For a valid comparison against the train-risk ICL baseline, for real LLM tasks, we would have needed to train an LLM from scratch using the train-risk objective we outline (L223-238 RHS). Given that this paper is about a general theory about ICL, expending such industry-scale compute resources isn’t reasonable, especially considering that we perform ablations to carefully study modeling choices. Consequently, we experiment with non-iid HMM based tasks (L248-259 LHS) to capture the structure of natural language, following common practice (c.f., [3]).\n4. Similar theoretical work in the field of ICL also makes use of synthetic tasks, and we aimed to remain consistent with standard practice (e.g., citations on L221-222 LHS).\n\n[1] Honkela, A., & Valpola, H. (2004). Variational learning and bits-back coding: an information-theoretic view to Bayesian learning\n\n[2] Blier, L., & Ollivier, Y. (2018). The description length of deep learning models\n\n[3] Xie, S. M., Raghunathan, A., Liang, P., & Ma, T. (2021). An explanation of in-context learning as implicit bayesian inference", "claims_and_evidence": "The claims made in the paper appear to be supported by convincing theoretical and empirical evidence though I have not verified the theoretical results.", "methods_and_evaluation_criteria": "The authors perform experiments using synthetic tasks that allow finer control over task and sample complextiy. The evaluation criteria of prequential length and generalization error are very relevant to the problem at hand.", "theoretical_claims": "I have not verified the theoretical correctness of proofs.", "experimental_designs_or_analyses": "The authors conducted experiments to compare ICL to standard trianing error minimization using SGD. They also conducted the impact of transformer architecture on prequential code minimization and their generalization ability which is highly appreciative.", "relation_to_broader_scientific_literature": "ICL has been widely used in modern LLMs to solve various task without model fine tuning and is an important paradigm of study in modern LLMs. This paper takes an important step in properly studying ICL from the lens of model compression and Occam's razor.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths: The paper establishes a good theoretical connection between the joint objective of reducing training error and model compression to prequential encoding and establishes the meta-learning problem of next token prediction used to train ICL already solves this problem.\n\nWeakness: The connection between prequential encoding and ICL meta-training is more of an upper bound rather than a direct equivalence. The prequential encoding does not directly suggest the specific meta-training algorithm or architectures used.", "other_comments_or_suggestions": "It would be valuable to include some more realistic tasks in empirical evaluation.", "questions_for_authors": "1. You highlight that current ICL methods underfit. Based on your study, do you see a way to mitigate this issue perhaps by better architecture or model design?\n2. Have you conducted experiments on real world task involving natural languages? If so, could you please elaborate on that?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QEKBGlb2hd", "reviewer": "Reviewer_grfc", "summary": "This paper explores a theoretical framework linking next-word prediction losses in large language models to coding-theoretic principles, often referred to as “prequenial” coding. It argues that simpler, more compact representations (inspired by Occam’s Razor) can facilitate stronger in-context learning performance. The authors present a bound-based objective aimed at improving generalization from prompts, and provide preliminary results on synthetic tasks suggesting the benefit of these simplicity-driven principles.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review.\n\n**Clarification of contributions**\n\nThe reviewer suggests that we “present a bound-based objective aimed at improving generalization from prompts” and that our work centres around “a newly introduced Occam’s Razor-inspired bound” that gives “stronger in-context learning performance”. We in fact do not attempt to improve ICL and do not propose novel methods for it: we provide a normative theory based on Occam’s razor to explain the effectiveness of ICL as it currently exists. Specifically, we argue that its effectiveness as a learning algorithm lies in the next-token prediction loss used to train sequence models, which optimizes a compression scheme called prequential coding (PCL) that implicitly fits simple models in-context that generalize well. We believe that this theoretical link is a novel contribution to the field of ICL.\n\n**Justification of experimental protocol**\n\nWe decided to focus on synthetic tasks for a few reasons.\n\n1. Interpretability:  For theoretical work, synthetic tasks are easier to control and results are easier to interpret, allowing us to concretely compare different objectives to illustrate the validity of our central insight: that ICL learners are more performant and efficient, especially in low-data regimes.\n2. We are in a meta-learning setting where sequence models need to be trained on a large meta-distribution of tasks in order to perform ICL. With real-world data, it is difficult to control the size of the meta-distribution over tasks or find meta-distributions that are sufficiently broad.\n3. Valid comparison against the train-risk ICL baseline for real LLM tasks we would have required training an LLM from scratch using the train-risk objective we outline (L223-238 RHS). Given that this paper is about a general theory of ICL, expending such industry-scale compute resources isn’t reasonable, especially considering that we perform ablations to carefully study modeling choices. Consequently, we experiment with non-iid HMM based tasks (L248-259 LHS) to capture the structure of natural language, following common practice (c.f., [1]).\n4. Similar theoretical work in the field of ICL also makes use of synthetic tasks, and we aimed to remain consistent with standard practice (e.g., citations on L221-222 LHS).\n\nThe reviewer suggests our work lacks “extensive ablation”, but we introduce baselines (e.g., train-risk ICL, off-the-shelf learners with different inductive biases) to isolate the role of the next-token loss that bounds $K(D,p)$.\n\nThe reviewer suggests a lack of “multiple domains or tasks”, but our experimental settings are in fact wide-ranging: we study linear & nonlinear tasks, regression & classification, iid & non-iid, scaled task difficulties, Transformers & SSMs, and models trained from scratch & LLMs.\n\n**Q1**\n\nWe would again like to emphasize that we did not introduce a novel training algorithm for sequence models as the reviewer suggests. We provided a theory that explains why the standard next-token prediction loss is an effective method for training sequence models. We do not have to “scale our approach to more complex, real-world tasks” since cumulative next-token prediction loss is *already* the objective used to train LLMs. \n\n**Q2** \n\nMeasuring the tightness of the bound $K(D,p) \\lt L_{preq}$  involves computing Kolmogorov complexity, which is uncomputable. However, minimizing an upper bound on an intractable quantity follows a long line of work in ML. For example, as we state in our paper (L156-159 RHS), all variational inference methods that minimize the negative ELBO—from VAEs to diffusion models—learn via a tractable bound to an intractable quantity (the negative log likelihood). In compression too, there is longstanding work (c.f., [2]) proposing variational approximations to minimizing the complexity of deep learning models. Pushing down an upper-bound is a workable proxy for optimizing a target quantity, therefore our argument that minimizing PCL minimizes training error + model complexity is valid. Finally, even when it is not being minimized through a meta-learning objective, PCL has been found to be a strong compression algorithm in deep learning settings [3], bounding $K(D, p)$ better than other methods. We will further clarify this in revisions.\n\n**Q3**\n\nPAC-Bayes bounds are also rooted in Kolmogorov complexity, but require a prior over models. PCL only depends on a learning algorithm. Viewing a sequence model as a learning algorithm therefore makes it easy to compute PCL, but not PAC-Bayes bounds. We’ll include a brief discussion about the link in the revised draft.\n\n[1] Xie, S. M., Raghunathan, A., Liang, P., & Ma, T. (2021). An explanation of in-context learning as implicit bayesian inference\n\n[2] Honkela, A., & Valpola, H. (2004). Variational learning and bits-back coding: an information-theoretic view to Bayesian learning\n\n[3] Blier, L., & Ollivier, Y. (2018). The description length of deep learning models", "claims_and_evidence": "The submission posits that next-word prediction objectives parallel coding-based formulations and that enforcing an Occam’s Razor-style bound can yield practical improvements in in-context learning. The key claims are supported by derivations that connect model complexity and predictive accuracy, alongside synthetic experiments. However, the paper offers limited evidence of how these findings directly translate into real-world scenarios, since the experiments remain small-scale and somewhat specialized.", "methods_and_evaluation_criteria": "The methods center on a bound-based reweighting scheme intended to emphasize simplicity in the learned representations. Evaluation is conducted via synthetic pattern extrapolation tasks, showing modest gains under the proposed approach. While these tasks illustrate potential effectiveness, more extensive benchmarks or realistic datasets would strengthen the case for broader applicability.", "theoretical_claims": "The theoretical arguments rest on a newly introduced Occam’s Razor-inspired bound relating predictive cross-entropy to compact representations. The proofs, rooted in coding theory, appear consistent with standard generalization frameworks, but the paper does not delve into how tight or loose these bounds might be in practice, which raises questions about their practical utility.", "experimental_designs_or_analyses": "The experiments use simple synthetic tasks designed to capture in-context learning behavior. They document improvements that align with the theoretical claims, but do not include extensive ablation or broader domain testing. Consequently, while the setup seems sound for initial validation, it provides limited evidence of robustness or real-world feasibility.", "relation_to_broader_scientific_literature": "By linking next-word prediction to coding-theoretic insights, this work resonates with the long-standing principle of minimum description length and various PAC-Bayes approaches, all of which emphasize model simplicity as a route to better generalization. It adds to recent discussions on in-context learning by proposing a formal perspective on why large language models can generalize from prompts.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "A notable strength is the novel theoretical perspective that attempts to unify coding-theoretic arguments with in-context learning. The main weaknesses are the lack of clarity regarding how these ideas translate into practical improvements, as well as the absence of a detailed analysis on the tightness of the proposed bounds.", "other_comments_or_suggestions": "A broader discussion of how bound-based optimization might scale to real-world tasks and how it compares or integrates with standard in-context learning pipelines would considerably strengthen the paper. Small additions, like evaluating multiple domains or tasks, could showcase broader relevance.", "questions_for_authors": "How do you envision scaling your bound-based approach to more complex, real-world tasks without incurring excessive computational cost? 2) Have you attempted to measure the tightness of your bounds empirically in different settings to ensure that they offer meaningful guidance rather than a loose theoretical construct? 3) Could you compare and contrast your approach with standard PAC-Bayes bounds to clarify any points of conceptual or methodological overlap?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ULjkbtvHma", "reviewer": "Reviewer_tMvj", "summary": "The paper studies ICL and tries to relate ICL to prequential coding length through the scope of Kolmogorov complexity.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review.\n\n**Empirical studies**\n\nOur work is not an \"empirical paper\", but a theoretical one. Unlike standard theory papers, we studied 4 tasks including the challenging Mastermind task, multiple sequence models to highlight the generality of the theory (Fig. 2b), and conducted numerous ablations (Apx. D, E).\n\nNevertheless, if this remains unconvincing, please clarify *which* conclusions (listed under the paper's “Findings.” headings) you find unsupported by our results or what additional experiments you’d liked to see.\n\n**Lack of theorems**\n\nWe build on [1-3] to establish a novel connection between description length results for DNNs and ICL. In section 2, we mathematically derive the link from prequential code length (PCL) minimization to implicit model complexity when a pretrained model learns a task from examples presented in context. We chose not to use the \"Theorem, Lemma, Proposition\" formulation, as we believe it helps readability.\n\n**Relation between ICL and next-token prediction**\n\nICL is indeed *not equivalent* to next-token prediction, and we do not suggest that it is. Rather, we show that training via next-token prediction loss explains the effectiveness of ICL because of the link from next-token prediction to compression.\n\n**Q1**\n\nGiven equally good explanations, Occam's razor prefers the simplest one. In a typical ML textbook, Occam's razor is the justification for why simpler models generalize better (e.g., see chapter 1 in [4] and 7.3 in [10] for a detailed discussion), where \"explain the training data\" means minimizing training error. Further, the most common way to formalize model simplicity is using Kolmogorov complexity as we do. See [5-6] for short introductions, and [7] for a discussion in the context of deep learning.\n\n**Q2**\n\nAs stated in L156-159, minimizing upper bounds to intractable quantities is standard practice in ML [4, chapter 10], e.g., we minimize the negative evidence lower-bound instead of the intractable negative log likelihood with VAEs [8] or diffusion models [9]. Furthermore, even when it is not being minimized through a meta-learning objective, PCL has been found to be a strong compression algorithm in deep learning settings [1], bounding $K(D, p)$ better than other methods.\n\n**Q3 and Q5**\n\nOur theory predicts that prequential ICL should generalize better since it was meta-learned to minimize model complexity as well as training error. To verify this, we need a ‘control’  that is meta-learned to only minimize training error, which is exactly \"train-risk ICL\". You're right that if implemented naively, such a train-risk learner could simply memorize in-context examples, which is why we minimally modify the Transformer architecture to summarize the context in a bottleneck. We explain this in L240-252 RHS.\n\n**Q4**\n\nWe pretrain separate models using (a) the next-token prediction objective or (b) the past-token prediction objective on a distribution of tasks and then compare these resulting learners on unseen tasks at inference time (L252-258 and Apx. C.2). This is in line with other work studying ICL in controlled settings  (e.g., citations on L221-222 LHS)].\n\n**Q6**\n\nGeneralization error (y-axis) at a particular context length (x-axis) is the inferred model's prediction error on *unseen* data (Fig. 2 caption). MSE is the standard metric used to measure error for regression.\n\n**Q7**\n\nGiven equal training error, it is well-known that simple models generalize better [4, 10]. Overfitting indeed happens due to excess model complexity. We in fact do define generalization on L255-258 RHS as prediction error on unseen data, which is how it is always defined [4].\n\n**Q8**\n\nPCL and MSE are not the same. PCL is defined as the cumulative next-token negative log-likelihood (NLL) across a dataset (section 2.2,  Fig. 1, Eq. 4)—for regression, NLL is measured using MSE (well-known to be equivalent to NLL under a Gaussian). PCL is therefore given by the area under a curve in Fig. 2 (L300-301), whereas MSE is the y-axis of the plots for regression problems.\n\n**Q9**\n\nWe describe the Mastermind task and data format in L237-247 LHS. Other training details are provided in Apx. C.\n\n[1] Blier & Ollivier (2018). The description length of deep learning models\n\n[2] Delétang et al. (2023). Language modeling is compression\n\n[3] Wilkenfeld (2019). Understanding as compression\n\n[4] Bishop & Nasrabadi (2006). Pattern recognition and machine learning\n\n[5] Nannen (2010). A short introduction to model selection, Kolmogorov complexity and Minimum Description Length\n\n[6] Wallace & Dowe (1999). Minimum message length and Kolmogorov complexity\n\n[7] Mingard et al. (2025). Deep neural networks have an inbuilt Occam's razor\n\n[8] Kingma & Welling (2013). Auto-encoding variational bayes\n\n[9] Song et al. (2020). Score-based generative modeling through stochastic differential equations\n\n[10] Shalev-Shwartz & Ben-David (2014). Understanding machine learning: From theory to algorithms", "claims_and_evidence": "There're some vague claims stated by the authors, see questions part.", "methods_and_evaluation_criteria": "Proposed methods and evaluation criteria is confusing.", "theoretical_claims": "There're no theoretical claims.", "experimental_designs_or_analyses": "The experimental designs are confusing, see questions part.", "relation_to_broader_scientific_literature": "The paper is related to unveiling the black box ICL of transformers.", "essential_references_not_discussed": "Not any that I know of.", "other_strengths_and_weaknesses": "### Strengths\n1. The paper studies ICL, which is an important ML topic.\n\n### Weaknesses\n1. The paper claims to provide a theory on ICL, but no formal theorems or statements can be found in the paper.\n2. The relationship with ICL is vague, the next-token prediction is not the essence of ICL, it is the training paradigm of all modern LLMs.\n3. The message the paper tries to convey is unclear, and some statements seem unjustified or out of the blue (see questions).\n4. For an empirical paper, it is short of experiments and the empirical evidence is not convincing.", "other_comments_or_suggestions": "1. line 153 \"Figure 1b\" should be \"Figure 1\".", "questions_for_authors": "1. How is “simple models which explain the training data generalize best\" mentioned in the abstract related to the Occam's razor principle, and what does \"explain the training data\" mean?\n\n2. In section 2.4 (which I believe is the main contribution of this paper) the summary part, you mentioined \"... explicitly optimize a meta-learning objective that jointly minimizes training error and model complexity\". However, the next-token prediction loss (or equivalently the prequential loss? Correct me if I'm wrong), is an upper bound for the training error plus model complexity, thus the statement doesn't seem valid?\n\n3. In section 3.1 you mentioned two training objectives, one of them is to \"training $T\\_{\\Phi}$ to predict past datapoints in the context\". Why is this necessary? Can't a transformer model simply copy (or memorize) the datapoints in the context? It's \n\n4. For the two different training objectives, do you implement different pretraining objectives or do you simply test the inference time ICL ability without pretraining?\n\n5. In line 232 right column you stated \"While nobody uses train-risk ICL in practice, it serves as an ideal control to illustrate our theory of ICL...\". How does this train-risk illustrate your theory of ICL?\n\n6. In figure2, why do you call the MSE error the \"generalization error\"?\n\n7. I don't understand how could \"simple\" model be better at generalization in section 3.1 findings (althogh generalization itself is not formally defined in the paper). Is it simply due to the lack of expressivity of simple models so that overfitting is less likely?\n\n8. In line 333 right column you mentioned \"Not only is its prequential code length substantially higher than ...\", are you suggesting that prequential code length is the same as the MSE loss since in figure 2c you used the generalization error (which is the MSE loss)?\n\n9. In figure 2c, \"our transformer\" is pretrained on \"a distribution of Mastermind tasks\", could you provide some details of the training regime (i.e. the training data format, the training distribution etc.)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission explores a theoretical perspective linking in-context learning (ICL) with Occam’s razor through the lens of prequential coding. Most reviewers found the paper’s central insight, that the cumulative next-token prediction objective implicitly encourages simpler learned models that exhibit strong generalization in context, interesting and grounded in a sound line of literature on description length and Kolmogorov complexity. The authors supported their argument with controlled synthetic experiments that illustrate the difference between meta-training objectives that account for model complexity (prequential) and those that only minimize training error. Two reviewers gave “weak accept” recommendations, citing the paper’s coherent theoretical message and its plausible, though modestly scaled, empirical support. They also saw value in the discussion of underfitting and the paper’s potential to spur new research into improved sequence-model architectures for in-context learning.

However, one reviewer recommended rejection, contending that the theory lacks the typical “theorem-proof” format and that linking pretraining-time next-token prediction strictly to in-context generalization remains incomplete without a tighter test-time analysis or more direct empirical verification at scale. This reviewer further argued that minimizing a practical upper bound (i.e., prequential code length) does not necessarily imply minimal Kolmogorov complexity, so the Occam’s razor claim may be overstated. In their rebuttal, the authors clarified that bounding Kolmogorov complexity with a tractable surrogate remains standard practice in machine learning (e.g., variational methods) and emphasized that in-context generalization is indeed assessed through example-based prompts at inference. While concerns persist regarding the gap between real-world LLM usage and the paper’s synthetic tasks, the consensus is that this work offers an insightful theoretical perspective.
Decision: Accept (poster)