Trie Automata for Constrained Decoding over Large Finite Sets

# Trie Automata for Constrained Decoding over Large Finite Sets
Source: [https://arxiv.org/html/2608.12574](https://arxiv.org/html/2608.12574)
###### Abstract

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 7×\\timesfaster per\-step valid\-token computation \(0\.65μ\\mus vs\. 5\.8μ\\mus\) compared to XGrammar, one of the primary backends in vLLM and SGLang, and 2–6\.5×\\timesfaster compilation atK≥300K\\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\)\. This 29×\\timescombines the algorithmic speedup with integration\-path savings that only precomputed masks make possible\. Across seven tokenizer families \(32K–262K vocabulary\), the trie maintains sub\-100ms compilation up toK=10,000K=10\{,\}000and flat per\-step cost regardless of set size, while guaranteeing 100% output validity\.

## 1Introduction

Constrained decoding has become the standard mechanism for guaranteeing that LLM outputs conform to a schema\([34](https://arxiv.org/html/2608.12574#bib.bib1);[15](https://arxiv.org/html/2608.12574#bib.bib6)\)\. By masking invalid tokens at each generation step, it eliminates malformed JSON, hallucinated field names, and invalid values\. Major LLM providers now offer it, and open\-source engines like Outlines, XGrammar\([10](https://arxiv.org/html/2608.12574#bib.bib4)\), and SGLang\([35](https://arxiv.org/html/2608.12574#bib.bib2)\)have made it accessible to any application\. These systems compile a JSON schema \(or grammar\) into a general\-purpose automaton \(a finite\-state machine, pushdown automaton, or Earley parser\) and use it to mask tokens at each decoding step\. This architecture handles arbitrary schemas, including nested objects, recursive structures, and complex regex patterns\. However, it applies the same general\-purpose compilation pipeline to all constraints, regardless of their actual complexity\. A deeply nested recursive JSON schema and a flat list of 1,000 tool names both undergo the same compilation pipeline, a fundamental mismatch between general\-purpose engines and simple constraints\.

This uniformity creates a bottleneck for one of the most common constraints in production:*select one string from a known finite set*\. OpenAI’s structured outputs impose a 1,000 enum limit\([26](https://arxiv.org/html/2608.12574#bib.bib25)\), Google Gemini fails at approximately 120 enum values\([17](https://arxiv.org/html/2608.12574#bib.bib26)\), and Anthropic’s 180\-second compilation timeout\([3](https://arxiv.org/html/2608.12574#bib.bib27)\)implies a similar wall at a few hundred values\. These limits are increasingly consequential as LLM applications shift from open\-ended generation to structured tool use\. In agentic workflows, an LLM must select which tool to invoke from a registry that may contain 500–5,000\+ APIs\([28](https://arxiv.org/html/2608.12574#bib.bib19);[11](https://arxiv.org/html/2608.12574#bib.bib20);[14](https://arxiv.org/html/2608.12574#bib.bib21)\); as Model Context Protocol \(MCP\) ecosystems grow and organizations expose internal services as tools, these registries expand rapidly, often exceeding provider enum limits within months of deployment\. The same pattern appears in zero\-shot classification over label sets like product taxonomies \(1,500\+ categories\), ICD\-10\-CM medical codes \(74,719 codes in the 2026 CMS release\([6](https://arxiv.org/html/2608.12574#bib.bib10)\)\), or legal case types \(10,000\+\); in entity linking against knowledge bases\([9](https://arxiv.org/html/2608.12574#bib.bib18)\)with tens of thousands of entries; and in dynamic per\-query constraints from retrieval\-augmented systems where the valid set changes each query, preventing amortization of compilation costs\. In all these cases, the constraint is a finite union of stringss1\|s2​\|⋯\|​sKs\_\{1\}\|s\_\{2\}\|\\cdots\|s\_\{K\}\. While this is a regular language with no Kleene star, recursion, or nested structure, current systems compile it through the same regex\-to\-NFA\-to\-DFA pipeline used for arbitrary grammars, at a cost that grows with both the number of strings and the alphabet size\. This creates what we term the*cardinality wall*: a maximumKKbeyond which constrained decoding becomes impractically slow\.

The core insight is that different constraint types deserve different enforcement mechanisms\. A finite set of strings has exploitable structure: shared prefixes, finite depth, and known cardinality\. We introduce the*trie automaton*, a drop\-in replacement for the FSM layer in existing constrained decoding pipelines, specialized for finite\-set constraints\. It \(1\) builds a character\-level trie\([13](https://arxiv.org/html/2608.12574#bib.bib16)\)directly from the set, \(2\) precomputes vocabulary\-aware token masks at each trie node using Aho\-Corasick multi\-pattern matching\([1](https://arxiv.org/html/2608.12574#bib.bib22)\)to align BPE tokens with character\-level trie paths, and \(3\) serves masks via𝒪⁡\(1\)\\mathcal\{O\}\(1\)cached lookups at decode time\. The central algorithmic challenge is BPE\-trie alignment: a single BPE token can span multiple trie nodes, and a vocabulary of32​K32\\text\{K\}–262​K262\\text\{K\}tokens must be matched against every node\. To our knowledge, this alignment problem has not been addressed in the constrained decoding literature; prior trie\-based work\([9](https://arxiv.org/html/2608.12574#bib.bib18)\)sidesteps it by operating at token granularity\. We show that it reduces to multi\-pattern string matching, solvable in time linear in the trie size rather than quadratic in the vocabulary, enabling sub\-100ms compilation up toK=10,000K=10\{,\}000\. Figure[1](https://arxiv.org/html/2608.12574#S1.F1)illustrates the cardinality wall and how the trie automaton overcomes it, expanding the practical limit from∼\\sim1,000 to∼\\sim100,000 values while maintaining 100% constraint compliance\.

This work makes two main contributions: \(1\) We introduce the*trie automaton*, a specialized constrained decoding backend for finite\-set constraints that combines character\-level tries, Aho\-Corasick multi\-pattern matching, and precomputed token masks to achieve𝒪​\(\|valid​\[st\]\|\)\\mathcal\{O\}\(\|\\text\{valid\}\[s\_\{t\}\]\|\)per\-step masking \(empirically 10–100 tokens after 3–4 characters of prefix, yielding effectively constant cost versus the𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)cost of general FSM approaches\)\. The BPE\-trie alignment problem reduces to multi\-pattern string matching, yielding 2–6\.5×\\timesfaster compilation and up to 29×\\timeshigher end\-to\-end throughput in batch serving: 7×\\timesfrom faster per\-step masking, compounded by a simpler serving path that only precomputed masks can use\. \(2\) We empirically characterize the cardinality wall across seven tokenizer families \(32K–262K vocabulary\), showing that matching enforcement mechanisms to constraint structure, including the integration path, overcomes scaling bottlenecks\. Precomputed masks let the trie bypass the guided decoding pipeline entirely; FSM approaches cannot\.

Enum Cardinality \(KK\)Compilation Time101001K10K100K1ms10ms100ms1sGeminiAnthropicOpenAI40×\\times

\(a\) Compilation time

Batch sizeThroughput \(req/s\)124816326412825611010029×\\times

\(b\) vLLM throughput \(K=1,000K\{=\}1\{,\}000\)

Trie \(ours\)FSM \(XGrammar\)

Figure 1:\(a\) Compilation time vs\. enum cardinality \(Qwen3\-8B, log\-log scale\)\. Dotted lines mark documented provider limits \(Gemini∼\{\\sim\}120, Anthropic∼\{\\sim\}200, OpenAI 1,000\)\. The trie is flat at 30–67ms; XGrammar crosses the trie atK≈300K\{\\approx\}300and reaches 2\.7s atK=100​KK\{=\}100\\text\{K\}\. \(b\) End\-to\-end vLLM throughput \(log scale\)\. The 29×\\timesgap atB=256B\{=\}256combines 7×\\timesper\-step algorithmic advantage with integration\-path savings from precomputed masks \(Section[5](https://arxiv.org/html/2608.12574#S5)\)\.
## 2Background and Problem Formulation

Constrained decoding restricts the model’s output distribution at each stepttto tokens that can lead to valid completions\. Given a vocabulary𝒱\\mathcal\{V\}of sizeVVand a regular languageℒ\\mathcal\{L\}defined by a schema, the constrained distribution is:

pc​\(yt∣𝐲<t\)=p\(yt∣𝐲<t\)⋅𝟏\[yt∈𝒜\(𝐲<t\)\]Z⁡\(𝐲<t\)p\_\{c\}\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)=\\frac\{p\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)\\cdot\\mathbf\{1\}\[y\_\{t\}\\in\\mathcal\{A\}\(\\mathbf\{y\}\_\{<t\}\)\]\}\{Z\(\\mathbf\{y\}\_\{<t\}\)\}\(1\)where𝒜⁡\(𝐲<t\)⊆𝒱\\mathcal\{A\}\(\\mathbf\{y\}\_\{<t\}\)\\subseteq\\mathcal\{V\}is the set of allowed tokens given the prefix, computed by maintaining an FSM statest=δ∗​\(s0,chars​\(𝐲<t\)\)s\_\{t\}=\\delta^\{\*\}\(s\_\{0\},\\text\{chars\}\(\\mathbf\{y\}\_\{<t\}\)\)\(whereδ∗\\delta^\{\*\}extends the character\-level transition function to token sequences ands0s\_\{0\}is the start state\) and checking valid transitions; equivalently,𝒜⁡\(𝐲<t\)=𝒜⁡\(st\)\\mathcal\{A\}\(\\mathbf\{y\}\_\{<t\}\)=\\mathcal\{A\}\(s\_\{t\}\)depends only on the current statests\_\{t\}, not the full prefix\. An enum constraintℰ=\{e1,e2,…,eK\}\\mathcal\{E\}=\\\{e\_\{1\},e\_\{2\},\\ldots,e\_\{K\}\\\}defines the regular languageℒℰ=\{e1\}∪\{e2\}∪⋯∪\{eK\}\\mathcal\{L\}\_\{\\mathcal\{E\}\}=\\\{e\_\{1\}\\\}\\cup\\\{e\_\{2\}\\\}\\cup\\cdots\\cup\\\{e\_\{K\}\\\}\. LetLmax=maxi⁡\|ei\|L\_\{\\max\}=\\max\_\{i\}\|e\_\{i\}\|be the maximum string length,ℓ\\ellthe maximum token length in characters, and\|Σ\|\|\\Sigma\|the alphabet size \(256 for byte\-level BPE tokenizers, which we refer to as “characters” throughout for readability; multi\-byte UTF\-8 sequences and emoji are handled naturally since both the trie and BPE tokenizers operate at byte granularity\)\. The standard approach converts the enum to a regular expressione1\|e2​\|⋯\|​eKe\_\{1\}\|e\_\{2\}\|\\cdots\|e\_\{K\}and compiles it into a deterministic FSM\. This creates problematic scaling: the DFA has𝒪⁡\(K⋅Lmax\)\\mathcal\{O\}\(K\\cdot L\_\{\\max\}\)states in the worst case, per\-step masking costs𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)\(checking each token’s character sequence against the FSM\), and compilation costs𝒪⁡\(K⋅Lmax⋅\|Σ\|\)\\mathcal\{O\}\(K\\cdot L\_\{\\max\}\\cdot\|\\Sigma\|\), creating the cardinality wall observed in practice \(detailed analysis in Appendices[A](https://arxiv.org/html/2608.12574#A1)and[G](https://arxiv.org/html/2608.12574#A7)\)\.

To illustrate concretely, consider an agentic system routing requests to the correct tool from a registry of 2,000 APIs\([11](https://arxiv.org/html/2608.12574#bib.bib20);[14](https://arxiv.org/html/2608.12574#bib.bib21)\)\. FSM compilation requires processing 15\.4 million character\-level transitions \(25–50 seconds\), while per\-step masking requires∼\{\\sim\}1\.3 million effective FSM operations per tool selection when accounting for cache effects \(Appendix[F](https://arxiv.org/html/2608.12574#A6)\), making the system unusable for interactive workflows that demand sub\-second tool dispatch\.

## 3Related Work

#### Constrained decoding\.

Early approaches enforced specific constraint types: lexically constrained beam search\([27](https://arxiv.org/html/2608.12574#bib.bib15);[2](https://arxiv.org/html/2608.12574#bib.bib17)\), predicate logic constraints\([25](https://arxiv.org/html/2608.12574#bib.bib12);[24](https://arxiv.org/html/2608.12574#bib.bib13)\), and incremental parsing for code generation\([29](https://arxiv.org/html/2608.12574#bib.bib14)\)\. Outlines\([34](https://arxiv.org/html/2608.12574#bib.bib1)\)introduced the dominant paradigm of compiling JSON schemas into FSMs for token masking, extended to context\-free grammars by[16](https://arxiv.org/html/2608.12574#bib.bib3)and formalized by[20](https://arxiv.org/html/2608.12574#bib.bib7)\. LMQL\([4](https://arxiv.org/html/2608.12574#bib.bib8)\)embedded constraints into a query language\. Subsequent work optimized within this paradigm: SGLang\([35](https://arxiv.org/html/2608.12574#bib.bib2)\)introduced jump\-forward decoding, XGrammar\([10](https://arxiv.org/html/2608.12574#bib.bib4)\)optimized vocabulary partitioning, and SynCode\([32](https://arxiv.org/html/2608.12574#bib.bib5)\)and[33](https://arxiv.org/html/2608.12574#bib.bib9)continued this trajectory\. LLGuidance\([15](https://arxiv.org/html/2608.12574#bib.bib6)\)takes a different approach: an Earley parser with lazy automaton construction that avoids upfront DFA compilation\. On Qwen3\-8B \(151K vocabulary\), LLGuidance compiles enum schemas in 0\.6–24ms forK=10K=10–10,00010\{,\}000, far faster than XGrammar’s 5–695ms\. However, its per\-step cost remains𝒪⁡\(V\)\\mathcal\{O\}\(V\): we measure 73–141μ\\mus per mask computation, compared to our trie’s 0\.65μ\\mus \(110–215×\\timesslower; Appendix[M](https://arxiv.org/html/2608.12574#A13)\)\. The two are complementary: LLGuidance excels at schema diversity with negligible startup, while the trie exploits finite\-set structure for per\-step speedups that compound in batch serving\. Despite these advances, persistent enum limits across major providers indicate that no current system adequately addresses the cardinality wall\.

#### Trie\-based generation\.

GENRE\([9](https://arxiv.org/html/2608.12574#bib.bib18)\)demonstrated trie\-constrained generation for entity linking with a fine\-tuned seq2seq model, building a*token\-level*trie whose nodes are pre\-tokenized token IDs, which sidesteps the vocabulary\-trie alignment problem but shares prefixes only at token boundaries\. Our trie automaton instead builds a*character\-level*trie that maximizes prefix sharing regardless of tokenizer, solving the BPE alignment problem via Aho\-Corasick multi\-pattern matching\([1](https://arxiv.org/html/2608.12574#bib.bib22)\)to determine which BPE tokens from a vocabulary of32​K32\\text\{K\}–262​K262\\text\{K\}entries are valid continuations at each node \(Section[4\.2](https://arxiv.org/html/2608.12574#S4.SS2)\)\. We compare the two constructions directly in Section[4\.2](https://arxiv.org/html/2608.12574#S4.SS2): they cross over atK≈1,000K\\approx 1\{,\}000, exactly the cardinality\-wall regime, and the character\-level trie is tokenization\-agnostic where GENRE’s is tied to one fixed tokenization\. Concurrent work by[30](https://arxiv.org/html/2608.12574#bib.bib28)flattens token\-level prefix trees into CSR sparse matrices for vectorized TPU/GPU execution; like GENRE, it operates on small semantic ID vocabularies \(\|𝒱\|≈2,048\|\\mathcal\{V\}\|\\approx 2\{,\}048\) where the BPE alignment problem does not arise\. Tries also structure LLM decoding pipelines beyond finite\-set enforcement:[7](https://arxiv.org/html/2608.12574#bib.bib33)share KV\-cache across beams with common prefixes to accelerate beam search, and[23](https://arxiv.org/html/2608.12574#bib.bib35)apply trie\-based contextual biasing for rare words in ASR via soft shallow\-fusion rewards\. Both index emerging hypotheses or bias scores rather than a fixed enum, and are complementary to the hard\-constraint masking we study\. Finally,[8](https://arxiv.org/html/2608.12574#bib.bib34)cast tokenization itself as finite\-state transduction and give a polynomial\-time framework for enforcing canonical tokenization, complementary to our character\-level constraint and layerable on top of it without changing the trie \(Appendix[H\.9](https://arxiv.org/html/2608.12574#A8.SS9)\)\.

## 4Methods

### 4\.1Character\-Level Trie with Precomputed Masks

Given an enumℰ=\{e1,…,eK\}\\mathcal\{E\}=\\\{e\_\{1\},\\ldots,e\_\{K\}\\\}, we build a character\-level trie𝒯\\mathcal\{T\}by inserting each string character\-by\-character\. The trie\([13](https://arxiv.org/html/2608.12574#bib.bib16)\)merges shared prefixes: if many tool names start withget\_, they share a single prefix path rather than duplicating it for each value\. This reduces the number of nodes from𝒪⁡\(K⋅Lmax\)\\mathcal\{O\}\(K\\cdot L\_\{\\max\}\)\(as in the equivalent DFA\) to𝒪⁡\(Nchars\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\), whereNchars=∑i=1K\|ei\|N\_\{\\text\{chars\}\}=\\sum\_\{i=1\}^\{K\}\|e\_\{i\}\|is the total character count\. For each trie nodenn, we precompute a setvalid​\[n\]⊆𝒱\\text\{valid\}\[n\]\\subseteq\\mathcal\{V\}of vocabulary tokens that are valid continuations fromnn\. At decode time, masking reduces to a direct lookup:𝒜⁡\(st\)=valid​\[st\]\\mathcal\{A\}\(s\_\{t\}\)=\\text\{valid\}\[s\_\{t\}\], transforming per\-step cost from𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)\(scanning all tokens against the FSM\) to𝒪​\(\|valid​\[st\]\|\)\\mathcal\{O\}\(\|\\text\{valid\}\[s\_\{t\}\]\|\)\(iterating the precomputed set\)\.

The challenge is computingvalid​\[n\]\\text\{valid\}\[n\]efficiently\. A tokenvvis valid at nodennif its character sequence traces a path starting atnnthat stays within the trie, but BPE tokens are multi\-character, so a single token can traverse several trie edges\. For example, given enum valuesmedical\_billingandmedical\_coding, the token‘‘medical’’\(7 characters\) is valid at the root because it traces the path through nodesm→\\toe→⋯→\\to\\cdots\\tol, while the token‘‘\_bill’’is valid at the node afterlbecause it continues along the\_billingbranch \(Figure[2](https://arxiv.org/html/2608.12574#S4.F2)\)\. A naive approach checks every token at every node by simulating the character walk, costing𝒪⁡\(Nchars⋅V⋅ℓ\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot V\\cdot\\ell\), which is prohibitive for vocabularies of32​K32\\text\{K\}–262​K262\\text\{K\}tokens\.

∘\\circmedical\_billingcodingationmedical\_ationPrecomputed masks
valid\[root\] = \{medic, m, …\}
valid\[medic\] = \{al\_,ation\}
valid\[l\_\] = \{billing, coding\}Figure 2:The BPE\-trie alignment problem\. A character\-level trie encodes three enum values with shared prefix structure\. BPE tokens \(colored brackets\) span multiple trie edges:medictraverses 5 character nodes from the root\. At each node, we precompute the set of valid BPE tokens \(right\), enabling precomputed mask lookups at decode time\.
### 4\.2Efficient Mask Precomputation via Multi\-Pattern Matching

We solve the precomputation problem by reducing it to*multi\-pattern string matching*: given a set of patterns \(the vocabulary token strings\) and a text \(each root\-to\-leaf path in the trie\), find all positions where any pattern occurs\. The Aho\-Corasick \(AC\) algorithm\([1](https://arxiv.org/html/2608.12574#bib.bib22)\)solves this classic problem by building a finite automaton from the pattern set in𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)time, whereℓ\\ellis the maximum token length in characters, then processing any input text in a single linear pass, reporting all pattern matches as they are encountered\. The processing cost is𝒪⁡\(L\+m\)\\mathcal\{O\}\(L\+m\)for a text of lengthLLwithmmreported matches, independent of the number of patternsVV\. Since at each of theLLcharacter positions at mostℓ\\elltokens of different lengths can match,m≤L⋅ℓm\\leq L\\cdot\\ell, so scanning a trie path of lengthLLcosts𝒪⁡\(L⋅ℓ\)\\mathcal\{O\}\(L\\cdot\\ell\)rather than𝒪⁡\(L⋅V⋅ℓ\)\\mathcal\{O\}\(L\\cdot V\\cdot\\ell\)\. We apply this as follows:

1. 1\.Build AC automaton from vocabulary\.Insert each vocabulary token’s character string as a pattern\. This constructs the automaton in𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)time\.
2. 2\.Traverse the trie with the automaton\.Before any decoding begins, we perform a depth\-first traversal of the trie, maintaining the AC automaton state across edges\. The AC state is a single integer \(current node index\), so save/restore at branch points is trivial \(push/pop one integer per DFS stack frame\), and each edge is processed exactly once\. At each trie nodenn, the automaton identifies which vocabulary tokens have a character string that starts atnnand follows a valid path in the trie\. A matched tokenvvis added tovalid​\[n\]\\text\{valid\}\[n\]if its characters trace a path fromnnthat either reaches a leaf \(completing an enum value\) or lands on an internal node \(allowing continuation by subsequent tokens\)\. Tokens that would “overshoot” a leaf, i\.e\., whose characters extend beyond the end of an enum value, are excluded\. When an enum value is a proper prefix of another \(e\.g\.,"get"and"get\_user"\), the trie marks the shorter value’s terminal node as both a leaf \(where EOS is valid\) and an internal node \(where continuation tokens are valid\), ensuring both values are reachable\. This is done once per schema and cached\.

This reduces precomputation from𝒪⁡\(Nchars⋅V⋅ℓ\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot V\\cdot\\ell\)to𝒪⁡\(\(Nchars\+V\)⋅ℓ\)\\mathcal\{O\}\(\(N\_\{\\text\{chars\}\}\+V\)\\cdot\\ell\), a factor ofVVimprovement\. In practice, the AC automaton construction \(𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)\) dominates the total compilation cost becauseV≫NcharsV\\gg N\_\{\\text\{chars\}\}for typical enum sizes: withV=151​KV=151\\text\{K\}andℓ=4\\ell=4, the AC construction requires∼600​K\{\\sim\}600\\text\{K\}operations regardless ofKK, while the trie traversal adds onlyNchars⋅ℓN\_\{\\text\{chars\}\}\\cdot\\elloperations \(e\.g\.,240​K240\\text\{K\}atK=2,000K=2\{,\}000\)\. This explains the empirically observed near\-flat compilation time \(30–40ms for Qwen3\-8B acrossK=10K=10–10,00010\{,\}000; 67ms atK=100,000K=100\{,\}000\): the cost is dominated by theKK\-independent AC construction over the vocabulary\. Since the AC automaton depends only on the tokenizer \(not the enum set\), it can be built once per tokenizer and reused across all enum schemas, reducing per\-schema compilation to just the trie traversal:𝒪⁡\(Nchars⋅ℓ\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot\\ell\)\. At decode time, masking is a direct lookup:𝒜⁡\(st\)=valid​\[st\]\\mathcal\{A\}\(s\_\{t\}\)=\\text\{valid\}\[s\_\{t\}\], costing𝒪​\(\|valid​\[st\]\|\)\\mathcal\{O\}\(\|\\text\{valid\}\[s\_\{t\}\]\|\)instead of𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)\. Note that applying the mask to the logits vector is𝒪⁡\(V\)\\mathcal\{O\}\(V\)regardless of method \(setting invalid logits to−∞\-\\infty\); the savings is in*computing*which tokens are valid, not in applying the result\. Since\|valid​\[st\]\|\|\\text\{valid\}\[s\_\{t\}\]\|shrinks exponentially with trie depth \(after 3–4 characters of prefix, typically 10–100 tokens remain valid\), the lookup cost is effectively constant at 0\.65μ\\mus regardless ofKKor vocabulary size\. While the worst case is𝒪⁡\(V\)\\mathcal\{O\}\(V\)\(at the root node\), the rapid prefix\-driven shrinkage means the practical per\-step cost is orders of magnitude below FSM approaches, which must scan allVVtokens regardless of constraint structure\.

Table[1](https://arxiv.org/html/2608.12574#S4.T1)summarizes both effects against the FSM\. The compilation advantage comes from avoiding the\|Σ\|\|\\Sigma\|factor \(the FSM fills transition entries for all 256 byte values at each state, while the trie processes only characters that appear\); the per\-step advantage comes from replacing a full vocabulary scan with a cached lookup whose working set \(<<1 KB\) fits in L1 cache, versus the FSM’s∼\{\\sim\}47 MB transition table that overflows L2 \(Appendix[G](https://arxiv.org/html/2608.12574#A7)\)\.

Table 1:Complexity comparison between FSM and trie automaton\. Concrete values useK=2,000K=2\{,\}000,Lmax=30L\_\{\\max\}=30,\|Σ\|=256\|\\Sigma\|=256,V=32,000V=32\{,\}000,ℓ=4\\ell=4\.The trie automaton is not an approximation: it produces*identical outputs*to FSM\-based constrained decoding, which is the paper’s central formal guarantee and the basis for the 100% validity we report\.

###### Proposition 1\(Output equivalence\)\.

Let𝒱dec⊆𝒱\\mathcal\{V\}\_\{\\textup\{dec\}\}\\subseteq\\mathcal\{V\}be the vocabulary tokens with valid character decompositions \(excluding special tokens such as<pad\>,<unk\>\)\. For any enumℰ\\mathcal\{E\}and any prefix𝐲<t\\mathbf\{y\}\_\{<t\}, the constrained distributions of the FSM and the trie automaton are identical,pcFSM​\(yt∣𝐲<t\)=pctrie​\(yt∣𝐲<t\)p\_\{c\}^\{\\textup\{FSM\}\}\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)=p\_\{c\}^\{\\textup\{trie\}\}\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)for allyt∈𝒱decy\_\{t\}\\in\\mathcal\{V\}\_\{\\textup\{dec\}\}\. Consequently, greedy decoding and fixed\-seed sampling produce identical outputs under both methods\.

*Proof sketch\.*The valid\-token sets suffice, sincepc\(yt∣𝐲<t\)∝p\(yt∣𝐲<t\)⋅𝟏\[yt∈𝒜\(st\)\]p\_\{c\}\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)\\propto p\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)\\cdot\\mathbf\{1\}\[y\_\{t\}\\in\\mathcal\{A\}\(s\_\{t\}\)\]\. By Myhill\-Nerode, the equivalence classes ofℒℰ\\mathcal\{L\}\_\{\\mathcal\{E\}\}are exactly the distinct enum\-value prefixes \(plus a dead state\), so the trie is isomorphic to the minimal DFA forℒℰ\\mathcal\{L\}\_\{\\mathcal\{E\}\}and their transition functions agree\. Both methods admitvvatsts\_\{t\}iff its characters trace a live path fromsts\_\{t\}that can still reach an accept state, so the sets coincide\. The equivalence is over the decodable vocabulary𝒱dec\\mathcal\{V\}\_\{\\text\{dec\}\}; the two can differ only in the trailing EOS, which does not change the decoded string\. The full proof and EOS handling are in Appendix[G](https://arxiv.org/html/2608.12574#A7)\.

#### Worked example\.

Considerℰ=\{medical\_billing,medical\_coding,medical\_records\}\\mathcal\{E\}=\\\{\\texttt\{medical\\\_billing\},\\texttt\{medical\\\_coding\},\\texttt\{medical\\\_records\}\\\}and a toy vocabulary\{medical,\_bill,\_cod,\_rec,ing,…\}\\\{\\texttt\{medical\},\\texttt\{\\\_bill\},\\texttt\{\\\_cod\},\\texttt\{\\\_rec\},\\texttt\{ing\},\\ldots\\\}\. The trie merges the sharedmedical\_prefix into one path of nine nodes and then branches three ways; call the branch nodenn\(reached aftermedical\_\) and the node aftermedicalits parentn′n^\{\\prime\}\. Traversing the trie while carrying the AC state, the automaton reportsmedicalending atn′n^\{\\prime\}, somedicalentersvalid​\[root\]\\text\{valid\}\[\\text\{root\}\]; descending each branch reports\_bill,\_cod, and\_rec, all starting atn′n^\{\\prime\}, so all three entervalid​\[n′\]\\text\{valid\}\[n^\{\\prime\}\]\. Because the DFS restores the AC state to its value atn′n^\{\\prime\}before each branch, the three suffix tokens are attributed to the same node rather than leaking across branches\. The precomputed masks are thereforevalid​\[root\]=\{medical\}\\text\{valid\}\[\\text\{root\}\]=\\\{\\texttt\{medical\}\\\}andvalid​\[n′\]=\{\_bill,\_cod,\_rec\}\\text\{valid\}\[n^\{\\prime\}\]=\\\{\\texttt\{\\\_bill\},\\texttt\{\\\_cod\},\\texttt\{\\\_rec\}\\\}, with a single continuation token at each deeper node\. At decode time the model emitsmedicalfrom the root, then chooses one of\_bill/\_cod/\_recto commit to a value, and follows the unique remaining path to the leaf, so the vocabulary scan for the shared prefix is paid once at compile time rather than at every step\. A full trace with failure links and the mask at every node is given in Appendix[G\.1](https://arxiv.org/html/2608.12574#A7.SS1)\.

#### Why character\-level rather than token\-level?

GENRE\([9](https://arxiv.org/html/2608.12574#bib.bib18)\)avoids the BPE\-alignment problem by building the trie over*token IDs*: each enum value is pre\-tokenized once and the valid tokens at any node are simply its children, requiring no vocabulary scan, no AC automaton, and no mask precomputation\. The character\-level construction is more expensive per schema, and the reason to prefer it is how the two scale withKK\. A token\-level trie shares prefixes only at token boundaries: two values sharing a 10\-character prefix may share a single token\-level node if tokenized differently, so its size, and hence its compilation cost, grows roughly linearly withKK\. The character\-level trie merges every shared character, and its dominant cost is theKK\-independent AC build, which amortizes across all shared prefixes\. Table[2](https://arxiv.org/html/2608.12574#S4.T2)shows the consequence: the token trie is faster belowK≈1,000K\\approx 1\{,\}000\(it simply does less work\), but the two cross over there and the char trie is7×7\\timesfaster byK=10,000K=10\{,\}000\. This crossover sits exactly at the cardinality wall we target, namely provider limits of 120 to 1,000 and dynamic per\-query sets that force recompilation, so the token\-level trie scales linearly*into*the wall while the char\-level trie clears it\. Per\-step masking is sub\-microsecond for both, both produce byte\-identical outputs \(Proposition[1](https://arxiv.org/html/2608.12574#Thmproposition1)\), and a Python token\-trie reproduces the same crossover, confirming the effect is algorithmic, not a Rust\-vs\-Python artifact \(Appendix[H\.8](https://arxiv.org/html/2608.12574#A8.SS8)\)\. The character\-level construction is also a drop\-in backend for any tokenizer and is tokenization\-agnostic \(Appendix[H\.9](https://arxiv.org/html/2608.12574#A8.SS9)\), whereas GENRE’s trie is tied to one fixed tokenization\.

Table 2:Compilation: character\-level trie \+ Aho\-Corasick vs\. GENRE\-style token\-level trie \(Qwen3\-8B, 151K vocab, synthetic tools\)\. The token trie grows withKK; the char trie pays a fixed∼30\{\\sim\}30ms AC\-build overhead and stays flat\. Both yield byte\-identical outputs \(Appendix[H\.8](https://arxiv.org/html/2608.12574#A8.SS8)\)\.

### 4\.3Extensions and Integration

The trie automaton is designed as a*drop\-in component*for mixed schemas: the system routes finite\-set constraints to the trie while delegating structural constraints to the standard FSM/PDA backend, requiring no changes to user schemas\. ForK\>50,000K\>50\{,\}000, we sketch two preliminary extensions in Appendices[I](https://arxiv.org/html/2608.12574#A9)and[J](https://arxiv.org/html/2608.12574#A10)for future directions: hierarchical schema rewriting \(𝒪⁡\(K\)\\mathcal\{O\}\(\\sqrt\{K\}\)effective per\-step cardinality\) and speculative short\-circuiting\.

## 5Experiments

We evaluate the trie automaton on latency, compilation time, and accuracy/validity across various open\-sourced model series on NVIDIA A100 GPUs\. The primary comparison is against xgrammar\([10](https://arxiv.org/html/2608.12574#bib.bib4)\), the backend used by vLLM and SGLang\. The trie automaton is implemented in Rust with Python bindings via PyO3; XGrammar is implemented in C\+\+ with Python bindings\. Full experimental details are in Appendix[C](https://arxiv.org/html/2608.12574#A3)\.

### 5\.1Latency and Scalability

Table[4](https://arxiv.org/html/2608.12574#S5.T4)shows the performance breakdown acrossK∈\{10,100,1,000,10,000\}K\\in\\\{10,100,1\{,\}000,10\{,\}000\\\}for XGrammar\([10](https://arxiv.org/html/2608.12574#bib.bib4)\), LLGuidance\([15](https://arxiv.org/html/2608.12574#bib.bib6)\), and our trie\. All benchmarks run on NVIDIA A100 GPUs \(80GB\) with AMD EPYC 7R32 CPUs \(96 cores\)\.

Three approaches occupy distinct points in the compilation\-vs\-masking tradeoff \(Table[18](https://arxiv.org/html/2608.12574#A13.T18)\)\. LLGuidance achieves near\-zero compilation \(0\.6–24ms\) but per\-step masking costs 73–141μ\\mus\. XGrammar balances both \(3–239ms compilation, 5–10μ\\mus masking\)\. The trie minimizes per\-step cost \(0\.65μ\\mus\) through precomputation, with nearly\-flat compilation \(30–40ms\)\. For one\-shot dynamic schemas where compilation dominates \(e\.g\., retrieval\-augmented settings with per\-query enum sets atK<500K<500\), LLGuidance’s 1–3ms compilation may be preferable despite higher per\-step cost; the trie’s advantage is decisive when per\-step cost dominates, particularly in batch serving \(Appendix[L](https://arxiv.org/html/2608.12574#A12)\)\.

The trie’s advantage is decisive in batch serving, where the GPU forward pass is shared acrossBBrequests but masking runs per\-request on CPU\. AtB=128B=128, LLGuidance masking \(3\.7ms\) consumes 37% of the GPU forward pass, becoming the throughput bottleneck; XGrammar’s 783μ\\mus is 7\.8%; the trie’s 10μ\\mus is negligible \(0\.1%\) \(per\-batch\-step masking costs acrossBBin Appendix[M\.1](https://arxiv.org/html/2608.12574#A13.SS1), Table[19](https://arxiv.org/html/2608.12574#A13.T19)\)\. We validate this with end\-to\-end vLLM throughput atK=1,000K=1\{,\}000\(Table[3](https://arxiv.org/html/2608.12574#S5.T3)\): atB=256B=256, the trie achieves 219 req/s vs\. XGrammar’s 7\.5 req/s \(29×\\times\)\. The trie also exceeds unconstrained throughput \(219 vs\. 104 req/s\) because constrained decoding terminates at trie leaf nodes \(3\.2 tokens/request vs\. 8\.7 unconstrained\), reducing GPU forward passes\. Both constrained methods generate the same number of tokens, so the trie\-vs\-XGrammar ratio isolates the masking and integration differences\.

The 29×\\timesgap compounds two effects\. First, the per\-step algorithmic advantage: precomputed mask lookup costs 0\.65μ\\mus vs\. XGrammar’s 5\.9μ\\mus dynamic computation \(∼\{\\sim\}7×\\times; Table[4](https://arxiv.org/html/2608.12574#S5.T4)\)\. Second, the integration path: because the trie’s masks are precomputed, it integrates as a statelessLogitsProcessorthat returns a cached bitmask per step\. XGrammar does not currently support this path; its architecture requires dynamic mask computation via vLLM’s guided decoding pipeline with per\-request grammar compilation, sequential FSM state management, and scheduling overhead\. In principle, XGrammar*could*precompute and cache per\-state masks for enum constraints, but doing so would effectively reconstruct the trie: the minimal DFA for a finite set is isomorphic to the trie \(Proposition[1](https://arxiv.org/html/2608.12574#Thmproposition1)\), so caching its per\-state masks yields the same data structure\. The trie is thus the natural endpoint of optimizing FSM\-based decoding for finite sets\.

#### Deployment implications\.

The batch serving results have direct consequences for GPU utilization in production\. AtB=128B=128, each decoding step comprises a GPU forward pass \(∼10\{\\sim\}10ms\) followed by CPU mask computation\. With XGrammar, masking takes 783μ\\mus, where 7\.8% of the step is spent with the GPU idle waiting for the mask\. With LLGuidance \(3\.7 ms\), this rises to 27%, making masking the primary bottleneck\. The trie reduces idle time to 0\.1% of the step, keeping the GPU saturated\. For dynamic enum constraints \(e\.g\., retrieval\-augmented tool selection where the valid set changes per query\), the trie’s 33–40 ms compilation is fast enough to run on\-the\-fly without impacting serving latency, whereas XGrammar’s 75–239 ms compilation atK≥1,000K\\geq 1\{,\}000adds perceptible delay\. The AC automaton can be cached per tokenizer and shared across all enum schemas, so only the trie traversal \(𝒪⁡\(Nchars⋅ℓ\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot\\ell\), typically<5\{<\}\\,5ms\) runs per schema change\.

Table 3:End\-to\-end vLLM throughput \(req/s\) atK=1,000K=1\{,\}000on the synthetic tools benchmark \(Appendix[C\.2](https://arxiv.org/html/2608.12574#A3.SS2)\)\. The trie integrates as a statelessLogitsProcessor\(precomputed masks\); XGrammar requires vLLM’s guided decoding pipeline \(dynamic mask computation\)\. Trie exceeds unconstrained throughput due to early termination at trie leaves \(3\.2 vs\. 8\.7 tokens/request\); both constrained methods generate 3\.2 tokens/request \(verified\), so the trie\-vs\-XGrammar ratio isolates the masking and integration differences\. Qwen3\-8B, A100, greedy, median of 3 runs\.Table 4:Compilation time and per\-step masking cost byKK\(Qwen3\-8B, 151K vocab, synthetic tools benchmark; Appendix[C\.2](https://arxiv.org/html/2608.12574#A3.SS2)\)\. Per\-step measures mask*computation*only \(determining valid tokens\), not the𝒪⁡\(V\)\\mathcal\{O\}\(V\)bitmask application to logits \(∼\{\\sim\}31μ\\mus via tensor operation, identical for all methods\)\. XGrammar’s non\-monotonic per\-step cost \(9\.5μ\\mus atK=10K\{=\}10, 5\.4μ\\mus atK=100K\{=\}100\) reflects its vocabulary partitioning: at smallKK, fewer tokens fall in the “adaptive” partition, causing more cache misses; the partition stabilizes atK≥100K\\geq 100\. Mean±\\pmstd, 10 runs\.
#### Memory and deployment\.

The trie’s memory scales modestly \(Appendix[D](https://arxiv.org/html/2608.12574#A4), Table[10](https://arxiv.org/html/2608.12574#A4.T10)\): 0\.9 MB atK=10,000K=10\{,\}000, 8 MB atK=100,000K=100\{,\}000, vs\.∼\{\\sim\}2 GB for the FSM \(Appendix[H](https://arxiv.org/html/2608.12574#A8)\)\. The AC automaton requires∼\{\\sim\}150 MB for the largest vocabulary \(Gemma3 262K\), amortized across all enum schemas sharing that tokenizer\. The precomputed masks are immutable after construction, so concurrent read access from multiple serving threads requires no synchronization\. Integrated with vLLM as aLogitsProcessor, the trie maintains sub\-100ms per\-example latency atK=10,000K=10\{,\}000\(Table[13](https://arxiv.org/html/2608.12574#A4.T13), Appendix[D](https://arxiv.org/html/2608.12574#A4)\)\.

#### Mixed schemas\.

To validate the trie as a drop\-in component, we measure compilation for three mixed schemas \(enum \+ structural fields\): tool\-calling \(K=1,000K=1\{,\}000\), classification \(K=500K=500\), and entity\-linking \(K=5,000K=5\{,\}000\)\. The system routes enum fields to the trie and structural fields to XGrammar \(<<1ms dispatch overhead\)\. AtK=5,000K=5\{,\}000: 37ms vs\. 150ms; atK=1,000K=1\{,\}000: 33ms vs\. 75ms\. For nested enums, the PDA backend handles structural navigation and transfers control to the trie at enum\-valued fields\. Multiple enum fields in a single schema each get their own trie\. The principle extends to non\-enum constraints \(Appendix[K](https://arxiv.org/html/2608.12574#A11)\)\.

### 5\.2Generalization

To verify these results generalize, we evaluate across seven model families \(32K–262K vocabulary; Table[5](https://arxiv.org/html/2608.12574#S5.T5)\)\. The trie achieves consistent compilation speedups atK≥1,000K\\geq 1\{,\}000: 1\.2–6\.4×\\times, increasing to 3\.5–13\.7×\\timesatK=5,000K=5\{,\}000–10,00010\{,\}000\. Smaller vocabularies amplify the advantage because AC construction is𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\), so smallerVVyields faster precomputation\. Conversely, for very large vocabularies \(Gemma3 262K\), theKK\-independent AC overhead reduces the speedup to 1\.2×\\timesatK=1,000K=1\{,\}000; as vocabulary sizes trend upward, the compilation crossover shifts to higherKK\. Per\-step cost is unaffected by vocabulary size: Mistral\-32K 0\.60μ\\mus, GPT2\-50K 0\.62μ\\mus, OLMo\-100K 0\.63μ\\mus, Mistral Small\-131K 0\.64μ\\mus, Qwen3\-151K 0\.65μ\\mus, gpt\-oss\-200K 0\.66μ\\mus, Gemma3\-262K 0\.67μ\\mus\.

Table 5:Compilation speedup \(trie vs\. xgrammar\) across model families\. Values\>\>1×\\timesindicate trie is faster\. Per\-step masking is 0\.60–0\.67μ\\mus for all configurations\. Trie compilation is nearly flat: 11–96ms across allKKand tokenizers\.
### 5\.3Accuracy and Validity

The trie produces identical outputs to FSM\-based constrained decoding \(Proposition[1](https://arxiv.org/html/2608.12574#Thmproposition1), verified on 1,000 samples\)\. Its contribution is not improving accuracy at any givenKK, but*enabling*constrained decoding where FSM compilation is impractical\. We evaluate on four public classification benchmarks where ground\-truth accuracy can be measured: TREC\([22](https://arxiv.org/html/2608.12574#bib.bib29)\), MASSIVE\([12](https://arxiv.org/html/2608.12574#bib.bib30)\), Banking77\([5](https://arxiv.org/html/2608.12574#bib.bib31)\), and CLINC150\([21](https://arxiv.org/html/2608.12574#bib.bib32)\)\(documented in Appendix[C\.2](https://arxiv.org/html/2608.12574#A3.SS2)\)\. Existing tool\-calling benchmarks evaluate multi\-step chains rather than flat tool selection, making them unsuitable for isolating the constrained decoding bottleneck\. We compare: single\-pass unconstrained, single\-pass \+ trie \(same prompt\), think unconstrained, and think \+ trie \(prompts in Appendix[C\.1](https://arxiv.org/html/2608.12574#A3.SS1)\)\.

Table 6:Accuracy \(%\) and validity \(%\) on four public classification benchmarks \(TREC\([22](https://arxiv.org/html/2608.12574#bib.bib29)\), MASSIVE\([12](https://arxiv.org/html/2608.12574#bib.bib30)\), Banking77\([5](https://arxiv.org/html/2608.12574#bib.bib31)\), and CLINC150\([21](https://arxiv.org/html/2608.12574#bib.bib32)\); details in Appendix[C\.2](https://arxiv.org/html/2608.12574#A3.SS2); 5 runs, mean±\\pmstd, greedy\)\. Prompts identical within each pair; trie is the only difference\. Trie guarantees 100% validity\. Full results \(6 models\) in Appendix Table[7](https://arxiv.org/html/2608.12574#A2.T7)\.Across all 24 model×\\timesdataset settings \(Table[7](https://arxiv.org/html/2608.12574#A2.T7)\), constrained decoding achieves the highest accuracy in 21/24 cases while guaranteeing 100% validity; unconstrained decoding reaches≥\\geq95% validity in only 8/24\. The trie acts as a no\-cost safety net for strong models \(Gemma3 12B: matches unconstrained accuracy while eliminating the 0\.2–0\.5% failure rate\) and a critical enabler for weaker ones \(Qwen3\-1\.7B Banking77: 24\.8% with trie vs\. 4\.8% unconstrained at 6\.6% validity\)\. The think\-then\-answer strategy is particularly effective with the trie: on Qwen3\-8B, think\+trie achieves the best accuracy in all four datasets, with gains of up to 21\.5 points over single\-pass unconstrained \(TREC: 63\.1 vs\. 36\.3\)\. Without the trie, think\+unconstrained often*degrades*accuracy relative to single\-pass \(Qwen3\-8B Banking77: 37\.6 vs\. 48\.8\) because the reasoning phase produces outputs that are harder to parse into valid labels\. The three cases where unconstrained decoding wins \(Gemma3 MASSIVE, Gemma3 CLINC150, gpt\-oss CLINC150\) all involve strong models on datasets where PE validity already exceeds 89%; even here, the accuracy gap is small \(1–5 points\) while the validity gap remains \(89–100% vs\. 100%\)\.

AtK=500K=500–5,0005\{,\}000, the trie guarantees 100% validity while unconstrained drops to 84–98% \(Table[16](https://arxiv.org/html/2608.12574#A8.T16)\)\. Practitioner guidance in Appendix[L](https://arxiv.org/html/2608.12574#A12)\.

## 6Conclusion

This work addresses a mismatch in constrained decoding: applying general\-purpose automata to constraints with exploitable structure\. We solve it for finite\-set constraints using Aho\-Corasick precomputation, expanding the practical enum limit from hundreds to tens of thousands\. The trie achieves 7×\\timesfaster per\-step masking through precomputed lookups; because precomputed masks also enable a stateless serving path that bypasses the guided decoding pipeline, the advantage compounds to 29×\\timeshigher end\-to\-end batch throughput\. Across seven tokenizer families and six models, the trie maintains sub\-100ms compilation and flat per\-step cost while guaranteeing 100% output validity\. A controlled comparison confirms the trie is the efficient algorithm for this precomputation: the equivalent FSM\-based approach produces an isomorphic data structure 196×\\timesslower \(Appendix[H\.2](https://arxiv.org/html/2608.12574#A8.SS2)\)\. The underlying principle, matching enforcement mechanisms to constraint structure, generalizes beyond enums to any constraint with exploitable regularity\. As structured generation becomes central to agentic systems, we expect constraint\-specialized backends to become the norm rather than the exception\. Extending the dispatch principle to other structured patterns, such as date/time formats \(Appendix[K](https://arxiv.org/html/2608.12574#A11)\), numeric ranges, and regex subclasses, is a natural next step, and code will be released upon publication\.

#### Limitations\.

The trie automaton is specialized for flat finite\-set constraints; production schemas that also contain nested objects or arrays still require a general\-purpose backend for the structural portions, and our mixed\-schema evaluation validates compilation time but not end\-to\-end serving throughput for such cases\. The per\-step speedup matters most in batch serving, where the single\-request cost is dominated by the method\-independent𝒪⁡\(V\)\\mathcal\{O\}\(V\)bitmask application\. For dynamic one\-shot schemas at smallKK, LLGuidance’s near\-zero compilation may outweigh the trie’s per\-step advantage; at extremeKK, validity is guaranteed but accuracy is bounded by the model, not the decoder \(Appendix[E](https://arxiv.org/html/2608.12574#A5)\)\.

## References

- Aho and Corasick \(1975\)A\. V\. Aho and M\. J\. CorasickEfficient string matching: an aid to bibliographic search\.Communications of the ACM18\(6\),pp\. 333–340\.Cited by:[§G\.3](https://arxiv.org/html/2608.12574#A7.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.12574#S1.p3.1),[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px2.p1.1),[§4\.2](https://arxiv.org/html/2608.12574#S4.SS2.p1.1)\.
- Andersonet al\.\(2017\)P\. Anderson, B\. Fernando, M\. Johnson, and S\. GouldGuided open vocabulary image captioning with constrained beam search\.InEMNLP,Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Anthropic \(2025\)AnthropicStructured outputs\.Note:[https://docs\.anthropic\.com/en/docs/build\-with\-claude/structured\-outputs](https://docs.anthropic.com/en/docs/build-with-claude/structured-outputs)180\-second compilation timeout\. Accessed: 2026\-03\-09Cited by:[§G\.7](https://arxiv.org/html/2608.12574#A7.SS7.p1.2),[§1](https://arxiv.org/html/2608.12574#S1.p2.1)\.
- Beurer\-Kellneret al\.\(2023\)L\. Beurer\-Kellner, M\. Fischer, and M\. VechevPrompting is programming: a query language for large language models\.Proc\. ACM Program\. Lang\.7\(PLDI\)\.External Links:[Link](https://doi.org/10.1145/3591300),[Document](https://dx.doi.org/10.1145/3591300)Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Casanuevaet al\.\(2020\)I\. Casanueva, T\. Temčinas, D\. Gerz, M\. Henderson, and I\. VulićEfficient intent detection with dual sentence encoders\.InProceedings of the 2nd Workshop on Natural Language Processing for Conversational AI \(NLP4ConvAI\), ACL,Note:arXiv:2003\.04807Cited by:[3rd item](https://arxiv.org/html/2608.12574#A3.I1.i3.p1.1),[§5\.3](https://arxiv.org/html/2608.12574#S5.SS3.p1.1),[Table 6](https://arxiv.org/html/2608.12574#S5.T6)\.
- Centers for Medicare & Medicaid Services \(2025\)Centers for Medicare & Medicaid Services2026 ICD\-10\-CM: code descriptions in tabular order\.Note:[https://www\.cms\.gov/medicare/coding\-billing/icd\-10\-codes](https://www.cms.gov/medicare/coding-billing/icd-10-codes)Effective October 1, 2025; 74,719 codesCited by:[2nd item](https://arxiv.org/html/2608.12574#A3.I2.i2.p1.1),[Table 11](https://arxiv.org/html/2608.12574#A4.T11),[§1](https://arxiv.org/html/2608.12574#S1.p2.1)\.
- Chanet al\.\(2025\)B\. J\. Chan, M\. Huang, J\. Cheng, C\. Chen, and H\. HuangEfficient beam search for large language models using trie\-based decoding\.InEMNLP,Note:pages 14795–14807Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px2.p1.1)\.
- Cognetta and Okazaki \(2025\)M\. Cognetta and N\. OkazakiTokenization as finite\-state transduction\.Computational Linguistics51\(4\),pp\. 1119–1149\.Cited by:[§H\.9](https://arxiv.org/html/2608.12574#A8.SS9.p2.1),[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px2.p1.1)\.
- De Caoet al\.\(2021\)N\. De Cao, G\. Izacard, S\. Riedel, and F\. PetroniAutoregressive entity retrieval\.InICLR,Note:arXiv:2010\.00904Cited by:[§H\.8](https://arxiv.org/html/2608.12574#A8.SS8.p1.1),[§1](https://arxiv.org/html/2608.12574#S1.p2.1),[§1](https://arxiv.org/html/2608.12574#S1.p3.1),[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px2.p1.1),[§4\.2](https://arxiv.org/html/2608.12574#S4.SS2.SSS0.Px2.p1.1)\.
- Donget al\.\(2024\)Y\. Dong, C\. F\. Ruan, Y\. Cai, R\. Lai, Z\. Xu, Y\. Zhao, and T\. ChenXGrammar: flexible and efficient structured generation engine for large language models\.arXiv preprint arXiv:2411\.15100\.Cited by:[Appendix C](https://arxiv.org/html/2608.12574#A3.p1.1),[§1](https://arxiv.org/html/2608.12574#S1.p1.1),[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2608.12574#S5.SS1.p1.1),[§5](https://arxiv.org/html/2608.12574#S5.p1.1)\.
- Feiet al\.\(2025\)X\. Fei, X\. Zheng, and H\. FengMCP\-Zero: active tool discovery for autonomous LLM agents\.arXiv preprint arXiv:2506\.01056\.Cited by:[§1](https://arxiv.org/html/2608.12574#S1.p2.1),[§2](https://arxiv.org/html/2608.12574#S2.p2.1)\.
- FitzGeraldet al\.\(2022\)J\. FitzGerald, C\. Hench, C\. Peris, S\. Mackie, K\. Rottmann, A\. Sanchez, A\. Nash, L\. Urbach, V\. Kakarala, R\. Singh, S\. Ranganath, L\. Crist, M\. Britan, W\. Leeuwis, G\. Tur, and P\. NatarajanMASSIVE: a 1M\-example multilingual natural language understanding dataset with 51 typologically\-diverse languages\.arXiv preprint arXiv:2204\.08582\.Cited by:[2nd item](https://arxiv.org/html/2608.12574#A3.I1.i2.p1.1),[§5\.3](https://arxiv.org/html/2608.12574#S5.SS3.p1.1),[Table 6](https://arxiv.org/html/2608.12574#S5.T6)\.
- Fredkin \(1960\)E\. FredkinTrie memory\.Communications of the ACM3\(9\),pp\. 490–499\.Cited by:[§1](https://arxiv.org/html/2608.12574#S1.p3.1),[§4\.1](https://arxiv.org/html/2608.12574#S4.SS1.p1.1)\.
- Gauravet al\.\(2025\)N\. Gaurav, A\. Akarsh, A\. Ranjan, and M\. BajajDynamic react: scalable tool selection for large\-scale mcp environmentss\.arXiv preprint arXiv:2509\.20386\.Cited by:[§1](https://arxiv.org/html/2608.12574#S1.p2.1),[§2](https://arxiv.org/html/2608.12574#S2.p2.1)\.
- Genget al\.\(2025\)S\. Geng, H\. Cooper, M\. Moskal, S\. Jenkins, J\. Berman, N\. Ranchin, R\. West, E\. Horvitz, and H\. NoriJSONSchemaBench: a rigorous benchmark of structured outputs for language models\.arXiv preprint arXiv:2501\.10868\.Cited by:[Appendix M](https://arxiv.org/html/2608.12574#A13.p1.1),[Appendix C](https://arxiv.org/html/2608.12574#A3.p1.1),[§1](https://arxiv.org/html/2608.12574#S1.p1.1),[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2608.12574#S5.SS1.p1.1)\.
- Genget al\.\(2023\)S\. Geng, M\. Josifoski, M\. Peyrard, and R\. WestGrammar\-constrained decoding for structured NLP tasks without finetuning\.InEMNLP,Note:arXiv:2305\.13971Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Google \(2024\)GoogleStructured outputs\.Note:[https://ai\.google\.dev/gemini\-api/docs/structured\-output](https://ai.google.dev/gemini-api/docs/structured-output)Accessed: 2026\-02\-01Cited by:[§1](https://arxiv.org/html/2608.12574#S1.p2.1)\.
- Hopcroftet al\.\(1979\)J\. E\. Hopcroft, R\. Motwani, and J\. D\. UllmanIntroduction to automata theory, languages, and computation\.Addison\-Wesley\.Cited by:[§G\.2](https://arxiv.org/html/2608.12574#A7.SS2.p1.1)\.
- Hopcroft \(1971\)J\. HopcroftAnn​log⁡nn\\log nalgorithm for minimizing states in a finite automaton\.Theory of Machines and Computations,pp\. 189–196\.Cited by:[§G\.2](https://arxiv.org/html/2608.12574#A7.SS2.p1.1)\.
- Kooet al\.\(2024\)T\. Koo, F\. Liu, and L\. HeAutomata\-based constraints for language model decoding\.InNeurIPS,Note:arXiv:2407\.08103Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Larsonet al\.\(2019\)S\. Larson, A\. Mahendran, J\. J\. Peper, C\. Clarke, A\. Lee, P\. Hill, J\. K\. Kummerfeld, K\. Leach, M\. A\. Laurenzano, L\. Tang, and J\. MarsAn evaluation dataset for intent classification and out\-of\-scope prediction\.InEMNLP\-IJCNLP,Note:arXiv:1909\.02027Cited by:[4th item](https://arxiv.org/html/2608.12574#A3.I1.i4.p1.1),[§5\.3](https://arxiv.org/html/2608.12574#S5.SS3.p1.1),[Table 6](https://arxiv.org/html/2608.12574#S5.T6)\.
- Li and Roth \(2002\)X\. Li and D\. RothLearning question classifiers\.InCOLING,Cited by:[1st item](https://arxiv.org/html/2608.12574#A3.I1.i1.p1.1),[§5\.3](https://arxiv.org/html/2608.12574#S5.SS3.p1.1),[Table 6](https://arxiv.org/html/2608.12574#S5.T6)\.
- Liuet al\.\(2025\)C\. Liu, Y\. Peng, and E\. S\. ChngZero\-shot context biasing with trie\-based decoding using synthetic multi\-pronunciation\.InAPSIPA ASC,Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px2.p1.1)\.
- Luet al\.\(2022\)X\. Lu, S\. Welleck, P\. West, L\. Jiang, J\. Kasai, D\. Khashabi, R\. L\. Bras, L\. Qin, Y\. Yu, R\. Zellers, N\. A\. Smith, and Y\. ChoiNeuroLogic a\*esque decoding: constrained text generation with lookahead heuristics\.InNAACL,Note:arXiv:2112\.08726Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Luet al\.\(2021\)X\. Lu, P\. West, R\. Zellers, R\. L\. Bras, C\. Bhagavatula, and Y\. ChoiNeuroLogic decoding: \(un\)supervised neural text generation with predicate logic constraints\.InNAACL,Note:arXiv:2010\.12884Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- OpenAI \(2024\)OpenAIStructured model outputs\.Note:[https://platform\.openai\.com/docs/guides/structured\-outputs](https://platform.openai.com/docs/guides/structured-outputs)Accessed: 2026\-02\-01Cited by:[§1](https://arxiv.org/html/2608.12574#S1.p2.1)\.
- Post and Vilar \(2018\)M\. Post and D\. VilarFast lexically constrained decoding with dynamic beam allocation for neural machine translation\.InNAACL,Note:arXiv:1804\.06609Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Qinet al\.\(2024\)Y\. Qin, S\. Liang, Y\. Ye, K\. Zhu, L\. Yan, Y\. Lu, Y\. Lin, X\. Cong, X\. Tang, B\. Qian, S\. Zhao, L\. Hong, R\. Tian, R\. Xie, J\. Zhou, M\. Gerstein, D\. Li, Z\. Liu, and M\. SunToolLLM: facilitating large language models to master 16000\+ real\-world APIs\.InICLR,Note:arXiv:2307\.16789Cited by:[§1](https://arxiv.org/html/2608.12574#S1.p2.1)\.
- Scholaket al\.\(2021\)T\. Scholak, N\. Schucher, and D\. BahdanauPICARD: parsing incrementally for constrained auto\-regressive decoding from language models\.InEMNLP,Note:arXiv:2109\.05093Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Suet al\.\(2026\)Z\. Su, I\. Katsman, Y\. Wang, R\. He, L\. Heldt, R\. Keshavan, S\. Wang, X\. Yi, M\. Gao, O\. Dalal, L\. Hong, E\. Chi, and N\. HanVectorizing the trie: efficient constrained decoding for LLM\-based generative retrieval on accelerators\.arXiv preprint arXiv:2602\.22647\.Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px2.p1.1)\.
- Thompson \(1968\)K\. ThompsonProgramming techniques: regular expression search algorithm\.Communications of the ACM11\(6\),pp\. 419–422\.Cited by:[§G\.2](https://arxiv.org/html/2608.12574#A7.SS2.p1.1)\.
- Ugareet al\.\(2024\)S\. Ugare, T\. Suresh, H\. Kang, S\. Misailovic, and G\. SinghSynCode: llm generation with grammar augmentation\.Trans\. Mach\. Learn\. Res\.2025\.External Links:[Link](https://api.semanticscholar.org/CorpusID:268248075)Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Wanget al\.\(2025\)R\. Wang, X\. Liu, H\. Ren, G\. Chen, F\. Qi, and M\. SunWGRAMMAR: leverage prior knowledge to accelerate structured decoding\.arXiv preprint arXiv:2507\.16768\.Cited by:[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Willard and Louf \(2023\)B\. T\. Willard and R\. LoufEfficient guided generation for large language models\.External Links:2307\.09702,[Link](https://arxiv.org/abs/2307.09702)Cited by:[§1](https://arxiv.org/html/2608.12574#S1.p1.1),[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.
- Zhenget al\.\(2024\)L\. Zheng, L\. Yin, Z\. Xie, C\. Sun, J\. Huang, C\. H\. Yu, S\. Cao, C\. Kozyrakis, I\. Stoica, J\. E\. Gonzalez, C\. Barrett, and Y\. ShengSGLang: efficient execution of structured language model programs\.InNeurIPS,Cited by:[§1](https://arxiv.org/html/2608.12574#S1.p1.1),[§3](https://arxiv.org/html/2608.12574#S3.SS0.SSS0.Px1.p1.1)\.

## Appendix ADetailed Background

The key bottlenecks in FSM\-based constrained decoding for enums are: \(1\) state space explosion \(𝒪⁡\(K⋅Lmax\)\\mathcal\{O\}\(K\\cdot L\_\{\\max\}\)DFA states\), \(2\) per\-step masking cost \(𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)with cache penalties at largeKK\), and \(3\) compilation cost \(𝒪⁡\(K⋅Lmax⋅\|Σ\|\)\\mathcal\{O\}\(K\\cdot L\_\{\\max\}\\cdot\|\\Sigma\|\)\)\. These compound super\-linearly: doublingKKmore than doubles end\-to\-end latency because the cache penaltyf⁡\(\|𝒮\|\)f\(\|\\mathcal\{S\}\|\)is itself increasing inKK\. Dynamic schemas \(tool registries, retrieval\-augmented selection, multi\-tenant serving\) prevent amortization, making compilation latency the dominant cost\.

## Appendix BFull Accuracy and Validity Results

Table[7](https://arxiv.org/html/2608.12574#A2.T7)presents the complete accuracy and validity results across all six models and four datasets\. The main body \(Table[6](https://arxiv.org/html/2608.12574#S5.T6)\) shows three representative models; this table adds Qwen3\-1\.7B \(small model where constrained decoding is critical\), Gemma3 12B \(strong model where unconstrained decoding nearly suffices\), and Mistral 7B v0\.3 \(mid\-range instruction\-tuned model\)\.

Table 7:Accuracy \(%\) and validity \(%\) results across all three additional models \(5 runs, mean±\\pmstd, greedy decoding\)\. Extends Table[6](https://arxiv.org/html/2608.12574#S5.T6)with three additional models\.Bold: best accuracy per row;italic: second best\.
## Appendix CExperimental Setup Details

We implement the trie automaton in Rust with Python bindings via PyO3, using theaho\-corasickcrate \(v1\.1\) for multi\-pattern matching and parallel precomputation across CPU cores \(using all available cores via Rayon; XGrammar’s C\+\+ backend is also multi\-threaded\)\. Both are compiled languages with comparable performance characteristics; the per\-step advantage \(precomputed lookup vs\. dynamic computation\) is algorithmic\. Our primary comparison is against xgrammar v0\.1\.11\([10](https://arxiv.org/html/2608.12574#bib.bib4)\)and llguidance v1\.6\.1\([15](https://arxiv.org/html/2608.12574#bib.bib6)\)\. We verified that XGrammar’scompile\_json\_schemawith an enum schema produces equivalent compilation times tocompile\_regexwith a union pattern \(within 5% across allKK\), confirming thatcompile\_regexis a fair baseline\. We also evaluate several alternative approaches: naive FSM\-based constrained decoding, unconstrained generation with retry \(up to 3 attempts\), unconstrained generation with post\-hoc string similarity matching, and prompt engineering that includes enum values directly in the prompt\. All timing benchmarks run on NVIDIA A100 GPUs \(80GB\); CPU timing on AMD EPYC 7R32 \(96 cores, 3\.3 GHz\)\. Per\-step masking times are measured with 200 warm\-up iterations followed by 1,000 timed iterations \(same warm\-up for all three methods\)\. Compilation and per\-step results report mean±\\pmstd over 10 runs; end\-to\-end vLLM throughput reports median of 3 runs\.

### C\.1Prompt Templates

For the accuracy and validity experiments \(Section[5](https://arxiv.org/html/2608.12574#S5)\), we use the following prompt templates\. Letoptionsdenote the comma\-separated enum values andtextdenote the input\.

#### PE and Trie Strict\.

Both methods use the same prompt; the only difference is whether trie\-constrained decoding is applied\. This enables a controlled comparison isolating the effect of constrained decoding from prompt wording\.

```
Select exactly one of the following options.
Output ONLY the option itself, nothing else.

Options: {options}

Text: {text}
Answer:
```

#### Trie\.

A shorter prompt relying on the trie constraint to enforce validity:

```
Select one of: {options}

Text: {text}
Answer:
```

#### Think\+PE and Think\+Trie\.

Phase 1 generates reasoning \(unconstrained, up to 300 tokens\), and phase 2 generates the result\.

Phase 1:

```
Options: {options}

Text: {text}
Let me think step by step:
```

Phase 2:

```
Select exactly one of the following options.
Output ONLY the option itself, nothing else.

Options: {options}

Text: {text}
Thinking: {phase_1_output}
Answer:
```

#### Summary of prompt controls\.

PE vs\. \+Trie is a clean comparison: identical prompts, differing only in decoding strategy\. Think\+PE vs\. Think\+Trie share the same prompts; the only difference is whether the Phase 2 answer is trie\-constrained\. For unconstrained methods, we extract the model’s output and fuzzy\-match against the enum set\. For trie methods, the output is guaranteed valid by construction\.

### C\.2Datasets

We use three categories of enum sets: public classification benchmarks \(for accuracy/validity\), a synthetic tool\-name benchmark \(for latency, compilation, and validity at scale\), and two high\-cardinality enums \(for behavior beyond provider limits\)\. Table[4](https://arxiv.org/html/2608.12574#S5.T4)through Table[3](https://arxiv.org/html/2608.12574#S5.T3)and all main\-body latency/throughput results use the synthetic tools; Table[6](https://arxiv.org/html/2608.12574#S5.T6)and Table[7](https://arxiv.org/html/2608.12574#A2.T7)use the classification benchmarks; Table[11](https://arxiv.org/html/2608.12574#A4.T11)uses the high\-cardinality enums\. The prefix\-sharing ratiorrfor every set is reported in Table[14](https://arxiv.org/html/2608.12574#A8.T14)\.

#### Public classification benchmarks\.

These are standard datasets used unchanged\. Within each unconstrained/trie pair the prompt is identical \(Appendix[C\.1](https://arxiv.org/html/2608.12574#A3.SS1)\), so trie constraining is the only difference\. Evaluation uses greedy decoding with 5 random seeds\.

- •TREC\([22](https://arxiv.org/html/2608.12574#bib.bib29)\)\(K=42K=42,CogComp/trec\): question classification with fine\-grained categories such asLOC:cityandHUM:individual\. SmallKKbut non\-trivially structured labels\.
- •MASSIVE\([12](https://arxiv.org/html/2608.12574#bib.bib30)\)\(K=59K=59,AmazonScience/massive, English subset\): intent classification with intents such asplay\_musicandgeneral\_quirky\. ModerateKKwith high natural\-language overlap between intents\.
- •Banking77\([5](https://arxiv.org/html/2608.12574#bib.bib31)\)\(K=77K=77,PolyAI/banking77\): single\-domain banking intent classification\. Labels share heavy lexical overlap \(card\_payment\_failed,topping\_up\_by\_card\), which exposes parsing failures in unconstrained generation \(Mistral 7B validity drops to 78\.4%; Table[7](https://arxiv.org/html/2608.12574#A2.T7)\)\.
- •CLINC150\([21](https://arxiv.org/html/2608.12574#bib.bib32)\)\(K=150K=150,clinc/clinc\_oos\): 150 in\-scope intents across 10 domains\. The largest natural\-languageKKin the accuracy evaluation, where unconstrained validity drops further \(10\.4% on Qwen3\-1\.7B\)\.

#### Synthetic tools\.

A controlled benchmark constructed to isolate the constrained\-decoding bottleneck from natural\-language ambiguity\. Tool names follow the format<namespace\>\.<action\>\_<resource\>\(e\.g\.,slack\.get\_user,aws\.create\_invoice\), with 70% drawn from the namespaced pattern and 30% from a simpler<action\>\_<resource\>pattern\. The pools are 10 namespaces \(slack,github,stripe,aws,google,microsoft,salesforce,jira,notion,discord\), 10 actions \(get,create,update,delete,list,search,send,fetch,upload,download\), and 10 resources \(user,message,file,project,issue,payment,invoice,document,channel,repository\); theKKlargest reachable set is sampled uniformly\. The resulting prefix\-sharing ratio isr=0\.40r=0\.40atK=1,000K=1\{,\}000\(Table[14](https://arxiv.org/html/2608.12574#A8.T14)\), reflecting heavy namespace and action overlap\. Sizes used:K∈\{10,50,100,500,1,000,2,000,5,000,10,000,50,000,100,000\}K\\in\\\{10,50,100,500,1\{,\}000,2\{,\}000,5\{,\}000,10\{,\}000,50\{,\}000,100\{,\}000\\\}\.

#### High\-cardinality enums\.

- •Product names\(synthetic,K=1,500K=1\{,\}500\): constructed from category×\\timesbrand×\\timesadjective×\\timescolor×\\timesmodel\-number tuples \(e\.g\.,Electronics \> Sony \> Premium 4823 \> Black\)\. Exercises trie compilation beyond provider enum limits in a domain with natural\-language\-like prefix sharing \(r=0\.40r=0\.40\)\.
- •ICD\-10\-CM\(K=74,719K=74\{,\}719\): the official 2026 ICD\-10\-CM code list published by the U\.S\. Centers for Medicare & Medicaid Services\([6](https://arxiv.org/html/2608.12574#bib.bib10)\)\(file2026\-Code\-Descriptions\-in\-Tabular\-Order\.zip, effective October 1, 2025\)\. Prefix sharingr=0\.19r=0\.19, the lowest in our benchmarks, due to the hierarchical chapter\-letter structure\. A real production\-grade enum at a scale where FSM\-based constrained decoding times out\.

## Appendix DDetailed Experimental Results

### D\.1Main Results

This subsection reports the full latency, compliance, memory, and ablation results on the synthetic tools benchmark \(Appendix[C\.2](https://arxiv.org/html/2608.12574#A3.SS2)\) that the main body summarizes\. Table[8](https://arxiv.org/html/2608.12574#A4.T8)gives end\-to\-end enum\-generation latency by cardinality: the trie automaton stays flat at 0\.72–0\.77 s acrossK=10K=10–10,00010\{,\}000, while the FSM path \(Outlines/SGLang/XGrammar\) rises from 0\.05 s to 5\.88 s asKKgrows\. Table[9](https://arxiv.org/html/2608.12574#A4.T9)reports schema compliance: all constrained methods are 100% valid by construction, whereas unconstrained retry never reproduces a synthetic tool name verbatim \(0%\)\. Table[10](https://arxiv.org/html/2608.12574#A4.T10)reports the memory footprint of the precomputed masks acrossK=100K=100–100,000100\{,\}000, confirming the near\-linear∼8\{\\sim\}8MB\-at\-100,000100\{,\}000scaling\. Table[11](https://arxiv.org/html/2608.12574#A4.T11)reports the two high\-cardinality enums, and Table[12](https://arxiv.org/html/2608.12574#A4.T12)ablates the trie against its hierarchical and speculative variants atK=5,000K=5\{,\}000, where the trie alone is fastest \(0\.77 s\) since masking is already cheap at this scale\.

Table 8:End\-to\-end latency \(seconds\) for enum generation by cardinalityKK\. Timeout threshold is 60s\.Table 9:Schema compliance \(%\) for different approaches\. Constrained methods achieve 100% by design\.Table 10:Memory footprint of precomputed trie masks\.Table 11:High\-cardinality task results\. Product names are a synthetic enum constructed from category×\\timesbrand×\\timesadjective×\\timescolor tuples; ICD\-10\-CM uses the full 2026 CMS code list\([6](https://arxiv.org/html/2608.12574#bib.bib10)\)\. Both are documented in Appendix[C\.2](https://arxiv.org/html/2608.12574#A3.SS2)\. Accuracy is classification accuracy; latency is median per\-example\. The 0% accuracy atK=74,719K\{=\}74\{,\}719reflects model capability limitations at extreme cardinality, not a trie limitation; the trie enables the attempt where FSM compilation times out\.Table 12:Ablation atK=5,000K=5\{,\}000\. Each row removes one component\. Speculative short\-circuiting provides no benefit at thisKK\(trie masking alone is fast\)\. The trie’s compilation advantage \(Table[4](https://arxiv.org/html/2608.12574#S5.T4): 3\.5–13\.7×\\timesatK≥5,000K\\geq 5\{,\}000\) and per\-step masking advantage \(0\.65μ\\mus vs\. 5\.9μ\\mus\) compound in batch serving\.
### D\.2vLLM Performance Results

Table[13](https://arxiv.org/html/2608.12574#A4.T13)reports per\-example latency for the two constrained\-decoding modes exposed by vLLM, measured end\-to\-end \(compilation plus inference\) at batch size 1\. The trie\-backed “guided choice” path stays within 0\.05–0\.10 s acrossK=500K=500–10,00010\{,\}000, while the XGrammar\-backed “guided regex” path rises to 5\.88 s atK=10,000K=10\{,\}000, tracking the compilation growth in Table[4](https://arxiv.org/html/2608.12574#S5.T4)\. This is the single\-request view; the batch\-serving throughput gains that motivate the trie appear at higher batch sizes \(Table[3](https://arxiv.org/html/2608.12574#S5.T3)\)\.

Table 13:vLLM end\-to\-end per\-example latency \(seconds\), including both compilation and inference\. “Guided choice” uses vLLM’s built\-in EBNF\-based choice mode; “guided regex” uses XGrammar regex compilation\. Both use XGrammar as the backend; our trie integration \(Table[3](https://arxiv.org/html/2608.12574#S5.T3)\) shows larger gains at higher batch sizes\.

## Appendix ELimitations and Future Work

#### Scope\.

The trie automaton optimizes exactly one constraint pattern: flat finite\-set selection\. While this is common \(tool routing, classification, entity linking\), real\-world schemas typically combine enum fields with structural constraints\. Our mixed\-schema evaluation \(Section[5](https://arxiv.org/html/2608.12574#S5)\) validates compilation time but not end\-to\-end throughput for nested schemas\. Dynamic enum updates require full recompilation \(37ms, negligible in practice but not incremental\)\.

#### Engine scope\.

End\-to\-end throughput is measured only on vLLM, and the headline 29×\\timesatB=256B=256\(Table[3](https://arxiv.org/html/2608.12574#S5.T3)\) is a vLLM\-specific figure that should not be read as engine\-independent\. It composes two contributions of the trie’s design\. First, an*algorithmic*improvement in mask construction that is engine\-independent: XGrammar derives the next\-token bitmask from runtime matcher state at every step \(FSM walk plus lookahead, 5\.8μ\\mus atK=1,000K=1\{,\}000; Table[4](https://arxiv.org/html/2608.12574#S5.T4)\), whereas the trie precomputes one bitmask per node and reduces the per\-step path to a stateless character walk plus bitmask copy \(0\.65μ\\mus\), an∼9×\{\\sim\}9\\timesgap that transfers to any serving engine\. Second, an*integration*improvement whose magnitude is vLLM\-specific: because the trie’s per\-step path is stateless, it wraps as vLLM’sCustomLogitProcessor\(a thin tensor op run alongside the forward pass\), while XGrammar’s state\-dependent mask must thread through vLLM’s guided\-decoding pipeline and its scheduling overhead, visible as XGrammar saturating near 7\.5 req/s while the trie scales to 219 req/s\. The per\-step and compilation results \(Tables[3](https://arxiv.org/html/2608.12574#S5.T3),[4](https://arxiv.org/html/2608.12574#S5.T4), and[5](https://arxiv.org/html/2608.12574#S5.T5)\) are engine\-independent and transfer directly; the integration magnitude depends on the target engine’s plumbing\. SGLang shares XGrammar as its constrained\-decoding backend, so the per\-step XGrammar measurements reflect the algorithmic cost SGLang pays as well; TensorRT\-LLM uses a distinct constrained\-decoding stack, and integrating the trie there is left to future work\.

#### Baselines\.

LLGuidance’s Earley parser avoids upfront compilation entirely and achieves faster compilation than both XGrammar and our trie \(Table[18](https://arxiv.org/html/2608.12574#A13.T18)\); however, its per\-step cost remains𝒪⁡\(V\)\\mathcal\{O\}\(V\)for finite sets \(73–141μ\\mus vs\. our 0\.65μ\\mus\)\. If serving engines move masking to GPU \(Section[H\.6](https://arxiv.org/html/2608.12574#A8.SS6)\), the CPU per\-step advantage becomes less relevant, though the trie’s compact bitmask representation remains more amenable to GPU transfer\.

#### Implementation\.

The trie is in Rust while XGrammar uses C\+\+\. The per\-step advantage \(precomputed lookup vs\. dynamic computation\) is algorithmic and independent of implementation language\.

## Appendix FDetailed Tool Routing Example

Consider an agentic system routing requests to the correct tool from a registry ofK=2,000K=2\{,\}000APIs \(e\.g\.,aws\.cloudwatch\.get\_metric\_statistics\), averagingLmax=30L\_\{\\max\}=30characters with strong prefix structure\. FSM compilation requiresK⋅Lmax⋅\|Σ\|=15\.4K\\cdot L\_\{\\max\}\\cdot\|\\Sigma\|=15\.4M character\-level transitions \(25–50s\)\. Per\-step masking requiresV⋅L¯tok=102,400V\\cdot\\bar\{L\}\_\{\\text\{tok\}\}=102\{,\}400FSM traversals per step; with 6\.4 tokens per tool name and cache effects \(f≈2\.0f\\approx 2\.0due to the 47 MB transition table exceeding L2 cache\), the effective cost is∼1\.3×106\{\\sim\}1\.3\\times 10^\{6\}operations per selection\. In an agentic loop with 5–10 tool calls per task, this compounds to minutes of latency, forcing practitioners to cap the registry or abandon constrained decoding\.

## Appendix GTheoretical Analysis

We analyze the complexity of both the standard FSM pipeline and the trie automaton, then establish correctness and discuss practical performance considerations\. Throughout, letNchars=∑i=1K\|ei\|N\_\{\\text\{chars\}\}=\\sum\_\{i=1\}^\{K\}\|e\_\{i\}\|denote the total character count across all enum values\.

### G\.1Worked Example: Trie Construction and Aho\-Corasick Traversal

We walk through the full precomputation on a small enum to make the construction concrete, extending the running example \(Section[4\.1](https://arxiv.org/html/2608.12574#S4.SS1)\) with a third value\. Let

ℰ=\{medical\_billing,medical\_coding,medical\_records\}\.\\mathcal\{E\}=\\\{\\texttt\{medical\\\_billing\},\\ \\texttt\{medical\\\_coding\},\\ \\texttt\{medical\\\_records\}\\\}\.
#### Step 1: Trie construction\.

Inserting the three strings character\-by\-character merges the shared prefixmedical\_into a single path and then branches into three suffixes\. Writingn0n\_\{0\}for the root and labeling nodes by the string consumed so far:

n0→m⋯→ln7​\(medical\)→\_n8​\(medical\_\)​\{→b⋯→gleaf​\(medical\_billing\)→c⋯→gleaf​\(medical\_coding\)→r⋯→sleaf​\(medical\_records\)n\_\{0\}\\xrightarrow\{\\texttt\{m\}\}\\cdots\\xrightarrow\{\\texttt\{l\}\}n\_\{7\}\\,\(\\texttt\{medical\}\)\\xrightarrow\{\\texttt\{\\\_\}\}n\_\{8\}\\,\(\\texttt\{medical\\\_\}\)\\begin\{cases\}\\xrightarrow\{\\texttt\{b\}\}\\cdots\\xrightarrow\{\\texttt\{g\}\}\\ \\text\{leaf \}\(\\texttt\{medical\\\_billing\}\)\\\\ \\xrightarrow\{\\texttt\{c\}\}\\cdots\\xrightarrow\{\\texttt\{g\}\}\\ \\text\{leaf \}\(\\texttt\{medical\\\_coding\}\)\\\\ \\xrightarrow\{\\texttt\{r\}\}\\cdots\\xrightarrow\{\\texttt\{s\}\}\\ \\text\{leaf \}\(\\texttt\{medical\\\_records\}\)\\end\{cases\}The branch node isn8n\_\{8\}\(aftermedical\_\); nodesn0n\_\{0\}throughn8n\_\{8\}form the shared trunk, and each of the three suffixes \(billing,coding,records\) is a separate chain\. Total charactersNchars=15\+14\+15=44N\_\{\\text\{chars\}\}=15\+14\+15=44, versus99\(shared trunk\)\+7\+6\+7=29\+7\+6\+7=29trie nodes: prefix sharing collapses the trunk from three copies to one\.

#### Step 2: Aho\-Corasick automaton over the vocabulary\.

Suppose the tokenizer contains the toy vocabulary\{medical,\_bill,\_cod,\_rec,ing,ords\}\\\{\\texttt\{medical\},\\texttt\{\\\_bill\},\\texttt\{\\\_cod\},\\texttt\{\\\_rec\},\\texttt\{ing\},\\texttt\{ords\}\\\}\(real vocabularies have32​K32\\text\{K\}–262​K262\\text\{K\}tokens; the mechanism is identical\)\. We build one AC automaton from these six patterns: a goto trie over the pattern strings, failure links pointing each state to the longest proper suffix that is also a prefix of some pattern, and an output set at each state listing the patterns that end there\. This automaton depends only on the tokenizer, not onℰ\\mathcal\{E\}, so it is built once and reused across all schemas\.

#### Step 3: Trie traversal with AC state maintenance\.

We DFS the trie, feeding the character on each edge to the AC automaton and carrying the AC stateqqalong\. At a branch we pushqqbefore descending and pop it on backtrack, so each trie edge is processed exactly once\. Reaching an AC output means a vocabulary token’s characters end at the current trie node; that token started\|token\|\|\\text\{token\}\|characters earlier, at the trie node we call its*start node*, and it is recorded invalid​\[start node\]\\text\{valid\}\[\\text\{start node\}\]provided its path stays inside the trie and does not overshoot a leaf\. Concretely:

- •Walkingm→⋯→\\to\\cdots\\tolinton7n\_\{7\}triggers the AC outputmedical, whose 7\-character span starts at the rootn0n\_\{0\}\. Sincemedicaltraces a valid path fromn0n\_\{0\}to the internal noden7n\_\{7\}, we addmedicaltovalid​\[n0\]\\text\{valid\}\[n\_\{0\}\]\.
- •Fromn7n\_\{7\}, the edge\_advances the AC state; descending thebbranch triggers\_bill, spanning the 5 characters fromn7n\_\{7\}to a node inside thebillingchain, so\_billis added tovalid​\[n7\]\\text\{valid\}\[n\_\{7\}\]\. Descending thecbranch instead triggers\_cod\(added tovalid​\[n7\]\\text\{valid\}\[n\_\{7\}\]\), and therbranch triggers\_rec\(added tovalid​\[n7\]\\text\{valid\}\[n\_\{7\}\]\)\. Because the DFS restores the AC state to its value atn7n\_\{7\}before each branch, all three suffix tokens are correctly attributed ton7n\_\{7\}\.
- •Deeper in thebillingchain,ingmatches and is added to thevalidset of the node three characters back \(aftermedical\_bill\); similarlyordsis added inside therecordschain\.

#### Step 4: Resulting masks\.

The precomputed sets arevalid​\[n0\]=\{medical\}\\text\{valid\}\[n\_\{0\}\]=\\\{\\texttt\{medical\}\\\},valid​\[n7\]=\{\_bill,\_cod,\_rec\}\\text\{valid\}\[n\_\{7\}\]=\\\{\\texttt\{\\\_bill\},\\texttt\{\\\_cod\},\\texttt\{\\\_rec\}\\\}, and the deeper single\-token continuations along each chain\. At decode time, masking at any node is a direct lookup into these sets, with no vocabulary scan\. Starting from the root, the model can only emitmedical; aftermedical\_it chooses among\_bill/\_cod/\_rec, committing to one of the three enum values; each subsequent step has a single valid continuation until the leaf, where only EOS is valid\. This reproduces exactly the reachability an FSM would compute \(Proposition[1](https://arxiv.org/html/2608.12574#Thmproposition1)\), but with the vocabulary matching amortized once across the sharedmedical\_trunk rather than recomputed per step\.

### G\.2FSM Complexity Analysis

For an enumℰ=\{e1,e2,…,eK\}\\mathcal\{E\}=\\\{e\_\{1\},e\_\{2\},\\ldots,e\_\{K\}\\\}, the standard approach constructs a DFA from the regular expressione1\|e2​\|⋯\|​eKe\_\{1\}\|e\_\{2\}\|\\cdots\|e\_\{K\}\([18](https://arxiv.org/html/2608.12574#bib.bib11)\)via Thompson’s construction\([31](https://arxiv.org/html/2608.12574#bib.bib23)\)followed by subset construction and Hopcroft minimization\([19](https://arxiv.org/html/2608.12574#bib.bib24)\)\.

#### State space\.

The minimal DFA has between\|𝒯⁡\(ℰ\)\|\+1\|\\mathcal\{T\}\(\\mathcal\{E\}\)\|\+1and1\+Nchars1\+N\_\{\\text\{chars\}\}states, where\|𝒯⁡\(ℰ\)\|\|\\mathcal\{T\}\(\\mathcal\{E\}\)\|is the trie node count \(number of distinct prefixes\) and the\+1\+1accounts for the dead state\. The upper bound1\+Nchars≤1\+K⋅Lmax1\+N\_\{\\text\{chars\}\}\\leq 1\+K\\cdot L\_\{\\max\}is achieved when no enum values share prefixes; the lower bound is achieved when the trie is the minimal DFA \(which it always is for finite string unions, up to the dead state\)\. This follows from the Myhill\-Nerode theorem: each distinct prefix defines a distinct equivalence class\.

#### Compilation cost\.

The three\-phase pipeline costs:

CcompileFSM=𝒪⁡\(Nchars\)⏟NFA construction\+𝒪⁡\(Nchars⋅\|Σ\|\)⏟subset construction\+𝒪⁡\(Nchars⋅\|Σ\|⋅log⁡Nchars\)⏟Hopcroft minimizationC\_\{\\text\{compile\}\}^\{\\text\{FSM\}\}=\\underbrace\{\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\)\}\_\{\\text\{NFA construction\}\}\+\\underbrace\{\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot\|\\Sigma\|\)\}\_\{\\text\{subset construction\}\}\+\\underbrace\{\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot\|\\Sigma\|\\cdot\\log N\_\{\\text\{chars\}\}\)\}\_\{\\text\{Hopcroft minimization\}\}\(2\)The dominant term is minimization\. The transition table requires𝒪⁡\(Nchars⋅\|Σ\|\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot\|\\Sigma\|\)space\. ForK=2,000K=2\{,\}000,Lmax=30L\_\{\\max\}=30,\|Σ\|=256\|\\Sigma\|=256, this is≈15\.4\\approx 15\.4million operations\.

#### Per\-step masking cost\.

At each decoding step, the system checks allVVvocabulary tokens by simulating up toℓ\\ellcharacter transitions per token:

CmaskFSM=𝒪⁡\(V⋅ℓ\)C\_\{\\text\{mask\}\}^\{\\text\{FSM\}\}=\\mathcal\{O\}\(V\\cdot\\ell\)\(3\)The total decoding cost for one enum value of character lengthLLis\(L/ℓ¯\)⋅\(CmaskFSM\+Cforward\)\(L/\\bar\{\\ell\}\)\\cdot\(C\_\{\\text\{mask\}\}^\{\\text\{FSM\}\}\+C\_\{\\text\{forward\}\}\), whereℓ¯\\bar\{\\ell\}is the average token length andCforwardC\_\{\\text\{forward\}\}is the LLM forward pass cost\.

### G\.3Trie Automaton Complexity

#### Compilation cost\.

Trie construction costs𝒪⁡\(Nchars\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\)\. The naive mask precomputation \(checking every token at every node\) costs𝒪⁡\(Nchars⋅V⋅ℓ\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot V\\cdot\\ell\), but using Aho\-Corasick multi\-pattern matching\([1](https://arxiv.org/html/2608.12574#bib.bib22)\)over the vocabulary token strings reduces this to:

Ccompiletrie=𝒪⁡\(\(Nchars\+V\)⋅ℓ\)C\_\{\\text\{compile\}\}^\{\\text\{trie\}\}=\\mathcal\{O\}\(\(N\_\{\\text\{chars\}\}\+V\)\\cdot\\ell\)\(4\)The Aho\-Corasick automaton is built over theVVtoken strings in𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\), then the trie is traversed depth\-first, maintaining the AC state across edges \(saving and restoring at branch points so each trie edge is processed exactly once\)\. The total text length is thusNcharsN\_\{\\text\{chars\}\}, requiring𝒪⁡\(Nchars\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\)character steps; the total number of reported matches across all positions is bounded by𝒪⁡\(Nchars⋅ℓ\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot\\ell\)since at each of theNcharsN\_\{\\text\{chars\}\}character positions, at mostℓ\\elltokens of different lengths can start there\. The overall cost is thus𝒪⁡\(Nchars⋅ℓ\+V⋅ℓ\)=𝒪⁡\(\(Nchars\+V\)⋅ℓ\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot\\ell\+V\\cdot\\ell\)=\\mathcal\{O\}\(\(N\_\{\\text\{chars\}\}\+V\)\\cdot\\ell\)\.

#### Per\-step masking cost\.

After precomputation, masking is a lookup into the stored valid token list:

Cmasktrie=𝒪⁡\(\|valid​\[st\]\|\)C\_\{\\text\{mask\}\}^\{\\text\{trie\}\}=\\mathcal\{O\}\(\|\\text\{valid\}\[s\_\{t\}\]\|\)\(5\)The valid set size shrinks exponentially with trie depth: assuming each character position in the vocabulary is drawn independently and uniformly fromΣ\\Sigma, the probability that a token of lengthjjmatches a specificjj\-character trie path is\|Σ\|−j\|\\Sigma\|^\{\-j\}, giving𝔼⁡\[\|valid​\[st\]\|\]≤V⋅ℓ¯/\|Σ\|d⁡\(st\)\\mathbb\{E\}\[\|\\text\{valid\}\[s\_\{t\}\]\|\]\\leq V\\cdot\\bar\{\\ell\}/\|\\Sigma\|^\{d\(s\_\{t\}\)\}whered⁡\(st\)d\(s\_\{t\}\)is the node depth\. This is a loose upper bound \(real tokenizers have non\-uniform character distributions\), but the qualitative exponential decay is confirmed empirically: after 3–4 characters of prefix, the valid set is typically 10–100 tokens, making per\-step cost effectively constant\.

### G\.4Complexity Comparison

Table[1](https://arxiv.org/html/2608.12574#S4.T1)\(main body\) summarizes the asymptotic and concrete costs\. The compilation speedup is driven by the\|Σ\|\|\\Sigma\|factor: the FSM must fill transition entries for all 256 byte values at each state, while the trie only processes characters that actually appear\. The per\-step speedup comes from replacing a full vocabulary scan with a cached lookup whose size shrinks with trie depth, and whose working set stays within L1 cache \(contrasted with the FSM’s L2\-overflowing transition table in Appendix[G](https://arxiv.org/html/2608.12574#A7), “Cache Effects”\)\.

### G\.5Correctness

We give the full proof of the output\-equivalence guarantee stated in the main body \(Proposition[1](https://arxiv.org/html/2608.12574#Thmproposition1)\): the trie automaton is not an approximation, but produces identical outputs to the FSM approach\. Recall the statement: for the decodable vocabulary𝒱dec⊆𝒱\\mathcal\{V\}\_\{\\textup\{dec\}\}\\subseteq\\mathcal\{V\}\(excluding special tokens such as<pad\>,<unk\>that do not correspond to character sequences\), any enumℰ\\mathcal\{E\}, and any prefix𝐲<t\\mathbf\{y\}\_\{<t\}, the constrained distributions produced by the FSM and trie automaton are identical,pcFSM​\(yt∣𝐲<t\)=pctrie​\(yt∣𝐲<t\)p\_\{c\}^\{\\textup\{FSM\}\}\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)=p\_\{c\}^\{\\textup\{trie\}\}\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)for allyt∈𝒱decy\_\{t\}\\in\\mathcal\{V\}\_\{\\textup\{dec\}\}, so greedy decoding and fixed\-seed sampling produce identical outputs under both methods\.

###### Proof\.

It suffices to show that𝒜FSM​\(st\)=𝒜trie​\(st\)\\mathcal\{A\}^\{\\text\{FSM\}\}\(s\_\{t\}\)=\\mathcal\{A\}^\{\\text\{trie\}\}\(s\_\{t\}\)for all reachable statessts\_\{t\}, since the constrained distributionpc\(yt∣𝐲<t\)∝p\(yt∣𝐲<t\)⋅𝟏\[yt∈𝒜\(st\)\]p\_\{c\}\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)\\propto p\(y\_\{t\}\\mid\\mathbf\{y\}\_\{<t\}\)\\cdot\\mathbf\{1\}\[y\_\{t\}\\in\\mathcal\{A\}\(s\_\{t\}\)\]is determined entirely by the valid token set and the unconstrained distribution\.

Both methods define validity over𝒱dec\\mathcal\{V\}\_\{\\text\{dec\}\}as follows: a tokenvvwith character decompositionc1⋯c\|v\|c\_\{1\}\\cdots c\_\{\|v\|\}is valid at statests\_\{t\}if and only if \(i\) the sequence of transitionsst→c1s′→c2⋯→c\|v\|s′′s\_\{t\}\\xrightarrow\{c\_\{1\}\}s^\{\\prime\}\\xrightarrow\{c\_\{2\}\}\\cdots\\xrightarrow\{c\_\{\|v\|\}\}s^\{\\prime\\prime\}does not encounter a dead state, and \(ii\) from the resulting states′′s^\{\\prime\\prime\}, there exists at least one stringw∈Σ∗w\\in\\Sigma^\{\*\}such thats′′→𝑤saccs^\{\\prime\\prime\}\\xrightarrow\{w\}s\_\{\\text\{acc\}\}for some accept statesaccs\_\{\\text\{acc\}\}\(i\.e\., the consumed prefix𝐲<t⋅v\\mathbf\{y\}\_\{<t\}\\cdot vis a prefix of someei∈ℰe\_\{i\}\\in\\mathcal\{E\}\)\.

The FSM computes this at each decoding step by simulating transitionsδ⁡\(st,c1\),δ⁡\(⋅,c2\),…\\delta\(s\_\{t\},c\_\{1\}\),\\delta\(\\cdot,c\_\{2\}\),\\ldotsfor each tokenv∈𝒱decv\\in\\mathcal\{V\}\_\{\\text\{dec\}\}\. The trie computes this during precomputation by walking each token’s characters down the trie from nodests\_\{t\}\.

The two computations produce identical results because the trie for a finite setℰ\\mathcal\{E\}is isomorphic to the minimal DFA forℒℰ\\mathcal\{L\}\_\{\\mathcal\{E\}\}\. Specifically, by the Myhill\-Nerode theorem, the equivalence classes of the right\-congruence relation forℒℰ\\mathcal\{L\}\_\{\\mathcal\{E\}\}are exactly the distinct prefixes of the enum values \(plus the equivalence class of strings that are not prefixes of anyeie\_\{i\}, corresponding to the dead state\)\. Each trie node represents one such equivalence class, so the trie node set plus a dead state is in bijection with the minimal DFA state set\. Under this bijection, the transition functions agree:δDFA​\(s,c\)=δtrie​\(s,c\)\\delta\_\{\\text\{DFA\}\}\(s,c\)=\\delta\_\{\\text\{trie\}\}\(s,c\)for all statesssand characterscc\. Therefore, the multi\-character extensionδ∗​\(st,v\)\\delta^\{\*\}\(s\_\{t\},v\)produces the same result under both representations, and the accept\-reachability check \(condition \(ii\)\) is identical since the accept states correspond to the same trie leaves\.

The precomputed maskvalid​\[st\]\\text\{valid\}\[s\_\{t\}\]stores exactly the set\{v∈𝒱dec:conditions \(i\) and \(ii\) hold\}\\\{v\\in\\mathcal\{V\}\_\{\\text\{dec\}\}:\\text\{conditions \(i\) and \(ii\) hold\}\\\}, so𝒜trie​\(st\)=valid​\[st\]=𝒜FSM​\(st\)\\mathcal\{A\}^\{\\text\{trie\}\}\(s\_\{t\}\)=\\text\{valid\}\[s\_\{t\}\]=\\mathcal\{A\}^\{\\text\{FSM\}\}\(s\_\{t\}\)\. ∎

#### EOS token handling\.

The restriction to𝒱dec\\mathcal\{V\}\_\{\\text\{dec\}\}\(excluding special tokens\) means the trie and FSM may differ only in whether an EOS token is appended after the enum value is complete\. In our vLLM integration, the trie signals completion by including only EOS in the valid set at leaf nodes, matching vLLM’s expected termination protocol\. Our empirical verification \(Section[5](https://arxiv.org/html/2608.12574#S5)\) confirms that all*content*tokens are identical; the only difference is the trailing EOS, which does not affect the decoded string\.

###### Proposition 2\(Hierarchical cardinality reduction\)\.

Letℰ\\mathcal\{E\}be partitioned intoGGgroups of sizesK1,…,KGK\_\{1\},\\ldots,K\_\{G\}with∑jKj=K\\sum\_\{j\}K\_\{j\}=K\. The effective per\-step cardinality isCeff=max⁡\(G,maxj⁡Kj\)C\_\{\\text\{eff\}\}=\\max\(G,\\max\_\{j\}K\_\{j\}\)\. For balanced partitions, this is minimized atCeff∗=⌈K⌉C\_\{\\text\{eff\}\}^\{\*\}=\\lceil\\sqrt\{K\}\\rceilwhenG=⌈K⌉G=\\lceil\\sqrt\{K\}\\rceil\.

###### Proof of Proposition[2](https://arxiv.org/html/2608.12574#Thmproposition2)\.

The two\-level scheme requires one constrained decoding call overGGgroup names, then one call overKjK\_\{j\}values within the selected groupjj\. The per\-step cardinality is thusmax⁡\(G,maxj⁡Kj\)\\max\(G,\\max\_\{j\}K\_\{j\}\)\. For balanced partitions,maxj⁡Kj=⌈K/G⌉\\max\_\{j\}K\_\{j\}=\\lceil K/G\\rceil, soCeff=max⁡\(G,⌈K/G⌉\)C\_\{\\text\{eff\}\}=\\max\(G,\\lceil K/G\\rceil\)\. Sincemax⁡\(a,b\)≥a​b\\max\(a,b\)\\geq\\sqrt\{ab\}fora,b\>0a,b\>0, we havemax⁡\(G,K/G\)≥K\\max\(G,K/G\)\\geq\\sqrt\{K\}, with equality whenG=K/GG=K/G, i\.e\.,G=KG=\\sqrt\{K\}\. Rounding givesCeff∗=⌈K⌉C\_\{\\text\{eff\}\}^\{\*\}=\\lceil\\sqrt\{K\}\\rceil\. ∎

### G\.6Cache Effects and Practical Performance

The analysis above uses the unit\-cost RAM model\. Real hardware introduces cache hierarchy effects that significantly impact the FSM approach but not the trie automaton\.

The FSM transition table occupies\|𝒮\|⋅\|Σ\|⋅w\|\\mathcal\{S\}\|\\cdot\|\\Sigma\|\\cdot wbytes \(wherewwis the word size\)\. When this exceeds L2 cache capacityCL2C\_\{\\text\{L2\}\}, transition lookups incur main\-memory access penalties\. We model the effective per\-step cost asCmask,effFSM=V⋅ℓ⋅f⁡\(\|𝒮\|\)C\_\{\\text\{mask,eff\}\}^\{\\text\{FSM\}\}=V\\cdot\\ell\\cdot f\(\|\\mathcal\{S\}\|\), where:

f⁡\(\|𝒮\|\)=\{1if​\|𝒮\|⋅\|Σ\|⋅w≤CL2α⋅\|𝒮\|⋅\|Σ\|⋅wCL2otherwisef\(\|\\mathcal\{S\}\|\)=\\begin\{cases\}1&\\text\{if \}\|\\mathcal\{S\}\|\\cdot\|\\Sigma\|\\cdot w\\leq C\_\{\\text\{L2\}\}\\\\ \\alpha\\cdot\\frac\{\|\\mathcal\{S\}\|\\cdot\|\\Sigma\|\\cdot w\}\{C\_\{\\text\{L2\}\}\}&\\text\{otherwise\}\\end\{cases\}\(6\)withα≈2\\alpha\\approx 2–33reflecting the ratio of main memory to cache access latency, attenuated by hardware prefetching\. For the trie automaton, the working set per step is\|valid​\[st\]\|⋅w<1\|\\text\{valid\}\[s\_\{t\}\]\|\\cdot w<1KB, which always fits in L1 cache, softrie=1f^\{\\text\{trie\}\}=1\.

This cache penalty grows withKK: atK=2,000K=2\{,\}000\(\|𝒮\|≈48,000\|\\mathcal\{S\}\|\\approx 48\{,\}000, table≈47\\approx 47MB\),f≈2\.0f\\approx 2\.0; atK=10,000K=10\{,\}000\(\|𝒮\|≈240,000\|\\mathcal\{S\}\|\\approx 240\{,\}000, table≈235\\approx 235MB\),f≈2\.5f\\approx 2\.5\. This compounds with the linear scaling of\|𝒮\|\|\\mathcal\{S\}\|inKK, producing the super\-linear degradation observed in our experiments \(Section[5](https://arxiv.org/html/2608.12574#S5)\)\.

### G\.7Enum Window Scaling

Given a latency budgetTbudgetT\_\{\\text\{budget\}\}, we can estimate the maximum enum cardinality each approach supports\. In the compilation\-dominated regime \(Ccompile≫CdecodeC\_\{\\text\{compile\}\}\\gg C\_\{\\text\{decode\}\}\), settingTbudget≥Ccompile/csysT\_\{\\text\{budget\}\}\\geq C\_\{\\text\{compile\}\}/c\_\{\\text\{sys\}\}\(wherecsysc\_\{\\text\{sys\}\}is the system throughput in operations per second\) and solving forKKgives conservative \(worst\-case\) bounds usingNchars≤K⋅LmaxN\_\{\\text\{chars\}\}\\leq K\\cdot L\_\{\\max\}:

KmaxFSM≈csys⋅TbudgetLmax⋅\|Σ\|,Kmaxtrie≈csys⋅TbudgetLmax⋅ℓK\_\{\\max\}^\{\\text\{FSM\}\}\\approx\\frac\{c\_\{\\text\{sys\}\}\\cdot T\_\{\\text\{budget\}\}\}\{L\_\{\\max\}\\cdot\|\\Sigma\|\},\\qquad K\_\{\\max\}^\{\\text\{trie\}\}\\approx\\frac\{c\_\{\\text\{sys\}\}\\cdot T\_\{\\text\{budget\}\}\}\{L\_\{\\max\}\\cdot\\ell\}\(7\)These are lower bounds on the achievableKK; with prefix sharing \(Nchars<K⋅LmaxN\_\{\\text\{chars\}\}<K\\cdot L\_\{\\max\}\), the actual limits are higher\. The cardinality expansion factor isKmaxtrie/KmaxFSM=\|Σ\|/ℓ≈64×K\_\{\\max\}^\{\\text\{trie\}\}/K\_\{\\max\}^\{\\text\{FSM\}\}=\|\\Sigma\|/\\ell\\approx 64\\timesfor ASCII with maximum token length 4\. For a 5\-second timeout withLmax=30L\_\{\\max\}=30and\|Σ\|=256\|\\Sigma\|=256, the FSM supportsKmax≈500K\_\{\\max\}\\approx 500–1,0001\{,\}000\(matching OpenAI’s documented limit\), while the trie automaton supportsKmaxtrie≈30,000K\_\{\\max\}^\{\\text\{trie\}\}\\approx 30\{,\}000–100,000100\{,\}000\. Google Gemini’s lower limit \(≈\\approx120\) and Anthropic’s compilation timeout\([3](https://arxiv.org/html/2608.12574#bib.bib27)\)are consistent with more conservative timeouts or less optimized compilation\.

## Appendix HComplexity Analysis: Concrete Examples

### H\.1Scaling Example

The following comparison illustrates the scaling differences for a concrete example withK=2,000K=2\{,\}000enum values \(compilation numbers shown atK=100,000K=100\{,\}000to illustrate the scaling regime\):

To understand these complexity differences concretely, consider anℰ\\mathcal\{E\}withK=2,000K=2\{,\}000values, maximum lengthLmax=30L\_\{\\max\}=30, ASCII alphabet\|Σ\|=256\|\\Sigma\|=256, vocabulary sizeV=32,000V=32\{,\}000, and maximum token lengthℓ=4\\ell=4characters\. Assuming moderate prefix sharing, the total character count isNchars=60,000N\_\{\\text\{chars\}\}=60\{,\}000\.

For FSM compilation, the subset construction cost alone isNchars⋅\|Σ\|=60,000×256≈15\.4N\_\{\\text\{chars\}\}\\cdot\|\\Sigma\|=60\{,\}000\\times 256\\approx 15\.4million operations\. Including Hopcroft minimization adds alog⁡Nchars≈11\\log N\_\{\\text\{chars\}\}\\approx 11factor, yielding≈169\\approx 169million total operations\. In contrast, trie compilation requires𝒪⁡\(\(Nchars\+V\)⋅ℓ\)=\(60,000\+32,000\)×4=368,000\\mathcal\{O\}\(\(N\_\{\\text\{chars\}\}\+V\)\\cdot\\ell\)=\(60\{,\}000\+32\{,\}000\)\\times 4=368\{,\}000operations, a40×40\\timesreduction against subset construction alone, or460×460\\timesincluding minimization\.

The per\-step masking cost difference is equally dramatic\. FSM\-based masking requires checking allV⋅ℓ=32,000×4=128,000V\\cdot\\ell=32\{,\}000\\times 4=128\{,\}000character positions against the current state\. The trie automaton only examines tokens invalid​\[st\]\\text\{valid\}\[s\_\{t\}\], which typically contains 50–500 entries depending on the current trie node depth and prefix sharing\. This represents a 250–2500×\\timesspeedup in the common case\.

### H\.2Controlled Comparison: Precomputed Masks

To isolate the algorithmic contribution from integration\-path effects, we implement a controlled comparison: precomputing XGrammar’s per\-state bitmasks for all DFA states and serving them via cached lookup \(the same path the trie uses\)\. Results on Qwen3\-8B \(K=1,000K=1\{,\}000\):

The number of DFA states equals the number of trie nodes \(both are the minimal DFA forℒℰ\\mathcal\{L\}\_\{\\mathcal\{E\}\}, per Proposition[1](https://arxiv.org/html/2608.12574#Thmproposition1)\)\. Once precomputed, per\-step lookup is identical\. The difference is entirely in precomputation efficiency: the trie’s AC\-based approach computes all masks in𝒪⁡\(\(Nchars\+V\)⋅ℓ\)=33\\mathcal\{O\}\(\(N\_\{\\text\{chars\}\}\+V\)\\cdot\\ell\)=33ms, while enumerating XGrammar’s DFA states and extracting per\-state masks requires instantiating aGrammarMatcherper state, taking 6\.5s\. This confirms that the trie is the efficient algorithm for precomputing per\-state masks over finite sets\.

#### Could DFA\-based precomputation be faster?

The 196×\\timesratio reflects XGrammar’s current API \(per\-stateGrammarMatcherinstantiation\)\. A purpose\-built DFA traversal that directly enumerates states and computes masks could be faster\. However, the fundamental cost remains𝒪⁡\(\|𝒮\|⋅V⋅ℓ\)\\mathcal\{O\}\(\|\\mathcal\{S\}\|\\cdot V\\cdot\\ell\)\(checking each token at each state\), while the trie\+AC approach achieves𝒪⁡\(\(Nchars\+V\)⋅ℓ\)\\mathcal\{O\}\(\(N\_\{\\text\{chars\}\}\+V\)\\cdot\\ell\)by amortizing vocabulary matching across shared prefixes\. The asymptotic gap is a factor of\|𝒮\|/\(Nchars/V\+1\)\|\\mathcal\{S\}\|/\(N\_\{\\text\{chars\}\}/V\+1\), which grows withKK\.

### H\.3Per\-Step Cost Breakdown

Table[4](https://arxiv.org/html/2608.12574#S5.T4)reports valid\-token computation time only\. The full per\-step breakdown including bitmask application \(K=1,000K=1\{,\}000, Qwen3\-8B\):

The𝒪⁡\(V\)\\mathcal\{O\}\(V\)bitmask application \(∼\\sim31μ\\mus via PyTorch tensor operation forV=151V=151K\) dominates single\-request per\-step cost and is method\-independent\. The trie’s valid\-token computation advantage \(0\.08 vs\. 4\.5μ\\mus\) is a small fraction of total per\-step time for a single request\. The advantage compounds in batch serving: atB=128B=128, valid\-token computation runs 128 times \(trie: 10μ\\mus total; XGrammar: 576μ\\mus\), and the trie’s precomputed masks enable the statelessLogitsProcessorpath that bypasses vLLM’s guided decoding pipeline overhead\.

#### Reconciling per\-step numbers\.

Table[4](https://arxiv.org/html/2608.12574#S5.T4)reports 0\.65μ\\mus \(trie\) and 5\.8μ\\mus \(XGrammar\) atK=1,000K=1\{,\}000, while the breakdown above reports 0\.08μ\\mus and 4\.5μ\\mus\. The difference is measurement methodology: Table[4](https://arxiv.org/html/2608.12574#S5.T4)measures the full per\-step masking operation as invoked during batch serving \(including Python binding overhead, bitmask copy from the precomputed store, and loop dispatch\), averaged over 1,000 iterations at realistic decoding states\. The 0\.08μ\\mus above isolates the raw valid\-token\-list lookup in a tight microbenchmark loop\. Both are valid measurements at different abstraction levels; the Table[4](https://arxiv.org/html/2608.12574#S5.T4)numbers reflect the cost actually incurred during serving\. The ratio is consistent:∼\{\\sim\}9×\\times\(Table[4](https://arxiv.org/html/2608.12574#S5.T4): 0\.65 vs\. 5\.8μ\\mus\) vs\.∼\{\\sim\}56×\\times\(raw lookup: 0\.08 vs\. 4\.5μ\\mus\), with the difference attributable to fixed per\-call overhead that is proportionally larger for the faster method\.

### H\.4Precomputation Cost Breakdown

The trie automaton’s precomputation consists of four distinct phases, each with different computational characteristics:

#### Phase 1: Trie Construction

Building the trie fromℰ\\mathcal\{E\}values requires𝒪⁡\(Nchars\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\)operations with one insertion per character\. This phase is typically fast, completing in milliseconds even for large enums\.

#### Phase 2: Vocabulary Decoding

Converting each vocabulary token from its integer ID to its character string representation requires𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)operations\. For modern tokenizers withV≈32,000V\\approx 32\{,\}000andℓ≈4\\ell\\approx 4, this involves roughly 128K character accesses\.

#### Phase 3: Aho\-Corasick Automaton Construction

Building the multi\-pattern matcher over all vocabulary tokens requires𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)time and space\. The resulting automaton enables efficient simultaneous matching of all tokens against any input string\.

#### Phase 4: Trie Traversal with AC Matching

The trie is traversed depth\-first, maintaining the AC automaton state across edges \(saving and restoring at branch points so each edge is processed exactly once\)\. At each node, the automaton identifies all tokens whose character strings start at that position\. This requires𝒪⁡\(Nchars⋅ℓ\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot\\ell\)operations in total, as each character position may trigger up toℓ\\elltoken matches\.

The Aho\-Corasick optimization accounts for most of the efficiency gain\. A naive approach would check each of theVVtokens against each of the\|T⁡\(ℰ\)\|\|T\(\\mathcal\{E\}\)\|trie nodes independently, requiring𝒪⁡\(V⋅\|T⁡\(ℰ\)\|⋅ℓ\)\\mathcal\{O\}\(V\\cdot\|T\(\\mathcal\{E\}\)\|\\cdot\\ell\)operations\. The AC automaton reduces this to𝒪⁡\(\(V\+\|T⁡\(ℰ\)\|\)⋅ℓ\)\\mathcal\{O\}\(\(V\+\|T\(\\mathcal\{E\}\)\|\)\\cdot\\ell\)by building the multi\-pattern matcher once and traversing the trie once with AC state maintenance\.

### H\.5Memory vs\. Speed Trade\-off

The precomputed lookup tables require𝒪⁡\(Nchars⋅f¯\)\\mathcal\{O\}\(N\_\{\\text\{chars\}\}\\cdot\\bar\{f\}\)memory, wheref¯\\bar\{f\}is the average fanout \(number of valid tokens per trie node\)\. At each trie node, we store a list of valid token IDs, with each ID requiring 4 bytes\. The total memory footprint is∑n∈T⁡\(ℰ\)\|valid​\[n\]\|×4\\sum\_\{n\\in T\(\\mathcal\{E\}\)\}\|\\text\{valid\}\[n\]\|\\times 4bytes\.

Concrete memory requirements scale predictably withℰ\\mathcal\{E\}size:

The FSM column shows the theoretical worst\-case\|𝒮\|×\|Σ\|×4\|\\mathcal\{S\}\|\\times\|\\Sigma\|\\times 4bytes\. In practice, XGrammar uses vocabulary partitioning and compressed representations that significantly reduce actual memory\. Measured RSS overhead \(process\-level\) atK=10,000K=10\{,\}000: XGrammar 9\.6 MB, trie 2\.2 MB \(4\.4×\\timesratio\), substantially less than the theoretical 222×\\timesbut still a meaningful advantage\.

For memory\-constrained environments, we employ*lazy computation*: computevalid​\[n\]\\text\{valid\}\[n\]only when nodennis first visited during decoding, and use an LRU cache to bound memory usage\. The total space for full precomputation is𝒪⁡\(\|T⁡\(ℰ\)\|⋅f¯\)\\mathcal\{O\}\(\|T\(\\mathcal\{E\}\)\|\\cdot\\bar\{f\}\), wheref¯\\bar\{f\}is the mean fanout per node; this is typically 1–8 MB forK≤100,000K\\leq 100\{,\}000\(Table[10](https://arxiv.org/html/2608.12574#A4.T10)\), well within L3 cache\. The cache size can be tuned based on available memory, as even a 1MB cache provides substantial speedup by avoiding recomputation of frequently accessed nodes\. The Aho\-Corasick\-based precomputation can also be performed lazily by restricting the multi\-pattern match to subtrees reachable from the current generation prefix, further reducing memory pressure\.

### H\.6GPU\-Based Masking Considerations

Our analysis assumes CPU\-based masking, which is the current practice in vLLM and SGLang\. Modern serving engines increasingly explore GPU\-based logit masking via precomputed bitmask tensors, where the masking operation becomes a single elementwise multiply,𝒪⁡\(V\)\\mathcal\{O\}\(V\)but massively parallel and essentially free relative to the forward pass\. If masking moves entirely to GPU, the per\-step CPU cost advantage diminishes\. However, the trie’s compact bitmask representation \(8 MB atK=100,000K=100\{,\}000vs\.∼\{\\sim\}2 GB for FSM transition tables\) makes it substantially more amenable to GPU transfer, and the compilation time advantages are independent of where masking executes\. The trie’s precomputed per\-node bitmasks are directly usable as GPU tensors without conversion, whereas FSM\-based approaches must still compute the valid set per state before transferring\.

### H\.7Prefix Sharing Analysis

Prefix sharing largely determines the trie automaton’s efficiency\. We define the prefix sharing ratio asr=\|T⁡\(ℰ\)\|/Ncharsr=\|T\(\\mathcal\{E\}\)\|/N\_\{\\text\{chars\}\}, representing the fraction of characters that correspond to unique trie nodes\. Whenr≈1r\\approx 1\(minimal sharing\), the trie has nearly as many nodes as total characters\. Whenr≪1r\\ll 1\(heavy sharing\), the trie is much more compact\.

The prefix sharing ratio affects performance across multiple dimensions:

#### Compilation Time

The trie traversal phase scales with\|T⁡\(ℰ\)\|\|T\(\\mathcal\{E\}\)\|, notNcharsN\_\{\\text\{chars\}\}\. Heavy prefix sharing \(smallrr\) reduces compilation time proportionally\. For example, AWS API names with commonaws\.\*prefixes might achiever=0\.3r=0\.3, reducing compilation time by 70%\.

#### Memory Usage

Fewer trie nodes directly translate to lower memory consumption\. The memory scaling becomes𝒪⁡\(r⋅Nchars⋅f¯\)\\mathcal\{O\}\(r\\cdot N\_\{\\text\{chars\}\}\\cdot\\bar\{f\}\), whererracts as a compression factor\.

#### Per\-step Masking

Nodes near the trie root \(shared prefixes\) tend to have higher fanout, while deeper nodes have lower fanout\. This creates a natural filtering effect: early in the generation process, many tokens remain valid, but the valid set shrinks rapidly as the prefix becomes more specific\.

Real\-world examples demonstrate significant variation in prefix sharing:

- •Tool/API names\(e\.g\.,aws\.s3\.\*,google\.cloud\.\*\):r≈0\.2r\\approx 0\.2–0\.40\.4
- •Medical codes\(e\.g\., ICD\-10 with hierarchical structure\):r≈0\.15r\\approx 0\.15–0\.250\.25
- •Random strings\(e\.g\., UUIDs, random identifiers\):r≈0\.95r\\approx 0\.95–1\.01\.0
- •Natural language\(e\.g\., city names, product names\):r≈0\.6r\\approx 0\.6–0\.80\.8

#### Empirical prefix sharing in our benchmarks\.

Table[14](https://arxiv.org/html/2608.12574#A8.T14)reports the measured prefix sharing ratiorrfor all enum sets used in our experiments\. The classification benchmarks have moderate\-to\-highrr\(0\.59–0\.90\), reflecting natural language labels with limited prefix overlap\. Synthetic tool names and product names have lowrr\(≈0\.40\\approx 0\.40\) due to namespace prefixes \(slack\.get\_\*,aws\.create\_\*\) and shared category/brand prefixes, and the real CMS ICD\-10\-CM code list has the lowestrr\(0\.19\) due to its hierarchical chapter\-letter structure, representing the regime where the trie excels most\.

Table 14:Prefix sharing ratior=\|𝒯⁡\(ℰ\)\|/Ncharsr=\|\\mathcal\{T\}\(\\mathcal\{E\}\)\|/N\_\{\\text\{chars\}\}for benchmark enum sets\. Lowerrrindicates more prefix sharing and greater trie compression\.
#### Valid set size distribution\.

A concern is that\|valid​\[st\]\|\|\\text\{valid\}\[s\_\{t\}\]\|may be𝒪⁡\(V\)\\mathcal\{O\}\(V\)at the root node\. Table[15](https://arxiv.org/html/2608.12574#A8.T15)shows the measured distribution across trie depth forK=1,000K=1\{,\}000synthetic tool names \(Qwen3\-8B, 151K vocabulary\)\. The root node has only 72 valid tokens \(0\.05% ofVV\), notVV, because most vocabulary tokens do not start with any character present in the trie’s root children\. By depth 2, the mean valid set shrinks to 3 tokens\. The increase at depths 3–5 reflects the structure of tool names: short shared prefixes \(e\.g\.,get\_\) end at depth 3–4, after which diverse suffixes create more branching before converging again at deeper levels\.

Table 15:Distribution of\|valid​\[st\]\|\|\\text\{valid\}\[s\_\{t\}\]\|by trie depth \(K=1,000K=1\{,\}000, Qwen3\-8B\)\.DepthMean\|valid\|\|\\text\{valid\}\|Max\|valid\|\|\\text\{valid\}\|Nodes072721161712237193535214103921584334

### H\.8Comparison with Token\-Level Tries \(GENRE\)

GENRE\([9](https://arxiv.org/html/2608.12574#bib.bib18)\)builds tries at token granularity, where each edge is a full BPE token ID\. This avoids the BPE\-trie alignment problem entirely but loses character\-level prefix sharing\. Table[2](https://arxiv.org/html/2608.12574#S4.T2)\(main body\) reports the compilation comparison on synthetic tool names \(Qwen3\-8B,V=151​KV=151\\text\{K\}\); here we add the analysis behind it\.

At smallKK, the token trie is faster because it requires no mask precomputation \(valid tokens are simply the children keys\)\. Our Rust implementation with AC precomputation crosses over atK≈1,000K\\approx 1\{,\}000and is7×7\\timesfaster atK=10,000K=10\{,\}000, because the character\-level trie has fewer nodes \(3×\\timesatK=100K=100, 1\.2×\\timesatK=10,000K=10\{,\}000\) and the AC automaton amortizes vocabulary matching across shared prefixes\. A Python token\-trie implementation \(our own, following GENRE’s design\) shows the same crossover \(K≈1,000K\\approx 1\{,\}000\) and similar per\-step costs \(0\.43–0\.63μ\\mus vs\. our 0\.40–0\.64μ\\mus\), confirming the advantage is algorithmic, not implementation\-specific\. Per\-step costs are language\-invariant at this scale because a CPythondictlookup dispatches to a C implementation, so a single hash lookup is bounded by memory access regardless of the surrounding language; either way, hash lookup \(≈\\approx0\.4–0\.6μ\\mus\) and precomputed bitmask lookup \(≈\\approx0\.65μ\\mus\) are both negligible against the GPU forward pass\. Both methods produce identical outputs \(Proposition[1](https://arxiv.org/html/2608.12574#Thmproposition1)\)\.

#### Per\-step masking comparison\.

The token\-level trie has a per\-step advantage: masking is a single hash lookup on the current token ID to retrieve child keys, costing𝒪⁡\(b\)\\mathcal\{O\}\(b\)wherebbis the branching factor at the current node \(typically 1–10 after the first token\)\. Our character\-level trie costs𝒪​\(\|valid​\[st\]\|\)\\mathcal\{O\}\(\|\\text\{valid\}\[s\_\{t\}\]\|\)per step \(empirically 0\.65μ\\mus, dominated by bitmask copy\)\. In practice, both are sub\-microsecond and negligible relative to the GPU forward pass\. The character\-level trie’s advantage is in compilation at largeKKand tokenizer independence; the token\-level trie’s advantage is in per\-step simplicity at smallKK\.

#### Output equivalence at scale\.

To verify that character\-level and token\-level tries produce identical outputs \(not just enforce the same constraint set\), we ran both on a synthetic tool\-selection task atK∈\{500,1,000,2,000,5,000\}K\\in\\\{500,1\{,\}000,2\{,\}000,5\{,\}000\\\}with Qwen3\-8B \(100 samples perKK, greedy decoding\)\. Both methods produced identical outputs on every sample at everyKK, confirming that the BPE\-trie alignment via AC does not introduce any approximation relative to GENRE\-style token\-level tries\.

### H\.9Canonical vs\. Non\-Canonical Tokenization

The character\-level trie does not restrict generation to canonical tokenization\. Given an enum value such asmedical\_billing, the trie admits*any*vocabulary\-token sequence whose concatenated characters trace the trie pathm→\\toe→⋯→\\to\\cdots\\tog\. Both the canonical BPE decomposition and non\-canonical decompositions \(for examplemed\+ical\+\_billing\) are valid paths, and at decode time the model’s logits select among them\. This is the same tokenization\-agnostic behavior as Outlines, XGrammar, and LLGuidance, and it differs from GENRE, which builds its token\-level trie from one fixed tokenization per enum value and so admits only that decomposition\.

[8](https://arxiv.org/html/2608.12574#bib.bib34)note that this tokenization\-agnostic behavior can in principle degrade quality, since “language models are not conditioned on the surface form of the text, but rather the exact tokenization of the text,” and give a polynomial\-time finite\-state\-transduction framework that enforces canonical\-only tokenization for both BPE and MaxMatch\. Their canonical enforcement is complementary to ours: it can be layered on top of the character\-level constraint without changing the trie, intersecting the trie’s language with the canonical\-tokenization transducer\.

Empirically, the additional freedom is essentially never exercised in our setting\. Across 100 greedy\-decoded samples perK∈\{500,1,000,2,000,5,000\}K\\in\\\{500,1\{,\}000,2\{,\}000,5\{,\}000\\\}on Qwen3\-8B \(Table[16](https://arxiv.org/html/2608.12574#A8.T16)\), the character\-level trie and the GENRE\-style canonical\-only token trie produce identical token sequences on every sample, despite the character trie also permitting non\-canonical decompositions\. For realistic enum strings seen during training, the model’s logits favor canonical decompositions strongly enough that the extra paths carry negligible probability\. This is empirical evidence for our benchmarks rather than a worst\-case guarantee; where a guarantee is required, the Cognetta–Okazaki transducer supplies it\.

### H\.10Alternative Baselines

#### Vocabulary pre\-filtering\.

A natural question is whether simply filtering the vocabulary to tokens that appear as substrings of enum values can speed up FSM compilation\. We build the set of all substrings \(up to length 20\) of the enum values and count matching vocabulary tokens\. On Qwen3\-8B \(151K vocab\), only 0\.2% of tokens match \(379/151K\) regardless ofKK, because most BPE tokens contain characters not present in tool names\. However, pre\-filtering itself costs 5–405ms \(scaling linearly withKK\), comparable to or slower than the trie’s total compilation \(30–48ms\)\. Moreover, pre\-filtering cannot reduce XGrammar’s compilation cost because the bottleneck is DFA state construction, not vocabulary scanning\.

#### Cached DFA compilation\.

Since the trie’s AC automaton can be cached per\-tokenizer, a fair comparison should also cache XGrammar’s tokenizer info\. With warmTokenizerInfo, XGrammar compilation drops from 529–1749ms \(cold\) to 3\.7–1207ms \(warm\)\. However, the warm XGrammar still scales linearly withKK\(246ms atK=1,000K\{=\}1\{,\}000, 1207ms atK=10,000K\{=\}10\{,\}000\), while the trie remains nearly flat \(35–48ms\)\. The trie is faster than warm XGrammar atK≥100K\\geq 100, confirming that the advantage is algorithmic \(avoiding DFA construction\), not merely an artifact of cold\-start overhead\.

#### Hash\-set prefix matching\.

A simpler baseline would maintain a hash set of valid strings and, at each decoding step, check which vocabulary tokens are consistent with remaining valid strings given the current prefix\. This avoids both DFA compilation and AC construction\. However, this approach has𝒪⁡\(K⋅ℓ\)\\mathcal\{O\}\(K\\cdot\\ell\)per\-step cost \(checking each token againstKKstrings\), which is worse than the trie’s𝒪​\(\|valid​\[st\]\|\)\\mathcal\{O\}\(\|\\text\{valid\}\[s\_\{t\}\]\|\)precomputed lookup and comparable to the FSM’s𝒪⁡\(V⋅ℓ\)\\mathcal\{O\}\(V\\cdot\\ell\)whenKKis large\. The trie’s advantage is precisely that it moves this work to compilation time\.

### H\.11Validity at High Cardinality

A central question is whether the trie enables constrained decoding atKKvalues where FSM approaches become impractical\. Table[16](https://arxiv.org/html/2608.12574#A8.T16)shows validity rates on a synthetic tool\-selection task atK=500K=500–5,0005\{,\}000\(Qwen3\-8B, 100 samples perKK\)\. The trie guarantees 100% validity at allKK, while unconstrained decoding drops to 84% atK=1,000K=1\{,\}000\. Both char\-level and token\-level tries produce identical outputs\.

Table 16:Validity \(%\) at high cardinality\. Trie\-constrained decoding guarantees 100% valid outputs regardless ofKK; unconstrained decoding validity degrades\. Char\-level and token\-level \(GENRE\-style\) tries produce identical outputs at allKK\.
### H\.12When the Trie Automaton Excels

The trie automaton provides the greatest benefit under specific conditions that can be systematically identified:

#### Enum Size Threshold

For small enums \(K<50K<50\), the compilation overhead dominates and simple approaches suffice\. The trie automaton becomes advantageous whenK\>100K\>100, with benefits increasing dramatically beyondK=1,000K=1\{,\}000\.

#### Prefix Structure

Enums with meaningful prefix sharing \(r<0\.8r<0\.8\) see substantial memory and compilation time reductions\. Random string enums with no structure \(r≈1\.0r\\approx 1\.0\) still benefit from faster per\-step masking but lose the compilation advantages\.

#### Vocabulary Characteristics

Large vocabularies \(V\>10,000V\>10\{,\}000\) with long average token length \(ℓ\>2\\ell\>2\) make naive per\-step masking expensive, amplifying the trie automaton’s per\-step advantages\.

#### Usage Pattern

Systems serving repeated queries with the same schema can amortize precomputation costs\. Interactive applications with latency budgets under 1 second particularly benefit from the faster per\-step masking\.

Based on these factors, we recommend the following decision criteria:

- •Use trie automatonwhenK\>100K\>100and enum values have identifiable prefix structure
- •Use hierarchical clustering\(Appendix[I](https://arxiv.org/html/2608.12574#A9)\) whenK\>5,000K\>5\{,\}000to manage compilation time
- •Use speculative decoding\(Appendix[J](https://arxiv.org/html/2608.12574#A10)\) whenK\>10,000K\>10\{,\}000or latency budget<1<1s
- •Use simple FSMonly whenK<50K<50or when prefix sharing is minimal \(r\>0\.9r\>0\.9\)

The crossover point where FSM compilation becomes slower than trie compilation typically occurs aroundK=50K=50–100100, depending on prefix sharing and vocabulary size\. BeyondK=1,000K=1\{,\}000, the trie automaton consistently outperforms FSM\-based approaches by orders of magnitude\.

## Appendix IHierarchical Schema Rewriting Details

ForK\>50,000K\>50\{,\}000, hierarchical decomposition partitions the enum intoG≈KG\\approx\\sqrt\{K\}groups, reducing per\-step cardinality fromKKtoK\\sqrt\{K\}\(Proposition[2](https://arxiv.org/html/2608.12574#Thmproposition2)\)\. We consider three clustering approaches: \(1\) string similarity \(edit distance \+ hierarchical clustering\), \(2\) semantic similarity \(sentence embeddings \+ k\-means\), and \(3\) domain taxonomy \(e\.g\., ICD\-10 chapter structure\)\. Effectiveness depends on cluster coherence: when\>\>80% of within\-cluster pairs are more similar than between\-cluster pairs, the LLM reliably selects the correct group\. The approach is robust to 10–20% misassignment \(per\-step cardinality remains𝒪⁡\(K\)\\mathcal\{O\}\(\\sqrt\{K\}\)\), but poor clustering degrades accuracy\. This is a preliminary direction requiring further validation\.

## Appendix JSpeculative Short\-Circuiting Details

Speculative short\-circuiting uses a lightweight scoring function \(embedding similarity, unconstrained LLM generation, or a small classifier\) to identify a top\-kkshortlist before applying trie\-constrained decoding\. This trades the 100% validity guarantee for reduced latency at extremeKK\. Empirical recall varies by domain: Recall@20 ranges from 87% \(medical coding\) to 97% \(geographic entities\)\. A cascading fallback \(top\-kk→\\totop\-2​k2k→\\tofull decoding\) maintains schema compliance\. This extension is most effective when input context strongly predicts the correct enum value and least effective for highly similar enum values\. Like hierarchical rewriting, this is a preliminary direction\.

## Appendix KConstraint\-Aware Dispatch Beyond Finite Sets

To validate that the dispatch principle generalizes beyond finite\-set constraints, we benchmark a*character\-position mask*engine for fixed\-format strings against xgrammar’s regex compilation\. For a format likeYYYY\-MM\-DD, each character position has a known set of valid characters \(digits, hyphens, etc\.\)\. The specialized engine builds a char\-indexed vocabulary and checks only tokens whose first character matches the allowed set at each position, avoiding the full DFA construction\. Table[17](https://arxiv.org/html/2608.12574#A11.T17)shows compilation speedups across all seven tokenizer families and four format types\.

Table 17:Compilation speedup of character\-position masks vs\. xgrammar regex for fixed\-format strings\. Values are×\\timesfaster \(median over 10 runs\)\. xgrammar compilation time is constant per format regardless of format complexity \(88ms–1\.2s depending on vocabulary size\)\.The speedups range from 2×\\times\(UUID on 32K vocab\) to 7,939×\\times\(date on 262K vocab\)\. For date/time formats with small character classes \(digits, separators\), the char\-position mask compiles in under 1ms while xgrammar pays 88ms–1\.2s for DFA construction regardless of format simplicity\. UUIDs show smaller speedups because hexadecimal character classes \(16 valid characters\) produce more candidate tokens per position\. These results confirm that constraint\-aware dispatch, matching specialized engines to constraint structure, yields large speedups whenever the constraint has exploitable regularity, not just for finite sets\.

## Appendix LPractitioner Guidance

The accuracy\-validity tradeoff depends onKK, model capability, and error tolerance\. At smallKK\(≤\\leq59\) with strong models, PE validity exceeds 95% and can surpass trie accuracy; but even here, weaker models \(Mistral: 42\.5%, DeepSeek R1: 0\.2% PE validity\) already benefit from trie enforcement\. At moderateKK\(76–150\), trie strict typically matches or exceeds PE accuracy while guaranteeing validity, though PE can retain an accuracy edge on strong models \(gpt\-oss CLINC150: PE 79\.7% vs\. trie strict 77\.0%\) at the cost of 89% validity\. At largeKK\(≥\\geq1,000\), PE validity approaches 0%\. We recommend: \(1\) PE whenK<50K<50, the model is strong, and retries are acceptable; \(2\) think\+trie when validity must be 100% orK\>50K\>50; \(3\) trie\-only when latency is critical\.

#### When to use which backend\.

For the constrained decoding backend itself \(independent of prompting strategy\):

## Appendix MLLGuidance Comparison

To directly compare against LLGuidance\([15](https://arxiv.org/html/2608.12574#bib.bib6)\), we benchmark its Python library \(v1\.6\.1\) on the same hardware and tokenizer \(Qwen3\-8B, 151K vocabulary\) used for our main experiments\. We measure compilation time \(grammar construction \+ first mask computation\) and per\-step mask computation time for enum schemas withK∈\{10,100,1,000,5,000,10,000\}K\\in\\\{10,100,1\{,\}000,5\{,\}000,10\{,\}000\\\}tool\-like names with realistic prefix structure\. Compilation is averaged over 5 runs; per\-step masking over 200 runs\.

Table 18:Compilation time and per\-step mask computation: LLGuidance vs\. XGrammar vs\. Trie Automaton \(Qwen3\-8B, 151K vocabulary\)\. LLGuidance achieves the fastest compilation via lazy Earley parsing, but its per\-step masking is 110–215×\\timesslower than the trie’s precomputed lookups\.LLGuidance’s lazy Earley parser achieves near\-zero compilation cost \(0\.6ms atK=100K=100, 24ms atK=10,000K=10\{,\}000\), outperforming both XGrammar and our trie on this dimension\. However, its per\-step mask computation \(73–141μ\\mus\) is 110–215×\\timesslower than the trie automaton’s precomputed lookups \(0\.65μ\\mus\) and 9–24×\\timesslower than XGrammar \(5–10μ\\mus\)\. This confirms the theoretical prediction: LLGuidance must traverse the full vocabulary trie at each step \(𝒪⁡\(V\)\\mathcal\{O\}\(V\)\), while our precomputed masks reduce this to𝒪​\(\|valid​\[st\]\|\)\\mathcal\{O\}\(\|\\text\{valid\}\[s\_\{t\}\]\|\)\. For a typical enum generation requiring 5–10 decoding steps, the per\-step advantage dominates: the trie’s total masking cost is∼\\sim5μ\\mus versus LLGuidance’s∼\\sim500μ\\mus, a 100×\\timesdifference that compounds in batch serving\. The three approaches occupy distinct points in the compilation\-vs\-masking tradeoff: LLGuidance minimizes compilation, XGrammar balances both, and the trie automaton minimizes per\-step cost through precomputation\.

### M\.1Batch Serving Throughput

The per\-step masking cost differences above are measured for a single request\. In production batch serving, the GPU forward pass is shared acrossBBconcurrent requests \(one batched matrix multiply\), but masking runs per\-request on CPU since each request occupies a different decoding state\. Table[19](https://arxiv.org/html/2608.12574#A13.T19)shows the measured total CPU masking time per batch\-step asBBgrows\.

Table 19:Measured batch masking cost \(μ\\mus per batch\-step\) on Qwen3\-8B \(151K vocabulary\),K=1,000K=1\{,\}000tool names\. A typical GPU forward pass takes∼\{\\sim\}10ms; the “% fwd” column shows masking cost as a fraction of this\. AtB=128B=128, LLGuidance masking consumes 37% of the forward pass, becoming the throughput bottleneck\.AtB=128B=128, LLGuidance’s per\-step masking \(3\.7ms\) consumes over a third of the GPU forward pass time, directly reducing serving throughput\. XGrammar’s 783μ\\mus \(7\.8%\) is also significant\. The trie’s 10μ\\mus \(0\.1%\) is negligible at any batch size\. These results are K\-independent for the trie: atK=10,000K=10\{,\}000, the trie still measures 10\.3μ\\mus atB=128B=128, while XGrammar and LLGuidance show similar costs \(781μ\\mus and 3,671μ\\mus respectively\)\. This explains why per\-step masking cost, not compilation, is the binding constraint for serving throughput at scale\.