Foundations — Speculative decoding

This page assumes you know nothing. Every letter, arrow, and squiggle the parent note throws at you is built here from the ground up, in an order where each idea leans on the one before it.

---

0. What is a "token"?

Before any symbol, the object everything acts on: a token.

Look at the figure: text on the left, its token-numbers on the right. From now on when we write $x$, we mean one token (one box). Everything the models do is "pick the next box".

---

1. The subscript notation $x_t$ and $x_{<t}$

Picture: a row of boxes. $x_{<t}$ is the shaded stretch already written; $x_t$ is the one box we are about to fill.

Why the topic needs it: the entire game is "given everything so far ($x_{<t}$), what is the next token ($x_t$)?" You cannot even state the problem without this notation.

---

2. Probability $p(x_t\mid x_{<t})$ — the model's opinion

The model never returns a single word. It returns a probability for every possible next token.

Picture: a bar chart over the vocabulary. Tall bar on "Paris", tiny bars on everything else. The whole set of bar heights is the model's distribution for this position.

Why the topic needs it: speculative decoding compares two such bar charts (draft's vs. target's) at every position. Everything downstream is arithmetic on these bar heights.

---

3. Where the numbers come from: $\text{softmax}(W_{\text{out}}{h}_t)$

The parent writes $p(x_t\mid x_{<t})=\text{softmax}(W_{\text{out}}{h}_t)$. Let us earn each piece.

Why $\text{softmax}$ and not just "divide by the sum"? Because logits can be negative, and plain division could give negative "probabilities". Exponentiating with $e^{(\cdot )}$ guarantees positivity and keeps the ordering (bigger logit ⇒ bigger probability). That is exactly the tool for "turn arbitrary scores into a probability bar chart".

Recall Why is one token expensive?

To get $p(x_t\mid x_{<t})$ you must build $h_t$, which means loading all the model's billions of weights from memory. ::: Each new token = one full memory trip through the whole model.

---

4. "Sampling" and the squiggle $\sim$

Picture: a dartboard whose sector sizes equal the bar heights. Throw one dart → you get one token. Tall bars are big sectors, so likely tokens usually win, but rare ones can still land.

Why the topic needs it: the draft model samples $K$ guesses; the acceptance test then samples a coin flip. Both are this same dice-roll idea.

---

5. The two models: $M_q$ with $q$, and $M_p$ with $p$

Picture: two bar charts side by side over the same vocabulary — mostly agreeing, differing on a few tokens. The whole method lives in that gap between $p$ and $q$.

---

6. The lookahead $K$

Picture: the row of boxes with $K$ dashed "guess" boxes drawn ahead of the current position.

Why the topic needs it: bigger $K$ = more potential speedup per target pass, but also more guesses that can be wrong. $K$ is the knob balancing that trade-off.

---

7. The ratio $p/q$ and $\min (1,p/q)$ — the accept coin

This is the heart of the method, so we build it very slowly.

The draft handed us a guess $\tilde{x}$ that it liked with probability $q(\tilde{x})$. The target's opinion of that same token is $p(\tilde{x})$. We compare them by dividing:

$$\text{accept probability}=\min \left(1,\frac{p(\tilde{x})}{q(\tilde{x})}\right)$$

Why divide, why $\min$? Division asks "how does the target's enthusiasm compare to the draft's?" — a pure ratio, scale-free. The $\min (1,\cdot )$ exists because a probability can never exceed $1$; we never "accept more than always". Together they are precisely the tool that makes the kept tokens follow $p$ exactly (proven in the parent's derivation).

Picture: subtract the $q$ bars from the $p$ bars; keep only the bars that stick up above zero. Those leftover stumps, normalized, are the resample distribution.

---

8. Expected value $\mathbb{E}[\cdot ]$ and the geometric sum

The speedup analysis uses $\mathbb{E}[\text{tokens}]$.

The closed form $\frac{1-{\alpha }^{K+1}}{1-\alpha }$ comes from a geometric series — a sum where each term is the previous times $\alpha$. You do not need to prove it here; just know $\mathbb{E}$ and $\alpha$ are the ingredients, and see 3.2.4-Beam-search for a contrasting "keep-many-candidates" strategy.

---

The prerequisite map

Read top to bottom: raw tokens feed positions, positions feed probabilities, probabilities feed both the two models and the accept-coin, and all of it pours into the topic node.

---

Equipment checklist

Cover the right side; can you answer before revealing?

• What a token is, and why the model sees numbers not letters ::: A token is one text chunk; the model reads/writes lists of token-numbers, picking the next one each step.
• What $x_{<t}$ means ::: All tokens before position $t$ — the story written so far.
• What the "$\mid$" bar means in $p(x_t\mid x_{<t})$ ::: "given" — the probability of $x_t$ given the past $x_{<t}$.
• Why softmax and not plain division ::: Exponentiating makes every score positive and preserves order; dividing by the total forces a valid probability sum of $1$.
• Why one token is memory-expensive ::: Building $h_t$ loads all the model's billions of weights from memory — one full trip per token.
• What the tilde in $\tilde{x}$ and the $\sim$ mean ::: Tilde marks a draft guess; $\sim$ means "drawn by dice-roll from" a distribution.
• Which model is $p$ and which is $q$ ::: $p$ = powerful/target (big, accurate, slow); $q$ = quick/draft (small, fast, rough).
• What $K$ controls ::: How many tokens the draft guesses before the target verifies.
• What $\min (1,p/q)$ decides ::: The probability of accepting a draft token: always if $p\ge q$, else with chance $p/q$.
• What $\max (0,p-q)$ is for ::: The rescaled "leftover target desire" we resample from after a rejection, to stay unbiased.
• What $\alpha$ and $\mathbb{E}[\text{tokens}]$ mean ::: $\alpha$ = per-token acceptance chance; $\mathbb{E}$ = average tokens produced per cycle.

Related foundations you may want fresh: 6.1.11-Model-quantization, 6.2.1-Distributed-training.