Literature
Display
← All papers

Learning Iterative Reasoning through Energy Diffusion

Yilun Du · Jiayuan Mao · Joshua B. Tenenbaum

· ICML 2024 ↗

Reasoning7 min text · CondensedOriginal paper ↗
Contents

Overview

The supplement provides data-generation and training details for continuous reasoning, discrete reasoning, and planning, followed by the complete task-specific model architectures.

At a glance

IRED learns a sequence of noise-conditioned energy functions whose low-energy outputs approximate solutions to reasoning tasks. Inference optimizes the candidate through progressively sharper landscapes, and training combines denoising-gradient supervision with a contrastive preference for correct labels. The approach improves generalization on several harder matrix, Sudoku, connectivity, and graph-planning datasets. More inference steps can help, but low learned energy is not a certificate of correctness, and the planning metric checks the first move rather than complete path execution.

1 Introduction

Many reasoning problems can be expressed as selecting an output that satisfies constraints. IRED learns that selection objective from paired inputs and solutions instead of requiring a symbolic task specification. Its central design is an annealed sequence of learned energy landscapes plus training that avoids differentiating through a full optimization rollout. Computation at inference can be increased for difficult instances. The scope is supervised synthetic reasoning tasks; theorem proving and general decision-making motivate the framework but are not demonstrated here.

Refer to caption
Figure 1: Reasoning as Energy Diffusion – IRED formulates reasoning problem with inputs 𝒙{\bm{x}} and output 𝒚{\bm{y}}, as an energy minimization problem over a learned energy function. It can be trained stably for a wide variety of reasoning tasks and achieves strong generalization to harder problem instances, through adaptive computation in the optimization process.

2 Related Work

Du et al. (2022) previously used iterative energy minimization for learned reasoning. IRED combines that formulation with the noise-conditioned supervision of denoising diffusion models (Ho et al., 2020). It differs from direct diffusion prediction by performing several optimization steps on each landscape rather than relying on one learned reverse transition per stage.

Other approaches insert task-specific solvers or use recurrent computation and learned halting. IRED shares an optimization paradigm across tasks but changes its encoder for matrices, boards, and graphs. Its claimed flexibility therefore does not mean one unchanged network solves every domain.

Refer to caption
Figure 2: IRED Learns a Sequence of Energy Landscapes. During inference time, we optimize for 𝒚∗{\bm{y}}^{*} that minimizes the energy function, and we gradually increase the complexity of the energy optimization problem. The energy functions are trained with a combination of score function supervision and energy landscape supervision.

3 Learning Iterative Reasoning through Energy Optimization

Training learns energies over an input and candidate output. Inference repeatedly refines the output, with the intended energy minimum corresponding to a valid solution. The annealing and contrastive components address difficult optimization and inadequately shaped learned objectives.

 Input: Problem Dist pD​(𝒙,𝒚)p_{D}({\bm{x}},{\bm{y}}), EBM Eθ​(⋅)E_{\theta}(\cdot), Noise Schedules {σk}\{\sigma_{k}\}, Corruption Function c⁡(⋅)c(\cdot), Landscapes kk.
 while not converged do
  ⊳\triangleright Supervise the Energy Landscape through Denoising:
  𝒙i,𝒚i∼pD,ϵ∼𝒩⁡(0,1),k∼{1,…,K}{\bm{x}}_{i},{\bm{y}}_{i}\sim p_{D},\epsilon\sim\mathcal{N}(0,1),k\sim\{1,\ldots,K\}
  𝒚i~←1−σk2​𝒚i+σk​ϵ\tilde{{\bm{y}}_{i}}\leftarrow\sqrt{1-\sigma_{k}^{2}}{\bm{y}}_{i}+\sigma_{k}\epsilon
  ℒMSE←‖∇yEθ​(𝒙i,𝒚i~,k)−ϵ‖2\mathcal{L}_{\text{MSE}}\leftarrow\|\nabla_{y}E_{\theta}({\bm{x}}_{i},\tilde{{\bm{y}}_{i}},k)-\epsilon\|^{2}
  ⊳\triangleright Shape the Energy Landscape Contrastively:
  𝒚i−←c⁡(𝒚i){\bm{y}}^{-}_{i}\leftarrow c({\bm{y}}_{i})
  𝒚i~−←1−σk2​𝒚i−+σk​ϵ\tilde{{\bm{y}}_{i}}^{-}\leftarrow\sqrt{1-\sigma_{k}^{2}}{\bm{y}}^{-}_{i}+\sigma_{k}\epsilon
  Ei+←Eθ​(𝒙i,𝒚i~,k)E^{+}_{i}\leftarrow E_{\theta}({\bm{x}}_{i},\tilde{{\bm{y}}_{i}},k); Ei−←Eθ​(𝒙i,𝒚~i−,k)E^{-}_{i}\leftarrow E_{\theta}({\bm{x}}_{i},\tilde{{\bm{y}}}^{-}_{i},k)
  ℒContrast←−log⁡(e−Ei+e−Ei++e−Ei−)\mathcal{L}_{\text{Contrast}}\leftarrow-\log\left(\frac{e^{-E^{+}_{i}}}{e^{-E^{+}_{i}}+e^{-E^{-}_{i}}}\right)
  ⊳\triangleright Optimize objective ℒMSE+ℒContrast\mathcal{L}_{\text{MSE}}+\mathcal{L}_{\text{Contrast}} wrt θ\theta:
  Δ​θ←∇θ(ℒMSE+ℒContrast)\Delta\theta\leftarrow\nabla_{\theta}(\mathcal{L}_{\text{MSE}}+\mathcal{L}_{\text{Contrast}})
  Update θ\theta based on Δ​θ\Delta\theta using Adam optimizer
 end while
Algorithm 1 IRED Training
 Input: Input task 𝒙i{\bm{x}}_{i}, Step Sizes λk\lambda_{k}, Number of Landscapes KK, EBM Eθ​(⋅)E_{\theta}(\cdot), Optimization Steps TT.
 𝒚~i∼𝒩⁡(0,1)\tilde{{\bm{y}}}_{i}\sim\mathcal{N}(0,1)
 for each landscape k=1k=1 to KK do
  for run T steps of optimization t=1t=1 to TT do
   ⊳\triangleright Optimize candidate solution 𝐲~i\tilde{{\bm{y}}}_{i} with gradient:
   𝒚~i′←𝒚~i−λk​∇𝒚Eθ​(𝒙i,𝒚~i,k)\tilde{{\bm{y}}}_{i}^{\prime}\leftarrow\tilde{{\bm{y}}}_{i}-\lambda_{k}\nabla_{\bm{y}}E_{\theta}({\bm{x}}_{i},\tilde{{\bm{y}}}_{i},k)
   ⊳\triangleright Check if the gradient descent step decreases energy:
   if Eθ​(𝒙i,𝒚~i,k)>Eθ​(𝒙i,𝒚~i′,k)E_{\theta}({\bm{x}}_{i},\tilde{{\bm{y}}}_{i},k)>E_{\theta}({\bm{x}}_{i},\tilde{{\bm{y}}}_{i}^{\prime},k) then
    𝒚i←𝒚i′{\bm{y}}_{i}\leftarrow{\bm{y}}_{i}^{\prime}
   end if
  end for
  ⊳\triangleright Scale optimized candidate solution:
  𝒚~i←1−σk21−σk−12​𝒚~i\tilde{{\bm{y}}}_{i}\leftarrow\frac{\sqrt{1-\sigma_{k}^{2}}}{\sqrt{1-\sigma_{k-1}^{2}}}\tilde{{\bm{y}}}_{i}
 end for
 return 𝒚=𝒚~i{\bm{y}}=\tilde{{\bm{y}}}_{i}
Algorithm 2 IRED prediction algorithm

3.1 Reasoning as Annealed Energy Minimization

Inference initializes a candidate from Gaussian noise and minimizes its learned energy by gradient descent. Earlier energy-based reasoning trained through the whole optimization trajectory; IRED instead supervises energy gradients at corrupted ground-truth labels. This removes the need to backpropagate through many inference updates during training, though energy-gradient computation itself still requires differentiation. The method’s equations minimize energy; a contrary “maximizes” phrase in the introduction is not the operative objective.

Equations 1–3
𝒚=arg​min𝐲⁡Eθ​(𝐱,𝐲).{\bm{y}}=\argmin_{{\bm{y}}}E_{\theta}({\bm{x}},{\bm{y}}). (1)
𝒚t=𝒚t−1−λ​∇𝒚Eθ​(𝒙,𝒚t−1),{\bm{y}}^{t}={\bm{y}}^{t-1}-\lambda\nabla_{{\bm{y}}}E_{\theta}({\bm{x}},{\bm{y}}^{t-1}), (2)
ℒMSE​(θ)=‖∇𝒚Eθ​(𝒙,𝒚+ϵ)−ϵ‖2,ϵ∼𝒩⁡(0,1).\mathcal{L}_{\text{MSE}}(\theta)=\|\nabla_{{\bm{y}}}E_{\theta}({\bm{x}},{\bm{y}}+\epsilon)-\epsilon\|^{2},\quad\epsilon\sim\mathcal{N}(0,1). (3)

3.2 Learning Sequence of Annealed Energy Landscapes

Noise conditioning produces ten landscapes, from smoother high-noise objectives to sharper low-noise ones. At each stage, gradients learn to predict the noise added to a scaled target. Inference optimizes repeatedly at one level, rescales its candidate, and passes it to the next. The schedule eases search empirically, without guaranteeing a convex landscape or global optimum.

Equations 4–5
e−Eθk​(𝒙,𝒚)∝∫𝒚∗p⁡(𝒚∗|x)⋅𝒩⁡(𝒚,1−σk2​𝒚∗,σk2​𝐈)e^{-E^{k}_{\theta}({\bm{x}},{\bm{y}})}\propto\int_{{\bm{y}}^{*}}p({\bm{y}}^{*}|x)\cdot\mathcal{N}({\bm{y}};\sqrt{1-\sigma_{k}^{2}}{\bm{y}}^{*},\sigma^{2}_{k}\mathbf{I}) (4)
ℒMSE​(θ)=‖∇𝒚Eθ​(𝒙,1−σk2​𝒚∗+σk​ϵ,k)−ϵ‖2,\mathcal{L}_{\text{MSE}}(\theta)=\|\nabla_{{\bm{y}}}E_{\theta}({\bm{x}},\sqrt{1-\sigma_{k}^{2}}{\bm{y}}^{*}+\sigma_{k}\epsilon;k)-\epsilon\|^{2}, (5)

3.3 Shaping the Energy Landscape

Denoising supervision constrains local gradients but may leave incorrect low-energy solutions elsewhere. A contrastive loss compares a correct label with a corrupted negative under the same sampled noise, favoring the correct candidate. Sharing noise reduces comparison variance. This sampled loss encourages better energy ordering; it cannot enforce global correctness over every possible output.

3.4 Combined Training and Inference Paradigms

The combined objective and complete pseudocode are retained. Training uses a cosine noise schedule and ten landscapes. Inference takes a specified number of gradient steps per landscape and accepts steps that lower energy. The experiments vary that step budget; they do not establish an automatically calibrated stopping rule that detects every wrong solution. Composing extra constraints or representing multiple valid outputs is discussed as a possible extension.

4 Experiments

Evaluation covers matrix operations, symbolic and visual Sudoku, graph connectivity, and graph path decisions. The emphasis is generalization to harder inputs and the effect of additional inference computation.

4.1 Continuous Algorithmic Reasoning

Tasks and comparison. Addition, low-rank completion with half the entries masked, and inversion use 20 × 20 matrices. Harder tests increase value magnitudes or worsen conditioning, rather than increasing matrix dimensions. Models share comparable encoder architectures. Continuous negatives are formed by corrupting labels and taking two energy-optimization steps.

Results. IRED’s harder-test mean squared errors are 0.0020 for addition, 0.2054 for completion, and 0.2063 for inversion, versus IREM’s 0.0021, 0.2074, and 0.2083. The advantages over the previous energy method are modest on these aggregate errors, though larger than several other comparisons. Increasing inversion optimization steps from ten to forty changes harder-test error from 0.2110 to 0.2063; same-distribution error changes from 0.0096 to 0.0095.

Diagnostics. The error maps and energy cross-sections illustrate increasing accuracy and sharper landscapes. Ablations favor gradient optimization, repeated refinement, and contrastive shaping. These visual slices and finite tests do not demonstrate global constraint recovery.

Same Harder
Task Method Difficulty Difficulty
Addition Feedforward 0.0448 0.7029
Recurrent 0.3610 2.6133
Programmatic 0.0111 0.3446
Diffusion 0.0071 0.5931
IREM 0.0003 0.0021
IRED (ours) 0.0002 0.0020
Matrix Feedforward 0.0203 0.2720
Completion Recurrent 0.0266 0.3285
Programmatic 0.0203 0.2637
Diffusion 0.0219 0.2142
IREM 0.0183 0.2074
IRED (Ours) 0.0174 0.2054
Matrix Feedforward 0.0112 0.2150
Inverse Recurrent 0.0109 0.2123
Programmatic 0.0124 0.2209
Diffusion 0.0115 0.2132
IREM 0.0108 0.2083
IRED (Ours) 0.0095 0.2063
Table 1: Continuous Algorithmic Reasoning. Test evaluation performance on continuous algorithmic tasks. Inputs and outputs are 20 by 20 matrices. Error is reported using elementwise mean square error. Models are evaluated on test problems drawn from the training distribution (same difficulty) and a harder test distribution (harder difficulty). IRED outperforms comparisons.
Refer to caption
Figure 3: Optimized Solutions Across Landscapes – Error maps of intermediate optimized solutions. Optimized solutions at earlier landscapes are less accurate than later ones.
Refer to caption
Figure 4: Energy Landscape – Predicted energy values for 𝒚{\bm{y}} and the corresponding MSE distance of 𝒚{\bm{y}} from the problem solution across different landscapes on the matrix inverse task. The earlier energy landscapes are smoother than the later ones.
Opt. Steps Same Difficulty Harder Difficulty
10 0.0096 0.2110
20 0.0096 0.2100
30 0.0096 0.2090
40 0.0095 0.2063
Table 2: Continuous-Space Reasoning Performance vs Reasoning Steps. More reasoning steps in IRED at inference time substantially improve generalization to harder difficulty tasks on the matrix inverse task. IRED is trained with 10 energy landscapes.
Gradient Optimization Contrastive Same Harder
Descent Refinement Shaping Difficulty Difficulty
No No No 0.0158 0.2223
Yes No No 0.0097 0.2135
Yes Yes No 0.0097 0.2113
Yes Yes Yes 0.0095 0.2063
Table 3: Continuous Ablations – Ablations of proposed components of IRED on performance on the matrix inverse task. Leveraging gradient descent to optimize energy functions, using multiple steps of optimization at each energy landscape and contrastively shaping the energy landscape with ground truth labels all improve the performance on the Inverse task.

4.2 Discrete-Space Reasoning

Sudoku and connectivity. Sudoku training uses boards with 31–42 given cells; the harder dataset has 17–34. IRED achieves 99.4% standard-test accuracy and 62.1% on the harder set, compared with RRN’s 99.8% and 28.6%. Thus it leads the harder comparison while the recurrent baseline is slightly better in-distribution. Visual Sudoku replaces symbolic entries with digit images and obtains 98.3%/46.6%. Connectivity grows from at most twelve nodes to eighteen, with accuracy 99.1%/93.8%.

Computation and failure. Additional optimization particularly helps harder Sudoku. The ablation’s harder accuracy rises from 35.0% without the three proposed components to 62.1% with all of them. Nevertheless, the authors observe invalid boards assigned lower energy than the correct solution. More optimization can then prefer the wrong answer, so energy should not be treated as an exact satisfiability test. The full intermediate boards and performance curves are retained.

Task Method Test Harder
Dataset Dataset
Sudoku IREM 93.5% 24.6%
Diffusion 66.1% 10.3%
SAT-Net 98.3% 3.2%
RRN 99.8% 28.6%
IRED (ours) 99.4% 62.1%
Visual Sudoku SAT-Net 63.2% 0.0%
RRN 99.8% 28.6%
IRED (ours) 98.3% 46.6%
Connectivity IREM 94.3% 89.8%
Diffusion 61.6% 61.3%
IRED (ours) 99.1% 93.8%
Table 4: Discrete Reasoning Performance. We evaluate models on the Sudoku task and the connectivity task. Sudoku:” the harder dataset has between 17 to 34 entries given, while models are trained with 31 to 42 entries given. Connectivity: the harder graphs have at most 18 nodes while the training graphs have only 12.
Refer to caption
Figure 5: Optimized Boards Across Landscapes – Plot of the minimal energy board across energy landscapes, given the same initial board. Later energy landscapes lead to more accurate boards. We highlight inconsistent entries in red.
Original figure
Figure 6: Sudoku Performance with Optimization Steps – Generalization to harder Sudoku problems significantly improves with a larger number of optimization steps in Sudoku.
Gradient Optimization Contrastive Same Harder
Descent Refinement Shaping Difficulty Difficulty
No No No 97.0% 35.0%
Yes No No 98.8% 45.1%
Yes Yes No 99.3% 59.7%
Yes Yes Yes 99.4% 62.1%
Table 5: Discrete Reasoning Ablations – Ablations of proposed components of IRED on performance on the Sudoku task. Leveraging gradient descent to optimize energy functions, using multiple steps of optimization at each energy landscape and contrastively shaping the energy landscape with ground truth labels all improve the performance.

4.3 Planning

The planner receives a directed graph, start, and goal and predicts a node sequence using a spatial-temporal graph encoder. Training graphs have fifteen nodes and harder tests twenty-five. Evaluation counts whether the first predicted action decreases shortest-path distance; it does not report success for executing the whole generated path or repeated closed-loop episodes.

IRED achieves 92.6% and 91.9% first-action success on standard and harder graphs, versus IREM’s 90.4%/88.4% and diffusion’s 45.2%/46.9%. Multi-step optimization and contrastive shaping improve the ablations. Gradient descent alone slightly lowers the first ablated score, so the benefit belongs to the tested combination rather than every component independently improving every task. Figure 7 shows the next-node distribution concentrating during optimization.

Task Method Test Harder
Dataset Dataset
Shortest Path IREM 90.4% 88.4%
Diffusion 45.2% 46.9%
IRED (ours) 92.6% 91.9%
Table 6: Planning Performance. Test evaluation performance on the shortest path task. The harder tasks consists of graphs of size 25 while models are trained on graphs of size 15.
Refer to caption
Figure 7: Optimized Plans Across Landscapes – Plot of next action prediction in plans across energy landscapes. In each visualization, the green/red nodes indicate start/goal nodes with connections between nodes indicated with arrows. The darkness of a node indicates the score for selecting the corresponding node as the next node to move to in the predicted plan. As landscapes are sequentially optimized, the correct next action is selected.
Gradient Optimization Contrastive Same Harder
Descent Refinement Shaping Difficulty Difficulty
No No No 80.8% 80.4%
Yes No No 80.7% 79.1%
Yes Yes No 88.6% 87.9%
Yes Yes Yes 92.6% 91.9%
Table 7: Path Planning Ablations – Ablations of proposed components of IRED on performance on the path planning task. Using multiple steps of optimization at each energy landscape and contrastively shaping the energy landscape with ground truth labels both improve path planning performance.

5 Conclusion and Discussions

Repeated energy optimization improves selected learned reasoning tasks and permits an inference-compute tradeoff. It still requires many gradient evaluations and is likely slower than specialized solvers when exact task specifications are available. Gaussian annealing is fixed, external intermediate memory is absent, and learned low-energy errors remain possible. Faster initialization, learned schedules, richer memory, hybrid planning, and reward-supervised policies are proposed directions rather than results established by these experiments.

Acknowledgements

Support comes from US research agencies, MIT programs and the MIT–IBM Watson AI Lab, the Simons Center, and a graduate fellowship. The authors state that conclusions are their own.

Impact Statement

The authors identify no immediate negative social impact from the present evaluation on simple standard datasets. Broader deployment effects are not empirically studied in this paper.

Appendix A Experimental Details

Continuous tasks. Models train for about 50,000 iterations with batch size 2,048, Adam at 10⁻⁴, and one RTX 2080, taking roughly two hours. Evaluation uses 20,000 problems. Sudoku uses 50,000 iterations and batch size 64 on the same GPU class.

Graph generation. Nodes are sampled in a unit square and connected to nearby points with randomized out-degree. Connectivity uses degree range 1 to n/2; planning uses 1 to n/5. Edges have unit length, and Floyd–Warshall supplies reachability or shortest-distance targets. Graph models train for 100,000 iterations with batch size 512. These structured graph distributions define the tested generalization setting.

Appendix B Model Architectures

Tables 8–12 preserve complete network layer lists. Continuous energy models use three 512-wide layers and a scalar energy output; the diffusion baseline has an output-sized final layer. Sudoku uses a 384-channel residual convolutional model, with output norm producing energy and direct output producing diffusion noise predictions.

Connectivity and planning use relational architectures based on Neural Logic Machines (Dong et al., 2019). Global pooling creates the scalar energy; diffusion removes that pooling to predict per-edge or per-node noise. Planning additionally stacks adjacent-time embeddings for temporal message passing. These architecture adaptations supply substantial task-appropriate structure while retaining the common training/inference framework.

Linear 512
Linear 512
Linear 512
Linear →\rightarrow 1

Table 8: The model architecture for IRED on continuous-space algorithmic reasoning tasks
Linear 512
Linear 512
Linear 512
Linear →\rightarrow Output Dim

Table 9: The model architecture for diffusion baselines on continuous-space algorithmic reasoning tasks.
3x3 Conv2D, 384
Resblock 384
Resblock 384
Resblock 384
Resblock 384
Resblock 384
Resblock 384
3x3 Conv2D, 9

Table 10: The model architecture for IRED and diffusion baselines on the Sudoku task. The energy value is computed using the L2 norm of the final predicted output similar to  (Du et al., 2023), while the output is directly used as noise prediction for the diffusion baseline.
NLM Arity=3, Hidden=64
NLM Arity=3, Hidden=64
Max-Pooling over All Edge Features
Linear, 1

Table 11: The model architecture for IRED and diffusion baselines on the connectivity task. For the diffusion baseline, we simply remove the pooling layer and apply the same linear layer on all edge embeddings to predict the noise value for each entry.
NLM Arity=2, Hideen=64
NLM Arity=2, Hideen=64
Max-Pooling over All Node Features
Linear, 1

Table 12: The model architecture for IRED and diffusion baselines on the shortest-path task. For the diffusion baseline, we simply remove the pooling layer and apply the same linear layer on all node embedding to predict the noise value for each entry.
Concept demonstration

Open image ↗