Speculative Speculative Decoding

  • 文章标题：推测性推测解码
  • 作者/机构：Tanishq Kumar (斯坦福大学), Tri Dao (普林斯顿大学, Together AI), Avner May (Together AI)

A1 主要贡献

本文旨在解决推测解码（Speculative Decoding, SD）中存在的草稿（drafting）与验证（verification）之间的顺序依赖问题。在标准的推测解码中，草稿模型必须等待验证过程完成后才能开始下一轮的推测，这限制了其加速效果。

核心问题：我们能否消除草稿和验证之间的顺序依赖？

研究目标与创新点：
为了解决此问题，本文提出了推测性推测解码（Speculative Speculative Decoding, SSD），一个统一的框架，旨在并行化草稿和验证操作。其核心思想是：当目标模型正在进行验证时，草稿模型并不空闲等待，而是预测多种最可能出现的验证结果，并为这些结果预先推测（pre-speculates）后续的tokens。如果实际的验证结果恰好是预先推测的几种之一，草稿模型便可以立即返回已准备好的推测序列，从而完全消除草稿生成的开销。SSD与普通推测解码一样，是无损的，但要求草稿模型部署在与目标模型不同的硬件上。

本文识别并解决了实现高效SSD算法的三个主要挑战，并提出了一个名为Saguaro的优化SSD算法：
1. 验证结果预测：为了解决如何从海量的可能验证结果中选出最可能的部分进行预推测的问题，本文将其构建为一个约束优化问题。Saguaro使用草稿模型最可能的logits来预测奖励令牌（bonus token），准确率高达90%。
2. 接受率与预测准确率的权衡：本文发现，在提高验证结果预测准确率与生成高质量（高接受率）的推测之间存在一个微妙的权衡。为此，开发了一种新的采样算法，允许在这两者之间进行平衡。
3. 缓存未命中处理：对于未能成功预测验证结果的情况（缓存未命中），本文研究了多种回退策略，并证明最优策略随批量大小（batch size）而变化。Saguaro采纳了这种自适应策略，即使在较大批量下，尽管每个批次元素需要更多的计算，但性能仍比SD高出20%。

主要成果：
Saguaro算法的实现相较于优化的推测解码基线实现了高达2倍的加速，相较于自回归生成（autoregressive decoding）实现了高达5倍的加速（如图1和图7所示），并在不同批量大小下全面改进了吞吐量-延迟的帕累托前沿。


图1：（左）普通推测解码（SD）要求验证器在草稿推测时空闲等待。（中）在我们的算法中，推测在独立的设备（1×H100）上与验证并行运行；草稿模型为多种可能的验证结果预先计算推测，如果其中之一发生，则立即返回推测的令牌。（右）SSD、SD和自回归（AR）解码在四个跨越数学、代码和聊天的数据集上的端到端性能平均值，针对Llama-3.1-70B在TP=4 H100s上，批量大小为1，贪婪解码，草稿模型为Llama-3.2-1B。

A3 背景知识

2.1 投机解码

投机解码原理。投机解码通过使用一个计算成本较低的草稿分布 $p_{draft}$ 来生成候选续写，然后使用目标分布 $p_{target}$ 进行选择性接受，从而加速从目标分布 $p_{target}$ 的采样。在验证阶段，目标模型首先通过一次前向传播并行计算所有推测令牌的概率。草稿令牌按顺序被接受，每个令牌的接受概率为 $\min\{1, p_{target}(x)/p_{draft}(x)\}$。一旦出现第一个被拒绝的令牌，剩余的草稿令牌将被丢弃，并使用最后一个令牌的目标logits来采样一个“奖励令牌”（bonus token）。这是通过从一个修改后的分布中采样奖励令牌来完成的，该分布保证了最终生成的序列与从 $p_{target}$ 中采样的分布一致。这个修改后的分布被称为残差分布（residual distribution），其形式为 $r(·) \propto \max (p_{target}(·) − p_{draft}(·), 0)$。如果所有令牌都被接受，残差分布就是目标分布本身。

接受率与分布近似度。每轮生成的预期令牌数，也即投机解码的整体效率，由接受率决定：即在所有先前令牌都被接受的条件下，接受当前推测令牌的概率。在【19, Fast inference from transformers via speculative decoding, 2023, https://arxiv.org/abs/2211.17192】中，证明了接受率可以表示为草稿分布对目标分布的近似程度，具体如下 。

定理1。（Leviathan et al., 2023）

$$\alpha = \sum_{x} \min\{p_{\text{target}}(x), p_{\text{draft}}(x)\} = 1 - \frac{1}{2} \| p_{\text{target}} - p_{\text{draft}} \|_{1}$$

推测序列的定义。我们将第T轮的推测定义为一个由草稿模型自回归提出的K个令牌序列，记为 $s_T := (s_{T_1}, . . . , s_{T_K})$。推测序列的长度K被称为推测前瞻（speculative lookahead）。

验证结果的定义。我们将第T轮的验证结果定义为 $v_T := (k, t^*) \in V_T$，其中 $(s_{T-1}, ..., s_{T-1})$ 是从第T-1轮接受的草稿令牌，而 $t^*$ 是从残差分布（或在所有令牌都被接受时从目标分布）中采样的奖励令牌。

2.2 相关工作

并行投机解码。AMUSD【27, AMUSD: asynchronous multi-device speculative decoding for LLM acceleration, 2025, ISCAS】和PEARL【26, Pearl: Parallel speculative decoding with adaptive draft length, 2025, https://arxiv.org/abs/2408.11850】提出在进行验证的同时推测下一轮，但它们只为所有令牌都被接受这一种验证结果做准备，而这只是众多可能结果中的一种特例。SwiftSpec 【45, Swiftspec: Ultra-low latency llm decoding by scaling asynchronous speculative decoding, 2025, https://arxiv.org/abs/2506.11309】和SpecBranch 【36, Speculative decoding via hybrid drafting and rollback-aware branch parallelism, 2025, https://arxiv.org/abs/2506.01979】准备了一个更大的缓存，该缓存由一个从正在验证的推测序列分支出来的令牌树组成（从而实现更大的加速），但这两种方法都使用了在大型批处理中效果不佳的回退策略。SpecBranch的动机与SSD相似：它（近似地）构成了SSD框架的一个特例，其中只允许一个分支点，回退推测器与常规推测器相同，并且超参数（分支点、分支数、推测长度）是动态选择以最大化加速效果。SwiftSpec考虑了贪婪采样的特殊情况，并采用了一种即时推测的回退策略，这种策略在较高温度和批处理大小时，当缓存未命中变得不可避免时会遇到困难 。

基于树的投机解码。已有多篇工作提出通过让草稿模型推测一个令牌树而非序列，来增加预期接受的令牌数，从而在每个位置为验证器提供多个令牌选项【28, Specinfer: Accelerating large language model serving with tree-based speculative inference and verification, 2024, ASPLOS】【6, Sequoia: Scalable and robust speculative decoding, 2024, NeurIPS】【23, EAGLE-2: faster inference of language models with dynamic draft trees, 2024, EMNLP】【37, Specexec: Massively parallel speculative decoding for interactive LLM inference on consumer devices, 2024, NeurIPS】。我们的方法在几个重要方面有所不同：首先，现有的基于树的方法仍然是顺序的：先推测，后验证。其次，基于树的方法引入了大量的验证器计算——由于目标模型规模巨大，这部分计算非常昂贵——因为整个树都必须在目标模型的前向传播中进行验证。相比之下，我们的方法通过并行地为多个验证结果进行预推测来扩展推测计算，但不会引入任何额外的验证器计算。最后，值得注意的是，我们的方法可以与这些基于树的方法结合以获得进一步的性能提升（详见附录E的讨论）。

改进的草稿模型架构。在草稿模型架构方面已有许多进展，可以提高草稿模型的接受率和/或速度，这些进展可以用于SSD以获得更好的性能。例如，EAGLE【22, EAGLE: speculative sampling requires rethinking feature uncertainty, 2024, ICML】【23, EAGLE-2: faster inference of language models with dynamic draft trees, 2024, EMNLP】【24, Eagle-3: Scaling up inference acceleration of large language models via training-time test, 2025, https://arxiv.org/abs/2503.01840】允许草稿模型将来自目标模型的强大表示作为当前前缀的输入，而GliDe 【11, Glide with a cape: A low-hassle method to accelerate speculative decoding, 2024, https://arxiv.org/abs/2402.02082】和LongSpec 【42, Longspec: Long-context lossless speculative decoding with efficient drafting and verification, 2025, https://arxiv.org/abs/2502.17421】允许草稿模型对目标模型的KV缓存执行交叉注意力。替代的模型架构，如扩散语言模型 （diffusion LLMs）【30, Large language diffusion models, 2025, NeurIPS】【32, Simple and effective masked diffusion language models, 2024, NeurIPS】【21, Diffuspec: Unlocking diffusion language models for speculative decoding, 2025, CoRR】【7, Speculative diffusion decoding: Accelerating language generation through diffusion, 2025, NAACL】【33, Your LLM knows the future: Uncovering its multi-token prediction potential, 2025, CoRR】【4, Dflash: Block diffusion for flash speculative decoding, 2026, https://arxiv.org/abs/2602.06036】或状态空间模型（SSMs） 【16, Efficiently modeling long sequences with structured state spaces, 2022, ICLR】【15, Mamba: Linear-Time Sequence Modeling with Selective State Spaces, 2023, arXiv】【38, The mamba in the llama: Distilling and accelerating hybrid models, 2024, NeurIPS】，也可以用来提高草稿模型生成推测令牌序列的速度。我们在附录E中包含了更多关于SSD如何与这些改进的草稿模型架构（例如，EAGLE-3）有效结合的技术细节。

A2 方法细节

3 推测性推测解码框架

我们引入推测性推测解码（SSD），一个用于推理推测解码的异步变体的框架（第3.1节），并展示了将SSD的预期速度与基线进行比较的结果（第3.2节）。本节引入的定义在第4节中将非常重要。

3.1 算法

SSD框架概述。我们在算法1中展示了SSD框架。推测器（speculator）和验证器（verifier）进程在不同的硬件上并行运行。当验证器正在验证第T轮的草稿令牌时，推测器开始推测第T+1轮。它通过预测可能的验证结果，然后为每个这些结果并行准备推测，并将这些推测存储在一个“推测缓存”（speculation cache）中（下文将正式定义）。然后，当它接收到实际的验证结果时，它会检查这个结果是否在它已准备的缓存结果中。如果是，它会立即返回对应的推测。否则，它会转而采用一个回退推测策略（fallback speculation strategy）。

与推测执行的类比。为了直观理解SSD算法及其无损性质，可以考虑它与用于CPU优化的推测执行（speculative execution）【14, Speculative execution via address prediction and data prefetching, 1997, ICS】的相似之处。就像推测执行利用空闲计算资源预先执行条件路径以备后用一样，SSD对多种可能的验证结果进行预推测，以便当其中一种发生时，相应的令牌序列立即可用。然后，该序列完全按照标准SD的方式进行验证。如果实现的验证结果未被预推测，SSD会回退到一个同步的推测器，这是无损的，因为它退化为普通的SD。以下定义对于理解SSD框架至关重要。

推测缓存的定义。我们将第T轮的推测缓存$S_T$定义为一个字典，它将一组验证结果$V_T$映射到为这些结果预先计算的推测。我们用$S_T(v_T)$表示一个缓存查找操作，它对应于结果$v_T \in V_T$的推测令牌序列$s_T$。

$$\begin{aligned} \begin{array}{l} \hline \textbf{Algorithm 1: } \text{The Speculative Speculative Decoding (SSD) Framework.} \\ \hline \textbf{Function } \text{main}(prompt, target, primary\_draft, backup\_draft)\text{:} \\ \quad \text{asynchronously launch } speculator(prompt, primary\_draft, backup\_draft) \\ \quad generated\_tokens \leftarrow verifier(prompt, target) \\ \quad \textbf{return } generated\_tokens \\ \\ \textbf{Function } verifier(prompt, target)\text{:} \\ \quad target.prefill(prompt) \\ \quad \textbf{WAIT TO RECEIVE } spec\_tokens \text{ from } speculator \\ \quad generated\_tokens \leftarrow [] \\ \quad \textbf{while } \text{True } \textbf{do} \\ \quad \quad verify\_outcome \leftarrow target.verify(spec\_tokens) \\ \quad \quad generated\_tokens.append(verify\_outcome.tokens) \\ \quad \quad \textbf{SEND } verify\_outcome \text{ to } speculator \\ \quad \quad \textbf{if } end\_token \in verify\_outcome \textbf{ then} \\ \quad \quad \quad \textbf{return } generated\_tokens \\ \quad \quad \textbf{end} \\ \quad \quad \textbf{WAIT TO RECEIVE } spec\_tokens \text{ from } speculator \\ \quad \textbf{end} \\ \\ \textbf{Function } speculator(prompt, primary\_draft, backup\_draft)\text{:} \\ \quad primary\_draft.prefill(prompt) \\ \quad spec\_tokens \leftarrow primary\_draft.speculate(prompt) \\ \quad \textbf{while } \text{True } \textbf{do} \\ \quad \quad \textbf{SEND } spec\_tokens \text{ to } verifier \text{ for verification} \\ \quad \quad \color{blue}{outcomes \leftarrow predict\_verify\_outcomes(spec\_tokens, primary\_draft) // \text{ Sec. 4.1}} \\ \quad \quad \color{blue}{cache \leftarrow speculate\_for\_outcomes(outcomes, primary\_draft) // \text{ Sec. 4.2}} \\ \quad \quad \textbf{WAIT TO RECEIVE } verify\_outcome \text{ from } verifier \\ \quad \quad \textbf{if } end\_token \in verify\_outcome \textbf{ then} \\ \quad \quad \quad \textbf{return} \\ \quad \quad \textbf{end} \\ \quad \quad \textbf{if } verify\_outcome \in cache \textbf{ then} \\ \quad \quad \quad spec\_tokens \leftarrow cache[verify\_outcome] \\ \quad \quad \textbf{else} \\ \quad \quad \quad \color{blue}{spec\_tokens \leftarrow fallback\_speculate (} \\ \quad \quad \quad \quad \color{blue}{verify\_outcome, primary\_spec, backup\_spec} \\ \quad \quad \quad \color{blue}{) // \text{ Sec. 4.3}} \\ \quad \quad \textbf{end} \\ \quad \textbf{end} \\ \hline \end{array} \end{aligned}$$

缓存命中/未命中的定义。缓存命中（cache hit）指的是验证$s_{T-1}$的结果$v_T$包含在推测缓存$S_T$中。缓存未命中（cache miss）指的是$v_T \notin S_T$。

命中概率的定义。设$p_{hit,p}$为在一次迭代中发生缓存命中的概率，条件是前一次迭代是由主推测器（primary speculator）进行推测的。类似地，$p_{hit,b}$表示在一次迭代中发生缓存命中的概率，条件是使用备用模型（backup model）进行推测。最后，设$p_{hit}$为在一次迭代中发生缓存命中的无条件概率。

3.2 理论结果

性能分析引言。我们分析了Saguaro相对于常规自回归解码（定理7）和普通推测解码（推论9）的性能。证明过程推迟到附录A。

SSD相对于自回归解码的加速比。设主推测器和备用推测器相对于验证器的时间分别为$T_p$和$T_b$。设$E_{hit}$和$E_{miss}$分别表示主推测器和备用推测器生成的预期令牌数。那么，算法1相对于自回归解码的预期加速比为：

$$speedup_{\text{SSD}} = \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{p_{\text{hit}} \cdot \max(1, T_p) + (1 - p_{\text{hit}}) \cdot (1 + T_b)}.$$


公式的分子对应算法每次迭代中生成的预期令牌数，分母对应每次迭代相对于自回归解码的预期延迟。这引出了两个关键的推论。

关键推论。
- 推论8（严格快于SD）：假设我们使用给定的推测器M运行SD。如果运行SSD时将主推测器和备用推测器都设置为M，其性能不会比SD差（如果$p_{hit} > 0$且$T_{SD} > 0$，则严格更优）。
- 推论9（加速比上下界）：假设我们选择一个主推测器，其草稿生成在验证完成前结束（$T_p < 1$），以及一个快速的备用推测器（$T_b = 0$）。如果$T_{SD}$和$E_{SD}$分别代表SD中草稿模型的延迟和预期生成令牌数，那么SSD相对于SD的加速比可以被界定为：

$$ \left(1+T_{\mathrm{SD}}\right) \cdot \frac{E_{\mathrm{hit}}}{E_{\mathrm{SD}}} \cdot p_{\mathrm{hit}} \leq \frac{speedup_{\mathrm{SSD}}}{speedup_{\mathrm{SD}}} \leq \left(1+T_{\mathrm{SD}}\right) \cdot \frac{E_{\mathrm{hit}}}{E_{\mathrm{SD}}} . $$


这个方程揭示了SSD可实现的最大加速比与隐藏草稿延迟所带来的延迟减少（$1 + T_{SD}$）以及增加草稿时间所带来的预期生成令牌数增加（$E_{hit}/E_{SD}$）成正比。然而，较低的缓存命中率$p_{hit}$会降低该算法的有效性，如下界所示。

4 Saguaro：一个优化的SSD算法

在本节中，我们介绍Saguaro，它是SSD框架的一个优化实例。我们将分别在第4.1节（Saguaro缓存构建）、第4.2节（Saguaro采样）和第4.3节（Saguaro回退）中介绍三个核心优化，然后在第5节中对Saguaro进行端到端评估。

实验设置。除非另有说明，实验均在批量大小为1和贪婪解码的条件下运行，目标模型部署在4个H100上。在SD中，草稿模型与目标模型部署在相同的硬件上。在SSD中，草稿模型位于一个独立的设备上（1个H100），因为它在验证期间异步进行推测。我们研究了两个模型家族，Llama-3（正文）和Qwen-3（附录F），并在四个数据集上进行测试：Alpaca【12, Alpacafarm: A simulation framework for methods that learn from human feedback, 2023, https://arxiv.org/abs/2305.14387】，GSM8k 【8, Training verifiers to solve math word problems, 2021, https://arxiv.org/abs/2110.14168】，UltraFeedback 【9, Ultrafeedback: Boosting language models with scaled ai feedback, 2024, https://arxiv.org/abs/2310.01377】，HumanEval 【5, Evaluating large language models trained on code, 2021, https://arxiv.org/abs/2107.03374】。更多细节见附录B 。

4.1 预测验证结果：构建Saguaro缓存

验证结果预测的挑战。给定一个正在被验证的推测$s_T$，Saguaro必须为最可能的验证结果构建一个缓存$S_T$。困难在于可能的验证结果空间非常巨大，大小约为$(K + 1)V$，其中V是模型的词汇表大小。由于存在$O(KV)$个潜在的验证结果，为所有这些结果并行地进行预推测是不切实际的。这启发我们将验证预测问题构建为一个约束优化问题：在给定B个验证结果的预算下，应如何选择它们以最大化缓存命中的机会？注意，预算B通常对应于在验证完成前，草稿模型能够完成推测的最大结果数量。

4.1.1 算法

扇出策略的定义。我们将在位置k的扇出（fan-out） $F_p$ 定义为：在给定前一轮由主推测器推测的情况下，推测缓存中包含的、接受了k个令牌的验证结果的数量，即 $F_p := |\{v_T := (k', t^*) \in S_T | k' = k\}|$。$F_b$ 的定义类似，用于备用推测器。


图2：推测缓存策略示意图。我们根据定理12，在序列长度K+1上分配扇出$F_k$（奖励令牌的猜测）。

Saguaro验证结果预测算法。给定一个扇出策略 $\{F_k^p, F_k^b\}$（我们的策略基于定理12），Saguaro在草稿logits的每个前瞻位置k处选择前$F_k$个令牌，并将它们添加到推测缓存中。这些是排除了在该位置发送用于验证的采样令牌（该令牌保证不会是奖励令牌）之后的前$F_k$个logits。

4.1.2 理论结果

扇出值优化。我们展示了如何优化扇出值$F_k^p$和$F_b$的选择，以在推测缓存大小的约束下最大化加速比。

缓存命中率的幂律特性。在给定迭代中，验证结果为(k, ·)的概率取决于前一次推测是由主推测器还是备用推测器生成的。因此，如果在构建缓存时默认的扇出策略是在每个序列位置均匀扇出，那么在给定迭代中的缓存命中率将取决于前一次迭代是由主推测器还是备用推测器推测的。这分别是$p_{hit,p}(F)$和$p_{hit,b}(F)$的定义。我们在图3中看到，这些函数（实际上是它们的补集，即拒绝率）在经验上遵循幂律。

r次幂律缓存命中率的定义。我们说一个推测器具有r次幂律缓存命中率，如果对于由该推测器草稿的序列，扇出为F时的缓存未命中概率等于F的r次幂，即对于某个r > 0，有 $1 - p_{hit,*}(F) = 1/F^r, \forall F \in N$。

基于幂律假设优化扇出。我们现在使用这个定义来推断在缓存大小的计算约束下，如何最优地选择扇出值$F_k^p$和$F_k^b$。我们在附录A中考虑了这个假设不成立的一般情况。

Saguaro缓存形状：几何扇出（定理12）。考虑一个接受率为$a_p$且具有r次幂律缓存命中率的草稿模型。那么，在约束$\sum_{k=0}^{K} F_k^p \le B$下，对于$k \in [0, K]$的最优$F_k^p$值选择遵循一个有上限的几何级数：

$$\begin{aligned} \begin{aligned} F_{k} & =F_{0} \cdot a_{p}^{k /(1+r)} \forall k<K, \text { and } \\ F_{K} & =F_{0} \cdot a_{p}^{K /(1+r)} \cdot\left(1-a_{p}\right)^{-1 /(1+r)}, \end{aligned} \end{aligned}$$ <p>
其中$F_0$的选择可以使得$\sum_{k=0}^{K} F_k^p = B$（闭式解见附录A）。对于$F_k^b$也有等价的结果。

理论结果的直觉解释。这个结果清晰地反映了一个直觉，即已验证字符串的长度遵循一个在推测前瞻范围内有上限的几何分布。换句话说，如果验证器接受$j \in [0, K]$个令牌的可能性很小，我们就不应该浪费计算资源去猜测和推测该位置的奖励令牌，而应该降低$F_j$。

4.1.3 经验评估

几何扇出与均匀扇出的对比。我们比较了使用朴素的（均匀）扇出策略与定理12提出的几何扇出策略的端到端性能。在图4中，我们发现几何扇出策略提高了缓存命中率（右图）和端到端解码速度，尤其是在较高的温度下，此时SD和均匀扇出策略的性能都开始下降。


图3：缓存命中率随扇出的扩展情况。（左，中）分别以前一轮推测来自主推测器和备用推测器为条件，拒绝率（1 - $p_{hit,*}(F)$）的变化。拒绝率（缓存未命中）随草稿扇出呈幂律下降，表明缓存命中率随缓存大小增加而增加。（右）总体的缓存命中率$p_{hit}(F)$。


图4：几何扇出策略的优势在较高温度下增加，从而提高了推测缓存命中率（右）和端到端速度（左）。结果为四个数据集的平均值。在所有温度下，使用任一扇出策略的SSD都优于普通推测解码。

4.2 通过Saguaro采样平衡缓存命中率和接受率

预测残差分布的挑战。在大多数情况下，奖励令牌是从残差分布中采样的（除非所有令牌都被接受，此时直接从目标分布中采样）。回想一下，残差分布由$r(·) \propto \max(p_{target}(·) - p_{draft}(·), 0)$给出。这个分布可能很难预测，尤其是在采样温度升高时。我们引入一种新颖的采样方案，使这个残差分布更容易预测，从而提高缓存命中率。

Saguaro采样的权衡。该采样方案利用了残差分布是草稿分布（包括草稿采样方案）的函数这一事实。我们通过明确增加最可能的草稿令牌上的残差概率质量，使奖励令牌更容易预测；这是通过在从草稿中采样时减少相应的概率质量来实现的。然而，在偏置草稿分布时，我们可能会因为使草稿分布离目标分布更远而降低接受率（见定理1），从而在接受率和缓存命中率之间产生一个权衡，这两者都对端到端速度有贡献（见图5，左）。我们在附录A.3.1中证明，存在$p_{target}$和$p_{draft}$分布，使得以这种方式偏置草稿分布会导致端到端的加速。

4.2.1 算法

采样方案的定义。我们将采样方案定义为一个从模型logits $z_{draft} \in R^V$到概率分布$p \in \Delta^{V-1}$的函数$\sigma: R^V \rightarrow \Delta^{V-1}$。

缓存感知采样方案。为了理解如何设计一个能增加最可能草稿令牌上残差概率质量的采样方案，我们首先注意到令牌t在残差分布中的概率正portional于$\max(p_{target}(t) - p_{draft}(t), 0)$。因此，减小$p_{draft}(t)$会增加t在残差分布中的概率。这正是我们的缓存感知采样方案所做的。

Saguaro采样方案的定义。给定草稿logits $z \in R^V$，我们将扇出为F和降权常数$C \in [0, 1]$的Saguaro采样方案$\sigma_{F,C}(z)$定义为：

$$\begin{aligned} \sigma_{F, C}(z) \propto \begin{cases}C \cdot \exp \left(z_t\right) & \text { if } t \in \operatorname{top}_F(z) \\ \exp \left(z_t\right) & \text { otherwise, }\end{cases} \end{aligned}$$


在实践中，C是一个通过经验选择的超参数。

4.2.2 理论结果

Saguaro采样与缓存命中率的关系（定理15）。对于扇出F和主推测器logits z，Saguaro采样方案的缓存命中率$p_{hit}$随着$C \rightarrow 0$单调增加。

Saguaro采样的直觉。新的采样超参数C允许在缓存命中率和接受率之间进行权衡。我们在图5（左）中绘制了这种权衡。图5（右）展示了Saguar_sampling如何通过在推测期间操纵草稿分布来控制残差分布的示意图。其直觉是，Saguaro采样有意地抑制了F个缓存令牌上的草稿概率。通过降低这组令牌上的$p_{draft}(t)$，残差$\max(p_{target}(t) - p_{draft}(t), 0)$被推动集中在这些相同的令牌上，从而通过构造增加了奖励令牌落在缓存内的机会。

4.2.3 经验评估

实验验证权衡关系。我们在图5中展示了接受率和缓存命中率之间存在一个权衡，我们可以通过使用不同C值的Saguaro采样方案来调控。较低的C值会导致较高的缓存命中率和较低的接受率，因为它们为了控制残差分布而使草稿分布偏离了目标分布。


图5：我们引入了Saguaro采样，这是一种专为SSD设计的新颖采样方案。（左）它在高缓存命中率和高推测接受率之间进行插值。（右）Saguaro采样如何增加顶部草稿令牌上的残差概率质量的示意图，通过构造鼓励采样出的奖励令牌位于推测缓存中。

4.3 使用Saguaro回退处理缓存未命中

缓存未命中处理优化。我们现在讨论如何在Saguaro中优化缓存未命中的处理，并根据批量大小提出一个选择备用推测器的最优策略。

4.3.1 算法

Saguaro回退策略。我们基于这样一个观察来设计Saguaro的缓存未命中策略：在大的批量大小时，缓存未命中几乎肯定会发生，并且当这种情况发生时，在SSD中，整个批次都必须等待备用推测器完成才能进行验证。我们提出了Saguaro回退策略：在低批量大小时，将备用推测器设置为主推测器；当批量大小$b > b^*$时，切换到一个低延迟的推测器（例如【31, Suffixdecoding: Extreme speculative decoding for emerging ai applications, 2024, CoRR】；【25, Infini-gram: Scaling unbounded n-gram language models to a trillion tokens, 2024, CoRR】；【40, Infini-gram mini: Exact n-gram search at the internet scale with fm-index, 2025, CoRR】），其中临界批量大小$b^*$在下一节中推导。

4.3.2 理论结果

策略最优性证明。我们证明，在SSD使用高质量（慢）推测器（主）和低质量（快）推测器（备用）的条件下，Saguaro的备用推测器策略是最优的。我们从定理7的一个推论开始，该推论考虑了批量大小对SSD所获加速比的影响。这个结果假设在SSD中，整个批次等待备用推测器完成后才进行验证。

批量大小对加速比的影响（推论16）。在批量大小为b时，SSD的预期加速比等于：

$$\begin{aligned} \begin{aligned} speedup & = \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{p_{\text{hit}}^b \cdot \max(1, T_p) + (1 - p_{\text{hit}}^b) \cdot (1 + T_b)}, \quad \textit{which approaches} \\ & \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{1 + T_b} \quad \textit{as } b \to \infty. \end{aligned} \end{aligned}$$

大批量下对低延迟推测器的需求。在我们的实现中，备用策略是返回随机令牌，而主策略是进行即时推测。随着批量大小的增加，由于缓存未命中更频繁地发生，整个批次都因备用推测器的延迟而停滞。这迫使我们在更大的批量大小时选择一个低延迟的推测器，如下面的定理所精确阐述的。

最优回退策略（定理17）。给定两种速度和质量不同的推测器，缓存未命中的最优回退策略是：对于批量大小$b < b^*$，使用慢而精确的推测器作为备用；否则，使用快速推测器。我们在附录A中求解了$b^*$。

4.3.3 经验评估

实验验证批量大小的影响。我们在图6（左）中显示，随着批量大小的增加，使用返回随机令牌的快速备用推测器，其性能优于即时使用一个慢但更准确的神经推测器。我们注意到，对于所有这些批量大小，我们都使用F=1的扇出和1个H100 GPU进行草稿生成。

通过扩展草稿计算来减少延迟。在图6（右）中，我们展示了通过扩展草稿阶段的计算可以进一步减少延迟。具体来说，我们展示了在批量大小为16时，如果我们增加草稿GPU的数量（从而增加扇出因子），我们可以获得的预期加速——这是基于我们的缓存命中率曲线（图4）计算得出的。为推测分配更多的设备可以产生更大的推测缓存，从而带来更高的缓存命中率。


图6：（左）最优的备用推测器（快速 vs 神经）取决于批量大小，正如定理17所预测的（温度为0）。（右）我们预测在批量大小为16时，解码速度如何随着草稿计算（以及扇出）的增加而提高（使用快速备用推测器）。在大的批量大小时，我们受计算限制，需要更多的GPU用于草稿生成以获得加速。

A4 实验结果

端到端评估。在图7中，我们将Saguaro的端到端性能与关键基线进行了比较，包括我们自己实现的普通推测解码，以及最强大的开源推理引擎（vLLM/SGLang）。我们还在开源引擎支持的情况下包含了EAGLE-3。我们的方法相比自回归基线平均获得了近5倍的加速，并且比优化的推测解码基线快了高达两倍，创造了新的技术水平。

吞吐量-延迟帕累托前沿。尽管推测解码算法旨在通过计算换取更低的延迟，但我们在图7（右）中展示了SSD在延迟和吞吐量两个维度上都推动了帕累托前沿，在较小的批量大小时增益最大。这意味着SSD不仅提高了最佳可能的解码速度，而且在每个设备上的计算效率也更高。


图7：（左）在Llama-3.1-Instruct 70B上跨四个数据集的SSD与SD和标准自回归解码的端到端解码速度比较。（右）SSD改进了吞吐量-延迟的帕累托前沿。

Qwen3模型族的附加实验。我们在Qwen3模型系列上重现了与正文相似的趋势，证明我们的结果和算法是模型和数据集无关的。如图10所示，其拒绝率和缓存命中率扩展情况与Llama-3类似，近似呈幂律分布。图11、12、13展示了在Qwen-3 32B上的端到端速度、不同温度下的性能以及批量大小扩展性，均表明SSD优于SD和AR基线。


图10：Qwen-3模型族的拒绝率和缓存命中率扩展。与Llama-3模型族类似，我们看到它与扇出F近似成幂律关系，因此随着我们增加F（缓存的大小），缓存命中率稳定增加。


图11：Qwen-3端到端加速比。


图12：Qwen-3模型族与同步基线的端到端速度比较。


图13：Qwen-3模型与同步基线的批量大小扩展性。

数值结果。下表总结了Llama-3.1和Qwen-3模型在不同数据集上的详细性能数据。

A4 实验环境

  • 硬件配置:

    • 目标模型: 部署在4块NVIDIA H100 80GB GPU上，使用张量并行（TP=4）。
    • 草稿模型 (SSD): 部署在1块独立的NVIDIA H100 GPU上。
    • 连接: 设备间通过NVLink上的NCCL进行通信。
    • 实验均在单个节点上完成。

  • 软件配置:

    • 实现: Saguaro在一个用PyTorch编写的自定义推理引擎中实现。
    • 核心库与技术: 集成了PagedAttention【18, Efficient memory management for large language model serving with pagedattention, 2023, SOSP】, 连续批处理【43, Orca: A distributed serving system for Transformer-Based generative models, 2022, OSDI】, BF16混合精度, torch.compile, 和CUDAGraphs。
    • 基线: 与vLLM (v0.16.0)和SGLang (v0.5.9)进行比较。

  • 模型架构:

    • Llama-3: 目标模型为Llama-3.1-70B-Instruct，草稿模型为Llama-3.2-1B-Instruct。
    • Qwen-3: 目标模型为Qwen3-32B，草稿模型为Qwen3-0.6B。

  • 数据集:

    • 名称: HumanEval, Alpaca, GSM8K, UltraFeedback。
    • 规模及用途: 从每个数据集中抽取128个提示，每个提示生成512个解码令牌。用于评估端到端的解码吞吐量（不包括预填充阶段）。

A5 结论

结论。投机解码通过计算换取延迟，但草稿和验证过程仍然是同步的。本文引入了推测性推测解码（SSD），它甚至将这种顺序依赖关系并行化了。我们推导了性能界限，研究了设计空间的每个组成部分，并将我们的发现提炼成Saguaro，一个优化的SSD算法，它在不同数据集和模型家族中，比优化的推测解码快了高达2倍，比自回归生成快了高达5倍。

局限性。推测解码主要关注降低延迟，对于吞吐量受限的工作负载——如大规模强化学习、离线数据生成——通常效果不佳，因为它给一个已经是计算密集型的过程增加了验证工作量。尽管如此，我们表明SSD能够推动延迟-吞吐量的帕累托前沿，即使考虑到使用的额外硬件，也能在延迟和吞吐量两方面都带来增益。

未来工作。仍有许多开放问题。SSD可以自然地与EAGLE和令牌树推测相结合（附录E）；其联合设计和权衡空间在很大程度上尚未被探索。通过扩展草稿设备的数量从而扩大推测缓存，可以进一步降低延迟，尽管收益最终会递减。最后，在集群级别上跨多个目标模型部署共享推测端点——类似于预填充-解码分离【46, Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving, 2024, OSDI】——是另一个自然的研究方向。

A6 附录

A 理论结果

基本假设。除非另有说明，我们始终假设$T_p < 1$，因此$\max(T_p, 1) = 1$。这是因为SSD通过构造使主推测器（带有自定义注意力掩码的草稿）与验证重叠，从而使其在验证完成前结束。在我们的实现中，推测前瞻长度的选择保证了这一点。我们还假设批次中的不同序列是无关的，因此缓存命中的概率是独立同分布的，为$p_{hit}$。

A.1 定理7证明：建模SSD的加速比

定理7（扩展版）。设主推测器和备用推测器相对于验证器的时间分别为$T_p$和$T_b$。设主推测器生成的预期令牌数为$E_{hit}$，备用推测器生成的预期令牌数为$E_{miss}$。那么，算法1相对于自回归解码的预期加速比为：

$$speedup = \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{p_{\text{hit}} \cdot \max(1, T_p) + (1 - p_{\text{hit}}) \cdot (1 + T_b)}.$$


全局缓存命中率$p_{hit}$可以表示为$p_{hit,p}$和$p_{hit,b}$的函数，分别对应上一轮的推测器是主推测器还是备用推测器（假设$|p_{hit,p} - p_{hit,b}| < 1$）：

$$p_{\text{hit}} = \frac{p_{\text{hit,b}}}{1 + p_{\text{hit,b}} - p_{\text{hit,p}}}.$$

证明第一部分。在SSD的每次迭代中，如果缓存命中，预期生成的令牌数为$E_{hit}$，否则为$E_{miss}$。类似地，如果缓存命中，延迟为$\max(1, T_p)$，否则为$1 + T_b$——这是因为备用推测（耗时$T_b$）仅在验证（我们假设耗时1个单位）完成后才开始。因此，SSD一次迭代的预期生成令牌数和预期延迟（相对于自回归解码）为：

$$\begin{aligned} \begin{aligned} E[\# \text{ Generated tokens}] &= p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}} \\ E[\text{Latency}] &= p_{\text{hit}} \cdot \max(1, T_p) + (1 - p_{\text{hit}}) \cdot (1 + T_b) \end{aligned} \end{aligned}$$


因此，预期加速比为：

$$\begin{aligned} \begin{aligned} speedup &= \frac{E[\# \text{ Generated tokens}]}{E[\text{Latency}]} \\ &= \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{p_{\text{hit}} \cdot \max(1, T_p) + (1 - p_{\text{hit}}) \cdot (1 + T_b)} \end{aligned} \end{aligned}$$

证明第二部分。我们现在证明整体（无条件）缓存命中率$p_{hit}$等于：

$$p_{\text{hit}} = \frac{p_{\text{hit,b}}}{1 + p_{\text{hit,b}} - p_{\text{hit,p}}}.$$


其中$p_{hit,p}$和$p_{hit,b}$是分别以先前迭代由主推测器和备用推测器推测为条件的缓存命中率。推导$p_{hit}$的闭式解的挑战在于，迭代T时的$p_{hit}$取决于前一轮是否有缓存命中。我们首先将$p_{hit}$写成一个递归方程：

$$\begin{aligned} \begin{aligned} p_{\text {hit }}(0) & =p_{\text {hit }, \mathrm{p}}, \quad \text { because we use the primary speculator at } T=0, \\ p_{\text {hit }}(T) & =p_{\text {hit }}(T-1) \cdot p_{\text {hit }, \mathrm{p}}+\left(1-p_{\text {hit }}(T-1)\right) \cdot p_{\text {hit }, \mathrm{b}} \end{aligned} \end{aligned}$$
重新整理并展开这个递归关系：
$$\begin{aligned} \begin{aligned} p_{\text{hit}}(T) &= p_{\text{hit}}(T-1) \cdot (p_{\text{hit,p}} - p_{\text{hit,b}}) + p_{\text{hit,b}} \\ &= p_{\text{hit}}(T-1) \cdot r + p_{\text{hit,b}}, \quad \text{letting } r := p_{\text{hit,p}} - p_{\text{hit,b}} \\ &= \left( p_{\text{hit}}(T-2) \cdot r + p_{\text{hit,b}} \right) \cdot r + p_{\text{hit,b}} \\ &= p_{\text{hit}}(T-2) \cdot r^2 + p_{\text{hit,b}} \cdot r + p_{\text{hit,b}} \\ &= \left( p_{\text{hit}}(T-3) \cdot r + p_{\text{hit,b}} \right) \cdot r^2 + p_{\text{hit,b}} \cdot r + p_{\text{hit,b}} \\ &= p_{\text{hit}}(T-3) \cdot r^3 + p_{\text{hit,b}} \cdot r^2 + p_{\text{hit,b}} \cdot r + p_{\text{hit,b}} \\ &= \dots \\ &= p_{\text{hit}}(0) \cdot r^T + p_{\text{hit,b}} \sum_{t=0}^{T-1} r^t \\ &= p_{\text{hit}}(0) \cdot r^T + p_{\text{hit,b}} \frac{1-r^T}{1-r} \end{aligned} \end{aligned}$$
在$|r| := |p_{hit,p} - p_{hit,b}| < 1$的假设下，第一项收敛于0，第二项收敛于$p_{hit,b} / (1-r) = p_{hit,b} / (1+p_{hit,b}-p_{hit,p})$，这与预期相符。

两个推论的证明。

  • 推论8（严格快于SD）。设$E_{hit} = E_{miss} = E_{SD}$，且$T_p = T_b = T_{SD}$。则SSD的加速比公式变为：

    $$\begin{aligned} \begin{aligned} speedup &= \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{p_{\text{hit}} \cdot \max(1, T_p) + (1 - p_{\text{hit}}) \cdot (1 + T_b)} \\ &= \frac{p_{\text{hit}} \cdot E_{\text{SD}} + (1 - p_{\text{hit}}) \cdot E_{\text{SD}}}{p_{\text{hit}} \cdot \max(1, T_{\text{SD}}) + (1 - p_{\text{hit}}) \cdot (1 + T_{\text{SD}})} \\ &= \frac{E_{\text{SD}}}{p_{\text{hit}} \cdot \max(1, T_{\text{SD}}) + (1 - p_{\text{hit}}) \cdot (1 + T_{\text{SD}})} \end{aligned} \end{aligned}$$


    SD的加速比为$E_{SD}/(1 + T_{SD})$。如果$p_{hit} > 0$且$T_{SD} > 0$，由于$\max(1, T_{SD}) < 1 + T_{SD}$，SSD的加速比严格大于SD。

  • 推论9（加速比上下界）。根据假设，$T_p < 1$且$T_b = 0$。所以SSD的加速比为：
    $$\begin{aligned} \begin{aligned} speedup_{\text{SSD}} &= \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{p_{\text{hit}} \cdot \max(1, T_p) + (1 - p_{\text{hit}}) \cdot (1 + T_b)} \\ &= p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}} \end{aligned} \end{aligned}$$
    SD的加速比为：
    $$speedup_{\text{SD}} = \frac{E_{\text{SD}}}{1+T_{\text{SD}}}.$$
    因此，SSD与SD的加速比之比为：
    $$\frac{speedup_{\text{SSD}}}{speedup_{\text{SD}}} = \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{E_{\text{SD}}/(1 + T_{\text{SD}})}$$
    由于$p_{hit} \le 1$，我们得到上界（假设$E_{hit} \ge E_{miss}$）：
    $$\frac{speedup_{\mathrm{SSD}}}{speedup_{\mathrm{SD}}}=\left(1+T_{\mathrm{SD}}\right) \cdot \frac{E_{\mathrm{hit}}}{E_{\mathrm{SD}}}$$
    由于$E_{miss} \ge 1$（奖励令牌总能生成），我们得到下界：
    $$\begin{aligned} \begin{aligned} \frac{speedup_{\mathrm{SSD}}}{speedup_{\mathrm{SD}}} & = \frac{p_{\text {hit }} \cdot E_{\text {hit }}+\left(1-p_{\text {hit }}\right) \cdot E_{\text {miss }}}{E_{\mathrm{SD}} /\left(1+T_{\mathrm{SD}}\right)} \\ & \geq\left(1+T_{\mathrm{SD}}\right) \cdot \frac{E_{\mathrm{hit}}}{E_{\mathrm{SD}}} \cdot p_{\text {hit }} . \end{aligned} \end{aligned}$$

A.2 定理12证明：优化Saguaro缓存拓扑

定理18（泛化版本）。在约束$\sum_{k=0}^{K} F_k^p \le B$下，最大化Saguaro加速比的$F_k^p$（同样适用于$F_k^b$）值选择为：

$$\sum_{k=0}^{K} F_{k}^{p}=B,$$
$$\frac{\partial p_{\mathrm{hit}, \mathrm{p}}^{k}}{\partial F}\left(F_{k}\right)=a_{p}^{-k} \cdot \frac{\partial p_{\mathrm{hit}, \mathrm{p}}^{0}}{\partial F}\left(F_{0}\right) \quad \forall k<K, \text { and }$$</div>
$$\frac{\partial p_{\mathrm{hit}, \mathrm{p}}^{K, a l l}}{\partial F}\left(F_{K}\right)=\left(1-a_{p}\right) \cdot a_{p}^{-K} \cdot \frac{\partial p_{\mathrm{hit}, \mathrm{p}}^{0}}{\partial F}\left(F_{0}\right) .$$

证明。首先，我们将第3.2节的加速比方程重写，明确其对$F_k^p$和$F_k^b$值的依赖：

$$\begin{aligned} \begin{aligned} speedup\left(\{F_k^p\}_{k=0}^K, \{F_k^b\}_{k=0}^K\right) = \ & p_{\text{hit}}\left(\{F_k^p\}, \{F_k^b\}\right) \cdot E_{\text{hit}} \\ & + \left(1 - p_{\text{hit}}\left(\{F_k^p\}, \{F_k^b\}\right)\right) \cdot E_{\text{miss}}, \quad \text{where} \\ p_{\text{hit}}\left(\{F_k^p\}, \{F_k^b\}\right) = \ & \frac{p_{\text{hit,b}}(\{F_k^b\})}{1 + p_{\text{hit,b}}(\{F_k^b\}) - p_{\text{hit,p}}(\{F_k^p\})}. \end{aligned} \end{aligned}$$


$p_{hit,p}$可以更精确地表示为：

$$p_{\mathrm{hit}, \mathrm{p}}\left(\left\{F_{k}^{p}\right\}\right)=a_{p}^{K} \cdot p_{\mathrm{hit}, \mathrm{p}}^{K, a l l}\left(F_{K}\right)+\sum_{k=0}^{K-1} a_{p}^{k}\left(1-a_{p}\right) \cdot p_{\mathrm{hit}, \mathrm{p}}^{k}\left(F_{k}\right), \quad and$$
由于加速比在$p_{hit}$中单调递增，而$p_{hit}$在$p_{hit,p}$和$p_{hit,b}$中也单调递增，我们只需在约束下最大化$p_{hit,p}(\{F_k^p\})$和$p_{hit,b}(\{F_k^b\})$。
我们使用拉格朗日乘子法解决以下最大化问题：
$$\max_{\sum_{k} F_{k} \leq B} p_{\text{hit,p}}(K, F) = \max_{\sum_{k} F_{k} \leq B} a_{p}^{K} \cdot p_{\text{hit,p}}^{K,all}(F_{K}) + \sum_{k=0}^{K-1} a_{p}^{k}(1 - a_{p}) \cdot p_{\text{hit,p}}^{k}(F_{k})$$
拉格朗日函数为：
$$\mathcal{L}(F_0, \dots, F_k, \lambda) = a_p^K \cdot p_{\text{hit},p}^{K,all}(F_K) + \sum_{k=0}^{K-1} a_p^k(1-a_p) \cdot p_{\text{hit,p}}^k(F_k) + \lambda \cdot \left(\sum_{k=0}^K F_k - B\right)$$
对所有变量求导并令其为零：
$$\begin{aligned} \begin{aligned} \frac{\partial \mathcal{L}}{\partial F_{k}} &= a_{p}^{k}(1-a_{p}) \cdot \frac{\partial}{\partial F_{k}} p_{\mathrm{hit}, \mathrm{p}}^{k}\left(F_{k}\right)+\lambda=0 \quad \text { for } k<K \\ \frac{\partial \mathcal{L}}{\partial F_{K}} &= a_{p}^{K} \frac{\partial}{\partial F_{k}} p_{\mathrm{hit}, \mathrm{p}}^{K, a l l}\left(F_{K}\right)+\lambda=0 \\ \frac{\partial \mathcal{L}}{\partial \lambda} &= \sum_{k=0}^{K} F_{k}-B=0 \end{aligned} \end{aligned}$$</div> 我们注意到所有k的$\partial\mathcal{L}/\partial F_k$都相等（等于$-\lambda$），因此：
$$\begin{aligned} \begin{aligned} (1-a_{p}) \frac{\partial}{\partial F_{k}} p_{\text {hit }, \mathrm{p}}^{0}\left(F_{0}\right) &= a_{p}(1-a_{p}) \frac{\partial}{\partial F_{k}} p_{\text {hit }, \mathrm{p}}^{1}\left(F_{1}\right)=\ldots \\ \ldots &= a_{p}^{K-1}(1-a_{p}) \frac{\partial}{\partial F_{k}} p_{\text {hit }, \mathrm{p}}^{K-1}\left(F_{K-1}\right)=a_{p}^{K} \frac{\partial}{\partial F_{k}} p_{\text {hit }, \mathrm{p}}^{K, a l l}\left(F_{K}\right) \\ \Rightarrow \frac{\partial}{\partial F_{k}} p_{\text {hit }, \mathrm{p}}^{k}\left(F_{k}\right) &= a_{p}^{-k} \frac{\partial}{\partial F_{k}} p_{\text {hit }, \mathrm{p}}^{0}\left(F_{0}\right) \quad \forall k<K, \text { and } \\ \frac{\partial}{\partial F_{k}} p_{\text {hit }, \mathrm{p}}^{K, \text { all }}\left(F_{K}\right) &= (1-a_{p}) a_{p}^{-K} \frac{\partial}{\partial F_{k}} p_{\text {hit }, \mathrm{p}}^{0}\left(F_{0}\right) \end{aligned} \end{aligned}$$</div> 这就得到了期望的结果。

定理12（Saguaro缓存形状：几何扇出）。在约束$\sum_{k=0}^K F_k^p \le B$下，并假设推测器具有接受率$a_p$和r次幂律缓存命中率，Saguaro的最优$F_k^p$值选择遵循几何级数（对于k < K）：

$$\begin{aligned} \begin{aligned} F_k &= F_0 \cdot a_p^{k/(1+r)} \ \forall k < K, \text{ and} \\ F_K &= F_0 \cdot a_p^{K/(1+r)} \cdot (1 - a_p)^{-1/(1+r)}, \end{aligned} \end{aligned}$$

$$F_0 = \frac{B}{a_p^{K/(1+r)} \cdot (1 - a_p)^{-1/(1+r)} + \left(1 - a_p^{K/(1+r)}\right) / \left(1 - a_p^{1/(1+r)}\right)}$$
证明。代入$p^k_{hit,p}(F) = 1 - F^{-r}$（因此$\frac{\partial}{\partial F_k} p^k_{hit,p}(F) = r \cdot F^{-r-1}$），我们得到：
$$\begin{aligned} \begin{aligned} \Rightarrow r \cdot F_{k}^{-r-1} &= a_{p}^{-k} r \cdot F_{0}^{-r-1} \quad \forall k<K, \text { and } \\ r \cdot F_{K}^{-r-1} &= \left(1-a_{p}\right) \cdot a_{p}^{-K} \cdot r \cdot F_{0}^{-r-1} . \\ \Rightarrow F_{k} &= F_{0} \cdot a_{p}^{k /(1+r)} \quad \forall k<K, \text { and } \\ F_{K} &= F_{0}^{(1+r) /(1+r)} \cdot a_{p}^{K /(1+r)} \cdot\left(1-a_{p}\right)^{-1 /(1+r)} \cdot(r / r)^{-1 /(1+r)} . \end{aligned} \end{aligned}$$</div> 将上述值代入预算方程求解$F_0$：
$$B = F_0 \cdot a_p^{K/(1+r)} \cdot (1-a_p)^{-1/(1+r)} + \sum_{k=0}^{K-1} F_0 \cdot a_p^{k/(1+r)}$$
最终得到$F_0$的闭式解。

A.3 定理15证明：优化Saguaro采样算法

定理15。对于扇出F和草稿logits z，Saguaro采样算法的缓存命中率$p_{hit}$随着$C \to 0$而增加。
证明。固定扇出F和草稿logits z。令$S := \text{top}_F(z)$表示F个缓存令牌。Saguaro采样方案导出的草稿分布为$p_C(t)$。可以证明，当$C$增加时，$p_C(t)$在缓存令牌上增加，在缓存外令牌上减少。残差质量$u_C(t) := \max(q(t) - p_C(t), 0)$在缓存令牌上是$C$的非增函数，在缓存外是$C$的非减函数。因此，缓存内总残差质量$\text{in}(C)$是非增的，缓存外总残差质量$\text{out}(C)$是非减的。缓存命中率$p_{hit}(C) = \text{in}(C) / (\text{in}(C) + \text{out}(C))$，由于分子非增而分母中的$\text{out}(C)$非减，所以$p_{hit}(C)$是$C$的非增函数。

构造性证明：Saguaro采样可带来加速（定理19）。存在目标分布$p_t$和草稿分布$p_d$，应用Saguaro采样到$p_d$（使用某个$C \in (0, 1)$）比直接从$p_d$采样能获得严格更快的端到端速度。
证明。我们构造一个4个令牌词汇表上的分布：

$$\begin{aligned} \begin{aligned} p_{t} & :=(0.48,0.48,0.02,0.02), \\ p_{d} & :=(0.49,0.49,0.01,0.01) . \end{aligned} \end{aligned}$$


我们证明，对$p_d$应用$C = 47/147$的Saguaro采样得到$p'_d = (0.47, 0.47, 0.03, 0.03)$。可以计算出，$p_d$和$p'_d$的接受率相同（均为0.98），但$p'_d$的缓存命中率（100%）严格高于$p_d$的缓存命中率（50%）。根据定理7，这意味着$p'_d$能带来更快的端到端速度。

A.4 推论16和定理17证明：优化Saguaro回退策略

推论16。在批量大小为b时，SSD的预期加速比为：

$$speedup = \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{p_{\text{hit}}^b \cdot \max(1, T_p) + (1 - p_{\text{hit}}^b) \cdot (1 + T_b)}, \textit{ which approaches } \frac{p_{\text{hit}} \cdot E_{\text{hit}} + (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}{1 + T_b} \textit{ as } b \to \infty.$$


证明。批次中每个元素的预期生成令牌数是$p_{hit} \cdot E_{hit} + (1 - p_{hit}) \cdot E_{miss}$。然而，批次的延迟取决于是否有任何元素缓存未命中。如果任何一个元素未命中，整个批次的延迟是$1 + T_b$。如果所有元素都命中（概率为$p_{hit}^b$），延迟是$\max(1, T_p)$。由此可推导出上述加速比公式。

定理17。最优缓存未命中策略是，对于批量大小$b < b^*$，使用主推测器作为备用；否则使用快速备用推测器。$b^*$的值为：

$$b^* = \frac{1}{\log(p_{\text{hit}})} \cdot \log\left(\left(1 + \frac{1}{T_p} - \frac{E_{\text{hit}}}{T_p \cdot p_{\text{hit}} \cdot E_{\text{hit}} + T_p \cdot (1 - p_{\text{hit}}) \cdot E_{\text{miss}}}\right)\right)$$


证明。我们分别写出使用慢速备用和快速备用时的加速比表达式。令这两个表达式相等，解出b，即可得到$b^*$的表达式。然后，我们证明慢速备用策略的加速比是b的单调递减函数，而快速备用策略的加速比与b无关。这表明存在一个临界点$b^*$，在该点之前慢速策略更优，之后快速策略更优。

B 实现细节

B.1 系统设计

整体设计。我们使用PyTorch实现了一个自定义推理引擎Saguaro。该实现集成了PagedAttention【18, Efficient memory management for large language model serving with pagedattention, 2023, SOSP】、连续批处理【43, Orca: A distributed serving system for Transformer-Based generative models, 2022, OSDI】、张量并行、BF16混合精度、torch编译和CUDAGraphs。该架构的核心是，目标模型分布在4个设备上，而一个小型草稿模型在独立的设备上运行。两者每轮推测通过NCCL通信一次，目标模型仅发送上一轮的结果（接受的令牌数、采样的奖励令牌），草稿模型用此作为键来查找其预先准备的推测缓存，并在缓存命中时立即返回令牌和logits。关键点是目标模型永远不会看到草稿端的推测缓存，并且设备之间从不传输KV缓存。

实现细节。引擎由主GPU上的协调器进程进行协调。调度器与块管理器一起处理预填充/解码调度和页表簿记。在异步模式下，草稿模型在自己的GPU上以独立进程运行。目标和草稿通过NCCL进行迭代通信。


图8：用于并行解码所有BF(K+1)个验证分支的自定义注意力掩码。此掩码适用于B=1, K=3，均匀扇出F=4，在深度i=2处。黑色表示可以关注的令牌。左侧块显示对已验证前缀的注意力；对角线带显示每个分支仅在其分叉路径内进行关注。

设计决策与性能工程。在草稿推测期间，每个序列的所有F(K+1)个分支都使用一个自定义的稀疏注意力掩码并行解码，该掩码允许每个分支关注已验证的主干及其自身的分叉路径。我们尽可能使用FlashAttention【34, Flashattention-3: Fast and accurate attention with asynchrony and low-precision, 2024, NeurIPS】内核，在需要自定义掩码的多查询解码路径上回退到FlashInfer【44, Flashinfer: Efficient and customizable attention engine for llm inference serving, 2025, https://arxiv.org/abs/2501.01005】。一个掩码示例见图8。生成这些掩码的开销很大，并且自定义掩码注意力内核中的稀疏、非合并内存访问模式是我们的关键路径，限制了草稿步数。因此，大部分端到端加速来自隐藏草稿延迟，而非增加前瞻 。

B.2 实验设计

数据集。我们从每个数据集中选取128个提示，并为每个提示采样512个解码令牌。我们使用普通采样（非top-p或top-k）。我们测量解码吞吐量，不包括预填充。所有实验都在单个NVIDIA H100s节点上完成，但我们一次只使用TP=4（AR，SD）或5（SSD）个GPU。

基线。我们与两个最广泛使用的开源推理引擎进行比较：vLLM（v0.16.0）和SGLang（v0.5.9），涵盖自回归、独立的推测解码和EAGLE-3。所有基线都使用4个H100 80GB GPU进行张量并行，采用贪婪解码。对于推测解码，我们使用Llama-3.2-1B-Instruct作为Llama-3.1-70B-Instruct的草稿模型，Qwen3-0.6B作为Qwen3-32B的草稿模型，每步提出5个草稿令牌。

B.3 数值结果

C SSD 开销

计算。设目标批大小为B，推测前瞻为K，草稿模型猜测验证奖励令牌的（均匀）扇出因子为F。在SSD中，草稿模型每轮解码BK(K+1)F个令牌，而在SD中每轮解码BK个令牌。因此，相对于普通推测解码，草稿模型的FLOPs增加了ˆc(K+1)F倍。与SD用更多FLOPs换取更低延迟一样，SSD用更多的FLOPs换取比SD更低的延迟，这引入了计算和延迟之间新的权衡。

内存。草稿模型必须在异步推测时建立一个推测缓存。这需要存储一个大小为BK(K+1)F的令牌张量，以及每个令牌大小为V的logits，因此推测缓存总共存储O(BFK(K+1)(V+1))比特。在实践中，这大约是几百兆字节，由于现代GPU的HBM要大得多，这不是一个问题。

通信。草稿和目标模型每轮推测同步一次。目标模型发送上一轮推测的结果（O(B)比特信息）。草稿模型发回新推测的令牌及其logits（O(BKV)比特信息）。所有通信都是通过NVLink上的NCCL进行的设备到设备通信，速度足够快，在实践中不是瓶颈。

D 扩展相关工作

互补性工作。SSD与其他通过正交方式加速LLM推理的工作线是互补的，这些工作包括：硬件感知算法如FlashAttention【10, Flashattention: Fast and memory-efficient exact attention with io-awareness, 2022, NeurIPS】，KV缓存管理和分页【18, Efficient memory management for large language model serving with pagedattention, 2023, SOSP】；【47, H2O: heavyhitter oracle for efficient generative inference of large language models, 2023, https://arxiv.org/abs/2306.14048】； 【17, Kvquant: Towards 10 million context length llm inference with kv cache quantization, 2024, NeurIPS】，稀疏或近似注意力【1, Longformer: The long-document transformer, 2020, EMNLP】；【48, Big bird: Transformers for longer sequences, 2020, NeurIPS】，以及多令牌或基于树的草稿方法【2, Medusa: Simple llm inference acceleration framework with multiple decoding heads, 2024, https://arxiv.org/abs/2401.10774】； 【13, Break the sequential dependency of llm inference using lookahead decoding, 2024, ICML】。SSD针对的是一个不同的瓶颈——草稿和验证之间的顺序依赖——并且原则上可以与这些方法中的任何一种结合。

E 将SSD与SD变体结合

与EAGLE-3结合。EAGLE-3【24, Eagle-3: Scaling up inference acceleration of large language models via training-time test, 2025, https://arxiv.org/abs/2503.01840】通过训练草稿模型以在前一轮验证期间提取的目标激活为条件来提高接受率α。这与SSD完全兼容，但有一个细微差别：由于SSD草稿模型预先开始推测第T+1轮，它还没有第T轮的目标激活。因此，草稿模型需要以多达2K个自生成的令牌为条件，这可能会降低后K个令牌的接受率。这可以通过训练EAGLE-3草稿模型在更长的自条件作用期间保持接受率来缓解，如图9所示 。

与Token-Tree方法结合。Token-tree SD方法【28, Specinfer: Accelerating large language model serving with tree-based speculative inference and verification, 2024, ASPLOS】；【6, Sequoia: Scalable and robust speculative decoding, 2024, NeurIPS】；【23, EAGLE-2: faster inference of language models with dynamic draft trees, 2024, EMNLP】；【24, Eagle-3: Scaling up inference acceleration of large language models via training-time test, 2025, https://arxiv.org/abs/2503.01840】可以自然地与SSD结合。SSD为许多可能的验证结果草拟一个线性链。要将SSD与这些token-tree方法结合，只需为每个验证结果预推测（和验证）一个令牌树而不是令牌链。这在实践中需要一个比图8中更复杂的注意力掩码 。


图9：EAGLE-3与SSD-EAGLE-3中激活条件作用的比较。在标准EAGLE-3中（下），第T轮草稿几乎完全以从已验证的第T-1轮提取的目标激活为条件。在SSD-EAGLE-3中（上），第T轮推测在第T-1轮验证完成前开始，因此草稿必须用自己的激活（浅色节点）替代尚未可用的目标激活。如果草稿模型没有经过有效使用草稿自条件的训练，以更多草稿激活为条件可能会降低EAGLE推测的质量。

F 附加实验

Qwen3模型族的附加实验。在这里，我们复现了正文中关于Qwen3模型系列的类似趋势，证明了我们的结果和算法是模型和数据集无关的。


图10：Qwen-3模型族的拒绝率和缓存命中率扩展。与Llama-3模型族类似，我们发现它与扇出F的关系近似为幂律，因此随着我们增大F（即缓存大小），缓存命中率稳定提高。


图11：Qwen3端到端加速。


图12：Qwen-3模型族与同步基线的端到端速度比较。


图13：Qwen-3模型与同步基线的批量大小扩展性。