Grammar-Aligned Decoding

大型语言模型（LLMs）难以可靠地生成高度结构化的输出，例如程序代码、数学公式或规范的标记。受限解码方法通过贪心地限制LLM在每个步骤中可以输出的标记，以保证输出与给定约束匹配，从而缓解了这个问题。具体而言，在语法受限解码（GCD）中，LLM的输出必须遵循给定的语法。在本文中，我们证明了GCD技术（以及一般的受限解码技术）可能会扭曲LLM的分布，导致输出虽然符合语法，但出现的可能性不与LLM给出的概率成比例，因此最终质量较低。我们将对齐采样与语法约束的问题称为语法对齐解码（GAD），并提出了自适应采样与近似期望未来（ASAp）的解码算法，该算法保证输出符合语法，同时能够证明产生与给定语法约束条件下LLM的条件概率分布相匹配的输出。我们的算法使用先前的样本输出来准确估计不同输出前缀的未来语法性。我们在代码生成和结构化NLP任务上的评估表明，ASAp通常会产生比现有的GCD技术更高概率（根据LLM的分布）的输出，同时仍然强制执行所需的语法约束。

解决问题：论文提出了一种名为Grammar-aligned decoding (GAD)的算法，旨在解决语法约束下的采样问题。即如何在保证输出符合语法约束的前提下，仍能保证输出的概率分布符合原始模型的概率分布。

关键思路：论文提出了一种名为adaptive sampling with approximate expected futures (ASAp)的算法，该算法使用先前的样本输出来近似计算不同输出前缀的未来语法正确性，从而保证输出的语法正确性的同时，还能保证输出的概率分布符合原始模型的概率分布。

其他亮点：论文通过实验验证了ASAp算法在代码生成和结构化NLP任务中的有效性，相比于当前的GCD技术，ASAp算法能够产生更高概率的输出，同时仍然遵循语法约束。论文还提供了开源代码和使用的数据集，值得进一步研究。

相关研究：最近的相关研究包括：《Constrained Decoding for Neural NLG from Abstract Meaning Representations》、《Incorporating Structural Alignment Biases into Grammar-Based Neural Machine Translation》等。