Language Modeling Is Compression
Authors: Gregoire Deletang
Anian Ruoss
Paul-Ambroise Duquenne
Elliot Catt
Tim Genewein
Christopher Mattern
Jordi Grau-Moya
Li Kevin Wenliang
Matthew Aitchison
Laurent Orseau
Marcus Hutter
Joel Veness
Venue: ICLR 2024 poster (2024)
Keywords: lossless compression
arithmetic coding
language models
scaling laws
in-context learning
Primary area: general machine learning (i.e., none of the above)

Abstract: It has long been established that predictive models can be transformed into lossless compressors and vice versa. Incidentally, in recent years, the machine learning community has focused on training increasingly large and powerful self-supervised (language) models. Since these large language models exhibit impressive predictive capabilities, they are well-positioned to be strong compressors. In this work, we advocate for viewing the prediction problem through the lens of compression and evaluate the compression capabilities of large (foundation) models. We show that large language models are powerful general-purpose predictors and that the compression viewpoint provides novel insights into scaling laws, tokenization, and in-context learning. For example, Chinchilla 70B, while trained primarily on text, compresses ImageNet patches to 43.4% and LibriSpeech samples to 16.4% of their raw size, beating domain-specific compressors like PNG (58.5%) or FLAC (30.3%), respectively. Finally, we show that the prediction-compression equivalence allows us to use any compressor (like gzip) to build a conditional generative model.

Published as a conference paper at ICLR 2024
LANGUAGE MODELING Is COMPRESSION
Grégoire Delétang"!
Anian Ruoss" 11
Paul-Ambroise Duquenne
Elliot Catt
Tim Genewein' 1
Christopher Mattern
Jordi Grau-Moya'
Li Kevin Wenliang
Matthew Aitchison
Laurent Orseau'
Marcus Hutter'
Joel Veness*
ABSTRACT
It has long been established that predictive models can be transformed into lossless compressors and vice versa. Incidentally, in recent years, the machine learning community has focused on training increasingly large and powerful self-supervised (language) models. Since these large language models exhibit impressive predictive capabilities, they are well-posiin well-positioned to be strong compressors. In this work, we advocate for viewing the prediction problem through the lens of compression and evaluate the compression capabilities of large (foundation) models. We show that large language models are powerful general-purpose predictors and that the compression viewpoint provides novel insights into scaling laws, tokenization, and in in-context learning. For example, Chinchilla 70B, while trained primarily on text, compresses ImageNet patches to 43.4% and LibriSpeech samples to 16.4% of their raw size, beating domain-specifte compressors like PNG (58.5%) or FLAC (30.3%), respectively. Finally, we show that the prediction-compression equivalence allows us to use any compressor (like gzip) to build conditional generative model.
INTRODUCTION
Information theory and machine learning are inextricably linked and have even been referred as "two sides of the same coin" (MacKay 2003). One particularly elegant connection is the essential equivalence between probabilistic models of data and lossless compression. The source coding theorem (Shannon 1948) is the fundamental theorem describing this idea. i.e., the expected message length in bits of an optimal entropy encoder is equal the negative logg- likelihoodd of the statistical model. In other words, maximizing the bogy-likelihook (of the data) is equivalent to minimizing the number of bits required per message. Indeed, lossless compression with a probabilistic model can be achieved in variety of different ways, including Huffman coding (Huffman 1952). arithmetic coding (Pacco) 1977 Rissanen 1976), and asymmetric numeral systems (Duda) 2009).
Arithmetic coding, in particular, is known to be optimal in terms of coding length, meaning that the overall compression performance depends on the capabilities of the probabilistic model (see Fig. []] for an overview of arithmetic coding). Incidentally, in recent years, large pre-trained Transform- ers (Vaswani et al. 2017), so-called foundation models (Bommasaní et al. (202T) have proven to be fo-calleefoundatiion
highly successful across wide range of predictive tasks (Bubeck et al. [023 Rae et al., [022] and are thus promising candidates for use with arithmetic coding. Indeed, Transformer-batt with arithmetic coding has produced state-of-the-art results both in the online (Bellard 2021 Mao et al. 2022) and offline settings (Valmeekam et al.) 2023). In the online setting, pseudo-randomly initialized model is directly trained on the stream of data that is be compressed, while the offline setting, which we consider in our work, trains the model on an external dataset before employing it to compress (potentially different) data stream. Consequently, offline compression is performed in- context, with a fixed set of model parameters. Transformers have demonstrated impressive in- in-context learning abilities (Laskin al. 2023] Brown al., 2020 Wei al. 2022) Genewein et al. 2023) and are thus ideally suited for offline compression.
compression
Equal contribution. 'Google DeepMind. "Meta AT Inria. Correspondence (gdelt, anianr) @ @ggogle.com.

---

Published as a conference paper at ICLR 2024
Input (4 bytes)
A
X
0.45
0.36
0.36
P.X)=0,25
-
b01
0.36
b010
=03)A1)=0.35
b0101
0.341
b1
0.75
0.266
b0101010
P(IJAIX)
-0.2
D.))=
0.25
0.25
0.322
0.5
0.45
P0.)
0.3125
PO]A1)=0.45
b001
60
P(A)=0.45
b00
0.09
0.144
P(A]AIX)-0.6
0.125
b0100
P(A)A)=0.2
P(AJA))=0.2
0.09
b0
bo?
b010
b0101010
Output (7 bit)
Figure I: Arithmetic encoding of 'AIXT with a probabilistic model / (blue) resulting in the binary code 'b0101010' (green). We iteratively divide the real interval / = [0, 1) according to the model's (conditional) probabilities and select the sub-interval corresponding to the observed symbol (e.g.. I= [0, 0.45) for P(A)). We further refine for each input symbol (indicated by the arrows), e.g.. -= [0.09, 0.36) for A)] To determine the encoded output, we iteratively split (0, 1) in half and assign a binary code to each sub-interval (shaded red areas). At every step we can output the binary code if / fully contained in the corresponding binary interval (c.g.. 'bo' for 'A', but not for 'Al' as it could be 'b00' 'b01"), At the end of the input, the code is 'b0101', which cannot be uniquely decoded (PXA[ATX) ATX)) P(X ATX) all overlap with 'b0101'). Thus, we further refine the binary code until its binary interval is fully contained in I (all calculations in Appendix Ap.
The context length is a key limiting factor in offline compression, as it dictates the maximum number of bytes a model can compress at a time. Transformers can only compress a few kilobytes (cach "token" being coded with 2 or 3 bytes), while requiring lot of compute. Correspondingly, many challenging predictive tasks (e.g., algorithmic reasoning or long-term memory) require long contexts (Delétang al. (023), and thus extending these models' context lengths is key challenge which is gaining increased attention (Zaheer et al., 2020 Guo et al. [022 Bulatov et al. 2023). The in-context compression view provides insights into the failure modes of current foundation models.
This Work We advocate for using (lossless) compression study foundation models. To that end, we conduct an extensive empirical investigation the offline (in-context) compression capabilities of large language models, with the rationale that they have become readily available (Touvron et al.) 2023a b) and can thus be used for compression without the training overhead. We empirically demon- strate that these models, while (meta-)trained primarily text, achieve competitive compression rates across different data modalities, outperforming domain-specific standard compressors (not accounting for model parameter size). Moreover, we shed new light on scaling laws (Kaplan et al.) 2020), showing that they also hold true for compression but that measuring the adjusted compression rates instead the log loss adds a twist: Scaling beyond a certain point will deteriorate the compres- sion performance since the model parameters need to be accounted for in the compressed output. Finally, we advocate for framing (self-supervised) prediction through the lens of compression as encompasses generalization: a model that compresses well generalizes well (Hutter 2006).
Contributions
We empirically study the lossless compression capabilities of foundation models:
We review how to compress with predictive models via arithmetic coding and call attention to the connection between current language modeling research and compression.
We show that large language models achieve impressive compression rates (disregarding model parameter size) on modalities other than text. For example, Chinchilla 70B achieves compression rates of 43.4% on ImageNet patches and 16.4% on LibriSpeech samples, beating domain-specific compressors like PNG (58.5%) or FLAC (30.3%), respectively.
2

---

binary source Published as a conference paper at ICLR 2024
We revisit scaling laws, showing that the dataset size provides hard limit on model size in terms of compression performance and that model scaling is not a silver bullet.
We leverage the compression- prreecicionnniiiiiionnn equivalence to employ compressors as generative models and visually illustrate the performance of the underlying compressor.
We demonstrate that tokenization, which can be viewed as a pre-compression, does, in gen- eral, improve compression performance, but allows models to increase the information content in their context and is thus generally employed to improve prediction performance.
BACKGROUND
In this section, we review the necessary background on information theory and its relation to likelihood maximization. To that end, consider streams of data 21:m 21 .., E X of length from a finite set symbols X. We write øıj = Æej+1 == Fisj for j Σ n and denote the empty string as c. Finally, we denote the concatenation of two strings and by sr.
coding distribution p is a sequence of probability mass functions Pn. X" + (0, 1], which for all E N satisfy the constraint that P.. (1(mm)))) ΣyEx Pn-1(X1mm)) for all Ji:n E X", with the base case Po(c) 1. From here out, whenever the meaning is clear from the argument to we drop the subseript on p. Under this definition, the conditional probability of a symbol x, given previous data Fen is defined as p(In F<n) = p(x1m))/////))))))))(()))))))p ((( with the familiar chain rules p(aim)) Il
Coding Distributions
p(az Fe3) and jz (ee))) = II p(ar i xes) following.
Lossless Compression The goal of lossless compression is to encode stream of symbols 2i-m sampled from a coding distribution into a bitstream minimal (expected) length, while ensuring that the original data sequence is recoverable from the bitstream. To that end,
code c : X + {0, 1}", which assigns to each possible data sequence Fich a binary code word c( of length (I (in bits). Thus, the aim is minimize the expected bits per sequence L = (fa i.e., encoding rare sequences with more bits and frequent sequences with fewer bits. Shannon's 's source coding theorem establishes the limit on possible data compression as L > (p)
for any possible code, where (p) == Ez~pl- loga p(r) is the Shannon entropy (Shannon 1948
Arithmetic Coding Given a coding distribution and sequence Iin arithmetic coding (Pasco) 1977; Rissanen 1976) constructs a code with almost optimal length. It directly connects coding and compression with prediction and modeling: compressing well means modeling well in a log- loss sense and vice-versa. Assuming infinite precision for the arithmetic operations involved, the arithmetic code has length- - -[lo (( 1 bits, whereas the optimal code length is log p(x).a) bits. A practical implementation that is subject to bit precision adds further O(n2 B) bits (Howard Vitter [99T), which is negligible for 32- or 64-bit arithmetic. the following we consider infinite precision arithmetic coders and refer to Witten et al. (1987) for the finite-precision implementation.
Arithmetic Encoder The arithmetic code of sequence 2i.m is the binary representation of number E [o, 1). We identify À by narrowing down an interval that encloses X step by step (maintaining growing prefix of the binary representation of À throughout the process). Initially, this interval is Io = j0, 1). In step & > 0 (i.e., encoding Æx). we first partition the previous interval J--1 = [4 1, uk 1 into N sub-intervals (x)),, Te(2)),.... one for each letter from = {x1, T2,... (21,,22,-
J. The size of sub-interval (y) that represents letter y is (ux-1 - 4--1) 1s-11)p(o) p(y xee). Formally, define
[(x):= = 4-1+ (1x1-141---
Σ Ely x 4-11 + (wx-1 - 4-1) Σ Epl x<() v<x
assuming a strict order on X. To encode I&k we proceed with its corresponding interval, i.e.,
I, = Ig (zz). Finally, we choose À E In with the shortest binary representation in the terminating interval T, and use that binary representation encode Ti:a- Fig. I iillustrates this process.
3

---

Published as a conference paper at ICLR 2024
Arithmetic Decoder Given À and p decoding the k-th letter is easy: Starting with Iu [0, 1), find y such that À E Tx(y)) decode 2 y: then & Fy. (2x)) and proceed with the k 1-st letter.
Likelihood Maximization In practice, the source distribution p is usually unknown and is in- stead estimated with parametric probabilistic model p. Thus, instead of achieving code length >i= == loga p(z; (ex) for the sequence Zinn we obtain the suboptimal length -E= log, p(r; T As result, the expected (suboptimal) number of bits is the cross-entropy:
Hp := E=
loga p(1; xes)
(2)
Thus, we can minimize the expected length of the encoded data stream with symbols distributed according to p by minimizing the cross-entropy with respect to some á, which is equivalent to likelihood maximization [MacKay] 2003). However, Eq. (2) is exactly the same objective used to train current foundation models, i.e., the log-loss. Thus, minimizing the log-loss is equivalent to minimizing the compression rate that model used as a lossless compressor with arithmetic coding, objective.
ie., current language model training protocols use maximum-comprestte
Compression-Basee Baased Sequence Prediction Analogous to how predictive distribution can be used for lossless compression via arithmetic coding (described above), any compressor can be employed for sequence prediction (Frank et al. 2000). The main idea is to define p(z1.n) as the coding distribution 2 2-f2(), where & (1m))))) is the length of sequence Fin when encoded with compressor c (e.g., gzip). by computing (f((ae)) (f((es)))) for all z,.
We thus recover the conditional distribution p(a; I<l))
Universal Coding Above we discussed optimal (arithmetic) coding with respect to data sam- pled from fixed distribution p. In contrast, universal (optimal) source coding with respect to all computable sampling distributions can, in theory. be achieved by choosing fc(x1.)) as the Kolmogorov complexity of øi.n (Kolmogorov) 1998 Li & Vitányi| 2019). For this choice, the conditional distribution described above is universally optimal over T< recovering the Solomonoff predictor (Solomonoff 1964a]b] |aathannner Bayesian mixture of all predictors that can be programmed in chosen Curingecomplete program- ming language. More precisely, for a predictor q of program-length (g(g) bits, the Solomonoff predictor assigns a prior weight of 2-(-(9) to predictor q. That is, if Q is the set of all pre- dictors that can be programmed and computed, the Solomonoff predictor assigns probability for
Hutter] 2011). The Solomonoff predictor a
((11.) Eye 2-4((9) (31m)) to sequence Ti... Therefore, S(x1.)) > 2 2-(c(9) all q E Q, and thus log, S(#1m) S logg g(#1m))+ le(g). Observe that lc(g) is a constant of that is independent of the sequence length. Therefore, compressing optimally is equivalent to predicting optimally and vice versa (Hutter 2005).
EXPERIMENTAL EVALUATION
Here, we evaluate foundation models' (in-context) compression capabilities (details in Appendix B and code at httttss:/ggithub.com www.ttthh.c.oooooooo wtt google http://oooooooooleeeeeeee///aaaa model ltt.iiinnnoooppoooooooe compression).
Compressors We compare our arithmetic coding-based language model compressors to two
competitive general-purpose lossless compressors: gzip (Deutsch] 1996) and its improvement LZMA2 (Pavlov) 2019). used by the 7zip software. Both are based on Huffman coding (Huff) algorithm (Welch) 1984). We also consider specialized
man 1952) and the Lempel-Ziv-We lossless compressors for image and audio data, i.e., PNG (Boutell 1997) and FLAC (Coalson) 2008). respectively. Finally, we evaluate two types of language models (of different sizes) with arithmetic
coding: vanilla decoder-only Transformers (Vaswani et al. (2077), which we train on the enwik8 dataset, and the pretrained Ilama 2 (Touvron et al. 2023b) and Chinchilla (Hoffmann et al. 2022).
3.1 DATASETS
We consider datasets of three different modalities, text, image, and audio, which have (a priori) very different biases for compression and thus provide a good testbed for evaluating a compressor's general capabilities. To render the results comparable across modalities, all our datasets are IGB.
4

---

Published as a conference paper at ICLR 2024
A key question is how to reconcile the different context lengths C' of the compressors consider. Transformers are restricted to short contexts (2048 "tokens", coded over 1 byte for our trained transformers, and 4 bytes for the pretrained models), while gzip uses maximum context of 32 kilobytes, and 1.ZMA2 has a virtually "infinite" context length. Having a longer context allows compressor exploit more sequential dependencies to achieve better compression rate. For compressors with finite contexts, there are two approaches to compress sequences that are longer than the context length: (i) slide the compressor byte by byte, thus always processing a history of the previous C - bytes when compressing a new byte, and (ii) chunk the data stream into S sequences of C' bytes and evaluate the in-context compression (without any history) averaged across batches. For Transformers, we consider the latter approach since sliding would increase their (already very long) running time by factor of S. Therefore, we chunk all datasets into sequences of 2048 bytes and feed them to the compressors one-by-one. However, since classical compressors usually include a header in their compressed output, which can be larger than the compressed data in some cases, we only count it once for all batches. Moreover, since chunking deteriorates the performance of classical compressors, which have context lengths C' >> 2048, we also report their compression rates on the unchunked datasets. We consider the following datasets:
enwik9 The enwik9 dataset (Hutter 2006) consists of the first 000 000 000 (1 billion) bytes of the English Wikipedia XML dump on March 3rd, 2006 and is typically used to measure a model's ability to compress data. It is extension of the enwik8 dataset that only contains the first 100 million bytes. We train our vanilla Transformer models on enwik8, but evaluate on both enwik8 and enwik9 (to evaluate the out-t--distiibution compression performance). While enwik8 included in enwik9, it only represents the first 10% and thus still constitutes a significant distribution shift.
ImageNet The ImageNet dataset (Russakovsky et al. 2015) contains 14 197 122 annotated images from the WordNet hierarchy. Since 2010, the dataset has been used in the ImageNet Large Scale Visual Recognition Challenge (ILSVRC), a benchmark in image classification and object detection. We extract contiguous patches of size 32 x 64 from all images, flatten them, convert them grayscale (so that each byte represents exactly one pixel) to obtain samples of 2048 bytes. We then concatenate 488 821 of these patches, following the original dataset order, to create a dataset of GB.
LibriSpeech LibriSpeech (Panayotov al. 2015) contains roughly 1000 hours of 16kHz English speech data derived from audiobooks of the Libri Vox project that has been segmented and aligned. We chunk the samples into 2048 bytes and gather 488 821 such chunks into a dataset of size GB.
3.2 COMPARING COMPRESSION RATES
Table Ihoww the compression rates for all compressors and datasets. We show both the raw compression rate, which does not take the model size (in bytes) into account, as well as the adjusted rate, which does. The size of the Python program for classical compressors is very small (a few kilobytes at most) and thus barely affects the compression rate. In contrast, language models suffer huge loss in compression rate due to their large size, which cannot be offset when compressing only IGB of data. We encode each neural network parameter with 2 bytes, using a f representation since quantizing weights to this level does not significantly affect performance (Tao et al. 2022) and standard for model inference. Note that further compressing the float parameters using classical compressors does not significantly reduce their size (we obtained rates of 92.2% and 89. % on a 38M parameter Transformer with gzip and I.ZMA2, respectively). We only consider the offline setting, which computes the adjusted compression rate using a two-part code (i.e., it adds the model size to the log-loss of the data). In contrast, prequential (online) coding would provide an alternative view on adjusted compression by computing the adjusted compression rate as the log- plus the size of the training script (not the model parameters). Prequential coding leads to better compression with overparametrized neural networks (Blier & Ollivier 2018). but it requires training the model online both during encoding and decoding (which is very costly for our models).
Foundation Models Are General-Purpose Compressors A lossless compressor induces an injective function over bit sequences, meaning that we camnot compress all sequences equally well (by the pigeonhole principle). Consequently, in practice, compressors are often tailored to a particular setting, e.g., FLAAC for audio or PNG for images, and thus fail to compress other data modalities well
5

---

Published as a conference paper at ICLR 2024
Table Compression rates (compressed size raw size) on different datatsets (lower is better). The raw compression rate does not take the parameter size into account for the neural models, while the adjusted compression rate considers the parameter size part of the compressed size. All datasets are of size GGB. Random data is used as baseline and should not be compressible. Transformer, Llama 2. and Chinchilla are predictive models, which we use with arithmetic coding to obtain lossless compressors. We train the Transformer models from scratch on enwik8, while the Chinchilla models are pretrained on large text datasets. Transformers trained on enwik overfit to that data modality, while large language models are good compressors for various data types.
Raw Compression Rate (S)
Adjusted Compression Rate
Chunk
Compressor
enwiky
ImageNet
LibriSpeech
Random
enwik)
ImageNet
LibriSpeech
Random
gzip
32.3
36.4
100.0
32.3
70.7
36.4
LZMA2
23.0
57.9
29.9
100.0
23.0
57.9
29.9
100,0
PNG
42.9
32.2
100.0
42.9
58.5
32.2
100.0
FLAC
89,5
61.9
30,9
107.8
89.5
61,9
30,9
107.8
grip
48.1
68.6
38.5
100.1
48.1
68.6
38.5
100.1
1.7M22
50.0
62.4
38.2
100.0
50.0
62.4
38.2
100.0
PNG
80.6
61.7
37.6
103.2
80.6
61.7
37.6
103.2
FLAAC
88.9
60.9
30.3
107.2
88.9
60.9
30.3
107.2
Transfommer 200K
30.9
194.0
146.6
195.5
30,9
194.0
146.6
195.5
2048
Transfomer 800K
21.7
21.9
200.3
Transformer 3.2M
17.0
215.8
228.2
224.0
17.7
216.5
228.9
224.7
Llama 2 (7B)
8.9
53.4
23.1
103.2
1408.9
1453.4
1423.1
1503.2
Chinchilla IB
11.3
62.2
24.9
108.8
211.3
262.2
224.9
308.8
Chinchilla 7B
10.2
54.7
23.6
101.6
1410.2
1454.7
1423.6
1501.6
Chinchilla 70B
8.3
48.0
21.0
100.8
14008.3
14048.0
14021.0
14100.8
(see Table [ In contrast, general-purpor compressors, such as gzip, offer good performance on wide range of data sources. Surprisingly, large language models, while trained primarily text, also appear to be general-purpose compressors, as they outperform all other compressors, even on image and audio data (see Table Dp. Note that these models have not been trained on this kind of data: for Chinchilla, Appendix A. of Hoffmann et al. (2022) states that the training dataset consists of mix of internet text data (Wikipedia, websites, github) and books. However, it is still possible (but unlikely) that some images or audio samples were encoded into text on some websites. Thus, pretrained models achieve their impressive compression performance by conditioning a (meta-)trained model to a particular task at hand via in in-context learning (Genewein et al., (023). In contrast, smaller Transformers, trained manually on enwik8, only achieve good compression rates on similar Wikipedia data, i.e., enwik9. However, larger models' stronger in-context compression (or in-context learning) comes at a price: the number of parameters, which has be offset with increasingly large data sources when computing the adjusted compression rate (see Section 3.3)
3.3 OPTIMAL MODEL-DATASER SIZE TRADEOFF
As shown in Table [ foundation models incur a huge cost in compression rates when accounting for their size, which is in the order of hundreds of GBs for billions of parameters. In theory, if the dataset is infinite, we can ignore the model's size since it is insignificant compared to the size of the dataset. However, in practice, foundation model can only achieve non-trivial (adjusted) compression rates when evaluated on datasets in the order of TBs (or more). Since this is infeasible under reasonable hardware constraints, we instead investigate the optimal model size with smaller Transformers that we train on enwik8. Recall that the model size (in bytes) is twice the number of (float parameters.
Fig. visualizes the adjusted compression rate for vanilla Transformers of different sizes for enwik. We observe that larger models achieve better compression rates on larger datasets, justifying recent trends in model scaling (Kaplan et al. 2020). However, they achieve worse rates on smaller datasets, indicating that scaling laws are, in fact, dependent on the size of the test set. That is, for each dataset, the model sizes reach critical point, after which the adjusted compression rate starts to increase again the number of parameters overweighs the size of the dataset. Note that evaluate offline compression, i.e., we do not necessarily compress the data the model was trained on, meaning that the results on enwik7 and enwik8 are in-distribution, while enwik9 is (partially) out-of out-of-distribution

---

Published as a conference paper at ICLR 2024
enwik7
Adjusted compressio on rate
enwikg
Table Raw compression rates (com- pressed size / raw size) on enwik9 for Transformers trained on enwik8 with dif- ferent tokenizers, ASCII and byte-pair encoding (BPE), with various vocabu- lary sizes. Transformers compress better with simpler tokenizers. However, larger vocabulary sizes reduce the length of the sequence more, meaning more informa- tion can be packed into the context.
10
10f
107
Model (in bytas)
Figure 2: Adjusted compression rates (compressed size raw size) for Transformers of different sizes, trained on enwik8 and evaluated on enwik (both axes are logarith- mic). Here, the compressed size does not only consider the size of the compressed output (roughly equal to the log-loss) but also the model size, which causes all curves to increase at some point. Every dataset gives rise to an optimal model size, with a good trade-off between performance (the size of the compressed data) and cost of the model (the number of parameters). The larger the dataset, the more parameters we can afford.
Raw Compression Rute (%)
Tokenizer
200K
6.4M
38M
ASCII
22.9
13.6
6.4
BPE IK
25.4
14.8
6.9
BPE 2K
25.6
15.7
7.4
BPE 5K
23.1
17.1
8.7
BPE 10K
21.3
17.0
8.9
BPE 20K
19.3
16.4
9.0
3.4 COMPRESSORS AS GENERATIVE MODELS
3.2 we showed that any predictor can be employed as a compressor. Here, following 2 we empirically demonstrate the opposite direction, i.e., that compressors can be used sequence prediction model, establishing our main claim that "language modeling is compression". We compute the length le of the compressed sequence c( for all possible b X to get the probabilities p(b) < 2(=(=<))-(<(x<<)) This can straightforwarddy be extended to sampling whole continuation autoregressively by appending the last output to the sequence and iterating.
In Section
Section
Theoretically, there no strong guarantee that good compression rate leads "good" autoregressive samples. However, empirically it has been shown that better sequence prediction (i.e., lower log-loss, often leads better generation (Rae al., 2021: Brown al. 2020). Nevertheless, in autoregressive sampling small errors often accumulate, which can lead to samples that diverge from the ground-truth distribution. Also, this standard sampling technique only looks one step into the future, and can be biased: gzip, for instance, builds an internal dictionary of 'tokens', which will be compressed using their indexes. Extending the sequence deg with one of these tokens will lead to good compression rate, but will be omitted as it can be longer than one byte. Our neural models do not suffer such bias as they are trained to predict one step ahead with the cross-entropy loss.
We compare the generative capabilities of gzip and Chinchilla 70B images in Fig. Each image is a sampled from ImageNet with height 290 and width 500. For each row in the image, we condition the model on the first 250 pixels and autoregressively generate the remaining 250 pixels, treating different rows as independent of each other (an oversimplification w.r.t. natural image statistics). We use the same byte conversions and tokenization details explained in Appendix [B Chinchilla 70B shows signatures of visually appropriate continuations (judged qualitatively). which tend to degrade with increased sample length more and more error accumulates. gzip produces much noisier completions. We compare the generative performance of gzip and Chinchilla (IB, 7B, and 70B) across all three data modalities in Figs. to for text, image, and audio data, respectively.
3.5 SEQUENTIAL EVOLUTION OF IN-CONTEXT COMPRESSION
Language models take very different "approach" to compression compared to classical compressors. Classical compressors have a small program size and optimize for a large context length to exploit sequential dependencies in the data. In contrast, foundation models consist of billions of parameters,
7

---

Published as a conference paper at ICLR 2024
(a) Original image
(b) gzip (row-wise)
(c) Chinchilla (row-wise)
Figure 3: Compression-basee generation for image data. We condition gzip and Chinchilla on the first half of every row of the ImageNet image and then sample the remaining half autoregressively. Both models produce incoherent samples, but Chinchilla looks much less noisy than gzip.
tomgressonn P9)
10*
Com Domgrassion (9)
4.8M
10a
Chinchilla
10a
qCip
Row Compression
10a
10-
10-
16:
10a
500
1000
1500
2000
500
1000
1500
2000
500
1000
1500
2000
Sequence Length (Byles)
Sequence Length (Byles)
Sequence Length (Byles)
(a) enwik9
(b) ImageNet
(c) LibriSpeech
Figure 4: In-context compression rate over sequence length. For every dataset, we compute the compression rate for all subsequences 2048 bytes, averaged over 100 sequences.
which enable rapid adaptation in their (relatively) short context window (Genewein et al. 2023 ).
Thus, arithmetic coding- based compressors rely heavily on the predictive models' in-context learning capabilities to achieve competitive compression performance. We investigate this phenomenon in Fig. 4 which visualizes the compression rate across sequence lengths for gzip, Chinchilla IB and enwik8. Intuitively, the longer the sequence, the more data the model can process in context, and therefore, the better the compression. decrease quickly with increasing sequence length, indicating that the models learn some data statistics in-context, without any gradient-base pradient-based training. As in Table the Chinchilla model achieves the best compression rates across all three data modalities and sequence lengths.
Transformer pretrained
expected, most compression rates
3.6 TOKENIZATION IS COMPRESSION
Transformers generally not trained raw input data but tokenized versions thereof, both for efficiency and performance reasons. As a consequence, Transformers are trained on compressed data, with tokenizers acting the compressor. Since tokenization is known have impact the generalization performance (Radford et al., (201)), we investigate its impact on the compression rate Table 2 Concretely, we train Transformers on enwik8 using different tokenizers: ASCII, i.e., an alphabet of size 256 (no tokenization), and byte-pair encoding trained on enwik8, with various vocabulary sizes (1K, 2K, 5K, 10K, and 20K tokens). Note that the tokenizations are lossless.
Increasing the number of tokens (i.e., the "alphabet size") reduces the length of the sequence and models context. However, decreasing the sequence
thus increases the amount of information length comes at price: the number of tokens is larger, which makes the prediction task more challenging since reducing the entropy of the conditional distribution p(z; x<<e) increasingly difficult for larger alphabet size. In theory, as the tokenization is lossless compression, the two effects should compensate. practice, we observe that if the model small, increasing the number of possible tokens boosts the compression performance. In contrast, for bigger models, seems that the converse happens: having a larger token vocabulary harms the final compression rate of the model. Nevertheless, short sequence lengths also help Transformers since their time complexity scales quadratically with context length, and it has been shown they do not generalize well long
contexts (Deéétang al. 2023 Ruoss al. 2023
8

---

Published as a conference paper at ICLR 2024
4 RELATED WORK
Prediction vs. Compression Leveraging Shannon's source coding theorem (Shannon, 1948).
plethora of approaches exploit the connection between prediction and compression. For example, context-tree weighting (CTW) (Willems et al. 1995) mixes the predictions of many underlying Markov models to achieve lossless compression via arithmetic coding (Pasco 1977; Rissanen 1976).
Similarly, prediction by partial matching (PPM) (Cleary Witten 1984) also leverages arithmetic coding, but uses a contiguous context matching method to create probability distributions based on the history of characters a sequence. Likewise, PAQ8 (Knoll de Freitas 2012) uses a weighted combination of predictions from a large number of models (most of them based on context matching, but unlike PPM also noncontiguous context matches). In a different setting. Veness et al. (2015) demonstrated how employ compression to obtain value estimates of a policy in an environment. Frank et al. 2000) and later Teahan & Harper (2003) introduced the idea of classification with compressors. Recently, Jiang et al. (2023) applied this technique with NLP tasks, paired with n-nearest-niighbuu algorithm, in which gzip achieves good results. Jiang et al. (2022) exploit the same idea but train the compressor on vast amount of unlabeled data first. Further comparisons on the same tasks have been done between gzip and simple bag-of-words models (Opitz) (023). Finally,
van den Oord & Schrauwen (2014) apply arithmetic coding image compression using Student distribution mixtures and Gaussian processes as predictors.
Compression With Neural Networks Prior work demonstrated that neural predictive distributions
can be employed to perform lossless compression via arithmetic coding (Schmidhuber & Heil
1994
1996. Mahoney| 2000; Knoll 2014 Cox 2016 Schiopu et al., 2018 Goyal et al. 2019 Liu
et al.
2019 Mentzer et al.) 2019 2020; Schiopu & Munteanu] [020 Rhee et al. [022] Mikolov
2012).
Similarly, neural networks were also shown to achieve strong lossless compression rates
when replacing arithmetic coding with asymmetric numeral systems (Hoogeboom et al.] 2019]]
Kingma et al.] 2019: Townsend al., 2019; [Bazeen et al.,, (022). While these approaches assume the existence of a separate training set, a different line of work investigated arithmetic coding-base based neural compression a purely online fashion, i.e.. training the model only on the data stream that is to be compressed (Bellard 2019 Goyal et al. 2020; Bellard] [02 Mao et al.) (022). Concurrent work (Valmeekam al. (023) also investigated lossless offline compression with foundation models, using arithmetic coding with Llama 2 (7B) (Touvron et al. 2023b).
Compression Biases: Tokenization, Model Size, etc. Much effort has been devoted to under- standing the inductive biases of neural networks, in particular with respect to Natural Language Processing (NLP) and Transformers. Kudo & Richardson (2188) developed tokenizer for NLP
that improves over well-known techniques such as byte-pair encoding (BPE) (Sennrich et al. 2016). BPE dropout (Provilkov al. 2020), and subword regularization (Kudo 2018). In this paper, we show how these tokenization techniques act as pre-compressors for the data and can significantly affect the final compression rates when paired with neural model. Other work investigated different aspects of generalization (Neyshabur et al. 2017: Mirchandani et al. 2023 Ge et al. 2023). which is equivalent to compression when accounting for the parameters' codejlength. Finally, [Cheng et al. (2017) investigated compressing the neural models' parameters to further reduce the code length.
CONCLUSION
In this paper we investigated how and why sequence modeling is equivalent to compression. Arith- metic coding transforms sequence model into a compressor, and, conversely, a compressor can be transformed into predictor using its coding lengths to construct probability distributions following Shannon's is entropy principle. We evaluated large language models as compressors against various standard compressors and showed that they are competitive not only on text but also modalities they have never been trained on (image and audio data). We showed that the compression view provides novel insights scaling laws since it takes the model size into account, unlike the log- objective, which is standard in current language modeling research. Consequently, we showed that the optimal model size is inextricably linked to the dataset size and cannot be scaled without limit.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank Jörg Bornschein, Nando de Freitas, Slav Petrov, Zhengdong Wang, and the anonymous reviewers for their helpful feedback and insightful discussions.
REFERENCES
Benjamin Lukas Cajus Barzen, Fedor Glazov, Jonas Geistert, and Thomas Sikora. Accelerated deep lossless image coding with unified paralleleized GPU coding architecture. In PCS, 2022.
Fabrice Bellard. Lossless data compression with neural networks. Technical report, Amarisoft, 2019.
Fabrice Bellard. NNCP v2: Lossless data compression with transformer. Technical report, Amarisoft, 2021.
Léonard Blier and Yann Ollivier. The description length of deep learning models. In NeurlPS, 2018.
Rishi Bommasani et al. On the opportunities and risks of foundation models. arXIv:2108.07258. 2021.
Thomas Boutell. PNG (portable network graphics) specification version 1.0. RFC, 1997.
Tom B. Brown, Benjamin Mannand Nick Ryder, Melanie Subbiah, et al. Language models are few-shot learners. In NeurlPS, 2020.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott M. Lundberg, Harsha Nori, Hamid Palangi, Marco Túlio Ribeiro, and Yi Zhang. Sparks of artificial general intelligence: Early experiments with GPT-4. arXiv:2303. 12712, 2023.
Aydar Bulatov, Yuri Kuratov, and Mikhail S. Burtsev. Scaling transformer Im tokens and beyond with RMT. arXiv:2304. /062, 2023.
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and acceleration for deep neural networks. arXiv: 171000922, 2017.
John G. Cleary and lan H. Witten. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun., 1984.
Josh Coalson. Free lossless audio codec, 2008. UtU/tttp::/xipp.orr/ff
David Cox. Syntactically informed text compression with recurrent neural networks. 16Xiv:1608.0 02893, 2016.
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the chomsky hierarchy. In ICLR, 2023.
Peter Deutsch. GZIP file format specification version 4.3, RFC, 1996.
Jarek Duda. Asymmetric numeral systems. arXiv:0902.0271, 2009.
2009.
Eibe Frank, Chang Chui, and Ian H. Witten. Text categorization using compression models. In Data Compression Conference, 2000.
Tao Ge, Jing Hu, Xun Wang, Si-Qing Chen, and Furu Wei. In-context autoencoder for context compression in large language model. arXiv:2307.0600 2023.
Tim Genewein, Grégoire Delétang, Anian Ruoss, Kevin Wenliang, Elliot Catt, Vincent Dutordoir,
Jordi Grau-Moya, Laurent Orseau, Marcus Hutter, and Joel Veness. Memory-based meta-learning on non-stationary distributions. /CML, 2023.
Mohit Goyal, Kedar Tatwawadi, Shubham Chandak, and Idoia Ochoa. Deepzip: Lossless data compression using recurrent neural networks. In DCC, 2019.
10

---

Published as a conference paper at ICLR 2024
Mohit Goyal, Kedar Tatwawadi, Shubham Chandak, and Idoia Ochoa. Dzip: Improved general- purpose lossless compression based on novel neural network modeling. In DCC, 2020.
Mandy Guo, Joshua Ainslie, David C. Uthus, Santiago Ontañón, Jianmo Ni, Yun-Hsuan Sung, and Yinfei Yang. Longt5: Efficient text-to-text transformer for long sequences. In NAACL-IILT (Findings), 2022.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, et al. Training compute-optimal large language models. arXiv:2203.15556, 2022.
Emiel Hoogeboom, Jorn W. T. Peters, Rianne van den Berg, and Max Welling. Integer discrete flows and lossless compression. In NeurlPS, 2019.
Paul G. Howard and Jeffrey Scott Vitter. Analysis of arithmetic coding for data compression. In Data Compression Conference, 1991.
David A. Huffman. A method for the construction of minimum cinimuum-rddundncyy codes. Proceedings of the IRE, 1952.
Marcus Hutter. Universal Artificial Intellegence Sequential Decisions Based on Algorithmic Probability. Springer, 2005.
Marcus Hutter. hutterl.net!
prize for compressing human knowledge, 2006. URL http://priz
Zhiying Jiang, Yiqin Dai, Ji Xin, Ming Li, and Jimmy Lin. Few-shot non- non-parametric learning with deep latent variable model. In NeurlPS, 2022.
Zhiying Jiang, Matthew Y. R. Yang, Mikhail Tsirlin, Raphael Tang, Yiqin Dai, and Jimmy Lin. "low-resource" text classification: A parameter-free classification method with compressors. In ACI. (Findings) 2023.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv:2001.0836 2020.
Friso H. Kingma, Pieter Abbeel, and Jonathan Ho. Bit-swap: Recursive bits-back coding for lossless compression with hierarchical latent variables. In ICML, 2019.
Byron Knoll. CMIX, 2014. URL./htt::/wwwwbbyrrokkko www.cmim..cccccccc html
Byron Knoll and Nando de Freitas. machine learning perspective on predictive coding with PAQS. In DCC, 2012.
Andrei N. Kolmogorov. On tables of random numbers. Theoretical Computer Science, 1998.
Taku Kudo. Subword regularization: Improving neural network translation models with multiple subword candidates. In ACL (1), 2018.
Taku Kudo and John Richardson. Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. EMNLP (Demonstration), 2018
Michael Laskin, Luyu Wang, et al. In-context reinforcement learning with algorithm distillation. In ICLR. OpenReview.net, 2023.
Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition. Springer, 2019.
Qian Liu, Yiling Xu, and Zhu Li. DecMac: A deep context model for high efficiency arithmetic coding. In ICAIIC, 2019.
David J. C. MacKay, Information theory, inference, and learning algorithms. Cambridge University Press, 2003.
Matthew V. Mahoney. Fast text compression with neural networks. In FLAIRS, 2000.
11

---

Published as a conference paper at ICLR 2024
Yu Mao, Yufei Cui, Tei-Wei Kuo, and Chun Jason Xue. TRACE: A fast wansformer-basee general- purpose lossless compressor. In WWW, 2022.
Fabian Mentzer, Eirikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Practical full resolution learned lossless image compression. In CVPR, 2019.
Fabian Mentzer, Luc Van Gool, and Michael Tschannen. Learning better lossless compression using lossy compression. In CVPR, 2020.
Tomas Mikolov. Statistical Language Models Based on Neural Networks. PhD thesis, Brno Universtiy of Technology, 2012.
Suvir Mirchandani, Fei Xia, Pete Florence, Brian Ichter, Danny Driess, Montserrat Gonzalez Arenas, Kanishka Rao, Dorsa Sadigh, and Andy Zeng. Large language models general pattern machines. arXiv:2307.04721, 2023.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generaliza- tion in deep learning. NIPS, 2017.
Juri Opitz. Gzip versus bag-of-words for text classification, 2023.
Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: An ASR corpus based public domain audio books. In ICASSP, 2015.
Richard C. Pasco. Source coding algorithms for fast data compression (ph.d. thesis abstr.). IEEE
Trans. Inf. Theory, 1977.
Igor Pavlov. 7z Format, 2019. wtL.ttp::www..7z....rgg///
Ivan Provilkov, Dmitrii Emelianenko, and Elena Voita. Bpe-dropout: Simple and effective subword regularization. In ACL, 2020.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models unsupervised multitask learners. Technical report, OpenAI, 2019.
Jack W. Rae et al. Scaling language models: Methods, analysis & insights from training gopher. arXiv:2112.11446, 2021.
Samuel Rathmanner and Marcus Hutter. A philosophical treatise of universal induction. Entropy. 2011.
Hochang Rhee, Yeong Il Jang, Seyun Kim, and Nam Ik Cho. LC-FDNet: Learned lossless image compression with frequency decomposition network. In CVPR, 2022.
Jorma Rissanen. Generalized kraft inequality and arithmetic coding. IBM J. Res. Dev., 1976.
Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani. Shane Legg, and Joel Veness. Randomized positional encodings boost length generalization of transformers. In ACI (2), 2023.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and Li Fei-Fei. Imagenet large scale visual recognition challenge. Int. J. Comput. Vis., 2015.
Ionut Schiopu and Adrian Munteanu. Deep-learning-basse lossless image coding. IEEE Trans. Circuits Syst. Video Technol., 2020.
Ionut Schiopu, Yu Liu, and Adrian Munteanu. CNN-based prediction for lossless coding of photo- graphic images. In PCS, 2018.
Jürgen Schmidhuber and Stefan Heil. Predictive coding with neural nets: Application to text compression. In NIPS, pp. 1047-1054. MIT Press, 1994.
Jürgen Schmidhuber and Stefan Heil. Sequential neural text compression. IEEE Trans. Neural Networks, 1996.
12

---

Published as a conference paper at ICLR 2024
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. ACL (1), 2016.
Claude E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., 1948.
Ray J. Solomonoff. A formal theory of inductive inference. part I. Inf. Control., 1964a.
Ray J. Solomonoff. A formal theory of inductive inference. part II. Inf. Control., 1964b.
Chaofan Tao, Lu Hou, Wei Zhang, Lifeng Shang, Xin Jiang, Qun Liu, Ping Luo, and Ngai Wong. Compression of generative pre-trained language models via quantization. In ACL, 2022.
William J. Teahan and David J. Harper. Using CimpresssionBasee Language Models for Text Categorization, pp. 141-165. Springer Netherlands, 2003.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, al. Llama: Open and efficient foundation language models. arXiv:2302. 2023a.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay 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, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Ilama 2: Open foundation and fine-tuned chat models. arXiv:2307.09288, 2023b.
James Townsend, Thomas Bird, and David Barber. Practical lossless compression with latent variables using bits back coding. In ICLR (Poster), 2019.
Chandra Shekhara Kaushik Valmeekam, Krishna Narayanan, Dileep Kalathil, Jean-François Cham- berland, and Srinivas Shakkottai. Llmzip: Lossless text compression using large language models. arXiv:2306.00
04050, 340.0000000 2023.
Aäron van den Oord and Benjamin Schrauwen. The student-t mixture as a natural image patch prior with application to image compression. J. Mach. Learn. Res., 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NIPS, 2017.
Joel Veness, Mare G. Bellemare, Marcus Hutter, Alvin Chua, and Guillaume Desjardins. Compress and control. AAAI, 2015.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoe V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In NeurlPS, 2022.
Terry A. Welch. A technique for beg-operformanc data compression. Computer, 1984.
Frans M. J. Willems, Yuri M. Shtarkov, and Tjalling J. Tjalkens. The context-tree weighting method: basic properties. IEEE Trans. Inf. Theory, 1995.
Ian H. Witten, Radford M. Neal, and John G. Cleary. Arithmetic coding for data compression. Commun. ACM, 1987.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang. Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences. In NeurlPS, 2020.
13

---

Published as a conference paper at ICLR 2024
A ARITHMETIC CODING
Here we provide step-by-step explanation of the arithmetic encoding example visualized in Fig. Recall from Section 2 that arithmetic encoding iteratively partitions the interval / = [0, 1) according to predictive model P and an input string, i.e., AIXI for Fig. |
First, we construct the intervals for the first token, corresponding to P(-):
[0, 0.45) for P(A) 0.45
(0.45, 0.75) for P(7) 0.3
[0.75, 1) for P(X) 0.25
Since the first token is A, we set / - 0.45) and iterate. Thus, the intervals for P(-IA) are:
[..2 0, 0.2 0.45) = [0, 0.09) for P(4[A) = 0.2
[0.09; (0.2 0.6) 0.45) = [0.09, 0.36) for P(7JA) 0.3
[0.36, (0.2 0.6 0.2) 0.45) = 0.366, 0.45) for P(X|A) 0.2
Since the next token is I, set / [0, 0.44) and so We terminate with / 00.322, 0341) for ATXT. Next, arithmetic will compute the binary sequence corresponding to iteratively splitting the interval [0, 1) in half until is fully contained in /. Concretely, this yields the binary sequence.
60 [0, 0.5)
. 801 + [0.25, 0.5)
6010 - [0.25, 0.375)
b0101 + [0.3125, 0.375)
101010 > [0.3125, 0.34375)
0010101 + [0.328125, 0.34375)
60101010 - [0.328125, 0.3359375)
As 10.328125, 0.3359375) is fully contained in / [0.322, 0341), the compressed output is 0101010. which consists of 7 bits as opposed to the 4 bytes used to encode AIXI.
B EXPERIMENTAL DETAILS
B. DATA MANIPULATION
ASCII as a standard The neural models we use (Transformers trained specifically on enwik, and Chinchilla which trained vast and diverse set of text from various sources) take text input. In theory, they could take in any Unicode character, but unfortunately not all bytes in the range [128, 256]. However, any ASCII character, i.c. in the range [0, 127] is a valid input. Therefore, to compress all bytes sequences by first mapping them to the range [0. 127]. We account for the loss of bit by updating the compression ratio accordingly, necessary. Each character that needs some processing adds bit to the final compressed sequence.
chose
Compressing text Text compression is very straightforward. As state above, the text is encoded in most significant bit, such that the value falls back in the range [0, 127], suitable for ASCII encoding. We append this lost bit at the end of the compressed byte sequence, account for in the compression rate.
ASCII format. the character is special, we zero the
Image data comes as patches of size (32, 64), each pixel being grayscaled and therefore encoded on I byte. This byte gives the brightness of the pixel, being completely black and 255 being completely white. We then flatten this patch to get a sequence of 2048 bytes. Note that it means we lose some dimension correlation between the pixels: the last pixel of the first line will be right next to the first pixel of the second line. For each byte, map it into the range [0, 127),
Compressing images
14

---

Published as a conference paper at ICLR 2024
simply divide it by 2, and lose the least significant bit. This is performed via simple byte shifting. Note that we do this transformation for every byte, and not only those in the range [128, 255], for consistency. We append the lost bit to the end of the compressed byte sequence, as explained above.
Compressing sound Sound data from LibriSpeech is sampled at 16Khz, with a sample size of bytes (int16). We manually reduce the sample size to 1 byte. We then split the raw dataset into chunks of size 2048 bytes each, which correspond to roughly 64 milliseconds of speech. We checked whether reducing the sample rate to have longer sequences had a significant impact on the relative compression powers of the models, and we concluded that it had not. We chose to keep the original rate for our experiments. Exactly as for images, for each byte, to map into the range [0, 127], we simply divide it by 2, and lose the least significant bit. Note that we do this transformation for every byte, and not only those in the range [128, 255], for consistency. The lost bit also appended at the end of the compressed byte sequence, explained above.
B.2 LARGE LANGUAGE MODELS TOKENIZATION
As described in the last subsection, the data fed to the large language models we use (Chinchilla and LLama2) is an ASCII string of exactly 2048 characters. However, the models immediately tokenizes the string using SentencePiece (Kudo & Richardson (018)). The string is transformed into sequence of integer tokens between 0 and T. T being the vocabulary size (they both use T = 32000). Note that the length of the sequence has now completely changed, and depends on the input: tokenization already form lossless compression. This sequence is fed into the big pretrained Transformer model, which gives the conditionals x(y] for all histories I<i and tokens in the alphabet y. Denoting the length of the sequence after tokenization as I, we obtain T log rogg-rrbbbblities We can pass them to arithmetic encoder of vocabulary size T, to encode the sequence into bits. This is final compressed sequence, which size in bytes is compared with the initial size, i.e., 2048 bytes.
In practice, the large models had only access the top-k next token log- pog-pobbabilities, for each context. We chose k = 100, which almost fully recovers the conditional distribution. Arithmetic coding can still be applied as the alphabet size is allowed change while coding: what matters is that the conditional probabilities in each step sum to I. Accordingly, we renormalize the top-k log- pog-pobbabilities.
The Transformer models we trained specifically on enwik do not use any tokenization, except in Section 3.6 The reasoning above also holds, except that our models returned the full distribution over tokens, and not only the top-k.
C ADDITIONAL RESULTS
Fig. C.I Fig. and Fig. C.3 show data autoregressively generated by compressors, one step at a time. Note that for Chinchilla, we generate tokens (which size bytes can vary) until we reach the length in bytes we desire. Also, note that gzip samples are biased, as explained in Section 3.4 looking 1 step ahead not sufficient to get good samples, and it's likely that looking multiple steps ahead would improve the results. However, that's 's not the purpose of this paper, and we kept the simplest setup for all our compressors.
15

---

Published as a conference paper at ICLR 2024
Context Text (1948 Bytes)
formally appointed Sovercign. Lord of Appeal Ordinary must retire al the age of 70, oz, his or her term is extended by the Government, the age of 75; after reaching such an age, the Law Lord cannot hear any further legal cases. The number of Lords of Appeal in Ordinary (exchuding those who are cases due age restrictions) limited twelve. Appeal in Ordinary traditionally do not participate in political dehutes, so as to maintain judicial independence. Lorks of Appeal Ordinary hold seats the House of Lords for life. remaining members even after reaching the retirement age of 70 75. Former high judicial office may in practice this right is infrequently exercised. After the coming into force Appeal in Ordinary will become judges of the Supreme Court of the United Kingdom and will be barred from sitting voting until they retire as judges. Anlhlhe largest group Lords Temporal, and indeed of whole House, are Life peetllife peers peers with seals in the House of Lords rank only as burons or buronesses, and are created under the [[Late Peerages Act 1958]]- Like all other peers. life peers created by the Sovereign, who acts on the advice of the Prime Minister. By convention, bowever, Prime Minister allows leaders Lords. Moreover, some non party life peens (the number being determined by the Prime Minister) are nominated by an independent House of Lords Appointments Commission. hereditary peer also holds life pecrage.
ction Act 1876]). They selected by the Prime Minister,
longer
may be chunged by ||statulory instument]] Lords
Load Chancellors
holders
although under Appellate Jurisdiction Constitational Reform Act 2005, the Lords
parties select some poers
political balance the House
Ground Truth (100 Bytes)
she remains member of the House of Lords without a need for an election. In (12000)). the guvernm
gzip Samples (100 Bytes)
(0k5Ezatmc.isbbben ios.ssobbboosoooossssciiiiec peu7vevwt farmissfommceea are nombban hm, c,00. pnemm..ccg uam
Suasa8g thfoempOiufoof Lo oTvkoasacka w8viiuooumb. w@viaafoeumb.bbpp.dcc.... see.pe..gegg...o.deyl.......
CxOsic, F0nF/00nkmmmm eaadhppuffiygglfeaaaaamaammaaa Loventil Lww.enii..myhhoortttysssseeeeeee Apo.arelyehm:,
Chinchilla 1B Samples (100 bytes)
Lords. Appeal in Ordinary she may be compelled by the House of Lords resign his ber life peerage, and receive pension
may, but does not have to, step down
she becomes life peer nutomatically. If life peer succeeded in his or her pocrage, the House
Chinchilla 7B Samples (100 bytes)
she ranks as a life poor without the addition of an "ct" to the peers title. Some heroditary peets
she loses his or her hereditary seal in the House Lorls, and is permitted to sit only as a life Lords as whole. Only heredit
ranks peer in Londs, not
Chinchilla 70B Samples (100 bytes)
may
bereditury peerage considered superior. Temporal
may choose which title though the title life pecrage normally used. The Sover
she may elect to sit in the House life rather than hereditary Life poers
Figure C.1: Compression- generation for text data. We condition gzip and Chinchilla
context text of size 1948 bytes (from enwik9) and then sample 100 bytes (N tokens) autoregressively, Since Chinchilla employs tokenizer, the sampled sequences will contain N tokens, which do not necessarily decode to 100 bytes. Chinchilla's 's predictions are significantly more coherent than gzip's s.
(a) Chinchilla
(b) Chinchilla 7b
(c) Chinchilla 70b
Figure C.2: Compression-bel based generation for image data, for 3 Chinchilla models with different number of parameters. We condition the models the first half of every row of the image (250 bytes) and then sample the remaining half (250 bytes) autoregressively.
16

---

Published as a conference paper at ICLR 2024
(a) Original spectrogram
(b) gzip
(c) Chinchilla
Figure C.3: Compression- generation for audio data. We condition gzip and Chinchilla on the first 1024 bytes of the base sequence (from LibriSpeech) and then sample the remaining 1024 bytes autoregressively. Chinchilla predictions exhibit a typical "loop" pattern of autoregressive generation.
17


Reviews:
[{"review_id": "XWpd2IAVz7", "reviewer": "Reviewer_hCy6", "summary": "This paper demonstrates that pre-trained large language models can be used for compressing text, image, and audio data. This is done by inputing the data to the model and relying on the model’s output probabilities across the vocabulary to perform arithmetic coding. When not considering the size of a model for computing compression ratios, the authors show that Chinchilla-70B, achieves high compression ratios surpassing well-established domain-specific compressors like PNG or FLAC. When taking into account the number of model parameters for calculating the compression ratio, the authors illustrate new empirical scaling-laws by plotting the compression ratio as a function of model size, resulting in an U-shaped curve. This scaling law suggests that depending on the size of a dataset the optimal compression ratio is achieved for one specific model size. The authors also attempt to show how compressors can be used as conditional generative models. Finally, the authors analyze how the context-length for in-context learning and different tokenizers affect a model's compression performance.", "questions": "Questions:\n- The questions mentioned in the \"Weaknesses\" paragraph\n\nSuggestions:\n- To me, some findings feel somewhat scattered and it is difficult to draw a clear conclusion from this work. For example when and why is it important to distinguish between compression rates that consider and do not consider model size, and particularly the part discussing the generative capabilities feels disconnected from the rest of the story. I recommend aligning the narrative more cohesively and concluding with a clear takeaway message\n- I find that the background section is more technical than needed to understand the results of the paper. For example, the authors could maybe show on a concrete example how arithmetic coding works instead being very general and introducing a lot of mathematical notations and concepts. Reducing the relatively heavy use of mathematical notation could also help with reading since most of it does not appear again after the background section. Also, in Figure 1 which illustrates arithmetic coding, there are missing explanations (e.g. arrows are not explained) to guide the reader.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper presents how large language models pre-trained on text data can be used for compression beyond text data \n- The authors demonstrate that this approach outperforms several well-established compression methods like gzip, PNG or FLAC in terms of raw compression ratio\n- The paper provides insights on how different aspects like model size and choice of the tokenizer affects performance. For example, for model size the authors provide empirical scaling laws\n- The experiments are well described, easy to follow, and kept fair for all the methods being compared. \n- Tables and figures showing the results of the experiments are also simple to understand\n- The authors openly discuss limitations of using large language models as compressors (e.g. model size and context length for transformer models)", "weaknesses": "- The motivation of this work is rather unclear to me. Is this work about advocating the use of pre-trained large language models as a potential method for compression? If so, how can they be used as such in practice considering their limitations? Or is it about using the compression framework to better understand large language models? If so, why is it interesting to study pre-trained large language models  \"through the lens of compression\"?\n- The authors mention that they “advocate for using (lossless) compression to study foundation models”. Why and what benefits does this framework have? It is not clear to me how the results in this paper should help my understanding of large language models beyond their use as compressors? What are the further implications of the results?\n- No experiments with pre-trained models other than Chinchilla-70B. Having more models could provide more evidence on the compression capabilities of pre-trained large language models and to see how compression capabilities correlate with prediction performance\n- Not using publicly available pre-trained large language models for reproducibility\n- The results for the generative modeling performance of compressors and Chinchilla-70B look rather poor. For example, the generated image in Figure 3 looks unconvincing since only lines are generated and not actual image content, and a quantitative analysis is also missing. Why is this section important, and why would it fit into the rest of the 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": {}}, {"review_id": "a3sW5oVCa5", "reviewer": "Reviewer_8SR8", "summary": "This paper advocates viewing the prediction problem through the lens of compression and evaluates the compression capabilities of large (foundation) models, thereby providing insights into scaling laws, tokenization, and in-context learning.", "questions": "See weaknesses for questions.\n\nAlso, is the context length of 2048 bytes still a must given the recent work on lifting this length constraint? e.g. \"Efficient Streaming Language Models with Attention Sinks\".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Novel in the sense of applying LLM to compressed coding of images & audio.\n2. Demonstration through resourceful examples.", "weaknesses": "1. The idea of deep model learning being a compression of natural data is not new, I think this is echoed by the authors too. It has, e.g., been a core and explicit theme in \"High Dimensional Data Analysis with Low-Dimensional Models: Principles, Computation, and Applications\". As such, shouldn't the paper's title be more specific, such as \"LLMs are general-purpose image & audio compressors\"?\n\n2.  A key into understanding the algorithm is Fig. 1, but the figure contains ambiguities and confusion. E.g. Why a \"?\" in \"b0?\" only? In the last column, how to go from 4bit to 7bit? The illustration should be more tractable.\n\n3. I have doubt about the \"generative\" model part, for the text examples in B.1, the good performance of Chinchilla over gzip is no surprise. But the poor performance on images & audio in Fig. 3 & B.2 indeed shows LLM can't handle these data in general. How can an LLM even be called generative in images/audio if the results make no sense? If that's the case, the last sentence in Abstract shouldn't be made.\n\n4. I am also doubtful about the part on tokenization. The tokenizer being part of a Transformer is only due to its root in language modeling. In the same vein, we can easily make a claim on \"A CNN stem is compression\" (a CNN has a stem, body & head), and varying the stem (e.g. different strides) we get different compression rates too, so what is interesting in that?\n\nEditorial:\nThe line above Sect 3.6, typo \"accross\"", "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": "86bcdrEqa4", "reviewer": "Reviewer_NHbN", "summary": "The authors argue that predictive models can be transformed into lossless compressors and vice versa, and that language models can also be powerful compressors, providing novel insights into scaling laws and in-context learning. The paper includes experimental details and additional results, including data auto-regressively generated by gzip and Chinchilla.", "questions": "The questions are listed in the weakness part.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.  The paper is well-written and clear to investigate how and why compression and prediction are equivalent. \n2. Evaluate large pretrained models used as compressors against various standard compressors and showed that they are competitive, not only on text but also on modalities they have never been trained on, such as images and audio data.", "weaknesses": "If we discuss the number of parameters in larger language models and how it reflects compression performance, it would be better to investigate the reasons behind this relationship.", "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": "DedLwBCEvm", "reviewer": "Reviewer_55Jb", "summary": "This paper presents an interesting view that connects compression and prediction of LLM. It leverages a pre-defined rule (e.g., Arithmetic coding) to compress a sequence based on the conditional probabilistic intervals of its each token. The compressed content can be losslessly restored to the original content based on the decoding rules that reverse the encoding process. The experimental results show an LLM can be very effective to compress content and works as a general-purpose compressor.", "questions": "See the weakness section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper discusses a novel perspective to connect between compression and sequence prediction. Its evaluations on the compression capabilities of LLMs are extensive and sound. The results that it can compress other modalities like images and audio are pretty interesting and its insight of the compression with the size of data and model (scaling) is inspiring.", "weaknesses": "While this paper introduces a novel perspective to understand the compression ability of Large Language Models (LLMs), its contribution or novelty is not particularly prominent from a high-level idea/conclusion standpoint.\n\nFirstly, the concept that a language model is a form of compression is not new. As early as 2023, in an interview between Nvidia's Jensen Huang and OpenAI's Ilya Sutskever, Ilya mentioned that a language model learns through compression, and the generative model is essentially a compression of data in the world. This insight is well ingrained among most NLP/LLM professionals. Therefore, although this paper connects sequence prediction and compression from an arithmetic perspective, aside from some interesting experimental results, it doesn't provide practitioners with many new insights, such as in terms of methodology. While its LLM compressor performs well compared to gzip, it is difficult to use in practice due to the high inference cost.\n\nSecondly, I believe a major highlight of this paper is the discussion on general-purpose (trained on text, but can work for other modalities) and scaling (the larger, the better at compression). The overall method of the paper still uses the Arithmetic coding approach. However, prior work has already presented similar observations and conclusions, albeit not from an arithmetic coding perspective. For instance, Ge et al. (2023) proposed using lora tuning to adapt the LLM for the compression ability, enabling it to compress a long context into a short span. Although Ge et al.'s (2023) work is not lossless compression, they observed similar phenomena: for example, their Table 3 comparison of normal text, patterned random text, and completely random text shows that LLMs can compress based on certain patterns (even though the model has not seen patterned random text, it performs better on patterned random text than on completely random text). Similarly, their Tables 5 and 8 also indicate that more potent LLMs are better at compression. Therefore, while I find the perspective of this paper novel and interesting, its final conclusions cannot be considered entirely novel.\n\nDespite these weaknesses, I think this paper's contribution overweigh the weaknesses as a research paper to present in ICLR.\n\nReferences:\n\nGe et al. In-context Autoencoder for Context Compression in a Large Language Model. https://arxiv.org/abs/2307.06945", "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)