Research map / Image generation / Fast diffusion sampling
Constrained Discrete Diffusion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Constrained Discrete Diffusion (CDD), a training-free method that projects each discrete diffusion denoising step onto a constraint set via an augmented-Lagrangian KL projection, achieving zero constraint violations on toxicity, molecule, and instruction-following tasks.
Problem
Autoregressive and standard discrete diffusion language models cannot natively guarantee sequence-level constraints (toxicity thresholds, molecular synthetic accessibility or novelty, symbolic lexical/counting constraints), and post-hoc filtering or retraining is costly or unreliable.
Approach
At each reverse diffusion step, project the denoiser's token-probability distribution onto the feasible set by minimizing KL divergence subject to constraints, solved with a Gumbel-softmax relaxation and an augmented Lagrangian method; a best-first traversal handles novelty constraints. The method needs no retraining.
Key results
- On toxicity mitigation, CDD achieves perfect constraint satisfaction at all thresholds (tau=0.25, 0.50, 0.75) while keeping perplexity comparable to MDLM and baselines.
- On novelty-constrained molecule generation, CBG-guided CDD yields a 203.4% increase in novel molecules with QED guidance.
- On counting and lexical instruction-following constraints, CDD reaches 0.0% violation, versus 54.5% (MDLM counting) and 97.5% (MDLM lexical).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply CDD projection during diffusion sampling | MDLM · Counting constraints | Viol (%): 54.5 -> 0.0 | Helped |
| Apply CDD projection during diffusion sampling | MDLM · Lexical constraints | Viol (%): 97.5 -> 0.0 | Helped |
| Apply CDD projection during diffusion sampling | MDLM · Lexical constraints | LLM-Judge: 34.8 -> 65.1 | Helped |
| Apply CDD projection during diffusion sampling | MDLM · Counting constraints | PPL: 16.9 ± 1.0 -> 17.9 ± 1.1 | Hurt |
| Apply CDD projection during diffusion sampling | MDLM · Toxicity mitigation | Violation rate: 0% | Helped |
| Apply novelty projection without QED guidance | UDLM · Molecule generation | Novel molecule generation: 48.1% more novel molecules | Helped |
| Apply novelty projection with CFG QED guidance | UDLM · Molecule generation | Novel molecule generation: 161.4% increase | Helped |
| Apply novelty projection with CBG QED guidance | UDLM · Molecule generation | Novel molecule generation: 203.4% increase | Helped |
| Use instruction-tuned GPT-2 instead of zero-shot GPT-2 | GPT-2 · Counting constraints | Viol (%): 100 -> 5.0 | Helped |
| Use instruction-tuned Llama 3.2 instead of zero-shot Llama 3.2 | Llama 3.2 · Counting constraints | Viol (%): 100 -> 9.1 | Helped |
Surprising findings
- CDD's coherence as judged by the LLM judge increases under toxicity constraints, unlike the baselines whose coherence degrades.
Limitations
- Discrete diffusion base models are small (about 169M parameters) and fall short of large-scale LLMs.
- Constraint imposition adds computational overhead that reduces the parallelism speed-up of diffusion.
- The convergence theorem assumes prox-regularity and a bounded score norm; the empirical guarantees rely on the Lagrangian relaxation converging in tested cases.
Experimental setup
Datasets: RealToxicityPrompts Jigsaw Toxic Comment Classification Challenge QM9 COLLIE
Benchmarks: RealToxicityPrompts QM9 COLLIE
Metrics: toxicity violation rate perplexity LLM-judge coherence QED novelty constraint violation rate entropy
Baselines: GPT-2 Llama 3.2 MDLM UDLM PPLM FUDGE CBG CFG
Builds on: MDLM UDLM augmented Lagrangian method Gumbel-softmax FUDGE
Closest papers by meaning
- Primal-Dual Guided Decoding for Constrained Discrete Diffusion (NeurIPS 2026 · similarity 0.92)
- Fast Sampling via Discrete Non-Markov Diffusion Models with Predetermined Transition Time (NeurIPS 2024 · similarity 0.91)
- Non-Markovian Discrete Diffusion with Causal Language Models (NeurIPS 2025 · similarity 0.90)
- Search-Augmented Masked Diffusion Models for Constrained Generation (NeurIPS 2026 · similarity 0.90)
- Think while You Generate: Discrete Diffusion with Planned Denoising (ICLR 2025 · similarity 0.89)
- The Diffusion Duality (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.