GRID: 语法约束解码用于企业级SQL生成

# 面向企业SQL生成的语法约束解码  
本文的缩减版正在接受KDD 2027审稿。  
来源：https://arxiv.org/html/2607.11951  
（2026年7月）

###### 摘要

大型语言模型能够编写SQL，但企业部署对输出提出了更高要求：语法必须有效，必须遵守按角色和按模式的策略，必须提供可证明的（而非尽力而为的）保证，不能随着生成序列增长而变慢，并且必须为每个决策留下合规级别的记录。我们提出GRID（语法约束解码），这是一个语法约束解码引擎，其关键创新在于：它基于*解析器配置*（词法分析器扫描状态 × LALR(1)栈）而非令牌序列来构建精确的下一令牌掩码；使用递增推进的LALR(1)解析器本身作为可行前缀预言机；并通过字节级前缀树遍历来桥接LLM令牌与语法终结符，该遍历采用上下文无关/上下文相关分割，使得缓存键的正确性得以构造性保证。基于角色的访问控制被*编译进语言本身*：角色投影对语法产生式进行子集化，模式词库对标识符终结符进行限制，因此被禁止的动词和标识符在掩码层面便不可达。四个保证——正确性、完备性、终止性和近乎恒定的每令牌成本（需求R）——都附有明确的前提条件，并配有相应的测试或基准来验证。Rust内核将热服务的处理步骤降至每请求1.33微秒，每令牌掩码的中位数时间为3.6–6.7微秒——在两种基准测试的分词器上，p50和p90均优于llguidance，且无错误拒绝；而llguidance在p99上仍保持最平坦。在声明的H100 SXM5运行器上，vLLM下的端到端服务开销在批处理大小为32时，每输出令牌的时间增加1.51%，冷模式特化耗时27.3毫秒；一个新（未见过的）模式需要约0.7毫秒的首令牌延迟，随后以1.00倍热速度解码。一个v7内核将整个冷掩码缺失处理保留在Rust中（融合的遍历→blob→寄存器，单次GIL释放调用），在实际硬件上将热共租户的最差引擎步骤控制在15.3毫秒；唯一剩余的成本——新模式约0.66秒的特化窗口期间，同批次瞬态TPOT减速约34%——是冷遍历与引擎前向循环之间真实的主机CPU/内存带宽争用（随着遍历线程增加而缩小），这被标记为计算隔离的权衡（作为未来工作），而非缺陷。每令牌的防护成本在位置上是平坦的（在n=16,000处斜率≈0，所有嵌套深度）。在Spider上，约束解码在0.5B模型上带来了+13的执行准确率提升；在7B模型上，仅掩码便贡献了约+1个点，而对掩码无法强制执行的残留问题（列级策略）进行一次检查器引导的修复遍历，将执行准确率提升至94.5%，EX较无约束情况提升+2.3。基于哈希链的每令牌审计跟踪可以比特级精确回放（跨越缓存命名空间滚动的1000次生成；100%篡改检测）。我们诚实地说明了掩码无法做到的事情——分布保真度、列级RBAC、非LALR(1)语言——以及测量成本仍然存在的领域（冷前缀树遍历；服务冷窗口计算争用；一个经表征的、外生于GRID的引擎侧伪像）。

## 1 引言

我们关注的是，在企业CRUD/RBAC部署的运行条件下，从大型语言模型生成SQL（更一般地，任何LALR(1)可解析语言的句子）。在这种场景下，“模型通常能写出有效SQL”并非可接受的契约。以下六个问题必须*同时*解决，每个都塑造了我们的设计：

1. P1. 有效性与策略的联合。输出必须能在SQL方言下解析，*并且*符合按角色策略（允许的动词、禁止的子句）和按模式词汇表（仅限真实表名和列名）。策略不是事后过滤器：一个只能执行`select`的角色必须完全无法产生`delete`，标识符必须*通过构造*便是模式有效的。
2. P2. 可证明的保证。正确性（绝不发出会离开语言前缀集的令牌）、完备性（绝不阻止仍可能导向有效句子的令牌）和终止性（每个停止标记都是一个完整句子）必须是带有明确前提条件的定理，每个都配有相应的验证测试——而非测试套件的涌现属性。
3. P3. 平坦的每令牌成本（需求R）。每令牌的防护开销必须在当前输出长度n上摊销为O(1)（最坏情况由语法/嵌套常数决定，绝不受n影响），因此总防护成本在一个生成序列上为O(n)。一个每令牌成本随上下文增长的防护系统对于长生成序列是不可用的；§8.2展示了2023年的一个系统，其每令牌开销约为每位置增长1.19毫秒。
4. P4. 可重放的审计跟踪。在合规场景中，必须能在事后回答“在第t步，模型被允许说什么，以及为什么？”：一个基于哈希链的、包含每个令牌允许/阻止决策的记录，能够针对版本化的语法工件进行比特级精确重放。
5. P5. 服务现实。生产环境下的解码是批处理的，同批次请求的语法可能是异构的，并且新模式可能在热批次运行时到达。防护系统必须将掩码计算与GPU前向传播重叠，绝不能让一个请求的冷缺失导致同批次其他请求停滞（*冷模式混入热批次*问题），也绝不能为了满足截止时间而使用近似掩码。
6. P6. 不可强制执行残留的诚实边界。某些策略*可证明*无法被任何从左到右的上下文无关掩码强制执行——列级RBAC是典型情况（命题11）。系统必须明确划定此边界而非模糊处理，在解析后强制执行它，并且在模型能力足够时，将命名违规转化为检查器引导的修复循环。

GRID用一个核心架构思想及其推论来回答这些问题：*将所有关键信息建立在解析器配置上*。一个配置——词法分析器在部分词素上的扫描状态与LALR(1)解析器栈的配对——正是决定哪些后续动作可行的信息。掩码从配置计算得出，基于配置派生的键进行缓存（其正确性是有明确陈述的义务的，一种Myhill–Nerode风格的细化，见§4.3），并在滚动配置哈希下进行审计。因此，掩码成本跟踪的是*语法配置*，而非输出位置，这通过构造满足了需求R；§8中的基准测试在n=16,384的实际词汇表上验证了这一点。

#### 贡献。

（1）一个配置键控约束解码的形式化框架：将递增LALR(1)解析器作为可行前缀预言机，在表压缩下实现精确的EOS门控（§3）；一个字节级令牌↔终结符桥接，采用上下文无关/上下文相关分割，使缓存键的正确性得以构造性保证（§4）；缓存键正确性义务OBL-KEY1和标识符组合规则，以及最大化跨请求共享正确性的扫描器范式（§4.3）。（2）四个以命题形式陈述的保证，附带明确前提条件，包括诚实的负面结果——列级RBAC无法通过掩码强制执行（§5）。（3）实现该框架的系统——语法流水线、Rust内核（v4→v7，热服务步骤从7.39降至1.33微秒/请求，随后是v7融合的冷缺失路径）、双层写回掩码缓存、批处理异构解码的服务合约、以及基于哈希链的审计日志（§6）——附有工作示例（§7）。（4）一份承诺的基准测试记录：在两种分词器上，针对XGrammar、llguidance和Outlines的每令牌掩码延迟；需求R斜率测量；MaskBench；带检查器引导修复的Spider执行准确率；以及包括冷缺失压力测试臂的端到端vLLM服务记录（§8）。

#### 设计谱系。

最初的专利文件捕获了此设计的早期部分快照（v0.0.5，设计于2023年8月）：一个针对令牌序列（相对于下推自动机）的预计算有效性表，以及解码时的logit掩码。计划的迭代推动了设计向前发展：v0.0.6（2023年9月）在当时的扩展基准测试中已经优于2023年7月发布的guidance，而v0.0.7（2023年11月）——即本文描述的系统，也是最终专利申请所遵循的路线——用配置键替换了序列键，用前缀可行性替换了接受语义，添加了字节级令牌↔终结符桥接、写回缓存、RBAC/模式投影、审计链和检查器引导修复；此后工作一直在持续改进。§3-§4呈现了支撑两个关键修订的设计分析。该设计从已发表工作中汲取了灵感——特别是Willard和Louf的Outlines论文[1]，其在寄存器中对引导生成的有穷自动机形式化，本文有意识地进行了类似阐述——而GRID的设计和实现完全是我们自己的。

## 2 预备知识

#### 掩码解码。

令V为分词器词汇表，|V|=N，令Σ为字节字母表。一个自回归语言模型定义logits α = LM(s_1..t, θ) ∈ ℝ^N；引导生成在采样前应用一个掩码 m ∈ {0,1}^N，α̃ = m ⊙ α（实现为原地 masked_fill_(-∞)），并采样 s_{t+1} ~ Categorical(α̃)。每一步构造m是整个问题：朴素实现需要针对每个候选令牌、每一步对整个前缀进行解析，代价高昂。

#### 令牌是字节串。

每个令牌都有一个规范的拼写 bytes: V → Σ^*（token_bytes）：字节级BPE的unicode重映射被反转，SentencePiece/BPE的空格标记归一化为0x20，字节回退字面量<0xNN>映射到其字节。一个定义便服务于前缀树构建、快速路径和参考预言机。不同的令牌ID可能共享一个拼写（*别名类*）；掩码是针对ID，而非拼写。

#### 三个语法层，一种语言。

* L1（方言核心）。一个CFG G = (N, T, P, S)，其终结符 τ ∈ T 携带正则词素语言 R_τ ⊆ Σ^*，并有一个被忽略的子集 I ⊆ T（空白、注释），该子集是一等公民。生产级SQL语法（PostgreSQL, MySQL, SQLite）是LALR(1)的，因此确定性PDA覆盖就足够了。词法分析是在联合自动机上进行的最大匹配，带有*上下文消歧*：一个强制发射事件在最长匹配处携带完整的候选终结符集合，消费者选择优先级最高的*解析器可行*候选（这使得TABLE_NAME和COLUMN_NAME可以共享一个正则表达式，并无需新机制即可解决JSON中属性键与字符串的重叠问题）。
* L2（角色投影）。产生式子集 P_role ⊆ P（动词子集、子句禁止），随后进行*强制性的*无用符号消除，并验证 L(G_role) ≠ ∅。简化性是负载关键的：没有它，“非空动作集 ⇒ 可行前缀”不成立，会导致死胡同返回。
* L3（模式词库）。对于标识符类别 C ⊆ T，有限的允许列表 W_c ⊆ Σ^* 实现为词法分析器前缀树；这些列表从数据库目录（information_schema）生成。前提条件（在引导构建时验证而非假设）：对于每个类别，W_c ⊆ R_c（每个允许的词必须能被扫描到其终结符的接受状态）。

约束语言 L = L(G_role, schema) 是字节串的集合，这些字节串能在投影语法下进行词法分析和解析，并且每个类别为c的词素都在W_c中。策略包和模式快照都是带指纹的、不可变的输入；语法、前缀树和预留表都是内容寻址的工件。

## 3 可行前缀预言机

### 3.1 设计分析：为何序列键和接受语义会失败

v0.0.5设计快照预计算了一个内存表，将LLM*令牌序列*标记为由下推自动机接受或拒绝，并在每一步通过表查找进行掩码。在对该快照进行计划中的设计评审时，两个观察结果迫使形成了后续所有设计的形态。

###### 命题1（序列键表组合爆炸）。

一个针对长度≤m的令牌序列的完全有效性表具有Θ(|V|^m)个条目。当|V|=32,768且m=3时，已有约3.3×10^13个条目（每个条目12字节，约400TB）；当m=18时，超过可观测宇宙中的原子数。

该表的一个“代表性子集”是由结果而非构造定义的，因此不提供构建方法。然而，该表试图枚举的信息是有限可表示的：根据LR自动机的可行前缀性质[2]，一个LR语法的可行前缀集合由解析器的配置来表征，这是一个*语法规模*的键空间（对于SQL类语法为10^4–10^6）。

###### 命题2（接受语义在第一步死锁）。

令标记语义为“PDA接受此序列”（即L中的成员资格）。对于任何不包含长度为1个令牌的句子的L，空前缀的每个单令牌续接都被标记为拒绝，因此第一步掩码为空，生成无法开始。掩码需要的是 Prefix(L) = { w: ∃w', ww' ∈ L }，而非L。

两个结论都是建设性的，而不仅仅是破坏性的：它们确定了正确的键空间（配置）和正确的语义（前缀可行性），本节的其余部分将对此进行形式化。

### 3.2 配置与正确前缀性质

###### 定义1（解析器配置）。

一个*配置*是一个二元组 κ = (σ, ρ)，其中 σ 是 LALR(1) 解析器栈（一个持久的、节点不可变的链，状态构成），ρ 是当前部分词素上的词法分析器扫描状态——具体而言，是单个进行中词素的剩余字节 r，它决定性地确定了扫描器DFA状态、最大匹配假设集和最后接受位置。

###### 定义2（可行前缀）。

w ∈ Prefix(L) ⇔ ∃ w' ∈ Σ^*: w w' ∈ L。操作上：对w进行递增扫描和移进成功，并且尾部的部分词素对于某个允许或忽略的终结符是活动的。

###### 命题3（递增解析器即预言机）。

在§2的前提条件（简化的投影语法；经过验证的词库W_c ⊆ R_c）下，递增推进的解析器——在每一步将当前配置κ更新为κ' = parse_step(κ, token)（对完成的词素执行移进或规约动作，并记录部分词素的剩余字节）——在可接受的步数内提供函数 viable_prefix(κ) = { τ ∈ T : κ 处τ词法分析可行 }（通过扫描器DFA试探可达性检查）。此外，由于LALR(1)动作表是确定性的，对于每个κ，最多有一个规约动作处于待命状态；该动作的先行符号是已知的，因此部分词素的可行终结符集是一个纯扫描器属性，与先行状态无关。这保证了掩码构建可以在扫描器层面完成，而无需同步回溯解析器。¹

> ¹ 非LALR(1)语言（例如Python）可以用GLR解析器以相同模式处理，但GLR的并行栈导致配置激增。当前系统假定LALR(1)；扩展至LR(1)/GLR是第10节“限制”中列出的未来工作。