acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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.6× 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.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
constrained decoding, diffusion language models, factor graphs, exact inference, variable elimination, structured generation, benchmark auditing

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_PzHjOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes to represent finite-domain relations as factor graphs, in order to tackle a known problem in constrained decoding for diffusion models where relational constraints (such as values that must match at different positions in a string) induce an exponential blowup in the size of the automaton. The authors claim that their encoding using factor graphs changes this exponential cost to one over the induced width of the constraint graph, and adds experiments that illustrate their efficiency.

Critical strengths

The evaluation seems to be conducted over a relatively comprehensive set of benchmarks.

Critical weaknesses

I find that the paper is highly opaque and failed to understand most of the key technical details. In particular, the paper is lacking definitions for all key concepts: factor graphs, variable elimination, what a chain case in the factor graph is, amongst others. Because these definitions are not stated, and notation is also not well-defined, I cannot understand how the proposed algorithm operates either, how constraints are modeled and what constraints are supported, what the input and the output of the proposed algorithm is, etc.

To be honest, my guess is that the entire paper was generated by an LLM. I strongly encourage the writers to review and fix their writing, as it seems that the approach and evaluation may be hiding an actual contribution.

Questions for authors

NA

2 comments

We thank the reviewer. We have heavily rewritten the paper so that the method can be understood from the main text alone.

FactorDLM takes a masked diffusion LM, a prompt, and an output layout of L positions, each with a finite set of allowed tokens. The constraint is a set of hard factors: small tables over a few positions that mark each combination of values as allowed or forbidden. It also takes a number of denoising steps and a size budget. It returns an output that satisfies every factor, and if exact inference would need a table larger than the budget, it refuses before running the model. Any finite-domain relation that can be written as such tables within the budget is supported. In our experiments this covers equalities and inequalities between positions, tables of allowed combinations, all-different, running sums, and automata for syntax, all in one graph (Table 1).

At each denoising step, the model's log-probabilities become one-variable factors. Together with the hard factors, they give the model's prediction restricted to allowed outputs. Variable elimination then returns the most likely allowed complete output, or an exact sample. The decoder keeps the values at the positions where the model is most confident and repeats. Because every proposal is a complete allowed output, a valid completion always exists, so the final output always satisfies the constraints (Algorithm 1 and the proof in §3.2).

The three terms raised in the review are now defined in Section 2. A factor graph is a set of discrete variables and factors; each factor is a table over a few of the variables, and the distribution is proportional to the exponential of the sum of all factors. Variable elimination removes variables one at a time in some order; for each variable it combines the factors that mention it into one table, then maximizes or sums the variable out, and the largest table has d^(w+1) entries, where w is the induced width of the order. The chain case is a deterministic automaton written as a factor graph: state variables z_0, ..., z_L form a chain linked by transition factors g_i(z_{i-1}, x_i, z_i). This is the structure that earlier exact decoders for diffusion LMs work with.

We are happy to clarify any part that remains unclear. If possible we hope reviewer can read the newer pdf version again.

Thanks for the update. I am not willing to reread the entire rewritten paper to understand it. I won't stand in the way of other reviewers if they decide to support it, but this type of edit is beyond revision in my opinion.

Reviewer_aqtEOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces FactorDLM, a training-free framework for constrained decoding of diffusion language models. At each denoising step, model predictions supply unary potentials, while a factor graph encodes hard constraints. Exact variable elimination produces a feasible MAP assignment or sample, and selected positions are committed before the next step. A reusable compiler estimates intermediate table sizes and rejects computations that exceed declared budgets.

The principal contribution is a representation argument: nonlocal relations can admit compact factor graphs even when automata reading the prescribed output serialization require exponentially many states. The framework also combines syntax automata with relational factors and supports class-based vocabulary reduction. Experiments cover puzzles, planning, copy constraints, and structured JSON generation across three backbones, with additional workflow studies. The paper reports exact constraint satisfaction on executed instances, solver comparisons, and benchmark audits separating structural validity from semantic correctness. Candidate reranking improves semantic performance in some settings, although it introduces substantial additional computation.

Critical strengths

The paper makes a useful distinction between the order in which an output is written and the relationships that constrain it. Proposition 1 shows a clear separation when the automaton has to follow the original output order. The factor graph provides a unified way to handle both syntax and nonlocal constraints. The commitment rule also makes sense. Committing values from a complete feasible proposal keeps at least one valid completion available. Requiring a unique assignment of auxiliary variables for each valid output also prevents bias from counting the same output multiple times. These components fit together well and give the method a credible technical foundation.

Critical weaknesses

My concern is that we still don’t know the full computational cost of the strongest semantic results, or how much the model-guided proposals actually contribute.

The paper shows that projection itself adds very little overhead, but that doesn’t tell us how expensive the whole pipeline is. Section 5.4 reports substantially more computation for generating candidates and scoring them with PLL. For example, the referential JSON setting involves 584 masked-token scoring evaluations. We also don’t have an end-to-end timing for selection. And Appendix E says that latency wasn’t recorded for variable-length JSON at its peak of around 7.6 million entries. So it’s still hard to judge the practical cost of getting these results.

For meeting planning, I’d also like to see a baseline that builds a pool by sampling uniformly from the feasible solutions, then uses the same PLL scorer to select from that pool. Without this comparison, it’s hard to tell how much the model-guided proposals help beyond what the scorer can already achieve with uniformly sampled candidates. This matters especially because there are relatively few feasible solutions in the three-person setting. Table 8 also shows that model unaries perform worse than uniform unaries in some larger settings.

So, based on the current evidence, I’m not yet convinced that the full generation-and-selection pipeline offers a meaningful quality improvement at a comparable computational cost.

Questions for authors

Does the exponential separation still hold if both methods can choose their inference order?

What are the total runtime and peak memory costs of your best-performing pipelines, including candidate generation and PLL scoring?

How much does compilation cost, and can the compiled representation be reused across different inputs?

How well do uniformly sampled feasible schedules perform with the same PLL scorer, candidate budget, and rendering?

How does the hybrid factor graph compare with a product automaton using the same constraints, logits, and decoding schedule?

2 comments

We thank the reviewer. We ran every requested comparison. One of them changed how the paper describes the selection results, as explained under Q4.

Q1. Does the exponential separation still hold if both methods can choose their order?

No, and we now say so in the paper (new Proposition 2). For any reading order there is an automaton whose state stores the values of the already-read positions that still share a factor with an unread one. If b is the number of such positions, the automaton needs at most d^b + 1 states. The smallest b over all orders is the pathwidth of the constraint graph (Kinnersley, 1992), and pathwidth is O((w+1) log n) for treewidth w (Korach and Solel, 1993). So with a free order the gap is polynomial for bounded treewidth and alphabet size; for copy, reading the two halves interleaved needs only q + 1 states. An automaton with a chosen order is therefore a path-shaped elimination plan, and variable elimination can also use tree-shaped ones. The exponential gap of Proposition 1 applies when the automaton has to read the output in the order it is written. That is the situation of existing exact decoders for diffusion LMs, because their automata and grammars describe syntax. FactorDLM keeps the syntax automaton in output order and adds the relations as separate factors.

Q2. Total runtime and peak memory, including candidate generation and PLL scoring.

New Table 3 gives the full cost per output, measured on LLaDA-8B with one RTX A6000:

TaskPipelineForward passesTime (s)Peak GPU (GiB)
Meeting, 3 peoplegreedy30.3119.2
+ selection27 + 8 batched10.919.2
Meeting, 5 peoplegreedy30.5424.2
+ selection27 + 17 batched41.524.2
Referential JSONexact top-811.0516.0
+ PLL1 + 24 batched8.0616.0
Var-JSON, 3 usersexact top-8127.416.1
+ PLL1 + 32 batched37.416.1

Selection is expensive: about 35 times greedy decoding on meeting planning, and 77 times at five people, mostly because of PLL scoring (each batched pass scores 16 masked copies). Peak GPU memory comes from the model weights and does not grow with selection. The most expensive constraint inference in the paper is variable-length JSON with three users, at 27.4 s on the CPU and 266 MiB of host memory, compared with 0.8 s for two users. The paper now reports these costs next to Table 2, and we agree the +Sel columns should be read with them in mind.

Q3. Compilation cost and reuse.

Compilation is cheap because it only works out table shapes. For referential JSON, building the graph and searching for an elimination order takes 1.1–1.7 s, and compiling the plan takes 2–5 ms. The plan depends on which positions each factor touches and on the domain sizes, never on the prompt or the logits, so one plan serves every step and every input with the same layout. That means one plan for all referential-JSON prompts, two for all variable-length prompts, and one for all 900 Sudoku puzzles, whose clues enter as fixed values. Meeting planning needs one plan per record because each record has its own time windows; that cost is included in the timings above.

Q4. Uniformly sampled feasible schedules with the same scorer, budget, and rendering.

We ran this, and also a stronger version that scores every feasible schedule (on records with at most 128 of them). All pools use the same rendering and the same PLL scorer, and the model pool reproduces the numbers in the paper exactly. The table shows the rate of picking an optimal schedule.

ModelPeopleGreedyModel poolUniform poolAll feasible (n)Model pool, same n
Dream30.120.490.770.97 (100)0.49
Dream40.040.290.490.92 (89)0.30
Dream50.050.170.200.65 (46)0.20
LLaDA-8B30.530.970.760.97 (100)0.97
LLaDA-8B40.410.570.420.64 (89)0.62
LLaDA-8B50.130.210.190.57 (46)0.33
LLaDA-1.530.650.970.710.91 (100)0.97
LLaDA-1.540.450.510.380.58 (89)0.56
LLaDA-1.550.140.220.190.50 (46)0.30

The model's candidates help in some settings, and the scorer accounts for most of the gain. For the LLaDA models on small problems, the model's own candidates help: with three people its pool beats the uniform pool by 21 and 26 points (exact McNemar, p < 1e-4), even though the uniform pool has more distinct candidates (6.5 against 3.5–3.7), because the model's pool contains an optimal schedule much more often (0.97–0.98 against 0.80). That advantage gets smaller at four people (p = 0.06 and 0.09) and is gone at five. For Dream, the sampled candidates are worse than uniform ones at every size, which fits Table 8 of the submission (Table 11 in the revision), where Dream's per-position predictions are worse than uniform. Scoring every feasible schedule matches or beats the model's pool in every case except LLaDA-1.5 with three people, by a wide margin for Dream (0.65–0.97 against 0.20–0.49) and for the LLaDA models at five people (0.50–0.57 against 0.30–0.33); every five-person difference is significant (p < 0.03).

So most of the gain comes from the model acting as a scorer of complete candidates. Exact inference still matters here in two ways: every candidate is valid, and when the feasible set is small it can be listed exactly and scored in full, which is the strongest approach in our experiments. Section 5.4 has been rewritten around this. Referential JSON is the opposite case: eight uniformly chosen records contain a correct one with probability at most 0.7%, while the model's exact top-8 contains one for 98% of prompts.

Q5. The hybrid graph against a product automaton with the same constraints, logits, and schedule.

We built the minimal product automaton of schema and references for referential JSON (3,021 states) and decoded it as a chain in the same engine, from the same logits, on 200 prompts for each of the three models. Both encode the same set of allowed records, so the exact top-8 lists agree on all 600 instances (595 identical, five differing only in the order of tied scores) and the accuracy is identical. The difference is cost:

Referential JSON, exact top-8Our graphProduct automaton
Largest table (entries)86432,400
Peak host memory0.34 MiB7.2 MiB
Time1.0 s4.0 s

For variable-length JSON, the product automaton needs at least 23,409 states. On these schemas the product automaton is still feasible; our graph is cheaper and lets the schema and the relations be written separately. The exponential separation itself is the copy result of Proposition 1 (see Q1).

In the revision, Table 2's +Sel columns come with their cost, and Section 5.4 attributes the gain to the model as a scorer. The main contribution does not rely on selection: exact relational constraints, with every output valid at 0.4–6.9% overhead.

Reviewer_PWBdOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper proposes to use factor graphs as the constraints in constrained decoding of diffusion language models (dLLMs).

Based on this form of constraints, the authors proposes FactorDLM. It calculates the mean-field distribution after considering the factor-graph constraints.

It is evaluated on Sudoku puzzles, graph-coloring tests, N-queen boards, two planning tasks, self-constructed countdown tasks and JSON tasks and relational consistent function-call workflow tests, and only compared against the base model. There is also a best-of-8 selection variant being compared.

Critical strengths
  • Novel idea of using factor graphs as the constraints.
  • Theoretical analysis of the advantages of factor graphs over regular languages or context-free grammars.
Critical weaknesses
  • The paper focuses on factor graph constraints, but factor graph constraints require explicit relationship between different positions in the generated text. It is hardly useful, because the role of each token has to be predetermined before generation.
  • The paper is too hard to read. It is hard to believe that any human had even read this paper before submission. For example, (1) in the abstract, they use the analysis and the numbers in 4-symbol same-order copy for genral same-order copy; (2) the explanation text in Figure 1(d) overlays on the automaton; (3) most concepts are suddenly introduced without proper explanation; (4) in the related work, finite automata constraints are classified as different constraints as regular languages, and lookahead verification are classified as different from context-free grammars. There are other places where I cannot exactly say why it is hard to read, but in general, this feels completely different from other human-written papers I read during reviewing, where the mindflow of human authors are clear, but this paper seems to be an unpolished AI-generated paper.
Questions for authors

See above weaknesses.

1 comment

We thank the reviewer. On whether the role of each token must be fixed in advance: positions do need a layout, but their roles can be decided while decoding. A masked diffusion LM always generates on a canvas of fixed length, so every exact decoder for these models, including the automaton and grammar decoders we compare with, works on such a layout. In FactorDLM a schema automaton inside the factor graph decides which field each position holds, and a padding symbol marks where the output ends. In our variable-length JSON task, the record length (77 to 104 tokens, with an optional note) is decided during decoding by the model's own end-of-text token. In the open-vocabulary task, a free-text field can take any token in the vocabulary and the model chooses how long it is. The setting we target is structured output, such as JSON records, function calls, plans, and puzzle solutions, where fields follow a schema and relations between fields have to hold. Long free-form text with relations between arbitrary words is outside that scope, and the Limitations paragraph now says so.

Writing a constraint takes a few calls to hard_factor(scope, allowed_table), built automatically from each instance, and the new Appendix C shows the code. A copy constraint is one line per pair. Meeting planning is one table per pair of people, saying that one meeting ends, travel included, before the other starts. JSON references take three tables. A whole task module, with parsing, prompts, and evaluation, is 93 to 500 lines of Python.

Earlier exact decoders for diffusion LMs enforce syntax, through regular languages and grammars. FactorDLM adds relations between positions, such as references between fields, equal answers, and conflicts between meetings, and enforces them together with syntax, with every output valid and the cost known before the model runs.

On presentation:

  1. The abstract and Proposition 1 now state the bound for an alphabet of size q: q^k automaton states against k tables of q^2 entries.
  2. Figure 1 is redrawn at print size, with three panels and no overlapping text.
  3. The new Section 2 defines every concept before it is used, and Section 3.1 states the inputs, the output, and the supported constraints.
  4. Related work now groups earlier decoders by the kind of constraint: regular constraints through automata (DINGO; Dang and Ermon), and context-free constraints through grammars (Mündler et al.; EPIC), with LAVE adding lookahead verification.

On baselines: besides the base model, the paper compares with the released CFG, EPIC, and LAVE decoders and an exact automaton decoder on Sudoku (2.5x faster than LAVE at the same accuracy), with the official CFG engine on copy (44 MB of grammar and 8.2 s per query at k = 10), and with CP-SAT on repeated solves (13.6x faster). The revision adds a product-automaton decoder on referential JSON (same outputs, 4x the time and 20x the memory) and the new selection controls. All baselines are now listed together in Section 4.

If possible we hope reviewer can read the newer pdf version again.

Comments on the paper

1 comment

We thank the reviewers. We were trying to fit too many results into nine pages and used several concepts before explaining them. We have rewritten the paper with readability as the main goal, and we ran all of the experiments that Reviewer aqtE asked for. New and substantially changed text is shown in blue in the revised PDF; passages that we only reworded or moved are left in black.

On the writing side, the paper now has a Preliminaries section (Section 2) that defines factor graphs, the automaton as a chain-shaped factor graph, and variable elimination before they are used, all on one running example. Section 3.1 states what the method takes as input, what it returns, and which constraints it supports; Table 1 lists the constraint types, and Table 5 in the appendix gives the encoding of every task. Algorithm 1 has moved from the appendix into the main text, next to the system overview (Figure 2) and a short proof that every output is valid. Figure 1 is redrawn at a readable size. Some secondary material (benchmark audits, Countdown, the open-vocabulary propositions) has moved to the appendix to make room.

The new results are summarized here, with details in the individual replies:

QuestionWhat we foundWhere
Does the separation survive a free reading order? (aqtE)No; with a free order the gap is polynomial (new Proposition 2)§3.3
Full cost of selection (aqtE)Time, forward passes, and memory for every pipelineTable 3
Compilation cost and reuse (aqtE)2–5 ms per plan, one plan per output layout§3.2, §5.3
Uniform-pool control (aqtE)Plus a stronger control that scores every feasible outputTable 4, §5.4
Product automaton, same logits (aqtE)Same outputs on 600 instances, 4x the time and 20x the memory§5.2
A multimodal model (new)Visual Sudoku with Dimple-7B: validity goes from 2.2% to 100%Table 2

One of these results changed our own reading of the paper. The uniform-pool control shows that most of the gain from selection comes from the model scoring complete candidates, and less from the candidates it proposes. Section 5.4 now says this plainly. The main contribution stands without selection: relational constraints, compiled together with syntax, enforced exactly on every output at 0.4–6.9% added latency.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.