Derive the expected speedup of speculative decoding, prove it does not change the output distribution, and tell me when it stops paying.

TL;DR: With per-token acceptance $\alpha$ and draft length $\gamma$, one target pass emits $\frac{1-\alpha^{\gamma+1}}{1-\alpha}$ tokens: 3.36 at $\alpha = 0.8, \gamma = 4$, a 2.8x speedup when a draft step costs 5% of a target step. Accepting with $\min(1, p/q)$ and resampling rejections from $(p-q)_+$ makes the output exactly $p$. It stops paying once the batch is large enough that verifying $\gamma + 1$ tokens per sequence no longer fits in the compute a bandwidth-bound decode step leaves idle.

How to approach it

Frame speculation as trading idle arithmetic for fewer sequential steps, because that framing produces all three answers. Decode is bandwidth-bound, so a target forward pass over 5 tokens costs about the same as over 1. Ask what the draft is (a separate small model, an EAGLE-style head on the target's hidden states, n-gram lookup), what the batch size is, and whether sampling is greedy or at temperature, since the verification rule differs.

A strong answer

The algebra. Assume each draft token is accepted independently with probability $\alpha$, and the first rejection ends the step. The target always contributes one token, either the correction at the first rejection or a bonus token if all $\gamma$ drafts pass. The number of accepted drafts is truncated-geometric, so the tokens per target pass are:

$$\mathbb{E}[\text{tokens}] = \sum_{i=0}^{\gamma} \alpha^i = \frac{1 - \alpha^{\gamma+1}}{1 - \alpha}$$

If one draft step costs $c$ target steps, a speculative step costs $\gamma c + 1$, and the speedup over plain decoding is $\mathbb{E}[\text{tokens}] / (\gamma c + 1)$:

alpha = 0.8, gamma = 4:  E = (1 - 0.8^5) / 0.2 = 3.36 tokens per target pass
c = 0.05:                speedup = 3.36 / (4 x 0.05 + 1) = 3.36 / 1.20 = 2.80x
sanity: alpha -> 1 gives gamma + 1 = 5 tokens; alpha -> 0 gives 1 token at extra cost

The table overstates long drafts: real acceptance falls with position, because a draft conditioned on its own earlier guesses drifts. That is why typical configurations propose only a handful of draft tokens per step, and why the measured quantity to report is mean accepted length per step rather than a single $\alpha$.

The proof. Let the draft propose $x \sim q$. Accept with probability $\min(1, p(x)/q(x))$. On rejection, sample from the residual $r(x) = \frac{(p(x) - q(x))_+}{\sum_y (p(y)-q(y))_+}$. The total acceptance probability is $\alpha = \sum_x \min(p(x), q(x))$, so the rejection mass is $1 - \alpha = \sum_x (p(x)-q(x))_+$, and:

$$P(\text{emit } x) = q(x)\min\!\Big(1, \tfrac{p(x)}{q(x)}\Big) + (1-\alpha)\, r(x) = \min(p,q)(x) + (p-q)_+(x) = p(x)$$

The same identity also gives the acceptance rate: $\alpha = 1 - \mathrm{TV}(p, q)$, the total-variation distance between draft and target. A run of 200,000 trials with a deliberately poor draft ($\alpha = 0.55$) reproduced the target distribution to within 0.002 and measured acceptance 0.552. The reference verifier:

import numpy as np

def verify(p, q, draft, rng):
    """p: [gamma+1, V] target probs, q: [gamma, V] draft probs,
    draft: gamma token ids sampled from q. Returns the emitted tokens."""
    out = []
    for i, t in enumerate(draft):
        if rng.random() < min(1.0, p[i, t] / q[i, t]):
            out.append(t)                        # accept the draft token
            continue
        resid = np.maximum(p[i] - q[i], 0.0)     # reject: resample from (p - q)+
        out.append(rng.choice(len(resid), p=resid / resid.sum()))
        return out
    out.append(rng.choice(p.shape[1], p=p[-1]))  # all accepted: bonus token
    return out

When it stops paying. The cost model assumed a verify pass costs one target step. That holds only while the target is bandwidth-bound. Verification feeds $B(\gamma+1)$ tokens through the weights per step, and on an H100 in BF16 a decode step turns compute-bound near 295 tokens of work. With $\gamma = 4$ that budget is exhausted near $B = 295 / 5 \approx 59$. Past it, verification costs more than one step, rejected drafts become wasted FLOPs, and the speedup shrinks toward 1 and can go below it. The EAGLE-3 authors report this shape themselves: large gains at batch 1 and a much smaller throughput gain at batch 64 in SGLang (their arXiv abstract gives 1.38x). The decision is therefore per load level, which is why engines expose speculation as a setting to turn down under heavy traffic.

What interviewers probe next

"Why does EAGLE beat an independent small draft model?" It predicts from the target's own hidden states, so its proposals sit closer to $p$: higher $\alpha$ at a lower $c$, both terms improving at once.

"Temperature zero: what changes?" Verification becomes exact match against the target's argmax, and the residual step disappears. The speedup formula is unchanged.

"Draft and target tokenizers differ." Then token-level verification is undefined. Either share a vocabulary or verify at the string level, which costs much of the gain.

"Tree drafts?" Verify several candidate continuations in one pass with a tree attention mask. Accepted length goes up and so does $B(\gamma+1)$, which moves the break-even batch down.

How it's scored

Weak: says speculation "predicts several tokens at once" with no acceptance model, or claims a fixed speedup independent of batch size.

Hire: derives the truncated-geometric expectation, includes the draft's cost, and states the $\min(1, p/q)$ rule.

Strong Hire: proves losslessness including the residual distribution, identifies $\alpha = 1 - \mathrm{TV}(p,q)$, and computes the batch size where verification stops being free from the ridge point.

Common mistakes

• Resampling rejections from $p$ instead of $(p - q)_+$. The output is then $\min(p,q) + (1-\alpha)p$: in the 200,000-trial run the target's most likely token, at 0.40, was emitted only 28% of the time.
• Forgetting the bonus token, which undercounts by one token per fully accepted step.
• Benchmarking at batch 1 and promising the same gain to a fleet that runs at batch 128.
• Reporting $\alpha$ from one prompt domain. Acceptance on code is often far higher than on open chat, so a mixed workload needs a mixed measurement.