Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
While existing constrained decoders for masked diffusion language models achieve step-exact sampling via automaton-constrained dynamic programming, this work proves that sequential composition introduces severe trajectory bias away from the true conditional distribution. To eliminate this distortion, the authors develop an exact analytical formulation of trajectory tilt and derive TWISTER, an automaton-twisted Sequential Monte Carlo decoding framework. For regular language constraints, TWISTER efficiently calculates exact Feynman-Kac potential updates from pre-computed DP tables, provably targeting the unbiased Doob $h$-transformed path law.
Step-exact constrained decoding in masked diffusion models quietly tilts the global trajectory distribution away from valid path laws—a distortion that twisted Sequential Monte Carlo can completely eliminate without extra dynamic programming overhead.
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.