- 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
-
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.
-
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 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).
-
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.
-
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
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 , 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 .
- 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.
- 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.
- 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.
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 zL, 61.75 ± 8.74% when carrying only zH, 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.