Understanding Generalization Requires Universal Induction
Aram Ebtekar, Marcus Hutter, Danica J. Sutherland
NeurIPS 2026 Position Paper Tra
stat.ML, cs.AI, cs.IT, cs.LG, math.ST
2026-09-28
Relativized Solomonoff induction bounds extra log-loss regret by a predictor's algorithmic mutual information with the data, the only known answer to meta-NFL.
Statistical learning theory has a clean theorem for small hypothesis classes: training error tracks test error. VC dimension, uniform convergence, and structural risk minimization all buy a bound on the generalization gap. None of them say which small class actually contains the target. That inductive bias is left to the human. For a specialist the outsourcing is tolerable. For a generalist thrown at increasingly arbitrary tasks, it is the hole.
No Free Lunch makes the hole countable. On finite input and output alphabets, every unused label is equally common among functions that match the training set. Any algorithm that sees only those labels loses to chance on most targets. Ask instead which inductive bias to use, and the same counting argument returns as meta-NFL. Experience, meta-learning, and Darwinian evolution treated as learning from ignorance cannot produce the first non-uniform prior. Non-overfitting and non-underfitting can each be proved. Jointly, they cannot.
A toy count from the paper. Learn f : Z19 → Z19 given f(4)=4, f(8)=8, f(11)=11. The identity f1(x)=x predicts 0 at the origin. A cubic f2 fits the same three points and predicts 9. Each function sits in some class of size 361; the full cubic class has 130,321 members. Theory says pick a small class. It does not say which one. Degree is a terrible heuristic for f3(x)=⌊x/10⌋.
A predictor that beats chance has to start with a bias that is not in the data. Bias toward short programs and Solomonoff induction appears: a mixture over all computable predictors, weights exponential in program length. In sample efficiency it competes with every computable expert, with regret at most log(1/wi), independent of the sequence. Against a specialist that already encodes background knowledge, that additive constant can dwarf the comparison. Swap the description language and "short" moves with it. Every prior can be sold as simplicity.
Relativize SI to an information vantage point. Fix a universal monotone Turing machine U and an oracle tape q that holds what the observer already has: local disk, a web snapshot, libraries, downloadable pretrained models. The prior M^q(x) is the fraction of random programs whose output, given q, starts with x. The bias is accessibility from this vantage point. Borges' Library of Babel, which contains every book and privileges none, does not help. A pointer to one volume can be as long as the volume.
Theorem 3 gives the regret shape. Log-loss regret of M^q against any predictor μp is at most the algorithmic mutual information MI^q(p:x) between that code and the data, relative to q, minus the reverse term MI^p(q:x). Theorem 5 is conservation: a short meta-program r that writes p from q and randomness has expected mutual information at most the length of r. Information is not created. A designer can copy existing bits into q. Extra bits that are useful about x cannot be manufactured.
Position paper. No new benchmark. The load-bearing claims are the theorems.
| Setting | Claim |
| Uniform prior, or uniform draw among consistent hypotheses | Unseen-point posterior 1/k; no generalization |
| Classical SI (empty oracle) | Competitive with all computable predictors; constants can explode vs specialists |
| Oracle SI M^q | regret at most MI^q(p:x) minus MI^p(q:x), hence at most MI^q(p:x) |
| p written by a short meta-program r | expected MI at most the length of r; almost never beats M^q |
On neural nets the paper only collates prior work. In wide feedforward nets, parameter-space volume for functions of much narrower nets is disproportionately large, so a random interpolator looks like a narrow teacher. Narrow nets sit close to small circuits; recurrence plus external memory reaches Turing completeness; transformers with chain of thought move that way. In-context learning in large language models has been read as Bayesian inference, and in some accounts as SI itself. Grau-Moya et al. train a network to approximate SI in context on synthetic data from time-bounded random programs, with no real data. Under NFL, fitting those programs cannot explain strong behavior on unseen inputs. The quantity to measure is whether the architecture already carries a pseudo-universal bias before any training set arrives.
There is no algorithm to ship. SI is uncomputable; the halting problem blocks it. The offering is a formal optimum at unbounded compute, and a regret shape that generalist systems can aim at when their compute dwarfs an expert μp. Gaps from that ideal, computational bounds included, become the baseline for reading real systems.
Goldblum et al. (2024) argued that shared low-complexity structure lets one model class generalize across domains. The direction is fine. Low complexity in which language, and why, still loops back to Corollary 2 once the argument leans on empirical success. Accessibility stops in a cleaner place: M^q is not guaranteed to be accurate, and no reachable alternative is substantially better. Agent models built on M^q, AIXI among them, are named as tools for anticipating future capabilities and safety failures.
SI is uncomputable. Joint optimization of time and sample efficiency is declared out of scope, and time-bounded accessibility is left open. Hidden multiplicative and additive constants depend only on U; in principle U can be chosen so they are small. Against an expert that already hardcodes domain knowledge, that "small" is not calibrated. The claim that a designer cannot create information also leans on a physical Church-Turing thesis.
The suggestion that frontier systems roughly approximate SI is a collage. Parameter-space simplicity bias, Bayesian readings of in-context learning, and training on synthetic programs are citations. Mutual information and regret of a real large model against a concrete q are not measured here. Taking q as "today's web plus local disk" folds most of contemporary engineering into the prior. The story explains a lot and is hard to falsify. Philosophical objections to SI as a gold standard, from McGregor, Herrmann, Neth, and Sterkenburg, are cited; relativization is the reply, not an experimental verdict. An appendix applies the same bound to Boltzmann brains, farther from training practice.