第12章 投机解码：以小博大

“It is better to be approximately right than precisely wrong.” — Warren Buffett

12.1 自回归枷锁：memory-bound 的根本代价

要理解投机解码为什么能工作，得先理解它在解决什么——LLM Decode 是被内存带宽而不是算力拖慢的。

12.1.1 一次 decode step 的成本结构

低并发 decode 的核心问题是：每一步通常只生成很少的新 token，但仍要走完整模型前向。对大模型来说，权重读取、KV Cache 访问、attention 状态组织、kernel 调度和采样输出都会进入临界路径。具体多少毫秒不能在书里写成常数，因为它随模型大小、dtype、量化方式、GPU 型号、batch、上下文长度、CUDA Graph、FlashAttention 后端和服务端队列状态变化。

更稳妥的拆法是：

成本项	为什么存在	投机解码能否缓解
模型权重读取	每步都要让目标模型计算下一个分布	可以通过一次 verify 覆盖多个候选位置来摊薄
KV Cache 访问	attention 需要历史 K/V	不能消除，只能减少目标模型 step 数
draft 生成	额外 proposer 要先猜 token	会新增成本，收益取决于接受率
拒绝采样	需要保证输出分布仍等价于目标模型	必需成本，不能省
采样与停止处理	每步都要采样、detokenize、检查终止条件	step 数少了会间接受益

因此本章不把某个模型在某张卡上的演示数字写成普遍事实。投机解码的正确判断方式是：在你的模型、你的 prompt 分布、你的并发下，实测 num_draft_tokens、num_accepted_tokens、TTFT、TPOT 和吞吐变化。

12.1.2 Batch 能救一点，但不多

提高 batch size 可以分摊部分目标模型前向成本，但它不是投机解码的替代品。batch 变大后，GPU 利用率更高，单 token 的摊销成本可能下降；同时排队时间、KV 压力、调度预算和请求间长度差异也会上升。低并发在线对话追求的是单请求 TPOT，离线批处理追求的是总 tokens/s，这两个目标不是一回事。

12.1.3 投机解码的直觉：反正要读一遍权重，顺便多验几个 token

核心洞察：既然目标模型一次 verify 可以同时计算多个连续位置的 logits，就让便宜的 proposer 先猜一串候选 token，再让目标模型一次性验证。若前几个候选被接受，就减少了目标模型自回归 step 数；若候选经常被拒绝，draft 和验证的额外工作反而会拖慢系统。

graph TB
    subgraph "传统 Decode (baseline)"
        T1[每步生成 1 token] --> T2[目标模型一次 forward]
        T2 --> T3[产出 1 个 token]
    end

    subgraph "投机解码 k=5"
        S1[Draft 提议 5 个候选] --> S2[大模型 1 次 forward 验证 5 个位置]
        S2 --> S3{接受 n 个}
        S3 -->|接受前缀| S4[本 step 产出多个 token]
        S4 --> S5[目标模型 step 数减少]
        S5 --> S6[TPOT 可能下降]
    end

    style T3 fill:#ef4444,color:#fff,stroke:none
    style S6 fill:#10b981,color:#fff,stroke:none

这就是”以小博大”——用一个廉价的 draft（小模型 / 预测头 / n-gram）产生候选，用大模型一次 forward 并行验证。如果 draft 猜得准，加速立竿见影。

12.2 拒绝采样：为什么投机解码是精确的而不是近似的

一个常见的误解：投机解码是”用小模型近似大模型”。错。投机解码产出的 token 分布与直接用大模型采样完全一致。这是通过一个叫”拒绝采样（Rejection Sampling / Speculative Sampling）“的精妙算法保证的。

12.2.1 算法原理

设大模型的 token 分布为 $p(x)$，草稿模型的分布为 $q(x)$。

对每个候选位置：

1. 草稿阶段：从 $q$ 中采样一个 token $x^* \sim q$
2. 验证阶段：大模型计算 $p(x^*)$
3. 接受/拒绝：
   • 如果 $p(x^*) \geq q(x^*)$（大模型比草稿更看好这个 token），无条件接受
   • 否则，以概率 $\frac{p(x^*)}{q(x^*)}$ 接受
   • 拒绝时，从修正分布 $p'(x) = \frac{\max(0, p(x) - q(x))}{\sum_y \max(0, p(y) - q(y))}$ 中重新采样

12.2.2 数学证明（接受的 token 分布 = $p$）

考虑任一 token $x$ 被最终采纳为输出的概率：

$$\Pr(\text{output} = x) = \underbrace{q(x) \cdot \min\left(1, \frac{p(x)}{q(x)}\right)}_{\text{作为候选被接受}} + \underbrace{(1 - A) \cdot p'(x)}_{\text{上一个被拒后作为重采样}}$$

其中 $A = \sum_y \min(p(y), q(y))$ 是平均接受概率。

化简第一项：$q(x) \cdot \min\left(1, \frac{p(x)}{q(x)}\right) = \min(p(x), q(x))$

化简第二项：

$$(1 - A) \cdot p'(x) = \left(1 - \sum_y \min(p, q)\right) \cdot \frac{\max(0, p(x) - q(x))}{\sum_y \max(0, p(y) - q(y))}$$

注意 $\sum_y \max(0, p(y) - q(y)) = 1 - \sum_y \min(p(y), q(y)) = 1 - A$，所以第二项 = $\max(0, p(x) - q(x))$。

合起来：

$$\Pr(\text{output} = x) = \min(p(x), q(x)) + \max(0, p(x) - q(x))$$

• 如果 $p(x) \geq q(x)$：= $q(x) + (p(x) - q(x)) = p(x)$ ✓
• 如果 $p(x) < q(x)$：= $p(x) + 0 = p(x)$ ✓

两种情况下都等于 $p(x)$。QED.

12.2.3 直觉解释

小模型和大模型的概率分布如果”大致一致”，小模型提议的候选 token 通常会被接受（因为 $p(x) \geq q(x)$ 的概率高）。只有当小模型”错判”（给了一个大模型不看好的 token 高概率），才会被拒绝——被拒绝后从”大模型独有的倾向分布”中重采样，保证整体分布等于大模型。

这个算法最早由 DeepMind 的 Chen et al. (arXiv:2302.01318) 和 Google 的 Leviathan et al. (arXiv:2211.17192) 独立提出，2023 年成为 LLM 推理优化的显学。vLLM 的 V1 spec decode 实现完全忠于这个算法，没有做任何”为了性能而精度打折”的简化。

12.2.4 贪心采样（temperature=0）的退化形式

当 $\text{temperature} = 0$，分布退化为 one-hot（所有概率集中在 argmax token）。拒绝采样变成简单的相等比较：

draft_token == target_token → 接受
draft_token != target_token → 拒绝，用 target 的 argmax

接受率就是”两个模型在当前上下文下恰好选同一个 argmax 的概率”。这种 case 的接受率通常比随机采样更高（因为模型在贪心模式下更确定），但也更依赖模型相似度。

12.3 num_speculative_tokens=k 一次 forward 里发生了什么

弄清楚数学之后，我们看工程——给定 k=5，一次 spec decode step 实际上 GPU 里跑的是什么。

12.3.1 Draft 阶段（5 个并行 step）

如果用 Draft Model（一个独立的小 LLM），5 次自回归 forward：

step-draft-1: input = [last_target_token], output = draft_token_1
step-draft-2: input = [draft_token_1],     output = draft_token_2
step-draft-3: input = [draft_token_2],     output = draft_token_3
step-draft-4: input = [draft_token_3],     output = draft_token_4
step-draft-5: input = [draft_token_4],     output = draft_token_5

小模型 draft 的成本取决于 draft 模型大小、并行度和是否与目标模型共享资源。它不是免费路径，必须把额外显存和额外 forward 纳入压测。

如果用 EAGLE / MTP（共享大模型 hidden state 的预测头），5 次预测头 forward：

hidden_0 (from target) → head(hidden_0) → draft_token_1 + hidden_1
hidden_1 → head(hidden_1) → draft_token_2 + hidden_2
hidden_2 → head(hidden_2) → draft_token_3 + hidden_3
...

EAGLE/MTP 这类预测头通常比完整 draft 模型轻，但具体成本仍取决于实现、模型结构和批大小。不要把某个 benchmark 的数字写成通用结论。

如果用 n-gram，候选来自已有上下文的 token 匹配，不需要额外 GPU 模型；但 CPU 查表、JIT 预热和上下文长度仍会影响开销。

12.3.2 Verify 阶段：大模型一次 forward 5+1 个 token

Verify 阶段把 5 个 draft token 追加到输入序列，调用大模型 forward。大模型会输出6 个位置的 logits：

• 位置 0（last_target_token 之后）：验证 draft_token_1
• 位置 1（draft_token_1 之后）：验证 draft_token_2
• 位置 2（draft_token_2 之后）：验证 draft_token_3
• 位置 3（draft_token_3 之后）：验证 draft_token_4
• 位置 4（draft_token_4 之后）：验证 draft_token_5
• 位置 5（draft_token_5 之后）：总会被用到的 bonus token

第 5 位的 logits 是”如果 draft 全接受，顺便给你生成的下一个 token”。这是 spec decode 的免费午餐——无论前面接受几个，总会多得这 1 个 bonus token。

12.3.3 cu_seqlens 的构造

FlashAttention-3 的 varlen batch（第 11 章）为此优化：

# 假设 batch 里 3 个 decode 请求都做 spec decode with k=5
# 每个请求贡献 6 个 Q 位置（5 draft + 1 bonus）

query_tensor.shape = [3 * 6, num_heads, head_dim] = [18, H, D]
cu_seqlens_q = [0, 6, 12, 18]  # 每请求 6 个 Q

# K/V 方面，每请求的 KV 长度是它的 context + 5 draft
# req_A: context=2000, kv_len=2005
# req_B: context=1500, kv_len=1505
# req_C: context=3000, kv_len=3005
cu_seqlens_k = [0, 2005, 3510, 6515]

Attention mask 有一个 subtle 细节——5 个 draft token 之间要有因果掩码（draft_token_2 能看 draft_token_1，但不能看 draft_token_3-5）。FlashAttention-3 原生支持这种 “causal mask within each q segment” 模式，通过 causal=True 标志启用。

12.3.4 接受 n 个 token 后的状态更新

Verify 返回 6 个位置的 logits 后，拒绝采样逐个检查 5 个 draft token：

if accepted all 5:  next step starts at position + 6 (5 accepted + 1 bonus)
if accepted 3:      next step starts at position + 4 (3 accepted + 1 resampled)
if accepted 0:      next step starts at position + 1 (0 accepted + 1 resampled)

关键是 KV Cache 的处理——draft 阶段我们已经把所有 5 个 token 的 KV 写进 KV Cache 了。如果只接受了 3 个：

• 前 3 个 draft token 的 KV 是正确的（大模型验证通过）
• 第 4 个位置：draft 被拒，从大模型重采样出一个新 token；这个新 token 的 KV 已经在 Verify 阶段被大模型算好了（position=3 位置输出的 logits 就用了正确的前缀）
• 第 5 个 draft token 的 KV 需要废弃 — 因为它是基于错误的 draft_4 算的

V1 的 KVCacheManager 会”逻辑上”rollback 被拒部分的 KV——把 num_computed_tokens 回退到正确位置。由于 KV 是 block 级的，如果被拒的 token 恰好跨过 block 边界，可能整个 block 的部分内容需要重写。

12.3.5 当前 V1 主路径怎么串起来

把上面的概念落到本地源码，V1 主路径可以按四段读。

第一段是初始化。gpu_model_runner.py 在构造时检查 self.speculative_config。如果存在配置，就把 use_spec_decode 设为 True；最后一个 pipeline rank 上，method == "ngram" 创建 NgramProposer，use_eagle() 创建 EagleProposer，并创建 RejectionSampler。这就是为什么 §12.4 反复强调：当前 V1 直接接入的是 n-gram 与 EAGLE/EAGLE3，而不是配置层认识的所有 speculative method。

第二段是生成 draft。generate_draft_token_ids() 会逐请求检查几个跳过条件：本轮没有 sampled token 就跳过；请求的采样参数不支持 spec decode 就跳过；追加 sampled token 后已经到 max_model_len 就跳过；proposer 返回 None 或空结果也跳过。最终返回的是 list[list[int]]，也就是每个请求各自的 draft token 列表。这个设计允许同一个 batch 里有些请求使用 spec，有些请求不使用 spec。

第三段是把 ragged draft 列表变成张量。SpecDecodeMetadata.from_lists() 会把二维 list 展平成 draft_token_ids_tensor，同时记录每个请求的 num_draft_tokens 和前缀和 cu_num_draft_tokens。这和第 11 章 chunked prefill 讨论的 varlen 元数据思想一致：真正麻烦的不是 token 值，而是每个请求 draft 长度不同。

第四段是接受/拒绝。目标模型 forward 后，rejection_sampler.py 根据 target logits、draft token、采样参数和 draft 概率做接受判断。它还要处理贪心退化路径、top-k/top-p 约束、seed 随机数、按位置接受统计等细节。因此 V1 里最大的 spec decode 相关单文件不是 proposer，而是 vllm/v1/sample/rejection_sampler.py。

12.4 Proposer 谱系：V1 主路径与广义方法

当前本地源码里，V1 worker 直接初始化的 proposer 只有两类：NgramProposer 和 EagleProposer。gpu_model_runner.py:169-181 的逻辑很明确：method == "ngram" 创建 NgramProposer；use_eagle() 创建 EagleProposer；其他方法在 V1 路径会报 unknown method。更广的 vLLM 代码仍保留 V0 vllm/spec_decode/、draft model、Medusa、MLP speculator，以及 model executor 里的 deepseek_mtp.py 等文件，所以读源码时要区分”配置层认识的 method”、“V0 遗留 worker”和”V1 当前主路径”。

graph TB
    Prop[Spec Decode Proposer]
    Prop --> NG["n-gram<br/>V1 直接支持"]
    Prop --> EG["EAGLE / EAGLE3<br/>V1 直接支持"]
    Prop --> DM["Draft Model<br/>配置层/V0 路径相关"]
    Prop --> MTP["MTP / Medusa / MLP<br/>模型文件或 V0 路径相关"]

    NG --> NGD["从上下文匹配候选<br/>收益依赖重复性"]
    EG --> EGD["使用 EAGLE draft 模型<br/>需要对应权重与配置"]
    DM --> DMD["独立小模型 draft<br/>额外显存与 forward 成本"]
    MTP --> MTPD["模型原生或专门头<br/>是否可用取决于当前路径"]

    style NG fill:#f59e0b,color:#fff,stroke:none
    style EG fill:#10b981,color:#fff,stroke:none
    style DM fill:#3b82f6,color:#fff,stroke:none
    style MTP fill:#8b5cf6,color:#fff,stroke:none

12.4.1 Draft Model

最经典的形态——用一个小得多的同系列模型做 draft。例如 Llama-3-8B-Instruct 给 Llama-3-70B-Instruct 做 draft。

# vllm/v1/spec_decode/draft_model_proposer.py（概念性）
class DraftModelProposer:
    def __init__(self, draft_model_config, ...):
        # 加载 draft 模型到 GPU（占一部分显存）
        self.draft_runner = GPUModelRunner(draft_model_config, ...)

    def propose(self, target_ids, num_speculative_tokens, ...):
        # 自回归跑 k 步 draft
        draft_ids = []
        current_input = target_ids[-1:]
        for _ in range(num_speculative_tokens):
            logits = self.draft_runner.forward(current_input, past_kv=...)
            draft_token = sample(logits, temperature=draft_temp)
            draft_ids.append(draft_token)
            current_input = draft_token.unsqueeze(0)
        return draft_ids

优点：

• 接受率最高（同系列模型训练数据、tokenizer、架构一致）
• 草稿质量可控（可以用 draft_temperature 单独调小模型的随机性）
• 现成的 checkpoint 可直接用（Llama-3 系列的 1B/8B/70B 都有）

缺点：

• 显存占用和加载时间取决于 draft 模型大小、dtype、量化方式和并行度
• 每个 draft step 都是额外计算，不能只看目标模型 verify 的收益
• 长序列 draft 时，小模型自己也要做 KV Cache 管理

12.4.2 EAGLE / EAGLE3

EAGLE (arXiv:2401.15077) 的洞察：大模型最后一层的 hidden state 已经包含了”下一个 token 应该是什么”的几乎所有信息。只需要一个超轻量的”预测头”就能从 hidden state 里解码出后续 token。

# vllm/v1/spec_decode/eagle.py（概念性）
class EagleProposer:
    def __init__(self, eagle_head_config, target_model, ...):
        self.eagle_head = load_eagle_head(eagle_head_config)  # 1-2 层 Transformer
        # 共享 target 模型的 hidden states，不需要独立跑大模型

    def propose(self, target_hidden_states, target_token_ids, ...):
        # 从 target 最后一层 hidden 出发，跑 k 步 eagle head
        hidden = target_hidden_states[-1:]
        draft_ids = []
        for _ in range(num_speculative_tokens):
            # eagle_head 是个小 transformer，输入 hidden + last_token
            next_hidden, next_logits = self.eagle_head(hidden, ...)
            next_token = sample(next_logits)
            draft_ids.append(next_token)
            hidden = next_hidden
        return draft_ids

EAGLE3 在 EAGLE 基础上改变了 draft 模型结构，vLLM V1 会在 method == "eagle3" 时打开 use_aux_hidden_state_outputs。接受率和收益必须按具体 EAGLE 权重、目标模型和任务压测，不能只靠方法名判断。

优点：

• 相比完整 draft 模型，EAGLE 路径通常更轻
• V1 主路径有明确的 EagleProposer 实现
• 不需要额外的 tokenizer / config（复用 target 的一切）

缺点：

• 需要针对特定 target 模型预训练 EAGLE head——不是所有模型都有现成 checkpoint
• 需要和目标模型匹配的 EAGLE/EAGLE3 权重；跨模型乱配会直接伤接受率

12.4.3 MTP (Multi-Token Prediction)

DeepSeek-V3 引入的架构创新——模型本身就内置了多 token 预测头，训练时就按 “预测 next-4-tokens” 的目标训练。使用时：

# DeepSeek-V3 / V3.1 风格
def propose_mtp(target_output):
    # MTP heads 是模型的一部分，训练时已对齐
    for i in range(num_mtp_heads):
        draft_token_i = target_output.mtp_heads[i].logits.argmax()
    return draft_tokens

优点：

• 预测头和主模型是同一模型设计的一部分，理论上比外接小模型更容易对齐
• 不需要另选一个独立 draft checkpoint

缺点：

• 只有原生支持 MTP 的模型能用
• 不能跨模型适配（不像 Draft Model 那样你可以自选一对模型）

当前本地源码里可以看到 vllm/model_executor/models/deepseek_mtp.py，但 V1 GPUModelRunner 的 drafter 初始化分支只直接接受 n-gram 和 EAGLE/EAGLE3。阅读时不要把”模型文件存在”等同于”V1 spec decode proposer 已把它作为独立方法启用”。

12.4.4 n-gram

最简单但在对的场景下惊人有效。原理：在已生成的上下文里找重复模式。

打开 vllm/v1/spec_decode/ngram_proposer.py，实现不是朴素的嵌套循环——而是 KMP（Knuth-Morris-Pratt）字符串匹配 + Numba JIT。131 行代码完整实现了线性时间模式匹配：

# vllm/v1/spec_decode/ngram_proposer.py:10
class NgramProposer:
    def __init__(self, vllm_config):
        self.min_n = vllm_config.speculative_config.prompt_lookup_min
        self.max_n = vllm_config.speculative_config.prompt_lookup_max
        self.k = vllm_config.speculative_config.num_speculative_tokens

        # Trigger Numba JIT compilation for N-gram proposer.
        # This usually takes less than 1 second.
        self.propose(np.zeros(1024, dtype=np.int32))   # ← 构造时预热

    def propose(self, context_token_ids):
        k = min(self.k, self.max_model_len - context_token_ids.shape[0])
        if k <= 0:
            return None
        for n in range(self.max_n, self.min_n - 1, -1):    # 先试长 n-gram
            result = _find_subarray_kmp(context_token_ids, n, k)
            if result is not None:
                return result
        return None

@jit(nopython=True)
def _kmp_lps_array(pattern):
    """Build the lps (longest proper prefix which is also suffix) array."""
    lps = np.zeros(len(pattern), dtype=np.int32)
    prev_lps = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[prev_lps]:
            prev_lps += 1
            lps[i] = prev_lps
            i += 1
        else:
            if prev_lps != 0:
                prev_lps = lps[prev_lps - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

@jit(nopython=True)
def _find_subarray_kmp(context_token_ids, n, k):
    pattern = context_token_ids[-n:]        # 末尾 n 个 token 做 pattern
    lps = _kmp_lps_array(pattern)
    i, j = 0, 0
    while i < context_token_ids.shape[0] - n:
        if context_token_ids[i] == pattern[j]:
            i += 1; j += 1
            if j == n:
                return context_token_ids[i:i + k]   # 返回匹配后的 k 个 token
        else:
            if j != 0:
                j = lps[j - 1]              # KMP 的精髓：跳过已匹配前缀
            else:
                i += 1
    return None

四个真实实现细节值得展开——它们决定了这个模块能不能在生产流量下真的省出延迟：

1. KMP 而不是朴素 O(N·M) 搜索。对 4K context、max_n=8 的 pattern，朴素搜索是 32K 次比较；KMP 通过 lps 数组记住”已匹配前缀里有多少能当作新起点”，全程 O(N+M) — 约 4K 次。看起来小，但 decode 每一步都跑、累积放大。KMP 在 LLM 场景的 pattern 长度较小（<=8），lps 数组也只有 8 元素——实际性能差距主要来自”命中时不退回重扫”。

2. Numba JIT @jit(nopython=True) 的 nopython 模式是关键——nopython=True 强制 Numba 生成不调用 Python C API 的机器码。没这个参数可能退化到 object-mode，循环仍会受 Python 解释器影响。源码选择 JIT，是因为 n-gram proposer 可能在每个 decode 步都运行。

3. 构造时预热（self.propose(np.zeros(1024, dtype=np.int32))）——Numba JIT 首次调用需要编译。源码在 __init__ 里主动跑一次 propose，目的就是把首次编译成本从第一条真实请求上移走。

4. 长 n-gram 优先回退（line 62 range(self.max_n, self.min_n - 1, -1)）——先试 max_n=8 的模式匹配，没找到降到 min_n=2。理由：长模式匹配成功的信号更强（8 个连续 token 重复几乎确定是模板化输出），短模式命中多但假阳性也多。先试长的能让”真正的高接受率命中”优先返回——绕过短 pattern 的干扰。

示例直接来自源码 docstring（line 46-54）：

context_token_ids = [1,2,3,4,2,3], min_n=2, max_n=3, k=4
- 最后 3 个 token [4,2,3] 找不到匹配
- 最后 2 个 token [2,3] 在前 4 个 [1,2,3,4] 里找到
- 返回 [2,3] 之后的 token，共 3 个（因为 context 只剩这么多）

注意返回的可以短于 k——源码注释明示”如果匹配后剩余 token 不足 k 个，返回全部剩余”。这种”尽力而为”语义对调度器是友好的——总比返回 None 让 proposer 失效要强。

场景契合度：代码生成、模板化摘要、长文改写里更容易出现重复片段，n-gram 更可能命中；开放聊天和创意写作的后续分布更分散，n-gram 可能经常返回 None 或低质量候选。这也是为什么 n-gram 是”低额外成本但场景敏感”的选项。

典型场景是代码生成：

# 已生成的 context
"def foo(a, b): return a + b\ndef bar(x, y): return x + "
# 末尾 "return x + " 没有完全匹配，但 "return " 之前出现过
# 查表找到 "return a + b\n" 这个模式，猜测后续是 "y\n"
# 大多数情况会被验证通过

优点：

• 零 GPU 开销（纯 CPU + Numba JIT）
• 零显存占用
• 实现简单，几十行代码
• 在高重复性任务上更可能命中有用候选

缺点：

• 创意写作、开放对话等场景命中率和接受率通常更不稳定
• 依赖 context 长度（越长找到匹配概率越高）

12.4.5 选择建议

graph LR
    Q[选 Proposer?] --> A{任务类型}
    A -->|代码 / 翻译 / 摘要| NG[n-gram<br/>零成本，常有惊喜]
    A -->|对话 / 通用| B{target 模型}
    B -->|DeepSeek-V3/R1| MTP[MTP<br/>原生内置，最强]
    B -->|其他| C{VRAM 宽裕?}
    C -->|有| DM[Draft Model<br/>最高接受率]
    C -->|紧张| EG[EAGLE<br/>轻量折中]

    style NG fill:#f59e0b,color:#fff,stroke:none
    style MTP fill:#8b5cf6,color:#fff,stroke:none
    style DM fill:#3b82f6,color:#fff,stroke:none
    style EG fill:#10b981,color:#fff,stroke:none

12.5 加速比的闭式公式

推一下 spec decode 的理论加速比。

12.5.1 接受率与期望接受长度

设每个位置被接受的独立概率为 $\alpha$（接受率），num_speculative_tokens=k。期望接受的 token 数：

$$E[\text{accepted}] = \sum_{i=0}^{k-1} \alpha^i \cdot (1 - \alpha) \cdot i + \alpha^k \cdot k = \frac{1 - \alpha^{k+1}}{1 - \alpha} - 1$$

加上那 1 个 bonus token，每 step 净产出：

$$E[\text{tokens per step}] = \frac{1 - \alpha^{k+1}}{1 - \alpha}$$

12.5.2 时间成本

设 verify 一次 forward 的时间为 $T_v$，draft 的相对开销为 $c = T_d / T_v$。这里的 $c$ 必须来自压测，不能按 proposer 名字固定。完整 draft model、EAGLE、n-gram 在不同模型和不同 batch 下的 $c$ 都会变。

每 step 总时间：

$$T_{\text{step}} = T_v \cdot (1 + c \cdot k)$$

12.5.3 加速比

原始 decode 每 step 产出 1 token，时间 $T_v$（简化：忽略 verify 比原 decode 稍多的那一点）。所以：

$$\text{speedup} = \frac{E[\text{tokens per step}]}{T_{\text{step}} / T_v} = \frac{1 - \alpha^{k+1}}{(1 - \alpha)(1 + c \cdot k)}$$

12.5.4 数值计算

下面这张表是代入公式的假设值示例，不是 vLLM 官方 benchmark，也不是本书实测。它的用途是展示 $\alpha$ 和 $c$ 如何影响最优 k：

假设场景	α	c	k=3	k=5	k=7	观察
高接受率、低 draft 成本	0.75	0.05	2.63×	3.20×	3.53×	k 增大仍有收益
中等接受率、中等成本	0.55	0.20	1.74×	1.79×	1.73×	很快进入平台期
低接受率、低成本	0.25	0.00	1.33×	1.33×	1.33×	接受率本身限制收益
高接受率、高成本	0.75	0.40	1.66×	1.84×	1.94×	draft 成本吃掉收益

几个洞察：

• 高 $\alpha$ 时，k 越大越好（MTP 可以把 k 拉到 10+）
• 低 $\alpha$ 时，k 存在饱和点（跨系列 Draft Model 过 k=5 后收益递减）
• $c$ 决定了”最优 k”的位置——$c$ 越小，最优 k 越大

实际生产中不要按表抄 k。正确流程是固定目标模型和流量，扫描 num_speculative_tokens，同时看接受率、TPOT、TTFT、总吞吐、KV 占用和错误率。只要 k 增大后接受率下降、draft 成本上升或队列变长，就应该停在更小的 k。

12.6 为什么”batch 大了投机解码反而变慢”

这是一个经常让工程师困惑的现象。原因是高并发下三个变化：

12.6.1 Draft cost 不再可忽略

低并发下目标模型 step 数少是主要矛盾，draft 的额外工作可能被收益覆盖；高并发下 GPU、KV 和调度预算更紧，draft 的额外 forward、额外 token 位置和拒绝后的浪费都更明显。是否变慢取决于实际 batch，而不是某个固定阈值。

12.6.2 Verify 的 k 倍 Q 占用 budget

一个 running 请求 decode 时 num_scheduled_tokens=1；开了 spec=5 后变成 6。如果 max_num_batched_tokens=4096，原本能塞 4000 个 decode 请求的 step，现在只能塞 650 个。

换句话说，spec decode 把 budget 消费放大了 k 倍。在中高并发下，这个放大效应让 batch 压不下来，吞吐反而降。

12.6.3 拒绝采样的部分浪费

被拒绝的 draft token 会带来无效验证工作。接受率越低，浪费越大；k 越大，单步可能浪费的位置也越多。这部分成本在高并发场景会更容易暴露。

12.6.4 经验法则

当前本地 SamplingParams 没有 use_spec_decode 字段；投机解码是 engine 级 --speculative-config / SpeculativeConfig 能力。配置层有 disable_by_batch_size，语义是当排队请求数超过阈值时，对新进请求禁用 speculative decoding。也就是说，“按负载动态收缩”是配置层能力，不是每个请求随手传一个 SamplingParams(use_spec_decode=False)。

12.7 生产配置模板与调优

12.7.1 单用户对话（低并发，追求 TPOT）

vllm serve meta-llama/Llama-3-70B-Instruct \
    --speculative-model meta-llama/Llama-3-8B-Instruct \
    --num-speculative-tokens 5 \
    --speculative-draft-tensor-parallel-size 1 \
    --max-num-seqs 16 \
    --gpu-memory-utilization 0.92

这类配置的目标是降低低并发 TPOT，但收益和显存占用必须用目标模型实测；不要把示例命令理解成固定 2 倍收益。

12.7.2 DeepSeek-V3 启用 MTP

vllm serve deepseek-ai/DeepSeek-V3 \
    --speculative-config '{"method": "deepseek_mtp", "num_speculative_tokens": 3}' \
    --max-num-seqs 64

DeepSeek MTP 属于模型原生多 token 预测路线。当前本地源码有 deepseek_mtp.py 模型实现；是否能作为你的在线服务 spec decode 路径启用，要以当前 vLLM 版本、V0/V1 路径和配置校验结果为准。

12.7.3 代码生成工作流（n-gram）

vllm serve meta-llama/Llama-3-70B-Instruct \
    --speculative-config '{"method": "ngram", "num_speculative_tokens": 5, "prompt_lookup_min": 3, "prompt_lookup_max": 8}' \
    --max-num-seqs 32

n-gram 不加载额外 GPU 模型，适合先用低额外成本验证重复性任务有没有收益。代码场景经常值得试，但接受率和提速仍要用 spec_decode_* 指标验证。

12.7.4 调优关键指标

vLLM 暴露 spec decode 的专用 Prometheus 指标：

vllm:spec_decode_num_accepted_tokens_total   # 累计接受 token 数
vllm:spec_decode_num_draft_tokens_total      # 累计 draft token 数
vllm:spec_decode_num_emitted_tokens_total    # 累计 emit token 数

计算实时接受率：$\alpha = \frac{\text{accepted}}{\text{draft}}$。如果接受率长期偏低、TPOT 没降反升或队列变长，就考虑降 k、换 proposer、调低并发下才启用，或直接关闭 spec decode。

12.8 投机解码的未来

Spec Decode 这个方向从 2022 年以来持续演进。可以关注的方向包括：

• 模型协同设计——像 MTP 这样”训练时就考虑 spec”的模型会越来越多
• Tree-based 投机——一次 draft 多个分支（tree），验证时挑最好的那支；已在 EAGLE2 / Medusa-2 中实现
• 层次化投机——draft 嵌套 draft（小小模型 + 小模型 + 大模型），像 CPU cache 的 L1/L2/L3
• 跨请求共享 draft——同 prompt 前缀的多个请求共用同一段 draft
• 硬件协同——draft 上 CPU / NPU 异构加速，verify 上 GPU

vLLM 的配置层和模型实现层保留了多种 speculative decoding 路线，但能否进入 V1 主路径，要看 GPUModelRunner、SpeculativeConfig 校验和对应 proposer 是否已接好。读新 PR 时优先看三处：config.py 是否识别 method，gpu_model_runner.py 是否初始化 proposer，vllm/v1/sample/rejection_sampler.py 是否支持对应接受逻辑。

12.8.1 V1 vs V0 投机解码模块的真实尺寸：从 4320 行简化到 692 行

vLLM 在 V1 重写了整个投机解码子系统、规模缩减 6.25 倍——

模块	文件数	行	备注
V1 vllm/v1/spec_decode/	6	692	eagle.py 318 + metrics.py 164 + ngram_proposer.py 131 + metadata.py 61 + utils.py 18 + __init__.py 0
V0 vllm/spec_decode/	9	4320	spec_decode_worker.py 1324 + batch_expansion.py 505 + multi_step_worker.py 416 + 其余 6 个 worker / proposer 文件
拒绝采样（V1 在 sample/）	1	631	vllm/v1/sample/rejection_sampler.py——本章 §12.2 算法的实际实现
模型实现 model_executor/models/	6	1312	eagle 247 / deepseek_mtp 266 / llama_eagle3 232 / medusa 210 / mlp_speculator 205 / llama_eagle 152

V1 目录规模更小的三条根因——

1. 没有独立的 worker 类——V0 有 SpecDecodeWorker（1324 行）+ MultiStepWorker（416）+ BatchExpansionTop1Scorer（505）三套专门的 worker 实现；V1 把投机解码变成 GPUModelRunner.execute_model 主循环里的一段分支——proposer 跑完直接拼到主 forward 的 batch 里、不需要单独的执行器
2. 没有独立 BatchExpansion 文件——V0 的 batch_expansion.py 505 行专门处理”如何把 k 个 draft token 展开成 verifier 的 input”；V1 把 draft token、num_draft_tokens、cu_num_draft_tokens 等信息放进 SpecDecodeMetadata，再交给主 runner 组织 target forward
3. 没有 proposer 间的通用基类——V0 的 proposer_worker_base.py（58 行）+ top1_proposer.py（274 行）是为了让 ngram / draft model / MLP speculator / EAGLE 走统一的 sample_proposals 接口；V1 的 4 种 proposer 直接各写各的 propose() 方法——共享的只有 SpecDecodeMetadata 这个 61 行的 dataclass——鸭子类型替代继承

rejection_sampler.py 631 行是 §12.2 算法的核心——是整个 V1 spec_decode 子系统最大的单文件（比 eagle.py 318 还大近 1 倍）——因为拒绝采样本身要处理 (a) 贪心退化路径（temperature=0）；(b) 概率分布的 KL 重采样；(c) k 个 draft token 的 batched 接受/拒绝决策；(d) 失败时从修正分布 $p - q$ 重新采样——算法层面就比 4 种 proposer 加起来都重。

注意 metrics.py 在 spec_decode/ 而不是 v1/metrics/——这是因为 spec decode 指标和算法状态强耦合：草稿次数、草稿 token 数、接受 token 数、按位置接受矩阵，都来自 spec decode 自己的统计对象。放在同目录里，改 proposer 或接受逻辑时更容易同步更新指标。

12.9 本章小结

投机解码是打破 LLM decode memory-bound 枷锁的关键武器：

• 动因：低并发 decode 容易受 memory-bound 和 step-by-step 自回归限制；一次 verify 覆盖多个候选位置可以减少目标模型 step 数
• 数学等价：拒绝采样证明输出分布 = 原始大模型 decode，不是近似，是精确
• 一次 forward 内部：k+1 个 Q 位置、varlen cu_seqlens、causal mask within draft span
• Proposer 谱系：当前 V1 主路径直接支持 n-gram 与 EAGLE/EAGLE3；draft model、MTP、Medusa、MLP speculator 要区分 V0 路径、模型文件和配置层能力
• 加速比闭式公式：$\frac{1-\alpha^{k+1}}{(1-\alpha)(1+c \cdot k)}$，用来理解接受率和 draft 成本如何影响收益
• 反直觉现象：并发升高后，draft 成本、预算放大和拒绝浪费可能让 spec decode 变慢
• 实战配置：--speculative-config 是 engine 级能力，是否启用和 k 值必须靠指标压测决定

物理事实：当前本地 vllm/v1/spec_decode/ 只有 6 个 Python 文件、692 行；V0 vllm/spec_decode/ 有 16 个 Python 文件、4320 行；vllm/v1/sample/rejection_sampler.py 单独 631 行，是本章 §12.2 算法的主要实现位置。

---

源码导航（实测 vllm 仓库当前布局）

• V1 投机解码主目录：vllm/v1/spec_decode/（6 文件 692 行）—— eagle.py 318 / metrics.py 164 / ngram_proposer.py 131 / metadata.py 61 / utils.py 18 / __init__.py 0
• 没有独立 interface.py / draft_model_proposer.py / deepseek_mtp.py——proposer 公共接口隐式表达在 metadata.py 的 SpecDecodeMetadata dataclass + 各 proposer 实现的 propose() 方法上
• 拒绝采样：vllm/v1/sample/rejection_sampler.py（631 行——本章核心算法主体在这里、几乎是 spec_decode/ 全部 6 文件之和）
• 模型实现（在 model_executor/models/）：eagle.py 247 / llama_eagle.py 152 / llama_eagle3.py 232 / medusa.py 210 / deepseek_mtp.py 266 / mlp_speculator.py 205——6 文件 1312 行
• V0 遗留 vllm/spec_decode/ 4320 行（spec_decode_worker.py 1324 / batch_expansion.py 505）——理解 V1 简化幅度的对比基准
• Metrics：vllm/v1/spec_decode/metrics.py（不在 v1/metrics/）

论文

• Leviathan et al., “Fast Inference from Transformers via Speculative Decoding”, ICML 2023 (arXiv:2211.17192)
• Chen et al., “Accelerating Large Language Model Decoding with Speculative Sampling”, 2023 (arXiv:2302.01318)
• Cai et al., “Medusa: Simple LLM Inference Acceleration Framework”, 2024 (arXiv:2401.10774)
• Li et al., “EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty”, ICML 2024 (arXiv:2401.15077)
• DeepSeek-AI, “DeepSeek-V3 Technical Report”, 2024 (arXiv:2412.19437) — MTP section