← All problems
#87 Speculative Decoding Verification Medium

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\):

pos 0 pos 1 pos 2 pos 3 draft t₀ t₁ t₂ t₃ probs p(t₀) = 0.60 q(t₀) = 0.50 p(t₁) = 0.50 q(t₁) = 0.20 not reached not reached α, test α = .50/.60 = .83 u=0.1 < .83 ✓ α = .20/.50 = .40 u=0.7 ≥ .40 ✗ skipped skipped reject at pos 1 → stop, resample from adj(v) = max(0, q(v) − p(v)) normalize adj, inverse-CDF sample using u[b, T] → replacement token t₁′ output t₀ t₁′ 0 0 p = draft prob q = target prob α = min(1, q/p) ■ accepted ■ resampled ■ pad If all T tokens accepted: sample bonus token from q at last position using u[b, T]

For each sequence \(b\), process positions \(i = 0, 1, \ldots, T{-}1\) left-to-right:

  1. Compute acceptance probability: \(\displaystyle \alpha_i = \min\!\left(1,\; \frac{q_i(t_i)}{p_i(t_i)}\right)\)
  2. If \(u_i < \alpha_i\): accept \(t_i\), continue to position \(i{+}1\).
  3. If \(u_i \ge \alpha_i\): reject, stop. Sample replacement from: \[\text{adj}(v) = \frac{\max(0,\; q_i(v) - p_i(v))}{\sum_{v'} \max(0,\; q_i(v') - p_i(v'))}\] using inverse CDF with \(r = \texttt{uniform_samples}[b, T]\). If \(\text{adj}\) is all zeros, use uniform \(1/V\).
  4. If all \(T\) tokens accepted: sample a bonus token from \(q_{T-1}\) using \(\texttt{uniform_samples}[b, T]\).

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.

Implementation Requirements

Example

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}\]

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.