# Trie Automata for Constrained Decoding over Large Finite Sets

arXiv: https://arxiv.org/abs/2608.12574 · HTML: https://mlsanity.com/paper/2608.12574/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 35 references that are in the map.
- First posted on arXiv 12 Aug 2026.

## Builds on (most cited first, 25 of 25)

- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Efficient Intent Detection with Dual Sentence Encoders](https://mlsanity.com/paper/2003.04807/) (2020)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [An Evaluation Dataset for Intent Classification and Out-of-Scope Prediction](https://mlsanity.com/paper/1909.02027/) (2019)
- [Autoregressive Entity Retrieval](https://mlsanity.com/paper/2010.00904/) (2020)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)
- [MASSIVE: A 1M-Example Multilingual Natural Language Understanding Dataset with 51 Typologically-Diverse Languages](https://mlsanity.com/paper/2204.08582/) (2022)
- [Prompting Is Programming: A Query Language for Large Language Models](https://mlsanity.com/paper/2212.06094/) (2022)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models](https://mlsanity.com/paper/2501.10868/) (2025)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [MCP-Zero: Active Tool Discovery for Autonomous LLM Agents](https://mlsanity.com/paper/2506.01056/) (2025)
- [Efficient Beam Search for Large Language Models Using Trie-Based Decoding](https://mlsanity.com/paper/2502.00085/) (2025)
- [Dynamic ReAct: Scalable Tool Selection for Large-Scale MCP Environments](https://mlsanity.com/paper/2509.20386/) (2025)
- [Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators](https://mlsanity.com/paper/2602.22647/) (2026)
- [Tokenization as Finite-State Transduction](https://mlsanity.com/paper/2410.15696/) (2024)
- [Zero-shot Context Biasing with Trie-based Decoding using Synthetic Multi-Pronunciation](https://mlsanity.com/paper/2508.17796/) (2025)
- [WGRAMMAR: Leverage Prior Knowledge to Accelerate Structured Decoding](https://mlsanity.com/paper/2507.16768/) (2025)

## Abstract (arXiv)

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.