# Medusa 是什么？多头解码为什么能加速 LLM 推理

> Medusa 在模型上挂多个解码头，一次预测多个后续位置，再用树注意力并行验证候选路径。本文写出 head 结构与树掩码规则，用覆盖率模型推导期望接受长度，说明典型验收与拒绝采样的区别，以及树大小为什么存在最优值。

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-03-medusa-%E5%A4%9A%E5%A4%B4%E8%A7%A3%E7%A0%81/


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

> 对应：Cai et al., *Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads*（arXiv:2401.10774，ICML 2024）；官方实现 FasterDecoding/Medusa。
> 前置：01 章的接受率数学、02 章的验证与拒绝采样。学完本章你应该能：① 说清 Medusa 相对"独立草稿模型"路线的三个优势；② 写出 Medusa head 的结构、候选树构建公式与树注意力掩码规则；③ 用"覆盖率"模型推导树的期望接受长度，并手算数值例；④ 解释典型验收（typical acceptance）与拒绝采样的区别，以及无损性代价在哪里；⑤ 对比 Medusa-1/Medusa-2 的训练配方与论文加速比数据；⑥ 解释为什么树大小存在最优值。

---

## 目录（本章）

1. 本章目标
2. 动机：独立草稿模型的三个痛点
3. 架构：Medusa Heads
4. 候选树与树注意力
5. 推理循环（伪代码）
6. 接受率数学：从链到树
7. 优化树：节点贡献与贪婪建树
8. 验收策略：拒绝采样 vs 典型验收
9. 训练配方：Medusa-1 与 Medusa-2
10. 数值算例：完整一轮
11. 树大小权衡：加速率与开销
12. 实验结果
13. 与 02 章对照
14. 实现细节与坑
15. 本章小结
16. 习题与解答
17. 延伸阅读

---

## 2. 动机：独立草稿模型的三个痛点

02 章的原始推测解码把草稿职责交给一个**独立小模型** $q$。理论上优雅，工程上难受：

```
痛点 1：草稿模型从哪来？
  要么现成（很难恰好有"又快又跟目标分布接近"的模型），
  要么自己预训练/微调一个（SpecInfer 报告约 275 A100 GPU 小时）。

痛点 2：分布式部署复杂度。
  两个模型、两套权重、两份 KV cache、两种调度；
  论文（Chen et al. 2023）明确提到多模型 serving 的复杂度。

痛点 3：草稿阶段是串行的 K 步自回归。
  每轮要先付 K·T_q 的草稿时间；草稿越慢，K 就越不敢取大。
```

Medusa 的做法：在主干上追加 $K$ 个轻量解码头，与主干共享表示，一次前向同时给出多个未来位置的候选；再用**树注意力**把多条候选路径一次性验证完。

三个痛点对应的解法：

| 痛点 | Medusa 的解法 |
|---|---|
| 草稿从哪来 | 训练 $K$ 个头（参数高效，主干可冻结） |
| 部署复杂度 | 仍是单模型、单权重、单 KV cache |
| 串行草稿成本 | 头与前向并行，草稿阶段几乎免费 |

---

## 3. 架构：Medusa Heads

### 3.1 定义

设主干模型在位置 $t$ 的最后一层隐藏状态为 $h_t \in \mathbb{R}^d$，词表大小 $V$。原始 LM head 预测位置 $t+1$（记为 head 0，输出分布 $p_t^{(0)}$）。额外添加 $K$ 个 Medusa head，第 $k$ 个头预测位置 $t+k+1$（$k = 1, \dots, K$），输出分布：

$$
p_t^{(k)} = \mathrm{softmax}\!\left(W_2^{(k)} \cdot \left(\mathrm{SiLU}(W_1^{(k)} h_t) + h_t\right)\right)
$$

其中 $W_1^{(k)} \in \mathbb{R}^{d \times d}$、$W_2^{(k)} \in \mathbb{R}^{d \times V}$。每个头是**一个残差 MLP + 输出投影**：残差块 $h_t + \mathrm{SiLU}(W_1^{(k)} h_t)$ 相当于一个"轻量特征变换"，再经过 $W_2^{(k)}$ 投影到词表。

### 3.2 初始化：让头一开始就"像主干"

$$
W_1^{(k)} \leftarrow 0, \qquad W_2^{(k)} \leftarrow W_{\text{LM head}}
$$

$W_1 = 0$ 使残差块退化为恒等映射，$W_2$ 复制原 LM head，于是训练前每个 Medusa head 的预测**恰好等于主干的预测**（$p_t^{(k)} = p_t^{(0)}$）。这有两个好处：训练起点稳定；即使只训少量数据，头也不会一开始就胡猜。

### 3.3 关键性质：头的预测是"平行"的

注意第 $k$ 个头**只看 $h_t$**，不看前几个候选 token。也就是说，$p_t^{(k)}$ 是在"不知道中间 token 是什么"的情况下对未来第 $k$ 个位置做的猜测。这与 02 章草稿模型的"逐 token 条件化自回归"完全不同——**这正是需要用树来验证的原因**：真正到位置 $t+k+1$ 时，正确条件依赖是中间的候选 token，树把各种组合都枚举出来，由主干在验证时重新做条件化。

---

## 4. 候选树与树注意力

### 4.1 树的构建

设第 $k$ 个头取 top-$s_k$ 候选（$s_k$ 是超参）。候选序列由各层候选的**笛卡尔积**构成：

```
层 0（位置 t+1）：head 0 贪心 token，直接接受（每轮保底 1 个 token）
层 1（位置 t+2）：head 1 的 top-s_1
层 2（位置 t+3）：head 2 的 top-s_2，与层 1 的每个候选组合
……
层 K（位置 t+K+1）：head K 的 top-s_K
```

这是一个"每层候选集共享"的规则树：第 $k$ 层每个节点都有同样的 $s_{k+1}$ 个孩子（因为 $p_t^{(k)}$ 只依赖 $h_t$）。整棵树新增的 token 数为：

$$
T(s_1, \dots, s_K) = \sum_{k=1}^{K} \prod_{i=1}^{k} s_i
$$

例：$s_1 = 2$、$s_2 = 3$ 时，$T = 2 + 2\times 3 = 8$：层 1 有 2 个节点，层 2 有 $2\times 3 = 6$ 个叶子。

### 4.2 树注意力：一次前向验证整棵树

普通因果注意力的掩码是"只看左侧"。树注意力把掩码改成**"只看自己的祖先"**：

```
树上节点 (k, j)（第 k 层的第 j 个候选）的注意力范围 =
    前缀 token ∪ 自己的祖先链（层 1 到层 k-1 各一个节点）∪ 自己
```

同一个层里不同分支的节点**互相不可见**（它们代表互斥的候选世界）。实现上：

- 给树节点分配拓扑顺序的位置索引，注意**同一层共享同一个 RoPE 位置**（它们都是前缀之后第 $k$ 个 token）；
- 预计算一个布尔掩码矩阵 $M[i][j] = 1 \iff j$ 是 $i$ 的祖先或 $i = j$；
- 把 $T$ 个候选节点拼进序列，一次前向得到所有节点的 logits——不需要展开 batch。

树注意力的意义：02 章"一次验证一条链"只检查 $K+1$ 个位置；树注意力一次检查 $T$ 个位置，**把"猜错一个就整条链作废"的风险摊薄到多个分支上**。

---

## 5. 推理循环（伪代码）

```
输入：带 K 个 Medusa head 的模型、前缀 x_<t、树配置 s_1..s_K、验收策略
输出：N 个新 token（N ≥ 1）

每轮：
1. 取当前最后位置隐藏状态 h_t（首轮来自 prefill；之后复用上一轮验证的 hidden state）
2. 候选生成（并行、几乎免费）：
     第 1 位置：head 0 贪心 token（无条件接受）
     第 k 层（k=1..K）：head k 的 top-s_k 候选
3. 树注意力验证（一次主干前向）：
     对树上每个节点算 p(· | 前缀 + 该节点祖先链)
4. 验收（沿树找最长可接受前缀）：
     层 0：直接接受
     层 k：若某候选满足验收条件（拒绝采样或典型验收）→ 接受，进入它的孩子；
           否则 → 停在层 k-1
5. 输出接受路径上的所有 token；该路径末端节点的 hidden state 成为下一轮的 h_t
```

一轮最多产出 $K+1$ 个 token（层 0 的 1 个 + $K$ 层候选），至少 1 个。第 2 步不需要独立的草稿模型前向：头是主干之上的小 MLP，且第 3 步验证前向的 hidden state 直接复用于下一轮。这是与 02 章最大的结构性差异。

---

## 6. 接受率数学：从链到树

### 6.1 覆盖率模型

02 章的单链每层只有 1 个候选，接受率是 **top-1 命中率** $\alpha$。Medusa 每层有 $s_k$ 个候选，接受条件放宽为"目标 token 落在候选集里"。定义第 $k$ 层的**覆盖率**：

$$
q_k = P\!\left(\arg\max_x p(x \mid \text{前缀} + \text{已接受路径}) \in \text{head } k \text{ 的 top-}s_k \text{ 候选集}\right)
$$

（路径平均意义上的概率；下文与论文一致，假设各层覆盖率独立。）

### 6.2 期望接受长度

记 $N$ 为每轮产出 token 数。$P(N \ge 1) = 1$（层 0 保底），$P(N \ge 1 + m) = \prod_{j=1}^{m} q_j$（前 $m$ 层都命中），于是：

$$
E[N] = \sum_{i \ge 1} P(N \ge i)
      = 1 + q_1 + q_1 q_2 + \cdots + \prod_{j=1}^{K} q_j
$$

**退化检查**：当所有 $s_k = 1$ 时，$q_k = \alpha$（top-1 接受率），上式退化为 $1 + \alpha + \cdots + \alpha^K = \dfrac{1-\alpha^{K+1}}{1-\alpha}$——与 02 章公式完全一致。树不改变公式结构，改变的是**每层的 $q_k$**。

### 6.3 树 vs 链：为什么树赢

覆盖率 $q_k$ 是"目标 token 在 top-$s_k$ 里"的概率，而 top-1 命中率只是 $s_k=1$ 的特例。对常见分布，覆盖率随 $s$ 的增长远快于线性：

| 方案 | 每层接受概率 | E[N]（K=2） |
|---|---|---:|
| 链式草稿（02 章） | top-1：$\alpha = 0.6$ | $1 + 0.6 + 0.36 = 1.96$ |
| Medusa 树 $s=(1,1)$ | $q = 0.6$ | $1.96$（退化，同上） |
| Medusa 树 $s=(3,2)$ | $q = (0.9, 0.8)$ | $1 + 0.9 + 0.72 = 2.62$ |

同一条"主干"，top-3 覆盖率 0.9 远高于 top-1 命中率 0.6——树把"单个候选猜对"变成"候选集覆盖对"，这就是树注意力的数学价值。

### 6.4 代价：节点数

覆盖率提高不是免费的：$s_k$ 越大，树节点 $T = \sum_k \prod_{i \le k} s_i$ 增长得越快（组合爆炸），验证前向处理的 token 越多。$E[N]$ 增长是**线性叠加**（每层至多加一项），而 $T$ 增长是**乘积式**——收益与开销赛跑，最优树一定在中间（第 11 节量化）。

---

## 7. 优化树：节点贡献与贪婪建树

论文（§2.3.3）给了一个可操作的建树准则。设 $a_k^{(i)}$ 为 head $k$ 的第 $i$ 高候选的**边际命中率**（即 top-$i$ 命中率减 top-$(i-1)$ 命中率，用校准集统计）。假设各层独立，节点 $[i_1, \dots, i_k]$（依次取各层的第 $i_j$ 高候选）对期望接受长度的贡献为：

$$
\text{contrib}\!\left([i_1, \dots, i_k]\right) = \prod_{j=1}^{k} a_j^{(i_j)}
$$

整个树的期望接受长度就是所有节点贡献之和：

$$
E[\text{accept length}] = \sum_{[i_1, \dots, i_k] \in \text{tree}} \prod_{j=1}^{k} a_j^{(i_j)}
$$

因此建树变成"**往树上加节点**"的贪心过程：每次从"与当前树相邻的节点"里选贡献 $\prod_j a_j^{(i_j)}$ 最大的一个，加到节点预算用完为止。这样得到的**稀疏树**在 64 个节点时加速率优于 256 节点的稠密树（论文 Fig. 4）——因为稠密树的节点大多是低边际命中的"陪跑"候选，白付验证开销。

---

## 8. 验收策略：拒绝采样 vs 典型验收

Medusa 提供两种验收方式。

### 8.1 拒绝采样（严格无损）

与 02 章相同的规则：候选 $x$ 以概率 $\min(1, p(x)/q(x))$ 接受（$q$ 是 head 分布），拒绝时从残差分布重采样。这是**严格无损**的：输出分布等于主干模型的分布。代价：温度升高时，两个分布都变平，拒绝率上升，加速率下降（02 章末尾提到的问题）。

### 8.2 典型验收（Typical Acceptance，默认）

论文观察到：实际部署里温度只是调"创造力"的旋钮，不需要让草稿分布严格等于目标分布。于是他们改用**合理性阈值**：候选 $x$ 在位置 $n+k$ 被接受当且仅当

$$
p_{\text{original}}\!\left(x \mid x_1, \dots, x_{n+k-1}\right) > \min\!\left(\epsilon,\ \delta \exp\!\left(-H(p_{\text{original}}(\cdot \mid x_1, \dots, x_{n+k-1}))\right)\right)
$$

其中 $H(\cdot)$ 是目标分布的信息熵，$\epsilon$ 是硬阈值，$\delta$ 是熵相关阈值（官方默认 $\epsilon = 0.09$、$\delta = 0.3 \approx \sqrt{\epsilon}$）。直觉：

```
候选概率足够高 → 合理，接受
目标分布本身很平（熵高）→ 阈值放松，各种候选都算合理
```

另外，**第一个 token 用贪心并无条件接受**（保证每轮至少 1 个 token），然后沿树取"最长满足条件的可接受前缀"。

### 8.3 两种方式的取舍

| | 拒绝采样 | 典型验收 |
|---|---|---|
| 分布保证 | 严格等于 $p$ | 近似（质量靠阈值保护） |
| 温度升高时 | 接受率下降 | 接受率**上升**（熵高 → 阈值低） |
| 速度 | 较慢 | 更快（官方默认） |
| 使用场景 | 需要理论无损 | 生产默认、追求吞吐 |

> 一个常见的误读是"Medusa 一定无损"。准确说法：**Medusa-1 + 拒绝采样**是严格无损的（论文抽象里的 lossless 指这条路线）；默认的典型验收是**近似无损**的工程选择。写报告时务必区分。

---

## 9. 训练配方：Medusa-1 与 Medusa-2

### 9.1 Medusa-1：只训头，冻结主干

- 主干完全冻结，只训练 $K$ 个头的参数；
- 参数高效、显存友好，甚至可以对主干做 QLoRA 式量化来省显存（头照训）；
- 因为主干不变，**能力零损失**；头学会"顺着主干表示猜未来 token"；
- 论文数据：Vicuna-7B 2.18x、Vicuna-13B 2.33x。

### 9.2 Medusa-2：联合微调，两阶段

只训头时，头的预测受限于主干既有的表示。Medusa-2 把主干也放开微调，让头和主干协同，接受率更高：

```
阶段 1：冻结主干，只训头（即 Medusa-1）
阶段 2：联合微调主干 + 头，用特殊配方保住原模型能力
```

特殊配方的关键：主干用**知识蒸馏损失**而不是硬标签：

$$
\mathcal{L}_{\text{LM-distill}} = \mathrm{KL}\!\left(p_{\text{original}, t}^{(0)} \,\|\, p_{t}^{(0)}\right)
$$

让微调后的主干尽量贴着原模型的预测分布，而不是被新数据带偏。实现上主干用 LoRA 适配器训练，"教师"就是**关掉适配器的原模型**，几乎不增加显存。

### 9.3 数据：没有训练数据怎么办（Self-Distillation）

有些模型（如 RLHF 后的 Zephyr、私有数据训练的 Vicuna-33B）没有公开微调数据。论文的**自蒸馏**方案：

```
1. 拿一份同领域的种子数据（如 ShareGPT 的 prompt）
2. 让目标模型自己生成回答（多轮可自问自答）
3. 用生成结果训练 Medusa 头
```

论文报告自蒸馏模型（Zephyr-7B、Vicuna-33B）的加速比略低于有原始数据的模型——质量与速度的权衡。

---

## 10. 数值算例：完整一轮

场景：前缀 "The capital of France is"，$K = 2$ 个 Medusa head，树配置 $s = (3, 2)$。

**候选生成**（全部由当前 $h_t$ 并行算出）：

```
层 0（位置 t+1）：head 0 贪心 → " Paris"
层 1（位置 t+2）：head 1 的 top-3 → {",", " and", "!"}
层 2（位置 t+3）：head 2 的 top-2 → {" the", " a"}
```

树节点数：

$$
T = s_1 + s_1 s_2 = 3 + 3 \times 2 = 9
$$

**树注意力验证**（一次主干前向，9 个候选节点 + 前缀）：

```
位置 t+2 给定 "Paris"：p 的 argmax = "," → 在层 1 候选集里 ✓
位置 t+3 给定 "Paris,"：p 的 argmax = " the" → 在层 2 候选集里 ✓
```

**产出**：` Paris` + `,` + ` the`，本轮 $N = 3$。下一轮直接复用 " the" 的 hidden state 继续。

**与公式对照**：设 $q_1 = 0.9$、$q_2 = 0.8$（覆盖率），

$$
E[N] = 1 + q_1 + q_1 q_2 = 1 + 0.9 + 0.72 = 2.62
$$

本轮实际 3 个 token，高于期望，正常波动。若验证前向比普通 decode 贵 15%（9 个树节点 + 前缀的额外计算），净加速约 $2.62 / 1.15 \approx 2.3\text{x}$。

---

## 11. 树大小权衡：加速率与开销

论文定义 **加速率 = 加速比 / 开销**（overhead 指树前向比单 token 前向多出的计算）。两个相反的趋势：

```
加速率：随节点数增长，但呈对数式衰减（前几个候选收益最大）
开销：随节点数近线性增长（矩阵乘、注意力都变重）
净加速：先升后降，存在最优节点数
```

示意数值（趋势取自论文 Fig. 4，非实验精确值）：

| 树配置 | 节点数 T | 示意 E[N] | 示意开销 | 净加速 |
|---|---:|---:|---:|---:|
| 无树（单链 $s=1$） | 2 | 1.96 | 1.00 | 1.96x |
| $s=(3,2)$ | 9 | 2.62 | 1.10 | 2.38x |
| $s=(4,3,2)$ | 40 | 3.31 | 1.18 | 2.81x |
| 优化稀疏树 | 64 | 3.45 | 1.25 | 2.76x |
| 稠密大树 | 256+ | 3.6+ | 1.5+ | 2.4x 以下 |

论文在 Vicuna-7B（Medusa-2）上的实际结论：**64 节点的优化稀疏树效果最好**；超过约 64 个候选后速度开始下降（Fig. 4b / 附录 Fig. 21）。工程启示：树配置是超参，要在目标负载上扫描，别盲目加大 $s_k$。

---

## 12. 实验结果

论文与官方仓库的已核实数据（MT-Bench，GPT-4 评分验证质量不变）：

| 配置 | 加速比 |
|---|---:|
| Medusa-1 · Vicuna-7B | 2.18x |
| Medusa-1 · Vicuna-13B | 2.33x |
| Medusa-2 · Vicuna-7B | 2.83x |
| Medusa-2 · Vicuna-13B | 2.83x |
| Medusa-2 · Vicuna-7B（coding 类） | 3.29x |
| Medusa-2 · Vicuna-7B（extraction 类） | 3.62x |
| 论文摘要（多模型、多提示） | Medusa-1 > 2.2x；Medusa-2 2.3–2.8x |
| 官方仓库更新（更多 LLM） | 2.2–3.6x |

论文数据里有三点：

1. **代码/提取类任务收益最高**（3.29x/3.62x）——这些任务的局部结构规律性强，多头更容易猜中；
2. 自蒸馏模型（Zephyr-7B、Vicuna-33B）加速比略低，因为头的训练分布与真实分布有偏移；
3. 论文在同一批模型上对比了可获得的独立草稿模型方案，Medusa 的加速比更高。

---

## 13. 与 02 章对照

| 维度 | 02 原始推测解码 | 03 Medusa |
|---|---|---|
| 草稿来源 | 独立小模型（需预训练/获取） | 主干自带的 $K$ 个头（需训练头） |
| 词表/分布一致性 | 需强制对齐 | 天然一致（同一主干） |
| 草稿成本 | $K$ 步串行自回归（$K \cdot T_q$） | 头并行前向，几乎免费 |
| 候选结构 | 单条链 | 树（笛卡尔积，多候选并行） |
| 每层接受 | top-1 命中率 $\alpha$ | top-$s$ 覆盖率 $q \ge \alpha$ |
| 分布保证 | 严格无损 | 拒绝采样=严格无损；典型验收≈近似 |
| 部署 | 双模型、分布式复杂 | 单模型、无缝接入 |
| 训练 | 无（草稿现成） | Medusa-1（只训头）/ Medusa-2（联合微调） |
| 典型加速 | 2–3x（T5-XXL 实验） | 2.2–3.6x |

一句话概括演进：02 章解决"**怎么用便宜的猜测换并行**"，03 章把"便宜的猜测"从**外部模型**换成**模型自己的头**，并用树把"猜得准"升级为"覆盖得全"。

---

## 14. 实现细节与坑

1. **树掩码必须正确**：同一层不同分支不可互见。若误用全因果掩码，层 2 的候选会"偷看"到兄弟分支的信息，验证分布全错。测试办法：把树退化到 $s_k = 1$，输出必须与逐 token 贪心完全一致。
2. **RoPE 位置**：同一层的所有候选共享同一个位置索引（都是前缀后第 $k$ 个 token），不能用扁平化的拓扑序号。
3. **只收一条路径**：同一层可能有多个候选满足阈值；要按优先级（如 head 概率序）只选一条继续，避免"同时活在多个世界"。
4. **KV cache 复用**：验证前向为整棵树算 KV；接受路径的 KV 保留，其余丢弃。下一轮 head 直接复用路径末端 hidden state，省一次前向。
5. **严格无损 vs 默认行为**：官方默认典型验收 + 第一个 token 无条件接受，**不是**严格无损；要严格无损就切拒绝采样。
6. **batch 支持**：官方实现只支持 batch=1（本地单用户场景）；多请求批处理需要把多个请求的树拼进同一个注意力掩码（vLLM / TensorRT-LLM 的 Medusa 实现做了这件事）。
7. **与量化组合**：Medusa-1 训练时可量化主干（QLoRA 式）；推理时可与 W4A16 等量化方案叠加。量化降低每步成本，推测减少步数，联合收益要按 06 章的模型单独测。
8. **树配置要调**：$s_k$ 不是越大越好（第 11 节）；用校准集按第 7 节公式贪心建树。

---

## 15. 本章小结

1. **动机**：独立草稿模型有三痛（获取难、部署重、草稿串行贵）；Medusa 用主干自带的头替代。
2. **头**：$p_t^{(k)} = \mathrm{softmax}(W_2^{(k)}(\mathrm{SiLU}(W_1^{(k)} h_t) + h_t))$，$W_1$ 初始化 0、$W_2$ 复制 LM head。
3. **树**：候选 = 各层 top-$s_k$ 的笛卡尔积，节点数 $T = \sum_k \prod_{i \le k} s_i$；树注意力掩码只允许看祖先。
4. **数学**：$E[N] = 1 + q_1 + q_1 q_2 + \cdots + \prod_j q_j$，树的收益来自覆盖率 $q \ge$ top-1 命中率 $\alpha$；节点贡献公式指导贪婪建树。
5. **验收**：拒绝采样严格无损；典型验收（概率 > 阈值）更快但近似。
6. **训练**：Medusa-1 冻结主干只训头；Medusa-2 两阶段联合微调 + KL 蒸馏保住质量；无数据用自蒸馏。
7. **数据**：2.18–3.62x 不等；树最优约 64 节点，不是越大越好。

---

## 16. 习题与解答

### 题 1（推导）：树的期望接受长度

给定 $K=3$、覆盖率 $q = (0.9, 0.8, 0.7)$，写出 $E[N]$ 表达式并计算；再验证 $q_k = \alpha$ 时退化为 02 章公式。

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

$E[N] = 1 + q_1 + q_1 q_2 + q_1 q_2 q_3 = 1 + 0.9 + 0.72 + 0.504 = 3.124$。退化：$1 + \alpha + \alpha^2 + \alpha^3 = (1-\alpha^4)/(1-\alpha)$，即 02 章 $K=3$ 时的公式。
</details>

### 题 2（计算）：树节点数

分别计算 $s=(4,2)$、$s=(4,3,2)$、$s=(5,4,3)$ 的节点数 $T$；若验证开销与 $T$ 近似线性、覆盖率提升随 $s$ 递减，哪个树更可能最优？为什么？

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

$T = 4 + 8 = 12$；$T = 4 + 12 + 24 = 40$；$T = 5 + 20 + 60 = 85$。第三个树节点数比第二个翻倍，但覆盖率从 top-4→top-5 的增益很小（边际命中递减），开销却近线性增长——大概率不如 40 节点树。这解释了"最优树在中间"。
</details>

### 题 3（构造）：错误掩码的反例

构造一个最小例子说明：若层 2 的候选能注意到同层兄弟分支的 token，验证分布会出什么问题。

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

设层 1 有两个候选 A、B（互斥世界），层 2 的候选来自"给定 A"的分布。若层 2 在计算注意力时混入 B 的信息，它得到的条件分布既不是 $p(\cdot|A)$ 也不是 $p(\cdot|B)$，而是两者的混合——验收时无法与 head 的分布对齐，接受/拒绝决策失真。树注意力的意义就是保证每个节点只活在"自己的祖先链"里。
</details>

### 题 4（思考）：典型验收为什么随温度变快

解释：为什么温度升高时拒绝采样的接受率下降，而典型验收的接受率反而上升？这对"严格无损"意味着什么？

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

温度升高 → $p$ 与 $q$ 都变平 → 拒绝采样中 $\min(1, p/q)$ 的"匹配度"下降，且两份独立采样更容易不一致。典型验收只看 $p_{\text{original}}(x)$ 是否超过阈值：分布越平，熵越高，$\delta e^{-H}$ 阈值越低，更多候选被放行。代价是输出分布不再严格等于 $p$——质量靠阈值（$\epsilon$、$\delta$）保护，是工程近似而非数学保证。
</details>

### 题 5（设计）：贪心建树

用校准集统计出 head 1 的边际命中率 $a_1 = (0.6, 0.2, 0.1, 0.05)$、head 2 的 $a_2 = (0.5, 0.25, 0.15)$。预算 5 个节点，按贡献贪心建树，写出加入顺序与最终树的期望接受长度。

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

节点贡献 = 路径上边际命中率之积。候选及贡献：层1：$a_1^{(1)}=0.6$、$a_1^{(2)}=0.2$、$a_1^{(3)}=0.1$；层2（必须挂在已选层1节点下）：$0.6\times 0.5=0.3$、$0.6\times 0.25=0.15$、$0.6\times 0.15=0.09$。贪心顺序：层1第1（0.6）→ 层2第1（0.3）→ 层1第2（0.2）→ 层2第2（0.15）→ 层1第3（0.1）。期望接受长度 $= 1 + 0.6 + 0.3 + 0.2 + 0.15 + 0.1 = 2.35$（1 为保底首 token）。对比：若把第 5 个名额给层 2 第 3 个候选（挂在层 1 第 1 名下），$1 + 0.6 + 0.3 + 0.15 + 0.2 + 0.09 = 2.34$，略低于贪心。注意即使预算再加 1（第 6 个节点），边际贡献也只有 0.1 或 0.09——收益递减，这正是第 11 节"树不是越大越好"的来源。
</details>

### 题 6（编程）：toy 树验证

实现一个 2-head、$s=(2,2)$ 的 toy 验证器：给定 head 分布与目标分布（小词表），① greedy 模式跑 5 万轮统计每轮 token 数，与 $E[N] = 1 + q_1 + q_1 q_2$ 对比；② 切到典型验收（阈值 $\epsilon$），观察温度/阈值对接受长度的影响。

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

① 每轮：首 token 贪心直接收；层 1 检查目标 argmax 是否在 top-2 里，层 2 同理；统计均值应接近公式（覆盖率按实际分布计算）。② 典型验收把"argmax ∈ 集合"换成"候选概率 > min(ε, δe^{−H})"，$\epsilon$ 越小接受越多；对比两种方式的经验输出分布会发现典型验收有可测偏差——这就是 8.3 节表格的实验证据。
</details>

---

## 17. 延伸阅读

1. [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads（arXiv:2401.10774）](https://arxiv.org/abs/2401.10774)：本章全部内容出处（head 定义 §2.1.1、树注意力 §2.1.2、典型验收 §2.3.1、优化树 §2.3.3、实验 §3）。
2. [FasterDecoding/Medusa 官方仓库](https://github.com/FasterDecoding/Medusa)：参考实现（单 GPU、batch=1、典型验收默认参数）。
3. [SpecInfer（arXiv:2305.09781）](https://arxiv.org/abs/2305.09781)：树验证的一般框架（多草稿模型 + 自底向上建树），与 Medusa 的自顶向下建树对照阅读。
4. [Blockwise Parallel Decoding（arXiv:1808.02647）](https://arxiv.org/abs/1808.02647)：多头并行解码的思想源头。
5. 上一篇：[02 原始推测解码](/notes/llm推测解码精读笔记-02-原始推测解码-草稿模型与拒绝采样/)；下一篇：**04 EAGLE：特征空间草稿**——回答"为什么在隐藏状态上做自回归，接受率会大幅提升"。

