CoRecursive: Coding Stories - The Hutter Prize: Compression, prediction, and the limits of intelligence

Episode Date: August 4, 2026

I texted Don about a side gig: €5,000 for every 1% you shave off a zip file. It's a real contest. For 20 years, Marcus Hutter has offered €500,000 to anyone who can losslessly compress a gigabyte of Wikipedia below 110 megabytes. Gzip gets you to 322. After that you're on your own. So we tried. Run-length encoding. Pointing back instead of repeating yourself. Huffman coding worked out by hand. Arithmetic coding, which spends less than one bit per character. Then Claude Shannon's 1951 guessing game, and a paper where an LLM beats every record and still wins nothing, because the model counts against you. Don wanted the euros. I had other reasons for bringing him over. Episode Page Support The Show Subscribe To The Podcast Join The Newsletter  

Hi, I'm Adam Gordon Bell, and this is co-recursive, and today I have here with me, which seems to be a trend. Don. Hello, I'm Don McKay, and I'm back. So I sent you a text yesterday. What did I send you? You found us a side gig that pays $8,000, $8,000 Canadian dollars per 1%. And then I blocked you. It blocked me.

So the thing that I wanted to talk about, I actually printed it out. It's a real contest. It's been around for about 20 years. and there's a prize. Losslessly compress the one-gigabyte file N-Wick-9 to less than 110 megabytes more precisely create a Linux or Windows compressor comp E-XE of the size S-1 that compresses N-WIC-9 to archive EXE of size S2

such that S-1 equals S-1 plus S2 less than L equals, yeah, 110 megabytes. It's got like a whole bunch of numbers. It's like 110,793,1. 120. So it's, it's zipping a file, basically. You're being paid to zip a file smaller than somebody else has zipped it. Oh, and then eventually you'll run into problems because you'll have to invent some other compression algorithm that will do it. Yeah, but, so the file is a gigabyte of Wikipedia data. And then whoever can make it into the smallest file and then reconstitute it,

gets money. Yeah, I think I figured this out, though. It's middle out. There's more. Oh, you're eligible for a prize of 500,000 euros, 500,000 euros times 1 minus S divided by L. Being able to compress well is closely related to intelligence as explained below while intelligence is a slippery concept. File sizes are hard numbers. The intention of this prize is to encourage development of intelligent compressors programs as a path to AGI. It's a weird thing to say. The development of intelligent compressors as a path to artificial general intelligence. It feels like saying, you know, like this crossword contest will clear the way for world peace. Step one, really small zip file.

Oh, it's just a three-step process? I mean, we may be simplifying it, but yeah. So when I was a kid, zipping was very important. I think my first computer had maybe, it was either 40 megabytes or 80 megabytes. Yeah. You would run out of space very quickly. Oh, if you wanted to take anything with you, you used to have to compress things down to put them on disk.

And then you could, you know, split the file across multiple disks. Which was a pain. Yeah. And I used Winrar for that. I remember. They used LHA. LHA. Yeah, I used to freeze and thaw things.

Anyways, here's the thing. I want to try to beat the contest, right? I don't think we can get the whole 500,000 euros, but maybe we can, maybe we can get a 1% improvement and then we can make some money. Cool. Yeah. I've never actually looked into how compression works. So this will be enlightening.

So I got my computer here, my MacBook Pro. Can you see this or it's way too small? It looks like you've done an LS and Linux on some files that are in a directory. So there's NWIC 8 and NWIC 9. If I G zip it. Have you not rehearsed this? I never rehearse. I like to just let it fly.

Yeah, let it fly. Okay, so here we go. So NWIC 9, originally this is our What was it? Originally, it is one gigabyte, and they want you to compress it down to 110 makes. Where did we get to? So we got it down to 322 megabytes from the original one gigabyte. That's pretty good. We got, it's like a third of the size, almost exactly, right? We've taken it. So that's our first step. We just, we send this in collector money. Well, I mean, you didn't meet the requirement. It has to go down to 110. Oh yeah, yeah, you're right. So we're at 322. We need to get it down. Yeah, you need to get it down to, was it 110.

So we got a ways to go. Yeah, I mean, it doesn't look like you're getting close to the target. Yeah. In fact, I did try to double compress and it doesn't, it didn't gain me anything. And here I'm using GZp with negative 9, which I believe is the... The maximum? The maximum. Yeah. So you've reached the limits of the GZIP algorithm. Yeah. So we need to do something else. Okay. So, so. I think the key thing to do is to just try to build our own compression algorithm. Because I don't think we're going to win with just GZip. Seems like somebody might have thought of that and collected it already.

The easiest way that I can think of to make a file smaller, right? Like you just have a bunch of characters and some of the characters repeat. So the easiest thing I know of is just like when you have a repetition, you take it out. Because the whole idea with compression is, yeah, you need to find a way to just... find patterns and then you replace those patterns with a symbol that's smaller. Yeah. And like it's each like compression algorithm because there's a bunch of different ones, right? They each look and look for and are good at finding certain types of patterns. And if you actually don't have those type of patterns, then it's not useful. Yeah. So like each

compression algorithm is sort of like a bet on the type of output. It's like a text file is we'll compress more than some complex binary or something like that. Yeah. And like the raw video frames of a video file can be compressed very well by like mpeg but if you just took all those raw frames and tried to run them through a zip they might not work as well because the impug encoder actually understands the type of patterns that are in a video yeah yeah like i i'm showing you basically my my little algorithm what are you seeing um you have a function that you've written that runs through a byte array and performs some kind of uh transformation on it. So I have a box for my

little Python algorithm and then sort of I can feed it input and then I can kind of get an answer or how that compresses and then I have this big button that lets me run it against the dataset from the Hutter Prize. Okay so

here's my first algorithm right? So it's just run length encoding and then I'm going to run it on this string which I assume must be in Wikipedia somewhere which just says no with an exclamation mark. So you're going to replace all of the O's

with another symbol that's less space. Yeah, this is my attempt to beat the prize, right? But isn't that sort of what GZIP probably already incorporates? We'll find out. Okay, so if I run it on my no, yeah, it changes it to this format, right? So it'll say like one N and then 24Os and then one exclamation mark. Which is less space than all of the 24? O's. Yeah. And so the compression ratio on that is it's 4.3 times smaller.

Yeah, which that's good. That's good. But if I run it on, okay, like here's Don laughing. So just ha ha ha. So now there's not quite repeat. Like there's the same characters, but they're not repeated sequentially. Yeah. Okay. So I run on that and I yeah, the open format now. Because for every letter I need to put the frequency of it and now my compression ratio is, well, I've actually made the document longer. Okay, so it's not looking good but let's run the thing

on the Wikipedia small corpus. Okay, so it actually made the Wikipedia corpus larger. So our compression ratio is 0.53. So we're doubling the size which is worse than our our zip. Yeah. The zips 2.74

times. And the record is 9.03. Yeah, we got a waste go. You got it, yeah, because you've made it bigger by... Wrong direction, I think we're good. Yeah. So it'd be like tearinging a one gig file into a 1.5 gig file. Yeah, now we know how to make files bigger.

Okay, so I have another idea. The other thing we could do is instead of just looking at, you know, letters repeating, we could assume that text repeats. Yeah, and it does because we use words and we use the same words over and over again. Yeah, and so my new idea is whenever we find a repetition of something, then instead of putting in that repeated text, we just put a pointer back to where it was. That makes sense to me.

Yeah. So in this example, which I would like you to sing. Like the row row your boat gently down the stream, and then merrily, merrily, merrily, life is but a dream. I don't think I have to read the whole thing, do I? People know row row row your boat, which has a lot of repeated words in a pattern. So yeah, I have my little algorithm.

It's just kind of basically, it's like pointers from like C, right? It's like, but in text. Whenever we have some text that repeats, we'll just say like, use that. So if we run this on row, row, row, row your boat, we end up with something like this. So it ends up with row and then it says repeat four to eight. So it's taken the two rows out and replace them with the pointer back. And then it's got your boat gently down the stream.

merrily and then the repeated merrily's become pointers back and then it has life is but a stream oh it's even catching part of letters yeah it doesn't know that it's a word okay very cool it works even better than i thought better than you anticipated yeah and then and then it just ends with this this final pointer because the whole thing repeats gives us i see like so that whole verse is now a pointer that the second verse just points to instead of okay Actually, we already ran it. So what did we get? 2.8 four times.

See, there you go. We're getting somewhere. Suffice it to say that that is less good than G-Zip. But we're making progress. Yeah, you're going in the right direction. That is a more likely pattern than our just like repeated specific letters. You've widened your pattern recognition. Yeah.

Yeah. But we can do even better, which dates back in some ways to Moore's code. The clever thing that he did. They don't all have the same length of dashes and dots. The most common letters, if you're doing a telegraph, are shorter. Are shorter. Yeah. Which allows you to compress things down.

Side note. SOS doesn't stand for anything. It was just the simplest pattern to remember. Oh, because it's dashes and dots? Yeah. People think that the letters SOS actually stand for something. Yeah, doesn't stand for anything. It's just that the three longs and the three shorts are the easiest things.

to remember. So it's the easiest pattern to, uh, to transmit. That's awesome. Yeah, I thought it was like save our, save our ship. Yeah, it doesn't stand for anything. Okay, so the next thing we're going to hit is like an important idea. It's not mine, but an important idea in compression. So in the fall of 51, there's this grad student and his name is David Huffman and he's 25 and he's going to Ohio University and he's two years out of the Navy and he has a class and the class they say, you know, you can take the final exam or you can write a term paper instead and you want to come up with the frequency, you want to come up with a mapping so that the most frequent things use the least amount of terms, but it's not just come up with a scheme like that like Morris Code

did, it's, you know, come up the provably correct way to take a bunch of text. and figure out what's most common and give it a binary mapping. So that was the homework project. The professor's name was Robert Fano, and he doesn't tell them that as part of this assignment that this problem he put to them is one that he can't solve himself. And he was the professor, but it gets worse because he had been working with a colleague on this problem,

and his colleague was Claude Shannon, who we'll talk about later. Claude Shannon invented information theory. He invented the bit. The idea that you could transmit information digitally. He invented the whole field, super interesting guy. He could not solve it either. He was a genius.

And these two could not solve this problem. And he's like, you know what? Give it to the student. If you don't want to do the final, just prove this thing. Just take this thing that we've struggled with for our career and figure it out. I think you have a quote. Huffman worked on the problem for months, developing a number of approaches, but none that he could prove to be the most efficient.

Finally, he despaired of, he despaired of ever reaching a solution and decided to start studying for the final. Just as he was throwing his notes into the garbage, the solution came to him. It was the most singular moment of my life, Huffman says. There was an absolute lightning of sudden realization. I always have this thing, like especially if I'm working on problem and I can't solve it. And then when I put it away...

Your subconscious crunches on it. Yeah. Do you know, do you ever have when you were a kid? It was this thing and it has like a whole bunch of needles. They're not sharp, but you like... Yeah. Yeah, Kavan got one of those. They're like, they're plastic now, not metal and they're like multicolored.

But yeah, it's the, the, all of the matrix of little pins. And you can push something into it and you can see the impression. Somebody told me before, you know, your brain kind of works like that. where like different areas, different thoughts, they get like activated. So you're thinking about something and it's sort of like pushing up on all these areas. If you're trying to brainstorm an idea, like there might be something in the back of your head. And so that causes an area to like light up a little bit. You can imagine, oh, here's like an idea around the topic.

And so that needle goes up. But there's also all these other things going on, like the other things you've thought of and whatever. Right. So the idea is there and it's pushed up. But so is a lot of other things. And you can't, yeah, there's too much noise. So you can't see it. But then if you walk away, you know, the other things you were thinking about,

they all sort of settled down. And then you can see, like, oh, there's that idea. The other needles have fallen away. And I can see this one is just jetting up a little bit. Yeah, that makes a lot of sense. Right. So his paper that he submitted became one of the most cited papers in computer science. I'd like to see.

I was like, oh. Did it? I mean, I knew you could. Did I tell you that this is an unsolved problem? And that Claude Shannon, the smartest. guy that I have ever met could not solve this. I mean, you did okay. Yeah, we'll give you a pass on the class.

Cool. So this idea, though, uh, Hoffman, it becomes called like Huffman encoding. And I mean, it, it's used everywhere. His paper that he submitted became one of the most cited papers in computer science. So this is used inside of GZIP. Yeah, he never patented it or anything. So it was just like a concept he, you know, ended up becoming. computer science professor and leading a department

probably helped that he had solved this great thing for his career, right? So here's my version of that. Benny beat the best bet. It's like a tongue twister, but it does tie into all this, right? If I run it, it's going to go through and find

what characters are the most frequently, and probably not surprising, there's a lot of B's and E's in here. And so it ends up, oh, and T, apparently T is the most common. I would have thought it was the B. You can see it ends up with this table. Right, and it assigns it a binary code.

1-0-0-1, has a four-letter code. And like the other thing that's happening here that's very valuable is we're not encoding any of the other stuff. We don't have to worry about and per sand or whatever, right? We only need to encode the things that are actually in the text. This is all capitals. We don't have to encode lowercase. Like we're only focused in on the most frequent characters. Yeah, including space.

Including the space, yes, which we have. But yeah, how much smaller is this version? So it says it's raw bytes. It was 8 bits slash for sim, and then it's 2.7, so 66% versus raw. So we're 66% smaller. Let's try to run our corpus. So when we run this against the Wikipedia standard, we've actually gotten a smaller file, which is good before we were increasing. Yeah, 1.56% times.

Sweet. So we're making progress. We have a long ways to go before we beat the prize. Get that sweet, sweet. 5,000 euros. Got to get that sweet euros, but... I like how it's in euros, but like when you texted me about it, you did the conversion on my behalf to put it in the end dollars.

You're like, oh, euros, he's not going to know that, so I'm going to do the conversion here. It's about 8,000 Canadian dollars. I didn't know what a euro was worth, did you? A euro? No, not like offhand. Like, I do know that it's about one and a half. So the first algorithm we did was run length encoding,

which was basically, like that didn't work well. Then we did the pointer one. Which worked well. So the pointer one. Actually did compress something. Yeah. And so that was invented by two information theorists, Jacob Ziv and Abraham Lempel. Do you know what year? 1977. That was a long time ago, right?

And then the one we just did, the Huffman encoding, was obviously by this David Huffman. But you put those two things together. Guess what you get? A more efficient algorithm? that is that is very much the case g zip or zip files okay so like everything that's that's the common standard that's the common standard is the zip file and the zip file just uses those two algorithms so those two algorithms were combined into this compression algorithm which i believe was called

compression program that i believe was called arc and it was big in like the bbs days there was like a free version of this ark archive builder i mean it was just the most common format. And then there was this guy named Phil Katz. So yeah, in the late 80s, before, you know, the internet, there was all these BBSs. And so compression was important because you just had dial-up. There was this arc format and it was, you know, it was usable by this company called C. Bill Katz lived in Milwaukee and he was kind of a really good hacker and he liked to write things in assembly. And so he wrote his own version of their archiver. And he called it P.K. Ark, with the Phil Katz archive. Okay, is that where PKZIP comes from? That's where PKZIP

comes from. Okay, I put that together. Yeah. And so it does exactly what arc does. It does the equivalent algorithm, except because he hand-writes assembly, it's like super fast. So people start using this P-K arc. Everybody switches to it on all these Bolton boards. So this C-company gets mad, right? He's just like replaced their thing with a better thing. Right? So they sue him because, you know, he's copied what they've code and released it. And it becomes this big court case. And I don't know all the details of it, but apparently they find that there is some comments

in their source code where there's typos and then they get his source code and he has the same typo. Oh, to try and prove that he just copied it? That he just copied it and then made some improvements. So he loses the lawsuit. And out of frustration, I assume he's like, well, F this nonsense. he rewrites, right? It's just these two algorithms that we just went through.

He rewrites it in like a text file from scratch and shares it with the world. So now there's an implementation of how to do this that is unencumbered and, you know, has no cost. And he kind of did it, I think, a little bit of spite. But yeah, this became PKZIP. And because the P and K was for Philip Katz and everybody just adopted it because it was free and it also was fast because he was good at what he did. And yeah, did you have PKZIP files? Yeah, of course.

I never knew what it stood for. No, I didn't know what it stood for either, no. Yeah, so because it was unencumbered, that's what made it popular, right? Anybody could use it. It was open, yeah. It was open. And so, you know, you get it used in WinZip. You get it, you know, when the GNU project is trying to open source things, they're like, oh, we can use this, right?

So that's where you get GZIP. The algorithm, the combination of the two of them is called deflate. apparently. Yeah, and then his life kind of went sideways. I guess he had a drinking problem. And yeah, he was found dead in his, he was found dead April 2000 in a hotel room in Milwaukee. He was 37 years old. Yeah, he did not make it very far. That's sad. No, it's super sad. He was clearly talented at what he did, but I mean, addiction can be a challenge. But he left his mark on the world, right? Like, everybody's still using the software. So with what we have so far, we can compress a file and do pretty good.

We won't win our contest. But like, if I have a file where the character is used a lot, I don't have a way. What's the way to say it? Imagine this, right? So I have a 25-sided dice. Does it such a thing exist? Most often, it's a 20-sider.

Funny side, okay. Then it goes up to, I think, I think you can get a 25. It's odd, but like, I think the next step up is like a 30. Yeah. Okay. So we have a D-20. We have letters on it. But all the letters.

are A, except for one, which is a B. Okay. So I roll it. I get like A, A, A, A. You got 95% chance of getting an A. Yeah. And so if I make text like that, what we've created here doesn't necessarily help, or there's a different way, which is called arithmetic coding.

Yeah. So arithmetic coding has this idea. The math is a little bit more complex, but it tries to look at, why don't I just encode what's surprising? And so the way they do that for this is very simple. Here's the compressed format. What do you see in? It looks like it's just noting where the Bs occur at which position.

Right? So you never have to say, A, A, you just say, here's a B, here's a B. And everything else is A. And everything else is A, which allows you to get below one bit per character. Yeah, I mean, that's the stats for this test data. But I mean, like, the test data is basically like a ton of A's and a couple Bs. Yes.

So this example is very... Yeah, it's very specific to the scenario. But it does come up in the real world where something is so common that you want to actually encode it at less than a bit of information. I can show you. Here's my results table overall.

Here's our run length encoding. This is on the big file. So our run length encoding made the file twice the size. So that wasn't very good. Zip makes it more than... a third of the size, right? So 2.74. This is our arithmetic coding.

Which is 3.96, almost down to a quarter. It's funny. So I had this guy, Jan Cola, I had this great episode, right? And he was in France, and he ended up building his own compression system that was better than Zip. And it's called

the ZST. It's the Zed standard. And it uses this arithmetic coding concept. And he was trying to explain it to me how you can store a character in less than a bit, which is what we just showed, right? We're able to compress all those A's. It's easy for me to understand it in the A example. It's harder for me to understand how it works.

In the context of an actual document. In the context of an actual document, how it works. But the way it ends up working out mathematically is that you only use as many bits for a character to do with how surprising it is. And so I showed an extreme example where the A is not surprising at all. So all we're encoding is the B. it's able to use fractional bits to encode things. And so this idea had been around for a while.

There was some patent problems that allowed people that made it problematic for people to use it. But he brought it to common usage by making an open source project, allowing lots of people to do it. And he went from just being a hobbyist person building his own compression algorithms to working at Facebook. And this algorithm is now used everywhere. That gets us to hear. Yeah. We are almost at four times. Yeah, that would be like if you're down to almost a quarter, right?

So like around 250 bags. Yeah. So we still have a ways to go, I guess. Yeah. I don't know. That's where I run our ideas. What do you got? That's where you run it up.

Let's find somebody who's figured it out and bring them on the podcast. Yeah, exactly. All right, Don, what do you got? I did the first part. You did the second part where we win. Question mark, question mark, question mark, profit. Exactly. Exactly.

I don't know. I guess a combination of approaches. I mean, it's either that or coming up with like a new idea on how to compress something. It seems like compression at its core is just recognizing patterns and replacing them with something smaller. Or another way to phrase that that people have used, which at first I found confusing. The Huffman coding, right, is it's taking this idea. It's predicting that there is an uneven distribution of characters. And the run-like encoding, you hit that immediately because it's,

expectations are for repetition. It worked very well on one thing, but on the rest it failed on. A compression algorithm in some ways needs to be able to predict what the file format is going to look like. Yeah. So if you're encoding something that's like an English language document, then there's certain predictions you can make around the structure of that document because it's using English as a language. You were on to something. Sometimes I'm smart. Coffee's kicking in. Yeah, man. The challenge is always that you're too smart. I have to be just dumb enough. Yeah, because I bring you here to try to explain something.

And you're like, oh, yeah, what if they did that? You're like, you're like Huffman with the papers. Like, I think I got something here. They're like, Jesus Christ, we've been working on this. And you just did it in a weekend? Okay, I have the next thing, though. So it's 1950 and there's Claude Shannon, right? And Claude Shannon has this problem that he came up with.

So he had defined the bit. And he had come up with this idea about, transmitting information. He worked at Bell Labs. What does it say? He proved that every stream of information has a floor, an irreducible bottom, the minimum important information in it, which is called entropy, right? So the theory says that there's a way to make things smaller. He was never able to figure out if there was a bottom. So he was kind of dancing around this idea of compression, right? If you're transmitting information, some of it is important, some of it is not. Right? Like, if we're talking on the phone and you miss a word, I probably still know what you're saying. But if I miss

every other word, sometimes I'll put it together, but sometimes I won't. Right. And so his idea was it's entropy. It's this transmission of information. He's an information theorist and that there's essential information you're transferring and if we remove too much, it's gone. It's an easy idea. Think about, but I mean, the math round is very complex. So to figure out his estimate for this amount of information. He came up with a game. So we have here some text. The Big Sleep. The Big Sleep by Raymond Chandler. Raymond Chandler, are you familiar with him at all? He, no, he wrote these, like, noir detective novels. Okay. I think he's one of the, like, there's several authors of them, but he was one of the most famous, right, where it's like a smoky room and the names on the door

and damsel in distress. So here's the game he comes up with. His wife is sitting where you are. He's sitting here. He reads her part of the sentence, so it says, it was about 11. Now, the game is you need to guess what the next letter is. And going back to where we were before, just like our text documents, we're going to limit it to like lowercase letters and a space, because we're just going to reduce the domain to make a little easier. Can you guess what the next letter is? Oh, for O clock. All right, let's try it. That's right. So you got O on the first guess, and he records these numbers. Oh, okay. So on that letter, you got it on the first. So what's your next guessed. I think it was o'clock. Wouldn't it be like an apostrophe? So we don't have apostrophies because I just,

I reduced it down to make it simple. C? Got it. L. L. L. O. C. Got it. Okay. And so you were able to guess all the letters on the first try there. But okay, what's next? Space. A for at night. Nope. I for in the evening. Oh, ooh. I think you got it, right? The wild thing is how much little information is actually needed to transmit the English here. You were able to predict it. Because of common sayings and phrases. The predictable letters cost one guess is what he says. A surprise letter can cost five or six. You didn't even get that high. You only got as high as two. But he says, on a demonstration passage, 100 plus letters of Raymond Chandler's book, the guess was correct, a one, about seven out of ten times. Okay. Like, I find this part hard to explain. It's hard to

explain. What he's trying to say is there's actually, if you try to encode this information as like asky or binary or whatever, it will take a lot of numbers. But actually a lot of that is unnecessary. The actual surprising things are very small. You guessed almost all of these from the get. And it took you only two guesses to get to some of them. So here's his crazy idea in 1950. This is the guy, by the way, who couldn't solve the Huffman thing. So what he said is, imagine there's a second Don. I put this same problem to Don number two. If I assume that Don will always guess the same order, I don't actually need to know what the text is here. I only need to know how many times I need to ask Don to guess. Right. And so I've just compressed using Don. Yeah, but like you were able to

do this because you knew what the correct answer was. So you're saying I wouldn't be able to decompress it. Okay, but here's the, here's the tricky part. He's saying no, that's not the case, right? Yeah, I guess I got lost to like that's where that's where I'm that's where I'm struggling. So like yeah, I get that I guessed correctly most times. Because I was given the beginning prompt of it was about 11. I could kind of extrapolate what the rest of the sentence was. And when I guess you're able to check against an uncompressed version of the document. So tell me I was right or not. Otherwise, how do we know? Yeah. So you compress the word O'clock. Given given it was a little. 11, you compress the word o'clock to six ones. And so his idea is to transmit the word o'clock that it finishes, that it follows from 11. I could just write down those six ones in the beginning. It was 11. And then you'd have to have somebody like me on the other end. You have to have a dawn on the other end that would be able to do what I just did. And we played the same game, but I don't actually know the answer this time. I know that when you say your first number,

if you got the number two before, I have to say like, no, try again. And that second number is the number that goes in. So the person on the other side doesn't actually need to know the answer. They just need to know how Dawn would guess. Would guess. This is messed up.

Yeah, that's messed up. But yeah, I get it now. But he's, I mean, he did this in 1950. So computers were pretty simplified, but he called it like a digital twin. You know, if we had a Don on the other side, an exact Don duplicate, I could decode the sentences

without knowing what it was, because I would know your guesses would be the same as his. In his thinking, what he's saying is he identified a range based on a human, and he published this bracket 0.6 to 1.3

bits per character. But it's clever. He managed to figure out how he could use, well, a physical person's brain as a compression mechanism. Yeah. And it would be that specific person

because each code would be individual to a person's thought process. Because if it was a slightly different person, they might pick a different letter. It'd pick a different letter. And it would all be blown out of the water. But the interesting thing is,

from his perspective, then, all of these compression algorithms become prediction algorithms, right? Because what you're trying to do is predict what comes next. And you're just really good at predicting English language because you understand it very well. So that means that our other algorithms, the way the Huffman encoding tries to predict things

is by looking at all the characters and seeing which are most common. And that's its power to predict things, as it knows this is the most frequent thing. Well, I don't think that the, I don't think that it's guessing. It knows what the answer is. It knows that T occurs as many times.

This is the confusing part. When you encoded that word, you came up with like one, one, one, one, which meant it was your first guess. It was your first guess. But if you think of the Huffman table as a prediction, then that means by default, the very first thing it predicts is T for any answer.

But if T is wrong, then it predicts the second one. E. Yeah. And then like these ones, it takes a while for it to predict it. So it goes further down. So it ends up with a similar encoding as you, but it takes it a lot longer, I think. Yeah, no, I understand.

You take the table it came up with, but I thought that it was making this table so that it could replace the character with a different code. It is. So it's not making a prediction. it's doing a substitution. I guess. But you could use its same information as a prediction

because like it's already kind of done the work to find out what the most common thing is. And instead of using that as its prediction, it's using that as a, oh, well, I'll replace this with a small code. And the ones that are least, I'll replace those with a larger code. It's not using it to like predict the actual letter. Yeah. But there's a way to view them that they are the same, right?

Another way is it saying like, oh, you're just, it's treating you as a lookup table when it's saying when Don says one, it's like, well, how do I look up one in the dawn table? Like, well, you just ask them, like, given the sentence, what's the first letter you'd come up with? But it gets at this key thing, right? Which was the guy on that Hutter Prize. What did he say?

Do you have that first quote? Something about intelligence and compression being the same thing. Being able to compress well is closely related to intelligence is explained below, while intelligence is a slippery concept, file sizes, or hard numbers. Yeah. So, like, he's saying that past, these certain easy tricks, the way that you compress a file actually has to do with like intelligently understanding it, which is what you did as part of that game. Yeah, because I understood

English so I could make a educated guess. So the whole point of the prize is that if we pay people to compress files smaller and smaller, they're going to have to come up with machines, algorithms that actually understand English language text. Yeah, because I mean, if I didn't understand English, I would just be picking a letter at random. Well, not exactly. I guess because some letters are more common than others in English. Yeah. Or you'd get a little better. You'd do the Hoffman thing and you'd be like, well, the most common letter is A. So I pick A. That's the relationship, right? Earlier we had the tongue twister about Betty. So Betty was Cloud Shannon's wife and, like, he tested this theory on her. So Betty was the person who did the guessing. Yeah. And then he made the paper out of it.

And then Cloud Shannon is a super interesting guy. I should do an episode on him, but he built a flame-throwing trumpet. So when you played the trumpet, it shot flames out of it. He built. the machine that had a button on the top, and when you press the button, a hand came out and then closed. There's a, yeah, there's a toy you can get now. So I think it's based on something he made. I mean, his was very simple. It was just like a switch, I think. And when you flip the switch, like a hand would come out.

Oh, my back, yeah. But, yeah, from this came the concept of entropy or surprise. The thing that he got down in information theory was like the meaning of a message is how surprising it is. So the letters where you had to, where you got it the first try. were not very surprising. And so there was actually very little information there. So they could be compressed very small. If you had to guess a lot, then that meant that that character was surprising.

And so this notion of surprising puts a cap on the size that you can compress things. So our AAA and then occasionally a B, the A's were never surprising. So we only had to encode the B's. In 1951, he figured all this out because he didn't have YouTube. he had to sit down and think. And think about something. Yeah. He couldn't just like scroll a bunch of silly videos.

Yeah. I mean, I think that he might have been smarter than the average person in general. Probably. I don't think if I was back then, I'm like, oh. But, okay, here's the crazy thing, right?

So this is my benchmark of all the things we ran. So run length encoding. The actual record for the Hunter Prize is under a bit, right? It's under a bit. It's at 0.88. But in 1950, Claude Shannon, And he's like, I think this is the range on English language. And his range was 0.6 to like 1.2.

He was like, that's the floor. You can't get any lower than that? That way you say? That's his theory about English language and the amount of information that's embedded in it based on humans' ability to pattern match. But like, it seems to be holding, right? Nobody's gotten past his 0.6. Intentionally, this AGI guy created this Hutter Prize. he's trying to say, can you make something that will understand English?

Because he said, oh, it's really hard to measure how smart something is, but it's very easy to measure the size of a file. Like, it's very definitive. And so, like, if you can get past all of these levels and it keeps getting smaller and it starts getting towards Shannon's range, that means that whatever's doing that tipping must understand English language. Yeah, must be very smart. Must be very smart.

Turns out compression is very related to intelligence, at least in this case where you're compressing English language. based on your ability to predict what the next letter is going to be in the English language. Yeah, but I think I found a way around it so that we can win our contest. Let's get that money. Yeah, let's get that money, man. I made this file. Basically, I generated a file and a compressor for it, and this is like a sample of the file.

We could open it, but it's just... 4.1 megs. Yeah, it's 4.1 megs, and it's full of just like random... Hexodemortem. Yeah, I mean, this is in hexadecimal. So it's not text. Okay. And then I tried to compress it.

So zip file pressed at 0%. In fact, it got a little bit larger. Arithmetic coding, like the ZSTD, got it to zero. But then my algorithm, here's where we claim the prize. How did my algorithm do? It got it a lot smaller. Was that 486,000 times? Well, there you go.

The question mark, question mark algorithm. Yeah. But it's a trick, obviously, right? I use the random number generator and just generated a whole bunch of binary that I wrote to a file. Okay. And then my compressor, basically, it takes that number. It finds what the seed is that was used, and it writes that to a file.

And then so all my decoder does is read what the seed is and run the generator function again. But it's a random generator function from the same seed? Yeah. Oh, well, that's how Minecraft works. And anybody with the same seed can generate the same Minecraft world, as long as they know the seed. So this is the same trick I've done here. they, I've made a file full of... Minecraft already figured of Atlanta.

I can reduce it just... To the seed, yeah. And then I can re-expan it to its seed. And so out of all of the possible data in the world, there is like one very specific set of data that this thing dominates. It makes it like... It's very hyper-specific to one thing.

If you could make one that's hyper-specific to that one file, we can win. It's sort of an example. You know, if you just had this file and you tried all these algorithms at it and you saw it never got smaller, you would think, oh, this data is actually not able to be compressed. There's no patterns in it.

But in fact, there is a pattern. You just don't know what it is. So Kolmogorov complexity, invented by Kolmogorov, it has this idea that you can measure the information in a piece of data by the length of the smallest program that could possibly describe it. So in my example here, right, I have this crazy amount of seemingly random data, but actually it can be described by this program that's just like use, Generator C-89.

But that's true of a million things, but it can also be shown that, like, there's no way to figure out if you've determined that that's the shortest program. You just can't know. But there's no way to prove that it doesn't exist. But it sets a bound on things. And that could be your compressed form.

Like, instead of coming up with a special format, you just send over the program that if Ron reproduces it. Reproduces the entire document. But this is all going somewhere, I promise you. Does it end with me getting $5,000? Well, we got to split it, don't we here? Yes, no, that's true.

That's true. So there's a, I did an episode about this guy named Sluat. It's a great episode if you haven't listened to it. But Slew had this idea for a movie playing system. So people could watch movies in their homes. It was like in an earlier era. And he said he could compress videos, you know, into, I think it was eight kilobytes. That would be the size of the movie.

He was trying to explain how his invention word, because they're like, yeah, you can't store a movie in eight kilobytes. but it's just not possible. And he said, oh, it works like this. If I were to send you, you know, a picture of the Mona Lisa, there's a lot of data there, you know, a lot of different pixels. But if you and I had the same art history book and I wanted to send you the Mona Lisa, I could just say like, hey, look on page 76, and there it is. So his, what was his source, though, for movies, just like a collection of pictures?

Yeah, I mean, there's not enough data to, like, encode all movies. It's actually like a clear problem in compression to say like eight kilobytes like even as a number is not that big of a number. There's more movies than even if you just were storing like where to go get the DVD and put it in your machine. Like you would run out of numbers. And he had some demos. He had like some sort of home entertainment system where you could take a movie and you could play it from this eight kilobytes. And it became this big thing. People invested in it.

And then, you know, he ended up dying and they never found how the system worked. But the idea makes sense, right? He's saying, like, if we have some shared information, then I don't need to transmit every single detail because we share it. And the, you know, the Don thing sort of does that, right? Because you're... Similar to, like, a cipher? Because a cipher is, you don't understand this text,

but if we both share a common key, then we can reconstruct what the message would be. Yeah, like, I think it is, right? But it presents a problem to the whole prize. If Wikipedia is already... Yeah, we'll just store, like, the link to the Wikipedia URL. I feel like that they have to have something in the rules that prevents that from happening.

They're not going to give you money for that. Specifically, what they have is that it was that weird math that you had at the beginning, which is the program, its size counts to. The size of your program S1 compresses the file to the archive EXE of the size S2. So, yeah, it's included. Yeah, so if your program gets too big and complex, like you need to make that up in the advantage of compressing. So if we're thinking of this guessing game we did where we had some texts and then we have to guess what the next words are, can you think of anything that's good at that? Like all of our phones?

Yeah, yeah, like predictive text. And predictive text does, you know, it has a dictionary of some sort that's shared, right? Because it knows English and it knows the, it knows grammar to a certain extent. and it's all been kind of programmed into like this common database that they all share. So whenever you're typing, it makes a predictive suggestion. Yeah. So then whatever the size of that dictionary is, right, you need to pay that off in smaller compression. Or, yeah, like a smaller file.

But what else? Like what else makes predictive text? Yeah. Gayi. Yeah. And LLM is exactly this where you could give it. Here's the characters I have so far, like give me some more. And so his idea, I mean, the contest is 20 years old.

But this is what's super cool to me. He thought, hey, this will reveal something about AGI and human understanding. And I assume people are like, due to it. We're just zipping files. I don't know what you're talking about. I mean, yeah, that's exactly what I think I said at the beginning of podcast. Like, yeah, it's just zipping files.

I mean, it's probably something that's required, right, in the grand scheme of things. But it's not going to be something that directly relates. And now it does, yeah. But here it does directly relate, right? So this research group, use an LM to make a zip file. So they made something called like LLM zip. And instead of using this idea of like a dictionary of common words, they just had an LLM in there.

And so you can understand exactly how this would work, right? So they're using, instead of having a dawn, they have an LLM. They have an LLM to it. So they can say like, hey, we have this text, guess the next character. And when it's right, then that's easy, right? And when it's wrong, guess again. Guess again until they get it.

And if the LLM is good at predicting that type of text, they now have the Don on both sides that can decode the thing. And this LLM Zip was able to beat like all kinds of records. And I think it did well on image compression as well. So blew all kinds of standards out of the water. Except the problem is that that LLM like base file is like gigs and gigs of data. Okay. It's like 17 gigs of data or something.

So like the S1 and the algorithm there would mean that they wouldn't get any money. So they wouldn't get any money because of the size of it. But what they did find that intelligence. is helpful for compressing things. They proved that Claude Shannon's theory works out. So we're looking at a table of different compression sizes. So our run length and coding made files bigger. Zip files made it 2.8, 2.74 times smaller.

Arithmetic coding, which was our ZST, it gets almost to four. The record is here at 9. This is LLM Zip. So LLM Zip used a 13 gigabyte decompressor. You needed to give it one of these early LLM models. But if you... you ignore that, it got 11.27. Okay, so it's by far the smallest. Yeah, so it made the file way smaller because it is way more knowledge of English language. It's like it's dawn. It understands how

English language works, maybe not as well as you. But if you need a 13 gigabyte file to decompress a one gigabyte file, you haven't really gained anything. Exactly, right? You've just kind of like offset all of that information inside your decompressor. But there's all kinds of ways that you could think it would be useful, not for this contest, but I mean, yeah, you could, we could all have a 13 gigabyte file on our machines and use it to compress and decompress anything English text. Yeah, if it was a common thing that everybody had. It would do very well.

But you'd all have to have the same version, right? It has to be the digital twin. So this guy made something called TensorFlow Compress. So TensorFlow Compress, it doesn't really violate any of the clear rules. It takes the Wikipedia file, and as it's decoding the file, it trains an LLM on it. And then it uses that LLM to do the trick.

The problem is it needs a very expensive cluster of GPUs and has to run for like days. Oh, yeah. And so it violates the theory, and it's very impractical to take your one gigabyte file and to spend. It'll be a couple days. Yeah, seven days on hundreds of thousands of dollars worth of equipment

to decompress it. But so the current record for the contact is this C-Mix, and that's the one that's at 9. And in it, it uses this same idea of trying to predict what the data is, but in much simpler fashion, and it has actually 2,000 different little algorithms that try to predict what character is going to go next, and then it has them all vote.

And so some of them are really good at understanding, like Wikipedia, markup language, some are good at understanding this or that, and they all vote. I don't know, I went deep on this, Don. there's people who say that this Hutter guy should change the prize because he came up with this test for AGI. To modernize it? To modernize it because these limits that we talked about,

like LLMZIP doesn't pass the test because the files are too big. But you could imagine changing it, right? You could imagine that he says, okay, here's, I have 10 separate one-gigabyte files of Wikipedia. I'm only going to give you one of them, run your thing on that, and then all tested on all 10, and like the cost amortizes over all 10, right?

No, I guess that wouldn't work because it's 13 gigabytes. If the amount of data that you're using is bigger than 13 gigabytes, then you might be able to pay it off, right? Like if it's like a petabyte of data. We're creating AIs now, and they're just at a different scale. Like there's not one CPU, there's like thousands of GPUs, and it's not, it's petabytes and petabytes of data. Yeah.

And you came up with this very cool, very specific, can't cheat at test because a file size is a file size. But you put the constraints as such that like nobody takes it seriously. They're outdated. Yeah. Yeah. No, I think the modernizing test would be, right? Because then it gets people thinking about things in the modern context. And when we when we talked earlier, it's about the pre-training wall and how the LLMs had consumed all of the internet and they were out.

You know, this is in some ways a different view of things. Because here he's saying like every piece of data counts. You can't just use all of the internet to answer this question. You need to learn the structure from just this. And every extra bite you add of looking things up is cost you. So he's on the other side of the coin of like, what is the like maximum information that we can suck out of this data? Yeah.

Same as that Claude Shannon with saying like, what is the minimum we can send and extract the maximum from? Like, this is, compression turns out to have a lot to do with extracting the maximum amount of data from. The minimum amount of instructions. Yeah. It's also the challenge just that, like, it's very hard to explain why getting better at file comprehension has to do with intelligence.

It's very obscure, really, or obtuse, actually figuring out how to make a file smaller, somehow bumps up against intelligence. Like, that's a very odd thing. I don't know. Initially, you wouldn't come up with that. But then after you explain that, oh, well, we can actually make things a lot smaller if we just knew how to predict what would be the next, you know, the next piece of data. Yeah.

And you're using the brain, right? You're using some kind of intelligence to come up with, to make the prediction. Yeah. And I don't think we're actually going to make any money, Don. No. I didn't think we were going to make any money when you texted me. It's a, it's a ruse. I brought you over here

because the thing I wanted to talk about was this idea. Yeah, that compressing documents is basically predicting and that that requires intelligence. This is why the guy running this Hutter Prize is not, in fact, a high-performance computing guy. He's an AI person. And so he said 20 years ago that he would put, yeah, half a million dollars

on anyone that compress Wikipedia. Because he had already come to the conclusion that a requirement of being able to compress English Wikipedia would be some kind of command of the English language, some kind of intelligence behind it. Yeah. In fact, he was making this bet, you know, that compression and understanding are the same thing in a way, that to make a file smaller, you need to understand the patterns in it.

If you understand the patterns in a giant swath of Wikipedia, like, how is that different than actual intelligence? It took me on this wild goose chase. I learned a lot about compression, but I didn't get any euro. Right? There's no euros involved. I'm very upset that we didn't get any money. But I don't know. It's super cool. If you haven't listened to the two episodes, one about Sluat, one about one about Yon Colette,

you know, one legitimately rocked the world of compression. One, you know, thought he did. But it's cool how we can take just an idea that seems simple and something you use every day. And if you start pulling on it, it feels like in every area, if you look into it, there's actually a surprising amount there and it will connect to a lot of other things. areas you can learn about. I don't know. Maybe I need a better hobby. I'm sorry we didn't make any money. No, it's fine. I got a coffee out of it. That's good enough for me. Yeah. And until next time, thank you so much for listening.