I3Hard★ Core Essential · Industrial BedrockPart I · Inference, Decoding & Quantization
Speculative Decoding Verification & Accept/Reject
Verify K draft tokens in one parallel target forward pass with exact acceptance/residual resampling.
⏱️ Time:
大模型调用次数缩减至原先的 1/(1 - 平均接受率)💾 Space:
需同时在显存中维护大模型和小模型的 KV 缓存🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
def speculative_step_verification(
draft_tokens: list, # 长度为 K 的草稿 Token 序列
p_probs: np.ndarray, # (K, V) 大目标模型在各位置预测的概率分布
q_probs: np.ndarray # (K, V) 小草稿模型在各位置预测的概率分布
) -> list:
"""
执行投机解码单批验证。
返回: 最终被接受与修正采样的 Token 列表
"""
accepted_tokens = []
K = len(draft_tokens)
for i in range(K):
token = draft_tokens[i]
p_val = p_probs[i, token]
q_val = q_probs[i, token]
# 1. 接受概率: min(1, p/q)
acceptance_prob =
# 2. 掷骰子决定是否接受
if np.random.rand() < acceptance_prob:
accepted_tokens.append(token)
else:
# 3. 拒绝!从残差修正分布中采样并立即截断后续
residual = np.maximum(0.0, p_probs[i] - q_probs[i])
res_sum = np.sum(residual)
if res_sum > 0:
p_prime = residual / res_sum
resampled_token = int(np.random.choice(len(p_prime), p=p_prime))
else:
resampled_token =
accepted_tokens.append(resampled_token)
return accepted_tokens # 终止后续
# 如果全部接受,还可以免费多采一个额外 Token
return accepted_tokens
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: How do Medusa and Eagle improve upon standalone draft-model speculative decoding?
💡
Core Mental Anchor / Mnemonic
Accept draft with prob min(1, p/q); on rejection, resample from normalized max(0, p - q).
📐 Mathematical Derivation & Core Formula
### Lossless Rejection Sampling Proof
Because autoregressive decoding is memory-bandwidth-bound, verifying positions in one forward pass costs almost the same as 1 step:
1. A small draft model generates candidate tokens ;
2. Target model evaluates all probabilities in parallel;
3. Each token is accepted with probability . Upon the first rejection, resample a token from the residual distribution .
Mathematically, accepted + resampled draws preserve the exact target distribution , yielding lossless speedups (often 2–3x in memory-bound regimes depending on acceptance rate and draft cost).
Because autoregressive decoding is memory-bandwidth-bound, verifying positions in one forward pass costs almost the same as 1 step:
1. A small draft model generates candidate tokens ;
2. Target model evaluates all probabilities in parallel;
3. Each token is accepted with probability . Upon the first rejection, resample a token from the residual distribution .
Mathematically, accepted + resampled draws preserve the exact target distribution , yielding lossless speedups (often 2–3x in memory-bound regimes depending on acceptance rate and draft cost).
🔄 Tensor Dimensions & Shape Flow
draft_tokens (K,) -> accept w.p. min(1, p/q) -> on first reject sample max(0, p-q) residual and stop
🛡️ Numerical Stability & Pitfalls Checklist
- Guard
q_valdenominator with small epsilon (e.g., 1e-12) against division by zero. - Normalize
max(0, p - q)cleanly and fall back topif numerical rounding leaves sum <= 0.
💻 Reference Code Implementation
import numpy as np
def speculative_step_verification(
draft_tokens: list, # 长度为 K 的草稿 Token 序列
p_probs: np.ndarray, # (K, V) 大目标模型在各位置预测的概率分布
q_probs: np.ndarray # (K, V) 小草稿模型在各位置预测的概率分布
) -> list:
"""
执行投机解码单批验证。
返回: 最终被接受与修正采样的 Token 列表
"""
accepted_tokens = []
K = len(draft_tokens)
for i in range(K):
token = draft_tokens[i]
p_val = p_probs[i, token]
q_val = q_probs[i, token]
# 1. 接受概率: min(1, p/q)
acceptance_prob = min(1.0, p_val / (q_val + 1e-12))
# 2. 掷骰子决定是否接受
if np.random.rand() < acceptance_prob:
accepted_tokens.append(token)
else:
# 3. 拒绝!从残差修正分布中采样并立即截断后续
residual = np.maximum(0.0, p_probs[i] - q_probs[i])
res_sum = np.sum(residual)
if res_sum > 0:
p_prime = residual / res_sum
resampled_token = int(np.random.choice(len(p_prime), p=p_prime))
else:
resampled_token = int(np.argmax(p_probs[i]))
accepted_tokens.append(resampled_token)
return accepted_tokens # 终止后续
# 如果全部接受,还可以免费多采一个额外 Token
return accepted_tokens
🧪 Runnable Assertions & Validation
Copy and run directly in Python / Jupyter:
import numpy as np
# 模拟目标大模型与草稿模型分布完全一致
K, V = 3, 10
p = np.ones((K, V)) / V
q = p.copy()
draft = [1, 2, 3]
res = speculative_step_verification(draft, p, q)
assert res == draft, "完全相同分布下应 100% 接受"
print("✓ 投机解码验证与残差重采样自测通过")🎯 Core Follow-up Inquiries & Reference Answers
Q1:How do Medusa and Eagle improve upon standalone draft-model speculative decoding?
Instead of deploying and scheduling a separate draft LLM, Medusa and Eagle attach lightweight prediction heads directly atop the target model's hidden states to propose candidate token trees in parallel.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.