acceptodds
Under review as a conference paper at ICLR 2027

Belief Propagation enables Compositional Diffusion for Constraint Reasoning

Abstract

Diffusion models have shown promise as iterative solvers for constraint reasoning problems. Most approaches train a single model on complete problem instances, inhibiting systematic generalization to novel combinations of the same constraints. *Compositional diffusion* instead seeks to learn reusable local constraint "experts" that are assembled at inference time, enabling generalization to new problem structures. Existing methods in this setting inherit two challenges of compositional diffusion without resolving them. First, noising and composition do not commute: composing independently noised experts does not recover the distribution obtained by first composing the experts in the clean space and then applying the forward diffusion process. Second, to produce a consistent solution, variables that participate in multiple constraints must resolve conflicts in the experts' value preferences. We introduce *CompDiff-BP*, a compositional diffusion method that addresses both challenges by performing inference over clean assignments using loopy belief propagation. At each diffusion step, we construct a constraint-based factor graph for the posterior over clean assignments conditioned on the current noisy state, then use belief propagation to approximate variable marginals. Their means then parameterize the next reverse step. In this way, without retraining the local experts, we directly approximate the denoiser of the forward-noised clean composition while reconciling overlapping experts on their shared variables. We evaluate *CompDiff-BP* on 3-SAT, Graph Coloring, N-Queens, and Crosswords, where it consistently outperforms existing compositional approaches, with particularly strong gains on larger problem instances.

Primary area:
generative models
Keywords:
constraint satisfaction problems, compositional diffusion, graphical models

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_3fSYOpenReview ↗
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
  1. 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.

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

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

We thank the reviewer for their detailed review and encouraging feedback. We address your concerns below.

The crossword results do not clearly separate better inference from the benefit of a restricted answer space. Clarify how much of the reported gain comes from this restriction.

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.

MethodLexiconLetter (%)Word (%)Solved
PEMyes58.618.00/20
PEMno70.835.50/20
Betheyes59.222.50/20
Betheno71.631.00/20
CompDiff-BPyes85.865.55/20

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.

The method depends on each local constraint having a manageable set of possible assignments.

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.

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.

Reviewer_6NuxOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CompDiff-BP, a compositional diffusion method for constraint satisfaction problems. A small energy-based model is trained for each type of local constraint and composed at inference time to solve arbitrary-sized instances. CompDiff-BP addresses two challenges of compositional diffusion: it avoids the noising-composition mismatch by performing inference over clean assignments, and it reconciles conflicts between overlapping experts via loopy belief propagation. At each reverse-diffusion step, a factor graph is constructed from learned constraint potentials and Gaussian unary likelihoods, and sum-product BP approximates variable marginals whose means parameterize the reverse update. Experiments on 3-SAT, graph coloring, 8-Queens, and mini crosswords show consistent improvements over existing compositional baselines, with large gains on bigger instances.

Critical strengths
  • The method is genuinely general across problem structures. The same factor-graph-plus-BP pipeline handles boolean satisfiability, graph coloring, queen placement, and semantic word matching without task-specific modifications.
  • The BP-depth ablation (Table 4) is well-designed and provides the most convincing evidence in the paper. By comparing R=1 against R>1 with everything else held fixed, it cleanly isolates the effect of iterative message passing from static aggregation.
Critical weaknesses
  • Conceptually, the paper tries to learn potential functions to guide the decoding process. However, the authors do not compare with hard-coded potential functions. Graph-coloring, 3-SAT & 8-queens all have potential functions in analytical form. Comparison is necessary to seperate the contribution of learned potential functions and inference protocol.

  • There are many established inference techniques for constraint reasoning. In particular, damped min-sum BP with SCFG exhibits strong performance on general constraint reasoning problems including graph-coloring (with small costs to break tie). I suggest the authors including damped min-sum BP as an additional baseline, so as to confirm the merit of learned potential functions.

  • The benchmark problems are relatively small (e.g., 50 variables for UF50-218, <=100 variables for graph-coloring problems), which cannot support the scalability of the proposed method.

Questions for authors

N.A.

4 comments

We thank the reviewer for their thorough review. We address your concerns below.

hard-coded potential functions.

Our goal is to study how independently learned constraint experts can be composed at inference time, rather than how to solve problems where the exact constraint functions are already known. This is why our main experiments use the same learned experts across CompDiff-BP, PEM, and Bethe, allowing us to study the effect of different composition methods.

However, we agree that studying the performance of exact analytical potentials where available can provide insight into the gap for learned experts. We therefore ablate our method to use analytical potentials where available. We conducted additional experiments replacing the learned energies with exact constraint costs and comparing the different inference methods.

MethodUF20UF508-QueensColoring conflicts ↓
Bethe-Analytical100/10013/10092/100475
PEM-Analytical44/1000/10038/1001287
CompDiff-BP-Analytical100/100100/100100/100120

We observe that CompDiff-BP also performs very well with analytical potentials, solving all SAT instances and substantially outperforming on Graph Coloring. These results show that our approach is not limited to learned energies and that iterative reconciliation remains beneficial even when the exact local constraint costs are available. We have included these results in the revised paper.

damped min-sum BP with SCFG

Thank you for suggesting this baseline. We implemented damped min-sum BP with SCFG following [1]. We evaluated it with both analytical constraint costs and learned energy tables obtained from our pretrained local experts. We use the reference’s 2000-iteration budget and the same candidate counts.

PotentialsMethodUF20UF50Coloring conflicts ↓
AnalyticalMin-sum/SCFG100/100100/100101
AnalyticalCompDiff-BP100/100100/100120
LearnedMin-sum/SCFG79/10048/1001162
LearnedCompDiff-BP92/10071/100422

With analytical potentials, CompDiff-BP achieves comparable performance to min-sum on SAT instances but trails on the coloring task. With learned potentials, however, CompDiff-BP substantially outperforms min-sum, demonstrating its advantage in the setting targeted by our work: composing learned constraint experts, such as the clue-answer relationships in Crosswords. We have updated the manuscript with this discussion.

[1] Cohen et al. "Governing convergence of Max-sum on DCOPs through damping and splitting." Artificial Intelligence (2020).

Scalability

Our goal is to advance compositional diffusion by developing a more effective way to combine reusable learned constraint experts. Our experiments demonstrate substantial improvements over existing compositional approaches across SAT, Graph Coloring, 8-Queens, and Crosswords, particularly on larger instances. While additional computational resources would enable evaluation on even larger problems, we believe the current results provide meaningful evidence of the advantages of our method.

We would also like to clarify that our Graph Coloring evaluation is not limited to 100 vertices. Appendix E includes COLOR instances with up to 556 vertices, using the same learned edge expert without retraining. On the 556-vertex instance, CompDiff-BP obtains 31 conflicting edges, compared with 69 for PEM and 239 for Bethe. As discussed in our Limitations section, the current implementation is best suited to problems with tractable factor scopes, and extending it to more complex constraints remains an important direction for future work.

I appreciate the authors’ efforts to address my concerns. However, the analytical-potential experiments remain insufficiently specified, in particular how the clean-space constraints are converted into time-dependent energies and scores for PEM and Bethe. The substantial degradation of these baselines under analytical potentials raises concerns about the fairness of the comparison. Moreover, the new results show that analytical potentials consistently outperform learned ones, and that damped min-sum BP with analytical potentials matches or exceeds CompDiff-BP, which weakens the case for learned potentials on these benchmarks; Mini Crosswords, the only task requiring learned constraints, provides limited evidence.

We thank the reviewer for the follow-up clarification.

We would like to emphasize that our goal is to develop an effective method for composing independently learned constraint experts, rather than to outperform analytical approaches when exact constraints are available. We therefore follow Oarga & Du (2025), the previous state-of-the-art compositional diffusion approach for constraint reasoning, using the same benchmarks and local expert models. All compositional methods share the same trained checkpoints, allowing direct comparison of their inference procedures.

We agree that, when analytical constraints are available, compositional diffusion methods still lag behind classical inference. This gap highlights the need for further advances in compositional diffusion, and our results demonstrate substantial improvements over existing approaches when composing learned experts.

We have added implementation details for the analytical-potential experiments in Appendix D.4. All methods use the same analytical constraint costs. CompDiff-BP uses the clean factor potentials directly, while PEM and Bethe obtain time-dependent noisy-space experts by applying the Gaussian forward process independently to each factor. These experts are then used within their original composition and sampling procedures.

I appreciate the authors' substantial efforts to address my concerns. The additional experiments and implementation details have satisfactorily resolved my main concerns regarding analytical potentials and classical inference baselines. While the scalability evaluation remains somewhat limited, I find the revised paper considerably stronger and have updated my rating from 2 to 3.

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

The paper proposes CompDiff-BP, a framework for compositional diffusion that addresses two problems with existing composition methods: independently composing local predictions does not generally recover the correct global denoising distribution, and composing independently noised local experts does not preserve the intended clean-space composition. At each intermediate diffusion step, it represents each local operator’s posterior over clean assignments as a factor in a shared factor graph. It then runs loopy belief propagation (LBP) to approximate the posterior marginals of the composed clean assignments, which parameterize the global reverse-diffusion transition. Experiments on constraint-reasoning tasks demonstrate the advantages of CompDiff-BP for composing diffusion models. However, the method does not establish convergence guarantees or conditions under which LBP recovers the correct target distribution.

Critical strengths
  1. Well-motivated approach: The paper presents a compelling idea for composing diffusion models for constraint-reasoning tasks by representing local operators as factors in a shared factor graph and using LBP to approximate the composed posterior.
  2. Clear presentation: The paper is well organized and easy to follow, with a clear explanation of the proposed method.
  3. Empirical validation: The experiments demonstrate the effectiveness of CompDiff-BP on constraint-reasoning tasks and provide evidence of its advantages over existing composition approaches.
Critical weaknesses
  1. Lack of convergence guarantees: The paper does not establish conditions under which LBP converges or accurately approximates the target posterior marginals in the proposed factor graphs.

  2. Limited analysis of LBP's contribution: The paper provides limited analysis of how much the gains depend on LBP isolated from just non-message passing based composition, including the effect of the number of message-passing rounds per reverse diffusion step.

  3. Fairness of computational comparisons: Although the paper includes neural non-diffusion baselines, their results are taken from prior work rather than retrained or reevaluated. It is therefore unclear whether these comparisons use matched wall-clock budgets. The compositional methods share a candidate budget, but equal candidate counts need not imply equal inference time, particularly when diffusion methods use iterative sampling trajectories.

As a result, this paper has some nice ideas for composing diffusion models outputs during inference but it needs some work to mitigate these weaknesses.

Questions for authors
  1. Ablation of LBP: Could the authors provide more extensive ablations isolating the contribution of LBP, such as comparing against direct composition without message passing and varying the number of LBP rounds, to clarify where the gains come from?
  2. Comparison with traditional solvers: How does CompDiff-BP compare with traditional non-neural constraint-reasoning solvers under comparable wall-clock budgets? This would help establish its practical advantage beyond comparisons with other diffusion-composition methods.
  3. What other areas do the authors see CompDiffBP method of composing diffusion being applied?
4 comments

We thank the reviewer for their detailed review and encouraging feedback. We address your concerns below.

Lack of convergence guarantees

We agree that our method does not have general convergence or approximation guarantees on loopy factor graphs. We use BP with a fixed number of message-passing rounds to approximate the posterior marginals at each diffusion step. Running BP until convergence at every diffusion step would introduce substantial and potentially unbounded computational overhead.

To analyze the approximation accuracy, we conducted additional experiments on small SAT and Graph Coloring instances where the exact posterior marginals can be computed. We report the mean marginal total variation distance to the exact posterior below.

BP roundsSATGraph Coloring
00.1460.086
10.0830.022
20.0600.011
30.0500.007
50.0380.004
100.0340.005
250.0320.005

These results demonstrate that finite-round BP substantially improves the approximation of the intended clean posterior. Establishing theoretical guarantees for arbitrary learned factor graphs is an interesting direction which we leave for future work. We have added this discussion to the revised manuscript.

Limited analysis of LBP's contribution; Ablation of LBP.

We directly study LBP's contribution in Section 4.2 and Appendix G, where we vary the number of BP rounds while keeping the learned factors and diffusion settings fixed. We found that increasing the number of BP rounds substantially improves performance. In particular, the poorly performing R=1 setting corresponds to no iterative message passing, as each factor contributes its local evidence without incorporating feedback from neighboring constraints. This suggests that LBP is important for reconciling predictions across overlapping constraints.

Fairness of computational comparisons

Following common practice, we report the published results of non-compositional baselines rather than rerunning every method, due to limited computational resources and the difficulty of reproducing all baselines. We have edited the manuscript to clarify that these results provide additional context and were not obtained under the same computational conditions.

For the compositional methods, we agree that using the same number of candidates does not necessarily mean using the same computation time. We report the running times of these methods in Appendix F, showing that CompDiff-BP is 2.1–206.7 times faster than PEM, while Bethe can be faster on some tasks.

We additionally conducted experiments where all methods receive the same wall-clock budget per instance, allowing each method to run as many complete sampling trajectories as the budget permits. We use the same learned experts and energy-based candidate selection. The results are shown below.

BenchmarkTime budgetCompDiff-BPBethePEM
UF50 solved ↑120 s71/10041/1004/100
Coloring conflicts ↓120 s42022321454
Crosswords word accuracy ↑120 s65.5%49.5%41.0%

We observe that CompDiff-BP continues to outperform the other compositional methods under the same runtime budgets. These results show that the performance gains are not simply due to additional computation. We have included this comparison in the revised paper.

Comparison with traditional solvers

Our goal is not to establish diffusion as a replacement for specialized constraint solvers. We study the setting where constraints are represented by reusable learned experts rather than provided analytically. Accordingly, our main comparisons use the same learned experts across CompDiff-BP, PEM, and Bethe to isolate the effect of the composition method.

However, we agree that comparing against classical solvers is informative for understanding the gap between compositional diffusion and specialized solvers on problems where analytical constraints are available. We evaluated OR-Tools CP-SAT on the same SAT and Graph Coloring instances, using eight CPU workers and time limits of 20 seconds per instance. OR-Tools solves all 100 UF20 and 100 UF50 instances and achieves 103 total conflicting edges across the same 58 Graph Coloring instances.

As expected, OR-Tools performs extremely well when the constraints are known analytically. However, it cannot directly solve our Crossword task, where determining whether a word answers a natural-language clue requires learned semantic information. This highlights the motivation for compositional diffusion, where learned local constraints can be combined to solve larger problems. We have included these results and discussion in the revised paper.

Other domains

Compositional diffusion is an active research direction, with applications in planning and robotics [1], molecular discovery [2], image generation [3], and beyond. To the best of our knowledge, CompDiff-BP is the first method to introduce iterative belief propagation for reconciling predictions from overlapping diffusion experts. While we focus on constraint reasoning to demonstrate the effectiveness of this approach, the underlying idea is not limited to these tasks. We believe extending CompDiff-BP to these broader applications is an exciting direction for future work.

[1] Mishra, et al. "Generative skill chaining: Long-horizon skill planning with diffusion models." Conference on Robot Learning. 2023. [2] Skreta, et al. “Feynman-Kac Correctors in Diffusion: Annealing, Guidance, and Product of Experts.” International conference on machine learning. 2025. [3] Du, et al. "Reduce, reuse, recycle: Compositional generation with energy-based diffusion models and mcmc." International conference on machine learning. 2023.

Reviewer_AYyAOpenReview ↗

Thank you for the response

Some of the concerns have been addressed. But the major limitation about theoretical analysis of the proposed algorithm is still not addressed. The paper applies LBP at every reverse-diffusion step, where the factor graph and posterior change with the current noisy state. While Yedidia et al. (2005) establish the relationship between LBP fixed points and stationary points of the Bethe free energy, this analysis does not characterize the behavior of the proposed procedure, which performs a fixed number of message-passing iterations at each diffusion step. The additional experiments provide empirical evidence of improved marginal accuracy with more BP rounds, but do not address this theoretical gap. The authors should build on existing analyses of BP convergence and message-error propagation, such as Ihler et al. (2005), to characterize the approximation error of finite-round BP and how these errors propagate across reverse-diffusion steps, ultimately affecting the resulting distribution.

References

  1. Yedidia, J. S., Freeman, W. T., and Weiss, Y. (2005). Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms. IEEE Transactions on Information Theory, 51(7), 2282–2312.
  2. Ihler, A. T., Fisher, J. W., and Willsky, A. S. (2005). Loopy Belief Propagation: Convergence and Effects of Message Errors. Journal of Machine Learning Research, 6, 905–936.

We thank the reviewer for the follow-up clarification.

We would like to clarify that the focus of our paper is empirical. LBP is a well-established and practically useful approximate inference algorithm for estimating marginal distributions in graphical models where exact inference is expensive due to large treewidth [1]. Our experiments demonstrate its effectiveness in reconciling independently learned constraint experts during compositional diffusion, while the new exact-enumeration experiments directly quantify the approximation error relative to exact posterior marginals.

We agree that characterizing finite-round BP approximation error and its propagation across reverse-diffusion steps is an interesting theoretical direction. Existing analyses, such as Yedidia et al. (2005) and Ihler et al. (2005), study LBP fixed points, convergence, and message errors. However, extending these results to our setting, which involves arbitrary learned constraint potentials and changing posteriors across diffusion steps, would require substantial additional theoretical work beyond the scope of this paper.

We have added references to these theoretical analyses in Section 3.2 and further clarified this future research direction in Section 6 of the revised manuscript.

[1] Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.