Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers
Authors: Peter Shaw
James Cohan
Jacob Eisenstein
Kristina Toutanova
Venue: ICLR 2026 Poster (2026)
Keywords: kolmogorov complexity
minimum description length principle
compression
variational inference
quantization
Primary area: learning theory
TL;DR: This paper formally links Kolmogorov complexity to deep learning by proving the existence of asymptotically optimal description length objectives for Transformers.

Abstract: The Minimum Description Length (MDL) principle offers a formal framework for applying Occam's razor in machine learning. However, its application to neural networks such as Transformers is challenging due to the lack of a principled, universal measure for model complexity. This paper introduces the theoretical notion of asymptotically optimal description length objectives, grounded in the theory of Kolmogorov complexity. We establish that a minimizer of such an objective achieves optimal compression, for any dataset, up to an additive constant, in the limit as model resource bounds increase. We prove that asymptotically optimal objectives exist for Transformers, building on a new demonstration of their computational universality. We further show that such objectives can be tractable and differentiable by constructing and analyzing a variational objective based on an adaptive Gaussian mixture prior. Our empirical analysis shows that this variational objective selects for a low-complexity solution with strong generalization on an algorithmic task, but standard optimizers fail to find such solutions from a random initialization, highlighting key optimization challenges. More broadly, by providing a theoretical framework for identifying description length objectives with strong asymptotic guarantees, we outline a potential path towards training neural networks that achieve greater compression and generalization.

Published as a conference paper at ICLR 2026
BRIDGING KOLMOGOROV COMPLEXITY AND DEEP LEARNING: ASYMPTOTICALLY OPTIMAL DESCRIP-
TION LENGTH OBJECTIVES FOR TRANSFORMERS
Peter Shaw Google DeepMind
James Cohan Google Research
Jacob Eisenstein Google DeepMind
Kristina Toutanova Google DeepMind
ABSTRACT
The Minimum Description Length (MDL) principle offers a formal framework for applying Occam's razor in machine learning. However, its application neural networks such as Transformers is challenging due to the lack of principled, uni- versal measure for model complexity. This paper introduces the theoretical notion asymptotically optimal description length objectives, grounded in the theory of Kolmogorov complexity. We establish that minimizer of such objective achieves optimal compression, for any dataset, up to an additive constant, the limit model resource bounds increase. We prove that asymptotically optimal objectives exist for Transformers, building on a new demonstration of their com- putational universality. We further show that such objectives can be tractable and differentiable by constructing and analyzing a variational objective based on an adaptive Gaussian mixture prior. Our empirical analysis shows that this varia- tional objective selects for low-complexity solution with strong generalization on an algorithmic task, but standard optimizers fail to find such solutions from random initialization, highlighting key optimization challenges, More broadly, by providing a theoretical framework for identifying description length objectives with strong asymptotic guarantees, we outline potential path towards training neural networks that achieve greater compression and generalization.
INTRODUCTION
The principle of Occam's 's razor-thhe simpler explanations are preferable- foundational concept in machine learning. Algorithmic information theory provides an elegant formalization through the Minimum Description Length (MDL; Rissanen, 1978) principle. The MDL principle frames learning as data compression: the best model for a dataset is the one that minimizes the combined length of the model's description plus the description of the data encoded with that model. Intuitively, any regularity in the data that is useful for prediction is also useful for compression, and vice versa.
The empirical success of large neural networks might consider a naive, uniform encoding of their weights. Such networks often generalize surprisingly well, even when highly over-parameterized and trained with simple maximum likelihood objec- tives (Zhang et al., 2017). However, various methods have been proposed for training compressible neural networks based on, e.g., quantization (Han al., 2016), subspace training (Li et al., 2018), low-rank approximation, variational inference (Louizos et al., 2017; Hinton & Van Camp. 1993), or some combination (Lotfi al., 2022: 2024; DeMoss al., 2025). These methods have highlighted that neural networks can often be highly compressed, i.e. their true complexity can be much smaller than naive parameter counting would suggest (Blier Ollivier, 2018). While such methods have thus far not led directly to MDL-inspired regularizers that reliably improve generalization, these methods have been successful for establishing tighter compression bounds (Lotfi et al., 2022; 2024) and inspiring parameter-efffcieet fine-tum tnn-ttnnng methods such as LoRA (Hu et al., 2022).
contradict the MDL. principle if
However, key theoretical questions remain. These methods from prior work can be interpreted as defining different description length measures capture different types of regularities, but fail to capture all potential regularities in the network. MDLL objectives based on such measures may therefore fail to incentivize capturing all of the regu-
network's weights. Different measures may

---

Published as a conference paper at ICLR 2026
larities in the data, if certain patterns cannot be encoded efficiently in the network's weights. This can lead to sub-optimal compression and-per per the MDL principle-sut ally, we want description length objective that encourages the model to capture any regularity in the data. Assuming perfect optimization, such an objective would lead to optimal compression, regardless of the dataset. To what extent can we implement such idealized objective?
generalization, Ide-
Algorithmic information theory offers a framework to address this question (Li & Vitányi, 2008; Hutter, 2005; Schmidhuber, 1997). MDL was inspired by Solomonoff's s theory of inductive infer- ence (Solomonoff, 1964), which proposed to favor hypotheses with low Kolmogorov complexity. Put simply, the Kolmogorov complexity of an object is the length of the shortest program that gen- erates that object (see Section 2). Kolmogorov complexity offers optimal compression relative to any other computable description length measure, up to an additive constant. This universality is rooted in the Church-Tuurin thesis that any sufficiently powerful model of computation can simulate any other. Computable shource-bounder approximations maintain this universality in the limit as resource bounds increase. The notion of Kolmogorov complexity can be directly applied to pro- gram induction priors based on program length have been empirically successful for inducing programs (e.g.. Hooera--Paredes et al., 2024) and grammars (e.g., Shaw al., 2021) with strong generalization. However, applying this notion to neural networks is less straightforward. While we can easily compute the length of a discrete program, it is less clear how quantify the complexity of the function a neural network computes in an analogous way. Therefore, a conceptual gap remains between theoretical frameworks based on algorithmic information theory and practical description length objectives for neural networks. We aim to narrow this gap.
Building on the theory of Kolmogorov complexity and the computational universality of Transform- ers, we demonstrate the existence of asymptotically optimal description length objectives for Trans- formers, with optimality guarantees analogous to those that hold for Kolmogorov complexity. Our theoretical framework therefore highlights a potential path forward for identifying description length objectives for neural networks that select for models offering greater compression and potentially greater generalization. Specifically, we develop the theory of asymptotically optimal description length measures for neural networks through the following contributions:
We define universal two-part codes for probabilistic models whose minimum description length for any data sample is provably optimal, up to additive constant, relative any other two-part code. This framework circumvents the need for arbitrary domain-specific priors by leveraging the universal properties of Kolmogorov complexity. (Section 4)
We prove the existence of asymptotically optimal families of codes for Transformers, which are universal in the limit as resource bounds increase. This result is established via new demonstration that Transformer encoders are computationally universal in their ability to represent any computable, rational- -valued conditional probability distribution. (Section 4)
We further prove that tractable and differentiable objectives for Transformers can be asymptotically optimal, establishing this by constructing and analyzing variational ob- jective based on an adaptive Gaussian mixture prior. (Section 5)
We analyze various codelength objectives empirically and analytically. Using a manually constructed solution for an algorithmic task, we show that our variational objective se- lects for highly compressible model with strong generalization. However, we find that standard optimizers fail to discover such low-complexity solutions from a random initial- ization, highlighting a key challenge for future work. Additionally, we analytically derive asymptotic bounds for various alternative two-part codes. (Section 6)
2 BACKGROUND: KOLMOGOROV COMPLEXITY
We give a brief introduction to Kolmogorov complexity, with an extended and more formal ver- sion in Appendix A. Intuitively, the Kolmogorov complexity K K(x) of an object x is the length of the shortest program, written in some standard programming language, that prints Similarly, the Kolmogorov complexity K(f) of a discrete function f is the length of the shortest program that computes f. To formalize these notions, Kolmogorov complexity universal prefix Turing machines, which are multi-tape Turing machines that represent programs as binary strings encoded read-only program tape. The key invariance theorem states that K
be defined with respect to
2

---

Published as a conference paper at ICLR 2026
is independent of the particular choice of universal prefix Turing machine up to additive stant. While Kolmogorov complexity is not strictly computable due to the halting problem, we write (f) f to denote computable approximation under resource bound R = (R,, Rg)) E N2, which considers only programs that terminate within R steps and require at most RG registers on any tape, with respect universal prefix Turing machine T. As resource bounds increase, Kr.n(f) mono- tonically decreases to K (f), up to an additive constant, per the invariance theorem. We introduce concise notation express such relations that hold up to additive constants next.
Inequalities with additive constants Let : R and X + IR be functions over the same domain X. Then we can write Vx, f(x) 3 g(ar) if and only if there exists some constant IR such that Vx, f(x) < g(z) + where the additive constant e must not depend on œ. We write Va,, (xx) = g(x) to denote that both Vx,, [(x) g(x) and Va, g(ar) (xx hold."
PROBLEM SETTING AND MODEL FUNCTIONS
Problem setting Let the input space X be discrete and countable set, and the output space y be a discrete and finite set. We define the space of all possible datasets as = (X' x 3)),, the set of all finite sequences of input-output pairs. For any dataset D ((æ1, 1/ ya),..., (In, Vn)) DD we denote the corresponding sequence of inputs as X = (Iı,... Znn)) and outputs as Y (y1,...,;be) Mn). Our analysis focuses properties of encoding schemes that hold for any such pair of sequences (X, Y).
Model functions Neural networks modeling distributions over a discrete output space are typically characterized by model function, f. which defines a conditional distribution over a discrete space Y by mapping an input z E X' to vector of unnormalized logits, f(z) E L. Motivated by the umite-precision arithmetic used in neural networks, we assume these logits are rational numbers (i.e. Q ) which enables a straightforward definition for the Kolmogorov complexity of model function, K (f).² We denote the set of all such computable model functions as F. The conditional distribution for function f is given by applying the softmax function, σ, its output logits:
P(Y (:f)= = II plV f)
ply z; f) o (f(x))
(1)
T,E,X,Y
In the following sections, we apply the MDL principle to this setting, where we want to identify codes that select for a probabilistic model of this form that optimally compresses a set of labels Y given corresponding inputs X, yielding description length objective.
4 TWO-PART CODES
One way to apply the MDL principle is with two-part codes. Consider the cost for sender (e.g., Alice) to transmit labels to receiver (e.g., Bob). both are given the inputs X. With a two- part code, Alice first transmits a model hypothesis, and then transmits the labels encoded given this model hypothesis (Figure 1). Specifically, we consider two-part codes that are parameterized by probabilistic model function (Section 3). which we refer to simply as two-part codes in this paper.
Definition (two-part code). two-part code M is specified by a triplet (Has. mm, aad) with:
A hypothesis space HM which we assume is countable, e.g., the parameter space of a particular neural network assuming parameters with some -nitte-reciison.
A mapping mm Has - F from hypotheses to model functions (Section 3), e.g., the mapping defined by a particular neural network architecture."
A prior a:M (h) defining a distribution over model hypotheses, Hm.."
Extending this notation to codelength functions over variables X and Y, Y,,,Y Y, (Y|X)) [2(Y|X)
implies 3c R., VX, Y, [L(Y] |X) [2 [X)+ +)++o where does depend X Y. We omit explicit quantifiers when they are clear from context.
"Se Appendix B.1 for discussion of the complexities involved with real-valued functions.
TThis can he a partial function, e.g. a Turing machine with unbounded resources may never halt for some
inputs.
*Formally we allow the prior to he any lower semicomputable semimeasure (see Appendix A).
3

---

Published as a conference paper at ICLR 2026
Sender (Alice)
Recelver (Bob)
Transmit model hypothesis in -1og,% (2) bits
Step 2: Transmit labels y encoded given hypothesis -log,p ( X2m, (hr) bits
X,
X
Figure I: Two-part code. One way to formalize the MDL principle is with a two-part code. Assume Alice and Bob agree on two-part code M and each are given inputs X. Alice then finds the hypothesis (e.g.. model parameters) that enables sending Bob the labels Y in the fewest total bits, balancing the complexity of the model with how well it fits the data. One key challenge we address is that the minimum codelength is dependent on the potentially arbitrary choice of prior ar (h).
Given a two-part code M, the codelength for transmitting Y given X is defined as the sum of the codelength of the hypothesis and the codelength of the data given the hypothesis:
L two-part
MM
h)
log2 a<(h) loga (x)mar(h))-
The log, terms represent the ideal codelength for transmitting the model and data under the distri- butions specified by the prior and the selected hypothesis, respectively; the latter term is recognizable as the standard negative log-likelihoon (NLL) objective. From a Bayesian perspective, minimizing equation 2 can be interpreted as finding the MAP estimate. The minimum achievable codelength for transmitting the labels with the two-part code M is then denoted as:
L M
# two- part (Y XX)= min L NEH
two-part (Y (:h).
(3)
Universal two-part codes Notably, there is a considerable degree of freedom in specifying a two-part code, e.g. for particular neural network architecture specifying the hypothesis space and mapping function, we can choose any prior over the model weights. The prior determines the description length measure over the weights, which, in effect, determines the inductive bias of the codelength objective. Building on the invariance theorem for Kolmogorov complexity, we will show that there exists an equivalence class of two-part codes that are universal in the sense that minimizer of any universal two-part code offers at least as much compression any other two-part code, for any dataset, up to an additive constant that does not depend on the data. This guarantee holds regardless of the specific prior, as long as it constructs a universal code, and is captured in the following theorem and its corollary.
Definition (universal two-part code). Let M be two-part code, M² is a universal two-part code if and only if. for any other two-part code, 2 the following holds for any dataset X, Y:
two-part "M
(Y X) I
twoo-pp (Y |X).
(4)
Proposition 1. There exists a universal two-part code.
Corollary 1. The minimum of any universal two-part code M is equal to the following bound, denoted Cowo-panyy (Y) (X), up to an additive constant:
L niw-patt (Y XX) + Covo-part (Y 1X) min k(f) loga p(Y Xxf).
Jef
The core requirement for two-part code to be universal is that its underlying model class must be computationally universal. That is, for any computable model function f. there must be some hypothesis h in the hypothesis space that computes it, i.c. where mn (h) f. Furthermore, the prior, (h), must assign at least one such hypothesis a codelength, - log, (h)) that is equivalent to the Kolmogorov complexity of the function being computed, K(J), up to an additive constant (see B.4.2 for the formal proofs). This ensures the code can, in principle, efficiently represent any computable regularity in the data. Fully satisfying these conditions requires a model class with unbounded computational resources, like a Turing machine, and strictly minimizing the code is not computable, due to the halting problem. Since any real-world model, such Transformer, has finite resources (c.g., a finite number of layers and context window), it cannot be strictly universal. This motivates the notion of asymptotically optimal codes, introduced next.
4

---

Published as a conference paper at ICLR 2026
Decodi
plylx]
Porameters
Program, 2
zmap (", Ry 21
Cutput Tapes
Program Tape
Universal Prefix
Turing Machine, I
Trensformer
Work Tape
Input Tape
Prepend
Prompt
1og 1oog,orth (h("")
|
Enoode
Figure 2: Constructing asymptotically optimal codes for Transformers. We construct a function zmap that establishes that Transformer (right) can effectively simulate prefix Turing machine with any prefix & encoded on program tape (left), and therefore can represent any computable model function (as defined in section 3) within some arbitrary time and space resource bound R. With this mapping between model functions and Transformer parameters established, we can select a prior that assigns probability sets of parameters based on the algorithmic complexity of the function they compute, thus forming an asymptotically optimal code (Section 4.1).
Asymptotically optimal two-part codes Neural network architectures, such as Transformers, de- fine a family of models, with hyperparameters corresponding to finite time and space resource. Certain families of two-part codes can then be shown to be asymptotically optimal in the sense that as the resource bounds increase, the minimum code length monotonically decreases to the minimum of universal two-part code (see B.4.5 for the proof).
Definition (asymptotically optimal families of two-part codes). A family of two-part codes {Ma |
R E N2} is asymptotically optimal with respect to a universal prefix Turing machine T if:
VR E N2, L awo-part (Y ( S T,
(Y IX),
(6)
MR
where Ctvo-part (Y) X) min Kr,u(f) log2 p(Y f) and KT, denotes Kolmogorov complexity under resource bound R.
Proposition 2. Given asymptotically optimal family of two-part codes (Mx R E N*):
lim R4 R, +00
awo-part (Y X) $ Chwo-part X),
MR
with the bound CT,R
Otwo-part (Y)
X) monotonically non-increasing with increasing R4 or Rg-
We demonstrate the existence of such asymptotically codes for Transformers next.
4.1 TWO-PART CODES FOR TRANSFORMERS
The Transformer architecture (Vaswani al., 2017) defines a family of models with various hy- perparameters determining the time (e.g., number of layers) and space (e.g.. context window size) resources of the model. We focus our theoretical analysis on Transformer encoders applied se- quence classification, commonly studied setting (c.g., Devlin et al., 2019).
Theorem 1. There exists an asymptotically optimal family of two-part codes for Transformer en- coders.
Figure 2 captures the main idea. Given universal prefix Turing machine T and resource bound R. let ZT.R denote the of programs such that T halts within Rg steps and requires only up to R, registers on any tape. for any input X' encoded on the input tape. Let f X + L be the model function computed by T with prefix on the program tape. For given R, we construct two-part code MR where the hypothesis space HM, and mapping function mMa are defined by Transformer encoder, with O (Rt) layers and a context window size of O(R)). We use ALTA (Shaw et al., 2024), a compiler from symbolic programs to Transformer weights, to construct a function zmap such that Vz E Zr.R. mM, (h*) = ff where h zmap R, 2). While future work could consider alternative ways of constructing such mapping (see 6.3), our particular construction relies on prepending a sequence of R, 'prompt tokens" to the model input, with learnable embeddings. These prompt tokens represent the program 2, while the attention and ML. weights configured
5

---

Published as a conference paper at ICLR 2026
Computable prefix codes
Two-part codes
Universal two-part codes
Variational codes Quasi-universal variational codes
K()X)
(YIX))
Champe (Y
Figure 3: Upper and lower bounds on minimum codelengths. The figure shows the minimum number of bits required to transmit labels Y given inputs X. for different classes of codes. The bounds hold for any dataset (X, Y) up to an additive constant that does not depend on the dataset.
to act as an interpreter, emulating the Turing machine T. We can then trivially construct a prior MM (h) that such that Vz 27, R. -log2 0.g (h*) = |a|. with o (h) for hypotheses outside the range of zmap. This construction can be shown to satisfy the conditions of an asymptotically optimal family of codes with respect to T. Further, any prior satisfying the more relaxed condition Vz Rr - log2 (h*) < |2| + cr where or is constant not depending on R or z is sufficient. (See B.6 for the formal proof.)
4.2 LIMITATIONS PRACTICAL CONSIDERATIONS
While asymptotically optimal codes offers appealing compression bounds, in this section dis- cuss why these bounds are insufficient to guarantee real-world performance and relevant practical considerations.
First, the theoretical guarantees hold in the limit as model resources increase, and hold up to an ad- ditive constant that only becomes negligible dataset complexity increases. While the community has been training increasingly large models on increasingly large datasets, any real-world models and datasets are, of course, finite. For a finite-resoureed Transformer, satisfying the conditions of an asymptotically optimal code only formally constrains the description length of a subset of the com- putable functions that could be represented. Strictly emulating a Turing machine can be inefficient, failing to leverage Transformer's 's capacity for parallel and numerical computation. Therefore, in- tuitively, we should consider sufficiently general and flexible priors that are not overly specialized to specific Turing machine. For sufficiently flexible prior, method used to prove asymptotic optimally showing that Transformer can emulate a universal prefix Turing machine serves primarily establish worst-case upper bound on the minimum achievable codelength.
Second, the formal guarantees apply to the minimum the codelength objective. Practically, we need to consider objectives that computationally tractable and can be efficiently optimized.
Therefore, we should aim to identify codes that are asymptotically optimal (or approximately opti- mal) but also satisfy these additional informal but intuitive criteria, which can ultimately be assessed empirically. As one potential path toward meeting this goal, we consider variational codes, which study theoretically in Section 5 and empirically in 6.1. We also analyze the asymptotic bounds for various alternative two-part codes 6.2.
5 VARIATIONAL. CODES
An alternative approach for Alice to transmit the data labels to Bob is to use a variational code, which considers distribution hypotheses, rather than selecting single best hypothesis. We start with some definitions and formal results, and then work towards a practical implementation.
Definition (variational code). variational code M consists of a hypothesis space H.s a mappingg mM HM + FF from hypotheses to model functions. and prior (a) over HM. specified in definition Additionally, a variational code specifies a posterior hypothesis space, PM, and distribution over hypotheses, Ia (h; σ), parameterized by hh.-
The conditional distribution over Y given X is therefore specified by the posterior parameters á E M, and defined by marginalizing over hypotheses:
PM (Y x; Enp P( K3mms(h))
(8)

---

Published as a conference paper at ICLR 2026
The codelength for variational code M is then defined as:
MM x)) = (x)))r()))) |- log, oas (h) logg BM (h; - log, p( m (h))
(9)
KL ]KL [BMM(:: || a. (-) log2 Pas (Y X:)),
(10)
which can be interpreted as the cost of transmitting the labels given the "bits back" argument of Hin- & Van Camp (1993). The intuition is that parameters with higher uncertainty can be transmitted
with lower cost. Equation 10 mirrors equation 2, with the KL term capturing the model cost. We denote the minimum of a variational code M as:
L var (Y X) min (Y () 6E
(11)
A variational code can be seen approximating an idealized but intractable Bayesian code (B.7.5). As with two-part codes, variational codes require choosing a seemingly arbitrary prior. We address this by defining quasi-universal variational codes, which are analogous to universal two-part codes.
Definition 5 (quasi-uma uuiserluniversal variational code). A variational code M is quasi-universal varia- tional code if and only if:
L *.vrr (Y X)
Ch (X).
(12)
We use the term quasi-universal because such codes are not necessarily strictly universal among the set of variational codes. However, their minima are tightly bound per the following theorem. Proposition 3. For any quasi-universal variational code M,
K(Y X) & bbayes( (Y (X) 2/2 * (Y (X) C'woopartyy (Y |X,,
(13)
M
where Chhoyes (Y X) == - log E₁EF 2 K() k() X)
The result is visualized in Figure The proof involves deriving Cbayes(Y | X) the minimum of universal Bayesian code (B.7.6). Under reasonable conditions. the differences between each of these quantities are expected be small. See B.7 for formal analysis and discussion. The definition of asymptotically optimal families of two-part codes directly extends to variational codes (B.8.2). 2). Ad- ditionally, variational codes can be seen as a generalization of two-part codes (B.8.1), 1),, and therefore previous result constructing asymptotically optimal two-part codes for Transformers directly extends to prove the following proposition (B.8.3).
Proposition 4. There exists an asymptotically optimal family of variational codes for Transformer encoders.
Finally, we note that we can also generalize variational codes by using an adaptive prior (Hinton & Van Camp, 1993), where the prior is itself parameterized. We term such codes adaptive variational codes, defined formally in B.8.4. Adaptive priors help generalize our previously constructed codes to form more flexible implementation, discussed next.
5.1 DIFTEENTIABLE CODES VIA GAUSSIAN MIXTURE MODELS
Per the discussion in 4.2, we aim to identify families of asymptotically optimal codes for Trans- formers that are based on flexible and general priors not explicitly constructed around specific Turing machine emulation and are amenable to standard gradient-based optimization. As one path towards this goal, we construct family of adaptive variational codes where the adaptive prior and posterior distributions are both parameterized by sets of independent Gaussian mixture models (GMMs; see 1.9. Intuitively, a GMM prior shared across group of weights drives compression by encouraging a low-entropy clustering of weight values around the component means. akin to soft quantization (Ullrich et al., 2017: Achterhold et al., 2018; Han et al., 2016). Such a GMM-basedd construction is appealing for its generality, and because we can estimate the variational codelength objective using Monte-Carlo sampling and apply standard optimizers via the reparameterization trick (Kingma& & Welling, 2014; Jang et al., 2017; Maddison et al., 2017). The proof of Theorem 2 below demonstrates that this construction is also asymptotically optimal, thus establishing a worst- case asymptotic upper bound the minimal codelength (i.e. compression) achievable with such codes. The proof also serves to illustrate a potential path towards identifying other instances of practical and asymptotically optimal codes.
7

---

Published as a conference paper at ICLR 2026
Theorem 2. There exists asymptotically optimal famity of adaptive variational codes for Trans- former encoders where the adaptive prior and posterior distributions are both specified by products of independent GMMs.
The key challenge in satisfying this theorem, in contrast to our earlier existence proofs, lies in the stronger constraints imposed on the prior distribution, particularly the independence assumptions. We show that two relatively general conditions are sufficient to establish asymptotic optimality. First, we layerwise weight sharing, as in Universal Transformer (Dehghani et al., 2019), ensur- ing that the number of Transformer weights doesn't 't scale with the time bound R, Second, we share GMM prior over groups of Transformer weights, ensuring that the number of prior parameters doesn't scale with the space bound R...
The formal proof is in B.10. Our proof sketch here builds the function zmap and the related notation introduced in Section 4.1. Given universal prefix Turing machine T, for every resource bound R E N² and program E ZT,R, we construct GMM posterior parameters &R.² and GMM prior parameters vi such that the KI. divergence is equal |z| plus additive constant and the model function is deterministic and equivalent to fj. Specifically, we construct of to approximate delta function each weight in zmap(T, R, 2). except for weights representing the program tape past the |æ|th register; these weights do not affect the model function being computed, and we therefore set their posterior to be equal to their respective prior, such that they can be transmitted "for free". Importantly, by construction, the output of zmap consists of a constant number of weights (depending on but not R?) outside of the Rt prompt embeddings (which represent the program tape contents). By sharing GMM prior across each feature column of the prompt embeddings table, the total KL for these embeddings is shown to be |2| bits. The fixed number of remaining weights can be transmitted in constant number of bits for any GMM prior assigning non-zero probability to the associated weights in zm R, z). This establishes the necessary upper bound on the minimum codelength, although there may be prior and posterior parameters offering even greater compression.
EXPERIMENTS & ANALYSIS
6.1 EMPIRICAL ANALYSIS VARIATIONAL CODE
First, we empirically evaluate the GMM-baseed adaptive variational code discussed in Section 5.1 as a computationally tractable and differentiable instance of an asymptotically optimal code for Transformers.
Computing parity We focus our initial investigation on the task of computing parity, i.e. given sequence of Os and 1s, determining whether there is odd or even number of Is. Computing parity is a common task for assessing Transformer expressivity and generalization (Hahn, 2020; Bhattamishra et al., 2020; Chiang & Cholak, 2022; Ruoss et al., 2023; Delétang al., 2022; Anil et al., 2022; Zhou et al., 2022; 2023). Standard Transformers trained with maximum likelihood ob- jectives struggle with consistent length generalization this task, making it useful benchmark for assessing whether an alternative objective can encourage stronger nattof-distribution generalization. key objective of our experiments is to distinguish between (1) failures of the proposed objective to select for compressible models with strong generalization and (2) failures to effectively optimize the proposed objective. To this end, for simple algorithmic tasks such as computing parity, we can again use ALTA, this time to manually determine a set of parameters that fits the training data and also has low complexity according to the proposed objective, establishing an upper bound on the minimum of the variational objective. We can then determine whether our optimization process, starting from a random initialization, can find a set of parameters with similar or lower loss. See C. for details.
The results for Transformers with different training objectives and initializations are shown in Ta- ble 1. Only the manually initialized model exhibits strong length generalization (OOD accuracy). All randomly initialized models fit the training set, but struggle with length generalization. The model trained with the variational objective from a random initialization does not achieve a loss comparable to the ALTA-compiler initialization. This suggests that while the objective may select for models with stronger generalization, standard optimization techniques fail to effectively find a strong minimizer, which we investigate further next.
8

---

Published as a conference paper at ICLR 2026
Table 1: Transformer performance on parity task for different training objectives and initializations.
Init.
Objective
KL (bits)
Train NLL (bits)
Train Acc.
OOD Acc.
Random
MLF Baseline
2.5 10a
100%
56.4%
Random
Variational
x 106
2.4 10a
100%
60.4%
Manual
Variational
8.7 x 10a
0.0
100%
100%
Optimization analysis To understand why our Transformer models underfit the proposed objec- tive when randomly initialized, we study the simplified setting of 2-layer MLP on simple identity task, with details in C.2. We use shared GMM prior and Gaussian posteriors for each weight. Again, we that random initialization fails to find loss comparable to that achieved via manual initialization, indicating poor optimization of the proposed objective. By inspecting the learned prior and posterior distributions compared those from manual initialization, we identify that one poten- tial culprit is that the prior distribution collapses to a unimodal distribution (see Figure 10 in C.2). This is in contrast our manually identified solution which consists of a multimodal distribution with low variance components, which leads to a significantly lower KL divergence. These results suggests that future work should consider alternative optimization procedures that discourage this form of collapse, or consider alternative families of asymptotically optimal codes altogether.
6.2 ASYMPTOTIC BOUNDS FOR ALTERNATIVE TWO-PART CODES
Next, analyze asymptotic bounds for alternative two-part codes that may be of practical interest but do not strictly satisfy the conditions of asymptotic optimality. Recall from 4.1 that the key requirement for satisfying the conditions of asymptotic optimality is that VR E N2 and Yz ZT, -lgg2 a (h*) < |a|+er +er where h² zmap(T' R, z) and or is an additive constant not depending on R 2. In Table the Description Length Bound refers to an upper bound on this model cost - log, aMa (h²), up to an additive constant, for various two-part codes that do not strictly satisfy this theoretical ideal. A sub-optimal bound for this quantity leads to sub-optimal bound for the overall minimum codelength, but close approximations could still be of practical interest.
Table 2: Combining standard methods for quantization, adaptive selection of the prefix length, and layerwise weight sharing yields two-part code with description length upper bound (described in 6.2) close to the theoretical ideal of |z|- Ablating these methods degrades the bound, shifting the encoding cost away from the algorithmic complexity of the function computed by the network (|z)) and causing the encoding cost to scale linearly with the total parameter count of the network, driven by its maximum space (R,) and time (R.) resources.
Quantization Aduptive Prefix Length Layerwise Weight Sharing
Description Length Bound
|a| log R, O(I=)) + log Rs ((R.) O(R.) + O(R))
X
We show that combining form of quantization, adaptive selection of the prefix length, and layer- wise weight sharing yields a description length bound that is close to the theoretically ideal descrip- tion length bound of |2], differing by only a log R, term. Adaptive prefix length means dynamically selecting the optimal prefix length, e.g. via hyperparameter sweep; transmitting this quantity introduces the log R2 term. Sufficient quantization can be achieved by using an adaptive GMM prior similarly to the previously studied variational code, using the adaptive quantization method proposed by Han et al. (2016), or by restricting the prefix embeddings to a fixed vocabulary as in discrete prompt optimization. The bound becomes progressively worse as these aspects are ablated, ultimately resulting in a uniform encoding of the model weights. Note that by definition |2| < R,, and we adopt O()) notation to indicate a multiplicative factor 1. Overall, the |x| + log R, bound can perhaps be seen as a relatively positive theoretical result for methods related to discrete prompt optimization. (See B. for additional details and discussion.)

---

Published as a conference paper at ICLR 2026
6.3 ALTERNATIVE TRANSFORMER FAMILIES
The analysis in this paper has focused primarily on scaling the time and space resource bounds of a Transformer encoder by scaling the number of layers and the length of prefix prepended the input, respectively, as described in 4.1. Here we briefly discuss alternative families of Transformers.
Scaling Transformer Dimensionality Rather than scaling the number of prefix token embeddings to represent increasingly complex programs, we could scale the dimensionality of the Transformer, effectively encoding the program tape in the MLP parameters. In B. 12 we discuss how mapping analogous to zmap could be established for such family of Transformers; however, this requires scaling the model and MLP dimensions linearly with program length. This results in the number of MLP parameters growing quadratically with program length, leading to bound of ((2)²) + log R. in the context of Table 2 if applying similar techniques. The constructed MLP matrices highly structured, but have rank that scales linearly with program length, and therefore cannot be easily compressed with standard techniques such as rank factorization. Therefore, identifying tighter asymptotic bounds for practical methods for MLP matrix compression would be of interest for future work. Otherwise, these results potentially indicate poor asymptotic bounds for standard methods related to MLP compression.
Transformer Decoders Rather than scaling the number of layers in a Transformer encoder to scale the time resource bound, we could scale the number of intermediate decoding steps in a Transformer decoder. This would not require explicit layerwise weight sharing maintain constant description length with respect to a growing time resource bound. The main challenge in implementing a map- ping analogous to zmap for Transformer decoder is in representing updates the Turing machine tape given the decoder's attention mask, but such a result could build on prior work establishing the Turing completeness of Transformer decoders under various conditions (Pérez et al., 2021; Merrill & Sabharwal, 2024a; Li & Wang, 2025). Future work could also study bounds for Transformer decoders that can interact with external tools.
RELATED WORK
Our work closely related the notion of universal induction (Solomonoff, 1964) and related theoretical frameworks (Levin, 1973; Hutter, 2000; Lattimore & Hutter, 2013; Achille et al., 2021; Nakkiran, 2021). For neural networks, a notable early work is Schmidhuber (1997), which in- troduced probabilistic search algorithm for discovering neural networks with low Kolmogorov complexity. However, none of these theoretically compelling approaches directly lead to practi- cal and scalable training objectives for neural networks. On the other hand, various MDL-inspired complexity measures have been proposed and evaluated for neural networks, based on variational inference (Hinton & Van Camp, 1993; Blundell et al., 2015; Louizos et al., 2017; Blier & Ollivier, 2018) or other methods (Li et al., 2018; Lotfi et al., 2022; 2024; DeMoss et al., 2025; Abudy et al., 2025), such quantization and low-rank approximation. However, prior work has not demonstrated asymptotic compression guarantees for such methods. Our main contribution is establishing asymp- totic bounds by constructing a bridge between Transformer weights and prefix Turing machines. Our results extend prior work establishing the Turing completeness of Transformers (Pérez et al., 2021: Nowak et al., 2024). We provide an extended discussion of related work in Appendix D.
CONCLUSION
In this paper, we introduced framework for analyzing asymptotic bounds for description length objectives, grounded in the MDL principle and the universality of Kolmogorov complexity. We established that there exist asymptotically optimal description length objectives for Transformers, while also highlighting potential challenges related to effectively optimizing such objectives. Min- imizing an asymptotically optimal description length objective achieves optimal compression for any dataset, up to an additive constant, in the limit resource bounds increase. Such guarantees are particularly compelling as the computational resources available for training models continue to increase. Our theoretical framework therefore highlights potential path towards identifying description length objectives leading to greater compression, and potentially greater generalization.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
We thank Jonathan Berant, Kenton Lee, and Tim Genewein for useful discussions and feedback, and the anonymous reviewers for their helpful comments.
REFERENCES
Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk. Generalization the unseen, logic reasoning and degree curriculum. In International Conference on Machine Learning, pp. 31-60.
PMLR, 2023.
Matan Abudy, Orr Well, Emmanuel Chemla, Roni Katzir, and Nur Lan. minimum description length approach to regularization in neural networks. arXiv preprint Sott:::200513399 2025.
Alessandro Achille, Giovanni Paolini, Glen Mbeng, and Stefano Soatto. The information complexity oonal of learning tasks, their structure and their distance. Information and Inference: A Journal of the IMA, 10(1):51-72, 2021.
Jan Achterhold, Jan Mathias Koehler, Anke Schmeink, and Tim Genewein. Variational network quantization. In International Conference on Learning Representations, 2018. URL https:
/ //openzeview. www.neee/oounnne wtr.//oommmrrrrrro -ieeeiidryy--e WAb.
Victor Akinwande, Yiding Jiang, Dylan Sam, and Zico Kolter. Understanding prompt engineering may not require rethinking generalization. In The Twelfth International Conference on Learning Representations, 2024. URL https:ttp//.occ http:///ppeeeveeeeeeeee htt.ttt///peeerreeeeeee
net. forum? d= FF......
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowyez, Vedant Misra, Vinay Ramasesh, Am- brose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35:38546-38556, 2022.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey Hinton. Layer normalization. arXiv preprint 1rX1vv:607.06444 2016.
Andrew R Barron. Logically smooth density estimation. PhD thesis, Stanford University, 1985.
Andrew R Barron and Thomas M Cover. Minimum complexity density estimation. IEEE transac- tions on information theory, 1034-1444, 1991.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. arXiv preprint arXiv:2009. /264, 2020.
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in transformers and their ability to learn sparse boolean functions. In The ó Annual Meeting Of The Association For Computational Linguistics, 2023.
Léonard Blier and Yann Ollivier. The description length of deep learning models. arXiv preprint 18X2:08002.0044 2018
Charles Blundell, Julien Corebiie, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International conference on machine learning, pp. 1613-1622. PMLR, 2015.
Jorg Bornschein, Yazhe Li, and Marcus Hutter. Sequential learning of neural networks for prequen- tial MDL. In The Eleventh International Conference on Learning Representations, 2023. URL https:://ppereviiee wwwppeweeweeeeeeeee/eeee /
James Bradbury, Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github. com/ jax aaaaammmaaaaaaaaaaeaaeaeaeealama ml/jax.
Gregory J Chaitin. On the length of programs for computing finite binary sequences: statistical considerations, Journal of the ACM (JACM), 16(1):145-159, 1969.

---

Published as a conference paper at ICLR 2026
Angelica Chen, Ravid Shwartz-Ziv, Kyunghyun Cho, Matthew L Leavitt, and Naomi Saphra. Sud- den drops in the loss: Syntax acquisition, phase transitions, and simplicity bias in MLMs. In The Twelfth International Conference Learning Representations, 2024. URL https: / //oppprreiiee ew net. forum? i d=MO5P KHELW.
David Chiang and Peter Cholak. Overcoming theoretical limitation of self- arXiv preprint arXiv:2202. 12172, 2022.
David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In International Conference Machine Learning, pp. 5544 5562. PMLR, 2023.
Tristan Cinquin, Alexander Immer, Max Horn, and Vincent Fortuin. Pathologies priors and infer- ence for bayesian transformers. In I (Still) Can't Believe It's Not Better! NeurlPS 202/ Workshop, 2021.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, 2nd edition, 2006.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser, Universal transformers. In International Conference on Learning Representations, 2019.
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg. Joel Veness, et al. Neural networks and the Chomsky hierarchy. arXiv preprint arXiv:2207.02096, 2022.
Gregoire Deletang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christo- pher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. Language modeling is compression. In The Twelfth International Confer- ence on Learning Representations, 2024. URL https:/ /tpp//ppeeevveeeeeeeeeee/eeeeeee ew net/ forum? did= jarbgiynus.
Branton DeMoss, Silvia Sapora, Jakob Foerster, Nick Hawes, and Ingmar Posner. The complexity dynamics of grokking. Physica D: Nonlinear Phenomena, pp. 134859, 2025.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized llss. Advances in neural information processing systems, 36: 10088-00115,,, 2023.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume (long and short papers), pp. 4171-4186, 2019.
Raaz Dwivedi, Chandan Singh, Bin Yu, and Martin Wainwright. Revisiting minimum description length complexity overparameterized models. Journal of Machine Learning Reseurch, 24(268): 1-59, 2023.
Nelson Elhage. Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. A mathematical frame- work for transformer cireuits. Transformer Circuits Thread, 2021. URL https:// transformer- circciitt..... www.eiis...tteete....... pwbppppbbat. httpp//////aaaneooo////oaaaaa
http///amawww/eeeeeeeeeeeeeeea/e html.
Fabio James Fehr and James Henderson. Nonparametric variational regularisation of pre- trained transformers. In First Conference on Language Modeling, 2024. URL https:
/ //openzeview..c..m htte://orummndd2.ssmnte
Guhao Feng. Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. In Shirtt-seventth Conference on Neural Information Processing Systems, 2023. URL https:/ http:////ppeeeeieeeeee net forum? AD=AAdAD
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059. PMLR, 2016.
12

---

Published as a conference paper at ICLR 2026
Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. International Conference on Machine Learning, pp. 11398-11442 PMLR, 2023.
Micah Goldblum, Mare Finzi, Keefer Rowan, and Andrew Gordon Wilson. The free lunch theorem, kolmogorov complexity, and the role of inductive biases in machine learning. arXiv preprint arX1v:2304.05366, 2023.
Jordi Grau-Moya, Tim Genewein, Marcus Hutter, Laurent Orseau, Gregoire Deletang, Elliot Catt, Anian Ruoss, Li Kevin Wenliang, Christopher Mattern, Matthew Aitchison, and Joel Veness. Learning universal predictors. In Forty-first International Conference Machine Learning, 2024. URL https::///// /ttps////oppeeeeeeeeeeeeee net/ http://www.eeettorriaa---------
Alex Graves. Practical variational inference for neural networks. Advances in neural information processing systems, 24, 2011.
Peter Grunwald. tutorial introduction to the minimum description length principle. arXiv preprint math/0406077, 2004.
Peter D Grunwald and Paul Vitanyi.
Algorithmic information theory.
arXiv preprint
arXiv:0809. 2254, 2008.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020.
Boumediene Hamzi, Marcus Hutter, and Houman Owhadi. Bridging algorithmic information theory and machine learning: A new approach to kernel learning. Physica D: Nonlinear PaeneeaarPeeenneee Phenomena, 464:134153 2024.
Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. In ICLR, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing huven-level performance on imagenet classification. In Proceedings of the IEFE international conference on computer vision, pp. 1026-1034, 2015.
Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings the the sixth annual conference on Computational
learning theory, pp. 5-13, 1993.
Antti Honkela and Harri Valpola. Variational learning and bits-back coding: information- theoretic view to bayesian learning. IEFE transactions on Neural Networks, 15(4):800-810, 2004.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang. Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. ICLR, 1(2):3, 2022.
Marcus Hutter. A theory of universal artificial intelligence based on algorithmic complexity. arXiv preprint cs/0004001, 2000.
Mareus Hutter. Universal artificial intelligence: Sequential decisions based algorithmic proba-
bility. Springer Science & Business Media, 2005.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax In International Conference Learning Representations, 2017.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas-
tic generalization measures and where to find them. In International Conference on Learning Representations, 2020. URL https: http///ppwweww.eec/eeee net httprrrewrreeeeeetooorrrrt-----e fote:/fffunu---SSSIIIRII
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412x:14/2.69880 2014.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. In International Conference Learning Representations, 2014.
13

---

Published as a conference paper at ICLR 2026
Diederik P. Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparame- terization trick. Advances in neural information processing systems, 28, 2015.
Kolmogorov. Three approaches to the quantitative definition of information. Problems of Infor- mation Transmission, 1:3-11, 1965.
Tor Lattimore and Marcus Hutter. No free lunch versus occam's razor in supervised learning. In Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence: Papers from the Ray Solomonoff 85th Memorial Conference, Melbourne, VIC, Australia, November 30-
December 2, 2011, pp. 223 225.235. Springer, 2013.
Leonid A Levin. Universal sequential search problems. Problems of information transmission, 9(3): 265-266, 1973.
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In International Conference on Learning Representations, 2018.
Ming Li and Paul Vitányi. An introduction to Kolmogorov complexity and its applications, volume 3.
Springer, 2008.
Qian Li and Yuyi Wang. Constant bit-size transformers are turing complete. ninth Annual Conference on Neural Information Processing Systems, 2025. URL https:
In The Thirty-
/popnrevieww wwwpenrewww.nee/eooooeeeeeeeeeee
David Lindner, János Kramár, Sebastian Farquhar, Matthew Rahtz, Tom McGrath, and Vladimir Mikulik. Tracr: Compiled transformers as a laboratory for interpretability. Advances in Neural Information Processing Systems, 36, 2023.
Sanae Lotfi, Mare Finzi, Sanyam Kapoor, Andres Potapezynski, Micah Goldblum, and Andrew G Wilson. Pac-bayes compression bounds so tight that they can explain generalization. Advances in Neural Information Processing Systems, 35:31459-31477 14773, 2022.
Sanae Lotfi, Mare Finzi, Yilun Kuang, Tim GJ Rudner, Micah Goldblum, and Andrew Gordon Wilson. Non-vacuous generalization bounds for large language models. In Proceedings of the 41st International Conference on Machine Learning, pp. 32801-32818, 2024.
Christos Louizos, Karen Ullrich, and Max Welling. Bayesian compression for deep learning. Ad- vances in neural information processing systems, 30, 2017.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous laxation of discrete random variables. In International Conference on Learning Representations, 2017.
James Martens and Roger Grosse. Optimizing neural networks with kronecker factored curvature. In Proceedings of the 32nd International Conference on International Conference on Machine Learning- Searning-Volume Volume 37, pp. 2408-2417, 2015.
kronecker-factored approximate
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations, 2024a.
William Merrill and Ashish Sabharwal. A little depth goes long way: The expressive power of log- depth transformers. In NeuriPS 2024 Workshop on Mathematics of Modern Machine Learning, 2024b.
Chris Mingard, Henry Rees, Guillermo Valle-Pérez, and Ard Louis. Deep neural networks have an inbuilt occam's 's razor. Nature Communications, 16(1):220, 2025.
Preetum Nakkiran. Turing-universal learners with optimal scaling laws. arXiv preprint arXiv:2111.05321, 2021.
Yaniv Nikankin, Anja Reusch, Aaron Mueller, and Yonatan Belinkov. Arithmetic without algo- rithms: Language models solve math with bag of heuristics. In The Thirteenth International Conference on Learning Representations, 2025, URL https: opwereviii. net forum?
1d=09YTe26r22.
14

---

Published as a conference paper at ICLR 2026
Franz Nowak, Anej Svete, Alexandra Butoi, and Ryan Cotterell. On the representational capacity of neural language models with chain-of of-in-of-thuuhhh reasoning. In Proceedings of the 62nd Annual Meeting the Association for Computational Linguistics (Volume 1: Long Papers), pp. 12510- 12548, 2024.
Steven J Nowlan and Geoffrey E Hinton. Simplifying neural networks by soft weight-sharing.
Neural Computation, 4(4):473-493, 1992.
Christos H. Papadimitriou. Computational complexity. Addison-Wand Weslle, 1994. ISBN 978-0-201- 53082-7.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Ma- chine Learning Research, 22(75):1-35,, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of machine learning research, 21(14)):1-67, 2020.
Samuel Rathmanner and Marcus Hutter. A philosophical treatise of universal induction. Entropy, 13(6):107--136, 2011.
Jorma Rissanen. Modeling by shortest data description. Automatica, 14(5):465 471, 1978.
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468 475, 2024.
Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Ben- nani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generalization of transformers. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 1889-1999999 1903, 2023.
Karthik Abinav Sankararaman, Sinong Wang. and Han Fang. Bayesformer: Transformer with un- certainty estimation. arXiv preprint arXiv:2206.00 00826, 2022.
Jürgen Schmidhuber. Discovering neural nets with low kolmogorov complexity and high general- ization capability. Neural Networks, 10(5):857-873 1997.
Dale Schuurmans. Memory augmented large language models are computationally universal. arXiv preprint arXiv:2301.044 044589, 2023.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pp-
464-668, 2018
Peter Shaw, Ming- Wei Chang, Panupong Pasupat, and Kristina Toutanova. Compositional gen- eralization and natural language variation: Can semantic parsing approach handle both? In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pp. 922-938, 2021.
Peter Shaw, James Cohan, Jacob Eisenstein, Kenton Lee, Jonathan Berant, and Kristina Toutanova. Alta: Compiler-base based analysis of transformers. arXiv preprint arXiv:2410.18077, 2024.
Ray J Solomonoff. formal theory of inductive inference. Information and control, 7(1):1-22,244 254, 1964.
Nikita Tsoy and Nikola Konstantinov. Simplicity bias of two-layer networks beyond linearly sepa- rable data. arXiv preprint arXiv:2405.17299, 2024.
Karen Ullrich, Edward Meeds, and Max Welling. Soft weight-sharing for neural network compres- sion. In International Conference Learning Representations, 2017.
15

---

Published as a conference paper at ICLR 2026
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- tion processing systems, 30, 2017.
Elena Voita and Ivan Titov. Information-theoretie probing with minimum description length. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 183-196, 2020.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Confer- ence on Machine Learning, pp. 11080-1 10990. PMLR, 2021.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of Sequence-to-sequeee functions? In International Con- ference Learning Representations, 2020. URL https:/ /ttp:////ppeeeeieee/e www. forum?
iddByxRMONtVV.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations, 2017. URL https: opw.revee.....e.eeeeeee.. net/ wtr.e/rrnmmmmmdaaaaaaa
Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi. Teaching algorithmic reasoning via in-context learning. arXiv preprint arXiv:2211.09000 2022.
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers learn? study in length generalization. arXiv preprint arXiv:2310.16028 2023.
Jiachen Zhu, Xinlei Chen, Kaiming He, Yann LeCun, and Zhuang Liu. Transformers without nor- malization. In Proceedings of the Computer Vision and Pattern Recognition Conference, pp- 14901-14911, 2025.
16

---

Published as a conference paper at ICLR 2026
APPENDIX
Additional Background
17
A.1 Binary Strings
18
A.2 Codes and Description Lengths
18
A.3 Kolmogorov Complexity
19
B Additional Theoretical Analysis and Proofs
21
B.1 Rationale for Rational-valued Model Functions
B.2 Note on "Universal" Terminology
21
B.3 Model Functions and Notation
22
B.4 Analysis of Two-Part Codes
23
B.5 Details of zmap
26
B.6 Proof of Theorem
31
B.7 Relations Between Codelengths
32
B.8 Analysis of Variational Codes
35
B.9 Analysis of Gaussian Mixture Models
37
B.10 Proof of Theorem 2
40
B.11 Analysis of Alternative Two-Part Codes
42
B.12 Scaling Transformer Dimensionality
43
Additional Experimental Results and Details
44
C.1 Transformer Experiments
44
C.2 MLP Experiments
47
Extended Related Work
48
D.I Theoretical Foundations
48
D.2 Variational Inference
48
D.3 Non- Non-Variational Complexity Measures
49
D.4 Computational Universality of Transformers
49
D.5 Simplicity Bias
50
A ADDITIONAL BACKGROUND
We first give an overview of relevant concepts related to Kolmogorov complexity and the Minimum Description Length (MDL) principle, and refer the reader to other resources for further reading, such as Li & Vitányi (2008), a reference text for Kolmogorov complexity and related topics. Other texts that cover these topics include Cover & Thomas (2006) and Hutter (2005). Some material is also covered tutorials Grunwald & Vitanyi (2008) and Grunwald (2004). Other notable resources include Barron (1985) which discusses the Kolmogoroy complexity of probability distributions, Rathmanner & Hutter (2011) which offers a more philosophical and intuitive discussion, and the in- troduction of Schmidhuber (1997) which offers concise summary for machine learning audience.
17

---

Published as a conference paper at ICLR 2026
A.1 BINARY STRINGS
Let {0, 13 denote the set of finite binary strings or sequences, e.g.:
{0, 13" {e, 0, 01, 10, 11, ..,,...,, with denoting the empty string. We denote the length of a string x {0, 1) as e.g. |0101 = 4.
(14)
Note that there is one-to-one correspondence between the set of binary strings and the natural numbers N,, e.g. equation 14 shows a standard enumeration. Therefore, there is also a one-to-one mapping between the elements of any countable set and binary strings.
A.2 CODES AND DESCRIPTION LENGTHS
We consider settings where a sender (e.g., Alice) wants to transmit some information to receiver (e.g.. Bob). Formally, consider the case where Alice wants to transmit an element from some count- able set X' to Bob by sending message consisting of some binary string, such that Bob can re- construct the element from the transmitted message. Thus, prior to communication, Alice and Bob must agree on a code, or description method, which can be characterized by a decoding function X. We refer to the binary strings in the domain of the decoding function as code-
D (0, 10" words (or programs, for reasons which will become clear in the following sections). For each code D, we can therefore associate description length measure, or complexity measure, LD : X + N, where the complexity measure's 's value for every x is equal to the length of the shortest program that generates z:
Lp(x)= length of the shortest program such that D(2)
min |
(15)
D(=)=s
Therefore, a code D establishes a compression scheme, where Alice can transmit an element æ E X to Bob using (1) bits.
Prefix codes and Kraft's inequality If Alice wants to send Bob a sequence of elements in X, not all codes guarantee that such a sequence is uniquely decodeable, i.c. that the sequence can be unambiguously reconstructed when the messages for each of the elements are concatenated. This ambiguity can be resolved by considering a prefix code. A set B C {0, 1) is prefix-free if no element in B is prefix of any other element in B. A decoding function specifies a prefix code if its domain is prefix-free. A common example of a prefix-free code is Huffmann code.
Krafi's 's inequality captures an important relation between description length measures and prefix codes. states that there exists a prefix code D over X' with description lengths LD if and only if:
2--Lo(z) < 1.
2 Lo(x)
(16)
Prefix codes and probability distributions Beyond the practical advantages of self-delimiting codes, primary theoretical motivation for considering prefix-free codes their close connection with probability distributions. Given probability distribution p(x) over X, there exists prefix-free code D for X' such that:
(17) where we round up form integer-length codewords. One method for constructing such code is Shannon-Fame Fano coding, where more likely elements are assigned shorter codewords. As we are primarily interested in theoretical codelengths rather than practical codes, we will typically omit the additive constant from this rounding and consider non-integer codelengths.
LD(x)= = loge p(x)
Universal prefix codes Let us consider the set of all computable prefix- free partial functions map- ping from binary strings to elements of some set X, denoted as D. Each decoding function D E 'D has a corresponding description length measure, Lp. given by equation 15. In general, Ln may be an unsatisfying complexity measure for elements of X' due to its strong dependence on the po- tentially arbitrary choice of D. However, in the following section, we will show that there exists a subset of functions in D, that are universal in the sense of offering at least much compression as any other description length measure, up to an additive constant that does not depend on the complexity of the element being encoded.
18

---

Published as a conference paper at ICLR 2026
A.3 KOLMOGOROV COMPLEXITY
The definition of Kolmogorov complexity (also called algorithmic complexity) and the proof of its universality come from Kolmogorov (1965), with similar formulations appearing independently in Solomonoff (1964) and Chaitin (1969).
Intuitively, we can think of the Kolmogorov complexity K (x) of an object æ as the shortest program written in some standard programming language (such as Python) that prints æ. To make this notion more precise, Kolmogorov complexity is typically defined with respect to special class of Turing machines, called prefix Turing machines. (With some effort, it could be defined with respect to any universal model of computation.)
Prefix Turing machines Prefix Turing machines multi-tape Turing machines. As with all multi-tape Turing machines, the behavior of the machine is specified by a transition function. At each step of computation, the transition function takes as input the current state and the register values at current "head" position of any readable tape. The transition function can then optionally update the register values of any writeable tapes at their current "head" positions and optionally move each "head" to an adjacent register. The machine then updates the state for the next step or halts the computation.
The defining characteristic of prefix Turing machine is a binary, unidirectional, read-only program tape with no blank symbols. The machine also consists of bidirectional, read-write work tape. The machine also has at least one read-only input tape, and at least one write-only output tape."
For prefix Turing machine T, we abuse notation and write T to denote the partial function that the machine computes, i.e. where = T(x, =) denotes that the Turing machine T, with the input tape initialized with æ and the program tape initialized with prefix 2, runs for some number of steps before halting with written to the output tape. The function is undefined for (zz 2) that do not halt.
Universal Turing machines Notably, there exists a subset of prefix Turing machines that are universal the sense of being able simulate the computation of any other prefix Turing machine. Such a machine can effectively take as input the description of any other Turing machine, and emulate the computation that machine.
Kolmogorov complexity The commonly used notion of Kolmogorov complexity used throughout this paper - is called prefix Kolmogorov complexity, to distinguish from plain Kol- mogorov complexity, which lacks some of the desirable formal properties.
The (prefix) Kolmogorov complexity of a string x E {0, 1}" with respect to a universal prefix Turing machine T is:
Kr(x)
min |2). T(e
(18)
where denotes the empty string.
Similarly, the conditional Kolmogorov complexity of string y given is:
Kr(y)=) =: T:(,))))= |z|.
min
(19)
Note that Kolmogorov complexity (r(x)) satisfies Kraft's inequality because the set of halting pro- grams is freei
Invariance theorem
The invariance theorem is the key result that gives Kolmogorov complexity its universal property. Given any two universal prefix-free Turing machines 7 7
Vx, Krr (x) - (Tr(2)) c,
(20)
where e is a constant that depends on the choice of 7 and T but not on æ, and therefore we write
Vxx Krr (x) 1 Ky= (z), recalling the notation from Section 2. The invariance theorem intuitively
NNoe that in some constructions, programs and inputs are encoded on the same tape, although this detail only affects the resulting definition of Kolmogorov complexity by an additive constant.
19

---

Published as a conference paper at ICLR 2026
follows from the result that universal Turing machine simulate the computation of any other Turing machine. Informally, the constant с captures the cost of constructing an interpreter for pro- grams written for T in the language of T The result also extends to conditional Kolmogorov complexity.
Therefore, we are primarily interested in inequalities that hold up to additive constant, write Kolmogorov complexity as (() and drop the explicit dependence on a particular choice of reference machine.
Computability Kolmogorov complexity is formally uncomputable due to the halting problem. If we try to enumerate programs from shortest to longest, some may never halt. It is, however, upper semicomputable. Any program that halts and generates the given object provides an upper bound. This upper bound becomes increasingly tight we run more programs for more steps.
Universality of Kolmogorov complexity As corollary the invariance theorem, Kolmogorov complexity is universal description length measure as described in Section A.2, i.e. for any com- putable prefix-free decoding function D and corresponding description length measure Lp,
Vz K(x) S LD(x).
(21)
In other words, Kolmogorov complexity can be interpreted as a compression scheme, where Alice encodes string by the shortest program that generates x. This compression scheme offers least as much compression of x, for any z, as any other computable prefix code up to an additive constant that does not depend on x. Thus, the complexity of x: increases, the additive constant becomes negligible, and all such universal description length measures are asymptotically equivalent. Con- versely, any description length measure provides an upper bound on Kolmogorov complexity, up to an additive constant, however this bound may be arbitrarily loose for some objects.
Kolmogorov complexity of countable objects The definition of Kolmogorov complexity natu- rally extends to countable sets other than the non-binary strings. For example, for æ X and y E y where X' and Y are countable, we have:
K x)
min |2/
(22)
2: T.:T(ex ((ex(())))==)((l
or oo if no such exists, where ex (x computable functions mapping from x and y to binary encodings, and T is universal prefix Turing machine. While K (y I²) therefore depends on a specific choice of ex and ey, we leave this implicit the notation. Since ex and ey are computable functions, the specific choice only affects K (y x)) up to an additive constant that does not depend on x. similar to the choice of T.
X + 10, and ey(x) : y + 10, are one-to-one
For structured objects such as tuples, we can consider prefix Turing machines with multiple output tapes, in order to simplify the encoding of such objects. For such universal prefix Turing machine T. we use the same notation as above, assuming that both T(x 2) and éy output a tuple of strings with number of elements equal the number of output tapes. Again, such choice only affects the resulting definition of Kolmogorov complex up to an additive constant, as the number tapes does not affect the machine's expressive power (Papadimitriou, 1994).
Kolmogorov complexity of discrete functions We can extend the definition of Kolmogorov com- plexity to functions. This is relatively straightforward for a function f X + y if the domain X' and range y are countable such that the inputs and outputs of the function can be encoded as binary strings. Again, we choose reference universal prefix Turing machine T.
K()-
min
|z|,
(23)
2: Vz. T(ex (a) my (f())
or oo if no such 2 exists, which is the case if f is uncomputable, e.g. it solves the halting problem. As a direct analogue the invariance theorem for Kolmogorov complexity of strings, the same property holds for the Kolmogorov complexity of functions. Extensions to real-valued functions are discussed in Appendix B.I.
20

---

Published as a conference paper at ICLR 2026
Resource-bounded Kolmogorov complexity can consider computable, resource- resource-bounded ap- proximations to Kolmogorov complexity (Li & Vitányi, 2008, section 7).
Consider resource bound R. (Re, R2) N2, representing bound on the time Rd N and Rg E N space resources available.
Given universal prefix Turing machine T, let y Tu(x, 2) denote the partial function computed by T if the execution given I and halts within Rg steps and uses at most R, registers on each tape; otherwise (2, is undefined. We can then define time and space bounded Kolmogorov complexity with respect to and Rt
KT x)
min
|2|,
(24)
a (0,)))==
or oo if no such exists, with an analogous definition for functions.
The resource-bounded version lacks the universal properties of unbounded Kolmegorov complex- ity. However, Kr,n(y x) is monotonically non-increasing with respect to increasing R2 and R., decreasing to KT (y x) as R& and Rg go to co.
Coding theorem The coding theorem is central result in algorithmic information theory (Li & Vitányi, 2008, Section 4), and relates to the universality of Kolmogorov complexity. key result of the coding theorem is that if m is lower semicomputable semimeasure, then:
K(x) S - log, m(x).
(25)
where semimeasure is generalization of probability distribution, such that semimeasure over a domain satisfies:
Σ ((())_L)
(26)
ZEX
Note that because ((x) is upper semicomputable and satisfies Kraft's 's inequality. 2 xx)(x) is lower semicomputable semimeasure.
This result also extends to conditional Kolmogorov complexity, and, as a direct analogue, to the Kolmogorov complexity of discrete functions.
B ADDITIONAL THEORETICAL ANALYSIS AND PROOFS
B. RATIONALE FOR RATIONAL- VALUED MODEL FUNCTIONS
Defining Kolmogorov complexity for function f X + IR with a countable domain but real- valued range is slightly more complicated than for functions with countable (c.g. rational-valued) outputs, but we accomplish this by considering the shortest program for given universal prefix Turing machine I' that can approximate ff an arbitrary degree of precision E specified additional input:
K() = min[[2|: Vo X. (() - s(x) < 1/a).
(27)
Given this definition, could define two-part and variational codes with respect to model func- tions with real-valued logits, analogously to those defined with respect to model functions with rational-valued logits. However, this leads significantly greater theoretical complexity with lim- ited practical benefit, given that real-world neural networks represent logits with finite precision, and any valued function can be approximated an arbitrary degree of precision by rational-valued function.
B.2 NOTE ON "UNIVERSAL" TERMINOLOGY
The term universal is overloaded in the context of codes and compression schemes, with different usages varying with respect to the scope (the class of codes/models being compared against) and the nature of the performance guarantee. Our usage of the term in this paper follows the use of the term in the algorithmic information theory literature describe the universality of Kolmogorov
21

---

Published as a conference paper at ICLR 2026
complexity with respect to any computable prefix code, up to additive constant. We extend this notion to slightly restricted sets prefix codes, i.c. the specific classes of two-part, Bayesian, and variational codes discussed in this paper.
In contrast, the term universal code also appears in the MDL literature (Grunwald, 2004) to describe codes that universal with respect specific of candidate codes, in the sense of offering as much compression as any candidate code, up to a factor that is typically logarithmic with respect to the size of the candidate set data sample. The term "universal code" is also used describe prefix codes for integers, such as Elias codes, which offer asymptotic guarantees relative to any other prefix code assuming a monotonically decreasing probability distribution over the integers.
B.3 MODEL FUNCTIONS AND NOTATION
Here we introduce standard encodings, and eg, used to define the Kolmogorov complexity of model functions, F X + L, introduced in Section Let us denote the class of universal prefix Turing machines compatible with these encodings as T, with the specific assumptions specified in the following paragraphs. Recall that the specific choice of universal prefix Turing machine, and encoding functions ex and eg, only affect the resulting definition of Kolmogorov complexity by an additive term (A.3), which does not affect the main inequalities we are interested in proving, which hold up to additive term. Therefore we choose encodings to simplify the construction of function zmap introduced later (B.5), which generates Transformer parameters to emulate a prefix Turing machine.
Input encoding Let V be vocabulary input tokens. We assume some one-to-one encoding of inputs ex X 1/ as a token sequence, which is represented the input tape. For generality, do not necessarily assume the input vocabulary is binary, and assume the input tape of any T e T has number of symbols greater than or equal to |V].
Output encoding Recall that the output of a model function a tuple of rational-valued logits, with one logit for each element in the output space y, i.e. L = Q!Vi, We assume that any T E T has | write-once, unidirectional output tapes, with each logit E Q encoded on a separate output tape in the following format. Let E {0, 1} denote the sign of the logit, numerator E No be the numerator and denominator E N be the denominator. The logit is then encoded on the output tape as:
numarator denom! nstor-1
1,1,, 1,0, 1,1, followed by blank symbols. Therefore, ec : Q131 + 13))D.
(28)
Shorthand notation We introduce the following shorthand notation related to prefix Turing ma- chines and the encoding functions introduced above.
First, let us define a model function fi F computed by T E T with program a as follows:
(x) ==- (T(ex(x),=)).
(29)
Next, let define the set of programs where T E T halts with valid output for any input:
ET = (= Vx E X, ((ex( E dom(ez))
(30)
Additionally, let denote the set of programs where T T halts with valid output for any input under resource bound R as:
Zr, {2 Vx X, Tn(ex(*), 2) e dom(ez)).
(31)
Note that we can rewrite the definitions of Kolmogorov complexity with respect to these definitions.
Kr(f)
min 2E f/=1
x//
(32)
or oo if no such z exists, and similarly:
KI,R(f)
min = ZT, - |2/,
(33)
if no such exists, where f denotes that Vor E X, fz(x) f(x).
22

---

Published as a conference paper at ICLR 2026
B.4 ANALYSIS TWO-PART CODES
Here we provide the proof of Proposition 1, along with supporting lemmas and related analysis of two-part codes.
B.4.1 LEMMAS AND 2
We introduce the following lemmas support our later proofs.
Definition 6 (description length of model function). The description length of a model function f under code M, denoted MM() (f). is the codelength of the shortest hypothesis that maps f:
(T)
min (b)=
-log 0'M (h).
(34)
hERa
Lemma 1. The minimum codelength of two-part code M can be expressed as minimization over the set of model functions realized by M:
L % p.opprr
MM
(Y
min
(L log, P()
(35)
fEim(mar)
where im(ms) is the image of the mapping mas i.e, the set of all model functions such that = mM (h) for some E H...
Proof. We start from the definition of the minimum achievable codelength, equation 3:
L M
two-part
(YIX)= min
LM (Y|X;h)
two-part
N
min (-logz 0rM (h) - log, P(Y M; (h))).
We partition the hypothesis space HM into disjoint sets, where each set contains all hypotheses that map to the same model function f E im(mas). The minimization over all E Hy can then be rewritten two-level minimization: first, for each function f, minimize over all hypotheses that produce it, and second, we minimize over all possible functions f:
( min (EEHM mas (h)=f (- logg a's (h) logg p(Y X: mm((()))))
L two-part (Y[X)= min fEim(maz)
For the inner minimization, all hypotheses h map to the same function f. Therefore, the term - logg p(Y M; is constant and equal to - log, p(Y X: can pull this constant term out of the inner minimization:
L * two-part (Y
min /Eim(maz)
( min
loog am (f)) log, p(Y Xx xx:))
ma (h)=f
By our definition in equation 34, the inner term is precisely the description length of the function f. L (f). Substituting this back gives the final result:
L two-part (Y[X)=
min fEin(mar)
(IZ7( log, P( (x:
Lemma 2. For any Iwo-part code M and for all f FFF
K()) & (5)
(36)
Proof. First, we show that 2- ()) is semimeasure over F.
Substituting and simplifying the definition of L (f), we have:
2 -4a0))
max heHM mm mM (
a. (h)
(37)
We now need to show:
Σ
max heHar ms (h)=f (m)(1)) S
(38)
fEim
23

---

Published as a conference paper at ICLR 2026
The summation is effectively over some subset of hypotheses in HM, i.e those that offer the shortest description length for some function. As each element of the summation is non-negative, we have the following inequality:
max NeH m ( (nr(h))
Σ
am((h)
Σ
aM)),,
/éim mar
fEim ma
heHaa (h)
hEHA
and because (h) is, by definition, semimeasure over HM, we have:
Σ (h) S
kMHM
and therefore ( is semimeasure. Similarly, 2 -- (f) is lower semicomputable, given that au (h) by definition lower semicomputable. Therefore, per the coding theorem, we have:
K(f) & logg 2-22--3 (3)
K()) & (S).
B.4.2 PROOF OF PROPOSITION
Proposition (Proposition restated), There exists a universal two-part code.
Proof. We construct two-part code with respect to a universal prefix Turing machine T T. The components of U are defined as follows:
The hypothesis space Hu {0, 13* is the set of binary strings, i.e. programs.
The mapping function my Hy - FF takes program h E Hy and maps to model function. Specifically, my (h) f/. i.e. the function computed by running the machine T with program h.
The prior au (h) is defined as 2 |hl for h E Zr, where |h] is the length of halting program h. Otherwise, ou (h) if h does not halt for all inputs. The prior is therefore lower semicomputable semimeasure.
By the definition of a universal Turing machine, the image my is the set all computable model functions, F.
Using Lemma we can analyze the description length of a function f under our code U. Recall that L (f) is the codelength of the shortest hypothesis that maps to f. For our code U, this becomes:
TT
NgHu min mu mm()= (- logg or (h))
min Ae(0,1) mR (M)= (- logg 2-1h)
min he カ= [n].
(39)
The final expression is, by definition, the Kolmogorov complexity of the function with respect to machine T, denoted K2 (f). By the invariance theorem, LF(f) - K(f). By Lemma 2, for any other two-part code M. we have K(f) ž (f). Therefore, combining these results, we have key inequality that holds for any two-part code M and any function f:
DE( = K() 3 (.)
(40)
Finally, we show that U is a universal two-part code. We must prove that for any other code M, * tww-part
T. two-part [Y] x) & T
soo-pat(ty (Y X).
24

---

Published as a conference paper at ICLR 2026
Let für be any model function that minimizes the codelength for code M given dataset (X, Y), re- re-written as a minimum over model functions, per Lemma 1, such that:
L * www--prrt/ (Y X) Lis (Ji) loga p ( ftr).
(41)
The minimum codelength for our universal code U is, by definition, no greater than the codelength achieved by using the specific function f'a::
* k.ww part (Y x) (FM)) loggp(V[X;
(42)
Using our key inequality from equation 40, we know that (fM) & L (fM). Substituting this into the right-hand side of equation 42 yields:
* two-patt x) E (SM) log, PY fMr)
L.
Now, substituting equation 41 into the right-hand side of the expression above gives us our final result:
* two-part (Y (X) S *. two-part (Y X M
(43)
Since this holds for any two-part code M, we have shown that U is universal two-part code.
B.4.3 DISCUSSION OF UNIVERSAL TWO-PART CODES
Notably, satisfying the conditions of universal two-part code does not require that LM (h) &or (h) for all hypotheses. This is particularly notable for neural networks, where hypothesis spaces are typically highly redundant many different parameter sets (hypotheses) compute the same model function. Our definition allows for some of these parameter sets to be inefficiently described, with description length far exceeding their own Kolmogorov complexity. Universality is maintained as long as for any given model function, at least one of its corresponding parameter sets is described efficiently (with description length equal to the function's Kolmogorov complexity, up to some ad- ditive constant). Therefore, we can devise universal two-part codes without necessarily needing to devise description length measures that optimally compress every possible hypothesis, a potentially significant challenge for the vast and redundant parameter spaces of neural networks.
On the other hand, because some (or even most) hypotheses may coded quite inefficiently, a universal two-part code would not necessarily be useful for post-hoc model selection across models that were not trained to optimize the given two-part description length objective.
B.4.4 PROOF OF COROLLARY 1
Corollary (Corollary 1 restated). The minimum of any universal two-part code M is equal to the following bound, denoted Chno-port (Y X), up to additive term:
Chwo-paart (Y (X) min K()) log2 p(Y (X;)) $ LM
paor (Y X).
(44)
FEF
Proof. Let U be the specific universal two-part code constructed in the proof of Proposition Its minimum codelength is given by:
# pwotpart (Y X)
min (L) log, (Y] FEF
(45)
In that proof, we established that, (.) $ K()). Substituting this into the equation above directly shows that the minimum codelength of U is equivalent to the bound twwoppart (Y X):
L *c. part (Y X)
+ min (K()) - log,, p(Y (x;f)) = twoo-part (Y X).
(46)
fE
Now, let A be any other universal two-part code. By the definition of a universal two-part code, its minimum codelength must be equivalent to that of U. i.e., LM tttt--part (Y X) # L k.too-par (Y X)) therefore follows that the minimum codelength for any universal code M is equivalent to the bound.
25

---

Published as a conference paper at ICLR 2026
B.4.5 PROOF PROPOSITION
Proposition (Proposition restated). Given an asymptotically optimal family of two-part codes {MR E Nº]:
lim I>*.wo--oon pa X) Chho-ppart Rs R, -000
part (Y X);
(47)
with the bound CT (Y) X) monotonically non-increasing with increasing R₂ or Rs-
Proof. The proof has two parts: establishing the limit and showing monotonicity.
First, for the upper bound, the definition of an asymptotically optimal family states that for any resource bound R:
M
J.www-parttoo (Y (X) I T. MR
Olwo-part (Y X) = min (Kr,a(f) - log, P(Y x:f)).
(48)
FEF
As the resource bounds Re; R. - xo, the resource-bounded Kolmogorov complexity KT,R(f)
converges the standard Kolmogorov complexity Kr(f). By the invariance theorem, Kr(s) 1 K(),, so the bound converges to the universal two-part codelength:
lim R,000
TT, (Y X) = Cowo-par (Y XX.
(49)
This establishes the upper bound for our limit:
lim
L # Atw--aprrt (Y X) towo-part (Y X)).
(50)
MM
Re,
For the lower bound, we know from Corollary that Ctwo-part (Y
X) is the universal lower bound (Y x) Ctwo-par(y
for any two-part code. Thus, for any R. I * two hold in the limit.
X), which must also
MR
Since the limit is both upper- and lower-bounded by (two-purt)) (Y X) up to additive constant, the equivalence holds.
Now we focus on showing monotonicity. Let R and R'' be two resource bounds such that It' provides at least as many resources as R (i.c., R2 2 R,, R, > R.). Any program that is computable within bounds R. is also computable within bounds R'. This implics that for any function f. KT, (f) I (f).(f). Consequently, the bound on the codelength is monotonic:
(dwo-part (Y Cwwo-pan part (Y X) < C
( XX).
B.5 DETAILS OF 2MAP
We use the ALTA compiler (Shaw et al., 2024) to construct (in Python) a function zmap(T, R, that generates Transformer weights such that the Transformer emulates the model function computed by a prefix Turing machine T with program tape contents = under resource bound R. Formally, we construct zmap satisfy the following condition for all X, R E N2. E ZT, and T T:
mR 22, = f7.
(51)
where:
The mapping function mR prepends R, "prompt tokens" to the input and then runs the forward pass of the Transformer with parameters h, outputting the unnormalized logits prior to the final softmax. Recall that R, E a space resource bound.
The output of zmap is set of Transformer weights, with the particular model dimensions depending on and R.
Recall f F is the model function from X' L computed by prefix Turing machine T' T with program z, where T is a class of universal prefix Turing machines which assumes specific encodings for X' and on the input and output tapes, ex and eg, respectively. Also recall that Zr is the set of programs for T that halt with a valid output under resource bounds for all inputs. (See B.3)
In this section we detail the construction of zmap and these supporting constructions, which are later used to prove the paper's key theorems.
26

---

Published as a conference paper at ICLR 2026
B.5.1 TRANSFORMER INPUT PREPROCESSING
As described above, the mapping function my involves prepending R2 prompt tokens, and then running the forward pass of the Transformer. Given input tokens ex(x) = (I1, T2, -//1) E V", we prepend a sequence of Rg prompt tokens (p1,72," .RR) from a separate vocabulary of size Rg. We then form the Transformer input sequence (prior the embedding lookup) follows:
START, Pl, P2. P2,
PR, SEP, 11,42, 42, 3/1x] END,
(52)
where START, SEP, and END special reserved tokens.
B.5.2 EMULATING SINGLE-TAPE TURING MACHINES
The function zmap generates Transformer weights that emulate multi-tape prefix Turing machine, including decoding of the output tapes to set of logits. Before we describe zmap, we start with simpler explanation of how Transformer can emulate single-tape Turing machine, by giving code for an ALTA program. We refer the reader to Shaw et al. (2024) for an explanation of the ALTA language and compiler.
class PransitionIn: state: head_symbol: int
class Move (enum. Enum)
LEFT enum. auto ()
RIGHT enum. auto ()
class TransitionOut:
state:
symbal: int | None
Move None
halt: bool Fal
TransitiorPh Callable [TransitionIn), TransitionCut]
class MachineSpac:
transition_fes TransitionFa Turing machine transition function. num_states: int Turing machine number states.
num num_symbols: int Number of tape symbols.
num_steps: int Time resource bound.
num_registers: int Space resource bound.
Figure 4: Transition function definition for standard single-tape Turing machine.
To start, we define data structures to represent the transition function of single-tape Turing machine in Figure Next, in Figure 5, we include function that, given transition function, defines an ALTA program that can be compiled to Transformer, which emulates the provided Turing machine. The Transformer expects, input, sequence representing the initial state of the machine's tape.
While there are potentially many ways to emulate Turing machine in Transformer, representing each register different input position, and using relative position representations facilitate shifting the attention head to the right or left, is relatively straightforward implementation that efficiently leverages the Transformer's element-wise weight sharing and self-attention mechanism.
B.5.3 DEFINING žMAP
The sketch of the ALTA program for zmap roughly follows the program for a single-tape Turing machine from B.5.2, extended to handle multiple tapes: the input, program, work, and output tapes.
To facilitate "decoding", the output tape registers are represented differently in the Transformer than the registers for other tapes. Recall the encoding of the logits the output tapes specified in B.3. The first bit written to the Turing machine's 's tape specifies the sign of the logit, and therefore for this first bit set the value of binary "sign" variable. The number of subsequent 1s written
27

---

Published as a conference paper at ICLR 2026
from alta import bullder as
def bulld_turing wwwhine_epograaaaeeeeeeeeeeeeaae seeeca MachineSpec) -> pb..roge Progr **"Reuurns ALTA program spec for Turing machine emulator.
variables -
"halted": pb.var(2),
"state": pb. (spec. aereeccnmm_sttteeee
"symbol*: pb. input_vae var (spec. num_symbols),
"head": pb. Lnput__atva (2, fn-lambda -- START),
"one": pb. var (2, default=1), # Constant for queries.
attention_head -1
# Read the symbol at the current head position. "head "head_symboll" symbol": ab.qkk("ane" "head", "symbol"), Identify tape ceils to the ieft and right of the head. "head_laft"; pb.y_relative ("head", -1), Thead_right pb.v_relative ("head"
def ffr_fn (X):
"RAFEN function for Turing machine emulator. ""* if x x["balted"]:
return
Get the next action from the state transition function. output spec. opec.transition_fn (
"ranstiionn(sttttexx
head_synbol-x ("eaadd-xx"eeddaaee symbe_"
x ["staate"] steput.statt.
if haltu
x x["halted"] -
Write a new symbol at current head position specified if x["head"] and output. symbol is not None: x x["symbol"] output. output.symbol symbol
Nove the tape head left right if specified. if output. move is not None and x["head"]; x [[heaa"] -
if output.moov move -- Move.RIGIT and x ["symbol*)) !- START and x x x x["head"] =
elif output..toooo move == Move. MFVe.IEFT and x x["symba" "] != END and x xi"heed_right"") x("head")
pb. ob.pprogran_spet fn-fffn fn, variablee-variables heads-attention heads, ditpput_nam==ssymbba input_range-spent nun_symbols 2, position_range-
Figure 5: ALTA program specification for emulating single-tape Turing machine.
the Turing machine's tape specifies the numerator. For each we increment numerical variable "sum" by +1 or -1 depending on the "sign" variable. This "sum" variable is only non-zero at the START position. After 0 is written the Turing machine's tape, we transition to incrementing the denominator. This is represented by changing binary "key" variable from 0 to 1 at subsequent positions each time the transition function specifies that should be written (the "key" value also initialized to 1 at START). Finally, once the Turing machine has halted, attention head attends to each position where "key" is 1, and then averages over the "sum" variable, which is non-zero and equal the numerator exactly position. The output of the attention head is therefore the logit value, equivalent to the value decoded from the Turing machine's 's corresponding output tape given the encoding function.
The pseudocode for both zmap and the corresponding mapping function are given in Figure 6. The Pref xMach neSpec specifies the transition function for prefix Turing machine T as well
28

---

Published as a conference paper at ICLR 2026
Inpu:Sequence = 1ist [int]
Logits = list [float]
ModelFunction - Callable| (taaaable(ittttteeeeeeeeee [IngutSequence),
Logits]
def zmap (machineg (machine_speneeeeee se_cpec:
program_pzeeixx [int()
TransformerParameters
alta_program_spec huil:ooreeiiiiiiineeeeeeeeeeeee
machine_spec, program_preffxx prefix)
return alta_compi Ter talta lerraaltappoorrmmeeee
def mapping_fn(
machire_spec: PrefixMacis ieachiMachinne Maaahhnnee Meecicceceeee,,,,,
parama: TransformerParamettttoo
ModelFunction:
def model_fn (Lopl__nntaputttookee Input.Sequence) -> Logits:
Prepend promot and add special tekens.
tramsformer_imput preprocess_input (machine_spec, input_tckens) return run transfrrrrreee (parama, nachine_apes tranaformer input) return model_fa
Figure 6: Pseudocode for zmap and corresponding mapping function.
as resource bounds R. We omit the full implementation of the program specification for brevity. We verified the correctness zmap using unit tests.
B.5.4 ALTA COMPILER MODIFICATIONS
We make several modifications to the original ALTA compiler detailed in Shaw al. (2024) to reduce the number of compiled weights, which is necessary to support our later proofs. ALTA programs represent the behavior of the MLP sub-layer compiles to a single dimension of the weight matrices in the MLP sub-layer.
of MLP rules. Each MLP rule
The original ALTA compiler represents all categorical variables as one-hot vectors. We introduce binary variables, which function similarly to categorical variables with range 2, but are represented one necessary modification to constructing the first MLP weight matrix in the case where MLP rule needs to match against a binary variable being 0. In this case, we include a -1 at the index corresponding to the binary variable. This is particularly useful to represent each bit the program tape as a single weight.
single activation dimension, as either or This leads to
We don't 't require specifying fixed buckets for discretizing numerical variables. This means that numerical variables cannot be used as constraints in MLP rules, but this is not required for the zmap program. This also means that the number of weights in the MLP layer does not need to scale with the number of values the numerical variable can take on, which is useful given that the scale of the "sum" variables representing the logit numerators can grow arbitrarily.
We add support for a MLP rule to increment a numerical variable by a fixed sealar. This is relatively straightforward to implement by including the fixed scalar at the index corre- sponding to the numerical variable in the second MLP weight matrix. This enables us to increment the "sum" variables by less of the input value of the variable, by leveraging the Transformer's 's residual connection.
-1, with MLP rules covering both cases, regard-
We enable specifying multiple output variables for the Transformer. This way, the output projection can select the \ variables corresponding to the outputs of the attention heads that compute the final Y logit values.
B.5.5 COMPILED WEIGHTS
The weights compiled by zmap have the following properties:
All layers share the same weights, as in a Universal Transformer (Dehghani et al., 2019) or Looped Transformer (Giannou al., 2023).
29

---

Published as a conference paper at ICLR 2026
The minimum dimensionality of the activations in the Transformer scales linearly with the number of input (V) and output (())) symbols and the number of Turing machine states (specified by T E T), and does not grow with increasing resource bounds. Therefore, the number of weights in invariant to to the time resource bound R.
The minimum number of attention heads similarly scales linearly with the number of output symbols, as each output tape requires 3 attention heads, and there is output tape per output symbol. A total of 7 additional heads are needed for the program, input, and work tapes. However, the minimum number of attention heads does not scale with any resource bound.
The minimum hidden dimension of the MLP layer determined by the complexity of Turing machine's transition function, but similarly does not scale with any resource bound.
The Transformer requires only relative position representations, and no absolute position representations. requires separate bias terms only for relative positions -1 and +1, i.c. to attend to positions immediately to the left or right.
The Transformer's input embedding table has VI + R. + rows, i.e. embeddings for START, SEP, END, each token in the input vocabulary V. and R, prompt tokens, where Rg is the space resource bound. As the embeddings for the prompt tokens therefore are the only weights that scale as a function of any resource bound, we discuss these weights specifically in the following section.
Therefore, the number of necessary weights, i.c. the hypothesis space, is a function of T and R, but not The weight dimensions are minimums because the compiled weights always be padded with Os or 1s. Also note that Transformers compiled by ALTA exactly compute a symbolic program in the limit as the configurable attention matrix scalar goes oc, such that the compiled Transformers implement "hard attention" (Pérez et al., 2021). All weight values belong to a small of unique values, and therefore require only finite precision represent.
B.5.6 PROMPT EMBEDDINGS
The prompt token embeddings for prompt tokens P1, P2. PR, produced by zmap for given program & = 21, 22, .. 2|2| are specified as follows:
P1
bi
W1
P2
W1
(53)
PR.
R,
Wi W|u
where (wi,'.. (iw is finite-length weight vector that does not depend any resource bound, and the weights (bi, ,br)) encode the |z| bits of in Rg |z| weights as follows:
1.0,
<<=
A 24 =1
69
1.0,
-<=
A 2/ 0
(54)
|=|
where be chosen arbitrarily, these weights represent bits the program tape that, by construction, will never be read, because by definition the program halts after reading the final bit of and does not move the head for the unidirectional program tape any further. In the Transformer. this results in the attention head that "reads" the program tape never attending to these values. Therefore, arbitrarily choose 0.0.
B.5.7 RESOURCE BOUNDS DISCUSSION
Since the compiled weights are the same across all layers, the resource bound R. denoting the maximum number of Turing machine steps and therefore the maximum number of Transformer layers- does not affect the compilation. The Transformer requires R, + layers at inference time, as it executes the Turing machine's 's transition function once per layer, and then requires 2 additional layers to compute the final logit values described above. The registers of the initially blank work
30

---

Published as a conference paper at ICLR 2026
and output tapes also represented by the prompt tokens, and therefore the number of prompt tokens determines both the maximum program length and maximum number registers on the work and output tapes.
Notably, because only the number of prompt tokens grows with increasing space resource bound Rg, and not any of the other aspect of the Transformer, as this bound becomes larger increasing proportion of the Transformer's s overall weights are allocated to embeddings of prompt tokens, rather than, e.g. the weights of the MLP layer. This is quite different from how Transformer parameter counts are conventionally scaled. It's possible there are alternative ways of emulating a prefix Turing machine that would lead different scaling behavior, e.g. by effectively representing the program within the MLP layer, but we leave consideration of this to future work.
Future work could also consider separate resource bounds for the maximum number of program tape registers (bounding the model's capacity to represent increasingly complex functions) and the number of work tape registers (bounding the model's 's memory capacity during the forward pass).
B.6 PROOF OF THEOREM
Theorem (Theorem restated). There exists an asymptotically optimal family of two-part codes for Transformer encoders.
Proof. Our proof builds the construction of the function zmap, detailed in B.5, which generates Transformer parameters satisfying equation 51.
Let T T be universal prefix Turing machine. We can define family of two-part codes {UR) Re E N² that is asymptotically optimal with respect to T as follows.
The hypothesis space HUR is the Transformer parameter space specified by the codomain of zmap given 7 and R.
The mapping function mux is the mapping function described in B.5, where mug (h) con- sists of prepending R, prompt tokens and running Transformer forward pass with param- eters h.
We can trivially define the prior as aug (h) 2-1 if there exists E ΣT such that h = 2T, Rt 2), or 0 otherwise. This prior therefore assigns non-zero probability only to those specific Transformer parameters that correspond to valid Turing machine emulation.
Now, we must show that this family is asymptotically optimal with respect to T, meaning we must prove that for any resource bound Rt E N²2 and dataset (X, Y):
L tww.-art (Y UR
X)
(Y X). T.R
(55)
Using Lemma 1, we can express the codelength on the left as a minimum over functions:
LUn
L # two (Y X)
min feIm(mug)
(LT (f) - loga p(
(56)
The function description length, LFF, (f), the codelength of the shortest hypothesis that computes f. Given our prior, hypothesis h has finite codelength only if it is the output of zmap for some program z E ZT,R. Therefore, the minimization effectively over programs z:
min LE NEHUR mu (h)=f
log, aUR (h)
min zEZr, mun (2ma)((.
log, 2 [=]
min seZr, $3=1" |z|
The final step follows from equation 51, and this final expression is precisely the definition of the resource-bounded Kolmogorov complexity of with respect T, i.e., Kr) So, we have shown that T (f) Kr. (J).
31

---

Published as a conference paper at ICLR 2026
Substituting this equality back into the expression for the total codelength, we find:
LUR
two-part (Y X) min
(Kr,n(f) log2 p(Y(x;))
fmim(me
T, C (Y X).
This step holds because the image of our constructed mapping function includes all functions com- putable by T within bounds n.
Since we have shown that the condition for being an asymptotically optimal family is satisfied.
L x-to--part (Y | X) is not just bounded by, but equal to TTR
Caro (Y X))
B.7 RELATIONS BETWEEN CODELENGTHS
In this section establish upper and lower bounds the minimums of various classes of codes. To this end, we review Bayesian codes, and establish a universal lower bound on the minimums of Bayesian and variational codes. These results are used prove Proposition 3.
B.7.1 BAYESIAN CODES
Under a Bayesian code, labels are encoded according to their likelihood under a Bayesian posterior distribution, defined below. A Bayesian code M, just like a two-part code, is specified by a hypoth- esis space Has mapping ma from hypothesis to model functions, and lower semicomputable semimeasure (i.e., prior) axx (h).
The Bayesian codelength is defined with respect to the Bayesian marginal likelihood of the data:
L * bayes
(Y) X) loga PM
marginal
(Y
X)
(57)
M
loga
Σ p(Y (x:m((h)) car(h))
(58)
While the summation over all hypotheses is typically intractable, the Bayesian codelength serves as a theoretical lower bound and motivation for variational codes.
B.7.2 UNIVERSAL BAYESIAN CODES
Analogously two-part codes, we can show that there exists an equivalence class of universal Bayesian codes.
Definition 7 (universal Bayesian code), A Bayesian code M is universal Bayesian code if and only if. for any other Bayesian code M and for all X, Y:
+ L b (Y (X) 2
L bayes (Y X).
(59)
M2
Lemma 3. There exists a universal Bayesian code.
Proof. Consider a Bayesian code U defined identically to the two-part code in the proof Propo- sition 1, with respect to universal prefix Turing machine T. We will show that U is universal Bayesian code.
Similarly Lemma 1, re- wertt the codelength for any Bayesian code M as functions rather than hypotheses.
model
baves
(Y X) -log2
Σ
p(Y X; (mmm((h) (h
(60)
M
hERx
- =-log, Σ
p(Y X: a (f).
(61)
fEim((m)
where:
Σ am (h)
(62)
heHM (
32

---

Published as a conference paper at ICLR 2026
or if such exists. Similarly to Lemma we have (f)) _ logg a (f), because a (f) is lower semicomputable semimeasure, as by definition (m(h is a lower semicomputable semimea- sure. Additionally, for our proposed universal code, the quantity of (f) recognizable as the algorithmic probability of f (Li & Vitányi, 2008), and we have K(f) = log2 (f). We have al- ready shown one side of this inequality above. The other side - logg ( K() holds because by definition af(A (f) includes 2 kr(f) as an element in the summation over non-negative elements. Combining these results, we have:
log, (f K(f) f - llgg (f).
(63)
Therefore, there exists positive constant CM that does not depend on such that for all f:
(f) 2 cM * a (f).
(64)
We need to show that the following holds for any other Bayesian code M:
T bayes (Y x) I bayes (Y) X).
(65)
We can re-write the left side as:
L # buyes (Y x) -
Σ
p(Y X: (x
(66)
FEF
- llgg Σ
p(Y X; [;J)eM (Z
(67)
JEF
- -log CM - log2
Σ FEF
plY 1x: (a:
(68)
x - logg -logz
Σ p(Y X:f)a FEF
(69)
This expression is the definition of L byye (Y X), and therefore we have demonstrated that U is universal Bayesian code.
bayes
Corollary 2. For any universal Bayesian code M:
Choyes (Y | X) = - -log
Σ JEF
K() p(Y X; -
L * bayes (Y X)
(70)
Proof. Let U be the universal Bayesian code constructed in the proof of Lemma 2. Its minimum codelength is equivalent to Chayes(Y [Y|X), shown by rewriting the sum over hypotheses as a sum over
functions and applying our previous result that K(F) = llog2 ofy (f).
L bayes (Y XX) = - -log2 Σ P(Y X: (f)
fEF
+ loga Σp(r P(Y X; K))
JEF
brayes (Y XX).
Now, let M be any other universal Bayesian code. By definition, L bayes (Y 1 L bayes (Y
directly follows that L bayes [Y Obayes Obbaye(Y (X)
B.7.3 UNIVERSAL BAYESIAN CODES AND UNIVERSAL TWO-PART CODES
Lemma 4.
The minimum of any universal Bayesian code is less than or equal to the minimum of any universal two-part code up to an additive term, i.e.:
Chayes (Y (x) Chwo-part (X)
(71)
33

---

Published as a conference paper at ICLR 2026
Proof. Recall the definitions of Chuyes and C
bayye (Y xX) = -log2
Σ
2
p(Y (x;f)
(72)
SEF
Ctwo-part (Y |X) = min K (f) SEF
log2 p(Y (X:f)
(73)
= - logg max 2
K() p(Y f).).
(74)
feJ
We can substitute these definitions into the inequality above, and then apply Ar 2 to both sides, which is monotonically decreasing, and therefore we also reverse the direction of the inequality:
22-K0pp(Y x; 2 max 2 K()) p(Y (x;)) JEF
(75)
feF
The inequality holds because the left-hand side is sum of nonnegative elements where one of the elements is the element from the right-hand side.
Note that per the above inequality, is also clear that C" | Cruyyes (Y) X) as more probability converges towards any single hypothesis.
X) will decrease towards
B.7.4 UNIVERSAL. BAYESIAN CODES AND KOLMOGOROV COMPLEXITY
How does Chhnees (Y X) relate to K(Y X)? Per the coding theorem, we know that K(Y Chayes (Y X). Establishing bound in the other direction is more challenging. We have defined the sets of two-part and Bayesian codes with respect a probabilistic model that makes independent predictions for each individual (xr, y) pair, while the definition of K(Y X) makes such proba- bilistic independence assumptions. However, KYY X)) and Cbayes (Y X) may often be roughly equal for large numbers of independent and identically distributed samples (Li & Vitányi, 2008, Section 5).
[X)
B.7.5 BAYESIAN CODES AND VARIATIONAL CODES
The variational codelength defined equation 9 has a direct relationship to the Bayesian codelength. The difference between the variational codelength and the ideal Bayesian codelength is given by the KL divergence between the variational posterior Bas ()) and the true Bayesian posterior:
LT X, Φ) = KL [B
|l PMr
posterior
(- Y, [X,
logg PM
marginal
(Y X)
(76)
where the Bayesian posterior is defined as:
PM postetior (h |X,))= P(Y Kim (l)) ars (h)
(77)
PM
marginal
(Y X)
and the Bayesian marginal likelihood is:
marginal
(Y [X) Σ P(Y X;mm(h)) ams
(78)
PM
BEMM
Minimizing the variational codelength I. X, Φ) with respect to & is equivalent to maximizing the Evidence Lower Bound (ELBO) from variational inference. This process drives the variational posterior (: d) closer to the true Bayesian posterior prosterior, X, Y) (by minimizing their KI. divergence), and consequently brings the variational codelength closer to the corresponding Bayesian codelength * bayes (Y X). The variational codelength can thus be seen as an efficiently computable surrogate or approximation for the ideal Bayesian codelength.
B.7.6 PROOF OF PROPOSITION
Proposition (Proposition 3 restated). For any quasi-universal variational code M,
K(Y X) Chayes( (Y () & "Y |
x)
hwo-part (Y) X),
(79)
where buayes (Y X) - log, E,er 2 K() KY) X:
34

---

Published as a conference paper at ICLR 2026
Proof. This theorem combines several of our previous results.
The relationship Ly var (Y () C Cawo-part)) (Y X) follows directly from the definition of a quasi-
universal variational code.
The relationship Chayes X) I I.*. (Y X) follows from a two-step argument. First, as estab-
lished by the non-negativity of the KL divergence term in equation 76 (discussed in Section B.7.5), any variational codelength is lower-bounded by its corresponding Bayesian codelength:
h.hyes (Y X) - MM
N (Y X
Second, by the existence of universal Bayesian code (Lemmaa 3), any specific Bayesian code is lower-bounded by the universal bound:
Cbayes (Y
X
S L MM
hayeey (Y X).
Combining these two incqualities yields the desired result, with discussion relating Chhyee( |X) and Cuwo part (Y X) in B.7.3.
Finally, the relationship KY XX) 3 Chayes (X) follows from the discussion in B.7.4.
B.8 ANALYSIS OF VARIATIONAL CODES
This section provides additional definitions and analysis related to variational codes.
B.8.1 EQUIVALENCE BETWEEN TWO-PART AND VARIATIONAL CODES
Here show that variational codes can be seen as generalization of two-part codes, with equiva- lence when we restrict the posterior hypothesis space to distributions that assign all probability to single hypothesis.
Recall that for a two-part code we optimize the codelength over the hypothesis space directly. In variational code, we optimize the codelength over a set of posterior parameters, which define a distribution over the hypothesis space. The codes are equivalent if we can establish bijective mapping between the hypothesis space of a two-part code and the posterior parameter space of variational code, such that for these corresponding values the codelengths are the same and the model functions are the same. We formalize this notion in the following definition.
Definition 8. (equivalency for two-part and variational codes) A variational code Mar and two- part code Mwoo-part are equivalent if there exists a bijective mapping : Mgooo - $ Myarr such that if u(h) then yaar LM (X:)) L (Y X; and Pat xi() ply
I, Momappr (h)).
Lemma 5. For every two-part code M part, there exists an equivalent variational code M
Proof. Given Wow-pp can define var as:
+ -r H.yar H. yraagnn
(80)
MM magoop
(81)
0. (h) = a Aimosn (h)
(82)
8(h; Φ) [ h],
(83)
where [P] denotes the Iverson bracket, i.c. if is true and otherwise.
In other words, the posterior hypothesis space is restricted to distributions that assign all probability to single hypothesis. The bijective mapping u is the identity function, as T agwe = Hagoopa.
The codelength of our variational code with u(h) h is defined as:
- (Y (X))) = En (:sh) |- log, a' (h) + log, - (h; h) - logg p(Y | XX; my (h))
log2 O Su san (h) (h h]] log P(Y X; (M
log, Mpsoppo (h))
log, p(Y Y X; poo (h))
J. Miingan
x|X;h).
35

---

Published as a conference paper at ICLR 2026
The conditional distribution for our variational code with @ u(h) h is given
PM (Y) X; o) Bn- p(Y X; mm
p(Y X; Mygerpa (h))-
Thus Mtwo part and M are equivalent given the bijective mapping u.
B.8.2 ASYMPTOTICALLY OPTIMAL VARIATIONAL CODES
Asymptotically optimal variational codes are defined in the same way as asymptotically optimal two-part codes.
Definition 9. (asymptotically optimal variational code) family of variational codes
(Mr R N2) is asymptotically optimal with respect to universal prefix Turing machine T if for all and for all X,Y:
L vor Ma (Y X) S
min Kr,K(r - log2 p(Y Ix;)),
(84)
JEF
where Kr,n denotes resource-bounded Kolmogorov complexity.
The codelength L var (Y M bounds R increase.
X) monotonically decreases to be Cown-pant(Y (Y] X) as the resource
B.8.3 PROOF OF PROPOSITION
Proposition (Proposition 4 restated). There exists asymptotically optimal family of variational codes for Transformer encoders.
Proof. This trivially follows from Theorem 4, which establishes that there exists an asymptotically optimal family of two-part codes for Transformer encoders, and Lemma 5, which establishes that for every two-part code there exists equivalent variational code.
B.8.4 VARIATIONAL CODES WITH ADAPTIVE PRIORS
We extend the definition of variational code (Section 5) include an adaptive prior, termed an adaptive variational code.
Definition 10 (adaptive variational code). An adaptive variational code M consists of a hypothesis space H., a mapping mM HM - F from hypotheses to model functions, and a prior am (h) over HM, specified in Definition I. Additionally, an adaptive variational code specifies:
1. A prior hypothesis space Vi M and prior distribution over hypotheses, (rr 1b), parame- terized by E MM
2. A posterior hypothesis space 4 and posterior distribution over hypotheses, Bad (h: Φ), parameterized by ó E &
3. A description length measure L M for the prior parameters satisfying Kraft's inequality, which can be interpreted as implicitly specifying a hyperprior over the prior parameters.
Similar standard variational code, the conditional distribution over Y given X is therefore specified by the posterior parameters 4as. and defined by marginalizing over hypotheses:
PM (Y X; Φ) E P(Y X; m; (h))
(85)
Different from a standard variational code, the codelength for a variational code M then defindd with respect to both e and v as:
L
adaptive-var (Y X; th, Φ) 1% KL (+((=))) || (xr(:))] - loga Pas (Y XX;). M
(86)
The codelength accounts for the cost of transmitting the prior parameters, L (16). Alice can then
first send Bob these prior parameters at a cost of L (æb), and the remainder of the transmission then follows that of standard variational code, following the bits-back argument.
36

---

Published as a conference paper at ICLR 2026
We similarly denote the minimum of an adaptive variational code M as:
L aduapiie-var (Y XX
min
LM
udoptive-var (Y (x)
(87)
WEW o
The definition an asymptotically family of adaptive variational codes is directly analogous to the definition for standard variational and two-part codes.
Note that a two-part code could also include an adaptive prior, although we don't explicitly consider such codes in this paper.
B.9 ANALYSIS OF GAUSSIAN MIXTURE MODELS
This section provides additional analysis of variational codes constructed via Gaussian Mixture Models (GMMs).
B.9.1 PARAMETERIZATION OF GAUSSIAN MIXTURE MODELS
In formulating variational codes, we consider Gaussian Mixture Models (GMMs) with K compo- nents. We parameterize such models with parameters {(u,, Pk, Jkm where for the k-th component, Pa is the mean, is parameter controlling variance, and is a logit for the mixture weight. The probability density function given by:
GMM w) =
Σ Th No;
(88)
where the mixing coefficients, are computed via the softmax function applied to the logits wy to ensure they form a valid probability distribution (i.e., Σ. F 1):
T
and the variances, of are parameterized using the softplus function of to ensure they are strictly positive:
oe log(1 e.*).
(90)
key property of this parameterization is that as Ui > -0,, the corresponding variance of 0. In this limit, the k-th Gaussian component, N(1; μkg of), converges to Dirac delta function, 8(x - nx). Consequently, this GMM formulation can approximate any discrete distribution over K points by treating it as limiting case of the mixture.
B.9.2 UNIMODAL VS. MULTIMODAL. PRIORS
This section provides simple, illustrative example of the benefits of multimodal GMM prior a unimodal Gaussian prior for encoding discrete information.
Consider setting where Alice wants send Bob a single random bit 6 {0, 13. Let assume we have a simple variational code consisting of a prior and posterior over a single scalar parameter w. Further, assume Bob "decodes" the bit based on the sign of Assume the posterior B is parameterized as Gaussian, ((w; μr, o²) (ww fr, o²) with mean f and variance o². We can consider two different parameterizations of the prior a, as a single unimodal Gaussian, or as multimodal mixture of 2 Gaussians, which we show enables much more efficient transmission cost. Under a variational code, Alice selects the parameters of the posterior (μ and o²) that minimize the cost of the transmission, which is related to the KL divergence between the prior and posterior distributions (KL[ μ1 o²) || a<w=)) and the probability that the can be correctly decoded (E (2) [sgn(w) b))
Figure/ visualizes posterior distributions for transmitting bits 0 or 1, along with a unimodal Gaus- sian prior (left) and multimodal GMM prior (right). Transmission is significantly more efficient with a GMM prior, highlighting why such a prior is critical for constructing our family asymptot- ically optimal variational codes. We provide
detailed analysis of each case below.
37

---

Published as a conference paper at ICLR 2026
Unimodal Prior
Multimodal Prior
Probability Density
0.50
0.50
0.25
0.25
-5
Prior
Posterior (b=0)
Posterior (b=1)
Figure 7: Visualization of posteriors for transmitting bit b under unimodal Gaussian prior multimodal GMM prior.
Unimodal (Gaussian) Prior First, consider the case where the prior is a single zero-mean unit Gaussian, aww) = (ww 0,1). The KL divergence (in nats) can be computed analytically:
KL [s(w; |l [[w]] = [02 + 122 log[o")]
(91)
To make the transmission reliable, the mean μ must sufficiently far from 0 and the variance o² must be sufficiently small. However, increasing μ > 0 or decreasing o² < 1 both increase the KL divergence. Therefore, we must tradeoff the KL divergence with the probability of correct decoding, with the Pareto frontier visualized in Figure 8. Reaching probability of correct decoding close to requires a KL of > bits.
Efficiency of Encoding a Bit
Unimodal Prior
Multimodal Prior
3
KL (bits)
2
1
8.5
0.6
0.7
0.8
0.9
1.0
Probability of Correct Decoding
Figure 8: With unimodal prior, must tradeoff the KL divergence of the posterior against the expectation that the sign of the sampled parameter matches the sign of given With a multimodal prior, we can optimally encode the bit.
Multimodal (GMM) Prior Now, let the adaptive prior be two-component Gaussian Mixture Model (GMM) with equal weights, means -1 and 1, and variance 2² zs O.
a<w) 2 N(w: 1,03) + 2 Nw: 1,02)
To send bit = 1 or b = 0, Alice can choose posterior with mean 1 or -1, respectively, and variance 2 Consider the 1 case. Since δ² ~ 0. the probability of correct decoding is 1. Additionally, the probability of any value sampled from the posterior ((w; 1, 6²) according to the prior mixture component with mean -1 is negligible, the KI. divergence then simplifies to be the
38

---

Published as a conference paper at ICLR 2026
KL divergence between the posterior and the prior component
log2 (w:; 1,02)
xl(B(x;1,03)) || a(w))] = 1w-.(u:11,2))
a(w)
Nww 1,0
E Bw
log2 2 -WWw; 1, 62) [log2 2| = bit.
E 10
Thus, we can transmit the bit with an optimal KL cost of bit, with near certain probability of correct decoding, as shown Figure 8.
B.9.3 OPTIMAL MIXTURE PRIORS
In this section we discuss as previously discussed in Ullrich et al. (2017) and Nowlan & Hinton (1992). Specifically, we will derive the optimal GMM prior parameters for the following case:
how adaptive GMM priors enable efficient encoding of quantized weights,
We have a group of N weights with a shared, adaptive GMM prior with mixture com- ponents (B.9.1).
We want to optimize the KL divergence between this prior and a posterior over these weights.
The posterior for each weight approximates a delta function at particular value.
These posterior delta functions are all clustered small set of M s K unique values. Let {m,, M22 mm } denote these unique values, and let e; be the count of weights that have the value m,, such that E
M
N.
The optimal GMM prior (that minimizes KL divergence) a mixture of M components. where each component is Dirac delta function centered at one of the unique value m,, The remaining K M components should have a mixing weight of zero. Specifically, the optimal parameters, {(UR, uk, ux)) K for this prior are:
Means:
The mean of each active component is set to one of the unique weight values. For M,, the optimal mean is μ4 m4.
Variances: As the components converge to Dirac delta functions, their variances must ap- proach zero. Thus, the optimal softplus parameter is v; - -o, which implies of -
The mixing coefficient for each active component should be equal to the empirical frequency of the corresponding unique value in the data. For i 1. 1..... M, we select such that the optimal mixing coefficient is स. N for the remaining K .M components are zero.
Mixing coefficients:
G The mixing coefficients
By using a GMM with delta function components, the prior perfectly matches the empirical distri- bution of the weights, leading to the minimum KL divergence. In this idealized setting, the total KL divergence is equivalent to the Shannon entropy of the empirical distribution of the weights, scaled by the total number of weights N. Let p. c//N be the empirical frequency of the unique weight value m,. The KL divergence for single weight whose posterior is delta function at simplifies to the negative log- ligliiilloood under the prior, log, a(m.). Since the optimal prior sets (mm,) Ps, the cost for this single weight is - log, pi. Summing this cost over all N weights in group, we get the total KL divergence:
M ca(-log, po) = Σ Np:(- (oo(-oog,,y log, N
M
M pt log, = N H()
(-Σ 1=1
where (p) is the Shannon entropy the empirical distribution = (pI.... PM)). This is the the- oretical minimum number of bits required to encode the specific weight values given their empirical frequencies.
This highlights close connection between the dynamic quantization method of Han et al. (2016), as employed by Lotfi et al. (2022; 2024), and this special case of optimizing a variational objective with adaptive GMM prior.
39

---

Published as a conference paper at ICLR 2026
B.10 PROOF OF THEOREM 2
Theorem (Theorem restated). There exists an asymptotically optimal family of adaptive varia- tional codes for Transformer encoders where the adaptive prior and posterior distributions are both specified by products of independent GMMs.
Proof. We construct a family of adaptive variational codes {MR R E ] and show it is asymp- totically optimal with respect to a universal prefix Turing machine T T.
Construction of the code family For each resource bound R E N2, the code MR is defined as follows. The hypothesis space HMg consists of the weights for a Transformer encoder architecture that uses layerwise weight sharing, as specified by the construction of zmap(T, R, z) in Section B.5. For given h E Hann let h, E h denote the specific Transformer weight value for some index i, assuming some arbitrary enumeration of the weights. The mapping function mmM,, is also defined in that section, prepending Rg prompt tokens to the input before the Transformer forward pass.
The prior and posterior hypotheses spaces, V Mr and 4M are both parameterized by sets of inde- pendent Gaussian mixture models (GMMs), as described in Section B.9.1. For posterior parameters & Ma let d; denote the parameters of GMM with index i. Similarly, for adaptive prior pa- rameters to E V Mg. let Vgroup(() denote the parameters of GMM with index group(i), where group: N N is function defining grouping of Transformer weights that share the same prior GMM.
The posterior distribution is defined as:
SaR (h; Φ)
II GMM(h; 0z).
(92)
The adaptive prior distribution is similarly defined as:
M. (h; 1b) II GMM(h;; (Parou((t))
(93)
Recall that the number of weights in the Transformer constructed by zmap is finite, except for the number of prompt token embeddings, where the number of rows (i.e. number of prompt tokens) grows with the space resource bound R,, and therefore our asymptotic analysis largely focuses on these weights (see B.5.6).
For the prompt token embeddings, a separate GMM prior is shared across each feature column. For all weights other than the prompt token embeddings, this grouping does not formally affect our results, e.g. we can simply share a single GMM prior across each matrix or bias vector in the Transformer.
We require that the prior and posterior GMMs corresponding to the weights of the prompt embed- ding table have at least 2 components. We will show that the other GMMs only formally require single component for the desired asymptotic bounds to hold, although prior with more components can lead to a more efficient code in practice, as discussed below.
Finally, we construct the encoding of the prior parameters, M as follows. Our constructed group- ing of weights sharing the same prior ensures that the total number of prior parameters in Ma is small constant that does not depend on the resource bound R. This is because the number of param- eters generated by zmap constant with respect to R, other than the number of rows in the prompt token embedding table, and single prior for each column is shared across every row of the prompt embedding table. Assuming the prior parameters can be encoded with some finite precision, we select some uniform encoding for the prior parameters, L I which assigns non-zero probability to any specific set of prior parameters we construct below, such that they can be transmitted in cy bits, which does not depend R.
Proof of asymptotic optimality To prove that the family {Mn R E N2) } is asymptotically optimal, we must show that for any resource bound E N2 and any dataset X,Y:
I * adapiieevarr (Y
MR
X)
Cawo-part X).
Tr.
(94)
40

---

Published as a conference paper at ICLR 2026
Recall that the minimum codelength is achieved by minimizing over all possible prior and posterior parameters,
L * adaapiiveeeaa var
MR
(Y |x) =
min
L MR
adaptive var (Y 12
NEW MR ME
where,
T MR
X; d0 6) = LM (1b) + KL. BaSK (; aM (s+)) logz PArR (Y x; adaatiiv- (Y
= = + KI. |MM (:5 aoMa (x - log2 PMR (Y X; ())
We will show that for any resource bound R E N² and program & E ZT,R. we can construct a specific set of prior parameters nn - not dependent on program 2 - and posterior parameters &R such that the resulting variational codelength satisfies the following bound with respect the function f computed by prefix Turing machine with program 2. That is, we will show that there exist v. E Vain and & R E DMn such that:
idpptivo-var (Y X, ( S + |2| + MR
logz P(Y X;
(95)
where eT and 6g are constants that do not depend on X, Y, 2, or We address the data like- lihood and KI. divergence terms individually next. Then we will show that this condition implies asymptotic optimality.
Let ht zmap(T, RR, z) be the set of weights generated by the ALTA compiler to emulate the Turing machine with program 2.
Data likelihood For given program = E 2T, Rt construct posterior parameters such that any weights sampled from the posterior distribution compute fī, i.e. any sampled weights compute the same function as the weights R,2
To accomplish this, partition the Transformer weights into two disjoint subsets, which will denote with respect a set of indexes N. For the first subset, consisting of weights with indexes E I, we can set the parameters the corresponding posterior GMM o; to approximate Dirac delta function at the desired weight value, A. This is possible because GMM component's variance can approach zero (see B.9.1). The second subset, consisting of weights with indexes & I, consists of only those weights in the first column of the prompt token embedding table (see B.5.6) corresponding to weights encoding the values of bits on the program tape after 2, i.e. rows | + Rg. By construction, these parameters tape, so their value does not affect the function being computed by the Transformer. We therefore allow these weights to take on "random" value by setting the corresponding posterior parameters to approximate the Rademacher distribution. This construction allows these bits to be transmitted "for free", as we will show the next section. Formally, the posterior distribution specified by the posterior parameters o R?, is therefore:
never "read" by the attention head scanning the program
GMM(W; R.e
8(w h R.2 j0ww + 1) [ , L
,iEZ I
(96)
Therefore, given the posterior parameters R.2, the negative log likelihood of the data is equivalent that under two-part code with weights / R.2.
log, PMR (Y R..)
En~ ( Rx)) | log, p (h))
(97)
-llog, P(Y i; Ri²)
(98)
log2 P(Y (i)
(99)
KL divergence We now show that we can select prior parameters dtth MMR such that the KL divergence term is bounded by |æ| cr, where er is constant depending only on T' but not on 2 or R. Because the prior and posterior are parameterized by independent GMMs, the overall KL. computation factors across the individual weights of the Transformer:
KL (l.) R..) aaa: ")] = Σ KL [(::0[ (l.2)) |l al3 a (et
(100)
41

---

Published as a conference paper at ICLR 2026
We consider the weights in the prompt embedding table first, and then discuss the remaining weights. Recall that a GMM prior is shared for each column this table. The weights in the first column encodes the contents of the program tape. We set the prior for this first column of the program emhedding table to approximate the Rademacher distribution, such that the prior and posterior dis- tribution are the same for the weights corresponding the R. - ||| rows in the table after row |z|- The KL divergence between two equal distributions is O. For the weights in the first |ж] rows, the posterior is either a delta function or -1. In either case, the KL divergence is bit (see B.9.2, which also highlights the importance of multimodal prior in our construction). For the remain- ing columns of the prompt embedding table, each row has the same value, and the posterior for all rows within column approximates a delta function at this value. Therefore, we can set the prior to for these weights. Therefore, the overall KI.
be equal to the posterior, and the KL divergence divergence for the prompt embedding table is |z|-
For the finite set of weights outside of the prompt embedding table, the posterior distribution for each weight approximates delta function. The weights generated by zmap contain relatively small set unique values determined by T. We can choose any prior that assigns non-zero probability to these specific weight values. Summing over all fixed weights gives total constant cost er that depends on T but not on 2 or R. A single mixture component is formally sufficient, since it can have sufficiently large variance to assign non-zero probability each unique value in the corresponding weight matrix. However, since the weight values generated by zmap have values drawn from a finite set determined by T. with sufficient number of components, we can construct the shared GMM priors to be mixtures of delta functions centered at these values, as described in B.9.3, and therefore or can be relatively small.
Combining these parts, the total KL divergence is cr.
Conclusion We have shown that for any program : E Zr,n and resource bound R E N?, there exists a choice of prior and posterior parameters (w² RR.2) such that:
L vda (Y X, R. R.2) S logg PY (x cr MR
(101)
The minimum codelength for the family MR is found by minimizing over all (v), Φ). so it must be less than or equal to the codelength for this specific choice, minimized over all programs
L
Mn
* adaptive-var
(Y (X)
min
L adaptive-var
MR
(Y ()
NEW MR P
min
L mlaptive
MR
(Y & of 2)2)
=6 =E2T,R
< min (cp |z| CT log, p(Y (x;f))
=E R
< min (|æ1 log p(Y Y (f))
zEZr,R
This last expression is equal to the definition of Cewo-pant (Y X):
Clwe-part (Y
X) = min
(Kr,n(f) - loga pY (;f)) /EF
min
(|2) log, p(Y X: ff)).
=c =E2T,
Therefore our construction satisfies the condition for asymptotically optimal family of codes.
B.11 ANALYSIS OF ALTERNATIVE TWO-PART CODES
Here we provide additional details and discussion related the bounds in Table 2 introduced in Section 6.2. The first row of the table shows description length bound of |z| + log R., leading to an overall codelength bound:
I (Y X)
two-part (Y X) log, R.- CTR
(102)
42

---

Published as a conference paper at ICLR 2026
First let us detail the construction of this family of two-part codes in contrast to the construction of the variational code detailed in B.10. One of the key challenges addressed by the adaptive varia- tional code is that we wanted to transmit the R. prefix token embeddings representing the program tape contents in |=| bits in order to satisfy the conditions of asymptotic optimality. In order for the "unused" capacity to be transmitted "for free", our proposal required a multimodal GMM posterior that could be set equal to the prior for the R. - |z| "unused" weights. However, implementing and optimizing a multimodal posterior can be challenging. Instead, Alice can adaptively determine the optimal prefix length by selecting |a| E {1.
Rs ), e.g. by sweeping over prefix length as a hyper- parameter, using structured dropout, or using some other approach. Alice can then communicate |a| to Bob in loga R, bits, assuming naive uniform prior over the integers {1,... R. } for encoding |z|. Then, Alice can simply communicate z in |a| bits assuming a Rademacher prior over the | weights, as in our previous construction in 1010. As in our previous construction, this can be gener- alized by using an adaptive GMM prior. Alternatively, such a code could potentially be constructed using the quantization method of Han et al. (2016), which has also been employed by Lotfi et al. (2022; 2024). Alternatively, we could restrict the prefix embeddings to some fixed vocabulary, akin to discrete prompt optimization. Most directly, in the special case where the vocabulary size is 2, we reach the same bound.
Next discuss the bounds in Table 2 resulting from ablating aspects of this recipe. First, if do not use any form of quantization, and instead use a fixed prior, such as the unimodal Gaussian prior implicit in methods such as weight decay, or uniform prior implicit in standard MLE objectives, then each weight encoding a bit of requires more than a single bit to encode. Therefore, the program length term in the bound changes from |a| ([z)), where the multiplicative factor is > 1. Second, if we do not adaptively select the prefix length, then we must encode the entire prefix embedding table, which contains Rg rows, regardless of the length of the program encodes. Therefore, the bound degrades further to ORR)). where R, > |^| as by definition Rt determines the maximum program length that can be represented. Finally, if we do not use layerwise weight sharing, then our bound simply becomes a function of the number of parameters in the Transformer. As Re specifies the number of layers, we must encode (Re) weights, in addition to the O(R,) weights in the prefix embedding table. Note that the bounds we have derived assume we using the Transformer family and specification of zmap discussed in Section 4.1. Alternative constructions could potentially lead to different bounds.
Overall, a weaker bound on the model description length leads to a weaker bound on the minimum of the overall codelength. Therefore, optimizing such an objective may lead to sub-optimal compres- sion, and-from an MDL gerspective-suu-opttinn
model selection. Regardless, the |=| + log R, bound is close to the theoretically optimal bound of |a|. While pre-trained Transformer decoders are a different setting than the one we have studied here, if our results could be extended to that setting would provide a strong asymptotic bound for the compression achievable via prompt optimization methods, complementing the positive empirical results from Akinwande et al. (2024).
B. SCALING TRANSFORMER DIMENSIONALITY
Here we provide additional details the alternative Transformer family discussed in Section 6.3. In contrast to the Transformer family detailed in B.5, the program tape contents are implicitly encoded in the MLP parameters. In this construction, we still require prepending R, "padding" tokens the input in order to scale the context window so that the Transformer can represent Turing machine tapes of size Rg. However, the program is encoded in the MLP layer, and we do not require prefix embedding table. An ALTA program for populating the program tape contents based on a program encoded in the MLP weights is shown in Figure 9. The overall construction first itera- tively populates the program tape contents at sequential Transformer positions, and then the Turing machine emulation continues as in our previous construction. Therefore, this construction requires R2 + R2 + layers.
The MLP matrices generated by the ALTA program in Figure 9 require O(Ix(²) parameters, and have rank O[Iz)). where |a| is the program length. While the existence of a mapping analogous to zmap for this Transformer family indicates that asymptotically optimal description length objectives exist, implementing such prior introduces complex dependencies across the parameters of the MLP. Given the rank requirements on the MLP matrices under this construction, rank factorization would not be an effective means of compression, but it would be interesting for future work to consider
43

---

Published as a conference paper at ICLR 2026
from alta import builden_builder as
def spec Machinespec) >> pb. ob.Frogrammpec: "*"tuurns ALTA program spec for populating program tape,
variables
"done": (2),
"is_start"; pb. in..tt___aaa inim_bf-
START),
"head": pb.input_varre (2, fn=landaaa START),
"symbol": pb. -a.. "prder" pb.var (Len(pprorra__input]]
attention_ I "head_left"; pb. wwwellatiee""haule -1),
def ffr_fn (x):
if x x["progran Indexx) len (program
x["done"] =
return
if x x["head]]
x x["aymbol"] = int (program_input [=(ppoorram_ndex""
x x["head"] =
if not x xi"is_start"]
xeftt)
x x["head"]
("program_index 3["orogran_irdex*
return pb. lb..progran_spec
ffn_ variables-variables, heads-attenttonnheall heads, citpptt_nam="symbol input_range=2, position_range=Nons
Figure 9: ALTA program specification for populating a program tape given program encoded in the MLP layer.
alternative constructions practical methods for matrix compression that could yield asymptotic bounds approaching the theoretical ideal.
C ADDITIONAL EXPERIMENTAL RESULTS AND DETAILS
Here provide additional details and results for the Transformer and MLP experiments discussed in Section 6.
C.I TRANSFORMER EXPERIMENTS
Parity task details We follow the setting of Shaw et al. (2024). The train consists of examples with lengths ranging from I to 20. The train set includes 100, 000 examples, with roughly an equal number of examples per number ones. We evaluate out-of-distribution (OOD) accuracy on test set with lengths ranging from 21 to 40.
ALTA program for parity The ALTA program for parity that we use our manual initialization is based on the sequential algorithm with relative position representations presented in Shaw et al. (2024). This algorithm computes parity by iterating through each position (one per layer), flipping a running parity bit every time left-to-right right-to-left, to accommodate that our model's classification decision depends on the SEP token at the beginning of the input sequence (see below).
encountered. We simply reverse the direction of iteration from
Architecture and ALTA weight conversion One implementation challenge that our experi- ments require trainable Transformer that is compatible with AL.TA-compiled weights. The ref-
44

---

Published as a conference paper at ICLR 2026
erence ALTA Transformer implementation in numpy is not trainable (Shaw et al., 2024). To ac- complish this, we implement a trainable version in Jax (Bradbury et al., 2018), following the same parameterization expected by the ALTA compiler. This parameterization uses relative position rep- resentations (Shaw et al., 2018) following the parameterization of T5 (Raffel et al., 2020), which uses single scalar bias term for relative positions within some window. It also uses alternative parameterization for the attention head output transformations, as proposed by Elhage et al. (2021), to simplify compilation; however, this alternative attention output parameterization is shown to be equivalent to that of the original Transformer. We select the logits for the SEP token as the output of the model, as our experiments focus on classification tasks.
A more significant challenge is that ALTA-compiln weights are not designed to be used with layer normalization (Ba et al., 2016). As the sequential algorithm for parity requires at least as many layers as bits in the longest input sequence, and our test set contains sequences up to length 40, we require a relatively deep Transformer, using 42 layers in our experiments. that while shallow Transformer could converge without layer normalization, training a Transformer with 2 40 layers was not feasible on the parity task without some form of normalization. We also evaluated using tanh normalization, as alternative to layer normalization, proposed by Zhu et al. (2025), which we found to perform at least as well as layer normalization in our experiments, with without using the variant with dynamic scalar. We therefore use tanh normalization, and adapted the ALTA compiler to generate weights compatible with this form of normalization.
our initial experiments we found
This required few changes the ALTA compiler. However, our parity program only requires categorical variables, the changes are relatively straightforward. First, we changed how categorical variables are represented in the residual stream. In the original ALTA compiler, these are represented as "one-hot" vectors, i.e. a sequence of Os and 1s. Instead, we represent categorical variables as "signed one-hot" vectors, i.e, a sequence of -1s and 1s. with the position of the still representing the value of the variable. This change only requires minor modifications to the compiled embedding and MI.P parameters. We additionally scale the compiled parameters by configurable scalars > to ensure the outputs of every sub-layer sufficiently saturate the tanh function. This also makes the compiled parameters more robust to noise. We zero-pad pad the ALTA -enerreed weights up to the dimensions specified by the given hyperparameters. Finally, as are using only categorical variables, we can use the more standard ReLU activation in the MLP layer, as opposed to the clipped ReLU activation required to handle numerical variables in the original ALTA compiler.
We can then convert from the scalar weights produced by the ALTA compiler to posterior distribu- tions used by our experiments with variational codes by setting the mean of the posterior distribution to the scalar weight and setting the variance to be a small, configurable scalar (e.g. V = - -00). As ALTAA-gnerrted weights contain few unique values, can analytical determine the optimal pa- rameters for the adaptive prior (B.9.3).
We otherwise use a "tiny" Transformer encoder, which was previously shown be sufficient fit the parity task (Shaw et al., 2024), with 2 attention heads, 128 model dimensions, and 512 hidden MLP dimensions. We prepend 20 prompt tokens to the model input.
Relation to asymptotic bounds The experiment setting, using relatively small model on sim- ple synthetic task, is potentially not well aligned with where the asymptotic guarantees from our theory are most likely to apply, which is in the limit model size and dataset complexity increase. Regardless, this experiment setting is a useful initial investigation of the proposed variational code. Relatedly, the ALTA program for parity does not emulate a Turing machine; rather it represents the algorithm within the weights of the MLP and attention sub-layers and leaves the prompt tokens effectively unused. However, this is not entirely at odds with our theory; as discussed in 4.2, the min- imizer of asymptotically optimal code may be quite different from the Turing machine emulation used to prove the asymptotic bound, especially under finite resource constraints.
Model training We use Monte-Carlo sampling to estimate the expected data likelihood in the adaptive variational codelength objective during training. Each gradient step is computed over 2 MC weight samples shared across a minibatch of 128 examples, for a total of 256 forward passes of the model (computed in parallel) per step. Prior work has commonly shared single MC weight sample across a minibatch. In our initial experiments, we did not find significant improvements from increasing beyond 2 MC weight samples per minibatch. For the posteriors corresponding to
45

---

Published as a conference paper at ICLR 2026
weights in the prompt token embeddings table, we use GMM posterior with 2 components, and use Gumbel-Softnee Softmax (Jang et al., 2017; Maddison et al., 2017) sampling with a temperature of 0.1. For all other posteriors, we use single Gaussian, and use the standard Gaussian reparameterization trick (Kingma& & Welling, 2014). We did not implement the local reparameterization trick of Kingma et al. (2015) for reducing variance, although this could be useful for future work.
Following Blundell et al. (2015), we also use MC samples to estimate KL divergence, as there is no closed form expression for the KL divergence of GMMs with multiple components. Specifically, we use 100 MC samples for estimating KL. For sampling from posterior distributions consisting of mixtures with more than one component, we use the Frraight-Througe (ST) Gumbel-Softman estimator (Jang et al., 2017), as soft estimates can be problematic and lead to negative KL estimates. For example, if the components of the true posterior distribution have relatively low variance, then samples from the Gumbel-Softman distribution with sufficiently large temperature can actually have higher probability under a higher-variance prior distribution than under prior matching the posterior.
We use the Adam optimizer (Kingma & Ba, 2014), with a learning rate of 10-3, 1000 warmup steps, and 50, 000 total steps with exponential decay of the learning rate. We determined some hyperparameters such as learning rate on an in-distribution validation set.
As we train the model on minibatches consisting of 128 samples from the 100, 000 training amples, we need to scale the coefficient of the KL term in the loss to accommodate that the data likelihood estimate is over small sample, 10-3, of the full dataset. Therefore, term in the loss by a coefficient of 10-3, which we found to produce the lowest total codelength. Sweeping the KL coefficient produces tradeoff between the data likelihood and the KL divergence. as observed in Table 4 for the MLP experiments.
scale the KL
Random initialization For the MLE baseline experiment, we initialize the weight matrices using the standard variant of normal random initialization proposed by He et al. (2015), as our network uses ReLU activations. Bias vectors are initialized to zeros. For the experiments with random initialization and the variational objective, there are many possibilities for initializing the parameters of the prior and posterior GMMs, and we did not explore this space exhaustively. However, we did find in our initial experiments that it was necessary initialize the posterior distributions with relatively low variance in order for the model to converge towards a solution that fits the data. Therefore, for the means of the posterior distributions, we sample random weight values following the same method the MLE experiments, set these sampled weights as the GMM means, and then set the GMM variance parameter v (i.e. the variance prior to the softplus function) to be -10. We initialize the prior parameters similarly. but set the initial variance parameter y to be 1 to avoid instability in KL estimates at initialization. We set all mixing weights for the GMMs to be initially equal. Future work could explore alternative initializations.
Optimizer Comparison We evaluated SGD in comparison to Adam the optimizer for Trans- formers with the variational objective for the parity task, following the setting reported in Section 6.
Table 3: Comparison of Adam and SGD for optimizing variational objective.
Optimizer
Train NLL (bits)
KL (bits)
OOD Accuracy
Adam
2.36 x 10²
2.81 x 10
60.4%
SGD
1.58 x 10"
2.44 x 10"
49.6%
Adam and SGD exhibit different optimization behavior, and a different trade-off between optimizing the model cost (KL divergence) and data cost (negative log likelihood). Both methods fail to find a codelength comparable to that of the manual initialization. SGD more severely underfits the data, leading to poor generalization. This highlights the sensitivity of optimizing the variational objective to the specific optimization procedure. Future work could more fully explore alternative hyperpa- rameters, learning rate and KL coefficient schedules, or alternative families of optimizers, such as approximate second-order methods, e.g., K-FAC (Martens & Grosse, 2015).
46

---

Published as a conference paper at ICLR 2026
Manual Solution
Leamndd Solution
10
10P
10-4
10
10
10
10-4
-10
-5
5
10
15
20
-10
5
10 15
Aggregated
Component
Figure 10: Manually specified vs. learned distributions for MLP trained with a variational objective on the identity task with an adaptive GMM prior. The aggregated posterior shown in the figure is an equally-weighted mixture of the individual Gaussian posteriors for each MLP weight.
C.2 MLP EXPERIMENTS
Here we provide additional details on the MLP experiments discussed in Section 6. To under- stand why our Transformer models underfit the proposed objective when randomly initialized (as evidenced by the significantly lower loss achieved by ALTA-initialized models), we study the sim- plified setting of 2-layer MLP. Specifically, we study the task of learning an identity function over a vector of binary values. The model MLP with 4 input dimensions, 16 hidden dimensions, and 4 output dimensions, which makes 4 independent binary classifications. We again compare random initialization with initializing the model with manually chosen weights that the data and have low complexity according to the proposed objective, by selecting weights inspired by how the ALTA compiler generates MI.P layers.
Table 4: MLP performance on identity task.
Objective
Init.
KL Coef.
KL (bits)
Train NLL (bits)
Codelength (bits)
Accuracy
MI.E Baseline
Random
8.82
100%
Variational
Random
1.0
2.87
2.64
10a
2.64
10a
54%
10
3.19
10a
1.90
10a
1.93
10a
63%
10
2.24
10a
1.12
102
3.37
10
100%
10 3
2.88
10a
5.39
10a
3.42
102
100%
10-1
2.98
x 10a
5.09 x 10
3.49
102
100%
Variational
Manual
10-1
9.87
10a
0.0
9.87 10a
100%
The results shown in Table 4, and show similar trends the Transformer experiments. We that when starting from random initialization, the optimization process fails to find loss compa- rable to that achieved via manual initialization, indicating poor optimization of the proposed objec- tive. To understand why the randomly initialized models underfit, we can inspect the properties of the learned prior and posterior distributions compared to those from manual initialization. Notably, the prior distribution appears to converge to unimodal distribution, visualized in Figure 10, in contrast to the multimodal prior the manual solution, with lower-variance components.
Task and network Our network is a 2 layer MI.P with 4 inputs dimensions and 16 hidden dimen- sions, that computes the function:
f(x; 8) W ReLU(W" (x) + +b) + 62)
(103)
with parameters 0 = (W1 bA 12).
Our goal to learn the identity function such that f(x; zs x for any binary vector x E 10,1
Posterior and prior distributions We parameterize the posterior distribution with independent Gaussian corresponding to each weight the MLP. We use a single adaptive GMM prior with components shared across all weights.
47

---

Published as a conference paper at ICLR 2026
Manual solution A relatively simple "manual" solution to the identity task can be constructed by choosing some scalar weights follows:
> (we choose = 20 in our experiments) and defining the network
A
0
07 ... 0
2² = (W))T=
0
b'
b²
=
Training details The negative log-likelihood of given with respect to 0 follows the standard binary cross-entropy loss:
4
- log, ply 0)
Σ
yi logo - (1 y:) log, f(x; 0):)
(104)
We train the MLP with variational objective. We specify posterior and prior distributions over o as specified above, minimizing the variational objective consisting of the sum of the KI. divergence between posterior and prior distributions, and the expected binary cross entropy loss with respect to sampling weights from the posterior distribution. We over-sample the space of 24 possible binary vectors of length 4 create minibatches for training of 128 examples.
Sampling, initialization, and training details are similar to the Transformer setting detailed above, except training only required 000 steps. We show sweep over different KL coefficients in Ta- ble 4.
D EXTENDED RELATED WORK
Here offer extended discussion of related work previously summarized in Section 7.
D.1 THEORETICAL FOUNDATIONS
Our work is closely related to the theoretical notion of universal induction (Solomonoff, 1964; Hut- ter, 2000; Lattimore & Hutter, 2013; Achille et al., 2021) and related resource-bounded vari- ants (Levin, 1973; Nakkiran, 2021). Previous work has developed theoretical frameworks applying these notions to density estimation (Barron, 1985; Barron & Cover, 1991), sequential decision the- ory (Hutter, 2005), and kemnel methods (Hamzi al., 2024). For neural networks, Schmidhuber (1997) introduced probabilistic search algorithm for discovering neural networks with low Kol- mogorov complexity. However, none of these theoretical frameworks directly lead to practical and scalable training objectives for neural networks.
D.2 VARIATIONAL INFERENCE
Variational inference proposed regularizer to improve generalization (Hinton & Van Camp, 1993), under the "bits back" argument, which can also be viewed as a form of Bayesian infer- ence (Honkela & Valpola, 2004). Such variational methods variational autoencoders (VAEs) (Kingma & Welling, 2014), and related advances that enabled ap- plying such methods to neural networks using standard gradient-based optimizers (Graves, 2011; Blundell et al., 2015). Variational methods have found success for network compression enabling weight pruning (Louizos et al., 2017) and quantization (Achterhold al., 2018; Ullrich et al., 2017) as well as for probing (Voita & Titov, 2020) and improving uncertainty modeling (Sankararaman al., 2022; Gal & Ghahramani, 2016). Other work has pursued applying variational bottlenecks to network activations (Fehr & Henderson, 2024), as opposed to network weights. However, in general, the effectiveness of variational methods for implementing MDL-inspired regularizers for improving generalization has remained elusive (Blier & Ollivier, 2018; Cinquin et al., 2021). Prior work has typically found tighter compression bounds via prequential coding methods (Blier Ollivier, 2018; Borsschein al., 2023). Our work provides some perspectives the poor performance of variational approaches: objectives evaluated by prior work may have poor asymptotic bounds, and variational objectives can be difficult to optimize.
popularized by the success of
48

---

Published as a conference paper at ICLR 2026
D.3 NoN- VARIATIONAL COMPLEXITY MEASURES
As regularization is a foundational concept in machine learning, there are many related methods for neural networks (Jiang et al., 2020), and we give only a brief survey here. We focus on recently proposed compression-based methods with connections to the MDL principle, as these are most relevant to the description length objectives discussed in this paper.
Motivated by prior work on the intrinsic dimensionality of neural networks (Li et al., 2018), Lotfi et al. (2022) propose a complexity measure based on subspace sampling combined with dynamic quantization, similar to the quantization method of Han et al. (2016). Lotfi et al. (2024) combines the method of Lotfi et al. (2022) with LoRA (Hu et al., 2022: Dettmers et al., 2023), to further drive compression. Both Lotfi et al. (2022) and Lotfi et al. (2024) discuss generalization bounds for neural networks related to compression, relevant topic, but not one we study explicitly in this paper. DeMoss et al. (2025) studies the connection between the complexity of a neural network and "Grokking", i.e. the transition from memorization to generalization during training. To this end, they propose a new complexity measure and regularizer based on coarse-grained quantization and spectral entropy, which encourages low rank parameter matrices. Abudy al. (2025) similarly advocate for regularizers grounded in MDL instead of standard norm- based penalties on weights. They demonstrate how norm-based regularizers actively push RNN weights away from perfect ini- tializations on algorithmic tasks, while their MDLLiinppieed objective does not. Their proposed MDL measure can be interpreted as two-part code, using non-differentiable prior that encodes individ- ual weight values according to their representation as a rational number. Dwivedi et al. (2023) similarly studies MDL-inspired complexity measures in over-paramettrized models where param- eter count does not provide a suitable measure of complexity, and proposes a principled measure, MDL-COMP. However, their scope limited to specific classes of linear models and kernel meth- ods.
The variational code proposed in Section 5.1 drives compression by encouraging soft quantization of model weights around the means of the components of the GMM prior, and by reducing the effective number of weights by encouraging higher uncertainty posterior distributions close to the prior for "unused" capacity. The non-variational approaches discussed here similarly combine some form of quantization with some alternative means of reducing the effective number of parameters, e.g. through low-rank approximation. While prior work has not established asymptotic guarantees for these alternative encoding schemes, future work could aim to construct families of asymptotically optimal, or quasi-optimal, codes based these alternative methods.
D.4 COMPUTATIONAL UNIVERSALITY OF TRANSFORMERS
There has been considraabe interest in establishing the theoretical expressivity of various classes of Transformers (Pérez et al., 2021; Chiang et al., 2023; Yun et al., 2020; Feng et al., 2023; Merrill & Sabharwal, 2024a; Nowak et al., 2024; Merrill & Sabharwal, 2024b). Most relevant to constructed mapping between computable, rational-valued distributions and Transformer weights is prior work establishing various equivalences between Transformers and Turing machines. Pérez et al. (2021) established Turing completeness of encoder-decoder Transformer in non- probabilistic language recognition setting, with Merrill & Sabharwal (2024a) and Feng et al. (2023) extending this result to decoder-only variants. Most relevant to our result is Nowak al. (2024), which demonstrates Turing completeness in a probabilistic setting. One difference is that our result holds for Transformer encoders (in the limit as context size and number of layers increase) compared with Nowak et al. (2024)'s 's result for Transformer decoders with intermediate decoding steps. Their result also does not directly extend to prefix Turing machines, which is necessary to support our the- oretical results. However, their work could be potentially helpful for future work seeking to establish the existence of families of asymptotically optimal codes for Transformer decoders with interme- diate decoding steps. Finally, Schuurmans (2023) shows that Transformer decoder augmented with an external memory tape is computationally universal. Broadly, considering description length objectives over models with external tools could be of interest for future work.
We use the ALTA compiler (Shaw et al., 2024) to support our demonstration of universality. ALTA was inspired by RASP (Weiss et al., 2021), an altermative language for compiling programs to Trans- formers, and the related Tracr (Lindner et al., 2023) compiler. ALTA offers better support for pro- grams with loops, which is useful for emulating Turing machine.
49

---

Published as a conference paper at ICLR 2026
D.5 SIMPLICITY BIAS
While our work focuses on implementing a simplicity bias explicitly in a training objective, several studies have evaluated the implicit simplicity bias of neural networks (Zhou et al., 2023; Abbe al., 2023; Bhattamishra et al., 2023; Tsoy & Konstantinov, 2024; Chen et al., 2024; Mingard et al., 2025), or lack thereof (c.g., Nikankin et al., 2025). Others study the simplicity bias of in-context learning with pre-trained models (Goldblum et al., 2023; Deletang et al., 2024), or proposed tasks enhance this bias (Grau-Moya al., 2024).
50


Reviews:
[{"review_id": "2Fq2eUhP2g", "reviewer": "Reviewer_76Kf", "summary": "The authors introduce a theoretical bridge between Kolmogorov complexity and transformers by defining asymptotically optimal description length objectives. The authors show that under certain resource bounds a minimizer of this quantity achieves optimal compression up to an additive constant. They demonstrate that these objectives exist for Transformers, using the computational universality of Transformers. They then develop a variational objective based on adaptive Gaussian mixture prior. Empirically, the proposed objtective encourages lower-complexity solutions with strong generalization on algorithmic tasks, though optimization challenges remain.", "questions": "- Would the proposed objective lead to tighter generalization bounds? It seems like the natural objective to use for those, as it balances the compressed size and empirical performance. Could the authors try computing such bounds?\n- Would using optimizers other than Adam prevent the collapse? SGD is known to generalize better than Adam, and there are now other pseudo second-order optimizers that work well in practice for Transformers. \n- How doable is it to optimize the asymptotically optimal objective in large-scale training? \n- Are there other prior distributions that could be theoretically sound in this context and could improve the optimization?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper provides a rigorous, original connection between the Kolmogorov complexity and neural network training objectives, extending minimum description length to modern architectures. \n- The mathematical derivations are sound, explained thoroughly, and presented in a way that makes them easy to parse. \n- The idea of asymptotically optimal description length objectives is novel and opens an the door towards a theory that guides model optimization in practice.", "weaknesses": "- The experimental section is narrow and doesn’t convincingly show that the proposed objectives can scale or improve over baselines in realistic settings. In particular, the OOD Acc gain is relatively small when random initialization is used and does not achieve the intended purpose of bridging the theory of MDL to practical value through new training objectives. \n- It is hard to do random initialization at larger scales and for more complex tasks, hence the method would not be useful for such settings. \n- There’s no quantitative comparison to other compression-aware training approaches.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "gJl5sFNu0V", "reviewer": "Reviewer_wRu9", "summary": "This theoretical paper connects Kolmogorov complexity with deep learning by creating optimal compression goals for Transformers, based on the idea that the best model is the one that compresses the data the most. It shows that Transformers can simulate any computation, allowing them to achieve near-optimal compression as they grow larger. The paper also provides a practical version of this goal that can be trained with gradients, but finds that standard training methods struggle to find these well-compressed solutions on their own.", "questions": "Is the optimization difficulty fundamental to MDL objectives in neural networks and what do you think would work best to resolve it?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes significant theoretical contributions by rigorously connecting Kolmogorov complexity to neural network training through MDL, providing detailed proofs for the existence of universal two-part codes and asymptotically optimal families for Transformers.", "weaknesses": "1) The paper admits that standard optimizers fail to find solutions of low complexity via random initialization as also shown in Table 1. This might lead to practical difficulties when optimizing the objective if one doesn’t choose careful initialization or specialized methods.\n\n2) The asymptotically optimal code relies on emulating a Turing machine via prompt tokens, which the authors acknowledge is \"inefficient\" and \"overly restricting\" (Section 4.2). This construction is primarily an existence proof and does not leverage the parallel or numerical strengths of Transformers, making it unclear for me how to apply it in practice reliably.\n\n3) I would encourage the authors to explore asymptotically quasi-optimal codes (Appendix B.11) more deeply in future work, as they might offer better trade-offs between theory and practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "oxtmhdAJof", "reviewer": "Reviewer_yv8U", "summary": "This paper proposes a framework for analyzing asymptotic bounds for description length objectives based on the Minimum Description Length (MDL) principle and the universality of Kolmogorov complexity. The authors prove the existence of asymptotically optimal description length objectives for Transformers. Empirically, they evaluate their derived variational objective on a parity task to demonstrate out-of-distribution (OOD) generalization ability.", "questions": "1. In your statement, “Any regularity in the data that is useful for prediction is also useful for compression, and vice versa,” how do you formally define regularities? For readers without a background in computational complexity or algorithmic information theory, a more intuitive explanation would greatly enhance the readability.\n\n2. Is the proposed description length objective specific to Transformers, or can it be generalized to other neural architectures such as fully connected or convolutional networks? If it is general, why is the empirical focus exclusively on Transformers? It is quite strange not to start with simpler fully connected networks. If it is not, what makes Transformers particularly suitable or unique in this context?\n\n3. How does your objective compare to previous complexity measures such as path norms or weight norms investigated in [1] and other compression-based methods as surveyed in Appendix D.3? These metrics also serve as regularizers tied to model complexity and generalization. What conceptual or empirical distinctions set your formulation apart?\n\n[1] Fantastic Generalization Measures and Where to Find Them, ICLR 2020.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The motivation for designing practical description length objectives for deep learning models is clear and well-articulated.\n\n2. The notion of asymptotically optimal codes and their connection to the MDL principle is well-motivated and explained.\n\n3. The paper is overall well-written and structured, offering a useful background on Kolmogorov complexity, source bounds, and the invariance theorem, along with a solid problem statement and mathematically detailed analysis.", "weaknesses": "**Major Concerns**:\n\n1. **Limited practical significance**: While the paper formally establishes the existence of asymptotically optimal codes for Transformers (Theorem 1), it is hard to see what tangible impact or practical value this result provides to Transformer practitioners. The connection between the theoretical guarantees and practical model performance is weak.\n\n2. **Reliance on heuristics**: Although Section 4 presents seemingly rigorous derivations, the practical heuristics (e.g., line 310) are mostly informal, intuitive, and insufficiently justified. This raises concerns about the soundness of analysis and whether the theoretical principles or the heuristics themselves are driving the results. The transition from theory to practice is not well grounded.\n\n3. **Insufficient empirical validation**: The only empirical evaluation (Table 1) focuses on a toy parity task. This experiment is too limited to substantiate the theoretical claims or to demonstrate the effectiveness on realistic settings or tasks. The theory currently appears preliminary and largely hypothetical.\n\n4. **Ambiguous scope**: The authors implement their framework on Transformers, yet do not make any architecture-specific analysis. It remains unclear whether the theory is meant to be architecture-agnostic or specific to Transformers, and why Transformers were chosen as the primary focus.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Qw1Sp0C4Oq", "reviewer": "Reviewer_ALYM", "summary": "This work suggests theoretical bridge between Kolmogorov complexity and deep learning. The authors demonstrate that transformer models can be trained using objectives derived from asymptotically optimal description length. They prove that minimizing these objectives leads to representations that are optimally compressed, with any deviation from the theoretical limit being negligible. The paper also confirms the existence of transformer architectures capable of achieving this asymptotic optimality. While the theory is promising, the authors note that the practical optimization of these objectives remains a significant challenge, even as their empirical results show measurable gains in model generalization.", "questions": "1. Could the optimization challenges be addressed through better initialization schemes or alternative optimization algorithms specifically designed for these objectives?\n2. How does the performance of the GMM-based variational code compare to state-of-the-art compression methods like quantization-aware training or low-rank adaptation?\n3. Are there theoretical guarantees about the convergence rate when optimizing these objectives, or bounds on the gap between the found solution and the theoretical optimum?\n4. How scalable is the ALTA-based construction to large-scale transformers used in practice? Are there complexity bounds on the compilation process?\n5. How do these objectives perform when applied to large-scale datasets and models, beyond presented synthetic tasks?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper establishes rigorous theoretical foundations connecting Kolmogorov complexity to deep learning, proving the existence of asymptotically optimal description length objectives for transformers. The novel construction using the ALTA compiler to map Turing machines to transformer weights provides a concrete bridge between computation theory and neural networks. The paper offers comprehensive analysis of both two-part and variational codes with detailed proofs, while the gaussian mixture model implementation presents a practical, differentiable approach to these theoretically-grounded objectives.", "weaknesses": "While theoretically sound, the work faces significant practical limitations. The proposed method encounters substantial optimization difficulties - standard training procedures fail to discover the low-complexity solutions that the theory guarantees exist. This optimization challenge undermines immediate practical utility. The empirical validation remains quite narrow, relying primarily on synthetic tasks like parity computation without broader benchmarking. The Turing machine emulation approach, while elegant theoretically, appears computationally inefficient for real-world applications. Furthermore, the paper would benefit from direct comparisons with contemporary compression techniques to better position its contributions within the current landscape of this area.\n\nMinor Issues:\n\n1. The notation for additive constants ($\\stackrel{+}{=}$, $\\stackrel{+}{\\leq}$) while standard in information theory, may be unfamiliar to some machine learning readers and could benefit from additional explanation.\n2. Some figures (particularly in appendices) have small font sizes that reduce readability.\n3. The relationship between the theoretical bounds and practical performance could be more clearly articulated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)