Compression is prediction | ngrok blog

Skip to main contentSearch…Control⌃KNewsletterRSS

Related posts<br>Quantization from the ground up<br>A complete guide to what quantization is, how it works, and how it's used to compress large language models

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.

In this post, I’m going to walk us through the basics of compression to understand its deep relationship with language modeling. It’s probably going to blow your mind.

Bookmark this sectionHow compression works

There are many ways of shrinking data. Take minification, for example: it works by stripping code down to the bare minimum that machines need to parse. Human-readable variables are reduced to single letters; whitespace and comments are removed.

Click “Minify” to see it in action:

sum-numbers.js<br>// Sum every number in the list<br>function sumNumbers(numbers) {<br>let total = 0;<br>for (const number of numbers) {<br>total += number;<br>return total;<br>Original source, 156 characters:<br>// Sum every number in the list<br>function sumNumbers(numbers) {<br>let total = 0;<br>for (const number of numbers) {<br>total += number;<br>return total;<br>}Minified to 62 characters — 60 percent smaller — by removing the comment, shortening the variable names to single letters, and stripping the whitespace, braces, and semicolons.

MinifyStart over

The resulting file is considerably smaller, and yet you’d almost never hear minification mentioned in the field of data compression. Why is that?

Minification is fairly straightforward: it just tosses out any syntax that’s not required by machines. But “true” compression relies on redundancy to condense data.

Consider the string “AAAAAAAAABBBBCCDAAADDDDDDDDD”of nine A’s, four B’s, two C’s, one D, three A’s, then nine D’s: there’s a lot of redundancy here. We could encode this as a shorter string by noting the total run of each character in order:

Original string: 9 A's, 4 B's, 2 C's, 1 D, 3 A's, 9 D's — 28 characters, 224 bits.<br>Replacing each run with its character and how many times it repeats gives A9B4C2D1A3D9 — 12 characters, 96 bits, 57 percent smaller.

TOTAL: 224 bits<br>AAAAAAAAA9

BBBB4

CC2

D1

AAA3

DDDDDDDDD9

Encode

Using standard 8-bit ASCII encoding, our original string requires 224 bits , whereas our compressed string (“A9B4C2D1A3D9”) needs only 96 . Not bad!

The above technique is just one compression method (it’s called run-length encoding ), but we can do much better. Actual compressors like gzip, Brotli, etc, rely on several methods to shrink data. Let’s take a look.

Bookmark this sectionThe anatomy of a compressor

There are roughly three “organs” of modern compression tools: transforms, models, and entropy coders. I’m talking about these terms as if they were clear and distinct things, but the lines can get a little blurry, and they are rarely used in isolation.

Transforms<br>Model<br>Entropy Coder<br>100101110

Transforms are the preprocessing steps that make our data easier to compress. The method we saw earlier<br>(run-length encoding) is an example of a transform, but it’s worth noting that transforms don’t always shrink the<br>data. Sometimes they can be used to create more redundancy, and the more redundancy, the more we can compress later<br>on. We aren’t going to focus on transforms in this article, but they’re still an important part of any compression tool.

Models describe the shape of our data based on the frequencies of each symbol (whatever unit we’re<br>using to look for redundancies: letters, numbers, tokens, or even binary code). For now, you can think of a model as a<br>table that maps each symbol to its probability , but as we’ll see later on, they can get a lot more<br>sophisticated.

Here’s an example based on our earlier string:

Original string: 9 A's, 4 B's, 2 C's, 1 D, 3 A's, 9 D's — 28 characters.<br>Counted by symbol: 12 A's, 10 D's, 4 B's, 2 C's.

AAAAAAAAABBBBCCDAAADDDDDDDDD<br>Each symbol in the string and its probability, most frequent first.tr:last-child>*]:border-b [&>tr:last-child>*]:border-card-muted [&>tr+tr>*]:border-t [&>tr+tr>*]:border-card-muted text-muted bg-base [&>tr]:bg-base">SymbolProbabilitytr+tr>*]:border-t [&>tr+tr>*]:border-card-muted text-body [&>tr]:bg-card [&>tr]:not-only:hover:bg-card-hover">A0.429D0.357B0.143C0.071

Entropy coders are almost always the final step in any compression algorithm and are what produce the final<br>compressed artifact: a raw bitstream , which is just a bare sequence of bits with none of the structure a file format<br>would wrap around it.

I want to focus on the last two steps, because this is important. Our data model hands the entropy coder a set of probabilities to encode your data as efficiently as possible. Probabilities go in, compressed bitstream comes out:

Model<br>SymbolProbabilityA0.429D0.357B0.143C0.071<br>Entropy Coder<br>100101110

Now, let’s be honest: this is all still a bit hand-wavy. What does an entropy coder even DO with...