Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models

Jianchang Su; Wei Zhang

cs.AISep 26, 2026

Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models

Authors: Jianchang Su, Wei Zhang

Organizations: University of Connecticut

Abstract

Diffusion language models (dLLMs) predict masked positions in arbitrary order, but their exact constrained decoders still encode constraints as sequential languages, whose state must track every unresolved dependency between positions. For relational constraints this encoding grows exponentially: for same-order copy, every finite automaton needs $4^k$ states, deterministic or nondeterministic, and every context-free grammar has size $2^{Ω(k)}$ , while the factor graph of the same relation has size $O(k)$ and a 16-entry peak table. We introduce FactorDLM, a training-free decoder that represents finite-domain relations as a factor graph and, at each denoising step, conditions the model's mean-field prediction on that graph exactly by variable elimination. Decoding cost then grows exponentially with the induced width of the constraint graph, which replaces automaton size as the governing parameter. Because a finite automaton is a chain-shaped factor graph, one compiler enforces syntax and nonlocal relations together: on JSON records with cross-field references, a schema automaton alone leaves references dangling, relational factors alone produce malformed JSON, and the combined plan is valid on both counts, including on records of variable length. Across nine relational benchmarks and three backbones, every output satisfies every declared constraint at 0.4-6.9% projection overhead, where unconstrained decoding is 0-79% valid, and compiled projection answers repeated queries 13.6x faster than CP-SAT with eight parallel workers. Because model-free rules solve three of five standard benchmarks, we construct benchmarks with exact chance and fixed-template floors, on which selecting among exact constrained samples beats greedy projection. Which encoding is cheaper, sequential state or direct factors, depends on the constraint and is computable before decoding begins.

Figures & tables

Panel of Figure 1 — Figure 1: Constraints are graphs, not chains. (a) Prior exact decoders run inference in the chain graphical model of an automaton ( Dang & Ermon, 2026 ) , which needs $4^{k}$ states for the copy relation (Proposition 1 ); (b) its factor graph has width one and 16-entry tables; (c) one denoising step commits the most confident slots of an exactly valid assignment; (d) a schema automaton is a chain-shaped factor graph, so schema and cross-field references compile into one plan (§ 5.1 ).

Panel of Figure 2 — Figure 2: Overview of FactorDLM on the copy relation $x_{i}=x_{i+3}$ (cell colors encode values). The same per-slot scores give an invalid assignment under per-slot argmax and a valid joint proposal under exact elimination over a plan compiled once; the most confident proposed slots are committed and the next step starts from $x^{t-1}$ .

			Dream-7B			LLaDA-8B			LLaDA-1.5
	Task	Metric	Base	Ours	+Sel	Base	Ours	+Sel	Base	Ours	+Sel
PLAN	Meeting (3 people)	norm. objective	42.8	55.8	75.3	62.0	83.5	99.0	65.0	87.7	98.8
PLAN	Trip	exact match	19.9	92.1	82.9	0.0	84.7	72.2	0.0	78.7	72.2
MATH	Countdown ‡	success	0.0	1.4	3.0	0.0	1.0	9.4	0.0	0.8	8.6
JSON	JSON §	instructed record	0.0	0.0	0.0	0.0	41.4	92.0	0.0	43.4	96.4
	Var-JSON §	instructed record	0.0	0.0	0.8	0.0	38.3	41.7	0.0	37.9	35.4

Table 1: Task accuracy (%) with projection ( Ours ) and best-of-8 selection ( +Sel ) against unconstrained decoding ( Base ). Bold: best per cell; dashes: outside the protocol. † Unique completion; the last two rows also admit model-free shortcuts (§ 5.3 ). Floors: ‡ chance 1.0%, template 13.2%; § referential chance 0.09%, template 1.6%. Meeting: the three-person split;

N

-queens: 1,373 of 1,483 boards run, 110 refused before decoding (§ 5.2 ). +Sel decodes

K{+}1

times and scores every rendered token (cost in § 5.4 ).

Figure 3: Solver comparison and the width boundary. (a) Per-query speedup of compiled CUDA projection over CP-SAT with eight workers on the eight fully optimal cells ( $d$ : domain size, $w$ : induced width, $n=16$ unless shown). (b) Exact-MAP latency and the CPU/CUDA crossover. (c) Executed and budget-rejected cells.

Figure 4: Three shortcut classes on the published metrics. (a) Unique completion: uniform potentials tie every model at 100. (b) Canonical targets: a two-line rule hits 309/309 and the

N

-queens target is the lexicographic minimum (405/405); every dLLM method sits below chance. (c) The published uniform-MAP control scores zero by tie-break and is omitted; a random control beats Dream (Table 11 ).

Backbone	People	Greedy	PLL	Judge	Top-8	Oracle	Normalized objective
			Exact-optimum rate
Dream	3	0.120	0.490	0.320	0.920	0.500	$0.558\to 0.753$
Dream	4	0.040	0.290	0.270	0.640	0.400	$0.578\to 0.754$
Dream	5	0.051	0.173	0.143	0.286	0.276	$0.533\to 0.688$
LLaDA	3	0.530	0.970	0.970	0.980	0.970	$0.835\to 0.990$
LLaDA	4	0.410	0.570	0.730	0.450	0.750	$0.711\to 0.852$

Table 2: PLL selection beats greedy projection in all nine cells , significantly in six after Holm correction (exact McNemar). Oracle : best sampled candidate; Top-8 : PLL over the exact top-8.

Appendix figures & tables26 assets

Supplementary material from the paper’s appendix.

Appendix

	Dream-7B	LLaDA-8B	LLaDA-1.5
Method	syntax / references / instructed record
Chance floor (analytic)	0.0009
Best fixed template	0.016
Independent	0.000 / 0.000 / 0.000	0.000 / 0.000 / 0.000	0.000 / 0.000 / 0.000
Automaton only	1.000 / 0.474 / 0.000	1.000 / 0.480 / 0.186	1.000 / 0.516 / 0.224
Relations only	0.000 / 1.000 / 0.000	0.000 / 1.000 / 0.000	0.000 / 1.000 / 0.000

Appendix

Table 4: Referential JSON over 500 instances per backbone: syntax validity, referential validity, and the instructed-record rate. Neither representation alone enforces both axes; the hybrid enforces both on every record. Dream returns valid records that never match the instruction, and its pool oracle is zero, so its failure is in the constrained distribution’s head, which the scorer can only choose from.

Work	Constraint/tasks	Quality evidence	System evidence
DINGO	Regular; GSM-Symbolic, JSON	accuracy, parse and schema validity	wall time, automaton precomputation
CFG	Context-free; C++, JSON, SMILES	syntax, exact match, pass@1	inference and completion behavior
LAVE	Context-free; C++, JSON, SMILES	syntactic@k, functional@k	mean time, lookahead ablations
EPIC	Context-free; C++, JSON, SMILES	syntax and functional correctness	normalized time, breakdown, steps, ablations
Finite automata	Automata; function calls, Sudoku, planning, SQL, math	accuracy and constraint satisfaction; greedy and sample	latency, throughput, automaton size, step sweep
FactorDLM	Factor graphs; Sudoku, coloring, copy, meetings	validity, exact match, task success, agreement, paired inference	latency decomposition, memory, steps, width, CPU/CUDA, failure boundary

Appendix

Table 5: Evaluation-methodology alignment with the closest constrained-dLLM systems. Native tasks differ by representable constraint class. Sudoku supplies the exact shared protocol with finite automata; the official CFG engine supplies the representation probe.

Question	Metric and direction	Denominator / paired unit	Evidence
Direct system quality	complete valid output without repair	900 Sudoku per model–mode cell	Fig. 11
Constraint coverage	validity; higher is better	all 900 Sudoku or all 100 plans	Fig. 6
Model utility	normalized objective; invalid is zero	all 100 planning records	Fig. 6 c
Schedule quality	semantic-score effect; positive favors dispersed	generated groups within 40 subjects	Fig. 13
Workflow selection	execution-success effect	all 124 development records	Fig. 13
Exact-system win	CP-SAT/FactorDLM; above one favors FactorDLM	eight optimal cells, 20 queries each	Fig. 3 a

Appendix

Table 6: Metric ledger. Values across rows answer different questions and are not numerically comparable. Oracle and non-executed cross-paper values are labeled in their figure captions.

Figure 6: Task-quality evidence with metric and denominator separated by panel. Panels (a) and (b) stand: shared-protocol Sudoku validity against the non-executed published automaton result, and planning feasibility. Panel (c)’s uniform bar is a degenerate control : it is zero because deterministic ties decline every meeting, so its margin reflects the tie-break. In panel (c), uniform and model are FactorDLM under uniform and model unaries. The informative comparison for that panel is against the non-degenerate model-free controls in Table 13 , where model utility is established on LLaDA and refuted on Dream.

Figure 7: Matched primary-cell cost. Each bar separates synchronized decode from per-puzzle grammar/checker setup; static local plans are compiled once and reused. Lower is better.

Figure 8: MAP setup-plus-decode scaling on the same clue-stratified 90-puzzle subset at 4, 8, 16, and 32 denoising steps.

Figure 9: Official Sudoku validity by clue count. FactorDLM enforces rows, columns, and boxes; the local control and published finite automaton enforce only format and given clues.

Figure 10: Solver-only Sudoku audit. Uniform unary potentials recover the unique official completion on all 900 puzzles, proving that the shared-task result measures relational coverage rather than improved model selection.

Cell	Greedy	Best-of- $K$ oracle	Oracle gap	Realised gain
Dream trip	0.921	0.963	0.042	$-0.093$
LLaDA trip	0.847	0.954	0.106	$-0.125$
Dream meeting 5p	0.051	0.276	0.224	$+0.122$
LLaDA meeting 5p	0.133	0.367	0.235	$+0.082$
LLaDA meeting 4p	0.410	0.750	0.340	$+0.160$
Dream meeting 4p	0.040	0.400	0.360	$+0.250$

Appendix

Table 7: Exploratory relation between oracle gap and reranking gain across two task families, two backbones and four problem sizes, with Pearson

r=0.955

. Trip-planning cells are golden-itinerary match; meeting cells are exact-optimum rate. The prospective calendar holdout rejects the fitted law on LLaDA, so this figure is descriptive and does not validate a general predictor or adaptive deployment rule.

People	Backbone	model $-$ uniform (sampling)	model $-$ shuffled (MAP)	Records
4	Dream	$+0.003$ [ $-0.031$ , $+0.038$ ]	$+0.023$ [ $-0.006$ , $+0.052$ ]	100
4	LLaDA	$+0.063$ [ $+0.020$ , $+0.105$ ]	$-0.018$ [ $-0.049$ , $+0.014$ ]	100
5	Dream	$-0.058$ [ $-0.091$ , $-0.025$ ]	$+0.015$ [ $-0.025$ , $+0.055$ ]	98
5	LLaDA	$-0.074$ [ $-0.118$ , $-0.029$ ]	$+0.018$ [ $-0.025$ , $+0.061$ ]	98

Appendix

Table 8: Extended NATURAL PLAN, paired record-level differences in normalized objective with 95% bootstrap intervals over 20,000 resamples. The model-utility criterion passes 5 of 8 cells and the position-semantics criterion 0 of 8; every passing MAP cell is measured against the degenerate all- skip control. At five people the model is significantly worse than uniform unary potentials on both backbones.

Backbone	People	Agreement	Judge, sorted	Judge, permuted	Judge, symmetrized	PLL
Dream	3	0.627	0.320	0.267	0.310	0.490
Dream	4	0.487	0.270	0.235	0.290	0.290
Dream	5	0.430	0.143	0.146	0.184	0.173
LLaDA	3	0.729	0.970	0.850	0.970	0.970
LLaDA	4	0.642	0.730	0.643	0.710	0.570
LLaDA	5	0.543	0.296	0.276	0.357	0.214

Appendix

Table 9: Judge order probe over the matched candidate pools: exact-optimum rate under the recorded sorted candidate order, averaged over ten seeded permutations, and under order-symmetrized scoring over all eleven orderings, with the order-free pseudo-likelihood scorer for reference. Agreement is the fraction of the ten permuted trials per record that repeat the sorted-order choice. Every cell is order-sensitive and none reaches the 0.80 stability threshold fixed in advance; the LLaDA-8B advantage at four and five people survives permutation and is a content result, while its three-person tie is ordering-assisted.

Figure 11: Direct fixed-budget validity on the matched 900-puzzle protocol. LAVE, the local exact DFA, and FactorDLM tie at 100% in every cell. CFG and EPIC are shown with completion-based repair disabled (their Con. - and E. - configurations); within the fixed 16-slot budget neither reaches an accepting string on any puzzle, so their zeros measure the direct setting and say nothing about their repaired modes, which the figure does not rank.

Figure 12: Relational constraints defeat independent decoding, and sequential encodings of them are expensive. (a) Constraint satisfaction of independent decoding over the identical prompt and slot layout: near zero where the relation graph is dense, and never complete. FactorDLM is exact by construction. (b) The same-order copy relation

x_{i}=x_{k+i}

has induced width one and a constant 16-entry table at every

k

, while a deterministic automaton must distinguish all

4^{k}

first blocks. (c) That growth is not merely asymptotic: on the official CFG engine, the finite restriction of the same relation costs 0.06 ms and 80 MiB at

k=2

and 4.8 s and 4.1 GiB at

k=10

	Dream-7B		LLaDA-8B		LLaDA-1.5
Budget	Rerank	Oracle	Rerank	Oracle	Rerank	Oracle
greedy	0.120		0.530		0.650
$K=2$	0.240	0.250	0.790	0.790	0.840	0.840
$K=4$	0.360	0.370	0.930	0.940	0.930	0.940
$K=8$	0.490	0.500	0.970	0.970	0.970	0.980

Appendix

Table 10: Candidate-budget sweep behind Figure 3 : exact-optimum rate of pseudo-likelihood reranking and of the best-of-

K

oracle on three-person meeting planning. The reranker sits on or within one record of the oracle at every budget on every backbone, and every rerank point beats greedy with exact McNemar

p\leq 3.9\times 10^{-6}

Benchmark	Metric	What determines it	Shortcut result
Official Sudoku (900)	exact match	unique feasible completion	model-free uniform unary potentials reach 900/900 in 36.22 ms
Same-order copy	validity	constraint, by construction	second block is a function of the first
GRAM N-Queens	target agreement	canonical labeling	target is the lexicographic minimum in 405/405 multi-solution instances
GRAM coloring	target partition	canonical labeling	vertex-order greedy reproduces the target on 309/309 graphs; every dLLM method scores below chance
NATURAL PLAN	normalized objective	a degenerate control	uniform-MAP scores zero by tie-break; against random unary potentials LLaDA gains 21 points and Dream loses

Appendix

Table 11: The shortcut analyses behind Figure 4 : what determines each published metric, and the model-free rule that achieves it.

Model	Method	Valid (%)	Partition (%)	Agreement (%)	ms/output
Dream	Independent	2.68	0.00	55.47	69.03
	Finite support	100.00	13.87	76.02	71.71
	Factor separator	100.00	16.78	76.92	71.16
LLaDA	Independent	0.89	0.00	54.88	76.57
	Finite support	100.00	15.88	77.52	79.18
	Factor separator	100.00	16.78	77.82	78.66

Appendix

Table 12: GRAM graph coloring on the complete public test split. Validity is the informative column: independent decoding almost always violates an edge, and exact projection satisfies every edge. The partition column measures agreement with a canonical target, so it gives little evidence of quality. We audit it in § 5.3 and find that the published target is the lexicographic-minimum coloring, which vertex-order greedy reproduces on 309 of 309 graphs where three colors suffice. Every method here therefore scores below the 0.191 rate of choosing uniformly among partitions, and the column measures agreement with a two-line deterministic routine.

Model	Method (MAP unless noted)	Valid (%)	Objective (%)	skip rate	Optimum (%)
Dream	Independent model	79.00	42.83	—	6.00
	Uniform factor	100.00	0.00	1.000	0.00
	Uniform factor, sampling	100.00	57.94	0.450	22.30
	Random factor	100.00	62.61	0.401	24.30
	Shuffled-position factor	100.00	52.78	0.497	12.30
	Factor model	100.00	55.83	0.467	12.00

Appendix

Table 13: All 100 three-person NATURAL PLAN records, with the non-degenerate controls in italics. Objective is the scheduled-meeting count normalized by the instance optimum. Uniform MAP scores zero only because deterministic ties select skip everywhere, so its margin is not evidence. Against the sampling and random controls, Dream’s model unary potentials are worse than model-free ones, and on both backbones the objective tracks the skip rate rather than the unary source. Uniform and random are model-free and therefore identical across backbones, which is a correctness check on the controls.

Model	BFCL-derived method	Execution (%)	Exact plan (%)	ms/output
Dream	Format-only (typed slots)	1.61	1.61	118.20
	One-shot CP-SAT	15.32	15.32	136.96
	Component factor	16.13	15.32	593.44
	Global verifier	10.48	9.68	3,443.28
	Factorized verifier	16.13	16.13	3,333.92
LLaDA	Format-only (typed slots)	0.81	0.81	130.55

Appendix

Table 14: The 124-record executable-workflow study, official checker. The format-only arm decodes every slot from its own typed candidate list, so all of its outputs are individually well-typed, yet only 14.5% and 12.9% satisfy the cross-call relations and execution collapses to 1.6% and 0.8%, so the residual failures on this task are relational. Relational factors lift execution to 16.1% on both backbones (18W/0L,

p=7.6\times 10^{-6}

; 19W/0L,

p=3.8\times 10^{-6}

) and match a solver handed the same candidates (differences not significant). Factorized verification has complete candidate coverage but passed only 4 of 16 development criteria.

Figure 13: Complete MAP paired effects; points show estimates and bars show 95% paired-unit bootstrap intervals, in purple when the interval excludes zero. Positive favors the first named method. Rows separate planning objective over 100 records, workflow execution over 124 records, and same-order semantic score over 200 generated groups (1,200 questions). Constraint and model-utility effects are positive, while factorized workflow selection and dispersed schedule quality do not beat strong controls.

$k$	Finite-state lower bound	Factor peak	Finite support	FactorDLM
4	256	16	runs	100% valid
8	65,536	16	runs	100% valid
16	4,294,967,296	16	state cap	100% valid
32	18,446,744,073,709,551,616	16	state cap	100% valid

Appendix

Table 15: Native representation and GPU decoding scale for four-way same-order copy.

$k$	Alternatives	Grammar MB	Compile ms	Query ms	RSS MiB
2	16	0.0002	0.06	0.04	80.0
4	256	0.0046	0.57	0.43	80.0
6	4,096	0.1065	14.18	11.70	80.0
8	65,536	2.2282	278.48	377.01	206.9
10	1,048,576	44.0402	4,764.55	8,238.87	4,114.6

Appendix

Table 16: Official CFG engine on finite same-order-copy grammars.

Figure 14: Controlled A6000 runtime. Error bars are standard deviations over 20 repeats per method–record cell; the right column decomposes synchronized end-to-end time.

Figure 15: Exact CPU/CUDA placement validation over 100 balanced repetitions per workload. CUDA is

6.32\times

faster on the width-nine Sudoku graph, the CPU is

3.65\times

faster when width-one tables are too small to amortize kernel launches, and all 400 cross-device comparisons agree exactly.

Figure 16: Compiled-plan CPU speedup and fail-fast allocation boundary. The 24-variable clique is rejected symbolically before its dense table allocates.

Figure 17: Pinned CP-SAT divided by FactorDLM latency on the eight cells where every solver query is optimal. Repeated projection reuses the factor plan; one-shot includes compilation.

Method	Cells	vs. 1-worker CP-SAT	95% CI	vs. 8-worker CP-SAT
Factor CPU	8	61.06 $\times$	[19.43, 201.84]	43.11 $\times$
Factor CUDA	8	19.33 $\times$	[5.82, 64.73]	13.64 $\times$

Appendix

Table 17: Repeated changing-unary projection, geometric means over equally weighted fully optimal solver cells. All 320 listed factor–solver objective comparisons agree exactly. The scaling matrix pins one search worker for determinism; the audit re-times the same queries with num_search_workers = 8 , OR-Tools’ multi-worker portfolio, which is

1.42\times

faster here, so the bolded column is the stricter comparison and the one quoted in the main text. FactorDLM wins all eight cells under both configurations.

Constrained Decoding

Constrained decoding steers language model outputs to satisfy formal or task-specific rules while balancing validity, quality, and faithful probabilities.

See all 67 papers

DConstrain: Compiling Context-Parameterized Transitions for Diffusion Language Model Constrained Decoding
Oct 22, 2026Shidong Cao, Jing Ma, Wenhao Chai +3Constrained Decoding Grammar-Constrained Decoding
Hong Kong Baptist University · Princeton University · Ant Group
Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata
Jul 8, 2026Meihua Dang, Stefano ErmonConstrained Generative Modeling Constrained Decoding
Stanford University
Factorization-Error-Free Discrete Diffusion Language Model via Speculative Decoding
May 14, 2026Xun Fang, Yunchen Li, Hang Yuan +1Speculative Decoding for Diffusion Language Models Diffusion Language Model Inference
East China Normal University · Beijing Zhongguancun Academy

Oct 22, 2026J/K move · Enter open · S save

DConstrain: Compiling Context-Parameterized Transitions for Diffusion Language Model Constrained Decoding

Shidong Cao, Jing Ma, Wenhao Chai, Yuchen Tian+2

Hong Kong Baptist University · Princeton University · Ant Group

Constrained Decoding Grammar-Constrained Decoding Diffusion Language Model Decoding Diffusion Language Model Inference Diffusion Language Models

Open paper AskPDF arXiv

Diffusion language models (DLMs) decode multiple tokens in parallel, so individually valid tokens can be incompatible together under a schema. Exact joint inference over a grammar graph enforces compatibility, but it requires token-labeled successors across many hypothetical parser configurations. Encoding stacks and field histories in compiled states can cause exponential growth, which forces prior exact decoders to fix property orders and exclude valid outputs. We present DConstrain, which compiles schemas into context-parameterized transition programs. Cold compilation specializes token consumption to local grammar states while retaining context-dependent stack operations, environment guards, and caller-dependent deferred parsing symbolically. Tracking field histories as runtime values supports arbitrary property order without enumerating field subsets offline. At runtime, warm compilation binds reached configurations to these programs to construct exact successors, overlapping with the model forward pass because graph construction requires no model scores. Furthermore, token-effect grouping merges tokens with identical compiled effects before runtime contexts are bound, so groups are reused across stacks and environments even when concrete successors differ. Objective-specific score aggregation and token restoration provably preserve both the Viterbi optimum and the token-labeled path distribution of ungrouped inference. Across three benchmarks and two DLM families, DConstrain compiles 100% of BFCL schemas under arbitrary property orders, whereas an optimized finite-state baseline compiles only 71.30-85.81%. Under arbitrary property order, it reduces BFCL end-to-end decoding latency by 6.65-46.26 times with 100% schema validity and raises DiffusionGemma's BFCL accuracy from 37.27% under fixed order to 81.56%.

Abstract

Constrained Decoding

Explore similar work

DConstrain: Compiling Context-Parameterized Transitions for Diffusion Language Model Constrained Decoding

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

Factorization-Error-Free Discrete Diffusion Language Model via Speculative Decoding