🤖 AI

Accelerating Constrained Decoding with Token Space Compression

本文介绍了 CFGzip，这是一种离线令牌空间压缩技术，可显著降低约束解码的计算开销，在复杂上下文无关文法的全生成时间上实现高达 7.5 倍的加速。

原作者： Michael Sullivan, Alexander Koller

发布于 2026-05-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Michael Sullivan, Alexander Koller

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你有一位才华横溢但略显混乱的厨师（即大语言模型，LLM），他几乎能烹饪任何菜肴。然而，你需要他按照一份非常严格且复杂的食谱（即上下文无关文法，CFG）来准备一道菜，比如某种特定的编程语言或精确的数据格式。

如果厨师猜错了食材，整道菜就毁了。为了防止这种情况，你雇佣了一位严格的文法引擎（就像主厨或食品安全检查员），他站在厨师身旁。在厨师添加任何食材之前，检查员会检查整个储藏室，确认该特定食材是否允许在当前食谱步骤中使用。

问题：“储藏室”太大了

问题在于，厨师的储藏室（即词元词汇表）极其庞大，包含数十万种不同的食材（单词、符号、代码片段）。

每当厨师想要添加一种食材时，检查员都必须遍历整个储藏室，以确认该特定物品在此时是否有效。对于简单的食谱（如 JSON 数据），这很快。但对于复杂的食谱（如 C++ 代码或一种名为"Bython"的虚构语言），检查员会不堪重负。他们必须检查如此多的可能性，导致烹饪过程大幅减慢——有时比正常情况慢2 到 10 倍。论文将这种情况称为“难以处理的高开销”。

解决方案：CFGZIP（“分组”技巧）

作者介绍了一种名为CFGZIP的新工具。CFGZIP 不是在厨师开始烹饪后让检查员逐一检查储藏室里的每一种食材，而是在烹饪开始前重新整理储藏室。

以下是类比：

分组食材：CFGZIP 查看储藏室，发现许多食材在食谱目的上是可互换的。例如，在代码食谱的特定部分，单词 if、else 和 while 在语法上可能表现相同。或者，在不同的上下文中，数字 1、2 和 3 可能都是有效的占位符。
创建“代表”桶：CFGZIP 将这些可互换的食材分组到桶中。它从每个桶中挑选一个“代表”食材（通常是较短的那个）来代表整个组。
新工作流程：
- 烹饪前（离线）：系统执行将储藏室分类到这些桶中的繁重工作。这一步只需执行一次并保存。
- 烹饪中（推理）：当厨师挑选一种食材时，系统会迅速将其替换为桶中的“代表”。检查员只需将代表与食谱进行核对，而无需检查整个储藏室。
- 结果：由于检查员现在只需检查一个微小的代表列表，而不是庞大的原始储藏室，过程变得极其迅速。

为什么这很重要

论文声称，将 CFGZIP 与顶级文法引擎（XGrammar2）结合使用，能带来巨大的加速：

延迟降低：规则检查所需的时间减少了10 到 100 倍（两个数量级）。
总体加速：对于复杂任务，生成文本的整个过程速度提高了7.5 倍。
无质量损失：这是一种“无损”压缩。最终输出与不使用加速时得到的结果逐字节完全相同。厨师仍然能做出完全相同的完美菜肴；只是他们到达终点快得多了。

论文中的实际结果

研究人员在三种不同的 AI 模型（Llama、Qwen 和 GPT）和四项不同的任务上测试了此方法：

JSON 和 XML：标准数据格式。
C++：一种复杂的编程语言。
Bython：一种虚构的、人造的编程语言（类似于 Python，但使用大括号和分号代替空格）。

发现：

对于标准格式（JSON），加速效果良好但并非革命性，因为这些规则本身已经很简单。
对于复杂且不熟悉的语言（如 C++ 和 Bython），差异巨大。如果没有 CFGZIP，文法引擎慢到使 AI 在这些任务上几乎无法使用。有了 CFGZIP，AI 能够快速且正确地生成复杂代码。
有趣的是，对于 AI 从未见过的"Bython"任务，使用这种约束方法将 AI 编写可运行代码的能力从2.3% 提高到了 46.9%（针对某一款模型），证明当任务困难时，严格的规则有助于 AI。

注意事项（局限性）

论文指出了一个主要局限性：准备时间。
将储藏室分类到桶中（即“离线预计算”）需要时间。

如果你需要为一个一次性、快速的任务生成 JSON 文件，那么整理储藏室所花费的时间可能比直接正常完成任务还要长。
然而，如果你正在进行大规模代码生成，或者反复使用相同的复杂规则，那么初始设置时间是值得的，因为烹饪（生成）过程变得快得多。

总结

CFGZIP就像一位聪明的图书管理员，在你到达之前将庞大的图书馆重新组织成“主题桶”。你不再需要搜索每一本书来找到正确的那一本，图书管理员只需指向“主题桶”的代表。这使得找到正确信息（或在本案中，生成正确代码）的速度 dramatically 加快，而不会丢失任何一本书或改变故事内容。

技术摘要：利用令牌空间压缩加速约束解码（CFGZIP）

问题陈述

大型语言模型（LLM）经常需要生成符合特定结构的文本，例如 JSON、XML 或特定领域的编程语言。虽然 LLM 在其训练数据中常见的格式上表现良好，但在面对新颖或复杂的格式时却显得力不从心。为了确保语法正确性，通常会采用约束解码（Constrained Decoding）引擎。这些引擎利用上下文无关文法（CFG）在每一步生成过程中屏蔽无效的令牌。

然而，当前最先进的（SoTA）文法引擎（例如 XGrammar2）面临着显著的性能瓶颈。尽管经过优化，它们仍需在每一步解码时针对整个令牌词汇表验证令牌的有效性。对于复杂的 CFG（例如 C++ 或自定义语言），这会导致难以承受的开销，使得与无约束生成相比，推理延迟增加了2 倍至 10 倍。这种延迟使得涉及复杂文法的约束解码在大规模应用中变得不可行。

方法论：CFGZIP

作者介绍了CFGZIP，这是一种离线技术，旨在压缩令牌搜索空间，从而在不牺牲正确性的前提下降低文法引擎的每步运行时间。

核心概念：等价类

CFGZIP 的基本洞察是，词汇表中的许多令牌对于特定的 CFG 而言是可互换的。如果两个令牌 $t$ 和 $u$ 是“语法同余”的，那么它们可以在语言 $L(G)$ 的任何有效字符串中互换，而不会影响有效性。因此，文法引擎只需验证每个等价类中的一个代表令牌的有效性，而无需验证每一个单独的令牌。

流程

离线预计算：
- 近似：由于针对任意 CFG 的精确语法同余是不可判定的，CFGZIP 计算一种称为位移等价（Displacement Equivalence, $\sim_{L(G)}$ ）的可行近似。
- 机制：CFG 被转换为 Greibach 范式（GNF）以利用下推自动机（PDA）。对于每个令牌，系统计算其“位移” $\Delta_G(t)$ ，定义为该令牌在 PDA 上引发的输入/输出栈转换集合。具有相同位移集合的令牌被归入同一个等价类。
- 优化：为了使计算可行，作者利用预计算的栈邻接关系限制了栈回溯操作，从而防止在大型文法中出现内存爆炸。
- 缓存：系统将令牌 ID 映射到类 ID，并为每个类选择一个字节长度最短的令牌作为“代表”。这些映射被缓存到磁盘上。
推理时操作：
- 词汇表缩减：文法引擎使用等价类代表的词汇表进行初始化，而非完整的令牌词汇表。
- 令牌映射：当 LLM 采样一个令牌时，CFGZIP 将其映射到其类代表，并将该代表传递给文法引擎以更新解析器状态。
- 屏蔽：文法引擎在较小的代表集合上生成有效性掩码。随后，该掩码被“收集”并应用于原始 LLM 的 logits。此操作可在 GPU 上并行化，且开销极小。

关键特性

无损：压缩在理论上被证明是无损的；配备 CFGZIP 的引擎的输出与原始引擎的输出在字节层面完全一致。
引擎无关：理论上兼容任何文法引擎，尽管论文主要关注 XGrammar2。
离线：繁重的计算每个分词器/CFG 对仅执行一次，在推理过程中几乎不产生额外开销。

实验结果

作者在 Llama-3.2-3B、Qwen3-4B 和 gpt-oss-20B 模型上评估了与 XGrammar2 结合的 CFGZIP，涵盖了四个任务：JSON Schema、XML、C++ 和Bython（一种自定义的基于大括号的 Python 变体）。

延迟降低：CFGZIP 将文法引擎的开销降低了一到两个数量级。
- 对于C++，总推理时间几乎减半。
- 对于Bython（一种复杂且资源匮乏的语言），总约束生成时间减少了约7.5 倍。
正确性：CFGZIP 保持了100% 的语法正确性（与基准引擎字节级一致）。
- 功能正确性：约束解码显著提高了功能正确性，特别是在 Bython 任务中，无约束模型在此类任务上表现挣扎（例如，GPT-20B 的功能正确率从 10.8% 提升至 46.9%）。
压缩率：该技术实现的压缩率范围从40:1（Llama-3B/C++）到800:1（GPT-20B/JSON），大幅减少了引擎需要处理的词汇表大小。

意义与主张

论文声称，CFGZIP 使得在大规模复杂 CFG 场景下的约束解码变得可行。

弥合差距：虽然 SoTA 引擎对简单文法（如 JSON）效率很高，但对复杂文法（如 C++）却引入了难以处理的延迟。CFGZIP 将这种开销缩减至几乎可忽略的水平，从而解锁了这些困难案例中约束解码的性能优势。
成本效益：结果表明，对于更小、更便宜的模型，约束解码可以成为实现高功能正确性的替代方案，而无需使用更大的模型。
实用性：通过将繁重工作解耦到离线预计算阶段，CFGZIP 使得需要严格遵循复杂特定领域语言（DSL）的实时应用成为可能，同时不牺牲速度。

局限性

作者指出，CFGZIP 并非适用于所有场景的通用解决方案：

动态上下文：离线预计算时间（从几秒到几分钟不等）使其不太适合动态的、单次使用的 CFG（例如临时 JSON 架构或函数调用），在这些场景中，像 llguidance 这样的引擎已经高度优化。
引擎兼容性：虽然理论上与引擎无关，但当前实现基于 Python 并与 XGrammar2 集成。它与仅基于 C++ 的引擎（如 llama.cpp，由于缺乏 Python 绑定）或不支持特定 CFG 的引擎（例如 transformers-cfg 中的左递归文法）不兼容。
适用范围：该方法最适合静态、大型且复杂的 CFG，例如代码生成中使用的文法。