自回归语言模型的可处理层级控制

# 自回归语言模型的可处理分层控制

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

Antonio Vergari [email protected]  
Vaishak Belle [email protected]  
University of Edinburgh

###### 摘要

约束自回归大型语言模型（LLM）的生成是将语言模型集成到形式系统中的重要组成部分。在代码生成和数据生成等任务中（如程序合成），确保语言模型产生符合句法的有效输出是处理这些输出的前提条件。这些语言（例如SQL或JSON）通常被设计为LR(k)上下文无关文法。通过将LLM蒸馏为可处理的概率模型，可以引导和屏蔽其自回归生成过程，以纳入满足逻辑约束的概率，从而保证高质量且必定有效的输出。本文证明，对任何有限持续时间的LR(k)文法，其满足性可在多项式时间内计算，这比先前方法应用于此类文法所需的指数时间有了改进。这一结果使得LLM生成能够高效地被约束和引导，从而更好地满足形式句法约束。

## 1 引言

大型语言模型（LLM）的输出通常需要被解析并转换为结构化形式。在代码生成（Jiang等人，2026）、数据生成（Li等人，2024）以及结构化自然语言处理任务（Geng等人，2023）中，大型语言模型必须生成满足预定义形式语言的序列，以便后续任务处理。这些语言中有许多被设计为LR(k)语言，即能够使用移进-归约解析器解析的语言（Aho等人，2006）。对LR(k)语言进行分类的自动机类别是**确定下推自动机（DPDA）**（Knuth，1965）。因此，改进自回归文本生成，使其能够保证满足任意DPDA，对于将这些模型的输出用于形式系统至关重要。

即使被提示满足简单的分层约束，LLM也可能会失败，尤其是当这些约束偏离其训练分布时。在四个开源的LLM上（图1），我们发现这些模型始终未能生成满足简单上下文无关文法约束的文本——即生成一个简短的良好嵌套的方括号和尖括号序列，该语言称为Dyck-2语言（在Ebrahimi等人（2020）中讨论）。我们发现，当括号集合从更规范的`()[]`变为Dyck语言文献中较少出现的括号如`<>`和`{}`时，所有模型在生成良好类型和良好嵌套序列方面的表现都更差。尽管规范的Dyck-2语言出现在这些模型的语料中，但它们无法生成满足非规范但概念上等价约束的序列，如图1所示。这些模型无法可靠地生成满足此类约束的文本，这表明在需要LLM满足具有此类嵌套结构的更复杂语言的任务中，约束和引导生成是更广泛必要的。

请参见图注

图1：LLM无法满足简单的上下文无关约束。Llama 3.3（700亿参数）、Olmo 3.1（320亿参数）、Mistral Medium 3.5（1280亿参数）和DeepSeek V4 Pro（1.6万亿参数）被要求生成一个简短的Dyck-2示例（具有两种不同类型括号的平衡括号语言）。

当LLM生成文本时，它们会生成所有可能的下一个标记的概率分布，然后从中采样一个新标记。最近在约束自回归生成方面的成功工作通过屏蔽LLM生成的下一标记logits，以确保模型只能生成有效标记（Deutsch等人，2019；Dong等人，2025；Kuchnik等人，2023）。这种方法确保模型永远不会生成违反指定生成约束的序列。然而，约束序列剩余部分的概率并未被纳入立即下一个标记概率的估计中。未能纳入立即下一个标记决策的未来后果会导致整体序列生成质量较低（Loula等人，2025）。我们在Zhang等人（2023a）的基础上，通过将LLM蒸馏成一个可处理的概率模型（TPM）（Vergari等人，2019），在其中可以精确且准确地核算未来的约束概率质量，从而将下一标记决策的未来后果纳入考虑。这种方法先前已被用于在语言模型生成中强制执行确定有限自动机（DFA）约束（Zhang等人，2023b，2024）。DFA约束可以确保LLM生成符合任何指定**正则语言**的文本。正则语言可以描述对子字符串包含或排除的约束以及其他简单约束。它们无法强制执行计算上更复杂的**确定上下文无关语言（DCFL）**类别（Hopcroft和Ullman，1979），这类语言描述具有递归结构的语言。DCFL的例子范围从简单的语言（如嵌套括号）到复杂的编程语言（如HTML、C、SQL等）。为了确保满足任意DCFL，适当的约束自动机类别是确定下推自动机。本文记录了我们在可处理地约束和引导语言模型以满足DCFL方面的方法，我们称之为**PASTA-G**（用于可处理自回归生成的推下自动机引导）。PASTA-G修改自回归语言模型，以将整个序列的概率精确地纳入每个标记的概率分布中，从而改进复杂递归定义约束的生成。这样做，它能够保证满足DCFL约束。

## 2 先前工作

Zhang等人（2023a）描述了一种方法，使用蒸馏后的TPM来获取标记序列概率，从而引导自回归LLM的生成。与自回归LLM不同，TPM能够可处理地评估给定对将来标记的复杂长期约束（而不仅仅是生成中的立即下一个标记）的下一个标记概率。约束（表示为α）可以描述为序列上的布尔函数。满足这样一个约束可以描述为一个加权模型计数问题：满足布尔约束α的概率等于所有满足约束的序列（x₁:ₙ）的概率之和。
p(α) = Σ_{x₁:ₙ满足α} p(x₁:ₙ)

在自回归生成中，当已经生成了t-1个标记时，先前标记的概率p(x₁:t-1)是已知的。因此，我们关注在给定先前标记的情况下，满足约束α的**条件**概率，p(α | x₁:t-1)。这可以通过对所有可能的下一个标记的序列求和来计算：
p(α | x₁:t-1) = Σ_{xₜ ∈ V} p(xₜ | x₁:t-1) · p(α | xₜ, x₁:t-1)

其中V是词汇表。注意，p(α | xₜ, x₁:t-1)是给定到目前为止已经生成的所有标记（直到并包括xₜ）时未来满足约束的概率。因此，当我们考虑在时间步t选择特定xₜ时，我们允许模型基于该选择调整其未来概率。这是TPM方法的核心：这使得我们能够在每个时间步更新未完成序列满足约束的概率，从而将未来后果纳入对p(xₜ | x₁:t-1)的估计中。文献中，已将从概率模型（如隐马尔可夫模型（HMM））获得的后验概率纳入自回归生成称为**预测**。使用HMM的预测称为ϕₜ，因为可以使用前向-后向算法（Rabiner，1989）高效计算。对于时间步t和特定标记xₜ，我们计算：
p(α | xₜ, x₁:t-1) = p(xₜ, x₁:t-1 满足 α) / Σ_{x∈V} p(x, x₁:t-1 满足 α)

其中“满足α”指的是未完成的序列（包括迄今为止的所有标记）能够被完成以满足α。对于HMM，p(xₜ, x₁:t-1满足α)可以以对每个特定配对（xₜ, x₁:t-1）的常数时间计算，但需要遍历所有可能的词汇标记，导致每次计算需要词汇表大小的时间。使用我们的算法（作为推论2呈现），我们可以在常数时间内评估两个互补的p(α | xₜ, x₁:t-1)函数，从而允许以Q(|V| · n²)的时间完成完整序列生成，其中n是最大序列长度。

预测然后按如下方式与LLM概率混合：
p̃(xₜ | x₁:t-1) = (p_LLM(xₜ | x₁:t-1) · p(α | xₜ, x₁:t-1)) / Σ_{x∈V} (p_LLM(x | x₁:t-1) · p(α | x, x₁:t-1))

## 3 方法

我们将约束λ·p(α | xₜ, x₁:t-1)的评估视为在DPDA上使用HMM后验概率的问题。我们将HMM的状态集表示为Q = {q₀, q₁, ..., q_{|Q|-1}}，将栈符号集表示为Γ = {γ₀, γ₁, ..., γ_{|Γ|-1}}。我们将序列x₁:t中的概率质量在DPDA的配置（q, γ）上的分布计算为一个矩阵Mₜ，其中Mₜ[q][γ] = p(到达具有状态q和栈γ的配置，同时生成x₁:t)。此外，我们计算矩阵Fₜ，它给出了配置（q, γ）下完成序列以满足质量约束的概率：Fₜ[q][γ] = p(在给定配置（q, γ）下被栈终止约束完成的序列)。然后，p(α | xₜ, x₁:t-1) = (Mₜ · Fₜ)[q₀][γ₀]，其中·表示逐元素乘积（但初始配置固定为q₀和γ₀）。在论文中，我们展示了如何通过使用HMM的转移和发射概率以类似于HMM前向-后向的方式更新Mₜ和Fₜ，从而在O(n² · |Q|² · |Γ|)时间内评估这些矩阵，其中n是最大序列长度，|Q|是HMM状态数，|Γ|是DPDA栈符号数。这里重要的是，DPDA的栈大小在有限持续时间内是有界的。

## 4 理论结果

我们的主要理论贡献表明，对于任何LR(k)文法（它等价于DPDA）且有限生成持续时间，满足约束的概率可以在多项式时间内计算。更正式地：

**推论2** 对于任意DPDA A和序列长度n的上界，计算序列x₁:n由A生成的概率是一项可以在O(n² · |Q|² · |Γ|)时间内完成的任务，其中|Q|是A的状态数，|Γ|是其栈符号数。

这对比于现有方法（如Ctrl-G）的指数时间是一个改进，后者针对DPDA约束会因序列长度呈指数级扩展状态空间。

## 5 实验

我们在Dyck-1（一种括号的平衡括号语言）和Dyck-2（两种括号的平衡括号语言）上评估了PASTA-G。我们使用一个简单的HMM（|Q|=2，|Γ|={'('，')'}用于Dyck-1；|Q|=2，|Γ|={'('，')'，'[',']'}用于Dyck-2）以及一个蒸馏后的GPT-2模型（Radford等人，2019）。我们比较了PASTA-G与以下基线：1）无条件GPT-2生成；2）使用Ctrl-G（掩码）方法；3）使用PASTA-G的预测引导。

结果（图3）显示，PASTA-G生成的序列始终满足约束（满足率达到100%），而标准GPT-2和Ctrl-G在较长序列上的失败率增加。Ctrl-G也满足约束，但生成序列的困惑度更高，意味着整体质量较低。PASTA-G在保持高似然的同时满足约束。

## 6 计算复杂度

我们与Ctrl-G进行了复杂度比较，Ctrl-G将DPDA转换为确定性有限自动机，方法是将所有可能的栈配置展开为显式状态。这导致状态集大小随序列长度呈指数增长：对于Dyck-1，展开的DFA状态数为O(2^{n})。PASTA-G通过保持栈隐式（存储在每个配置的概率中）避免了这一点，导致O(n²)时间和O(n)空间复杂度（相对于最大序列长度）。

具体地，对于Dyck-1，我们使用一个HMM（状态集Q={q₀,q₁}，栈符号集Γ={'('，')'}）。对于每个生成步骤t，我们更新Mₜ（大小|Q|×(H+1)，其中H≤n/2）和Fₜ（相同大小）。这导致每个时间步的更新复杂度为O(|Q|²·H²)，整体O(n·H²)=O(n³)，但通过利用HMM结构可以降低到O(n²)。Ctrl-G的复杂度为O(2ⁿ)（时间和空间）。图4显示了指数对比多项式增长。

## 7 相关工作

在Loula等人（2025）中，通过使用顺序蒙特卡罗方法，将总序列概率纳入自回归下一标记决策以实现上下文无关文法满足。该方法在多种语言上展示了令人印象深刻的结果。然而，它没有使用TPM所提供的可处理边缘化，这意味着该方法将依赖大量粒子才能收敛。它确实表明，基于logits的引导可以可测量地提高复杂真实世界代码和数据约束生成任务中的生成质量。

Baiget等人（2026）采用了类似的方法来整合TPM和上下文无关文法，尽管没有使用LLM。他们通过将文法编译成一个可处理概率电路（PC）（Darwiche，2003；Vergari等人，2019；Choi等人，2020）来处理此任务，该电路可以在文法的观察示例上训练。PC是HMM和其他TPM的推广，并已被广泛用于可处理的神经符号计算（Ahmed等人，2022）。PASTA-G使用一个预先存在的TPM（一个HMM）并动态组合其参数，以可处理地估计序列中每个元素在自回归中的概率。理想情况下，我们可以使用Baiget等人（2026）相同的编译策略（该策略具有三次复杂度），来获得一个编码上下文无关文法的PC，并使其与HMM可处理地相乘，以得到我们的算法（Vergari等人，2021）。然而，这将需要额外的内存和计算开销用于乘法。我们的方法相对于Baiget等人（2026）使用的另一个优势是：当文法改变时，PASTA-G不需要重新蒸馏可处理概率模型，并且PASTA-G的HMM对于生成到固定序列持续时间的文法没有参数数量的上界。

## 8 未来研究方向

### 8.1 分词

将PASTA-G应用于大型语言模型的一个限制是LLM分词器与DPDA假定的分词之间的不对齐问题。这种不对齐的第一个问题是，LLM分词器可能会拆分DPDA的标记，从而破坏此方法所需的确定性。另一个问题是，DPDA的标记可能会拆分LLM的规范序列分词。例如，大多数英语单词序列的确定上下文无关文法表示假定空格是与单词分开的标记，而LLM中使用的大多数字节对编码分词器会将单词和空格合并。这些分词不对齐需要在将PASTA-G应用于更多样化的语言时加以解决。

### 8.2 其他未来研究方向

任何可以使用确定数量的向前看符号进行确定解析的语言都是确定上下文无关语言，并且可以使用DPDA进行解析（Knuth，1965）。自动将比本文处理的更复杂的DCFL转换为DPDA可能是一个有成效的未来研究方向。这样做将使PASTA-G能够轻松地应用于任意DCFL。将此工作扩展到其他形式自动机是一个开放的未来研究方向。将PASTA-G的方法应用于非确定下推自动机将生成更强大的语言，并具有精确满足保证。类似地，为更强大的自动机（如嵌套栈自动机）创建类似PASTA-G的方法，将使其能够应用于上下文敏感语言。大多数自然语言是“轻度上下文敏感的”（Shieber，1985；Michaelis，1998），一些编程语言也是如此（例如Python，Laurent和Mens，2016）。将精确概率推理扩展到轻度上下文敏感语言的约束生成，可以改进自回归代码和语言生成。最后，我们的方法可以与Baiget等人（2026）的方法混合，通过将HMM作为概率电路层嵌入到LLM（Grivas等人，2026）中，该层编译一个上下文无关文法。

## 参考文献

- K. Ahmed, S. Teso, K. Chang, G. Van den Broeck, and A. Vergari (2022) Semantic probabilistic layers for neuro-symbolic learning. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA. ISBN 9781713871088. 被引用: §7 (https://arxiv.org/html/2607.20483#S7.p2.1).
- A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman (2006) Compilers: principles, techniques, and tools (2nd edition). Addison-Wesley Longman Publishing Co., Inc., USA. ISBN 0321486811. 被引用: §1 (https://arxiv.org/html/2607.20483#S1.p1.2).
- A. Baiget, J. Maene, S. Lee, B. Wang, G. V. den Broeck, and M. Kim (2026) ExplainFuzz: explainable and constraint-conditioned test generation with probabilistic circuits. arXiv:2604.06559, Link (https://arxiv.org/abs/2604.06559). 被引用: §7 (https://arxiv.org/html/2607.20483#S7.p2.1), §8.2 (https://arxiv.org/html/2607.20483#S8.SS2.p2.1).
- Y. Choi, A. Vergari, and G. Van den Broeck (2020) Probabilistic circuits: a unifying framework for tractable probabilistic modeling. Technical report, University of California, Los Angeles (UCLA). Link (http://starai.cs.ucla.edu/papers/ProbCirc20.pdf). 被引用: §7 (https://arxiv.org/html/2607.20483#S7.p2.1).
- A. Darwiche (2003) A differential approach to inference in bayesian networks. Journal of the ACM (JACM) 50, pp. 280–305. 被引用: §7 (https://arxiv.org/html/2607.20483#S7.p2.1).
- D. Deutsch, S. Upadhyay, and D. Roth (2019) A general-purpose algorithm for constrained sequential inference. In Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), M. Bansal and A. Villavicencio (Eds.), Hong Kong, China, pp. 482–492. Link (https://aclanthology.org/K19-1045/), Document (https://dx.doi.org/10.18653/v1/K19-1045). 被引用: §1 (https://arxiv.org/html/2607.20483#S1.p4.1).