# Large Language Models as Computable Approximations to Solomonoff Induction

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 70 references that are in the map.
- First posted on arXiv 21 May 2025.

## Builds on (most cited first, 30 of 49)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Instruction Tuning with GPT-4](https://mlsanity.com/paper/2304.03277/) (2023)
- [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [Label Words are Anchors: An Information Flow Perspective for Understanding In-Context Learning](https://mlsanity.com/paper/2305.14160/) (2023)
- [Patchscopes: A Unifying Framework for Inspecting Hidden Representations of Language Models](https://mlsanity.com/paper/2401.06102/) (2024)
- [Language Modeling Is Compression](https://mlsanity.com/paper/2309.10668/) (2023)
- [Make Pixels Dance: High-Dynamic Video Generation](https://mlsanity.com/paper/2311.10982/) (2023)
- [A Practical Review of Mechanistic Interpretability for Transformer-Based Language Models](https://mlsanity.com/paper/2407.02646/) (2024)
- [The Description Length of Deep Learning Models](https://mlsanity.com/paper/1802.07044/) (2018)
- [LongDocURL: a Comprehensive Multimodal Long Document Benchmark Integrating Understanding, Reasoning, and Locating](https://mlsanity.com/paper/2412.18424/) (2024)
- [What Matters in Training a GPT4-Style Language Model with Multimodal Inputs?](https://mlsanity.com/paper/2307.02469/) (2023)
- [Transformer-based Image Compression](https://mlsanity.com/paper/2111.06707/) (2021)
- [RedStar: Does Scaling Long-CoT Data Unlock Better Slow-Reasoning Systems?](https://mlsanity.com/paper/2501.11284/) (2025)
- [Context-DPO: Aligning Language Models for Context-Faithfulness](https://mlsanity.com/paper/2412.15280/) (2024)
- [From Understanding to Utilization: A Survey on Explainability for Large Language Models](https://mlsanity.com/paper/2401.12874/) (2024)
- [GeoEval: Benchmark for Evaluating LLMs and Multi-Modal Models on Geometry Problem-Solving](https://mlsanity.com/paper/2402.10104/) (2024)
- [Parameters vs. Context: Fine-Grained Control of Knowledge Reliance in Language Models](https://mlsanity.com/paper/2503.15888/) (2025)
- [Decoding by Contrasting Knowledge: Enhancing LLMs' Confidence on Edited Facts](https://mlsanity.com/paper/2405.11613/) (2024)
- [MV-MATH: Evaluating Multimodal Math Reasoning in Multi-Visual Contexts](https://mlsanity.com/paper/2502.20808/) (2025)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [DocTER: Evaluating Document-based Knowledge Editing](https://mlsanity.com/paper/2308.09954/) (2023)

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

- [A Survey of Context Engineering for Large Language Models](https://mlsanity.com/paper/2507.13334/) (2025)
- [Gated Differentiable Working Memory for Long-Context Language Modeling](https://mlsanity.com/paper/2601.12906/) (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)
- [Truth as a Compression Artifact in Language Model Training](https://mlsanity.com/paper/2603.11749/) (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)

## Abstract (arXiv)

The rapid advancement of large language models (LLMs) calls for a rigorous theoretical framework to explain their empirical success. While significant progress has been made in understanding LLM behaviors, existing theoretical frameworks remain fragmented in explaining emergent phenomena through a unified mathematical lens. We establish the first formal connection between LLM architectures and Algorithmic Information Theory (AIT) by proving two fundamental results: (1) the training process computationally approximates Solomonoff prior through loss minimization interpreted as program length optimization, and (2) next-token prediction implements approximate Solomonoff induction. We leverage AIT to provide a unified theoretical explanation for in-context learning, few-shot learning, and scaling laws. Furthermore, our theoretical insights lead to a principled method for few-shot example selection that prioritizes samples where models exhibit lower predictive confidence. We demonstrate through experiments on diverse text classification benchmarks that this strategy yields significant performance improvements, particularly for smaller model architectures, when compared to selecting high-confidence examples. Our framework bridges the gap between theoretical foundations and practical LLM behaviors, providing both explanatory power and actionable insights for future model development.