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.