Applied Information Theory: An Interactive Guide

🎓 What if we want a big model's quality in a small box?

Scaling laws say bigger is better — train a 70B-parameter model on 1.4T tokens, the cross-entropy loss drops to a level a 7B model can't reach by training directly on the same data. But you can't ship a 70B model to a phone, a browser tab, or an embedded sensor. You need a small box at inference time.

The natural question: can a small student model inherit what a large teacher learned, even though it can't learn it from scratch on the same data?

🌑

The information-theoretic answer is YES — if you transfer the teacher's full output distribution to the student, not just its labels. A hard label is one bit of information ("this is a cat"). A soft distribution ('cat 70% · lion 25% · lynx 4% · dog 1%') is a much richer signal: the relative ranking of the wrong classes is data — the teacher is telling you cats are like lions and unlike dogs.

📜 2006 — Caruana et al.: Model Compression

Bucilă, Caruana, Niculescu-Mizil — "Model Compression"
Cornell · KDD 2006

The first attempt at the idea, nine years before Hinton. The Cornell team had built ensembles — random forests, bagged decision trees — that won every Kaggle-era benchmark, but were huge: hundreds of trees, gigabytes of memory, slow at inference.

Their trick: generate millions of unlabeled synthetic examples, run them through the ensemble to get labels, then train a small neural net on that synthetic dataset. Result: the small net got within ~0.5% of the ensemble's accuracy at 1000× lower inference cost.

⚠️

What was missing: they used the ensemble's hard predictions (argmax labels), not its full probability distribution. There was no information-theoretic framing — no D _KL , no temperature, no soft targets. The idea was right; the mechanism would take nine more years to crack.

🧠 2015 — Hinton et al.: Distilling the Knowledge

Hinton, Vinyals, Dean — "Distilling the Knowledge in a Neural Network"
Google · NIPS 2014 deep learning workshop · arXiv 1503.02531 (March 2015)
arxiv.org/abs/1503.02531

Same setup as Caruana — small student trained to match a big teacher's outputs. But Hinton added two things that turned the idea into a universal technique:

1 · Soft probabilities

Use the teacher's full softmax distribution as the training target — not just the argmax. The student learns from the whole probability vector, including the teacher's relative confidence in wrong classes.

2 · Temperature

Divide logits by T > 1 before softmax-ing. T = 1 is the normal softmax; T = 4 is much softer. Soft = the teacher's tiny tail probabilities (0.001 vs 0.0001) become big enough for gradients to use.

🌑

Hinton named this "dark knowledge" — the structure hidden in the tail of the teacher's distribution. With T = 1 you can't see it because all the wrong-class probabilities are visually zero. With T = 4 it shines through, and the student can learn from it.

🌡️ Temperature — the entropy dial on softmax

The same parameter, name, and role that appears in Boltzmann distributions in statistical mechanics . T literally controls the entropy of the output distribution — low T concentrates probability mass; high T spreads it out.

softmax(z / T) _i = exp(z _i / T) / Σ _j exp(z _j / T)

🎛️ Try it: drag T to soften the teacher's distribution

A teacher classifies an image of a CAT. Below are the teacher's logits — fixed values from the network. Slide T to see how softmax(z / T) changes. Watch how dark knowledge emerges as T grows.

Temperature: 1.0

Class	Logit z _i	softmax(z / T) _i	Distribution

Top-class probability

—

cat probability

Tail mass (wrong classes)

—

where dark knowledge lives

Entropy of distribution

—

bits — the "softness"

T → 0

argmax · zero entropy · no dark knowledge

T = 1

standard softmax · tail lost in noise

T = 4 – 10

tail visible · gradients can use it

T → ∞

uniform · max entropy · no info

⚖️ The distillation loss — two terms, one objective

Hinton's recipe combines a small hard-label cross-entropy with a larger soft-distribution KL term:

L = α · H( y _hard , q _T=1 ) + (1 − α) · T² · D _KL ( p _T ‖ q _T )

Term 1 — hard cross-entropy

Standard supervised loss on the true label, at temperature 1. Keeps the student grounded — even when the teacher is wrong, the truth still pulls the student toward correct answers. Acts as a safety rail.

Term 2 — soft KL

                                (1 − α) · T² · D
                                KL
                                ( p
                                T
                                ‖ q
                                T
                                )
                            

KL between teacher's softened distribution p _T and student's softened distribution q _T (both at temperature T). The T² factor compensates for softmax gradients shrinking by 1/T² — keeps the gradient magnitude scale-invariant in T.

🎚️ Try it: balance hard label vs soft KL

α controls how much the student listens to the hard label vs the teacher's soft distribution. Move it from 0 (pure distillation) to 1 (pure supervised) and watch the breakdown.

α (hard label weight): 0.10

α · hard CE

0.10 · 1.20

= 0.120 bits

(1 − α) · T² · KL

0.90 · 16 · 0.05

= 0.720 bits

Total loss L

0.840

Mostly KL — the recipe Hinton suggested.

🔑

Recipe in practice: α ≈ 0.1, T ≈ 4. The KL term does most of the work transferring dark knowledge; the small hard-label term is a safety rail. With α = 1 (no KL term) you're doing plain supervised learning on the original labels — and you lose the distillation gain entirely. The whole game is in the soft term.

📊 Worked example — what the student actually sees

Same teacher logits as the temperature demo above, side by side. With T = 1 the wrong-class probabilities are visually zero to gradients — they get lost in numerical noise. With T = 4 they become 12× larger and the student finally has signal to learn from.

Class	Hard label	Teacher · T = 1	Teacher · T = 4	What the student learns
🐱 cat	1.0	0.95	0.55	Top class — easy. The cat label.
🦁 lion	0.0	0.04	0.25	Cats are similar to lions — feline structure.
🐆 lynx	0.0	0.008	0.13	Lynx still feline — second cousin.
🐶 dog	0.0	0.002	0.07	Far less similar — different family.

🧩

This is concretely what dark knowledge means. At T = 4 the student gets a usable signal that {lion, lynx} ≫ {dog} in similarity to cat. That structural information was always in the teacher's logits — it just took raising the temperature to make it visible to the student's gradients. A model trained from scratch on hard labels would have to discover that structure by itself, slowly, from raw data. The student gets it for free, in a single forward pass.

🚀 Distillation at production scale

You've used distilled models without realizing. The technique is now ubiquitous in shipping ML:

DistilBERT · 2019

Sanh, Debut, Chaumond, Wolf (Hugging Face). 60% the size of BERT with 97% of GLUE benchmark performance. Combined recipe: soft KL + cosine + masked-LM losses. arXiv:1910.01108

TinyBERT · 2019

Jiao et al. Distill at multiple layers — embeddings, attention matrices, hidden states — not just the final output. 7.5× smaller, 9.4× faster than BERT. arXiv:1909.10351

Llama · on-device variants

Meta routinely distills its frontier models into the on-device sizes shipped in apps. Chinchilla-scaled teachers, distilled students. Same pattern at OpenAI, Anthropic, Google.

CLIP · MobileCLIP / DistilCLIP

Apple, OpenAI both distill the dual-tower CLIP into mobile-sized models that match retrieval accuracy at a fraction of the FLOPs. Same dark-knowledge trick — soft similarity scores transfer better than hard match/no-match labels.

🌍

Every on-device LLM, every mobile vision model, every embedded ASR system you've ever used was almost certainly a distilled student. Cross-entropy and KL divergence aren't just theory — they're how production ML actually ships.

🪢 The thread that ties everything together

Distillation is the first and oldest place where the surf-buoy machinery — cross-entropy, KL divergence — does real, named work in ML. Each later chapter of this deck reuses the same machinery for a different purpose:

Era	Application	Quantity
2006 / 2015	Distillation — transfer teacher's dark knowledge to student	min D _KL (p _T ‖ q _T )
2020 / 2022	Scaling laws — D _KL shrinks predictably with model / data / compute	D _KL ~ N ^−α
2022 / 2023	Speculative decoding — exploit a small model that's near-match to a big one	α = 1 − TV ≤ √(½ D _KL )
2025	L²M — MI between past and future bounds the state size needed	I ^BP ~ L ^β ≤ C·dim(z)

⚡

Distillation and speculative decoding are the same coin, two sides: distillation USES D _KL as the training objective to make a small model close to a big one. Speculative decoding then EXPLOITS that closeness at inference time — Pinsker's inequality says small D _KL guarantees high acceptance rate. In practice, the draft model in spec-dec is often a distilled version of the target. The two compose: distill offline to get the small model close, then spec-dec online to use it.

📈 Scaling Laws: Cross-Entropy Is the Loss Function

When you read that a language model was "trained on 10 trillion tokens" or "has 405 billion parameters," the question is: how do we know if it's getting better? The answer is the number we've been studying all along.

The training loss in every modern language model is:

Loss = 𝔼 _{x ~ p
_data} [ −log q _θ (x) ]

Two distributions, same roles as the buoy:

                            p
                            data
                        

The true data distribution — what humans actually write. We never know this exactly, but we can sample from it (that's the training corpus). This is p in our buoy example: the real Guiones swell distribution.

                            q
                            θ
                        

The model's learned distribution — what the neural network with parameters θ predicts. This is q: the Manhattan engineer's mental model, except with billions of adjustable knobs instead of gut feelings.

So the formula says: draw real text x from p _data , score it with the model's log-probability −log q _θ (x), and average. That's cross-entropy H(p _data , q _θ ) — the expected surprise of the model when reality is drawn from real language. The exact same formula we used for the wave buoy. The only difference: instead of four swell states, there are tens of thousands of tokens, and instead of a hand-tuned model, q _θ has billions of parameters being optimized by gradient descent.

🔬 The Decomposition That Makes It Click

Here's the decomposition we've already seen, now applied to training:

Training loss

Irreducible noise

                                H(p)
                            

Model's ignorance

H(p) is the entropy of real language — the genuine unpredictability of what a person writes next. No model can beat this floor. If someone could write "the" or "a" in a sentence, that uncertainty is baked into the data. This is exactly the entropy floor from the wave buoy: the 1.709 bits/report that no code can compress below.

D _KL (p ‖ q _θ ) is the KL divergence — the extra bits the model wastes because it doesn't yet match reality. This is the Manhattan engineer's penalty: the gap between an imperfect model and the truth. Training a model means shrinking this gap.

🎯

Since H(p) is fixed, minimizing cross-entropy is equivalent to minimizing KL divergence. The optimizer doesn't know H(p) and doesn't need to — it just pushes the total loss down, and all the movement comes from D _KL shrinking. Every gradient step is the model's distribution q _θ inching closer to the true distribution p.

⚡ The Power Law: How Fast Does D _KL Shrink?

Scaling laws (Kaplan et al. 2020, Hoffmann et al. 2022) discovered that this shrinkage is remarkably predictable. The KL divergence — the gap between model and reality — follows a power law as you increase three things:

🧠

Model size N

More parameters → more capacity to approximate p → less wasted bits

📚

Dataset size D

More data → better estimate of p → model learns finer distinctions

🔥

Compute C

More FLOPs → more gradient steps × bigger model → loss drops predictably

A power law means the improvement is a straight line on a log-log plot: 10× more compute gives a fixed percentage drop in loss, not a fixed absolute drop. The gains get smaller in absolute terms but never quite stop.

As you scale up, the blue curve (total loss) descends toward the green floor (entropy of language). The red gap between them is the KL divergence — the model's remaining ignorance. It shrinks as a power law but never reaches zero. A model with infinite parameters and infinite data would theoretically hit the floor, but in practice there's always a gap.

🌊 Back to the Buoy

Map the scaling law directly onto our surf example:

Scaling law concept	Wave buoy equivalent
H(p) = entropy floor	1.709 bits/report — the genuine unpredictability of Guiones swell. No model can beat this.
H(p, q _θ ) = training loss	Manhattan engineer's 2.782 bits — cross-entropy of a wrong model. This is what training starts high and pushes down.
D _KL (p ‖ q _θ ) = the gap	1.073 bits wasted — the Manhattan engineer's ignorance about Guiones. Training shrinks this.
Scaling up	Like the Manhattan engineer spending more time in Guiones, surfing more sessions, talking to locals — each iteration brings q closer to p, shrinking D _KL .
Diminishing returns	After a month, the engineer knows most patterns. The last 0.01 bits of D _KL — distinguishing rare double-overhead swells from merely head-high — takes disproportionate effort. Power law.

🧩 Chinchilla and the Optimal Tradeoff

Kaplan et al. (2020) found the power laws. Hoffmann et al. (2022) — the "Chinchilla" paper — asked the next question: given a fixed compute budget C, how should you split it between model size N and dataset size D?

The answer: scale them together . For every doubling of parameters, you need roughly a doubling of training tokens. Their key finding was that many existing models (including the original Gopher) were undertrained — too many parameters, not enough data. Chinchilla (70B parameters, 1.4T tokens) matched the much larger Gopher (280B parameters, 300B tokens) because it had a better balance.

In KL terms: a huge model with too little data overfits — its q _θ memorizes the training set rather than learning the true distribution p. A tiny model with massive data underfits — q _θ lacks the capacity to represent the structure in p. The optimal frontier minimizes D _KL (p ‖ q _θ ) for a given compute budget by balancing both.

🏄

Surf analogy: You could spend a year watching Guiones webcams (huge dataset, tiny model = memorizing pixel patterns without understanding swell). Or you could study one session with a PhD in fluid dynamics (huge model, tiny data = elegant theory that doesn't match local reality). The best surfer-forecaster balances both: enough sessions to learn the patterns, enough framework to generalize from them.

🔑 The Takeaway

Scaling laws aren't some separate topic bolted onto information theory — they are information theory applied to training dynamics:

Training loss = cross-entropy H(p, q _θ )
What training minimizes = KL divergence D _KL (p ‖ q _θ )
Scaling laws describe = how D _KL shrinks as a power law with N, D, and C
The floor = H(p), the irreducible entropy of language itself
The question = how fast does q _θ approach p as we scale?

Every loss curve you've ever seen on a training dashboard is a cross-entropy curve. The Y-axis is H(p, q _θ ). The asymptote it's approaching is H(p). The gap is D _KL . Now you know exactly what all three mean.

📄 From Entropy to Long-Context LLMs

Everything we've built — entropy, cross-entropy, KL divergence — isn't textbook filler. It's the core language of a 2025 MIT paper that answers a fundamental question: how much memory does a language model need to handle long sequences?

The paper's key tool is something called mutual information — which is built entirely from entropy and KL divergence. Before we get to the paper itself, let's define this concept properly.

🔗 Mutual Information (MI): The Definition

You have two random variables — X and Y. Each carries some information on its own (measured by their entropies H(X) and H(Y)). But they might also share information: knowing X might tell you something about Y, and vice versa. Mutual information , written I(X; Y), quantifies exactly that overlap — how much does knowing one tell you about the other? We abbreviate it as MI from here on.

MI has two equivalent definitions — one built from KL divergence, one from entropies:

KL divergence form

                                I(X; Y) = D
                                KL
                                ( p
                                XY
                                ‖ p
                                X
                                · p
                                Y
                                )
                            

How far is the joint distribution from independence? If X and Y are independent, p _XY = p _X ·p _Y and the KL is zero — knowing X tells you nothing about Y.

Entropy form

                                I(X; Y) = H(X) + H(Y) − H(X,Y)
                            

The information in X plus the information in Y, minus the information you need for both together. The overlap is what they share — that's the mutual information.

Both forms say the same thing. The KL form asks: "how different is the real joint distribution from what you'd get if X and Y were independent?" The entropy form asks: "how much total information do X and Y carry individually versus together?" The gap — the overlap — is the mutual information.

                                I(X;Y) = 0
                            

X and Y are independent — knowing one tells you nothing about the other

                                I(X;Y) > 0
                            

They share information — knowing X reduces your uncertainty about Y

                                I(X;Y) = H(Y)
                            

X completely determines Y — no residual uncertainty

🏄

Surf analogy: X is the morning swell report, Y is the afternoon session quality. H(X) is how much information the swell report carries. H(Y) is how much information the session quality carries. I(X;Y) is how much the morning report tells you about the afternoon — the overlap. If conditions are random (no correlation), I(X;Y) = 0. If the morning report perfectly predicts the afternoon, I(X;Y) = H(Y).

📄 The Paper: L²M

With MI defined, here's the paper that uses it as its central tool:

L²M: Mutual Information Scaling Law for Long-Context Language Modeling
Zhuo Chen, Oriol Mayné Comas, Zhuotao Jin, Di Luo, Marin Soljačić — MIT, 2025
arxiv.org/abs/2503.04725

The paper's insight: mutual information between past and future tokens in language grows as a power law with sequence length, and a model's state size must grow to match — or it will fail at long contexts. Let's walk through how they use MI.

📐 Bipartite MI: Applying It to Text

Bipartite means "split into two parts" — that's it. Instead of measuring MI between two individual tokens, the paper measures MI between two blocks of text: everything before a split point (the past) and everything after it (the future). Take a sequence of L tokens and cut it in half:

X = past tokens Y = future tokens

I ^BP _L/2;L = I(X; Y) — how much does the first half tell you about the second half?

The notation: I ^BP is just I(X; Y) — the mutual information we defined above — with a superscript BP for "bipartite" to remind us we're measuring between two blocks, not two individual tokens. The subscript L/2;L means the split is at the halfway point of a sequence of length L.

The paper's central empirical finding: this mutual information follows a power law :

I ^BP ~ L ^β (β ≈ 0.5–0.7 for English)

Double the sequence length and the mutual information doesn't just double — it grows as a fractional power. This means long-range dependencies in language are real and increasing : the further back you go, the more information is relevant to predicting the future.

The chart below shows three scaling regimes. The orange curve is the paper's finding for natural language — bipartite MI grows as a power of sequence length. The dashed red curve shows logarithmic growth (log L), which is a much slower scaling class that the paper uses as a contrast. The dashed blue line shows linear growth for reference. The key insight: if you only look at how pairs of individual tokens correlate at a distance (two-point MI), both language and log-L systems look similar — power-law decay. But when you measure block-level dependencies, language grows far faster. That's why the paper argues bipartite MI is the right measure — it reveals structure that pairwise statistics miss:

⚡

Key distinction the paper makes: two-point mutual information, or MI — the dependence between individual tokens separated by distance d — decays as d ^−α . Many systems share this same pairwise decay pattern. But bipartite MI (between whole blocks) grows as L ^β for language, far faster than the log L growth seen in other systems with identical pairwise statistics. Pairwise correlations are misleading — they can't distinguish fundamentally different dependency structures. Bipartite MI can, and that's why the paper uses it as the foundation for the L²M condition.

📡 Measuring MI with Cross-Entropy

You can't directly measure mutual information in text — you'd need the true probability distribution p, which is unknown. The paper's trick: use an LLM (LLaMA 3.1 405B) as an approximation q, then estimate MI using cross-entropy differences .

But first, a new piece of notation. So far we've written cross-entropy as H(p, q) — one true distribution, one model. Now we need a conditional version: the cross-entropy of the model after it has seen some context.

H(p _Y , q _Y ) — marginal cross-entropy. The model predicts Y having seen nothing. "How surprised is q by future text, going in blind?"

H(p _Y|X , q _Y|X ) — conditional cross-entropy. The model predicts Y after seeing past text X. "How surprised is q by future text, given it read the past?" This is what every autoregressive LLM actually computes — each token is predicted given all previous tokens.

The paper calls this the direct estimator — "direct" because it estimates MI straight from the model's log-probabilities, without any extra tricks:

I ^BP,direct = H(p _Y , q _Y ) − H(p _Y|X , q _Y|X )

The superscript is just a label, not an operator: BP = bipartite (between two blocks, as we defined above), direct = computed directly from the model's output probabilities. So I ^BP,direct reads as "bipartite mutual information, estimated via the direct method." The paper also uses a second estimator called vCLUB as a cross-check, so the label distinguishes which estimation method was used. The underlying quantity being estimated is the same I ^BP we saw earlier.

marginal cross-entropy

Surprise without seeing X

−

conditional cross-entropy

Surprise after seeing X

If X is completely unhelpful, both cross-entropies are the same and MI = 0. If X is highly informative, the conditional cross-entropy drops significantly — the context bought you real predictive power.

🏄

Surf analogy: Ask someone to predict tomorrow's Guiones session (surprise = H(p _Y , q _Y )). Then show them this week's swell forecasts (X) and ask again (surprise = H(p _Y|X , q _Y|X )). The drop in surprise is the mutual information — it's how many bits of prediction the forecast bought you.

🧠 The L²M Condition

This is the paper's punchline. For an autoregressive model to handle long sequences, it needs to cache past information in a history state z. How that state works depends on the architecture:

Transformers (GPT, LLaMA, etc.) use attention — every new token can look back at all previous tokens. To make this fast during generation, they store a KV cache (key-value cache): a growing list of compressed representations for every past token. More tokens processed → bigger cache.

Recurrent Neural Networks (RNNs) and State Space Models (SSMs) (like Mamba) take a different approach: they compress all past context into a single fixed-size hidden state, updated token by token. Think of it like a summary that gets overwritten each step. This is fast and memory-efficient — processing each token costs the same regardless of sequence length — but the summary has a fixed capacity.

The paper proves that the maximum MI a model can capture is bounded by its state size:

I ^BP _captured ≤ C · dim(z) + log(M)

                            dim(z)
                        

The dimension of the history state — how many numbers the model uses to represent everything it remembers about past tokens. For a transformer, this is the size of the KV cache; for an RNN/SSM, it's the hidden state size.

C

A constant that depends on how the state is stored (e.g., bits per dimension for discrete/quantized states). It doesn't change with sequence length — it's just a scaling factor.

M

The vocabulary size — how many distinct tokens the model can output (typically 32K–128K for modern LLMs). The log(M) term accounts for the information carried by the single current input token x _ℓ , separate from the history state.

The bound says: the total MI a model can capture between past and future is limited by how much information its state can hold. This follows from the data processing inequality — no computation downstream of z can recover information that z didn't store.

Since the true MI in language grows as L ^β , the state must grow at least as fast:

L²M Condition: dim(z) ≳ L ^β

This has immediate architectural consequences:

✅ Transformers

KV cache stores key-value pairs for every previous token. State size grows linearly with L:

                                dim(z) ~ L ≥ L
                                β
                                ✓
                            

Automatically satisfies L²M without scaling model size. The quadratic compute cost is the price of keeping enough state.

⚠️ RNNs / SSMs / Linear Attention

Fixed-size hidden state. State size is constant regardless of L:

                                dim(z) ~ O(1) ≱ L
                                β
                                ✗
                            

Violates L²M at long enough sequences. Must scale up model size as L grows to compensate — offsetting their linear complexity advantage.

🧩

The information-theoretic argument: By the data processing inequality, no downstream computation can create information that wasn't in the state z. If z is too small to hold the MI between past and future, the model physically cannot capture those dependencies — no matter how clever the architecture. This is why the L²M condition is a hard lower bound, not a soft guideline.

⚡ Speculative Decoding: Why It Provably Works

Normal autoregressive decoding is painfully slow — one token per forward pass through a massive model. Speculative decoding speeds this up by having a small, fast draft model guess K tokens ahead, then verifying them all at once with the big target model . The key question: does this change the output distribution?

Accelerating Large Language Model Decoding with Speculative Sampling
Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, John Jumper — DeepMind, 2023
arxiv.org/abs/2302.01318

Theorem 1 proves the answer is no — the modified rejection sampling scheme recovers the target distribution exactly . The proof uses nothing more than the probability concepts we've already built. Let's walk through it.

🎯 The Setup: Two Models, One Distribution

You have two models looking at the same context (the tokens generated so far):

p(x) — Draft model

Small, fast model (e.g. 4B params). Generates a candidate token x̃ quickly. Cheap to run but imperfect.

q(x) — Target model

Large, powerful model (e.g. 70B params). The distribution we actually want to sample from. Expensive to run.

The draft model proposes x̃ ∼ p. We want the final output X to follow q — the target distribution. The algorithm does this in two cases:

Accept:

Keep the draft token x̃ with probability min(1, q(x̃)/p(x̃))

Reject:

Discard x̃ and resample from the adjusted distribution (q(x) − p(x))⁺

The notation (f(x))⁺ means: take max(0, f(x)) for each x, then normalize so it sums to 1. This is the distribution over tokens where q assigns more probability than p — exactly the tokens the draft model underweights.

🎲 Building the Acceptance Rule

We have a draft token x̃ sampled from p, but we want our output to follow q. The question is: should we keep this particular token, or throw it away? We need a number between 0 and 1 — an acceptance probability. Let's build it from scratch.

What does q(x̃) / p(x̃) tell us?

This ratio measures how much the target agrees with the draft's choice , relative to how enthusiastically the draft proposed it. It's a correction factor:

                                q(x̃) / p(x̃) = 1
                            

Both models assign exactly the same probability to this token. The draft nailed it — no correction needed.

                                q(x̃) / p(x̃) = 0.3
                            

The target thinks this token is only 30% as likely as the draft claimed. The draft was overconfident here — we should reject it most of the time.

                                q(x̃) / p(x̃) = 2.5
                            

The target actually thinks this token is more likely than the draft did. The draft was right but underconfident — we definitely want to keep it.

                                q(x̃) / p(x̃) → 0
                            

The target assigns near-zero probability. The draft hallucinated a token the target would never produce — almost always reject.

So q/p is naturally the right thing to use as an acceptance probability. If the target agrees more, accept more. If it agrees less, accept less. The ratio does the bookkeeping for us.

Why do we need the min(1, ...)?

There's a problem: when q(x̃) > p(x̃), the ratio exceeds 1. But a probability can't be greater than 1 — you can't "more than certainly" accept something. So we clamp it:

P(accept | x̃) = min(1, q(x̃) / p(x̃))

When q(x̃)/p(x̃) ≥ 1, the target wants this token at least as much as the draft — accept with certainty. When the ratio is less than 1, accept with that exact probability. This is the full acceptance rule.

                                q(x̃) ≥ p(x̃)
                            

Ratio ≥ 1 → clamped to 1 → always accept

                                q(x̃) < p(x̃)
                            

Ratio < 1 → accept with prob q/p, correcting the draft's overconfidence

                                p = q everywhere
                            

Ratio = 1 everywhere → accept everything → zero overhead

🏄

Surf analogy: Your local friend (draft model) says there's a 60% chance today's session will be "firing." The authoritative forecast (target model) says 30%. The ratio is 30/60 = 0.5, so you accept your friend's call only half the time — correcting for their overenthusiasm. But if the forecast said 80% and your friend said 60%, the ratio is 80/60 = 1.33, clamped to 1 — your friend was actually conservative , so always trust the call.

📐 Theorem 1: The Proof, Step by Step

Goal: Show that P(X = x) = q(x) for every token x — the final sample follows the target distribution exactly.

The final sample X comes from one of two paths: the draft was accepted, or it was rejected and we resampled. By the law of total probability:

P(X = x) = P(x̃ = x) · P(accept | x̃ = x) + P(reject) · P(X = x | rejected)

Step 1: The acceptance term

The draft produces x̃ = x with probability p(x), and we accept with probability min(1, q(x)/p(x)):

p(x) · min(1, q(x)/p(x)) = min(p(x), q(x))

The p(x) partially cancels. If q(x) ≥ p(x), we get p(x) · 1 = p(x) = min(p,q). If q(x) < p(x), we get p(x) · q(x)/p(x) = q(x) = min(p,q). Either way: min(p(x), q(x)).

Step 2: The rejection probability

The total probability that the draft gets rejected (for any value of x̃):

P(reject) = 1 − Σ_x min(p(x), q(x)) = Σ_x max(0, q(x) − p(x))

Total acceptance across all x is Σ min(p(x), q(x)). What's left is the sum of max(0, q(x) − p(x)) — the total "excess" probability that q assigns beyond p.

Step 3: The resample distribution

When rejected, we sample from (q(x) − p(x))⁺ — normalized to sum to 1:

P(X = x | rejected) = max(0, q(x) − p(x)) / Σ_{x'} max(0, q(x') − p(x'))

The denominator is exactly P(reject) from Step 2. So when we multiply:

P(reject) · P(X = x | rejected) = max(0, q(x) − p(x))

The normalizing constant cancels with the rejection probability.

Step 4: Combine

P(X = x) = min(p(x), q(x)) + max(0, q(x) − p(x)) = q(x) ∎

The min grabs the part where draft and target agree. The max grabs the leftover where the target wants more. Together they always sum to q(x).

🔑

Why this works: For any real numbers a and b: min(a,b) + max(0, b−a) = b. If a ≥ b, then min = b and max = 0, so b + 0 = b. If a < b, then min = a and max = b−a, so a + (b−a) = b. The proof is just applying this identity pointwise to p(x) and q(x) for every token in the vocabulary.

📊 Visualizing the Probability Split

For each token x in the vocabulary, the target probability q(x) is recovered from two sources:

For tokens where q(x) > p(x) (A, C, E), the draft model underweights them — so the resample distribution fills in the gap. For tokens where q(x) ≤ p(x) (B, D), acceptance already throttles down to q(x). Either way, green + red = q(x).

🔗 Connection to KL Divergence

How efficient is speculative decoding? It depends on how similar the draft model p is to the target q — and we already have a tool for measuring that.

The expected acceptance rate across all possible draft tokens is:

α = Σ_x min(p(x), q(x)) = 1 − TV(p, q)

where TV(p, q) is the total variation distance — half the sum of |p(x) − q(x)| over all x. When p = q exactly, α = 1 (accept everything). When p and q are far apart, α drops and you waste time resampling.

Total variation is bounded by KL divergence via Pinsker's inequality :

TV(p, q) ≤ √(½ · D_KL(p ‖ q))

So a small D_KL between draft and target guarantees a high acceptance rate. Everything we learned about KL divergence as "wasted bits" directly translates to "wasted compute" in speculative decoding. A draft model that closely matches the target (low D_KL) wastes fewer proposed tokens.

🏄

Full circle: In the buoy example, the Manhattan engineer's D_KL of 1.073 bits meant 1.073 extra bits wasted per report. In speculative decoding, a high D_KL between draft and target means a low acceptance rate — more rejected tokens, less speedup. The same quantity measures waste whether you're transmitting swell data or generating text. KL divergence is the universal cost of using the wrong model.

🚀 2–2.5× Speedup, Zero Quality Loss

The beauty of Theorem 1 is that it gives you a hard guarantee : no matter how bad the draft model is, the output distribution is exactly q. A terrible draft just means low acceptance → no speedup. A great draft means high acceptance → massive speedup. But quality is never compromised.

What you gain

Multiple tokens per target model call. The paper shows 2–2.5× speedup on Chinchilla 70B with a 4B draft model. On code (HumanEval), speedup reached 2.46× because code has more predictable patterns.

What you don't lose

The output distribution. Every sample is provably drawn from q — the target model's distribution. No approximation, no bias, no quality degradation. Theorem 1 guarantees this.

🧩

The information-theoretic thread: Cross-entropy tells us the cost of using the wrong model. KL divergence quantifies the gap. Speculative decoding exploits this gap operationally — when the draft model is close enough to the target (low KL), most drafts get accepted and you decode faster. Theorem 1 proves this works without losing anything, using a rejection scheme that perfectly redistributes probability: min(p,q) + max(0, q−p) = q. The math we've been building all along.

Applied Information Theory