Exploring Gzip as a Language Model Alternative
Can compression algorithms generate coherent text?
1Compression as prediction
The paper 'Language Modeling is Compression' establishes a fundamental equivalence: all compression algorithms are prediction models, and vice versa. This insight suggests that tools like gzip, designed for data compression, might inherently perform language modeling by assigning probabilities to byte sequences. The core principle is that compressors spend fewer bytes on expected data and more on surprises, mirroring how language models assign probabilities.
2Gzip's hidden probability model
Gzip uses DEFLATE algorithm which compresses by finding matches in a 32KB sliding window. When a continuation echoes text in this window, it encodes it as a cheap back-reference. This mechanism implicitly creates a probability model where frequently seen patterns require fewer bits to encode (-log₂p), exactly like a language model's probability distribution over tokens. The compressor's behavior reveals its hidden expectations about the data.
3Experimental setup
The author primed gzip with Shakespeare's text and tested its generation capability. The system scores candidate continuations by measuring compressed length - shorter compression indicates better prediction. While the output wasn't fully coherent ('MENENIUS: Though all at once canq...'), it showed surprising structural knowledge of the text format, demonstrating that compression does capture some linguistic patterns.
4Beam search improvement
The naive approach of picking single best-compressing bytes failed due to quantization noise in gzip's integer byte lengths. Implementing beam search over byte sequences significantly improved results by evaluating multi-byte spans before committing. This maintains multiple candidate paths, similar to how neural LMs avoid greedy decoding pitfalls. The paper notes this was crucial for meaningful generation.
5Context window constraints
Only the last tail bytes of generated output stay in the scoring context. This prevents verbatim loops that would occur if gzip could see its entire history, as DEFLATE codes nearby matches more cheaply. The 32KB window forces the model to focus on recent patterns rather than endlessly recycling old text, creating more varied output.
6Implementation details
The experiment used pure Python's zlib (gzip's underlying library) without neural networks. The system compresses context+candidate to score continuations. While performance trails neural models, the approach demonstrates that sophisticated architectures aren't strictly necessary for basic language modeling. The code is available on GitHub for experimentation.
7Theoretical implications
This exploration validates the compression-prediction equivalence theorem practically. It shows that any system making data compact (like gzip) must be modeling its structure, whether designed as a language model or not. The results suggest that compression ratio could serve as an unsupervised metric for evaluating generative models.
8Practical limitations
While gzip shows some language modeling capability, its 32KB window and lack of learned parameters limit coherence compared to neural models. The approach works best for local patterns rather than long-range structure. However, it provides a fascinating baseline for understanding what minimal components are needed for generation.