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