约束是图，而不是链：扩散语言模型的精确解码

扩散语言模型（dLLM）以任意顺序预测屏蔽位置，但它们的精确约束解码器仍然将约束编码为顺序语言，其状态必须跟踪位置之间每个未解决的依赖关系。对于关系约束，这种编码呈指数增长：对于同阶复制，每个有限自动机需要 $4^k$ 状态，确定性或非确定性，并且每个上下文无关语法的大小为 $2^{\Omega(k)}$，而相同关系的因子图的大小为 $O(k)$ 和一个 16 项峰值表。我们引入了 FactorDLM，这是一种免训练解码器，它将有限域关系表示为因子图，并且在每个去噪步骤中，通过变量消除精确地调节模型在该图上的平均场预测。然后，解码成本随着约束图的诱导宽度呈指数增长，约束图取代自动机大小作为控制参数。由于有限自动机是链形因子图，因此一个编译器将语法和非局部关系一起强制执行：在具有跨字段引用的 JSON 记录上，单独的模式自动机会使引用悬空，单独的关系因子会产生格式错误的 JSON，并且组合计划在这两个方面都有效，包括在可变长度的记录上。在九个关系基准和三个骨干网中，每个输出都以 0.4-6.9% 的投影开销满足每个声明的约束，其中无约束解码的有效率为 0-79%，并且编译后的投影回答重复查询的速度比具有 8 个并行工作器的 CP-SAT 快 13.6 倍。由于无模型规则解决了五个标准基准中的三个，因此我们构建了具有精确机会和固定模板底线的基准，在精确约束样本中进行选择击败了贪婪投影。哪种编码更便宜，顺序状态还是直接因素，取决于约束并且在解码开始之前是可计算的。