# Transformers As Approximations of Solomonoff Induction

arXiv: https://arxiv.org/abs/2408.12065 · HTML: https://mlsanity.com/paper/2408.12065/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 18 references that are in the map.
- First posted on arXiv 22 Aug 2024.

## Builds on (most cited first, 8 of 8)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [Tensor Decomposition for Model Reduction in Neural Networks: A Review](https://mlsanity.com/paper/2304.13539/) (2023)

## Built on by (most cited first, 6 of 6)

- [Language Models are Symbolic Learners in Arithmetic](https://mlsanity.com/paper/2410.15580/) (2024)
- [Solomonoff induction](https://mlsanity.com/paper/2603.20274/) (2026)
- [Large Language Models are Shannon Lossy Compressors Not Solomonoff Induction Estimators: Self-improvement and Singularity Are Not Near Without Symbolic Model Synthesis](https://mlsanity.com/paper/2601.05280/) (2026)
- [Thermodynamic Limits of Physical Intelligence](https://mlsanity.com/paper/2602.05463/) (2026)
- [Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model](https://mlsanity.com/paper/2608.01005/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)

## Abstract (arXiv)

Solomonoff Induction is an optimal-in-the-limit unbounded algorithm for sequence prediction, representing a Bayesian mixture of every computable probability distribution and performing close to optimally in predicting any computable sequence. Being an optimal form of computational sequence prediction, it seems plausible that it may be used as a model against which other methods of sequence prediction might be compared. We put forth and explore the hypothesis that Transformer models - the basis of Large Language Models - approximate Solomonoff Induction better than any other extant sequence prediction method. We explore evidence for and against this hypothesis, give alternate hypotheses that take this evidence into account, and outline next steps for modelling Transformers and other kinds of AI in this way.