The KoLMogorov Test: Compression by Code Generation
Authors: Ori Yoran
Kunhao Zheng
Fabian Gloeckle
Jonas Gehring
Gabriel Synnaeve
Taco Cohen
Venue: ICLR 2025 Poster (2025)
Keywords: Code generation
code
compression
LLM
dataset
benchmark
Primary area: datasets and benchmarks
TL;DR: We propose KT, a compression-as-intelligence test for code generation LMs based on the notion of Kolmogorov Complexity, and identify several theoretical and empirical benefits: KT is challenging for current LMs and essentially infinite problems exist

Abstract: 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 intelligence test for code generation 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.

Published as a conference paper at ICLR 2025
THE KOLMOGOROV TEsT: COMPRESSION BY CODE GENERATION
Ori Yoran 12 Kunhao Zheng', Fabian Gloeckle! Jonas Gehring', Gabriel Synnaeve', Taco Cohen! 'Meta Al (FAIR), TTel Aviv University ori, yoran taw.tataaa... ac.
(kunhao, fgloeckle, jgehring, gab, tscchen Aeeetn com
ABSTRACT
Compression is at the heart of intelligence. A theoretically optimal way to com- press any sequence of data is find the shortest program that outputs that se- quence and then halts. However, such Kolmogorov compression is uncomputable, and code generating LLMs struggle to approximate this theoretical ideal, it requires reasoning, planning and search capabilities beyond those of current mod- els. In this work, we introduce the KoLMoGOROV-TES. as is-intelligence test for code generating LLMs. In KT a model is presented with 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 evalua- tion 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 highly un- likely. To evaluate current models, we use audio, text, and DNA data, well sequences produced by random synthetic programs. Current flagship models per- form poorly both GPT4-0 and LLAMA-3. 1-405B struggle synthetic sequences. On our synthetic distribution, we are able to train code gener- ation 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.
(KT), compression-
natural and
INTRODUCTION
Compression and code generation are deeply related through the notion of Kolmogorov complexity, denoted K K(x), which defined as the length of the shortest computer program that produces the sequence x as output and hence constitutes the optimal compression of (Kolmogorov) 1963 Li & Vitányi 1997 Hutter et al.] 2024) (see for a detailed background). Kolmogorov complexity is un- computable as it reduces to the halting problem, making the search for improved computable upper bounds a never-ending challenge and a potential benchmark for intelligence that by definition cannot saturate. We propose view code generation language models (CODELMs) Kolmogorov complexity: we task them to identify patterns an input sequence and to compress by producing a short program that outputs said sequence, and can measure their accuracy produc- ing correct programs as well as the compression rates achieved. This is the KOLMOGOROV-TESS (KT), a benchmark for reasoning capabilities for CODELMS, illustrated in Fig. [
upper bounds for
We point out the following benefits of compression by code generation as a benchmark for the rea- soning capabilities of language models: (1) the compression metric can be trusted in that does not produce false positives, (2) diverse and richly structured sequence data is abundantly available, (3) it is highly unlikely that pretrained models have seen many relevant (program, sequence) pairs, making memorization-bnn based solutions infeasible (4) if the benchmark is saturated, either through improved reasoning and search capabilities or memorization, we can simply increase the sequence
* Work done during an internship Meta FAIR.
I For some universal Turing machine U.
Models trained synthetic data by RI. could very well end up using memorization.

---

Published as a conference paper at ICLR 2025
74 bytes (982 bits)
[152, 89, 99, 104, 204, 242, 231, 44, 120, 35, 243, 56, 86, 17, 0, 41, 243, 68. 181. 110, 147, 13,
110. 113, 116, 119, 122, 125, 128, 131, 134, 137, 140, 143, 146, 149, 152, 155. 158, 161, 164.
167, 170, 173, 156, 157, 158, 159, 160, 161. 162, 163, 162, 187, 192, 197, 202, 207, 212, 217.
222, 227, 232, 237, 242, 247, 252, 104, 204, 242, 231, 120, 35]
Standard (Gzip)
Language modeling
Code generation
(25)) a oscan 11.0
seq, 1=set Fsx1152,89. 10.116228.....11.... 18) 131 2erange/110 173, 24 bit
(PMM51)) D. 20056 10.3 Mh
seg, 355ange/156, 162) 21
LZ7?
Huffmen Enoodling
Pa 170)
4-rsnge(182, 182, 252, 24
(150055 170, a 002505 t1.
oupuueennareesteeee.. sen_2. seq 3. seq B) 47
Seauu seglenn 3)
Pa.CE 190, 178, 120) 0.17600044
592 bits
P 416 bits
G 320 bits
Figure 1: Data compression by code generation. Consider compressing a sequence of bytes (pre- sented as numbers in range [0, 255)) that can be produced by composing simpler sub-sequences. Standard compression methods, such as GZIP, focous on repetitions and frequency of characters weeeeeeeuueeee
and fail to exploit the logical patterns in this sequence (although they are strong baselines for long sequences. $5.3). LLMs are better at finding complex patterns, such as a sequence of incremental numbers, and can be used for compression with arithmetic coding. However, they are sensitive to phase-shifts due to their auto-regressive manner, and require model weights for decoding. Code generative models, inspired by the concept of Kolmogorov Complexity, can identify patterns in the input sequence to generate concise programs whose execution produces the original sequence.
length and (5) following research spanning decades of theoretical computer science, classical com- pression algorithms such as GZIP (Deutsch) 1996) can serve as strong baselines.
To evaluate current CODELMS on KT, we use naturally occurring sequences from three data modal- ities: text, audio, and DNA (3..). As we do not know the optimal program for the sequences, is not possible to use this data for supervised learning, making it ideal for evaluation. To collect program-sequence sequence pairs for supervised training and evaluation, we design a compositional domain- specific language (DSL) coupled with automatic data generation framework ($3.3). inspired by context-free free grammars (Chomsky] 1956 Hopcroft et al. 2006).
Our experiments ($4) show that sequence compression is extremely challenging task for cur- rent CODELMS. Strong LLAMA-3. 3-105BB (Grattafiori et al., 2024) and GPT4-0 (OpenAl et al, 2024b) models generate Python programs that fail to produce the input sequence in 78% and 40% of the time for naturally occurring data, and 66% and 45% percent of the time for synthetic se- quences that follow clear patterns. On our synthetic distribution, CODELMS with 1.5B parameters that outperform state-of-the-ar prompted models by more than 40%, but struggle on real sequences. We further find that the prior used for program-compression is an important factor in overall compression performance, with simple uniform prior over our DSL. outperforming GZIP. Finally, we observe modest gains for adding inline execution feedback.
are able to train relatively small
In $5.3 we conduct thorough analysis of our results. We find that gains on synthetic data partially generalize to real data models trained for longer perform better on short sequences, but all current models perform poorly on long sequences, suggesting KT can act as useful test-bed to evaluate scaling properties of new methods. Finally, we perform an error analysis and find that models make wide range of errors, from generating over-simplified programs that do not produce the input sequence, to repeating the input sequence in over-complicated ways.
To summarize, our main contributions are
We propose the KoL.MoGoRov-TEST an extremely challenging compression-as- intelligence test for CODELMS ($3)
We show that CODELMS can outperform previous compression methods on synthetic dis- tributions where sampling program-sequence pairs is possible and efficient priors can be used, but fare very poorly on real data ($5)
Too support future progress, release our code, data, and public leaderboard.
2

---

Published as a conference paper at ICLR 2025
Evaluate pre-trained LLMs on natural
Collect syntheti pragram-sequene pairs. train, ovaluate on natural and syn. data
Collect natural sequences (e.g. g. DNA)
Sample executable programs from
Evaluste trained models on held-out syn. data
DSL and train over generated pairs
Genevall a gython programe which
se0, Teael Juk 152.50--11 111
Outgut #1:
123, 23, 15
b. Prompt instrcciion-tued LLMs
Sesaggef 96
1152.
IM57: Gonorate a python program which outcate bie GNomio aequaincc:
156. 157 158 outppeeercattooo 1oors
and dxxeppa (82
Evaluste trained modets real data
8.1225220: 22222222222222222222222222 111223200:1162300
104, 204 242
WST Genovale a pytto progroms which oxtjuus the folwssng any sivioooe (0 0.1.2.2222022 22200222221222222000
Figure 2: Our main experimental settings.
We show that performance on real data scales poorly with increasing synthetic dataset size, suggesting that new breakthroughs may be needed for further progress on KT.
2 BACKGROUND
Generative Modelling, Information Theory and Compression. Generative modelling and com- pression are deeply related. Given a generative model over sequences (e.g., autoregressive trans- former (Radford et al. 2018 (x<), one can use the arithmetic coding algorithm to compress bitstream of length about - -E, log2 p(z; [<))) bits (Rissanen) 1976. Pasco 1977). If the sequences are sampled from the gold distribution p", then the expected arith- metic code length is the cross entropy between p" and p. When p = p". the cross entropy equals the entropy, which is the fundamental limit on average compression length for data sampled from p".
particular sequence
Similarly, given a latent variable model p(zr, 2), can encode sequence or by first encoding code: = using prior p(z) and then encoding x using likelihood p( (z). Using an optimal code for p(2) and p(x]=z) the coding cost will be roughly log p(=) llog p(x|2) If we obtain by sampling from an encoder network (2][z). the expected coding cost will be E, - log - log p(x|2)] (Habibian al. 2019), which (up an additional entropy bonus H [(g)) equals the evidence lower bound
(ELBO) used for instance for VAE training (Kingma & Welling 2022). Thus, both for autoregressive
and latent variable models, maximizing likelihood is maximizing compression.
Algorithmic Information Theory, Solomonoff Induction, and Kolmogorov Complexity. In classical generative modelling and compression, one is concerned with finding generative model from a particular model class that can be used to compress data from particular distribution. By contrast, in algorithmic information theory, one considers as "model class" the set of all computable functions. This class trivially contains the optimal compression, and changing the computational model (programming language/ / universal Turing machine) only incurs constant overhead depend- ing on the pair of languages involved and regardless of the input (Grunwald & Vitanyi 2008 2.2.2).
In analogy to the discussion above, we can sketch the theory as follows, inspired by Solomonoff's theory of inductive inference (Solomonoff) 1964). We consider the universal prior p(p) = 2-((p) over programs p (where/ 1(p) denotes the length) that assigns higher probability to shorter programs (*Occam's 's Razor"). Furthermore, we consider the likelihood p(rlp) over output sequences given P which puts all mass on the actual output of
Then, treating P latent we may encode x using two-part code by finding a program p that outputs x (e.g. using a neural network {(p)z)). and encoding it using the prior p(p). As before, the coding cost will be !- [- log p(p) log p()] where the second term is whenever is not the output of p, and 0 when is. Clearly, the optimal p is the shortest program that outputs x. The length of this
program p" is called the Kolmogorov Complexity K(x)) (Kolmogorov 1963
Li & Vitányi 1997..
3

---

Published as a conference paper at ICLR 2025
3 DATA COLLECTION
3.1 PROBLEM SETTING
The theory presented ahove suggests an interesting challenge for CODELMS: generate concise programs (under well-defined priors) that output a given sequence (Fig. | and Alg. 2 in A.3) We evaluate CODELMS on three naturally occurring modalities: audio, text, and DNA (Fig. left, and $3.2). We focus on audio and textual data, popular modalities in compression works with strong baselines (Deletang et al. 2024). We also introduce DNA sequences as these follow simple biolog- ical patterns. Although real data is useful for evaluation since it can be obtained in large amounts for many modalities, corresponding progrums required for supervised training are not available. As a remedy, we experiment with synthetic settings where we collect program-sequence pairs by sampling programs from a Domain Specific Language (DSI.) and executing the sampled programs (Fig. 2 right, and 433
3.2
NATURALLY OCCURRING SEQUENCES
In all our experiments on natural data, the model has to compress IMB of information. The length of the input sequence presented our models ranges from 16 to 1024 bytes depending on the setting.
Audio. We randomly sample audio snippets from the LibriSpeech development and test sets (Panayotov al.] 2015). We parse the data three audio formats: (a) high quality audio with 16 bits depth, from which the original data can be perfectly recreated but each sample is split across two bytes, (b) lower quality audio with 8 bits depth, which is simpler for our baselines (55), and (c) an estimation of the Mel-Frequency Cepstral Coefficients encoding (MFCC) which does not allow direct reconstruction but describes the main features of the sound (see $A.I for more details). Each byte is represented as number in range [0, 255].
Text. Following recent work (Deletang et al., 2024), we use the enwik9 Wikipedia corpus (Hut- ter 2009).. The Unicode text is encoded to sequence of bytes with UTF-8 encoding which are represented as list of numbers.
DNA. We use Genome assembly GRCh38 which contains 3.1 of human DNA in FASTA format NCBI 2023). Since the original files include upper and lower case variants of each of the four nucleotides, we use vocabulary of eight characters represented by numbers in range [0, 7
3.3 SYNTHETIC DATA GENERATION
Our aim is to examine whether CODELMS can be trained to generate concise and correct programs. Hence, we adhere to the following desiderata for our data generation process: (a) completeness: each sequence has some probability for a program that produces it to be sampled, and (b) simplicity: shorter programs will be sampled with higher probability.
Domain Specific Language. We design a compositional DSL, in the sense that the output se- quence is created by composing simpler sub-sequences (Fig. 2 center). Our DSL supports the following four classes of functions (see $A.2 for a list of all supported functions)
Sequence initiators: functions that take variables as input and return sequence of num- bers. These include a range of increasing numbers, a repetition of a single number, or a fixed (hard-coded) list of numbers.
Sequence modifiers: functions that take sequence as input and return a modified version of the sequence, e.g., by reversing, repeating, or substituting elements from the sequence. A sub-class of our modifiers includes mathematical operations, such as scan-adding the elements the sequence or applying a modulo operation.
'Lower case variants represent low-complexity which we keep to allow perfect reconstruction of the input sequence.
masked regions (c.g., repeats or predicted sequences),
'ee note that for simplicity, our DSL. does not allow recursion - it is proper subset of primitive recursive functions and of Turing-computable functions (Turing
1937) and thus deviates from the theory in $
4

---

Published as a conference paper at ICLR 2025
Program
Executed sequence 1
Program 2
Execuled 176. 100. 142. 95, 95,
=range|229 256,
229. 133, 164, 135.
T-eel [iii661.74 117)
1788)
50q 2-repeat(21,
195,
155.
Beq 3=auustttttttsse 95,
sea 3 198)
133.
197 233.
500
176, 61, 61, 74, 142.
seq
derepeat(E, 133)
198, 6, 23b,
6, 23r. 15.
5eg
4rrrin n[seq
130, 100, 176, 61, 74,
seg 5-inteffovoteeoL seq_2)
239, 6, 241,
6, 243, 6.
seq S-interesveejee 882
95, 61. 14, 142, 95.
@einterfoaveiseq__
245, 247.
749. 6
500.
6ecomcarenaal((enn 5,
681_3)
seq Trinterfesveiseg. seq 4)
seq, T=cgncalenale(see [esesaggsssssseeeeeeeeeee 992_4)
seq. B-concatenntteieer 7, seq 3)
5. 5,
6, 194, 195
seq Broooncatenateeeee
seg 9=comostensteisae__ $90_4)
198, 197. 198, 133, 193.
culput-2ec_
outprtsse
9
133. 133, 195)
Figure 3: Two examples of program pairs from our synthetic data generation process.
Sequence filters:
functions that filter sequence, e.g., by keeping only even values. functions that take two sequences and merge them to a single one: concatenation, interleaving, pointwise addition, subtraction modulo of the sequences.
Sequence mergers:
Sampling programs. Given the compositional nature of our DSL, we sample programs similarly to the way sequences are sampled from a Context Free Grammar (Chomsky), 1956 Hoperoft et al. 2006). We can also control the distribution of programs by assigning priors over the program distri- bution, c.g., the lengths of the initiated sequence or probability to apply modifications. For simplicity and to avoid biases we keep the priors uniform( For examples of program-sequence pairs, Fig. As in the natural data domains, we generate TMB of evaluation data. For training, we sample 1M pairs from the same distribution. We provide additional details and statistics in A..2
Encoding programs. We encode programs written in our DSL using a factorized uniform prior over functions and arguments. As each line includes a call to single function, the encoding cost of each line is the cost of encoding the function (i.e., logg (1 (uuccioncss)) 1)) plus the cost of the input parameters (e.g.. the number of bits needed to set an arbitrary list for set list, or the indices of the
sequences in concatenate). Our code length calculation algorithm is presented in AA.2 Alg.
4 EXPERIMENTAL SETUP
Baselines. For classical compression baseline, use GZIP (Deutsch| 1996). We also include a Language Modeling is Compression (LMIC) baseline (see ŞB. for implementation details), where the LM predictions are used together with arithmetic coding to compress the sequence as discussed in $ (Deletang et al.] (024).. A major limitation of LMIC is that the original LLM is needed decompress the data 1 We also include REPEAT, naive baseline that always returns the input sequence, and an UPPER BOUND baseline that returns the matching program for our synthetic pairs.
Zero-shot prompted baselines. We prompt our models to generate the shortest Python program that produces the input sequence (see $B. Fig. g for the full prompt). We strong beinwh models from the LLAMA-3. family with 8, 70, and 405 billion parameters Grattafiori et al. (2024). In addition, iment with a chain-of-thought (CoT) (Wei et al., 2022) baseline (see prompt in Fig. T0) and with OPENAI -I-MINI (OpenAl al., 2024a), closed-source model trained to think before generating the final answer. We use GZIP to encode programs before measuring their bit length (i.c., we use GZIP prior over programs) in all experiments, unless stated otherwise.
GPT4-0 as a closed-soure alternative (OpenAl et al. 2024b). We also exper-
Trained models. For our trained models, we use LLAMA-3.1 -318-B811-BB as base model in addition to 1.5-biliion parameter LLM with the same architecture, which we train on a mixture open-source code and text (see $B.1 for more details and technical specifications). We further train our models on 10K, 100K or 1M unique programs-sequenc, pairs sampled from our data generator ($3.3) and
'We note that this does not guarantee that each operator is used with the same probability, as some operators only applicable in specific contexts (e.g.. an addition between sequences is only applicable when the sequences have the same length and the sum of the matching elements
the allowed range).
As our focus is on compressing relatively small amounts of data, report raw LMIC results disregarding the weights of the model, upper bound of the true performance which requires the weights that were used for encoding at decoding time.
5

---

Published as a conference paper at ICLR 2025
name them SEQCODER-100 10K, SEOCODER- 100K and SEQCODER(-IM) respectively. We use the encoding algorithm defined in $3.3 for encoding programs from our synthetic DSL.
Sequence lengths. We use a sequence length of 1024 bytes for our LMIC baseline, based on findings that further increasing context length does not result in significant gains (Deletang al.) 2024). For natural data, we use a sequence length of 128 bytes (see $5.3 for a discussion on input lengths). Our synthetic data has average sequence length of 75.9 bytes with standard deviation of 73.7 (see $A.2 Fig. 7 and Fig. 8 for histograms of sequence and programs lengths).
Metrics. Given a sequence and a program candidate suggested by the model with output [p]. define the variable y that backs off the REPEAT baseline when P errs by:
if [p] 2, otherwise.
We define the following metrics:
Accuracy(ær, p) ([p]=x)
CompressionRate((.,) 1 |1yleene
||=|||
||
Precision(r,,) p)
where [p]
| gzip
where || denotes the bit-length of the data, || Ilsaip denotes the length after GZIP-encoding and || llene denotes the length after encoding programs with GZIP for prompted models and our uni- form encoding for SEOCODER models. In other words, Accuracy measures whether the program correct, RatpressionRate measures the compression of the input when storing the compressed representation (an additional bit is saved to determine whether y is p or z and lower Compression- Rate is better") and Precision measures the compression of correct programs in relation to the GZIP baseline. REPEAT has an Accuracy, RampressionRate and Precision of by definition.
5 RESULTS
Running prompted pretrained models well smaller trained models KoL.MoGoROv-TEsy with natural as well as synthetic sequence data sources, we make the following main findings: Zero- shot compression by code generation a challenging benchmark even for the most powerful models available ($5.1). On short sequences of synthetic data, trained specialized models outperform the in-context reasoning baseline LMIC well as classical baseline algorithms ($5.2). In additional analyses, we examine the effect of scaling model and dataset size for models trained on synthetic data, their length generalization as well as typical failure modes ($5.3)
5.1 GOLMoGOROV-TESS IS CHALLENGING FOR CURRENT MODELS
Tab. presents results for our prompted and SEQCODER models on different data modalities. Prompted models perform poorly strong LLAMA-3.1 1400B and GPT4-0 models on average more than 78% and 40% of the time for naturally occurring sequences, with high variance between synthetic data, which follows simple
modalities, and more than 65% and 55% of the time compositional rules by design.
Nevertheless, larger models perform better, with LLAMA-3.1 reaching the best Accuracy be- tween LLAMA models, and GPT4-0 reaching the highest Accuracy and lowest Precision overall. All prompted models have Precision score that is higher than 1.0, meaning that on average, gen- erated programs are larger than the SzzI--encddd sequences. We partly attribute this to GZIp being unoptimized to the generated Python programs, a phenomenon we discuss in more detail $5.3
"CompressionRate higher than when the compressed representation is larger than the original.

---

Published as a conference paper at ICLR 2025
Audio- 16 bit
Audio & bit Prec.
Audio MFFCC
DNA
Text
Syn
Prec.
Acc.
Acc.
Prec.
Acc.
Prec.
Acc.
Prec.
Acc.
Prec.
1-AMA-3.1-5R
59
1.54
3.9
1.74
888
1.51
377
2.34
14
3.12
8.5
2.48
LLAMA-3.1-708
10.1
24.2
22.5
2.18
3.17
LLAMA-3.1
35.6
1.66
15.0
1.66
29.6
1.58
24.8
2.06
3.17
33.3
2.18
GPT4-0
|
364
SuoConnR-1.58
<0.1
ata
0.1
0.57
SEOCODER-SB
<0.1
0.1
m/a
0.1
ml
0.0
0.0
WV
92.5
0.56
Table Accuracy and Precision for zero-shot prompted models on the KoLMoGoROV-TEsS for sequences of length 128. Larger models have higher Accuracy. On synthetic distributions when sampling program-sequence pairs is possible, our trained SEQCoDER performs best and is the only model to achieve Precision that is lower than 1.0, i.e., it outperforms GZIP when programs are correct. However, it performs poorly on real data.
Our trained SEQCODER models significantly outperform all CODELMS on synthetic data, and are the only models with a better Precision than the naive REPEAT baseline (which has perfect Accu- racy and Precision of 1.0 by definition), suggesting that training data and strong priors are nec- essary for good performance. Nevertheless, reaches near-zero performance on natural sequences. We discuss generalization to real data in more detail in $5.2 and $5.
We present results for LLAMA with CoT prompting in $ B.2 Tab. We observe similar trends, albeit lower performance for LLAMA-3. 1-8B and LLAMA-3 -70B (a drop of 1.3 and 5.1 points in Accuracy on average across modalities), and a small increase of 2.1 points Accuracy for LLAMA- 3.1-405B. For OI-MINI, we observe overall similar results to GPT4-0 (see $B.2] Tab. [ mode details). Overall, our results are in line with recent work showing that CoT does not consistently improve performance for code generation tasks (Sprague al. 2025 Zheng al. 2025
5.2 TRAINED CODELMS OUTPERFORM PREVIOUS COMPRESSION ALGORITHMS
Fig. presents Compression Rate on synthetic data for SEQ- CODER models. Even though instruction-tune models strug- gle on this distribution, models can be trained to outperform previous compression algorithms, reaching Compression- Rate of 0.38 for SEQCODER-SB. outperforming the strong GZIP and LMIC baselines without requiring gigabytes of LLM weights for decoding (in $B.2 we empirically show that GZIP and LMIC are strong baselines and that scaling also improves Accuracy on synthetic data).
0:59
oz
50.80 ml
Compandio
Length generalization. To better test if improvements synthetic data generalize to real data, we evaluate SEQCODER models 10,000 shorter Audio-MFCC sequences of lengths 16-64, presented in Fig. 5 All models perform poorly on longer sequences of length 64. Models trained on 100K and REROODER--.----I
Figure 4: CompressionRate for SEQCODER models trained on 10K-1M program-sequence pairs. Models trained on enough data outperform the basclines.
IM examples significantly outperform on shorter sequences, and larger SEoCODER 8B perform best.
Fig. о presents the length of correct prefixes for SEOCODER on Audio-MFCC sequences of length 128. SEQCODER- 1.5B models trained on 10K examples fail early, i.e., more than 99% of programs have an emor in the first 16 characters, even though the model correctly produces programs for 27.2% of sequences of the same length (Fig. 5). Models trained on 100K and 1M examples perform better, but they exhibit similar trends, and in the first 16 characters in 93.5% and 88.7% 3% of test cases. We provide additional evidence that longer synthetic programs and sequences challenging for SEOCODER- 1.5BB in B.3] Fig. T and Fig. T1b
Tab. 2 presents results for GZIP and LLAMA-3.1 1.1.AMA-3.114000 1-005B on a random sample of 2,000 Audio-8-bii sequences of lengths 16-128. As expected, CompressionRate for GZIp improves with length, as it is able to better exploit patterns in the input data (we extend to longer sequences for GZIp and LMIC in B.2 Tab. 6. showing that these are strong baselines and CompressionRate is correlated
7

---

Published as a conference paper at ICLR 2025
GZIP CR
LLAMA-405B
Length
Acc.
Prec.
Syn.
Audio
16
0.966
47.1
3.20
32
0.846
29,9
2.70
5Q-1.5B
86.6
6.5
64
0.736
20.9
1.82
+ feed only
77.6
0.622
14.2
1.67
+ feed & ex
73.9
8.7
1M
0.398
n/a
n/a
Table 3: Accuracy for synthetic sequences and Audio MFCC sequences of length 64 bytes with and without execution feed- back. Execution feedback is not sufficient to close the gap between synthetic and real data.
Table 2: Effect of input length on Audio- 8-bit sequences. Performance improves for GZIP and RanpressionRate as lengths in- crease, but Accuracy decreases.
with length). However, for prompted models, longer sequences decreases with length. Overall, these results suggest that while scaling to large models is beneficial, generalization long sequences and from synthetic real distributions remains major challenge.
challenging and Accuracy
<0.0
1.50-1KK
1.5 00C 1.50-M
00-1M
40.0
30.0
20.0
10.0
0.5
18
32
64
120
0.0
16
84
128
SecCoder Accuracy on sequences
SecCoder Programs with Correct Prefix of Length 16-128
Figure 5: Accuracy for our SEoCODER- 1.5B on Audio MFCC sequences of lengths 16-128. Models trained on more ex- amples are significantly better on short se- quences, but all models struggle longer ones.
Figure 6: The longest correct prefix length for SEQCODER quences of length 128. Models trained on more examples and more parameters gener- ate longer correct prefixes.
Audio MFCC
5.3 ADDITIONAL ANALYSES
To examine the effect adding exccution feedback (Yang et al. 2023 (hooaae al., 2023 Ni et al. 2024), experiment with variants: (a) feedback only during training: execution feedback is added to training examples, and (b) feedback & execution: the code is executed by an interpreter at each line and results are presented the model before the next step. In both cases the feedback is added as an end-of-line comment (see BB.3 Fig. 12).
Effect of execution feedback.
Tab. 3 presents our results for 1,280 synthetic and 1,280 Audio-MFCC sequences of length 64. Execution feedback leads to small gains on real data, but also decreases performance on synthetic data and is not sufficient significantly improve performance. This can partially attributed the fact that most training is spent on feedback tokens and the model is only trained on gold programs, and hence is not trained to dynamically fix model errors or bad trajectories (Ni al. 2024).
Repetitions of input data. Python is highly expressive there are many ways the model can repeat input sequences (e.g., g.. by extracting to multiple sub-sequences that are later concatenated, see BB. Fig. 13 and Fig. 14. To check how often repetitions happen, we perform qualitative analysis for 25 correct programs per modality (chosen randomly) for our LLAMA-3.1 3.11..1.44 1405B and GPT4-0 prompted models, presented in Tab. We find that repetitions account for most correct predictions on natural data (more than 95% on average), but only 20% on our synthetic sequences, where models are able to leverage the synthetically induced patterns (Fig. 15). Hence, the low
8

---

Published as a conference paper at ICLR 2025
Precision of our prompted models can be partly attributed to the GZIP prior being under-optimized to Python programs.
Error analysis. To understand the errors our models make, manually analyze 25 errors per modality for LLAMA-3. 1-...B and GPT4-0, presented in Tab. [o] For both natural and syn- thetic sequences, most emrors caused by models misusing specific operators during execution, e.g., the wrong number of repetitions for a character (see Fig. [16 and Fig. 17 in $B.3). 3 This can be attributed to the fact that current LLMS still struggle with symbolic reasoning and counting in particular (Hendrycks et al. 2021 Yehudai et al. 2024 Ball et al. 2024
Additionally, we identify couple of specific failure cases. In more than 30% of cases, models try repeating the input sequence by breaking it to sub-sequences that are later merged, but still introduce subtle errors when constructing and merging these sub-sequences (Fig. 18 We identify special failure case for the text modality, where models successfully reverse-engineer our data generation process and generate a string which they convert to UTF-8-ent -rF-oden bytes, but often with subtle errors leading to low success rates (Fig. 19
6 RELATED WORK
Data compression. Data compression one of the main problems computer science com- munications. In addition to the works described in [2 fundamental work includes [Shannon (1948);
Cover & Thomas (2006). See [Salomon (2004); Lelewer & Hirschberg (1987): Jayasankar et al. (2021) for detailed surveys. A major line of work is devoted towards domain-specifie algorithms, including specifically for text, audio, and DNA (Storer & Szymanski] 1982 Neuburger 2010) Salau al. 2019 Du et al.] 2020). Recently, it has been proposed that LLMs can be harnessed for compression via arithmetic coding (Valmeekam et al. 2023 Deletang et al. 2024). While the raw compression rate (excluding the weights of the LLM) of this method outperforms classical compres- sion algorithms, the full LLM parameters are required for decoding. Our work differs by prompting and training CODELMS directly generate programs that produce the original data.
Evaluation of CODELMS. Recent jumps in the coding ability of LLMs (Chen et al. 2021 Rozière et al. 2024) paved the path benchmarks that focus on code generation. For example, Chen et al. (2021) on generating code given function's 's signature, (Austin et al. (202T) on solving coding interview questions, and [Li al.] (2022) focus on competitive programming tasks. Other benchmarks focus agentic settings where models interact with an environment to solve GitHub issues or run research experiments (Jimenez et al. 2024, [Bogin et al., 2024). KT has several advan- tages over previous benchmarks: there is abundance of diverse natural data, strong baselines for compression already exist, and evaluation metrics are well-defined. Our work suggests that making progress on KT is challenging and new innovations are needed for further progress. Moreover, to outperform current compression methods, CODELMS must model complex environments, poten- tially improving their ability to act as world models (Tang et al.) 2024).
Synthetic data augmentation for coding and symbolic reasoning. Synthetic data augmentation has been recently shown to be highly effective in injecting numerical skills LMs (Geva et al. 2020
Yoran et al. [022]] Lu et al., 2024 MMtra et al., [202]), however improvements do not necessarily generalize (Liu et al.) 2023a). More complex pipelines for synthetic data generation with LLMs are often used for CODELMS (Rozière et al. (2024).
7 DISCUSSION AND LIMITATIONS
Generalization from synthetic to real data. Our results show that generalization from synthetic to real distributions remains a challenge. Future work can experiment with methods that tilt the syn- thetic distribution towards the real one, e.g., by filtering easy-to-detect synthetic sequences (Ganin) & Leepptsky 2015). An exciting direction for future research is to model KT reinforcement learning task (François-
et al. 2018 Mnih et al., 2013) and learn from a reward when cor- rect solutions generated, with bias towards shorter solutions (Ellis et al. (023). Additionally, future methods can benefit from curriculum- -eauunnn--ennnnggna where models learn simpler examples before
more complex ones (Hacohen & Weinshall 2019 Soviany et al. 2022)

---

Published as a conference paper at ICLR 2025
Additional modalities. This work focuses on natural text, audio, and DNA sequences in addition to our synthetic data, and can be easily extended to cover additional modalities such as publicly- available image and video sequences (Deng al. 2009 SSommo et al., 2012). An exciting direction for future work is to mix training examples from different domains, composing of different patterns and functionalities. Additionally, only focus on the ability of CODELMS compress sequences of data, and leave compression of executable programs for future work.
Compressing larger amounts of data. In this work, we focus on compressing 1MB of data, a smaller amount than previous work (Deletang et al.) 2024) and the Hutter Prize (Hutter) 2009), which focus on IGB of data per modality. We opt for IMB sequences as this amounts to roughly 60K sequences across all modalities (around 20K for 1MB of DNA and 7800 sequences for each of the other modalities), a relatively large amount of examples in terms current code generation benchmarks (Chen al. [ larger sequences is likely to be feasible as CODEL and hardware continue to improve. To assist further progress, will also release IGB versions of our datasets.
(Austin et al. 2021 Li et al., 2022 Nevertheless, compressing
Scaling to longer sequences. In our synthetic experiments, we set the maximum size of a sub- sequence to 25, and the maximum number initiated sub-sequences to 5 (see $(A.2 for all hyper- parameters), Hence, a program will not produce a sequence of more than 125 random characters (concatenating sub-sequences of 25 random characters), but can produce longer sequences by using modifiers, e.g.. by repeating sub-sequence. Extending our DSL to longer sequences, for example by further scaling training compute, can be an interesting direction for future research.
Morcover, longer sequences sequences yield lower compression rates, exemplified for GZIP in Tab. 2 Although we mainly experiment with sequences of length 128 due to the low Accuracy of current models long sequences, future models might be able achieve better compression much longer sequences.
Other languages We have experimented with general Python as well as simple sequence- oriented DSL. Future work could explore how the choice of language affects the performance of models, the rate of training progress, and the degree of generalization to OOD sequences.
Stronger priors. In experiments used the GZIP prior for programs from our prompted models and our uniform prior over our synthetic DSL. Future work can experiment with stronger priors, e.g., small LMs that are trained on the distribution of programs. Another possible future direction is to focus on lower level languages where developing strong priors might be simpler. Although such programs might be harder for humans understand, the potential of CODELMS to generate novel solutions is an exciting opportunity for future work.
Runtime compute. In our experiments, we do not consider the runtime compute of programs execution. To limit the effect of inefficient programs, limit the runtime of each program five seconds and consider programs that run for longer as non-executable (similar to runtime exceptions). We provide additional statisties failed and non-executable programs in (B.2 Similarly, we do not consider the weights of the LLM (which are only required for generating the programs) or the cost of the Python standard library required to execute the programs. Additionally, we leave experimenting with specialized tokenization methods, e.g.. Dagan et al. (2024), for future work.
8 CONCLUSION
In this work we introduce the KoLMOGOROV- TEST,, a compression-as as -stii-ellinnnnnccce test for code generation models, based on the notion of Kolmogorov complexity. To evaluate current models, we use real audio, text, and DNA data, and develop an automatic framework for sampling program- sequence pairs. KT is extremely challenging for current models, including LLAMA-3. 1.AMA-3.1-455. 1-40BB and GPT4-0. Additionally, for synthetic distributions where pairs can be automatically sampled, trained models have a better Compression Rate than current methods. As our method can potentially be scaled to an infinite number of real problems of varying difficulty, it can provide challenging evaluation test-bed for future code generation models and pave the path towards new methods that compress large amounts of real data.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY
We have made significant efforts to ensure our work can be reproduced. Our datasets will be fully released, including our DSL and synthetic data generation framework. We will also release larger IGB variants to facilitate future research. In addition, we will release code to reproduce results with our prompted models and will host a live leaderboard allow the community to monitor future developments. As we will not be able to open-weight our SEQCODER models, we will release training code for SEQCODER-88 models on our synthetic pairs, enabling reproduction of our results and simplify training new SEQCODER models.
ETHICS STATEMENT
In this work, we introduce the KoL.MoGORVV-TEST, challenging intelligence test for CODEL based on the notion of Kolmogorov complexity. While we do not see any immediate risk caused by KT, code generation research is not without risk. Powerful models can be used for malicious reasons, e.g., by hackers or other malicious users. If compression via zero-shot code generation was solved, it might enable leap in telecommunications efficiency while at the same time raising concerns about opaque behavior of strong artificial intelligence.
REFERENCES
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. Program synthesis with large language models, 2021. URL httpt::///// /trxivivvv/..////// www.rxi....ggaaa.e 21 2000000000 07732
Thomas Ball, Shuo Chen, and Cormac Herley. Can we count on LLMs? the fixed-effect fallacy and claims of GPT-4 capabilities. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL http://///ppeeeeeeeeeeeee/eoooot
Yonatan Bisk, Rowan Zellers, Ronan Le bras, Jianfeng Gao, and Yejin Choi. Piqa: Reasoning about
physical commonsense in natural language. Proceedings of the AAAI Conference on Artificial Intelligence, 34005);4432-7439, Apr. 2020.
doi: 10.1609/aaai, h341:///aai..4005....0 (34105.6239) URL https://
ojs aaai org http:/idexxxo http:/iinxxx.pp//aaae.me AAAI article/view/bb// 6239
Ben Bogin, Kejuan Yang. Shashank Gupta, Kyle Richardson, Erin Bransom, Peter Clark, Ashish Sabharwal, and Tushar Khot. SUPER: Evaluating agents on setting up and exccuting tasks from research repositories. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Pro- ceedings of the 2024 Conference on Empirical Methods Natural Language Processing, pp- 12622 12645, Miami, Florida, USA, November 2024. Association for Computational Linguis- URL aelcaannhllogyy org/2024.
tics. doi:
emmlpp ma iomain.... 7027
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fo- tios Chantzis, Elizabeth Barnes, Ariel MeererrtVosss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike. Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob Mc- Grew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code, 2021. URL https: arxiv. htt.gggabb/21101 03374
N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 2(3):1 13-1224 1956. doi:
1056813.
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv: 1803 05457v1. 2018
11

---

Published as a conference paper at ICLR 2025
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecom- munications and Signal Processing). Wiley- Wiley--nterscceence, USA, 2006. ISBN 0471241954.
Gautier Dagan, Gabriel Synnaeve, and Baptiste Rozière. Getting the most out of your tokenizer for pre-training and domain adaptation. In Proceedings of the 41st International Conference on Machine Learning, ICML' 24. JMLR.org. 2024.
Gregoire Deletang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christo- pher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. Language modeling is compression. In The Twelfth International Confer- ence on Learning Representations, 2024. URL https: https::/openreviiii net / Forum?id= janbgiynus
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-2552 2009. doi: 10.1 1...10/R.R...09.... 520.5448888.
Deutsch. RFC1952: GZIP file format specification version 4.3. RFC Editor, USA, 1996.
Shasha Du, Jialin Li, and Ning Bian. A compression method for dna. PLoS One, 15(11))e0238220 November 2020. doi: 10. www.a/uaaaallo..eeo....
Published 2020 Nov 25.
Kevin Ellis, Lawrence Wong, Max Nye, et al. Dreamcoder: growing generalizable, interpretable knowledge with wake sleep bayesian program learning. Philosophical Transactions of the Royal Society A: Mathematical. Physical and Engineering Sciences, 381(2251), 2023.
Vincent François-Laves Peter Henderson, Riashat Islam, Marc G. Bellemare, and Joelle Pineau. An introduction to deep reinforcement learning. Foundations and Trends@ in Machine Learning, 11 (3-4):219-354, 2018. ISSN 1935-8245. doi: 10.1561/22000000771
htttht:://// doi.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In Pro- ceedings of the 32nd International Conference on International Conference on Machine Learning -Volume 37, ICML'15. pp. 1180-1189 1189. JMLR.org. 2015.
Mor Geva, Ankit Gupta, and Jonathan Berant. Injecting numerical reasoning skills into language models. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguisties, pp. 946-958, Online, July 2020. Association for Computational Linguistics. doi: 10. 1825 URL
org.//ggg///.ooo.. 2020.
89
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Ko- renev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurelien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Roziere, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak. Chloc Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius, Daniel Song, Danielle Pintz, Danny Livshits, Danny Wyatt, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Garcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Francisco Guzmán, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Govind That- tai, Graeme Nail, Gregoire Mialon, Guan Pang, Guillem Cucurell, Hailey Nguyen, Hannah Kore- vaar, Hu Xu, Hugo Touvron, Iliyan Zarov, Imanol Arrieta Ibarra, Isabel Kloumann, Ishan Misra, Ivan Evtimov, Jack Zhang, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Ma- hadeokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong, Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang, Jiecao Yu, Joanna Bitton, Joe Spisak, Jong- soo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Vasuden Alwala, Karthik Prasad, Kartikeya Upasami. Kate Plawiak, Ke Li, Kenneth Heafield, Kevin Stone, Khalid El-Arini, Krithika Iyer, Kshitiz Malik, Kuenley Chiu. Kunal Bhalla, Kushal Lakhotia. Lauren Rantala- Yeary, Laurens van der Maaten, Lawrence Chen, Liang Tan, Liz Jenkins, Louis Martin, Lovish Madaan, Lubo Malo, Lukas Blecher, Lukas Landzaat, Luke de Oliveira, Madeline Muzzi,
12

---

Published as a conference paper at ICLR 2025
Mahesh Pasupuleti, Mannat Singh. Manohar Paluri, Marcin Kardas, Maria Tsimpoukelli, Mathew Oldham, Mathieu Rita, Maya Pavlova, Melanie Kambadur, Mike Lewis, Min Si, Mitesh Ku- mar Singh, Mona Hassan, Naman Goyal, Narjes Torabi, Nikolay Bashlykov, Nikolay Bogoy- chev, Niladri Chatterji, Ning Zhang, Olivier Duchenne, Onur Çelebi, Patrick Alrassy, Pengchuan Zhang, Pengwei Li, Petar Vasic, Peter Weng. Prajjwal Bhargava, Pratik Dubal, Praveen Krishnan, Punit Singh Koura, Puxin Xu, Qing He, Qingxiao Dong, Ragavan Srinivasan, Raj Ganapathy, Ra- mon Calderer, Ricardo Silveira Cabral, Robert Stojnic, Roberta Raileanu, Rohan Maheswari, Ro- hit Girdhar, Rohit Patel, Romain Sauvestre, Ronnie Polidoro, Roshan Sumbaly, Ross Taylor, Ruan Silva, Rui Hou, Rui Wang, Saghar Hosseini, Sahana Chennabasappa, Sanjay Singh, Sean Bell, Seohyun Sonia Kim, Sergey Edunov, Shaoliang Nie, Sharan Narang. Sharath Raparthy, Sheng Shen, Shengye Wan, Shruti Bhosale, Shun Zhang, Simon Vandenhende, Soumya Batra, Spencer Whitman, Sten Sootla, Stephane Collot, Suchin Gururangan, Sydney Borodinsky, Tamar Herman, Tara Fowler, Tarek Sheasha, Thomas Georgiou, Thomas Scialom, Tobias Speckbacher, Todor Mi- haylov, Tong Xiao, Ujjwal Karn, Vedanuj Goswami, Vibhor Gupta, Vignesh Ramanathan, Viktor Kerkez, Vincent Gonguet, Virginie Do. Vish Vogeti, Vítor Albiero, Vladan Petrovic, Weiwei Chu, Wenhan Xiong, Wenyin Fu, Whitney Meers, Xavier Martinet, Xiaodong Wang, Xiaofang Wang, Xiaoqing Ellen Tan, Xide Xia, Xinfeng Xie, Xuchao Jia, Xuewei Wang, Yaelle Gold- schlag, Yashesh Gaur, Yasmine Babaei, Yi Wen, Yiwen Song. Yuchen Zhang, Yue Li, Yuning Mao, Zacharie Delpierre Coudert. Zheng Yan, Zhengxing Chen, Zoe Papakipos, Aaditya Singh, Aayushi Srivastava, Abha Jain, Adam Kelsey, Adam Shajnfeld, Adithya Gangidi, Adolfo Victoria, Ahuva Goldstand, Ajay Menon, Ajay Sharma, Alex Boesenberg, Alexii Baevski, Allie Feinstein, Amanda Kallet, Amit Sangani, Amos Teo, Anam Yunus, Andrei Lupu, Andres Alvarado, An- drew Caples, Andrew Gu, Andrew Ho, Andrew Poulton, Andrew Ryan, Ankit Ramchandani, An- nie Dong, Annie Franco, Anuj Goyal, Aparajita Saraf, Arkabandhu Chowdhury, Ashley Gabriel, Ashwin Bharambe, Assaf Eisenman, Azadeh Yazdan, Beau James, Ben Maurer, Benjamin Leon- hardi, Bernie Huang. Beth Loyd, Beto De Paola, Bhargavi Paranjape, Bing Liu, Bo Wu, Boyu Ni, Braden Hancock, Bram Wasti, Brandon Spence, Brani Stojkovic, Brian Gamido, Britt Mon- talvo, Carl Parker, Carly Burton, Catalina Mejia, Ce Liu, Changhan Wang, Changkyu Kim, Chao Zhou, Chester Hu, Ching-Hsiang Chu, Chris Cai, Chris Tindal, Christoph Feichtenhofer, Cynthia Gao, Damon Civin, Dana Beaty, Daniel Kreymer, Daniel Li, David Adkins, David Xu, Davide Testuggine, Delia David, Devi Parikh, Diana Liskovich, Didem Foss, Dingkang Wang. Due Le, Dustin Holland, Edward Dowling, Eissa Jamil, Elaine Montgomery, Elconora Presani, Emily Hahn, Emily Wood, Eric-Tuan Le, Erik Brinkman, Esteban Arcaute, Evan Dunbar, Evan Smoth- ers, Fei Sun, Felix Kreuk, Feng Tian, Filippos Kokkinos, Firat Ozgenel, Francesco Caggioni, Frank Kanayet, Frank Seide, Gabriela Medina Florez, Gabriella Schwarz, Gada Badeer, Georgia Swee, Gil Halpern, Grant Herman, Grigory Sizov, Guangyi, Zhang, Guna Lakshminarayanan, Hakan Inan, Hamid Shojanazeri, Han Zou, Hannah Wang, Hanwen Zha, Haroun Habeeb, Harri- son Rudolph, Helen Suk, Henry Aspegren, Hunter Goldman, Hongyuan Zhan, Ibrahim Damlaj, Igor Molybog. Igor Tufanov, Ilias Leontiadis, Irina-Elena Veliche, Itai Gat, Jake Weissman, James Geboski, James Kohli, Janice Lam, Japhet Asher, Jean -aptisee Gaya, Jeff Mareus, Jeff Tang, Jen- nifer Chan, Jenny Zhen, Jeremy Reizenstein, Jeremy Teboul, Jessica Zhong, Jian Jin, Jingyi Yang, Joe Cummings, Jon Carvill, Jon Shepard, Jonathan McPhie, Jonathan Torres, Josh Ginsburg, Jun- jie Wang, Kai Wu, Kam Hou U, Karan Saxena, Kartikay Khandelwal, Katayoun Zand, Kathy Matosich, Kaushik Veeraraghavan, Kelly Michelena. Keqian Li, Kiran Jagadeesh. Kun Huang, Kunal Chawla, Kyle Huang, Lailin Chen, Lakshya Garg, Lavender A, Leandro Silva, Lee Bell, Lei Zhang. Liangpeng Guo, Licheng Yu, Liron Moshkovich, Luca Wehrstedt, Madian Khabsa, Manav Avalani, Manish Bhatt, Martynas Mankus, Matan Hasson, Matthew Lennie, Matthias Reso, Maxim Groshev, Maxim Naumov, Maya Lathi, Meghan Keneally, Miao Liu, Michael L. Seltzer, Michal Valko, Michelle Restrepo, Mihir Patel, Mik Vyatskov. Mikayel Samvelyan. Mike Clark, Mike Macey, Mike Wang, Miquel Jubert Hermoso, Mo Metanat, Mohammad Rastegari, Munish Bansal, Nandhini Santhanam, Natascha Parks, Natasha White, Navyata Bawa, Nayan Singhal, Nick Egebo,, Nicolas Usunier, Nikhil Mehta, Nikolay Pavlovich Laptev, Ning Dong, Norman Cheng, Oleg Chernoguz, Olivia Hart, Omkar Salpekar, Ozlem Kalinli, Parkin Kent, Parth Parekh, Paul Saab, Pavan Balaji, Pedro Rittner, Philip Bontrager, Pierre Roux, Piotr Dollar, Polina Zvyagina, Prashant Ratanchandani, Pritish Yuvraj, Qian Liang. Rachad Alao, Rachel Ro- driguez, Rafi Ayub, Raghotham Murthy, Raghu Nayani. Rahul Mitra, Rangaprabhu Parthasarathy, Raymond Li, Rebekkah Hogan, Robin Battey, Rocky Wang. Russ Howes, Ruty Rinott, Sachin Mehta, Sachin Siby, Sai layesh Bondu, Samyak Datta, Sara Chugh, Sara Hunt, Sargun Dhillon, Sasha Sidorov, Satadru Pan, Saurabh Mahajan, Saurabh Verma, Seiji Yamamoto, Sharadh Ra-
13

---

Published as a conference paper at ICLR 2025
maswamy, Shaun Lindsay, Shaun Lindsay, Sheng Feng. Shenghao Lin, Shengxin Cindy Zha, Shishir Patil, Shiva Shankar, Shuqiang Zhang, Shuqiang Zhang, Sinong Wang, Sneha Agarwal, Soji Sajuyigbe, Soumith Chintala, Stephanie Max, Stephen Chen, Steve Kehoe. Steve Satter- field, Sudarshan Govindaprasad, Sumit Gupta, Summer Deng, Sungmin Cho, Sunny Virk, Suraj Subramanian, Sy Choudhury, Sydney Goldman, Tal Remez, Tamar Glaser, Tamara Best, Thilo Koehler, Thomas Robinson, Tianhe Li, Tianjun Zhang, Tim Matthews, Timothy Chou, Tzook Shaked, Varun Vontimitta, Victoria Ajayi, Victoria Montanez, Vijai Mohan, Vinay Satish Ku- mar, Vishal Mangla, Vlad Ionescu, Vlad Poenaru, Vlad Tiberiu Mihailescu, Vladimir Ivanov, Wei Li, Wenchen Wang, Wenwen Jiang. Wes Bouaziz, Will Constable, Xiaocheng Tang. Xiao- jian Wu, Xiaolan Wang, Xilun Wu, Xinbo Gao, Yaniv Kleinman, Yanjun Chen, Ye Hu, Ye Jia, Ye Qi. Yenda Li, Yilin Zhang, Ying Zhang, Yossi Adi, Youngjin Nam, Yu, Wang, Yu Zhao, Yuchen Hao, Yundi Qian, Yunlu Li, Yuzi He, 7ach Rait, Zachary DeVito, 7ef Rosnbrick, Zhao- duo Wen. Zhenyu Yang, Zhiwei Zhao, and Zhiyu Ma. The llama 3 herd of models, 2024. URL https://arxiv: org/ abs/ 1.407.21782
Peter D. Grunwald and Paul M. B. Vitanyi. Algorithmic information theory, 2008 URL https:
//arxiv.org/aatt 0809.2754
Amirhossein Habibian, Ties Van Rozendaal, Jakub Tomczak, and Taco Cohen. Video compression with rate-distortion autoencoders. In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 7032-7041, 2019. doi: 10.1 10.1109/CCV.2211900000 900713..
Guy Hacohen and Daphna Weinshall. On the power of curriculum learning in training deep net- works, 2019. URL httttt://axxiiisii org/ wwtg/bb/////e aabs/1900 191/9994.... 03626
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. NeurIPS, 2021.
John H. Hoperoft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction Automata Theory, Lan- guages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., USA, 2006. ISBN 0321455363.
Marcus Hutter. The hutter prize for compressing human knowledge. Theoretical Computer Science, 410(51):5372-5388 2009. doi: 10. 10.1006/jjccs.20099
Mareus Hutter, Elliot Catt, and David Quarel. An introduction to universal artificial intelligence. Chapman & Hall/CRC, 2024.
Uthayakumar Jayasankar, Vengattaraman Thirumal, and Dhavachelvan Ponnurangam. A survey on data compression techniques: From the perspective of data quality, coding schemes, data type and applications. Journal of King Saud University Computer and Information Sciences, 33(2):119- 140, 2021. ISSN 1319-1578.
doi: http://doo.rr//1111116...kkk wttp://wwwwww....e...tttttttttt. htt.a//ccc...c.o..........eeoaaa
URL https:
Carlos E. Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik R Narasimhan. SWE-bench: Can language models resolve real-world github issues? In The Twelfth International Conference on Learning Representations, 2024. URL WRLLittpss///ppeeeeeet
net/ iinimiiddiiii 8yNQM66
Diederik P Kingma and Max Welling. Auto-encoding variational bayes, 2022. URL https:
7 7/arxiv. www.ii..rg/aaa//3333 wttp://g/aaaaaaaaeo..eeeeaeeeeee 1atbb. 6114
A. N. Kolmogorov. On tables of random numbers. Sankkyā: The Indian Journal of Statistics, Series
A (1961-2002), 25(4):369 1963. ISSN 0581572X. URL http: //tt:://www.... www. jstor.otooooo org/
stable/25049284
Debra A. Lelewer and Daniel S. Hirschberg. Data compression. ACM Comput. Surv., 19(3): 261-296, sep 1987. ISSN 0360-0300. doi: 10.1145/45022.450744 10.1145 75.7774444
URL /tthttss://cc...... org/
Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and Its Applica- tions. Springer- Springer-Verlag New York Inc., 01 1997. ISBN 9780387948683. doi: 10.1007/ 978-1-4757-2606-0.
14

---

Published as a conference paper at ICLR 2025
Rongao Li, Jie Fu, Bo-Wen Zhang. Tao Huang, Zhihong Sun, Chen Lyu, Guang Liu, Zhi Jin, and Ge Li. Taco: Topics in algorithmic code generation dataset, 2023. URL https://arxil erg/abs. 231.2332..0 14852
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Push- meet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level code generation with alphacode. Science, 378((822))))2)) http:///ww.iiiccccrrreeeoe ottaa///wee...aacccccccco....///
2022. doi: 10. 10.1126/science.angg 158.
Bingbin Liu, Sebastien Bubeck, Ronen Eldan, Janardhan Kulkarni, Yuanzhi Li, Anb Aguyen Rachel Ward, and Yi Zhang. Tinygsm: achieving '80 URL htttp::/axxi..rr////6t
09241
Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang. Is your code generated by chatGPT really correct? rigoruus evaluation of large language models for code generation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023b. URL https:
//openreview. fort/foumm?
d= d= OCu?
Zimu Lu, Aojun Zhou, Houxing Ren, Ke Wang, Weikang Shi, Junting Pan, Mingjie Zhan, and Hongsheng Li. MathGenie: Generating synthetic data with question back-translation for en- hancing mathematical reasoning of LLMs. In Lun-Wei Ku, Andre Martins, and Vivek Sriku- mar (eds.). Proceedings of the 62nd Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pp. 2732-2747, Bangkok, Thailand, August 2024. Asso- ciation for Computational Linguisties. doi: 18655//11/0224ccllooggg
URL https:
-ccpoloogg..rr///22a.aaaaooooo-. 151
Arindam Mitra, Hamed Khanpour, Corby Rosset, and Ahmed Awadallah. Orca-math: Unlocking the potential of slms in grade school math, 2024. URL htttps::/axxx...rg///bbba
14830
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, 2013. URL
https://arxiv: /ttpss//axxxv..orr//b/////111 5602
NCBI. Genome reference consortium human build 38 (grch38), 2023. URL httph:// /www. nobi
Shoshana Neuburger. The burrows- transform: data compression, suffix arrays, and pattern
matching by donald adjeroh, timothy bell and amar mukherjee springer, 2008 SIGACT News, 41 (1):21-24, mar 2010. ISSN 0163-5700, doi: 10. 10.114//153111.1175311 URL httpps://ooi.
org/10 10111111511111 1753177
Ansong Ni, Miltiadis Allamanis, Arman Cohan, Yinlin Deng, Kensen Shi, Charles Sutton, and Pengcheng Yin. Next: teaching large language models reason about code execution. In Pro- ceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org, 2024.
OpenAl, Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed EI-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, Alex Iftimie, Alex Karpenko, Alex Tachard Passos, Alexander Neitz, Alexander Prokofiev, Alexander Wei, Allison Tam, Ally Bennett, Ananya Kumar, Andre Saraiva, Andrea Vallone, Andrew Duberstein, Andrew Kondrich, Andrey Mishchenko, Andy Applebaum, Angela Jiang, Ashvin Nair, Barret Zoph. Behrooz Ghor- bani, Ben Rossen, Benjamin Sokolowsky, Boaz Barak, Bob McGrew, Borys Minaiev, Botao Hao, Bowen Baker, Brandon Houghton, Brandon McKinzie, Brydon Eastman, Camillo Lugaresi, Cary Bassin, Cary Hudson, Chak Ming Li, Charles de Bourcy, Chelsea Voss, Chen Shen, Chong Zhang, Chris Koch, Chris Orsinger, Christopher Hesse, Claudia Fischer, Clive Chan, Dan Roberts, Daniel Kappler, Daniel Levy, Daniel Selsam, David Dohan, David Farhi, David Mely, David Robinson, Dimitris Tsipras, Doug Li. Dragos Oprica, Eben Freeman, Eddie Zhang, Edmund Wong, Eliz- abeth Prochl, Enoch Cheung, Eric Mitchell, Eric Wallace, Erik Ritter, Evan Mays, Fan Wang, Felipe Petroski Such, Filippo Raso, Florencia Leoni, Foivos Tsimpourlas, Francis Song, Fred
15

---

Published as a conference paper at ICLR 2025
von Lohmann, Freddie Sulit, Geoff Salmon, Giambattista Parascandolo, Gildas Chabot, Grace Zhao, Greg Brockman, Guillaume Leclere, Hadi Salman, Haiming Bao, Hao Sheng, Hart An- drin, Hessam Bagherinezhad, Hongyu Ren, Hunter Lightman. Hyung Won Chung, Ian Kivlichan, Ian O'Connell, Ian Oshand, Ignasi Clavera Gilaberte, Iige Akkaya, Hla Kostrikov, llya Sutskever, Irina Kofman, Jakub Pachocki, James Lennon, Jason Wei, Jean Harb, Jerry Twore, Jiacheng Feng. Jiahui Yu, Jiayi Weng, Jie Tang, Jieqi Yu, Joaquin Quiñonero Candela, Joe Palermo, Joel Parish, Johannes Heidecke, John Hallman, John Rizzo, Jonathan Gordon, Jonathan Uesato, Jonathan Ward, Joost Huizinga, Julie Wang, Kai Chen. Kai Xiao, Karan Singhal, Karina Nguyen, Karl Cobbe, Katy Shi, Kayla Wood, Kendra Rimbach, Keren Gu-Lemberg, Kevin Liu, Kevin Lu, Kevin Stone, Kevin Yu, Lama Ahmad, Lauren Yang. Leo Liu, Leon Maksin, Leyton Ho, Liam Fedus, Lilian Weng. Linden Li, Lindsay McCallum, Lindsey Held, Lorenz Kuhn, Lukas Kon- draciuk, Lukasz Kaiser, I Luke Metz, Madelaine Boyd, Maja Trebacz, Manas Joglekar, Mark Chen, Marko Tintor, Mason Meyer, Matt Jones, Matt Kaufer, Max Schwarzer, Meghan Shah, Mehmet Yatbaz, Melody Y. Guan, Mengyuan Xu, Mengyuan Yan, Mia Glaese, Mianna Chen, Michael Lampe, Michael Malek, Michele Wang, Michelle Fradin, Mike McClay, Mikhail Pavlov, Miles Wang, Mingxuan Wang, Mira Murati, Mo Bavarian, Mostafa Rohaninejad, Nat McAleese, Neil Chowdhury. Neil Chowdhury, Nick Ryder, Nikolas Tezak, Noam Brown, Ofir Nachum, Oleg Boiko, Oleg Murk, Olivia Watkins, Patrick Chao, Paul Ashbourne, Pavel Izmailov, Peter Zhokhov, Rachel Dias, Rahul Arora, Randall Lin, Rapha Gontijo Lopes, Raz Gaon, Reah Miyara, Reimar Leike, Renny Hwang. Rhythm Garg, Robin Brown, Roshan James, Rui Shu, Ryan Cheu, Ryan Greene, Saachi Jain, Sam Altman, Sam Toizer, Sam Toyer, Samuel Miserendino. Sandhini Agar- wal, Santiago Hernandez, Sasha Baker, Scott McKinney, Scottie Yan, Shengjia Zhao, Shengli Hu, Shibani Santurkar, Shraman Ray Chaudhuri, Shuyuan Zhang. Siyuan Fu, Spencer Papay, Steph Lin, Suchir Balaji, Suvansh Sanjeev, Szymon Sidor, Tal Broda, Aidan Clark, Tao Wang. Tay- lor Gordon, Ted Sanders, Tejal Patwardhan, Thibault Sottiaux, Thomas Degry, Thomas Dimson, Tianhao Zheng, Timur Garipov, Tom Stasi, Trapit Bansal, Trevor Creech, Troy Peterson, Tyna Eloundou, Valerie Qi, Vineet Kosaraju, Vinnie Monaco. Vitchyr Pong, Vlad Fomenko, Weiyi Zheng, Wenda Zhou, Wes McCabe, Wojeiech Zaremba, Yann Dubois, Yinghai Lu, Yining Chen, Young Cha, Yu Bai, Yuchen He, Yuchen Zhang, Yunyun Wang, Zheng Shao, and Zhuohan Li. Openai 0l system card, 2024a. URL htttps://axxx....
http:::///axxv.orgg// wrw.bbs///////ooooooooo......... abs 22122 16720
OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Floren- cia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babusehkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Moham- mad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapiro, Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brock- man, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings. Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Floundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elic Georges, Christian Gib- son, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lppss Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hal- lacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga. Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Ka- mali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim. Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Lukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil. David Medina. Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong MU, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichiro Nakano, Ra-
16

---

Published as a conference paper at ICLR 2025
jeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O' O'Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford. Jack Rac, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Sel- sam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang. Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Pre- ston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vi- jayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang. Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Work- man, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. Gpt-4 technical report, 2024b. URL https: //rxivv org/ abs 2303. 08774
Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: An corpus based on public domain audio books. In 2015 IEEE International Conference on Acoustics, doi: 10.1109/CAASPP2005.
Speech and Signal Processing (ICASSP), pp. 5206-5210, 2015.
7178964.
R. Pasco. Source coding algorithms for fast data compression (ph.d. thesis abstr.). IEEE Transac- tions on Information Theory, 2344)5548-548 1977. doi: 10. 100110991T11997710555599
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training. 2018
Rissanen. Generalized kraft inequality and arithmetic coding. IBM Journal of Research and Development, 20(3):198-203, 1976. doi: 10. 10.1147/rd.203.013
Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Ev- timov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. Code Ilama: Open foundation models for code, 2024.
URL httphtttt:/aaaae /ttp:i//aavvvv.v
Ayodeji Olalekan Salau, Ifetayo Oluwafemi, Kehinde Felix Faleye, and Shruti Jain. Audio com- pression using modified discrete cosine transform with temporal auditory masking. In 2019 international conference on signal processing and communication (ICSC), pp. 135-142. IEEE, 2019.
David Salomon. Data Compression: The Complete Reference. Springer, New York, 4th edition, 2004.
C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27 (3):379 423, 1948. doi: 10.1002/j. 15002//.138-730000
Parshin Shojaee, Aneesh Jain, Sindhu Tipimeni, and Chandan K. Reddy. Execution-based code gen- eration using deep reinforcement learning. Transactions on Machine Learning Research, 2023. ISSN 2835-8855 8856. URL https: /eEtps::/oppereviiie
net Tt-
R.J. Solomonoff. A formal theory of inductive inference. part i. Information and Control, 7(1):1- 22, 1964. ISSN 0019-9958. doi: http://///o.a.a////o/../oooos//p URL https: httt
// www.
Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah. Ucf101: A dataset of 101 human actions 0402
classes from videos in the wild, 2012. URL htt.://ss///x....oo//////////
17

---

Published as a conference paper at ICLR 2025
Petru Soviany, Radu Tudor lonescu, Paolo Rota, and Nicu Sebe. Curriculum learning: A sur- vey. Int. J. Comput. Vision, 13066):152-11655 June 2022. ISSN 0920-5691. doi: 10.1007/ s11263-022-01611-x
Zayne Rea Sprague, Fangcong Yin, Juan Diego Rodriguez. Dongwei Jiang. Manya Wadhwa, Prasann Singhal, Xinyu Zhao, Xi Ye, Kyle Mahowald, and Greg Durrett. To cot or not to cot? chain-of-thought helps mainly on math and symbolic reasoning. In The Thirteenth International Conference on Learning Reprexentations, 2025. URI httthh:///ppprreeee
net forum?
id==6nl c58kkn
James A. Storer and Thomas G. Szymanski. Data compression via textual substitution. J. ACM, 29 (4):928-551, oct 1982 ISSN 0004-5411, doi: 10.11455323344522236 URL httpp://ddoi.
org/10. 11111453333 42/322444444.2 322346)
Hao Tang, Darren Yan Key, and Kevin Ellis. Worldcoder, a model-based LLM agent: Building world models by writing code and interacting with the environment. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. BtLhttts:: //tperevee//pereeee.... met/forumm id- QGJSXMMVaL
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer. Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Ilyaan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodrigue7, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models, 2023. URL.htttss//aaxii.....
abs 22002/37.0000 09288
A. M. Turing. On Computable Numbers, with an Application to the Entscheiduuggsprohllm... Pro- ceedings of the London Mathematical Society, 52-42(1) 01 1937. ISSN 0024-6115, doi: 10.11122pplss/2-422.1 1.230. /B/t///pp////aa...oo//01/111///2
Chandra Shekhara Kaushik Valmeekam, Krishna Narayanan, Dileep Kalathil, Jean-Francois Cham- berland, and Srinivas Shakkottai. Llmzip: Lossless text compression using large language models, 2023. URL
/twp///aavvvv//a///////aa///.aaa org/ abs hatgg//b///30.0. /2006 04050
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Proceedings of the 31st Inter- national Conference Neural Information Processing Systems, NIPS' 17, pp. 6000-6015 Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoe V Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Ad- vances Neural Information Processing Systems, 2022. URL U htt.thtt:://peeeeeeeeeeee Forum?id= _eeiddd___vvvvooe ViQ1MeSB_
n
John Yang, Akshara Prabhakar, Karthik R Narasimhan, and Shunyu Yao. Intercode: Standardizing and benchmarking interactive coding with execution feedback. In Thirty-sevntth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023. URL https:
//openzeview.o wwwprreviwwwwee/foo....eeee.
fvKaLF FirKaFFins3 1
Gilad Yehudai, Haim Kaplan, Asma Ghandeharioun, Mor Geva, and Amir Globerson. When can transformers count to n?, 2024. URL http://wwwww..og//////00...110.0
Ori Yoran, Alon Talmor, and Jonathan Berant. Turning tables: Generating examples from semi- structured tables for endowing language models with reasoning skills. In Smaranda Muresan,
18

---

Published as a conference paper at ICLR 2025
Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Pp. 6016-6031, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.18653/w//2222.clllogggg 416. URL htt.hhttt:://acc www.aaagt.oooooooooooooo.ooo http:////..niooooooooooor////aa/
416
Kunhao Zheng, Juliette Decugis, Jonas Gehring, Taco Cohen, benjamin negrevergne, and Gabriel Synnaeve. What makes large language models reason in (multi-turn) code generation? In The Thirteenth International Conference on Learning Representations, 2025. URL https:
//operrview net/ i d= 9gu01 9NS
19

---

Published as a conference paper at ICLR 2025
A DATA GENERATION
Additional details and statistics. We randomly choose audio sequences from LibriSpeech until reaching IMB of data. As we opt not to trim sequences, we are left with 1,015,360 bytes in the bit setting, 1,00,3280 bytes in the 8-bit setting, and 1,000,960 bytes in the MFCC setting. Similarly, we have 1,004,232 text bytes, and 1,000, 105 synthetic bytes. For DNA, we have exactly 1MB.
The maximum sequence length shown to models is 128. As do not merge between different origin sequences (i.e., an audio file or synthetic sequence), some sequences can be shorter. The average sequence length for natural sequences is 75.9 for our synthetic data, 126.0 for MFCC and 127.9 for all other modalities. We provide detailed statistics regarding synthetic program-sequence lenghts in A.2
Figures.
The DNA illustration in Fig. courtesy of The National Human Genome Research Institute
A.1 NATURALLY OCCURRING SEQUENCES
Audio MFCC. We use Libros: TO parse audio files to MFCC. Specifically, parse each file to 20 MFCCs. As MFCCs are floats, we round each float into an integer which we take modulo 256 obtain numbers in the range (0, 255). Note that this representation far from being reconstructible but we posit that it provides source of richly structured natural data nevertheless.
A.2 SYNTHETIC DATA GENERATION
Automatic generation of program-sequence pairs. Our DSL supports the following functions and can be easily extended in the future:
[nitiitor]] Set list: Initiates a fixed sequence of numbers.
[Initiator] Range: Initiates a sequence of increasing numbers from start to end index, either with or without step interval.
[Initiator] Repeat: Initiates sequence of repeated occurrences of same number.
[Modifier] Substitute: Substitutes a value in a list with different value.
[Modifier] Reverse: Reverses sequence.
[Modifier] Sub-sequence between indexes: Returns sub-sequence between two indexes, either with or without intervals.
[Modifier] Repeat list: Returns repetition of a sequence a specified number of times.
[Modifier] Max/Min: Returns the maximum minimum items in the sequence.
[Modifier] Add/SubrractModdulo Applies mathematical operation (addition, subtrac- tion, or modulo) with a specified fixed operand to all elements in the sequence.
[Modifier] Scan add: Returns sequence where the value at index is the sum of all items up to that index.
[Filter] Is even/odd Keeps only even or odd numbers in the sequence.
[Filter] Is non-zero: Keeps only non-zero numbers in the sequence.
[Merger] Add/Subtract/Mdduu two lists: Applies mathematical operation (addition, subtraction, or modulo) over elements at matching indexes in two sequences.
[Merger] Concatenate: Concatenates two sequences.
[Merger] Interleave: Interleaves one sequence with another in alternating indexes. If one sequence is longer, the remaining values will form the suffix of the interleaved sequence.
feature.nfoe.. htm1
20

---

Published as a conference paper at ICLR 2025
When sampling from our DSL, we first sample the initiators, then produce additional sequences using sampled filters and modifiers before the sub-sequences are composed by sampled mergers to form the final sequence. We can control the distribution of programs via the seper-parameters of the sampling process.
The number of initiators is uniformly sampled in range {1,..., 5). the length of each fixed sequence sampled uniformly in range 25}.
The probability to apply any mathemattcaal modifier (e.g., repeat substitute) is set to 0.4, and the probability for each specific modifier is set to 0.1. After the modification, we reuse the original sequence probability 0.2. For substitution, 0.25. Similarly. the probability to apply any mathematical modifier (c.g., Add/Subtract/Modulo)) to an initiated sequence or filter is set 0.4, and the probability for a specific filter set to 0.1. Mathematical mergers are treated similarly the probability to any mathematical merger is 0.4 and for a specific merger is 0.1. Finally, the probability for concatenate and interleave operations is set to 0.8 and 0.2, respectively, and we continue to concatenate and interleave sub-sequence until all sub-sequences are used the final output sequence.
exclude the original sequence probability
Additionally, make sure that sequences in our evaluation data will not be part of program- sequence pair during training. case a sequence generated by more than one program, we only keep the shortest program that produces the sequence in dataset.
Program-sequest lengths. Fig. 7 and Fig. presents the histogram of the lengths of our syn- thetic sequences and programs respectively.
Curulaative Il stogram of Program Lengths
Curuulative Histogram Lengths
1.0
0.9
0.6
0.5
Cammatrr
0.4
90
0.0
Length Sequencces
Figure 8: Cumulative histogram of program lengths (number of lines) for our synthetic distribution.
Figure 7: Cumulative histogram of sequence lengths for our synthetic distribution.
Uniform prior over DSL programs. Alg. presents the number of bits needed to sample pro- gram using the uniform prior over programs and arithmetic coding (Rissanen 1976. Pasco 1977). The cost to encode each line has two main components.
The first, is encode the method that is being called. Since use a uniform prior, this always log of the number of functions (stopping the generation and assigning one of the previously defined sequences as the output formulized as an additional function).
The second, is to encode the variables that are being passed to the function, which is determined by the environment and specific for each function. For example, setting a random list of elements (set list), requires / bytes, indicating the length of the list, and b indicating the number of bits in each byte. Similarly, concatenation two previously defined sub-sequences requires encoding the indexes of these sequences (which is log operation of the current number of lines), and repeating a character requires encoding the character (again, the byte size) and the number repetitions (log of the maximal number of allowed repetitions in the environment).
21

---

Published as a conference paper at ICLR 2025
Algorithm Encoding program under the uniform prior.
function
func panamp. hps)
hps.byte.size, "concatenate". (0sghhs.liee_indeee 2, "repeat_num: hps.byte_size hpp.mao..mm.rrpetiiiee
mapping { "set_isst": haalfuun.praasstitl...
return mapping/func]
end function
bils sper pprr-prrrae -fun:: +- logg (rumm,fucctionss +
for all i, ( -params) in enumerate((rogram lines) do
+= bits.pet -f
D bits to encode the function type # bits encode the function params
enconde_func.prrmms(( f f-params, hps, i)
end for return J:
A.3 FORMAL DEFINITION OF THE KOLMOGOROV-TEST
Alg. 2 presents formal definition of the KoLMoGOROV-TEsT CODELMs that generate shorter programs have better compression rates (see $4 for our metries and experimental settings).
Algorithm Compression by Code Generation (The KoLMoGOROVVTEST)
Require: Sequence x, CODELM M, Programs prior p
I: Generate program p with model M that produces the sequence
2: Encode p with prior p
3: return p(p)
B EXPERIMENTS
B. MODELS
GZIP baseline. We use the python implementation of GZI To enable reconstruction of the sequential data, we use new line as the separator between sequences.
LMIC baseline.
We use our B.QCODER-1.5B model for the results reported in $ and provide B.2
additional results
Prompted baselines. Fig. presents our full prompt used in prompted models experiments. We use vLLM 12) to set-up inference servers with the instruction-tumed LLAMA-3. models available
on HuggingFace
Trained models. Our SEQCODER- 1.5B model is a transformer (Vaswani et al. 2017 with 1.5 billion parameters. The model follows similar architecture to the recent LLAMA models Touvrron et al. 2023, Grattafiori et al. 2024) but with less parameters it has 24 layers, hidden-dimension of 2,048, multi-head attention with 16 heads, and a maximum sequence length of 2,048 tokens. To endow the model with coding and reasoning skills before training on synthetic data from our DSL, we pre-train on 200B tokens of publicly-availabe trained in relation to current state-of-the of-thh-artttttt models and hence significantly weaker, it achieves negligible performance on popular coding and reasoning tasks - Pass@1 of 1 11.6 on HumanEvalPlus (Liu et al. 2023b), and Accuracy of 28. 28.2% ARC (Clark et al. 2018) and 68. 2% PIQA (Bisk
text and code. Although this model is under-
et al. 2020
"https:: docs pwtpaoo..crr////laaaararrrraa.pp https://gihbu..o///limmppoogiooo
22

---

Published as a conference paper at ICLR 2025
System Prompt
Generate a Pythen program that, when executed, reproduces specified input sequence. The program should be as concise as possible.
Instructions
Instructions:
write multi-line Python program. Bach 1ine should either assign new variable define new function.
These variables and functions be reused throughout the program.
Identify and utilize patterns in the input sequence to minimize the length of the program.
Assign the final output of the sequence the variable output. This output will used to verify the correctness the program.
Do not include print statements or return statements. Ensure that the generated code is executable in Python interpreter without modifications.
Do not include the python code block syntax your response.
End your response with PH4.
Input Sequence:
#SEO#
### Expected Output:
The Python program that generates the sequence is:
Figure 9: Full prompt used in our zero-shot experiments.
Audio- 16-bit
Audio-B-bil Acc.
Audio-MFCC
DNA
Text
Syn.
Acc.
Prec.
Prec:
Acc.
Prec.
Acc.
Prec.
Acc.
Prec.
Acc.
Prec.
LLAMA-331188
2.9
1.60
2.05
5.4
1.59
69
38
0.
2.67
6.9
3.8
1L170-3.1-708
14.3
1.61
42
1.74
23.6
1.50
9.2
225
37
2.69
16.9
2.9
LLAMA-3.1 3.1-405B
37.9
10.4
49.7
23,4
1.4
30.5
Table 4: Accuracy and Precision for zero-shot prompted models on the KOLMoGOROV-TES, for sequences of length 128 with CoT. Trends are similar to those without CoT in Tab,
B.2 RESULTS
Chain-of-thought prompting does not lead to additional improvements. We present our CoT prompt in Fig. 10 and our experiments with CoT with LLAMA in Tab Similarly recent work Sprague et al. (2025) Zheng et al. (2025), we do not observe significant gains with CoT prompting.
We present the percentage of executable programs, accuracy for executable programs, and Accuracy for GPT4-0 and -I-MINT in Tab. 5 While 01-MIN has higher accuracy for executable programs (69.8 vs 63.2), also has lower percentage of executable programs (81.7 vs 89.9), and both models have similar Accuracy (57.2 vs 56.5), suggesting that while longer chains-of-thought are able to increase performance, they do not yet lead to major improvements on the KoLMoGoROV-
GZIP and LMIC are strong baselines. Tab. 6 presents results for our GZIP and LMIC base- lines, for sequences of length 128 and 1,02414 For GZIP we also compress all IMB as a single
"aac element in the sequence is single token, and consider the cost of generating the separator token for the L.IIC baseline.
comma separator hetween elements. We do
23

---

Published as a conference paper at ICLR 2025
System Prompt
Generate a Pythen program that, when executed, reproduces specified input sequence. The program should be as concise as possible.
Instructions
Instructions:
write multi-line Python program. Bach line should either assign new variable define new function.
These variables and functions be reused throughout the program.
Identify and utilize patterns in the input sequence to minimize the length of the program.
Assign the final output of the sequence the variable output. This output will used to verify the correctness the program.
Do not include print statements or return statements. Ensure that the generated code is executable in Python interpreter without modifications.
Do not include the python code block syntax your response.
End your response with IFF. Before the program, you generate how you think task should solved. After the thought, generate "The Python program that generates the sequence is:", followed by the program
the Thought field to
### Input Sequence:
#SEQ#
### Expected Output:
The Python program that generates the sequence is:
Figure 10: Full prompt used in our zero-shot CoT experiments. The difference from our non-CoT prompt in Fig. is highlighted.
GPT4-0 Ex. Acc.
O1-MINI Ex. Acc.
% Ex
Acc.
% Ex.
Acc.
Audio 16-bit
88.2
78.8
69.5
81.2
87.7
71.2
Audio-8-bii
94.6
38.5
36.4
82.2
51.1
42.0
Audio-MFCC
94.4
88.8
83.8
86.8
93.8
81.4
DNA
93.1
54.0
50.3
85.6
67.1
57.4
Text
76.5
70.8
54.2
82.8
53.6
44.4
Synthetic
92.9
48.1
44.7
71.4
65.8
47.0
Average 89.9
63.2
56.5
81.7
69.8
57.2
Table 5: The percentage of executable programs (% Ex.), accuracy for executable programs (Ex. Acc.), and Accuracy (Acc.) for GPT4-0 and o 01-MINI. To reduce costs, 01-MINI was evaluated on 500 random uub-sequences of length 128. On average, both models have similar Accuracy. O1-MINI has higher accuracy for executable programs, but a lower percentage of executable programs.
sequence. We note that stronger compression baselines exist, and that the current state-of-the-an CompressionRate for our text data from the Hutter Prize is around 0.11 (Hutter 2009).
LMIC is a strong baseline, outperforms GZIp (with 1MB) on 5/6 modalities with a sequence length of 1,024 and 4/6 modalities with sequence length of 128. Our results Audio-8-bit
24

---

Published as a conference paper at ICLR 2025
LMIC
GZIP
Sequence length
128
1024
128
1024
1MB
Audio-16-bit
0.697
0.639
1.147
1.014
0.920
Audio-8 b-bits
0,319
0.273
0.621
0.454
0.398
Audio MFCC
0.739
0.698
1.250
0.974
0,903
DNA
0.750
0,662
1.182
0.894
0.714
Text
0.611
0.463
0.782
0.525
0.357
Synthetic
0.449
0.450
0.943
0.819
0.593
Average
0.594
0.531
0.988
0.748
0.647
Table 6: CampressionRate for GZIP and LMIC with various input sequence lengths.
comparable the GZIP and CHINCHILLLA-IB baseline from Deletang et al.) (2024) (which reports compression rates of 0.249 with LMIC and 0.364 for GZIP with IGB of data, both within 3.6- point margin). On on text, our LMIC baseline significantly weaker than the one in Deletang et al. 2024). We attribute the difference to the different setting numbers (to enable model to identify mathematical patterns), while the original work presents se- increase the input length, reaching
present the sequences decimal
quences as ASCII characters. Moreover, GZIP improves CompressionRate of 0.32 for 1GB of data, similar to Deletang et al. (2024).
Scaling SEQCODER models improves Accuracy on synthetic data. Fig. presents the Accu- racy for the different SFOCODER models SFOCODER-888 models are trained for 20K and 10K steps, respectively. SEQCODER- 1.5B-10K overfits and accuracy decreases with additional training. SEOCODER-LE (IM examples) signif- icantly outperforms SEQCODER-1.35 1--DDRR--.---1 1.5B-100000 100K and the larger SEQCODER-SB performs better and learns faster.
held-out synthetic dataset. SFOCODER-1.5B and
Scaling prompted models increases percentage of executable programs. Fig. g shows the per- centage of programs that execute without error and terminate within five seconds, broken down by model and dataset. Larger models generate more executable programs, Programs generated by LLAMA-3.1-4055 and GPT4-0 are executable 77.2% and 89.9% of the time on average across modalities.
Passgl vs Training Steps :ata)
LLAMA-3.1
GPT
Modality
70B
405B
4-0
Audio-16-ba
25.6
67.2
69.3
88.2
Audio-8-bit
28.2
82.0
87.4
94.6
Audio-MFCC
25.9
71.0
76.6
94.4
DNA
33.7
Text
4.3
51.0
49.1
76.5
Synthetic
42.0
85.4
88.9
92.9
Average
26.6
75.1
77.2
89.9
400
520
$3:0
3300
13930
S1230
19:00
14:00
20030
Table 8: The percentage of executable pro- grams for our prompted models.
Table 7: Accuracy on our synthetic held-out set for the different SEOCODER models.
Strong priors necessary for good compression. In 5 Fig we show that can outperform previous compression methods for our synthetic data using SEQCODER- 1.5B and a uniform prior over programs and arithmetic coding. The same programs achieve compression rate of 5.26 and 0.59 with raw (the size of the programs saved as strings on the disk) and GZIP encoding, showing that strong priors needed for good RatpressionRate.
25

---

Published as a conference paper at ICLR 2025
Accurscy Longes
Accuracy Sequence Longth
1.20.00
140 1.00
A12
30
130 100
(a) SEOCODER-1.SH accuracy as function of gold program lengths.
(h) SFQCODER-1..5 accuracy function of input sequence lengths.
Figure 11: SEQCODER- 1.5B accuracy as function of gold program and input sequence lengths.
Model Input
Generate program whose execution resulta in the following sequences [18, 149, 19, 150, 20, 151, 21, 152, 22, 153, 23, 151, 21, 155, 25, 155, 26, 157, 27, 158,
28, 159, 237, 160, 237, 161, 237, 162, 237, 163, 231, 164, 231, 165, 231, 166.
237, 167, 237, 168, 237, 169, 237, 270, 237, 171, 233, 237, 237, 237, 237, 237,
237, 237, 237,
143, 144,
147, 146, 149, 150, 152, 152, 153,
154, 155, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 149, 150, 151, 152, 153,
154, 155, 156, 157, 158, 159, 160, 161,
163, 164, 134, 166, 167, 168, 169, 20, 21, 22, 23, 24, 25, 26,
173, 28, 177, 26, 25, 24, 23, 22, 21, 20, 19, 18, 28, 177, 26, 25, 24, 23, 22, 21, 20, 19, 18, 119, 150, 152,
170, 171, 18,
152, 153, 154, 155, 156, 157, 156, 159, 160, 161, 162, 163, 164, 165, 166, 167,
168, 169, 170, 171]
Gold Output (with in-line execution feedback)
sequence__
range__une__pe
[149, .... 170,
sequence_2 2
xange__uune_up(13 (18, 26)
[16, 19, 27, 26]
sequence_3
repeat_num (22, 237)
[237, 237, .... 237, 2371
sequence_
jange_5une_uu1142 (142,, 155)
[142, 143,
154, 155]
sequence_5
reverse_list (sequence__
[26, 27, .... 19, 18]
sequenes_6
substitute (saguencee 165, 174) [149, 152,
.... 175,
sequence
aubstitute (seguenceeeeeeeeee 28, 177) f 118, 19,
26, 177]
sequence_
(sequencee,, 27,
177, .... 19, 18]
sequence_
concatenate (sceuence.........e_e_.. sequence_3) f [18, 19,
237, 237]
sequence
concatenate [sequence__e sequence_4) [18, 19,
154, 155]
sequence_ 11
concatenate [aeeuacee___ sequence_5)
[18, 19,
18, 18)
sequence, 12
concatenate (sequence_.. zequence_6) [13, 19,
170, 271]
sequence_
[scpranoooo saquence_?) [18,
26, 177]
sequence 14
concatenate laequenoeee_ sequence_8) [18, 19,
15, 18]
seguence interleave (sequence_11, sequence_l)
[13, 119, ..... 170, 171]
sequence_li 16
concatenate isequence_is, sequence_8)
19, 18] [18, 149,
sequence_11 concatenate [sequence__6 16, saquence_1)
[18, 149, 170, 171]
output sequence_11 [18, 149, 170, 171]
Figure 12: An example program-sequence pair with in-line exccution feedback.
B.3 ANALYSIS
Fig. I1a and Fig. TTb present accuracy for SEQCODER- 1.5B as a function of program and sequence length, respectively. Accuracy decreases with length of programs sequences.
Fig. 12
presents an example for synthetic program -equence pair with in-line execution feedback.
Tab.
presents the percentage of repetitions in correct programs for LLAMA-3. 1.MMA-3.1-4PP 3.15BB and GPT4-
0. Fig. 13
presents an example where LLAMA-3. 1..MA-3,11444 1-00BB succeeds by repeating the input sequence.
Fig. 44
presents example where LLAMA-3. 1-405B repeats the input sequence in complex
26

---

Published as a conference paper at ICLR 2025
Audio- 16 bit
Audio- S bit
Audio Audio-MFCC MFCC
DNA
Test
Symhhetic
No
Rep
No
No
No Rep
Kep
Rep
Kep
1TLAMA-3.1-4055
16
4
100
4
100
0
96
20
80
GPT4-0
4
Table 9: The percentage of repetitions in correct programs from qualitative analysis of 25 programs per modality for LLAMA-3. 1-40SB and GPT4-0. Most correct examples for natural sequences are because of repetitions, but the contrary is true for synthetic sequences.
S-hit
MPCC
Text
Synthetic
BX
GPT4-0
28
12
40
60
96
Table 10: The percentage of execution (Ex), repetition (Re), and Unicode (Un) emoos erro- neous programs from qualitative analysis of 25 programs per modality for LLAMA-3. 1--05-40 and GPT4-0. More than a third of the errors for natural sequences are caused by repetition errors.
and verbose manner, which is sub-optimal for the GZIP prior. Fig. presents an example where 1.AMA-3.1-405D succeeds on a synthetic sequence by leveraging the induced patterns.
Tab. 10 presents qualitative error analysis 25 erroneous programs per modality for LLAMA- 3.1-405B and GPT4-o. Fig. I6 Fig. 17 Fig. 18 and Fig. 19 examples where LLAMA-3. 1- 405B errs due a wrong execution on an Audio-8-bitt wrong execution on synthetic sequence, repetition on an Audio-8 sequence, and conversion from text to bytes for a text sequence.
Input Sequence
Generated Program
Produced Sequence
1249. 252,
254, 255, 254, 249, 246, 250.
[249, 252, 254, 255] [254, 249, 246, 250, 254,
[249, 252, 254, 255, 254, 249, 246, 250,
254, 255, 255, 2255,223 252, 254, 253,
254, 255, 255, 253, 252, 255,0,
1. 3. 1, 6,
255, 255. 253, 252, 254, 255]
1. 1,
1,4, 6, 1,
3.
254, 255, 255, 254, 254,
[0, 1, 1, 3, 5, 3, 1, 1, 4, 6, 4, 1, 0, 2, 3, d [254, 255, 255, 254, 254,
1, 0, 254, 255, 255, 254, 254,
253, 253, 254, 254, 253, 253, 253, 255,
253, 253, 254 254, 253, 253, 253, 255,
0,
255,
255,
255,
1,0, 1, 1,
254, 254, 255, 255,
253, 253, 254. 254, 253, 253,
1, 0, 1,0,
255, 254, 254,,5220 254, 255,
255, 254, 253,
252,
254, 254, 255, 255,
253, 255]
255, 253,
252, 254, 254, 255,
254, 253, 253,
254,
255.
(1, 3, 255, 255, 255, 0, 2,
254, 253, 253, 255, 254, 255, 255,
255, 255, 254, 255,25520
0, 5,
1, 1, 1, 0, 1, 1, 0,
255, 255,
255,
4,
1. 2. 3.
1, 0.
01
2, 1,
1,0,
255, 254, 253, 253, 254, 255, 255, 254,
[255, 254, 254, 255,
255, 254, 253, 253, 254, 255, 255, 254
251,
255,
254, 253, 252, 254, 254, 255,
251,
254,
254, 255, 1,2]
253, 254]
254, 255, 1.
g (253, 253, 255, 254, 255,
255, 255, 255, 255, 254, 255]
3,
5, 5, 6, 3, 1, 0, 1, 2, 1, 01
(255, 254, 253, 253, 254,
255, 255, 254, 251, 251 253, 255]
3 [0, 255, 255, 254, 254, 255,
cutput + + a+bti+7
Figure 13: An example generation for LLAMA-3, 1-40BB on Audio-8-bir where the model succeeds by splitting the sequence to sub-sequences that are later concatenated.
27

---

Published as a conference paper at ICLR 2025
Inpat Sequence
Generated Program
Produced Sequence
[250, 250,
251, 251, 251, 250,
248, 246.
[250, 250, 251, 251, 251, 250, 248, 246,
244, 244,
243,
244,
245, 247,
249, 251.
b [d, al [251, 251, 251] extend (c)
244, 244,
243, 244,
245, 247, 249, 251,
251. 250,
248,
246,
243, 242,
241, 241.
251. 250,
248, 246,
243, 242, 241, 241,
E.
246. 245, 245,
244, 244, 245, 245, 245.
[a, 248, 246, 244, 244, 243,
246, 245, 245, 244, 244, 245, 245, 245,
245,
245,
244,
244, 245, 247, 249]
246,
244,
245. 246 247,
249, 255. 16,
b.exterd (d)
244, 245, 246, 247, 249, 255, 16.
43, 40,
29,
252, 248, 250,
[251, 251, a, 248, 246,
43, 40, 29, 27, 29,
252, 248, 250,
245, 250,
242, 241, 241, 241,
248, 245, 250,
7, 2,
9. 4, 21,
31, 30,
242, 243,
245,
9, 9,4,8 16, 21,
26, 31, 30,
7,4,
245. 246, 246, 245,
241.
243, 249, 255,
4, 4,
245, 244, 244, 245, 245,
243, 249, 2,
6,
13, 11,9,
245, 215, 245, 246.
5.9. 13, 9,
2,
241. 239, 236, 235, 237, 242, 248, 252.
245, 244, 243, 243, 244, 244,
241. 239, 236, 235, 237, 242, 248, 252.
255, 2, 4, 5,
246, 247,
255, 2, 4,
249, 255, 16, 34, 43, 40,
29, 29, 23, 91
b.extend (e)
(252, 248, 250, 248, 245,
250, 11, 7, 2, 4,
12, 14, 9, 4, 8, 16, 22, 22.
31,
12, 7, 41 b.axtend (f)
[252, 241, 234, 235, 239,
241, 243, 249, 255, 2,
1, 1, 7, 6, 4, 13, 11, 9, 6, 1)
13,
exeteeddg))
h (249, 243, 241, 239, 236,
235, 237, 242, 248.
252, 255,
5, 5]
b. b.extend cutput
An example generation from LLAMA-3.1-4055 for Audio-8-bit where the program repeats the input sequence verbose way, iee. by extracting the number 255 variable and splitting to sub-sequences.
Figure 14:
Inpul Sequence
Program
Sequence
[196,
197,
200, 201, 202,
cutput
[196. 197,
200,
201, 202, 203,
204,
205,
206,
207,
208,
209, 210, 211.
list (range (196, 214))
204, 205, 206
207,
208,
209 210, 211.
80,
80,
[83]
80,
26, 26, 26, 26,
108. 97, 19, 25,
[26]
5
26, 26,
26,
26,
108, 97, 251, 31, 45,
93. 136,22 249,
162.
184,
191.
[138,
97, 19, 251, 31, 45,
93. 136, 249,
162,
184, 244,
178. 179, 180,
181, 182. 183, 184, 185.
93, 136, 249, 32, 162, 7,
178. 179, 180,
181, 182, 183, 184, 185.
186. 187, 188. 189, 190, 191, 192, 193.
184,
186. 187, 188, 189, 190, 191, 192, 193,
199, 201.
list (range (178, 202))
194.
196,
198.
200,
80, 80,
80,
80,
80,
80, 80)
[80]
80, 80,
80,
80,
80,
80, 801
An example synthetic sequence where LLAMA-3, 3..A-,3.14000 1-40BB succeeds in leveraging pat- terns the input sequence, i.e., repetitions and an increasing range, generate a correct program.
Figure 15:
28

---

Published as a conference paper at ICLR 2025
Inpott Sequence
Program
Sequence
7, 10, 11,
II,
Predefined Constants Start__sqqeere [6,
[6. 7.7.8.8..
10, 11,
7. 3. 6,
254, 247, 246.
8,
3, 254, 253,, 252.
246.
11, 11, 11, 7, 3, 3, 4]
245,
247,
250, 254, 254,
253, 253, 254,
mi mid_sequence [255, 6, 255, 255, 255]
249. 254, 254,
253,
255, 0. 255, 255, 254.
254, 255, 255, 0,5,
254, 254, 253, 253, 254, 255.
end_sequence [0, 0, 0]
255, 254, 254, 254, 253,
254, 252, 252, 253, 254, 255,
252, 0, 255, 254, 254,
253, 253, 254, 25,,
Pattern 1: Jecreasing by 1 dbcreasingg_etttrntttee
254, 254, 253, 252,
255, 253, 254, 254, 254,
253, 253, 254, 254,
253, 254,
length):
2,
25 2. 3.
return (start for i in
3, 1,
3, 1,0,
range (length)]
0, 255, 255, 255, 253,
255, 253, 253, 253, 253, 253,
253, 253, 253, 253, 254,
253, 253, 254, 0,
Pattern Increasing by def increasing parressinng.tttttrtttrtr
255, 0, 0, 5,4,,,
62, 7, 7. 252, 251, 250, 249,
11. 12. 5, 7.
length):
249, 251, 249.
return (start 1 for 1 in range (length)]
247,
246, 245, 247, 251, 252, 252,
252, 253, 254, 255, 0,
252, 253, 254, 255, 255, O. 0)
Pattern 3: Repeating a number def zepeat_pattert (num, timesl: return [num] times
Senerate the Sequence sequence start_
sequence decreessin_oaallen 1254, 5) sequence increasing_portern (245, 5) sequence repeat_patterr:
3) sequence [253, 252, 254, 255] sequence mid_sequence
sequence -- repest_patteer:1255 (254,
sequence decreasing_patter
1254, 3)
sequence = [2, C, 255] sequence = repest_pattem:1254
sequence + decreasing_patterr 1254, 4)
sequence 1253, 253, 253, 234, 254, 251, 255, 0]
sequence [2, 2, 2, 1, 2, 3, 4,
3, 2, 1, 1, 1, 1, D)
sequence mid_sequence sequence - pappstt_pattormpP00
7)
sequence -- [254, 255,
3, 4, 5, 6, 7, 9, 10, 11, 12, 9, 6, 5, 7, 7, 2]
sequence - degreas' pattern 1252,
sequence + [249, 245, 245, 247, 251, 252, 252, 252, 253. 254, 255, 255] sequence end_seee
Final Output output sequence
Figure 16: An example program for Audio-8-bit from LLAMA-3. 1-405B where the model tries identify patterns in the input sequence, but the execution does not result in the input.
29

---

Published as a conference paper at ICLR 2025
Input Sequence
Generated Program
Produced Sequence
1140, 55,
142,
57,
144,
59, 146, 61.
140
[140, 142,
144,
146,
148. 150, 152,
148. 63,
150,
65,
152.
67, 154, 69.
b 55
154, 156, 158, 55, 57,
61, 63,
156. 71,
73,
77,
101,
45,
67. 69.
71, 73,
75,
77,
101, 45, 160,
79, 160,
236,
d [a 1 For in range (10)
187, 236,
68, 139, 221.
87, 65,
89,
196, 91. 18, 93, 68, 95.
165. 79,
81, 83,
166, 167, 168. 169, 170.
[b.
for in range (20)
173,
175,
169. 170. 171.
173, 174, 175.
61. 65,
67,
69.
71,
75,
77.
176. 55, 57. 59,
61, 63, 65, 69,
[101, 45,
81, 83,
85, 87, 89, 91, 93, 95, 97, 99]
71,
77.
77,
85,
65,
89, 91,
93, 95, 97, 99]
196, 68, 139, 221,
list (range (166, 177)1
(55
for range
[231]
output d[C:10] + a[0:10] [1]
e[10:12] 1 E e12::15: tith
Figure 17: An example program for a synthetic sequence from LLAMA-3. 3.-0.BB where the model tries to identify patterns in the input sequence, but the execution does result in the input.
Input Sequence
Program
Produced Sequence
[235.
236,
240,
248, 252, 255, 16,
[235, 236, 240, 244, 248, 252, 255]
[235. 236,
240,
244, 248, 252, 255, I,
4. 6.
10,
10,
12,
4. 6,6,8 8,
10.
10,
12.
14, 16,
5,
b [1, 4, 6, 8, 19]
13,
248. 244,
241,
240, 239, 239,
238, 236,
[10, 12, 14, 16, 18]
9. 0. 4.
254
248, 244, 241,
233,
236
237,
238,
[16, 13, 9, 5, 4, 11
240
241. 244,
246
246,
246,
245, 245, 246,
(254, 248, 244, 241, 240,
236. 237,
234,
236,
237, 236 237.
247, 248,
247, 246,
246, 246,
247, 247,
2391
238. 241
244
246
245, 245,
247.
243.243.
245,
246
É [239, 238, 236, 234, 2331
248.
247
246, 248,
245,
245,
245,
247,
249, 249, 249, 250.
g (234, 236, 237]
247.
246
243,
243,
244, 245, 246, 243,
2,
[238, 241, 244, 246]
245,
18, 22,
27, 30,
34,
39, 40,
[245, 215, 246, 247, 248, 247, 246]
252, 254, 4, 2, 5, 11,
41.
36,
20,
27,
37, 40,
5. 1,
255,
252, 247, 244, 243,
3 (243, 243, 244, 245, 246] [249, 249, 249, 250, 254)
41. 41
40.
28,
20,
240, 235,
233, 234,
238, 242, 246, 249,
10. 5,
255,
252,
247, 243,
10,
240,
235,
233,
246,
19. 20,
19,
15, 12]
[2, 5, 3, 9, 11, 14, 18, 22,
253,
3, 6,
10, 11, 12.
27, 30, 34, 37, 39. 401
19,
12]
m. [41, 41, 10, 36, 28, 20, 17,
14, 10,
n (255, 252, 247, 244, 243.
240, 235]
(233, 234, 238, 242, 246.
249, 253]
3, 6, 8, 9, 10, 11, 12. 15, 19, 20]
q (19, 15, 12]
output
Figure 18: An example program for Audio-8 --dio----iit bit from LLAMA-3. 3. 1-00BB where the model tries to repeat the input sequence by breaking it to sub-sequences that are later concatenated but still errs.
30

---

Published as a conference paper at ICLR 2025
Input Sequence
Program
Produced Sequence
[32. 102.
111,
114,
101.
115, 32,
letters
1102. 111.
114,
101.
115. 32,
105,
105.
110,
32,
116,
104,
32, 69.
abodefghi Siaieggghhikmmmopgsssuuweyy numbers
110,
32,
116.
104,
101,
32,
101, 97.
115,
'0123456789'
100,
101. 97. 108, 32,
119.
105,
116, 104,
sentence "Forcea in the East to
97. 108. 32, 119.
105,
116,
104, 46.
101,
32,
deal with. Weeks later Johnston would defy Jefferson
107
108, 97, 116, 101,
114, 74, 111.
97. 116, 101,
114,
32,
106,
111, 104.
104. 110.
115. 116. 111. 110,
119,
Davis and surrender his forces to Sharman. of course"
110, 111, 116,
111.
32.
111.
111. 117, 108. 100,
32, 100, 101, 102,
117, 108, 100,
32.
100.
101.
102, 121.
121. 32, 74, 101, 102. 102. 101. 114,
32. 106, 101. 102.
102,
101
114. 115.
118,
cutpot
(ord (cwlew)) if a. Lower () in lesters else ord
115, 32, 97, 110, 100,
32, 115, 117,
32, 97, 110, 100,
32, 115, 117. 114,
114, 101, 110,
101,
for in sentence]
114. 101, [10,
101,
104,
104, 105, 115, 32, 102,
111, 19,
105. 115. 32, 102.
111. 114, 101.
101. 115, 32, 116, 111,
32, 83, 104,
115, 32. 116. 111.
32, 115, 104, 101,
101. 114, 109,
110,46.
79.
114, 109,
110,
46,
111. 102.
102. 32, 99.
111, 117. 114, 115. 1011
32, 99, 111, 117,
114, 115, 1011
Figure 19: An example program for the text modality from 1LLAMA-3.1-4051 where the model tries produce the sequence by writing and converting it Unicode bytes, but errs slightly (the correct text being forces in the East to deal with. Weeks later Johnston would defy Jefferson Davis and surrender his forces to Sherman. Of course").
31


Reviews:
[{"review_id": "09hxtl7BOT", "reviewer": "Reviewer_5eaV", "summary": "The paper introduces a benchmark designed to evaluate LLM's capabilities in compression as an indicator of intelligence. The Benchmark requires models to generate the shortest possible python program that reproduces an input data sequence, aligning with the concept of Kolmogorov complexity. The authors assess current language models' performance in KT using data from text, audio, and DNA, as well as synthetic data with specific patterns. Results show that models like GPT4-O and LLAMA-3.1-405B struggle with both natural and synthetic data. The authors also develop a Domain Specific Language (DSL) to create program-sequence pairs for supervised training, leading to trained models that achieve lower compression rates than traditional methods on synthetic data but perform poorly on real data. Authors have conducted further experiments and comparisons with different baselines including GZIP, \"Language Model is Compression\", etc. The paper suggests that further innovations are necessary for models to generalize well on real-world data within the KT framework.", "questions": "See weaknesses for questions\n\nAlso, does any of the recent works on lifting the length constraint of LLMs help in Length generalization for SeqCoder? e.g. \"Efficient Streaming Language Models with Attention Sinks\".", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. Extensive amounts of experiments conducted and insights gathered from it are the major strengths of this paper. Experiments related to trained SeqCoder are  particularly helpful in highlighting the generalization issues and how much it could be overcome with synthetic data.\n2. Clear articulation of the DSL Language and of the techniques used in generating the data. The DSL Language and its complexity seems sufficient for benchmarking SOTA LLMs.\n3. Easy to read, with key pieces of information and additional analysis generally emphasized appropriately.\n4. Setting aside the question of whether LLMs will be widely used to generate code to compress data, this benchmark highlights current limitations of SOTA LLMs, even with basic patterns such as repetition.", "weaknesses": "1. Though the breadth of the experiments is extensive, the Paper could have included experiments and analysis of popular prompting techniques that have been shown to increase the reasoning and coding capabilities of LLMs, such as Chain-of-Thought, Tree-of-Thoughts etc. Given the popularity of these techniques and how prevalent CoT is in all major reasoning benchmarks, including at least one prompting technique would have been useful in the analysis.\n\n2. As the paper's main idea is influenced by the Hutter Prize [1], it would be useful to use any of the compressors in the leaderboard [2] as an additional baseline. Specifically, compressors that use LSTM (such as tensorflow-compress) would make make of an interesting baseline for the benchmark.\n\n[1] - http://prize.hutter1.net\n\n[2] - http://mattmahoney.net/dc/text.html", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7BmuVybApk", "reviewer": "Reviewer_xD3h", "summary": "The paper talks about compression of data using LLMs via code generation. The smallest possible way to compress a sequence of data called the Kolmogorov compression is uncomputable. Therefore, the paper tests the capability of code generating LLMs to generate a program that can produce the sequence, thus compressing it. They argue that achieving this requires the models to reason, plan, and search for complex patterns within the sequence to enhance compression performance. The paper evaluates state-of-the-art models, such as Llama-3.1-405b and GPT-4-o, in a zero-shot manner on real-world compression data sources like audio, text, and DNA, demonstrating that these models perform poorly compared to the deterministic gzip baseline. Additionally, the authors assess the models on a synthetic benchmark of (sequence, program) pairs created using a custom domain-specific language (DSL). On this synthetic distribution, they trained a code generation model that outperformed gzip with a uniform prior over the custom DSL. However, they also showed that these models don’t generalize to real data. The paper highlights significant differences between the distributions of real and synthetic sequences, with real sequences exhibiting more repetitions. Through ablation studies, the authors further demonstrate that the trained models do not generalize well to longer sequences.", "questions": "For the experiments, the following should have been additionally explored by the authors :\n\n- The authors didn’t report the effect of execution and feedback on the SOTA LLMs. From Table 3, the authors have just presented the ablation on the trained synthetic model.\n- The authors didn’t use models like openai-o1 which can reason before emitting any code and have shown to have good performance on code based tasks. It would be interesting how these inference based reasoning models perform on this task ? \n- The authors haven’t reported the accuracy and precision of the Seqcoder 8B 1M model on synthetic data. Does starting from a better base model help in accuracy ?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strengths of the paper include :\n\n- The paper studies the problem of compression as a code generation problem with current code language models. This is quite novel in the context of language models as previous works have primarily used language models for compression through arithmetic coding. This new framing of the task surely requires the model to understand patterns in the sequence and reason about how to segment the sequence into different subsequences.\n\n- The paper proposes a dynamic benchmark comprising of (sequence, program) pairs which test model’s capability at compressing sequences which are generated using a custom domain specific language (DSL) comprising of different functions that can be realized as python functions. The paper shows that codeLMs trained on this synthetic benchmark can outperform deterministic compression methods like gzip when efficient compression priors are applied to generated functions. Notably, zero-shot prompted state-of-the-art models like GPT-4-o and Llama-3.1-504b fail to reproduce input sequence for more than 66% and 45% of the time, respectively. The dynamic nature of the benchmark, due to its dependency on the customizable DSL, prevents existing LLMs from gaming or memorizing it, as it can generate different examples of varying complexity that the model has not previously encountered during training. \n\n- The paper’s evaluation of code generation based compression on various real world data sources like audio, text and DNA is also noteworthy. In the literature of information theory and communication, these domains have been thoroughly studied for different compression based algorithms. Although none of the models discussed in the paper outperformed the gzip baseline for compression, this finding highlights an interesting phenomenon that is widely discussed in the literature: the numerical reasoning and counting limitations of these LLMs.", "weaknesses": "The major weaknesses of the paper include :\n\n- Although the benchmark is effectively designed around compression as a code generation problem, the prompts used in the zero shot evaluation of the models are quite open-ended compared to the structured and closed nature of the DSL design that has been used in the synthetic experiments. This leads to an unfair comparison with the synthetic model.  With better prompt-designs, with better in-context examples, inclusion of DSL definitions in the prompt, ReACT prompts with verification in the loop, these SOTA models can achieve good performance. This is particularly relevant given that feedback and execution improved the accuracy of the trained model on audio-based data, and the majority of errors in SOTA models were execution-based.\n\n- While the assessment using real-world data is sensible, expecting the smaller 1.5B/8B model trained on synthetic data to generalize effectively to real-world data is quite ambitious. The distribution of real data significantly differs from synthetic data; the former has more repetitions, while the latter exhibits more complexity in terms of interleaving sequences. The synthetic data used by the authors consists of smaller sequences and smaller length programs whereas real-world data with more repetitions would result in longer generated programs - something the model wasn't trained on, leading to a significant drop in accuracy. This decrease in accuracy for the trained synthetic model could also be attributed to model capacity, as similar models like LLaMa-3.1-8B also show lower accuracy on real-world data.\n\n- Beyond the evaluation and training of models, it is highly unlikely that LLMs can be traditionally and reliably used for compression instead of deterministic methods like gzip. LLMs are inherently probabilistic models and cannot generate lossless compressions without hallucinations or mistakes in a zero-shot setup. The motivation behind designing such a complex benchmark around the Kolmogorov test is unclear. If the focus is on synthetically generated data/benchmark, small 1.5B models trained on 10k-1M perform well on them with some supervised training. However, if the focus is on real data, realizing real-world data compression as a code generation problem that outperforms gzip is very challenging without better base models, improved prompt design, or better synthetic data design.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8Et5tcIDcH", "reviewer": "Reviewer_uxqq", "summary": "This paper presents two contributions to the field of language model (LM) evaluation and training:\n\n* KoLMogorov Test: A proposed test for language models grounded in compression principles with several benefits. Specifically, there is a preponderance of real-world examples (e.g. audio, text, DNA, or any other modality data that can be represented as bit sequence ) that can used to curate an evaluation set of desired degrees of hardness that cannot be otherwise used for fine-tuning LMs - preventing benchmark hacking. Also, this method allows for computationally cheap and reliable automated evaluation that can measure both the generation accuracy and quality, which is traditionally a bottleneck in language model evaluation setups.\n* Synthetic instruction set for fine-tuning LMs for the compression task: This work also turns this test into an LM post-training task and provides a framework for generating a synthetic instruction set to enhance LMs' compression capabilities.\n\nAdditionally, this work provides interesting insights on LM fine-tuning:\n1. Specifically, small LMs extensively fine-tuned on a synthetic instruction set outperform state-of-the-art prompted models and classical baselines (gzip algorithm).\n2. that such performance gains by small fine-tuned models on synthetic data do not translate to the performance gains on real-world data", "questions": "Since compression is posited as a test of [coding] LM intelligence, it will be interesting to examine the other dimensions of an LM's \"intelligence\" that correlate with its compression efficacy. A potential experimental set-up to this end could involve fixing a base model and measuring the performance of its variants which have been fine-tuned on disparate tasks such as math reasoning, code, etc., on the KoLMogorov Test. If the KoLMogorov Test exhibits a good correlation with the other intelligence dimensions, its benefits may allow it to subsume other benchmarks. KT may also lend itself as a reward function during LM preference optimizations.\n\nThe observations in this work when fine-tuning small LMs on synthetic instruction sets for compression tasks - appear to echo other works from the math-reasoning domain, where extensive fine-tuning allows a relatively smaller model to outperform a larger base model (on tasks such as GSM8k), but without any generalized improvements. If the authors see any fine-grained parallels here - this discussion would be a useful contribution to the community.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The authors have considered datasets of different modalities and degrees of hardness and analyzed state-of-the-art models from both open and closed-source spaces, making a convincing case for KT as a test for code-generation models. This test has the additional benefits of the corresponding evaluation sets not being directly usable for fine-tuning and the preponderance of hard examples in natural data sources.\n\nThe various ablations presented in this work comprehensively capture the limited performance of these SOTA LMs on the task of compression, which will be helpful to the broader community.\n\nThe framework for synthetic data generation proposed in this work could be used to augment instruction sets towards large-scale post-trainings of LMs aimed at generalized gains.", "weaknesses": "Two points that are fundamental to this work -\n1. the efficacy of code-generation language models at compression tasks and \n2. some of the observations around fine-tuning LM on compression tasks \n\nhave already been discussed in prior work, as the authors of this work aptly reference. This limits the novelty of the present work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "krZUW44ETw", "reviewer": "Reviewer_CMwz", "summary": "The authors introduce the KOLMOGOROV-TEST (KT), a novel \"compression-as-intelligence\" test for code generation in large language models (LLMs). Using KT we can prompt or train LLMs to generate the shortest possible programs that reproduce given data sequences, emulating an ideal form of data compression known as Kolmogorov compression, which is theoretically optimal but incomputable priori. The contribution has several advantages: it provides a myriad supply of problem instances of varying difficulty, uses a robust metric (compression rate), and minimizes risks of pretraining data contamination. In evaluating current models like GPT-4o Omni and LLAMA-3.1-405B across multi-modal data types (audio, text, DNA, and synthetic sequences), the authors find that these models perform poorly on both natural and synthetic data. Also authors showed that while training on synthetic data shows improved compression rates, the gains do not transfer well to real-world data for KT.", "questions": "1. **Live Benchmark Availability**:  \n   Are there any plans to release KT as a live benchmark in addition to the dataset? A live benchmark could provide ongoing insights into model performance and facilitate community-driven improvements over time.\n\n2. **Use of Code-Specific LLMs**:  \n   Why weren’t code-specific LLMs, such as CodeLLAMA, DeepSeek Coder, or StarCoder, tested in this work? These models have vocabularies optimized for code, which may affect compression rates and generalization performance. Testing code-specific LLMs could provide better priors for transfer learning and potentially enhance performance on program generation tasks.\n\n3. **Training Details**:  \n   How many epochs or steps were the models trained on for this task? Understanding the training duration would clarify whether models had sufficient exposure to the data to learn effective compression strategies.\n\n4. **Sequence Length and Token Count**:  \n   The input sequence lengths vary from 16 to 1024 bytes, but could you clarify the number of tokens these represent? This information would help assess how sequence length impacts model performance and how the model tokenizes different sequence lengths.\n\n5. **Data Type Configuration for LLAMA-3.1-405B**:  \n   Which data type was used for LLAMA-3.1-405B (e.g., bf16, fp16, fp8)? Were any specific data types recommended by the model’s authors tested to ensure compatibility with the architecture? Correct data type configurations can be critical for performance, and confirming this would add clarity to the experimental setup.", "limitations": "", "rating": 10, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**:  \nThe authors present an innovative approach by introducing a \"compression-as-intelligence\" test (KOLMOGOROV-TEST, or KT) that challenges LLMs to generate the shortest programs across multiple data modalities, a novel and ambitious application of LLMs in program synthesis. The use of a multi-modal framework (including audio, text, DNA, and synthetic data) is particularly original, expanding the scope of LLMs in code generation.\n\n**Quality**:  \nThe authors collected program-sequence pairs for supervised training and evaluation, developing a compositional domain-specific language (DSL) and an automatic data generation framework. This framework enables consistent and reliable data generation while avoiding potential biases through uniform priors, which strengthens the robustness of the study. Additionally, the authors investigated the impact of execution feedback on performance, further enhancing the study's depth.\n\n**Clarity**:  \nThe paper includes a detailed analysis section, providing insights into model performance and limitations. The authors clearly document failure cases, particularly highlighting instances where models fail by attempting to reverse-engineer the data generation process rather than compress it effectively. This transparency improves the readability and interpretability of the results.\n\n**Significance**:  \nKT sets a new benchmark for evaluating LLMs on program synthesis via compression tasks, offering a reliable metric (compression rate) that is both challenging and robust. The framework holds potential for broader applications and improvements in LLM-based code generation by identifying key areas for enhancement, such as in handling complex, real-world data compression.", "weaknesses": "**Limited Focus on Code-Specific LLMs**:  \nAlthough the paper introduces a compression benchmark specifically for code-generating language models (CODE LMs), the experiments primarily use general-purpose LLMs. Testing specialized CODE LMs could offer a more accurate assessment of model performance for program synthesis tasks, as these models are often fine-tuned with code-specific vocabularies and architectures. Incorporating CODE LMs in future work would enhance the relevance and impact of the findings.\n\n**Understudied Tokenization Impact**:  \nThe impact of tokenization on model performance is underexplored. Prior work (e.g., Delétang et al.) suggests that larger vocabularies may offer more expressive flexibility but can also complicate next-token prediction. Evaluating different tokenization strategies would shed light on their influence on compression rates and model accuracy, potentially guiding optimizations in vocabulary selection to balance expressiveness and predictive ease.\n\n**Suggestions to test Length Generalization**:  \nScaling to longer sequences remains an open question. Applying techniques like Rotary Position Embeddings (ROPE) for scaling might provide insights into the model's capacity for length generalization. Additional experiments with longer sequences could clarify how well the model generalizes across variable input sizes, which is critical for practical applications of program synthesis.\n\n**Limited Prompt Optimization**:  \nThe paper could benefit from more work on prompt optimization, as prompt quality can significantly impact model output. Experimenting with prompt tuning strategies or context-enhancing techniques could improve model performance and compression efficiency. This would help achieve the paper’s goal of generating shorter, more precise programs, as optimized prompts can guide the model more effectively toward compact solutions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s94bzarKKM", "reviewer": "Reviewer_y77n", "summary": "The papers proposes a method to evaluate code based language models by using them a compression mechanism to approximately compute the Kolmorogov Complexity (which is uncomputable). The aim of the evaluation procedure is to generate the shortest program which produces a certain data point and then stops. The paper proposes simple experiments to show how to approximately compute the Kolmogorov complexity of datums from LLMs. Experiments in the paper use the state of art closed and open source language models, and show that even the SOTA models struggle on the Kolmogorov test proposed in the paper.", "questions": "- Are the Llama models instruction tuned or pre-trained?\n- What’s the compression rate for the training data? How many bits can it be compressed to?\n- The proposed method seems to be very much model dependent, even on the size of the model? Do you add the size of the model while using your test, so that you can normalize your method across models? Otherwise larger models can very well compress all short programs effectively, thus it would then be a test of how large the LLM is.\n- In table 1 what could be the reason for the Llama models to have a low accuracy for 8-bit prediction, while having almost double accuracy for 16-bit case?\n- A lot of the analysis seems to be heavily focused on Audio datasets/tasks, is there any particular reason for that? Instead of using existing code based benchmarks?\n- Section 1 of this paper by Vitanyi (https://arxiv.org/pdf/0809.2754) has some interesting results on the Kolmogorov Complexity of different objects like, very simple objects, complex objects, random objects etc. I think some inspiration could be used from there to construct interesting examples for evaluating the LLMs, for instances showing if the existing SOTA LLMs can encode simple objects, and then progressively build on complex objects.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed test is an interesting information theoretic test which can be used to compute the information in data samples relative to a model. If samples have smaller programs, then we know that the LLM has understood the structure of that problem/sequence.\n- Table 1 is an interesting figure as it shows that even SoTA models currently struggle on at least some benchmarks like Kolmogorov-Test proposed in the paper.\n- The experiments in the paper are intuitive, seem to be easy to follow and replicate.\n- Test proposed in the paper is different from the usual benchmarks and can be added to any existing code evaluation pipeline by simply computing the size of the program which generates the desired output from the test cases.", "weaknesses": "- The connection between Kolmogorov Complexity and Intelligence is not clear in the submission. If we take the popular code based benchmarks, and compute the size of the programs lets say at pass @ 10, then can we say that models which produce shorter programs are more intelligent?\n- When using LLMs on the application side, users are often interested in easy to use/understand programs, will producing shorter programs be useful in this case?\n- For the synthetic programs that are constructed as part of the dataset, is there a short proof for why they are the shortest length? Are you using some of the properties of the operations to assure that?\n    - Here is an example where the training set may not contain the shortest program, for instance consider the following program:\n        - seq_1 = range(0,10,2) seq_2 = range(1,11,2) seq_3 = interleave(seq_1,seq_2) output=seq_3 In this case the shorted program is range(0,11,1) and not the program in the training set. \n- Generating the shortest program for any given sequence is NP-Complete so what does line 246 correspond to? Are we trusting the LLM to generate the shortest programs? The baseline seems to be unreliable.\n- In terms of the paper writing, it would certainly help if you define the Kolmogorov test or present it as an algorithm. While it’s understandable for people with background, it could be hard to understand for general audience.\n- For the Lams in Table 1 especially the Llama models, why was few shot prompt / chain of thoughts reasoning not considered as good baselines? For the synthetic tasks, I believe using CoT with few-shot examples could certainly improve performance. It also seems that the SeqCoder-1.5B model is overfitting to the synthetic task instead of actually being intelligent. Would the claim here be that the 1.5B model is more intelligent than GPT-4o since it has a higher accuracy?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N5fKFvfrq0", "reviewer": "Reviewer_ohAG", "summary": "This work presents a Kolmogorov test for code generation models.\n\nExperiments are performed on synthetic data, natural text from Wikipedia, audio sequences from LibriSpeech, and human DNA sequences from the GRCh38 assembly.\n\nStandard compression is compared with LLMs and code generation. Specifically, Gzip and LMiC are used as baselines, and compared with baselines that prompt open-weights (Llama-3.1) and closed-weights (GPT-4o) LLMs to generate the shortest Python program that produces the input, and also open-weight models trained on synthetic text and code.", "questions": "How sensitive are the results as a function of the action space?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The result of the open-weight models trained on synthetic text and code is impressive (84.5% accuracy),\nand their compression rate outperforms existing baselines.\n\n2. Compression by code generation may serve as a useful additional scalable benchmark for LLMs.\n\n3. The paper is well-written, and the exposition is clear.", "weaknesses": "1. My main concern is that the results do not generalize at all from synthetic to real datasets (0 accuracy).\n\n2. In addition to synthetic data, the data used in this work includes natural text, audio, and human DNA sequences from the GRCh38 assembly represented in FASTA format. In protein structure prediction (PSP), sequences of proteins are commonly represented in FASTA format, and their 3D structure predicted. It would be interesting to see the compression results for protein sequences and their structures.\nIt would be interesting to extend the real-world datasets to other data types.\n\n3. The synthetic DSL includes 3 initiators x 7 modifies x 2 filters x 3 merger functions. It would be interesting to see this action space extended and understand how sensitive the results are as a function of the action space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wySgpElRuR", "reviewer": "Reviewer_1MaY", "summary": "This paper proposes a novel aspect to evaluate the LLM: by testing its ability to compress discrete sequence data. The proposed benchmark features several advantages such as unlimited data availability and easy to control difficulty in synthetic data generation. The proposed benchmark can be viewed as a sub-task of code-generation. This paper further trained a few models to outperform current models in this task to explore LLM's edge in data compression.", "questions": "See sections above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The studied problem is interesting and challenging for LLMs, and not seriously studied before.\n\n- The proposed benchmark is described in detail, making it easy to understand and reproduce.\n\n- The efforts to train a few LLMs proved that this problem is addressable, which offers more context and helps future researches.", "weaknesses": "- Better to provide a few examples on where the LLM's ability starts to drop: for tasks than that threshold, LLMs are able to produce perfect compression programs (and separately for each studied and fine tuned LLMs); for tasks harder than that, LLMs fails even with fine-tuning.\n\n- Better study on the edge of LLM: if more training data are provided, if higher rank LoRA applied, or if better curriculum learning applied, will it be stronger, or stops at current level?\n\n- I believe the LLM could perform better if more domain-specific presets of data are assembled, such as DNS sub-sequences with known patterns and known functionalities, yet this seems to be beyond the scope of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)