通过渐进式树形草稿的推测解码解锁自回归语言模型中的并行性

# 通过渐进式树草稿投机解码解锁自回归语言模型中的并行性

来源：https://arxiv.org/html/2607.10661

Zipeng Gao¹，Zhi Zheng¹，Qingrong Xia²，Junda Lin¹，Ziwei Zhao¹，Tong Xu¹，Zhefeng Wang²，Enhong Chen¹

¹认知智能国家重点实验室，中国科学技术大学
²华为技术有限公司

{gaozp619, zhengzhi97, linjunda, zzw22222}@mail.ustc.edu.cn
{zhengzhi97, tongxu, cheneh}@ustc.edu.cn
{xiaqingrong, wangzhefeng}@huawei.com

######  摘要

投机解码通过缓解内存瓶颈显著加速了大语言模型（LLM）的推理过程。然而，传统的投机解码通常依赖辅助草稿模块，这会带来大量的训练和通信开销。尽管最近的方法尝试在目标模型内部生成草稿，但由于缺乏结构协调，它们往往无法充分利用模型潜在的并行能力。本文提出了渐进式树草稿（PTD），它采用一种结构化的、有引导的并行草稿策略来挖掘模型的并行潜力。通过将渐进式树结构与逐步剪枝机制相结合，PTD 主动引导 LLM 在单次前向传播中探索多条语义路径，确保了草稿的多样性和连贯性。实验表明，PTD 在各种基准测试中实现了高达 2× 的解码加速，同时保持免训练和模型无关。我们的代码开源在：https://github.com/MINE-USTC/PTD。

## 1 引言

投机解码已成为加速大语言模型（LLM）推理的一种重要范式，它缓解了自回归生成中固有的内存瓶颈（Yuan et al., 2024；Xia et al., 2024）。通过将低效的逐 token 处理转变为候选并行验证过程，该范式在不影响生成质量的前提下，提高了计算效率和推理速度。投机解码的关键在于获取高质量的草稿。传统方法通常采用较小的辅助模块来生成草稿，这些方法往往会产生显著的通信开销，并且需要大量的训练来进行模型对齐（Xia et al., 2023；Leviathan et al., 2023；Chen et al., 2023；Miao et al., 2024；Yang et al., 2024；Cai et al., 2024；Stern et al., 2018；Li et al., 2025）。为了缓解这些问题，最近的研究转向了免训练的、模型无关的策略，直接在目标 LLM 内部生成草稿。例如，Lookahead Decoding (LADE)（Fu et al., 2024）通过在主要解码目标上补充并行雅可比迭代任务来预测和优化线性候选序列；而 Self-Draft（Gao et al., 2025）则利用 LLM 自身的鲁棒性，通过输入扰动来生成多个候选分支，从而引入一个辅助草稿任务。

尽管这些方法证实了内生加速的可行性，但我们认为，自回归模型中潜在的并行处理能力仍未得到充分利用，这主要归因于其候选生成过程的独立性和非结构性。具体来说，我们的深入分析揭示了该范式中的一个关键瓶颈。如图 2（右）所示，我们对 Self-Draft 的分析表明，超过一半的解码步骤中包含相似度超过 80% 的分支。这种高度的语义冗余表明，简单地生成独立的线性分支无法有效地引导模型的并行资源投向多样化的草稿生成。这一观察促使我们重新思考：如何才能更刻意、更有结构地引导模型，将其并行潜力转化为高质量、多样化的草稿？

参考图标题
图 1：投机解码的范式。（左）使用辅助草稿模块的传统方法。（右）内生、免训练的方法。

参考图标题
图 2：Self-Draft（Gao et al., 2025）的草稿示例（左）和分支相似度分析（右）。曲线表示至少有两条分支超过相似度阈值的步骤的比例。

基于这一见解，我们提出了渐进式树草稿（PTD），这是一种新颖的策略，它将草稿生成重新构建为一个结构化的、有引导的并行推理过程。通过利用树结构合并冗余前缀，PTD 消除了独立分支中固有的计算浪费。此外，将逐步更新的进化过程与逐步剪枝机制相结合，使得 PTD 能够引导 LLM 在单次前向传播中探索多个不同的语义路径。这种方法确保了生成的草稿既多样又连贯，从而提高了接受率并释放了模型的并行潜力。本文的主要贡献总结如下：

- • 我们识别并量化了现有线性或非结构化草稿方法中的计算冗余，揭示了这些方法未能充分利用自回归模型的并行能力。
- • 我们提出了渐进式树草稿（PTD），这是一种将草稿生成重构为结构化的、有引导的并行生成过程的策略，以确保草稿的多样性和连贯性。
- • 实验结果表明，PTD 在各种基准测试中始终能够实现高达 2× 的加速，且无需任何辅助模块。

本文的结构如下：首先，我们回顾相关工作，然后详细描述所提出的方法。接着，我们展示实验结果以验证其有效性。最后，我们总结全文并讨论未来可能的研究方向。

## 2 相关工作

### 2.1 带有附加模块的投机解码

传统的投机解码范式依赖**附加模块**，包括独立模型和架构扩展，来生成候选 token。最初的公式（Xia et al., 2023；Leviathan et al., 2023）使用一个较小的独立**草稿模型**生成候选，然后由目标 LLM 进行验证。这些方法存在序列化瓶颈，并且严重依赖草稿模型的准确性。PEARL（Liu et al., 2025）和 SwiftSpec（Zhang et al., 2025）通过优化草稿生成和验证阶段之间的交互协议来解决这些同步问题。后续的工作如 MCSD（Yang et al., 2024）和 SpecInfer（Miao et al., 2024）通过使用多个草稿模型或采样策略来增强多样性，但维护多个独立的模型仍然是一个瓶颈。JudgeDecoding（Bachmann et al., 2025）采用了一种宽松的对齐范式，通过轻微牺牲准确性来提升验证速度。基于检索的方法如 REST（He et al., 2023）用外部数据存储模块替代了草稿模型，但这将依赖性转移到了检索语料的质量和领域相关性上。

或者，某些方法将草稿模块直接集成到目标模型的架构中。EAGLE 系列（Li et al., 2024a；b）、Medusa（Cai et al., 2024）、Blockwise Decoding（Stern et al., 2018）、Hydra（Ankner et al., 2024）向 LLM 附加**额外的预测头或层**，以并行预测未来的 token。尽管这些架构修改相比独立模型减少了通信延迟，但它们从根本上改变了模型结构，需要大量额外的训练，并且无法无缝部署在现有的即用型 LLM 上。

### 2.2 免训练的内生加速

与基于模块的方法不同，最近的一系列研究专注于**内生加速**，即利用目标 LLM 的内在能力来生成草稿，无需任何额外模块或训练。Lookahead Decoding (LADE)（Fu et al., 2024）利用雅可比迭代方法在原始模型架构内进行并行解码。同时，Self-Draft（Gao et al., 2025）利用 LLM 自身的鲁棒性，采用多分支输入扰动来促使模型生成自己的草稿。这些方法代表了向架构无关加速的转变。然而，正如引言中所述，当前的内生方法通常依赖缺乏结构协调的线性或迭代生成方案，未能完全利用模型的并行潜力。我们的渐进式树草稿（PTD）通过引入一种结构化的、有引导的探索机制，推进了这一范式，在无需额外模块负担的情况下实现了高效的自加速。

## 3 方法

传统的自回归解码每次预测一个 token。给定前缀 \(\mathbf{X} = [x_1, x_2, \cdots, x_{t-1}]\)，LLM 计算下一个 token 的分布 \(P(y_t|\mathbf{X})\)，并使用解码策略 \(\mathcal{S}\) 选择下一个 token：
\[
x_t = \mathcal{S}(P(y_t|\mathbf{X}))
\]
投机解码通过引入候选续写 \(\mathbf{C}_{\mathbf{X}}\) 并并行验证它们来推广这一步：
\[
x_t, x_{t+1}, ..., x_{t+k} = \mathcal{S}\left(P(y_t, \mathbf{y}_{\mathbf{C}} | [\mathbf{X}; \mathbf{C}_{\mathbf{X}}])\right),
\]
这些公式为投机解码提供了理论基础。在实践中，传统实现通常依赖外部草稿模型，但这种依赖会带来对齐和通信开销。内生加速通过利用目标模型内部的并行处理能力，提供了一种更高效的替代方案。具体来说，基于 Transformer 的 LLM 的推理行为由输入内容和注意力矩阵控制。通过重新配置输入内容和注意力掩码，我们可以将模型的注意力从线性路径转移到多个并发推理轨迹上。这种灵活性允许 LLM 在单次前向传播中探索结构化的语义空间并生成高质量的草稿。

基于这一见解，我们开发了渐进式树草稿（PTD），将模型的并行潜力转化为实际的解码加速。PTD 的设计聚焦于解决两个实际问题：如何组织并行草稿路径以及如何保持它们的上下文连贯性。对于前者，我们采用草稿树，因为其前缀共享特性代表了自回归模型理论上支持的最复杂拓扑。对于后者，我们引入了一种带有逐步剪枝的渐进式更新算法，以确保生成的内容与上下文相关。

参考图标题
图 3：渐进式树草稿（PTD）框架概览。**绿色**路径展示了候选草稿的验证过程，而**蓝色**路径则表示语义引导的渐进式树草稿过程。**红色**框表示解码结果。

图 3 展示了 PTD 的整体框架。在以下小节中，我们首先介绍控制草稿树动态演化的树扩展和剪枝策略。然后，我们详细说明草稿提取过程和验证机制。

### 3.1 渐进式树草稿

为了将 LLM 的并行潜力转化为实际加速，我们提出了渐进式树草稿（PTD）机制。本节详细阐述树的生命周期，从其结构初始化到动态演化和剪枝。

**树构建。** 我们将草稿结构表示为树 \(T = (V, E)\)。为了启动渐进过程，\(T\) 首先用一组种子节点初始化。这些节点可以通过随机方式生成，或者从上下文中的语义信息推导而来，用于触发 LLM 在不同语义轨迹上的推理。为了确保语义一致性，每个节点 \(v \in V\) 只能关注其祖先。形式上，对于任何节点 \(v\)，其可观察前缀节点集合 \(\pi(v)\) 递归定义如下：
\[
\pi(v) = \{v\} \cup \pi(\mathcal{P}(v))
\]
其中 \(\mathcal{P}(v)\) 表示节点 \(v\) 的唯一父节点。节点 \(v\) 的位置编码由 \(\pi(v)\) 的基数决定，确保树结构输入与 Transformer 的因果注意力兼容。

**渐进式扩展。** 在第 \(t\) 步对草稿树 \(T^{t-1}\) 的推理公式化为：
\[
x_t, \mathcal{D}_t = \mathcal{S}\left(P\left(y_t, \mathbf{y}_T | [\mathbf{X}; T^{t-1}]\right)\right)
\]
其中 \(\mathcal{D}_t = \{d_v \mid v \in V^{t-1}\}\) 是在单次前向传播中由 \(T^{t-1}\) 中所有节点生成的**草稿 token** 集合。PTD 然后将这些新生成的 token 作为子节点附加到树上，从而将草稿树演化为 \(T^t = (V^t, E^t)\)：
\[
V^t = V^{t-1} \cup \{d_v\}_{v \in V^{t-1}}, \quad E^t = E^{t-1} \cup \{(v, d_v)\}_{v \in V^{t-1}}
\]

参考图标题
图 4：逐步剪枝算法示意图。

**开销约束。** 通常，草稿树中的节点数量保证了其生成的草稿的多样性，而扩展过程则维护了树中相邻节点之间的语义连贯性。然而，草稿树引入的计算开销会随着其增长而逐渐增加。因此，有必要对其增长施加约束，以防止规模过大，否则可能降低整体解码速度。具体来说，我们从两个维度对树形拓扑施加约束：

- • **宽度控制：** 我们限制每个父节点的最大子节点数。这可以防止低置信度的 token 过度分支，确保树聚焦于高概率的推理路径。
- • **步进机制（深度控制）：** 为了防止树变得过深，我们实现了一种滑动窗口式的步进机制。如图 4 所示，当子树超过深度阈值时，我们保留最早添加的子节点及其后代作为新的子树，并修剪所有其他陈旧分支。这种步进机制