Research map / Large language models / Language, safety and interpretability
DINGO: Constrained Inference for Diffusion LLMs
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.
Proposes DINGO, a dynamic-programming constrained decoder for diffusion LLMs that enforces user regular expressions while maximizing block sequence probability under the model's distribution.
Problem
Diffusion LLMs unmask tokens in parallel, so existing autoregressive constrained decoding cannot guarantee regex/schema-valid outputs or preserve the true output distribution.
Approach
Build a token-level DFA with a mask-aware transition function (masked positions map to sets of states, NFA-like), then run a dynamic program over block positions that tracks the maximum-probability path to each DFA state and selects the most probable string ending in a live state.
Key results
- On GSM-Symbolic, DINGO reaches 32% accuracy with 100% parse rate for LLaDA-8B-I versus 19% unconstrained and 27% greedy constrained.
- On JSON-Mode-Eval, DINGO achieves 100% accuracy and parse rate across all four diffusion models, e.g. Dream-B-7B from 15% unconstrained to 100%.
- DINGO adds marginal runtime overhead (e.g. 23.92s vs 23.78s unconstrained for LLaDA-8B-I on GSM-Symbolic).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DINGO instead of Best of Greedy + Unconstrained | LLaDA-8B-Base · GSM-Symbolic | accuracy: 30 -> 31 | Helped |
| Use DINGO instead of Best of Greedy + Unconstrained | LLaDA-8B-Instruct · GSM-Symbolic | accuracy: 27 -> 32 | Helped |
| Use DINGO instead of Best of Greedy + Unconstrained | Dream-v0-Base-7B · GSM-Symbolic | accuracy: 21 -> 23 | Helped |
| Use DINGO instead of Best of Greedy + Unconstrained | Dream-v0-Instruct-7B · GSM-Symbolic | accuracy: 34 -> 36 | Helped |
| Use DINGO instead of Best of Greedy + Unconstrained | LLaDA-8B-Base · JSON-Mode-Eval | accuracy: 88 -> 100 | Helped |
| Use DINGO instead of Best of Greedy + Unconstrained | LLaDA-8B-Instruct · JSON-Mode-Eval | accuracy: 99 -> 100 | Helped |
| Use DINGO instead of Best of Greedy + Unconstrained | Dream-v0-Base-7B · JSON-Mode-Eval | accuracy: 32 -> 100 | Helped |
| Use DINGO instead of Best of Greedy + Unconstrained | Dream-v0-Instruct-7B · JSON-Mode-Eval | accuracy: 91 -> 100 | Helped |
| Use DINGO instead of Best of Greedy + Unconstrained | all evaluated models · GSM-Symbolic | parse rate: 75 -> 100; 98 -> 100; 41 -> 100; 93 -> 100 | Helped |
| Use DINGO instead of Best of Greedy + Unconstrained | all evaluated models · JSON-Mode-Eval | parse rate: 90 -> 100; 99 -> 100; 35 -> 100; 93 -> 100 | Helped |
| Vary the number of diffusion blocks from 1 to 2 to 8 (ablation) | DINGO with LLaDA-8B-Instruct · GSM-Symbolic | accuracy: 29; 32; 32 | Mixed |
Surprising findings
- Greedy constrained decoding sometimes underperforms unconstrained generation (e.g. LLaDA-8B-I JSON: 78% vs 87%), showing greedy masking can distort the distribution.
Limitations
- Optimality holds only per block; may not hold in semi-autoregressive multi-block setups.
- Limited to regular language constraints; cannot enforce context-free constraints such as programming language syntax.
- Experiments are on only two benchmarks and four diffusion models with greedy decoding and no error bars.
Experimental setup
Datasets: GSM-Symbolic JSON-Mode-Eval
Benchmarks: GSM-Symbolic JSON-Mode-Eval
Metrics: accuracy parse rate time per completion
Baselines: Unconstrained Greedy Constrained Best of Greedy + Unconstrained
Builds on: LLaDA Dream-7B CRANE greedy constrained decoding
Closest papers by meaning
- Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata (NeurIPS 2026 · similarity 0.92)
- Primal-Dual Guided Decoding for Constrained Discrete Diffusion (NeurIPS 2026 · similarity 0.89)
- Accelerating Diffusion LLMs via Adaptive Parallel Decoding (NeurIPS 2025 · similarity 0.89)
- Lookahead Path Likelihood Optimization for Diffusion LLMs (ICML 2026 · similarity 0.89)
- SimSD: Simple Speculative Decoding in Diffusion Language Models (NeurIPS 2026 · similarity 0.89)
- Fast and Fluent Diffusion Language Models via Convolutional Decoding and Rejective Fine-tuning (NeurIPS 2025 · similarity 0.88)
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.