Speculative Decoding

Speculative decoding uses a small, fast draft model to guess γ candidate tokens ahead, then has the target model verify the whole candidate sequence in one parallel forward pass, accepting matching tokens and resampling where they diverge — turning each forward pass from producing 1 token into >1, trading decode's bandwidth-bound bottleneck for prefill-style compute parallelism. Pipeline: ① the draft model autoregressively generates $\gamma$ candidates (fast per-step on a small model); ② the target model does a single forward pass over the candidates, obtaining true next-token distributions $p_i$ alongside draft distributions $q_i$; ③ compare position by position — greedy mode accepts when argmax $p_i$ equals the draft token, otherwise rolls back and resamples from that position; ④ optionally use rejection sampling: accept with probability $\min(1, p_i/q_i)$, otherwise resample from $\text{norm}(\max(0, p_i - q_i))$, which provably preserves the target model's exact distribution (lossless). Speedup formula (acceptance rate $\alpha$, draft length $\gamma$, expected accepted tokens per round): $E \approx \frac{1 - \alpha^{\gamma}}{1 - \alpha}$. Worked example: $\alpha = 0.8,\ \gamma = 4$ → $E = \frac{1 - 0.8^4}{1 - 0.8} = \frac{0.5904}{0.2} \approx 2.95\times$. Note the diminishing returns of larger $\gamma$ (bounded by $1/(1-\alpha)$ as $\alpha^{\gamma} \to 0$): raising the acceptance rate beats lengthening the draft. Variants: EAGLE feeds the target model's previous-token hidden states through a small autoregressive head to predict the next layer's feature before mapping to vocabulary, giving high-quality drafts ($\alpha$ 0.7-0.9); Medusa attaches multiple parallel decoding heads to the backbone so no separate draft model is needed; both can use tree attention to verify several candidate branches in one forward pass, pushing $\alpha$ toward 1 while bounding verification cost.

any autoregressive serving where decode dominates (prefill already cached, throughput bound by token-at-a-time generation); built into vLLM/SGLang/TensorRT-LLM; interview favorites: "how do you compute the speedup", "why is verification one parallel pass", "EAGLE vs Medusa".

large-model decode produces 1 token per step and is HBM-bandwidth-bound (weight/KV reads ≫ compute), leaving tensor cores idle. Speculative decoding turns one serial step into a γ-token parallel verification at nearly the same forward cost (candidates are fed together, matrix parallelism amortizes), raising expected tokens per pass from 1 to $E$ — 2-3× throughput in practice, and with rejection sampling the output distribution is provably identical to the target model, so speedup costs no quality.

Describe the draft-verify flow and hand-compute the speedup: $E \approx \frac{1 - \alpha^{\gamma}}{1 - \alpha}$; with $\alpha=0.8,\gamma=4$ get ≈ 2.95×; explain why larger $\gamma$ has diminishing returns (bounded by $1/(1-\alpha)$).

Why verifying γ candidates in one pass costs almost no extra latency: candidates enter as one forward, per-position logits computed in parallel; contrast serial 1-token decode with γ-token verification.

How rejection sampling provably matches the target distribution (lossless): the math behind accept probability $\min(1, p_i/q_i)$ and resampling from $\text{norm}(\max(0, p_i - q_i))$.

EAGLE vs Medusa vs a separate small draft model: how drafts are produced, acceptance quality, training requirements, and how tree attention verifies multiple branches at once.

What determines the acceptance rate $\alpha$, how to measure and improve it; how draft-model distillation or weight sharing affects throughput and memory.