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.
Figures & tables
Figure 1: Trajectory bias in constrained decoding of MDLMs captured by the Total Variation Distance (TVD) between the Doob h -transformed native path law (rejection sampling) and the step-exact automaton-constrained distribution ( Dang and Ermon (2026) , \textscTwistersmc4 and \textscTwistersmc8 ) across denoising steps. For "a.*".
Figure 2: A three-token example of trajectory bias. Let V={a,b} , C=a∗b+ , T=2 , and x0=(⊥,⊥,b) , with position 2 revealed before position 1 . Revealing a gives x1a=(⊥,a,b) , with aab as its only valid completion under C , while revealing b gives x1b=(⊥,b,b) , whose completions are both valid. Assuming uniform categoricals at x0 ( 1 ), Z(x1a;x0)=0.5 ( 2 ) and Z(x1b;x0)=1 , so the step-exact decoder chooses x1a with probability 0.5/(0.5+1)=1/3 . After committing x1a , the denoiser rescores position 1 as Cat1(a∣x1a)=0.9 ( 3 ), so x1a ’s actual valid mass is Z(x1a;x1a)=0.9 ; which is what the Doob path law uses to choose x1a , h1(x1a)=0.9 , i.e., with probability 0.9/(0.9+1)=9/19 . But step-exact decoding only renormalizes by Z(x1a;x1a) in the next step, thus never correcting Z(x1a;x0) . Since aab is the only valid completion of x1a , p_{1:2}^{\scalebox{0.56}{\,\bm{\mathcal{A}}}}((\textbf{x}_{1}^{a},aab)\mid\textbf{x}_{0};\mathcal{C})\!=\!1/3 but p_{1:2}^{\scalebox{0.6}{\bigstar}}((\textbf{x}_{1}^{a},aab)\mid\textbf{x}_{0};\mathcal{C})\!=\!9/19 , due to the per-step mismatch Z(x1a;x0)/Z(x1a;x1a)=5/9 in Eq. ( 14 ).
Algorithm 1 Twister for step-exact decoding (adaptive resampling shown in Appendix E ).
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Algorithm 2 Twister for step-exact decoding (with adaptive resampling).
Figure 3: Swarm plot of token-prefix DFA state counts on JSON-Mode-Eval. Each point is one datapoint; the diamond marks the mean.
Figure 4: Example JSON-Mode-Eval prompt messages (datapoint json-0 ). The final user-turn line is our appended instruction to emit only the JSON object.
Model
Method
Parse Valid (%)
Schema Valid (%)
Time (s)
Dream-7B-Base
DINGO †
100
98
22±43
Dang and Ermon †
100
98
22±43
\textscTwistersmc1
100
98
32±65
\textscTwistersmc4
100
98
42±86
Dream-7B-Inst
DINGO †
100
99
21±45
Dang and Ermon †
100
99
21±46
Appendix
Table 1: Constraint satisfaction on JSON-Mode-Eval for all decoding methods. The Parse Valid (%) and Schema Valid (%) columns measure whether outputs are valid JSON and satisfy the schema set by the datapoint; Time (s) measures the average time taken to generate the output.
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.
Masked Diffusion Language Models (MDLMs) have emerged as a distinct paradigm for sequence generation. As MDLMs become diverse in capabilities and knowledge coverage, an important question is how to combine their knowledge. Toward this, we first investigate the unique decoding dynamics of MDLMs. We find that successful generations exhibit stable confidence dynamics over answer-relevant positions, while unreliable trajectories can often be corrected by injecting promising intermediate states from other models. Guided by this observation, we propose TIE (Trajectory-based Iterative Ensembling), a knowledge fusion framework in which MDLMs iteratively identify reliable decoding trajectories and relay them across models. TIE tracks confidence dynamics over answer-relevant positions to determine which model currently follows a more reliable trajectory and selectively transfers partially denoised sequences across models. As the model on the more promising trajectory often changes across denoising steps, TIE allows different models to contribute complementary strengths at different stages of generation. Strong performance across diverse reasoning tasks, along with our analyses, suggests that TIE offers a practical approach to the underexplored problem of MDLM ensembling.
Chain-of-thought reasoning helps autoregressive models solve complex problems by generating intermediate steps that support later predictions. Masked diffusion models (MDMs) offer a similar opportunity through arbitrary-order generation: they can ideally reveal intermediate results along logical dependencies. In practice, however, standard decoding simply prioritizes high-confidence tokens, which need not align with this dependency order. We identify this discrepancy as the \emph{confidence shortcut}: models commit with high certainty to plausible tokens while neglecting long-range dependencies. In multi-digit addition, models predict higher-order digits without properly tracking carries through long chains. Controlled pretraining across diverse reasoning tasks confirms that confidence-guided ordering often selects suboptimal sequences, and confidence-aligned training schemes can exacerbate these failures---for example, increasing addition error rates by an order of magnitude. Our findings caution against relying solely on confidence to choose generation orders and against training objectives that reinforce this preference. The experimental code is available at https://github.com/jinha2536/mdm-arithmetic.
Dueun Kim, Albert No
Department of Artificial Intelligence, Yonsei University