Research map / Image generation / Fast diffusion sampling

Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata

NeurIPS 2026 · Image generation › Fast diffusion sampling · approach: Masked diffusion language model decoding · 0 citations (OpenAlex)

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.

Exact, constraint-satisfying sampler for diffusion LLMs that treats a finite automaton as a chain graphical model and uses a log-depth tree sampler to decode under the constrained mean-field posterior.

Problem

Constrained decoding assumes left-to-right generation; diffusion LLMs sample all positions in parallel from a fully factorized distribution, so per-position masking cannot enforce global structural constraints such as JSON schemas or SQL grammar.

Approach

Sample at every denoising step from the mean-field prediction reweighted by a finite automaton, computed exactly via forward-backward over the automaton viewed as a chain graphical model, and reduce sampling depth from O(L) to O(log L) by a divide-and-conquer tree decomposition over prefix-suffix state pairs.

Key results

• On BFCL-Live (JSON), Dream-7B greedy accuracy rises from 63.9% to 71.5% with constrained decoding.
• Under stochastic sampling, Dream-7B BFCL-Live (JSON) accuracy goes from 22.3% baseline to 69.0% with the method.
• The tree (log-depth) sampler adds about 4% wall-clock overhead on BFCL versus unconstrained decoding, while the chain variant adds 114%.

Surprising findings

• Unconstrained dLLM accuracy collapses under stochastic sampling, largely because constraint violations increase, and constrained decoding recovers near-greedy accuracy.
• Recomputing remasking confidence from the constrained marginals outperforms using the base mean-field confidence, especially when the baseline performs poorly.

Limitations

• Only covers finite-automaton constraints; richer context-free grammars are not supported.
• Sudoku DFA does not enforce row, column, or box constraints due to exponential DFA size.
• Spider requires NFAs with about 10k states and 100k edges, indicating scaling cost for large schemas.

Experimental setup

Datasets: xlam-function-calling-60k BFCL Sudoku Countdown GSM-Symbolic Spider

Benchmarks: xLAM BFCL Sudoku Countdown GSM-Symbolic Spider

Metrics: exact match execution accuracy constraint satisfaction rate latency throughput

Baselines: Unconstrained Dream-7B Unconstrained LLaDA-8B DINGO Llama-3.1-8B Qwen3-8B

Builds on: DINGO Outlines LLaDA Dream

Closest papers by meaning

• DINGO: Constrained Inference for Diffusion LLMs (NeurIPS 2025 · similarity 0.92)
• Primal-Dual Guided Decoding for Constrained Discrete Diffusion (NeurIPS 2026 · similarity 0.91)
• SimSD: Simple Speculative Decoding in Diffusion Language Models (NeurIPS 2026 · similarity 0.90)
• Confidence-Based Decoding is Provably Efficient for Diffusion Language Models (NeurIPS 2026 · similarity 0.90)
• Dynamically Structured Diffusion Language Model Decoding via Bayesian Inference (NeurIPS 2026 · similarity 0.90)
• Free Draft-and-Verification: Toward Lossless Parallel Decoding for Diffusion Large Language Models (NeurIPS 2026 · similarity 0.90)