# Automata-based constraints for language model decoding

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 11 Jul 2024.

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

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- ["We Need Structured Output": Towards User-centered Constraints on Large Language Model Output](https://mlsanity.com/paper/2404.07362/) (2024)
- [RNN Approaches to Text Normalization: A Challenge](https://mlsanity.com/paper/1611.00068/) (2016)
- [Composing Finite State Transducers on GPUs](https://mlsanity.com/paper/1805.06383/) (2018)

## Built on by (most cited first, 30 of 51)

- [Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models](https://mlsanity.com/paper/2408.02442/) (2024)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [Inference Scaling for Long-Context Retrieval Augmented Generation](https://mlsanity.com/paper/2410.04343/) (2024)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [Enforcing Temporal Constraints for LLM Agents](https://mlsanity.com/paper/2512.23738/) (2025)
- [From Language Models over Tokens to Language Models over Characters](https://mlsanity.com/paper/2412.03719/) (2024)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [DINGO: Constrained Inference for Diffusion LLMs](https://mlsanity.com/paper/2505.23061/) (2025)
- [Unveiling the Potential of Diffusion Large Language Model in Controllable Generation](https://mlsanity.com/paper/2507.04504/) (2025)
- [Self-Steering Language Models](https://mlsanity.com/paper/2504.07081/) (2025)
- [Controllable Generation via Locally Constrained Resampling](https://mlsanity.com/paper/2410.13111/) (2024)
- [Pre3: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation](https://mlsanity.com/paper/2506.03887/) (2025)
- [Natural Language Outlines for Code: Literate Programming in the LLM Era](https://mlsanity.com/paper/2408.04820/) (2024)
- [Correctness-Guaranteed Code Generation via Constrained Decoding](https://mlsanity.com/paper/2508.15866/) (2025)
- [The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decoding](https://mlsanity.com/paper/2603.03305/) (2026)
- [Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators](https://mlsanity.com/paper/2602.22647/) (2026)
- [Tokenization as Finite-State Transduction](https://mlsanity.com/paper/2410.15696/) (2024)
- [RefineStat: Efficient Exploration for Probabilistic Program Synthesis](https://mlsanity.com/paper/2509.01082/) (2025)
- [Thinking Before Constraining: A Unified Decoding Framework for Large Language Models](https://mlsanity.com/paper/2601.07525/) (2026)
- [Transducing Language Models](https://mlsanity.com/paper/2603.05193/) (2026)
- [When Grammar Guides the Attack: Uncovering Control-Plane Vulnerabilities in LLMs with Structured Output](https://mlsanity.com/paper/2503.24191/) (2025)
- [Semantic Probabilistic Control of Language Models](https://mlsanity.com/paper/2505.01954/) (2025)
- [Earley-Driven Dynamic Pruning for Efficient Structured Decoding](https://mlsanity.com/paper/2506.01151/) (2025)
- [Schema Generation for Large Knowledge Graphs Using Large Language Models](https://mlsanity.com/paper/2506.04512/) (2025)
- [Calibrated Predictive Lower Bounds on Time-to-Unsafe-Sampling in LLMs](https://mlsanity.com/paper/2506.13593/) (2025)
- [UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8](https://mlsanity.com/paper/2511.05578/) (2025)
- [DICE: Structured Reasoning in LLMs through SLM-Guided Chain-of-Thought Correction](https://mlsanity.com/paper/2510.09211/) (2025)
- [Google's AI & Economy ATLAS v1.0: Mapping Gemini Usage in the Economy](https://mlsanity.com/paper/2608.00038/) (2026)
- [Decoding-Free Sampling Strategies for LLM Marginalization](https://mlsanity.com/paper/2510.20208/) (2025)

## Abstract (arXiv)

Language models (LMs) are often expected to generate strings in some formal language; for example, structured data, API calls, or code snippets. Although LMs can be tuned to improve their adherence to formal syntax, this does not guarantee conformance, especially with smaller LMs suitable for large-scale deployment. In addition, tuning requires significant resources, making it impractical for uncommon or task-specific formats. To prevent downstream parsing errors we would ideally constrain the LM to only produce valid output, but this is severely complicated by tokenization, which is typically both ambiguous and misaligned with the formal grammar. We solve these issues through the application of automata theory, deriving an efficient closed-form solution for the regular languages, a broad class of formal languages with many practical applications, including API calls or schema-guided JSON and YAML. We also discuss pragmatic extensions for coping with the issue of high branching factor, and extend our techniques to deterministic context-free languages, which similarly admit an efficient closed-form solution. Previous work on this topic (Willard and Louf, 2023) layers bespoke solutions onto automata, leading to problems with speed, correctness, and extensibility. Instead, we reformulate the entire task in terms of automata so we can leverage well-studied and well-optimized algorithms. Our system compiles constraints ~7,000x faster, is provably correct, and can be extended in a modular fashion.