Speculative Decoding Verification
Problem statement
Speculative decoding speeds up large language model inference. A small, fast draft model proposes $K$ tokens, and the large target model scores all of them in one forward pass. A verification rule then decides which draft tokens to keep, in a way that leaves the output distributed exactly as if the target model had generated it alone.
Implement speculative_decode_verify(draft_tokens, draft_probs, target_probs, coin_flips, resample_coin):
draft_tokens: the $K$ proposed token idsdraft_probs: a $K \times V$ array, the draft distribution $q$ at each positiontarget_probs: a $K \times V$ array, the target distribution $p$ at each positioncoin_flips: $K$ uniform numbers in $[0, 1)$ for the accept/reject decisionsresample_coin: one uniform number in $[0, 1)$ used if a rejection happens
Process positions in order. At position $i$ with draft token $x_i$:
- Accept if
coin_flips[i]$< \min\left(1, p(x_i) / q(x_i)\right)$ (strictly less), and move on. - Otherwise reject: build the adjusted distribution $p'(x) = \max(0, p(x) - q(x)) / \sum_{x'} \max(0, p(x') - q(x'))$ at that position, sample one replacement token from it by inverse CDF (the first index whose cumulative probability is $\ge$
resample_coin), append it, and stop. Remaining draft tokens are discarded.
If all $K$ tokens are accepted, return them all (no extra token). Return the list of final token ids.
Example
Input:
draft_tokens = [0, 2]
draft_probs = [[0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.5, 0.2]]
target_probs = [[0.5, 0.2, 0.2, 0.1], [0.1, 0.3, 0.3, 0.3]]
coin_flips = [0.3, 0.7]
resample_coin = 0.5
Output:
[0, 1]
Reasoning: at position 0, $q = 0.4$ and $p = 0.5$, so the acceptance probability is 1 and token 0 is kept. At position 1, $q = 0.5$ and $p = 0.3$, so the acceptance probability is 0.6, and the coin 0.7 rejects. The residual is $\max(0, p - q) = [0, 0.1, 0, 0.1]$, normalized to $[0, 0.5, 0, 0.5]$ with cumulative sums $[0, 0.5, 0.5, 1.0]$. The first index with cumulative sum at least 0.5 is 1, so the output is [0, 1].
Show hint
If the draft model overestimated a token's probability compared to the target, how should that change the chance you keep it?
Relevant roles: LLM Engineer, ML Engineer, AI Engineer, Gen AI Engineer and Research Scientist.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium