- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes MESCO, a self-supervised method for large-scale TSP. It combines the edges from several short MCTS searches into soft targets for training a diffusion model and updates these targets as training progresses. This avoids the need for expensive pre-solved training labels. Experiments show lower gaps than the compared heatmap-based methods on 1,000- and 10,000-node problems, with lower supervision costs.
Critical strengths
S1. MESCO generates training targets from short MCTS searches, reducing supervision costs compared with solver-generated labels.
S2. Impressive experimental results, especially on large-scale instances.
S3. Generalization to CVRP is considered.
Critical weaknesses
W1. Limited novelty. Several key parts of MESCO come from existing work. Heatmap-guided MCTS was introduced by Fu et al. (2021). The denoising network follows DIFUSCO and Fast-T2T, while the diffusion training objective builds on Sanokowski et al. (2024). The main new design therefore appears to be combining multiple short MCTS searches with randomly sampled configurations, weighting their returned tours by quality, and using the resulting edge probabilities to supervise diffusion training. This is a useful extension, but the paper needs to explain more clearly what it adds beyond existing search-based self-improvement. It’s also not clear to me why “the first neural heatmap method to place MCTS inside the training loop” is considered as an important novelty?
W2. The experiments give each heatmap-based method the same MCTS search time, but their total inference times differ. On TSP-10000, GT-Prior takes about 16.65 minutes, while MESCO takes an additional 3.60 minutes to generate heatmaps, bringing its total to 20.25 minutes. This does not invalidate the improvement, but it leaves unclear how much of the advantage remains under an equal total budget. Another issue is that both GPU and CPU resources are used for experiments, which also cause concerns on fair comparison. What happens if only CPU is used for all the experiments?
W3. The main TSP experiments rely on uniformly distributed Euclidean instances. It would be good to test other distributions or TSPLIB instances.
Questions for authors
Please address W1-W3
4 comments
Response to Reviewer tohi (2/3)
W2 (equal total budget, and CPU vs. GPU). We address the two points separately.
(i) Equal total time (Appendix A.8, new in revision). GT-Prior and SoftDist need no time to generate a heatmap, so at the same MCTS budget, MESCO uses more total time than they do. We therefore re-ran GT-Prior and SoftDist with an MCTS budget equal to MESCO's total time in Table 2, that is, heatmap generation plus MCTS: 3.17, 6.33, and 20.25 minutes for the test sets at TSP-500, TSP-1000, and TSP-10000, respectively. Even with this additional search time, GT-Prior attains optimality gaps of 0.54%, 0.89%, and 2.09%, and SoftDist attains 0.60%, 0.94%, and 3.25% at the three problem sizes, compared with 0.22%, 0.51%, and 1.10% for MESCO (Table 2). Their gaps therefore remain 1.7–3.0× MESCO's at every problem size.
Optimality gap (%) when all methods use the same total time per test set (Appendix A.8 in the revision):
| Method | Total time (TSP-500 / TSP-1000 / TSP-10000) | TSP-500 | TSP-1000 | TSP-10000 |
|---|---|---|---|---|
| SoftDist (MCTS only) | 3.17 / 6.33 / 20.25 min | 0.60 | 0.94 | 3.25 |
| GT-Prior (MCTS only) | 3.17 / 6.33 / 20.25 min | 0.54 | 0.89 | 2.09 |
| MESCO (heatmap + MCTS, Table 2) | 3.17 / 6.33 / 20.25 min | 0.22 | 0.51 | 1.10 |
(ii) CPU-only inference (Appendix A.8, new in revision). MESCO's heatmaps can also be generated without a GPU. On the 36 CPU threads alone, heatmap generation takes 0.14 s, 0.25 s, and 9.9 s per instance at TSP-500, TSP-1000, and TSP-10000, respectively, compared with 50 s, 100 s, and 1000 s of MCTS per instance. CPU-only heatmap generation therefore adds less than 1% to the total time at every problem size, and the comparison in (i) does not change if only CPUs are used. DIFUSCO and Fast-T2T also generate their heatmaps on a GPU.
Response to Reviewer tohi (3/3)
W3 (other distributions and TSPLIB). We evaluated all models with zero-shot transfer on clustered, explosion, and implosion instances generated with the INViT generator (128 instances each at TSP-500 and TSP-1000, and 16 at TSP-10000). In these experiments, we used exactly the same checkpoints, MCTS configurations, and time budgets as on uniform instances. All methods (Zero, SoftDist, GT-Prior, DIFUSCO, and MESCO) are run under the same protocol on the same instances. The results are in the new Table 4, with details of the setup in Appendix A.13.
MESCO attains the lowest optimality gap in eight of the nine settings (three distributions at each of three problem sizes). On TSP-500, MESCO attains gaps of 0.29%, 0.20%, and 0.26% on the clustered, explosion, and implosion instances, respectively, compared with 0.64%, 0.48%, and 0.64% for the next-best method, GT-Prior. On TSP-1000, MESCO attains gaps of 0.66% and 0.55% on the clustered and explosion instances, compared with 0.81% and 0.69% for the next-best method, DIFUSCO; on the implosion instances, DIFUSCO has a lower gap than MESCO (0.61% vs. 0.74%). On TSP-10000, MESCO attains gaps of 1.32%, 1.67%, and 1.70% on the clustered, explosion, and implosion instances, compared with 2.13%, 2.38%, and 2.83% for the next-best method, GT-Prior, so its gap is 0.8–1.1 percentage points lower in every distribution. Since MESCO needs no solver labels, it can be trained directly on such instances at no extra labeling cost, and we expect it to perform even better in that setting.
Optimality gap (%) on non-uniform instances, zero-shot, seed 1 (Table 4 in the revision; Clu. = clustered, Exp. = explosion, Imp. = implosion):
| Method | TSP-500 Clu. | TSP-500 Exp. | TSP-500 Imp. | TSP-1000 Clu. | TSP-1000 Exp. | TSP-1000 Imp. | TSP-10000 Clu. | TSP-10000 Exp. | TSP-10000 Imp. |
|---|---|---|---|---|---|---|---|---|---|
| Zero | 0.95 | 0.76 | 0.88 | 1.70 | 1.72 | 1.75 | 3.73 | 4.19 | 5.18 |
| SoftDist | 1.10 | 0.60 | 0.65 | 1.98 | 1.44 | 1.07 | 3.51 | 4.11 | 4.48 |
| GT-Prior | 0.64 | 0.48 | 0.64 | 0.98 | 0.86 | 1.08 | 2.13 | 2.38 | 2.83 |
| DIFUSCO | 0.91 | 0.59 | 0.64 | 0.81 | 0.69 | 0.61 | 3.03 | 2.86 | 3.05 |
| MESCO | 0.29 | 0.20 | 0.26 | 0.66 | 0.55 | 0.74 | 1.32 | 1.67 | 1.70 |
On TSPLIB, we use the 35 instances of Pan et al. (2026) with MCTS configurations tuned on uniform instances, and compare against the eight methods that they report (new Table 5; per-instance results in Appendix A.14). On the Medium group (21 instances with 500–2000 nodes), MESCO attains a mean optimality gap of 2.70%, second only to DIFUSCO (2.38%), and it is the best method on 9 of the 21 instances. On the Large group (14 instances with more than 2000 nodes), MESCO attains a mean optimality gap of 4.34%, third behind GT-Prior (3.53%) and Att-GCN (3.92%). The clustered drilling instances (fl1400, fl1577, and fl3795) are the hardest for every method.
Mean optimality gap (%) on TSPLIB (Table 5 in the revision; per-instance results in Appendix A.14):
| Group | Zero | Att-GCN | DIMES | UTSP | SoftDist | DIFUSCO | Fast-T2T | GT-Prior | MESCO |
|---|---|---|---|---|---|---|---|---|---|
| Medium (21 instances, 500–2000 nodes) | 15.24 | 11.47 | 10.64 | 12.03 | 6.79 | 2.38 | 4.18 | 10.08 | 2.70 |
| Large (14 instances, more than 2000 nodes) | 5.54 | 3.92 | 5.48 | 26.51 | 4.43 | 5.68 | 6.81 | 3.53 | 4.34 |
The authors addressed some of my concerns. I still maintain the positive score.
Response to Reviewer tohi (1/3)
We thank the reviewer for the careful review and for recognizing the importance of the problem and the strength of the results on TSP-10000. We address each point below; all new results are included in the revised paper, with changes marked in blue.
W1 (novelty of the approach). We agree that the denoising network itself is not new: it follows DIFUSCO and Fast-T2T. What is new is how the network is trained. MESCO never sees a TSP solution during training. Instead, its heatmap targets come from the same search that is used at test time. Three elements make up this training scheme:
The updated ablation in Table 7 quantifies each element; "single refresh" computes the targets only once at the start of training and never recomputes them.
Optimality gap (%) at TSP-500 over 5 decoding seeds (Table 7 in the revision; Refresh = targets recomputed during training):
We have revised Section 1 to describe the contribution in these terms.
W1, continued (importance of placing MCTS in the training loop). Let us restate this claim more precisely: to our knowledge, MESCO is the first heatmap-guided MCTS solver in which MCTS, the decoder used at test time, also generates the training targets during training. UTSP and DIMES are also label-free, but neither runs the search during training. This matters for three reasons: