通过解析器堆栈分类进行高效的语法约束解码

LLM 广泛用于生成结构化输出，如源代码或 JSON。语法约束解码（GCD）可以通过屏蔽掉违反上下文无关语法指定的规则的标记来保证生成的输出的语法有效性。然而，现有 GCD 方法的在线计算开销（延迟通常与词汇量大小呈线性关系）限制了 LLM 的吞吐量，特别是对于词汇量较大的模型。为了解决这个问题，我们提出了 PSC，一种新颖的语法约束解码方法。通过在预处理期间将所有词汇标记的接受条件组合到解析器堆栈的单个分类器中，PSC 可以通过每个解码步骤精确检查一次解析器堆栈来计算完整的词汇掩码，时间复杂度与词汇大小无关。实验表明，在复杂的编程语言语法上，PSC 计算掩码的速度比基线快 700$\times$，对于符合模式的 JSON，速度最高 30$\time$； PSC 的端到端 LLM 吞吐量接近无约束解码的吞吐量。我们为预处理提供者和解码用户分析预处理开销，并提供盈亏平衡点分析，帮助用户决定是否自行进行预处理。