GRID语法约束解码引擎为企业SQL生成提供可证明保证

背景

企业部署 SQL 生成时，大型语言模型（LLM）虽然能写出看似合理的 SQL 语句，但远远不够。实际生产环境要求输出必须语法上严格合法，必须遵守基于角色和数据库模式的访问控制策略，必须提供可证明（而非尽力而为）的保证，生成速度不能随着序列长度增加而下降，并且每个解码步骤都必须留下可供合规审计的不可篡改记录。现有约束解码方法（如基于 token 序列的掩码）在语法覆盖范围、计算效率、可证明性以及 RBAC（基于角色的访问控制）集成方面存在显著短板。针对这些需求，本文提出GRID（Grammar-Railed Decoding），一种全新的语法约束解码引擎。

核心内容

GRID 的核心创新在于将语法约束与增量式 LALR(1) 解析器深度耦合，而非依赖简单的 token 序列前缀匹配。具体而言：

1. 掩码生成基于解析器状态
   GRID 的 next-token 掩码不是由 token 序列本身决定，而是由词法分析器的扫描状态与 LALR(1) 分析栈共同构成的解析器配置（parser configuration）作为键值。这样，每次生成下一个 token 时，掩码直接由当前语法上下文（即解析器内部状态）精确决定，而非仅靠已生成 token 序列的近似推断。

2. 利用增量解析器作为可行前缀预言
   GRID 利用逐步推进的 LALR(1) 解析器本身作为“可行前缀（viable-prefix）”的 oracle。解析器在每一步都能判断当前前缀是否可能扩展为完整合法的句子，从而提供精确的允许 token 集合。

3. LLM token 到语法终结符的桥接
   LLM 输出的 token（可能是子词或字节）通过一个字节级 trie 遍历映射到语法定义的终结符。为了保持缓存键的一致性（soundness），设计将上下文无关（context-independent）与上下文相关（context-dependent）的情况分开处理，确保不同词法上下文不会错误共享缓存。

4. 基于角色的访问控制编译进语法
   RBAC 被直接集成到语法定义中：不同角色对应的视图（projections）会子集化（subset）语法的产生式规则，同时模式词库（schema lexicons）限制标识符终结符的允许范围。因此，禁止的动词（如 DROP、ALTER）和禁止的标识符（如某些表或列名）在掩码层面就是不可到达的——不是事后过滤，而是构造性不可生成。

5. 四个可证明保证
   GRID 明确声明了以下四个性质，每个都有显式的前提条件，并附有测试或基准验证：

   • Soundness（健全性）：任何被掩码允许的 token 序列都能扩展为某个合法句子。
   • Completeness（完备性）：任何合法句子中的每个 token 都会被掩码允许。
   • Termination（终止性）：解码过程必然在有限步内结束（不会死循环）。
   • Near-constant per-token cost（近常数每 token 开销）：生成每个 token 的额外计算成本不随已生成序列长度增长。

6. 性能表现
   使用 Rust 实现的内核，每 token 掩码生成的中位数延迟为 3.6–6.7 微秒。在两个 tokenizer 上的 p50 和 p90 均优于对比方法 llguidance，且零假拒绝（zero false rejects）。每 token 的防护成本在序列长度达到 16,000 时仍然保持位置平坦（即几乎不随长度增加）。

7. 实际效果评测
   在 Spider 数据集上，约束解码在 0.5B 参数的模型上带来了 +13 个执行准确率（execution accuracy）百分点的提升。对于掩码本身无法强制执行的残留问题（如列级约束），通过一次 checker-guided 修复 pass，将 7B 模型的可执行率提升至 94.5%。

8. 审计轨迹
   GRID 为每个生成的 token 记录一个哈希链审计轨迹，该轨迹可以以比特完全相同的方式重放（bit-identical replay），并具有 100% 的篡改检测能力。

9. 坦诚的局限性
   GRID 明确指出了掩码技术无法覆盖的方面：

   • 分布保真度（distibution faithfulness）：约束解码不能保证 LLM 原本的概率分布被忠实保留。
   • 列级 RBAC：目前仅支持 schema 级（表/视图）的标识符限制，列级策略仍需通过外部 checker 修复。
   • 非 LALR(1) 语法：引擎依赖 LALR(1) 解析器，不能直接处理需要更复杂语法（如上下文相关）的语言。
   • 仍存在较高开销的场景：部分罕见情况下的掩码生成成本尚未完全优化。

关键要点

• 掩码键的设计创新：使用“词法扫描状态 × LALR(1) 栈”代替传统基于 token 序列的掩码，实现精确且高效的语法约束。
• 增量解析器即 oracle：将 LALR(1) 解析器本身作为可行前缀判断器，无需额外构建前缀树。
• 字节级 trie 桥接：解决 LLM 子词 token 到语法终结符的映射问题，并通过上下文分离保证缓存键健全。
• RBAC 编译进语法：通过角色投影和 schema 词库子集化，从根源上阻止非法操作，而非事后过滤。
• 四个可证明性质：健全性、完备性、终止性、近常数代价，每个都有明确前提和验证。
• 极低延迟：Rust 实现使每 token 掩码中位数在 3.6–6.7 μs，优于 llguidance，且零假拒绝。
• 长度无关的代价：每 token 防护成本在序列长度 16,000 时仍平坦，适合长 SQL 生成。
• 显著准确率提升：在 Spider 上，小模型（0.5B）获益 +13 点，大模型（7B）通过附加修复达 94.5% 可执行率。
• 完整审计轨迹：哈希链方式确保每步可重放、可检测篡改，满足合规需求。
• 诚实的边界声明：承认掩码不能保证分布保真、不能处理列级 RBAC、限于 LALR(1) 语法，并指出成本未完全优化的角落案例。

意义与影响

GRID 提出了一种面向企业级 SQL 生成的语法约束解码框架，最显著的意义在于将形式语法验证、基于角色的安全策略、可证明保证和计算效率统一在一个引擎中。相比于此前工作（如使用正则表达式或 CFG 掩码），GRID 通过利用 LALR(1) 分析器的增量特性，实现了更高的精确性和可证明性，同时保持了极低的运行时开销。这对金融、医疗、政务等需要严格合规和审计的领域具有直接应用价值。

另外，GRID 明确区分了掩码层能做什么和不能做什么，并针对无法强制执行的部分（如列级策略）提出了 checker-guided 修复作为互补方案，这种“约束+修复”的双层思路为企业部署提供了务实路径。哈希链审计轨迹的设计也回应了监管机构对模型输出可追溯性的要求。

从技术影响看，GRID 将 RBAC 编译到语法本身的做法可能启发后续工作把更多安全策略（如数据脱敏、行级过滤）直接注入解码过程。同时，其坦诚的局限性也为后续研究指明了方向：如何扩展到非 LALR(1) 语法、如何实现细粒度列级约束、如何在约束下保持分布保真等。总体而言，GRID 在语法约束解码的可证明性与工程实用性之间取得了重要的平衡，为 LLM 在关键业务场景中的可信部署提供了一项扎实的基础设施。