Surprise, bits, and why prediction is compression

Measuring surprise

If something you were sure of happens, you learn nothing. If something you thought impossible happens, you learn a great deal. Information theory turns that into a number: the surprise of an outcome with probability p is

surprise = −log2(p)   bits

A fair coin landing heads has p = 0.5, so −log2(0.5) = 1 bit. A specific card from a shuffled pack has p = 1/52, so 5.7 bits. An outcome with p = 0.9 is worth −log2(0.9) = 0.152 bits: mild. An outcome with p = 1 is worth exactly zero.

Why a log rather than, say, 1/p? Two reasons that pin it down. Surprise should be additive for independent events: two fair coins should be twice as surprising as one, and −log2(0.25) = 2 gives exactly that where 1/p would give 4. And certainty should cost nothing, which the log gives for free. There is a theorem that the log is the only function with these properties, but the additivity is the part to keep.

Bits are yes-or-no questions

A bit is one answer to a well-chosen yes-or-no question. Locating one item among 1,024 equally likely ones takes ten questions, and log2(1024) = 10. Locating one token among a 32,000-word vocabulary with no information at all takes log2(32000) = 14.97 questions.

A language model reduces that count. If it assigns probability 0.25 to the token that actually comes next, that token cost it −log2(0.25) = 2 bits rather than fifteen. If it assigned 0.001, the token cost 10 bits. The average of those costs over a text is the model's cross-entropy loss in bits, which the next two lessons build up properly.

Nats

PyTorch, TensorFlow and every paper's loss column report surprise in nats, using the natural log instead of base 2. One nat is 1 / ln 2 = 1.443 bits. A loss of 2.0 nats per token is 2.89 bits per token. Nothing about the model changes; only the unit does. When somebody quotes a loss without a unit, assume nats.

Prediction is compression

Here is the fact that a product page will not tell you. Any probability distribution over messages can be turned into a code in which a message of probability p is written in about −log2(p) bits, and no code can do better on average. The technique is called arithmetic coding, and it is not exotic; it is inside every video codec you use.

So a model's loss in bits per token is the size it would compress the text to. Take a model scoring 2.0 nats per token on a corpus of one billion tokens:

2.0 nats × 1.443 = 2.89 bits per token
2.89 × 1,000,000,000 = 2.89 × 10^9 bits = 361 MB

The raw corpus, at roughly four characters per token and one byte per character, is about 4 GB. The model has compressed it eleven to one. For comparison, gzip gets ordinary English to about 2.5 bits per character, which is roughly 10 bits per token, so this model is compressing three and a half times better than gzip. Claude Shannon estimated in 1951 that a fluent human predicts English at about one bit per character, which is roughly four bits per token. A modern large model beats that.

You can measure the gzip side yourself in four lines, and it is a good number to have in your head:

import zlib
text = open("some_english.txt", "rb").read()
bits_per_char = 8 * len(zlib.compress(text, 9)) / len(text)
print(round(bits_per_char, 2))    # about 2.5 for ordinary prose

Two honest limits

Surprise is about the model, not about the world. A rare typo costs a model many bits because it did not expect it, yet the typo carries almost no meaning. High surprise means "this model predicted poorly here", nothing more profound. Two models can assign different surprises to the same token and both be reasonable.

The compressor must be counted. The 361 MB above only decompresses if the receiver has the model. A seven-billion-parameter model is about 14 GB in half precision, forty times larger than the compressed corpus. As a way of storing one billion tokens, the model is a terrible deal. The claim that stands is narrower and still striking: per token, a good predictor and a good compressor are the same object, and improving one improves the other by exactly the same amount.

The arithmetic to carry forward

Surprise is −log p. Bits use base 2, nats use base e, and one nat is 1.443 bits. A loss is an average surprise. That average is also a compressed size. Everything in the rest of this module is a consequence of those four sentences.