acceptodds
Under review as a conference paper at ICLR 2027

Learning Recursive Reasoners without Solutions

Abstract

Recursive reasoning models obtain effective depth by repeatedly applying small networks, but are typically trained on ground-truth solutions. We show that such models can instead be learned without solution supervision, using only a black-box verifier or energy function that scores candidate solutions. Our solution-free variant combines latent deterministic recurrence with stochastic refinement of explicit candidate assignments and is trained from terminal verifier feedback alone. On constraint satisfaction and combinatorial optimization problems, such as Graph Coloring, Maximum Independent Set and Sudoku, the resulting models are effective solvers, matching the state of the art. To our knowledge, we provide the first solution-free model to exceed 90% on Sudoku-Extreme. We further find that latent recurrence is a test-time scaling axis complementary to explicit refinement and parallel search, and that the compute-optimal allocation across these axes is problem-dependent. Finally, our results show that more training-time recurrence does not necessarily improve depth extrapolation, whereas truncating credit assignment to the final recursive cycle yields operators that keep improving well beyond their training depth.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
recurrent reasoning models, solution-free learning, combinatorial optimization, constraint satisfaction, test-time scaling, verifier-based learning, reinforcement learning, Tiny Recursion Model

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_u8qoOpenReview ↗
Rating
3(+2)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

This paper introduces uTRM, an unsupervised model for constraint reasoning problems. uTRM trains a Tiny Recursive Model (TRM) using energy-based RL instead of the standard supervised labels. Experiments show that uTRM achieves good performance on MIS, Graph Coloring 5 and Sudoku. Further analysis shows that scaling both the latent recursion and the explicit assignment space recursion are important.

Critical strengths

The paper is easy to follow.

The results on MIS and Sudoku are promising.

The motivation for unsupervised learning makes sense for constraint reasoning problems.

Critical weaknesses
  1. The methodology has limited novelty, at a high level, uTRM (as the name suggests) trains the TRM framework with an unsupervised objective. Since energy-based unsupervised objectives have been used by prior works, this makes the contribution of this paper limited.

  2. Relatedly, the paper can better clarify/present its relationship with existing works.

  • uTRM vs TRM: Line 228 states that uTRM departs from TRM, which along with Figure 1 left, could be interpreted as TRM decodes ZH(H)Z_H^{(H)} and uses it directly as the prediction y. This is not true since TRM also repeats this process and iteratively refines the decoded y. The main difference is therefore how the TRM model is trained (supervised labels vs energy-based RL).
  • uTRM vs diffusion: uTRM is closer to a diffusion process than the paper suggests. In figure 1 (right), the denoiser for the diffusion process can take any architecture form, including the TRM. Interpreting uTRM’s encoder -> H-block -> stochastic decoder as a denoiser for discrete diffusion, the difference also becomes how the model is trained (energy + KL vs energy only).
  1. The experiment has some inconsistent baselines. DiffUCO, OR-Tools, LTFT, SDDS and CAM are included only for MIS but not the others, the paper should discuss why they do not apply to the other benchmarks or include them. ConsFormer and BloGDiT are used for the main comparison for graph coloring, but not used for sudoku despite both papers using Sudoku as a benchmark.

  2. The paper aims to examine the balance between “weight-shared latent recursion within a revision and the number of revisions” as one of its central questions, but this is not well addressed. The main results table includes methods with varying K, H and L but does not effectively show any pattern/tradeoffs between the three axes. Similarly, Fig 2 and 3 shows that scaling both H/T performs the best, but this is not informative about how to balance the two.

Questions for authors

Can you provide more baseline results for Sudoku and Graph Coloring?

Can you provide more insight on the tradeoff between the 3 axes beyond figure 2 and 3?

Minor questions:

A diffusion method SDDS is used in Figure 2 right instead of a transformer baseline, why is that the case?

Line 85 states the paper compares with methods that use “explicit stochastic refinement”, but uTRM itself also does explicit stochastic refinement?

Line 197 states that energy is 0 for feasible assignments, but afterwards immediately states that MIS score includes solution quality rather than feasibility. Does this mean feasible but non-optimal assignments for MIS does not have 0 energy? This should be made clearer

Line 211 what does “factorized prior” refer to?

Line 217 bolded x_t is not defined.

Line 230 it is not clear what “stochastic policy over the next discrete candidate assignment” means. From my understanding, the prediction essentially defines a categorical distribution from which the assignment is sampled from.

4 comments

Thank you for the detailed review. We revised the presentation of our contributions and substantially expanded the experiments, particularly to clarify what recurrence contributes beyond solution-free training and how latent and discrete computation interact.

W1 (limited novelty). We agree that neither energy-based RL nor recursive architectures are individually novel. Our contribution is to establish that reusable recursive reasoning operators can be learned from terminal verifier feedback alone, and to characterize when and why such operators benefit from additional test-time computation.

This goes beyond simply replacing TRM's supervised objective with PPO. We added controlled comparisons with flat Transformers trained using the same terminal-verifier objective (Sec. 4.3, Table 7).

On GC50, a depth-matched 12-layer Transformer initially outperforms uTRM (82.22% vs. 81.33% best-of-20), but gains little from additional inference computation. At 3× training-time inference compute, uTRM reaches 83.00%, compared with 82.47% for the flat Transformer. A parameter-matched 2-layer Transformer is substantially weaker. The same qualitative result holds on an independently generated held-out GC50 split: at 3× compute, uTRM reaches 99.62% of proven-solvable instances, compared with 98.99% for the depth-matched Transformer.

We additionally show that training a reusable operator is not equivalent to training a model that performs well at a fixed depth. Truncating gradients to the final recursive cycle enables substantial inference-depth extrapolation, whereas full backpropagation largely removes this benefit (Sec. 4.4, Fig. 3). We consider this characterization of solution-free recursive computation a central contribution.

W2 (relationship to TRM). We agree that the original Figure 1 insufficiently represented TRM's iterative deep-supervision stages. We revised the figure caption and Secs. 2–3 to clarify this relationship.

TRM can produce multiple increasingly refined predictions, but its recursive computation continues through latent states; the decoded discrete prediction is not sampled and re-embedded as the state of the next refinement stage. uTRM instead performs explicit stochastic transitions between candidate assignments and conditions subsequent computation on the sampled discrete state. It also replaces solution supervision with terminal verifier feedback.

We further added a three-seed latent-state propagation ablation (App. C.10). Resetting both latent states between discrete revisions achieves 81.61 ± 0.13% best-of-20 GC50 accuracy, compared with 77.25 ± 1.80% when carrying only zLz_L, 61.75 ± 8.74% when carrying only zHz_H, and 59.78 ± 19.00% when carrying both. This provides empirical support for the chosen discrete refinement mechanism.

W2 (relationship to diffusion). We agree that a recursive model could be used as the denoiser of a discrete diffusion process. We now explicitly acknowledge this architectural compatibility in Sec. 2.

Our distinction is not that diffusion precludes recursion, but that uTRM learns the refinement process without a prescribed forward corruption process or transition-level reverse-process objective.

We also ablate the diffusion-derived process rewards of SDDS (App. C.2, Table 6). On GC50, removing these rewards does not reduce solution quality, suggesting that a prescribed reverse process is not necessary in this setting. Conversely, the new MIS comparison shows that process rewards do benefit the flat Transformer there, highlighting the task dependence of the training objective.

W3 (inconsistent baselines). We use published baseline results wherever available, which necessarily leads to different comparisons across benchmarks. Extending ConsFormer and BloGDiT to additional settings such as Sudoku-Extreme would require retraining them from scratch. Unfortunately, ConsFormer did not release trained checkpoints, and BloGDiT has not released its implementation, making faithful reproductions infeasible within the scope of this rebuttal. We expanded Sudoku evaluation to the published ConsFormer and BloGDiT Easy and OOD benchmarks (Tables 1 and 5).

For Sudoku-Extreme, we searched for published solution-free neural baselines but could not identify any reporting results on this benchmark. Recent Sudoku-Extreme methods, including energy-based reasoners, rely on solution-dependent training signals. Rather than present an unmatched comparison as equivalent, we include supervised HRM, TRM, and PTRM as reference points and clearly state the differences in supervision and inference protocols.

We also expanded Sudoku-Extreme evaluation to the full 422,786-puzzle test split, achieving 93.90% best-of-100 accuracy without solution labels.

The baseline sets otherwise reflect the domains and published results available: MIS includes SDDS, CAM, DiffUCO, LTFT, and OR-Tools; Graph Coloring and Sudoku include ConsFormer and BloGDiT where results are reported. Unfortunately, ConsFormer did not release checkpoints and BloGDiT did not release code, preventing reliable extensions of these baselines to additional settings. We distinguish their published scores from our own controlled experiments.

W4/Q2 (understanding the H/T/K tradeoff). We agree that showing that joint H/T scaling improves performance is insufficient to characterize the allocation of computation. We therefore added analyses of instance difficulty, Sudoku scaling, and the interaction with parallel sampling.

Q1 (additional baselines). Following your suggestion, we substantially expanded the baseline coverage in Table 1 and Appendix C, using published results on the same benchmark splits.

For Graph Coloring, we added DiT, RLSA, ANYCSP, and Feasibility Jump across all four settings, alongside ConsFormer and BloGDiT. For Sudoku Easy/OOD, we additionally included DiT, RLSA, and IRED. All new scores are taken from the published comparisons in BloGDiT (Xu et al., 2026b, Table 2, v1). We explicitly identify their provenance and retain their original evaluation protocols rather than presenting them as compute-matched reproductions.

These additions confirm that uTRM matches or exceeds the strongest published results on both in-distribution GC settings and GC50→GC100, while remaining behind stronger baselines on GC100-10c→GC200-10c.

For Sudoku-Extreme, we conducted an additional literature search but could not identify published neural baselines trained without ground-truth solutions on this benchmark. We therefore report supervised HRM, TRM, and PTRM results as clearly distinguished reference points rather than presenting them as directly comparable solution-free baselines.

  • Difficulty-conditioned Graph Coloring (App. C.4, Fig. 4): At matched compute HT=30HT=30, H-scaling solves 65.0% of proven-colorable GC50 graphs at mean degree 10.5, compared with 30.3% for T-scaling. Near the colorability transition, at mean degree 12, the difference grows to 22.0% vs. 2.7%. Latent recursion becomes increasingly advantageous on harder instances.
  • Sudoku scaling (App. C.9, Fig. 8): On Sudoku-OOD, increasing H is substantially more effective than increasing T. On Sudoku-Extreme, the behavior reverses: increasing H from 2 to 20 reduces first-attempt accuracy from 35.0% to 24.1%, whereas T-scaling improves it to 56.8%. Thus, latent recursion is not universally beneficial and cannot simply substitute for discrete refinement. The experiments use different checkpoints and configurations, so we do not attribute this reversal to distribution shift alone.
  • Parallel sampling (App. C.5, Fig. 5): Increasing H substantially improves individual GC50 trajectories, but differences between configurations diminish as K increases and best-of-K accuracy approaches the benchmark ceiling.
  • MIS (Fig. 2): H-scaling alone is insufficient to match SDDS, whereas jointly scaling H and T closes the gap at larger compute budgets.

These experiments establish that the relative value of latent recursion, explicit refinement, and parallel search is problem-dependent. We report empirical allocation frontiers rather than claiming a globally optimal allocation rule.

Minor questions. We clarified the remaining points in Secs. 3 and 4 and App. B:

  • We now include both SDDS and a seed-matched 12-layer Transformer trained with terminal rewards alone in Figure 2. Both use conditional-expectation decoding. The terminal-reward-only Transformer is consistently weaker than uTRM, whereas SDDS initially leads. This separates the architectural comparison from the effect of diffusion-derived process rewards.
  • uTRM itself performs explicit stochastic refinement; latent recurrence within each revision is the additional scaling axis.
  • MIS energy rewards independent-set size and penalizes conflicts. A feasible, non-optimal assignment therefore need not have zero energy.
  • The factorized initial prior samples decision variables independently and uniformly from their domains.
  • The embedded candidate is the learned representation of xtx_t.
  • The stochastic policy defines per-variable categorical distributions from which the next discrete assignment is sampled.

We hope these revisions clarify that the contribution is not merely combining TRM with an existing unsupervised objective, but establishing and characterizing the behavior of solution-free recursive reasoning operators. We would be grateful if you would reconsider your assessment in light of the additional controlled experiments and analyses.

Thank you for your detailed response and additional experiments. I believe the paper has substantially improved and will increase my score from 1 to 3. I have two remaining non-blocking suggestions for future revisions.

  1. Although the updated Figure 1 caption is helpful, I think updating Figure 1 itself to highlight the similarities between the 3 methods will make the contribution clearer.
  2. Even though existing works do not report Sudoku-Extreme, implementing and evaluating them where possible will be very beneficial for performance comparison.

Thank you for your constructive feedback and for reconsidering your rating.

We agree that Figure 1 could better highlight the similarities and distinctions between the three approaches, and will incorporate this suggestion in the camera-ready revision. We also appreciate your recommendation to extend the Sudoku-Extreme baseline comparisons and consider this a valuable direction for future work.

Thank you again for your thoughtful assessment.

Reviewer_SF6VOpenReview ↗
Rating
3(+1)
Confidence
2(−2)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

For some combinatorial optimization problems, ground-truth labels are often difficult to obtain within a limited budget. This paper investigates how to train recursive reasoning models using auxiliary signals in the absence of ground-truth labels. The authors first define energy functions to characterize solution quality or the degree of constraint satisfaction across different combinatorial optimization tasks. They then design uTRM, a variant of TRM, to adapt to their proposed training method. This variant explicitly decodes a solution after each H-Block × H loop, re-encodes it, and uses it together with reinitialized hidden vectors as the input to the next loop. During this process, the decoded solutions are evaluated by the energy functions and assigned rewards. The network is then trained using PPO, retaining only the gradients from the last H-Block × H loop. The paper conducts experiments on three tasks: graph coloring, MIS, and Sudoku-Extreme, and compares the proposed method with unsupervised methods such as ConsFormer and BloGDiT. The results show that, on GC, uTRM achieves scores comparable to the baselines with fewer Layer Evals; on MIS, its Layer Evals and performance are comparable to those of the baseline; and on Sudoku-Extreme, it achieves scores of 45.10 at K=1 and 94.17 at K=100.

Critical strengths

The paper investigates a very interesting problem and proposes a method with a certain degree of novelty. I believe it can provide readers with some insights.

Critical weaknesses

The experiments do not sufficiently demonstrate the superiority of uTRM. First, Layer Evals is only a proxy metric and cannot fairly or accurately reflect the resource consumption of different methods. Since different methods have different architectures and parameter counts, fewer Layer Evals do not necessarily imply fewer GPU hours consumed during inference. Therefore, the current experiments do not show whether uTRM can maintain accuracy comparable to the baselines on GC while consuming fewer resources. On MIS, uTRM and SDDS have almost identical Layer Evals and scores, making it difficult to see the superiority of uTRM on MIS. On Sudoku-Extreme, the authors only report the results of uTRM without providing results from any unsupervised baseline, which makes it impossible to determine whether uTRM is more effective than existing methods. In summary, the current experiments do not sufficiently demonstrate the advantages of uTRM over the baselines in terms of either efficiency or accuracy.

In addition, the motivation behind the method design is insufficient. The original TRM design retains the hidden vectors after each H-Block × H loop and directly passes them to the next loop. However, in uTRM, the authors choose to decode x after each H-Block × H loop, re-embed it, and reinitialize the hidden vectors. The authors provide neither theoretical nor experimental explanations for the motivation behind this design, leaving me unclear about its necessity and benefits.

The paper has significant formatting issues. Tables 1, 2, and 6 all extend beyond the page margins. In addition, although Figure 1 allows readers to understand the method's structure and its comparison with previous work, the figure is rather crowded, and some text (e.g., ×L and ×H) overlaps with the lines. I believe its visual presentation could still be improved.

Questions for authors

Please provide a comparison of the resource consumption of different methods using actual metrics such as GPU hours, to verify whether uTRM truly has an efficiency advantage. In addition, why is Sudoku not compared with any unsupervised baseline?

Why do the authors choose to re-embed the decoded x and reinitialize the hidden vectors, rather than retaining the previous states and passing them to the next H-Block × H loop? Could the authors provide theoretical or experimental analyses to motivate this design?

4 comments

Thank you for the constructive review. We substantially revised the experimental evaluation, adding wall-clock measurements, additional Sudoku baselines, and a controlled ablation of latent-state propagation.

W1/Q1 (inference efficiency). We agree that layer evaluations alone are insufficient to establish wall-clock efficiency across different architectures. We therefore introduced a sequential batch-one evaluation protocol with per-step feasibility checking and early stopping, subject to both a 3-second wall-clock limit and conservative layer-evaluation caps (Sec. 3.4, App. C.1).

We additionally benchmarked both uTRM and ConsFormer's released implementation on the same NVIDIA H200 (App. C.8). Since ConsFormer did not release checkpoints, we can reproduce its architecture's throughput but not its accuracy trajectory. Our measurements show:

  • Per-layer efficiency: uTRM executes approximately 3–8× as many logical Transformer-layer evaluations per second as ConsFormer, depending on the GC benchmark. Thus, even after accounting for hardware differences, uTRM's layers are at least approximately 3× cheaper in measured execution time. This remains implementation-dependent, as the methods differ in architecture, framework (JAX/PyTorch), and kernel execution.
  • Accuracy under bounded compute: uTRM matches BloGDiT on GC50 (83.03% vs. 83.00%) and improves on the strongest published GC50→GC100 result (56.69% vs. 55.67%), without exceeding the smaller baseline layer-evaluation budget.
  • Measured wall-clock times: Under our sequential protocol, mean per-instance inference times are 73 ms on GC50 and 198 ms on GC100-5c (Table 9).
  • Time to published accuracy: uTRM reaches ConsFormer's published GC endpoint accuracies within 13–125 ms. After correcting ConsFormer's reported 10-second budget for measured H200 throughput, the corresponding full-budget/uTRM-time ratios are 24–230× (Table 10). These are not directly measured baseline speedups: without ConsFormer's checkpoints, we cannot determine when ConsFormer itself first reaches its published endpoint accuracy.

We therefore distinguish measured implementation throughput, actual uTRM wall-clock performance, and the less directly comparable published-budget ratios.

On MIS, uTRM and our SDDS reimplementation both reach a mean independent-set size of 20.00 at matched layer-evaluation budgets. Their H200 training times are also comparable (67.43 vs. 63.29 hours; Table 3). We do not claim a substantial efficiency advantage here. Rather, a compact recursive model trained with terminal feedback alone matches a larger Transformer trained with additional diffusion-derived process rewards.

W1/Q1 (missing Sudoku baselines). We extended the evaluation to the Sudoku Easy (39–50 gaps) and OOD (47–64 gaps) benchmarks used by ConsFormer and BloGDiT (Tables 1 and 5). uTRM matches both at 100% on Easy but trails BloGDiT on OOD when trained on Easy (64.92% vs. 94.10%). Separately, a model trained without labels on the broader Sudoku-Extreme distribution reaches 98.37% on the 47–64-gap split. We report this separately because the training distributions differ.

Regarding Sudoku-Extreme, we conducted an additional literature search but could not identify any published neural baseline trained without ground-truth solutions on this benchmark. Existing Sudoku-Extreme reasoners, including recent energy-based methods, still use solution-dependent supervision. We therefore cannot provide a directly comparable solution-free baseline without implementing and training an additional method in a previously unreported setting.

Instead, we include supervised HRM, TRM, and PTRM as reference points, explicitly acknowledging differences in supervision and evaluation protocols. We additionally expanded Sudoku-Extreme evaluation from 4,000 to all 422,786 test puzzles (without 1000 validation samples), obtaining 93.90% best-of-100 accuracy from terminal verifier feedback alone.

W2/Q2 (motivation for resetting latent states). We expanded Sec. 3.1 and added a three-seed architectural ablation (App. C.10). All variants re-embed the sampled discrete assignment, differing only in whether the previous latent states are additionally propagated.

Resetting both states achieves 81.61 ± 0.13% best-of-20 GC50 accuracy, compared with:

  • Carry only zLz_L: 77.25 ± 1.80%
  • Carry only zHz_H: 61.75 ± 8.74%
  • Carry both: 59.78 ± 19.00%

Resetting improves both performance and training stability in this configuration. It also makes the sampled discrete assignment the sole information channel between refinement steps. We do not claim that propagating latent history is inherently invalid; the ablation demonstrates that resetting is empirically preferable under our architecture and optimization setup. We also analyze energy trajectories (Fig. 10), while distinguishing the observations from possible mechanistic explanations.

W3 (presentation). We simplified the main results table, moved detailed configurations and inference budgets to Appendix C.1, and clarified the relationship between supervised TRM and uTRM in Figure 1 and its caption.

We hope these revisions address your concerns and would be grateful if you would consider updating your score in light of them.

Thank you for the detailed response. The authors have addressed my concerns regarding missing baselines, inference efficiency, and design motivation. I have therefore decided to raise my overall rating from 2 to 3.

However, I still have two reservations:

  1. OOD generalization: GC200 (10 colors, n=200) appears to be a more discriminative OOD setting, where uTRM still underperforms BloGDiT by 4.75 percentage points.
  2. Presentation quality: The visual presentation of Fig. 1, as well as some aspects of the manuscript's organization and formatting, still require further polishing.

Thank you again for your constructive feedback that helped us present our inference efficiency and design choices more clearly. We also appreciate your comments on presentation quality and will further improve Figure 1, manuscript organization, and formatting in the camera-ready version.

Thank you again for your thoughtful assessment and considering our latest changes in your rating.

Reviewer_w7v7OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes a method for training a reasoning models on tasks, where the model is not provided any ground-truth solution. Instead, the feedback is provided under the form of an energy function, which is then leveraged for training a model through policy gradients. This is particularly relevant due to the fact that obtaining ground-truth solutions for training is an expensive step in the first place, and fixes a single solution where many should exist. The results obtained by the approach are strong.

Critical strengths
  • The paper details its setting, objective and method clearly.
  • The problem is highly relevant (solving combinatorial problems without pre-computed solutions). The method does address that problem through a relaxation of the need for a ground-truth feasible solution: it uses a (possibly non-differentiable) energy function and then trains the model through PPO.
  • The results are strong and evaluate several tradeoffs, such as scaling different loops independently under a budget constraint.
Critical weaknesses
  • The accuracy metric is not detailed in the paper. What exactly is measured?
  • The authors do not evaluate the performance as they vary the verifiers, or even provide the used verifiers for their approach.
  • Table 1 seems to evaluate various baselines on various problems in various settings without justifying why all methods are not evaluated on all three datasets. In particular, it would seem relevant to equalize either the inference time or (if applicable) the number of function evaluations to ensure fair comparison.
  • As I understand it, all the baselines are solutions-free. If so, how does the model's performance compare to solution-aware training? Evaluating this tradeoff seems critical to justify the method's relevance on benchmarks with existing solution data.
Questions for authors
  • What exactly is meant by the accuracy?
  • Which verifiers/energy functions are used in the experiments? They are one of the main contribution of the work, and therefore should be detailed in the main text.
  • How sensitive is the method to a change of the verifier? In particular, how to avoid getting stuck in local minima of the energy function (while it is not directly used in gradient descent, the policy optimization should still favor local minima).
  • How does time scale with H and T scaling?
  • Table seems to show that, wherever it is tested, BloGDiT performs similarly to uTRM, even outperforming it on transfer to larger-sized problems (GC100-GC200). The main exception is on MIS, where BloGDiT is capped at 4000 layers evaluation. Since BloGDiT is diffusion-based, couldn't it be applied on more steps to compare its performance scaling with uTRM (for instance using up to 17k layers eval to compare fairly with the best uTRM)?
4 comments

Thank you for the constructive review. The main change follows your W3, also raised by SF6V. On GC and Sudoku, Table 1 now caps uTRM at both baselines' time and layer-evaluation budgets.

W1/Q1 (accuracy). Accuracy is the fraction of all test instances for which the verifier certifies an assignment with EI(x)=0E_I(x)=0 within the budget. Any valid assignment counts. This definition is now stated explicitly in Sec. 4.1. MIS reports mean independent-set size.

W2/Q2 (energies). They are given in App. B.1. They are standard penalty terms and we now cite their sources there.

W2/Q3 (sensitivity, local minima). We do perform a dedicated study on a time dependent energy function / verifier in App. C.2. This particular choice is motivated since it represents the architecture-matched comparison to a popular diffusion-based objective (SDDS).

Three properties work against local minima along a trajectory:

  • The reward is terminal only, so the learning signal does not encourage greedy improvements but rather good final solutions of trajectories that eventually escaped local minima and traversed barriers.
  • Every step resamples all variables jointly, so moves are not single-flips that explore the local neighborhood. Hence jumps out of minima can be performed by the policy.
  • We adopt the commonly employed evaluation protocols on our benchmarks which employ restarts and parallel sampling which both enable the exploration of diverse solutions.

W3 (baselines, compute). Each baseline appears where it has published results. LTFT, DiffUCO, SDDS and CAM target binary problems such as MIS, ConsFormer targets CSPs, and BloGDiT's implementation is not yet released. Following your suggestion on the necessity of equalized inference budgets we adapted our evaluation strategy so that such a comparison can be read off more easily from the result table, i.e. with only a single uTRM number. Table 1 now bounds uTRM's inference cost by the baselines' budgets:

  • GC and Sudoku (vs. ConsFormer, BloGDiT): each instance runs at batch one, as in ConsFormer/BloGDiT. uTRM samples trajectories sequentially and stops at the first verifier-certified solution, or when a time cap or a layer-evaluation cap is reached. The layer cap is the smaller of the two baselines' reported budgets. ConsFormer's released code runs 3.00–3.32× faster on our H200 than reported by them (App. C.8), and we correct with the larger factor, giving 10 s / 3.32 ≈ 3.0 s per GC instance. uTRM thus never uses more time or layer evaluations than either baseline, and against BloGDiT the time cap is stricter still. We report accuracy over all test instances, as in the published tables (Tables 1 and 5), plus mean and maximum elapsed times (Table 9) and accuracy-versus-time curves (Fig. 7).
  • MIS (vs. SDDS): identical data, verifier, and layer evaluations.
  • Sudoku-Extreme (vs. PTRM): K=100K=100 samples as in PTRM. PTRM uses significantly more inference compute per problem instance (App. C.1).
  • Controlled baselines: a flat Transformer with identical data, verifier and budget (GC50), and SDDS-style process rewards (GC50, Table 6).

Q5 (BloGDiT). The revised protocol (W3) makes the comparison to BloGDiT now more direct. With no more time and no more layer evaluations than BloGDiT, uTRM matches or exceeds it on every in-distribution Graph Coloring, MIS and Sudoku setting and on GC50→GC100. On GC50 and GC100-10c, both methods are within one instance of the solvability ceiling (Table 2), so these settings cannot separate them. On MIS, Table 5 now includes a configuration below BloGDiT's budget (3,888 vs. 4,000 layer evaluations), at which uTRM reaches 19.78 and SDDS 19.91, compared with 19.52 for BloGDiT. In principle, BloGDiT could be run with a larger budget, but its implementation has not been released (its public repository contains no code yet), so we cannot extend it beyond its published configuration.

We do not match BloGDiT under shifts in instance statistics. These are GC100-10c→GC200-10c, where the mean degree rises from 20.7 to 33.7 (Table 2), and Sudoku-Easy→47–64 gaps. Two points put this in context:

  • Easy-to-hard transfer is the natural test when hard instances cannot be labeled. A solution-free method like ours, however, needs no labels, so it can train on unlabeled instances from the target distribution. Trained on Sudoku-Extreme without labels, uTRM solves 98.37% of the same 47–64-gap split with 1,022 mean layer evaluations, well within BloGDiT's 14,000-layer budget. We report this row separately because the training data differs.
  • Like most RRMs, uTRM targets its training distribution. HRM, TRM and PTRM are trained and tested on the same distribution. uTRM transfers across graph size (GC50→GC100), but shifts in density or clue count are not what it is designed for.

Matched on accuracy instead of budget and after correcting for hardware differences (Table 10), uTRM reaches ConsFormer's published GC solve rates within 13–125 ms, that is at least 24× below ConsFormer's full hardware-corrected budget of 3 s.

Q4 (time vs HH, TT). Time is linear in both. A trajectory costs Cseq=TH(L+1)nlayersC_{\mathrm{seq}} = T H (L+1) n_{\mathrm{layers}} sequential layer evaluations, and runtime is linear in layer evaluations (App. C.8). In training, the forward pass is linear in HH, and backward cost and memory are constant in HH due to truncation (Sec. 3.3).

W4 (solution-aware training). We agree and list it as a limitation. How much labels are worth relative to a verifier is an important open question in its own right. Answering it requires dedicated studies across diverse problem classes, beyond the scope of this work. We include Sudoku-Extreme and its supervised baselines to show that uTRM reaches competitive accuracy without labels and without excessive compute. At PTRM's K=100K=100, uTRM solves 93.90% vs. 99.06%, using 33% fewer layer evaluations and about 17× less arithmetic (App. C.1), and it exceeds single-sample TRM (87.4%). This matters because independence from solved instances is a key advantage of solution-free methods. In principle, they can be trained on problem classes for which no existing solver can produce labels.

We hope these revisions address your concerns and would be grateful if you would consider updating your score in light of them.

I thank the authors for their clarifications. I currently lean towards maintaining my score. My main reasons for maintaining a weak accept are:

  • the limited novelty of the approach, where all components (including the energy functions) are known literature components;
  • the absence of comparison with solution-aware methods prevents from having a clear vision of the gain of such solution-free methods. I believe a basis of comparison that shows how much "cost" is saved by not having to generate solutions would make the paper's impact clearer.

I believe those two points together limit the impact of the paper, but that the extensive experiments and relevance of the topic are strong enough to lean towards acceptance.

I will consider updating during reviewers discussion.

Thank you for the follow-up and for leaning towards acceptance.

Novelty. Supervised recursive reasoning models such as HRM, TRM and PTRM are among the most parameter-efficient learned reasoners on structured puzzle benchmarks and, like learned combinatorial solvers more broadly, offer an alternative to hand-crafted heuristics whose parameters are learned rather than tuned for each problem type. They still require solved instances for training, whereas solution-free training removes this requirement and in principle extends learned solvers to problem classes where labels are expensive or ambiguous because many solutions are valid. Making the RRM recurrence work without solutions is not a direct transfer, since the deep supervision against target solutions that drives RRM training is no longer available and the latent recursion must be learned from the energy of the final candidate alone. This required design choices that we identify and ablate, namely closing the refinement loop through sampled discrete assignments with latent states reset at every revision (Sec. 3.1, App. C.10) and truncated recursive credit assignment (Sec. 4.4), without which performance degrades or the learned operator stops benefiting from additional recursion. To our knowledge, uTRM is the first recursive reasoning model trained from a verifier alone, without any solutions, and it reaches competitive accuracy on Sudoku-Extreme, a standard RRM benchmark, which we consider the central contribution beyond the individual components. On Graph Coloring and MIS, uTRM matches or exceeds specialized solution-free solvers in most settings. The energies are deliberately the established ones, so that differences to prior solution-free solvers are attributable to the method rather than to the objective.

Comparison with solution-aware methods. We agree that the trade-off between labels and verifier feedback is important. To make the comparison with solution-aware methods explicit, Table 5 now also includes the supervised MIS baselines INTEL and DGL on RB-small, as reported by Zhang et al. (2023), complementing HRM, TRM and PTRM on Sudoku-Extreme; uTRM exceeds both supervised MIS baselines without using any solutions. Quantifying how much cost is saved by not generating solutions, however, depends on the labeling solver, its time budget and the treatment of multiple optima, and to our knowledge neither solution-free combinatorial solvers nor supervised RRMs have reported such a study. We therefore consider it a dedicated question beyond the scope of this paper.

Comments on the paper

1 comment

We thank all reviewers for their constructive feedback. Their comments motivated substantial revisions, including new controlled experiments, a redesigned evaluation protocol, broader baselines, and additional architectural and scaling analyses. We would like to highlight four central improvements.

  1. Novelty: Learning recursive reasoning without solutions.

Supervised RRMs such as HRM, TRM, and PTRM achieve strong performance with remarkably few parameters, but require ground-truth solutions. Removing this requirement extends their applicability to problems where solutions are expensive to obtain or many valid solutions exist.

This is not a straightforward substitution of supervision with PPO, the deep supervision driving conventional RRMs is unavailable, and useful latent recurrence must emerge from terminal verifier feedback alone. We identify and ablate two critical design choices: discrete refinement with latent-state resets (Sec. 3.1, App. D.10) and truncated recursive credit assignment (Sec. 4.4, Fig. 3). Controlled Transformer comparisons further demonstrate the benefits of learning a reusable recursive operator rather than a fixed-depth network (Sec. 4.3, Table 7). To our knowledge, uTRM is the first RRM trained entirely without solutions.

  1. Fair evaluation and wall-clock efficiency.

Addressing concerns about layer evaluations as an efficiency proxy, we adopted sequential batch-one inference with feasibility checking, early stopping, and conservative compute caps, matching the evaluation setting of ConsFormer and BloGDiT (Sec. 3.4, App. D.1).

We additionally benchmarked ConsFormer's released implementation on the same GPU as uTRM. The wall-clock results are even more favorable than layer counts suggest: uTRM reaches ConsFormer's published Graph Coloring accuracies using 24–230× less time than its hardware-corrected full evaluation budget (App. D.8, Tables 8–10, Fig. 7).

  1. Solution-free Sudoku-Extreme with a compact model.

We compare our unsupervised uTRM on Sudoku-Extreme only to supervised methods, as there are no unsupervised competitors. Not only are we in the same ballpark concerning accuracy, but we need an order of magnitude fewer parameters and estimated inference compute.

  1. Understanding test-time computation allocation.

We are the first to examine latent recursive scaling in the unsupervised setting. We expanded our analysis of latent recursion (H), discrete refinement (T), and parallel sampling (K). Difficulty-conditioned Graph Coloring experiments show that additional latent recursion becomes increasingly beneficial at difficult instances near the colorability transition (App. D.4, Fig. 4). On Sudoku, we discover settings that cause contrasting effects of recursive scaling (App. D.9), highlighting that recursive scaling is indeed a new scaling axis previously only demonstrated in the supervised setting.

We believe these revisions substantially strengthen the methodological and empirical contributions of the paper. We appreciate the reviewers' suggestions and would be grateful if they would reconsider their assessments in light of the new evidence.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.