PaperlayerView exact revision on arXiv

Source-linked AI summary

What Can Language Models Inherit from Solomonoff Induction? Limits, Attainable Properties, and What Served Conditionals Reveal

Luan Ozelim, Abicumaran Uthamacumaran, Hector Zenil

arXiv:2610.14007v1cs.LGcs.AIcs.ITmath.IT

TL;DR

The paper asks whether language models’ proper-loss training, flexibility, and predictive success justify saying they approach Solomonoff induction. Applying results from universal prediction and Bayesian consistency, it shows that no computable model achieves the uniform guarantee and that common evidence cannot certify it. Its Kraft lens recasts the issue as where predictors allocate a shared budget, while identifying guarantees attainable on declared classes.

  • Problem

    The inference from proper-loss training and universal approximation to approaching Solomonoff induction treats predictive success as evidence for a broader allocation that the paper asks whether it can establish.

    Source: §1 · pp. 1–2

  • Method

    The paper applies results from algorithmic information theory, universal prediction, and Bayesian consistency, using Kraft’s inequality as a lens on predictors’ allocation of predictive success.

    Source: §1 · p. 2

  • Results

    Every computable model has an environment where it loses log V bits per step while Solomonoff’s predictor pays a constant, and no uniformly computable family avoids a shared such environment.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Bayes mixtures attain Solomonoff-form guarantees on declared classes, while trustworthy deployment is argued to require Solomonoff-like beliefs with non-Solomonoff-like constraints.

    Source: §11 · p. 30

    Asymptotic consistency, merging, and vanishing per-step excess loss cannot reveal the constants carrying Solomonoff’s guarantee.

    Source: §7 · p. 18

Abstract

from arXiv · show

A familiar line of reasoning runs as follows: language models are flexible approximators trained under a strictly proper loss, so scale brings them closer to Solomonoff induction, and their predictive success is evidence of that approach. We apply known results from algorithmic information theory, universal prediction and Bayesian consistency. In its uniform form the conclusion holds for no computable model: each has cheap environments it never learns, and every uniformly computable family of total predictors shares one on which each member fails beyond a horizon growing with its index, so ``closer'' can hold only pointwise, one environment at a time. Nor could the offered routes certify even that: finite evaluation cannot certify agreement on rarely reached contexts, perfect corpus fit selects the corpus law as prior, and asymptotic criteria cannot see the constants that carry Solomonoff's guarantee. Our lens is the Kraft inequality read for predictors. Every model has at most the same budget of predictive success, so Solomonoff's predictor, which leaves part of it unspent, differs from a language model not in having more of it but in where it spends it; on mutually singular families this is exact, and only full-mass Bayes mixtures reach the frontier. We then discuss what is inheritable, including in-context learning as amortised Bayesian inference; what survives within a context window; which Solomonoff-like properties a deployed system should have or avoid; and what served conditionals determine. A closing table states what common practices certify and what to report. Tests are developed in a companion paper.

1 Introduction

The paper tests the inference that proper-loss training and model flexibility make language models approach Solomonoff induction, distinguishing what predictive success establishes from what it cannot certify. It argues that the uniform claim fails for computable models, while some Solomonoff-form guarantees remain attainable on declared classes.

Motivation

  • Language models’ strictly proper log-loss and transformers’ universal approximation motivate the claim that scale brings them closer to Solomonoff induction, but do not establish it.The paper treats that claim as a strengthened version of positions that survive only in part.Source: §1 · pp. 1–2

Evaluation

  • Finite evaluation cannot certify agreement on rarely reached contexts: N queries cannot distinguish models that differ only where queries rarely go.Benchmark and red-team evidence can falsify agreement, but not certify it; scaling curves track the test distribution’s ε.Source: §1 · p. 4

Scale

  • Every computable model has an environment no more complex than itself where it loses log V bits per step, while Solomonoff’s predictor pays a constant; a uniformly computable family shares such an environment.Thus convergence along a scaling family can be pointwise, not uniform.Source: §1 · p. 4

Data

  • A predictor with zero regret on its corpus coincides with the corpus law, so fitting a corpus chooses a prior rather than certifying allocation elsewhere.Solomonoff’s predictor pays at most K(q)+O(1) bits more on the corpus; data curation and mixture weights are prior design.Source: §1 · p. 4

Inheritance

  • Bayes mixtures attain Solomonoff-form guarantees on declared classes, and the paper frames in-context learning as amortised Bayesian inference.A pretraining loss certifies in-context allocation through prior mass, while demonstrations can steer it.Source: §1 · p. 4

Asymptotics

  • Consistency, merging, and vanishing per-step excess loss cannot reveal the constants carrying Solomonoff’s guarantee, because finite prior modifications and reweighting change those constants.Asymptotic criteria are blind to the prior.Source: §1 · p. 4

Deployment

  • Within a context window, a bounded-window model repays environment-identification cost at most about once per window, and exactly that on a copy source.Only temperature one keeps Solomonoff’s bound; truncation is dogmatism by design, and the character-level law is a marginal over tokenisations.Source: §1 · p. 4

Properties

  • The paper ranks attainable Solomonoff-like properties, noting that several are attack surfaces, and argues that trustworthy systems should pair Solomonoff-like beliefs with non-Solomonoff-like constraints.This is presented as a judgement, not a proved result.Source: §1 · pp. 4–5

2 Background and the Kraft lens

The background defines predictors and regret, then reads Kraft’s inequality as a fixed budget of predictive success. On mutually singular families, the regret frontier is exactly attained by full-mass Bayes mixtures.

2.1 Predictors, regret and Solomonoff’s predictor

  • A predictor assigns conditionals to contexts; its log-loss is negative log probability, and regret is excess expected loss over the source.Solomonoff’s predictor has regret at most K(µ)+O(1) bits on every computable measure µ.Source: §2.1 · pp. 5–6

2.2 Conservation as a lens

  • At most 2^b strings of any fixed length can receive cumulative log-loss below b bits, so every predictor has the same success budget to allocate.Predictors differ in where they spend it and how much they leave unused; Solomonoff’s predictor leaks part of its budget.Source: §2.2 · pp. 7–8

2.3 The frontier of regret profiles

  • For pairwise mutually singular environments, achievable regret profiles form the Kraft set, and every profile in it is attained by a Bayes mixture.The frontier consists exactly of full-mass Bayes mixtures; a profile is Pareto-optimal iff its Kraft sum is one.Source: §2.3 · pp. 8–9
  • On singular sources, the regret frontier makes prior allocation exact: the regret on each source is bounded below by the log inverse of the mixture’s mass on its carrier.Carrier masses sum to at most one, as illustrated by the singular-pair regret profiles.Source: §2.3 · p. 9, Figure 2 · p. 9
  • On overlapping finite families, the achievable region remains exact, but the maximal Kraft sum occurs only for mixtures over maximising priors.For countable non-singular families, only the weaker bound C∞ > 1 is established.Source: §2.3 · p. 9

3 What evaluation can certify

Evaluation constrains served conditionals only on contexts it reaches often enough, so finite tests can falsify agreement with a reference but cannot certify it on rarely sampled contexts. Adaptive queries can find failures more efficiently, but their certification limits depend on the rare-context mass and evaluation setup.

3 What evaluation can certify

  • Evaluation evidence constrains conditionals only on contexts reached with probability comparable to the inverse of the query count.Benchmarks, red teams, and scaling curves therefore address the evaluation distribution, not unvisited contexts.Source: §3 · pp. 9–10

3.1 Underdetermination

  • N-query evaluations cannot reliably distinguish predictors differing only on a set of mass δ: their verdict laws differ by at most Nδ.On low-mass contexts, predictions can be replaced at negligible average-score cost.Source: §3.1 · p. 10

3.2 Adaptive evaluation

  • At fixed resolution δ, adaptivity buys at most 2δ queries for separating every such alternative, while passive sampling detects a fixed disagreement set with N ≥ ln(1/α)/δ.The comparison is asymmetric: the adaptive quantity is a lower bound, while the passive quantity is an upper bound for a known reference.Source: §3.2 · p. 11

Benchmarks, red teaming, scaling curves and contamination.

  • Accuracy, red teaming, scaling curves, and contamination instantiate the same bound: they cannot certify off-distribution agreement with a reference.Scaling curves measure excess loss on the evaluation law; red teaming can falsify agreement but not certify it.Source: §3 · p. 10, Benchmarks, red teaming, scaling… · p. 11

4 What scale cannot deliver

Diagonal constructions show that no computable predictor has Solomonoff's regret guarantee uniformly, and a uniformly computable family shares an environment on which its members eventually fail. These results limit uniform convergence claims without determining any particular model's performance at observable horizons.

4.1 A single predictor

  • Every fixed computable predictor has a computable sequence of complexity at most K(q)+O(1) where it loses at least log V per step, while Solomonoff's total regret stays bounded.For real-valued computable conditionals, the per-step lower bound is log(2V/3).Source: §4.1 · p. 12
  • A uniformly computable family shares one environment where member i fails beyond a horizon growing with its index, but this implies no failure at any particular observable horizon.The apparent convergence exchanges “one model good at every horizon” for “some model good at each horizon.”Source: §4 · p. 11, §4.1 · p. 12

4.2 Randomised decoding and compute budgets

  • Randomization does not evade the diagonal: for random conditionals, the construction applies to their computable mean predictor, with expected loss at least n log(2V/3).The bound concerns the averaged allocation.Source: §4.2 · pp. 12–13
  • Resource-bounded diagonal results also apply, but the failing environment changes with the model's description-length and per-step-compute budget.The paper summarizes these bounded-resource forms in Section 8.Source: §4.2 · p. 13

5 Fitting a corpus chooses a prior

Perfect log-loss fitting selects the corpus law as the prior, whose predictive guarantees extend only to laws it dominates. The paper contrasts that allocation with Solomonoff's bounded, pathwise complexity premium and describes post-training and refitting as reallocations rather than expansions of the predictive budget.

5 Fitting a corpus chooses a prior

  • At the limit, minimizing log-loss selects the corpus law as prior, with finite regret only on laws absolutely continuous with respect to it.A law dominated by the corpus law by factor c incurs at most log c regret.Source: §5 · p. 13
  • The zero-excess-loss limit matches the source on every cylinder and pays D(ν ∥ µ) on another law; regret diverges for laws singular to µ.For a non-atomic µ, regret on every individual sequence tends to infinity.Source: §5 · p. 13
  • A finite corpus is atomic: exact fitting gives infinite loss to strings of corpus length absent from it, while the population-law theorem applies to the population source.Both laws concern tokens; the character law is a marginal over tokenizations.Source: §5 · p. 13
  • No computable corpus carries every class's constants, so fitting one does not recover the simplicity prior; declared-class mixtures or amortized pretraining offer alternatives.Amortized pretraining extends reach but gives up the certificate.Source: §5 · pp. 13–14
  • Solomonoff's pathwise premium over a computable model q is at most K(q)+O(1) bits, paid once at every horizon; the reverse trade is unbounded.The text estimates the premium below one percent for an 8-billion-parameter model under its stated token and coding assumptions, and about four percent for the 70-billion-parameter model.Source: §5 · p. 14
  • Post-training, data mixing, and generated-data refitting reallocate predictive budget: reward optimization changes environment regret, source reweighting trades bits, and refitting drifts toward an allocation vertex.The paper states these mechanisms in its discussion of post-training and refitting.Source: §5 · pp. 13–14

6 What is inheritable

Computable Bayes mixtures inherit Solomonoff-form regret guarantees on declared classes, while no computable predictor is maximal. In-context learning is posterior updating under pretraining weights, whose loss certificate depends on task prior mass and can be weak; demonstrations can steer the posterior, while tools and test-time compute alter the allocation setting.

6 What is inheritable

  • On declared uniformly computable classes, a computable Bayes mixture has regret at most log(1/wi) on component µi, with equality for singular families.No computable predictor is within a constant of K on every member of an infinite uniformly computable family of distinct deterministic environments.Source: §6 · p. 14
  • Adding a predictor’s diagonal environment to a mixture makes the hierarchy strict: the mixture pays bounded extra regret elsewhere while the original predictor fails on that diagonal.Thus no computable predictor is maximal or complete; inductive position depends on a class and its constants.Source: §6 · p. 15

6.1 In-context learning as amortised Bayesian inference

  • In-context learning is posterior prediction under pretraining-fixed mixture weights, with context updating the posterior; demonstrations can therefore steer the continuation law.Observed behaviors include order and label biases, task-diversity shifts toward ridge regression, and demonstrations that can signal task identity apart from task learning.Source: §6.1 · p. 15
  • A pretraining loss certifies in-context regret relative to its Bayes mixture according to prior mass, not task by task, and the bound weakens sharply for low-mass tasks.When task weights have no positive lower bound, no rate holds uniformly over tasks; the certificate is exponentially weak in k for prior mass 2^-k.Source: §6.1 · pp. 16–17

Steering by demonstrations.

  • A positive evidence rate against competing hypotheses makes demonstrations quantitatively steerable, with the required length growing with target rarity and desired accuracy.Choosing demonstrations where hypotheses disagree maximizes that per-demonstration evidence rate; the proposed link to many-shot jailbreaking is explicitly a hypothesis.Source: Steering by demonstrations · p. 17

Tools, retrieval and test-time compute.

  • Combining a tool or retriever as a joint mixture preserves each component’s bound at the cost of its mixture weight, unlike conditional interpolation or selection.Extra test-time computation changes what the model computes, not the prior it holds.Source: Tools, retrieval and test-time compute · p. 18

7 Asymptotic criteria cannot see allocation

Asymptotic consistency, merging, and vanishing per-step loss do not reveal the constants that carry Solomonoff’s guarantee. Finite modifications and prior reweighting preserve such criteria while changing regret, so claims of Bayesian or Solomonoff-like behavior have empirical content only over a declared class at finite horizons.

7 Asymptotic criteria cannot see allocation

  • Consistency, merging, and vanishing per-step excess loss are asymptotic properties shared by priors covering the truth, yet they cannot identify the constants in Solomonoff’s guarantee.Consistency can exempt a null set of parameters, and full-support priors can still concentrate on the wrong answer.Source: §7 · p. 18
  • Changing a predictor on finitely many contexts can preserve finite regret and vanishing per-step loss while leaving it with large regret on a simple computable source.A predictor uniform before horizon N pays N log V + O(1) on the constant sequence 0∞.Source: §7 · p. 18
  • Reweighting a Bayes prior changes regret constants without changing consistency: on singular families, full-mass mixtures attain the regret frontier, while their profiles can differ without bound.Frontier membership itself can be lost by changing a conditional at one context.Source: §7 · pp. 18–19
  • The implication from predictive success to approaching Solomonoff induction is invalid: finite-ε optimality on a context distribution does not entail a complexity bound on computable sources.A computable witness can yield the separation at arbitrarily small ε-cost by modifying contexts with sufficiently low distributional mass.Source: §7 · p. 19

7.1 What “language models are Bayesian” can mean

  • Calling a coherent predictor Bayesian without declaring a class and prior imposes no restriction, since any probability measure is a mixture of point masses under itself.Its conditionals are the corresponding posterior predictives.Source: §7.1 · p. 19
  • Once a class is declared, asymptotic Bayesian signatures are shared by all priors assigning positive weight to truth, so they identify neither the prior nor its source.Even universality leaves finite-horizon behavior unconstrained by the choice of reference machine, whose multiplicative constants are unbounded across machines.Source: §7.1 · p. 19
  • A claim that a model is Bayesian or approximately Solomonoff has empirical content only as a finite-horizon statement about constants over a declared class.Every computable predictor is within a bounded regret increment of some universal predictor, making dominance-based universality alone uninformative about behavior.Source: §7.1 · p. 20

8 The deployed regime

Within its context window, a deployed model retains the paper’s finite-horizon results, but a bounded window can repeatedly incur the cost of identifying a source. Temperature changes Solomonoff’s guarantees, and truncation, tokenisation, and reasoning traces change what served predictions represent.

8 The deployed regime

  • For horizons up to W + 1, windowed models retain finite-horizon results, including conservation, Kraft floors, mixture bounds, and diagonal lower bounds; infinite-horizon criteria no longer apply directly.A window-memory model reaches the infinite-horizon regime only through the window, which incurs a separately quantified cost.Source: §8 · p. 20

Context windows.

  • A window-W predictor can repeatedly pay the identification cost: on the period-(W + 1) copy witness it loses log V bits per token, while Solomonoff pays at most K(W + 1) + O(1) overall.For stationary tasks, the window tax can range from zero to its cap; evidence below W tokens does not resolve this regime.Source: Context windows · p. 21

Temperature.

  • Only temperature one retains Solomonoff’s regret bound; below one, deterministic-stream loss scales by at most 1/T while nonuniform i.i.d. sources incur positive asymptotic excess loss.Above one, the deterministic loss is unbounded and the same linear excess-loss bound holds for nonuniform i.i.d. sources.Source: Temperature · pp. 21–22

Truncation, tokenisation and reasoning traces.

  • Sampling at temperature T serves sequentially tempered conditionals, not a tempered joint law; without truncation, samples reveal normalized conditionals but not leakage.Truncation assigns zero probability to excluded continuations, while tokenisation and reasoning traces make the served answer law a marginal over tokenisations or traces.Source: Temperature · p. 22
  • A served read must state its truncation settings and discarded mass, because a renormalized alphabet mask defines neither the model’s full continuation law nor that law conditioned on remaining in the alphabet.The read should also specify the serving configuration.Source: Truncation, tokenisation and reasoning… · p. 22

9 Properties ranked, and those to avoid

The section distinguishes attainable safeguards from universality, which no computable system can have, and argues that desirable Solomonoff-like properties depend on whether a system governs beliefs or constraints.

9.1 Two floors

  • A Bayes mixture can dominate an expert with a bounded constant, but bounded-window prediction incurs a window tax over KT on some i.i.d. source.The excess tends to about (V −1)/(2W ln 2) bits; a failure within the window does not show the model is no mixture.Source: §9.1 · p. 23

9.2 The properties, ranked

  • Trust-relevant safety properties are attainable, while universality is not; expert dominance is scoped to the context window.The properties that make an inductor safe to rely on are attainable, with expert dominance limited to that window.Source: §9.2 · p. 23
  • Solomonoff’s ideal can fail on individual random sequences and selected structured positions because its unspent budget is allocated elsewhere.Normalisation restores selected-position learning; sampling at temperature one serves the normalised predictor.Source: §9.2 · p. 24

9.3 Properties that are undesirable in deployment

  • Deliberate dogmatism about designated hypotheses can resist steering, reallocating prediction budget away from environments one does not wish to predict.Zero prior weight alone is insufficient because other hypotheses can reproduce an excluded one.Source: §9.3 · p. 25
  • A perfect corpus predictor is the corpus law, so it reproduces corpus errors and harms at corpus rates, while post-training departs from that law.The stated consequence is the authors’ reading of the exact corpus-predictor result.Source: §9.3 · p. 25
  • Exchangeability fits conditionally i.i.d. demonstrations, but conversation position carries information, motivating an explicitly trained instruction hierarchy [187].Order invariance is desirable for demonstrations specified as conditionally i.i.d.Source: §9.3 · p. 25
  • Coherence, within-window dominance, and non-dogmatism about the world remain desirable; other properties can help beliefs but harm constraints or drifting-world adaptation.The proposed—not proved—position is Solomonoff-like beliefs with non-Solomonoff-like constraints.Source: §9.3 · p. 25

10 What served conditionals determine

Served conditionals can reveal coherence, invariance, constants, and a prior relative to a declared class. The proposed readings depend on how the served probabilities are elicited and on the probe set.

10 What served conditionals determine

  • Served conditionals determine coherence, invariance, constants against references, and a prior over a declared class, while tail-invariant and fixed-distribution statistics miss important information.The section gives definitions and identities; estimators, noise floors, and validation are deferred to Paper B.Source: §10 · p. 25

10.1 Elicitation and coherence

  • Elicitation reads served probabilities as T = 1 continuation probabilities without truncation on one tokenisation; a positive coherence residual rules out a measure and can imply arbitrage.For masked reads, the residual refutes coherence for the masked, renormalised predictor, not the unmasked continuation law; prompted probabilities and tokenisation can also affect readings.Source: §10.1 · pp. 25–26

10.2 Invariance and constants

  • Bayes mixtures over conditionally i.i.d. hypotheses are invariant to demonstration order, while description-length and uniform priors yield distinct truth-loss levels after identification.The levels are ℓ+c under a 2^-ℓ-c prior and log |H| under a uniform prior; before identification only the upper bound holds.Source: §10.2 · pp. 26–27

10.3 Reading the prior

  • Reading an implied prior is an inverse problem relative to a declared class: a zero membership residual means some Bayes mixture agrees on the finite probes, while a positive residual signals mismatch or a larger class.For deterministic classes, membership tests support rather than allocation; conditional readings can yield the same analysis by distillation under stated probe and student conditions.Source: §10.3 · p. 27

11 Discussion

The discussion concludes that computable models cannot inherit Solomonoff’s allocation, while Bayes-mixture guarantees and served-conditionals measurements remain relative to declared classes. It emphasizes idealised scope and leaves deployment-specific readings to a companion paper.

11 Discussion

  • Compression evidence beyond the corpus does not certify a constant on a declared class, and comparisons with adaptive coding on the same chunks were not reported.The paper treats the prior held by a trained network as an empirical question.Source: §11 · p. 29
  • The paper’s conclusions concern idealised objects, and the achievable frontier for countable non-singular families and its maximising priors remain open.Section 10.3 removes the declared prior from readings, not the declared class.Source: §11 · p. 29
  • The companion study measures particular deployments; its readings are consistent with mixture-like behaviour on declared classes, but allocation remains entangled with the interface.The reported measurements use stated renderings and do not establish general theorems.Source: §11 · p. 29
  • No computable model can hold Solomonoff’s allocation, but Bayes mixtures attain its form on declared classes, and pretraining loss certifies in-context constants only through task-family prior mass.The remaining questions are where each model spends its Kraft budget and which properties a deployed system should have.Source: §11 · p. 30

A Consequences of the Kraft inequality

Kraft’s inequality turns predictive regret into a finite budget across distinguishable strings: low regret on some contexts necessarily limits success elsewhere. The resulting floors and exchange bounds quantify that allocation.

A Consequences of the Kraft inequality

  • For any predictor q and finite antichain S, mean log-loss is at least log |S|, with equality only when q assigns each string equal mass.Equality also requires S to carry all of q’s mass.Source: A Consequences of the Kraft inequality · p. 31
  • If q′ gains b bits over q on a set A of strings, then q′ assigns at most 1 − 2^b q(A) mass to the rest of an antichain.In particular, q(A) ≤ 2^-b; on a complete antichain with q a measure, the rest loses at least (2^b − 1)q(A) mass.Source: A Consequences of the Kraft inequality · pp. 31–32
  • For m environments with distinct length-n prefixes, at most 2^b have regret at most b, at least half exceed log(m/2), and mean regret is at least log m.Their discounted regrets sum to at most one.Source: A Consequences of the Kraft inequality · p. 32
  • A Bayes mixture with weight wh on deterministic hypothesis h never exceeds the loss ceiling log(1/wh) on h.The mixture dominates wh times the point measure on h.Source: A Consequences of the Kraft inequality · p. 32

B.1 The singular case

On singular families, a predictor’s measure mass and within-family fit obey a Kraft ledger, and full-mass Bayes mixtures characterize the attainable frontier. For overlapping families, achievable regret profiles are governed by mutual information and its maximizing mixture.

B.1 The singular case

  • For each component μk, 2^-R∞(q; μk) = ck 2^-Dk; on pairwise singular families, these contributions share a Kraft budget of at most one.Here ck is the mass of q’s component absolutely continuous with respect to μk, and Dk measures its within-component misfit.Source: §B.1 · p. 33
  • The Kraft constant is at most one and attained on pairwise singular families; otherwise the mixture predictor has two component terms summing to more than one..Source: §B.1 · p. 33
  • Mixing joint laws with weight δ gives regret at most log(1/δ) on a singular target, while fixed-weight conditional interpolation can incur regret growing linearly with horizon.The interpolation bound assumes deterministic ν and μ’s conditionals are at least γ > 0.Source: §B.1 · p. 34
  • Zero limiting regret on μ forces q to equal μ on every cylinder, making its regret on any other law ν equal to D(ν ∥ μ).The divergence is infinite when ν is not absolutely continuous with respect to μ.Source: §B.1 · pp. 32–34

B.2 Overlapping families

  • For a finite family, a regret profile is achievable exactly when every prior-weighted profile is at least the corresponding mutual information; the minimax regret equals the maximum mutual information.Every Pareto-optimal finite profile is attained by a Bayes mixture, and every full-support mixture is Pareto-optimal.Source: §B.2 · p. 34
  • For overlapping families, log Cn equals the maximum posterior entropy; equality holds only for a Bayes mixture at a maximizing prior, and C∞ = 1 exactly for pairwise singular families.The maximizing prior is recovered as the mixture’s Gibbs weights.Source: §B.2 · p. 34

C.1 Evaluation

This section examines what evaluation results and attainable prediction guarantees can establish, including the limits of certifying conditional agreement beyond covered contexts and probes. It also characterizes how demonstration likelihood ratios govern steering, while posterior concentration alone does not determine the served law.

C.1 Evaluation

  • An N-query sampled evaluation can pass while a predictor disagrees with its reference by at least 1/2 − 1/(2V) on contexts of mass δ.The constructed alternative raises the evaluation failure probability by at most Nδ and increases its loss bound by δ log(2V).Source: §C.1 · p. 35
  • Adaptive protocols can miss disagreement on substantial context sets, and separating all such alternatives requires N ≥ (1 − 2α) ρ̄δ/(2δ).The evasion constant bounds how much query mass a protocol assigns to a set of ρ-mass at least δ; it is at most 2Nδ/ρ̄δ, and the stated sample-size bound is tight up to the given result.Source: §C.1 · p. 36

C.2 Benchmarks, red teaming, scaling curves and contamination

  • Accuracy, scaling curves, and red teaming provide limited evidence about conditionals: accuracy can coexist with near-maximal disagreement, while red teaming only probes searched regions.Scaling laws measure loss ε on the corpus prefix law ρ; control on a set B degrades as ε/ρ(B), and says nothing where ρ has no mass. Emergent metric jumps can reflect the verdict map rather than conditionals. Contamination breaks probe independence, so evaluations should report their probe distribution, resolution 1/N, whether the protocol preceded the model, and whether conditionals were read or sampled.Source: §C.2 · pp. 36–37

C.3 Scale

  • No computable predictor has finite regret on every computable measure, and concrete transformer families can be defeated by a computable sequence.Under an enforced clock, each such family is uniformly computable and one environment gives each member eventually linear regret while M pays at most c*. A diagonal sequence can be computed in polynomial time under the stated schedule, and least-likely continuations yield finite-horizon instances.Source: §C.3 · pp. 37–38

C.4 A model family and the quantifier exchange

  • A single computable environment can defeat every member of a uniformly computable predictor family, but its force on member i may begin only beyond horizon 4i.Finite benchmarks remain compatible with late family members performing well even as every fixed member eventually has linear regret on that environment. Computable selection, ensembling, annealing, or switching is itself a computable predictor, so approaching M requires an uncomputable selection oracle.Source: §C.4 · p. 39

C.5 Asymptotic criteria

  • Asymptotic consistency does not preserve Solomonoff’s regret bound: finite modifications can preserve consistency while changing regret, and computable mixture priors can have arbitrarily poor complexity-relative profiles.On mutually singular families, all predictors with finite regret on every member share the consistency properties, even when their regret profiles differ without bound; frontier membership itself is not tail-invariant. On classes with a deterministic member, computable predictors can satisfy each consistency property yet violate every proposed complexity-based bound.Source: §C.5 · pp. 40–41

D.1 Closure

  • A predictor with zero regret on a computable source has unbounded regret on every mutually singular source, while a full-mass mixture gives a log-weight regret bound on each component.No computable predictor has finite regret on every computable environment, so the simplicity prior must be supplied rather than fitted; class-restricted mixtures with positive computable weights attain regret at most log(1/wi) on component i.Source: §D.1 · p. 41, §D.2 · p. 41

D.2 Attainability and the hierarchy

  • Class-restricted computable Bayes mixtures attain finite regret on each positively weighted source, but no computable predictor achieves a uniform complexity-form bound across a uniformly computable family of distinct deterministic environments.The supplied theorem statement also introduces q′δ = (1 − δ)q + δµq and gives the regret comparison Rn(q′δ; µ) ≤ Rn(q; µ) + log 1/(1 − δ); it characterizes the hierarchy as strict and nonterminating.Source: §D.2 · pp. 41–42
  • If a computable predictor has finite regret on every deterministic sequence of complexity at most s, then its description complexity must satisfy K(q) ≥ s − O(1).The predictor’s diagonal has infinite regret and complexity at most K(q) + O(1), so it cannot be among those sequences.Source: §D.2 · p. 42
  • Mixing any predictor with an enumerated-class mixture gives regret bounds against either component, while the mixture’s sequence probability never exceeds the larger component probability.When the original predictor and mixing weight are computable, the mixture is computable and has its own real-valued diagonal.Source: §D.2 · p. 42
  • A history-dependent selector can trail the better of two component predictors by at least n/2 log((1−γ)/γ) over n steps.In the construction, the selector pays n log(1/γ), with V = 2 and γ < 1/2.Source: §D.2 · p. 43

D.3 Steering by demonstrations

  • If every competitor’s per-demonstration likelihood ratio is at most 2^-r, then m ≥ (log(1/why) + log(1/η))/r demonstrations suffice for served-law total-variation distance at most η.The passage separately gives a lower bound on m for posterior mass on the target hypothesis to reach 1−η when competitors of mass wH′ have likelihood ratios at least 2^-r.Source: §D.3 · p. 43
  • Concentrating posterior mass on a target hypothesis is not the same as steering the served law; zero prior mass on that hypothesis does not preclude steering if others reproduce its predictions.Source: §D.3 · p. 43

D.4 Tools, retrieval and test-time compute

The section distinguishes joint-law mixtures from per-step interpolation and tool selection, and shows that test-time compute changes resource-bounded coverage without escaping computability. Mixtures can carry guarantees on a declared class, but do not add depth beyond their better component.

D.4 Tools, retrieval and test-time compute

  • A mixture of joint laws preserves a regret bound from either component, while fixed-weight conditional interpolation and tool selection can incur regret growing linearly with sequence length.RAG-Sequence marginalizes documents over whole sequences and is a joint-law mixture; kNN-LM and RAG-Token interpolate conditionals, while routing to a tool is selection.Source: §D.4 · p. 43
  • With an enumerated mixture, certified constants apply on the declared class and the network’s uncertified constants elsewhere, without improving on the better component on any string.The components’ competence sets overlap, including in-context copying, preference for simple sequences, and zero-shot numeric extrapolation.Source: §D.4 · p. 43
  • Chain of thought and search leave the end-to-end map computable, changing resource-bounded coverage at an enumeration cost exponential in description length S.The diagonal argument applies relative to the same retrieval or tool resources queried by the pipeline.Source: §D.4 · p. 43

E Training: certification, mixtures and refitting

The section develops finite-horizon bounds linking pretraining loss, task regret, and allocation across data sources, then examines how post-training and refitting alter that allocation. Its results distinguish certified guarantees from reallocation effects and identify calibration and checkpoint choice as practical consequences.

E Training: certification, mixtures and refitting

  • For any event, pretraining divergence bounds its probability under the predictor, yielding regret lower bounds on environments that concentrate on events assigned too little mass.For disjoint supports, regret R requires divergence at least log(1/(1−2^-R)).Source: E Training: certification, mixtures… · p. 44
  • As pretraining loss tends to zero, regret converges to the prior mixture’s regret on each task, but singular families with vanishing prior weights still permit fixed excess regret.On singular families, a mixture can trade higher pretraining loss for lower regret on tasks outside its selected subset.Source: E Training: certification, mixtures… · p. 45
  • The excess-loss ledger decomposes task regret into a log inverse allocation term and a task-to-conditional divergence, with equality under disjoint-support conditions.The ledger’s weighted divergences sum to at most the pretraining divergence.Source: E Training: certification, mixtures… · p. 45
  • On horizon-singular sources, mixture regret is log(1/w); doubling a source weight below one-half buys one bit there and costs log(1/(1−2w)) bits on each other source.For finite source sets, the minimax mixture is uniform; repeated documents up-weight their source, while deduplication is the minimax point.Source: E Training: certification, mixtures… · p. 45, §E.1 · p. 47

E.1 Post-training, data mixing and calibration

  • KL-regularized post-training produces a Gibbs tilt whose regret change varies with environment reward, and it is a task-family prior reallocation only when reward is constant within each singular task.A KL budget alone does not bound the affine price of reallocation.Source: E Training: certification, mixtures… · p. 46, §E.1 · p. 47
  • Using one complete-string reward and one coefficient across prompts makes exact per-prompt optimizers conditionals of a single joint tilt; boundary-dependent rewards or coefficients can break this coherence.Practical PPO and DPO runs do not reach the exact optimizer.Source: E Training: certification, mixtures… · p. 46, §E.1 · p. 47

E Training: certification, mixtures and refitting

  • Maximum-likelihood refitting on generated data preserves Kraft sum one but almost surely reaches a vertex, assigning infinite divergence against the original mixture.A Dirichlet-smoothed refit instead maintains a weight floor and bounds each task’s regret by log(2N + |J|).Source: E Training: certification, mixtures… · p. 46

E.1 Post-training, data mixing and calibration

  • Post-training reallocation is associated with reduced calibration or diversity in reported settings, so reports should identify whether they evaluate a base or post-trained checkpoint.The paper distinguishes calibration under the served post-trained allocation from calibration against the pretraining prior.Source: §E.1 · pp. 47–48

F.1 Context windows

This section examines how context windows and related constraints—including tokenisation, decoding choices, and resource limits—shape predictors’ guarantees and what they can inherit. It develops supporting analyses of memory and regret limits, specific costs or failures, and the scope of the results.

F.1 Context windows

  • A window-W predictor’s least regret is MemW_n(µ), attained by the corresponding time-aware and window conditionals.For stationary mixtures, the memory rate is zero exactly when all positively weighted sources share a W-window conditional kernel; stationarity is required for this dichotomy and the associated cap.Source: §F.1 · pp. 48–49
  • A mixture’s weighted regret decomposes into information about its component identity plus regret under the mixture law.For a stationary mixture, MemW_n(ξw)/n converges to rW(w), bounded by excess entropy; when W < ℓ, the periodic source ωℓ incurs memory (n − ℓ)+ log V, while a computable mixture achieves regret at most log ℓ + 2 log log ℓ + O(1).Source: §F.1 · p. 48

F.2 Temperature

  • For i.i.d. sources with finite original regret, every temperature T ≠ 1 incurs asymptotic per-step regret at least D(θ ∥ θT), positive unless θ is uniform on its support.Sampling from a temperature-adjusted predictor does not reveal the scale of q: for the stated binary example, QT(1) = 1/2, unlike the first-symbol probability under the tempered joint law.Source: §F.2 · pp. 50–51

F.3 Floors, precision and truncation

  • A probability floor ϕ caps each-step surprisal at log(1/ϕ), but forces every sequence’s loss to be at least n rϕ; smoothing adds at most n rϕ.Top-k or qualifying top-p truncation assigns zero probability to some symbol at every context, yielding infinite regret on full-prefix-support sources and infinite loss on its own diagonal.Source: §F.3 · p. 51

F.4 Tokenisation

  • Marginalizing token probabilities over all tokenisations yields a character semimeasure and transfers dominance constants and regret bounds to characters.For universal semimeasures, tokenisation invariance holds up to constants exponential in K(A); canonical-tokenisation scoring instead can lose noncanonical-token mass, and dominance need not transfer.Source: §F.4 · pp. 51–52

F.5 Truncation, tokenisation and reasoning traces

  • Truncation trades guarantees on improbable continuations for sample quality on probable ones, and zeroing probabilities creates dogmatism with infinite loss on some sources.Smoothing to floor ϕ costs at most n log(1/(1 − (V − 1)ϕ)) bits; with logits capped at 30 and V = 218, the stated floor costs about 10^-26 bits per step, while the floor caps surprisal at about 105 bits.Source: §F.5 · p. 52

Tokenisation.

  • Claims about induction on text concern the character law marginalized over tokenisations, through which Solomonoff dominance constants pass up to O(K(A)) bits.Scoring only a canonical tokenisation loses model mass on noncanonical token strings, and dominance does not pass through that score.Source: Tokenisation · p. 53
  • Tokenisation can create zero-probability continuations and distort character-level coherence or surprisal–description-length analyses; rendering and discarded mass must be reported.Non-canonical token sequences carry signal, while restricting and renormalising to a rendered alphabet discards model mass. Nominal context is the proven discard boundary; treating effective context as the window is only an analogy, and chain-of-thought/search remain computable predictors subject to diagonals, while expanding end-to-end coverage.Source: Tokenisation · pp. 53–54

G.1 Proofs

  • A served conditional with positive residual cannot come from conditionals of one probability measure, while a zero residual at one event and history is necessary but not sufficient for coherence.For semimeasures the conditional identity holds with an inequality, with the gap representing lost mass; incoherent served prices permit a riskless arbitrage. Exchangeable Bayesian demonstrations yield permutation-invariant predictions, and the proofs also establish coding-loss bounds for consistent hypotheses.Source: §G.1 · p. 54

G.2 The implied prior, distillation and merging

  • The implied-prior fit is attained and has zero residual exactly when a Bayes mixture agrees with the model on the probe set; fitted values are unique, but mixture weights may not be.The implied coding is Kraft-valid, and bounded coding-distance from a declared code holds exactly when the priors are equivalent up to a constant. Conditional distillation can certify membership when loss vanishes, but its infimum may not be attained; conditionals identify weights only within co-consistency components, and a full-support floor handles off-class allocation.Source: §G.2 · p. 55
  • Merging of opinions and any observed per-step excess tending to zero survive finite modification and prior reweighting, so they evidence coverage rather than good coverage.This invariance is stated for merging of opinions and follows from the cited tail-invariance and prior-reweighting results.Source: §G.2 · p. 56

G.3 The window excess over KT

  • For a Jeffreys mixture over a V-symbol source, the least expected per-step window excess is rW = (V − 1)/(2W ln 2)(1+o(1)) bits, attained asymptotically by KT.Wholestream KT has expected cumulative excess (V − 1)/2 log n + O(1), and every window-W predictor trails it in expectation by at least (n − W)rW − (V − 1)/2 log n − O(1); the approximation requires W ≫ V.Source: §G.3 · p. 56

G.4 A corpus as one hypothesis

  • A perfect corpus predictor receives implied prior weight 1 on its corpus law, but that fit establishes neither a prior over English nor structure within the corpus law.The corpus supplies an exact likelihood for one hypothesis; Paper B checks membership residual, corpus weight, and distillation on known reference systems.Source: §G.4 · p. 56

H Related work and provenance

  • The provenance appendix labels results as known, derived, sharpened, new, or discussion, and attributes resource-bounded results to prior work while noting the added explicit-constant formulation and open exponential-gap question.It also identifies the KL-implied-prior result as new and elementary.Source: H Related work and provenance · p. 58

I Resource-bounded inheritance

  • The resource-bounded analysis fixes a deterministic multitape reference machine and assumes universal simulation with time overhead σ.The machine model uses binary programs and measures program length and per-step time on the fixed reference machine.Source: I Resource-bounded inheritance · p. 59
  • On budgeted environment classes, diagonalization forces linear regret from bounded predictors, while a clocked mixture achieves regret at most S.The lower bounds are pointwise in the budget, so sublinear worst-case regret violates the budget inequality at some n, not necessarily infinitely often. The uniform diagonal rate depends exponentially on t(1), and a slope independent of t(1) remains open.Source: I Resource-bounded inheritance · pp. 60, 62

Data and code availability

  • The paper releases the code and seeds for its numerical illustrations and frontier figure, with one command to regenerate them.The code is under the MIT License and outputs under CC BY 4.0; the manuscript notes that the URL/DOI is to be inserted.Source: Data and code availability · p. 62

Use of AI tools disclosure

  • The authors report using generative AI tools for editing, literature search, derivation checks, objections, organization, and accompanying-code work.They state that the definitions, theorems, proofs, and interpretations originated with the authors and were verified by them, and that they take responsibility for the manuscript.Source: Use of AI tools disclosure · p. 62
Loading 2610.14007v1…