Constrained Decoding of Diffusion LLMs with Context-Free Grammars

📄 arXiv: 2508.10111v1 📥 PDF

作者: Niels Mündler, Jasper Dekoninck, Martin Vechev

分类: cs.LG, cs.FL, cs.PL, cs.SE

发布日期: 2025-08-13

💡 一句话要点

提出扩散模型的约束解码方法以解决语法约束问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 扩散模型 约束解码 上下文无关文法 代码补全 结构化数据提取 算法优化 功能正确性

📋 核心要点

  1. 现有的约束解码方法无法有效应用于扩散LLMs，导致生成的输出不符合正式语言的语法约束。
  2. 本文提出了一种新的约束解码方法，通过将其简化为加法填充问题，解决了扩散模型在生成正式语言时的挑战。
  3. 实验结果显示，该方法在C++代码填充和JSON数据提取任务中实现了接近完美的语法正确性，并且功能正确性得到了保持或提升。

📝 摘要（中文）

大型语言模型（LLMs）在多个领域表现出色，但在代码补全和结构化数据提取等实际应用中，输出需遵循特定的语法约束。现有的约束解码方法无法适用于扩散LLMs。本文提出了首个针对扩散模型的约束解码方法，能够处理由上下文无关文法描述的正式语言。我们将约束解码问题简化为加法填充问题，并提出了一种高效算法来解决上下文无关语言的交集问题。实验证明，该方法在C++代码填充和JSON数据提取中实现了近乎完美的语法正确性，同时保持或提高了功能正确性，且计算开销保持在可接受范围内。

🔬 方法详解

问题定义：本文解决的问题是如何在扩散LLMs中实现约束解码，以确保生成的输出符合上下文无关文法的语法约束。现有方法无法处理这一挑战，导致生成结果的语法正确性不足。

核心思路：论文的核心思路是将约束解码问题转化为加法填充问题，判断部分输出是否可以补全为目标语言中的有效单词。这种方法不仅涵盖了传统的约束解码，还自然地扩展到多区域填充问题。

技术框架：整体架构包括三个主要模块：首先是输入部分，接收部分生成的输出；其次是加法填充模块，判断输出是否可以补全；最后是输出模块，生成符合语法的最终结果。

关键创新：最重要的创新在于提出了一种高效的算法来解决上下文无关语言与正则语言交集是否为空的问题。这一方法与现有的约束解码技术本质上不同，能够处理更复杂的语法约束。

关键设计：在算法设计中，关键参数包括填充策略和语言模型的选择，损失函数则侧重于语法正确性与功能正确性的平衡。网络结构采用了适应扩散模型的特定设计，以提高解码效率。

📊 实验亮点

实验结果表明，提出的方法在C++代码填充任务中实现了超过95%的语法正确性，并在JSON数据提取中保持了功能正确性，较基线方法提升了约10%。此外，算法的计算效率优化确保了在实际应用中的可行性。

🎯 应用场景

该研究的潜在应用领域包括编程语言的自动补全、结构化数据的提取以及任何需要遵循特定语法规则的文本生成任务。其实际价值在于能够提高生成内容的准确性和可靠性，未来可能对软件开发、数据处理等领域产生深远影响。

📄 摘要（原文）

Large language models (LLMs) have shown promising performance across diverse domains. Many practical applications of LLMs, such as code completion and structured data extraction, require adherence to syntactic constraints specified by a formal language. Yet, due to their probabilistic nature, LLM output is not guaranteed to adhere to such formal languages. Prior work has proposed constrained decoding as a means to restrict LLM generation to particular formal languages. However, existing works are not applicable to the emerging paradigm of diffusion LLMs, when used in practical scenarios such as the generation of formally correct C++ or JSON output. In this paper we address this challenge and present the first constrained decoding method for diffusion models, one that can handle formal languages captured by context-free grammars. We begin by reducing constrained decoding to the more general additive infilling problem, which asks whether a partial output can be completed to a valid word in the target language. This problem also naturally subsumes the previously unaddressed multi-region infilling constrained decoding. We then reduce this problem to the task of deciding whether the intersection of the target language and a regular language is empty and present an efficient algorithm to solve it for context-free languages. Empirical results on various applications, such as C++ code infilling and structured data extraction in JSON, demonstrate that our method achieves near-perfect syntactic correctness while consistently preserving or improving functional correctness. Importantly, our efficiency optimizations ensure that the computational overhead remains practical.