Can gzip be a language model?
4 hours ago
- Language modeling can be done without neural networks using compression algorithms like gzip, based on the compression-prediction equivalence.
- Compression works by assigning fewer bits to expected data, which embeds a probability model within any compressor.
- gzip uses DEFLATE, which compresses by finding matches in a 32 KiB sliding window, allowing it to score candidate continuations by compressed length.
- Naive byte-by-byte generation fails due to quantization noise, so beam search over byte sequences is used to look ahead before committing.
- The generation process involves priming gzip with a corpus, scoring candidate continuations by compressed length, and using beam search to select the best span.
- Only the recent tail of generated output is kept in the scoring context to prevent verbatim loops from exploiting nearby matches.
- The implementation is pure Python using zlib, and adding beam search significantly improves generation quality compared to the original paper's method.