推論系統
Trie Automata Precompute Token Masks, Delivering Up to 29× XGrammar’s Throughput for Finite-Choice Decoding in vLLM
A new method precomputes trie states and token masks for thousands to tens of thousands of valid strings, avoiding the cardinality bottleneck of general-purpose grammar compilation. The authors measured 219 requests per second at a batch size of 256, but have not yet released the implementation, and the figure also includes integration gains from bypassing the existing guided-decoding path.
Tool calling, product retrieval, and classification APIs often require models to output only one name from a predefined set. Existing serving systems typically compile the choices into a grammar and then compute the valid tokens at every decoding step. A study submitted on August 12 and listed among the [COLM 2026 accepted papers](https://colm.eventhosts.cc/Conferences/2026/AcceptedPapers) finds that general-purpose compilers hit a “cardinality wall” once the number of valid values reaches the thousands: even when each choice is only a short string, compilation and per-step state updates still grow rapidly.
[Trie Automata](https://arxiv.org/abs/2608.12574) first organizes all valid strings into a trie based on shared prefixes, then uses Aho–Corasick multi-pattern matching to precompute the acceptable token mask for each node. At serving time, the system only needs to retrieve the mask for the current node, so the cost no longer increases with the number of choices. Across seven tokenizers with vocabulary sizes ranging from 32K to 262K, the authors report that even 10,000 candidate values can be compiled in under 100 milliseconds while guaranteeing that every output belongs to the valid set.
The baseline is the general-purpose [XGrammar](https://github.com/mlc-ai/xgrammar), which is integrated into vLLM, SGLang, and TensorRT-LLM. The paper reports per-step valid-token computation times of 0.65 microseconds for the trie approach and 5.8 microseconds for XGrammar. With at least 300 candidates, compilation is 2× to 6.5× faster. In an end-to-end vLLM test with a batch size of 256, throughput rises from 7.5 to 219 requests per second.
The 29× figure should not be interpreted as the automaton itself being 29× faster. The gain comes from both precomputed masks and a stateless integration that can bypass the general-purpose guided-decoding pipeline. The method also applies only to known, finite sets of strings and cannot replace XGrammar’s support for JSON Schema, regular expressions, or context-free grammars. Engineering teams should next watch for the release of the authors’ vLLM modifications, memory-usage data, and multi-tenant caching strategy, and should reproduce the results using realistic choice lengths and batch-size distributions.