mlsanityData to 7 Oct 2026

Twist, Don't Tilt: Trajectory-Exact Constrained Decoding for Masked Diffusion Models

arXiv 2609.35609 ↗First posted 28 Sep 2026cs.LG cs.AI cs.CLcited by 0

On the map: Diffusion models → Discrete and text diffusion

Abstract (arXiv)

Constrained decoding for Masked Diffusion Language Models (MDLMs) aims to ensure that generated outputs satisfy a specified structure or syntax constraint. MDLMs generate outputs by repeatedly unmasking masked positions present in their current state. Recent strategies for constrained decoding constrain the model's per-step mean-field posterior (which factorizes over masked positions) by enforcing the desired constraint with an automaton. The resulting chain-structured factor graph allows exact constrained sampling via dynamic programming. However, despite each draw being exact and constraint-satisfying, we prove that their composition, in general, tilts away from the model's relative probabilities over valid trajectories, thus leading to trajectory bias. We derive an exact expression for this bias as a product of ratios measuring how valid continuation mass changes when the denoiser is reconditioned, and characterize when the bias vanishes. We then correct the bias by introducing TWISTER, the first automaton-twisted Sequential Monte Carlo decoder for MDLMs, using the step-exact decoder as the proposal. We show that for regular language constraints, the Feynman-Kac correction is exactly computable, with the twists obtained efficiently using quantities pre-computed for step-exact sampling. We prove that the resulting Feynman-Kac model targets the unbiased Doob h-transformed path law conditioned on constraint satisfaction.

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

Builds on

19 of 28 references.

Closest ancestors · 7

Same direction, newest first

  1. 2026Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata8 Jul
  2. 2026Self-Rewarding Sequential Monte Carlo for Masked Diffusion Language Models2 Feb
  3. 2025Dream-Coder 7B: An Open Diffusion Language Model for Code1 Sep
  4. 2025Dream 7B: Diffusion Large Language Models21 Aug
  5. 2025Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking30 May
  6. 2025Large Language Diffusion Models14 Feb
  7. 2024Simple and Effective Masked Diffusion Language Models11 Jun

Other references · 12

  1. 2025Fast-dLLM: Training-free Acceleration of Diffusion LLM by Enabling KV Cache and Parallel Decodingcited by 404
  2. 2023Efficient Guided Generation for Large Language Modelscited by 192
  3. 2023Grammar-Constrained Decoding for Structured NLP Tasks without Finetuningcited by 186
  4. 2024Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generationcited by 99
  5. 2024XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Modelscited by 73
  6. 2024SynCode: LLM Generation with Grammar Augmentationcited by 66
  7. 2024Grammar-Aligned Decodingcited by 54
  8. 2024Automata-based constraints for language model decodingcited by 49
  9. 2025Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlocited by 45
  10. 2025DINGO: Constrained Inference for Diffusion LLMscited by 15
  11. 2026Discrete Feynman-Kac Correctorscited by 9
  12. 2026Mitigating Bias in Locally Constrained Decoding via Tractable Proposalscited by 8

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models
  2. 2026On Trajectory-Aware Training for Masked Diffusion Language Models
  3. 2026Who Should Lead Decoding Now? Tracking Reliable Trajectories for Ensembling Masked Diffusion Language Models
  4. 2025Beyond Static Cutoffs: One-Shot Dynamic Thresholding for Diffusion Language Models
  5. 2026Continuous Diffusion Models Can Obey Formal Syntax
  6. 2025Activation Steering for Masked Diffusion Language Models
  7. 2026Not All Denoising Steps Are Equal: Model Scheduling for Faster Masked Diffusion Language Models
  8. 2026CoDR: Training-Free Confidence-Drift Remasking for Diffusion Language Models