通过有限自动机的有效推理对扩散语言模型进行约束解码

约束解码对于服务 LLM 至关重要，确保生成的输出遵循特定结构，例如 JSON 模式格式的函数调用。现有系统是为自回归模型设计的，并假设从左到右生成，在每一步屏蔽掉无效的下一个标记。然而，扩散语言模型打破了这一假设：它们在每个去噪步骤中从完全分解的平均场分布中同时采样多个位置。在本文中，我们提出了一种精确且易于处理的算法，用于在任何可表示为有限自动机的约束下从受约束的平均场后验中进行采样。将有限自动机视为图形模型，我们获得了约束分布的易于处理的表示，从而实现了有效的推理。该方法通过构造保证约束满足，支持贪婪和基于采样的解码，并且与任意重掩码计划下的并行和分块解码兼容。应用算术电路理论中的深度减少技术，我们进一步将序列长度上的采样深度从线性减少到对数。对 Dream-7B 和 LLaDA-8B 的实证评估显示，各种任务的准确性都有显着提高，包括函数调用（xLAM、BFCL）、规划（数独、倒计时）、文本到 SQL（Spider）和数学推理（GSM-Symbolic），相对于无约束解码，推理开销很小。例如，在 BFCL-Live 上，我们的方法将 Dream-7B 的贪婪解码精度从 63.9% 提高到 71.5%，将随机采样精度从 22.3% 提高到 69.0%，其中无约束基线崩溃，挂钟开销低于 5%。