更快的解码

前两章分别讨论了请求时序与内存分配，也确立了一条执行规则：执行词元计划之前，必须先预留所需状态。更快的解码改变的是这个计划。目标模型不再每次只生成一个新词元，而是由候选生成器先给出多个候选，目标模型再一次为它们打分。一轮成功的验证可以返回多个词元，但候选生成、验证计算和临时 KV 状态也都会产生开销。

当目标模型解码时没有充分利用加速器，这种交换可能很划算。低批量的稠密模型解码常受权重搬运限制，便是典型场景。但这不是解码的普遍属性。长上下文会增加 KV 流量，模型并行会增加通信，更大的批量还可能使验证转为算力受限。因此，推测方法是否划算，必须放到实测的服务运行区间中判断。

2023 年的两项工作给出了这种思路的精确版本：Leviathan、Kalman 与 Matias 提出的推测解码 (Leviathan et al. 2023)，以及 Chen 等人提出的推测采样 (Chen et al. 2023)。后续工作改变了候选的来源与组织方式。Medusa 与 Hydra 增加草稿头 (Cai et al. 2024; Ankner et al. 2024)，EAGLE 系列学习特征或词元草稿器 (Li et al. 2024; Li et al. 2024; Li et al. 2025)，前瞻解码通过迭代构造候选 (Fu et al. 2024)，多词元预测则在训练时加入未来词元模块 (Gloeckle et al. 2024)。这些是设计选择，并不是一条必须依次经过的技术谱系。

生成虽有顺序依赖，验证可以并行

自回归生成仍有顺序依赖：第 $i+1$ 个词元取决于第 $i$ 个词元。候选后缀预先提供了这些依赖所需的输入。目标模型采用因果掩码后，便能在一次前向传播中并行给后缀中的每个位置打分。最终决定权仍在目标模型手中，候选只是创造了一批可以验证的工作。

设线性候选的长度为 $\gamma$。用 $A_k$ 表示这样一个事件：前面所有位置都已接受，并且草稿的第 $k$ 个位置也被接受。定义

$$s_k=\Pr(A_1\cap\cdots\cap A_k),\qquad s_0=1.$$

如果每轮输出已接受的前缀，再加一个修正词元或奖励词元，并且没有停止条件提前截断输出，那么该轮产出的词元数 $Y$ 满足

$$\mathbb E[Y]=1+\sum_{k=1}^{\gamma}s_k.$$

这个式子说明，总体接受词元比例不能决定前缀存活率。较早的位置可能更容易通过，较晚的位置可能更难，接受事件之间也可能相关。只有额外假设每个位置的条件接受概率都恒为 $\alpha$，才有 $s_k=\alpha^k$，从而得到

$$\mathbb E[Y] =\sum_{k=0}^{\gamma}\alpha^k =\frac{1-\alpha^{\gamma+1}}{1-\alpha}, \qquad \alpha\ne1,$$

这里，当 $\alpha=1$ 时，$\mathbb E[Y]=\gamma+1$。这个量表示每轮验证的期望产出词元数，不是延迟加速比。它还没有计入这一轮花费的时间与内存。

下面的可运行示例用一组不相同的条件接受概率计算前缀存活率，再与使用这些概率算术平均值所得的独立同分布估计比较。即使在这个很小的确定性示例中，两者也不相同。

conditional = [0.85, 0.75, 0.60, 0.40]

survival = []
alive = 1.0
for probability in conditional:
    alive *= probability
    survival.append(alive)

expected = 1.0 + sum(survival)
alpha = sum(conditional) / len(conditional)
iid_estimate = sum(alpha**k for k in range(len(conditional) + 1))

print("survival by position:", ", ".join(f"{value:.4f}" for value in survival))
print(f"expected tokens/cycle: {expected:.4f}")
print(f"iid estimate at alpha={alpha:.2f}: {iid_estimate:.4f}")

修正拒绝采样保持目标分布不变

推测解码（speculative decoding）是一种“提出候选、再验证候选”的方法，它通过修正规则保持目标模型的输出分布不变。先考虑应用既定解码策略后的一个位置，这套策略包括温度、logit 约束，以及任何 top-$k$ 或 top-$p$ 截断。这里，$p$ 表示目标分布，$q$ 表示候选分布，$\mathcal V$ 表示两者共同的词元空间。从 $q$ 中采样得到候选 $X$，即 $X\sim q$，并以如下概率接受词元 $v$：

$$a(v)=\min\!\left(1,\frac{p(v)}{q(v)}\right).$$

候选既然能从 $q$ 中采到，必有 $q(v)>0$，因此分母有定义。若拒绝该候选，则从下面的残差分布采样：

$$Z=\sum_{u\in\mathcal V}[p(u)-q(u)]_+, \qquad r(v)=\frac{[p(v)-q(v)]_+}{Z},$$

其中 $[z]_+=\max(0,z)$。拒绝概率就是 $Z$。对任意词元 $v$，接受与修正两条路径贡献的概率质量为

$$q(v)a(v)+Zr(v)=\min(p(v),q(v))+[p(v)-q(v)]_+=p(v).$$

若 $Z=0$，拒绝概率为零，残差分布也永远不会被采样。这个单位置恒等式会从左到右应用：遇到第一次拒绝便停止，输出一个修正词元，并丢弃剩余候选。如果 $\gamma$ 个候选全部接受，则从目标模型在下一个位置的分布中再采样一个奖励词元。因此，目标模型的这次传播必须同时给出所有候选位置以及奖励位置的分布 (Leviathan et al. 2023; Chen et al. 2023)。

这里的“精确”是指输出分布相同，并不等于在同一随机种子下得到完全相同的词元序列。浮点内核、批处理方式和随机数消耗顺序都可能改变某次具体采样。要保持精确，比较的分布还必须采用相同的采样变换与停止策略；温度、截断、约束与词元映射不能暗中不同。EOS、停止序列和最大长度都可能缩短一轮执行，并使奖励词元不再产生。

贪心验证是另一套确定性契约。它可以接受与目标模型贪心词元一致的最长前缀，再采用目标模型在第一个不一致位置给出的词元。典型接受等放宽规则则有意牺牲分布相等性，换取其他质量或速度指标。系统必须把这些契约分开标明。

候选来源、候选结构与接受策略是三项独立选择

实现需要分别回答三个问题：候选由谁提出，候选如何组织，以及哪条规则允许提交输出。某种候选生成机制本身并不能保证采样精确。

这张表不是排名。有的部署已经拥有兼容的小模型，有的模型则自带可用的预测头。候选质量也会随领域、上下文长度、采样设置和量化方式而变化。真正便宜的候选方案，是能在实际工作负载中降低目标周期实测成本的方案。

线性链与候选树消耗工作的方式不同

线性后缀包含 $\gamma$ 个候选位置。如果较早的词元被拒绝，后面的词元在该轮就不可能输出。候选树通过同时保留多种续写来分散这种风险。树注意力掩码把各分支装入一次目标执行，同时保证每个节点只能关注自己的祖先节点。

flowchart TD
  C[上下文] --> A1[A1] --> A2[A2]
  C --> B1[B1] --> B2[B2]
  B1 --> B3[B3]

树注意力掩码只是让联合打分成为可能，并不会自动让验证器保持精确。贪心树搜索、保持分布的树采样和放宽接受的树验证，是不同的算法。增加树宽可能提高找到可用路径的机会，但验证耗时与临时 KV 会随被打分的节点数增加。被拒绝的分支同样是真实开销，不是免费的备选项。

加速必须用实际耗时衡量

加速是实际耗时的测量结果，不能从接受率或一轮产出的词元数直接推得。

设 $t_1$ 为基线目标模型执行一个普通解码步的实测时间，$t_{\mathrm{propose}}(\gamma)$ 为候选生成时间，$t_{\mathrm{verify}}(\gamma,m)$ 为目标模型验证含 $m$ 个候选节点的方案所需时间，$t_{\mathrm{reconcile}}$ 为接受判断、同步和状态对账所需时间。对线性链而言，$m=\gamma$。一个实用的一阶延迟比为

$$S_{\mathrm{latency}} \approx \frac{\mathbb E[Y]t_1} {t_{\mathrm{propose}}(\gamma) +t_{\mathrm{verify}}(\gamma,m) +t_{\mathrm{reconcile}}}.$$

分母就是 $t_{\mathrm{cycle}}$。换句话说，只有满足

$$\frac{t_{\mathrm{cycle}}}{\mathbb E[Y]}<t_1.$$

推测方法才能降低平均每个输出词元耗时。验证时间会随候选位置、树节点、上下文长度、KV 流量、批次组成、内核和通信而变化。在低批量、受权重带宽限制的运行区间中，这部分增长可能足够小，从而让减少目标同步次数取得净收益。利用率更高时，被拒绝的候选工作会与其他请求争用资源。进入算力受限区间通常会缩小优势，但也不能由此断言所有候选方案必然失败；候选生成放在哪里、能否重叠、内核如何实现以及同步方式都会改变结果。

论文结果只能证明相应实验配置下可行，不能提供可迁移的固定倍数。Leviathan 等人在其 T5 实验中报告了约 2 到 3 倍的提升 (Leviathan et al. 2023)，EAGLE 则在所评估的 LLaMA2-Chat 配置上报告了 2.7 到 3.5 倍的延迟下降 (Li et al. 2024)。两者使用的模型、硬件、软件、采样设置和基线均不相同。应先复现实验配置后再比较。

调度器必须规划推测工作

第 32 章的“预留、执行、提交”协议可以直接应用于这里。每轮开始前，调度器应为候选位置和工作区预留空间。线性方案需要容纳整个候选后缀，树形方案则需要容纳所有待打分节点。接纳时必须按计划中的最大值接纳，不能按期望接受长度接纳。

验证结束后，只能提交已接受草稿前缀对应的目标 KV，并释放所有被拒绝的尾部或分支。草稿缓存与目标缓存属于不同命名空间：它们来自不同模型或模块，张量不可互换。修正词元或奖励词元会成为下一轮目标执行的输入，届时才为它生成对应的目标 KV。调度器还必须在取消或失败时回滚预留，之后才能把同一批块交给其他请求。

不同请求接受的前缀长度不同，因此下一批工作是不齐整的。调度器重新装配批次时，必须保留每个请求的位置、掩码、停止状态与缓存所有权。内存压力增大或并发上升时，可以缩短 $\gamma$、收窄候选树、改用成本更低的候选生成器，或者退回普通的单词元解码。没有一个通用的批量阈值能替所有部署做出这些选择。

根据工作负载证据做选择

部署决策从契约开始，以负载测试结束。

1. 固定输出契约。 明确服务承诺的是精确采样、与贪心序列逐词元一致，还是有文档说明的放宽规则。核对目标模型、词元器、词表映射、模型版本、适配器、采样变换、约束和停止行为。这里的采样变换包括 top-$k$ 与 top-$p$。
2. 分析候选预算。 在有代表性的上下文长度、输出类型、批次形状和采样设置上，扫描线性链长度或树节点预算。必须纳入低接受率工作负载，不能只针对最容易的提示词调优。
3. 测量完整周期。 记录被接受前缀长度的分布，以及候选、验证、接受、修正和奖励词元数；同时测量每个输出词元对应的目标周期数、候选生成时间、验证时间、状态对账时间，以及临时 KV 与工作区的峰值占用。
4. 按服务系统评估。 在相同的接纳负载下比较，并报告 TTFT、TPOT、词元间延迟、端到端延迟、输出吞吐、有效吞吐、拒绝率、成本与能耗。中位数和尾部都要检查。
5. 保留回退路径。 当预测成本高于普通解码、无法预留容量或兼容性检查失败时，关闭推测执行。记录每次回退发生的时间与原因。

同一个接受率或论文加速数字都不能回答部署是否受益。例如，两个系统可能接受相同比例的候选，却在不同位置发生拒绝，因此得到不同的 $\mathbb E[Y]$。它们也可能有相同的产出，但目标验证时间相差很大。

正确性与故障测试

先分别测试采样器和内存协议，再把两者放在一起测试。

• 在一个很小的词表上，分别针对 $p=q$、部分重叠和不相交支持集，将经验输出频率与目标分布比较。这里的部分重叠，是指候选分布只有一部分概率质量与目标分布重合。强制制造第一次即拒绝、较晚位置拒绝和全部接受三种情况。
• 将贪心输出与基线解码逐词元比较。测试 EOS、停止序列与最大长度，也要覆盖恰好在边界处全部接受的情况。
• 在不同温度、top-$k$、top-$p$、语法约束和 logit 处理器下重复测试。若词元器、适配器或约束不匹配，必须在开始执行前拒绝请求。
• 把混合不同的已接受前缀长度的请求组成批次。重新装配批次后，验证位置、掩码、输出顺序和每个请求各自的随机状态。
• 跨越缓存块边界，拒绝一棵较宽的候选树，在验证期间取消请求，并注入目标模型故障。核对每项预留、已提交块、引用计数和被释放分支。
• 在不同批次与内核配置下，按明确给出的容差比较数值分布。不得要求随机采样逐位完全相同。
• 把接受率压低并提高内存压力，确认排队时间有界，并能干净地退回普通解码。

收益与边界

候选生成与验证并没有消除自回归。它只是预先提供候选依赖，使目标模型能够并行验证多个位置，然后只提交明确接受契约授权的输出。收益是每个输出词元所需的昂贵目标周期更少；代价是候选生成、更宽的验证、临时内存和更复杂的状态对账。

下一章改变的是另一项互补的量。量化会减少表示模型状态所需的字节数，融合内核会减少单个周期内的数据搬运与启动开销。这些变化既可能改变基线时间，也可能影响候选接受情况。因此，更快的解码、量化与内核需要一起测量，不能把各自的加速倍数直接相乘。

延伸阅读