Speculative Decoding Verification

HardML Coding

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 ids
  • draft_probs: a $K \times V$ array, the draft distribution $q$ at each position
  • target_probs: a $K \times V$ array, the target distribution $p$ at each position
  • coin_flips: $K$ uniform numbers in $[0, 1)$ for the accept/reject decisions
  • resample_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