# Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 23 of its 33 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Placed in

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

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

- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Shortcut Learning in Deep Neural Networks](https://mlsanity.com/paper/2004.07780/) (2020)
- [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)
- [Annotation Artifacts in Natural Language Inference Data](https://mlsanity.com/paper/1803.02324/) (2018)
- [Dream 7B: Diffusion Large Language Models](https://mlsanity.com/paper/2508.15487/) (2025)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)
- [NATURAL PLAN: Benchmarking LLMs on Natural Language Planning](https://mlsanity.com/paper/2406.04520/) (2024)
- [SatLM: Satisfiability-Aided Language Models Using Declarative Prompting](https://mlsanity.com/paper/2305.09656/) (2023)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Generative Recursive Reasoning](https://mlsanity.com/paper/2605.19376/) (2026)
- [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)
- [Breaking the Factorization Barrier in Diffusion Language Models](https://mlsanity.com/paper/2603.00045/) (2026)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)
- [Primal-Dual Guided Decoding for Constrained Discrete Diffusion](https://mlsanity.com/paper/2605.09749/) (2026)
- [Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata](https://mlsanity.com/paper/2607.07026/) (2026)
- [Search or Accelerate: Confidence-Switched Position Beam Search for Diffusion Language Models](https://mlsanity.com/paper/2602.10953/) (2026)
- [Guided Discrete Diffusion for Constraint Satisfaction Problems](https://mlsanity.com/paper/2512.14765/) (2025)
- [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)

## Abstract (arXiv)

Diffusion language models (dLLMs) predict masked positions in arbitrary order, but their exact constrained decoders still encode constraints as sequential languages, whose state must track every unresolved dependency between positions. For relational constraints this encoding grows exponentially: for same-order copy, every finite automaton needs 4k states, deterministic or nondeterministic, and every context-free grammar has size 2Omega(k), while the factor graph of the same relation has size O(k) and a 16-entry peak table. We introduce FactorDLM, a training-free decoder that represents finite-domain relations as a factor graph and, at each denoising step, conditions the model's mean-field prediction on that graph exactly by variable elimination. Decoding cost then grows exponentially with the induced width of the constraint graph, which replaces automaton size as the governing parameter. Because a finite automaton is a chain-shaped factor graph, one compiler enforces syntax and nonlocal relations together: on JSON records with cross-field references, a schema automaton alone leaves references dangling, relational factors alone produce malformed JSON, and the combined plan is valid on both counts, including on records of variable length. Across nine relational benchmarks and three backbones, every output satisfies every declared constraint at 0.4-6.9% projection overhead, where unconstrained decoding is 0-79% valid, and compiled projection answers repeated queries 13.6x faster than CP-SAT with eight parallel workers. Because model-free rules solve three of five standard benchmarks, we construct benchmarks with exact chance and fixed-template floors, on which selecting among exact constrained samples beats greedy projection. Which encoding is cheaper, sequential state or direct factors, depends on the constraint and is computable before decoding begins.