Prediction, Compression, and Intelligence

Connect probability to ideal code length, separate source entropy from model mismatch, include model complexity, and state the limits of compression as a view of intelligence.

Probabilistic prediction and lossless compression measure the same uncertainty in two forms. A model that assigns high probability to outcomes that occur can describe them with fewer bits on average. This connection explains why prediction can reveal structure, but it does not make compression a complete definition of intelligence.

Probability Determines Ideal Code Length

An outcome assigned probability $p(x)$ has ideal information content

\ell(x)=-\log_2p(x)\text{ bits}.

“The ideal code length for outcome x is the negative base-two logarithm of its probability.” Doubling the probability reduces ideal length by one bit; halving it adds one bit.

Probability	Ideal length
$1/2$	$1$ bit
$1/4$	$2$ bits
$1/8$	$3$ bits

These can be literal lengths for a suitable binary code. Other probabilities, such as $0.6$ , give fractional ideal lengths. Prefix codes use integer-length codewords, while arithmetic coding over long sequences can approach the fractional average predicted by logarithms.

Exercise: Convert probability to ideal length

What ideal code length corresponds to probability $1/16$ ?

Check the code length

Compute it first, then check your number.

HintWrite the probability as a power of two

$1/16=2^{-4}$ .

SolutionThe ideal length is four bits

Because $1/16=2^{-4}$ , $-\log_2(1/16)=-\log_2(2^{-4})=4$ bits. Four binary distinctions identify one outcome among sixteen equally likely possibilities.

Better Prediction Gives a Shorter Average Description

Suppose a binary source produces $A$ with probability $0.75$ and $B$ with probability $0.25$ . A code matched to the source has ideal average length

H(p)=-0.75\log_2(0.75)-0.25\log_2(0.25) \approx0.811\text{ bit per symbol}.

A model that predicts both symbols with probability $0.5$ spends

H(p,q)=-0.75\log_2(0.5)-0.25\log_2(0.5)=1

bit per symbol. Its mismatch costs about $1-0.811=0.189$ extra bit per symbol, exactly $D_{\mathrm{KL}}(p\parallel q)$ .

The model can remove mismatch cost by learning the source distribution. It cannot remove the source entropy while remaining lossless: genuinely uncertain outcomes still require information to distinguish them.

Matching predictable source structure can shorten average codes; genuine source uncertainty remains.

Exercise: Calculate excess description length

A source has entropy $1.6$ bits per symbol. A mismatched predictor gives cross-entropy $2.1$ bits per symbol. How many extra bits does it use over $1{,}000$ symbols on average?

Check the excess length

Compute it first, then check your number.

HintFind the excess per symbol first

Multiply $(2.1-1.6)$ bits by $1{,}000$ symbols.

SolutionThe mismatch costs 500 extra bits

The excess is $0.5$ bit per symbol, so $1{,}000(0.5)=500$ extra bits on average.

Context Makes Repeated Structure Predictable

For a sequence $x_1,\ldots,x_T$ , an autoregressive predictor gives the ideal description length

-\log_2p(x_{1:T}) =-\sum_{t=1}^{T}\log_2p(x_t\mid x_{<t}).

“The ideal length of the whole sequence is the sum, over positions t, of the negative log probability assigned to token x sub t given all earlier tokens.” A context that makes the next token easier to predict shortens its contribution.

Suppose a four-symbol sequence receives conditional probabilities $(0.5,0.9,0.9,0.9)$ . Its ideal length is

1+3[-\log_2(0.9)]\approx1+3(0.152)=1.456\text{ bits}.

A uniform binary predictor would spend four bits. The contextual predictor saves about $2.544$ bits on this sequence because it captures the repeated pattern after the first symbol.

Exercise: Add contextual code lengths

Three observed tokens have ideal lengths $1$ , $0.5$ , and $2$ bits. What is the sequence's ideal length?

Check the total length

Compute it first, then check your number.

HintConditional code lengths add across positions

Add the three token-level lengths.

SolutionThe sequence requires 3.5 ideal bits

Conditional ideal code lengths add across sequence positions, so the total is $1+0.5+2=3.5$ bits.

Learning a Pattern Can Improve Prediction

Text contains recurring structure at several scales: spelling, syntax, references between sentences, common facts, genre, and longer patterns of argument. A predictor can reduce average log loss only by exploiting structure that helps anticipate later tokens. This is why next-token prediction supplies a broad learning signal.

The relationship must be stated carefully. Predicting a sentence well means that it fits patterns in the training distribution and context. It does not prove that the sentence is true. Frequently repeated errors, fictional claims, and stylistic habits can also be predictable.

Exercise: Separate predictability from truth

Does assigning high probability to a claim prove that the claim is factually correct?

Choose one

Yes, high probability proves truth.

No, predictability and factual truth are different.

Select one choice, then check.

HintAsk what the probability model was trained to match

It predicts patterns in data and context.

SolutionPredictability does not establish truth

A claim can be common or contextually expected while still being false. Factual reliability requires evidence and evaluation beyond token loss.

A Compressor Also Has a Description Cost

A complicated model can memorize a finite dataset and assign it very short data codes. A fair comparison should also consider the cost of specifying the model. This motivates a two-part description:

L(\text{model})+L(\text{data}\mid\text{model}).

“Total description length is the length of the model plus the length of the data when encoded with that model.” A larger model is worthwhile only when the data savings compensate for its added description cost.

Suppose Model A takes $200$ bits to describe and encodes the data in $900$ bits, for a total of $1{,}100$ . Model B takes $500$ bits but encodes the data in $500$ bits, for a total of $1{,}000$ . Under this two-part accounting, Model B gives the shorter complete description despite being more complex.

Exercise: Compare complete description lengths

Model A costs $300$ bits and encodes data in $700$ bits. Model B costs $600$ bits and encodes the same data in $350$ bits. Which has the shorter total description?

Choose the shorter description

Model A: 1,000 bits total

Model B: 950 bits total

Select one choice, then check.

HintInclude both parts

Compare $300+700$ with $600+350$ .

SolutionModel B is shorter overall

Model A totals $1{,}000$ bits; Model B totals $950$ bits. Model B saves $50$ bits after model complexity is included.

Visualize the Cost of a Mismatched Predictor

Plot expected code length for a binary source

Change the source probability and see where the predictor minimizes expected code length.

Ready to run.

Exercise: Locate the best binary predictor

If a source produces $A$ with probability $0.75$ , which predicted probability for $A$ minimizes expected logarithmic code length?

Check the prediction

Compute it first, then check your number.

HintMatch the source distribution

Cross-entropy is minimized when the predictor equals the source.

SolutionThe optimum prediction is 0.75

Predicting $q(A)=0.75$ matches the source and removes KL mismatch cost.

Compression Is Evidence of Learned Structure, Not a Complete Verdict

Compression provides a precise way to test whether a model captures predictive regularities. It does not by itself measure factuality, causal understanding, planning, safety, fairness, computational cost, or usefulness to a person. Claims that “intelligence is compression” are therefore best read as a productive research viewpoint, not a settled mathematical equivalence.

The chapter's review now brings together surprise, entropy, distribution mismatch, shared information, log loss, perplexity, and the coding view.