# DINGO: Constrained Inference for Diffusion LLMs

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 44 references that are in the map.
- First posted on arXiv 29 May 2025.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [LeanDojo: Theorem Proving with Retrieval-Augmented Language Models](https://mlsanity.com/paper/2306.15626/) (2023)
- [Block Diffusion: Interpolating Between Autoregressive and Diffusion Language Models](https://mlsanity.com/paper/2503.09573/) (2025)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [SSD-LM: Semi-autoregressive Simplex-based Diffusion Language Model for Text Generation and Modular Control](https://mlsanity.com/paper/2210.17432/) (2022)
- [d1: Scaling Reasoning in Diffusion Large Language Models via Reinforcement Learning](https://mlsanity.com/paper/2504.12216/) (2025)
- [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)
- [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)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [CRANE: Reasoning with constrained LLM generation](https://mlsanity.com/paper/2502.09061/) (2025)
- [Validating Large Language Models with ReLM](https://mlsanity.com/paper/2211.15458/) (2022)

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

- [A Survey on Diffusion Language Models](https://mlsanity.com/paper/2508.10875/) (2025)
- [Constrained Decoding of Diffusion LLMs with Context-Free Grammars](https://mlsanity.com/paper/2508.10111/) (2025)
- [SEVerA: Verified Synthesis of Self-Evolving Agents](https://mlsanity.com/paper/2603.25111/) (2026)
- [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)
- [Constraint Tax in Open-Weight LLMs: An Empirical Study of Tool Calling Suppression Under Structured Output Constraints](https://mlsanity.com/paper/2606.25605/) (2026)
- [AnCoder: Anchored Code Generation via Discrete Diffusion Models](https://mlsanity.com/paper/2602.17688/) (2026)
- [The Architecture of Errors: From Universal Impossibility to Patch-Local LLM Reliability](https://mlsanity.com/paper/2605.30628/) (2026)
- [EPIC: Efficient and Parallel Inference under CFG Constraints for Diffusion Language Models](https://mlsanity.com/paper/2606.00722/) (2026)
- [Accelerating Masked Diffusion Large Language Models: A Survey of Efficient Inference Techniques](https://mlsanity.com/paper/2607.12829/) (2026)
- [Constraints-Guided Diffusion Reasoner for Neuro-Symbolic Learning](https://mlsanity.com/paper/2508.16524/) (2025)
- [Imprompt: A Language Framework for Prompt Programming](https://mlsanity.com/paper/2607.22683/) (2026)
- [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)
- [Intent-Triggered Anchoring for Multi-Token Format Units in Parallel Decoding of Diffusion Language Models](https://mlsanity.com/paper/2610.16516/) (2026)

## Abstract (arXiv)

Diffusion LLMs have emerged as a promising alternative to conventional autoregressive LLMs, offering significant potential for improved runtime efficiency. However, existing diffusion models lack the ability to provably enforce user-specified formal constraints, such as regular expressions, which makes them unreliable for tasks that require structured outputs, such as fixed-schema JSON generation. Unlike autoregressive models that generate tokens sequentially, diffusion LLMs predict a block of tokens in parallel. This parallelism makes traditional constrained decoding algorithms, which are designed for sequential token prediction, ineffective at preserving the true output distribution. To address this limitation, we propose DINGO, a dynamic programming-based constrained decoding strategy that is both efficient and provably distribution-preserving. DINGO enables sampling of output strings with the highest probability under the model's predicted distribution, while strictly satisfying any user-specified regular expression. On standard symbolic math and JSON generation benchmarks, DINGO achieves up to a 68 percentage point improvement over unconstrained inference