mlsanityData to 7 Oct 2026

Automata-based constraints for language model decoding

arXiv 2407.08103 ↗First posted 11 Jul 2024cs.CL cs.FLcited by 49

Not on the map. Why?

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.

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

Builds on

12 of 41 references.

References · 12

  1. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
  2. 2015Neural Machine Translation of Rare Words with Subword Unitscited by 2,898
  3. 2018SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processingcited by 1,973
  4. 2022Fast Inference from Transformers via Speculative Decodingcited by 1,615
  5. 2022Competition-Level Code Generation with AlphaCodecited by 1,427
  6. 2021PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Modelscited by 402
  7. 2023Grammar-Constrained Decoding for Structured NLP Tasks without Finetuningcited by 186
  8. 2022Synchromesh: Reliable code generation from pre-trained language modelscited by 156
  9. 2023Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programscited by 79
  10. 2024"We Need Structured Output": Towards User-centered Constraints on Large Language Model Outputcited by 46
  11. 2016RNN Approaches to Text Normalization: A Challengecited by 30
  12. 2018Composing Finite State Transducers on GPUscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 7; 2025: 21; 2026: 21.

49 papers.

Sort:

By area:

  1. 2024Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Modelscited by 90
  2. 2024XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Modelscited by 73
  3. 2024Inference Scaling for Long-Context Retrieval Augmented Generationcited by 65
  4. 2025Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlocited by 45
  5. 2025Flexible and Efficient Grammar-Constrained Decodingcited by 42
  6. 2025Enforcing Temporal Constraints for LLM Agentscited by 31
  7. 2024From Language Models over Tokens to Language Models over Characterscited by 28
  8. 2025Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Samplingcited by 20
  9. 2025DINGO: Constrained Inference for Diffusion LLMscited by 15
  10. 2025Unveiling the Potential of Diffusion Large Language Model in Controllable Generationcited by 14
  11. 2025Self-Steering Language Modelscited by 13
  12. 2024Controllable Generation via Locally Constrained Resamplingcited by 11
37 more
  1. 2025Pre3: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generationcited by 11
  2. 2024Natural Language Outlines for Code: Literate Programming in the LLM Eracited by 9
  3. 2025Correctness-Guaranteed Code Generation via Constrained Decodingcited by 7
  4. 2026The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decodingcited by 7
  5. 2026Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Acceleratorscited by 6
  6. 2024Tokenization as Finite-State Transductioncited by 5
  7. 2025RefineStat: Efficient Exploration for Probabilistic Program Synthesiscited by 5
  8. 2026Thinking Before Constraining: A Unified Decoding Framework for Large Language Modelscited by 5
  9. 2025Semantic Probabilistic Control of Language Modelscited by 4
  10. 2025When Grammar Guides the Attack: Uncovering Control-Plane Vulnerabilities in LLMs with Structured Outputcited by 3
  11. 2025Earley-Driven Dynamic Pruning for Efficient Structured Decodingcited by 3
  12. 2025Schema Generation for Large Knowledge Graphs Using Large Language Modelscited by 3
  13. 2025Calibrated Predictive Lower Bounds on Time-to-Unsafe-Sampling in LLMscited by 3
  14. 2025UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8cited by 3
  15. 2026Transducing Language Modelscited by 3
  16. 2025DICE: Structured Reasoning in LLMs through SLM-Guided Chain-of-Thought Correctioncited by 2
  17. 2025Decoding-Free Sampling Strategies for LLM Marginalizationcited by 1
  18. 2026EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Modelscited by 1
  19. 2025Semantic Integrity Constraints: Declarative Guardrails for AI-Augmented Data Processing Systemscited by 0
  20. 2025textttSEM-CTRL: Semantically Controlled Decodingcited by 0
  21. 2025Combining Constrained and Unconstrained Decoding via Boosting: BoostCD and Its Application to Information Extractioncited by 0
  22. 2026Autoregressive Synthesis of Sparse and Semi-Structured Mixed-Type Datacited by 0
  23. 2026Precise Robot Command Understanding Using Grammar-Constrained Large Language Modelscited by 0
  24. 2026An Empirical Analysis of Static Analysis Methods for Detection and Mitigation of Code Library Hallucinationscited by 0
  25. 2026Scalable Model-Based Clustering with Sequential Monte Carlocited by 0
  26. 2026NCO: A Versatile Plug-in for Handling Negative Constraints in Decodingcited by 0
  27. 2026Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Supportcited by 0
  28. 2026LatticeBridge: Rare-Event Sequential Inference for Faithful Structured Sequence Synthesiscited by 0
  29. 2026Beyond Perplexity: UTF-8 Validity in Byte-aware Language Modelscited by 0
  30. 2026Are you speaking my languages? On spoken language adherence in multimodal LLMscited by 0
  31. 2026Answer Engineering: Local Trajectory Editing for Protocol-Constrained Decision Making in Large Language Modelscited by 0
  32. 2026GRID: Grammar-Railed Decoding for Enterprise SQL Generationcited by 0
  33. 2026Imprompt: A Language Framework for Prompt Programmingcited by 0
  34. 2026Frustratingly Simple Black-Box Adaptation of Language Models via Logit Biascited by 0
  35. 2026Trie Automata for Constrained Decoding over Large Finite Setscited by 0
  36. 2026PTC-Decoder: Towards Intelligent SLMs on Offline Resource-Constrained Edge Devicescited by 0
  37. 2026Twist, Don't Tilt: Trajectory-Exact Constrained Decoding for Masked Diffusion Modelscited by 0