💻 computer science

Trie Automata for Constrained Decoding over Large Finite Sets

本文介绍了 Trie 自动机，这是一种利用 Aho-Corasick 多模式匹配来预计算有限集合约束解码的标记掩码（token masks）的专门机制，与 XGrammar 等现有系统相比，在保证 100% 输出有效性的同时，实现了高达 29 倍的吞吐量提升以及显著更快的编译速度。

原作者： Xingzi Xu, Karim Bouyarmane

发布于 2026-08-14

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Xingzi Xu, Karim Bouyarmane

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

想象一个这样的世界：计算机就像是才华横溢但有些混乱的大厨。它们能写故事、解数学题，甚至编写软件，但也有一个坏习惯——喜欢胡编乱造。如果你问它们世界上首都的名字，它们可能会自信满满地发明一个叫“纳尼亚”的城市，或者把“巴黎”拼错。为了阻止这种行为，科学家们使用了一种叫做**约束解码（constrained decoding）**的技术。你可以把它想象成给大厨一本严格的食谱。食谱不是让大厨从整个宇宙中随意挑选食材，而是说：“你只能使用面粉、糖或鸡蛋。”计算机在写下每一个词之前，都会根据这个清单进行检查，以确保它不会不小心发明出一种新的食材。

当清单很短时（比如只有三种食材的食谱），这种方法效果很好。但如果清单非常庞大呢？想象一下，一份食谱要求：“你可以使用世界上 10,000 种不同的香料，”或者“你可以从一个巨大的车间里挑选 50,000 种工具中的任何一种。”检查三个项目的清单很容易，但每当计算机想要产生一个新词时，都要去检查 50,000 个项目，这就像是在一个不断变大的草堆中寻找一根特定的针。计算机会被繁琐的检查工作搞得精疲力竭，导致停止烹饪，或者因为耗时太长而让食物变凉。这就是研究人员试图解决的问题：如何让计算机在面对庞大的“禁用清单”时，依然保持快速且准确。

被禁止词汇的大图书馆

在这篇论文中，研究人员引入了一个聪明的工具，叫做前缀树自动机（Trie Automaton）。为了理解为什么它是一个游戏规则改变者，让我们看看旧的方法是如何运作的。想象计算机是一个守在大型图书馆门口的保安。每当计算机想要说出一个词时，保安都必须跑过一条长长的走廊，翻阅一本巨大的、落满灰尘的账本（即那份包含 10,000 个有效词汇的清单），查看该词是否被允许。如果清单很大，保安就会把所有时间都花在来回奔跑上，而等待进入的人群（即计算机的思想）就会陷入停滞。这就是论文中所说的“基数墙（cardinality wall）”——即当清单变得如此之大，以至于系统崩溃或运行极其缓慢的临界点。

研究人员意识到，旧方法将每个清单都视为随机的词汇堆砌。但在现实世界中，清单并不是随机的。想想一个工具名称列表：“aws.create_user”、“aws.delete_user”、“aws.list_user”。它们都以“aws.”开头，然后接着是“create”、“delete”或“list”。它们拥有许多相同的起始部分，就像树上的分叉一样。旧的保安并没有注意到这一点；他们每次都会从头开始检查每一个单词。

新的前缀树自动机就像一位超级聪明的图书管理员，她为图书馆绘制了一张特殊的地图。她不再使用长长的走廊，而是构建了一棵树状路径。

地图： 他们为“aws.”绘制了一条路径。一旦你进入了“aws.”路径，你就无需再次检查“aws.”，只需观察下一个路口：是“create”、“delete”还是“list”。
预检查： 这是神奇之处。在计算机开始说话之前，图书管理员就已经预先计算出了在树的每一个分叉处哪些词是被允许的。他们把这些答案写在小贴纸上，并把它们贴在树枝上。
速度： 现在，当计算机想要说话时，图书管理员不需要跑向账本。她只需看一眼当前分支上的小贴纸。“哦，你在‘aws’分支上？贴纸说你接下来的词只能是‘create’、‘delete’或‘list’。”这只需要一瞬间。

结果：从蜗牛到火箭

研究人员使用从 10 到 10,000 个项目的有效词汇列表，将这个新系统与现有的最佳方法（如 XGrammar）进行了对比测试。结果非常显著。

编译速度： 在为 1,000 个项目的清单构建地图时，旧系统大约需要 75 毫秒（需要等待一会儿）；新的前缀树自动机仅需约 33 毫秒。但当清单增长到 10,000 个项目时，旧系统耗时接近 240 毫秒，而新系统几乎保持在 40 毫秒左右的平稳水平。这就像旧系统是在泥泞中行走，而新系统则是在跑步机上运行，无论跑多快，阻力都不会增加。
“基数墙”： 旧系统在清单超过几百个项目时就开始失效或大幅减速。而新系统处理 10,000 个项目的清单时毫不费力，研究人员还展示了它理论上可以处理高达 100,000 个项目。
批处理服务（真正的胜利）： 最令人惊喜的结果出现在他们同时处理多个请求时（例如一个有 256 个订单的繁忙餐厅）。旧系统每秒只能处理约 7.5 个订单，而新的前缀树自动机每秒可以处理 219 个订单。这是 29 倍 的提升。

为什么它会这么快？不仅仅是因为有了地图，更在于如何使用这张地图。因为答案已经预先写在了小贴纸上，计算机在说话时不需要进行任何复杂的思考或检查。它可以直接抓取贴纸并继续。这使得计算机可以跳过许多在旧系统中每次都需要进行的缓慢且复杂的步骤。

这意味着什么

论文证明了对于特定类型的列表——例如从注册表中选择工具、选择医疗代码或选择产品类别——旧的“检查一切”的方法太慢了。通过利用词汇的结构（共享的起始部分）并预先计算答案，新方法让约束解码重新变得快速且可靠。

研究人员非常谨慎地指出，这种新方法并不会让计算机变得更聪明，也不会改变它所说的内容；它只是确保它只说它应该说的话，并且做得极其迅速。他们在真实的计算机芯片上进行了测量，发现新方法在遵循规则方面达到了 100% 的准确率，与旧方法一致，但生成每个单词的速度快了 7 倍。当你把这个速度乘以同时进行的数百个请求时，差距是巨大的。

简而言之，这篇论文找到了一种方法，将原本在巨大草堆中混乱、缓慢的搜索，转变为在预设灯光路径下的快速、有序行走。它解决了“基数墙”的问题，让 AI 能够处理海量的选项列表而不会卡顿，这对于需要瞬间从数千种工具或服务中进行选择的 AI 智能体（AI agents）的未来至关重要。

技术摘要：用于大规模有限集合约束解码的 Trie 自动机

1. 问题陈述：基数墙 (The Cardinality Wall)

大语言模型（LLMs）日益需要符合预定义模式的结构化输出，特别是从已知有限集合中选择字符串（例如：工具名称、医学代码、产品分类法）。目前的约束解码系统（如 XGrammar 和 Outlines）通过将模式编译为通用自动机（有限状态机 FSM、下推自动机 PDA 或 Earley 解析器）来处理这些约束。

虽然这种通用方法对于复杂的语法非常有效，但对于简单的有限集合约束，它会产生一个“基数墙”。随着有效字符串数量 ( $K$ ) 增长到数千个，编译时间和每步解码延迟会变得极其缓慢。现有的提供商施加了严格的限制（例如：OpenAI 限制在 1,000 个枚举值以内，Google Gemini 限制在约 120 个以内），因为标准的编译流水线在 $K$ 较大时扩展性极差。核心问题在于一种根本性的不匹配：将通用的复杂引擎应用于具有可利用结构（共享前缀、有界深度、已知基数）的简单约束（有限字符串的并集）。

2. 方法论：Trie 自动机

作者引入了 Trie 自动机 (Trie Automaton)，这是一种专门用于有限集合约束的后端，取代了通用的 Fsm 层。该方法利用约束集的结构，实现了亚线性编译和常数时间的每步解码。

核心机制

字符级 Trie 构建： 该系统并非构建基于 Token 的 Trie（这会导致跨 Token 边界时无法共享前缀），而是直接从有效字符串集中构建一个字符级 Trie。这合并了共享前缀，将节点数量从 $O(K \cdot L_{max})$ 减少到 $O(N_{chars})$ ，其中 $N_{chars}$ 是总字符数。
通过 Aho-Corasick 实现 BPE-Trie 对齐： 一个核心挑战是将字符级 Trie 与模型的字节对编码（BPE）词表进行对齐。单个 BPE Token 可能跨越多个 Trie 边。作者通过将问题简化为多模式字符串匹配来解决这一问题。他们从词表 Token 构建 Aho-Corasick (AC) 自动机，并遍历 Trie，为每个 Trie 节点 $n$ 预计算有效的 BPE Token 集合 (valid[n])。
预计算掩码 (Precomputed Masks)： 在编译期间，系统会计算所有节点 $n$ 的 valid[n]。在解码时，掩码计算简化为直接的 $O(1)$ 查找： $A(s_t) = valid[s_t]$ 。这避免了在每一步都扫描整个词表或模拟状态转移的过程。

复杂度优势

编译： 成本主要由词表上的 AC 自动机构建决定，其复杂度为 $O((N_{chars} + V) \cdot \ell)$ ，其中 $V$ 是词表大小， $\ell$ 是最大 Token 长度。至关重要的是，一旦构建了 AC 自动机，该过程在很大程度上与 $K$ 无关，即使在 $K=10,000$ 时也能实现近乎平坦的编译时间（30–67ms）。
每步解码： 成本从 $O(V \cdot \ell)$ （扫描所有 Token）降至 $O(|valid[s_t]|)$ 。由于有效集合随 Trie 深度呈指数级缩小（通常在 3–4 个字符后，有效 Token 数仅为 10–100 个），其有效成本是常数且极低的（0.65µs）。
无状态服务 (Stateless Serving)： 由于掩码是预计算的，Trie 可以作为一个无状态的 LogicitsProcessor 运行，从而绕过了基于 FSM 的方法所需的引导式解码流水线的状态管理和调度开销。

3. 核心贡献

Trie 自动机： 一种专门的约束解码后端，结合了字符级 Trie、Aho-Corasick 多模式匹配和预计算 Token 掩码。它实现了 $O(|valid[s_t]|)$ 的每步掩码计算，相对于 $O(V \cdot \ell)$ 的成本实现了常数级性能。
解决了 BPE-Trie 对齐问题： 本文解决了此前未被解决的字符级 Trie 路径与 BPE Token 对齐的挑战。通过将此问题简化为多模式匹配，实现了在不同分词器家族下，针对 $K=10,000$ 仍能保持亚百毫秒级的编译速度。
对“基数墙”的实证表征： 作者证明了将强制执行机制与约束结构相匹配可以克服扩展瓶颈。他们展示了预计算掩码如何实现 FSM 方法无法实现的无状态服务路径，从而将算法加速转化为巨大的吞吐量提升。

4. 实验结果

实验在 NVIDIA A100 GPU 上进行，涵盖了七种分词器家族（词表大小 32K–262K）以及包括 Qwen3-8B、Mistral 和 Gemma3 在内的模型。

编译速度： 在 $K \ge 300$ 时，Trie 自动机的编译速度比 XGrammar 快 2–6.5 倍。虽然 XGrammar 的编译时间随 $K$ 线性增长（在 $K=100,000$ 时达到 2.7s），但 Trie 始终保持在 ~30–67ms 的平坦水平。
每步延迟： Trie 计算有效 Token 掩码的时间为 0.65µs，而 XGrammar 为 5.8µs（7 倍加速），LLGuidance 则为 73–141µs（慢了 110–215 倍）。
端到端吞吐量： 在批量服务（vLLM）中，这种优势会产生叠加效应。在 Batch Size 为 256 时，Trie 达到了 219 req/s，而 XGrammar 为 7.5 req/s（29 倍提升）。这一增益源于 7 倍的算法加速加上消除了引导式解码流水线的开销。
有效性与准确率： Trie 保证了 100% 的输出有效性。在分类基准测试（TREC, MASSIVE, Banking77, CLINC150）中，使用 Trie 的约束解码在消除幻觉的同时，其准确率与无约束解码持平甚至更高。对于较弱的模型，Trie 起到了关键作用，通过确保输出有效，将 Banking77 上的准确率从 4.8% 提升到了 24.8%。
可扩展性： 该方法在 $K$ 高达 10,000 及以上时，仍能保持亚百毫秒级的编译和常数级的每步成本，有效地将实际枚举上限从 ~1,000 扩展到了 ~100,000。

5. 意义与主张

本文声称 Trie 自动机解决了约束解码中的一个根本性低效问题：即对简单、结构化约束应用通用型自动机。通过利用有限集合的特定结构（共享前缀），作者证明了：

算法效率： 对于预计算有限集合上的每状态掩码，Trie 是最高效的算法，其编译时间比等效的 FSM 预计算快 196 倍。
系统性影响： 预计算掩码的能力使得无状态服务路径成为可能，从而绕过了引导式解码流水线。这一优势只有通过预计算掩码才能实现。这使得约束解码从一个瓶颈转变为批量服务中可以忽略不计的开销。
泛化性： 将强制执行机制与约束结构（例如使用字符位置掩码处理固定格式）相匹配的原则，可以为任何具有可利用规律性的约束带来巨大的加速。

作者将 Trie 自动机定位为有限集合解码的一种精确、同构的替代方案，而非近似方案，它在提供 100% 有效性的同时，在高度基数的场景下提供了数量级的性能提升。