# Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 27 of its 37 references that are in the map.
- First posted on arXiv 8 Jul 2026.

## Placed in

- Diffusion models / [Discrete and text diffusion](https://mlsanity.com/diffusion/discrete-and-text-diffusion/)

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

- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Dream 7B: Diffusion Large Language Models](https://mlsanity.com/paper/2508.15487/) (2025)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data](https://mlsanity.com/paper/2406.03736/) (2024)
- [Mercury: Ultra-Fast Language Models Based on Diffusion](https://mlsanity.com/paper/2506.17298/) (2025)
- [Spider 2.0: Evaluating Language Models on Real-World Enterprise Text-to-SQL Workflows](https://mlsanity.com/paper/2411.07763/) (2024)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [APIGen: Automated Pipeline for Generating Verifiable and Diverse Function-Calling Datasets](https://mlsanity.com/paper/2406.18518/) (2024)
- [Seed Diffusion: A Large-Scale Diffusion Language Model with High-Speed Inference](https://mlsanity.com/paper/2508.02193/) (2025)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Flexible and Efficient Grammar-Constrained Decoding](https://mlsanity.com/paper/2502.05111/) (2025)
- [DINGO: Constrained Inference for Diffusion LLMs](https://mlsanity.com/paper/2505.23061/) (2025)
- [Constrained Decoding of Diffusion LLMs with Context-Free Grammars](https://mlsanity.com/paper/2508.10111/) (2025)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)

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

- [Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models](https://mlsanity.com/paper/2609.32900/) (2026)
- [Twist, Don't Tilt: Trajectory-Exact Constrained Decoding for Masked Diffusion Models](https://mlsanity.com/paper/2609.35609/) (2026)
- [Grab a Coffee: Future-Aware Guidance for Discrete Diffusion with Compiled Objectives](https://mlsanity.com/paper/2609.35924/) (2026)
- [OxiGen: Oxidation-State-Aware Crystal Generation](https://mlsanity.com/paper/2610.08296/) (2026)

## Abstract (arXiv)

Constrained decoding is essential for serving LLMs, ensuring that generated outputs follow specific structures such as JSON schema-formatted function calls. Existing systems are designed for autoregressive models and assume left-to-right generation, masking out invalid next tokens at each step. Diffusion language models, however, break this assumption: they sample multiple positions simultaneously from a fully-factorized mean-field distribution at each denoising step. In this paper, we present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton. Viewing finite automata as graphical models, we obtain tractable representations of the constrained distribution that enable efficient inference. The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding under arbitrary remasking schedules. Applying depth-reduction techniques from arithmetic circuit theory, we further reduce sampling depth from linear to logarithmic in the sequence length. Empirical evaluations on Dream-7B and LLaDA-8B show substantial accuracy gains across various tasks including function calling (xLAM, BFCL), planning (Sudoku, Countdown), text-to-SQL (Spider), and math reasoning (GSM-Symbolic), with little inference overhead relative to unconstrained decoding. For example, on BFCL-Live, our approach improves Dream-7B's greedy decoding accuracy from 63.9% to 71.5%, and stochastic sampling accuracy from 22.3% to 69.0%, where the unconstrained baseline collapses, with under 5% wall-clock overhead.