# Constrained Decoding of Diffusion LLMs with Context-Free Grammars

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 52 references that are in the map.
- First posted on arXiv 13 Aug 2025.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence](https://mlsanity.com/paper/2401.14196/) (2024)
- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [StarCoder 2 and The Stack v2: The Next Generation](https://mlsanity.com/paper/2402.19173/) (2024)
- [InCoder: A Generative Model for Code Infilling and Synthesis](https://mlsanity.com/paper/2204.05999/) (2022)
- [CodeGeeX: A Pre-Trained Model for Code Generation with Multilingual Benchmarking on HumanEval-X](https://mlsanity.com/paper/2303.17568/) (2023)
- [Efficient Training of Language Models to Fill in the Middle](https://mlsanity.com/paper/2207.14255/) (2022)
- [OctoPack: Instruction Tuning Code Large Language Models](https://mlsanity.com/paper/2308.07124/) (2023)
- [DiffuCoder: Understanding and Improving Masked Diffusion Models for Code Generation](https://mlsanity.com/paper/2506.20639/) (2025)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [CodeGemma: Open Code Models Based on Gemma](https://mlsanity.com/paper/2406.11409/) (2024)
- [SWT-Bench: Testing and Validating Real-World Bug-Fixes with Code Agents](https://mlsanity.com/paper/2406.12952/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [BaxBench: Can LLMs Generate Correct and Secure Backends?](https://mlsanity.com/paper/2502.11844/) (2025)
- [Type-Constrained Code Generation with Language Models](https://mlsanity.com/paper/2504.09246/) (2025)
- [DINGO: Constrained Inference for Diffusion LLMs](https://mlsanity.com/paper/2505.23061/) (2025)
- [Enhancing Code Generation for Low-Resource Languages: No Silver Bullet](https://mlsanity.com/paper/2501.19085/) (2025)
- [Constrained Decoding for Fill-in-the-Middle Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars](https://mlsanity.com/paper/2402.17988/) (2024)
- [Live Functional Programming with Typed Holes](https://mlsanity.com/paper/1805.00155/) (2018)
- [Subsequence Matching and Analysis Problems for Formal Languages](https://mlsanity.com/paper/2410.07992/) (2024)

## Built on by (most cited first, 14 of 14)

- [Exploring the Potential of Diffusion Large Language Models in Code Generation](https://mlsanity.com/paper/2509.11252/) (2025)
- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)
- [Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata](https://mlsanity.com/paper/2607.07026/) (2026)
- [DiffuTester: Accelerating Unit Test Generation for Diffusion LLMs via Mining Structural Pattern](https://mlsanity.com/paper/2509.24975/) (2025)
- [AnCoder: Anchored Code Generation via Discrete Diffusion Models](https://mlsanity.com/paper/2602.17688/) (2026)
- [When Correct Isn't Usable: Improving Structured Output Reliability in Small Language Models](https://mlsanity.com/paper/2605.02363/) (2026)
- [Constrained Code Generation with Discrete Diffusion](https://mlsanity.com/paper/2605.16829/) (2026)
- [EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models](https://mlsanity.com/paper/2606.00722/) (2026)
- [The Alignment Problem in Constrained Code Generation](https://mlsanity.com/paper/2606.21619/) (2026)
- [Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance](https://mlsanity.com/paper/2608.28229/) (2026)
- [Continuous Diffusion Models Can Obey Formal Syntax](https://mlsanity.com/paper/2602.12468/) (2026)
- [Beyond the Autoregressive Horizon: A Comprehensive Survey of Diffusion Models, World Modelling, and State Space Models for Code](https://mlsanity.com/paper/2606.23690/) (2026)
- [Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models](https://mlsanity.com/paper/2609.32900/) (2026)
- [Intent-Triggered Anchoring for Multi-Token Format Units in Parallel Decoding of Diffusion Language Models](https://mlsanity.com/paper/2610.16516/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have shown promising performance across diverse domains. Many practical applications of LLMs, such as code completion and structured data extraction, require adherence to syntactic constraints specified by a formal language. Yet, due to their probabilistic nature, LLM output is not guaranteed to adhere to such formal languages. Prior work has proposed constrained decoding as a means to restrict LLM generation to particular formal languages. However, existing works are not applicable to the emerging paradigm of diffusion LLMs, when used in practical scenarios such as the generation of formally correct C++ or JSON output. In this paper we address this challenge and present the first constrained decoding method for diffusion models, one that can handle formal languages captured by context-free grammars. We begin by reducing constrained decoding to the more general additive infilling problem, which asks whether a partial output can be completed to a valid word in the target language. This problem also naturally subsumes the previously unaddressed multi-region infilling constrained decoding. We then reduce this problem to the task of deciding whether the intersection of the target language and a regular language is empty and present an efficient algorithm to solve it for context-free languages. Empirical results on various applications, such as C++ code infilling and structured data extraction in JSON, demonstrate that our method achieves near-perfect syntactic correctness while consistently preserving or improving functional correctness. Importantly, our efficiency optimizations ensure that the computational overhead remains practical.