- Rating
- 4
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes CompDiff-BP, which uses belief propagation to combine local constraint models during diffusion. At each step, the models exchange information through shared variables to estimate the clean assignment. This gives a principled way to compose the models and improves results on SAT, graph coloring, 8-Queens, and crosswords.
Critical strengths
-
The method follows clearly from the motivation. Constructing the posterior over clean assignments addresses the mismatch between composing clean distributions and composing independently noised models.
-
The experiments show meaningful improvements, especially on larger SAT instances. The method solves 71% of the 50-variable instances, compared with the previous compositional method’s published result of 43%.
Critical weaknesses
-
The crossword results do not clearly separate better inference from the benefit of a restricted answer space. CompDiff-BP restricts each word factor to a fixed Wordle lexicon, while the PEM and Bethe baselines do not appear to use the same restriction. This is a reasonable design choice, but it changes which assignments the factors allow. Some of the improvement may therefore come from excluding nonwords, rather than better coordination between experts. The gain over standalone BP remains useful because that comparison uses the same restricted factors.
-
The method depends on each local constraint having a manageable set of possible assignments. Its BP updates enumerate these assignments, which is practical for three-variable SAT clauses and pairs of colors. More complex local constraints can make this computation expensive; crosswords already require a word list to reduce the possibilities. The authors acknowledge this limitation. The larger-instance results demonstrate reuse of small local factors, while applicability to richer constraint models remains limited.
Questions for authors
Do the PEM and Bethe crossword baselines use the same word list? If not, could the authors clarify how much of the reported gain comes from this restriction?
2 comments
Thank you for the response and additional experiments. The comparison using the same lexicon addresses my main concern about the crossword results. The limitation on local factor size is also clearly acknowledged. I maintain my rating of 4.
We thank the reviewer for their detailed review and encouraging feedback. We address your concerns below.
Thank you for this suggestion, the original neural PEM and Bethe baselines do not use the same lexicon restriction. We have conducted a new experiment where all methods use the same 14,907-word lexicon, clue-conditioned learned energies, and temperature. This gives both baselines access to the same inductive bias as CompDiff-BP throughout inference.
With identical lexicon support and clue energies, CompDiff-BP still substantially outperforms both baselines. Interestingly PEM and Bethe performed worse using the lexicon-restricted energies. One possible explanation is that restricting each factor to valid words creates stronger competing preferences at intersecting cells. Without iterative reconciliation, these preferences may be difficult to coordinate: without this restriction, a method can predict a correct word for one clue while allowing an invalid word for an intersecting clue, whereas restricting both to valid words may push the method to change previously correct predictions. We have included this new discussion in the revised manuscript.
We agree that this is one of the main limitations of the current implementation. Current implementation for the crossword addresses this practically with a lexicon, but to extend the approach to more general complex constraints requires approximate message operators or other approximate message passing algorithms. We leave this for future work.