Paper deep dive
Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model
Nathan Young
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Solomonoff Induction, or SolInd, provides an ideal unbounded model of a priori sequence prediction but cannot naturally describe extrapolation from a given training dataset, as performed by Large Language Models. We apply de Finetti's theorem on exchangeable distributions to SolInd to produce what we call Hierarchical Solomonoff Induction, or HSI, which maintains a hyperprior over all Solomonoff priors that can be conditioned on previously observed sequences. We extend Wood et al.'s proof that universal mixtures of semimeasures are equivalent to SolInd to show that universal mixtures of these mixtures are also equivalent, proving that HSI=SolInd. We also prove that HSI's excess error on any distribution, compared to its true generator, is bounded by that generator's complexity in the hyperprior. This result is directly comparable to SolInd's prediction error being bounded by the Kolmogorov complexity of the sequence being predicted, and forces HSI's average excess error to converge to 0 as a dataset grows, leading to optimal prediction in the limit. We claim that HSI is an ideal unbounded model of sequence prediction given a dataset in the same way that SolInd is ideal over individual sequences.
Tags
Links
- Source: https://arxiv.org/abs/2608.01005v1
- Canonical: https://arxiv.org/abs/2608.01005v1
Trouble viewing inline? Open PDF directly →
Full Text
45,981 characters extracted from source content.
Expand or collapse full text
Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model Nathan Young Strong AI Lab, University of Auckland nathan.young@auckland.ac.nz Abstract Solomonoff Induction, or SolInd, provides an ideal unbounded model of a priori sequence prediction but cannot naturally describe extrapolation from a given training dataset, as performed by Large Language Models. We apply de Finetti’s theorem on exchangeable distributions to SolInd to produce what we call Hierarchical Solomonoff Induction, or HSI, which maintains a hyperprior over all Solomonoff priors that can be conditioned on previously observed sequences. We extend Wood et al.’s proof that universal mixtures of semimeasures are equivalent to SolInd to show that universal mixtures of these mixtures are also equivalent, proving that HSI=SolInd. We also prove that HSI’s excess error on any distribution, compared to its true generator, is bounded by that generator’s complexity in the hyperprior. This result is directly comparable to SolInd’s prediction error being bounded by the Kolmogorov complexity of the sequence being predicted, and forces HSI’s average excess error to converge to 0 as a dataset grows, leading to optimal prediction in the limit. We claim that HSI is an ideal unbounded model of sequence prediction given a dataset in the same way that SolInd is ideal over individual sequences. 1 Introduction To understand a solution to a computational problem, it can be helpful to first understand that problem’s unbounded solution, i.e. how it might be solved with unlimited computing power. Modern Large Language Models (LLMs) operate in the domain of sequence prediction: given an ordered sequence of symbols on some alphabet (e.g. letters, Unicode characters, or tokens), what symbol comes next? Or, in a probabilistic setting, what distribution over symbols should be expected to come next? The optimal solution to both of these problems is Solomonoff Induction, or SolInd, first described by Solomonoff [1964]. SolInd is Bayesian induction over inputs to a universal Turing machine U, with each input s assigned a prior probability of 2−ℓ(s)2^- (s) (i.e. shorter inputs get more weight). SolInd has been shown [Hutter, 2001] to have several useful optimality properties, including universal dominance (no computable predictor can beat SolInd on any sequence by more than a constant factor) and bounded error (SolInd’s prediction error on any sequence is bounded by that sequence’s Kolmogorov complexity on U). There has been some recent research on modelling LLMs as approximations of Solomonoff Induction [Young and Witbrock, 2025, Wan and Mei, 2025]. However, this research misses a significant part of how LLMs, and machine learning (ML) systems in general, work. Solomonoff inductors make optimal predictions over individual sequences, but not over datasets; it is possible to concatenate a set of strings and use this as a prefix for the sequence that a Solomonoff inductor must predict, but this has the risk of introducing new information not present in the sequences (for example, if the strings are sorted) and identifying programs more complicated than the dataset’s generator. In short, SolInd cannot be trained, and serves as an ideal model of sequence prediction at test time only; it cannot describe ideal performance at training time. Even then, the distribution over sequences represented by the UTM U does not necessarily correspond to the distribution we wish to predict, and it cannot be updated from one sequence to another. With the aim of introducing an unbounded sequence prediction model that can operate over arbitrary datasets of sequences as well as individual, we propose an alternative formulation called Hierarchical Solomonoff Induction, or HSI. HSI is a generalisation of SolInd to computable distributions and resembles a hierarchical Bayesian model, maintaining not only a prior over sequences but a hyperprior ℋH over all computable distributions of sequences (equivalently, over all Turing machines or all Solomonoff priors). HSI is identical to SolInd on individual sequences, but can also condition its hyperprior on a given dataset, in a way analogous to ML training. HSI exhibits optimality properties over datasets that are comparable to SolInd’s over sequences, making a finite amount of error on any dataset bounded by that dataset’s generator’s complexity in ℋH and dominating any other predictor of datasets. 2 Setup Preliminaries and Notation Unless otherwise stated, we follow the definitions and notation of Wood et al. [2013]. We define the binary alphabet =0,1B=\0,1\, the set of binary strings ∗B^* and infinite binary sequences ∞B^∞. We denote the empty string as ϵε, the length of a string x as ℓ(x) (x), the concatenation of strings a and b as abab, and prefixes as ⊑ (that is, p⊑pxp px for any x). We then have the cylinder set of x, Γx=ω∈∞:x⊑ω _x=\ω ^∞:x ω\, and the uniform measure λ with λ(Γx)=2−ℓ(x)λ( _x)=2^- (x). Rather than full probability measures over sequences with μ(ϵ)=1μ(ε)=1 and μ(x)=μ(x0)+μ(x1)μ(x)=μ(x0)+μ(x1), we consider semimeasures, which permit μ(ϵ)≤1μ(ε)≤ 1 and μ(x)≥μ(x0)+μ(x1)μ(x)≥μ(x0)+μ(x1). A semimeasure is lower-semicomputable (equivalently, enumerable) if it can be approximated from below by a computable, monotonically increasing series of values. We write ℳM for the set of all enumerable semimeasures. All Turing machines (TMs) discussed in this paper are of a class called monotone Turing machines. A monotone TM M has a unidirectional read-only input tape on which is written some sequence s, a unidirectional write-only output tape on which it writes some sequence x, a bidirectional working tape, and a finite state machine defining its behaviour over these tapes. M cannot proceed if it attempts to read from a blank cell on its input tape; it must wait for input to arrive. Therefore, if M(s)M(s) is finite, M may produce more output if given more input. If M outputs x when given s as input, we write that M(s)=xM(s)=x. For any x′⊑x x we say that s codes for x′x on M and write M(s)⊒x′M(s) x . We then define, over a TM M, the Solomonoff semimeasure PMP_M: PM(x)≔λ(ω:M(ω)⊒x)P_M(x) λ(\ω:M(ω) x\) This is equivalent to the measure of all minimal s that code for x on M: PM(x)=∑⌊s:M(s)⊒x⌋2−ℓ(s)P_M(x)= _ s:M(s) x 2^- (s) where ⌊X⌋ X is the maximal prefix-free subset of X. By Lemma 6 of Wood et al. [2013], Solomonoff priors on monotone TMs correspond directly to the class of lower-semicomputable semimeasures.111This only holds for nonempty strings, as TMs begin with an empty output tape and so always assign PM(ϵ)=1P_M(ε)=1. In this paper, we ignore the case of the empty string when comparing semimeasures. Universal TMs For a Solomonoff semimeasure to be a universal inductor, the chosen TM must be a universal Turing machine, or UTM. Existing literature [Wood et al., 2013, Li and Vitányi, 2019] describes multiple classes of TMs that might be considered ‘universal’; here we disambiguate and examine three such classes. • Universality by surjection: A TM U is surjective if, for any output sequence x, there exists some input sequence s such that U(s)=xU(s)=x (equivalently, PU(x)>0P_U(x)>0 for all x∈∗x ^*). • Optimality: A TM U is optimal if, for any TM V, there exists some positive constant c such that PU(x)≥cPV(x)P_U(x)≥ cP_V(x) — i.e. PUP_U dominates all Solomonoff semimeasures. This is the standard notion of an (additively) optimal machine in algorithmic information theory [Li and Vitányi, 2019, Downey and Hirschfeldt, 2010]. • Universality by adjunction: A TM U is universal by adjunction if there exists an enumeration Vi:i∈ℕ\V_i:i \ of all TMs and a prefix-free encoding p:ℕ→∗p:N ^* such that U(p(i)s)=Vi(s)U(p(i)s)=V_i(s) [Figueira et al., 2006, Downey and Hirschfeldt, 2010] — in other words, U can emulate any TM.222We might also define a class of machines with an encoding that is not necessarily prefix-free; this class, if distinct from both optimality and universality by adjunction, would be a subset of the former and a superset of the latter. In line with Wood et al. [2013], we use the term ‘universal Turing machine’, or ‘UTM’, to refer to this class. Note that for every VjV_j that is universal by adjunction, there is some additional prefix p′p such that U(p(j)p′(i)s)=Vj(p′(i)s)=Vi(s)U(p(j)p (i)s)=V_j(p (i)s)=V_i(s); there are therefore infinitely many p(j)p′(i)p(j)p (i) such that U(ps)=Vi(s)U(ps)=V_i(s). Wood et al. require UTMs to give no output if their input does not begin with some p(i)p(i); however, Corollary 3.1.5 of Theorem 3.1 shows that this is unnecessary. These classes form a strict hierarchy: UTMs are a subset of optimal TMs, which are a subset of surjective TMs. We now demonstrate this fact, as it is relevant to our later discussion of the domain of HSI’s hyperprior, as well as HSI’s equality to SolInd and induction over TMs in general. Lemma 2.1. There exists an optimal TM that is not a UTM. Proof. By Theorem 16 in Wood et al. [2013], there exists a universally dominant enumerable semimeasure δ′δ that is not a universal mixture. By their Lemma 6, there exists a TM Uδ′U_δ with a Solomonoff semimeasure equal to δ′δ . By their Lemma 10, all UTMs have Solomonoff semimeasures equivalent to a universal mixture. Uδ′U_δ has a universally dominant Solomonoff semimeasure that is not a universal mixture, and is therefore optimal but not a UTM. ∎ As an intuition, δ′δ assigns δ′(0)=δ′(1)=0.5δ (0)=δ (1)=0.5, equivalent to the Solomonoff semimeasure over a TM that begins by either outputting a 0 or a 1; such a machine cannot emulate a ‘silent’ TM that never prints any output at all. Lemma 2.2. There exists a surjective TM that is not optimal. Proof. Consider the identity TM UIU_I, where UI(s)=sU_I(s)=s. UIU_I is surjective, as it may output any x on receiving x as input. We then define the ‘all-zeroes’ TM U0U_0, which continuously prints 0 on its output tape regardless of input. On any sequence 0n0^n of n 0s, PU0(0n)=1P_U_0(0^n)=1 and PUI(0n)=2−nP_U_I(0^n)=2^-n. For UIU_I to be optimal, the following must hold for some positive constant c and all n∈ℕn : PUI(0n) P_U_I(0^n) ≥cPU0(0n) ≥ cP_U_0(0^n) 2−n 2^-n ≥c ≥ c Since 2−n→02^-n→ 0, no c can satisfy 2−n≥c2^-n≥ c for all n. Therefore UIU_I is surjective but not optimal. ∎ Lemma 2.3. Let A be the set of all universal-by-adjunction TMs, O the set of all optimal TMs, and S the set of all surjective TMs. Then A⊊O⊊SA O S. Proof. Take some Ua∈AU_a∈ A. By definition, for any TM T, there exists some prefix p such that Ua(ps)=T(s)U_a(ps)=T(s). Considering only inputs to UaU_a of the form psps, we have: PUa(x)>2−ℓ(p)PT(x)P_U_a(x)>2^- (p)P_T(x) Therefore there exists a positive constant c=2−ℓ(p)c=2^- (p) such that PUa(x)≥cPT(x)P_U_a(x)≥ cP_T(x), so Ua∈OU_a∈ O and A⊆OA O. Further, fix any Uo∈OU_o∈ O and Us∈SU_s∈ S. Then for some positive c, PUo(x)≥cPUs(x)>0P_U_o(x)≥ cP_U_s(x)>0 for any x. Therefore Uo∈SU_o∈ S and O⊆SO S. By Lemmas 2.1 and 2.2, A≠OA≠ O and O≠SO≠ S. Therefore A⊊O⊊SA O S. ∎ UTMs are required for some of SolInd’s optimality properties, and are the strictest of these three criteria; we therefore define SolInd with reference to UTMs only. Solomonoff Induction We can now define the Solomonoff prior PUP_U with respect to a UTM U as the Solomonoff semimeasure over U. The use of this prior to predict a sequence is Solomonoff Induction, or SolInd. While SolInd can be beaten by individual TMs on individual sequences — for example, any SolInd will incur loss on the “all-zeroes” sequences in Lemma 2.2, while U0U_0 will not — its logarithmic loss compared to any other TM M is bounded by the complexity of M on U. By Lemma 2.3, PUP_U dominates PMP_M, giving: PU(x) P_U(x) >2−ℓ(p)PM(x) >2^- (p)P_M(x) PU(x)PM(x) P_U(x)P_M(x) >2−ℓ(p) >2^- (p) −log2(PU(x)PM(x)) - _2 ( P_U(x)P_M(x) ) <ℓ(p) < (p) for some p such that U(ps)=M(s)U(ps)=M(s). Note that the length of the shortest such p is exactly the Kolmogorov complexity KU(M)K_U(M) of M on U. This gives PUP_U a finite error bound on every computable sequence and a constant 2−KU(M)2^-K_U(M) by which it dominates every enumerable semimeasure PMP_M. These bounds differ according to the choice of U; sufficiently poor choice of UTM can lead to arbitrarily large error bounds [Leike and Hutter, 2015]. Wood et al. [2013] proved direct correspondences between TMs and semimeasures: • Lemma 6 proves that the class of enumerable semimeasures is equivalent to Solomonoff semimeasures over the class of TMs; • Theorem 14 proves that the class of universal mixtures of enumerable semimeasures, ξU_ξ, is equivalent to Solomonoff semimeasures over the class of UTMs MU_M (i.e. to SolInd); • Theorem 16 proves that there exist universally dominant enumerable semimeasures that are not equivalent to universal mixtures. These are instead Solomonoff semimeasures over TMs that are optimal but not universal-by-adjunction. This is another way that Solomonoff prediction can differ depending on the choice of machine; these semimeasures have the same optimality properties as SolInd, but are not Solomonoff priors. De Finetti’s Theorem De Finetti’s theorem [De Finetti, 1931] states that if an infinite sequence of variables is exchangeable — that is, if the sequence has equal likelihood regardless of ordering — then there is some latent variable that makes these variables conditionally independent, and that the distribution defined by this variable can be expressed as a mixture over all possible independent and identically distributed (i.i.d.) distributions — that is, a probability distribution over possible distributions, or in other words, a hyperprior over priors. Applied to computable sequence distributions, this would mean that any unordered dataset can be expressed as the prefix of an infinite sequence of independent outputs of a computable sequence distribution, which can be modelled as a mixture of all such distributions. Not only does this framework match ML in describing how to extrapolate from unordered datasets, but the process of searching through the space of distributions to find the one that matches the underlying distribution is the ultimate goal of any ML system. A generalisation of SolInd to the task of sequence prediction by extrapolation from datasets may therefore be obtained by applying de Finetti’s theorem to Solomonoff’s formulation. It has been shown [Hewitt and Savage, 1955] that de Finetti’s theorem holds for Polish spaces, including Cantor space (i.e. ∞B^∞); therefore, the exchangeable distribution from which a dataset of strings is drawn (and therefore its ideal predictor) must take the form of a hyperprior over i.i.d. component distributions. While the computability of the de Finetti measure has been established only for real-valued sequences [Freer and Roy, 2009, 2012], we may assume for the moment that it extends to enumerable semimeasures over strings, and examine what properties such a hierarchical distribution would have. 3 Hierarchical Solomonoff Induction Definition Hierarchical Solomonoff Induction, or HSI, defines a distribution over Solomonoff priors, with a hyperprior ℋH assigning weight to all possible UTMs. Formally, let Uii∈ℕ\U_i\_i be an enumeration of TMs in which every UTM is guaranteed to appear and ℋ:Ui→[0,1]H:\U_i\→[0,1] be an enumerable semimeasure over this enumeration. Define: Pℋ(x)≔∑iℋ(Ui)PUi(x)P_H(x) _iH(U_i)P_U_i(x) (1) That is, PℋP_H is a weighted mixture of Solomonoff priors PUiP_U_i. We assume for the moment that every UiU_i is a UTM so that PℋP_H is a mixture of Solomonoff priors. After some x has been observed, the remaining weight in the hyperprior is equal to ℋ(Ui∣x)=ℋ(Ui)PUi(x)H(U_i x)=H(U_i)P_U_i(x) (2) This conditioned hyperprior will be used to predict the next sequence y: Pℋ(y∣x)=∑iℋ(Ui∣x)PUi(y)=∑iℋ(Ui)PUi(x)PUi(y) splitP_H(y x)&= _iH(U_i x)P_U_i(y)\\ &= _iH(U_i)P_U_i(x)P_U_i(y) split (3) It is worth considering another form of HSI with the conditioned hyperprior being renormalised: ℋ(Ui∣x)=ℋ(Ui)PUi(x)Pℋ(x)=ℋ(Ui)PUi(x)∑jℋ(Uj)PUj(x)H(U_i x)=H(U_i) P_U_i(x)P_H(x)= H(U_i)P_U_i(x) _jH(U_j)P_U_j(x) (4) This form has the advantage that its likelihoods will not monotonically decrease, but its conditional (i.e. next-symbol) predictions are identical, and the division of a lower-semicomputable measure by another removes lower-semicomputability. We therefore consider the unnormalised form in this paper. Here we consider a hyperprior over an enumeration of UTMs. This is the natural extension of SolInd to a hierarchical Bayesian context, with some weight on each possible Solomonoff distribution. However, there are two potential issues with this formulation. Firstly, universality (in all three senses described above) is undecidable in general. We may enumerate TMs that can be proven to be universal, but never the entire class. Secondly, our assumption of computable de Finetti distributions makes no mention of universality, only that the true generator was an enumerable semimeasure. The equivalent de Finetti mixture may therefore include non-universal semimeasures. We may then want to define ℋH over all TMs. This would mean that it included all UTMs with no decidability issues; however, this would make it a universal mixture of enumerable semimeasures, i.e. no different from SolInd. Conditioning the hyperprior on any string x would assign ℋ(U∣x)=0H(U x)=0 to many non-universal TMs, eliminating their contributions forever, but never to all, since for any finite set of strings X there must be some non-universal TM that outputs X. We must therefore consider what class of TMs ℋH should be defined over, and how these choices affect its properties, including its relation to SolInd. An ℋH defined over all UTMs is also a mixture over the enumerable semimeasures that define those UTMs, making such an HSI an instance of SolInd; but can any SolInd be expressed in the form of this more restrictive hyperprior? This question may be expressed in more general terms: define the class of universal mixtures of universal mixtures Ξ(x)≔∑iw(i)ξi(x) (x) _iw(i) _i(x) with some enumeration ξi\ _i\ of the class of all universal mixtures ξU_ξ and an enumerable weight function w. Denote the class of all Ξ as ΞU_ . Is ΞU_ equal to ξU_ξ? Just as ℋH over universal mixtures is equal to some SolInd, every member of ΞU_ is in ξU_ξ; if the reverse is true, then the class of HSI instances ℋU_H is equal to the class of Solomonoff inductors MU_M. In fact, it is possible to prove a more general theorem — that all enumerations of semimeasures in which all universal mixtures appear, when assigned arbitrary weights, are equivalent. Equivalence of HSI and SolInd Theorem 3.1. Let νii=1∞\ _i\_i=1^∞ be any enumeration of enumerable semimeasures in which every universal mixture ξ∈ξ _ξ appears. Let νC_ν be the class of all mixtures c≔∑i∈ℕw(c)(i)νic _i w^(c)(i) _i whose weight functions w(c):ℕ→ℝw^(c):N are lower-semicomputable with w(c)(i)>0∀i∈ℕw^(c)(i)>0\;∀ i and ∑i∈ℕw(c)(i)≤1 _i w^(c)(i)≤ 1. Then ν=ξC_ν=U_ξ. Proof. We take any c∈νc _ν and any ξ∈ξ _ξ, and show that each can be used to construct an instance of their own class equivalent to the other. We first prove that ν⊆ξC_ν _ξ. Since ν includes all universal mixtures, ξ must appear at some index iξ(ν)i_ξ^(ν). Define a new enumeration of semimeasures ν′ν that alternates between the outputs of ν and ξ’s own semimeasure enumeration ν(ξ)ν^(ξ), skipping ξ in ν. Note that as a universal mixture, ξ appears in its own enumeration. Give each semimeasure in ν its corresponding weight in w(c)w^(c) (again skipping ξ), and give each semimeasure in ν(ξ)ν^(ξ) its weight in w(ξ)w^(ξ) multiplied by w(c)(iξ(ν))w^(c)(i_ξ^(ν)). This defines a measure with lower-semicomputable weights on every enumerable semimeasure — that is, a universal mixture — equal to c. Then c∈ξc _ξ and ν⊆ξC_ν _ξ. We then prove that ν⊇ξC_ν _ξ. Since ν(ξ)ν^(ξ) includes all enumerable semimeasures, c must appear at some index ic(ξ)i_c^(ξ). Compute w(ξ)(ic(ξ))w^(ξ)(i_c^(ξ)) from below to find some positive rational q≤w(ξ)(ic(ξ))q≤ w^(ξ)(i_c^(ξ)) and fix δ=q2δ= q2 so that 0<δ<w(ξ)(ic(ξ))0<δ<w^(ξ)(i_c^(ξ)). Define a new universal mixture ξ′ξ with identical semimeasure enumeration to ξ but a new weight function w(ξ)′w^(ξ) : w(ξ)′(i)=w(ξ)(i)1−δ if i≠ic(ξ)w(ξ)(i)−δ1−δ if i=ic(ξ)w^(ξ) (i)= cases w^(ξ)(i)1-δ if i≠ i_c^(ξ)&\\ w^(ξ)(i)-δ1-δ if i=i_c^(ξ) cases As a universal mixture, ξ′ξ must appear in ν at some index iξ′(ν)i_ξ ^(ν). We may then define a new weight function w(c)′w^(c) over ν: w(c)′(i)=1−δ+δw(c)(i) if i=iξ′(ν)δw(c)(i) if i≠iξ′(ν)w^(c) (i)= cases1-δ+δ w^(c)(i) if i=i_ξ ^(ν)&\\ δ w^(c)(i) if i≠ i_ξ ^(ν) cases Multiplying ξ′ξ by 1−δ1-δ recovers the original weight function of ξ, except for the subtraction of δ from its weight on c; this is recovered by every νi _i receiving its weight in w(c)w^(c) multiplied by δ. This defines a measure with lower-semicomputable weights over ν — that is, a member of νC_ν — equal to ξ. Then ξ∈νξ _ν and ν⊇ξC_ν _ξ. We then have ν⊆ξ⊆νC_ν _ξ _ν, which gives ν=ξC_ν=U_ξ. ∎ Note that this is a non-constructive existence proof — iξ(ν)i_ξ^(ν) and ic(ξ)i_c^(ξ) are not always identifiable, but do always exist. Several useful corollaries follow from this result. Firstly, note that this means that any set of such classes must be equivalent: Corollary 3.1.1. Let N be any nonempty set of enumerations of enumerable semimeasures, each of which contains every universal mixture, and for ν∈Nν∈ N let νC_ν be the class from Theorem 3.1. Then ⋃ν∈Nν=⋃ν∈Nξ=ξ _ν∈ NC_ν= _ν∈ NU_ξ=U_ξ. All such enumerations ν therefore form an equivalence class when assigned arbitrary weights. This includes all hyperprior domains proposed above: Corollary 3.1.2. The class of HSI priors is identical given any hyperprior ℋH with a domain that includes all UTMs; for example, hyperpriors that use optimal TMs, surjective TMs, or all TMs will give identical HSI priors. Additionally, since ℋ(U∣X)>0H(U X)>0 for any UTM U and dataset X, this remains true for all conditioned hyperpriors. We may therefore assume only that ℋH assigns positive weight to all UTMs to obtain the same class ℋU_H regardless of what other machines are included. Having resolved our concerns about ℋU_H, we may now compare it to MU_M, and ΞU_ to ξU_ξ: Corollary 3.1.3. The classes ξU_ξ of universal mixtures, ΞU_ of universal mixtures of universal mixtures, MU_M of Solomonoff priors, and ℋU_H of universal mixtures of Solomonoff priors (that is, HSI priors) are all exactly equivalent. HSI being equivalent to all SolInd makes it a strictly smaller class than the universally dominant semimeasures: Corollary 3.1.4. The class of Solomonoff semimeasures on optimal TMs δU_δ, being strictly larger than ξU_ξ, is also strictly larger than ℋU_H regardless of hyperprior domain, even if all such optimal machines are included; that is, there exist universally dominant inductors that are not equivalent to any HSI, although these inductors do not use UTMs. Finally, we may refine our definition of a UTM by relaxing a requirement from Wood et al. [2013]: Corollary 3.1.5. If a TM U has a prefix-free encoding p:ℕ→∗p:N ^* for some enumeration Vi:i∈ℕ\V_i:i \ of all TMs such that U(p(i)s)=Vi(s)U(p(i)s)=V_i(s), this is sufficient for U to be universal by adjunction, as this includes all universal semimeasures; the requirement of Wood et al. [2013] that they produce no output on any other inputs is therefore unnecessary and does not change the class of priors defined. This definition admits some optimal machines that Wood et al. do not consider UTMs, but none with new Solomonoff priors; e.g. the optimal machine Uδ′U_δ from Lemma 2.1 is still unable to emulate a silent TM and so does not meet this definition. Optimality properties Recall that a Solomonoff inductor on UTM U will make no more error on x than KU(x)K_U(x), i.e. the Kolmogorov complexity of x on U. Since HSI is equivalent to SolInd, it inherits this bound on individual sequences, but we can also generalise this bound to prediction of, and extrapolation from, entire datasets. Consider an ordered dataset X=(x1,x2,…x|X|)X=(x_1,x_2,… x_|X|) sampled from some semimeasure μ computed by UμU_μ. The probability assigned to X by some predictor P is P(X)≔∏i=1|X|P(xi∣x<i)P(X) _i=1^|X|P(x_i x_<i) For HSI, this is equal to Pℋ(X)≔∑j∈ℕℋ(Uj)∏i=1|X|PUj(xi∣x<i)P_H(X) _j H(U_j) _i=1^|X|P_U_j(x_i x_<i) But since each individual SolInd prior is independent due to operating only on individual strings, PUj(xi∣x<i)=PUj(xi)P_U_j(x_i x_<i)=P_U_j(x_i), giving Pℋ(X) P_H(X) =∑j∈ℕℋ(Uj)∏i=1|X|PUj(xi) = _j H(U_j) _i=1^|X|P_U_j(x_i) Pℋ(X) P_H(X) =∑j∈ℕℋ(Uj)PUj(X) = _j H(U_j)P_U_j(X) Similarly, we can generalise Equation 2 to operate over datasets to obtain the conditioned hyperprior ℋ(⋅∣X)H(· X): ℋ(Ui∣X)=ℋ(Ui)∏x∈XPUi(x)H(U_i X)=H(U_i) _x∈ XP_U_i(x) (5) Note that this also gives Pℋ(X)=∑i∈ℕℋ(Ui∣X)P_H(X)= _i H(U_i X). Further note that every conditioned HSI prior is equivalent to PUP_U for some UTM U — this means that when a hyperprior is conditioned, it is equivalent to a Solomonoff inductor updating its UTM so that it can better predict the given dataset. Extrapolating from a dataset is therefore equivalent to induction using the conditioned hyperprior (analogous to inference using a trained model): Pℋ(x∣X)≔∑j∈ℕℋ(Uj∣X)PUj(x)P_H(x X) _j H(U_j X)P_U_j(x) (6) We can place a bound on HSI’s excess error on X relative to UμU_μ, given by its complexity in the hyperprior.333Note that UμU_μ need not be universal and therefore may not be in ℋH’s domain; in this case we may choose any encoding p of UμU_μ on any UTM U and use ℋ(Uμ)=2−ℓ(p)ℋ(U)H(U_μ)=2^- (p)H(U). We have: Pℋ(X) P_H(X) =∑jℋ(Uj)PUj(X) = _jH(U_j)P_U_j(X) >ℋ(Uμ)PUμ(X) >H(U_μ)P_U_μ(X) Pℋ(X)PUμ(X) P_H(X)P_U_μ(X) >ℋ(Uμ) >H(U_μ) Taking log loss on both sides, we obtain −log2(Pℋ(X)PUμ(X))<−log2(ℋ(Uμ))- _2 ( P_H(X)P_U_μ(X) )<- _2(H(U_μ)) (7) This bound is similar to SolInd’s error bound on individual sequences given above, with both being guaranteed by the positive probability given to the generator of the sequence or dataset, and made strict by there existing infinitely many such generators on any UTM. Since the above error bound applies regardless of |X||X|, HSI’s average error on sequences in X will approach 0 as it grows: −log2(Pℋ(X)PUμ(X))|X|<−log2(ℋ(Uμ))|X|→|X|→∞0 - _2 ( P_H(X)P_U_μ(X) )|X|< - _2(H(U_μ))|X| |X|→∞0 (8) Further, as new sequences are sampled from μ, we should expect PℋP_H’s excess error on any newly sampled xνx_ν to vanish: Eμ(−log2Pℋ(⋅∣X)(xν)PUμ(xν))→|X|→∞0E_μ (- _2 P_H(· X)(x_ν)P_U_μ(x_ν) ) |X|→∞0 (9) HSI’s ability to converge to any computable distribution of sequences leads us to make the following claim: HSI is the ideal unbounded solution to machine learning over sets of sequences. While SolInd is the ideal prediction scheme over individual sequences, it cannot change its distribution nor extrapolate from a dataset in a manner guaranteed to be order-independent. HSI is dependent on the choice of hyperprior in the same way that SolInd depends on the choice of UTM, but it can condition its hyperprior towards any distribution, remaining as powerful as SolInd at every point. 4 Applications We propose two ways in which HSI may be of practical use: 1. Conditioned hyperpriors as trained models. As an unbounded model of sequence prediction by extrapolation from a dataset, HSI serves as an upper bound for what ML systems in this domain (including LLMs) can achieve, with conditioned hyperpriors describing ideal probability distributions for trained models. These systems may reasonably be expected to more closely resemble approximations of HSI as they improve. Past work has investigated this hypothesis by comparing LLMs and other systems to SolInd [Grau-Moya et al., 2024, Young and Witbrock, 2025, Wan and Mei, 2025], but as discussed above, SolInd can only operate over individual strings and so cannot model ML training. 2. A formal model of document boundaries in training. Most LLM training can be divided into two kinds: training on separate documents from a dataset, and training on concatenations of documents with a delimiter token indicating document boundaries. These two training methods are analogous to the conditioning of an HSI prior on a dataset and giving SolInd the same dataset as a concatenated prefix, respectively. Zhao et al. [2024] find that intra-document masking produces superior results to inter-document concatenation, in line with our claim that HSI’s hyperprior conditioning is a superior approach to the use of concatenated datasets as prefixes. Limitations Like SolInd, HSI is incomputable, requiring an unbounded number of programs to be executed for an unbounded amount of time and use an unbounded amount of memory. However, since LLMs exist as remarkably capable sequence prediction algorithms with structural similarities to SolInd [Young and Witbrock, 2025], we do not count this as an indication that either SolInd or HSI are not useful models. Rather, our main concern with HSI (and equally with SolInd) is that it is monolithic, considering hypotheses and machines separately and only by their outputs. By contrast, bounded approximations of HSI might: • Recognise machines in ℋH and programs on machines that make identical predictions and consolidate these • Recognise programs that make similar predictions, and consolidate their similarities while separately modelling their differences • Break computations into modular parts that may be reused and composed • Compare its best-performing programs — similarities may reveal learned knowledge about the structure of the data while differences may reflect uncertainties • Learn to construct new programs or machines rather than including them all by default Just as HSI does not improve SolInd’s performance but instead creates new affordances like hyperprior conditioning and dataset extrapolation, new unbounded algorithms that model these or other optimisations may represent new ways of mapping the space of computable semimeasures and more closely resemble how state-of-the-art sequence prediction algorithms work in practice. 5 Related Work Unbounded Sequence Prediction Solomonoff [1964] provided the first description of what he called ‘algorithmic probability’, nowadays called Solomonoff Induction. He speculated that SolInd was “about as good as [most prediction methods]”; Hutter [2003] describes optimality results later found by Levin and Solomonoff and generalises these to arbitrary loss functions and alphabets. A comprehensive treatment of algorithmic probability can be found in Chapter 4 of Li and Vitányi [2019], while an in-depth philosophical perspective was given by Rathmanner and Hutter [2011]. UTM-Dependence Existing literature describes Solomonoff Induction as being highly dependent on the choice of UTM. Wood et al. [2013] describe how some universally dominant semimeasures (equivalent to Solomonoff semimeasures on some TMs) are not equivalent to any universal mixtures of semimeasures (and therefore to any SolInd or HSI), while Leike and Hutter [2015] give examples of how any policy in any environment can be optimal according to SolInd on some UTM. Their Lemma 1, which proves that the linear combination of an enumerable prior with a universal mixture results in another universal mixture, is closely related to our Theorem 3.1. SolInd leading to arbitrarily-poor decisions does not contradict its optimality properties; SolInd’s error bounds are finite but arbitrarily large on any particular sequence. Wood et al.’s result shows that Solomonoff semimeasures can be universal but not equivalent to SolInd, while Corollary 3.1.4 shows that this is not true of HSI, which is (by Corollary 3.1.3) an equivalent class to SolInd as long as its hyperprior includes all UTMs — inclusion of any other subset of TMs does not change the class of priors considered over sequences or datasets. This also gives a partial answer to the problem of the “identification of ‘natural’ Turing machines” given by Hutter [2009] — if there exist subclasses of UTMs that have some properties desirable for induction, these classes must not assign arbitrary weights to UTMs or universal mixtures. On the other hand, Corollary 3.1.5 shows that the space of UTMs is wider than defined by Wood et al.. Meta-learning and Hierarchical Bayes Grau-Moya et al. [2024] train Transformers to perform meta-learning by training on data sampled from a UTM, with the aim of comparing them to the ideal of SolInd. Baxter [2000] frames meta-learning as induction over a prior on hypotheses — that is, as hierarchical Bayesianism, with priors over observations and a hyperprior over these priors. Under this lens, the ideal way for an ML system to meta-learn data from a UTM is to maintain a hyperprior over possible UTM distributions; this is an exact description of HSI. Sterkenburg [2018] examines the suitability of SolInd for prediction in the real world, finding that its incomputability is a fundamental obstacle to its practical use and that no computable approximation can have any of its optimality properties. While the SolInd prior indeed cannot be learned in practice, HSI describes the ideal meta-learning algorithm for learning universal priors, and so may suggest ways in which approximations might be learned — however, HSI’s meta-learning is as incomputable as SolInd’s learning, and so may only offer suggestions that are as impractical as SolInd’s. Computable Probability Measures De Finetti [1931] describes how any infinite series of exchangeable observations must be conditionally independent in relation to some latent variable, and that the distribution defined by this variable must be expressible as a mixture over possible distributions — in other words, a hierarchical Bayesian structure inevitably emerges when modelling any exchangeable data. Hewitt and Savage [1955] describe how de Finetti’s theorem applies to Cartesian products such as the Cantor space over which sequence prediction is performed, while Freer and Roy [2009, 2012] prove that de Finetti mixtures over computable sequences of real numbers are themselves computable. The generalisation of computable de Finetti measures to sequence prediction is an open research area with a close theoretical relation to this work — we expect that de Finetti mixtures of enumerable semimeasures over sequences can be proven to also be enumerable semimeasures. If these mixtures are universal, they are (by Theorem 3.1) exactly equivalent to HSI, which would make HSI the unique ideal solution to extrapolation from exchangeable sets of sequences. LLMs as Approximations of SolInd Recent work has examined the hypothesis that LLMs can be understood as approximations of SolInd, and that they form better approximations than other architectures. 1 argue that language modelling is equivalent to compression, i.e. finding the shortest description of the training dataset according to some encoding. SolInd and HSI over a dataset use weighted averages of all possible descriptions, but shorter inputs get exponentially more weight and therefore dominate. Grau-Moya et al. [2024] trained Transformer models alongside other neural networks on data sampled from a UTM, finding that Transformers outperform all other models on this data, providing useful evidence that their resemblance to SolInd extends beyond language modelling to sequence modelling in general. Transformers’ performance suffered on out-of-distribution sequence lengths, but this can be attributed to the positional encoding used [Genewein et al., 2026]. Wan and Mei [2025] examine LLMs as approximations of SolInd, finding that when Transformers are fine-tuned on training examples on which they performed poorly, they improve more than when fine-tuned on examples on which they performed well, since these examples provided the largest Bayesian update to the model’s priors. HSI allows us to quantify this update exactly: updates to each ℋ(Ui)H(U_i) according to an example x are directly proportional to PUi(x)P_U_i(x). Since 0<PUi(x)<10<P_U_i(x)<1, this is always a decrease, so each ℋ(Ui)H(U_i) receives a greater update when PUi(x)P_U_i(x) is lesser, and likewise with ℋH receiving larger updates overall with smaller Pℋ(x)P_H(x). 6 Conclusion We have presented Hierarchical Solomonoff Induction, or HSI, an ideal unbounded sequence prediction algorithm with bounded error and convergence guarantees over both datasets and sequences. HSI’s hyperprior ℋH may be defined over any enumeration of Turing machines as long as all universal Turing machines are included, with the class of HSI priors ℋU_H being identical to the class of SolInd priors MU_M for any such enumeration. HSI is identical to SolInd over individual sequences, and is additionally capable of describing ideal sequence prediction by extrapolation from a dataset in a way that SolInd is not. We hope that HSI will be useful for understanding how LLMs and other sequence prediction models work by providing an upper bound on what they may achieve and an idealised method that they may approach. Acknowledgments An AI assistant helped plan, review, and edit this paper, as well as contributing an initial proof that a Turing machine could emulate any mixture of universal Turing machines. The concepts behind this proof were generalised to produce Theorem 3.1. No prose or results in this paper are AI-generated. I would like to thank my PhD supervisors, Michael Witbrock and Robert Amor. This research was supported by the University of Auckland Doctoral Scholarship. References [1] Cited by: §5. J. Baxter (2000) A model of inductive bias learning. Journal of Artificial Intelligence Research 12, p. 149–198. Cited by: §5. B. De Finetti (1931) Funzione caratteristica di un fenomeno aleatorio. Atti della R. Accademia Nazionale dei Lincei, Serie 6. Memorie, Classe di Scienze Fisiche, Matematiche e Naturali 4. Cited by: §2, §5. R. G. Downey and D. R. Hirschfeldt (2010) Algorithmic randomness and complexity. Theory and Applications of Computability, Springer. Cited by: 2nd item, 3rd item. S. Figueira, F. Stephan, and G. Wu (2006) Randomness and universal machines. Journal of Complexity 22 (6), p. 738–751. Cited by: 3rd item. C. E. Freer and D. M. Roy (2009) Computable exchangeable sequences have computable de Finetti measures. In Mathematical Theory and Computational Practice (CiE 2009), Lecture Notes in Computer Science, Vol. 5635, p. 218–231. External Links: Document Cited by: §2, §5. C. E. Freer and D. M. Roy (2012) Computable de Finetti measures. Annals of Pure and Applied Logic 163 (5), p. 530–546. Cited by: §2, §5. T. Genewein, J. Grau-Moya, L. K. Wenliang, L. Orseau, and M. Hutter (2026) Algorithmic compression via pretrained neural networks. Entropy 28 (6), p. 596. Cited by: §5. J. Grau-Moya, T. Genewein, M. Hutter, L. Orseau, G. Déletang, E. Catt, A. Ruoss, L. K. Wenliang, C. Mattern, M. Aitchison, and J. Veness (2024) Learning Universal Predictors. Proceedings of Machine Learning Research 235, p. 16178–16205. External Links: 2401.14953, ISSN 26403498, Link Cited by: item 1, §5, §5. E. Hewitt and L. J. Savage (1955) Symmetric measures on Cartesian products. Transactions of the American Mathematical Society 80 (2), p. 470–501. Cited by: §2, §5. M. Hutter (2001) General Loss Bounds for Universal Sequence Prediction. arXiv preprint arXiv:cs/0101019. External Links: 0101019, Link Cited by: §1. M. Hutter (2003) Optimality of Universal Bayesian Sequence Prediction for General Loss and Alphabet. Journal of Machine Learning Research 4 (Nov), p. 971–1000. Cited by: §5. M. Hutter (2009) Open problems in universal induction & intelligence. Algorithms 2 (3), p. 879–906. External Links: Document, 0907.0746, ISSN 19994893 Cited by: §5. J. Leike and M. Hutter (2015) Bad universal priors and notions of optimality. In Journal of Machine Learning Research, Vol. 40. External Links: 1510.04931, ISSN 15337928 Cited by: §2, §5. M. Li and P. Vitányi (2019) An introduction to kolmogorov complexity and its applications. 4th edition, Texts in Computer Science, Springer. Cited by: 2nd item, §2, §5. S. Rathmanner and M. Hutter (2011) A philosophical treatise of universal induction. Entropy 13 (6), p. 1076–1136. External Links: Document, 1105.5721, ISSN 10994300 Cited by: §5. R. J. Solomonoff (1964) A formal theory of inductive inference. Part I. Information and control 7 (1), p. 1–22. Cited by: §1, §5. T. Sterkenburg (2018) Universal prediction: a philosophical investigation. Ph.D. Thesis, University of Groningen. Cited by: §5. J. Wan and L. Mei (2025) Large Language Models as Computable Approximations to Solomonoff Induction. arXiv preprint arXiv:2505.15784. External Links: 2505.15784, Link Cited by: §1, item 1, §5. I. Wood, P. Sunehag, and M. Hutter (2013) (Non-)equivalence of universal priors. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 7070 LNAI, p. 417–425. External Links: Document, 1111.3854, ISBN 9783642449574, ISSN 16113349 Cited by: 3rd item, §2, §2, §2, §2, §2, §2, §3, §3, Corollary 3.1.5, §5, §5. N. Young and M. Witbrock (2025) Transformers as Approximations of Solomonoff Induction. Lecture Notes in Computer Science 15286 LNCS, p. 16–25. External Links: Document, 2408.12065, ISBN 9789819665754, ISSN 16113349 Cited by: §1, item 1, §4. Y. Zhao, Y. Qu, K. Staniszewski, S. Tworkowski, W. Liu, P. Miłoś, Y. Wu, and P. Minervini (2024) Analysing the Impact of Sequence Composition on Language Model Pre-Training. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, External Links: Link Cited by: item 2.