Primal-Dual Guided Decoding for Constrained Discrete Diffusion

A new inference-time method, primal-dual guided decoding, enables discrete diffusion models to enforce global property constraints during token unmasking without retraining. The approach formulates constrained generation as a KL-regularized optimization problem, solved online via adaptive Lagrangian multipliers. At each denoising step, token logits are modified by an additive constraint-dependent bias, with multipliers updated through mirror descent based on constraint violation. The bias represents the optimal KL-regularized projection of the constraint, keeping the constrained distribution as close as possible to the unconstrained model while satisfying constraints. The method supports multiple simultaneous constraints, requires no additional model evaluations beyond standard sampling, and provides formal bounds on constraint satisfaction. This addresses a key challenge in generating structured sequences with global properties.