Research map / Probabilistic and scientific modeling / Molecules and proteins
Generalizable Reasoning through Compositional Energy Minimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes compositional energy-based reasoning: train EBMs on single-clause/row/edge subproblems with diffusion+contrastive losses, sum energies at test time, and sample with Parallel Energy Minimization (PEM) to generalize to larger N-Queens, 3-SAT, graph coloring and crossword instances.
Problem
Neural reasoning models trained end-to-end map inputs to solutions and generalize poorly to problems larger or more complex than those seen in training, as in N-Queens, 3-SAT, graph coloring and crosswords.
Approach
Learn an energy function over solutions of small subproblems (one row, one clause, one edge, one word), then at test time compose them by summing energies over all subproblems of a larger instance, and sample with a particle-based resampling optimizer (PEM) that discards local minima.
Key results
- On 8-queens, the method generates 97 valid solutions out of 100 samples, while the best state-of-the-art combinatorial solver finds at most 41.
- On 3-SAT with 50 variables and 218 clauses, it solves 43 of 100 instances versus 37 for NSNet (T=500).
- On crosswords, it reaches an 80.4% grid completion rate compared with 78.0% for Tree of Thought, though ToT has higher word success (60.0% vs 50.5%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PEM instead of reverse diffusion for sampling (ablation) | Compositional EBM · N-Queens | sample quality | Helped |
| Increase the number of particles during sampling (ablation) | Compositional EBM · N-Queens (8-queens) | correct instances | Helped |
| Use diffusion and contrastive losses together instead of either loss alone (ablation) | Compositional EBM · 3-SAT | correct instances: 11 with diffusion loss only; 0 with contrastive loss only; 57 with both | Helped |
| Use PEM instead of baseline samplers (ablation) | Compositional EBM · 3-SAT | correct instances: 91 out of 100; baseline samples find at most one | Helped |
| Finetune the composed model (ablation) | Compositional EBM · 3-SAT | overall performance | Helped |
| Increase the number of particles from 8 to 1024 (ablation) | Compositional EBM · Graph coloring | conflicting edges: 15.0 to 8.0 | Helped |
| Use PEM instead of UHMC (ablation) | Compositional EBM · Graph coloring | conflicting edges: 12.3 with UHMC; 8.0 with PEM | Helped |
| Use contrastive loss only instead of diffusion loss only (ablation) | Compositional EBM · Graph coloring | conflicting edges: 15.0 with diffusion loss only; 9.0 with contrastive loss only | Helped |
| Increase the number of particles during sampling (ablation) | PEM · Holme-Kim small graph coloring | conflicting edges: 10.60(2.70) at 128; 7.04(3.64) at 1024 | Mixed |
| Increase the number of particles during sampling (ablation) | PEM · Holme-Kim large graph coloring | conflicting edges: 59.00(5.24) at 128; 55.57(4.58) at 2048 | Helped |
| Increase the number of optimization timesteps (ablation) | PEM · Holme-Kim small graph coloring | conflicting edges: 6.98(2.19) at 20; 6.51(2.35) at 1000 | Mixed |
| Increase the number of optimization timesteps (ablation) | PEM · Holme-Kim large graph coloring | conflicting edges: 44.27(7.29) at 20; 42.71(3.93) at 1000 | Helped |
Surprising findings
- Composing per-clause or per-row energies can outperform specialized combinatorial optimization solvers trained directly on full instances, even though the subproblem model never saw full instances.
- Training with only contrastive loss or only diffusion loss performed much worse than combined losses on 3-SAT (0 and 11 correct instances versus 57 with both).
Limitations
- Assumes a Gaussian starting distribution and models optimization as Gaussian increments, limiting non-Gaussian objectives and initializations.
- Graph coloring solutions remain suboptimal, with conflicting edges still present on larger graphs.
- Composition for N-Queens imposes a constraint that every row, column and diagonal has a queen, which the original problem does not require, requiring careful model design.
Experimental setup
Datasets: SATLIB COLOR benchmark Mini Crosswords Crosswords QA cnfgen-generated random 3-SAT random graphs (Erdos-Renyi, Holme-Kim, regular expander, Paley, complete)
Benchmarks: N-Queens (8-queens) SATLIB 3-SAT COLOR benchmark random graph coloring distributions Mini Crosswords
Metrics: correct instances average queens placed satisfied clauses conflicting edges word success rate grid completion rate
Baselines: LWD GFlowNets DIFUSCO Fast T2T NeuroSAT NSNet GCN GAT XLVIN GNN-GCP Gemini 2.5 Pro DeepSeek R1
Builds on: denoising diffusion energy-based models sequential Monte Carlo Fast T2T NSNet
Closest papers by meaning
- Learning Iterative Reasoning through Energy Diffusion (ICML 2024 · similarity 0.89)
- Compositional Generalization from Learned Skills via CoT Training: A Theoretical and Structural Analysis for Reasoning (ICLR 2026 · similarity 0.86)
- Compositional Risk Minimization (ICML 2025 · similarity 0.85)
- Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization (NeurIPS 2025 · similarity 0.85)
- Prismatic Synthesis: Gradient-based Data Diversification Boosts Generalization in LLM Reasoning (NeurIPS 2025 · similarity 0.85)
- When does compositional structure yield compositional generalization? A kernel theory. (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.