Approximately Aligned Decoding¶
会议: NeurIPS 2025
arXiv: 2410.01103
代码: 无（详细实现描述在附录中）
领域: LLM推理 / 受约束生成
关键词: 受约束解码, 错误避免, 投机采样, 概率放大, lipogram
一句话总结¶
提出 Approximately Aligned Decoding (AprAD)，一种利用投机解码（speculative decoding）中的前缀选择算法来实现LLM受约束生成的方法——在遇到约束违反时，既不像约束生成那样仅回退一步（导致极端概率放大），也不像ASAp那样完全重新采样（计算成本过高），而是通过投机采样智能选择回退位置，在输出分布失真和计算效率之间取得良好平衡。
背景与动机¶
LLM生成的文本可能包含不期望的内容——语法错误的代码、幻觉PII、脏话、失败的工具调用等。现有的约束满足方法各有致命缺陷：（1）约束生成（constrained generation）：遇到违反时只屏蔽违反token，但会极端放大低概率输出——如果合法token原始概率极低（如0.0001），仍会被强制选择，导致输出分布严重扭曲；（2）ASAp（无替换采样）：精确从 \(P^{\mathcal{B}}\) 采样，不扭曲分布，但在密集错误集上需要发现指数级多的错误序列后才能正确调整概率，效率接近拒绝采样；（3）后验估计方法（FUDGE、SMC Steering、Ctrl-G）：在约束违反概率不依赖前缀的场景中表现差。
核心问题¶
如何在LLM受约束生成中平衡两个冲突目标：（1）生成的输出分布尽可能接近理想的无错误分布 \(P^{\mathcal{B}}\)；（2）推理计算成本可控？特别是在"密集错误集"场景中（每个token都有非零错误概率，长序列几乎必然包含错误）。
方法详解¶
整体框架¶
AprAD的核心洞察：约束生成和ASAp可以统一理解为"遇到错误后的回退策略"——约束生成复用几乎全部序列（仅回退一个token），ASAp完全不复用（从头采样）。自然的中间方案是复用一部分序列。关键问题变成"复用多少？"——太多导致概率放大，太少浪费计算。投机解码的前缀选择算法恰好提供了完美的自适应回退策略。
关键设计¶
- 投机采样作为回退策略: 当从 \(P^B\) 采样到违反序列 \(x\) 时，计算更新后的分布 \(P^{B \cup \{x\}}\)。由于这两个分布通常非常接近，利用投机解码算法（SpecSample）确定保留 \(x\) 的多长前缀，使保留的前缀等价于从 \(P^{B \cup \{x\}}\) 采样。高熵情况下通常保留大部分前缀，低概率token处更容易回退——完美适配。
- Trie结构概率缓存: 用Trie数据结构高效维护已观察错误序列对概率分布的调整。每个Trie节点存储原始LLM概率和调整后的非归一化概率，通过AddBadSample过程沿路径反向传播调整。
- 概率放大的理论bound: 证明AprAD每次回退操作的概率放大因子至多为2（实际中通常远小于2），而约束生成的放大因子是无界的。引入超参数 \(h\) 可在约束生成（\(h=0\)）和ASAp（\(h \to \infty\)）之间连续调节。
损失函数 / 训练策略¶
无需训练，完全是推理时方法。核心超参数是投机采样中的接受概率比 \(r = P^{B\cup\{x\}}(x_i|x_{1...i-1}) / P^B(x_i|x_{1...i-1})\)。
实验关键数据¶
| 任务 | 指标 | AprAD | 约束生成 | ASAp | 无约束 |
|---|---|---|---|---|---|
| Lipogram(排除元音) | 质量评分(1-5) | 4.52 | 3.56 | 1.72 | 4.68 |
| Lipogram | 约束意图(1-3) | 2.84 | 2.32 | 2.36 | 1.00 |
| Lipogram | 生成比 | 4.20 | 1.00 | 321.00 | 1.00 |
| BigCodeBench-15B | Pass@1 | 0.26 | 0.22 | 0.26 | 0.21 |
| BigCodeBench-15B | 无幻觉率 | 0.98 | 0.93 | 0.98 | 0.83 |
| BigCodeBench-15B | 生成比 | 1.08 | 1.02 | 1.56 | 1.00 |
消融实验要点¶
- 仿真实验：AprAD的KL散度远低于约束生成，生成比远低于ASAp
- Lipogram实验中ASAp几乎无法在2000次模型调用内生成200个token（生成比高达321），而AprAD只需4.2的生成比
- 约束生成在lipogram中产生大量非ASCII字符和拼写错误（俄文字母替代），AprAD则通过选择合适的不含目标字母的词来满足约束
- BigCodeBench中，AprAD的任务性能接近ASAp，生成开销接近约束生成
亮点¶
- 优雅的算法洞察: 将投机解码从"加速推理"重新定义为"智能回退"，跨领域的技术迁移非常巧妙
- 概率放大bound: 理论证明每次回退至多2×放大，而约束生成是无界的——这个理论保证很有价值
- Lipogram实验的可视化对比: 生成"不含字母E的故事"时，AprAD写出流畅优美的文本，约束生成则产出满是乱码和西里尔字母替代的文本
局限性 / 可改进方向¶
- 在更密集的错误集上，AprAD仍有一定的概率放大
- 主要性能指标是生成比而非wall-clock时间（因为测试环境和优化差异导致时间测量不准确）
- 与搜索算法（如MCTS）的结合是一个有前景的未来方向
- 超参数 \(h\) 的自适应调节策略未深入探索
与相关工作的对比¶
与约束生成（如llama.cpp grammar、Outlines）相比，AprAD大幅降低概率放大。与ASAp相比，在密集错误集上效率提升数十到数百倍。与后验估计方法（FUDGE、Ctrl-G、SMC Steering）相比，AprAD不需要额外训练判别器或蒸馏HMM，且在约束违反概率不依赖前缀的场景中（如lipogram）仍然有效。AprAD填补了"低放大+高效率"的方法空白。
启发与关联¶
- 跨领域技术迁移的典范——投机解码→受约束生成
- 对任何需要满足约束的LLM应用（结构化输出、代码生成、安全过滤）都有实际价值
- 生成比这个指标比wall-clock时间更适合评估采样方法的计算效率
评分¶
- 新颖性: ⭐⭐⭐⭐ 投机解码到受约束生成的创造性迁移
- 实验充分度: ⭐⭐⭐⭐ 仿真+lipogram+代码生成三个层次，覆盖合成和真实场景
- 写作质量: ⭐⭐⭐⭐⭐ Running example贯穿全文，概率放大的图示清晰直观
- 价值: ⭐⭐⭐⭐ 实用的推理时约束满足工具