🤖 machine learning

Faster LLM Inference via Sequential Monte Carlo

该论文提出了基于序贯蒙特卡洛的推测解码方法（SMC-SD），通过用重要性加权重采样替代传统的拒绝采样，将验证过程转化为向量化固定大小操作，从而在保持与目标模型极高精度一致性的同时，显著提升了大语言模型的推理速度。

原作者： Yahya Emara, Mauricio Barba da Costa, Chi-Chih Chang, Cameron Freer, Tim Vieira, Ryan Cotterell, Mohamed S. Abdelfattah

发布于 2026-04-20

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Yahya Emara, Mauricio Barba da Costa, Chi-Chih Chang, Cameron Freer, Tim Vieira, Ryan Cotterell, Mohamed S. Abdelfattah

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一种名为 SMC-SD（基于序列蒙特卡洛的推测解码）的新方法，旨在让大型语言模型（LLM）“说话”得更快，同时保持聪明。

为了让你轻松理解，我们可以把语言模型的生成过程想象成一位作家在写故事。

1. 现在的困境：慢吞吞的“逐字写作”

现状（自回归解码）：想象一位作家（目标模型），他非常博学，但性格谨慎。他写故事时，必须一个字一个字地写。写完“今”，确认没问题，才能写“天”；写完“天”，才能写“气”。
瓶颈：因为必须等前一个字完全确定才能写下一个，所以速度很慢。就像一个人走楼梯，必须踩稳一级才能迈下一级，无法加速。

2. 现有的加速方案：大胆的“草稿员”与严格的“主编”

为了解决慢的问题，之前的方法叫推测解码（Speculative Decoding, SD）。

角色：
- 草稿员（小模型）：一个反应快但水平稍逊的助手。他负责快速猜出接下来的几个字（比如一口气猜出“今天天气不错”）。
- 主编（大模型）：那位谨慎的作家。
工作流程：
1. 草稿员快速写下“今天天气不错”。
2. 主编快速检查这串字。
3. 关键问题（拒绝机制）：如果主编发现“不错”这两个字不对（比如应该是“很好”），他会直接划掉“不错”，甚至把后面猜错的部分全部扔掉，只保留“今天天气很”，然后重新从“很”字开始猜。
缺点：如果草稿员猜得稍微有点偏，主编就会“翻脸”，把前面辛苦猜的一大串都作废。这就叫“拒绝截断”。一旦猜错，之前的努力就白费了，速度提升大打折扣。

3. 本文的突破：聪明的“海选”与“重加权”

这篇论文提出的 SMC-SD 方法，换了一种思路。它不再依赖“猜对就全留，猜错就全扔”的粗暴方式，而是引入了**“粒子群”和“投票”**的概念。

核心比喻：从“单人独裁”到“海选复投”

想象主编不再只让一个草稿员猜，而是让**一群草稿员（粒子群，比如 8 个）**同时猜接下来的故事走向。

步骤一：并行猜测
8 个草稿员同时开始猜，每人猜出 4 个字。
- 草稿员 A 猜：“今天天气不错"
- 草稿员 B 猜：“今天天气很好"
- 草稿员 C 猜：“今天天气真棒"
- ...
步骤二：打分（而不是直接拒绝）
主编（大模型）不再说“错！重来”，而是给这 8 个版本打分。
- 主编觉得“不错”有点俗气，给分 30 分。
- 主编觉得“很好”很贴切，给分 90 分。
- 主编觉得“真棒”太夸张，给分 10 分。
步骤三：优胜劣汰（重采样）
这是最精彩的一步。主编不会把低分的直接扔掉，而是进行**“加权复制”**：
- 因为“很好”得分高，主编决定多复制几份这个版本（比如复制 3 份）。
- 因为“不错”得分低，只保留 1 份。
- 因为“真棒”得分太低，直接淘汰（不再保留）。
- 结果：下一轮，大家手里拿的大多是“很好”这个版本，但并没有浪费之前计算“不错”和“真棒”的算力，因为那些计算已经发生了，只是用来辅助决策。

为什么这更快？

没有“回滚”浪费：在旧方法里，一旦猜错就要回退，之前的计算全废了。在新方法里，无论猜得准不准，所有的计算都变成了“投票数据”，没有一步是白费的。
利用闲置算力：现在的电脑显卡（GPU）非常强大，但往往因为要等前一个字，导致大部分算力在“发呆”。SMC-SD 让显卡同时处理 8 个、16 个甚至更多的猜测，把显卡的“空闲时间”利用了起来，把原本串行的工作变成了并行工作。
固定产出：无论猜得准不准，每一轮都能稳稳地输出固定数量的字（比如每轮固定输出 5 个字），不再因为猜错而卡顿。

4. 实际效果如何？

论文在多个测试（如数学推理、写代码、遵循指令）中证明了这种方法：

速度：比现有的最快方法快了 2.36 倍，比最原始的方法快了 5.2 倍。
质量：虽然它不是“完美”的（因为它是基于概率投票的近似），但生成的文章质量依然非常高，与原始大模型相比，准确率只下降了不到 3%。

总结

这就好比：

旧方法：派一个侦探去破案，一旦走错一步，就要回到起点重新走，非常浪费时间。
新方法（SMC-SD）：派一个侦探小队同时走不同的路。大家走到分岔口后，队长根据线索给每条路打分，然后让大部分队员集中走那条得分最高的路，同时保留少量队员走其他路以防万一。

SMC-SD 的核心思想就是：不要浪费任何一次尝试，用“概率投票”代替“非黑即白的拒绝”，从而让 AI 跑得更快、更稳。

1. 研究背景与问题 (Problem)

核心瓶颈：大语言模型（LLM）的自回归生成本质上是串行的，每个 token 的生成都依赖于前一个 token，导致推理速度慢，且受限于显存带宽（Memory Bandwidth-bound）。
现有方案局限：
- 自回归解码 (Autoregressive, AR)：速度最慢，每次只生成一个 token。
- 推测解码 (Speculative Decoding, SD)：目前的主流加速方案。它使用一个廉价的小模型（Draft Model）生成 $K$ 个 token，然后由大模型（Target Model）一次性验证。
- SD 的缺陷：SD 采用拒绝采样 (Rejection Sampling) 机制。一旦大模型在验证过程中发现第一个不匹配的 token，该 token 及其后的所有草稿 token 都会被丢弃（Truncation）。
- 后果：当草稿模型与大模型分布差异较大时，接受率下降，导致大量计算被浪费，吞吐量（Throughput）显著降低。此外，SD 的加速比是随机的，取决于草稿与大模型的对齐程度。

2. 方法论：SMC-SD (Methodology)

作者提出了一种名为 序贯蒙特卡洛推测解码 (Sequential Monte Carlo Speculative Decoding, SMC-SD) 的新方法。其核心思想是用重要性加权重采样 (Importance-weighted Resampling) 替代传统的拒绝采样。

核心流程

SMC-SD 维护一组 $N$ 个“粒子”（即 $N$ 条候选序列），每一步迭代包含以下操作：

扩展 (Extend)：草稿模型并行地为 $N$ 个粒子各生成 $K$ 个 token。
评分与奖励 (Score & Bonus)：目标模型在一个批处理的前向传播中，对所有 $N$ 条序列的 $K$ 个扩展 token 进行评分，并为每条序列生成一个额外的“奖励 token"（Bonus Token）。
重加权 (Reweight)：根据目标模型与草稿模型的概率比率，更新每个粒子的权重（重要性权重）。
重采样 (Resample)：
- 计算有效样本量 (ESS, Effective Sample Size)。
- 如果 ESS 低于阈值，则根据权重进行重采样：高权重的粒子被复制（保留），低权重的粒子被淘汰。
- 关键区别：不像 SD 那样遇到错误就截断，SMC-SD 总是生成固定数量的 token ( $K+1$ )，通过调整粒子的分布来逼近目标分布。

系统优化设计

为了在硬件上高效运行，作者设计了专门的推理引擎：

向量化执行：利用 GPU 的并行能力，将草稿和验证过程转化为固定大小的向量操作，消除了 SD 中的回滚（Rollback）开销。
KV Cache 优化：利用粒子间共享前缀的特性，在重采样步骤中，仅通过交换指针（Pointer Exchange）和更新引用计数来管理 KV Cache，避免了昂贵的数据拷贝。这使得 KV Cache 的使用量大幅减少（实验中减少约 72.3%）。
计算密度提升：SMC-SD 显著提高了算术强度（Arithmetic Intensity），将原本受限于显存带宽的推理转变为更接近计算受限（Compute-bound）的模式，充分利用了现代 GPU 的算力。

3. 理论贡献 (Key Contributions)

理论误差界：
- 证明了 SMC-SD 是一个有理论保证的近似采样方案。
- 推导了非渐近误差界： $L_2$ 偏差和均方误差 (MSE) 随粒子数 $N$ 的增加以 $O(1/N)$ 的速度衰减； $L_1$ 偏差以 $O(1/\sqrt{N})$ 的速度衰减。
- 误差常数由草稿模型与目标模型之间的 $\chi^2$ 散度决定。
速度提升分析 (Roofline Model)：
- 基于 GPU 的 Roofline 模型，推导了 SMC-SD 的吞吐量加速公式。
- 在显存带宽受限模式下，加速比约为 $S \approx \frac{K+1}{\rho K + 1}$ （其中 $\rho$ 是草稿与目标模型的参数量比），且粒子数 $N$ 的增加几乎是“免费”的。
- 在计算受限模式下，加速比随有效批处理大小线性下降，但整体仍优于传统 SD。
通用性扩展：
- SMC-SD 不仅能加速推理，还能用于采样非归一化分布（如 Power Sampling 用于提升推理能力，或 Reward-weighted Decoding 用于 RLHF 策略优化），这是传统 SD 无法做到的。

4. 实验结果 (Results)

作者在 GSM8K、MATH500、AlpacaEval 和 DS1000 等基准测试上进行了评估，使用了 Llama 和 Qwen 系列模型。

吞吐量提升：
- 在单卡 H100 上，SMC-SD 比优化的树形推测解码（SGLang SD）快 2.36 倍，比纯自回归解码快 5.2 倍。
- 在多卡（4 H100）设置下（Llama 1B $\to$ 70B），SMC-SD 达到 342 tokens/s，相比 SGLang SD 提升 2.36 倍。
精度保持：
- 在保持目标模型精度 3% 以内 的前提下，实现了上述加速。
- 在 Pareto 前沿（速度 - 精度权衡）上，SMC-SD 始终优于标准 SD，即在相同精度下速度更快，或在相同速度下精度更高。
鲁棒性：
- 与传统 SD 不同，SMC-SD 的吞吐量对温度（Temperature）变化不敏感。随着温度升高（草稿与大模型差异变大），SD 的接受率下降导致速度骤降，而 SMC-SD 保持稳定的吞吐量。

5. 意义与影响 (Significance)

范式转变：将 LLM 推理从“寻找更快的精确采样器”转变为“设计可控的近似采样器”，用微小的精度损失换取巨大的速度提升。
硬件协同设计：SMC-SD 完美契合现代 GPU 的架构特性（高算力、显存带宽瓶颈），通过消除拒绝采样的回滚机制，将验证过程转化为固定大小的向量化操作，极大提升了硬件利用率。
未来方向：
- 为下一代 GPU 架构（如 NVIDIA Blackwell，其 FLOPS 增长快于带宽）提供了理想的算法目标。
- 开启了利用 SMC 框架进行更复杂分布采样（如约束生成、奖励加权）的大门，超越了单纯的推理加速。
开源贡献：作者提供了基于 SGLang 的高性能推理引擎实现，推动了社区对近似采样推理的探索。

总结：SMC-SD 通过引入序贯蒙特卡洛方法，成功解决了传统推测解码在草稿与大模型分布不一致时的性能瓶颈，在保持高精度的同时实现了显著的推理加速，是 LLM 推理系统优化的重要突破。