# The KoLMogorov Test: Compression by Code Generation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 59 references that are in the map.
- First posted on arXiv 18 Mar 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [PIQA: Reasoning about Physical Commonsense in Natural Language](https://mlsanity.com/paper/1911.11641/) (2019)
- [Unsupervised Domain Adaptation by Backpropagation](https://mlsanity.com/paper/1409.7495/) (2014)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [On The Power of Curriculum Learning in Training Deep Networks](https://mlsanity.com/paper/1904.03626/) (2019)
- [To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning](https://mlsanity.com/paper/2409.12183/) (2024)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [InterCode: Standardizing and Benchmarking Interactive Coding with Execution Feedback](https://mlsanity.com/paper/2306.14898/) (2023)
- [Language Modeling Is Compression](https://mlsanity.com/paper/2309.10668/) (2023)
- [An Introduction to Deep Reinforcement Learning](https://mlsanity.com/paper/1811.12560/) (2018)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [Orca-Math: Unlocking the potential of SLMs in Grade School Math](https://mlsanity.com/paper/2402.14830/) (2024)
- [Injecting Numerical Reasoning Skills into Language Models](https://mlsanity.com/paper/2004.04487/) (2020)
- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [Execution-based Code Generation using Deep Reinforcement Learning](https://mlsanity.com/paper/2301.13816/) (2023)
- [Video Compression With Rate-Distortion Autoencoders](https://mlsanity.com/paper/1908.05717/) (2019)
- [MathGenie: Generating Synthetic Data with Question Back-translation for Enhancing Mathematical Reasoning of LLMs](https://mlsanity.com/paper/2402.16352/) (2024)
- [Getting the most out of your tokenizer for pre-training and domain adaptation](https://mlsanity.com/paper/2402.01035/) (2024)
- [NExT: Teaching Large Language Models to Reason about Code Execution](https://mlsanity.com/paper/2404.14662/) (2024)
- [SUPER: Evaluating Agents on Setting Up and Executing Tasks from Research Repositories](https://mlsanity.com/paper/2409.07440/) (2024)
- [LLMZip: Lossless Text Compression using Large Language Models](https://mlsanity.com/paper/2306.04050/) (2023)
- [Turning Tables: Generating Examples from Semi-structured Tables for Endowing Language Models with Reasoning Skills](https://mlsanity.com/paper/2107.07261/) (2021)

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

- [Exploiting Vocabulary Frequency Imbalance in Language Model Pre-training](https://mlsanity.com/paper/2508.15390/) (2025)
- [Is Compression Really Linear with Code Intelligence?](https://mlsanity.com/paper/2505.11441/) (2025)
- [Benchmarks Are Not That Out of Distribution: Word Overlap Predicts Performance](https://mlsanity.com/paper/2602.10657/) (2026)
- [Lossless Tensor Compression as Program Synthesis](https://mlsanity.com/paper/2608.02162/) (2026)
- [Self-Play Pretraining with Zero Data](https://mlsanity.com/paper/2609.30063/) (2026)

## Abstract (arXiv)

Compression is at the heart of intelligence. A theoretically optimal way to compress any sequence of data is to find the shortest program that outputs that sequence and then halts. However, such 'Kolmogorov compression' is uncomputable, and code generating LLMs struggle to approximate this theoretical ideal, as it requires reasoning, planning and search capabilities beyond those of current models. In this work, we introduce the KoLMogorov-Test (KT), a compression-as-intelligence test for code generating LLMs. In KT a model is presented with a sequence of data at inference time, and asked to generate the shortest program that produces the sequence. We identify several benefits of KT for both evaluation and training: an essentially infinite number of problem instances of varying difficulty is readily available, strong baselines already exist, the evaluation metric (compression) cannot be gamed, and pretraining data contamination is highly unlikely. To evaluate current models, we use audio, text, and DNA data, as well as sequences produced by random synthetic programs. Current flagship models perform poorly - both GPT4-o and Llama-3.1-405B struggle on our natural and synthetic sequences. On our synthetic distribution, we are able to train code generation models with lower compression rates than previous approaches. Moreover, we show that gains on synthetic data generalize poorly to real data, suggesting that new innovations are necessary for additional gains on KT.