Compression Is Prediction: How LLMs and Compressors Solve the Same Problem
Compression and language modeling are fundamentally the same task: predicting the next symbol. This post breaks down the anatomy of a compressor—transforms, models, and entropy coders—and explains arithmetic coding, a technique that encodes an entire dataset as a single number. The key insight: better probability predictions lead to better compression, and the same principle drives LLMs. With a concrete example, the author shows how skewed probabilities shrink average bits per symbol, revealing the deep connection between compression and AI.
It’s probably going to blow your mind.
- hexapus
So a company with an wildly superior compression algorithm stumbling into a society-breaking AI isn't so far-fetched. Jesus...Silicon Valley really was ahead of its time.
I mean, save for the part where the founders recognised the threat it posed to society and acted responsibly rather than unleashing it on the public and sucking down billions in VC money.
- farfatched
This is the thesis behind the "Information Theory, Inference, and Learning Algorithms" course that was taught at Cambridge University.
> Why unify information theory and machine learning? Because they are
two sides of the same coin. In the 1960s, a single field, cybernetics, was
populated by information theorists, computer scientists, and neuroscientists,
all studying common problems. Information theory and machine learning still
belong together. Brains are the ultimate compression and communication
systems. And the state-of-the-art algorithms for both data compression and
error-correcting codes use the same tools as machine learning.
Book (creative commons): https://www.inference.org.uk/mackay/itila/book.html
Lectures: https://m.youtube.com/playlist?list=PLruBu5BI5n4aFpG32iMbdWo...
- sheeeeesh
Grant Sanderson has an excellent video on the same topic [0]. It's part of a series that is ongoing.
[0] Compression is Intelligence Part 1 - https://youtu.be/l6DKRf-fAAM?si=yyLWq8x4sSRkWd98
- woliveirajr
There is Compression done by Prediction by partial matching [0]
There is the Kolmogorov Complexity [1], Normalized Information Distance [2] and Normalized compression distance [3] that correlates those.
Finally, there's the Pre-Big Bang Informational Compression and the Delayed Release of Antimatter [4]
All big {rabbit/black} holes to lose some time, if you have any.
[0] https://en.wikipedia.org/wiki/Prediction_by_partial_matching
[1] https://en.wikipedia.org/wiki/Kolmogorov_complexity
[2] https://homepages.cwi.nl/~paulv/papers/chapter08.pdf
[3] https://en.wikipedia.org/wiki/Normalized_compression_distanc...
- Lerc
Prediction is compression, but I am not sure if it is true the other way around.
It's obvious that an accurate predictor enables encoding only the data that the predictor gets wrong.
But a compressor can encode patterns that defy prediction by looking at the data as a whole. It doesn't have to look at everything in sequence as it arrives.
Applying transformations prior to entropy encoding often isn't just 'rearranging into an easier to compresss format' the transformation can be doing the job of peeking into the future. That makes the encoding a whole lot easier, but it is much harder to call it prediction.
- YuechenLi
Oh, since the topic of semantics compression via LLMs came up, here is some interesting research result that I had found earlier this year that I posted here and failed to explain properly, with a benchmark as well for you to try on your own if you want.
https://github.com/yuechen-li-dev/GenerativeCompressionProto...
Essentially, copypaste the codeblock in the Markdown into any LLM chat, and it will return with the benchmark results. Very easy benchmark to run.
Essentially, semantic compression refers to reducing the size of a set of data while retaining its full semantic meaning. The useful application of that is of course, with prompt compression to save context. I know a lot of people essentially sends their prompt to another LLM to compress into JSON first before they send it out, and this came out of an experiment to see the best method to accomplish that task, and the idea is that the compressed and uncompressed prompts will return the same result if sent to another LLM.
What that block of Chinese text is essentially a kind of "meta-prompt" that causes the LLM to reflect on itself as well as the method of how to compress information into the highest possible density form, and the reason it is in Chinese is because it is the language with the highest semantic density that I know of. You can ask an LLM to explain what the text in the block means to have an explanation of what everything means and why it works, but overall it tends to greatly increase the efficiency of sem […]
- throwaway_7274
This perspective is a useful source of intuition against the “LLMs can’t have new ideas, they’re just next-token-predictors” style arguments. What if you shift your perspective to thinking of training as optimization over a vast parametrized family of compression algorithms? Well, it suddenly looks a lot more plausible that “new” “ideas” can emerge from that process!
- saltcured
I think a better headline would be something like: Compression is Abstraction and Decompression is Extrapolation.
Many of the debates in the comments seem to come down to whether people believe prediction and extrapolation are synonymous.