大规模有限集约束解码的字典树自动机
文章背景与核心概要
随着大语言模型（LLM）在生成需严格遵循预定义架构的结构化输出方面需求日益增加，约束解码变得至关重要。一个常见的需求是将模型的生成限制在一个由大量合法字符串构成的有限集合内。传统的通用语法编译工具通常会面临“基数墙”（cardinality wall）的困境，当合法值的数量增长到数千级别时，其编译和运行速度会变得极其缓慢。
本文引入了字典树自动机（trie automaton）这一专有机制，它利用有限集结构（如共享前缀、有界深度和已知基数），通过 Aho-Corasick 多模式匹配来预计算每个节点的词元掩码。实验表明，该方法在保持 100% 输出有效性的同时，大幅提升了每步词元计算速度和批量服务吞吐量，为大规模有限集的约束解码提供了一种高效且可扩展的解决方案。
As large language models (LLMs) increasingly need to generate structured outputs that adhere to strict predefined schemas, constrained decoding becomes essential. A common requirement is restricting generation to a large finite set of valid strings. Traditional general-purpose grammar compilation tools often face a "cardinality wall," becoming prohibitively slow as the set of valid values grows into the thousands.
This paper introduces the trie automaton, a specialized mechanism leveraging finite-set structures (such as shared prefixes, bounded depth, and known cardinality) via Aho-Corasick multi-pattern matching to precompute per-node token masks.
核心发现与性能亮点：
- 更快的词元计算：相比于 XGrammar（vLLM 和 SGLang 中的主要后端），每步合法词元计算速度提升了 7 倍（\(0.65\,\mu\text{s}\) 对比 \(5.8\,\mu\text{s}\)）。
- 更优的编译性能：当 \(K \ge 300\) 时，编译速度提升了 2 至 6.5 倍。
- 批量服务可扩展性：预计算掩码实现了一种无状态的服务路径，完全绕过了引导解码（guided decoding）流水线。在批大小为 256 时，端到端 vLLM 吞吐量达到了 219 req/s（而 XGrammar 仅为 7.5 req/s），结合算法加速与集成路径优化，性能实现了 29 倍的提升。
- 稳健的可扩展性：在七个分词器系列（词表大小从 32K 到 262K）中，该字典树在 \(K = 10,000\) 时仍能保持低于 100ms 的编译时间、与集合大小无关的平稳每步开销，并严格保证 100% 的输出有效性。
Key Findings & Performance Highlights:
- Faster Token Computation: Achieves 7× faster per-step valid-token calculation (\(0.65\,\mu\text{s}\) vs. \(5.8\,\mu\text{s}\)) compared to XGrammar (a primary backend in vLLM and SGLang).
- Improved Compilation: Delivers 2–6.5× faster compilation speeds when \(K \ge 300\).
- Batch Serving Scalability: Precomputed masks allow for a stateless serving path that completely bypasses guided decoding pipelines. End-to-end vLLM throughput reaches 219 req/s compared to XGrammar's 7.5 req/s at a batch size of 256 (a 29× improvement combining algorithmic speedups with integration-path savings).
- Robust Scalability: Across seven tokenizer families (32K to 262K vocabulary sizes), the trie maintains sub-100ms compilation times up to \(K = 10,000\), a flat per-step cost regardless of set size, and a strict guarantee of 100% output validity.
🔗 全文与访问链接
🔗 Full-Text & Access Links
许可证：知识共享署名 4.0 国际
