Research map / Large language models / Agents, code and math
The KoLMogorov Test: Compression by Code Generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the KoLMogorov-Test, a benchmark asking code LLMs to compress byte sequences (audio, text, DNA, synthetic) by generating the shortest Python program that reproduces them, and trains SeqCoder models on a synthetic DSL.
Problem
Kolmogorov complexity is uncomputable, and it is unclear how well code generating LLMs can approximate it by finding short programs that output a given sequence; existing compression-by-LLM methods need model weights for decoding.
Approach
Frames compression as code generation: a code LM outputs a short program reproducing an input sequence, scored by the encoded program length under a fixed prior (Gzip or a uniform DSL prior), with an effectively unlimited supply of instances from natural and synthetically sampled data.
Key results
- Llama-3.1-405B and GPT-4o fail on 78% and 40% of natural sequences respectively; GPT-4o reaches 44.7% accuracy on synthetic data at length 128.
- SeqCoder-8B reaches 92.5% accuracy on synthetic sequences and a CompressionRate of 0.38, beating Gzip and LMiC on synthetic data.
- SeqCoder-1.5B gets near-zero accuracy on natural audio, DNA and text, showing synthetic gains generalize poorly to real data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train specialized SeqCoder models on synthetic program-sequence pairs instead of zero-shot prompting | CodeLMs · Synthetic | accuracy: 44.7 -> 92.5 | Helped |
| Train specialized SeqCoder models on synthetic program-sequence pairs instead of zero-shot prompting | CodeLMs · Synthetic | precision: 1.65 -> 0.56 | Helped |
| Train on synthetic data and evaluate on naturally occurring sequences | SeqCoder-8B · Natural audio, DNA, and text | accuracy: 92.5 -> 0.0; 92.5 -> 0.1 | Hurt |
| Add execution feedback to training examples only (ablation) | SQ-1.5B · Synthetic, sequence length 64 | accuracy: 86.6 -> 77.6 | Hurt |
| Add execution feedback to training examples only (ablation) | SQ-1.5B · Audio-MFCC, sequence length 64 | accuracy: 6.5 -> 8.6 | Helped |
| Add training feedback and line-by-line execution feedback (ablation) | SQ-1.5B · Synthetic, sequence length 64 | accuracy: 86.6 -> 75.9 | Hurt |
| Add training feedback and line-by-line execution feedback (ablation) | SQ-1.5B · Audio-MFCC, sequence length 64 | accuracy: 6.5 -> 8.7 | Helped |
| Add chain-of-thought prompting (ablation) | Llama-3.1 models · KoLMogorov-Test modalities | accuracy: drop of 1.3 and 5.1 points; increase of 2.1 points | Mixed |
| Increase input sequence length | Gzip · Audio-8-bit | compression rate: 0.966 -> 0.622 | Helped |
| Increase input sequence length | Llama-3.1-405B · Audio-8-bit | accuracy: 47.1 -> 14.2 | Hurt |
| Increase training data from 10K to 100K or 1M examples | SeqCoder-1.5B · Audio-MFCC, sequence lengths 16-64 | accuracy | Helped |
Surprising findings
- Chain-of-thought prompting does not consistently improve compression accuracy, with small drops for Llama 8B and 70B.
- Prompted models' correct programs often just repeat the input sequence in complex ways, which the Gzip prior penalizes.
Limitations
- Trained SeqCoder models perform near zero on real natural sequences, so synthetic gains do not transfer.
- Evaluation limited to 1MB data and sequences up to length 128 because accuracy collapses on longer inputs.
- Runtime compute of program execution and LLM weights are not counted in the compression metric.
Experimental setup
Datasets: LibriSpeech enwik9 GRCh38 human genome synthetic DSL program-sequence pairs
Benchmarks: KoLMogorov-Test
Metrics: Accuracy CompressionRate Precision
Baselines: Gzip LMiC Llama-3.1-8B Llama-3.1-70B Llama-3.1-405B GPT4-o o1-mini
Builds on: Language Modeling is Compression Gzip arithmetic coding Solomonoff induction
Closest papers by meaning
- Understanding LLM Behaviors via Compression: Data Generation, Knowledge Acquisition and Scaling Laws (NeurIPS 2025 · similarity 0.87)
- The Automated LLM Speedrunning Benchmark: Reproducing NanoGPT Improvements (NeurIPS 2025 · similarity 0.86)
- Can Compressed LLMs Truly Act? An Empirical Evaluation of Agentic Capabilities in LLM Compression (ICML 2025 · similarity 0.86)
- SciCode: A Research Coding Benchmark Curated by Scientists (NeurIPS 2024 · similarity 0.86)
- CodeChemist: Test-Time Scaling for Low-Resource Code Generation via Functional Knowledge Transfer (ICML 2026 · similarity 0.85)
- From Reproduction to Replication: Evaluating Research Agents with Progressive Code Masking (ICLR 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.