# Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 62 of its 95 references that are in the map.
- First posted on arXiv 26 Sep 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [QLoRA: Efficient Finetuning of Quantized LLMs](https://mlsanity.com/paper/2305.14314/) (2023)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Variational Dropout and the Local Reparameterization Trick](https://mlsanity.com/paper/1506.02557/) (2015)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Measuring the Intrinsic Dimension of Objective Landscapes](https://mlsanity.com/paper/1804.08838/) (2018)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [Information-Theoretic Probing with Minimum Description Length](https://mlsanity.com/paper/2003.12298/) (2020)
- [Language Modeling Is Compression](https://mlsanity.com/paper/2309.10668/) (2023)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?](https://mlsanity.com/paper/2010.12725/) (2020)
- [Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs](https://mlsanity.com/paper/2309.07311/) (2023)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Bayesian Compression for Deep Learning](https://mlsanity.com/paper/1705.08665/) (2017)

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

- [Block-Recurrent Dynamics in Vision Transformers](https://mlsanity.com/paper/2512.19941/) (2025)
- [Effective Reasoning Chains Reduce Intrinsic Dimensionality](https://mlsanity.com/paper/2602.09276/) (2026)
- [Neural Weight Norm = Kolmogorov Complexity](https://mlsanity.com/paper/2605.10878/) (2026)
- [A Differentiable Measure of Algebraic Complexity: Provably Exact Discovery of Group Structures](https://mlsanity.com/paper/2511.23152/) (2025)
- [On the Rate-Distortion-Complexity Tradeoff for Semantic Communication](https://mlsanity.com/paper/2602.14481/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)

## Abstract (arXiv)

The Minimum Description Length (MDL) principle offers a formal framework for applying Occam's razor in machine learning. However, its application to neural networks such as Transformers is challenging due to the lack of a principled, universal measure for model complexity. This paper introduces the theoretical notion of asymptotically optimal description length objectives, grounded in the theory of Kolmogorov complexity. We establish that a minimizer of such an objective achieves optimal compression, for any dataset, up to an additive constant, in the limit as model resource bounds increase. We prove that asymptotically optimal objectives exist for Transformers, building on a new demonstration of their computational universality. We further show that such objectives can be tractable and differentiable by constructing and analyzing a variational objective based on an adaptive Gaussian mixture prior. Our empirical analysis shows that this variational objective selects for a low-complexity solution with strong generalization on an algorithmic task, but standard optimizers fail to find such solutions from a random initialization, highlighting key optimization challenges. More broadly, by providing a theoretical framework for identifying description length objectives with strong asymptotic guarantees, we outline a potential path towards training neural networks that achieve greater compression and generalization.