形式化思维编织

# 形式化思维之织：技术报告

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

###### 摘要

大型语言模型（LLMs）在代码生成方面展现出显著的表层流畅性，但它们既不能正式保证输出的语法有效性，也通常不利用目标语言定义的层次化结构。虽然现有的约束解码框架（如 XGrammar、Guidance、Outlines、SynCode）为前者提供了解决方案，但它们主要在刚性假设下运行，排除了现代解析器依赖的关键词法机制——包括上下文相关词法分析（如 Python 缩进）、最大匹配分词和关键词提取——并且仅近似屏蔽无效子词词元，牺牲了完备性。对于后者，现代代码 LLMs 通过预定策略在训练期间注入语法结构，而不是学习暴露哪些结构信息。在这项工作中，我们介绍了**形式化思维之织**（WoFT），一个统一严谨语法验证与学习到的结构化表示的总体范式。首先，我们提出了一个形式化引擎和约束解码器，它对于完整的 Tree-sitter 规范是可靠且完备的，通过用新颖的**推测性词法分析**构造增强广义 LR（GLR）解析，该构造维护与 GLR 图结构栈同步的并发词法分析器状态假设；解码器接受每个能扩展为有效程序前缀的子词词元，拒绝每个不能的。其次，我们提出了一种潜在变量微调方法，训练语言模型将非终结语法符号直接交织到生成过程中。利用重加权唤醒-睡眠（RWS）算法优化表层文本的重要性加权证据下界（IW-ELBO），模型学会选择性地保留形式派生作为自适应结构草稿本。对于 Python，使用我们的 RWS 目标微调 StarCoder2-3B 将每个词元的交叉熵相对降低了 14.3%（与仅文本 SFT 基线相比），表明任意性潜在语法恢复了平坦自回归训练丢弃的关键结构信息。我们的代码和实现公开在 https://github.com/alexbouayad/formal。

## 1 引言

现代基于代码训练的自回归大型语言模型（LLMs）展现出显著的表面流畅性：它们以如此高的保真度重现惯用语法、标识符约定和库特定模式，以至于生成的文本平均而言在统计上与人类编写的程序无法区分。然而，这种能力在两个不同意义上都是脆弱的。首先，流畅性不等于形式正确性：即使最先进的代码模型也会以非平凡的概率产生无法解析、类型检查或编译的输出，这就需要下游过滤或修复流水线，其成本随目标规范的严格程度而增长。其次，更根本的是，模型无法*显式*访问*定义*语言的层次结构。每个程序对应一个唯一、有限且数学上严谨的抽象语法树（AST）派生；这个派生正是让模型能够在编写函数体之前规划函数、在首次使用循环变量之前分配它，或在打开新作用域之前关闭当前作用域所需的信息。标准自回归训练将文本和结构的联合分布坍缩到仅文本的边缘分布上，迫使模型在每个前向传递中隐式地*重新发现*这种层次结构。

最近向语言模型中注入显式推理的尝试大多朝着相反方向进行。思维链（CoT）提示（Wei 等人，2022 (https://arxiv.org/html/2606.25987#bib.bib4)）及其内部变体——暂停词元（Goyal 等人，2024 (https://arxiv.org/html/2606.25987#bib.bib63)）、Quiet-STaR（Zelikman 等人，2024 (https://arxiv.org/html/2606.25987#bib.bib48)）和连续潜在推理（Hao 等人，2025 (https://arxiv.org/html/2606.25987#bib.bib8)）——为模型提供额外的中间计算，但推理轨迹本身要么是自由形式的自然语言，要么是无约束的潜在向量。两者都没有提供能够拒绝错误推理步骤的验证器，并且都不符合编程语言已经提供的离散、层次化结构。语义规划差距因此是一个神经符号差距：目标语言的结构存在，形式上且明确无误，但在训练时间或解码时间都未被利用。

并行的工作线——约束解码——通过在每个步骤将词汇表屏蔽为与部分解析一致的词元来攻击问题的正确性方面（Scholak 等人，2021 (https://arxiv.org/html/2606.25987#bib.bib44)；Willard 和 Louf，2023 (https://arxiv.org/html/2606.25987#bib.bib39)；Ugare 等人，2025 (https://arxiv.org/html/2606.25987#bib.bib62)；Dong 等人，2025 (https://arxiv.org/html/2606.25987#bib.bib70)；Li 等人，2026 (https://arxiv.org/html/2606.25987#bib.bib71)；guidance-ai，2025 (https://arxiv.org/html/2606.25987#bib.bib33)，2023 (https://arxiv.org/html/2606.25987#bib.bib20)）。这些引擎已将结构化生成延迟降低到接近无约束解码的水平，但其形式覆盖范围滞后于实践者实际希望生成的语言。

为了弥合这一神经符号差距，我们引入了**形式化思维之织**（WoFT），一个统一严谨语法验证与学习到的结构化表示的总体范式。WoFT 通过两个互补组件运作：一个形式推理引擎（比喻为“织机”）和一个潜在变量微调方法（“织工”）。首先，我们提出了一个与语言模型无关的形式引擎和约束解码器，它对于完整的 Tree-sitter 规范（Tree-sitter 贡献者，2026 (https://arxiv.org/html/2606.25987#bib.bib66)）是可靠且完备的。通过用推测性词法分析构造增强广义 LR（GLR）解析（Tomita，1987 (https://arxiv.org/html/2606.25987#bib.bib65)），我们的引擎维护与 GLR 图结构栈同步的并发词法分析器状态假设。这种方法原生支持上下文相关词法分析（如 Python 缩进）、最大匹配分词和声明式歧义消解。结果解码器接受每个能扩展为有效程序前缀的子词词元，拒绝每个不能的。其次，我们引入了一种潜在变量微调方法，训练语言模型将非终结语法符号直接交织到生成过程中。我们不强制模型发射固定、确定性的语法轨迹，而是将形式派生视为离散潜在变量。我们使用重加权唤醒-睡眠（RWS）算法（Bornschein 和 Bengio，2015 (https://arxiv.org/html/2606.25987#bib.bib54)）训练模型，以优化表层文本的重要性加权证据下界（IW-ELBO）（Burda 等人，2016 (https://arxiv.org/html/2606.25987#bib.bib28)）。这使模型能够利用形式非终结符作为自适应结构草稿本，仅在它们有效压缩未来表层词元时保留它们。实验上，在 Python 上使用我们的 RWS 目标微调 StarCoder2-3B（Lozhkov 等人，2024 (https://arxiv.org/html/2606.25987#bib.bib58)）相比标准仅文本 SFT 基线，实现了 14.3% 的表面词元交叉熵相对降低，表明任意性潜在语法恢复了平坦自回归训练丢弃的关键结构信息。我们的完整实现，包括形式引擎和 RWS 训练流水线，公开在 https://github.com/alexbouayad/formal。

本文的其余部分组织如下。第 2 节 (https://arxiv.org/html/2606.25987#S2) 回顾约束解码、语言建模中的潜在结构和内部推理的相关工作。第 3 节 (https://arxiv.org/html/2606.25987#S3) 详细描述了我们形式引擎的设计和理论保证。第 4 节 (https://arxiv.org/html/2606.25987#S4) 介绍我们的潜在变量公式、RWS 优化目标和训练架构。第 5 节 (https://arxiv.org/html/2606.25987#S5) 详细说明我们的实验设置，并报告表面词元建模的实证结果。最后，第 6 节 (https://arxiv.org/html/2606.25987#S6) 总结我们的研究愿景和后续步骤。

## 2 相关工作

### 2.1 约束解码与形式文法

约束解码在自回归生成过程中进行干预，以确保语言模型输出满足形式语言规范，通常通过在每个步骤将模型的词汇表屏蔽为仅接受与部分解析一致的词元。PICARD（Scholak 等人，2021 (https://arxiv.org/html/2606.25987#bib.bib44)）引入了用于 SQL 的增量解析器引导解码；Outlines（Willard 和 Louf，2023 (https://arxiv.org/html/2606.25987#bib.bib39)）和 SynCode（Ugare 等人，2025 (https://arxiv.org/html/2606.25987#bib.bib62)）通过将文法分别编译为有限状态机和下推自动机，并离线预计算每个词元的掩码，将这种方法推广到任意正则和上下文无关语言。

最近的引擎将这些想法推向生产级延迟。XGrammar（Dong 等人，2025 (https://arxiv.org/html/2606.25987#bib.bib70)；Li 等人，2026 (https://arxiv.org/html/2606.25987#bib.bib71)）将词汇表划分为上下文无关和上下文相关子集，以在字节级 Earley（Earley，1970 (https://arxiv.org/html/2606.25987#bib.bib15)）和下推自动机识别器之上分摊解码步骤间的掩码构建。Guidance（guidance-ai，2023 (https://arxiv.org/html/2606.25987#bib.bib20)）及其 Rust 后端 LLGuidance（guidance-ai，2025 (https://arxiv.org/html/2606.25987#bib.bib33)）将基于导数的解析直接融合到解码循环中。

一条互补的工作线将子词词汇表与形式语言词素之间的不匹配确定为正确性失败的主要原因。DOMINO（Beurer-Kellner 等人，2024 (https://arxiv.org/html/2606.25987#bib.bib14)）通过将离线预计算与推测解码相结合，显式解决了这一差距，以子词对齐的方式强制约束，在正则表达式和 CFG 边界目标上实现接近零开销。我们同意 DOMINO 的诊断，但在编译器栈中高一层操作：不在融合的正则表达式/CFG 状态机内推测子词序列，而是维护多个并发词法分析器状态以及广义 LR（Tomita，1987 (https://arxiv.org/html/2606.25987#bib.bib65)）图结构栈。这保留了形式词素粒度上的独立、成熟的词法分析器，并支持无扫描器引擎无法表达的有状态词法行为。

我们的形式引擎完全集成到 Tree-sitter 框架（Tree-sitter 贡献者，2026 (https://arxiv.org/html/2606.25987#bib.bib66)）中，保留其完整的文法规范语言及其编译器级词法分析器。我们通过维护 GLR 图结构栈上的一组有限推测性词法分析路径来解决子词对齐问题：每条路径对应一个与已发射子词词元一致的活跃词法分析器状态假设，并且一个词汇词元被接受当且仅当至少一条路径可以扩展为语言中的有效前缀。第 3 节 (https://arxiv.org/html/2606.25987#S3) 形式化此构造；在 Tree-sitter 文法的标准良构假设下，产生的解码器对于完整 Tree-sitter 规范是可靠且完备的。

### 2.2 语言建模中的潜在结构

将显式句法结构集成到语言建模中在自然语言处理领域有着悠久的历史。早期结构化语言模型（Chelba 和 Jelinek，1998 (https://arxiv.org/html/2606.25987#bib.bib7)；Roark，2001 (https://arxiv.org/html/2606.25987#bib.bib53)；Charniak，2001 (https://arxiv.org/html/2606.25987#bib.bib5)）表明，将下一个词元预测条件化为部分解析树可以提高困惑度。随着深度学习的出现，像递归神经网络文法（RNNGs）（Dyer 等人，2016 (https://arxiv.org/html/2606.25987#bib.bib52)）和潜在概率上下文无关文法（PCFGs）（Kim 等人，2019 (https://arxiv.org/html/2606.25987#bib.bib30)）等框架试图将这些句法树作为潜在变量处理。这些模型通过使用动态规划（例如内外算法）对所有可能的树结构进行边缘化，来优化观察文本的边缘似然。虽然理论优雅，但这些历史上的潜在结构模型面临计算扩展限制。对解析树进行精确边缘化随序列长度呈三次方扩展（O(N³)），使其对现代 Transformer 的大词汇量和上下文窗口在计算上不可行。因此，标准语言建模范式放弃了显式潜在句法结构，完全依赖自注意力机制来隐式学习代码和文本的平坦表示。

更近期的工作将内部推理进一步推入潜在空间。Coconut（Hao 等人，2025 (https://arxiv.org/html/2606.25987#bib.bib8)）将离散思维链词元替换为作为输入嵌入反馈的连续隐藏状态向量，允许模型同时编码多个替代推理步骤，并对推理路径进行广度优先搜索。虽然这规避了自然语言推理的文本连贯开销，但产生的潜在向量是连续的，没有符号语义；它们不能被外部验证器验证、解释或组合。我们的框架在设计空间中占据一个互补的点：潜在变量是从形式文法中抽取的离散非终结符，每个潜在轨迹都通过 Tree-sitter GLR 预言机验证。这用符号基础、层次可解释性和数学上将推理轨迹约束为有效 AST 派生的能力，换取了 Coconut 的连续几何。

我们为自回归 Transformer 现代化了潜在结构语言建模的历史目标。不尝试在广阔子词空间上进行精确边缘化，而是利用 Tree-sitter 作为符号预言机。通过将形式抽象语法树（AST）派生建模为通过重加权唤醒-睡眠（RWS）算法训练的离散潜在变量，我们的模型学会优化终结符序列的重要性加权证据下界（IW-ELBO）。这使得语言模型能够显式利用层次语法，而无需早期结构化模型的 O(N³) 瓶颈。

### 2.3 内部思维链与推理

标准思维链（CoT）提示（Wei 等人，2022 (https://arxiv.org/html/2606.25987#bib.bib4)）通过分配额外的中间计算步骤（前向传递）来改进语言模型的语义规划，然后才产生最终答案。最近，有向内部或隐式推理的推动——允许模型在隐藏的草稿本中“思考”，该草稿本在最终输出中被省略。像暂停词元（Goyal 等人，2024 (https://arxiv.org/html/2606.25987#bib.bib63)）这样的技术插入虚拟词元以延迟生成，而 Quiet-STaR（Zelikman 等人，2024 (https://arxiv.org/html/2606.25987#bib.bib48)）