Belief Propagation enables Compositional Diffusion for Constraint Reasoning

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.