CS Paper Radar

Solomonoff Induction and Singular Integrals

Will Troiani, Daniel Murfet

cs.IT ·submitted 2026-09-01 01:21 UTC · v1
theory

Abstract

The Solomonoff distribution $M$ assigns an a priori probability to a finite binary string $z$ by summing over all programs whose output begins with $z$, weighting a program of length $\ell$ by $2^{-\ell}$. Thus, likely strings are those with many short explanations. This appears to be a purely discrete notion of complexity. However, Riemann sums are also countable. We show that the sum defining $M$, suitably reorganised, contains Riemann sums approximating the Bayesian evidence of any computable statistical model. These evidence integrals are singular integrals whose asymptotics are governed by Singular Learning Theory and, through it, by invariants of algebraic geometry. Concretely, for every computable Bayesian model, we construct a single monotone Turing machine whose induced semimeasure agrees with the evidence $Z_n$ up to a uniform multiplicative constant. If the model also satisfies the hypotheses of Watanabe's free-energy asymptotics, then a sample $X^n=X_1\cdots X_n$ drawn i.i.d. from the true distribution satisfies $-\log M(X^n) \le nL_n(w_0)+λ\log n-(m-1)\log\log n+O_{\mathbb{P}}(1)$, where $L_n$ is the empirical loss, $w_0$ is an optimal parameter, $λ$ is the learning coefficient, and $m$ is its multiplicity. Thus the learning coefficient, a geometric measure of model simplicity, appears within the Solomonoff distribution as the coefficient of $\log n$ in an upper bound on code length.

Comment
19 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Solomonoff induction of selected bits and online classification

cs.IT ·2026-10-13 ·Bruno Bauwens, German Kuznetsov
similarity 0.62
Abstract

Solomonoff induction is a general solution for sequence prediction that started the field of algorithmic information theory around 1960. Let $M$ be the universal semimeasure. After observing a string $ω_1 \cdots ω_{n-1}$, it predicts the next bit $ω_n$ to be $b$ with conditional probability proportional to $M(ω_1 \cdots ω_{n-1} b)$. Thus the error of this probability is \[ e_ω(n) = 1 - \frac {M(ω_1 \cdots ω_{n-1}ω_n)} {M(ω_1 \cdots ω_{n-1} 0) + M(ω_{1} \cdots ω_{n-1} 1)}. \] If $ω$ a computable infinite sequence with a self-delimiting description of at most $k$ bits, then $\sum_n e_ω(n) \le k\ln 2+O(1)$. Lattimore, Hutter and Gavane consider the problem of predicting computable patterns in a sequence, for example, the pattern of repeated bits $ω= 00\,11\,00\,00\,11\,00\cdots$ They show that the error probabilities of the bits fixed by a computable pattern have limit zero, for example, for repeated bits, one has $\lim_n e_ω(2n) = 0$. We show that for some computable pattern, the sum of $e_ω(n)$ over positions $n$ from the pattern is not bounded. However, the sum of squares $(e_ω(n))^2$ is bounded exponentially in the program length of the pattern. It is also shown that bits of $ω$ that are fixed by a computable classification function $f:\{0,1\}^* \rightarrow \{0,1\}$, converges faster: the sum of $(e_ω(n))^2$ is bounded by a polynomial in the program length for programs whose runtime is bounded by any fixed computable time bound.

0.22

The Complexity of Unpredictability

cs.CC ·2026-11-04 ·Aryan Agarwala, Dani Dorfman
theory similarity 0.58
Abstract

We initiate the study of middle-bit predictors: functions that take as input a string with one missing bit and try to predict that bit. These are closely related to next-bit predictors, a classical object in pseudorandomness. We study the deterministic complexity of computing an unpredictable distribution (UNPRED). Given a list of middle-bit predictors in circuit form and a parameter $ε>0$, output a multiset of strings such that each predictor succeeds with probability less than $1/2+ε$ on a uniformly sampled string from the multiset. We write $\mathsf{UNPRED}^{\mathsf{TC}^1}$ for the restriction to $\mathsf{TC}^1$ predictors. We show that UNPRED offers a unified route towards resolving several major open problems in catalytic computation, the biggest of which is whether deterministic polynomial time (P and FP) can simulate catalytic logspace (CL and SearchCL). It is believed that $\mathsf{SearchCL}\subseteq\mathsf{FP}$. We prove $$\mathsf{UNPRED}\in\mathsf{FP}\implies\mathsf{SearchCL}\subseteq\mathsf{FP}\implies\mathsf{UNPRED}^{\mathsf{TC}^1}\in\mathsf{FP}.$$ Thus, the questions of whether UNPRED is in FP and whether SearchCL is contained in FP are almost equivalent, up to the restriction to $\mathsf{TC}^1$ circuits. We also show that any deterministic polynomial-time algorithm for $\mathsf{UNPRED}^{\mathsf{TC}^1}$ must exploit properties of $\mathsf{TC}^1$ circuits, either in the algorithm itself or in its analysis. To our knowledge, this would also be the first algorithm to use the structure of $\mathsf{TC}^1$ circuits in this way to solve a natural problem, thus advancing our understanding of Boolean circuits. Together, our results provide strong evidence that middle-bit predictors could be the key to unlocking several major open problems in catalytic computation, pseudorandomness, and Boolean circuit complexity.

0.26

The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach

cs.AI cs.CCcs.IT ·2026-08-17 ·Rafael Pass
similarity 0.58
Abstract

In a world where valuable artifacts are increasingly created, completed, or processed by LLMs, the central economic question is not only what the LLM can produce, but what \emph{value} remains in the inputs (i.e., the prompts) we provide to it. Given a prompt, hint, critique, problem statement, or partial solution that helps an LLM produce an artifact $z$---a proof, program, design, or scientific hypothesis---how should we measure the value of that input? Intuitively, an input is valuable when it makes the target artifact easier for the model to generate: either by increasing its sampling probability, or by reducing the thinking time needed to find it. We propose a computational Levin--Kolmogorov complexity approach to this problem, by appropriately replacing the universal Turing machine in the classical definitions by the LLM itself. Concretely, we introduce an LLM-relative notion of \emph{probabilistic Levin--Kolmogorov complexity} $pKt$---treating the model's thinking as the random tape of the program, and charging logarithmically for it in Levin's manner---and define prompt value as algorithmic mutual information with respect to $pKt$. This captures the intuition above: a prompt having $b$ bits of value for an artifact $z$ makes $z$ $2^b$ times ``easier to obtain'', by multiplying the success probability by $2^b$, by dividing the required computation by $2^b$, or by any corresponding tradeoff between probability and computation. In contrast to the classical notion of algorithmic mutual information, ours is efficiently estimable. We additionally show that, under a natural reproduction experiment, a prompt value of \(b\) bits means that reproducing \(z\) without the prompt has median token cost \(2^b\) times that of reproducing it with the prompt.

0.35

Distributional Variants of the Aaronson-Ambainis Conjecture

cs.CC quant-ph ·2026-09-28 ·Uma Girish, Kunal Mittal, Barak Nehoran, Ran Raz
similarity 0.56
Abstract

A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution $μ_p$, where the input bits are independent Bernoulli variables with fixed bias $p$. We show that for every fixed $p \in (0, 1)$, quantum query algorithms under the $μ_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $ν_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $ν_p$ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.

0.43

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

cs.LG cs.AIcs.IT ·2026-09-28 ·Luan Ozelim, Abicumaran Uthamacumaran, Hector Zenil
similarity 0.56
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.

0.25

Unlocking Fractional Moments in Delphic Set Streams

cs.DS ·2026-08-13 ·Aranya Kumar Bal, Sourav Chakraborty, Arijit Ghosh, Rudrayan Kundu
similarity 0.55
Abstract · Fixed typos and a couple of localized proof fixes

We consider estimation of non-integer frequency moments $F_k$ and related Bernstein-type statistics in the Delphic set stream model under a bounded-frequency assumption: every universe element appears at most $τ$ times. The main challenge of this model is to keep space low while also keeping update time low, which is not trivial because the sets can be exponential in size compared to their representations. Our core insight is that by sampling the stream at different rates and observing the resulting distinct-counts, we can 'probe' the frequency distribution and numerically integrate these probes to reconstruct a broad class of statistics. Building on that, we crucially observe that the distinct-count of a randomly sampled substream, viewed as a function of the sampling rate, is a single analytic object whose evaluations determine a broad class of statistics via a complementary Laplace-type integral. Algorithmically we exploit this by: 1. estimating those evaluations using only standard $F_0$ (distinct-count) algorithms on sampled substreams and 2. recovering target statistics by controlled numerical integration on a judiciously chosen grid. For $F_k$ with $k\in (0,1)$ we obtain the first one-pass streaming algorithms for Delphic set streams whose space and per-set update time are $\mathrm{poly}(\log|Ω|,\log m,\varepsilon^{-1},\log(1/δ))$ in the practically relevant regime $τ=\mathrm{polylog}(|Ω|,m)$; in general the bounds are polynomial in $τ$ and $\varepsilon^{-1}$ and logarithmic in $δ^{-1}$. We also give a complexity-theoretic barrier explaining why lower bounds for removing the bounded-frequency assumption appear difficult: ruling out polylogarithmic algorithms for unrestricted Delphic $F_k$ would imply a linear-space threshold-counting separation.

0.04

Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction

cs.IT math.PR ·2026-08-20 ·Claude Gravel
theory similarity 0.55
Abstract · 42 pages, 1 figure

Bernard and Letac (1971) introduced a method for uniform random sampling among $m$ outcomes from an unknown biased source of independent and identically distributed symbols. The process terminates when the multinomial coefficient of the cumulative symbol counts equals zero modulo $m$. This study extends the computational and information-theoretic analysis of their construction by presenting five algorithms with formal correctness guarantees and comprehensive complexity analyses. For prime $m=p$, the Bernard-Letac framework is analyzed in greater detail. The Rényi entropies of the source yield an exact product formula for the expected number of draws. A first-order approximation consistently overestimates this value, and the entropy lower bound is never attained. As $p$, treated as a continuous parameter, approaches 1, the expected cost converges to a constant greater than 1, determined by the entire source distribution. Furthermore, for every prime modulus $p$ and every finite alphabet $I$, an explicit automaton with $p + |I| + 3$ states computes the mod-$p$ first-passage kernel of the walk from the base-$p$ digits of its arguments, reducing the fair assignment cost from quadratic to nearly linear.

0.34

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.55
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