Trie Automata for Constrained Decoding over Large Finite Sets

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 \emph{cardinality wall}. We introduce the \emph{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 7$\times$ faster per-step valid-token computation (0.65$\mu$s vs.\ 5.8$\mu$s) compared to XGrammar, one of the primary backends in vLLM and SGLang, and 2--6.5$\times$ faster compilation at $K \geq 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 (29$\times$). The 29$\times$ 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.