Flexible and Efficient Grammar-Constrained Decoding

📄 arXiv: 2502.05111v2 📥 PDF

作者: Kanghee Park, Timothy Zhou, Loris D'Antoni

分类: cs.CL, cs.AI

发布日期: 2025-02-07 (更新: 2025-07-15)

💡 一句话要点

提出一种更快语法约束解码算法，加速LLM生成结构化输出。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 语法约束解码 大型语言模型 结构化输出 上下文无关文法 代码生成

📋 核心要点

  1. 现有语法约束解码算法预处理耗时，成为LLM生成结构化输出的瓶颈。
  2. 提出一种新的GCD算法，加速tokenizer与CFG的对齐和token mask计算。
  3. 实验表明，该方法在离线预处理速度上显著优于现有方法，同时保持在线效率。

📝 摘要（中文）

大型语言模型（LLM）常被要求生成符合精确语法规则的结构化输出，例如代码片段或格式化数据。语法约束解码（GCD）通过屏蔽那些会导致不属于指定上下文无关文法（CFG）的输出的tokens，来保证LLM输出符合这些规则。为了保证可靠性，GCD算法必须计算给定的LLM subword tokenizer如何与给定的上下文无关文法使用的tokens对齐，并基于此信息计算token masks。高效地完成这项任务具有挑战性，现有的GCD算法需要花费数十分钟来预处理常见的语法。我们提出了一种新的GCD算法及其实现，与现有方法相比，离线预处理速度提高了17.71倍，同时保持了在线mask计算方面的最先进效率。

🔬 方法详解

问题定义：论文旨在解决大型语言模型在生成结构化输出时，现有语法约束解码（GCD）算法预处理速度慢的问题。现有的GCD算法需要花费大量时间来计算LLM subword tokenizer与上下文无关文法（CFG）token的对齐方式，这严重限制了GCD的应用。

核心思路：论文的核心思路是通过优化tokenizer与CFG的对齐算法，减少预处理时间。具体来说，该方法可能采用了更高效的数据结构或算法来表示和操作文法规则和tokenizer信息，从而加速对齐过程。

技术框架：论文提出的GCD算法包含离线预处理和在线mask计算两个阶段。离线预处理阶段负责计算tokenizer与CFG的对齐信息，并生成token masks。在线mask计算阶段则利用预处理阶段的结果，在LLM生成token时，动态地屏蔽掉不符合语法规则的token。具体模块细节未知。

关键创新：论文的关键创新在于提出了一种更高效的离线预处理算法，显著减少了预处理时间。这种改进可能来自于对现有算法的优化，或者采用了全新的算法思路。与现有方法相比，该方法在保证生成结果符合语法规则的前提下，大大提高了效率。

关键设计：论文的具体技术细节未知，包括关键参数设置、损失函数和网络结构等。但可以推测，该方法可能涉及到对文法规则的表示方式、tokenizer信息的处理方式以及mask计算策略的优化。

📊 实验亮点

实验结果表明，该论文提出的GCD算法在离线预处理速度上比现有方法提高了17.71倍，同时保持了在线mask计算方面的最先进效率。这意味着该方法可以在更短的时间内完成语法约束解码的预处理，从而加速LLM生成结构化输出的过程。

🎯 应用场景

该研究成果可广泛应用于需要LLM生成结构化输出的场景，例如代码生成、数据格式化、自然语言到SQL的转换等。通过提高GCD的效率，可以加速LLM在这些领域的应用，并降低计算成本。未来，该技术可能被集成到各种LLM应用框架中，成为生成结构化输出的标准组件。

📄 摘要（原文）

Large Language Models (LLMs) are often asked to generate structured outputs that obey precise syntactic rules, such as code snippets or formatted data. Grammar-constrained decoding (GCD) can guarantee that LLM outputs matches such rules by masking out tokens that will provably lead to outputs that do not belong to a specified context-free grammar (CFG). To guarantee soundness, GCD algorithms have to compute how a given LLM subword tokenizer can align with the tokens used by a given context-free grammar and compute token masks based on this information. Doing so efficiently is challenging and existing GCD algorithms require tens of minutes to preprocess common grammars. We present a new GCD algorithm together with an implementation that offers 17.71x faster offline preprocessing than existing approaches while preserving state-of-the-art efficiency in online mask computation.