推测解码：草稿、验证与实际加速

生成一段长回答时，目标模型通常每确定一个 token，就要再运行一次，才能知道下一个 token 的概率。推测解码先用便宜的计算提出一串候选，再让目标模型并行验证。一次验证可能提交多个 token，摊薄昂贵的串行步骤；Leviathan 等人的原始论文给出了保持目标采样分布的算法。

先理解自回归生成中的前缀依赖，以及推理性能中的 prefill、decode 和吞吐边界。这篇笔记关注怎样减少 decode 的目标模型调用，以及何时能把减少的调用变成实际节省的时间。

候选已知，验证才能并行

普通生成的难点在于：选择第二个 token 需要第一个 token，选择第三个又需要前两个。KV cache 保存已有前缀的状态，目标模型仍要处理新增位置。

设已经提交的前缀为 $h$，草稿模型连续提出 $x_1,x_2,x_3$。此时所有候选前缀都已知，目标可以在一轮因果前向计算中得到：

$$\begin{aligned} p_1&=p(\cdot\mid h),\\ p_2&=p(\cdot\mid h,x_1),\\ p_3&=p(\cdot\mid h,x_1,x_2),\\ p_4&=p(\cdot\mid h,x_1,x_2,x_3). \end{aligned}$$

用 $p_1$ 验证 $x_1$，用 $p_2$ 验证 $x_2$，依此类推，注意 logits 与候选位置的偏移。若前三个都接受，再从 $p_4$ 采样一个额外 token。若第二个被拒绝，只保留第一个，并在第二个位置补一个校正 token；原来的第三个及其验证结果作废，因为它们依赖被拒绝的前缀。EOS 或输出长度限制可以提前结束这一轮。

并行发生在目标验证阶段；线性草稿本身仍可能逐个生成候选。验证更多位置会增加计算量，收益取决于能否摊薄权重和历史状态的读取成本。

接受与拒绝怎样保住分布

原论文第 2.3 节与附录 A.1的规则适用于归一化的目标分布 $p$ 和实际用于提出候选的分布 $q$，两者对应相同前缀、同一组 token 标识。这里的 $p$ 已包含目标的 temperature、top-k、top-p 等采样处理，$q$ 也必须对应草稿实际采用的处理。

对从 $q$ 采样的候选 $x$，以如下概率接受：

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

候选来自 $q$，因此被提出的 token 有 $q(x)>0$。第一次拒绝后，从剩余概率质量中采样替代 token：

$$r(x)=\frac{\max(0,p(x)-q(x))}{\sum_y\max(0,p(y)-q(y))}.$$

若 $p=q$，所有候选都接受，不会进入分母为零的校正分支。逐个前缀正确执行这套规则，输出序列就保持目标分布。直接拒绝低概率 token 后重新从 $p$ 抽样，通常会改变分布。

算完三个 token 的全部概率

构造一个只有 A、B、C 的例子：$p=(0.5,0.3,0.2)$，$q=(0.6,0.1,0.3)$。接受概率分别为 $5/6,1,2/3$。乘上提议概率后，直接接受的质量是 $(0.5,0.1,0.2)$，总接受率为 $0.8$。剩余 $0.2$ 全补给 B，最终仍是 $(0.5,0.3,0.2)$。

以下 Python 3 代码用精确分数检查概率，再用固定候选和固定抽样值重放一轮验证。这里的 $p$、$q$ 是同一有限词表上的归一化分布，候选的 $q(x)>0$，抽样值位于 $[0,1)$。为便于计算，玩具分布在每个前缀下都相同；真实模型的分布会随前缀改变。首次拒绝时从校正分布抽样，全部接受时从 $p$ 抽样额外 token；$p=q$ 时不计算校正分布。默认输入会在 C 处拒绝，并以概率 1 补上 B。

from fractions import Fraction as F

tokens = ['A', 'B', 'C']
p = dict(zip(tokens, map(F, ['0.5', '0.3', '0.2'])))
q = dict(zip(tokens, map(F, ['0.6', '0.1', '0.3'])))
accepted = {x: min(p[x], q[x]) for x in tokens}
alpha = sum(accepted.values())
if alpha < 1:
    residual = {x: max(p[x] - q[x], 0) / (1 - alpha) for x in tokens}
    restored = {x: accepted[x] + (1 - alpha) * residual[x] for x in tokens}
else:
    residual = None
    restored = accepted
assert restored == p
print('accepted mass:', [float(accepted[x]) for x in tokens])
print('acceptance:', float(alpha))
print('residual:', None if residual is None else [float(residual[x]) for x in tokens])
print('reconstructed:', [float(restored[x]) for x in tokens])

def sample(distribution, u):
    assert 0 <= u < 1
    cumulative = F(0)
    for x in tokens:
        cumulative += distribution[x]
        if u < cumulative:
            return x
    raise ValueError('distribution must sum to 1')

draft = ['A', 'C', 'B']
draws = list(map(F, ['0.7', '0.9', '0.2']))
final_draw = F('0.2')
assert len(draft) == len(draws)
emitted = []
for i, (x, u) in enumerate(zip(draft, draws)):
    assert q[x] > 0 and 0 <= u < 1
    threshold = min(F(1), p[x] / q[x])
    ok = u < threshold
    print(f'{x}: u={float(u):.1f}, threshold={float(threshold):.3f}, accept={ok}')
    if not ok:
        assert residual is not None
        emitted.append(sample(residual, final_draw))
        print('discard:', draft[i:])
        break
    emitted.append(x)
else:
    bonus = sample(p, final_draw)
    emitted.append(bonus)
    print('bonus:', bonus)
print('emit:', emitted)

accepted mass: [0.5, 0.1, 0.2]
acceptance: 0.8
residual: [0.0, 1.0, 0.0]
reconstructed: [0.5, 0.3, 0.2]
A: u=0.7, threshold=0.833, accept=True
C: u=0.9, threshold=0.667, accept=False
discard: ['C', 'B']
emit: ['A', 'B']

这一轮提交 A、B；最后那个草稿 B 虽然碰巧与校正 token 相同，也要丢弃它原先基于 A、C 前缀的状态。

分布相同也不要求同一个随机种子产生逐字相同的回答，算法消费随机数的顺序可以不同。vLLM 的无损保证说明还保留了浮点精度、批大小与 logprob 稳定性的条件。保证针对既定目标的解码分布；目标本身的量化或近似缓存带来的改变，需要另作比较。

好草稿也要算得便宜

对一个固定前缀，接受率等于 $\sum_x\min(p(x),q(x))$。草稿与目标的分布接近，才容易接受；草稿独立回答问题的能力不能直接代替这个指标。

用一个简化预算估计是否值得尝试。设每轮提出 $\gamma$ 个候选，每个位置的条件接受概率都是 $\alpha$，接受事件独立同分布，且没有提前停止。包括校正或额外 token，一轮平均提交：

$$E[N]=1+\alpha+\alpha^2+\cdots+\alpha^\gamma.$$

这是原论文第 3.1 节采用的简化条件。实际接受率随位置和任务变化时，应统计一轮真正提交的 token 数，不能把一个总体平均接受率无条件代入。

下面的耗时全部是假设值：普通目标 decode 每 token 为 10 ms，$\gamma=4$，整轮目标验证为 12 ms，状态处理为 2 ms。草稿每 token 耗时为 $d$，且这些阶段不重叠，则每轮耗时为 $4d+12+2$ ms。在足够长的生成中，每 token 的长期平均耗时为这一预算除以 $E[N]$。

gamma = 4
baseline_ms = 10
verify_ms = 12
state_ms = 2
for alpha, draft_ms in [(0.8, 1), (0.9, 3)]:
    expected = sum(alpha ** j for j in range(gamma + 1))
    cycle_ms = gamma * draft_ms + verify_ms + state_ms
    per_token = cycle_ms / expected
    speedup = baseline_ms / per_token
    print(f'alpha={alpha:.1f} tokens={expected:.4f} cycle_ms={cycle_ms} '
          f'ms/token={per_token:.3f} speedup={speedup:.3f}x')

alpha=0.8 tokens=3.3616 cycle_ms=18 ms/token=5.355 speedup=1.868x
alpha=0.9 tokens=4.0951 cycle_ms=26 ms/token=6.349 speedup=1.575x

第一种草稿每 token 用 1 ms；第二种用 3 ms。第二种平均提交更多 token，却更慢：约 1.575 倍加速，低于第一种的 1.868 倍。真实验证耗时也可能随候选数、批大小、上下文和树形变化。把测得的成本代入，再调草稿长度；接受率、草稿速度、验证和状态处理成本要一起看。

链、树与自推测是不同维度

2026 年 9 月 21 日的 DeepSeek-V4 适配预印本讨论了线性链与候选树。LayerSkip 原论文提供了自推测的具体例子：训练时加入分层 dropout 和 early-exit loss，推理时用早期层起草，再用剩余层验证与校正。因此，不能假定任意未适配模型都能高质量地提前退出。

选择	候选或计算怎样组织	需要付出的成本
线性链	每轮只探索一条连续候选路径	早期拒绝会浪费后面的候选
候选树	共享前缀处分出多个可能的后续，限制待验证节点数	树形因果注意力、分支状态和路径提交
自推测	同一模型的一部分先起草，完整目标路径负责验证	早退能力、复用计算和回滚机制

前两行描述候选形状；第三行描述草稿来自哪里。候选树最终只提交一条连续路径，接受与采样规则仍须保持目标分布。不能把链上的单候选校正规则直接套在任意树上，也不能把“挑概率最高的分支”当作目标采样。它与用多个前缀优化序列分数的 beam search 目的不同。

KV 状态要跟随接受的路径

KV-cache 笔记解释了缓存复用与压缩的基础。推测解码还要求缓存内容对应最终提交的前缀：线性链拒绝后要撤销候选后缀；树中的节点只能看见已提交前缀和自己的祖先，不能看见兄弟分支。共享前缀可以复用，分叉后的暂存状态要隔离。新采样的校正或额外 token 若尚未经过前向计算，其 KV 状态要在后续计算中补齐，不能沿用被拒绝候选的状态。

DeepSeek-V4 预印本第 2–4 节说明，CSA（Compressed Sparse Attention）与 HCA（Heavily Compressed Attention）还会沿序列压缩历史。不同分支可能形成不同的压缩状态，仅换一个树形注意力 mask 不够。论文用临时 scratch pad 隔离分支，选择路径后再刷新该路径的 KV、压缩状态及中间缓冲区。这里的跨位置压缩，与 MLA（多头潜在注意力）缩小每个 token 的缓存表示宽度有区别。

论文在八张 NVIDIA GPU 上测试 DeepSeek-V4-Flash，验证预算为 5–8，批大小为 1–64，数据集为 GSM8K、MBPP 和 ShareGPT。它报告树相对同预算线性推测的最高 decode 吞吐提升约为 18.5%，出现在 ShareGPT、配置 s3_k2_d6、批大小 4。这个比较对象已经用了推测解码。预算继续增大时，接受长度仍可能上升，吞吐却趋于平台；分支管理和状态刷新会吃掉增益。

在相同负载和质量下比较

vLLM 官方文档把中低 QPS、受内存带宽限制的负载作为降低 token 间延迟的使用场景。先按本地运行时确认模型、草稿及后端兼容性，再作两组比较：关闭与开启推测；在线性推测已可用时，再比较同验证预算的链与树。

固定目标 checkpoint、精度、tokenizer、提示模板、采样和停止规则、缓存策略、硬件及运行时版本。使用同一提示集合和输入长度分布，记录实际输出长度，并分别测试相同并发数或相同到达率；低负载延迟与饱和吞吐需要分别测量。

记录什么	怎样判断收益
每轮提交 token 数，候选数和接受率的统计口径	分清草稿接受率与最终有用输出，尤其别把树节点总数当作接受路径长度
起草、验证、状态刷新耗时及峰值显存	确定多接受的 token 是否抵消额外工作；计入草稿模型和临时分支状态
TTFT、token 间隔、端到端延迟的中位数与 p95	推测可能成批输出，平均 token 速度会掩盖两批之间的停顿
每秒最终输出 token、每秒完成请求，以及错误和超时	未被接受的候选不计入有用吞吐；保留失败请求
相同任务的正确率、格式有效率和完成率	区分保持目标采样分布与改变精度、缓存或采样设置带来的质量变化

接受率说明草稿匹配程度；每轮耗时除以真正提交的 token 数，才连接到速度。以推理性能笔记中的测量边界报告结果，才能看清节省发生在 decode、整次请求，还是整个服务。

我的阅读 · 打开过的笔记会记在当前浏览器里。