Can gzip be a language model?
- Compression as Prediction:
- Grounded in information theory, the minimum bits needed to encode a symbol is \(log_2(p)\); high-probability symbols require fewer bits, meaning any effective compression algorithm inherently embodies a predictive model.
- Deep learning papers such as Language Modeling is Compression highlight the formal equivalence between compressors and next-token prediction models.
- Scoring Mechanism with DEFLATE:
- gzip utilizes the DEFLATE algorithm, which searches for repeated byte sequences in a 32 KiB sliding window and encodes matches as cheap back-references.
- By concatenating a reference corpus into the context window, candidate text continuations that closely resemble the corpus compress to smaller byte sizes, yielding the scoring metric:
score(candidate) = len(gzip(context + candidate)).
- Greedy Generation Failure & Beam Search Solution:
- Naive greedy next-byte selection fails due to quantization noise, as gzip reports lengths in discrete integer bytes, causing frequent ties among single-byte candidates.
- To circumvent this, the implementation ("GziPT") employs beam search over multi-byte sequence horizons, evaluating candidate branches across lookahead spans before committing.
- Preventing Repetition Loops:
- DEFLATE encodes nearby matches more compactly than distant matches.
- To prevent the model from degenerating into verbatim repetitive loops, only a recent tail of previously generated tokens is retained alongside the priming corpus in the scoring window.
- Implementation:
- The proof-of-concept runs in standard Python using only the built-in
zliblibrary, generating recognizable, pseudo-Shakespearean text purely through compression metrics without neural network weights.
- The proof-of-concept runs in standard Python using only the built-in
Hacker News Discussion
- Prior Art in Compression-Based Classification:
- Multiple commenters noted that using gzip as a classifier is an established technique (dating back to Ian Witten's research group at the University of Waikato and early 2000s language-detection systems).
- Practical applications often classify documents by appending a sample to pre-existing category corpora and selecting the domain yielding the smallest compressed archive.
- Methodological Nuances & Metrics:
- Users referenced formal theoretical frameworks like Normalized Compression Distance (NCD), Normalized Google Distance (NGD), and the Hutter Prize.
- Several commenters highlighted a methodological detail: naive concatenation must subtract the compressed baseline size of the reference text to avoid distortion caused by varying corpus compressibility.
- Information Theory Foundations:
- Readers recommended David MacKay’s classic textbook Information Theory, Inference, and Learning Algorithms as well as 3Blue1Brown video essays exploring entropy, cryptography, and prediction.
- Modern Compressor Comparisons:
- The discussion expanded to algorithm performance, comparing DEFLATE's 32 KiB window limitations against modern alternatives like zstd and LZMA/7-Zip, which offer significantly larger context windows and higher compression ratios.
- Participants also shared anecdotes regarding WinRAR's enduring enterprise profitability and file recovery record capabilities.