Can gzip be a language model?

The author set out to answer a question that sounds absurd at first: can gzip — the very compressor already installed on your system — act as a language model? No neural network, no learned weights, just compression. The spark was the paper "Language Modeling is Compression" and its central claim: every prediction model is inherently a compressor, and every compression algorithm is a prediction model.

Compression is prediction

The logic is simple. A compressor spends few bytes on what it "expects" and many on what it doesn't. A million repeated A's fits in one sentence; a million random bytes barely compress at all. This is not a coincidence but the core of information theory: the number of bits to encode a symbol is \(-\log_2 p\), where \(p\) is the probability the model assigns it. So a probability model already hides inside any compressor, whether or not anyone wrote it down.

gzip uses DEFLATE, which finds matches against recent text in a 32 KiB sliding window. If a continuation echoes something already in the window, it is encoded as a cheap back-reference instead of literal bytes. That gives a score for any candidate: the length of the compressed context + candidate. The smaller the result, the more "predicted" the continuation. Prime the window with a corpus, and anything resembling it compresses small.

Generating by beam search

Scoring is one thing; generating is another. Naively picking the single best next byte fails, because gzip only reports an integer byte length — no fractions. Adding one byte often doesn't change the length at all, so the signal drowns in quantization noise. The fix is to look ahead a whole span. The gzipt program runs a beam search over byte sequences, extending the most compressible partial continuations and pruning the rest.

One detail matters: only the tail of the already-generated text stays in the scoring context. DEFLATE codes nearby matches more cheaply than far ones, so if gzip could see its full history, the cheapest move would be to copy verbatim what it just emitted — the model falls into loops.

The output produced after priming on tiny Shakespeare is not coherent prose, yet it clearly knows something about the source — far more than the author expected from an archiver. The original paper tried the idea too but performed poorly; adding beam search markedly improved generation. The whole thing is one file of pure standard-library Python (just zlib), and the name GziPT, the author admits, was simply too good to pass up.

Source: Hacker News