But, I'm skeptical of using compressors directly for ML/AI/etc. (yes, compression and intelligence are very closely related, but practical compressors and practical classifiers have different goals and different practical constraints).

Back in 2023, I wrote two blog-posts [0,1] that refused the results in the 2023 paper referenced here (bad implementation and bad data).

[0] https://kenschutte.com/gzip-knn-paper/

[1] https://kenschutte.com/gzip-knn-paper2/

(KL divergence of letter frequencies is the same thing as ratio of lengths of their Huffman-compressed bitstreams, but you don't need to do all this bit-twiddling for real just to count the letters)

The article views compression entirely through Python's limitations.

> gzip and LZW don’t support incremental compression

This may be true in the Python's APIs, but is not true about these algorithms in general.

They absolutely support incremental compression even in APIs of popular lower-level libraries.

Snapshotting/rewinding of the state isn't exposed usually (custom gzip dictionary is close enough in practice, but a dedicated API would reuse its internal caches). Algorithmically it is possible, and quite frequently used by the compressors themselves: Zopfli tries lots of what-if scenarios in a loop. Good LZW compression requires rewinding to a smaller symbol size and restarting compression from there after you notice the dictionary stopped being helpful. The bitstream has a dedicated code for this, so this isn't just possible, but baked into the design.

Compression algorithms may have been supporting incremental compression for a while. But as some have pointed out, the point of the post is that it is practical and simple to have this available in Python's standard library. You could indeed do this in Bash, but then people don't do machine learning in Bash.

I think it makes sense to explore it from practical standpoint, too. It’s in Python stdlib, and works reasonably well, so for some applications it might be good enough.

It’s also fairly easy to implement in other languages with zstd bindings, or even shell scripts:

  $ echo 'taco burrito tortilla salsa guacamole cilantro lime' > /tmp/tacos.txt
  $ zstd --train $(yes '/tmp/tacos.txt' | head -n 50) -o tacos.dict
  [...snip]

  $ echo 'racket court serve volley smash lob match game set' > /tmp/padel.txt
  $ zstd --train $(yes '/tmp/padel.txt' | head -n 50) -o padel.dict
  [...snip]

  $ echo 'I ordered three tacos with extra guacamole' | zstd -D tacos.dict | wc -c
        57
  $ echo 'I ordered three tacos with extra guacamole' | zstd -D padel.dict | wc -c
        60

  import zlib

  input_text = b"I ordered three tacos with extra guacamole"

  tacos = b"taco burrito tortilla salsa guacamole cilantro lime " * 50
  taco_comp = zlib.compressobj(zdict=tacos)
  print(len(taco_comp.compress(input_text) + taco_comp.flush()))
  # prints 41

  padel = b"racket court serve volley smash lob match game set " * 50
  padel_comp = zlib.compressobj(zdict=padel)
  print(len(padel_comp.compress(input_text) +  padel_comp.flush()))
  # prints 54

zdict was added in Python 3.3, though, so it’s 2012, not 1997. (It might have worked before, just not a part of the official API :-)

Another way I've used image compression to identify cops that cover their body cameras while recording -- the filesize to length ratio reflects not much activity going on.

¹ https://matthodges.com/posts/2023-10-01-BIDEN-binary-inferen...

The author sets the solver to saga, doesn’t standardize the features, and uses a very high max_iter.

Logistic Regression takes longer to converge when features are not standardized.

Also, the zstd classifier time complexity scales linearly with the number of classes, logistic regression doesn’t. You have 20 (it’s in the name of the dataset), so why only use 4.

It’s a cool exploration of zstd. But please give the baseline some love. Not everything has to be better than something to be interesting.

Why should the baseline get "love"? The whole point is exploring a novel approach. If someone wants a perfectly tuned sklearn benchmark they can run it themselves in 5 minutes. The linear scaling critique is fair but doesn't invalidate showing that compression-based classification actually works here. Sometimes "good enough" beats "optimal" when the implementation is trivial.

The relationship between probabilistic modeling and lossless compression is very direct. A model that predicts the next symbol with probability p can on average losslessly compress that symbol with the help of an entropy coder (e.g. arithmetic coding) in -log(p) bits. Therefore improved probabilistic models immediately translate into improved lossless compressors.

There are two ways people have used compressors for ML: the first is based on the Minimum Description Length (MDL) principle [0] which says that the best model is the one which provides the shortest description of the data, counting the size of the model itself. This is similar to the technique used in this blog post (argmin code length across class-conditioned compressors) except for counting the model size. Basically you can train a compressor per class and then choose the class compressor which best compresses the test data. It is a maximum likelihood argument because of Shannon's source coding theorem: a code length L corresponds to a probability 2^-L. The second way is the Normalized Compression Distance (NCD) [1], which uses code lengths to calculate information-theoretic distances which can then be plugged into distance-based algorithms like kNN. MDL interprets compressed lengths as likelihoods, while NCD interprets them for distance calculations. The theoretical foundation is Kolmogorov complexity which is the ideal (& uncomputable) lossless compressor, used to define information distance, an "ideal" distance metric based on algorithmic similarity.

Data compression is not in principle restricted to syntactic similarity. As others have mentioned, the new wave of neural compressors (e.g. NNCP [2], CMIX [3], leading the large text compression benchmark [4]) outperform their traditional counterparts (e.g. gzip) because of the ability of neural networks to learn complex semantic patterns. Their improved ability to predict the next token means improved lossless compression. This has also been shown to be the case with pre-trained LLMs [5].

I think it's neat that improving compression improves machine learning, and improving machine learning improves compression!

Looking forward to hearing other thoughts.

[0] https://arxiv.org/abs/math/0406077 [1] https://arxiv.org/abs/cs/0111054 [2] https://bellard.org/nncp/nncp_v2.pdf [3] https://www.byronknoll.com/cmix.html [4] https://www.mattmahoney.net/dc/text.html [5] https://arxiv.org/abs/2309.10668

https://en.wikipedia.org/wiki/Normalized_Google_distance

It goes the other way too. Given that LLMs are just lossless compression machines, I do sometimes wonder how much better they are at compressing plain text compared to zstd or similar. Should be easy to calculate...

EDIT: lossless when they're used as the probability estimator and paired with something like an arithmetic coder.

The current leader on the Hutter Prize (http://prize.hutter1.net/) are all LLM based.

It can (slowly!!) compress a 1GB dump of Wikipedia to 106Mb

By comparison GZip can compress it to 321Mb

See https://mattmahoney.net/dc/text.html for the current leaderboard

It outperforms zstd by a long shot (I haven't dedicated the compute horsepower to figuring out what "a long shot" means quantitatively with reasonably small confidence intervals) on natural language, like wikipedia articles or markdown documents, but (using GPT-2) it's about as good as zstd or worse than zstd on things like files in the Kubernetes source repository.

You already get a significant amount of compression just out of the tokenization in some cases ("The quick red fox jumps over the lazy brown dog." encodes to one token per word plus one token for the '.' for the GPT-2 tokenizer), where as with code a lot of your tokens will just represent a single character so the entropy coding is doing all the work, which means your compression is only as good as the accuracy of your LLM, plus the efficiency of your entropy coding.

I would need to be encoding multiple tokens per "word" with Huffman Coding to hit the entropy bounds, since it has a minimum of one bit per character, so if tokens are mostly just one byte then I can't do better than a 12.5% compression ratio with one token per word. And doing otherwise gets computationally infeasible very fast. Arithmetic coding would do much better especially on code because it can encode a word with fractional bits.

I used Huffman coding for my first attempt because it's easier to implement and most libraries don't support dynamically updating the distribution throughout the process.

For example I would not want a zip of an encyclopedia that uncompresses to unverified, approximate and sometimes even wrong text. According to this site : https://www.wikiwand.com/en/articles/Size%20of%20Wikipedia a compressed Wikipedia without medias, just text is ~24GB. What's the medium size of an LLM, 10 GB ? 50 GB ? 100 GB ? Even if it's less, it's not an accurate and deterministic way to compress text.

Yeah, pretty easy to calculate...

With the usual interface it’s probably inefficient: giving just a prompt alone might not produce the output we need, or it might be larger than the thing we’re trying to compress. However, if we also steer the decisions along the way, we can probably give a small prompt that gets the LLM going, and tweak its decision process to get the tokens we want. We can then store those changes alongside the prompt. (This is a very hand-wavy concept, I know.)

So yes, LLMs are nearly ideal text compressors, except for all the practical inconveniences of their size and speed (they can be reliably deterministic if you sacrifice parallel execution and some optimizations).

Edit to soften a claim I didn't mean to make.

I've been playing with this exact comparison lately! You're right that LLMs are lossy by default, but the compression ratio gets pretty wild when you use them for arithmetic coding like the article describes. I tested GPT-2 on some technical docs and got ~3x better than zstd, though inference time makes it impractical for real use. The lossless trick with diffs is clever but kind of defeats the purpose.

Before 3.14, doing this required pip installing pyzstd or python-zstandard, which meant an extra dependency and a C extension build step. Having zstd in the stdlib means you can do dictionary-based compression tricks in any Python 3.14 environment without worrying about whether the deployment target has build tools or whether the package version matches across your team.

That matters more than it sounds for reproducibility. The gzip/zlib approach kenschutte mentions has been in stdlib forever, but zstd dictionaries are meaningfully better at learning domain-specific patterns from small training corpora. The difference between 41 and 54 bytes in the taco example is small, but on real classification tasks with thousands of categories the gap compounds.

Python 3.14 quietly shipped a lot of practical stuff like this that gets overshadowed by the free-threading and JIT headlines. The ZSTD module, t-strings for template injection safety, and deferred annotation evaluation are all things that change how you write everyday code, not just how the runtime performs.

Who exactly is training these classifiers, and on whose data? If compression ratios reveal patterns in text, they also reveal patterns in people. Are we comfortable with that being deployed without oversight in content moderation, surveillance systems, or hiring algorithms?