gzip as a Language Model: How DEFLATE Can Generate Text

gzip can act as a language model, but only in a limited, noisy way

Takeaway: By treating the compressed size of a candidate continuation as a proxy for its probability, the DEFLATE algorithm behind gzip can generate text through beam search, demonstrating the compression‑prediction equivalence, though the output remains far less coherent than neural language models.

Compression is prediction

Every compressor implicitly defines a probability distribution.

Information theory tells us that the optimal code length for a symbol is (-\log_2 p), where (p) is the model's assigned probability. A compressor that spends few bits on a symbol therefore assumes a high probability for it. gzip uses the DEFLATE algorithm, which maintains a 32 KiB sliding window and replaces repeated byte sequences with back‑references. When a continuation echoes recent bytes, DEFLATE encodes it with almost no extra bits, meaning the compressor “expected” that continuation.

Scoring rule:

score(candidate) = len(gzip(context + candidate))

A smaller compressed length indicates a higher predicted probability. By priming the compressor with a large corpus (e.g., tiny Shakespeare), any continuation that resembles the corpus will achieve a low score.

Generating text with beam search

A naïve greedy approach—picking the next byte that yields the smallest compressed length—fails because gzip reports only integer byte lengths. Adding a single byte often leaves the compressed size unchanged, causing massive ties and noisy gradients.

Beam search solution:

  1. Prompt – The user‑provided prompt is concatenated to the corpus window and treated as part of the initial context.
  2. Context – For each search step, gzip sees corpus_window + recent_tail, where recent_tail is the last tail bytes of generated output.
  3. Expand – Each beam candidate is extended by every byte that appears in the corpus. All extensions are scored with the compression length rule.
  4. Prune – Keep only the top beam_width candidates (the most compressible). Repeat for a fixed horizon of bytes.
  5. Commit – Output the best full span (or sample proportionally to a temperature parameter) and slide the window forward.

Limiting the context to the most recent tail bytes prevents the model from falling into trivial loops that simply copy its own recent output, because DEFLATE gives cheaper codes to nearer matches.

What the generated output looks like

Running the tool gzipt on the tiny Shakespeare corpus with the prompt "MENENIUS:\n" produces:

MENENIUS:
'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 .

The text is not fluent Shakespeare, but it clearly reuses fragments and punctuation patterns from the source, confirming that gzip’s compression model captures some statistical regularities of the corpus.

How other compressors behave

The author also experimented with bzip2 and Zstandard (zstd):

  • bzip2 – Generates long runs of alternating symbols (e.g., xyxyxy…). This reflects its reliance on the Burrows‑Wheeler Transform, which favors highly repetitive patterns rather than meaningful language.
  • zstd – Produces mostly whitespace with occasional letters, because its run‑length encoding makes a single repeated byte cheap, while space and newline are the cheapest literals in the Shakespeare corpus.

These results illustrate that the nature of the underlying compression algorithm strongly influences the style of generated text.

Community insights

"You can classify a test file by topic with gzip as follows: gzip -9 sports.txt testfile.txt … The test file belongs to the topic with the smallest size .gz file." – jll29 (HN)

"The space of possible sequences is many orders of magnitude larger than what was searched. So the result only gives a lower bound of how well gzip works as a ‘plausibility tester’ of a continuation." – mg (HN)

"I was curious to see how this would work with bzip2 and zstd… bzip2 produces sequences that don’t resemble human language; zstd encodes a run of one repeated byte as a near‑free run‑length sequence, and space and newline are the cheapest literals." – networked (author comment)

These comments reinforce two points: (1) compression‑based classification is a known technique, and (2) the beam‑search approach dramatically improves over naïve greedy search, but the search space remains astronomically large, so the method provides only a heuristic estimate of gzip’s predictive power.

Limitations and open questions

  • Coherence – The output lacks the long‑range semantic consistency of neural language models. DEFLATE only looks back 32 KiB, so it cannot capture plot or character arcs.
  • Search quality – Beam search is still a heuristic; there is no guarantee that the globally optimal (most compressible) continuation is found.
  • Speed vs. expressiveness – gzip scales linearly with input size and runs orders of magnitude faster than modern LLMs, but this speed comes at the cost of expressive power.
  • Comparison to LLMs as compressors – Some commenters wonder how well a large language model would compress text compared to gzip, highlighting a complementary research direction.

Why this matters

The experiment provides a concrete demonstration of the compression‑prediction equivalence theorem: any lossless compressor can be repurposed as a predictor, and vice versa. While gzip’s predictive ability is rudimentary, the approach opens avenues for exploring non‑neural language models, benchmarking compression algorithms as proxies for probability estimation, and revisiting classic algorithms in the era of large‑scale AI.

Sources

Related