# 投机采样原理是什么？草稿模型与拒绝采样怎么配合

> 完整写出投机采样算法：小模型草稿 K 个 token，大模型一次前向并行验证，再用拒绝采样做修正。本文证明无损性定理（输出分布严格等于目标分布，且与草稿质量无关），推导最优草稿长度 K*，并列出工程实现里最容易破坏无损性的几个坑。

Canonical: https://doraemeng.dev/notes/llm%E6%8E%A8%E6%B5%8B%E8%A7%A3%E7%A0%81%E7%B2%BE%E8%AF%BB%E7%AC%94%E8%AE%B0-02-%E5%8E%9F%E5%A7%8B%E6%8E%A8%E6%B5%8B%E8%A7%A3%E7%A0%81-%E8%8D%89%E7%A8%BF%E6%A8%A1%E5%9E%8B%E4%B8%8E%E6%8B%92%E7%BB%9D%E9%87%87%E6%A0%B7/


> 系列导航：[推测解码精读笔记总览](/notes/llm推测解码精读笔记-00-总览与学习地图/)（共 6 篇）｜上一篇：[投机采样为什么是无损的](/notes/llm推测解码精读笔记-01-问题形式化与接受率数学/)｜下一篇：[Medusa 是什么](/notes/llm推测解码精读笔记-03-medusa-多头解码/)

> 对应：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 相等"；⑥ 列出工程实现里最容易破坏无损性的几个坑。

---

## 目录（本章）

1. 本章目标
2. 从 01 到 02：还差什么
3. 设置与记号
4. 完整算法：Speculative Sampling
5. 无损性定理：完整证明
6. 每轮成本与加速比回顾
7. 最优草稿长度 K\*
8. 草稿模型怎么选：α 与 c 的权衡
9. 数值算例：完整一轮的逐步追踪
10. 贪心解码的特殊情形
11. 实现细节与常见坑
12. 变体预告：Staged Speculative Decoding
13. 本章小结
14. 习题与解答
15. 延伸阅读

---

## 2. 从 01 到 02：还差什么

01 章给出了接受概率、期望产出与加速比三个公式，但还没落到可执行的算法。还差三件事：

1. **算法本身**：验证阶段到底怎么"从左到右逐个检查"？拒绝之后用什么分布补一个 token？
2. **无损性的完整证明**：01 章验证了"单个位置的边际分布等于 $p$"，但整个序列的联合分布呢？需要归纳法。
3. **参数怎么定**：$K$ 取多少最好？草稿模型选多大？这就是本章的最优 $K^*$ 与草稿规模权衡。

---

## 3. 设置与记号

沿用 01 章并补充：

| 符号 | 含义 |
|---|---|
| $\mathcal{V}$ | 词表，$|\mathcal{V}| = V$ |
| $x_{<t} = (x_1, \dots, x_{t-1})$ | 已生成前缀 |
| $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_{<t}$，由引理 2，该位置输出 token 的条件分布是 $p(\cdot \mid x_{<t})$，与直接自回归采样一致。
- **归纳步**：假设前 $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 三个推论

1. **正确性与草稿质量无关**：$q$ 再差（甚至均匀分布），输出分布依然精确等于 $p$，只是 $E[N] \to 1$、没有加速。
2. **正确性与 $K$ 无关**：$K$ 只影响速度和效率，不影响正确性。
3. **对任意解码策略成立**：贪心、温度采样、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 |

三个可验证的规律：

1. **$K^*$ 随 $\alpha$ 增大而增大**：草稿越准，多猜几步越划算。
2. **$K^*$ 随 $c$ 增大而增大**：草稿相对越快，多猜几步越划算。
3. **峰值附近曲线平坦（α 高时）**：α ≥ 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 到同一长度后一次前向，最大化验证吞吐。
- **模型自带草稿的动机**：Medusa/EAGLE 在目标模型内部生成草稿，天然共享词表与表示（03/04 章）。
- **退化情形**：$\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. 本章小结

1. **算法**：草稿 $q$ 猜 $K$ 步 → 目标 $p$ 一次并行验证 $K+1$ 个位置 → 逐位拒绝采样 → 每轮产出 $1 \sim K+1$ 个 token。
2. **无损性定理**：单位置边际 $= p$（引理 2）⟹ 全序列分布 $= p$ 的自回归采样（归纳定理）。与 $\alpha$、$K$、$q$ 都无关。
3. **最优 $K^*$**：解驻点方程 $\alpha^{K^*+1}[1+(c+K^*)L] = 1$；$K^*$ 随 $\alpha$、$c$ 单调增，峰值附近平坦。
4. **草稿规模**：倒 U 形权衡——太小 α 低、太大 c 小；要在真实负载上同时测 α 和 c。
5. **贪心退化**：接受规则 = argmax 相等，仍严格无损；混用策略才会破坏无损。

---

## 14. 习题与解答

### 题 1（推导）：残差分布的归一性

证明 $\sum_x \max(0, p(x)-q(x)) = 1 - \alpha$，并说明为什么修正分布只在 $p > q$ 的位置有质量。

<details>
<summary>题 1 解答</summary>

$\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$ 只在目标比草稿更相信的位置采样——这正是"把草稿欠的概率补回来"。
</details>

### 题 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$，请追踪接受过程。

<details>
<summary>题 2 解答</summary>

① $\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$。
</details>

### 题 3（推导）：最优 K 的驻点方程

从 $f(K) = \frac{c}{c+K}\cdot\frac{1-\alpha^{K+1}}{1-\alpha}$ 出发，推导 $K^*$ 满足的方程，并说明为什么 $K^*$ 随 $c$ 增大而增大。

<details>
<summary>题 3 解答</summary>

$\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$ 平衡。
</details>

### 题 4（推导）：贪心接受规则

证明当 $p$、$q$ 都是单点分布（贪心）时，接受概率 $=\mathbf{1}[\tilde{x}_i = \arg\max_x p(x\mid h)]$，且输出序列等于目标模型的贪心输出。

<details>
<summary>题 4 解答</summary>

单点分布下 $p(x)/q(x) \in \{0, 1\}$：$\tilde{x}_i$ 同时是两边 argmax 时为 1，否则为 0。故 $\min(1, p/q)$ 是指示函数。拒绝时 $p_r$ 的支撑集只有目标 argmax，输出即目标贪心 token。逐位执行等价于"比较 argmax 链"，所以整条序列就是 $p$ 的贪心输出。
</details>

### 题 5（思考）：为什么"草稿差"仍然无损

既然无损性与 $q$ 无关，是不是随便拿个随机模型当草稿就行？实际部署中为什么不行？

<details>
<summary>题 5 解答要点</summary>

正确性上确实可以，但加速比会 $\to 1$ 甚至 < 1：$\alpha$ 低时 $E[N] \to 1$，还要额外付 $K\cdot T_q$ 的草稿开销。而且工程实现若引入"无条件接受第一个"等近似，草稿太差时偏差会被放大（近似与真实分布的混合）。所以无损是数学保证，收益是工程问题——两者要分开谈。
</details>

### 题 6（编程）：经验验证无损性

用一个小词表（如 $V=10$）随机生成 $p$、$q$，实现：① 采样版推测解码（K=3）；② 贪心版推测解码；③ 各跑 5 万轮，比较输出 token 的经验分布与 $p$（或贪心链），并统计每轮产出均值与 $E[N]$ 的偏差。

<details>
<summary>题 6 解答要点</summary>

① 接受用 $r_i \le \min(1,p/q)$，拒绝用残差分布采样。② 逐位比较 argmax。③ 采样版经验分布应与 $p$ 的 KL 距离趋近 0（无偏）；每轮均值趋近 $(1-\alpha^4)/(1-\alpha)$。贪心版应逐 token 与 $p$ 的贪心输出一致。若把"无条件接受第一个"加进去，经验分布会出现可检测的偏差——这就是 11.1 表第一行的实验证据。
</details>

---

## 15. 延伸阅读

1. [Fast Inference from Transformers via Speculative Decoding（arXiv:2211.17192）](https://arxiv.org/abs/2211.17192)：本章算法、无损性定理（Thm 1）、最优草稿规模分析、T5-XXL 实验（2–3x）的出处。
2. [Accelerating LLM Inference with Staged Speculative Decoding（arXiv:2302.01318）](https://arxiv.org/abs/2302.01318)：分阶段草稿变体，与本章算法对照阅读。
3. [Blockwise Parallel Decoding for Deep Autoregressive Models（Stern et al., arXiv:1808.02647）](https://arxiv.org/abs/1808.02647)：推测解码的思想前身（并行预测多个 token）。
4. [SpecInfer（arXiv:2305.09781）](https://arxiv.org/abs/2305.09781)：多草稿 + 树验证，03 章树注意力的前身。
5. 上一篇：[01 问题形式化与接受率数学](/notes/llm推测解码精读笔记-01-问题形式化与接受率数学/)；下一篇：**03 Medusa：多头解码**——不引入独立草稿模型，让目标模型自己长出"草稿头"。

