采样与解码
从 greedy 到 nucleus 再到 speculative decoding，各采样策略的原理与适用场景
核心要点：
- Greedy 易陷重复，beam search 在 LLM 时代被 nucleus 取代
- Temperature 仅 scale logits，不改变排序 （T<1 锐，T>1 平）
- Top-k 固定大小不灵活，Top-p (nucleus) 动态大小是主流
- p=0.95 是 Holtzman 2019 经典默认，重复率 0.36% 接近人类
- Repetition penalty θ=1.1-1.3，太高误伤标点
- Beam search perplexity 比 nucleus 低但更"机械"，印证 likelihood-quality mismatch
- Speculative decoding: draft 模型预测 K 个 → target 一次验证，2-3× 加速
- Medusa：长出多预测头 + tree attention，无 draft 模型 2.83× 加速
名词定义
本篇共享名词在 8.1 总览 已定义 (Greedy / Temperature / Top-k / Top-p / Beam search / Speculative decoding)。本篇新引入：
| 名词 | 定义 |
|---|---|
| HUSE | Holtzman 2019 提出的"Human Unified with Statistical Evaluation" 复合指标 |
| Repetition penalty | 已出现 token 的 logit 除以 （或乘以） penalty 系数 θ，减少重复 |
| Acceptance probability | Speculative decoding 中 target 模型接受 draft 模型预测的概率 |
| Tree attention | Medusa 用的注意力机制，一次验证多分支预测路径 |
@tbl-sample-glossary 本篇新引入名词
从 logits 到 token: 5 个常见算法
核心问题：LM head 给出 $V$ 维 logits，怎么选下一个 token？业界用哪些算法？
5 个主流算法：greedy / temperature / top-k / top-p / beam，各自有典型场景，现代 LLM 默认 temperature + top-p。
Greedy：每步 argmax
每步选概率最大的 token:
$$\begin{equation} x_t = \arg\max_v P(v \mid x_{<t}) \label{eq:sample-greedy} \end{equation}$$优点：确定性强 （相同 prompt 总是相同输出）。
致命缺陷：易陷重复循环。Holtzman 2019[1] 实测：
- Greedy 重复率 28.94% （vs 人类 0.28%, 100× 重复）
- 模型陷入"the the the..." 类循环
适用场景：结构化任务 （代码生成 / 翻译 / 数学），但不适合开放生成。
Temperature: scale logits
$$\begin{equation} P(v_k) = \frac{\exp(l_k / T)}{\sum_i \exp(l_i / T)} \label{eq:sample-temperature} \end{equation}$$- $T = 1$：原始 softmax
- $T < 1$：分布锐，趋向 greedy （确定性更强）
- $T > 1$：分布平，趋向均匀 （多样性更高）
- $T \to 0$：等价 greedy
- $T \to \infty$：等价均匀采样
业界典型：
| 场景 | Temperature |
|---|---|
| OpenAI API 默认 | 1.0 |
| 创意写作 | 0.7-1.0 |
| 代码生成 | 0.2-0.4 |
| Reasoning (CoT) | 0.0-0.6 |
@tbl-sample-temperature 业界 Temperature 经验值
Top-k：仅在前 k 个采样
Fan et al. ACL 2018[2]:
- 保留概率前 $k$ 大 token，其他 logits → $-\infty$
- 在剩下 $k$ 个上重归一化后采样
- $k$ 典型 50
缺陷：$k$ 是固定值，不灵活:
- 上下文约束强 （如 "1 + 1 = "） 时，真正合理的回答可能只有 1-2 个，$k=50$ 把低质 token 也纳入
- 上下文约束弱 （开放写作） 时，$k=50$ 可能截断过严，漏掉合理候选
Top-p (nucleus)：动态大小
Holtzman ICLR 2020[1] 提出 nucleus sampling:
$$\begin{equation} \text{选最小} V^{(p)} \subseteq V \text{ 使 } \sum_{x \in V^{(p)}} P(x \mid x_{<t}) \geq p \label{eq:sample-top-p} \end{equation}$$- $p = 0.95$ 经典默认
- 在 $V^{(p)}$ 上重归一化后采样
直觉：$V^{(p)}$ 是"最少 token 加起来覆盖 p 概率" 的集合，大小随分布形状动态变化：
- 分布尖 （上下文约束强）：$V^{(p)}$ 可能只 1-3 个 token
- 分布平 （开放生成）：$V^{(p)}$ 可能 100+ 个 token
Holtzman 2019 实证：nucleus 优于 beam / top-k
GPT-2 实测：
| 算法 | HUSE | Perplexity | 重复率 |
|---|---|---|---|
| Greedy | 低 | — | 28.94% |
| Beam search | 0.85 | 1.48 | 26.27% |
| Top-k k=40 | 0.94 | 6.88 | 1.78% |
| Nucleus p=0.95 | 0.97 | 13.13 | 0.36% |
| Human | 1.0 | 12.38 | 0.28% |
@tbl-sample-nucleus-ablation Holtzman 2019 GPT-2 实测 （HUSE / PPL / 重复率）
核心论点：Beam search perplexity 低至 1.48 正是"过度确定" 的证明，说明 likelihood maximization 与 quality 是 fundamental mismatch （likelihood 最大化的句子是 "I I I I I" 这种不像人类说的话）。Nucleus p=0.95 取 HUSE 最高 0.97，重复率仅 0.36% 接近人类。
现代 LLM 的默认配置
核心问题：ChatGPT / Claude / Llama 实际用什么 sampling?
业界默认：temperature + top-p 组合，T ≈ 0.7-1.0, p ≈ 0.9-0.95。
业界默认 （推测）
| 服务 | Temperature | Top-p |
|---|---|---|
| OpenAI API 默认 | 1.0 | 1.0 |
| OpenAI ChatGPT 推测 | 0.7-1.0 | 0.95 |
| Llama-3 推荐 | 0.6 | 0.9 |
| 代码 Copilot | 0.2 | 0.95 |
| 创意 / 故事 | 0.9-1.2 | 0.95 |
@tbl-sample-defaults 业界 sampling 默认 （公开或推测）
Repetition penalty：防重复
Keskar 2019 CTRL[3]:
- 已出现 token 的 logit 除以 （或乘以） $\theta$
- 正 logit 除以 $\theta$，负 logit 乘 $\theta$
- $\theta$ 典型 1.1-1.3, HuggingFace 推荐 1.2
局限：
- Binary 惩罚，不感知"重复次数"
- 过高 $\theta$ 会误伤空格 / 句号 / 标点 （它们也是"已出现"）
- 现代大模型用得越来越少 （训练数据多样性已足够防重复）
Beam search 在 LLM 时代为何被弃？
核心问题：Beam search 在 NMT 时代是黄金标准，为什么 LLM 时代不用？
Beam search 优化 likelihood，但 LLM 时代发现 high-likelihood 文本恰好是"机械化、单调、像机器人" 的——nucleus 更接近人类分布。
Beam search 算法
- 维护 b 条路径 (beam size = 4-16)
- 每步对每条路径展开所有可能 token，选总 log probability 最高的 b 个
- 最终选总 log probability 最高的完整序列
理论上找"最优 likelihood 序列"，在 NMT 上效果好 （因为翻译有"标准答案"）。
为什么 LLM 时代被弃
Holtzman 2019 揭示：
- LLM 训练数据是人类文本，但人类文本不是 likelihood-maximizing 的
- High-likelihood 序列恰好是"重复 + 单调"的模式塌缩
- Beam search 输出"听起来正确但毫无生气"
Likelihood-quality mismatch is a fundamental mismatch, not a bug：这是 LLM 训练目标 (CLM) 的内在结果——优化 next-token likelihood 让"重复 + 安全" 模式概率高。
Beam search 现状
- 开放式生成全面弃用 （ChatGPT / Claude / Llama 全用 nucleus）
- 翻译 / 摘要 等约束任务仍用 （有明确"对错"）
- HuggingFace transformers 仍支持但不是默认
Speculative decoding：加速 decode
核心问题：Decode memory-bound, throughput 受 HBM 限制。能不能"算多一点"提升 throughput?
Speculative decoding：用小 draft 模型预测 K 个 token，大 target 模型一次性 forward 验证，接受/拒绝——2-3× 加速，zero quality loss。
Leviathan ICML 2023 算法
Leviathan et al.[4]:
循环：
- Draft：用小模型 (~7B) 自回归生成 $\gamma$ 个 token (典型 $\gamma = 4-7$)
- Verify：大模型 (~70B) 一次 forward，并行算 $\gamma$ 个位置的概率分布
- Accept/Reject：对每个 draft token，按 acceptance probability $\min(1, p_{\text{target}} / p_{\text{draft}})$ 接受或拒绝
- Resample：拒绝的位置用 $\max(0, p_{\text{target}} - p_{\text{draft}})$ 重采保证 exact distribution
关键性质：输出分布与直接用 target 模型 sampling 完全等价——zero quality loss。
为什么有效
LLM 推理是 memory-bound:
- 大模型 forward 1 token 与 forward 4 token 的延迟差不多 （都被 HBM 读权重的时间主导）
- 用 draft 模型预测多 token + 一次验证 → 把 4 个 token 的 wall-clock 压缩到 1 个
实测
- T5-XXL 上 2-3× 加速 (Leviathan 2023)
- 接受率受 draft-target 相似度影响，接近 70-90% 时加速最显著
Medusa (Cai 2024)：无 draft 模型
Cai et al. 2024[5]:
- 不用独立 draft 模型，在 target model 的 LM head 之外长出 K 个独立预测头 （推荐 K=5）
- 第 k 头预测 $x_{t+k+1}$
- 用 tree attention 一次验证所有候选路径 （笛卡尔积树结构）
实测：
- Medusa-1 （冻结 backbone）：2.18-2.33× 加速
- Medusa-2 （联合训练）：2.83× 加速
- Coding / extraction 任务高达 3.29-3.62×
优势：不需要部署独立的小模型，工程更简单。
业界采用
- TensorRT-LLM / vLLM / SGLang 都支持 speculative decoding
- Llama 3 / Qwen 2 等模型可直接配 Medusa 头
Takeaway
| 知识点 | 核心结论 |
|---|---|
| Greedy | 每步 argmax，易陷重复 （28.94% vs 人类 0.28%） |
| Temperature | logits 除以 T, T<1 锐 / T>1 平 / T=1 原始 |
| Top-k | 固定 k 个 token 采样 (k=50)，不灵活 |
| Top-p (nucleus) | 动态选累积概率 ≥ p 的最小集合，p=0.95 经典 |
| Holtzman 2019 实证 | nucleus p=0.95 HUSE 0.97 接近人类 |
| Beam search 局限 | likelihood-quality mismatch，输出机械单调，LLM 时代弃用 |
| Repetition penalty | θ=1.1-1.3，过高误伤标点 |
| 业界默认 | Llama-3 推荐 T=0.6, p=0.9；代码 T=0.2 |
| Speculative decoding | draft K 个 + target 1 次验证，2-3× 加速，zero quality loss |
| Acceptance probability | $\min(1, p_{\text{target}}/p_{\text{draft}})$ |
| Medusa | LM head 之外 K 个预测头 + tree attention, 2.83× 加速 |
| 业界支持 | TRT-LLM / vLLM / SGLang 都支持 speculative |
开放问题
- Likelihood-quality mismatch 的根治：训练目标 (CLM) 内在导致，是否需要新训练目标 （RLHF 已部分缓解）
- Speculative draft 模型的最优选择：draft 太大失去加速，太小 acceptance 低；业界经验仍在探索
- Multi-token prediction （DeepSeek-V3 用） 是否会取代 speculative decoding 成为新标准：训练时长出多预测头，推理时直接用
- Sampling 算法在 reasoning 上的影响：o1 / R1 用 T=0 (greedy) 仍能好，是否说明 reasoning 不需 sampling
- Beam search 在某些 niche 场景 （代码 / 数学严格答案） 是否值得回归：当前主流仍 nucleus
延伸阅读
- 上一篇：KV cache → 8.3 KV cache
- 下一篇：量化简介 → 8.5 量化简介
- Temperature 训练 vs 推理 → 06-预训练/02-语言建模目标
- HuggingFace GenerationConfig 文档 → https://huggingface.co/docs/transformers/main_classes/text_generation
- Holtzman 2019 原论文 → https://arxiv.org/abs/1904.09751
参考资料
- Holtzman et al. The Curious Case of Neural Text Degeneration. ICLR 2020. https://arxiv.org/abs/1904.09751
- Fan et al. Hierarchical Neural Story Generation. ACL 2018. https://arxiv.org/abs/1805.04833
- Keskar et al. CTRL: A Conditional Transformer Language Model for Controllable Generation. 2019. https://arxiv.org/abs/1909.05858
- Leviathan et al. Fast Inference from Transformers via Speculative Decoding. ICML 2023. https://arxiv.org/abs/2211.17192
- Cai et al. Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads. 2024. https://arxiv.org/abs/2401.10774