A formal theory of inductive inference. Part II

TL;DR — In 1964 Ray Solomonoff defined the provably optimal sequence predictor: run every program, keep the ones whose output matches your data so far, weight each by 2^{-\ell} where \ell is its length in bits, and predict with the mixture. It is uncomputable, and even crude approximations were hopeless on machines doing ~10⁵ operations per second. Sixty years later, large language models look suspiciously like amortized approximations of exactly this object, LLM-guided program synthesis makes bounded-resource versions empirically testable, and Solomonoff's framework may be the closest thing we have to a theory of why scaling works. This is worth an afternoon of your time.

The idea as Solomonoff had it

The setting in 1964: Carnap's inductive logic was the reigning formal theory of confirmation, the perceptron was five years old and controversial, and "learning" mostly meant fitting parameters of hand-chosen models. Solomonoff's move — sketched in Part I and worked through concrete examples in Part II — was to refuse to choose a model class at all. Take all computable hypotheses and let description length arbitrate among them.

Concretely: fix a universal Turing machine U. The prior probability of a binary sequence x is

where the sum runs over all programs p whose output begins with x, and \ell(p) is the program's length in bits. Prediction is then just conditioning: the probability the next bit is 1 is M(x1)/M(x). Every program consistent with your observations votes, and shorter programs get exponentially larger votes. Occam's razor stops being a heuristic and becomes a theorem about prefix codes: a program of length \ell occupies a 2^{-\ell} fraction of code space, so simplicity is prior probability.

Part II is where Solomonoff shows this isn't empty formalism. He grinds through concrete cases: sequences with symbols of unknown frequency, where the universal prior approximately recovers Laplace's rule of succession \frac{n+1}{n+2} — a sanity check that the alien-looking definition reproduces two centuries of sensible statistics — and induction over phrase-structure grammars, an early formalization of grammar learning from positive examples. The paper is heuristic by modern standards; the sharp theorems came later. The one worth knowing: Solomonoff proved in 1978 that M's cumulative expected squared prediction error against any computable source \mu is bounded by roughly K(\mu)\ln 2, where K(\mu) is the length of the shortest program computing \mu. Total error, over an infinite sequence, bounded by a constant proportional to the complexity of the truth. No learner can do better than this up to that constant. It is the optimality result that everything from MDL to AIXI is built on.

Why it could not work then

Two walls, one fundamental and one practical.

The fundamental wall: M is uncomputable. You cannot know which programs halt, so you cannot even enumerate the sum. M is lower-semicomputable at best — you can approximate it from below, forever, without knowing how close you are. Solomonoff knew this and said so; the 1964 papers are explicit that the models are idealizations.

The practical wall is what matters for our purposes, because bounded approximations were also hopeless. The obvious approximation is: enumerate programs up to length n with a time cutoff t, keep the consistent ones. That costs on the order of 2^n \cdot t machine operations. In 1964 the workhorse was the IBM 7094: roughly a few hundred thousand operations per second and about 150 KB of core memory. Searching all programs of even 30 bits with a modest time budget is ~10¹⁰–10¹¹ operations — weeks of machine time on a computer that cost millions and was shared by a department — and 30-bit programs express almost nothing interesting. Levin's universal search (1973) later showed you can interleave program executions to get asymptotic optimality, but with multiplicative constants of 2^{\ell} that are astronomical for any \ell that matters. There was no gradient to descend, no way to amortize search across problems, and no corpus to learn a proposal distribution from. Solomonoff spent the rest of his career on approximation schemes and never found a tractable one.

Note what the chart implies: even 13 orders of magnitude of raw compute only extends exhaustive search from ~30-bit to ~70-bit programs, because the cost is exponential in \ell. Brute force was never going to be the answer. The unlock had to be something that skips the enumeration.

What changed

Three things, in ascending order of importance.

Compute and data, obviously. But as above, this alone doesn't beat 2^\ell.

Prediction = compression became operational. The identity between log-loss and code length means any autoregressive model is a compressor, and Solomonoff's theory says the best predictor is the best compressor. Delétang et al. ("Language Modeling is Compression," 2023) made this concrete: pretrained LLMs, used as arithmetic-coding models, compress not just text but images and audio competitively with domain-specific codecs. An LLM's training loss is literally its code length per token; scaling laws are statements about how fast we approach the entropy floor plus a complexity term. Solomonoff's framework is arguably the right lens for what those curves mean: the irreducible loss term is the source entropy, and the reducible term is the price of not yet having found the short programs.

Learned proposal distributions over programs. This is the real revival. An LLM trained on human code and reasoning is a proposal distribution q(p \mid x) over programs given data — precisely the object that makes bounded Solomonoff induction tractable. Instead of enumerating 2^{70} programs, you sample a few thousand from a model that already knows what plausible short programs look like. This is what the strongest ARC-AGI approaches do: sample thousands of candidate Python programs from an LLM, execute them against the training pairs, keep the consistent ones, predict with the survivors. That pipeline is the figure above, with the uniform enumeration replaced by a learned prior.

There is also direct evidence for the "LLMs approximate M" framing: DeepMind's "Learning Universal Predictors" (Grau-Moya et al., 2024) trained transformers on data generated by random programs on a UTM and showed the networks' predictions approach the Solomonoff predictor on that distribution — meta-learning converges toward the universal mixture when the task distribution is itself universal. That's a controlled, small-scale result, but it's the cleanest demonstration yet that neural amortization of Solomonoff induction is a real phenomenon rather than a metaphor.

What a serious 2026 revival looks like

Build an explicit bounded-resource Solomonoff predictor and test whether it beats — and explains — pure neural prediction:

1. Proposal: an LLM generates candidate programs p (in Python or a small DSL) conditioned on the observed sequence or ARC grid pairs.
2. Filter: execute each candidate with a time budget; keep those consistent with all observations.
3. Weight: score survivors by 2^{-\ell(p) - \log t(p)} — description length plus log runtime. This is Schmidhuber's speed prior (2002), the principled fix for the halting problem: it's computable and penalizes slow programs. Use compressed token count under a fixed code as \ell.
4. Predict: mixture over survivors, exactly as Solomonoff prescribed — not argmax over the single best program. The mixture is what carries the optimality guarantee, and it gives calibrated uncertainty when several short hypotheses disagree.

Keep from 1964: the mixture, the length-based weighting, the refusal to fix a hypothesis class. Replace: uniform enumeration with LLM proposals, the uncomputable prior with the speed prior, the abstract UTM with a real interpreter.

Two experiments matter. First, ARC-AGI as the benchmark, because it is explicitly designed so that each task has a short generating program and few examples — the Solomonoff regime, where a 5-example task is hopeless for gradient descent but trivial once you find the 50-bit program. Compare the explicit mixture against direct LLM transduction at matched compute, and measure whether performance tracks the description length of the true rule. Second, the scaling-law question: for sequence families with known Kolmogorov complexity (generated by random programs, à la Grau-Moya), test whether LLM in-context loss curves match the Solomonoff regret bound \sim K(\mu)\ln 2 — i.e., whether the model behaves as if it is paying a one-time cost proportional to the complexity of the source, then predicting near-optimally. If yes, "in-context learning" gets a quantitative theory.

Already tried, vindicated, and still open

Vindicated: the theoretical line is secure — Kolmogorov complexity, Levin search, Rissanen's MDL as the practical statistical offshoot, Hutter's AIXI extending Solomonoff to sequential decision-making, with AIXI-tl and the Monte-Carlo AIXI approximation (Veness et al., 2011) as bounded versions. Empirically, the compression-prediction identity is demonstrated at LLM scale, neural amortization of M is demonstrated at toy scale, and hybrid LLM-plus-execution program search is state of the art on ARC-style tasks. DreamCoder (2021) showed the library-learning version: amortize search by growing a DSL, which is exactly compressing the prior.

Open, and genuinely so: Does the 2^{-\ell} weighting matter in practice, or does the LLM's learned prior dominate everything? (My read: the execution filter clearly matters; the explicit length penalty is undertested.) The universal prior is only defined up to the choice of UTM — a O(1) constant in theory, everything in practice — and "LLM trained on human data" is a choice of reference machine whose inductive consequences nobody has characterized. Whether frontier-model scaling laws quantitatively match universal-prior convergence is, as far as I know, unresolved; the claim is plausible and testable, not established. And the mixture-vs-argmax question — whether keeping the full posterior over programs buys robustness worth its cost — is wide open at scale.

Where to read it

The paper: doi.org/10.1016/s0019-9958(64)90131-7 (bibliographic details verified; open access). Read Part I first for the four models, Part II for the worked inductions. Alongside: Li & Vitányi's An Introduction to Kolmogorov Complexity and Its Applications for the rigorous treatment the 1964 papers lack; Hutter's Universal Artificial Intelligence for the sequential-decision extension; Schmidhuber's "The Speed Prior" (2002) for the computable variant; Delétang et al., "Language Modeling is Compression" (2023) and Grau-Moya et al., "Learning Universal Predictors" (2024) for the modern empirical bridge. Solomonoff waited fifty years for hardware to catch up to his prior; it finally has, wearing a transformer.