Language Modeling Is Compression

Grégoire Delétang; 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

Source-linked AI summary

Language Modeling Is Compression

Grégoire Delétang, 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

arXiv:2309.10668v2Sep 19, 2023cs.LGcs.AIcs.CLcs.IT

TL;DR

The paper asks how predictive modeling and lossless compression can be unified and uses this equivalence to evaluate foundation models as compressors. It finds strong cross-modal compression, including 43.4% on ImageNet patches and 16.4% on LibriSpeech samples, while exposing effects of model size, tokenization, and context. It also shows that compressors such as gzip can define conditional generative models.

Problem
Context length limits how many bytes Transformers can compress at a time, motivating compression as a lens for studying foundation-model prediction.
Method
The paper converts predictive distributions into lossless compressors with arithmetic coding and converts compressors into predictors using coding-length-derived probabilities.
Results
Large language models achieve competitive compression across text, image, and audio data, including 43.4% on ImageNet patches and 16.4% on LibriSpeech samples.
Takeaways & Limitations
Compression provides a unified way to study foundation-model generalization, scaling laws, tokenization, and in-context prediction.
Takeaways & Limitations
Good compression does not theoretically guarantee good autoregressive samples, and small sampling errors can accumulate away from the ground-truth distribution.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper frames predictive modeling as lossless compression through arithmetic coding and evaluates foundation models as general-purpose compressors. This perspective yields findings about cross-modal compression, scaling, tokenization, and context limitations.

Compression and prediction: Predictive models and lossless compressors are equivalent: maximizing log2-likelihood minimizes expected coding length.The connection can be implemented with Huffman coding, arithmetic coding, or asymmetric numeral systems.
Compression and prediction: Arithmetic coding is optimal in coding length, so compression performance depends on the probabilistic model’s predictive capabilities.The model iteratively assigns probability-conditioned intervals to observed symbols and emits a binary code contained within the final interval.
Empirical evaluation: Foundation models achieve competitive compression rates across modalities, including data distributions on which they were not trained.The evaluation compares large language models with standard domain-specific compressors while disregarding model parameter size for raw rates.
Empirical evaluation: 43.4% on ImageNet patches and 16.4% on LibriSpeech samples are achieved by Chinchilla 70B, versus 58.5% for PNG and 30.3% for FLAC, respectively.These results demonstrate cross-modal compression performance from a model trained primarily on text.
Scaling and representation: Dataset size imposes a hard limit on compression performance, so increasing model size is not universally beneficial once parameter storage is included.The paper argues that adjusted compression rates can deteriorate beyond a certain model size because model parameters must be included in the compressed output.
Scaling and representation: Tokenization generally does not improve compression, but it increases context information and can improve prediction performance.Increasing alphabet size shortens sequences while making conditional prediction more difficult.

2 BACKGROUND

This section develops the equivalence between probabilistic prediction and lossless compression, introducing coding distributions, arithmetic coding, and likelihood-based training objectives. It also shows that compressors can define predictors and that optimal compression corresponds to optimal prediction.

Coding Distributions: A coding distribution assigns consistent probabilities to finite sequences, with conditional probabilities obtained by dividing sequence probabilities over prefixes.The chain rule recovers sequence probabilities from successive conditional probabilities.
Lossless Compression: Lossless compression encodes recoverable symbol streams into binary codewords while minimizing expected bit length.Rare sequences receive more bits and frequent sequences fewer bits under the coding distribution.
Arithmetic Coding: Arithmetic coding has near-optimal length, so compression quality depends on the predictive model’s log-loss performance.With infinite precision, the code length is −⌈log ρ(x1:n)⌉+ 1 bits versus optimal length −log ρ(x1:n) bits; finite precision adds O(n2^-B) bits.
Arithmetic Coding: Arithmetic coding narrows a probability-weighted interval for each successive symbol and selects a binary representation from the final interval for decoding.At each step, the interval for a symbol has size proportional to its conditional probability, and decoding identifies the sub-interval containing the code value.
Likelihood Maximization: Replacing the unknown source distribution with a model ˆρ makes expected code length equal to cross-entropy, whose minimization is equivalent to likelihood maximization.The same log-loss objective used to train foundation models therefore minimizes the compression rate of arithmetic coding.
Compression-Based Sequence Prediction: Any compressor can define a coding distribution and conditional predictor, while optimal compression is theoretically equivalent to optimal prediction.For compressor c, the conditional distribution is computed from the difference between compressed prefix lengths; Solomonoff prediction gives the corresponding universal theoretical result.

3 EXPERIMENTAL EVALUATION

The evaluation compares arithmetic-coding language-model compressors with general-purpose and domain-specific compressors across text, image, and audio data. It examines generalization across modalities, model-size/data-size tradeoffs, compressor-based generation, context length, and tokenization.

Comparing Compression Rates: The study evaluates foundation-model compression against gzip, LZMA2, PNG, and FLAC across equally sized text, image, and audio datasets.Language models are used with arithmetic coding, while the datasets are each 1 GB to make cross-modal results comparable.
Comparing Compression Rates: Adjusted compression rates worsen substantially for foundation models because billions of parameters add hundreds of gigabytes to the compressed size on 1 GB datasets.Non-trivial adjusted rates would require datasets on the order of terabytes or more.
Comparing Compression Rates: Large language models outperform other compressors across modalities, whereas Transformers trained on enwik8 primarily compress similar Wikipedia data well.The pretrained models were trained mainly on text yet achieve strong compression on image and audio data through in-context learning.
Optimal Model-Dataset Size Tradeoff: Larger Transformers compress larger datasets better but smaller datasets worse, because parameter costs eventually outweigh compression gains.Each dataset therefore has a critical model size after which the adjusted compression rate increases.
Compressors as Generative Models: Compressors can generate continuations by converting compressed-sequence lengths into conditional probabilities and sampling autoregressively.In image experiments, Chinchilla 70B produces less noisy but still degrading continuations than gzip, while accumulated errors limit sample quality.
In-Context Compression and Tokenization: Longer contexts generally improve in-context compression, while tokenization creates a tradeoff between shorter sequences and harder predictions.Larger vocabularies help small models in practice but can harm the final compression rate of bigger models.

4 RELATED WORK

Prior work connects predictive modeling with lossless compression, including arithmetic-coding approaches using Markov models and neural predictive distributions. Research also studies tokenization and other inductive biases affecting compression and language modeling.

Context-tree weighting and prediction by partial matching combine predictive modeling with arithmetic coding for lossless compression.
Predictive distributions from neural networks can be used for lossless compression through arithmetic coding.
Tokenization research has developed alternatives to byte-pair encoding, including methods designed to improve NLP tokenization.

5 CONCLUSION

The paper studies sequence modeling through its equivalence with lossless compression and evaluates large language models as compressors across text, image, and audio modalities. The compression perspective also links optimal model size to dataset size.

Arithmetic coding transforms a sequence model into a compressor, while coding lengths can transform a compressor into a predictor.
Large language models achieve competitive compression rates on text, image, and audio data, including modalities absent from their training.
The compression view incorporates model size into scaling-law analysis and links optimal model size to dataset size.

A ARITHMETIC CODING

Arithmetic encoding iteratively narrows an interval according to a predictive model and the input sequence, then represents the final interval with a binary code. In the example, AIXI is encoded in 7 bits instead of 4 bytes.

Arithmetic encoding partitions I = [0, 1) iteratively according to predictive probabilities and the input string.
After the first token A, the interval becomes I = [0, 0.45), after which conditional intervals are constructed.
For P(I|A) = 0.3, the conditional interval is [0.09, 0.36), while P(X|A) = 0.2 maps to [0.36, 0.45).
The sequence AIXI terminates with I = [0.322, 0341), which is then represented by repeatedly halving [0, 1) until a subinterval lies inside it.
7 bits encode AIXI, compared with the 4 bytes required by its original encoding.

B.1 DATA MANIPULATION

The experiments convert inputs into model-compatible byte sequences before compression. Text is mapped to ASCII, images are flattened grayscale patches with shifted bytes, and sound is reduced to one-byte samples in 2048-byte chunks.

Text bytes are mapped into the ASCII range [0, 127], with each processed character’s lost bit accounted for in the compressed sequence.
Special text characters have their most significant bit zeroed, and the lost bit is appended to the compressed byte sequence.
Image patches contain 2048 grayscale bytes after flattening a (32, 64) patch, which loses some two-dimensional pixel correlation.
Image bytes are divided by 2 through byte shifting, with the least significant bits appended to the compressed sequence.
LibriSpeech samples are reduced from 2-byte int16 values to 1 byte and split into 2048-byte chunks representing roughly 64 milliseconds of speech.

B.2 LARGE LANGUAGE MODELS TOKENIZATION

Large language models tokenize fixed-length ASCII inputs into variable-length token sequences, then use token-level conditional probabilities with arithmetic coding to produce compressed bitstreams. The pretrained models use SentencePiece tokenization, while the enwik-trained Transformers generally do not.

B.2 LARGE LANGUAGE MODELS TOKENIZATION: 2048 ASCII characters are converted by SentencePiece into a variable-length sequence of integer tokens before modeling.Both Chinchilla and Llama2 use a vocabulary size T = 32000.
B.2 LARGE LANGUAGE MODELS TOKENIZATION: Tokenization is itself lossless compression because it changes the input representation without losing information.
B.2 LARGE LANGUAGE MODELS TOKENIZATION: The Transformer produces token conditional log-probabilities, which an arithmetic encoder converts into the final compressed bitstream.The compressed size is compared with the original 2048-byte input.
B.2 LARGE LANGUAGE MODELS TOKENIZATION: With only top-k predictions available, k = 100 is renormalized so the probabilities sum to 1 before arithmetic coding.Arithmetic coding remains applicable even when the alphabet size changes during coding.
B.2 LARGE LANGUAGE MODELS TOKENIZATION: The enwik-trained Transformers do not use tokenization except in Section 3.6 and return the full token distribution.

C ADDITIONAL RESULTS

The additional results illustrate compression-based autoregressive generation for text, images, and audio. Chinchilla produces more coherent text than gzip, while image generation compares models of different sizes and audio samples show a characteristic loop pattern.

C ADDITIONAL RESULTS: Chinchilla generation proceeds by producing tokens until the desired byte length is reached, whereas gzip samples are biased by its one-step-ahead setup.Looking multiple steps ahead might improve gzip samples, but the paper retains the simplest setup for all compressors.
C ADDITIONAL RESULTS: Text generation conditions gzip and Chinchilla on 1948 bytes, then autoregressively samples 100 bytes or N tokens.Because Chinchilla uses a tokenizer, N tokens do not necessarily decode to 100 bytes.
C ADDITIONAL RESULTS: Chinchilla’s generated text is significantly more coherent than gzip’s under this compression-based sampling setup.
C ADDITIONAL RESULTS: Image generation compares three Chinchilla models with different parameter counts by conditioning on 250 bytes and sampling the remaining 250 bytes of each row.
C ADDITIONAL RESULTS: Audio generation conditions gzip and Chinchilla on the first 1024 bytes, then autoregressively samples the remaining 1024 bytes.Chinchilla predictions exhibit a typical loop pattern of autoregressive generation.