Compression is prediction

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...

Compression and error correction also go hand in hand: in compressed data every bit carries more information and therefore errors are more detrimental. This is one of the results that Shannon phrased exactly in terms of entropy.

My PhD supervisor had a beautiful example. Take an English message and ‘compress it’ by removing vowels. It’s still intelligible because English has redundancy:

rrrs cn mk mssgs nrdbl

Similarly, an uncompressed message with errors (swapped characters) is also intelligible because of the redundancy of English:

erwurs lan nake wesaagis unfeatable

But now we do both: we compress the message AND add errors. The result should be much harder (if not impossible) to read:

rwrs ln nk wssgs nftbl

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

The page source appears to contain all the actual text within <p> tags, but structured in a completely illogical way. With JavaScript disabled, there are a bunch of shaded bars where the text should appear, which look like placeholders for something that hasn't loaded yet even though it was there from the beginning. The <p> tags don't even seem to show up in the DOM. (I didn't check closely, but maybe they're embedded in an inline script.)

This is actively user-hostile. The site is going out of its way to interfere with the most basic possible function of HTML, i.e., the presentation of minimally marked-up plain text. The needless complexity is especially ironic in the context of an article about compression.

The article is using probability where it really means proportion and prediction where it means evaluation. The mathematical equivalency is both much less surprising and less revealing once reframed.

If we consider the first example with the arithmetic code, the initial presupposition that only the characters A, B, and C appear in the string already reduces the entropy from 56 ascii bits to 14 bits (A vs Not A and B vs Not B for each character). If you further consider that you only need to distinguish B vs Not B if it's not A, then you can just represent As with a single zero bit and only represent the non-As as two bits (the first of which will necessarily always be a 1 bit). This gets you to 10 bits without even having the proportions of the string. Of course this would be a poor convention if there were say only a single A; in that worst case scenario you would need 13 bits, but simply knowing which character appears the most, without knowing by how much, 11 bits is the worst case scenario for a length 7 string with 3 potential characters. The last bit can be made implicit if you further choose the second conditional appropriately - i.e. if instead of B vs Not B we chose C vs Not C, our last bit would be zero and could simply be dropped meaning both 10 and a single 1 bit encode C - allowing you to encode the example string in just 9 bits and an arbitrary string of that length in 10, again regardless of proportions. That improvement over the arithmetic encoding result in the example is just a case of us cramming a little extra information into the encoding algorithm.

Arithmetic encoding is more clean and more easily extensible, it makes more sense to use than this custom encoding of 7 trits to binary but the point is the "probability" the article mentions is a superficial quality of life feature, not the secret sauce that is the actual key to compression.

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.

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...

[4] https://philarchive.org/rec/GREPBI

Nope; there is a bit more nuance and the distinction is important.

Compression is functionally equivalent to prediction when the data distribution is exactly representative of all future problems. The story changes drastically if you want generalization -- because the test distribution could be arbitrarily different, even if it had the same support! Eg: you observe a rare edge case in your training data and (lossy) compression could simply ignore it. But if you wanted generalization in that particular part of the space -- either because an adversary was testing you, or for design freedom where you choose to build in that specific corner -- then you don't just want data compression, but good prediction performance on a test distribution which peaks in that corner.

Assuming that the training data distribution is exactly the distribution you will ever care for is implicitly doing a lot of the heavy lifting in the claim that compression = prediction, and I'm peeved at how much this statement is unthinkingly repeated like a manifesto.

There is nothing natural about the training data distribution, especially if the data generation process is exploratory while the downstream usage will be exploitative.

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!

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 semantic compression task of turning prose to JSON across the board on pretty much every LLM that I've tested it on.

That's basically the explanation of it, I thought it was a crazy discovery when I found it a couple of months ago, but now I just think it is pretty neat.

This is a lot less surprising when you learn how non-LZ compressors work, that is, by modeling a probability distribution and using those probabilities to encode information in the minimum number of bits required to transmit the data. A less obvious conclusion is that LZ compressors do this to implicitly, the length of each symbol they could emit (literal or match, etc.) can be converted to the probability distribution the LZ compressor induces, since the number of bits to encode the symbol is related to its probability by the information content.

Yep, for example for predicting future access patterns in a VM subsystem.

Practical Prefetching via Data Compression; Vitter, Krishnam, Curewitz. 1993

The page addresses ('names') were the characters and the built-up LZ dictionary used to predict which "characters" → pages would come next.

https://www.ittc.ku.edu/~jsv/Papers/CKV93.practical-prefetch...

Optimal Prediction for Prefecting in the Worst Case; Vitter, Krishnan

https://dl.acm.org/doi/pdf/10.5555/314464.314575

Apparently the same trick was later rediscovered for web-pages.

Small world. I just did a podcast on this same topic, but coming at it from a different direction, ie. me and my neighbor trying to beat the hutter prize for compression.

Hutter Prize being where you are paid if you can compress wikipedia small enough. LLMs do very well at that, if, big if, you ignore the cost of initial weights.

A cool Claude Shannon story:

    Shannon wanted to measure how much information is actually contained in ordinary
  English text. His 1948 theory said such a number must exist, but he had no way to
  calculate it, because the patterns in English reach across dozens of letters and no
  equation or frequency table captures all of them at once.

  So instead of calculating it, he ran an experiment on a person.

  He took a passage from a novel that the subject had not read, and covered it with a
  card so only the text already guessed was visible. He asked the subject to name
  the first letter. If the guess was wrong, he asked again, and kept asking until the
  subject named the correct letter. He wrote down how many guesses it had taken,
  revealed the letter, and moved the card one position to the right. Then he repeated
  the process for the next letter, and the next, through the whole passage.

  What this produced was not a sequence of letters but a sequence of numbers — one
  number per letter, recording how many guesses that letter required. Most of the
  numbers were 1, because someone fluent in English, seeing the preceding text,
  usually names the next letter correctly on the first attempt.

  Shannon then argued that this sequence of numbers contains exactly as much
  information as the original passage.

Sounds a lot like next token prediction to me.

https://corecursive.com/the-hutter-prize/

http://prize.hutter1.net/

https://github.com/hkust-nlp/llm-compression-intelligence

https://www.princeton.edu/~wbialek/rome/refs/shannon_51.pdf

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.

I stumbled across a connection between LLMs and compression when researching N-dim polytope emergence in neural networks. Toy Models of Superposition (Anthropic, 2022) suggests that gradient descent can independently discover efficient geometric packing arrangements for sparse features. LVQ compression uses regular lattice structures, including some based on 4D lattices.

I found this interesting and wonder whether LLMs have a higher density ceiling, since training and inference don't rely on a fixed lattice and can instead learn their own representational geometry.

If a string produced from random noise gets compressed (because it has invariably some repetitions in it if long enough), is there any prediction? Even getting the probability distributions right doesn't get to any way to reliably to predict the next symbol out of the sample string. Any functions fitted etc. will be incorrect, too.

Cool visuals and breakdown. I wrote something in early 2025 about how LLMs seem to be an emergent behavior of lossy compression, but did not have the knowledge or verbiage at the time to get this detailed. In retrospect my writing seems naive and I'm happy to have found this and the Google paper linked inside. To be a fly on the wall in some of the labs, man.

Another thought that came from the same post is that, insofar as we see LLMs as human-style intelligence, they're more like stream of consciousness devices. Essentially incessant talking and buying enough time until you get to a usable answer. I think I associate some subset of intelligence with what you don't say, which is impossible with the SOC-style outputs, so this is something I think about a fair bit.

What could maybe differentiate current gen models from next gen is the ability to call tools modeled within the layers themselves, not externally. I think as far as I understand it, model trainers expect the model to do this itself in a way we don't understand or control, like a version of the bitter lesson. But I posit we can model many determinate tools as NNs themselves and figure out how to get the internal states of the LLM to make use of them during inference, e.g. calculators, indexes, citations. Just an enthusiast though, so grain of salt and all.

I keep on seeing this claim, especially from popular creators such as 3Blue1Brown. How is this not borderline vacuous?

I'm not a LessWrong^TM rationalist guy, but one really good thought experiment I always keep in the back of my mind from them is Solomonoff induction. AIT people take it as a framework to work with - it's pretty cool, I agree. But I (and some other people, such as certain AI execs at Amazon - according to my interpretation of their public interviews) think it just highlights the trap - given an arbitrarily powerful oracle, you can get compression down pat. Like, if you assume the source is generatable with a turing machine, and you write a function to brute force over all turing machines, then whoa, your compression works. You will necessarily find the optimal compression at some point because your search function is literally searching over all possible turing machines that could've generated the input sequence, anyways (because the input sequence was generated by a turing machine)

These are the kinds of results you can get if you don't have any actual constraints on what the compressor can do.

(Of course, again - this is not the point of solomonoff induction - it's to use this as a base truth, to then layer parsimony on top of that. There are infinite number of turing machines that could match your prefix, parsimony filters, throw some bayesian inference on top of that, and you get Solomonoff induction. They constrain it afterwards. But I think to that intuition as a base whenever people claim new results.).

But I see in casual conversation, people constantly making claims like, "LLM's are so good because they compress a model of the world". What is that model then? Scott Aaronson has made points like this before - your "model" could just be a massive lookup table, so you can't just claim "compression" and win - the compressor must be reasonably small, too.

I don't object to the notion that LLM's have some notion of world models more sophisticated than memorization. That's proven by actual interventional experiments, such as the ones that actual interperability researchers do. But mere compression is vacuously powerful. "Vacuous" not in the sense that "oh, you might be suboptimal and be a little more complex", vacuous as in "the philosophical point you were trying to make is vacuous because you make a vacuously powerful statement".

(I'm not a total fan of intervention either, as an end-all gospel as some people use, but it's far, far better than not having it).

‘ I was reading about compression recently when I stumbled upon something crazy: that compressors and LLMs are, at their core, trying to solve the exact same problem.’

This reads as written by someone who just happened to understand what LLMs do, so I totally fail to understand how anything further said can have any real credibility…

As a matter of fact the best compression by Fabrice Bellard’s models have been achieved with NNs long before LLMs.

And also MP3 and MPEG in general are very apparent neural networks, yet not deep as in modern VLMs

Schmidhuber did it first:

Driven by Compression Progress: A Simple Principle Explains Essential Aspects of Subjective Beauty, Novelty, Surprise, Interestingness, Attention, Curiosity, Creativity, Art, Science, Music, Jokes

https://arxiv.org/abs/0812.4360

Ted Chiang made a similar point in his article "ChatGPT is a blurry JPEG of the web" a few years ago:

https://www.newyorker.com/tech/annals-of-technology/chatgpt-...

On a slightly related topic, static on disk files of LLMs are not incompressible, I have a number of "archived, maybe I'll use it later" Q8 quantized GGUF files that are about 90% of their original file size when run through xz with default options. It's not a ton of disk space savings, but disk space also isn't as cheap as it used to be. BF16 GGUFs will compress a lot.

Compression is just counting. Probability, also, pretty much, just counting. For these reasons I think the role of information theory in describing the process of the development of reasoning and the gain of understanding has been overstated.

Relevant old school compression benchmarks where people have been using different models (incl. transformers) for compression: https://www.mattmahoney.net/dc/text.html

Also interesting the top entry is from fabrice bellard: https://bellard.org/nncp/nncp.pdf

I was thinking about the same topic and the conclusion can be wrong. LLMs are compressors, but compressors are not LLMs. Mixing this can let you believe that you can use a compressor to do the same thing as LLMs, which you cannot.

Specifically I was thinking about a way to inject knowledge into LLMs training by using statistical properties of text in such a way that you don't have to train the LLM to achieve some level of predictions. There are actually some papers that inject n-grams statistics as a part of the neural network weights.

I tried asking a zip file to write a program for me but it did nothing.

I’m starting to think that compression is not, in fact, prediction.

Compression is not prediction, it is recall. Can we make predictions based on compression? Absolutely. Is memory encoded into physical neurons technically compression? I would argue also yes.

However, going from compression to prediction is a large jump that is unsubstantiated by this article and based on the claim that probabilistic recall is also prediction.

Two perfect counterpoints to this are markets and weather patterns. One cannot predict future events based on past performance or behavior. Change is the only thing that's constant, and chaos/entropy is everywhere we look.

For simple problems like programming, sure predictive recall works amazingly well, but let's not pretend LLMs are actually predicting something. This is exactly why LLMs suck at doing anything novel; they lack imagination and creativity.

I always feel like people leave out the third case of the analogy: indexing

The article itself has decision trees for the compression explanation, which is also a lookup index.

In each case you try to recognise (re)usable structure.

Self-indexing succinct data-structures are a good example of the third side of the coin.

So it's a trinity: compression, prediction, indexing

There is a correct sense, but we're sort of garbling concepts here:

Predictability is the inverse of information density.

Low information density enables high compression, and vice versa.

It's called entropy. This is basic information theory to be quite frank..

> compressors and LLMs

Why only LLMs? All statistical models are compressor. You can say "model" and "compressor" are synonyms.

Article does not mention "embeddings" at all, even though it's commonly viewed as a compression method. Also "encoder" part on "auto-encoders".

This immediately reminded me of the Hutter Prize (http://prize.hutter1.net/) - a contest that has run since 2005(?) based on the premise that compression is closely related to intelligence.

A few years ago I published BIDEN: Binary Inference Dictionaries for Electoral NLP, based on this idea - https://matthodges.com/posts/2023-10-01-BIDEN-binary-inferen...

1) am I allowed to scan the entire corpus in advance before I populate the dictionary? Is this a stream, or is their an EOF marker I will know in advance?

2) if 1) then "prediction" isn't the word I'm looking at.

The comparison can be carried on to another even crazier level: Evolution is compression. All the complexity of biology is executed at the highest possible efficiency.

Unrelated to the content: I was really pleased to see that this site defaults to the bare minimum for cookie consent. I reflexively clicked "Reject all" only to see that it was already the default, which threw me off.

It's more or less obvious that the LLM is a lossy-compressed version of the training data; it reproduces sequences of tokens that are the sort of thing that could plausibly occur in the training data, and avoids sequences that are implausible.

Because most of the training data has good grammar, the LLM is strongly trained on grammar; it will rarely predict ungrammatical gibberish. Even if there are grammar mistakes in the data, they are not systematic and so don't reinforce each other.

The prediction happens when it is uncompressed right?

LLM embeddings are compressed training data.

To decompress that is to make a prediction (in this case to convert the embedding into readable text)

Something Ngrok is doing is working, because first they manage to get Sam Rose of samwho.com and now this? At this point I care more about their blog than their products

How about dictionary based compression as a counter example? Or the zig zag encoding scheme used in JPEG? I find it difficult to cast some of the things that effectively compress data as prediction.

I see it that prediction is a form of compression.

Say you have a computer file composed of two parts, the first represents the setup of an experiment, and the second is the data produced by the experiment.

If you have a good theory relating to this type of experiment, then you can predict much of the second part of the file. So you only need to store the first part and possibly some corrections to the least significant bits of some of the parts of the second part of the file.

Thus with good prediction, you can compress this type of file.

Physics laws are the ultimate form of compression because they are so universal and say so much about so many things in few words, or a formula. This is why Newton's laws were a big achievement. And they enabled predicting the behavior of machines and started the industrial revolution. We are at yet another inflection point.

Awesome read and absolutely loved the interactivity. A lot of effort was put into this.

3Blue1Brown - "Compression is Intelligence": https://www.youtube.com/watch?v=l6DKRf-fAAM

Recently I wrote a blog post[0] expanding on a similar idea from the angle of ancient Greek philosophy, particularly Parmenides: to think is to compress.

[0]: https://faingezicht.com/articles/2026/05/28/shape-of-what-we...

See also: Bellard's Lossless Data Compression With Neural Networks

https://news.ycombinator.com/item?id=19589848

https://news.ycombinator.com/item?id=27244004

great talk by ilya sutskever on how this https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2121s

i do agree with that point of view. I often referred to models as 'modern mp3s' storing a lossfull but lookalike version of information in order to counter that 'AI is totally new and not violating copyright by storing information in a magic fashion' argument.

Author's bio:

> Annie Sexton is a Developer Educator at ngrok with a passion for nerd-sniping developers.

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.

did the SSL cert expire? i'm getting a big scary warning about this blog

Reminds me of this...

In Silicon Valley, Richard Hendricks creates a revolutionary lossless data compression algorithm for his startup, Pied Piper.

This is simply wrong.

Compression requires prediction.

The better the prediction, the better the compression, whether you are measuring fidelity or result size.

This doesn't mean that compression is prediction.

I was rushing to post this and then found out somebody had already

There

Perhaps a similar observation; https://news.ycombinator.com/item?id=48703636 :

> Compression, Predictive modeling, or Complexity?

Perhaps a bad example: https://news.ycombinator.com/item?id=38400380 :

> "78% MNIST accuracy using GZIP in under 10 lines of code" (2023) https://news.ycombinator.com/item?id=37583593

Not really, compression doesn't require a world model, it's mathematically pure. Any AGI system must periodically reset it's prediction since the world is inherently stochastic. When we look at prediction markets they only seem to work in the long term because human language is abstracted away from the real world, again it's mathematically pure. That's why we get bugs in code and disputes with prediction outcomes.

A better title, you can improve your compression if you make an accurate prediction. Much like how a branch predictor can make a CPU do the same work in less time. Or when your symbols are true uncompressable rules of reality (which is probably meaningless both semantically and physically again due to inherent randomness)

The main difference between minimalist and maximalists are how much that set of uncompressable rules gives you. I suspect the search space is too large. What we see in practice is that lossy rules let you cover more ground but eventually you hit a wall and have to move to a lower level of abstraction to make progress. There are 10^360 paths in a go tree, but something like 10^300,000 for molecular chemistry and that's not even all the way up (or down, say 10^3000 for the standard model of physics that's 10^900,000,000 if you want to do chemistry without chemistry abstractions.). Just semiconductor fab is 10^(10^11) so 10^(10^16) with molecular chemistry (think finding an implementation for some sort of desired self assembly outcome). AI can be way way way smarter than humans and there just not be enough energy in the universe to find these needles. So we definitely need abstractions, but those are at odds with predictions and the choice of symbols often introduces abstractions that the designer didn't consider.

[flagged]

[flagged]

[dead]

[dead]

[dead]

I'm surprised no one has mentioned the recent 3 Blue 1 Brown video on this topic: https://www.youtube.com/watch?v=l6DKRf-fAAM