# n-gram 投机采样怎么做？不用草稿模型的加速方案

> Prompt Lookup、Lookahead Decoding、REST 都不训练草稿模型，而是从 n-gram 或检索库里取候选，再交给目标模型并行验证。本文比较三种「记忆来源」的差异，解释 Lookahead 为什么能把 Jacobi 迭代救活，以及这类方法在什么任务上才真的赢。

Canonical: https://doraemeng.dev/notes/llm%E6%8E%A8%E6%B5%8B%E8%A7%A3%E7%A0%81%E7%B2%BE%E8%AF%BB%E7%AC%94%E8%AE%B0-05-n-gram%E6%A3%80%E7%B4%A2%E5%BC%8F%E4%B8%8E%E6%97%A0%E6%A8%A1%E5%9E%8B%E8%B7%AF%E7%BA%BF/


> 系列导航：[推测解码精读笔记总览](/notes/llm推测解码精读笔记-00-总览与学习地图/)（共 6 篇）｜上一篇：[EAGLE 推测解码为什么比 Medusa 快](/notes/llm推测解码精读笔记-04-eagle-特征空间草稿/)｜下一篇：[推测解码上线怎么验收](/notes/llm推测解码精读笔记-06-系统集成与生产验收/)

> 对应：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. 动机：草稿的第三种来源——记忆与检索

不训练任何草稿模型，能不能猜出接下来的几个 token？02–04 章的三条草稿路线都需要训练：

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

文本生成经常重复已有文本：代码里的模板、摘要里复述原文的句子、多轮对话里重复的指令。这些重复就是**免费的草稿来源**：

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

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

---

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

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

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

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

| 方法 | 记忆来源 | 一句话 |
|---|---|---|
| Prompt Lookup | 当前 prompt / 已生成文本 | "翻自己说过的话" |
| Lookahead Decoding | 自生成的 Jacobi 轨迹缓存 | "翻自己刚想过的词" |
| REST | 外部大规模语料 datastore | "翻全世界说过的话" |

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

---

## 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 退化为普通解码（白付一次验证开销）。

---

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

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

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

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

$$
y_i = \arg\max_y P_M(y \mid y_1, \dots, y_{i-1}, \mathbf{x}^0), \qquad i = 1, \dots, 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)$，上式等价于非线性方程组：

$$
f(y_i, \mathbf{y}_{1:i-1}, \mathbf{x}^0) = 0, \qquad i = 1, \dots, m
$$

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

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

$$
y_i^{t+1} = \arg\max_y P_M(y \mid y_1^{t}, \dots, y_{i-1}^{t}, \mathbf{x}^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 步数}}$。论文推导：

$$
S = \frac{f - 1 + E[\#\text{tokens}]}{f}
$$

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

---

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

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

### 6.1 Datastore 构建

$$
D = \{(c_i, t_i)\}
$$

对语料里每个位置，$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%：

$$
\text{Retrieve}(D, s) = \{(c_i, t_i) : c_i \text{ 以 } s \text{ 的最长匹配后缀结尾}\}
$$

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

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

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

### 6.4 验证与无损性

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

---

## 7. 三种方法对照

| 维度 | Prompt Lookup | Lookahead Decoding | REST |
|---|---|---|---|
| 记忆来源 | 当前 prompt/生成文本 | 自生成 Jacobi 轨迹 | 外部语料 datastore |
| 记忆规模 | 1 个序列（小） | 固定窗口（中） | 百万级语料（大） |
| 特有机制 | 无（纯字符串匹配） | 2D 窗口 + n-gram pool | 后缀数组检索 + Trie 加权 |
| 训练 | 无 | 无 | 无（但要建 datastore） |
| 无损 | 严格 | 严格（Appendix B 证明） | 严格 |
| 最擅长的任务 | 摘要/代码/多轮 | 代码补全（规律性强） | 代码（HumanEval）最强，通用其次 |
| 典型加速 | 取决于重复度 | 1.5–2.3x | 1.62–2.36x |

---

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

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

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

$$
\alpha_i = P\!\left(\hat{t}_i = \arg\max_x p(x \mid \text{上下文} + \hat{t}_{<i})\right)
$$

期望产出（贪心，K 个草稿 + 1 个修正/bonus）：

$$
E[N] = 1 + \alpha_1 + \alpha_1\alpha_2 + \cdots + \prod_{i=1}^{K}\alpha_i
$$

### 8.2 命中率由什么决定

$\alpha_i$ 的核心是 **n-gram 命中**：续写 $\hat{t}_{1:i}$ 恰好等于目标真正会生成的序列。命中概率由两个因素决定：

$$
P(\text{命中 } i \text{ 个}) = \underbrace{P(\text{上下文在记忆中出现过})}_{\text{覆盖}} \times \underbrace{P(\text{续写与目标一致} \mid \text{出现})}_{\text{规律性}}
$$

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

### 8.3 与训练路线的根本区别

| | 训练路线（Medusa/EAGLE） | 无模型路线（本章） |
|---|---|---|
| α 的来源 | 学出来的（参数记忆规律） | 查出来的（显式记忆实例） |
| 覆盖范围 | 任意上下文（泛化） | 只覆盖记忆里出现过的 n-gram |
| 长距离依赖 | 有（模型条件化） | 基本没有（局部匹配） |
| 部署成本 | 训练 + 额外权重 | 零训练，但 REST 要带 datastore |

---

## 9. 数值算例

### 9.1 PLD：一轮完整流程

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

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

设实际接受率剖面 $\alpha = (1, 1, 0.95, 0.9, 0.8)$（前几位完全复用原文，越往后越自由）：

$$
E[N] = 1 + 1 + 1 + 0.95 + 0.855 + 0.684 = 5.49
$$

一个目标前向换 5.49 个 token——摘要场景下 PLD 的威力。

### 9.2 Lookahead：轨迹如何变成记忆

```
前缀 "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"）
```

这一步的验证分支本来就不会命中：当前末尾是 "sat"，pool 里没有以 "sat" 开头的 n-gram，所以先按普通解码生成 "on"。等 "on" 成为当前末尾，下一轮才能从 pool 里取出 (on, the, mat) 作为草稿。

关键是：**Jacobi 一轮蒙对的 token 不再被覆盖，而是以 n-gram 形式缓存，下一轮通过验证正式"转正"**。这就是"边想边记"。

### 9.3 REST：命中率对加速的放大

设 REST 检索到一条 6-token 续写，实际接受率剖面 $\alpha = (0.9, 0.85, 0.8, 0.7, 0.6, 0.5)$：

$$
E[N] = 1 + 0.9 + 0.765 + 0.612 + 0.428 + 0.257 + 0.129 = 4.09
$$

对照：若命中率整体砍半（$\alpha = (0.45, 0.425, 0.4, 0.35, 0.3, 0.25)$），$E[N] \approx 1.75$；再算上检索和验证开销，加速比就贴近 1。

---

## 10. 实验结果

论文已核实数据：

| 方法 | 实验设置 | 结果 |
|---|---|---|
| Lookahead | 多种数据集，单 GPU | 1.5x–2.3x；代码补全最高 2.3x |
| Lookahead | 模型规模对比 | 小模型加速比更高（大模型更快触及 FLOPs 上限） |
| REST | CodeLlama 7B/13B + The Stack，HumanEval | 2.12x–2.36x |
| REST | Vicuna 7B/13B + UltraChat，MT-Bench | 1.62x–1.77x |
| REST（摘要） | 整体声明 | 1.62x–2.36x（代码或文本生成） |
| PLD | EAGLE-2 论文对照实验 | 摘要任务（CNN/DM）上无模型方法中最高加速 |

两个共同规律：

1. **代码 > 文本**：代码模板重复率高，n-gram 命中率显著更高（Lookahead 2.3x、REST 2.36x 都出现在代码任务）；
2. **重复率是主要变量**：同一方法在代码与通用对话任务上的差距可达 1.5 倍左右（表中 REST：HumanEval 2.36x，MT-Bench 1.62x）。

---

## 11. 决策框架：无模型 vs 训练路线

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

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

工程里的常见组合是 PLD 附加在 EAGLE/Medusa 上：它没有训练成本和额外权重，但命中失败时仍要付一次验证前向，所以只在命中率足够高的任务上保留。06 章会给出组合验收的具体协议。

---

## 12. 实现细节与坑

1. **n-gram 匹配要设长度下限**：太短的匹配（如 1-gram）几乎必然错误，白费验证；vLLM 的 `prompt_lookup_min` 默认设 1，工程上建议 ≥ 2–3。
2. **匹配位置要排除"正在生成的部分"**：PLD 必须只在已确认文本里查，否则会匹配到"自己刚猜的候选"，形成循环。
3. **Lookahead 的 2D 窗口参数要调**：$W$（向前看）与 $N$（往回看）决定每步 FLOPs；$W$、$N$ 太大会撞 GPU FLOPs 上限，加速比反而下降（论文 Fig. 4）。
4. **REST 的 datastore 要与任务同域**：代码模型配代码语料、对话模型配对话语料，否则覆盖率为 0。
5. **检索不是免费的**：REST 用后缀数组把开销压到 < 6%，但 naive 扫描会吃掉全部收益。
6. **无损性依赖验证**：无模型方法如果跳过验证直接采用检索续写（有些工程实现图快这么做），输出分布就变了——严格无损必须走拒绝采样/贪心比对。
7. **组合使用**：多个草稿源的候选要合并进同一棵树，掩码与概率记账都要相应处理。

---

## 13. 本章小结

1. **统一公式**：无模型路线 = n-gram 记忆续写 + 目标并行验证；差异只在记忆来源。
2. **PLD**：查自己（prompt），最简单，靠重复率吃饭。
3. **Lookahead**：查自己的 Jacobi 轨迹（2D 窗口 + n-gram pool），把"蒙对又覆盖"变成"缓存后转正"；缩放律支持靠算力压步数。
4. **REST**：查外部语料（后缀数组 + Trie），把语料当"非参数草稿模型"。
5. **数学**：$E[N] = 1 + \alpha_1 + \alpha_1\alpha_2 + \cdots$，$\alpha_i$ 由"记忆覆盖 × 文本规律性"决定；重复性强则接近训练路线，否则失效。
6. **共同底线**：全部严格无损（验证保证），这是它们作为"插件"的前提。

> 一句话记忆：**"不训练也能猜——前提是文本会重复：翻自己（PLD）、翻自己刚想的（Lookahead）、翻全世界（REST），都是把'说过的话'变成'接下来要说的话'。"**

---

## 14. 习题与解答

### 题 1（推导）：统一公式

写出无模型路线的统一流程，并解释为什么三种方法的唯一区别是"记忆来源"。用 $E[N] = 1 + \sum_{i=1}^{K}\prod_{j \le i}\alpha_j$ 说明验证的作用。

<details>
<summary>题 1 解答要点</summary>

统一流程：① 在记忆里找与当前后缀匹配的 n-gram → 取续写；② 目标并行验证；③ 拒绝采样/贪心比对保持分布。PLD/Lookahead/REST 只换第①步的记忆源。公式里 $\alpha_i$ 全由检索命中决定，验证本身不改变分布——所以无论 $\alpha$ 多低，无损性都成立。
</details>

### 题 2（计算）：命中率对加速的影响

比较两组接受率剖面：A = (0.9, 0.8, 0.7)、B = (0.5, 0.4, 0.3)（均 K=3），算 $E[N]$；设一次验证开销为 1.1 次普通前向，分别算净加速。

<details>
<summary>题 2 解答</summary>

A：$1 + 0.9 + 0.72 + 0.504 = 3.124$，净加速 $3.124/1.1 = 2.84\text{x}$。B：$1 + 0.5 + 0.2 + 0.06 = 1.76$，净加速 $1.76/1.1 = 1.60\text{x}$。B 虽然还是正的，但若检索再花一点时间就跌破 1——命中率是盈亏分界线。
</details>

### 题 3（推导）：Jacobi 为什么收敛但低效

证明 Jacobi 解码至多 $m$ 轮收敛（$m$ 为生成长度），并解释为什么"每轮至少 1 个 token 正确"不足以带来墙钟加速。

<details>
<summary>题 3 解答</summary>

第 $t+1$ 轮第 1 个位置用真实前缀计算，$y_1^{t+1}$ 必等于自回归首 token；第 $t+2$ 轮第 2 个位置可用 $y_1^{t+1}$（已正确）……归纳得每轮至少"多对 1 个位置"，故至多 $m$ 轮。低效原因：多轮迭代的 FLOPs 总和通常 ≥ 自回归的 $m$ 次前向（每轮都是全模型前向）；且已对的位置会被后续轮次用旧猜测覆盖，正确 token 常"落不了地"。
</details>

### 题 4（思考）：Lookahead 如何救活 Jacobi

解释"2D 窗口 + n-gram pool"分别解决了 Jacobi 的两个缺陷（错位、被覆盖），并说明验证分支为什么能"转正"轨迹里的 n-gram。

<details>
<summary>题 4 解答要点</summary>

错位：n-gram 按"起点 token"检索，只有与当前序列衔接的 n-gram 才会被验证，不再要求"整体序列刚好对齐"。被覆盖：轨迹里的 n-gram 被写进 pool 持久化，即使后续迭代覆盖了轨迹中的位置，pool 里仍保留候选。验证分支用目标模型确认"该 n-gram 的每个 token 与真实条件分布一致"，一致的前缀转正，不一致处停止——这就是无损的保证。
</details>

### 题 5（设计）：REST 的 datastore 与 Trie

给定语料里 5 条命中续写，说明 Trie 节点权重如何累计、为什么"最高频前缀"是好的草稿选择；若检索到 1000 条续写而验证预算只有 64 个节点，贪心挑权重最高的前缀子树会出现什么问题？

<details>
<summary>题 5 解答要点</summary>

每条续写的每个前缀都让对应 Trie 节点计数 +1；权重 = 频次，代表"语料里有多少证据支持这个前缀"。高频前缀是语料共识，命中率高。预算 64 节点时，纯按权重贪心会偏向"第一个 token 高频"的分支而忽略次高频的多样分支——需要在"深度"和"分支覆盖"间平衡（类似 03 章优化树的思路；REST 论文的 top-c 截断是一种简单近似）。
</details>

### 题 6（编程）：PLD 的 toy 实现

实现一个 toy：给定一个长 prompt 与目标贪心函数，跑 1 万轮 PLD（min=2, max=8），统计命中率与每轮 token 数；再构造一个"零重复"的随机 prompt 对比，观察加速比如何跌破 1。

<details>
<summary>题 6 解答要点</summary>

① 每次取末尾 n 个 token 在已确认文本里搜最长匹配，取后续为草稿；② 目标逐位比对，接受一致前缀，不一致处输出目标 token 并停；③ 统计 $E[N]$ 与公式对照；④ 随机 prompt 下匹配几乎失败，$E[N] \approx 1$ 且每轮仍付一次验证前向，净加速 < 1——复现"重复率决定盈亏"。
</details>

---

## 15. 延伸阅读

1. [Breaking the Sequential Dependency of LLM Inference Using Lookahead Decoding（arXiv:2307.09991 / 2402.02057）](https://arxiv.org/abs/2307.09991)：Jacobi 形式化、2D 窗口、n-gram pool、无损性证明（Appendix B）、缩放律。
2. [REST: Retrieval-Based Speculative Decoding（arXiv:2311.08252）](https://arxiv.org/abs/2311.08252)：datastore、后缀数组检索、Trie 建草稿、实验。
3. [Prompt Lookup Decoding（Saxena, GitHub）](https://github.com/apoorvumang/prompt-lookup-decoding)：PLD 的规范实现；vLLM 的 `[ngram]` 模式与 TensorRT-LLM NGram 模式文档。
4. [LLMA: Let Language Models be Maracas Again（Yang et al., arXiv:2309.14455）](https://arxiv.org/abs/2309.14455)：从 RAG 提供的参考上下文检索草稿的早期工作，REST 论文与之对比。
5. 上一篇：[04 EAGLE：特征空间草稿](/notes/llm推测解码精读笔记-04-eagle-特征空间草稿/)；下一篇：**06 系统集成与生产验收**——把量化、推测解码、KV 缓存、批处理组合成一份部署方案，并给出验收协议。

