Convex Compositional Reasoning Models
For researchers in compositional reasoning and energy-based models, this work provides a principled solution to the non-convexity bottleneck, enabling scalable generalization to larger problems.
The paper identifies non-convex energy landscapes as the key bottleneck in compositional reasoning, not composition itself. It introduces Convex Compositional Energy Minimization (CCEM), which uses input-convex neural networks and convex relaxation to enable deterministic optimization, achieving zero-shot transfer to larger problem instances without retraining.
Compositional energy-based models can generalize to larger combinatorial reasoning problems by reusing a learned factor energy across many local constraints. In our paper, we show that a key bottleneck in compositional reasoning is not composition itself, but the non-convex geometry of the learned energy landscape. To solve this problem, we introduce Convex Compositional Energy Minimization (CCEM), a framework that parameterizes each factor with an input-convex neural network and optimizes the composed energy over a tight convex relaxation of the feasible set. Because convexity is preserved under summation, the global relaxed objective remains convex, enabling deterministic projected first-order optimization. CCEM is trained in two stages: factor-level contrastive learning to shape local energy basins, followed by end-to-end refinement through an unrolled projected solver. Our experiments show that our models trained on small subproblems or a single problem size transfer to larger instances without retraining.