acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 per-step 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

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Masked Diffusion Language Models, Constrained Decoding, Sequential Monte Carlo, Finite-State Automata, Feynman–Kac Models, Structured Generation, Probabilistic Inference

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_fU5VOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3(+1)
Soundness
2
Read review
Paper summary

This paper studies the problem of constrained decoding in MDLMs. The main finding reported in the paper is that a trajectory bias can be observed in prior approaches that restrict the model's per-sample mean field posterior. The authors show that this bias stems from the fact that the denoising process retains only a subset of the sampled tokens at each step. The authors provide a comprehensive analysis of the discrepancy between the constraint-valid completions scored under the previous vs. current states. To correct this discrepancy the authors propose TWISTER, an automation-twisted SMC decoder. They experimentally show that TWISTER computes the Fynman-Kac correction to eliminate the trajectory bias.

Critical strengths
  • The paper provides a rigorous mathematical formalization of the trajectory bias in step-exact MDLM decoding. By formulating the unbiased target distribution as the Doob h-transform of the native path law conditioned on constraint satisfaction, the authors successfully pinpoint the exact source of the bias. The theoretical derivation of the "re-freezing tilt" is elegant and advances the fundamental understanding of diffusion language model decoding.
  • The proposed TWISTER algorithm is theoretically sound and practically clever because it does not require arbitrary approximations.
  • The experiments effectively validate the theoretical claims. As demonstrated in Figure 1 across multiple architectures (OWT-130M, DREAMCODER-7B-INST, DREAM-7B-BASE), TWISTER significantly reduces the Total Variation Distance (TVD) from the true Doob h-transformed native path law compared to the baseline approach by Dang & Ermon.
Critical weaknesses
  • While the paper conclusively proves that TWISTER minimizes trajectory bias measured by TVD on synthetic token-class constraints, it entirely omits evaluation on practical downstream tasks. There is no empirical evidence showing whether eliminating this theoretical bias actually improves the quality, perplexity, or accuracy of the generated text or code.
  • The methodology is strictly constrained to deterministic finite automata (DFA) and regular languages. Consequently, TWISTER cannot natively enforce context-free grammars (CFGs), which are often required for deeply nested coding structures, complex JSON arrays, or mathematical formulas.
Questions for authors
  • How does eliminating trajectory bias impact downstream generation quality?
  • What specific optimizations could mitigate the computational overhead of TWISTER?
  • Can the TWISTER framework be extended to Context-Free Grammars (CFGs)?
Reviewer_BEMYOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors seek to perform constrained generation with diffusion language models. They show the recent approach of Deng & Ermon 2026 is biased, and they fix it with SMC. Thorough proofs and experiments demonstrate the effectiveness of their method.

Critical strengths
  1. The authors identify a key area of interest: constrained decoding for diffusion language models
  2. The authors point out a real weakness of prior method and propose a principled fix to it
  3. The mathematical communication is very clear
Critical weaknesses
  1. The authors should better highlight their experimental results in the main body of the paper
Questions for authors
  1. Can the authors move some of the experimental results to the main body of the paper? Also, can the authors please elaborate further on practical examples of "constrained" decoding in diffusion languages models in the intro?
Reviewer_ZsGfOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies constrained decoding (as well as exact sampling from the conditional posterior) for masked diffusion language models. The authors characterize the previous approach and introduce TWISTER, an automaton-twisted SMC decoder with exactly computable incremental correction weights. Experiments demonstrate reduced distributional discrepancy and evaluate constraint validity and runtime on JSON generation.

Critical strengths
  • Clear theoretical contribution. The paper distinguishes per-step constrained sampling from globally conditioned generation. Its characterization of trajectory bias explains why local exactness is insufficient, even when every generated output satisfies the constraint.

  • Principled correction mechanism. The authors derive the bias caused by reconditioning the denoiser and construct correction weights that recover the desired Feynman–Kac target.

  • Tractable use of automaton computations. The correction exploits partition sums available through the existing automaton-based inference procedure. This provides a concrete algorithmic application of the analysis, and the distributional experiments support its intended effect.

Critical weaknesses
  • Insufficient evidence of practical benefit. The main empirical improvement is greater fidelity to the native model’s distribution conditioned on constraint satisfaction. While mathematically meaningful, this does not necessarily translate into practical gain. The JSON experiment primarily measures parse and schema validity, which the existing constrained decoders already achieve at comparable rates. The paper does not establish whether correcting trajectory bias improves semantic task success or useful diversity. This is my main concern.

  • The additional computation is not adequately justified. TWISTER introduces multiple particles and additional inference overhead, but the evaluation does not demonstrate a corresponding improvement in downstream utility. For example, on Dream-7B-Base, the reported average runtime increases from approximately 22 seconds for the step-exact baseline to 42 seconds for TWISTER with four particles, while validity remains unchanged. Given that the practical premise of masked diffusion is speed, this could remain a concern.

Questions for authors

see the weakness section.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.