Generalizable Reasoning through Compositional Energy Minimization

Alexandru Oarga, Yilun Du · 2025

Read Generalizable Reasoning through Compositional Energy Minimization by Alexandru Oarga, Yilun Du (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20607.txt.

Introduction

Alexandru Oarga and Yilun Du propose compositional energy minimization as a route to reasoning that generalizes to harder problems than those seen in training. End-to-end reasoning models learn useful heuristics but often fail outside their training distribution. Their approach instead learns energy landscapes over the solution spaces of smaller, tractable subproblems, one energy function per subproblem type.

At test time the subproblem energies combine into a global landscape for a full problem, and extra constraints can be added during inference to build landscapes for problems of growing difficulty. A parallel energy minimization procedure improves the quality of samples drawn from the combined landscape. Across a wide set of reasoning problems, the method outperforms leading rivals and generalizes to larger, more complex instances.

Catalog record

CREATORAlexandru Oarga, Yilun Du
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20607

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Generalizable Reasoning through Compositional Energy Minimization Alexandru Oarga, Yilun Du Abstract Generalization is a key challenge in machine learning, specifically in reasoning tasks, where models are expected to solve problems more complex than those encountered during training. Existing approaches typically train reasoning models in an end-to-end fashion, directly mapping input instances to solutions. While this allows models to learn useful heuristics from data, it often results in limited generalization beyond the training distribution. In this work, we propose a novel approach to reasoning generalization by learning energy landscapes over the solution spaces of smaller, more tractable subproblems. At test time, we construct a global energy landscape for a given problem by combining the energy functions of multiple subproblems. This compositional approach enables the incorporation of additional constraints during inference, allowing the construction of energy landscapes for problems of increasing difficulty. To improve the sample quality from this newly constructed energy landscape, we introduce Parallel Energy Minimization (PEM). We evaluate our approach on a wide set of reasoning problems. Our method outperforms existing state-of-the-art methods, demonstrating its ability to generalize to larger and more complex problems. Project website can be found at: https://alexoarga.github.io/compositional_reasoning/ † † footnotetext: Corresponding author: [email protected] 1 Introduction Being able to solve complex reasoning problems, such as logical reasoning, combinatorial puzzles and symbolic manipulation, is one of the key challenges in machine learning. This is particularly interesting because it requires models to go beyond pattern recognition. For a model to successfully perform reasoning tasks, it is expected to be able to generalize to unseen distributions during test time. That is, they are expected to solve not only problems similar to those encountered during training, but also to be able to generalize to novel conditions and distributions bottou2014machine . The standard paradigm in machine learning for solving reasoning tasks is to train models end-to-end to map inputs to outputs. During training, models are exposed to a large number of solutions and learn statistical heuristics that allow them to solve similar problems. This contrasts with human reasoning, where we first learn the rules and constraints governing a problem, and then apply them in a compositional manner to arrive at a solution. Notably, humans are able to solve such problems without having seen an exact solution before. Moreover, when prompted with harder tasks, we can invest more time, effectively searching for a solution, rather than relying on heuristics ackerman2017meta ; kahneman2011thinking . Train Evaluation \setchessboard boardfontsize=6.6pt,labelfontsize=6pt \newchessgame \chessboard [ printarea=a1-h1, setpieces=, color=red!70, showmover=false, label=false, pgfstyle=border, linewidth=0.2em, ] \setchessboard boardfontsize=6.6pt,labelfontsize=6pt \newchessgame \chessboard [ printarea=a1-h1, setpieces=qb1, color=red!70, showmover=false, label=false, pgfstyle=border, linewidth=0.2em, ] \setchessboard boardfontsize=6.6pt,labelfontsize=6pt \newchessgame \chessboard [ setpieces=, color=red!70, showmover=false, label=false, pgfstyle=border, linewidth=0.2em, ] \setchessboard boardfontsize=6.6pt,labelfontsize=6pt \newchessgame \chessboard [ setpieces=qf8,qd7,qg6,qa5,qb3,qe2,qc1,qh4, color=red!70, showmover=false, label=false, pgfstyle=border, linewidth=0.2em, ] Figure 1 : Compositional Generalizable Reasoning. We formulate reasoning as optimization problem with inputs \bm{x} and solutions \bm{y} . By combining multiple optimization objectives, we can generalize to larger problem instances (bottom) than those seen during training (top). This enables us to solve a complex instance of N-queens (left) or a more complex instance of graph coloring (right). In this work, we present an approach to reasoning where the overall process is cast as an optimization problem du2022learning . Specifically, we learn an energy function E_{\theta}(\bm{x},\bm{y}) across all possible solutions \bm{y} of the problem, where \bm{x} are the given conditions of the problem. This energy function is learned such that valid solutions are assigned lower energy, while invalid solutions receive higher energy. Reasoning corresponds to minimizing the energy function to find low-energy solutions. Harder problems can be solved by spending more time reasoning and minimizing the optimization objective. To solve more complex problems than those seen during training (see Figure 1 ), we can jointly reason and minimize the sum of several optimization objectives at the same time. For instance, in logical reasoning, we can learn the energy landscape of individual clauses, and then optimize over multiple clauses simultaneously. This composition of energy objectives enables the model to find assignments that satisfy all clauses simultaneously, enabling it to solve larger, more complex problems. However, combining multiple objectives makes the landscape increasingly complex and introduces local minima, making it hard to optimize. To address this, we propose a parallel strategy where we use a system of particles for optimization. In this setup, we leverage the energy function as a resampling mechanism to improve the quality of the samples and avoid local minima that attract particles. This approach improves exploration and ultimately makes optimization more effective. We illustrate the applicability of our approach across a set of difficult reasoning problems, including the N-Queens, 3-SAT and the Graph Coloring. We compare against domain-specific state of the art combinatorial optimization models, and show that our approach outperforms them in terms of solution quality and generalization to larger and more complex problems. We further show that, by adjusting the computational budget, we can adapt the model to solve more complex problems. Finally, ablation studies show that our training strategy leads to improved results and that our sampling strategy is able to produce better quality solutions than existing samplers. Overall, the contributions of this work are threefold. First, we propose a compositional approach to reasoning generalization, where we combine energy landscapes during inference to solve more complex problems. Second, we introduce a new sampling strategy, Parallel Energy Minimization (PEM), a particle-based optimization strategy that enables us to effectively optimize composed energy functions to solve hard reasoning tasks. Finally, we illustrate the efficacy of our approach empirically across a wide set of reasoning tasks, outperforming many existing combinatorial optimization approaches in generalization. 2 Related work Reasoning as Optimization. Reasoning includes multiple cognitive processes, such as logical inference, decision-making, planning, and scheduling. Many of these can be formulated as optimization problems, where the goal is to find variable assignments that minimize an objective function under certain constraints. Prior works have integrated logical reasoning into neural networks through differentiable relaxations of SAT evans2018learning and MAXSAT solvers wang2019satnet , differentiable theorem proving rocktaschel2017end ; minervini2020learning , probabilistic logic manhaeve2018deepproblog , differentiable logic rules shengyuan2023differentiable , and gradient-based methods for discrete distributions niepert2021implicit . Other approaches incorporate continuous optimization directly into models via differentiable convex agrawal2019differentiable , quadratic amos2017optnet or integer solvers thayaparan2024differentiable . These methods, however, often target specific domains or rely on strong assumptions. Another line formulates reasoning using general-purpose optimization frameworks. For instance, rubanova2021constraint ; comas2023inferring simulate physical dynamics using energy minimization. Latent space optimization has been used in variational methods for molecule generation gomez2018automatic and the Traveling Salesman Problem (TSP) hottung2021learning . More related to our work, du2022learning learns energy functions backpropagating through optimization steps or with diffusion-based losses du2024learning . Nonetheless, most of these approaches adopt end-to-end methods to learn reasoning tasks, limiting their generalization ability. We instead propose a compositional strategy, combining energy landscapes learned on subproblems to tackle larger tasks. Finally, recent approaches focus on learning-based methods for Combinatorial Optimization (CO), which aim to reduce the computational cost by generating near-optimal solutions. Graph Neural Networks (GNNs) are the standard in this domain due to their ability to represent variable-constraint relations. Recent works have employed GNNs to directly predict solutions cappart2023combinatorial ; joshi2019efficient ; schuetz2022combinatorial , learning discrete diffusion over graphs sun2023difusco

Read the complete text