Worked examples — Speculative decoding

This page is a drill. We take the parent topic and run it through every kind of situation the acceptance-sampling machinery can hit. If you have never seen the notation $p$, $q$, $\alpha$, $K$ before, read the two short reminders below first — then every example is self-contained.

---

The scenario matrix

Every worked example below is tagged with the cell it covers. Together they touch every cell.

Cell	Situation	What's special	Example
A	$p\ge q$ at every position	all accepted, plus bonus token	Ex 1
B	$p<q$ somewhere	biased coin, possible early stop	Ex 2
C	$p=q$ exactly	boundary $a=1$; draft is "perfect"	Ex 3
D	Degenerate: $p=0$ (target forbids token)	forced rejection, $a=0$	Ex 4
E	Degenerate: $q\to 0$	overconfident-editor blow-up, $\frac{p}{q}$ capped at 1	Ex 5
F	The resample step itself	build $p_{\text{adj}}$ over a full vocab	Ex 6
G	Limiting $\alpha \to 1$ and $\alpha \to 0$	speedup ceiling and floor	Ex 7
H	Real-world word problem (latency budget)	pick $K$, compute wall-clock speedup	Ex 8
I	Exam twist: $q$ correct token but wrong ordering	acceptance ignores rank, only ratio	Ex 9

---

Ex 1 — Cell A: everything accepted, bonus token

Forecast: Guess before reading. More or fewer than $K$?

1. Position $t$: $a=\min (1,0.7/0.6)=\min (1,1.1\overline{6})=1$. Accept. Why this step? $p>q$, editor is more confident, no reason to doubt the intern.
2. Position $t+1$: $a=\min (1,0.9/0.5)=1$. Accept. Why this step? Again $p>q$.
3. Position $t+2$: $a=\min (1,0.4/0.4)=\min (1,1)=1$. Accept. Why this step? Boundary — equal confidence still gives $a=1$ (see Cell C).
4. All $K=3$ accepted → sample bonus token from the target at position $t+3$. Why this step? Since the target already ran a forward pass over the whole drafted block, it also produced a distribution one step past the last draft — that token is free.

Answer: $K+1=4$ output tokens from a single target forward pass.

Verify: The formula $\mathbb{E}[\text{tokens}]=\frac{1-{\alpha }^{K+1}}{1-\alpha }$ gives the expected count over random coins; the maximum it can output is the all-accept case $K+1$. Here $K=3\Rightarrow K+1=4$. ✓

---

Ex 2 — Cell B: biased coin, early stop

Forecast: Will position $t+3$'s attractive $p=0.9$ ever get used?

1. $t$: $a=\min (1,0.8/0.7)=1$. Accept "token 1".
2. $t+1$: $a=\min (1,0.6/0.5)=1$. Accept "token 2".
3. $t+2$: $a=\min (1,0.2/0.4)=0.5$. Coin flip → fails → reject. Why this step? Editor likes this token half as much as the intern claimed, so we only keep it half the time. This coin failed.
4. Stop immediately. Discard the draft at $t+3$ even though its $p=0.9$ looked great. Why this step? Tokens are a sequence. The $t+3$ draft was written assuming $t+2$'s "," — once that's gone, the context is different, so the $t+3$ probabilities are meaningless. We resample $t+2$ instead from $p_{\text{adj}}$.

Answer: 2 accepted + 1 resampled = 3 output tokens. Position $t+3$'s $p=0.9$ is never used.

Verify: Output count on rejection at index $i=2$ (0-based) is $i+1=3$. ✓

---

Ex 3 — Cell C: $p=q$ exactly (perfect draft)

Forecast: Perfect draft — do we always get $K+1$?

1. Each position: $a=\min (1,p/q)=\min (1,1)=1$ for all. Why this step? Ratio is exactly 1 everywhere, so $\alpha =1$.
2. Expected tokens: plug $\alpha \to 1$ into $\frac{1-{\alpha }^{K+1}}{1-\alpha }$. This is $\frac{0}{0}$, so take the limit: it equals $K+1$. Why this step? When every draft is guaranteed accepted, you always reach the bonus token.

Answer: $\alpha =1$, expected tokens $=K+1=6$.

Verify: ${\lim }_{\alpha \to 1}\frac{1-{\alpha }^6}{1-\alpha }=6$ (L'Hôpital / geometric sum $1+1+\dots$ six terms). ✓

---

Ex 4 — Cell D: $p=0$, target forbids the token

Forecast: Can a token the editor calls impossible ever survive?

1. Accept prob: $a=\min (1,0/0.4)=\min (1,0)=0$. Always reject. Why this step? $p=0$ means the target would never produce this token; keeping it would break losslessness.
2. Resample from $p_{\text{adj}}(x)=\frac{\max (0,p(x)-q(x))}{Z}$. Why this step? The forbidden token has $p-q=0-0.4<0\Rightarrow \max (0,\cdot )=0$, so it gets zero resample mass too. Good — it's fully purged.

Answer: $a=0$, token rejected, resample avoids it entirely.

Verify: $\min (1,0/0.4)=0$ and $\max (0,0-0.4)=0$. ✓

---

Ex 5 — Cell E: $q\to 0$ (draft nearly rules token out)

Forecast: Does a tiny $q$ blow the ratio $p/q$ up to infinity and break things?

1. Ratio: $p/q=0.8/0.01=80$.
2. Accept prob: $a=\min (1,80)=1$. Always accept. Why this step? The $\min (1,\cdot )$ cap is exactly here to stop the ratio from exceeding a probability. No matter how tiny $q$ is, $a$ never exceeds 1.
3. Limit $q\to 0^{+}$: $p/q\to \infty$, but $\min (1,\infty )=1$. Stable. Why this step? Shows the algorithm is numerically safe against near-zero draft mass — the cap is load-bearing.

Answer: $a=1$; the cap makes $q\to 0$ harmless (the target simply reclaims the token).

Verify: $\min (1,0.8/0.01)=1$. ✓

---

Ex 6 — Cell F: building the resample distribution

Forecast: Which token is most likely to replace $B$?

1. Compute $p-q$ per token: $A:0.5-0.1=0.4$; $B:0.2-0.6=-0.4$; $C:0.3-0.3=0$.
2. Apply $\max (0,\cdot )$: $A:0.4$, $B:0$, $C:0$. Why this step? Only tokens the target wants more than the draft offered deserve extra mass. $B$ was over-supplied by the draft, so it drops to 0.
3. Normalise: $Z=0.4+0+0=0.4$. Then $p_{\text{adj}}=(0.4/0.4,0,0)=(1,0,0)$. Why this step? Dividing by $Z$ makes it a valid distribution summing to 1.

Answer: Resample gives $A$ with probability $1$, $B$ and $C$ with probability $0$.

Verify: $\max (0,p-q)=(0.4,0,0)$, $Z=0.4$, normalised $=(1,0,0)$. ✓

Look at the figure: the blue bars are $q$, the yellow bars are $p$. The green bars are the leftover $\max (0,p-q)$ — only $A$ pokes above the draft, so all resample mass lands there.

---

Ex 7 — Cell G: the two limits of speedup

Forecast: What is the best speedup you can ever get with $K=4$?

Recall speedup $=\frac{c_p\cdot \mathbb{E}[\text{tokens}]}{K{c}_q+c_p}$, with $\mathbb{E}[\text{tokens}]=\frac{1-{\alpha }^{K+1}}{1-\alpha }$.

1. $\alpha \to 1$: $\mathbb{E}[\text{tokens}]\to K+1=5$. With $c_q=0$: speedup $=\frac{10\cdot 5}{0+10}=5$. Why this step? Free draft + always-accept is the ideal ceiling, exactly $K+1$.
2. $\alpha \to 0$: $\mathbb{E}[\text{tokens}]\to \frac{1-0}{1-0}=1$. Speedup $=\frac{10\cdot 1}{10}=1$. Why this step? Nothing ever accepts, so you emit just the resampled token — same as plain decoding, no gain.

Answer: Speedup runs from 1 (worst, $\alpha \to 0$) up to $K+1=5$ (best, free draft, $\alpha \to 1$).

Verify: $\frac{1-{\alpha }^5}{1-\alpha }\to 5$ as $\alpha \to 1$ and $\to 1$ as $\alpha \to 0$; speedups $5$ and $1$. ✓

The curve rises fast near $\alpha =1$: the last few percent of acceptance rate buy most of the speedup.

---

Ex 8 — Cell H: real-world latency budget

Forecast: Bigger $K$ always better?

Effective ms/token $=\frac{K{c}_q+c_p}{\mathbb{E}[\text{tokens}]}$, $\mathbb{E}=\frac{1-0.7^{K+1}}{0.3}$.

1. $K=2$: cost $=2(5)+40=50$; $\mathbb{E}=\frac{1-0.7^3}{0.3}=\frac{1-0.343}{0.3}=2.19$; per-token $=50/2.19=22.83$ ms.
2. $K=4$: cost $=4(5)+40=60$; $\mathbb{E}=\frac{1-0.7^5}{0.3}=\frac{1-0.16807}{0.3}=2.7731$; per-token $=60/2.7731=21.64$ ms.
3. $K=8$: cost $=8(5)+40=80$; $\mathbb{E}=\frac{1-0.7^9}{0.3}=\frac{1-0.040354}{0.3}=3.1988$; per-token $=80/3.1988=25.01$ ms. Why this step? Big $K$ pays for lots of draft tokens ($K{c}_q$) that mostly get thrown away once acceptance stalls (geometric decay of ${\alpha }^i$) — diminishing returns turn into losses.

Answer: $K=4$ wins at $\approx 21.6$ ms/token. Speedup vs. target-only ($40$ ms) $=40/21.64\approx 1.85\times$.

Verify: All three per-token costs and the $1.85\times$ speedup are checked below. ✓

---

Ex 9 — Cell I: exam twist, rank vs. ratio

Forecast: Does agreeing on the best token guarantee acceptance?

1. Accept prob: $a=\min (1,0.4/0.9)=0.4/0.9=0.4\overline{4}$. Why this step? Acceptance depends only on the ratio $p/q$, never on rank. The draft was over-confident (0.9) about a token the target only mildly likes (0.4), so we keep it under half the time.
2. On rejection: resample from $\max (0,p-q)$ — this token gets $\max (0,0.4-0.9)=0$ mass, so it's removed from the resample even though it was the top-1. Why this step? Losslessness cares about matching the full distribution, not preserving the argmax.

Answer: No — same top token does not guarantee acceptance. Here $a\approx 0.444$.

Verify: $\min (1,0.4/0.9)=0.4444\dots$ ✓

---

Recall Quick self-test

What is $a$ when $p=0.3,q=0.2$? ::: $\min (1,0.3/0.2)=\min (1,1.5)=1$ — always accept. Draft accepts all $K$; how many tokens out? ::: $K+1$ (the bonus token). Resample mass on a token with $p<q$? ::: $0$, because $\max (0,p-q)=0$. As $\alpha \to 0$, speedup? ::: $\to \frac{c_p}{K{c}_q+c_p}\le 1$ — no gain.

Related: 5.3.2-Knowledge-distillation builds the draft; 6.1.11-Model-quantization shrinks it further; 3.2.4-Beam-search and 3.1.2-Transformer-architecture are the decoding backdrop; 6.13-Flash-attention speeds the verify pass; 6.2.1-Distributed-training scales the target.