arXiv:2607.18357cs.PLcs.AI2026-07

让大模型生成代码时自动避免引用未定义的变量或函数。

Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments

论文配图:Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments
图 1 · 摘自论文原文
  • 生成时动态构建语法片段,根据上下文环境选择合适规则
  • 通过环境类型槽位限制候选名称,消除无效引用错误
  • 适用于低资源编程场景,如自定义命令行工具和领域语言

大型语言模型正越来越多地编写代码,尤其在智能体和系统中直接生成可编译、执行或分发的代码,而无需逐行审查。这在主流语言上表现良好,但在低资源编程场景(如领域特定语言、自定义库 API、命令行工具)仍不稳定。即使使用语法约束解码,模型仍可能产生无效引用:未声明的缓冲区、不存在的列、库中不存在的函数或不支持的 CLI 选项。本文提出解码时语法(decode-time grammars):从运行时环境 Gamma 实例化语法片段,在生成过程中为每个待填区域选择特定片段,并用 Gamma 类型槽位替换开放引用位置,其候选仅限当前环境中可用的名称、字段、API 或选项。新生成的声明会提前加入 Gamma,使后续区域的约束依赖已生成前缀。该方法确保语法与语义双重正确性,杜绝未定义符号引用。我们形式化语法片段为按精炼顺序排列的环境索引语法,证明 Γ-槽位片段满足无幽灵(No-Ghost)正确性,且精炼过程保持支持集保证,刻画掩码可强制属性的边界。我们在 gproj 中实现该方法,采用离线语法归纳与在线策略解析。在 TileLang、SQL、P4 上,使用 0.6B 到 236B 参数模型验证,gproj 以适度开销彻底消除幽灵引用。

原文摘要 · Abstract (English)

Large language models now write a growing share of the world's code, increasingly inside agents and serving systems that compile, execute, or dispatch generated code without line-by-line review. This works well for mainstream languages but remains brittle for low-resource programming surfaces such as domain-specific languages, custom library APIs, and command-line tools. Even under grammar-constrained decoding, a model can still produce references invalid in the current environment: a buffer never declared, a column absent from the schema, a function the library does not provide, or an unsupported CLI option. This paper introduces decode-time grammars: grammar fragments instantiated during generation from a runtime environment Gamma. A region-specific policy selects a fragment for each hole, and a tightening operator replaces open reference positions with Gamma-typed slots whose candidates are exactly the names, fields, APIs, or options available at that point. Newly generated declarations enter Gamma before later regions are decoded, so the constraining grammar can depend on the prefix already generated. This ensures not only grammatical correctness but also semantic correctness, by preventing references to undefined symbols. We formalize grammar fragments as environment-indexed grammars ordered by refinement, prove No-Ghost soundness for Gamma-slotted fragments, show that refinement preserves this support-set guarantee, and characterize the boundary of mask-enforceable properties. We implement the approach in gproj with offline grammar induction and online policy resolution. Across TileLang, SQL, and P4, with models from 0.6B to 236B parameters, gproj eliminates ghost references by construction at moderate overhead over standard constrained decoding.

代码生成语法约束大模型语义正确

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。