# The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 118 references that are in the map.
- First posted on arXiv 11 Apr 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Conformer: Convolution-augmented Transformer for Speech Recognition](https://mlsanity.com/paper/2005.08100/) (2020)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Do ImageNet Classifiers Generalize to ImageNet?](https://mlsanity.com/paper/1902.10811/) (2019)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Galactica: A Large Language Model for Science](https://mlsanity.com/paper/2211.09085/) (2022)
- [TabPFN: A Transformer That Solves Small Tabular Classification Problems in a Second](https://mlsanity.com/paper/2207.01848/) (2022)
- [Perceiver IO: A General Architecture for Structured Inputs & Outputs](https://mlsanity.com/paper/2107.14795/) (2021)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Bayesian Deep Learning and a Probabilistic Perspective of Generalization](https://mlsanity.com/paper/2002.08791/) (2020)
- [Transformers Can Do Bayesian Inference](https://mlsanity.com/paper/2112.10510/) (2021)
- [SAINT: Improved Neural Networks for Tabular Data via Row Attention and Contrastive Pre-Training](https://mlsanity.com/paper/2106.01342/) (2021)
- [What Are Bayesian Neural Network Posteriors Really Like?](https://mlsanity.com/paper/2104.14421/) (2021)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Patches Are All You Need?](https://mlsanity.com/paper/2201.09792/) (2022)
- [Why do tree-based models still outperform deep learning on tabular data?](https://mlsanity.com/paper/2207.08815/) (2022)
- [A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups](https://mlsanity.com/paper/2104.09459/) (2021)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Generalization in Deep Learning](https://mlsanity.com/paper/1710.05468/) (2017)
- [A Bayesian Perspective on Generalization and Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06451/) (2017)

## Built on by (most cited first, 30 of 63)

- [Large Language Models Are Zero-Shot Time Series Forecasters](https://mlsanity.com/paper/2310.07820/) (2023)
- [The Platonic Representation Hypothesis](https://mlsanity.com/paper/2405.07987/) (2024)
- [Rethinking LLM Memorization through the Lens of Adversarial Compression](https://mlsanity.com/paper/2404.15146/) (2024)
- [Fine-Tuned Language Models Generate Stable Inorganic Materials as Text](https://mlsanity.com/paper/2402.04379/) (2024)
- [In-Context Learning through the Bayesian Prism](https://mlsanity.com/paper/2306.04891/) (2023)
- [Battle of the Backbones: A Large-Scale Comparison of Pretrained Models across Computer Vision Tasks](https://mlsanity.com/paper/2310.19909/) (2023)
- [Deep Learning is Not So Mysterious or Different](https://mlsanity.com/paper/2503.02113/) (2025)
- [Non-Vacuous Generalization Bounds for Large Language Models](https://mlsanity.com/paper/2312.17173/) (2023)
- [Learning from Teaching Regularization: Generalizable Correlations Should be Easy to Imitate](https://mlsanity.com/paper/2402.02769/) (2024)
- [Neural Redshift: Random Networks are not Random Functions](https://mlsanity.com/paper/2403.02241/) (2024)
- [Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models](https://mlsanity.com/paper/2407.18158/) (2024)
- [Implicit Multimodal Alignment: On the Generalization of Frozen LLMs to Multimodal Inputs](https://mlsanity.com/paper/2405.16700/) (2024)
- [The Complexity Dynamics of Grokking](https://mlsanity.com/paper/2412.09810/) (2024)
- [The Geometry of Reasoning: Flowing Logics in Representation Space](https://mlsanity.com/paper/2510.09782/) (2025)
- [Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression](https://mlsanity.com/paper/2306.00788/) (2023)
- [Block-Recurrent Dynamics in Vision Transformers](https://mlsanity.com/paper/2512.19941/) (2025)
- [Constant Bit-size Transformers Are Turing Complete](https://mlsanity.com/paper/2506.12027/) (2025)
- [Understanding Visual Feature Reliance through the Lens of Complexity](https://mlsanity.com/paper/2407.06076/) (2024)
- [Saddle-to-Saddle Dynamics Explains A Simplicity Bias Across Neural Network Architectures](https://mlsanity.com/paper/2512.20607/) (2025)
- [EXMOS: Explanatory Model Steering Through Multifaceted Explanations and Data Configurations](https://mlsanity.com/paper/2402.00491/) (2024)
- [In-Context Learning Dynamics with Random Binary Sequences](https://mlsanity.com/paper/2310.17639/) (2023)
- [A Complexity-Based Theory of Compositionality](https://mlsanity.com/paper/2410.14817/) (2024)
- [Do We Always Need the Simplicity Bias? Looking for Optimal Inductive Biases in the Wild](https://mlsanity.com/paper/2503.10065/) (2025)
- [Analyzing the Role of Semantic Representations in the Era of Large Language Models](https://mlsanity.com/paper/2405.01502/) (2024)
- [Zero-Shot Multi-Object Scene Completion](https://mlsanity.com/paper/2403.14628/) (2024)
- [In-context learning and Occam's razor](https://mlsanity.com/paper/2410.14086/) (2024)
- [When Do Neural Networks Learn World Models?](https://mlsanity.com/paper/2502.09297/) (2025)
- [Can You Learn to See Without Images? Procedural Warm-Up for Vision Transformers](https://mlsanity.com/paper/2511.13945/) (2025)
- [Exploiting Vocabulary Frequency Imbalance in Language Model Pre-training](https://mlsanity.com/paper/2508.15390/) (2025)
- [A Mathematical Philosophy of Explanations in Mechanistic Interpretability -- The Strange Science Part I.i](https://mlsanity.com/paper/2505.00808/) (2025)

## Abstract (arXiv)

No free lunch theorems for supervised learning state that no learner can solve all problems or that all learners achieve exactly the same accuracy on average over a uniform distribution on learning problems. Accordingly, these theorems are often referenced in support of the notion that individual problems require specially tailored inductive biases. While virtually all uniformly sampled datasets have high complexity, real-world problems disproportionately generate low-complexity data, and we argue that neural network models share this same preference, formalized using Kolmogorov complexity. Notably, we show that architectures designed for a particular domain, such as computer vision, can compress datasets on a variety of seemingly unrelated domains. Our experiments show that pre-trained and even randomly initialized language models prefer to generate low-complexity sequences. Whereas no free lunch theorems seemingly indicate that individual problems require specialized learners, we explain how tasks that often require human intervention such as picking an appropriately sized model when labeled data is scarce or plentiful can be automated into a single learning algorithm. These observations justify the trend in deep learning of unifying seemingly disparate problems with an increasingly small set of machine learning models.