摘要
约束自回归大型语言模型（LLMs）的生成是将语言模型整合到形式系统中的重要组成部分。在程序合成等任务中生成代码和数据时，确保语言模型产生语法有效的输出是处理此类输出的前提。这些语言（如 SQL 或 JSON）通常被设计为 $LR(k)$ 上下文无关文法。
通过将 LLM 提炼为一个可处理的概率模型，其自回归生成可以被引导和屏蔽，以结合满足逻辑约束的概率，从而确保高质量的有效输出。本文表明，任何有限持续时间的 $LR(k)$ 文法的满足性可以在多项式时间内计算，这比以往方法对这类文法的指数时间应用有了显著改进。这一结果使得高效约束和引导 LLM 生成更好地满足形式语法约束的输出成为可能。
博主点评： 本文为自回归语言模型的生成提供了一种高效的约束方法，显著提高了语法有效性的生成效率。通过将复杂的上下文无关文法问题转化为多项式时间内可解决的形式，为实际应用中的代码生成和数据处理奠定了基础，具有较高的理论和实际价值。