Primal-Dual Guided Decoding for Constrained Discrete Diffusion

Discrete diffusion models generate structured sequences by progressively unmasking tokens, but enforcing global property constraints during generation remains an open challenge. We propose primal-dual guided decoding, an inference-time method that formulates constrained generation as a KL-regularised optimisation problem and solves it online via adaptive Lagrangian multipliers. At each denoising step, the method adds a constraint-dependent bias to token logits, with multipliers updated by mirror descent based on constraint violation. The approach requires no retraining, introduces no additional model evaluations, supports multiple simultaneous constraints, and provides formal bounds on constraint violation. Because the bias is additive on logits, it preserves the model's learned distribution while steering outputs toward desired properties, yielding a favourable trade-off between constraint satisfaction and distributional fidelity. We demonstrate the method on topical text generation, molecular design, and music playlist generation, showing that a single algorithm instantiated via domain-specific scoring functions achieves high constraint satisfaction while maintaining diversity and validity, without additional training or inference cost.