Trie Automata for Constrained Decoding over Large Finite Sets
06:00 · August 15, 2026 · arXiv cs.AI RSS
Large language models increasingly need to generate structured outputs that conform to predefined schemas, with one common constraint being selection from a finite set of valid strings. Current constrained decoding systems handle this through general-purpose grammar compilation, which becomes prohibitively slow as the number of valid values grows into the thousands, a cardinality wall. We introduce the trie automaton, a specialized mechanism that exploits finite-set structure (shared prefixes, bounded depth, known cardinality) via Aho-Corasick multi-pattern matching to precompute per-node token masks. The trie achieves 7X faster per-step valid-token computation (0.65 us vs. 5.8 us) compared to XGrammar, one of the primary backends in vLLM and SGLang, and 2--6.5X faster compilation at K >= 300. Because precomputed masks enable a stateless serving path that bypasses the guided decoding pipeline, this advantage compounds in batch serving: end-to-end vLLM throughput reaches 219 req/s vs. XGrammar's 7.5 req/s at batch size 256 (29X). The 29X combines the algorithmic speedup with integration-path savings that only precomputed masks can unlock. Across seven tokenizer families (32K--262K vocabulary), the trie maintains sub-100ms compilation up to K = 10,000 and flat per-step cost regardless of set size, while guaranteeing 100% output validity.
Summary
Large language models increasingly require structured outputs that match predefined schemas, yet one of the most common constraints—selecting a string from a known finite set—exposes a practical limit in current systems. General-purpose grammar compilers treat an enum of several thousand values the same way they treat nested JSON schemas, producing automata whose construction time and per-step masking cost grow rapidly with set cardinality. The resulting “cardinality wall” already restricts commercial offerings: OpenAI caps enums at roughly 1,000 entries, Gemini at about 120, and Anthropic at a few hundred before compilation times become prohibitive.
The paper presents the trie automaton as a specialized replacement for the finite-state-machine layer when the constraint is exactly a finite union of strings. It builds a character-level trie directly from the allowed set, then uses Aho-Corasick multi-pattern matching to pre-compute, for every trie node, the vocabulary tokens that can legally extend the prefix reaching that node. Because the masks are computed once and stored, decoding reduces to an O(1) table lookup per step rather than repeated automaton transitions over the full vocabulary. The same pre-computed masks also allow a stateless serving path that bypasses the guided-decoding pipeline entirely.
Empirical measurements across seven tokenizer families show compilation remaining under 100 ms up to 10,000 entries and per-step masking at 0.65 µs—roughly seven times faster than XGrammar. In batched vLLM serving at size 256 the end-to-end throughput reaches 219 requests per second versus 7.5 for the baseline, a 29-fold improvement that combines the algorithmic gain with the simpler integration path. The authors supply complexity bounds, equivalence proofs, and measurements on both synthetic and production-style workloads such as tool registries and medical-code classification, confirming that the approach scales to sets an order of magnitude larger than current practical limits while guaranteeing 100 % output validity.
Why it matters
Offers actionable, high-technical-depth optimizations for structured LLM outputs that Dutch researchers and advanced practitioners can implement in vLLM/SGLang pipelines or similar serving stacks.
