Grammar-Constrained Decoding

Follow this topic Ask about this topic

The field studies how to combine language models with formal grammars so generated sequences follow languages and formats such as JSON, SQL, programming languages, and domain-specific commands. Common approaches use parser- or automaton-state token masks, context-free grammar parsing, and increasingly lookahead, grammar refinement, probability correction, or parallel decoding to improve completion and speed. These constraints support reliable structured generation, executable queries, and policy enforcement, but syntactic validity alone does not guarantee correct meaning or safe behavior. A central tension is that hard masking can distort the model’s conditional distribution or block good outputs when grammars are incomplete, while richer checks and more faithful sampling add computational cost.

Latest papers

30 papers4 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

DConstrain: Compiling Context-Parameterized Transitions for Diffusion Language Model Constrained Decoding
Oct 22, 2026Shidong Cao, Jing Ma, Wenhao Chai +3Constrained Decoding Grammar-Constrained Decoding
Hong Kong Baptist University · Princeton University · Ant Group
Metamodel-Guided LLM Decoding for Consistent DSL Generation
Oct 21, 2026Boqi Chen, Aren A. Babikian, José Antonio Hernández LópezConstrained Decoding Software Engineering
University of Ottawa, Ottawa, Canada · McGill University, Montreal, Canada · University of Murcia, Murcia, Spain
GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learning
Sep 30, 2026Gabriele Tuccio, Antonino Furnari, Aldo Gangemi +1RL for Language Models Constrained Decoding
University of Catania · ISTC - National Research Council, Italy · University of Bologna
Semantic Prefix Oracles for LLM Decoding: Contracts and Differential Validation
Sep 28, 2026Paul Kronlund-DrouaultConstrained Decoding LLM-Based Program Synthesis
ENS de Lyon Lyon, France · Unsuspicious Industries Paris, France · Université de Lille Lille, France
Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance
Aug 28, 2026Vincenzo Collura, Karim Tit, Eleonora Giunchiglia +2Constrained Decoding Grammar-Constrained Decoding
University of Luxembourg, Luxembourg · Imperial College London, United Kingdom
Beam Search, Self-Consistency, and the Limits of Inference-Time Scaling for Grammar-Constrained Text-to-SQL in Small Language Models
Aug 26, 2026Ty Chermsirivatana, John MacCormickInference-Time Scaling Small Language Models
Deep Network Understanding Lab Dickinson College
Repair, Not Improvement: Decomposing Constrained Decoding in Tool-Call Abstention
Aug 14, 2026Janghoon LeeLLM Tool Use LLM Abstention
Redrob
The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding
Aug 10, 2026Işıl Özgü, Yaoxuan Wu, Guy Van den Broeck +1Constrained Decoding Grammar-Constrained Decoding
University of California, Los Angeles Los Angeles, CA, USA
Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees
Aug 6, 2026Kevin Cheang, Geoff Hulette, Rahul Kumar +5LLM-Based Program Synthesis Linear Temporal Logic
Amazon Web Services · Purdue University
Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments
Jul 20, 2026Shuoming Zhang, Ruiyuan Xu, Haofeng Li +7Code Generation LLM Code Generation
SKLP, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China · University of Leeds, United Kingdom
Policy-Conditioned Constrained Decoding for Column-Level Access Control in Text-to-SQL
Jul 14, 2026Ryoto Miyamoto, Xin Fan, Hayato YamanaPrivacy Leakage in Language Models Text-to-SQL
Waseda University
GRID: Grammar-Railed Decoding for Enterprise SQL Generation
Jul 11, 2026Mohsen ArjmandiLLM Guardrails Text-to-SQL
evolutionID GmbH
Grammar-Guided Hierarchical Parsing for Long-form Audio Activity Recognition
Jun 26, 2026Peng Zhang, Qingyu Luo, Philip J. B. Jackson +1Temporal Action Segmentation Human Activity Recognition
Centre for Vision, Speech and Signal Processing (CVSSP), University of Surrey, U.K.
Weave of Formal Thought
Jun 24, 2026Alexandre BouayadCode Language Models LLM Code Generation
The Alignment Problem in Constrained Code Generation
Jun 19, 2026Matteo Biagiola, Jahrim Gabriele Cesario, Luca Di Grazia +2Constrained Decoding Constraint Satisfaction
University of St. Gallen and Università della Svizzera italiana (USI) St. Gallen and Lugano, SG and TI Switzerland · University of St. Gallen St. Gallen, SG, Switzerland
Grammar-Constrained Decoding Can Jailbreak LLMs into Generating Malicious Code
Jun 10, 2026Yitong Zhang, Shiteng Lu, Jia LiLLM Safety Alignment LLM Jailbreak Attacks
College of AI Tsinghua University Beijing, China · Yingcai Honors College University of Electronic Science and Technology of China Chengdu, China
EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models
May 30, 2026Hyundong Jin, Yo-Sub HanParallel Decoding Diffusion Language Model Decoding
Yonsei University, Seoul, Republic of Korea
Accelerating Constrained Decoding with Token Space Compression
May 28, 2026Michael Sullivan, Alexander KollerConstrained Decoding LLM Inference Acceleration
Department of Language Science and Technology Saarland Informatics Campus Saarland University, Saarbrücken, Germany
TruncProof: A Guardrail for LLM-based JSON Generation under Token-Length Constraints
May 13, 2026Yoshio Kato, Shuhei TarashimaConstrained Decoding Structured Output Generation
NTT DOCOMO BUSINESS, Inc., Japan
Extending Confidence-Based Text2Cypher with Grammar and Schema Aware Filtering
May 11, 2026Makbule Gulcin OzsoyLLM Inference Text-to-Cypher
Neo4j, London, UK
Future Validity is the Missing Statistic: From Impossibility to $Φ$ -Estimation for Grammar-Faithful Speculative Decoding
May 8, 2026Wenhua Nie, Zijie Meng, Kun Zou +5Doob H-Transform Speculative Decoding
National Taiwan University
Reliable Answers for Recurring Questions: Boosting Text-to-SQL Accuracy with Template Constrained Decoding
Apr 30, 2026Smit Jivani, Sarvam Maheshwari, Sunita SarawagiText-to-SQL Grammar-Constrained Decoding
Department of Computer Science and Engineering, Indian Institute of Technology Bombay, India
Prefix Parsing is Just Parsing
Apr 23, 2026Clemente Pasti, Andreas Opedal, Timothy J. O'Donnell +2Grammar-Constrained Decoding
1ETH Zürich · 2McGill University · 3Canada CIFAR AI Chair +2
Copy-as-Decode: Grammar-Constrained Parallel Prefill for LLM Editing
Apr 20, 2026Ziyang LiuLLM Inference Acceleration Parallel Decoding
Independent Researcher
Schema-Key Wording as an Instruction Channel in Structured Generation under Constrained Decoding
Apr 16, 2026Yifan LeConstrained Generative Modeling Constrained Decoding
Independent Researcher
Learning and Enforcing Context-Sensitive Control for LLMs
Apr 12, 2026Mohammad Albinhassan, Pranava Madhyastha, Mark Law +1Constrained Generative Modeling Grammar-Constrained Decoding
Imperial College London · City University of London · The Alan Turing Institute +1
Precise Robot Command Understanding Using Grammar-Constrained Large Language Models
Apr 5, 2026Xinyun Huo, Raghav Gnanasambandam, Xinyao ZhangHuman-Robot Interaction Human-Robot Collaboration
Industrial and Manufacturing Engineering, Florida State University, Tallahassee, FL, USA
Pingala: Prosody-Aware Decoding for Sanskrit Poetry Generation
Mar 25, 2026Manoj Balaji Jagadeeshan, Atul Singh, Nallani Chakravartula Sahith +2Text Generation Language Model Decoding
Indian Institute of Technology, Kharagpur · Oriﬂow
Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding
Mar 4, 2026Faruk Alpay, Bilge SenturkGrammar-Constrained Decoding
Department of Computer Engineering, Bahçeşehir University, Istanbul, Turkey · Department of Industrial Engineering, Bahçeşehir University, Istanbul, Turkey
Grammar-Aligned Decoding
May 31, 2024Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick +2Constrained Generative Modeling Constrained Decoding
University of Wisconsin-Madison · University of California San Diego

Oct 22, 2026J/K move · Enter open · S save

DConstrain: Compiling Context-Parameterized Transitions for Diffusion Language Model Constrained Decoding

Shidong Cao, Jing Ma, Wenhao Chai, Yuchen Tian+2

Hong Kong Baptist University · Princeton University · Ant Group

Constrained Decoding Grammar-Constrained Decoding Diffusion Language Model Decoding Diffusion Language Model Inference Diffusion Language Models

Open paper AskPDF arXiv

Diffusion language models (DLMs) decode multiple tokens in parallel, so individually valid tokens can be incompatible together under a schema. Exact joint inference over a grammar graph enforces compatibility, but it requires token-labeled successors across many hypothetical parser configurations. Encoding stacks and field histories in compiled states can cause exponential growth, which forces prior exact decoders to fix property orders and exclude valid outputs. We present DConstrain, which compiles schemas into context-parameterized transition programs. Cold compilation specializes token consumption to local grammar states while retaining context-dependent stack operations, environment guards, and caller-dependent deferred parsing symbolically. Tracking field histories as runtime values supports arbitrary property order without enumerating field subsets offline. At runtime, warm compilation binds reached configurations to these programs to construct exact successors, overlapping with the model forward pass because graph construction requires no model scores. Furthermore, token-effect grouping merges tokens with identical compiled effects before runtime contexts are bound, so groups are reused across stacks and environments even when concrete successors differ. Objective-specific score aggregation and token restoration provably preserve both the Viterbi optimum and the token-labeled path distribution of ungrouped inference. Across three benchmarks and two DLM families, DConstrain compiles 100% of BFCL schemas under arbitrary property orders, whereas an optimized finite-state baseline compiles only 71.30-85.81%. Under arbitrary property order, it reduces BFCL end-to-end decoding latency by 6.65-46.26 times with 100% schema validity and raises DiffusionGemma's BFCL accuracy from 37.27% under fixed order to 81.56%.