随着大型语言模型生成结构化输出的需求日益增长，约束解码系统需要能够高效地处理从大型有限集中的字符串选择。现有的约束解码系统通常通过通用语法编译来实现这一功能，但当有效值的数量达到数千时，编译速度变得非常慢。我们提出了 Trie 自动机，一种专门利用有限集结构（共享前缀、有界深度、已知基数）的机制，通过 Aho-Corasick 多模式匹配来预计算每个节点的令牌掩码。Trie 自动机相比 XGrammar（vLLM 和 SGLang 中的主要后端之一）实现了 7 倍更快的每步有效令牌计算（0.65 us vs. 5.8 us），并且在 K = 300 时编译速度快 2--6.5 倍。因为预计算的掩码使得状态无关的服务路径可以绕过有导向的解码管道，这一优势在批量服务中得到了复合：从端到端的 vLLM 吞吐量达到 219 req/s，而 XGrammar 的吞吐量为 7.5 req/s（批量大小为 256，29 倍）。在七个令牌器家族（32K-262K 词汇量）中，Trie 自动机保持了在 K = 10,000 时的子 100ms 编译时间和与集大小无关的每步成本，同时保证了 100% 的输出有效性。 博主点评： Trie 自动机为大型语言模型中的约束解码带来了高效的解决方案，尤其是在处理大型有限集时，其预计算的掩码机制使得解码过程变得更加快速和高效，具有广泛的应用前景。