自回归语言模型的可行分层控制

约束自回归大语言模型（LLM）的生成是把语言模型集成进形式系统的重要环节。在程序合成等任务的代码与数据生成中，确保语言模型产出语法有效的输出是处理该输出的前提。这些语言（如SQL或JSON）常被设计为LR(k)上下文文法。通过把LLM蒸馏为一个可行的概率模型，其自回归生成可以被转向与掩码，纳入满足逻辑约束的概率，确保有质量且保证有效的输出。本文证明：任何有限时长的LR(k)文法的满足性都可以在多项式时间内计算——相较既往方法在此类文法上的指数时间是一个改进。该结果使LLM生成的高效约束与转向成为可能，让输出更好满足形式语法约束。