Primal-Dual Guided Decoding for Constrained Discrete Diffusion

• URL: http://arxiv.org/abs/2605.09749v1
• Date: Sun, 10 May 2026 20:55:19 GMT
• Title: Primal-Dual Guided Decoding for Constrained Discrete Diffusion
• Abstract summary: We propose primal-dual guided decoding, an inference-time method that formulates constrained generation as a KL-regularised optimisation problem.<n>At each denoising step, the method modifies token logits through an additive, constraint-dependent bias, with multipliers updated by mirror descent based on constraint violation.<n>We evaluate our approach on topical text generation, molecular design, and music playlist generation, showing that a single algorithm instantiated via domain-specific scoring functions improves constraint satisfaction while preserving relevant domain-specific quality metrics.
• Score: 5.219025684249083
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 modifies token logits through an additive, constraint-dependent bias, with multipliers updated by mirror descent based on constraint violation. The bias arises as the optimal KL-regularised projection of the constraint, so the constrained distribution remains as close as possible to the model's unconstrained distribution while still satisfying the constraint. The method requires no retraining and no additional model evaluations beyond standard sampling, supports multiple simultaneous constraints, and provides formal bounds on constraint violation. We evaluate our approach on topical text generation, molecular design, and music playlist generation, showing that a single algorithm instantiated via domain-specific scoring functions improves constraint satisfaction while preserving relevant domain-specific quality metrics.

Related papers

• Constrained Code Generation with Discrete Diffusion [40.46661913038948]
  Constrained Diffusion for Code (CDC) is a training-free neurosymbolic inference framework for code generation.<n>CDC integrates constraint satisfaction directly into the reverse denoising process.<n>CDC consistently improves constraint satisfaction in functional correctness, security, and even syntax.
  arXiv  Detail & Related papers  (2026-05-16T06:15:47Z)
• Randomized multi-class classification under system constraints: a unified approach via post-processing [8.354034992258482]
  We study the problem of multi-class classification under system-level constraints expressible as linear functionals over randomized classifiers.<n>We propose a post-processing approach that adjusts a given base classifier to satisfy general constraints without retraining.
  arXiv  Detail & Related papers  (2025-12-16T09:53:22Z)
• Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning [52.03884701766989]
  offline reinforcement learning (RL) algorithms typically impose constraints on action selection.<n>We propose a new neighborhood constraint that restricts action selection in the Bellman target to the union of neighborhoods of dataset actions.<n>We develop a simple yet effective algorithm, Adaptive Neighborhood-constrained Q learning (ANQ), to perform Q learning with target actions satisfying this constraint.
  arXiv  Detail & Related papers  (2025-11-04T13:42:05Z)
• Constraint-Guided Prediction Refinement via Deterministic Diffusion Trajectories [7.279433512595361]
  We propose a general-purpose framework for constraint-aware guided denoising diffusion diffusionDDIMs.<n>Our method iteratively refines it through a diffusion trajectory by a learned prior and augmented by constraint corrections.
  arXiv  Detail & Related papers  (2025-06-15T17:02:07Z)
• Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees [34.164821598251315]
  In sparse optimization, enforcing hard constraints using the $ell_$ pseudo-norm offers advantages like controlled sparsity.<n>Many real-world applications demand not only sparsity constraints but also some extra constraints.<n>We present a new variant of hard-preserving iterative algorithm equipped with a two-step projection operator customized for these mixed constraints.
  arXiv  Detail & Related papers  (2025-06-10T08:27:01Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Constrained Discrete Diffusion [61.81569616239755]
  This paper introduces Constrained Discrete Diffusion (CDD), a novel integration of differentiable constraint optimization within the diffusion process.<n>CDD directly imposes constraints into the discrete diffusion sampling process, resulting in a training-free and effective approach.
  arXiv  Detail & Related papers  (2025-03-12T19:48:12Z)
• An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition [0.0]
  In this paper, we aim to investigate the sparse low-rank characteristics rectified on non-negative matrices.<n>We propose a novel regularization term incorporating useful structures in clustering and compression tasks.<n>We derive corresponding closed-form solutions while maintaining the $L$-smooth property always holds for any $Lge 1$.
  arXiv  Detail & Related papers  (2025-03-04T08:20:34Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  We study the Constrained Convex Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure. Design algorithms for a constrained convex MDP faces several challenges, including handling the large state space.
  arXiv  Detail & Related papers  (2024-02-16T16:35:18Z)
• On Regularization and Inference with Label Constraints [62.60903248392479]
  We compare two strategies for encoding label constraints in a machine learning pipeline, regularization with constraints and constrained inference. For regularization, we show that it narrows the generalization gap by precluding models that are inconsistent with the constraints. For constrained inference, we show that it reduces the population risk by correcting a model's violation, and hence turns the violation into an advantage.
  arXiv  Detail & Related papers  (2023-07-08T03:39:22Z)
• A Variational Inference Approach to Inverse Problems with Gamma Hyperpriors [60.489902135153415]
  This paper introduces a variational iterative alternating scheme for hierarchical inverse problems with gamma hyperpriors. The proposed variational inference approach yields accurate reconstruction, provides meaningful uncertainty quantification, and is easy to implement.
  arXiv  Detail & Related papers  (2021-11-26T06:33:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.