Speculative Decoding End-to-End Simulation
Problem statement
Implement speculative_decode(draft_probs, target_probs, draft_tokens, accept_rand, sample_rand), a full simulation of one round of speculative decoding, an inference acceleration technique for large language models.
A small, fast draft model proposes $K$ tokens, and a large target model verifies all of them in a single forward pass. Verifying $K$ tokens in parallel is much cheaper than generating them one at a time with the large model, and the accept/reject rule below guarantees the output follows the target model's distribution exactly.
Inputs:
draft_probs: $K$ probability vectors over the vocabulary, the draft model's distribution at each proposed position.target_probs: $K + 1$ probability vectors, the target model's distribution at each proposed position plus one extra position after the last draft token.draft_tokens: the $K$ token indices proposed by the draft model ($K$ may be 0).accept_rand: $K$ uniform random values in $[0, 1)$, one per accept/reject decision.sample_rand: $K + 1$ uniform random values in $[0, 1)$ used for sampling.
Procedure:
- Walk the draft tokens from left to right. At position $i$ with draft token $x$, accept it if
accept_rand[i]$< \min\big(1, p_{\text{target}}(x) / p_{\text{draft}}(x)\big)$ (treat the ratio as 1 if $p_{\text{draft}}(x) = 0$). - On the first rejection at position $i$, stop considering draft tokens. Instead sample a corrected token from the adjusted distribution $\max(0, p_{\text{target}} - p_{\text{draft}})$ at that position, renormalized to sum to 1 (use the uniform distribution if it is all zeros), using
sample_rand[i]. Return the accepted tokens followed by this corrected token. - If all $K$ draft tokens are accepted, sample one bonus token from
target_probs[K]usingsample_rand[K]and append it.
To sample a token from a distribution with a uniform value $u$, use the inverse CDF: return the smallest index whose cumulative probability exceeds $u$.
Return the list of token indices produced by the round.
Example
Input:
draft_probs = [[0.1, 0.7, 0.2], [0.3, 0.4, 0.3]]
target_probs = [[0.5, 0.3, 0.2], [0.2, 0.5, 0.3], [0.4, 0.4, 0.2]]
draft_tokens = [1, 1]
accept_rand = [0.9, 0.5]
sample_rand = [0.3, 0.5, 0.5]
Output:
[0]
Reasoning: At position 0 the draft proposes token 1 with draft probability 0.7 and target probability 0.3, so the acceptance probability is min(1, 0.3/0.7) = 0.4286. Since accept_rand[0] = 0.9 is not below it, the token is rejected. The adjusted distribution max(0, [0.5 - 0.1, 0.3 - 0.7, 0.2 - 0.2]) = [0.4, 0, 0] normalizes to [1, 0, 0], so sample_rand[0] = 0.3 picks token 0 and the round ends with [0].
Show hint
If the draft model proposes a token the target model likes less, with what probability should you keep it so the overall output still follows the target?
Relevant roles: LLM Engineer, ML Engineer, Deep Learning Engineer, Research Scientist and MLOps Engineer.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium