↓
  1. 笔记/

LLM 推测解码精读笔记 · 03 Medusa：多头解码

··
LLM推理优化 推测解码

对应：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$）21.961.001.96x
$s=(3,2)$92.621.102.38x
$s=(4,3,2)$403.311.182.81x
优化稀疏树643.451.252.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-7B2.18x
Medusa-1 · Vicuna-13B2.33x
Medusa-2 · Vicuna-7B2.83x
Medusa-2 · Vicuna-13B2.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 章公式。

题 1 解答

$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$ 时的公式。

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

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

题 2 解答

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

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

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

题 3 解答

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

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

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

题 4 解答要点

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

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

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

题 5 解答

节点贡献 = 路径上边际命中率之积。候选及贡献：层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 节"树不是越大越好"的来源。

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

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

题 6 解答要点

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

17. 延伸阅读 #

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