analiza aiqbench
This research introduces TWISTER, a novel decoder for Masked Diffusion Language Models that eliminates trajectory bias inherent in existing constrained sampling methods. By applying an automaton-twisted Sequential Monte Carlo approach, the method ensures generated outputs satisfy structural constraints while strictly preserving the model's original probability distribution over valid paths. This advancement is critical for deploying diffusion-based language models in applications requiring high-fidelity adherence to complex syntax or logic without distorting the underlying generative dynamics.
Twist, Don't Tilt: Trajectory-Exact Constrained Decoding for Masked Diffusion Models
arXiv:2609.35609v1 Announce Type: new 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 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.
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 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.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computation and Language (cs.CL)
arXiv:2609.35609 [cs.LG]
(or arXiv:2609.35609v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.35609 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 297 cuvinte
Subiecte conexe
Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models
arXiv · 29 sept. 2026
Trajectory-Level Speculative Decoding for Diffusion Language Models
arXiv · 1 sept. 2026
Masked Diffusion Language Agents for Tool-Integrated Chemical Reasoning
arXiv · 12 oct. 2026
DPRM: A Plug-in Doob h transform-induced Token-Ordering Module for Discrete Diffusion Models
arXiv · 25 aug. 2026