Proof idea: SLT to AIT

post by Lucius Bushnaq (Lblack) · 2025-02-10T23:14:24.538Z · LW · GW · 6 comments

Contents

  Background:
  Proof idea outline:
    Setup: Predicting a stochastic process
    Claims I want to prove:
  Comments:
None
6 comments

I think we may be able to prove that Bayesian learning on transformers^[1] or recurrent neural networks with a uniform^[2] prior over parameters is equivalent to a form of Solomonoff induction [? · GW] over a set of computationally-bounded programs. This bounded Solomonoff induction would still be 'approximately optimal' in a sense, being able to predict the data about as well any other bounded prediction procedure included in the set of programs it runs over. This proof would link Singular Learning Theory [? · GW] (SLT) back to basic Algorithmic Information Theory (AIT). 

This post is my current early-stage sketch of the proof idea. Don't take it too seriously yet. I’m writing this out mostly to organise my own thoughts. I'd originally planned for it to be a shortform, but I think it ended up a bit too long for that.

Background:

I recently held a small talk presenting an idea for how and why deep learning generalises. Slides for the talk here, slide discussion here [LW · GW].

In the talk, I tried to reduce concepts from SLT^[3] back to AIT^[4]. I sketched a story about deep learning, or perhaps even learning more generally, that goes like this:

1. Bayesian learning on (recurrent) neural networks is equivalent to a form of Solomonoff induction running over a set of programs bounded in length, runtime and memory usage.
2. Using SGD/genetic algorithms/your-fancy-update-method-of-choice to train a neural network is then a cheap bargain bin^[5] approximation of Bayesian learning on the neural network. Training steps are biased to make simple updates rather than complex updates because exponentially more parameter configurations in the architecture correspond to simpler programs.

Now, I want to actually prove this story. Specifically, I want to prove the first part: That Bayesian learning on transformers or RNNs is equivalent to a computationally bounded form of Solomonoff Induction (SI), in a sense I want to make precise. I also want to show that this bounded SI is a sensible approximation of actual unbounded SI, given some assumption of tractable predictability for the data. That is, we assume that it is possible at all to predict the data to good-enough accuracy with a limited computational budget. See e.g. these posts [1 [LW · GW],2 [LW · GW],3 [LW · GW]] if you want some idea of why we might think that this is a reasonable assumption to make for a lot of real-world data.^[6]

In the following, I’ll sketch a skeleton of the proof as I envision it right now, dividing it up into individual claims that seem tractable to prove to me. I’ve only just started on this, so some of the details here are probably wrong. Other details of the setup might just turn out to be hard to work with and get changed out for something better. 

Proof idea outline:

Setup: Predicting a stochastic process

We want to learn to predict some stochastic process from inputs $x$ to outputs $y$. We'll model the process as some function $f$ that takes two inputs: One input $x$ that we get to see, and one input $h$ we don't get to see, and returns one output $y$. $h$ is included to represent potential randomness in the process. It is drawn from some distribution with entropy $H\left(h\right)$.

Specifically, we define $f:(x,h)\to y$, where $f$ is a function, $x\in \{0,1{\}}^n$ and $h\in \{0,1{\}}^{n^{\prime }}$ are both tuples of $n,n^{\prime }$ booleans respectively, and $y\in \{0,1\}$ is a single boolean. We get to observe many pairs $(x,y)$.

Our prediction for $y$ will be probabilistic. Without loss of generality, we will make our prediction by naming the probability $p\left(y\right|x)$ that $y$ is a $1$ rather than a $0$. We’re about to think about this with programs, so we’ll restrict our $p$ to be floating point numbers of some finite precision $b$.

Claims I want to prove:

Claim 1: The ‘best’ way to make this prediction is to run a version of Solomonoff induction. By best, I mean we get a guarantee about the total error of our prediction ala Solomonoff completeness. Specifically, we take a Universal Turing Machine(UTM) $M_1$, which accepts the input $x$ and some program $P$ that outputs $b$ bits, representing the probability $p\left(y\right|x)$. We then run Solomonoff induction (SI) over the set of all such programs $P$ to make our prediction. The total error of our prediction in terms of KL-divergence measured in bits, across $D$ data points, should then be bounded below $\le C(f,M_1)+DH\left(h\right)$,  where $C(f,M_1)$ is the length of the shortest program that implements $f$ on the UTM $M_1$ and $H\left(h\right)$ is the entropy of our random variable $h$.

Proof status: This is just a slight variation of the textbook SI setup I am familiar with. I hope a proof of this already exists.

Claim 2: Solomonoff induction over length-bounded UTMs can still make approximately optimal predictions if $f$ is simple. Say the function $f$ has a description length of $K$ bits in our UTM $M_1$. If we know or heavily suspect that $K<<N$, we can run a version of SI that excludes programs above $N$ bits in length, and the result will still be very close to optimal in the sense described in claim 1. This length-bounded version would use a UTM $M_2$ that accepts plain program codes, not prefix-free program codes. It’d runs over all possible programs of length $N$, and assign a uniform prior $2^{-N}$ to every program. 

Proof status: I’d guess this proof might also exist somewhere already. If not, I think we can show it? See the discussion here [LW(p) · GW(p)] and here [LW(p) · GW(p)]. Also, I’ve since been pointed to the central lemma I think you’d want for this in this book on pages 145-146. 

Claim 3: If we further limit our Solomonoff induction to only include programs of runtime $T$ and space $s$, our prediction can still be approximately optimal in a sense. For this, we will assume that $f(x,h)=y$  is ‘efficiently predictable’. By ‘efficiently predictable’, we mean that there is some program $P^{\ast }$ of length $\left|P^{\ast }\right|<N$, that could be instantiated on $M_2$, requiring $s$ space and $T$ runtime, which makes predictions $p\left(y\right|x)$ that we consider ‘good-enough’ for our purposes. That is, the expected KL-divergence of its predictions from the actual distribution of $y$ is small enough that we would be happy with it. The time and space bounded SI is then approximately optimal in the sense that its total error compared to this efficient predictor, as measured by KL-divergence from the predictions made by $P^{\ast }$, will be $\le \left|P^{\ast }\right|$ bits summed across all data points.^[7] 

Proof status: Seems doable? We can just walk through the same style of argument used to show Solmonoff completeness for unbounded SI: Our SI will catch up to any such $P^{\ast }$ about as fast as programs simpler than $P^{\ast }$ are excluded by the training data.

Claim 4: Our bounded Solomonoff Induction is not very sensitive to the UTM we run it on. Just as in regular Solomonoff induction. If we use another UTM $M_3$ that can be implemented in the previous UTM $M_2$ using $N^{\prime }<<N$ bits, bounded SI on $M_3$ restricted to programs $N+N^{\prime }$ bits long or more, with $O\left(sT\right)$ runtime and $O\left(s\right)$ space, will still be approximately-optimal in the sense specified in claim 3, though our total error across all data compared to the efficient predictor will now be bounded to $\le \left|P^{\ast }\right|+N^{\prime }$ bits instead of $\le \left|P^{\ast }\right|$ bits.

Proof status: I think we can just use existing results on efficient simulation to show this? 

Claim 5: Transformers and RNNs are equivalent to a bounded UTM for our purposes. Consider e.g. a transformer in inference mode, with context window $T$ and $O\left(N\right)$ parameters. At the end of each forward pass, its output is fed back into its input layer. This happens for a total of $T$ forward passes. On the first forward pass, it is passed the input data $x$, padding the rest of the input with zeroes. On the final forward pass, its output is interpreted as the probability $p\left(y\right|x)$. This transformer is equivalent to a bounded UTM accepting programs of length $O\left(N\right)$, with a maximum runtime of $O\left(T\right)$, with a space bound determined by $T$ and the residual stream width.

Proof status: Some proofs along these lines already exist [1,2], though they seem to have minor problems. Mostly, I'm peeved that they use hardmax instead of softmax in the attention. This seems like a choice made for purely technical reasons though, they just didn't want a function that doesn't return rational numbers because that's annoying for their proof. 

Claim 6: Therefore, Bayesian learning on a transformer or RNN is a form of bounded Solomonoff induction, with the approximate optimality properties of the bounded induction outlined in claims 3 and 4. SLT^[3] describes Bayesian learning on neural networks, we have now shown SLT to be describing a form of Solomonoff induction.

Proof status: Immediately follows if we prove the other five claims.

If anyone points out errors or confusions in any of these claims or proof ideas, I'd appreciate it a lot. 

Comments:

On the meaning of the learning coefficient: Since the SLT^[3] posterior would now be proven equivalent to the posterior of a bounded Solomonoff induction, we can read off how the (empirical) learning coefficient $\lambda$ in SLT relates to the posterior in the induction, up to a conversion factor equal to the floating point precision of the network parameters.^[8] This factor is there because SLT works with real numbers whereas AIT^[4] works with bits. Also, note that for non-recursive neural networks like MLPs, this proof sketch would suggest that the learning coefficient is related to something more like circuit complexity than program complexity. So, the meaning of $\lambda$ from an AIT perspective depends on the networks architecture. It's (sort of)^[9] K-complexity related for something like an RNN or a transformer run in inference mode, and more circuit complexity related for something like an MLP.

On real world efficiency: This would be an AIT^[4]-style proof. None of this says very much about efficiency in the real world. It is not telling us whether we ought to use transformers or RNNs or Mamba for maximum efficiency, ReLUs or sigmoids, or anything of the kind. It's just showing, starting from an AIT perspective, why anything in a superset that includes all of these options would be able to do learning at all. 

On wider applicability: While the proof will be for deep learning on recurrent neural networks, I think the implications here could be much broader than that. I think this story of how learning is possible at all might also apply to in-context learning, and perhaps even many alternate setups outside of ‘deep learning’ that have not been invented yet. 

 

Thanks to Stefan Heimersheim for proofreading and comments. Thanks to Dmitry Vaintrob, Kaarel Hänni and Linda Linsefors for discussion. Thanks again to all of these [LW(p) · GW(p)] people. Thanks to everyone else at Apollo who endured my rants about this.

1. ^{^}

   Transformers run in inference mode. So, imagine something like RL training, but with Bayesian updating instead of gradient descent.

2. ^{^}

   I don't think using a Gaussian or some other typical NN initialisation scheme instead would change much, but I plan to prove it for a uniform distribution first because that seems more straightforward.

3. ^{^}

   Singular Learning Theory

4. ^{^}

   Algorithmic Information Theory

5. ^{^}

   Some things Bayesian learning can do SGD just can't do. See e.g. the parity learning problem [LW · GW].

6. ^{^}

   Also, observe how a lot of the real world does not seem like completely unpredictable tv static to your computationally limited brain.

7. ^{^}

   Credit to the logical induction paper for inspiring this idea. Seeing their proof that LIA isn’t exploitable by other traders than run in polynomial time is what got me thinking about this.

8. ^{^}

   Ok, really $\lambda$ should probably be related to the posterior of the induction on a UTM by first dividing it by the floating point precision of the neural network parameters, then letting that floating point precision tend to infinity.

9. ^{^}

   Only sort-of related because our prior only has support on programs bounded in runtime, space and description length, not on all programs. Also, K-complexity and (semi)-measure in the Solomonoff prior aren't identical [LW(p) · GW(p)] even in the conventional unbounded version of Solomonoff induction.

6 comments

Comments sorted by top scores.