- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes ResizeCO, which adapts a diffusion routing solver pretrained on small labeled instances to larger instances through label-free RL at the target size. It combines a Graph Transformer encoder with an MPNN structure extractor, post-2-opt rewards for RL fine-tuning, and GPU beam k-opt search at inference. The authors evaluate ResizeCO on TSP and CVRP instances with up to 10000 nodes, claiming a Pareto advantage over learning-based solvers in route quality and runtime.
Critical strengths
- The Graph Transformer encoder combines an MPNN structure extractor with global attention, making attention sensitive to local graph structure while retaining a global view.
- The GPU beam k-opt search organizes Lin-Kernighan-style edge exchanges into a parallel beam search and applies compatible moves together, making route improvement better suited to GPU execution.
Critical weaknesses
- The title about size generalization overstates what the major experiments establish. The main results primarily demonstrate target-size adaptation rather than zero-shot transfer of a model trained only on small instances.
- The claimed GRPO framework requires a more rigorous description. This paper actually adopts group-normalized REINFORCE-style training and sets the KL divergence coefficient to zero during training at a 10K-node scale.
- The evaluation omits highly relevant methods DGL and L2R, which are clearly trained only on 100-node instances and aimed at size generalization. Thus, the claim that ResizeCO dominates existing learned solvers is insufficiently supported.
- In the main experiment, the authors did not report constructive results without any post-search strategy. It is unclear whether the gains are attributable to improved construction quality or to stronger search.
- Although node-walk decoding respects capacity, Appendix B.5 allows GPU beam k-opt to pass through overloaded CVRP solutions without clearly specifying how final feasibility is enforced or reporting final feasibility rates. This makes the CVRP results unconvincing, particularly the negative gaps at size 10000.
Questions for authors
- Could the authors evaluate the model trained only at size 100 on large-scale uniformly distributed instances and all TSPLIB/CVRPLIB groups, without any target-size RL?
- Could you provide a controlled comparison between ResizeCO's group-standardized advantages and POMO-style mean-centered advantages to clarify whether the additional normalization provides a meaningful benefit?
- Given the use of B200/H200 GPUs for large-scale training, could you report peak GPU memory usage across the full training pipeline?
- Could you report ResizeCO's results without post-search, and baseline results with the same post-search strategy as ResizeCO?
- Could you clarify the CVRP post-search procedure, explain how final feasibility is ensured, and report the feasibility rate?
- Could you report the average and maximum numbers of GPU beam k-opt search at each test size for each problem?
7 comments
Response to Reviewer Aw3M (2/5)
Weakness 1: What do the main size-generalization results establish?
The main results test label-free RL adaptation at the target size. We also test the same model on larger instances without further training, comparing ResizeCO after RL with its starting checkpoint after SL.
The first table reports TSP and the second CVRP. The training-size column gives the supervised source size followed by the RL size; evaluation sizes are larger than the RL size. ResizeCO after SL and after RL use the same decoder, search, and sample count S. Entries are gap (%) / total time (s per instance). SIT uses PRC5/20/3 at 2,000/5,000/10,000 nodes and PRC2/10 at 20,000/50,000 nodes.
| Evaluation | SL → RL size | ResizeCO after SL | ResizeCO after RL | SIT |
|---|---|---|---|---|
| TSP-2,000 S=8 | 500 → 1,000 | 2.153 / 3.390 | 0.482 / 1.058 | 1.967 / 1.348 |
| TSP-5,000 S=8 | 500 → 1,000 | 3.437 / 7.648 | 3.133 / 8.461 | 2.542 / 8.364 |
| TSP-10,000 S=1 | 500 → 1,000 | 4.174 / 2.676 | 4.198 / 2.827 | 3.629 / 3.855 |
| TSP-20,000 S=1 | 1,000 → 10,000 | 4.985 / 9.63 | 3.908 / 8.32 | 5.151 / 7.33 |
| TSP-50,000 S=1 | 1,000 → 10,000 | 10.867 / 54.03 | 10.140 / 54.04 | 5.853 / 64.25 |
| Evaluation | SL → RL size | ResizeCO after SL | ResizeCO after RL | MaskCO |
|---|---|---|---|---|
| CVRP-5,000 S=1 | 500 → 1,000 | 1.525 / 12.249 | 0.926 / 5.904 | 2.985 / 6.95 |
| CVRP-10,000 S=1 | 500 → 1,000 | 0.703 / 67.724 | 0.317 / 31.678 | 7.971 / 29.34 |
| CVRP-20,000 S=1 | 1,000 → 10,000 | -0.016 / 131.7 | -0.610 / 38.5 | 381.481 / 78.11 |
| CVRP-50,000 S=1 | 1,000 → 10,000 | 2.019 / 691.7 | -0.864 / 498.3 | 863.302 / 194.5 (13/16 feasible) |
Beyond the RL size, ResizeCO after RL improves on its after-SL starting point in all four CVRP evaluations and four of five TSP evaluations. It has the lowest gap among the shown methods in every CVRP row and two TSP rows. SIT leads at several TSP sizes, and one TSP row slightly favors after SL. These tests show that adaptation gains often transfer to larger sizes without further training, in addition to our main label-free target-size adaptation claim. We added the results to the paper.
Weakness 4: Do ResizeCO’s gains come from RL, search, or both?
The submitted component ablations test learning and beam refinement separately: Table 5 and Appendix Table D.10 include no-RL and no-beam controls. The no-RL models retain the same search, while the no-beam models retain 2-opt. We extended these ablations to all 12 source-to-target pairs in the paper.
We also compared ResizeCO after RL before any post-search with the full solver on six source-to-target pairs. Within each pair, both versions use the same decoder and sample count. Entries are gap (%) / total time (s per instance).
| Evaluation | ResizeCO (raw construction) | ResizeCO (full solver) |
|---|---|---|
| TSP-100 → TSP-500 | 4.974 / 0.009 | 0.329 / 0.020 |
| TSP-500 → TSP-1,000 | 3.897 / 0.028 | 0.208 / 0.046 |
| TSP-1,000 → TSP-10,000 | 16.576 / 1.229 | 2.046 / 2.144 |
| CVRP-100 → CVRP-500 | 14.162 / 0.005 | 3.176 / 0.109 |
| CVRP-500 → CVRP-1,000 | 13.725 / 0.014 | 2.764 / 0.198 |
| CVRP-1,000 → CVRP-10,000 | 3.177 / 2.345 | -0.096 / 18.047 |
Search lowers the gap in every pair. This is consistent with the RL objective: we train using reward after 2-opt, so the model is trained to produce solutions that improve with search. Q1 answer separately shows that RL helps when decoding and search are fixed. In the matched-time CVRP-1,000→10,000 control of our response to Reviewer 4EkP (Question 1), ResizeCO after RL has lower gaps than after SL both before and after search, at nearly identical total inference time.
Response to Reviewer Aw3M (3/5)
Weakness 3: How does ResizeCO compare with DGL and L2R?
We ran their released size-100 models with native inference on our instances, references, and GPU. ResizeCO also begins with size-100 supervision but adds unlabeled target-size RL. DGL uses augmentation ×1, ×1, and ×8 for TSP-500/1,000/10,000 and ×32, ×32, and ×8 for CVRP-500/1,000/10,000; L2R uses greedy decoding. Each entry is gap (%) / total time (s per instance).
| Evaluation | ResizeCO | DGL | L2R |
|---|---|---|---|
| TSP-500 | 0.329 / 0.020 | 4.509 / 0.023 | 4.252 / 0.017 |
| TSP-1,000 | 0.813 / 0.059 | 5.185 / 0.048 | 4.494 / 0.036 |
| TSP-10,000 | 4.029 / 2.712 | 6.463 / 35.055 | 4.745 / 3.406 |
| CVRP-500 | 3.176 / 0.109 | 11.223 / 0.190 | 8.041 / 0.022 |
| CVRP-1,000 | 3.426 / 0.222 | 9.266 / 0.368 | 7.766 / 0.085 |
| CVRP-10,000 | -0.056 / 18.166 | 2.996 / 48.051 | 2.226 / 4.096 |
ResizeCO has a lower gap than DGL and L2R in all six settings. L2R is faster on CVRP, but has higher gaps. We also test whether the advantage remains when these baselines receive our search in Q4 below. We added both comparisons to the paper.
Question 4: How does ResizeCO compare when the baselines also use our search?
To test whether ResizeCO’s advantage comes only from its search, we applied GPU beam k-opt to the baseline solutions as well. The table compares the resulting complete TSP solvers, including their construction and refinement time.
DIMES retains active search and MCTS, and DIFUSCO retains its native 2-opt, before our beam search. For MaskCO, our beam search replaces its TSP 2-opt. Total time includes every stage. At TSP-10,000, S=1 gives ResizeCO’s faster setting, while S=16 uses a budget closer to SIT’s. Entries are gap (%) / total time (s per instance).
| Method | TSP-500 | TSP-1,000 | TSP-10,000 |
|---|---|---|---|
| ResizeCO, S=1 | 0.329 / 0.020 | 0.208 / 0.046 | 2.046 / 2.144 |
| ResizeCO, S=16 | 0.152 / 0.131 | 0.099 / 0.244 | 1.834 / 17.18 |
| DIMES (RL+AS+MCTS) + beam k-opt | 1.369 / 27.0 | 2.121 / 55.7 | 2.629 / 458 |
| DIFUSCO (Tₛ=50, S=4) + 2-opt + beam k-opt | 0.535 / 4.416 | 0.982 / 9.152 | 2.129 / 370.604 |
| SIT (greedy) + beam k-opt | 1.274 / 0.081 | 1.244 / 0.208 | 1.931 / 17.59 |
| MaskCO (T=16) + beam k-opt | 1.800 / 0.201 | 0.266 / 0.251 | 3.056 / 19.55 |
| DGL (BS4, aug×32/32/8) + beam k-opt | 0.922 / 0.786 | 1.270 / 1.067 | 2.157 / 42.709 |
| L2R (greedy) + beam k-opt | 2.167 / 0.072 | 2.481 / 0.115 | 3.370 / 3.648 |
ResizeCO has the lowest gap at TSP-500 and TSP-1,000 after the baselines also receive our search. At TSP-10,000, ResizeCO with S=16 beats SIT in gap and total time; S=1 is faster with a slightly higher gap. These comparisons show two benefits: our search also improves baseline solutions, while ResizeCO retains a quality advantage after the baselines receive that search. The gain therefore cannot be explained solely by giving ResizeCO a stronger refinement procedure.
Response to Reviewer Aw3M (1/5)
Thank you for the detailed review. Your comments helped us sharpen the paper: we now show solution quality before and after search, apply our search to the baselines, and report CVRP feasibility.
Critical strengths: We appreciate your recognition of our Graph Transformer, which combines local and global graph information, and GPU beam k-opt, which makes large-instance route refinement efficient.
Question 1: How does the size-100 model perform without target-size RL?
We evaluated the size-100 supervised checkpoint on every reported uniform and real-world group, before and after target-size RL. Both ResizeCO checkpoints use the same decoder and search. MaskCO-100 uses native inference with 2-opt and no beam. Each entry is gap (%) / total time (s per instance).
With the decoder and search fixed, RL lowers the gap in every uniform and real-world group. This directly shows a learning benefit from label-free target-size adaptation: the larger instances require no optimal solution labels. The submitted ablations already included comparisons with and without RL; we extended them to all 12 TSP/CVRP source-to-target pairs.