How Good Are Masked Discrete Diffusion Models at Constrained Sampling?

We study constrained sampling with masked discrete diffusion models in combinatorial domains with sparse constraint dependency graphs. Adopting the masking policy of partial rejection sampling (PRS), we extend its classical repair guarantees from fixed product distributions of independent variables to an adaptive repair process driven by the conditional distributions of masked diffusion. We obtain Lov\'asz local lemma–like conditions under which masked diffusion efficiently reaches a feasible assignment. Under the symmetric conditions, the expected number of repair rounds is at most logarithmic in the number of constraints, and the expected total number of constraints selected across rounds is at most linear, matching the classical PRS bounds for product distributions. We also give conditions for tractable exact sampling from the data distribution conditioned on feasibility. We test the distributional fidelity of the model for hypergraph coloring, uniform SAT, and rooted spanning trees, and show strong empirical results against state of the art diffusion solvers on 3-SAT.