💬 NLP

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

本文提出了一种通用方法，通过利用张量化有限自动机和电路乘法来构建可处理的全局约束提议，从而缓解局部约束解码中的偏差，进而实现高效的顺序蒙特卡洛采样，使其在函数调用和 SQL 生成等任务中能以更少的粒子更快地收敛至目标分布。

原作者： Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

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

想象一下，你正试图教一个非常有创意但有点混乱的讲故事者（大语言模型）去写一个必须遵循严格规则手册的故事，比如 JSON 代码格式或特定的 SQL 数据库查询。

问题在于，这个讲故事者喜欢漫游。如果你只是说“不要违反规则”，他们可能会开始一个看起来还算正常的句子，但到结尾时却变得无法正确完成。

以下是这篇论文如何通过简单的类比来解决这个问题的：

1. 旧的方法：“近视”向导 (LCD)

想象讲故事者正在迷宫中行走。旧的方法（称为局部约束解码或 LCD）就像是一个只看下一步的向导。

工作原理： 如果下一步看起来可能会撞到墙，向导就会将其阻挡。
缺陷： 这个向导是“近视”的（短视的）。他们可能会让讲故事者走上一条看起来在下一步很安全，但三步之后就会陷入死胡同的路。讲故事者继续走着，以为自己一切正常，直到最后才意识到自己无法在字数限制内完成故事。他们不得不重新开始，或者产生一个破碎的故事。

2. 新的方法：“全局地图” (GCD)

作者提出了一种名为全局约束解码 (GCD) 的新方法。

类比： 这个向导不再仅仅观察下一步，而是拥有一张完整的迷宫地图，并且确切知道距离到达出口还有多少步。
工作原理： 在讲故事者迈出一步之前，向导会检查：“如果你走这条路，你真的能在剩余的步数内到达出口吗？”
结果： 如果答案是“不”，向导会立即阻挡那条路径。这保证了无论讲故事者选择什么路径，他们始终能到达一个有效的终点。这就像拥有一个 GPS，它只显示那些能保证让你按时到达目的地的路线。

3. “聪明”的地图：加入概率 (P-GCD)

“全局地图” (GCD) 擅长避免死胡同，但它将所有有效路径视为同等对待。它并不知道讲故事者偏好哪条路径，或者哪条路径更有可能是一个好故事。

类比： 想象讲故事者有一种喜欢的走路方式。基础地图只是说：“这条路是有效的。”而新的概率性 GCD (P-GCD) 则说：“这条路是有效的，而且它也是讲故事者最可能喜欢的路径。”
工作原理： 作者将“全局地图”（规则）与“记忆模型”（讲故事者大脑的一个简化版本）结合起来。他们将两者相乘。
结果： 现在，向导不仅会阻挡坏路径，还会轻轻地将讲故事者引导向那些既有效又高质量的路径。这使得讲故事的过程更加高效。

4. “粒子”竞赛 (SMC)

为了测试这些方法，研究人员使用了一种称为顺序蒙特卡洛 (SMC) 的技术。

类比： 想象你正在试图寻找穿过迷雾森林的最佳路线。与其只派一个人，不如派出 100 个“粒子”（探险家）组成的集群。
旧的方法： 使用近视向导时，你需要派出成千上万的探险家，因为许多人会在完成任务前迷路或撞上死胡同。
新的方法： 有了“全局地图”和“聪明地图”的帮助，探险家们能保持在正确的轨道上。你只需要更少的探险家就能找到完美的路径，因为向导在早期过滤掉错误选项的能力非常出色。

5. “变形”技巧 (Tensorization)

这是论文中的一个技术突破之一，关于如何处理“地图”。

问题： 复杂的规则（如 JSON 模式）可能会创造出拥有数百万条路径的地图。通常，计算机在标准处理器上尝试绘制这些地图时会感到不堪重负。
解决方案： 作者将这些复杂的地图转化成了能够完美适配现代图形显卡 (GPU) 的数学块（张量/Tensors）。
类比： 这就像把一大堆乱七八糟的纸质地图折叠成一个紧凑、高速的数字芯片，让超级计算机可以瞬间读取。这使得“全局地图”即使对于非常复杂的规则，也能在眨眼之间完成计算。

结果总结

论文在三个现实任务上测试了这些方法：

函数调用 (Function Calling)： 确保 AI 以正确的格式（如 JSON）调用计算机函数。
关键词生成 (Keyword Generation)： 确保故事包含特定的词汇。
SQL 生成 (SQL Generation)： 编写语法正确的数据库查询。

结论：

可靠性： 新方法保证了故事能在字数限制内正确结束，而旧方法经常在终点线前失败。
效率： 为了获得相同质量的结果，新方法所需的“探险家”（粒子）数量显著减少。
速度： 虽然“聪明地图”（P-GCD）需要更多的计算能力，但它仍然足够快，足以投入实际应用；而“全局地图”（GCD）的速度几乎与旧方法一样快。

简而言之，这篇论文为 AI 提供了一张“全局地图”和一次“智能引导”，使其能够在遵循严格规则的同时，不会迷失方向、浪费时间或产生破碎的代码。

技术摘要：通过可解提议缓解局部约束解码中的偏差

问题陈述

大型语言模型（LLMs）经常无法生成严格遵守逻辑或结构约束（如 JSON 模式、有效的 SQL 查询或特定的函数调用格式）的输出。虽然指令微调和偏好优化改善了通用对齐，但对于强制执行“硬”约束而言，它们仍然不可靠。

现有方法面临两个主要局限性：

拒绝采样（Rejection Sampling）： 虽然是无偏的，但由于接受率极低，在处理复杂约束时计算上并不可行。
局部约束解码（Locally Constrained Decoding, LCD）： 这种标准方法在每一步都会屏蔽掉违反约束的 token。然而，它存在两个关键缺陷：
- 偏差（Bias）： 它通过在不考虑未来有效性的情况下进行近视式的屏蔽，扭曲了模型的底层分布，从而导致采样偏差。
- 无终止保证（No Termination Guarantee）： LCD 仅确保局部有效性。一个序列可能会在局部保持有效（例如，未闭合的 JSON 花括号），但在固定的 token 预算 $n$ 内无法满足约束。

为了解决这些问题，研究者提出了顺序蒙特卡洛（Sequential Monte Carlo, SMC）框架，使用 LCD 作为提议分布（proposal distribution），并通过重新加权粒子来收敛到目标分布。然而，SMC 的收敛速度受限于提议质量；LCD 是一个弱提议，因为它缺乏关于未来有效补全的概率信息，且无法保证在有限预算内满足约束。

方法论

作者提出了一种通用的方法，用于构建用于从约束分布 $p_{lm}(\cdot \mid C)$ 中进行 SMC 采样的可解提议和势函数（potential functions）。其核心创新在于将约束表示为有限自动机，并利用张量运算实现高效的 GPU 执行。

1. 全局约束解码 (GCD)

GCD 通过确保生成的每个 token 都能在剩余 token 预算 $n$ 内导向一个有效的补全，从而改进了 LCD。

张量化有限自动机（Tensorized Finite Automata）： 被编码为有限自动机（FA）的约束（特别是 NFA 和 DFA）被编译成张量化表示（转换矩阵 $T_{out}, T_{in}$ 和发射矩阵 $B_f$ ）。这使得在 GPU 上进行高效执行成为可能。
前向-后向推理（Forward-Backward Inference）：
- 前向过程： 计算在观察到前缀 $x_{1:t-1}$ 后可达到的 FA 状态集。
- 后向过程： 计算一个状态是否能在恰好 $n-t$ 步内到达接受状态。
全局屏蔽（Global Masking）： 只有当一个 token 能够导向一个在剩余预算内允许有效延续的状态时，该 token 才被允许。这保证了在 GCD 下生成的任何长度为 $n$ 的序列都满足约束 $C$ 。

2. 概率全局约束解码 (P-GCD)

虽然 GCD 保证了约束满足，但其掩码是二元的（有效/无效），并且忽略了 LLM 下有效补全的可能性。P-GCD 通过集成概率信息解决了这一问题。

HMM 蒸馏： 遵循前人工作（Zhang et al., 2023），LLM 的分布被近似为一个隐马尔可夫模型（HMM）。
电路乘法（Circuit Multiplication）： 将张量化 FA（视为边上的非归一化 HMM）与蒸馏后的 HMM 进行电路乘法。这利用了 FA 和 HMM 共享的代数结构。
乘积分布： 生成的乘积分布 $p_{prod}$ 既捕捉了 FA 的硬逻辑约束，又捕捉了 LLM 的概率偏好。
提议与势能：
- 提议 ( $q_{pgcd}$ )： 在每一步使用来自 $p_{prod}$ 的受约束的下一 token 概率对 LM 分布进行重加权。
- 势能 ( $\phi_{pgcd}$ )： 通过 LM 前缀概率和 HMM 对约束满足度的前瞻估计来对 SMC 中的粒子进行加权。

3. 高效实现

作者利用张量网络操作（特别是 Kronecker-vec 恒等式）来避免显式地实例化大型 Kronecker 积矩阵。这使得转换步骤的计算成本从 $O((HE)^2)$ 降低到 $O(H^2E + HE^2)$ ，其中 $H$ 是 HMM 隐藏层大小， $E$ 是 FA 边数，从而实现了高效的自回归生成。

核心贡献

GCD 和 P-GCD 框架： 引入了全局约束解码和概率 GCD，它们提供了可解的提议和势能，用于 SMC 采样，并保证在 token 预算内满足约束。
GPU 上的张量化自动机： 首次提出将有限自动机（包括 NFA）张量化，以实现高效的 GPU 原生推理，克服了现有框架（如 Outlines 和 XGrammar）受限于 CPU 的限制。
NFA 支持： 证明了对于复杂约束（例如带有变量参数的函数调用），NFA 可以比 DFA 更加简洁，这使得该方法能够扩展到现实世界的智能体应用场景，而在这些场景中，DFA 的构建可能会导致内存溢出。
与 SMC 的集成： 表明 (P-)GCD 与基于 LCD 的提议相比，显著加速了 SMC 的收敛，仅需更少的粒子即可达到目标分布。

实验结果

作者在三个基准测试上评估了 (P-)GCD：xLAM（函数调用）、CommonGen（基于关键词的生成）和 Spider（文本转 SQL）。

函数调用 (xLAM)：
- 在相同粒子数量下，(P-)GCD 取得了比 LCD 高得多的准确率。
- P-GCD 比 GCD 更快地收敛到地面真值分布（拒绝采样），凸显了概率信息的益处。
- 约束满足度： GCD 和 P-GCD 在所有粒子预算下都实现了 100% 的约束满足率，而 LCD 即使在适中预算下（例如 JSON 约为 95%）也无法满足约束。
- 效率： LCD 和 GCD 的开销较小（1.08× 和 1.10× 减速）。P-GCD 较慢（3.11× 至 10.2×），这是由于 HMM 计算引起的，但仍处于可行范围内。
关键词生成 (CommonGen)： 使用 P-GCD 同时作为提议和势能，其 BLEU 分数和收敛速度较 LCD 有显著提升。
文本转 SQL (Spider)： GCD 和 P-GCD 在各种粒子预算下，特别是在中等数值下，其执行准确率均优于 LCD。
NFA vs. DFA： 实验证实，对于复杂模式（例如变长函数参数），NFA 的规模呈线性增长，而 DFA 则呈指数级增长。对于 Spider SQL 语法，DFA 构建在 token 层面导致了内存溢出（OOM）错误，而 NFA 则保持了可处理性（约 32k 个状态）。

意义与主张

本文声称，局部约束解码会引入显著的采样偏差，并且无法保证在有限 token 预算内的约束满足。通过提出 (P-)GCD，作者提供了一个解决方案，该方案：

保证有效性： 确保生成的任何长度为 $n$ 的序列都满足约束，消除了 LCD 的失效情况。
减少偏差： 通过结合概率信息（通过 P-GCD）和全局前瞻，提议能更好地逼近目标条件分布。
提高效率： 在 SMC 框架中，(P-)GCD 比基于 LCD 的方法需要更少的粒子即可收敛到目标分布，从而降低了高质量约束生成的计算成本。

这项工作通过以 GPU 高效的方式统一逻辑约束（通过自动机）和概率建模（通过 HMM），为需要严格结构遵循的 LLM 应用（如函数调用和代码生成）提供了一个可靠的、满足约束的生成基础步骤。