---
title: 'Reinventing Entropy | Compression is Intelligence Part 1'
source: 'https://youtube.com/watch?v=l6DKRf-fAAM'
video_id: 'l6DKRf-fAAM'
date: 2026-08-08
duration_sec: 1939
---

# Reinventing Entropy | Compression is Intelligence Part 1

> Source: [Reinventing Entropy | Compression is Intelligence Part 1](https://youtube.com/watch?v=l6DKRf-fAAM)

## Summary

This video explores the fundamental limits of data compression, tracing the origins of information theory with Claude Shannon. It demonstrates how the concept of entropy naturally arises from the question of optimal encoding, and connects these ideas to modern machine learning, particularly the training of large language models.

### Key Points

- **The Compression Question** [00:00] — The video introduces the question of the fundamental limit of data compression, noting that ASCII is inefficient and clever encoding can reduce average bits per character.
- **Information Theory and ML** [00:44] — Shannon's work in information theory is surprisingly useful for modern machine learning, particularly in understanding cross-entropy loss in LLM pre-training.
- **Prediction Equals Compression** [01:12] — Prediction and compression are mathematically equivalent, allowing pre-training to be reframed as creating an efficient text compressor.
- **Warm-Up: Robot Instructions** [03:25] — A warm-up example: a robot with four instructions (up, down, left, right) with probabilities 1/2, 1/4, 1/8, 1/8. The naive encoding uses 2 bits per instruction.
- **Variable-Length Encoding** [05:06] — A clever student proposes a variable-length code: 0 for up, 10 for down, 110 for left, 111 for right, achieving an average of 1.75 bits per instruction.
- **Prefix-Free Codes** [08:07] — The key constraint is that no code word can be a prefix of another, making it a prefix-free code. This is visualized with a binary tree diagram.
- **Perfect Compression as Random Noise** [11:06] — The theoretical student argues that perfect compression should produce a bitstream indistinguishable from random noise, leading to the idea that each bit is an independent coin flip.
- **The Fundamental Formula** [15:07] — The number of bits allocated to a message in a perfect scheme is -log2(p), where p is the probability of the message. This is the fundamental formula of information theory.
- **Defining Information** [16:27] — Shannon defined -log2(p) as the information of an event, with highly expected messages containing low information.
- **Information in Language** [18:04] — For language, probabilities are context-dependent and not perfect powers of 2, so information values are fractional. The information of a full message is the sum of the information of each letter.
- **Shannon's Experiments** [21:20] — Shannon's experiments involved n-grams and human guessing games to estimate the entropy of English, treating human brains as black boxes that predict characters.
- **Defining Entropy** [25:02] — Entropy is the average information per symbol, calculated as the sum of p * -log2(p). It represents the minimum bits per symbol needed for encoding.
- **Noiseless Coding Theorem** [29:00] — Shannon's noiseless coding theorem states that no encoding can be more efficient than the entropy limit, and it's always possible to get arbitrarily close.
- **Entropy of English** [30:29] — Shannon estimated the entropy of English to be about one bit per character with 100 letters of context, suggesting English can be compressed to a single yes/no question per character.

## Transcript

[Submit subtitle corrections at criblate.com] When you encode text into binary, it's often nice to use as little data as possible, so you might naturally wonder, is there some kind of fundamental The default encoding with ASCII is pretty inefficient.
If you apply a little cleverness associating more common characters with smaller bit strings, you can get this down to an average of around four that leverage patterns among long sequences of text, can get even better still.
I'm guessing many of you might have heard an estimate here, single numerical answer is how you would even approach answering it.
with Claude Shannon's seminal work that kicked off information theory. Now what's very interesting is how the math that he developed to answer questions like this has turned out to be surprisingly useful for modern machine learning.
To take the salient example of today, when large language models are trained, the pre-training portion of that is usually described as being about next token prediction, specifically using something called cross-entropy loss.
But what's also interesting is that one of the conclusions of information theory says that prediction and compression are mathematically equivalent. Which means, you can entirely reframe how you think about the pre-training
but instead as being about creating the most efficient possible text compressor. I think it offers more clarity on what this notion of cross-entropy really is,
Also, I don't know about you, but to me at least, there's just something very intriguing about using compression as a fundamental In fact, some people have gone so far as to say, compression is intelligence.
since intelligence is such a squishy and ill-defined term. compression is bizarrely relevant to artificial intelligence.
first in a trilogy of videos aimed at laying down the mathematical For the next 30 minutes or so, you and I will be focused on understanding
the limits of compression, and seeing if we can get you to feel like you could have rediscovered the core idea behind Shannon's noiseless coding theorem. namely those of information and entropy.
And it might sound a little weird for me to describe definitions as something to be discovered, but great definitions are often the residue of some kind of insight. laying down a formula for you, but doing so too early would spoil a good story.
It is much more fun to see how you are inexorably drawn to And what I want you to notice by the end here is how we can't really answer this question, or at least Shannon couldn't,
without necessarily engaging with some notion of intelligence. but it helps to warm up with a simpler example containing the
same essential ideas needed for our path of rediscovery. whose job is to wander the surface and collect data. that are going to be limited to four very simple possibilities.
Move up, down, left, or right, each one with a fixed step size. The nuance will be that these instructions are not uniformly distributed. Half of everything we send is up, one fourth of the instructions are down,
one eighth are left, and the other eighth are right. and in that spirit of simplicity, we're also going to assume that every instruction They are sampled from this distribution regardless of the preceding context.
When we send data to this bot far away, we're doing it as a stream of bits, ones and zeros, and it's very slow and costly to do that, so the natural question, the warm-up puzzle for you today, is to ask what is the most efficient
possible way to encode these instructions as a stream of bits. And here, we might imagine three students who each attempt an answer, one who's straightforward, one who is clever, and one who is very theoretical.
well, for each of these four instructions, we could just use two bits. Maybe 00 encodes up, 01 encodes down, 10 encodes left, and 11 encodes right.
It simply breaks up the bitstream into chunks of two, and translates each chunk into the appropriate instruction. Now, the clever student points out, well, that does nothing to take advantage
of the fact that up comes up way more frequently than left or right. They propose a method where we use a different number of bits for each instruction. I'll explain it in just a second, but I do want to call out the fact that
it's certainly not obvious that the robot is going to know how to decode it. After all, it needs to somehow know where to draw the dividing lines.
but it's easiest to explain if I just kind of lay it all out. What they suggest is letting the single bit 0 represent up, letting the two bits 10 represent down, using 110 for left and 111 for right.
that this would require with a simple weighted sum. two bits are needed, and the remaining times, you need three bits.
When you add this all up, as a weighted sum, you get 1.75 bits per instruction, which is indeed better than the more naive approach of a flat two bits per instruction. but because they come up so much less frequently,
this is more than made up for by using only one bit for that most common instruction. And you can see this efficiency bear out empirically too. This right here is a set of instructions sampled from that distribution.
You'll notice lots of ups, about half as many downs, and even fewer lefts and rights. When you turn each symbol into the appropriate bit string following this encoding, the resulting sequence of bits is indeed shorter than what the naive method gave.
But I hear some of you asking, how does the robot know how to decode this? Can we be sure that there's an unambiguous way to draw the dividing lines? used to encode the instructions is called a code word.
student was following to make sure that their code words don't conflict with each other. stream from the robot's perspective and think it through.
So far, this could be encoding any of the last three instructions, down, left, or right. If what follows is a 0, then it can only be down.
So the robot can register that as a complete instruction. that must be encoding up, since there is no other possibility. After that, if they see a 1, this is so far ambiguous,
If the next bit is another 1, it remains ambiguous, it's the prefix of the last two. But that following 0 then makes clear these three bits must have been encoding left.
In short, all the robot has to do is read in the next sequence at which point it can register it as a complete instruction. If you step back and think about it, the key constraint for this
all to work is that no code word can be a prefix of another one. fifth instruction that had the code word 100. it's not clear whether that's supposed to be down,
or if it's supposed to be the start of this new fifth instruction. When you avoid this kind of conflict, an encoding method like this has a special name. It's known in the business as a prefix-free code, or what is confusingly synonymous,
And there's a really nice way to visualize choosing prefix-free codes with a certain diagram that represents every possible binary string. how I want to show entropy in just a few minutes.
and stare at it for a bit, but I'll call out the important features. and you'll notice everything that starts with a 0 lives on the left half
of this diagram, and everything that starts with a 1 lives on the right And that same idea continues recursively as you go up. So everything starting with 00 is above this quarter of the diagram,
everything starting with 01 is above this quarter of the diagram, and so on. In particular, the key property is that every binary string in So when our clever student chose to allocate a single bit 0 to
represent the instruction up, they were effectively consuming half of the space of all possible code words by doing so, since everything starting with a 0 is now prohibited based on this prefix-free property.
Similarly, allocating one 0 to down eats up another fourth of this space, and the remaining two instructions each eat up an eighth of the space. And at this point, I'm guessing that there's some bell kind of resonating in your mind,
probability for each instruction coming up. And in fact, that tickling sensation of a relationship between data size and probabilities is exactly the founding insight for information theory.
When you stare at this pleasing alignment, it might suggest that the clever student's solution is not just better, maybe it's somehow perfect. How could you know that there's not some ultra-clever method that does
makes it so the average bits per instruction gets even lower than this? who has not really been thinking about actual codes that they can implement.
They have been pondering what properties a perfect, optimally efficient code would have. They have this really clever idea, which is to argue that random noise should be incompressible, and therefore, a perfect compression algorithm
should produce a bitstream that's indistinguishable from random noise. this can actually lead you to reinventing the idea of Shannon entropy. Now when I say random noise, what I mean is that each bit is a 1 or a 0,
with 50% probability, and all of the bits act independent from one another. encoding for the robot genuinely follows this rule. If you think about it, there's a 50% chance that the message starts with the
instruction up, so that first bit has a 50% chance of being a 0, otherwise it's a 1. And then if it is a 1, there's a 50% chance that the instruction is down, And so on.
Each new bit really does act like an independent coin flip, so to the receiver, that compressed bitstream really is indistinguishable from random noise. Well, for that, let's really focus on things from the receiver's perspective.
it helps to zoom out and frame our discussion in terms of entire messages and what the encoding for full messages looks like. When that receiver sees a string of n bits representing some compressed message,
this is one out of 2 to the n possible messages they could And then critically, because we're assuming this looks like random noise, all 2 to the n of those messages must be equally likely.
Our theoretical head-in-the-cloud student really wants to make an argument for like maybe we're compressing language or compressing images,
and they want an argument that works regardless of the details of what specific A loose intuition in your head is that maybe among all of the messages that compress down to n bits, some of them would contain a larger amount of predictable data,
while others would have started as a smaller amount of unpredictable data. But the key point is that if the compressed bitstream really does look like random noise, meaning all of the bitstrings of size n are equally likely,
it must be the case that all the underlying messages being compressed were equally likely to arise, and even more specifically with probability 1 over 2 to the n. So again, why am I claiming that this is incompressible?
the space of all possible binary strings. In this case, we can think of all the encodings for our 2 to the n equally likely messages as being the bitstrings on one layer of this diagram.
If you tried to define an alternate scheme, where you tried to become more it would move lower on the diagram, which means it then overlaps with some other message, so you would have to put that other message somewhere else
At minimum, that means it's sharing a space with yet a third message, requiring that extra bit for each of them to disambiguate.
So saving one bit over here costs you two bits elsewhere. only to see it pop up even worse in another spot. In general, any message encoded with a string lower on this diagram is going to be eating
up more than its fair share of the space, which forces multiple other messages to occupy a smaller region, bumping them higher up, meaning they're encoded less efficiently. I'm going to guess that it's decently intuitive for everyone watching that
all the same number of bits, but I do think the diagram gives a more concrete way to see why you end up with unfavorable trade-offs otherwise. this is exactly the kind of thing I was referencing in the intro,
Notice how what we're basically saying is that a message that uses n bits in a perfect scheme must have a probability of 1 over 2 to the n, or 2 to the negative n.
If you take the log base 2 of both sides here and then negate, this is equivalent to saying that the number of bits allocated to a message, where p is the probability of occurring.
This negative log expression is the fundamental formula for all of information theory. Everything up to this point is me trying to make this value feel like something you are inevitably drawn to by asking about perfect compression,
rather than it feeling like some arbitrary definition that we start with. Some students do find this negative log takes a little getting used to. You know, it looks like it should be a negative value before you think about the fraction
in the middle, but really the intuitive way to read it is that it's asking how many times do you chop your space of possibilities in half to get to a certain quantity. Here, let me pull up some axes and show you the graph of negative log of p.
I've also seen some authors default to writing this as the log of 1 over p, You could also think of it as the log base 1 half of p, but personally I would be quite partial to that as a convention.
Now, however you write it, what Shannon realized is that this is a very useful way to think about the information that a message contains even when literal perfect compression is not possible and p is no longer a clean power of 2,
which would mean that the output here is some fractional amount. In fact, he defined this expression to be the information of an event. The image I sometimes have in my head is to picture the probability of an event
with a little pie chart, and the information is this bar above it that gets kind of pumped up to be taller as the probability is squeezed closer to zero. and the bar is relaxed to get shorter as the probability approaches 100%.
Highly expected messages contain very low information. I want to be clear that there is content to this definition. It's more than just rescaling probabilities, as if converting to an alternate unit system.
In a perfect compression scheme, the number of bits allocated to a full message precisely equals this information content. Your probability's messages are likely not perfect powers of 2.
information of a message gives you a lower bound on how much it can be compressed, It's perfectly possible to overfit a compression algorithm to one specific case.
we need to step up our game beyond that warm-up example. They were all perfect powers of 2, so that the information
But Shannon was very interested in this question of limits on compression for much more realistic and complicated cases, like natural language.
For example, here I'll pull up the probabilities for each new letter in an example phrase, at least as determined by a little GPT that I'm running locally. distinct from the probabilities of actual language,
It becomes very relevant later. One key difference with language is how heavily dependent on context everything is. The probability distribution for each new letter you see is highly,
The other big difference is that all of these probabilities So if you compute the Shannon information of each one of these,
meaning you take the negative log base 2, all the numbers that you see are And again, giving a vague interpretation of what these mean is really not hard. and it's high for very unpredictable letters.
But all of you watching this are smart enough to demand a more exact interpretation, one that justifies why these values deserve to be given the units of bits. I mean, it's not like there's going to be some perfect encoding where this
letter i has a code word that is somehow 4.19 bits, or where this highly predictable o is somehow encoded with just a narrow sliver of a bit. and coming up with a bound on their compression.
looks like multiplying the probabilities for each successive new letter, where again, I'll emphasize that these successive letters' probabilities are conditioned on what
This is essentially the chain rule from probability. If you ask for the information of that full message, taking this negative log expression,
this breaks up really nicely as the sum of the information for each individual letter. through a very specific compression algorithm that would
actually compress this text to within one or two bits of this value. It's no longer as simple as mapping each character to a predefined code word, but you nevertheless get this very direct sense of thinking about adding up the
fractional information content of each letter to determine the length of the final Even if, by the time you need to relate this to actual data sizes, what Shannon realized is just how useful it is to work at this higher layer of
abstraction, where all your information is allowed to freely be continuous and information of successive events really nicely adds together. the fundamental compressibility of language, all of this hinges on the
question of how you know the probabilities for each successive letter. Here, for all these animations, I've been illustrating things using a language model, but for one thing, that doesn't necessarily feel the same as the true
it's not even clear what we would mean by the true probabilities of language. back in time and see how Shannon himself thought about all of
Some of his earliest experiments on the information of language involved what you often hear referred to as n-grams, and then tracking the statistics
So, for example, if you scan through a few books, record what letters tend to follow, you could build up a table of probabilities you care about.
Now, the problem is that this just completely breaks down for longer strings of letters, of the books that you're analyzing. about what's expected to follow such a longer string.
since longer context windows are when things are at their most predictable, and that's where you stand to get the most compression due to that predictability.
Shannon analyzed a different model of the English language that he had available to him, As the story goes, Shannon pulled out a book and
Shannon would then transcribe her guesses letter by letter. Every time she guessed incorrectly, he wrote down the correct letter, and then whenever she guessed correctly, he would just replace it with a dash.
actual letters than the original, but his point was that it contained If he could somehow obtain an exact replica of his wife and conduct the
guessing game again, he would only need to supply her with this reduced text. for his duplicate wife to exactly reproduce the original.
Of course, in practice, a person wouldn't necessarily guess the same way twice, and while this qualitatively conveyed the idea of predictability allowing A bit later still, in his 1950 paper, Prediction and Entropy of Printed English,
Shannon updated the experimental design to get a more robust read on this slippery question of the average information content in English. each guess was right or wrong, Shannon recorded how many guesses were
necessary for a human guesser to come up with the correct next letter. the number of guesses required with an implicit probability that a person would have been assigning to the true next letter.
but the broader point I want to make is how, in analyzing language, he wasn't just doing pure data analysis looking through books. He was trying to probe at an underlying model of language, namely the interviewee's brain.
These brains that he could talk to were effectively treated as black boxes, ones with a sophisticated and yet indescribable understanding of language and an ability to predict characters based on the context.
interrogating black boxes that process language to designing them. The reason that you and I are here, revisiting the roots of information theory
is because of how much of the math in modern machine learning leverages the Aside from the definition of information itself, there are three more key expressions that I want you to feel like you could
have rediscovered, not just because rediscovery makes them more memorable, but because seeing how they naturally arise from studying compression gives a more solid ground from which you can assess that thought-provoking interplay
You already have everything you need to reinvent the first of these, which is entropy. whether that's the four robot instructions, the English language,
Entropy asks about the average amount of information for each symbol, where perfect compression looks like random noise, and how, in that case,
the number of bits used for a message is the same as the information content of that message, which again breaks down really nicely as the sum of the This question of measuring the average information per
It would give you a lower bound on how efficiently a given signal could be compressed. when we took that weighted sum to find the average bits per instruction for the
Basically, because that encoding was perfect, each symbol's code So, effectively, we're calculating the average information per symbol.
For any given probability distribution, characterizing whatever symbols your messages are made out of, the average information per symbol should look like
adding up p times the negative log of p for each probability p in that distribution. And take a moment to notice how we're visualizing this expression. distributions with stacked horizontal bars, where each bar's
width is equal to its probability, so altogether they add up to be 1. Now, above each one of those, I've put a rectangle whose height is locked to be the corresponding information value, the negative log base 2 of that probability.
So the weighted sum up top, the average information per symbol, can be thought of as the total area of all these rectangles together. It only describes the compression limit in cases where
That's true in the robot case, but it's not true in English, for example. And there's a fun story about how John von Neumann supposedly told Shannon that he should
it resembles an expression already used for the idea of entropy in statistical mechanics, and for another, quote, nobody knows what entropy really is, I looked into it, it's probably apocryphal, but
Now, whatever the true story is, Shannon did call this quantity entropy, And it's fun to take a moment to play around with
The more evenly distributed a probability distribution, the higher the total entropy, maybe with one event dominating the probability space,
this would have a very low entropy, since that one overwhelmingly probable event And then also, if you divide up the probability space even more, meaning it's distributed over more total possible symbols,
each one has more information, so the total entropy is higher. where a very skewed distribution gives lower total entropy, whereas a more even spread gives us higher entropy.
The vague qualitative intuition here is that entropy measures the amount of uncertainty in a distribution, but the more precise understanding, is that it describes the minimum number of bits per symbol necessary to encode
That statement, and everything we just covered, 1948 paper that kicked off information theory, the noiseless coding theorem.
It states that no encoding can ever be more efficient than this limit, and even more strongly, he showed that it's always possible to get arbitrarily close Now like I said, this expression only applies in cases where every symbol follows the
same distribution, but Shannon was of course keenly interested in a more general setting, where the probabilities for each new symbol don't necessarily follow the same the compressibility of natural language.
something known as the entropy rate for a stochastic process. What is the average information per symbol, except in this case we're now averaging over all possible messages.
with some clean visual like the one we were just playing with. After all, what formula describes the probability distribution for language? this is well beyond what any exact calculation can give you,
hence why Shannon turned to estimates based on observation. And again, his methodology was not just data analysis. In order to get a satisfying estimate on compressibility,
he found himself inevitably needing to probe at intelligent models of language. When his interviewees had at least 100 preceding letters of context, he estimated the entropy of English to be about one bit per character.
because it suggests that English could be compressed down to just a single yes or Wild as that sounds, in the third part here, I will show you that algorithm I've
referenced, where if you're allowed to use a high-quality language model for encoding and decoding, you can get surprisingly close to this limit in practice. Before then, it helps to understand a variation on entropy, known as cross-entropy,
asking both how and why it's used in training large language models. If you want to learn that, as well as a few fun related ideas like how and why on earth GZIP can recover the structure between distinct languages,
come join me in part 2. year is to have a virtual career fair, a page at 3b1b.co. talent, where this audience can explore aligned career opportunities.
mainly in the form of featured interviews between me and the relevant teams. it's almost impossible to get a true sense of what it's like to work at a place just by
poking around online, and you learn orders of magnitude more if you have a chance to sit My hope is to give you the vicarious version of that. So, if you're curious what I mean when I say these are all thoughtful and curious teams,
I really think you'll enjoy it.