Implement the token verification step of speculative decoding. A draft model proposes \(T\) tokens;
the target model evaluates them in one forward pass and accepts or rejects each. Given \(B\)
sequences, produce the verified output tokens. Probability tensors are float32;
token tensors are int32.
Notation for each sequence \(b\), at each draft position \(i = 0, \ldots, T{-}1\):
For each sequence \(b\), process positions \(i = 0, 1, \ldots, T{-}1\) left-to-right:
Write results into output_tokens[b, :] (shape \([B, T{+}1]\)): accepted/resampled tokens
fill positions \(0\) through the accepted count (inclusive), remaining positions are zero.
solve(draft_tokens, draft_probs, target_probs, uniform_samples, output_tokens, B, T, V).output_tokens buffer (shape [B, T+1], int32).draft_probs[b, i, v] is at offset b*T*V + i*V + v.Input: \(B = 1,\; T = 3,\; V = 4\)
\(\text{draft_tokens} = [1, 2, 0]\)
Draft probabilities \(p_i\) and target probabilities \(q_i\) per position: \[ p_0 = \begin{bmatrix} 0.10 & 0.60 & 0.20 & 0.10 \end{bmatrix}, \quad q_0 = \begin{bmatrix} 0.10 & 0.50 & 0.20 & 0.20 \end{bmatrix} \] \[ p_1 = \begin{bmatrix} 0.10 & 0.20 & 0.50 & 0.20 \end{bmatrix}, \quad q_1 = \begin{bmatrix} 0.30 & 0.20 & 0.20 & 0.30 \end{bmatrix} \] \[ \text{uniform_samples} = \begin{bmatrix} 0.50 & 0.70 & 0.30 & 0.90 \end{bmatrix} \]
Position 0 (draft token = 1): \(\alpha_0 = \min\!\left(1,\, \frac{q_0(1)}{p_0(1)}\right) = \min\!\left(1,\, \frac{0.50}{0.60}\right) \approx 0.833\). Since \(u_0 = 0.50 < 0.833\), accept token 1.
Position 1 (draft token = 2): \(\alpha_1 = \min\!\left(1,\, \frac{q_1(2)}{p_1(2)}\right) = \min\!\left(1,\, \frac{0.20}{0.50}\right) = 0.40\). Since \(u_1 = 0.70 \ge 0.40\), reject. Resample from adjusted distribution: \[ \text{adj}(v) = \max(0,\, q_1(v) - p_1(v)) = [0.20,\, 0,\, 0,\, 0.10] \] \[ \text{normalized} = \left[\tfrac{2}{3},\, 0,\, 0,\, \tfrac{1}{3}\right], \quad \text{CDF} = [0.667,\, 0.667,\, 0.667,\, 1.0] \] With \(r = \text{uniform_samples}[0, T] = 0.90\), inverse CDF gives token 3.
Output: \[\text{output_tokens} = \begin{bmatrix} 1 & 3 & 0 & 0 \end{bmatrix}\]
B ≤ 256T ≤ 16V ≤ 131,072draft_probs[b, i, :] and target_probs[b, i, :] are valid probability distributions (non-negative, sum to 1)draft_probs[b, i, draft_tokens[b, i]] > 0 for all b, iuniform_samples values are in \([0, 1)\)float32; token tensors use int32B = 64, T = 8, V = 32,768