让大模型生成代码时自动保证语法正确，效率比旧方法快得多
Tractable Hierarchical Control of Autoregressive Language Models
- 把大模型转成可计算的概率模型，用语法约束引导生成
- 对有限长度的LR(k)语法，验证合法性可在多项式时间内完成
- 适合需要严格语法输出的场景，如程序合成、数据生成
约束自回归大语言模型（LLM）的生成是将其集成到正式系统中的关键。在程序合成等任务中生成代码或数据时，确保输出具有语法规则性是后续处理的前提。这些语言（如SQL或JSON）通常被设计为LR(k)上下文无关文法。通过将LLM压缩为可计算的概率模型，其自回归生成过程可被引导和掩码，以融入满足逻辑约束的概率，从而保证高质量且语法正确的输出。本文证明，任何有限长度的LR(k)文法的满足性可在多项式时间内计算，优于此前方法的指数时间复杂度。这一结果使得高效施加约束并引导LLM生成更符合形式语法规则的输出成为可能。
原文摘要 · Abstract (English)
Constraining the generation of autoregressive large language models (LLMs) is an important component of integrating language models into formal systems. In the generation of code and data for tasks like program synthesis, ensuring that language models produce syntactically valid output is a prerequisite for processing such output. These languages (such as SQL or JSON) are often designed as $LR(k)$ context-free grammars. By distilling the LLM to a tractable probabilistic model, its autoregressive generation can be steered and masked to incorporate the probability of satisfying logical constraints, ensuring high quality output that is guaranteed to be valid. This paper demonstrates that the satisfaction of any $LR(k)$ grammar of finite duration can be calculated in polynomial time, an improvement over the exponential time of applying previous methods to such grammars. This result enables efficient constraint and steering of LLM generation towards output that better satisfies formal syntactic constraints.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。