acceptodds
Under review as a conference paper at ICLR 2027

MESCO: Learning to Solve Large-Scale TSP with Self-Supervision via MCTS Ensembles

Abstract

Many neural methods for solving the Traveling Salesman Problem (TSP) follow the heatmap-guided Monte Carlo Tree Search (MCTS) paradigm, in which a neural network assigns a probability to each edge and MCTS uses those probabilities to guide an improvement search. The strongest of such methods train on solved TSP instances, but at scale this supervision becomes a bottleneck: exact solvers are intractable beyond a few thousand nodes, and even heuristic solutions cost over an hour per instance at 10,000 nodes. This cost of supervision, rather than model capacity, appears to be the limit, as a recent study found that at 10,000 nodes, a simple heuristic heatmap beats every neural method, including supervised methods. To address the challenge of scale, we introduce MESCO, which derives supervision from an ensemble of short MCTS rollouts run during training. Each rollout follows the model's current heatmap, samples its own search configuration, and runs for a fixed budget instead of a solve time dictated by the instance. Aggregating the edges selected by the rollouts, weighted by the quality of the solutions they produce, yields a heatmap target that is more informative than any individual rollout's tour, and improves as the model does. To our knowledge, MESCO is the first neural heatmap method to place MCTS inside the training loop. MESCO attains the best reported optimality gaps on TSP problems with 1,000 and 10,000 nodes, % and %, and is competitive with supervised methods at 500 nodes with a gap of %, while reducing the cost of supervision by up to .

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Traveling Salesman Problem, Combinatorial Optimization, Monte Carlo Tree Search, Diffusion

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_tohiOpenReview ↗
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
AuthorsOpenReview ↗

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:

  1. Self-supervision from search. The targets come from MCTS runs guided by the model's own heatmap. No part of the training objective uses a solution from an exact solver (Concorde) or a heuristic solver (LKH-3).
  2. MCTS-ensemble targets. Short rollouts with randomly sampled search configurations are combined through a quality-weighted vote. At the same total search budget, this improves on using fewer rollouts or only the best tour. The rollouts also run in parallel, and no MCTS hyperparameters need to be tuned during training.
  3. Refresh loop. During training, the targets are periodically recomputed from the current model; we call each recomputation a refresh. The targets therefore improve as the model improves. This is the component with the largest effect.

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):

VariantRRefreshTargetEntropy termOptimality gap (%)
Best-of-R20✓one-hot✓0.260 ± 0.008
R = 55✓weighted✓0.262 ± 0.008
R = 11✓one-hot✓0.267 ± 0.023
Single refresh20weighted✓0.483 ± 0.010
No entropy term20✓weighted0.291 ± 0.012
MESCO20✓weighted✓0.230 ± 0.015
Every variant therefore stays behind MESCO by more than the seed-to-seed variation, and the refresh loop matters most.

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:

  1. The refresh loop is the largest effect we measure: if the targets are computed only once at the start of training and never refreshed, the gap at TSP-500 more than doubles, from 0.230% to 0.483% (Table 7).
  2. It trains the model to optimize the quantity that is evaluated at test time, which addresses the mismatch that Xia et al. (2024) identified between training on solver tours and being evaluated by MCTS. This is reflected in heatmap quality: in Table 3, MESCO's heatmaps have the highest recall of the optimal successor at every scale and for every k.
  3. It removes the need for supervision from any solver, exact or heuristic, rather than replacing LKH-3 with another solver.
AuthorsOpenReview ↗

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):

MethodTotal time (TSP-500 / TSP-1000 / TSP-10000)TSP-500TSP-1000TSP-10000
SoftDist (MCTS only)3.17 / 6.33 / 20.25 min0.600.943.25
GT-Prior (MCTS only)3.17 / 6.33 / 20.25 min0.540.892.09
MESCO (heatmap + MCTS, Table 2)3.17 / 6.33 / 20.25 min0.220.511.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.

AuthorsOpenReview ↗

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):

MethodTSP-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.
Zero0.950.760.881.701.721.753.734.195.18
SoftDist1.100.600.651.981.441.073.514.114.48
GT-Prior0.640.480.640.980.861.082.132.382.83
DIFUSCO0.910.590.640.810.690.613.032.863.05
MESCO0.290.200.260.660.550.741.321.671.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):

GroupZeroAtt-GCNDIMESUTSPSoftDistDIFUSCOFast-T2TGT-PriorMESCO
Medium (21 instances, 500–2000 nodes)15.2411.4710.6412.036.792.384.1810.082.70
Large (14 instances, more than 2000 nodes)5.543.925.4826.514.435.686.813.534.34

The authors addressed some of my concerns. I still maintain the positive score.

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

This paper proposes MESCO, a method for training heatmap generators in the heatmap-guided MCTS paradigm for large-scale TSP without relying on solver-generated labels. During training, the heatmap predicted by the current model is used to guide many short MCTS rollouts, each with randomly sampled search parameters. The resulting tours are combined into a soft target through a quality-weighted vote on each node’s successor, and these targets are periodically recomputed as the model improves. A discrete diffusion model is trained on these soft targets, using a framework that does not require known solutions. Experiments on TSP-500, TSP-1000, and TSP-10000 show that MESCO is competitive with supervised diffusion methods on smaller instances and achieves the best reported gaps on the larger ones, while greatly reducing the cost of generating supervision. A preliminary extension to CVRP is also presented.

Critical strengths
  • The paper addresses a well-known bottleneck of supervised heatmap methods, namely the high cost of obtaining solver labels at large scale, which is a practically important problem.
  • The idea of aggregating many short, diversely configured MCTS rollouts into soft targets is simple and intuitive, and Table 1 gives a nice illustration that the ensemble recovers optimal edges that individual rollouts do not find.
  • The results on TSP-10000 are notable, as MESCO clearly outperforms both supervised methods and the parameter-free GT-Prior baseline at this scale.
  • The paper is clearly written, and the method, hyperparameters, and search configuration spaces are described in enough detail to follow and reproduce, with code and checkpoints provided.
Critical weaknesses

Overall, I find the motivation of this paper compelling: the cost of solver-generated labels is a real bottleneck for heatmap-guided methods at large scale, and a label-free alternative that learns from the search itself is an attractive direction. My main concerns are about the experimental evaluation, and I believe that making it more rigorous in the following aspects would make the paper considerably more convincing.

  1. Since reducing the cost of supervision is one of the main motivations of the paper, I think a more complete comparison of the resources required by MESCO and by supervised methods would be very valuable. Table 4 currently compares only the CPU time spent on label or target generation. It does not report the GPU time for training, the wall-clock time of the whole training pipeline, or the cost of the model forward passes used to produce heatmaps at each refresh. In addition, the caption describes the target cost as per refresh, while the numbers appear to correspond to the total over all refreshes, which would be good to clarify. The comparison is also affected by the very different training-set sizes: at TSP-10000, MESCO uses 200 training graphs while DIFUSCO’s cost is estimated for 6,400 labeled instances, so much of the 192× reduction comes from the dataset size rather than from the supervision method itself. The label cost is also estimated with default LKH-3 settings on the authors’ hardware, which may differ from the settings used in the original works. A fairer comparison would be to train a supervised model under a matched budget, for example with LKH-3 labels for the same 200 instances or with a cheaper LKH-3 configuration, and to report the full training cost of both pipelines. How would a supervised model perform under the same labeling budget as MESCO?
  2. MCTS is stochastic, but the paper does not report results over multiple runs or seeds, and the TSP-10000 test set contains only 16 instances. On TSP-500 and TSP-1000, the differences between MESCO and the strongest baselines are small (for example, 0.51% versus 0.53% for DIFUSCO at TSP-1000), and in the ablation study the differences between variants are only around 0.07 to 0.09 points. The ablation is also run only on TSP-500. Reporting means and standard deviations over several runs, and repeating at least part of the ablation at larger scales, where the method’s advantage is most pronounced, would help confirm that these differences are meaningful.
  3. It is not clear how much the diffusion model itself contributes to the results. The model uses only three denoising steps, and the justification for using diffusion relies on the comparison between DIFUSCO and Att-GCN under supervised training. An ablation that trains a simpler single-pass GNN with the same MCTS-ensemble targets would help separate the contribution of the proposed supervision signal from that of the diffusion architecture.
  4. The paper does not compare against classical solvers under a matched time budget. At TSP-10000, MESCO uses about 20 minutes in total (3.6 minutes for heatmap generation plus 16.65 minutes of MCTS), while LKH-3 is run with its default settings for about 98 minutes and used as the reference. It would be informative to report how LKH-3 performs with a time budget comparable to that of MESCO, since this would show more clearly where the heatmap-guided MCTS paradigm stands in practice, a concern also raised by Xia et al. (2024).
  5. All experiments use uniformly distributed instances in the unit square for both training and testing. It would be helpful to evaluate generalization to other distributions, such as clustered instances or TSPLIB instances, especially since the targets are generated from the model’s own heatmaps and could potentially be sensitive to distribution shift.
Questions for authors

See the weaknesses.

6 comments
AuthorsOpenReview ↗

Response to Reviewer Q5bV (1/6)

We thank the reviewer for the detailed and constructive review, and for finding the motivation compelling. Following the reviewer's suggestions, we made the evaluation more rigorous along each of the five lines raised. All new results are included in the revised paper, with changes marked in blue.

W1 (cost of supervision). We now measure every part of the cost of supervision on the same machine and the same problem instances. The new Table 6 (replacing Table 4 of the submission, and discussed in Section 5.4) reports label or target generation, training, and the sizes of the training sets:

Cost of supervision (Table 6 in the revision):

TSP-500TSP-1000TSP-10000
LKH-3 (default), CPU time per instance40.9 s89.1 s3,113 s
DIFUSCO, published training instances128,00064,0006,400
DIFUSCO, label cost (CPU-h)1,4541,5845,534
DIFUSCO, training (GPU-h)190283265
MESCO, training instances4,0002,000200
MESCO, target cost over all refreshes (CPU-h)402.5282.550.6
MESCO, training (GPU-h)5.43.44.5
LKH-3 labels for MESCO's instances (CPU-h)45.549.5172.9
MESCO target cost ÷ LKH-3 labels, same instances8.9×5.7×0.29×
  • Caption. The target cost of MESCO in the submission was the total over all target computations during training (7, 5, and 4 at the three scales: the initial computation plus every refresh), not the cost per refresh. The caption now says so.
  • Per instance, MESCO's targets cost more than LKH-3 labels at TSP-500 and TSP-1000, where LKH-3 is fast: 8.9× and 5.7× as much, respectively. At TSP-10000, where solver time dominates, MESCO's targets cost 3.4× less: 50.6 CPU-hours for its 200 training instances, compared with 172.9 CPU-hours to label the same instances with LKH-3, which takes about 52 minutes per instance.
  • On DIFUSCO's published TSP-10000 training set, the reduction is 109× (50.6 vs. 5,534 CPU-hours). Both factors behind this reduction come from MESCO's design. Because its targets are produced by search and refreshed during training, MESCO needs far fewer training instances (200 vs. 6,400, a factor of 32), and each instance is 3.4× cheaper to supervise.
  • Training. Training takes 5.4, 3.4, and 4.5 GPU-hours for MESCO at TSP-500, TSP-1000, and TSP-10000, respectively, compared with roughly 190, 283, and 265 GPU-hours for DIFUSCO with its published training sets (all measured on one RTX 3090, except DIFUSCO at TSP-10000, which needs more memory and was measured on an NVIDIA L40S). The forward passes used to compute the heatmaps at each refresh are negligible (about 15 s, 11 s, and 12 s per refresh; Appendix A.12).
  • End-to-end wall-clock time. On our reference machine, target or label generation plus training takes 34.2, 22.6, and 14.9 hours for MESCO (56.8 and 49.2 hours cumulative at TSP-1000 and TSP-10000, including the earlier stages that these models are fine-tuned from), compared with 227.8, 360.0, and 456.7 hours for DIFUSCO with its published training sets, and 25.4, 29.1, and 39.1 hours for DIFUSCO trained on MESCO's instances (Appendix A.12, new in revision).
AuthorsOpenReview ↗

Response to Reviewer Q5bV (2/6)

W1, continued (matched labeling budget). We trained DIFUSCO with LKH-3 labels on exactly MESCO's training instances (4,000, 2,000, and 200 instances at TSP-500, TSP-1000, and TSP-10000), using DIFUSCO's own training recipe (Appendix A.12, new in revision). Labeling these instances costs less than MESCO's targets at TSP-500 and TSP-1000, and more at TSP-10000 (Table 6), so the supervised model is never limited by a smaller labeling budget. Averaged over 5 decoding seeds, MESCO attains lower optimality gaps at every problem size: 0.230% vs. 0.620% at TSP-500, 0.550% vs. 0.587% at TSP-1000, and 1.100% vs. 1.658% at TSP-10000. The table also includes DIFUSCO trained on its published, much larger training sets.

Optimality gap (%) over 5 decoding seeds (Appendix A.12 in the revision):

ModelTSP-500TSP-1000TSP-10000
DIFUSCO, published training set0.403 ± 0.0100.580 ± 0.0082.350 ± 0.030
DIFUSCO, MESCO's training instances0.620 ± 0.0130.587 ± 0.0101.658 ± 0.017
MESCO0.230 ± 0.0150.550 ± 0.0101.100 ± 0.025

Regarding a cheaper LKH-3 configuration: at TSP-500 and TSP-1000, default LKH-3 labels for the full training set are already inexpensive (41–89 s per instance). At TSP-10000, LKH-3 cannot return any tour within MESCO's per-rollout budget of 20 s, because its candidate-set preprocessing alone takes about 107 s per instance (Appendix A.11).

AuthorsOpenReview ↗

Response to Reviewer Q5bV (3/6)

W2 (seeds and ablation). We now report results over 5 decoding seeds (Appendix A.7, new in revision).

Optimality gap (%) over 5 decoding seeds (Appendix A.7 in the revision):

MethodTSP-500TSP-1000TSP-10000
GT-Prior0.586 ± 0.0160.907 ± 0.0212.162 ± 0.028
DIFUSCO0.403 ± 0.0100.580 ± 0.0082.350 ± 0.030
MESCO0.230 ± 0.0150.550 ± 0.0101.100 ± 0.025
The seed-to-seed standard deviations are at most 0.03 percentage points for every method and problem size. Comparing the methods instance by instance under the same seed, MESCO is ahead of GT-Prior on every test instance at every scale, and its gap is lower than DIFUSCO's by 0.17, 0.03, and 1.25 percentage points on average at TSP-500, TSP-1000, and TSP-10000, respectively. The margin over DIFUSCO at TSP-1000 is small but consistent across seeds.

The ablation in Table 7 now also reports the mean over 5 decoding seeds; "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):

VariantRRefreshTargetEntropy termOptimality gap (%)
Best-of-R20✓one-hot✓0.260 ± 0.008
R = 55✓weighted✓0.262 ± 0.008
R = 11✓one-hot✓0.267 ± 0.023
Single refresh20weighted✓0.483 ± 0.010
No entropy term20✓weighted0.291 ± 0.012
MESCO20✓weighted✓0.230 ± 0.015
Every variant therefore has a higher gap than MESCO: by 0.03–0.04 percentage points for the ensemble variants, 0.06 without the entropy term, and 0.25 with a single refresh. These differences are larger than the seed-to-seed variation, so they are meaningful and not due to seed noise.
Reviewer_NQ83OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes MESCO, a self-supervised framework that replaces solver-generated labels with targets derived from Monte Carlo tree search (MCTS), cutting the cost of supervision for diffusion-based heatmap models in neural combinatorial optimization (NCO). On TSP instances with 500 to 10,000 nodes, MESCO attains the best reported optimality gaps at 1,000 and 10,000 nodes and is competitive with supervised methods at 500, while reducing the cost of supervision by up to 192× and keeping heatmap-generation time close to that of label-free methods.

Critical strengths
  • The motivation is clear, and the limitation of existing work (supervision becomes expensive at scale) is well identified and aligns with a central challenge in NCO. The proposed method addresses it directly, reducing the cost of supervision by up to 192×.
  • MCTS is placed inside the training loop rather than treated only as a post-hoc decoder, so the training signal is aligned with the search that actually determines test-time performance.
  • The paper is clearly written and easy to follow.
Critical weaknesses

While preliminary results on CVRP were provided in Appendix A7, the main evaluation is confined to synthetic TSP instances with uniformly distributed nodes. Results on TSPLIB or on other non-uniform distributions (e.g., clustered instances), would show whether the learned heatmaps generalize beyond the training distribution.

Questions for authors
  1. The method relies on MCTS, yet Section 6 states that any stochastic heatmap-consuming search would do. How much does MCTS add over cheaper alternatives (heatmap sampling + 2-opt, noisy beam search, random-restart local search)? In particular, if LKH-3 were given the same per-rollout budget with random seeds, would its tours already provide good enough supervision—and if so, what does the heatmap-seeded refresh loop add?
  2. How many CPU threads are used to collect the MCTS rollouts? If LKH-3 were given the same threads and wall-clock budget, how many labeled instances could it produce, and would a supervised model trained on that smaller labeled set already match MESCO?
  3. Summing heatmap generation and MCTS decoding, MESCO is slower than Concorde at TSP-500 (3.17 vs. 2.11 min) and no faster than LKH-3 at TSP-1000 (6.33 vs. 7.50 min), both of which reach 0% gap. Is it fair to say the advantage appears only at TSP-10000? If so, how does LKH-3 perform under a matched 20-minute (i.e., 3.6m + 16.65m) budget at that scale?

I would be willing to raise my score if the authors address the questions above.

2 comments
AuthorsOpenReview ↗

Response to Reviewer NQ83 (1/2)

We thank the reviewer for the thoughtful review, and for highlighting that MESCO aligns training with the search used at test time. We address each point below; all new results are included in the revised paper, with changes marked in blue.

W1 (TSPLIB and non-uniform instances). 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):

MethodTSP-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.
Zero0.950.760.881.701.721.753.734.195.18
SoftDist1.100.600.651.981.441.073.514.114.48
GT-Prior0.640.480.640.980.861.082.132.382.83
DIFUSCO0.910.590.640.810.690.613.032.863.05
MESCO0.290.200.260.660.550.741.321.671.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):

GroupZeroAtt-GCNDIMESUTSPSoftDistDIFUSCOFast-T2TGT-PriorMESCO
Medium (21 instances, 500–2000 nodes)15.2411.4710.6412.036.792.384.1810.082.70
Large (14 instances, more than 2000 nodes)5.543.925.4826.514.435.686.813.534.34
AuthorsOpenReview ↗

Response to Reviewer NQ83 (2/2)

Q1 (advantage of MCTS). MCTS reads the current model's heatmap, so the targets that it provides change as the model learns, which closes the training loop. The standard LKH-3 implementation does not take a heatmap as input, so the targets that it provides are fixed labels. We ran the requested ablation at TSP-500 (Appendix A.11, new in revision). We trained the same model on frozen targets from three sources, each with 20 rollouts at MESCO's per-rollout budget of 2.5 s: (a) tours sampled from the heatmap and improved with 2-opt, (b) short LKH-3 runs with random seeds, and (c) MCTS, as in MESCO. Averaged over 5 decoding seeds, the models trained on targets from (a), (b), and (c) attain optimality gaps of 0.256%, 0.171%, and 0.196% at TSP-500, respectively.

Optimality gap (%) at TSP-500 over 5 decoding seeds (Appendix A.11 in the revision):

Target sourceUses the heatmapOptimality gap (%)
(a) Heatmap sampling + 2-opt✓0.256 ± 0.004
(b) Short LKH-3 runs with random seeds0.171 ± 0.011
(c) MCTS (as in MESCO)✓0.196 ± 0.009

At this scale, the comparison naturally favors LKH-3, which finds near-optimal tours within 2.5 s. Both LKH-3 and MCTS targets clearly outperform the targets from heatmap sampling followed by 2-opt, which suggests that a weaker search produces weaker targets. However, LKH-3's advantage does not carry over to larger instances: at TSP-10000, LKH-3 with the same settings cannot return any tour within MESCO's per-rollout budget of 20 s, because its candidate-set preprocessing alone takes about 107 s per instance. The refresh loop itself matters most: if the targets are computed only once at the start of training, the optimality gap at TSP-500 more than doubles, from 0.230% to 0.483% (Table 7). We have also clarified the statement in Section 6, which now refers to "heatmap-guided stochastic search".

Q2 (number of threads, and a supervised model under a matched labeling budget). The MCTS rollouts use 36 threads. With the same machine, threads, and CPU time that MESCO spends on its targets, LKH-3 could label about 35,400, 11,400, and 58 instances at TSP-500, TSP-1000, and TSP-10000, respectively (Table 6). We therefore trained DIFUSCO with LKH-3 labels on exactly MESCO's training instances (4,000, 2,000, and 200), using DIFUSCO's own training recipe (Appendix A.12, new in revision). At TSP-10000, this gives the supervised model more labels than the matched budget allows. Averaged over 5 decoding seeds, MESCO attains lower optimality gaps at every problem size: 0.230% vs. 0.620% at TSP-500, 0.550% vs. 0.587% at TSP-1000, and 1.100% vs. 1.658% at TSP-10000.

Optimality gap (%) over 5 decoding seeds (Appendix A.12 in the revision):

ModelTSP-500TSP-1000TSP-10000
DIFUSCO, published training set0.403 ± 0.0100.580 ± 0.0082.350 ± 0.030
DIFUSCO, MESCO's training instances0.620 ± 0.0130.587 ± 0.0101.658 ± 0.017
MESCO0.230 ± 0.0150.550 ± 0.0101.100 ± 0.025

Q3 (comparison with non-learning-based methods). We ran LKH-3 with its default settings and a wall-clock limit equal to MESCO's total time, with one thread per instance as for MCTS. The results are in a new row of Table 2, with details in Appendix A.9. At MESCO's total time (3.17, 6.33, and 20.25 minutes at TSP-500, TSP-1000, and TSP-10000), LKH-3 attains optimality gaps of −0.02%, −0.01%, and +0.01%, respectively, where a negative gap means a tour shorter than the reference tour. For comparison, MESCO attains gaps of 0.22%, 0.51%, and 1.10% at the same three problem sizes (Table 2). The same holds when LKH-3 receives only the MCTS time or DIFUSCO's total time.

Optimality gap (%) of LKH-3 at MESCO's total time (new row of Table 2; Appendix A.9 in the revision):

MethodTSP-500TSP-1000TSP-10000
LKH-3, same total time as MESCO (3.17, 6.33, and 20.25 min)−0.02−0.01+0.01
MESCO0.220.511.10
MESCO's advantage is within the heatmap-guided MCTS paradigm, where it is the strongest method at TSP-1000 and TSP-10000, and we now say so explicitly in the paper. TSP-10000 is also where solver labels become expensive (Table 6) and where MESCO generalizes best to other distributions (Table 4).

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response (1/2)

We sincerely thank the Area Chair and all reviewers for their time and valuable feedback. This paper studies how to train heatmap generators for large-scale TSP without solver labels. MESCO is built on a key idea: the search that decodes the heatmap at test time can also produce the heatmap's training targets. Its contributions are:

  1. Self-supervision from MCTS ensembles. Many short MCTS rollouts with randomly sampled configurations, guided by the model's current heatmap, form heatmap targets: each rollout votes for each node's successor, weighted by its tour length. These heatmap targets recover optimal edges that no single rollout finds, and they are recomputed (refreshed) as the model improves.
  2. MCTS inside the training loop. To our knowledge, MESCO is the first heatmap-guided MCTS solver in which MCTS, the search used at test time, also generates the training targets. This addresses the misalignment between training and test time in heatmap-guided MCTS identified by Xia et al. (2024), where heatmaps are trained on solver tours but evaluated by what MCTS finds.
  3. A self-supervised diffusion framework for TSP that does not need solutions. Supervised diffusion models such as DIFUSCO and Fast-T2T start the forward process from a known tour. MESCO instead runs the full denoising process from noise and supervises it with the heatmap targets from the MCTS ensembles, so the self-supervision shapes every denoising step and no solutions are needed at any point. This self-supervision is cheaper than solver labels at large problem sizes such as TSP-10000, where classical solvers such as Concorde and LKH-3 become expensive.

In our experimental results, MESCO attains the best reported optimality gaps on TSP-1000 and TSP-10000, outperforming other state-of-the-art heatmap-guided MCTS methods on large-scale TSP.

In their initial reviews, the reviewers highlighted that:

  1. The paper addresses a central and practically important bottleneck in neural combinatorial optimization: the cost of supervision at scale.
  2. Combining many short, randomly configured MCTS rollouts into soft targets is intuitive (Table 1), and running MCTS inside the training loop aligns training with the search used at test time.
  3. The results are strong, especially on TSP-10000, the paper is clearly written and reproducible, and the CVRP extension suggests that the approach generalizes beyond TSP.

To address the questions raised, we added new experiments and clarifications that further support these points. All of them are included in the revised paper, with changes marked in blue:

  • Importance of the training loop. Refreshing the targets is the most important component of MESCO: if the targets are computed only once at the start of training, the optimality gap at TSP-500 more than doubles, from 0.230% to 0.483% (Table 7, mean over 5 decoding seeds). A single-pass network trained on the same targets matches or improves on the diffusion model at all three scales, which shows that the training signal, rather than the denoising architecture, drives MESCO's performance (Appendix A.10).
  • Cost of supervision. We measured the cost of supervision in every case on the same machine and problem instances (Table 6). At TSP-10000, labeling MESCO's 200 training instances with LKH-3 takes 172.9 CPU-hours, which is 3.4× more than the 50.6 CPU-hours that MESCO spends generating its targets for the same instances. Labeling DIFUSCO's published training set of 6,400 instances takes 5,534 CPU-hours, which is 109× more than MESCO's targets.
  • Supervised training on the same instances. We trained DIFUSCO with LKH-3 labels on exactly MESCO's training instances. MESCO attains lower optimality gaps at every problem size: 0.230% vs. 0.620% at TSP-500, 0.550% vs. 0.587% at TSP-1000, and 1.100% vs. 1.658% at TSP-10000 (Appendix A.12).
  • Source of the targets. The targets provided by MCTS lead to a lower optimality gap than those from a cheaper heatmap-guided alternative, heatmap sampling followed by 2-opt (0.196% vs. 0.256% at TSP-500), and at TSP-10000, LKH-3 cannot return a tour within MESCO's per-rollout budget of 20 s (Appendix A.11).
  • Robustness of the results. Across 5 MCTS decoding seeds, MESCO’s optimality gap varies by at most 0.03 percentage points (Appendix A.7). When GT-Prior and SoftDist are given MESCO’s total running time (heatmap generation plus MCTS) as extra search time, their gaps remain 1.7–3.0× MESCO’s gaps (Appendix A.8). Finally, we ran a time-matched LKH-3, that is, LKH-3 with a time limit equal to MESCO’s total running time (3.17, 6.33, and 20.25 minutes at TSP-500, TSP-1000, and TSP-10000). Time-matched LKH-3 matches the reference tour lengths at every problem size, which shows where the heatmap-guided MCTS paradigm stands against a strong classical solver given the same time budget (Table 2, Appendix A.9).
AuthorsOpenReview ↗

General Response (2/2)

  • Zero-shot transfer to TSPLIB and non-uniform instances. Without retraining (i.e., zero-shot transfer), MESCO attains the best gap in eight of nine settings on clustered, explosion, and implosion problem instances (Table 4), and ranks second and third of nine methods on the TSPLIB Medium and Large groups (Table 5). Since MESCO needs no solver labels, it can also be trained directly on such distributions, which we expect to improve these results further.

Summary of new experiments in the revision

We also clarify three details in the appendix: that the larger models are fine-tuned from the smaller ones, which Max_Candidate_Num values are sampled during training, and what a refresh is. We also correct the caption of the cost table (Table 4 in the submission, now Table 6), and report each ablation variant with its own tuned MCTS configuration over 5 decoding seeds (Table 5 in the submission, now Table 7). The table below lists every new experiment, its main result, and where it appears in the revised paper.

ExperimentMain resultLocation in the revision
LKH-3 with the same total time as MESCOLKH-3 reaches the reference objective at every problem size: optimality gaps of −0.02% (TSP-500), −0.01% (TSP-1000), and +0.01% (TSP-10000). Within the heatmap-guided MCTS paradigm, MESCO has the lowest gap at TSP-1000 and TSP-10000.Table 2 (new row), Appendix A.9
Zero-shot transfer to clustered, explosion, and implosion instancesMESCO has the lowest optimality gap in 8 of the 9 settings (3 distributions × 3 problem sizes). At TSP-10000, its gap is 0.8–1.1 percentage points lower than that of the next-best method in every distribution.Table 4, Appendix A.13
Zero-shot transfer to TSPLIB (35 instances)Mean optimality gap of MESCO: 2.70% on the Medium group (500–2000 nodes; 2nd of 9 methods) and 4.34% on the Large group (more than 2000 nodes; 3rd of 9 methods).Table 5, Appendix A.14
Measured cost of supervision, on the same machineAt TSP-10000, labeling MESCO's 200 training instances with LKH-3 takes 172.9 CPU-hours, 3.4× more than the 50.6 CPU-hours MESCO spends on its targets. Labeling DIFUSCO's published set of 6,400 instances takes 5,534 CPU-hours, 109× more.Table 6
End-to-end training timeTarget or label generation plus training at TSP-10000: 14.9 hours for MESCO vs. 456.7 hours for DIFUSCO with its published training set.Appendix A.12
Ablation over 5 decoding seeds (TSP-500)MESCO's optimality gap is 0.230%; every variant has a higher gap (0.260–0.291%), and computing the targets only once, without refreshing them, gives 0.483%.Table 7
Variance over 5 decoding seedsMESCO's optimality gap (mean over 5 seeds): 0.230% (TSP-500), 0.550% (TSP-1000), and 1.100% (TSP-10000), with standard deviations of at most 0.03 percentage points. MESCO is ahead of GT-Prior on every test instance.Appendix A.7
Equal total time and CPU-only inferenceGiven MESCO's total time (heatmap generation plus MCTS) as pure search time, GT-Prior and SoftDist still have 1.7–3.0× MESCO's optimality gap at every problem size (e.g., 2.09% and 3.25% vs. 1.10% at TSP-10000). CPU-only heatmap generation adds less than 1% to MESCO's total running time.Appendix A.8
Single-pass network trained on the same targetsOptimality gap of the single-pass network vs. the three-step model: 0.187% vs. 0.212% (TSP-500), 0.502% vs. 0.515% (TSP-1000), and 1.067% vs. 1.111% (TSP-10000).Appendix A.10 (Table 13)
Source of the targets (TSP-500)Optimality gap with targets from MCTS: 0.196%, vs. 0.256% with targets from heatmap sampling + 2-opt. At TSP-10000, LKH-3 returns no tour within MESCO's 20 s per-rollout budget.Appendix A.11
DIFUSCO trained on MESCO's training instancesOptimality gap of MESCO vs. DIFUSCO: 0.230% vs. 0.620% (TSP-500), 0.550% vs. 0.587% (TSP-1000), and 1.100% vs. 1.658% (TSP-10000).Appendix A.12

The individual responses address each reviewer's comments and questions and explain these findings in more detail. We thank the Area Chair and all reviewers again and look forward to the discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.