Exercises — Speculative decoding

WHAT: Lossless means (b) — the probability distribution of generated tokens is exactly $p(x)$, the same distribution you'd get by running the slow target model by itself. NOT (a): sampling is still random, so different runs give different text — same as normal decoding. NOT (c): the draft is frequently wrong; the acceptance/resampling step is precisely what fixes those mistakes so the final distribution stays correct.

Each token needs one forward pass, which must load all model weights from GPU memory (billions of numbers). For a batch of one token, the GPU finishes the arithmetic long before the weights finish streaming in — so the wall-clock time is set by memory bandwidth, not by how many multiply-adds (FLOPs) the chip can do. The GPU sits idle waiting for memory. Speculative decoding fills that idle window by checking many tokens in the same load.

WHAT: $\frac{p}{q}=\frac{0.9}{0.3}=3.0$, so $\min (1,3.0)=\boxed{1}$. WHY: The target likes "cat" more than the draft did. When the target is at least as confident as the draft, there is no risk of over-representing that token, so we accept with certainty. The rule "$p\le q\Rightarrow$ accept probability $p/q$; else accept surely" caps at 1 exactly because a probability can't exceed 1.

WHAT: $\frac{p}{q}=\frac{0.15}{0.6}=0.25$, so ${\alpha }_{\text{token}}=\min (1,0.25)=\boxed{0.25}$. WHY: The draft was over-confident — it proposed "cat" more often than the target would. We accept only 25% of the time to bring the effective rate of emitting "cat" back down to the target's level. On rejection (75% of the time): we resample from the adjusted distribution $p_{\text{resample}}(x)=\frac{\max (0,p(x)-q(x))}{{\sum }_y\max (0,p(y)-q(y))}.$ This only keeps tokens the target wanted more than the draft supplied — repairing the bias.

WHAT: Cost $=K{c}_q+c_p=3(1)+8=\boxed{11}$ units. WHY: The draft runs $K=3$ sequential cheap passes (cost $3\times 1$), then the target runs one pass over all guesses at once (cost $8$). The target verifies all $K$ positions in that single pass — that parallelism is the whole point.

WHAT about the ratio: The formula $\min (1,p/q)$ is only ever evaluated for the token the draft actually proposed. A token can only be proposed if $q>0$ for it, so the denominator you plug in is never zero — the division-by-zero never happens in the accept test. If the draft sampled some token $\tilde{x}$, then by definition $q(\tilde{x})>0$. WHAT about "dog" still appearing: Even though the draft can never propose "dog", the target can still want it: $p(\text{dog})>0$. Look at the resample distribution $p_{\text{resample}}(x)=\frac{\max (0,p(x)-q(x))}{Z}.$ With $q(\text{dog})=0$ this becomes $\max (0,p(\text{dog})-0)=p(\text{dog})>0$. So on a rejection, "dog" can be resampled with positive weight. The resample branch is exactly what rescues tokens the draft assigned zero probability — that's why losslessness holds even for words the draft never dreams of. One-line rule: the accept ratio only sees proposed tokens ($q>0$, safe division); the resample branch handles every $q=0$ token the target still needs.

WHAT: $\frac{1-0.7^5}{1-0.7}=\frac{1-0.16807}{0.3}=\frac{0.83193}{0.3}\approx \boxed{2.773}$ tokens. WHY the closed form: Accepting the first $i$ draft tokens then rejecting has probability ${\alpha }^i(1-\alpha )$ and yields $i+1$ output tokens (the resampled one counts). Accepting all $K$ has probability ${\alpha }^K$ and yields $K+1$ (the bonus token). Summing ${\sum }_{i=0}^{K-1}(i+1){\alpha }^i(1-\alpha )+(K+1){\alpha }^K$ telescopes into the geometric sum $\frac{1-{\alpha }^{K+1}}{1-\alpha }$.

WHAT:

• Cycle cost $=K{c}_q+c_p=4(1)+10=14$ units.
• Effective cost per token $=\frac{14}{2.773}\approx \boxed{5.049}$ units.
• Baseline (target only) $=c_p=10$ units/token.
• Speedup $=\frac{10}{5.049}\approx \boxed{1.98\times }$. WHY less than $K$: Every rejection burns a whole target pass but only yields part of the guessed tokens. The waste caps the gain well below the naive "$K$ tokens per pass" dream.

WHAT: Write $\frac{1-{\alpha }^{K+1}}{1-\alpha }=1+\alpha +{\alpha }^2+\cdots +{\alpha }^K$ (finite geometric series, $K+1$ terms). As $\alpha \to 1$ every term $\to 1$, so the sum $\to K+1$. WHY / interpretation: If the draft is always right, we accept all $K$ guesses and also pick up the bonus token — $K+1$ tokens per single target pass. That is the theoretical ceiling on tokens-per-verification.

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

Model A ($\alpha =0.6$): $\mathbb{E}=\frac{1-0.6^5}{0.4}=\frac{1-0.07776}{0.4}=2.3056$. Cost $=4(1)+10=14$. Speedup $=\frac{10\times 2.3056}{14}=\frac{23.056}{14}\approx \boxed{1.647\times }$.

Model B ($\alpha =0.85$): $\mathbb{E}=\frac{1-0.85^5}{0.15}=\frac{1-0.4437053}{0.15}=3.70863$. Cost $=4(2)+10=18$. Speedup $=\frac{10\times 3.70863}{18}=\frac{37.0863}{18}\approx \boxed{2.060\times }$.

WHY B wins: Its far higher agreement ($0.85$ vs $0.6$) buys many more accepted tokens per pass ($3.71$ vs $2.31$), which more than pays for being twice as slow to draft. Agreement dominates draft speed here. See Knowledge distillation — the standard route to a high-$\alpha$ draft.

Speedup$(K)=\frac{c_p\frac{1-{\alpha }^{K+1}}{1-\alpha }}{K{c}_q+c_p}$. Numerator grows toward the ceiling $\frac{c_p}{1-\alpha }$ but with diminishing returns: each extra guess is reached only with probability ${\alpha }^K$, which shrinks geometrically. Denominator grows linearly in $K$ (each extra guess costs $c_q$ no matter what). Trade-off: Eventually the linear cost of extra draft passes outruns the saturating benefit, so there is an optimal lookahead $K_{\text{opt}}$ beyond which speedup falls. Larger $\alpha$ pushes $K_{\text{opt}}$ higher (agreement lets deep guesses survive); larger $c_q$ pushes $K_{\text{opt}}$ lower (each guess is expensive). A quick numeric sweep (see verify) with $\alpha =0.7,c_q=1,c_p=10$ finds speedup peaks around $K\approx 5\text{–}6$.

Setup. Two ways to emit $x$:

1. Accept branch: propose $x$ (prob $q(x)$) and accept it (prob $\min (1,p(x)/q(x))$). Contribution: $q(x)\min (1,\frac{p(x)}{q(x)})=\min (q(x),p(x))$.
2. Reject branch: some proposal gets rejected (total reject prob $R$), then we resample $x$ from $p_{\text{resample}}$. Contribution: $R\cdot p_{\text{resample}}(x)$.

Total reject probability. $R=1-{\sum }_{y}q(y)\min (1,\frac{p(y)}{q(y)})=1-{\sum }_y\min (q(y),p(y)).$ Normaliser of the resample. Using $\max (0,p-q)=p-\min (p,q)$, $Z={\sum }_y\max (0,p(y)-q(y))={\sum }_{y}p(y)-{\sum }_y\min (p(y),q(y))=1-{\sum }_y\min (p(y),q(y))=R.$ The $R$ cancels the $Z$! So the reject branch contributes $R\cdot \frac{\max (0,p(x)-q(x))}{Z}=\max (0,p(x)-q(x))=p(x)-\min (p(x),q(x)).$ Add the branches. $\underset{\text{accept}}{\underbrace{\min (q(x),p(x))}}+\underset{\text{reject}}{\underbrace{p(x)-\min (p(x),q(x))}}=p(x).■$ WHY it's beautiful: the reject mass $R$ exactly equals the missing mass $Z$, so resampling perfectly refills whatever the accept branch under-emitted. That cancellation is the mathematical heart of losslessness.

The flaw: Re-running the draft still samples from $q$, so the emitted token's distribution stays biased toward $q$, not $p$. From 5.1, the accept branch alone gives only $\min (p,q)$ — it undershoots $p$ wherever $p>q$. Without the $\max (0,p-q)$ resample, tokens the target favors more than the draft are permanently under-represented → output distribution $\ne p$ → not lossless. Correct fix's cost: you already have the target's full distribution $p(\cdot |x_{<t+i})$ from the same verification pass, so resampling from $\max (0,p-q)/Z$ is essentially free (one categorical draw). There is no reason to skip it. The colleague's idea trades a free correction for a broken guarantee.

L1 lossless means distribution match ::: distribution match, not identical text L2 accept prob for q=0.6,p=0.15 ::: 0.25 L2 cycle cost K=3,cq=1,cp=8 ::: 11 units L2 can a q=0 token still be emitted ::: yes, via the resample branch max(0,p-q)/Z L3 E[tokens] alpha=0.7,K=4 ::: about 2.773 L3 speedup alpha=0.7,K=4,cp=10 ::: about 1.98x L4 Model A vs B speedups ::: 1.647x vs 2.060x, B wins L5 losslessness key cancellation ::: reject mass R equals normaliser Z