# 投机采样为什么是无损的？接受率与期望 token 公式推导

> 自回归解码慢的结构性原因是因果依赖浪费了 GPU 并行能力，「草稿 + 并行验证」正好把它补回来。本文从定义推导期望接受 token 数 E[N]=(1-α^(K+1))/(1-α) 与墙钟加速比公式，并解释拒绝采样后输出分布为何依然无损。

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-01-%E9%97%AE%E9%A2%98%E5%BD%A2%E5%BC%8F%E5%8C%96%E4%B8%8E%E6%8E%A5%E5%8F%97%E7%8E%87%E6%95%B0%E5%AD%A6/


> 系列导航：上篇系列 [LLM 量化精读笔记总览](/notes/llm量化精读笔记-00-总览与学习地图/)｜[推测解码精读笔记总览](/notes/llm推测解码精读笔记-00-总览与学习地图/)（共 6 篇）｜下一篇：[投机采样原理是什么](/notes/llm推测解码精读笔记-02-原始推测解码-草稿模型与拒绝采样/)

> 对应：Leviathan et al., *Fast Inference from Transformers via Speculative Decoding*（2023）；Inference Engineering Ch5 的 Speculative Decoding 部分。
> 学完本章你应该能：① 说清自回归解码慢的**结构性原因**（因果依赖使 GPU 的并行能力被浪费）；② 用"草稿 + 并行验证"一句话解释推测解码为什么能加速；③ 从定义推导期望 token 数公式 $E[N] = (1-\alpha^{K+1})/(1-\alpha)$；④ 推导墙钟加速比公式并手算数值例；⑤ 解释"为什么推测解码是无损的"（拒绝采样的边际分布等于目标分布）。

---

## 目录（本章）

1. 本章目标
2. 自回归解码为什么慢：形式化
3. 核心思想：草稿 + 并行验证
4. 接受率数学：α 与 E[N]
5. 墙钟收益模型：速度比 c 与最优 K
6. 为什么无损：拒绝采样的边际分布定理
7. 设计空间：α、K、c 三者如何决定收益
8. 本章小结
9. 习题与解答
10. 延伸阅读

---

## 1. 本章目标

量化系列回答"每一步怎么更快"，本系列回答"**怎么用更少的步数生成同样的文本**"。本章建立整个系列的数学地基——接受率 α 和期望 token 数 E[N]。

---

## 2. 自回归解码为什么慢：形式化

### 2.1 自回归的结构性约束

LLM 按自回归方式生成：

$$
x_{t+1} \sim p(\cdot \mid x_1, \dots, x_t)
$$

第 $t+1$ 个 token 依赖前 $t$ 个 token——**严格串行**：

```
第 1 步：只算 1 个位置
第 2 步：只算 1 个位置（但前向里其实处理了 2 个位置的 KV）
……
每步只"新增"1 个 token 的预测
```

### 2.2 浪费在哪里

每次前向，GPU 会并行计算**所有 token 位置**的表示（矩阵乘天生并行），但自回归只取**最后一个位置**的输出：

```
GPU 实际算的：seq_len 个位置的全部激活
解码真正用的：最后 1 个位置的 logits
→ 计算利用率 ≈ 1/seq_len（序列越长越浪费）
```

更准确地说，decode 阶段是**访存密集**的（量化系列 03 章的带宽模型）：瓶颈在把权重从 HBM 搬到寄存器，而不是在"算"。但无论算还是搬，**每步只为 1 个新 token 付费**——这是自回归的根本开销。

### 2.3 关键矛盾

```
自回归的约束：token 之间存在因果依赖，必须串行决策
GPU 的能力：一次前向可以并行处理 K 个位置的输入
```

推测解码的思路：**用便宜的草稿模型先"猜" K 个 token，再用昂贵的目标模型一次并行验证**。如果草稿猜得准，一次目标前向就能产出多个 token。

---

## 3. 核心思想：草稿 + 并行验证

### 3.1 两个模型

```
目标模型 p：大、准、慢（真正负责质量，输出分布必须由它决定）
草稿模型 q：小、快、不太准（猜，猜错了会被纠正）
```

### 3.2 一轮操作的流程（预览）

```
1. 草稿：用 q 自回归生成 K 个候选 token（K 步，每步很快）
2. 验证：把 K 个候选一次性喂给 p，一次前向得到 K+1 个位置的 logits
3. 接受：从左到右逐个检查候选是否"与 p 一致"（拒绝采样规则）
4. 纠正：第一个不一致的位置，从修正分布重采样一个 token
5. 产出：这一轮得到 N 个新 token（1 ≤ N ≤ K+1）
```

> 关键：验证只花**一次目标前向**（代价约等于正常解码一步），却可能换来最多 K+1 个 token。这就是加速的来源。

### 3.3 先记三个量

```
K：每轮草稿长度（典型 4~8）
α：每个草稿 token 被接受的概率
c：目标模型每 token 耗时 / 草稿模型每 token 耗时（典型 5~20）
```

---

## 4. 接受率数学：α 与 E[N]

### 4.1 定义接受概率 α

设目标分布 p、草稿分布 q（同一时刻、同一前缀下）。草稿 token 按 q 采样，验证时以概率

$$
\min\left(1, \frac{p(x)}{q(x)}\right)
$$

接受它（拒绝采样规则，第 6 节证明它保持分布）。于是**无条件接受概率**：

$$
\alpha = \sum_x q(x) \cdot \min\left(1, \frac{p(x)}{q(x)}\right) = \sum_x \min(p(x), q(x))
$$

### 4.2 α 与 TV 距离的关系

利用 $\min(a,b) = \frac{a+b-|a-b|}{2}$：

$$
\alpha = \frac{1}{2}\sum_x \left(p(x)+q(x)-|p(x)-q(x)|\right) = 1 - \frac{1}{2}\sum_x |p(x)-q(x)|
$$

即

$$
\alpha = 1 - \mathrm{TV}(p, q)
$$

**α 越接近 1，草稿与目标分布越一致**。β = 1 − α 就是每 token 被拒绝的概率。

### 4.3 期望 token 数 E[N] 的推导

设每轮草稿 K 个 token，token 间相互独立（近似；严格版本对历史取条件期望，结论形式相同）。令 α 为单 token 接受概率。

每轮产出 N 个 token。N 的分布由"前 $i-1$ 个草稿 token 都被接受、第 $i$ 个被拒绝（随后补 1 个修正 token）"或"全部 $K$ 个都被接受（随后从 $p$ 直接采 1 个 bonus token）"决定：

$$
P(N = i) = \alpha^{i-1}(1-\alpha), \quad i = 1, \dots, K; \qquad
P(N = K+1) = \alpha^{K}
$$

期望：

$$
E[N] = \sum_{i=1}^{K} i \cdot \alpha^{i-1}(1-\alpha) + (K+1)\alpha^K
$$

用等比数列求和 $\sum_{i=1}^{K} i\alpha^{i-1} = \frac{1-(K+1)\alpha^K + K\alpha^{K+1}}{(1-\alpha)^2}$，整理得：

$$
E[N] = \frac{1-\alpha^{K+1}}{1-\alpha}
$$

**这是整个系列的"第一公式"。**

### 4.4 数值算例

不同 α、K 下的期望每轮 token 数：

| α | K=4 时 E[N] | K=8 时 E[N] |
|---|---|---|
| 0.5 | 1.94 | 1.996 |
| 0.6 | 2.31 | 2.47 |
| 0.7 | 2.77 | 3.20 |
| 0.8 | 3.36 | 4.33 |
| 0.9 | 4.10 | 6.13 |

验证一例（α=0.8, K=4）：

$$
E[N] = \frac{1-0.8^{5}}{1-0.8} = \frac{1-0.32768}{0.2} = 3.36
$$

直觉：α=0.8 时每轮平均产出 3.36 个 token，而目标只"真正解码"了 1 次。

---

## 5. 墙钟收益模型：速度比 c 与最优 K

### 5.1 一轮的墙钟时间

```
一轮时间 ≈ T_p + K·T_q
         = 一次目标验证 + K 步草稿
```

（目标验证一次前向处理 K+1 个位置，代价近似一次正常解码 T_p；草稿 K 步串行，每步 T_q。）

### 5.2 加速比公式

目标单独解码：每 token 耗时 $T_p$，每秒 $1/T_p$ 个 token。
推测解码：每轮 $E[N]$ 个 token，耗时 $T_p + K T_q$。

$$
\text{speedup} = \frac{E[N]\cdot T_p}{T_p + K\cdot T_q}
              = \frac{E[N]\cdot c}{c + K}, \quad c = \frac{T_p}{T_q}
$$

### 5.3 数值算例

设 c = 10（目标比草稿慢 10 倍），α = 0.8，K = 4：

$$
E[N] = 3.36, \quad \text{speedup} = \frac{3.36 \times 10}{10+4} = 2.40
$$

即墙钟约快 2.4 倍。再看不同组合：

| α | c | K | E[N] | speedup |
|---|---|---|---|---|
| 0.8 | 10 | 4 | 3.36 | 2.40x |
| 0.8 | 10 | 8 | 4.33 | 2.40x |
| 0.9 | 10 | 8 | 6.13 | 3.40x |
| 0.6 | 10 | 4 | 2.31 | 1.65x |
| 0.8 | 5 | 4 | 3.36 | 1.87x |

### 5.4 收益的两个边界

**上界**：α → 1 时 $E[N] \to K+1$，加速比 $\to \frac{(K+1)c}{c+K} \to c$。**推测解码最多快 c 倍**——草稿与目标的速度比是天花板，这解释了为什么要选足够小/快的草稿。

**下界**：α 太低时加速比 < 1（推测反而拖慢）。需要

$$
E[N] > 1 + \frac{K}{c}
$$

### 5.5 最优 K

给定 α、c，加速比是 K 的函数：

$$
f(K) = \frac{c}{c+K}\cdot\frac{1-\alpha^{K+1}}{1-\alpha}
$$

求整数 K 最大化 f(K)。经验规律：

```
α 高（0.8+）→ K 取大（8 甚至 16）收益仍增长
α 中（0.6~0.7）→ K 取 4~8 附近有峰值
c 小（草稿不够快）→ K 应该更小
```

---

## 6. 为什么无损：拒绝采样的边际分布定理

### 6.1 问题

草稿分布 q 和目标分布 p 不一致。**为什么最后产出的 token 分布仍然严格等于 p？** 这使推测解码属于"无损"优化。

### 6.2 拒绝采样规则

从 $q$ 采样得到 $x$，然后以概率 $\min(1, p(x)/q(x))$ 接受 $x$（直接输出）；否则从修正分布 $p_r$ 重采样：

$$
p_r(x) = \frac{\max(0, p(x) - q(x))}{\beta}, \qquad \beta = 1 - \alpha
$$

### 6.3 边际分布验证

输出 x 的概率 = 直接接受 x 的概率 + 被拒后重采样到 x 的概率：

$$
P_{\text{emit}}(x) = q(x)\min\left(1,\frac{p(x)}{q(x)}\right) + \beta \cdot p_r(x)
$$

分两种情形：

$$
P_{\text{emit}}(x) = \begin{cases}
q(x) + (p(x) - q(x)) = p(x), & p(x) \ge q(x) \\
p(x) + 0 = p(x), & p(x) < q(x)
\end{cases}
$$

统一写法：

$$
P_{\text{emit}}(x) = \min(p(x), q(x)) + \max(0, p(x)-q(x)) = p(x)
$$

**结论：无论草稿多不准，输出分布都精确等于目标分布。** 这是"无损"的数学保证。

### 6.4 一个直觉

拒绝采样把"q 猜错的那部分概率"按目标分布 p 重新分配，而不是丢弃：猜对的部分直接保留（min(p,q)），猜错的部分用 p−q 的残差补回来（max(0,p−q)），两者拼起来正好是 p。

---

## 7. 设计空间：α、K、c 三者如何决定收益

```
收益 = E[N](α, K) × c/(c+K)
     = 接受率    × 草稿开销

提高 α：草稿与目标越像越好（架构、训练数据、草稿规模）——02~05 章所有方法的主战场
提高 c：草稿越小越快（但太小 α 会掉）——权衡
调 K：在"多猜几次"与"多付草稿费"之间找峰值
```

---

## 8. 本章小结

1. **自回归慢的结构性原因**：每步只产出 1 个 token，GPU 的并行能力被因果依赖锁死。
2. **推测解码 = 草稿 + 并行验证**：草稿猜 K 个，目标一次验证，产出 E[N] 个。
3. **第一公式**：$E[N] = \dfrac{1-\alpha^{K+1}}{1-\alpha}$，其中 $\alpha = \sum_x \min(p(x), q(x)) = 1 - \mathrm{TV}(p,q)$。
4. **墙钟收益**：$\text{speedup} = \dfrac{E[N]\cdot c}{c+K}$；上限 c，α 太低会倒挂。
5. **无损性**：拒绝采样让边际分布严格等于 p。

---

## 9. 习题与解答

### 题 1（推导）：期望 token 数

从 P(N=i) 出发，完整推导 $E[N] = (1-\alpha^{K+1})/(1-\alpha)$。

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

$E[N] = \sum_{i=1}^{K} i\alpha^{i-1}(1-\alpha) + (K+1)\alpha^K$。利用 $\sum_{i=1}^{K} i\alpha^{i-1} = \frac{1-(K+1)\alpha^K+K\alpha^{K+1}}{(1-\alpha)^2}$，代入并通分：分子 = $1-(K+1)\alpha^K+K\alpha^{K+1}+(K+1)\alpha^K-(K+1)\alpha^{K+1} = 1-\alpha^{K+1}$。得 $E[N] = (1-\alpha^{K+1})/(1-\alpha)$。
</details>

### 题 2（计算）：加速比

c = 8，α = 0.7。比较 K = 4 与 K = 8 的加速比，并求使加速比 > 1 所需的最小 α（K=4, c=8）。

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

α=0.7：E[N](K=4) = (1−0.7⁵)/0.3 = 2.77；speedup = 2.77×8/12 = 1.85x。E[N](K=8) = (1−0.7⁹)/0.3 = 3.20；speedup = 3.20×8/16 = 1.60x——K=4 反而更好（草稿费高）。加速比 > 1 需 E[N] > 1+K/c = 1.5；解 (1−α⁵)/(1−α) > 1.5，试 α=0.34：E[N]=1.51 ✓；α=0.33：E[N]=1.49 ✗（边界约 0.34）。
</details>

### 题 3（推导）：TV 恒等式

证明 $\alpha = 1 - \frac{1}{2}\sum_x |p(x)-q(x)|$。

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

$\min(a,b) = \frac{a+b-|a-b|}{2}$，代入 $\alpha = \sum_x \min(p,q)$：$\alpha = \frac{1}{2}\sum p + \frac{1}{2}\sum q - \frac{1}{2}\sum|p-q| = 1 - \mathrm{TV}(p,q)$。
</details>

### 题 4（推导）：无损性

写出拒绝采样输出分布，证明 $P_{\text{emit}}(x) = p(x)$ 对任意 q 成立。

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

$P_{\text{emit}}(x) = q(x)\min(1, p(x)/q(x)) + \beta\cdot\frac{\max(0,p(x)-q(x))}{\beta} = \min(p,q) + \max(0,p-q) = p(x)$。
</details>

### 题 5（思考）：为什么说推测解码是"无损"

与量化相比，"无损"具体指什么？如果用户看到两次生成结果不同，怎么解释？

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

无损指**输出分布**严格等于目标模型的采样分布（对任意解码策略：贪心/采样都保持）。两次生成不同是因为采样本身有随机性，与是否用推测无关。注意：如果实现里"无条件接受第一个草稿 token"（加速常用技巧）或草稿/目标温度不一致，会破坏严格无损——工程上要区分"理论无损"与"实现近似"。
</details>

### 题 6（编程）：模拟接受过程

给定两个词表分布 p、q（如 100 维），实现：① 计算 α；② 模拟 10000 轮草稿-验证（K=4），统计每轮产出 token 数的均值，与公式对比。

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

① α = Σ min(p,q)。② 每轮：从 q 采样 K 个 token，逐个以 min(1,p(x)/q(x)) 接受；第一个拒绝处从残差分布 max(0,p−q)/β 重采样；全接受则再从 p 采 1 个 bonus。统计均值应接近 (1−α⁵)/(1−α)。可再验证输出 token 的经验分布 ≈ p（无损性）。
</details>

---

## 10. 延伸阅读

1. [Fast Inference from Transformers via Speculative Decoding（arXiv:2211.17192）](https://arxiv.org/abs/2211.17192)：本章公式出处（接受率、E[N]、最优草稿规模、墙钟实验）
2. [Accelerating LLM Inference with Staged Speculative Decoding（arXiv:2302.01318）](https://arxiv.org/abs/2302.01318)：同期独立工作，可对照阅读
3. [Inference Engineering Ch5](https://inferenceengineering.tech/chapters/techniques/)：Speculative Decoding 教材节
4. 下一篇：**[02 原始推测解码：草稿模型与拒绝采样]**——把本章公式落成完整算法，推导无损性定理并手算完整例子。

