- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes TRM4CO, a weight-tied recursive neural framework for combinatorial optimization with test-time scaling through additional recursion steps and parallel stochastic rollouts. Problem-specific encoders and decoders support TSP and MIS, while self-relabeling enables further improvement using the model’s own solutions.
Critical strengths
The framework provides a coherent adaptation of recursive models to CO, combining structural encoding, intermediate supervision, and objective-based selection, which is practically meaningful and the paper is clearly well-presented.
Critical weaknesses
- The gains seem to be strongly influenced by parallel sampling and problem-specific decoding, without compute-matched non-recursive controls.
- Runtime comparisons use different batching settings and extrapolated TSP-10000 timings. At that scale, TRM4CO matches COExpander’s gap while being approximately 15× slower, somewhat contradicting the broad lower-cost claim.
- Experiments are restricted to TSP and MIS, leaving broader applicability insufficiently validated. Additional tasks could include ATSP, maximum clique, Max-Cut, constrained routing problems such as CVRP/PCTSP, and structurally different problems such as KP/JSSP. Broader evaluation, or a concrete discussion of how the problem-specific encoders and decoders accommodate these tasks and constraints, would strengthen the generality claim. Related frameworks such as COExpander, DiffUCO, M²GenCO, and MaskCO provide useful comparisons.
- Self-relabeling comparisons lack matched training budgets, while label-free TSP performance remains substantially below supervised training.
- Incomplete coverage of test-time scaling baselines. Relevant approaches such as GenSCO, L2C, L2R, InViT, and NexCO exploit additional inference computation in different ways but are insufficiently covered. These methods, alongside the already included DualOpt, warrant more systematic discussion and, where applicable, quality–runtime comparisons under matched compute budgets to establish the distinct benefits of TRM4CO’s recursive depth and parallel width.
- The mentioned additional works are worth further discussion, if not empirically compared.
References:
-
Generation as Search Operator for Test-Time Scaling of Diffusion-based Combinatorial Optimization(GenSCO)
-
Learning to Insert for Constructive Neural Vehicle Routing Solver(L2C-Insert)
-
Learning to Reduce Search Space for Generalizable Neural Routing Solver(L2R)
-
INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer
-
NExCO: Native Solution Expansion for Diffusion-based Combinatorial Optimization
-
DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem
-
A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization(DiffUCO)
-
Problem Distributions as Tasks: Repurposing Meta Learning for Generative Combinatorial Optimization towards Multi-task Pretraining and Adaptation(M²GenCO)
-
MaskCO: Masked Generation Drives Effective Representation Learning and Exploiting for Combinatorial Optimization
Questions for authors
see weaknesses