Can gzip be a language model?nathan.rsWriting
X
Github
LinkedIn
☾Can gzip be a language model?Nathan Barry
June 14, 2026IntroductionCompression is predictionGenerating by beam searchA while back I wrote about language modeling without neural networks, where I generated Shakespeare with an unbounded n-gram model: no weights, no training, just counting. Fortuitously, I came across the paper Language Modeling is Compression, which mentioned the compression–prediction equivalence:every prediction model is inherently a compressor, and all compression algorithms are prediction models.This led to the natural question: can gzip do language modeling?1
No neural network, no learned parameters, nothing. Just the compressor that ships with your operating system. You prime it with a corpus, give it a normal text prompt, and it continues that prompt by searching for the byte sequences that compress best. Here’s some real, unedited output after priming it on tiny Shakespeare:gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:\n' --length 200MENENIUS:
'Though all at once canq

MARCIUS:
Pray now, nocamest thou to a morsel .

LARTIUS:
Hence, and
I' the end admire, where G
again; and after it ag .It turns out, kind of? It’s not exactly coherent text, but it clearly knows something about the text. Much more than I expected gzip to know.2 So how can a compressor generate this?Compression is prediction#Think about what a compressor does. It spends few bytes on data it “expects” and many bytes on data it doesn’t. If I hand you a file that’s the letter A repeated a million times, you can describe it in one sentence. A million random bytes, on the other hand, have no structure to exploit and barely compress at all.This is not a coincidence; it’s the core of information theory. The number of bits needed to encode a symbol is $-\log_2 p$, where $p$ is the probability the model assigns to it. High probability means few bits. So any compressor has a probability model hiding inside it, whether or not anyone wrote one down.gzip uses DEFLATE, which compresses the next bytes by finding matches against the recent text in a 32 KiB sliding window. If a continuation echoes something already in the window, DEFLATE encodes it as a cheap back-reference instead of literal bytes. So:A continuation that gzip “expected”, because it echoes text already in its window, compresses to almost nothing.That gives us a score. If I have some context and I want to know how good a candidate continuation is, I just measure:$$\text{score}(\text{candidate}) = \texttt{len(gzip(context + candidate))}$$The smaller the compressed length, the more “predicted” the candidate is. To prime the model, I include a corpus in gzip’s window. Any continuation that looks like the corpus compresses small, and any continuation that doesn’t compresses large.Generating by beam search#Scoring is one thing; generating is another. The naive approach of picking the single next byte that compresses best fails badly, and for a subtle reason: gzip only gives an integer byte length (no fractions). Adding one byte often doesn’t change the compressed length at all, so many candidates tie and the signal is buried in quantization noise.The fix is to look ahead a whole span before committing. gzipt runs a beam search over byte sequences. At each step, the current context is:corpus window + recent tail of (prompt + generated bytes)Then gzipt tries possible next bytes. Each candidate continuation is scored by compressing context + candidate and checking how many bytes the compressed result takes.The loop is:Prompt. Start with the user’s prompt as the initial text to continue. There is no start token; the prompt bytes are just part of the context gzip sees.Context. Show gzip the corpus window plus the recent tail of the prompt/generated text.Search. Keep the beam_width most-compressible partial continuations. Extend each by every byte that occurs in the corpus, score all of them by compressed length, and prune back down to the best beam_width. Repeat for horizon bytes.Commit. Take the most-compressible full span (or sample among the finalists if temperature is positive), append it, and start the loop over.One detail that matters is that only the last tail bytes of generated output stay in the scoring context. DEFLATE codes nearby matches more cheaply than far ones, so if gzip could see its entire history, the cheapest thing to do is often to fall into verbatim loops, repeatedly copying text it just emitted.You can see the decoding and scoring process in the animation above, which is the same replay shown at the top. The whole thing is one file of pure standard-library Python (just zlib). Code’s on GitHub if you want to play with it.The paper did try this, but it ended up performing poorly. Adding beam search significantly improved generation quality (an idea they mentioned), which is discussed below. ↩︎The code actually uses zlib instead of spawning a gzip process, but the name GziPT was too good. I believe they both use the same DEFLATE algorithm under the hood. ↩︎
Last modified: July 3, 2026nathan.rs - © 2025 Nathan Barry

The inquiry into whether gzip can function as a language model stems from the core concept of the compression-prediction equivalence, which posits that every prediction model is inherently a compressor and all compression algorithms are prediction models. This equivalence bridges language modeling, which can be achieved without neural networks using methods like n-gram models based on counting, and compression, which deals with encoding data based on expected sequences. The text explores how this relationship applies to gzip, which operates based on prediction inherent in information theory, where the required bits to encode a symbol depend on the probability the model assigns to it, specifically related to $-\log_2 p$.

Gzip achieves compression by utilizing the DEFLATE algorithm, which operates by finding matches against recent text within a sliding window, typically 32 KiB. When text exhibits repetition, DEFLATE encodes the continuation as a cheap back-reference rather than literal bytes, reflecting an expectation derived from the context. This mechanism demonstrates that a compressor implicitly contains a probability model of the data. The quality of a potential continuation can thus be scored by measuring the resulting compressed length of the combined context and candidate text; a smaller compressed size indicates a better prediction of the continuation.

To move from scoring candidates to actual generation, the naive approach of selecting the single next byte that yields the best compression fails due to quantization noise, as adding a single byte often does not change the compressed length, leading to ambiguous results. The text proposes using a beam search strategy to address this by looking ahead over an entire span of byte sequences before making a commitment. The generation process involves setting the context to include the corpus window and the recent tail of the prompt and generated text. The beam search iteratively searches across possible next bytes, scoring each candidate continuation by compressing the combined context and candidate, and then pruning the search space to retain only the most compressible sequences at each step. This process continues for a predefined horizon of bytes, ensuring that the context window is used effectively to guide the creation of more coherent sequences.

The observed generation quality in the original work that explored this connection was significantly improved by the incorporation of beam search, suggesting that this search mechanism is crucial for leveraging the predictive information embedded within the compression process effectively. The underlying principle is that the mechanism used for compression is fundamentally a predictive mechanism, providing a basis for linking the principles of information compression directly to the generation of textual sequences.