LLM 推测解码精读笔记 · 05 n-gram / 检索式与无模型路线

对应：Fu et al., Breaking the Sequential Dependency of LLM Inference Using Lookahead Decoding（arXiv:2307.09991 / 2402.02057，ICML 2024）；He et al., REST: Retrieval-Based Speculative Decoding（arXiv:2311.08252，2023）；Saxena, Prompt Lookup Decoding（vLLM / TensorRT-LLM 的 [ngram] 模式）。 前置：01–04 章。学完本章你应该能：① 说出无模型路线的统一公式"n-gram 记忆 + 目标并行验证"；② 比较 Prompt Lookup、Lookahead Decoding、REST 三种"记忆来源"的差异；③ 把自回归解码写成非线性方程组，解释 Jacobi 迭代为什么本身不加速、Lookahead 又怎么救活它；④ 写出 REST 的 datastore → 检索 → Trie 建草稿 → 树验证流程；⑤ 用命中率模型解释为什么这些方法在"重复性强"的任务上赢、在自由生成上输；⑥ 说清它们为什么都是无损的。

目录（本章） #

1. 本章目标
2. 动机：草稿的第三种来源——记忆与检索
3. 统一框架：n-gram 续写 + 目标验证
4. 方法一：Prompt Lookup Decoding（prompt 记忆）
5. 方法二：Lookahead Decoding（自生成轨迹记忆）
6. 方法三：REST（外部语料记忆）
7. 三种方法对照
8. 接受率数学：n-gram 命中率模型
9. 数值算例
10. 实验结果
11. 决策框架：无模型 vs 训练路线
12. 实现细节与坑
13. 本章小结
14. 习题与解答
15. 延伸阅读

2. 动机：草稿的第三种来源——记忆与检索 #

前三章回答了"草稿从哪来"的三种答案：

02：独立小模型（要预训练、要部署）
03：主干的头（要训练 K 个头）
04：特征级 decoder（要训练轻量模型）

共同点：都要训练。本章回答第四个问题：不训练任何东西，能不能猜？

答案藏在文本的结构里：生成过程经常重复已有文本——代码里的模板、摘要里复述原文的句子、多轮对话里重复的指令。这些"重复"是免费的草稿来源：

上下文结尾是 "return self.value + "，prompt 里出现过一模一样的片段，
后面大概率还是 "self.offset" 之类——直接在记忆里查，不用任何模型猜。

这类方法的共同名字叫无模型路线（model-free）：没有草稿模型、没有训练，只有"查表 + 验证"。

3. 统一框架：n-gram 续写 + 目标验证 #

本章三种方法（Prompt Lookup、Lookahead、REST）可以写成同一个公式：

候选 = 在"记忆"里找到与当前上下文后缀匹配的 n-gram，取出它的续写
验证 = 目标模型一次前向并行验证这些续写（拒绝采样保持无损）

差别只有一处——记忆从哪来：

后面每一节就是"把一种记忆源讲清楚 + 它特有的机制"。

4. 方法一：Prompt Lookup Decoding（PLD） #

4.1 算法 #

PLD 是最简单的无模型方法：把草稿模型替换成字符串匹配函数。

输入：当前已生成序列 S、lookup 长度范围 [min, max]
1. 取 S 末尾的 n 个 token 作为查询 q（从 max 开始，逐次减到 min）
2. 在 S 的前面部分（prompt + 已生成文本）里找 q 的精确匹配
3. 若找到：匹配位置之后的 token 序列（最长可用长度）作为草稿候选
4. 目标模型并行验证，接受匹配上的前缀

vLLM 里对应 speculative_model="[ngram]"，超参 prompt_lookup_min / prompt_lookup_max / num_speculative_tokens；TensorRT-LLM 的 NGram 模式同理。

4.2 为什么有效 #

典型场景：摘要、代码补全、翻译、多轮对话——输出大量逐字复用输入文本：

prompt ：“请总结：<长文>”
输出    ：“本文介绍了……文中提到……”   ← 大量短语直接来自 <长文>

EAGLE-2 论文的实验也印证：PLD 在摘要任务（CNN/DailyMail）上拿到无模型方法里最高的加速比，因为摘要与原文的重叠率最高。

4.3 边界 #

自由创作、开放域对话等重复率低的任务上，n-gram 匹配经常失败——PLD 退化为普通解码（白付一次验证开销）。所以 PLD 通常作为"零成本插件"与其他草稿方案组合，而不是独立路线。

5. 方法二：Lookahead Decoding（自生成轨迹记忆） #

Lookahead 回答的是另一个问题：没有外部记忆、prompt 也不重复时，草稿从哪来？ 答案是"让模型自己边想边记"。

5.1 自回归解码 = 解非线性方程组 #

设要生成 $m$ 个 token（贪心），自回归过程可以写成 $m$ 个方程：

定义 $f(y_i, \mathbf{y}_{1:i-1}, \mathbf{x}^0) = y_i - \arg\max_y P_M(y \mid \mathbf{y}_{1:i-1}, \mathbf{x}^0)$，上式等价于非线性方程组：

5.2 Jacobi 迭代：并行解方程组，但几乎不加速 #

求解非线性方程组的标准方法之一是 Jacobi 迭代：从一个初始猜测 $\mathbf{y}^0$ 出发，每一轮并行更新所有位置：

性质：

1. 每轮至少 1 个 token 正确：第一个位置用的是真实前缀，所以 $y_1^{t+1}$ 就是自回归的第一个 token——最多 $m$ 轮收敛；
2. 运气好时一轮能"蒙对"多个位置，减少解码步数；
3. 但论文实验发现 Jacobi 解码几乎不加速：猜对的 token 常被放在错误位置，且后续迭代会把已经放对的位置覆盖掉。

5.3 Lookahead 的补救：把轨迹变成 n-gram 记忆 #

Jacobi 每轮产生的轨迹 $(\mathbf{y}^0, \mathbf{y}^1, \dots)$ 里藏着一个事实：相邻两步的 token 组合是有意义的 2-gram（因为 $y_i^{t+1}$ 是基于 $y_{i-1}^{t}$ 生成的）。Lookahead 把这个观察推广到 $n$-gram，并加了两样东西：

① lookahead branch：一个固定大小的 2D 窗口
   W = 向前看几个位置（并行解码宽度）
   N = 往回看几步轨迹（n-gram 长度）
   每轮在 W 个位置并行生成 token，沿轨迹收集 n-gram

② n-gram pool：缓存轨迹里出现过的所有 n-gram
   下一轮用"当前最后 token"做 key，从 pool 里找以它开头的 n-gram 作为草稿

每轮三步：
1. lookahead branch：W 个位置并行生成新 token（一条新轨迹）
2. verification branch：从 n-gram pool 里取"以当前最后 token 开头"的候选，
   目标模型并行验证、接受匹配前缀
3. 把新轨迹的 n-gram 写回 pool；滑动窗口丢弃最旧的 token

注意 lookahead 分支与验证分支互不可见（各自独立的注意力掩码），同一个前向里并行执行。

5.4 无损性与采样支持 #

验证采用"不匹配即停"规则：n-gram 前缀与目标输出一致就接受，第一个不一致处停下。论文证明（Appendix B）：不相交 n-gram 的并行验证保持输出分布——这是 Lookahead 无损性的核心定理。

采样（非贪心）场景有个实现技巧：n-gram pool 若存概率分布会爆内存，所以 lookahead 分支强制贪心生成 n-gram——分布退化为 one-hot，只存选中的 token 即可。论文论证验证与草稿采样方式无关（采样方式只影响接受率，不改变输出分布），所以无损性依然成立。

5.5 缩放律 #

定义每步产出 $S = \frac{\#\text{生成 token}}{\#\text{Lookahead 步数}}$。论文推导：

（每 $f$ 步有 1 步好的猜测，其余退回自回归。）结论：步数随每步 $\log(\text{FLOPs})$ 线性下降——与推测解码"接受率封顶"不同，Lookahead 可以靠加算力（$W$、$N$）持续压步数；这也支撑它在多 GPU 上的强扩展性（lookahead parallelism：每 GPU 一份完整模型，按分支分发 token）。

6. 方法三：REST（外部语料记忆） #

REST 把记忆从"自己"扩展到"全世界"：用一个外部语料库当草稿模型。

6.1 Datastore 构建 #

对语料里每个位置，$c_i$ 是上下文、$t_i$ 是对应的续写，构成"上下文-续写"对。论文用了两个库：

代码域：The Stack 的 270 万条 Python 样本 → 加速 CodeLlama 7B/13B
通用域：UltraChat 约 77.4 万条对话 → 加速 Vicuna 7B/13B

6.2 检索：后缀精确匹配（几乎零开销） #

用当前上下文 $s$ 作为查询，在 $D$ 里找与 $s$ 最长后缀精确匹配的条目；匹配不到就缩短后缀长度再试。实现用后缀数组（suffix array），检索开销 < 6%：

6.3 Trie 建草稿：把一堆续写变成一棵候选树 #

检索结果可能很多，全用会撑爆验证前向。REST 用 Trie 合并它们：

1. 把所有续写 t_i 插进 Trie，每个节点累计"出现频次"作为权重
2. 按权重挑出 top-c 个最高频前缀（即"最被语料支持"的续写）
3. 这些前缀构成一棵草稿树

6.4 验证与无损性 #

草稿树用树注意力一次前向验证，从根开始接受，第一个不一致处之后全部丢弃；拒绝位置用标准拒绝采样修正。REST 与 PLD、Lookahead 一样严格无损——只影响草稿质量，不改变目标分布。

7. 三种方法对照 #

一个有趣的递进：记忆从小到大、检索从简单到复杂，但底层都是"找到与当前后缀匹配的 n-gram，取续写，交给目标验证"。

8. 接受率数学：n-gram 命中率模型 #

8.1 把无模型路线套进统一公式 #

设检索/查表得到续写 $(\hat{t}_1, \dots, \hat{t}_K)$，目标逐位验证。沿用 01–04 章的记号，第 $i$ 层接受概率：

摘要/代码/翻译：两个因素都高 → α ≈ 0.8~0.9，接近 Medusa/EAGLE
自由创作：覆盖低、规律性低 → α ≈ 0.2~0.4，加速比 < 1（白付验证费）

已生成序列：
  "请总结：AlphaGo 使用蒙特卡洛树搜索和深度神经网络。
   蒙特卡洛树搜索用于评估棋盘局面，深度神经网络……
   总结：AlphaGo 使用蒙特卡洛树搜索"

查询：取末尾 n=5："AlphaGo 使用蒙特卡洛树搜索"
匹配：在 prompt 开头找到相同片段（第 1 处）
草稿：取出其后续 "和深度神经网络"
验证：目标一次前向；贪心链 = "和深度神经网络" → 全部接受（α=1 直到第 5 位）
本轮产出：5 个 token（若第 6 位开始偏离则停在第一个不一致处）

前缀 "The cat sat"，目标续写应为 "on the mat"。

步 1：Jacobi 轨迹初始猜测 y^0 = (on, a, rug)
      并行更新：y^1 = (on, the, mat)     ← 一轮蒙对 3 个位置
      收集 n-gram：(on, the), (the, mat), (on, the, mat) → 写入 pool

步 2：当前最后 token = "sat"，pool 里查不到以 "sat" 开头的 n-gram
      → 验证分支查 "以当前序列末尾 n-gram 开头" 的候选：
      序列末尾是 "sat"，pool 有 ("sat" 之后的轨迹)……若无匹配则退化为普通一步
      （实际运行中，验证分支直接检查以当前最后 token 开头的 n-gram：
        若轨迹上一轮已生成 "on the mat" 且 "on" 紧邻当前 token，则直接验证 "on the mat"）

选无模型（本章）：
  ✓ 零训练、即插即用、严格无损
  ✓ 任务重复性强（摘要/代码/翻译/长上下文复用）
  ✗ 自由生成时命中率低，可能白付验证开销

选训练路线（03/04）：
  ✓ 接受率稳定（EAGLE ≈ 0.8），任意上下文可用
  ✓ 可与树、动态树、量化叠加
  ✗ 要训练、要维护额外权重