Unsupervised Recursive Reasoners for Combinatorial Problems

Neural solvers for combinatorial problems derive their problem-solving ability from repeated computational steps, which makes the structure of these recursive models a central design decision. Two corresponding families have developed largely separately. Data-free diffusion-style samplers are trained with energy-based objectives and acquire effective depth by reversing an annealed stochastic forward process step-by-step. Recursive reasoning models acquire depth through weight-shared recurrence and are trained almost exclusively with supervision. We bridge these paradigms and introduce a data-free recursive reasoning model trained via an energy that scores solution quality. It employs hierarchical recurrence without diffusion-derived process rewards or entropy regularization. Using graph coloring as a controlled testbed, we hold the total compute budget fixed and ask how much of it should be spent on stochastic resampling rather than on deterministic recurrence, how deep gradients should propagate through the recurrence when trading activation memory against gradient bias, and whether diffusion-derived process rewards improve credit assignment over terminal rewards. Our results suggest that parts of the diffusion-derived training machinery can be omitted without degrading performance in the studied settings, while recursive depth provides an effective axis for test-time scaling.