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 recur- rence, 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.