Live data from Hacker News

Data Compression Explained (2012)

mattmahoney.net

21–30 of 38 posts

Re: Data Compression Explained (2012)

#21
post #11

Earlier quoted context omitted.

No, LLMs only do this for language. They don't try to do this for arbitrary data.

Transformers do this for any stream of tokens, those tokens can map to anything you want, and you will get lossy compression. Text produced by humans just happens to be dense, available, and a useful prior, but it is not intrinsically required. See 3D vision transformers for example.

It is not possible to compress arbitrary data. If the data is already compressed, or it is encrypted, or it is randomly generated, it cannot be compressed with any method. This is foundational information theory.

https://en.wikipedia.org/wiki/Lossless_compression#Limitatio...

Re: Data Compression Explained (2012)

#26

Earlier quoted context omitted.

Transformers do this for any stream of tokens, those tokens can map to anything you want, and you will get lossy compression. Text produced by humans just happens to be dense, available, and a useful prior, but it is not intrinsically required. See 3D vision transformers for example.

It is not possible to compress arbitrary data. If the data is already compressed, or it is encrypted, or it is randomly generated, it cannot be compressed with any method. This is foundational information theory. https://en.wikipedia.org/wiki/Lossless_compression#Limitatio...

Whereas if we're talking about lossy compression (as is the person to whom you replied) we certainly can compress arbitrary data - almost as much as we want.

The hard question, then, is how much the decompressed output looks like the original.

Re: Data Compression Explained (2012)

#29

does anyone have any sources to read about ai-based compression? I remember hearing a lot about "compression is a lot about prediction", but I don't remember reading any practical result

compression = prediction + entropy coding was already an insight from Claude Shannon in the 1950s

Since LLM are inherently token predictors, that makes using them for losless compression almost trivial. For something close to the state of the art see e.g. Fabrice Bellard (of course) ts_zip: https://bellard.org/ts_zip/

I think some of the confusion comes from the fact that there is a pretty big difference between the techniques employed by compressors that optimize compression ratio at the cost of nearly everything else, like ts_zip above, and practical tools that intend to balance compression ratio with limitation on CPU speed / memory, like zstd.

When optimizing for compression ratio, the prediction + entropy coding paradigm dominates. Practical tools, even modern ones like zstd, are mostly based around sliding window compression à la LZ77 (unzip/deflate), with the main selling point of more modern tools being that they scale up to larger window sizes and run really really fast. Some of these (like LZO) don't even have an entropy coding step to save time. zstd has both Huffman coding and FSE: Huffman coding is suboptimal but presumably it's an option because it's faster, and on lower compression levels it's preferable to be fast.

Anyway, the bottom line is: don't get confused between the state of the art in terms of compression ratio, and practical tools. Those are quite different things.

Re: Data Compression Explained (2012)

#30

Earlier quoted context omitted.

I think this is an analogy that's been taken far too far. The output of intelligence just isn't compression, that's memorization. The role of intelligence is to generate novelty. It's true that LLMs do something that looks very compression like in their weights, but it is lossy, and it has to be--if you're not lossy, you've overfitted the corpus, and that's bad. Post-training takes this even further, because you're n…

LLM compression doesn't necessarily have to be lossy. You can use the fact that LLMs predict P(next token | existing tokens) to losslessly and efficiently compress arbitrary token sequences. This idea is closely related to arithmetic coding.

True, but it's not relevant because that isn't how we actually train LLMs for use as quasi-intelligent tools. We specifically do not want the model to be able to just memorize its input, which is what your process requires.

Many things about the process are similar, so there's some analogy, but it just isn't the same.

Post reply on HN