LLM 推测解码精读笔记 · 02 原始推测解码：草稿模型与拒绝采样
对应：Leviathan et al., Fast Inference from Transformers via Speculative Decoding（arXiv:2211.17192，2023）；Chen et al., Accelerating LLM Inference with Staged Speculative Decoding（arXiv:2302.01318，2023）。 前置：01 章的接受率数学（$\alpha$、$E[N]$、$c$）。学完本章你应该能：① 写出推测解码的完整算法（草稿 + 并行验证 + 拒绝采样修正）；② 完整证明无损性定理（输出分布严格等于目标分布，且与草稿质量无关）；③ 推导最优草稿长度 $K^*$ 的驻点方程并解释其单调性；④ 手算一个完整轮次的逐步追踪；⑤ 说清贪心解码下接受规则如何退化为"argmax 相等"；⑥ 列出工程实现里最容易破坏无损性的几个坑。
目录（本章） #
- 本章目标
- 从 01 到 02：还差什么
- 设置与记号
- 完整算法：Speculative Sampling
- 无损性定理：完整证明
- 每轮成本与加速比回顾
- 最优草稿长度 K*
- 草稿模型怎么选：α 与 c 的权衡
- 数值算例：完整一轮的逐步追踪
- 贪心解码的特殊情形
- 实现细节与常见坑
- 变体预告：Staged Speculative Decoding
- 本章小结
- 习题与解答
- 延伸阅读
2. 从 01 到 02：还差什么 #
01 章给了三个公式：接受概率 $\alpha = \sum_x \min(p(x), q(x))$、期望产出 $E[N] = (1-\alpha^{K+1})/(1-\alpha)$、加速比 $\text{speedup} = E[N]\cdot c/(c+K)$。但还差三件事：
- 算法本身：验证阶段到底怎么"从左到右逐个检查"？拒绝之后用什么分布补一个 token？
- 无损性的完整证明：01 章验证了"单个位置的边际分布等于 $p$"，但整个序列的联合分布呢？需要归纳法。
- 参数怎么定：$K$ 取多少最好？草稿模型选多大？这就是本章的最优 $K^*$ 与草稿规模权衡。
3. 设置与记号 #
沿用 01 章并补充：
| 符号 | 含义 |
|---|---|
| $\mathcal{V}$ | 词表，$ |
$x_{| 已生成前缀 | |
| $p(\cdot \mid h)$ | 目标模型给定历史 $h$ 的条件分布 |
| $q(\cdot \mid h)$ | 草稿模型给定历史 $h$ 的条件分布 |
| $\tilde{x}_i$ | 第 $i$ 个草稿 token（$i = 1, \dots, K$） |
| $r_i$ | 第 $i$ 次接受决策用的均匀随机数 $r_i \sim U[0,1]$ |
| $p_r$ | 修正分布（拒绝后的重采样分布） |
两个贯穿全章的前提假设（违反任何一个，算法都无法成立）：
- 共享词表与 tokenizer：$p$ 和 $q$ 必须在同一个词表上给出概率，否则 $p(x)/q(x)$ 没有定义，草稿序列也无法与目标序列拼接。
- 条件概率可比：验证时 $p$ 和 $q$ 的 logits 必须对应同一解码策略（温度等），否则接受概率算错。
4. 完整算法：Speculative Sampling #
Leviathan et al. 的 Algorithm 1（按概率采样版本）：
输入：目标模型 p、草稿模型 q、前缀 x_<t、草稿长度 K、随机数序列 r_1, r_2, ...
输出：N 个新 token，其分布与直接用 p 自回归采样完全一致
一、草稿阶段（K 步自回归，每步只跑 q）
x̃_1 ~ q(· | x_<t)
for i = 2 .. K:
x̃_i ~ q(· | x_<t, x̃_1, ..., x̃_{i-1})
二、验证阶段（一次目标前向，并行计算 K+1 个位置）
同时算出 p(·|x_<t), p(·|x_<t,x̃_1), ..., p(·|x_<t,x̃_1..x̃_K)
三、接受阶段（从左到右逐个检查）
for i = 1 .. K:
if r_i ≤ min(1, p(x̃_i | x_<t, x̃_<i) / q(x̃_i | x_<t, x̃_<i)):
接受 x̃_i
else:
从修正分布 p_r(· | x_<t, x̃_<i) ∝ max(0, p(·) - q(·)) 采样 x
输出 x̃_1, ..., x̃_{i-1}, x；本轮结束
若全部 K 个都被接受：
从 p(· | x_<t, x̃_1..x̃_K) 采样 bonus token x
输出 x̃_1, ..., x̃_K, x；本轮结束
4.1 三个阶段的代价 #
草稿阶段：K 步 q 前向 → 代价 K·T_q
验证阶段：1 次 p 前向（K+1 个位置）→ 代价 ≈ T_p
接受阶段：纯标量比较 + 一次重采样 → 代价可忽略
验证前向一次处理 $K+1$ 个位置，代价近似一次正常解码 $T_p$（当序列很长时，多算 $K$ 个位置的开销占比很小，第 6 节细说）。
4.2 为什么"每轮至少 1 个、至多 K+1 个 token" #
- 若第 1 个草稿就被拒绝：输出修正 token $x$，$N=1$。
- 若全部接受：第 $K+1$ 个位置没有草稿，直接从 $p$ 采样 bonus token，$N = K+1$。
- 一般情况下：接受前 $i-1$ 个、拒绝第 $i$ 个并输出修正 token，$N = i$。
这与 01 章 4.3 节的分布 $P(N=i)$ 完全对应。
5. 无损性定理：完整证明 #
5.1 引理 1：修正分布是合法分布 #
对任意历史 $h$，定义该位置的接受概率
$$ \alpha(h) = \sum_x \min(p(x \mid h), q(x \mid h)), \qquad \beta(h) = 1 - \alpha(h) $$命题：$\beta(h) = \sum_x \max(0, p(x \mid h) - q(x \mid h)) \ge 0$，且当 $\beta(h) > 0$ 时 $p_r$ 是合法概率分布。
证明：利用恒等式 $\max(0, a-b) = \frac{a-b+|a-b|}{2}$：
$$ \sum_x \max(0, p-q) = \frac{1}{2}\sum_x (p-q) + \frac{1}{2}\sum_x |p-q| = 0 + \mathrm{TV}(p,q) = 1 - \alpha(h) $$其中 $\sum_x (p-q) = 0$（两个分布各自归一），且由 01 章 $\alpha = 1 - \mathrm{TV}(p,q)$。因此残差非负、和为 $\beta(h)$，归一化后 $p_r(x) = \max(0,p-q)/\beta(h)$ 是合法分布。$\blacksquare$
5.2 引理 2：单位置边际分布不变 #
命题：到达草稿位置 $i$（即前 $i-1$ 个草稿均被接受，历史为 $h$）时，该位置最终输出 token 的条件分布恰为 $p(\cdot \mid h)$。
证明：给定历史 $h$，该位置的输出有两种路径：
$$ P_{\text{emit}}(x \mid h) = \underbrace{q(x \mid h)\cdot \min\!\left(1, \frac{p(x\mid h)}{q(x\mid h)}\right)}_{\text{直接接受}} + \underbrace{\beta(h)\cdot \frac{\max(0, p(x\mid h)-q(x\mid h))}{\beta(h)}}_{\text{拒绝后重采样}} $$第一项中：若 $p \ge q$，则 $\min(1, p/q) = 1$，第一项 $= q$；若 $p < q$，则第一项 $= p$。合并：
$$ P_{\text{emit}}(x \mid h) = \min(p(x\mid h), q(x\mid h)) + \max(0, p(x\mid h)-q(x\mid h)) = p(x \mid h) $$两种情形分别验证：$p \ge q$ 时第一项 $q$ 加残差 $p-q$ 得 $p$；$p < q$ 时第一项即 $p$、残差为 0。$\blacksquare$
5.3 定理：序列级无损 #
定理（Leviathan et al., Thm 1）：对任意草稿分布 $q$、任意草稿长度 $K$，推测解码生成的完整 token 序列与直接从 $p$ 自回归采样得到的序列同分布。
证明（对位置归纳）：
- 基步：每轮开始时，历史是已输出的全部 token。第 1 个草稿位置的历史 $h = x_{
- 归纳步：假设前 $i-1$ 个位置输出 token 的条件分布与 $p$ 自回归一致（即 $x_{t}, \dots, x_{t+i-2}$ 的联合分布正确）。到达位置 $i$ 时，历史 $h$ 等于前缀加上这些已输出 token；由引理 2，位置 $i$ 输出 token 的条件分布是 $p(\cdot \mid h)$。因此前 $i$ 个位置的联合分布仍然正确。
- 轮次切换：当发生拒绝或全部接受时，本轮结束、新轮开始。新轮的第 1 个位置以"全部已输出 token"为历史，基步重新适用。于是归纳可跨越轮次一直进行。
由归纳法，任意前缀长度下生成的序列分布都等于 $p$ 的自回归采样分布。$\blacksquare$
5.4 三个推论 #
- 正确性与草稿质量无关：$q$ 再差（甚至均匀分布），输出分布依然精确等于 $p$，只是 $E[N] \to 1$、没有加速。
- 正确性与 $K$ 无关：$K$ 只影响速度和效率，不影响正确性。
- 对任意解码策略成立：贪心、温度采样、top-$k$ 等，只要 $p$、$q$ 用同一策略，定理都成立。
这是推测解码与量化最本质的分界线：量化有损（改变分布），推测解码理论无损。工程实现可能引入近似（第 11 节），但算法本身是精确的。
6. 每轮成本与加速比回顾 #
一轮的墙钟时间与产出：
$$ T_{\text{round}} = T_p + K\cdot T_q, \qquad E[N] = \frac{1-\alpha^{K+1}}{1-\alpha} $$加速比（$c = T_p/T_q$）：
$$ \text{speedup}(K) = \frac{E[N]\cdot c}{c+K} $$两个精度说明（写论文/工程报告时会遇到）：
- 验证前向实际处理 $L + K$ 个位置（$L$ 为已有序列长），比正常 decode 一步略贵；精确写为 $T_p(L+K)$。当 $L \gg K$ 时可忽略；短序列时 $T_p$ 偏乐观，加速比要打折。
- 草稿阶段的 $K$ 步自回归是串行的；若草稿模型与目标模型在同一张卡上交替运行，还可能引入 kernel 切换开销。实际系统往往把多个请求的草稿/验证阶段分别批处理来摊薄这些开销（06 章详述）。
7. 最优草稿长度 K* #
7.1 驻点方程 #
把 $K$ 视为连续变量，对
$$ f(K) = \frac{c}{1-\alpha}\cdot\frac{1-\alpha^{K+1}}{c+K} $$求对数导数并令其为 0：
$$ \frac{d}{dK}\ln f = -\frac{\alpha^{K+1}\ln\alpha}{1-\alpha^{K+1}} - \frac{1}{c+K} = 0 $$令 $L = \ln(1/\alpha) > 0$（即 $-\ln\alpha$），整理得驻点方程：
$$ \alpha^{K^*+1}\left[1 + (c + K^*)\, L\right] = 1 $$这是超越方程，无闭式解，只能数值求解；且解唯一（$f(K)$ 先增后减）。
7.2 直觉：边际收益递减 #
从 $K$ 加到 $K+1$ 个草稿：
- 收益：多一个草稿 token 的期望价值是"前 $K+1$ 个草稿全部被接受"的概率，即 $\alpha^{K+1}$ 个目标 token；
- 成本：多花一步草稿时间 $T_q$。
粗略的停止准则：
$$ \alpha^{K+1}\cdot c \gtrsim 1 \quad\Longleftrightarrow\quad K \lesssim \frac{\ln c}{\ln(1/\alpha)} - 1 $$即"再加一个草稿的期望收益抵不上一步草稿开销"时就该停。这条近似与精确驻点方程同向（精确解见下表）。
7.3 数值表（精确 $K^*$） #
对驻点方程做整数搜索（$K \in \{1,\dots,64\}$ 中取最大 $f(K)$）：
| α | c | K* | speedup(K*) | speedup(K*−2) | speedup(K*+2) |
|---|---|---|---|---|---|
| 0.6 | 5 | 2 | 1.40x | 1.33（K=1） | 1.28 |
| 0.6 | 10 | 3 | 1.67x | 1.45 | 1.59 |
| 0.7 | 10 | 4 | 1.98x | 1.82 | 1.91 |
| 0.8 | 10 | 6 | 2.47x | 2.40 | 2.40 |
| 0.8 | 20 | 8 | 3.09x | 3.04 | 3.05 |
| 0.9 | 10 | 10 | 3.43x | 3.40 | 3.39 |
| 0.9 | 20 | 13 | 4.67x | 4.63 | 4.66 |
| 0.95 | 20 | 21 | 6.60x | 6.58 | 6.59 |
三个可验证的规律：
- $K^*$ 随 $\alpha$ 增大而增大：草稿越准，多猜几步越划算。
- $K^*$ 随 $c$ 增大而增大：草稿相对越快，多猜几步越划算。
- 峰值附近曲线平坦（α 高时）：α ≥ 0.8 时 $K^* \pm 2$ 的加速比损失通常 < 3%；α 低（0.6 左右）时对 $K$ 更敏感，应更贴近 $K^*$。总体上"偏大一点"比"偏小"更安全：草稿不足时 $E[N]$ 掉得快，多付几步草稿费损失小。
8. 草稿模型怎么选：α 与 c 的权衡 #
8.1 两个失败模式 #
草稿太小（如随机预测）：α → 0.5 以下，E[N] ≈ 1，加速比 < 1
草稿太大（接近目标模型）：α 高，但 c → 1，加速比上限 c → 1
总收益对草稿规模不是单调的，而是先升后降的倒 U 形：
$$ \text{speedup} = \underbrace{\frac{1-\alpha(K)^{K+1}}{1-\alpha(K)}}_{E[N](\alpha)} \times \underbrace{\frac{c(K)}{c(K)+K}}_{\text{草稿开销项}} $$增大草稿规模时：$\alpha$ 上升（第一项变大）、$c$ 下降（第二项变小），最优值在中间。
8.2 示意数值（同一目标模型、不同草稿规模） #
以下数据为教学示意（$K$ 取该行的最优值），展示趋势：
| 草稿规模 | α（估计） | c（估计） | K* | speedup |
|---|---|---|---|---|
| 极小（~1% 参数） | 0.55 | 25 | 4 | 1.41x |
| 小（~5% 参数） | 0.70 | 15 | 5 | 2.07x |
| 中（~10% 参数） | 0.80 | 10 | 6 | 2.47x |
| 大（~30% 参数） | 0.88 | 4 | 5 | 1.91x |
| 接近目标 | 0.95 | 1.3 | 3 | 1.19x |
Leviathan et al. 的实验印证了这一趋势：以 T5-XXL（11B）为目标、T5-small（约 60M，约 0.5% 参数）为草稿，在翻译与摘要任务上获得 2–3x 墙钟加速，且输出质量与目标模型单独解码一致（这就是无损性的实验证据）。
8.3 工程结论 #
选择草稿模型不是"越大越好"，而是在你的真实负载上同时测量 $\alpha$ 和 $c$，再最大化上式。这意味着需要一个验收协议：在代表性数据集上统计接受率、测量每 token 延迟，再调 $K$。这正是 06 章"生产验收"的内容。
9. 数值算例：完整一轮的逐步追踪 #
设前缀固定，词表为 $\{\text{A}, \text{B}, \text{C}, \text{D}, \text{E}\}$：
$$ q = (0.50,\ 0.20,\ 0.15,\ 0.10,\ 0.05), \qquad p = (0.30,\ 0.35,\ 0.20,\ 0.10,\ 0.05) $$9.1 先算 α、β、p_r #
$$ \alpha = \sum_x \min(p,q) = 0.30 + 0.20 + 0.15 + 0.10 + 0.05 = 0.80 $$$$ \beta = 1 - \alpha = 0.20 $$残差（只在 $p > q$ 的位置非零）：B 的残差 $0.35-0.20=0.15$，C 的残差 $0.20-0.15=0.05$。所以
$$ p_r = \left(0,\ \frac{0.15}{0.20},\ \frac{0.05}{0.20},\ 0,\ 0\right) = (0,\ 0.75,\ 0.25,\ 0,\ 0) $$直观含义：拒绝后只能在 B、C 之间重采样——因为只有这两个位置是"目标比草稿更相信"的。
9.2 追踪一轮（K = 3） #
草稿阶段，从 $q$ 采样得到：
$$ \tilde{x}_1 = \text{A},\quad \tilde{x}_2 = \text{B},\quad \tilde{x}_3 = \text{A} $$验证阶段，目标一次前向得到 4 个位置的条件分布；接受阶段逐位检查（随机数 $r_i$ 是演示给的）：
位置 1（$\tilde{x}_1 = \text{A}$）：
$$ \frac{p(\text{A})}{q(\text{A})} = \frac{0.30}{0.50} = 0.60 \quad\Rightarrow\quad \text{接受概率} = \min(1, 0.60) = 0.60 $$设 $r_1 = 0.35 < 0.60$ → 接受 A。
位置 2（$\tilde{x}_2 = \text{B}$）：
$$ \frac{p(\text{B})}{q(\text{B})} = \frac{0.35}{0.20} = 1.75 > 1 \quad\Rightarrow\quad \text{接受概率} = 1 $$→ 无条件接受 B（目标比草稿更看好 B，草稿猜对了）。
位置 3（$\tilde{x}_3 = \text{A}$）：
$$ \frac{p(\text{A})}{q(\text{A})} = 0.60, \qquad r_3 = 0.80 > 0.60 $$→ 拒绝。从修正分布重采样：B 概率 0.75，C 概率 0.25；设采样到 B，输出修正 token = B。
本轮产出：A, B, B，即 $N = 3$。
9.3 与公式对照 #
$$ E[N] = \frac{1-\alpha^{K+1}}{1-\alpha} = \frac{1-0.8^4}{0.2} = \frac{1-0.4096}{0.2} = 2.952 $$设 $c = 10$：
$$ \text{speedup} = \frac{2.952 \times 10}{10 + 3} = 2.27\text{x} $$这一轮实际产出 3 个 token，比期望值略高，属于正常波动。
10. 贪心解码的特殊情形 #
当 $p$、$q$ 都做贪心解码（每步取 argmax）时，$p(\cdot\mid h)$、$q(\cdot\mid h)$ 都是单点分布，接受规则退化为：
$$ \text{接受 } \tilde{x}_i \iff \tilde{x}_i = \arg\max_x p(x \mid h) $$证明：单点分布下 $p/q$ 要么 $1$（$\tilde{x}_i$ 同时是两个模型的 argmax）要么 $0$（不是目标 argmax），$\min(1, p/q)$ 即指示函数。拒绝时的修正分布也退化为"目标模型的 argmax"这一个 token。
贪心版接受规则（等价于原始算法，且同样严格无损）：
从左到右比较草稿 token 与目标 argmax：
相等 → 接受
不等 → 输出目标 argmax，本轮结束
注意：如果 $q$ 是采样、$p$ 是贪心（或反过来），“逐位比较"规则不再等价于拒绝采样，会破坏严格无损。工程实现若混用策略，必须清楚自己放弃了精确性（第 11 节）。
11. 实现细节与常见坑 #
11.1 会破坏严格无损的近似 #
| 常见做法 | 后果 |
|---|---|
| 无条件接受第一个草稿 token（“greedy-first” 提速技巧） | 第一位置不再是拒绝采样，边际分布偏离 $p$（偏差通常小，但理论不再无损） |
| $p$、$q$ 温度/策略不一致 | $p/q$ 计算无意义，接受规则失效 |
| 验证时用 argmax 代替采样分布 | 只对双方都贪心时正确 |
| 拒绝后不重采样，直接丢弃 | 概率质量被抹掉，分布坍缩 |
11.2 KV cache 怎么处理 #
- 验证前向中，目标模型会顺便计算草稿 token 的 KV；被接受的草稿 token 的 KV 直接复用，下一轮不需要重算。
- 发生拒绝的位置之后的 KV 作废（本轮结束时丢弃）。
- 草稿模型自己的 KV 也要维护（每轮从同一前缀重新生成草稿，或增量续草稿——增量方案见 03/04 章）。
11.3 其他工程细节 #
- 随机数：$r_i$ 与重采样必须走确定性的 RNG 序列，否则不可复现；多请求批处理时各请求的 RNG 要隔离。
- batch 化：多个请求同时进入时，草稿阶段可以按请求各自跑，验证阶段把不同长度的草稿序列 pad 到同一长度后一次前向，最大化验证吞吐。
- 词表一致性：草稿与目标必须共享 tokenizer；这也是后面 Medusa/EAGLE 这类"模型自带草稿"路线的一个动机——天然共享词表与表示。
- 退化情形：$\alpha = 1$（$p \equiv q$）时 $E[N] = K+1$，加速比 $(K+1)c/(c+K)$，推测解码变成"批量自回归”。
12. 变体预告：Staged Speculative Decoding #
原始推测解码的草稿阶段由一个草稿模型承担全部 $K$ 步。Chen et al.（arXiv:2302.01318）提出分阶段（staged）变体：用 $M$ 个越来越强的草稿模型 $q_1, \dots, q_M$，各承担一部分步骤——先让最弱的模型猜头几步，再让更强的模型在已接受的基础上继续猜。这样：
- 每步草稿的"质量-速度"组合更优（早期位置便宜模型就够，后期位置才需要强模型）；
- 单点失误不会浪费后面所有草稿（被拒绝的位置之前仍有产出）；
- 论文在 T5-XXL 等目标上报告约 2x 量级的墙钟加速，与单草稿版本相当或更好。
另外，SpecInfer（arXiv:2305.09781）提出用多个草稿模型 + 树结构草稿来提升每轮接受率——树结构正是 03 章 Medusa 树注意力的直接前身。这两条线都说明：原始推测解码只是起点，改进的主轴永远是"提高 α、压低草稿开销"。
13. 本章小结 #
- 算法：草稿 $q$ 猜 $K$ 步 → 目标 $p$ 一次并行验证 $K+1$ 个位置 → 逐位拒绝采样 → 每轮产出 $1 \sim K+1$ 个 token。
- 无损性定理：单位置边际 $= p$（引理 2）⟹ 全序列分布 $= p$ 的自回归采样（归纳定理）。与 $\alpha$、$K$、$q$ 都无关。
- 最优 $K^*$：解驻点方程 $\alpha^{K^*+1}[1+(c+K^*)L] = 1$；$K^*$ 随 $\alpha$、$c$ 单调增，峰值附近平坦。
- 草稿规模：倒 U 形权衡——太小 α 低、太大 c 小；要在真实负载上同时测 α 和 c。
- 贪心退化：接受规则 = argmax 相等，仍严格无损；混用策略才会破坏无损。
一句话记忆：“小模型先猜，大模型一审；猜错的地方按大模型的意见补一个——猜多快、审多快、押注几步（K），三者定收益。”
14. 习题与解答 #
题 1（推导）：残差分布的归一性 #
证明 $\sum_x \max(0, p(x)-q(x)) = 1 - \alpha$，并说明为什么修正分布只在 $p > q$ 的位置有质量。
题 1 解答
$\max(0,p-q) = \frac{p-q+|p-q|}{2}$，求和得 $\frac{1}{2}\sum(p-q) + \frac{1}{2}\sum|p-q| = \mathrm{TV}(p,q) = 1-\alpha$。残差为 0 当且仅当 $p \le q$，所以 $p_r$ 只在目标比草稿更相信的位置采样——这正是"把草稿欠的概率补回来"。
题 2（计算）：完整一轮 #
词表 $\{\text{A},\text{B},\text{C}\}$，$q = (0.6, 0.3, 0.1)$，$p = (0.4, 0.5, 0.1)$，$K=3$。
① 求 $\alpha$、$\beta$、$p_r$；② 求 $E[N]$；③ 设 $c = 8$，求加速比；④ 若草稿采样出 A, B, A，第一个随机数 $r_1 = 0.3$，请追踪接受过程。
题 2 解答
① $\alpha = \min(0.6,0.4)+\min(0.3,0.5)+\min(0.1,0.1) = 0.4+0.3+0.1 = 0.8$；$\beta=0.2$；残差只在 B：$0.5-0.3=0.2$，故 $p_r=(0,1,0)$（拒绝后必采 B）。② $E[N] = (1-0.8^4)/0.2 = 2.952$。③ speedup $= 2.952\times8/11 = 2.15\text{x}$。④ 位置 1：$p(\text{A})/q(\text{A}) = 0.4/0.6 = 0.667$，$r_1=0.3<0.667$ → 接受 A；位置 2：$p(\text{B})/q(\text{B})=0.5/0.3>1$ → 无条件接受 B；位置 3：$p(\text{A})/q(\text{A})=0.667$，若 $r_3>0.667$ 则拒绝并输出 B（$p_r$ 单点）。该轮产出 A, B, B，$N=3$。
题 3（推导）：最优 K 的驻点方程 #
从 $f(K) = \frac{c}{c+K}\cdot\frac{1-\alpha^{K+1}}{1-\alpha}$ 出发，推导 $K^*$ 满足的方程，并说明为什么 $K^*$ 随 $c$ 增大而增大。
题 3 解答
$\frac{d}{dK}\ln f = -\frac{\alpha^{K+1}\ln\alpha}{1-\alpha^{K+1}} - \frac{1}{c+K} = 0$。令 $L=\ln(1/\alpha)$，得 $\alpha^{K+1}[1+(c+K)L]=1$。$c$ 增大时等式左侧变小（$c$ 只在括号内以加法出现），需增大 $K$ 使 $\alpha^{K+1}$ 变小来恢复等式，故 $K^*$ 单调增。同理，$\alpha$ 增大时 $L$ 变小、$\alpha^{K+1}$ 变大，也需要更大的 $K$ 平衡。
题 4（推导）：贪心接受规则 #
证明当 $p$、$q$ 都是单点分布（贪心）时，接受概率 $=\mathbf{1}[\tilde{x}_i = \arg\max_x p(x\mid h)]$，且输出序列等于目标模型的贪心输出。
题 4 解答
单点分布下 $p(x)/q(x) \in \{0, 1\}$：$\tilde{x}_i$ 同时是两边 argmax 时为 1，否则为 0。故 $\min(1, p/q)$ 是指示函数。拒绝时 $p_r$ 的支撑集只有目标 argmax，输出即目标贪心 token。逐位执行等价于"比较 argmax 链"，所以整条序列就是 $p$ 的贪心输出。
题 5（思考）：为什么"草稿差"仍然无损 #
既然无损性与 $q$ 无关，是不是随便拿个随机模型当草稿就行？实际部署中为什么不行？
题 5 解答要点
正确性上确实可以，但加速比会 $\to 1$ 甚至 < 1：$\alpha$ 低时 $E[N] \to 1$，还要额外付 $K\cdot T_q$ 的草稿开销。而且工程实现若引入"无条件接受第一个"等近似，草稿太差时偏差会被放大（近似与真实分布的混合）。所以无损是数学保证，收益是工程问题——两者要分开谈。
题 6（编程）：经验验证无损性 #
用一个小词表（如 $V=10$）随机生成 $p$、$q$，实现：① 采样版推测解码（K=3）；② 贪心版推测解码；③ 各跑 5 万轮，比较输出 token 的经验分布与 $p$（或贪心链），并统计每轮产出均值与 $E[N]$ 的偏差。
题 6 解答要点
① 接受用 $r_i \le \min(1,p/q)$，拒绝用残差分布采样。② 逐位比较 argmax。③ 采样版经验分布应与 $p$ 的 KL 距离趋近 0（无偏）；每轮均值趋近 $(1-\alpha^4)/(1-\alpha)$。贪心版应逐 token 与 $p$ 的贪心输出一致。若把"无条件接受第一个"加进去，经验分布会出现可检测的偏差——这就是 11.1 表第一行的实验证据。
15. 延伸阅读 #
- Fast Inference from Transformers via Speculative Decoding（arXiv:2211.17192）：本章算法、无损性定理（Thm 1）、最优草稿规模分析、T5-XXL 实验（2–3x）的出处。
- Accelerating LLM Inference with Staged Speculative Decoding（arXiv:2302.01318）：分阶段草稿变体，与本章算法对照阅读。
- Blockwise Parallel Decoding for Deep Autoregressive Models（Stern et al., arXiv:1808.02647）：推测解码的思想前身（并行预测多个 token）。
- SpecInfer（arXiv:2305.09781）：多草稿 + 树验证，03 章树注意力的前身。
- 上一篇： 01 问题形式化与接受率数学；下一篇：03 Medusa：多头解码——不引入独立草稿模型，让目标模型自己长出"草稿头"。