EPIC: 在上下文无关文法约束下的扩散语言模型高效并行推理

# EPIC：面向扩散语言模型在上下文无关文法约束下的高效并行推理

来源：https://arxiv.org/html/2606.00722

Hyundong Jin, Yo-Sub Han⋆  
延世大学，首尔，韩国  
{tuzi04 (https://arxiv.org/html/2606.00722v1/mailto:[email protected]), emmous (https://arxiv.org/html/2606.00722v1/mailto:[email protected])}@yonsei.ac.kr

###### 摘要

控制语言模型的输出对于确保结构有效性、可靠性以及下游可用性至关重要，扩散语言模型也不例外。近期扩散语言模型解码方面的进展已将输出控制从正则约束扩展至上下文无关文法（CFG）约束。然而，现有方法的运行速度可能比无约束解码慢四倍之多。更重要的是，它们在很大程度上削弱了扩散语言模型相对于自回归模型的一个关键优势——并行解码。这种减速源于顺序有效性检查在并行生成过程中引入了显著开销。我们提出了一种高效的CFG约束解码框架EPIC，以解决这一局限性。该方法通过结合词法记忆化、使用Earley风格解析而非确定性自动机的验证，以及用于并行提交的松弛兼容子集选择，提升了解码效率。它减少了重复的词法分析和验证开销，同时允许多个兼容令牌一起提交。在三个基准测试上使用四个模型的实验表明，我们的方法在保持CFG约束解码的语法和功能正确性的同时，使整体运行时间接近无约束解码。与现有的CFG约束解码方法相比，EPIC将相对推理时间减少了高达67.5%。我们的实现可在 https://github.com/hyundong98/EPIC-Decoding.git 获取。

EPIC：面向扩散语言模型在上下文无关文法约束下的高效并行推理  
Hyundong Jin, Yo-Sub Han⋆  
延世大学，首尔，韩国  
{tuzi04 (https://arxiv.org/html/2606.00722v1/mailto:[email protected]), emmous (https://arxiv.org/html/2606.00722v1/mailto:[email protected])}@yonsei.ac.kr

## 1 引言

受扩散模型在视觉领域成功应用的推动，将基于扩散的方法用于语言建模的兴趣日益增长（Ho 等，2020 (https://arxiv.org/html/2606.00722#bib.bib23); Sahoo 等，2024 (https://arxiv.org/html/2606.00722#bib.bib1); Nie 等，2026 (https://arxiv.org/html/2606.00722#bib.bib2)）。扩散语言模型（DLMs）通过迭代去噪而非自回归（AR）式的下一个令牌预测来生成文本；掩码扩散语言模型（MDLMs）通过反复细化部分掩码序列实现了这一范式。近期进展表明，MDLMs 可以扩展至大型语言模型（LLMs），使 DLMs 成为 AR 生成的一个有前景的替代方案（Sahoo 等，2024 (https://arxiv.org/html/2606.00722#bib.bib1); Nie 等，2026 (https://arxiv.org/html/2606.00722#bib.bib2)）。与严格从左到右生成令牌的 AR 模型不同，DLMs 可以并行更新多个位置，这提供了独特的延迟优势（Kim 等，2026 (https://arxiv.org/html/2606.00722#bib.bib22)）。

请参阅图注

图 1：先前 CFG 约束扩散解码中的瓶颈概览以及 EPIC 的相应组件。

尽管有这一优势，无约束的 DLM 解码对于代码、JSON 和分子字符串等结构化输出仍然不够可靠。由于多个位置可能被独立填充，所提议的令牌可能会违反令牌间的依赖关系，从而降低序列级别的一致性（Kang 等，2026 (https://arxiv.org/html/2606.00722#bib.bib21); Kim 等，2026 (https://arxiv.org/html/2606.00722#bib.bib22)）。此外，DLM 生成的非顺序性质使得解码过程中的语法检查复杂化。与自回归解码不同，DLM 解码必须推理部分填充的序列，这些序列中未解决的掩码可能出现在已生成令牌之间。这些挑战促使了面向 DLM 的文法约束解码。受这些挑战的驱动，近期工作已开始开发面向 DLM 的约束解码。Suresh 等人（2025 (https://arxiv.org/html/2606.00722#bib.bib3)）研究了正则约束下的 DLM 约束解码，其中有效性可以用有限自动机表示。在此基础上，Mündler 等人（2026 (https://arxiv.org/html/2606.00722#bib.bib4)）使用拒绝采样解码器将约束扩展至上下文无关文法（CFGs），我们将其作为当前最先进的基线方法。该基线检查在应用候选更新后，部分输出在目标文法下是否仍可完成。然而，每次检查都需要重复的词法分析、确定性有限自动机（DFA）构建与最小化，以及顺序的基于 CFG 的验证，引入了大量开销。这一开销限制了并行生成的优势，特别是当使用更少的去噪步骤、每步提议更多令牌时。

我们提出 EPIC，一个解码框架，旨在减少先前管线中的主要开销来源，如图 1 (https://arxiv.org/html/2606.00722#S1.F1) 所示。EPIC 在相似的部分输出间重用词法计算结果，直接在词法图上检查 CFG 兼容性而无需构建确定性有限自动机（DFA），并在精确验证前选择兼容的候选子集以恢复并行提交。这些组件共同减少了重复词法分析、DFA 构建和顺序验证的开销，使面向 DLMs 的 CFG 约束解码更加高效。

我们的主要贡献如下：

- • 我们识别了先前面向 DLMs 的 CFG 约束解码工作中的三个主要开销来源：重复词法分析、DFA 构建和顺序候选验证。
- • 我们提出了 EPIC，一个面向 DLMs 的 CFG 约束解码框架，通过词法记忆化、无 DFA 验证以及用于并行提交的松弛兼容子集选择，针对先前工作的主要开销进行了优化。
- • 我们建立了所提解码过程的正确性，并在涵盖代码、JSON 和 SMILES 的结构化生成基准上评估了其推理效率。

## 2 相关工作

我们假设读者具备正则语言、有限自动机、上下文无关文法（CFGs）、词法分析和 CFG 解析的基本知识，并请参阅附录 A (https://arxiv.org/html/2606.00722#A1) 获取形式化背景。由于 EPIC 直接针对扩散语言模型 CFG 约束解码的计算瓶颈，本节我们将重点放在最相关的工作线上，并将关于扩散语言模型、自回归约束解码和基于形式语言的生成的更广泛讨论推迟到附录 B (https://arxiv.org/html/2606.00722#A2)。

最相关的前期工作是 Mündler 等人（2026 (https://arxiv.org/html/2606.00722#bib.bib4)），它代表了当前面向 DLMs 的 CFG 约束解码最先进方法。他们将 CFG 约束解码表述为对部分输出的重复完成性测试。给定一个对带掩码的部分输出提议的更新，其解码器检查剩余掩码是否仍可被填充，使得最终输出被目标文法接受。当测试成功时，解码器接受并提交该更新；否则拒绝。他们通过构建一个表示更新后的部分输出可能完成的自动机，并检查其与 CFG 的兼容性来实现该测试。对于在拒绝预算内未完成的输出，他们使用一种填充过程产生语法有效的完成。我们采用相同的可完成输出标准，并专注于使其更高效。

该先前管线涉及三个主要开销来源。首先，语言模型产生令牌级输出，而 CFG 是定义在文法终止符（即词素）上的。因此解码器在文法检查前需要一个词法分析步骤。这一步并非微不足道，因为部分输出可能包含掩码。一个生成的令牌可以完成其左侧的词素，开始其右侧的词素，或者参与一个跨越一个或多个掩码的词素。先前工作通过构建一个可能的词素序列的 NFA 来处理这些歧义，但由于必须为每次更新重复这一过程，它成为了一个主要的运行时瓶颈。其次，从部分输出导出的自动机在 CFG 验证前被确定化和最小化。这种重复的 NFA 到 DFA 转换代价高昂，在最坏情况下需要指数级时间（相对于 NFA 状态数）。此外，随后与 CFG 的兼容性检查进一步增加了验证开销。先前工作通过搜索一个交集文法来检查 DFA 是否接受至少一个与 CFG 一致的完成。尽管作者即时计算了该文法，但其底层构造仍可能在 DFA 状态数上以三次方式增长，使得验证步骤代价高昂。最后，整体程序削弱了扩散并行性的优势，因为候选令牌是一个一个地检查和提交的。因此，即使 DLM 在单个去噪步骤中提议了多个令牌，约束解码器仍可能承担大部分顺序验证成本。

## 3 问题形式化

设 \(G=(V,\Sigma_{\mathrm{lex}},P,S)\) 为一个上下文无关文法，其中 \(\Sigma_{\mathrm{lex}}\) 是词素词汇表，即文法终止符的集合。目标约束语言因此是 \(L(G)\subseteq\Sigma_{\mathrm{lex}}^{*}\)。该词素词汇表不应与用于表示原始字符串的字节级字母表 \(\Sigma_{\mathrm{byte}}\) 混淆，也不应与扩散语言模型使用的分词器词汇表 \(\Gamma\) 混淆。一个部分模型输出表示为 \(x\in (\Gamma\cup\{\texttt{[MASK]}\})^{n}\)，其中 \(\texttt{[MASK]}\) 表示一个掩码。由于模型操作在分词器级序列上，而 CFG 定义在词素序列上，有效性检查需要一个词法接口。我们令 \(\Lambda\) 表示词法映射，它将令牌级部分输出 \(x\) 转换为兼容词素序列的正则或图表示。我们将此表示记为 \(\mathcal{A}_{x}\)，且有 \(L(\mathcal{A}_{x})\subseteq\Sigma_{\mathrm{lex}}^{*}\)。为方便起见，我们记 \(C_{x}:=L(\mathcal{A}_{x})\) 为由 \(x\) 引发的词素序列完成语言，并记 \(M(x):=\{i\in[n]\mid x_{i}=\texttt{[MASK]}\}\) 为掩码位置的集合。

在每个扩散步骤中，模型为掩码位置预测令牌分布。给定一个揭示预算 \(k\)，解码器选择掩码位置的一个子集 \(I=\{i_{1},...,i_{k}\}\subseteq M(x)\)，并并行地采样这些位置的分词器令牌：\(t_{i}\sim p_{\theta}(\cdot\mid x),\quad i\in I.\) 等价地，模型提议更新 \(\Delta=\{(i,t_{i})\mid i\in I\}.\) 将此更新应用于 \(x\) 得到一个新的部分输出，按位置定义为 \((x\oplus\Delta)_{j}=\begin{cases}t_{j}&\text{if }(j,t_{j})\in\Delta,\\ x_{j}&\text{otherwise.}\end{cases}\)

CFG 约束 DLM 解码中的核心问题是，这个令牌级更新是否保留了将剩余掩码补全成文法接受的词素序列的可能性。我们说一个部分输出 \(x\) 关于 \(G\) 是可完成的，如果 \(L(G)\cap C_{x}\neq\emptyset.\) 一个提议的更新 \(\Delta\) 在以下情况下是有效的：\(\textsc{Valid}_{G}(x,\Delta)=\mathbf{1}\left[L(G)\cap C_{x\oplus\Delta}\neq\emptyset\right].\) 这一定义给出了约束扩散解码的规则。如果 \(\textsc{Valid}_{G}(x,\Delta)=1\)，解码器可以提交提议的令牌。否则，该提议必须被拒绝。

先前的方法通过为 \(C_{x\oplus\Delta}\) 构建一个自动机并检查其与 CFG 的兼容性来评估该条件。我们的目标是在 DLM 解码引入的重复和并行设置中更高效地计算相同的有效性谓词。\(\Delta\) 的多令牌性质至关重要。在无约束的 DLM 解码中，所有 \(I\) 中的令牌可以在一次模型前向传播后同时提交。然而，在 CFG 约束下，朴素的解码器必须顺序测试提议的令牌：\((i_{1},t_{i_{1}}), (i_{2},t_{i_{2}}), \ldots, (i_{k},t_{i_{k}})\)，因为一个令牌的有效性可能取决于其他哪些令牌已被接受。这种顺序处理削弱了 DLM 的主要优势。因此，我们要解决的问题是对多个令牌更新进行高效的有效性检查，同时保持在词素序列上的精确可完成输出标准。

## 4 所提方法

我们提出 EPIC，一个面向 CFG 约束的高效并行推理解码框架。我们的方法由三个主要组件组成：词法记忆化、带有 Earley 风格解析的无 DFA 验证，以及用于并行提交的松弛兼容子集选择。每个组件针对先前工作中的不同开销来源。我们框架的概览如图 2 (https://arxiv.org/html/2606.00722#S4.F2) 所示。

请参阅图注

图 2：EPIC 概览。EPIC 结合了词法记忆化、无 DFA 的图解析器验证以及正则覆盖批量选择，以减少 CFG 约束扩散解码中的开销。

### 4.1 词法记忆化

第一个改进利用了词法分析中的局部性。尽管掩码引入了词法歧义，但每个歧义都由一个局部文本段及其相邻的掩码边界决定。在扩散解码过程中，一次更新只修改了序列的一小部分，而其余掩码位置保持不变。因此，连续的验证查询往往包含许多不变的局部词法上下文。我们因此对掩码相邻段可能的词法前缀和后缀进行记忆化。当相同的局部上下文再次出现时，我们在部分语言构造期间重用存储的词法结果。这避免了不变区域的重复词法分析，并降低了构建部分输出自动机或图的成本。

### 4.2 带有 Earley 风格解析的无 DFA 验证

下一个组件是无 DFA 验证。先前工作将词法分析后的部分输出表示为一个 epsilon-NFA（ENFA），然后在 CFG 验证前对其进行确定化和最小化。在此转换之后，验证检查自动机是否接受一条其词素序列可由 CFG 生成的路径。先前工作将此搜索实现为 CFG 非终止符和自动机状态对上的动态规划，类似于在有限自动机上的 CYK 风格识别（Younger, 1967 (https://arxiv.org/html/2606.00722#bib.bib15); Kasami, 1965 (https://arxiv.org/html/2606.00722#bib.bib16)）。然而，该管线在每个解码步骤都付出了 ENFA 到 DFA 转换的成本，并且这种自底向上的形式化在搜索过程中提供的自上而下指导有限。相反，对于精确验证，我们避免 ENFA 到 DFA 的转换，直接使用基于 Earley 风格的图解析器在 ENFA 上进行见证检查。该解析器将来自 ENFA 转换的自底向上证据与来自 CFG 的自上而下预测相结合。直观上，