CS Paper Radar

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

Luan Ozelim, Abicumaran Uthamacumaran, Hector Zenil

cs.LG cs.AIcs.IT ·submitted 2026-09-28 19:01 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors

cs.LG stat.ML ·2026-10-21 ·Qian Li, Shang-Hua Teng
theory similarity 0.77
Abstract · 24 pages

Why large language models trained via log-loss minimization over massive and diverse datasets exhibit broad capabilities and generalizable skills is not yet fully understood. Grau-Moya et al. (ICML 2024) offer a conceptual explanation through the lens of meta-learning: if sequence-generating environments $ν$ are drawn from a prior $w_ν$, minimizing population log-loss recovers the corresponding Bayesian mixture predictor $ξ=\sum_νw_νν$. In the idealized limit in which $w$ is a universal prior, the optimal predictor corresponds to Solomonoff universal induction. Practical machine learning algorithms, however, generally produce only \emph{approximately} optimal predictors. This raises a natural question: \emph{Does the prediction performance remain robust under approximation}? In this paper, we first provide a tight bound on the worst-case effect of approximation on prediction error. We show any predictor $ρ$ satisfying $D_{KL}(ξ\|ρ)\leq η$ retains bounded cumulative-expected-squared prediction error. However, while the Bayesian mixture predictor $ξ$ has error $O(\log(1/w_μ))$ in an environment $μ$, we establish a tight $Θ(η/w_μ)$ bound on the excess error of $ρ$ relative to $ξ$. Thus, approximation can substantially degrade performance in environments assigned small prior probability. In sharp contrast, when environments are averaged according to prior $w$, we prove that the excess prediction error is only $O(η)$. Furthermore, we establish a distribution-shift theorem for dominated shifts from a training prior $w$ to a test prior $w'$, interpolating our average-case and worst-case guarantees. Finally, we extend our robustness analysis to a finite-sampling setting relevant to learning universal predictors with neural networks and Transformers, where $D_{KL}(ξ\|ρ)$ could be unbounded. [For the full abstract, see the paper.]

0.29

Solomonoff Induction with Reflective Oracles

cs.CC ·2026-11-10 ·Damini Kusum
similarity 0.66
Abstract

We study predictive properties of a reflective variant of Solomonoff induction formulated using reflective oracles (Fallenstein et al. 2015, Wyeth et al. 2025). We show that the resulting optimal predictor succeeds against computable predictive strategies that specify only part of the data-generating process. The argument relies on the fact that hypotheses computable from the predictor's own conditional probabilities remain within the reflective hypothesis class. In particular, the predictor learns incomplete models specified by computable interval restrictions on next-bit probabilities. We also establish weighted forms of unbiasedness and calibration. Finally, we discuss whether an optimal predictor's conditional probabilities suffice to compute every hypothesis in the reflective class.

0.17

Approximate Universal Prediction under Interaction

cs.LG stat.ML ·2026-10-24 ·Richard Cornelius Suwandi
similarity 0.63
Abstract

Bayesian mixtures, and Solomonoff induction in particular, provide an idealized model of prediction learned by minimizing population log loss, and they underlie universal agents such as AIXI. An agent that plans with an approximation of such a predictor decides where that predictor is evaluated, and a planner can be drawn toward branches on which its model is optimistic. We study which approximation guarantees survive this feedback. For normalized finite-horizon causal mixtures, the transfer coefficient factors into a policy likelihood ratio and task evidence available before each prediction, so task rarity and action-branch rarity can compound. Within one fixed universal mixture, infinitely many computable environments admit excess prediction error of order $κη\,2^{K(μ)}$, where $η$ is the training KL budget and $κ$ measures policy coverage. This order is sharp, and for each target a computable predictor attains it at a suitable finite horizon, so computability alone does not remove the penalty. For bounded returns, value error is controlled by the probability of entering a poorly covered branch plus a square-root term in $η$. Both terms are necessary, and finite maximum coverage ratios are not required. Motivated by the mentor override of Golden Handcuffs, we derive margins for preserving deferral decisions and conditional KL budgets with an unavoidable inverse-history-probability penalty, and a counterexample separates agreement of deferral decisions from task-wise event avoidance. The guarantees apply to any predictor architecture that meets explicit population approximation and coverage conditions, which gives concrete targets for implementing idealized universal agents.

0.12

Understanding Generalization Requires Universal Induction

cs.AI stat.MLcs.ITcs.LG+1 ·2026-09-28 ·Aram Ebtekar, Marcus Hutter, Danica J. Sutherland
top venue similarity 0.61
Abstract · Published at NeurIPS 2026 Position Paper Track

Classical statistical theory is insufficient to explain the successes of general-purpose AI models, because it depends on handcrafted inductive biases that it cannot justify. No Free Lunch (NFL) theorems force any learner that beats chance on some environments to underperform on others. We might hope that past experience informs which environments to expect, but NFL applies equally to meta-learning. Thus, any method that makes meaningful predictions necessarily begins with an inductive bias external to the data. Choosing to bias toward short programs yields Solomonoff induction (SI), whose performance is competitive against all computable learners - albeit up to "constants" that become large when comparing against specialized methods that exploit background information. We therefore relativize SI to an information vantage point, biasing toward short programs with access to all preexisting information. This reframes the inductive bias: instead of seeking some absolute notion of simplicity, we favour accessibility with respect to our vantage point. An algorithm can only outpredict the relativized SI to the extent that its code contains additional information about the data, and no algorithm can generate such information. While SI is incomputable and hence not a practical algorithm, it provides a formal optimum for inference in the limit of infinite compute, and there is evidence to suggest that frontier AI systems roughly approximate it. Thus, the only known answer to meta-NFL is rooted in algorithmic information theory, which we should expect to play a fundamental role in explaining the generalization behaviour of modern (and future) AI systems.

0.66

Rolling Conformal Prediction in Sequential Model Training

cs.LG math.STstat.MEstat.ML ·2026-09-22 ·Chen Cheng, Ruiting Liang, Rina Foygel Barber
similarity 0.61
Abstract · 42 pages, 5 figures

We introduce Rolling Conformal Prediction (rolling-CP), a distribution-free predictive inference method for the setting of sequential model training. Specifically, given a data stream $(X_1,Y_1),(X_2,Y_2),\dots$, at each time $n$ the trained model may depend on the observed history $\{(X_i,Y_i)\}_{i<n}$. This setting arises naturally in modern sequential training, including one-pass training over massive datasets and continual fine-tuning or test-time adaptation of language models during deployment. Rolling-CP first calibrates each incoming observation against the current predictor and then rolls it into future training. In this way, we avoid the need for data splitting. Remarkably, although the models at times $n=1,2,\dots$ may have entirely different properties and accuracy levels, for exchangeable data it is nonetheless possible to establish a guarantee of marginal coverage, with a familiar universal factor-two guarantee (a worst case guarantee of $1-2α$ coverage, as compared to the target level $1-α$), without any assumptions of stability or any restrictions on the model training process. For i.i.d. data streams, we further prove high-probability training-conditional validity uniformly over time; under stability conditions, coverage guarantees sharpen towards $1-α$. Numerical experiments on sequential regression, multiclass SGD, and one-pass neural-network training further demonstrate the practical effectiveness of rolling-CP.

0.33

Certification-Enhanced Generalization Bounds

cs.LG ·2026-10-05 ·Leo Elmecker-Plakolm, Matthew Wicker
top venue similarity 0.61
Abstract · Accepted at NeurIPS 2026

We investigate the use of formal methods to provide tight and sound generalization bounds for learning algorithms. By casting the traditional notion of algorithmic stability as a specification to be verified, we demonstrate that recent advances in reachability analysis can yield provable bounds on the generalization of a given model and algorithm on a sample dataset. As sample-specific algorithmic stability is insufficient to bound the usual distributional notion of generalization, we develop a novel concentration inequality to connect the sample-specific results of formal certification algorithms to the required distributional analysis for bounding the expected generalization gap. The resulting framework enables the analysis of prior generalization bounds to extend far beyond their original restrictive assumptions. Our approach computes sound bounds on the expected generalization gap in a constant number of algorithm runs without making any analytical assumptions on the algorithm; to achieve non-vacuous bounds we only require that the certified reachable parameter set is bounded --- a condition that we do not assume but formally verify. In practice, we demonstrate that our framework provides formal generalization guarantees that are orders of magnitude tighter than alternative sound computational approaches at scales ranging from toy datasets to fine-tuning classification heads on top of modern large language models. While we implement certification-enhanced versions of several well-known stability results, future extensions of our approach will enable tighter bounds and enhanced practical adoption across the spectrum of modern generalization bounds.

0.32

Matchability-Aware Conformal Prediction for Open-Ended Language Model Generation

cs.CL stat.MLcs.LGstat.ME ·2026-11-07 ·Ilia Azizi
top venuecode/data similarity 0.59
Abstract · Accepted at NeurIPS 2026. Project page: https://unco3892.github.io/caelum/

Large language models (LLMs) often do not produce calibrated uncertainty estimates for their answers. We propose CAELUM, a framework that builds semantic prediction sets while separating aleatoric from epistemic uncertainty. CAELUM samples answers using an ensemble of clarification prompts, clusters them by semantic equivalence, and estimates the aleatoric and epistemic components via kernel-based von Neumann entropy before calibrating nonconformity scores with split conformal prediction. We use a weight $w_λ(x)=1+U_{\mathrm{ale}}(x)+λ\,U_{\mathrm{epi}}(x)$ to control for the contribution of the epistemic uncertainty of each instance and fit a coefficient $λ^\star$ to minimize prediction set size. When the objective is nonflat and selection is stable across splits, $λ^\star$ could be a diagnostic, where large values may indicate epistemic dominance (retrieve, abstain) and $λ^\star\to 0$ aleatoric dominance (clarify). For individual queries, a log ratio $R(x)$ compares the weighted epistemic component with the aleatoric component. Theoretically, we demonstrate that the coverage is capped by matchability, the fraction of items whose reference answer appears in any sampled cluster. Empirically, this matchability can be predicted from the original question features using a lightweight classifier. We use those predictions to define a stratum and derive a conformal coverage bound within it. Across 30 LLM and dataset combinations (4-32B), mean coverage is 0.74 in the learned stratum versus 0.65 overall, averaged over the 78 evaluations using the learned classifier. Project page: https://unco3892.github.io/caelum/

0.44

Credal Large Language Models for Semantic Commitment under Uncertainty

cs.CL cs.AIcs.LGstat.ML ·2026-08-24 ·Shireen Kudukkil Manchingal, Sofiia Nikolenko, Fabio Cuzzolin
similarity 0.59
Abstract · 45 pages, 10 figures, 19 tables

Large language models (LLMs) often produce fluent but incorrect answers with unwarranted confidence. A central limitation is that standard LLMs represent uncertainty through a single predictive distribution, conflating epistemic ignorance with genuine ambiguity. We introduce Credal Large Language Models (CLLMs): an ensemble of LoRA adapters induces a credal set whose lower and upper probabilities expose the spread of plausible predictive distributions rather than collapsing to a single softmax output. From this representation, we derive a single commitment rule: the model commits to an answer only when its lower probability exceeds the upper probability of every alternative, and otherwise returns the set of answers that no plausible predictor rules out. We apply this commitment rule at two depths: Credal Token Commitment (CTC) applies it to answer tokens from one ensemble forward pass, which decides constrained answers without any generation; for open-ended answers, credal decoding extends a partial answer only when no completed answer dominates it, so that the completions produced are those the plausible predictors license, and Credal Semantic Commitment (CSC) applies the rule to their meaning clusters. We evaluate CLLMs with Gemma-2-9B, Llama-3.1-8B and Qwen2.5-7B on OpenBookQA, CoQA, TriviaQA and ARC-Challenge. On multiple choice, CTC commits on 73-91% of questions at 89-98% accuracy, returns sets of 1.1-1.5 options containing the gold one on 89-98%, and its intervals contain the observed accuracy in 24 of 30 confidence bins without calibration; corrupted context lowers commitment from 87-92% to 65-71%, and on Gemma the credal bound detects corruption better than every baseline. On open-ended QA, CLLM outperforms semantic entropy and Laplace-LoRA at a fixed coverage by up to 19% and 9.5% absolute accuracy on CoQA and TriviaQA with context, for every backbone.

0.44