Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers
Authors: Xuanhao Pan
Chenguang Wang
Chaolong Ying
Ye XUE
Tianshu Yu
Venue: ICLR 2026 Poster (2026)
Keywords: Travelling Salesman Problem
Heatmap
Monte Carlo Tree Search
Combinatorial optimization
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: This study shows simple heatmaps and well-tuned MCTS can outperform complex heatmap-based approaches for the Travelling Salesman Problem, advocating for a balanced focus on both learning and search components.

Abstract: The ``Heatmap + Monte Carlo Tree Search (MCTS)'' paradigm has recently emerged as a prominent framework for solving the Travelling Salesman Problem (TSP). While considerable effort has been devoted to enhancing heatmap sophistication through advanced learning models, this paper rigorously examines whether this emphasis is justified, critically assessing the relative impact of heatmap complexity versus MCTS configuration. Our extensive empirical analysis across diverse TSP scales, distributions, and benchmarks reveals two pivotal insights: \textbf{1}) The configuration of MCTS strategies significantly influences solution quality, underscoring the importance of meticulous tuning to achieve optimal results and enabling valid comparisons among different heatmap methodologies. \textbf{2}) A rudimentary, parameter-free heatmap based on the intrinsic $k$-nearest neighbor structure of TSP instances, when coupled with an optimally tuned MCTS, can match or surpass the performance of more sophisticated, learned heatmaps, demonstrating robust generalizability on problem scale and distribution shift. To facilitate rigorous and fair evaluations in future research, we introduce a streamlined pipeline for standardized MCTS hyperparameter tuning. Collectively, these findings challenge the prevalent assumption that heatmap complexity is the primary determinant of performance, advocating instead for a balanced integration and comprehensive evaluation of both learning and search components within this paradigm.

Published as a conference paper at ICLR 2026
BEYOND THE HEATMAP: A RIGOROUS EVALUATION OF COMPONENT IMPACT IN MCTS-BASED TSP SOLVERS
Xuanhao Pan'si
Chenguang Wangb Chaolong Ying' Ye X2 Tianshu Yu
"School of Data Science, The Chinese University of Hong Kong, Shenzhen
SShnnzhen Research Institute of Big Data
SScooo of Intelligent Systems Engineering, Shenzhen Campus of Sun Yat-sen University Shenzhen, China
xxuanhacpan, chenguangwang, chaolongying) (etperyiggggniinnn @link. cuhk, edu. cn xuey57 i sysu. sysu.edu.c. edu.cn yutianshu@cuhkk.ed on
'quua contribution
ABSTRACT
The "Heatmap + Monte Carlo Tree Search (MCTS)" paradigm has recently emerged prominent framework for solving the Traveling Salesman Problem (TSP). While considerable effort has been devoted to enhancing heatmap sophisti- cation through advanced learning models, this paper rigorously examines whether this emphasis is justified, assessing the relative impact of heatmap complexity versus MCTS configuration. Our extensive empirical analysis across diverse TSP scales, distributions, and benchmarks reveals two pivotal insights: 1) The configu- ration of MCTS strategies strongly influences solution quality, underscoring the importance of systematic tuning to achieve optimal results and enabling valid com- parisons among different heatmap methodologies. 2) A rudimentary, parameter-free heatmap based on the intrinsic k-nearest neighbor structure of TSP instances, when coupled with an optimally tuned MCTS, can match or surpass the performance more sophisticated, learned heatmaps, demonstrating robust generalizability problem scale and distribution shifts. To facilitate rigorous and fair evaluations future research, we introduce streamlined pipeline for standardized MCTS hyper- parameter tuning. Collectively, these findings challenge the prevalent assumption that heatmap complexity is the primary determinant of performance, advocating instead for balanced integration and comprehensive evaluation of both learning and search components within this paradigm. Our code is available at: https: //gi tegithhub... com LOGO- CRROOOOCCUSSZZ/SS /beyond hea tetatttappsssss. mst.t
INTRODUCTION
The Traveling Salesman Problem (TSP) remains a fundamental challenge in combinatorial opti- mization, drawing considerable interest from theoretical and applied research communities. As an NP-hard problem, the TSP serves erucial benchmark for evaluating novel algorithmic strategies for finding optimal or near-optimal solutions efficiently (Applegate et al.) 2009). Its practical sig- nificance spans logistics, transportation, manufacturing, and telecommunications where efficient routing is paramount for cost minimization and operational improvement (Helsgaun 2017 Nagata and Kobayashi 2013). Recent machine learning advancements have spurred new methodologies for tackling TSP, notably the "Heatmap Monte Carlo Tree Search (MCTS)" paradigm (Fu et al. 2021). Leveraging learned heatmaps to guide MCTS refining solutions, this approach has demonstrated success on large-scale instances and inspired proliferation of methods (Qiu et al. 2022) Sun and Yang, 2023; Min et al., 2024p. This rapid development signals a maturing field where systematic evaluation, comparison, and validation of emerging techniques are increasingly essential.
Within this "Heatmap + MCTS" framework, primary research thrust has centered on enhancing heatmap generation, often through increasingly sophisticated learning models, from supervised learning (Fu et al., (02I) to diffusion models (Sun and Yang) 2023). The underlying assumption is
"Corresponding author; rutianshu@cure edu..cn

---

Published as a conference paper at ICLR 2026
often that heatmap sophistication directly translates to superior solution quality. But is this pursuit of complexity the only, or even optimal, path to performance gains? Has the impact of MCTS configurations- the search component responsible for translating heatmap guidance into concrete solutions-beet fully acknowledged and systematically investigated? Although numerous solvers have emerged claiming performance improvements, there remains lack of evaluation-centereed scrutiny regarding the actual influence of the MCTS component and the true necessity of intricate heatmap designs. Our work aims to address this gap, challenging the potential cognitive bias that "more complex heatmaps consistently lead to better performance" and providing clarity for researchers and practitioners.
This work presents a rigorous, iuauuttion-centere analysis of the "Heatmap + MCTS" paradigm for TSP. Our primary objective is to examine the deep impact of MCTS configurations and re-evaluate the necessity of heatmap complexity. The central argument of our evaluation is twofold: first, that strategic MCTS calibration substantially influences solution quality, demanding meticulous attention; and second, that our proposed GT-Prior-a simple, parameter-free k-nearest neighbor heatmap can rival or even surpass complex learned heatmaps while also demonstrating strong generalization ability, Our evaluation spans various heatmap generation methods, from sophisticated Saaning-basse models to this GT-Prior, and scrutinizes diverse MCTS hyperparameter settings. The empirical validation performed TSP instances of varying scales (TSP-500, TSP-1000, and TSP- 10000), covering diverse problem structures through various synthetic distributions (including uniform, clustered, explosion, and implosion) and established real-world TSPLIB benchmarks.
The novelty of this paper lies not in proposing a new state-of-the-art solver, but in the rigor of its evaluation process and the critical insights derived. Our contributions are primarily evaluative:
We empirically quantify and thereby reveal the offen-undeerstimated significance of MCTS configurations in optimizing TSP solutions. Fine-tuning MCTS parameters such as explo- ration constant and node expansion criteria demonstrably impacts solution quality, urging a re-prioritization in algorithm design.
We challenge the prevailing emphasis on heatmap complexity by demonstrating that a simple, parameter-free heatmap grounded in the k-nearest neighbor nature of TSP (termed GT-Prior in this work) exhibits strong performance and generalizability across diverse problem scales when combined with an optimized MCTS. This baseline serves to assess the added value of more intricate heatmap models.
We introduce streamlined MCTS hyperparameter tuning pipeline, offering a practical tool to facilitate fairer and more robust comparisons in future research on heatmap designs.
These findings collectively advocate for a more holistic understanding and balanced integration of learning and search components within the "Heatmap MCTS" paradigm. Our work seeks to guide future research towards frameworks that synergistically harness both components, leading to more efficient, robust, and practically deployable TSP solvers, all while aligning with the foundational motivation of this research line: to better solve large-scale TSP by any means.
2 HEATMAP + MCTS: BACKGROUND AND CURRENT PERSPECTIVES
This section outlines the foundations of the "Heatmap + Monte Carlo Tree Search" paradigm for solving the Traveling Salesman Problem. We formalize the TSP and its heatmap representation. describe the adapted MCTS framework, review key methodological developments, and examine the current perspectives that motivate evaluation.
2.1 TRAVELING SALESMAN PROBLEM DEFINITION
The Traveling Salesman Problem (TSP) is classic combinatorial optimization problem defined over a set of N points I = {(x,, y4 J
1 in the Euclidean plane, where each point denotes a city located at coordinates (z,, 9:) [0, 1J2 The Euclidean distance between any two cities and j is calculated by
d, Viz - )²,)² + (y/ ,2 The objective is to find the shortest closed tour that visits each city exactly once. This optimal tour represented permutation = (mi, m...... xx minimizing
2

---

Published as a conference paper at ICLR 2026
the total length:
N-1
L(mT)) = Σ dag d
(1)
The performance of feasible solution л is measured using the optimality gap:
(L(T) [(TT) 1) x 100%.
Gap
(2)
In the "Heatmap MCTS" paradigm, the solution process is guided by heatmap PN E [0, 1] where each entry PN This heatmap serves probabilistic prior that informs the subsequent search process.
sj represents the estimated probability that edge (i,j) appears in the optimal tour.
2.2 THE MONTE CARLO TREE SEARCH FRAMEWORK FOR TSP
Originally introduced by Fu et al. 202 to integrate learned heatmap priors with Monte Carlo search, this MCTS framework has become the de facto search backbone for heatmap-guidke TSP solvers. MCTS formulates the TSP as a Markov Decision Process (MDP), where each state represents a valid tour and actions correspond k-opt moves modifying the current solution. While many follow-up studies have reused its core procedure with only superficial adjustments, few have explored deeper search-centric refinements.
In this framework, the search begins by constructing an initial tour: edges are sampled with probability PSS where P& is the heatmap prior. The edge weight matrix W is initialized as Wi = 100 P. the access frequency matrix Q is set to zero, and the overall move counter M starts zero. Each node in the TSP graph maintains candidate During each simulation, set of k-opt moves is generated and evaluated using the potential function in Equation 33, guiding the search toward higher-quality tours through repeated updates and restarts.
proportional to e
1f
constrain future edge selections.
Wi Zi = 2
In(M +
+ +av
Qu +1
where 24 =Eids Wij normalizes the edge weights from node i, and a is an exploration coefficient. Edges with higher potential are more likely to be selected.
If a generated move yields shorter tour (AL < 0), it is accepted and applied. Otherwise, the search restarts from a newly sampled initial tour. After each move, MCTS updates the edge weights to reflect the observed improvement:
(LT))L(T) L(T') L(T))
[(T))
-1).
W., Wiy 3 exp
(4)
where 3 is the learning rate. The access matrix Q is incremented for all modified edges. The process iterates until a fixed time limit is reached, at which point the best tour encountered is returned.
2.3 EVOLUTION AND PREVAILING RESEARCH IN HEATMAP-GUIDER MCTS
The "Heatmap+ + MCTS" framework, introduced by Fu et al. 202 marked a significant shift in TSP research by pairing neural heatmap predictions with Monte Carlo Tree Search. Their method used attention-based GCNs to estimate edge probabilities, which then guided stochastic search to build high-quality tours. This design has inspired numerous variants focused on refining heatmap quality.
Subsequent efforts introduced more sophisticated models to enhance generalization and structure awareness. DIMES employed meta-learned GNNs (Qiu et al. 2022); DIFUSCO leveraged diffusion- based generative models (Sun and Yang 2023); and UTSP proposed unsupervised learning strategy (Min et al., 2024). More recently, SoftDist (Xia et al. 2024) explored a simpler, distance- based heatmap, reflecting growing skepticism toward model complexity.
However, while heatmap design has seen continuous innovation, the search component- MCTS has received comparatively less attention. Most prior works adopt default configurations with minimal tuning, and few report the impact of auxiliary steps such as sparsification or additional supervision. As result, the actual contribution of MCTS to overall performance remains under-investigated.
3

---

Published as a conference paper at ICLR 2026
2.4 CURRENT PERSPECTIVES AND POTENTIAL OVERSIGHTS
This disparity in research focus reflects several implicit views that have shaped the paradigm: 1) that heatmap complexity is the primary driver of performance, justifying the emphasis on model sophisti- cation; 2) that default or minimally tuned MCTS configurations are sufficient for fair comparison, suggesting the search process is either secondary or robust by design; 3) that MCTS itself is well understood, with its impact assumed to be stable across different problem scales and heatmap types.
We challenge these views through systematic evaluation. Our results show that MCTS tuning plays pivotal role-often matching or exceeding the effect of heatmap refinement-and that simple, parameter-free prior can outperform complex models when coupled with optimized search. These findings argue for more balanced and transparent evaluation framework in future work.
EVALUATION METHODOLOGY
This section outlines our experimental framework for rigorous evaluation of the "Heatmap MCTS" paradigm in solving the TSP. We aim to assess the distinct contributions of heatmap quality and MCTS configuration solver performance, ensuring fair and robust comparisons.
3.1 EVALUATION OBJECTIVES
Our evaluation structured to answer three central questions:
Q1:
To what extent does the configuration of the MCTS component influence solution quality when applied to diverse heatmap generation techniques?
Q2: Can a simple, parameter-free heatmap with an optimally tuned MCTS match or surpass complex learned heatmaps using default MCTS settings?
Q3: Which MCTS hyperparameters are most influential, and how does their impact vary with heatmap type and problem scale?
Addressing these questions requires a methodology that isolates MCTS effects for accurate perfor- mance attribution.
3.2 ENSURING FAIR COMPARISONS
Comparing "Heatmap + MCTS" TSP solvers is challenging as MCTS performance can be con- founding factor. Fixed MCTS settings in prior work may obscure true heatmap efficacy, as MCTS parameters significantly impact solution quality. A sophisticated heatmap might underperform with poorly tuned MCTS, while a simpler one could excel with optimized search.
To ensure fairness, methodology mandates dedicated MCTS hyperparameter tuning for each evaluated heatmap. This optimizes the search strategy for each heatmap's characteristics, enabling a more accurate assessment of its intrinsic value.
3.3 MCTS HYPERPARAMETER TUNING PIPELINE
We employ streamlined MCTS hyperparameter tuning pipeline for standardized and reproducible evaluations across different heatmap methods and TSP scales.
Tuning Method. The pipeline uses grid search over key MCTS hyperparameters. For each heatmap and problem scale (TSP-500, TSP-1000, 10000,, configurations evaluated on dedicated tuning dataset of synthetic TSP instances. The configuration yielding the best average optimality gap selected for subsequent test evaluations. This tuning performed independently for each heatmap.
Key MCTS Hyperparameters. Based on prior literature (Fu et al. 2021 Min et al., 2024 Xia ct al. 2024 and our own empirical sensitivity analysis, we tune the following key hyperparameters:
Alpha: Exploration coefficient (Equation B
Beta: Edge weight update aggressiveness (Equation 4h)
4

---

Published as a conference paper at ICLR 2026
Max Dax_Depth: Maximum lc for k-opt moves.
Max_Candidate Num Candidate edge set size per node.
Param_H: MCTS simulations per move.
Use_ Use_Heatmap: Boolean for using heatmap or not for initial candidate set construction.
The search space for these parameters is detailed in Table 12 in Appendix
H
3.4 ANALYTICAL TOOLS FOR HYPERPARAMETER IMPORTANCE
To quantify each MCTS hyperparameter's influence on solution quality, we use SHapley Additive exPlanations (SHAP) (Lundberg and Lee 2017: Lundberg et al., 2020). SHAP values, derived from game theory, attribute performance contributions to each parameter, providing model-agnostic insights into their importance.
3.5 EXPERIMENTAL SETUP
Heatmap Methods Evaluated.
Our framework is applied to diverse heatmap techniques:
Learning- -baeiingg-beed:: based: Att-GCN (Fu al.
2021). DIMES QQu et al. 2022). DIFUSCO (Sun and
Yang. 2023), UTSP (Min et al. 2024). ). -2 et al. 2024).
Distance-based parameterized: SoftDist (Xia et al. 2024).
Baselines: A non-informative Zero heatmap and our proposed GT-Prior (Section 5.1
Pretrained models or generation code are sourced from original authors where possible.
Datasets. Experiments use synthetic TSP instances (sizes 500, 1000, 10000) with a distinct tuning set for each size (128 instances for TSP-500/1000, 16 for TSP-10000; cities sampled uniformly from [0, (]3) and test sets sourced from Fu et al. (2021). Generalization is assessed on varied distributions generated following Fang et al. 2024) and TSPLIB (Reinelt) 1991) benchmarks. Ground-truth
solutions were obtained from Concorde (Applegate et al. 2009) (TS-5000 SSP-500/1000) or LKH-3 (Helsgaun 2017) (TSP-10000).
Evaluation Metrics. 1) Optimality Gap (Gap): Relative solution quality to best-known tours, as in Equation ( 2) Improvement: Gap reduction post-tuning versus default MCTS settings: 3) Time: Heatmap generation + MCTS execution (with MCTS time controlled by Time_Limit)
Computational Environment. All experiments were run AMD EPYC 9754 128-Core CPU with 256 GB of memory. MCTS runtime per instance Time_Lime N seconds. This methodology underpins the analyses and conclusions presented subsequently.
COMPONENT IMPACT I: THE CRITICAL ROLE OF MCTS CONFIGURATION
This section presents the empirical analysis of MCTS hyperparameter impact, leveraging the eval- uation framework and tuning pipeline detailed in Section 3.3 We first examine the sensitivity and importance of individual MCTS hyperparameters and then quantify the performance gains achieved through their systematic tuning-
4.1 MCTS HYPERPARAMETER SENSITIVITY AND IMPORTANCE
The MCTS hyperparameter tuning pipeline was executed using the search space specified in Table 12 in Appendix H This space includes configurations inspired by prior works (Fu et al. 2021 Min
al. 2024 Xia et al. 2024) and algorithmic analysis, with default settings highlighted in bold. The impact of these MCTS configurations on TSP solution quality was subsequently analyzed using SHAP values, which attribute performance changes individual hyperparameters. Positive SHAP values suggest an increase in solution length (worse performance). while negative values indicate a reduction (better performance).
5

---

Published as a conference paper at ICLR 2026
High
High
Hlghh
MCN
MCN MD
MCN
UH Alpha
Posture valie
UH
Pesture valie
Alpha
MD
Alpba
MD
H
Beta
Beta
1ow
1.w
1ow
0.00
0.0
SHAP value
SHAP value
SHAP value
(a) At-GGNN
(b) UTSP
(c) SoftDist
Figure 1: Beeswarm plots of SHAP values for three different heatmaps. MD: Max Max_ Se___, MCN:
Max_ Ca__adanddeeeeeee Num, H: Param H, UH: Use Heatmap. Each dot represents a feature's s SHAP value for one instance, indicating its impact on the TSP solution length. The x-axis shows SHAP value magnitude and direction, while the y-axis lists features. Vertical stacking indicates similar impacts across instances. Wider spreads suggest greater influence and potential nonlinear effects. Dot color represents the corresponding feature value.
Cap Ratornaa Oilectvve 180 laymbagggg scalel
Performance Spectrum (TSP-500)
Performance Spectrum
Spectrum ITSP-10000)
10e
20-
Best Tanced MCTS
Wurst Turne MCTS
Defaul
Figure 2: Box plots of the optimality gap (%) for various heatmap sources, scales, and MCTS settings.
Figure ! presents the SHAP value distributions for key MCTS hyperparameters across three rep- resentative heatmap models (Att-GCN, UTSP, and SoftDist) on TSP-500 instances. Additional plots for other models and problem sizes are provided in Appendix F The Max_Cand @date_NNu parameter consistently demonstrates strong, often positive, impact across these models, suggesting that reducing the candidate set size from very large defaults can improve both computational speed and solution quality. Max Max_Depth generally exhibits positive SHAP values, indicating that exces- sively deep k-opt explorations within MCTS can sometimes be detrimental to finding good solutions quickly. The parameters A Alpha (exploration coefficient) and Use_Hea Hea_eeaamppppp (determining initial candidate set construction) show mixed effects, revealing non-linear interactions where their optimal values and impact depend on the specific heatmap being used. For instance, Beta (edge weight update aggressiveness) shows a notable positive influence in the SoftDist model, implying that its default update strategy might be suboptimal. Conversely, P Param_ H (MCTS simulations per move) generally demonstrates minimal overall influence across the examined heatmaps within the tested ranges. These findings directly address Q3, pinpointing influential MCTS hyperparameters and the context-dependent nature of their effects.
4.2 QUANTIFYING PERFORMANCE GAINS FROM MCTS TUNING
To quantify the impact of MCTS configuration, we tuned hyperparameter sets within the given search space and report their performance spectrum. During hyperparameter tuning, the Lime_Limii for MCTS was set to 0.1 for TSP-500 and TSP-1000, and 0.01 for TSP-10000. Performance is reported as the Optimality Gap (Gap). UTSP is not evaluated on TSP-10000 due unavailability of corresponding heatmaps. The Zero heatmap's tuning involved setting Use_Heatmap to Falsel
Figure 2 illustrates the critical role of MCTS hyperparameter tuning, directly answering QT by demonstrating the extent to which MCTS configuration determines final solution quality across diverse heatmap generation techniques. The plotted gap is computed relative to borrowed test set reference objectives (not strict per-instance optima), so small negative gaps may occasionally appear
For the Zero heatmap, Hee__Hatmmay was Fall se, provides instance-specific information.

---

Published as a conference paper at ICLR 2026
(e.g., Fast-T2T on TSP-500). This impact is evident in the vast performance gap between best-tuned (green circles) and worst-tumed (red 'x' configurations; for instance, DIMES on TSP-10000 ranges from a 4.86% gap to crippling 91.31% based on MCTS settings alone. Consequently, default MCTS configurations (blue stars) are often far from best-perforning settings.
In essence, Figure 2 reveals that MCTS configuration is dominant performance factor. Effective tuning is not only beneficial but crucial, capable of substantially elevating solution quality for all types of heatmaps and enabling even basic priors to achieve strong results. This underscores the necessity of our streamlined MCTS tuning pipeline (Section 3.3) for rigorous evaluations and realizing strong solver performance. The specific MCTS configurations yielding the best-tuned results are in
Appendix H
This one-time hyperparameter tuning (conducted via grid search) is pre-computation step compara- ble in effort to training many learning-based heatmap methods and does not affect the MCTS inference time. Further tuning efficiencies can be realized through parallelization advanced hyperparameter optimization algorithms like SMAC3 (Lindauer et al. 2022). as discussed in Appendix
5 COMPONENT IMPACT II: RE-EVALUATING HEATMAP SOPHISTICATION WITH A RIGOROUS BASELINE
While Section established the critical role of MCTS configuration, this section evaluates the prevailing view that increasingly sophisticated heatmap models are the primary drivers of performance in the "Heatmap MCTS" TSP paradigm. We introduce and evaluate simple, parameter-free baseline, GT-Prior, derived from the intrinsic k-nearest neighbor structure of TSP solutions. By comparing GT-Prior (with optimized MCTS) against complex learned heatmaps, we assess whether the pursuit of heatmap complexity consistently yields justifiable performance gains, especially when the search component is already operating effectively, providing an answer to Q2) This analysis aims to provide a clearer perspective on the added value of intricate heatmap models and advocate for the inclusion strong, simple basclines in future methodological comparisons.
5.1 THE k-NEAREST PRIOR IN TSP
The k-nearest prior in TSP posits that optimal tour edges predominantly connect a city to one of its clos- neighbors. This empirical observation has been implicitly used constructing sparse graph inputs for learning models (Fu al. 2021; Sun and Yang
GT--Priee for Unifomo Distribution
TEP 1000
T5P 20000
0.5
Probbility Mass Fanetoe
0.4-
2023
Min et al. 2024), yet its direct use as a primary heatmap source has been less explored.
0.3-
400%
0.2
To elucidate the k-nearest prior, we conducted a com- prehensive analysis of (near-) optimal solutions for TSP instances of various sizes. Given a set of TSP instances I, for each instance I and its optimal solution, calculate the rank of the nearest neigh- bors for the next city: k {,, (1.,,...,NN) and count their occurrences nig. where n represents the num- ber of times of selecting the k-nearest cities in an instance's 's optimal solution. We then calculate the distribution:
0.1
0.9
0.0
Rank
the R-neseest neighbor
Figure 3: Empirical distribution of k-nearest neighbor selection optimal TSP tours
Tof N
(k))
k E (1,2..,,N
(5)
and average these distributions across all instances to derive the empirical distribution:
PP (b)
Σ PK)()), (1,
(6)
To quantify this prior empirically, we analyzed (near-) )optimal solutions for uniform TSP instances of varying sizes (TSP-500, TSP- 1000 using Concorde; 1SP-10000 using LKH-3). For each instance T
7

---

Published as a conference paper at ICLR 2026
Table 1: Results on large-scale TSP problems. Abbreviations: RL (Reinforcement learning). SL (Supervised learning), UL (Unsupervised learning), AS (Active search), G (Greedy decoding), S (Sampling decoding), BS (Beam-search). * indicates baseline for performance gap. f indicates methods using heatmaps of test set from Xia et al. (2024) with our MCTS setup. Some methods show two Time terms (heatmap generation and MCTS runtimes). MCTS times denote the equivalent sequential runtime per instance. Concorde and Gurobi results are sourced from Fu et al. (202 Quu ct al. (022).
METROD
TYPE
LENGTI
TSP-500
GAP
TIME: J
LENGTIL J
TSP-1000 GAP L
TIME J
LENGTI
TSP-10000
GAP
TIME
CONCORDE
OR(EXACT) OR(EXACT) ORGIURISTIC
16.55"
17.658
23.12"
3.12M
NIA
NAA
N/A
0.00%
N/A
N/A
1.KH3 (DIFAURA)
16.35
0.00%
843
23.12
0.00%
1.03M
21.77
28.73M
ZERO
MCTS
16.66
0.66%
0.00
50.065
23.39
1.16%
0.00M
167M
74,50
3.80%
0
16.65M
4.16
ATT-GON'
SL+MCTS
16.66
0.69%
50.065
23.37
1.09%
1.67M
73.95
3.03%
16.65M
DIMES!
RL=MCTS
16.66
0.43%
0.97
50.066
23.37
1.11%
2.0RM+
1.67M
73.97
3.06%
16.65M
4.63M+
UTSP!
UL+MCTS
50.068
1.37
23.47
1.53%
1.67M
SOFTDIST!
SOFTDIST-MCTS
16.62
0.44%
0.0038
50.065
23.30
0.80%
0.00X
1.674
73.89
2,95%
0.00M
16.65M
DIEUSCO!
SL+MCTS
16.60
0.33%
3.61M+
23.24
0.53%
11MM
73.47
2.37%
28.
16.65M
FAST-T2T
SL+MCTS
16.57
0.12%
0.50M++
50.065
23.27
0.65%
1.78M+
1.67M
74.80
4.22%
16.65M
7.7336+
GT-PRIO
MCTS
16.63
0.50%
0,000M+
23.31
0.85%
0.00M+
73.31
2.14%
0.00MM+
16.65M
from set I, and its (near-)optimal tour, computed the frequency n/ with which edge connects ni to the k-th nearest neighbor. The averaged empirical distribution PNx यें Eier TN' is shown in Figure 3 The results reveal strong locality: the probability of selecting one of the top nearest neighbors exceeds 94%, rising above 99% for the top 10. This distribution is highly consistent across TSP scales, finding that also holds for instances from different underlying distributions (see Appendix[] D for similar results).
Leveraging insights from the optimal solution, we construct the heatmap by assigning probabilities to edges based on the empirical distribution of the k-nearest prior (-). For each city in a TSP instance of size N, we assign probabilities to edges (i,j) as follows:
P. (kig), ky E ..))....N))
where kú is the rank of city j among i's neighbors in terms of proximity (see the detailed statistical results in Appendix DD. Importantly, this heatmap is parameter-fiee and scale-independent, thus requiring no tuning or learning phase.
5.2 PERFORMANCE DEMONSTRATION: CHALLENGING COMPLEXITY
We evaluated GT-Prior against various heatmap methods, all coupled with MCTS configurations tuned according to our pipeline (Section 3.3). This ensures that comparisons reflect the heatmap's intrinsic quality when its search partner is optimized, rather than differences in MCTS efficacy.
As shown in Table T GT-Prior, a simple parameter-free free heatmap, when combined with an optimally tuned MCTS, achieves performance highly competitive with, and in some cases (TSP-1OO00 superior to, far more complex learning-bass and TSSP-1000. GT-Prior yields optimality gaps of 0.50%, 0.85% and 2. 1,44, respectively. This performance is achieved with no heatmap generation time at inference, similar to SoftDist and Zero.
heatmap generators like DIFUSCO. For TSP-500, 1000,
Critically, the Zero heatmap, providing no edge guidance, still achieves respectable gaps (e.g., 0.66% for TSP-500) solely through tuned MCTS (where on distance for candidate selection). This underscores the substantial impact of the search component itself. The strong showing of GT-Prior and even the tuned Zero heatmap challenges the narrative that gains in TSP solutions primarily hinge on increasing heatmap model sophistication. It suggests that much of the solution quality can be attributed to well-calibrated search process acting on
is optimally set to False, relying
8

---

Published as a conference paper at ICLR 2026
Table Generalization performance of different methods trained on TSP-300 across varying TSP sizes (TSP-500, TSP-1000 the performance on the same scales during the test phase, while "Gen." represents the model's generalized performance different scales.
"Res Type" refers to the result type: "Ori." indicates
TSP-500
TSP- 1000
TSP-10000
GAP
DEGRADATION
GAP J
DECRADATION
GAP 4
DEGRADATION
DIMES
ORL/GENN
0.43% 433%
0.00%
1.11%/1.19%
0.08%
3.05%
1.24%
UTSP
ORI//GEN.
0.90%
0.00%
1.53%%/1 .44%
-0.09%
DIFUSCO
ORL/GENN
0.33%
0.00%
0.53%%O..866.
0.33%
2.36% 27%
2.91%
SOFTDIST
ORL//GEN
0.4356/0 43%
0.00%
0.80%
0.17%
2.94% (3.4%%3.90%
0.96%
FASI-121
ORI//GEN.
0.12%%-0. 12%
0.00%
0.65% 440%
0.75%
4.22% 16%
-0.06%
GT-PRIOR
ORL/GEN.
0.50%5/0.500%
0.00%
0.85%%/0.88%5
0.03%
2.14%
-0.01%
Table 3: Optimality gap (%, 1) across distributions and sizes. Lighter color indicates lower gap.
METHOD
TSP-500
TSP-1000
TSP-10000
CLUSTER
EXPLOSION
IMPLOSION
CLUSTER
EXPLOSION
IMPLOSION
CLUSTER
EXPLOSION
IMPLOSION
ZERO
0.29
0.58
0.67
1.22
1.14
1.23
1.81
2,53
2.37
ATT-GUN
0.74
0.58
0.65
1.10
0.96
1.00
112
1.57
59
UTSP
0.97
0.72
0.83
1.38
1.25
1.36
DIFUSCO
0. 0.88
0.65
0.74
0.53
0.42
0.32
1.96
2.50
2.42
FAST-12T
0.28
0.17
0.20
0.57
0.94
0.69
2.13
3.24
GI-PRIOR
0.51
0.38
0.49
0.70
0.63
0.74
0.35
0.93
0.58
fundamental problem characteristics, a point potentially understated evaluations that do not tune MCTS for simpler baselines.
5.3 GENERALIZATION ABILITY: ROBUSTNESS SIMPLICITY
We further assessed the generalization of GT-Prior by applying the prior derived from TSP-500 data to larger TSP instances 1000-1000, TSP-10000), as well as different distributions (derived from uniform and tested on other distributions), comparing against learned models under the same cross-scale evaluation.
Table rreveaas GT-Prior's robust generalization across scales. When the prior derived from uniform TSP-500 applied to TSP-100000 GT-Prior's performance degradation is minimal (merely a -0.01 % change in gap. effectively maintaining its 2.3% gap), substantially outperforming complex learned models like DIFUSCO, which sees its gap increase from 2.36% to 5.27% (a 2.91% % degradation). This suggests that simpler priors based on inherent problem structure (like k-nearest neighbors) may offer greater robustness and scalability than intricate learned patterns, which might overfit to training distributions scales.
This robustness extends to generalization across qualitatively different problem structures. As evidenced in Table 3 when MCTS settings (tuned uniform data, and the heatmap also derived from uniform data) are applied to instances from clustered, explosion, and implosion distributions, GT-Prior consistently maintains strong performance. For example, on TSP-10000 10000, GT-Prior achieves impressive optimality gaps of 0.35% (clustered), 0.93% (explosion). and 0.58% (implosion). These results frequently surpass those of more complex models like DIFUSCO (1.96%. 2.50%, 2.42% respectively) under these challenging cross- disttriitiiittionn test conditions. This highlights that GT-Prior's fundamental k-nearest neighbor prior is less susceptible to distributional shifts than learned patterns, which might inadvertently specialize to the characteristics of (typically uniform) training data. While sophisticated learning-base models can achieve excellent results certain cases, demonstrating the generalization ability of their learned features (c.g., DIFUSCO's strong performance across distributions). GT-Prior's consistent efficacy underscores the value of simple, structurally- grounded priors for achieving reliable generalization- key quality for practical and versatile TSP solvers. This resilience is a crucial evaluative aspect, particularly for solvers intended for diverse, large-scale applications.
TSP-1000
More generalization results of models trained on TSP-1000 and TSP-10000 are left Appendix and additional results TSPLIB instances are listed in Appendix G

---

Published as a conference paper at ICLR 2026
6 CONCLUSIONS
This study underscores the necessity of a more balanced and rigorous approach to the "Heatmap + MCTS" paradigm for the TSP. By empirically demonstrating the distinct impact of MCTS con- figurations and the competitive strength of a simple, parameter-Iree k-nearest prior when coupled with optimized search, our work challenges the prevailing emphasis on heatmap sophistication. The introduced streamlined MCTS hyperparameter tuning pipeline offers concrete pathway toward fairer and more insightful comparisons of future heatmap designs. Looking ahead, these evaluative insights encourage research trajectory that moves beyond isolated component optimization. By fostering synergistic, holistically understood, and optimized integration of learning and search, the field can develop TSP solvers that are not only high-performing but also more robust, efficient, and genuinely impactful.
ETHICS STATEMENT
The research presented in this paper, aimed at improving solutions for the Traveling Salesman Problem (TSP), has several potential societal impacts. On the positíve side, advancements in TSP solvers can directly enhance efficiency in sectors like logisties and manufacturing, leading to reduced fuel consumption, lower operational costs, and decreased environmental emissions. Our findings that simpler, well-tuned methods can be highly effective may also help democratize access to advanced optimization tools, allowing smaller entities to benefit without requiring massive computational resources.
Conversely, acknowledge potential negative impacts. As with many advancements in Al and automation, the increased efficiency from improved TSP solvers could contribute to job displacement in manual planning and routing roles. There also risk of unintended consequences exacerbating existing inequities if these tools are deployed without careful consideration of all relevant factors. Therefore, this work encourages a methodical approach building AI systems, emphasizing the importance of understanding and tuning all components. By demonstrating the power of simpler priors combined with careful search configuration, we advocate for solutions that are more transparent and robust, aligning with principles of responsible Al development. Continuous attention to faimesss robustness, and human oversight will be crucial as such technologies are deployed.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our research, provide comprehensive suite of resources. The complete source code, including scripts for hyperparameter tuming and result evaluation. is available at: fbttps://iitub: com/ LOGO- CUoOO--uuKS2/beyoodd- www.haaattaaaaeeeeeeeee casp-mts--e tss A detailed README file offers step-by-step instructions for setting up the computational environment and executing the experiments described in this paper. Our full evaluation methodology, experimental setup, datasets, and computational environment are described in Section 3.5 The specific MCTS hyperparameter search space and the best-tuned configurations used to produce our final results are detailed in the Appendix H and The procedure for generating our proposed GT-Prior is explained in Section [.1] The datasets used in our experiments were sourced from established benchmarks as cited in Section 3.5 and the generation code for synthetic instances is also provided.
ACKNOWLEDGMENTS
This work was supported by National Science and Technology Major Project under Grant 2022ZD01 16408.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
David I. Applegate, Robert E Bixby, Vašek Chvátal, William Cook, Daniel G Espinoza, Marcos Goy- coolea, and Keld Helsgaun. Certification of an optimal tsp tour through 35,900 cities. Operations Research Letters, 37( 37(1):11-15, 2009.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arX1v:1611.09940 2016.
Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. Advances in Neural Information Processing Systems, 35:31226-311 31238, 2022.
Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. Advances in neural information processing systems, 32, 2019.
Jinho Choo, Ycong-Dac Kwon, Jihoon Kim, Jeongwoo Jac, André Hottung, Kevin Tiemny, and Youngjune Gwon. Simulation- guided beam search for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:8760-877 8772, 2022.
Paulo R d O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian conference on machine learning, pages (65-480. PMLR, 2020.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and
Rousseau. Learning heuristics for the tsp by policy gradient. Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26-29, 2018, Proceedings 15, pages 170-181. Springer, 2018
Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. Invit: generalizable routing problem solver with invariant nested view transformer. arXiv preprint arXiv:2402.00
2024.
Zhang-Hun Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 7474-7482, 2021.
Keld Helsgaun. An extension of the teemiigaan-helsaure tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-980, 2017.
André Hottung, Yeong-Dae Kwon, and Kevin Tiemney Efficient active search for combinatorial optimization problems. arXiv preprint 17Xiv:2106005126 2021.
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint 10.059,1, 2021.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint (rXXiv:1906.01277.. 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 14:10418-10430, 2021.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:1936-1949, 2022.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations, 2019.
Yeong- Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 18 188-21198 198, 2020.

---

Published as a conference paper at ICLR 2026
Yeong- Brong-Dae Kwon, Jinho Choo, Iijoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Ma- trix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138-55 (1138-5149) 5149, 2021.
Yang Li, Jinpei Guo, Runzhong Wang. Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds up diffusion- based training- to-tessing solving for combinatorial optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng. Carolin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter. Smac3: A versatile bayesian optimization package for hyperparameter optimization. Journal of Machine Learning Research, 23(54):1-9) 2022.
Fei Liu, Xi Lin, Zhenkun Wang. Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1898-1908, 2024.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems 30, pages 4765-4774. Curran Associates, Inc., 2017.
Scout M. Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M. Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. Nature Machine Intelligence, 2(1):2522-5839, 2020.
Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprini 2019.
Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems, 36, 2024.
Yuichi Nagata and Shigenobu Kobayashi. A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS Journal on Computing, 25(2):346-363, 2013.
Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng. Li Zhao, Lei Song, and Jiang Bian. H-tsp: Hierarchically solving the large-scale traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9345-9353 2023.
Bo Peng. Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In Artificial Intelligence Algorithms and Applications: 11th International Symposium, ISICA 2019, Guangzhou, China, November 16-17, 2019, Revised Selected Papers 11 pages 636-650. Springer, 2020.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35:25531-25544 2022.
Gerhard Reinelt. Tsplib-a traveling salesman problem library. ORSA journal on computing, 3(4): 376-384, 1991.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural Information Processing Systems, 36:3706-3731, 2023.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
Chenguang Wang and Tianshu Yu. Efficient training of mult combinatorial neural solver with multi-armed bandits. arXiv preprint arXiv:2305.063361, 2023.
12

---

Published as a conference paper at ICLR 2026
Chenguang Wang, Yaodong Yang, Oliver Slumbers, Congying Han, Tiande Guo, Haifeng Zhang, and Jun Wang. A game- theoretic approach for improving generalization ability of tsp solvers. arXiv preprint arXiv:2110.15105, 2021.
Chenguang Wang, Zhouliang Yu, Stephen McAleer, Tianshu Yu, and Yaodong Yang. Asp: Learn universal neural solver! IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE transactions on neural networks and learning systems, 33(9): 5057-5069, 2021.
Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoc search-basee neural approaches for solving large-scale traveling salesman problems. In Proceedings of the s1 International Conference Machine Learning, pages 54178-54199
2024.
Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao. Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20284-20292 2024.
Jianan Zhou, Yaoxin Wu, Wen Song. Zhiguang Cao, and Jie Zhang. Towards onni-generalizable neural methods for vehicle routing problems. In International Conference Machine Learning. pages 42789. PMLR, 2023.
Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. Mvmoe: Multi-task vehicle routing solver with mixture-of-cxperts. arXiv preprint arX1v22405.0102, 2024.
13

---

Published as a conference paper at ICLR 2026
A ADDITIONAL RELATED WORKS
Approaches using machine learning address the Traveling Salesman Problem (TSP) generally fall into two distinct groups based on how they generate solutions. The first group, known as construction methods, incrementally forms path by sequentially adding cities to an unfinished route, following an autoregressive process until the entire path is completed. The second group, improvement methods, starts with complete route and continually applies local search operations to improve the solution.
Construction Methods Since Vincals et al. (2015): Bello et al. (2016) introduced the autoregressive
combinatorial optimization neural solver, numerous advancements have emerged in subsequent years (Deudon et al., 20188) Kool et al., 2019 Peng et al., 2020 woon et al.) 2020 (202)). These
include enhanced network architectures (Kool et al. 2019). more sophisticated deep reinforcement learning techniques (Khalil et al., 2017 Ma et al. [019 M Choo et al., (022). and improved training
methods (Kim et al., 2022 Bi et al. 2022). For large-scale TSP, Pan et al. (2023) adopts a hierarchical
divide-and-conquee approach, breaking down the complex TSP into more manageable open-loop TSP sub-problems.
Improvement Methods In contrast construction methods, improvement-basee solvers leverage neural networks to progressively refine an existing feasible solution, continuing the process until the computational limit is reached. These improvement methods are often influenced by traditional local search techniques like k-opt, and have been shown to deliver impressive results in various previous
studies (Chen and Tian 2019 Wu al.) 202T] Kim al. 2021 Hudson al. 2021). Ye al. (2024)
implements a divide-and ande-ad--oon and-conquerr approach, using search-based based methods to enhance the solutions of smaller subproblems generated from the larger instances.
Recent breakthroughs in solving large-scale TSP problems (Fu et al. 2021, Qiu et al. 2022 Sun and Yang 2023 Min et al., 2024; Xia et al. 2024) have incorporated Monte Carlo tree search (MCTS) as effective post-procesd pest-processing technique. These heatmaps serve as priors for guiding the MCTS, resulting in impressive performance in large-scale TSP solutions, achieving state-of-the-ar results.
Other Directions In addition to exploring solution methods for combinatorial optimization prob- lems, some studies investigate intrinsic challenges encountered during the learning phase. These include generalization issues during inference (Wang et al. 2021 Zhou al. 2023; Wang et al.)
2024) and multi-tasi learning (Wang and Yu 2023 developing foundational models.
Liu et al. 2024 Zhou et al. 2024) aimed at
B IMPACT OF HEURISTIC POSTPROCESSING
In our experimental reproduction of various learning- heatmap generation methods for the Traveling Salesman Problem (TSP), we identified critical yet often overlooked factor affecting performance: the post-processing of model-generated heatmaps. This section details the post- processing strategies employed by different methods and evaluates their impact performance metrics.
B. POSTPROCESSING STRATEGIES
DIMES DIMES generates an initial heatmap matrix of dimension n x from a k-nearest neighbors (N-NN) subgraph of the original TSP instance (k 50). The post-processing involves two steps:
Sparsification: Retaining only the top-5 values for each row, setting all others to a significantly negative number.
Adaptive softmax: Iteratively applying a temperature- scaled softmax function with gradual temperature reduction until the minimum non-zero probability exceeds predefined threshold.
DIFUSCO DIFUSCO also generates a sparse heatmap based on the N--N subgraph (k 50 for TSP-500, A 100 for larger scales). The post-processing differs based problem scale:
14

---

Published as a conference paper at ICLR 2026
Table Performance Degradation for Different Methods with and without Postprocessing on TSP- 500, TSP-1000, and TSP-10000. 'W" indicates with postprocessing, while "W/O' indicates without postprocessing.
METHOD
POSTPROCESSING
TSP-500
TSP-1000
TSP-10000
GAP
DEGRADATION
GAP 4
GAP 4
DEGRADATION
2.50%
15.87%
DIMES
0.93%
6.77%
12.81%
W
1.57%
2.30%
3.05%
W/O
4.50%
6.30%
1.36%
3.14%
4.20%
W/O
2.33%
0.66%
45.20%
DIFUSCO
1.88%
-0.40%
42.52%
0.45%
1.07%
2.69%
For TSP-500 and TSP-1000: A single step integrating Euclidean distances, thresholding, and symmetrization.
2. For TSP-10000: Two steps are applied sequentially: a) Additional supervision using a greedy decoding strategy followed by 2-opt heuristics. b) The same process used for smaller instances.
UTSP UTSP's post-processing straightforward, involving sparsification of the dense heatmap matrix by preserving only the top 20 values per row.
Fast-T2T We use minimal post-processing: apply softmax to final-step logits and take the edge- existence probability as the heatmap. For sparse k-NN outputs, we map scores dense matrix and symmetrize by max Hig. Hyy) before MCTS.
Note. The original Fast-T2T (Li et 2024) paper does not provide MCTS-specific results. Therefore, we adopt the simple post post-processing above for our reproduction.
B.2 EXPERIMENTAL RESULTS
We conducted experiments the test set for heatmaps generated by these three methods, both with and without post-processing, using the default MCTS setting. Results are presented in Table
Our findings reveal that heatmaps generated without post-processing generally exhibit performance degradation, particularly for TSP-10000, where the gap increases by orders of magnitude. This underscores the importance of sparsification for large-scale instances and highlights the tendency of existing methodologies to overstate their efficacy in training complex deep learning models.
Interestingly, DIFUSCO's heatmap without post-processing outperforms its post-processed coun- terpart for TSP-1000, suggesting that the DIFUSCO model, when well-trained on this scale, can generate helpful heatmap matrices guide MCTS without additional refinement.
These results emphasize the critical role of post-processing in enhancing the performance of learning- based heatmap generation methods for TSP. particularly as problem scales increase. They also highlight the need for careful evaluation of model outputs and the potential for over-reliance on post-processing mask limitations in model training and generalization.
The substantial performance gap between heatmaps with and without post-pon post-processing raises questions about the extent to which the reported performance gains can be attributed solely the learning modules of these methods. While the learning components undoubtedly contribute to the overall effectiveness, the significant impact of post-processing suggests that the raw output of the learning models may not be as refined or directly applicable previously thought.
In light of these findings, we recommend that future research on heatmap- based methods for TSP provide detailed description of their post-processing operations. Additionally, we suggest reporting results both with and without post- prot-processing to offer a more comprehensive understanding of the method's 's performance and the relative contributions of its learning and proceeson components. This approach would foster greater transparency the field and facilitate more accurate comparisons between different methodologies.
15

---

Published as a conference paper at ICLR 2026
C ANALYSIS OF ONE-OFF COMPUTATIONAL COSTS
To ensure a holistic comparison, we analyze the one-off setup costs: model training for learning-basee baselines versus hyperparameter tuning for MCTS.
Training Costs. [ubbee]summriize the training times reported in original papers. Deep learning methods typically incur heavy computational overheads, requiring significant GPU hours (e.g.. ~0 hours for DIMES on TSP-100000
Table 5: Approximate training times for learning-based methods. Note: Times are rough references due to hardware variances.
Method
TSP-500
TSP-1000
TSP-10000
All-GNN DIMES
~55 h
~55 h
25 h
~1.5
~v.77
~10 h
UTSP
~0.55
N/A
N/A
Tuning vs. Training. MCTS tuning is comparable one-off cost but is generally more resource- efficient. Using SMAC3 (detailed Appendix D. tuning MCTS for TSP-10000 requires only 3.47 hours on CPU. This is notably lower than the GPU-intensive training required for basclines like DIMES. Furthermore, the resulting configurations (Table 13) are reusable across similar distributions.
GT-Prior Construction. The cost of constructing GT-Prior is negligible. It requires solving only a small set of instances (e.g., 128 for TSP-500) to extract k-NN statistics, avoiding the expensive pre-training phase entirely.
D FULL EXPERIMENTAL RESULTS
The following table presents the complete results of the large-scale TSP problems, including the four end-to-end learning based methods that were previously omitted in the main paper due to space constraints. These methods include EAN O Costa et al. 22200), A.M (Kool et al. 2019), GCN (Joshi) et al. 2019), and POMO+EAS (Hottung et al. 2021). ). We also included a more recent heatmap method: F2st- al. 2024). The methods listed here employ reinforcement learning (RL), supervised learning (SL), and unsupervised learning (UL) techniques, in addition to various decoding strategies such as greedy, sampling, and
baased
Complementing these, we introduce specific comparisons with greedy decoding and plain 2-opt to isolate the impact of the search mechanism. The greedy results exhibit large optimality gaps (e.g.. >50%), confirming that myopic decisions inevitably discard critical distributional information found in the heatmaps. Similarly, while plain 2-opt improves solution quality, it lags significantly behind MCTS large-scale instances (TSP-10000). This performance gap highlights that local search alone insufficient to escape local optima at this scale, validating the necessity of MCTS for providing high-level global guidance.
16

---

Published as a conference paper at ICLR 2026
Table 6: Full Results on large-scale TSP problems, Abbreviations: RL (Reinforcement learning), SL (Supervised learning), UL (Unsupervised learning), AS (Active search), G (Greedy decoding). (Sampling decoding), and BS (Beam-search). * indicates the baseline for performance gap calculation. i indicates methods utilizing heatmaps provided by Xia et (2024), with MCTS executed on our setup. Some methods list two terms for Time, corresponding to heatmap generation and MCTS runtimes, respectively. Concorde and Gurobi results are sourced from Fu et al. (02Th: Qiu al.
(2022)
TSP-500
TSP-1000
TSP: DSP-00000
Method
Typo
Length
Gap
Length
Gap-]
Length
Gap L
Conzorde
(R(extct)
16.55'
17.65s
23. 13.12"
3.12m
N/A
N/A
NEA
Gurobi
OR(exact)
0.00%
N/A
LKH-3 (default)
(RDeariitic)
16.55
0.00%
14.84s
23.12
0.00%
1,02m
71.27"
28.73m
Nearest Insestion
OR
20.62
24.59%
0.00:
28.96
25.26%
0.00s
90.51
26.12%
0.38s
Random Insestion
12.21%
0.00s
14.05%
Farthest Insertion
OR
18.30
10.57%
0.00s
25.72
11.25%
0.00s
80.59
12.30%
0.38s
EAN
RL
28.63
73.03%
9.46s
50.30
117.5990
17.38s
N/A
N/A
N/A
HAN
R1A8-2-opt
23.75
43.57%
27.07s
47.73
106.46%
2,53m
N/A
N/A
N/A
AM
RL.4G
20:02
20.99%
0.71s
31.15
34.75%
1.49%
141.68
97.40%%
22. 464
AM
RL+BS
19.53
18.03%
10.31s
29.90
29.23%
46.12s
129.40
80.29%
6.79m
GCN
SL+G
29.72
79.61%
3.13
18.62
29%
13.57%
N/A
NA
NIA
GCN
83.55%
17.82s
121.73%
N/A
POMO-EAS-Emt
16.25%
POMO-EAS-Lay
RL+AS
19:35
16.92%
7.50m
NIA
N/A
NIA
N/A
N/A
NIA
PAS--EAS-
RLAAS
24.54
48.22%
5.44m
49.56
114.36%
29.74m
NIA
N/A
N/A
7em
MCTS
16.66
0.66%
0.00mm
50.06s
23.39
1.16%
0.00m=
1.67m
74.50
3 3.00%
0.00m+
16.65m
0.73m
AULGCNI
SL+2-opt
17:42
5.27%
0.52mm
50.06s
24.77
7.16%
0.73m
1.67m
79.48
10.73%
4. 4.16me
16.65m
16.65 65.65
Steeryyyy
30.71
85.63%
0.52mm
0.02s
50,65
119.11%
0.73m=
0.05s
3044
324.769
4.1 11mm+
2.13s
DIMES'
0.97m
50.06s
2.08m
1.67m
3.06%
4.65m
16.65m
2l.+2-ope
17.58
6.26%
25.00
8.15%
93.56
30.35%
16.65m
0.97mm
2.08m
4.65m=
RL+Groedy
51.43
210.82%
0.02s
95.18
311.72%
0.05s
771.78
975.249
2.17s
3.35m
UTSP!
UL+MCTS
16.69
0.90%
1.37m-
50.06s
23.47
1.53%
3.35m
1.67m
Ul.x2.opt
17.59
6.32%
50.
25.03
8.28%
1.37m-
3.35m=
UL+Greedy
25.48
51.00%
0.02s
39.46
70.70%
0.05s
0.00h*+
ScADs+MMTTS
16.62
0.43%
50.06s
23.30
0.80%
1.67m
73,89
2.95%
16.65m
SofDiit
2ofo
17.50
5.75%
0.00m
24.82
7.34%
0.00m
10.21%
0.00m
16.65m
SonDistGreedy
20.87
26.13%
0.00m
0.02s
29.06
25.69%
0.00m=
0.05s
91.43
27.39%
0.00m
2.26s
28.5
SL+MCTS
16.60
0.33%
56.06s
23.24
0.53%
1.67m
73,47
2.37%
15.65m
DIFUSCO'
Sl.+2-opt
16.69
0.89%
3.61
24.38
5.45%
11. 11.86m++
78.78
9.76%
53
SL+Greedy
18.92
14.36%
3.61m
0,024
36.90
59.61%
11.86m
0.05s
120.53
67.92%
28.51m
2.13s
L.78m+
7.73m+
T2T
SL+MCTS
16.57
0.12%
56.
23.27
0.65%
1.67m
74.80
4.22%
16.65m
Sl.+2-opt
16.71
0.99%
0.50m
23.92
3.48%
1.78m=
112.99
57.42%
16.65m
7.73
SL+Greedy
18.32
10.75%
0.50m
0,024
25.89
11.98%
1.78mm
0.05s
101.05
40.78%
7.7 mm
2.23s
0.00m
Priari
Pris+MCCS
16.63
0.50%
50.06s
23.31
0.85%
1.67m
73.31
2.14%
15.65m
Price+2-opt
0.00m
0.00m
10.61%
0.00mm+
PriortGreedy
25.69
$5.27%
0.00m
0,024
40.45
74.99%
0.00me
0.05
197.77
175.53%
0.00m
2.26s
17

---

Published as a conference paper at ICLR 2026
E ADDITIONAL HYPERPARAMETER IMPORTANCE ANALYSIS
We employed the SHAP method to analyze hyperparameter importance across all conducted grid search experiments. Most resulting beeswarm plots for TSP-500, TSP-1000, and TSP-10000 in Figure 4 (including 'Zero' heatmap where Use_Heatmes is set to False). Plots of the UTSP heatmap are presented in Figure
The patterns of TSP-1000 are similar to those of TSP-500, as discussed in Section 4.1 However, the patterns for 1S000 show major difference, where the influence of Max Candidate Num and Uise_Heatmap becomes dominant. Furthermore, their SHAP values are clearly clustered rather than continuous, as observed in smaller scales. This could be explained by the candidate set of large-scale TSP instances having major impact on the running time of MCTS k-opt search. Additionally, the time limit setting causes the performance of different hyperparameter settings for Caw__aanddattee..ac
and tse_Heatmap to become more distinct.
F ADDITIONAL GENERALIZATION ABILITY RESULTS
Table 7 presents additional results the generalization ability of various methods when trained on TSP- IS0- and TSP-10000, respectively.
For models trained on TSP-1000, GT-Prior continues demonstrate superior generalization capability, When generalizing to smaller instances (TSP-500), GT-Prior shows minimal performance degradation (0.02%), comparable DIMES and better than UTSP and SoftDist. For larger instances (TSP- 10000), GT-Prior maintains consistent performance with a slight improvement (-0.02% degradation), outperforming all other methods. DIFUSCO, while showing good performance TSP-500 and TSP-1000, experiences significant degradation (2.91% 1)) when scaling to TSP-10000.
The results for models trained TSP-10000 further highlight GT-Prior's robust generalization ability. When applied to smaller problem sizes (TSP-500 and TSP-1000), GT-Prior exhibits minimal performance degradation (0.01% % and 0.02%, respectively). In contrast, other methods show more substantial degradation, particularly for TSP-1000. Notably, SoftDist experiences severe perfor- mance deterioration (73.36%) when generalizing to TSP- P-000 while DIFUSCO shows significant degradation for both TSP-500 (0.63%) and TSP- 1000 (2.74%).
These results consistently demonstrate GT-Prior's exceptional ability to generalize across various problem scales, maintaining stable performance regardless of whether it is scaling up or down from the training instance size. This stability is particularly evident when compared to the other methods, which often struggle with significant performance degradation when generalizing different problem sizes.
18

---

Published as a conference paper at ICLR 2026
High
High
High
MCN
MCN
MCN
Peature valse
Peature valos
Feature sulsc
MD
MD
Alpha
Alyba
Alpha
Beta
Beta
Beta
Low
0.0
0.5
0
20
SHAP value
SHAP value
SHAP value
(a) Zero, TSP-500
(b) Zero, TSP-1000
(c) Zero, TSP-10000
High
High
High
MCN
MCN UH
UH MCN
UH
Reauee value
Poauue value
Foauue value
Alpha
Alpha
MD
MD
MDD
Alpha
H
Bota
Beta
Beta
-0125
0.00
0.25 value
0.50
-0.5
0.0
0.5
valne
(d) Att-GCN, TSP-500
(e) Att-GCN, TSP-1000
(I) Att-GCN, TSP-10000
High
High
High
MCN
Alpha
Pourue value
MCN
Fostus value
MCN
Fostue ville
UH
Alpba
MD
MD
MD
Beta
H
Beta
Alpha
Beta
H
H
-0.55
0:00
0.25
0.50
-055
0.5
value
value
SHAP value
DIMES, TSP-500
(h) DIMES, TSP-1000
(i) DIMES, TSP-10000
High
High
High
MCN
UH
MCN
UH
Fosture value
MCN
Pesture value
UHI
Fosture value
Alpha
Alyba
MD
MD
MDD
Alpha Beta
H
H
Beta
Beta
Low
Low
Low
0.1
0.0
0.5
SILAP value
SHAP valno
SHAP value
(i) DIFUSCO, TSP-500
(k) DIFUSCO, TSP-1000
DIFUSCO, TSP-10000
MCN
MCN
MCN
UH
Postue valie
UH
Fomnre vañuo
UH
Postue value
Alpha
MD
MD
MD
Alybox
Alpha
Reta
Bata
Beta
Low
1uw
Low
0.0
SHAP value
SHAP value
SHAP value
(m) SofiDist, TSP-500
(n) SofiDist, TSP-1000
(0) SoftDist, T0P-10000
MCN
MCN
MCN
UH
Postuce value
Fostuee valso
Fostwe walse
Alpha
Alyba MD
MD
MD
Alpha
11
H
Beta
Beta
Low
Low
Low
-0.25
0.00
0.5
0.50
-0.5
0LU
0.5
SHAP value
SHAP
value
SHAP value
(p) GT-Prior, TSP-500
(q) GT-Prior, 100-
(r) GT-Prior, 1000
Figure 4: Beeswarm plots of SHAP values for six methods across different TSP sizes.
19

---

Published as a conference paper at ICLR 2026
High
High
MCN
MCN
MD
Postuee value
MD
UTI
UH
Posture:
Alpla
Algba
H
Bera
Beta
Low
-0.5
0.0
SHAP value
SHAP value
(a) UTSP, TSP-500
(b) UTSP, TSP-1000
Figure 5: Beeswarm plots of SHAP values for the UTSP heatmap across different TSP sizes.
Table 7: Generalization on the model trained on TSP-1000 (the upper table) and TSP-10000 (the lower table).
TSP-500
TSP-1000
TSP-10000
METHOD
RES TYPE
GAP
DEGRADATION
GAP
DEGRADATION
GAP 4
DEGRADATION
ORL GEN.
0.69%
1.11%
3.05% 4.06%
DIMES
0.02%
0.00%
1.01%
0.71%
1.11%
ORI. GEN.
0.90%
UTSP
0.96%
0.06%
1.53%
0.00%
ORL. 0.33%
0.53%
2.36%
DIFUSCO
-0.07%
0.00%
2.91%
GEN.
0.26%
0.53%
5.27%
ORL. 0.43%
0.80%
2.94%
SOFTDIST
0.08%
0.00%
0.74%
GEN.
0.51%
0.80%
3.68%
ORL GEN.
0.12%
0.65%
4.22%
FAST-T2T
0.11%
-0.01%
0.65%
0.00%
3,30%
-0.92%.
ORI. GEN.
0.50%
0.85%
2.13%
GT-PRIOR
0.02%
0.00%
-0.02%
0.52%
0.85%
2.11%
TSP-500 DEGRADATION
TSP-1000 DEGRADATION
TSP-10000
METHOD
RES TYPE
GAP
GAP
GAP | DEGRADATION
ORI. GEN.
0.69%
1.11%
3.05%
DIMES
0.75%
0.06%
1.18%
0.07%
3.05%
0.00%
ORI. 0.33%
0.53%
2.36%
DIFUSCO
0.63%
2.81%
0.00%
GEN.
0.95%
3.34%
2.36%
ORI. 0.43%
0.80%
2.94%
SOFTDIST
0.22%
73.44%
0.00%
GEN.
0.65%
74.24%
2.94%
ORI. 0.12%
0.65%
4.22%
FAST-T2T
0.23%
0.06%
0.00%
GEN.
0.35%
0.71 %
4.22%
ORI.
0.50%
0.85%
2.13%
GT-PRIOR
0.01%
0.04%
0.00%
GEN.
0.51%
0.89%
2.13%
G ADDITIONAL RESULTS ON TSPLIB
We categorize all Euclidean 2D TSP instances into three groups based on the number of nodes: Small (0-500 nodes), Medium (500-2000 nodes), and Large (more than 2000 nodes). For each category, we evaluate all baseline methods alongside our proposed GT-Prior.
We conducted MCTS evaluations under three distinct parameter settings: (1) Tuned Settings, opti- mized using uniform TSP instances as listed in Table 14 whose results are shown in Table (2) the Default Settings, originally employed by Fu et al. (2021). whose results are shown in Table I0 and (3) the Grid Search setting where the MCTS hyperparameters are obtained by instance-level grid search, whose results shown in Table 1T] The results in these tables showcase the performance of the methods in terms of solution length and optimality gap, highlighting the effectiveness of the proposed GT Prior approach.
The data Table 8 particularly under the 'Tuned on TSPLIB' setting, further emphasizes the critical role of hyperparameter selection tailored to the specific data distribution. Here, our proposed
20

---

Published as a conference paper at ICLR 2026
Table 8: Generalization performance testing of different methods on TSPLIB instances. The best results in the row are shown in bold and the second-best underlined.
MCTS Setting
Au-GCN
DIMES
UTSP
SoftDist
DIFUSCO
Fast-T2T
GT--Prior
Tuned TSPLIB
0.06%
0.05%
0,08%
0.10%
0.06%
0.07%
0.05%
0.05%
Small
Tuned Uniform
0.79%
0.67%
0.48%
0.45%
1.23%
0.58%
0.10%
0.77%
Default
0.87%
0.67%
16.01%
7.16%
1,80%
1.06%
0.96%
0.20%
Tuned on TSPLIB
1.18%
0.76%
0.97%
1.54%
0.74%
0.35%
0.46%
0.55%
Medium
Tuned Uniform
15.24%
11.47%
10.64%
12.03%
6.79%
2.38%
4.18%
10.08%
Default
4.89%
3.73%
4.06%
13.58%
7.20%
2.87%
5.82%
3.63%
Tuned on TSPLIB
5.39%
3.58%
4.55%
5.75%
3.03%
3.47%
3.23%
2.42%
Large
Tumed on Uniform
5.54%
3.92%
5,48%
26.51%
4.43%
5.68%
6.81%
3,53%
Default
6.51%
4.84%
391 8998
1481,66%
11.36%
12.62%
25.77%
5.51%
GT-Prior method consistently demonstrates strong performance, achieving the leading optimality gap for Large instances (2.42%) and tying for the best on Small instances (0.05%) Similarly, other approaches like Att-GCN (0.05% on Small) and DIFUSCO (0.35% on Medium) also exhibit their most competitive results when tuned directly on TSPLIB. This underscores that substantial performance gains are unlocked when hyperparameters align with the problem's characteristics. While more granular instance- (detailed Table (T), can yield further benefits, its current computational demands are considerable. Consequently, the efficacy of targeted tuning observed in Table & strongly motivates future research into efficient hyperparameter optimization, including the development of recommendation systems that could predict near-optimal settings from instance features, thereby achieving robust performance without exhaustive search.
hyperparameter optimization, such as the aforementioned grid search
Several key insights emerge from detailed experimental results. First, we observe strong interaction between instance distribution and parameter tuning effectiveness. While methods like UTSP and DIMES excel small uniform instances, their performance exhibits high sensitivity parameter settings when faced with real-world TSPLIB instances, particularly at larger scales (e.g., UTSP degrading from 26.51% % to 1481.66% on large instances). This finding reveals a fundamental generalization challenge shared by most learning- based methods the optimal parameters learned from one distribution may not transfer effectively to another, highlighting the critical importance of robust parameter tuning strategies. To illustrate this distribution sensitivity, we visualize representative hard and easy instances from each group in Figure 6 demonstrating that hard instances deviate significantly from uniform distribution while easy instances closely resemble it.
This generalization issue is particularly noteworthy as affects all methods except the Zero heatmap. which maintains relatively stable performance across different instance sizes and parameter settings. The Zero heatmap's s consistency (varying only from 5.54% to 6.51% % on large instances) provides compelling evidence for our thesis that the MCTS component's 's contribution to solution quality has been historically undervalued in the framework. Furthermore, this stability suggests that proper MCTS parameter tuning might be more crucial for achieving robust performance than developing increasingly sophisticated heatmap generation methods.
From a practical perspective, our analysis also reveals important computational consideration. The learning-buc based baselines necessitate GPU resources for both training and inference stages, potentially creating bottleneck when dealing with real-world data. In contrast, methods that reduce reliance on complex learned components might offer more practical utility in resource-constrainet settings while maintaining competitive performance through careful parameter optimization.
These findings collectively suggest that future research in this domain might benefit from a more bal- anced focus between heatmap sophistication and MCTS optimization, particularly when considering real-world applications where robustness and computational efficiency are paramount.
H TUNED HYPERPARAMETER SETTINGS
In this section, we present the search space in Table 12 and results of hyperparameter tuning, summarized in the following Table The table includes the various hyperparameter combinations explored during the tuning process and their corresponding heatmap generation methods.
21

---

Published as a conference paper at ICLR 2026
Table 9: Performance of different methods on TSPLIB instances of varying sizes. All hyperparameter settings are tuned on uniform TSP instances as listed in Table [4
(a) Small instances (0-500 nodes)
Optinsl
Length
Zoo
Gip.1
Lenph..
AU-OCK
Gay.
Leoph:
DIMES
Gap.1
Leoghh
UTSP
Gay
|eopph
S.nDKa
Gay
LLayfi
DEFUSCO
Gap.1
[Leygh
Fai-T2T
Gap
[Layph
CTE
Gep
675
676
8.38%
676
0.15%
676
11.5%%
676
0.15%
734
1.30%
676
0.15%
676
0.15%
676
0.15%
538
5:8
0.88%
538
0,88%
538
0.88%
538
0.00%
538
0,00%
538
0.00%
335
0.015
335
6JMG
0.889
20083
30303
0
20082
20083
s151
427
0.33%
0,338
427
427
427
0.236
2323
2328
2325
0.228
2333
0.86%
2325
0.22%
2326
0.2%%
2336
0.22%
1325
0.5%
2535
0.22%
14144
58537
50982
2,58%
65756
50533
59211
11158
(003)
14.7%
63385
5.350
54537
0.00
65485
11.7%
1657V
16579
16779
1677
0.80%
19151
1.5%%
14379
010%
14379
030%
14379
21234
11284
1134
1.88%
11244
1.80%
21284
1.80%
21214
21344
010%
21344
0101%
21394
21221
3128
0.88%
21382
0.88%
21282
11.87%
21382
0,.0%
21282
21381
610%
21283
0301%
21283
0101%
0055
136645
15291
136643
1551
0.88%
02200
136643
15539
0.88%
126643
15325
0.66%
0.55%
126643
15405
0.06%
0.33%
136643
1535)
0.0%%
0458
176643
15339
0356
0.0%
136643
1875
0.00
0/05
136643
15303
8.00
0.16G
15745
12617
0.50
23141
0.80%
15641
0.66%
23141
0.00%
23141
0000
22111
18763
15811
0,23G
420
620
622
622
621
427
010%
427
0241%
629
BJ0NS
41200
2230
42263
2200
72
2.12%
42883
1220
4213)
1111
7581
1/880
1351
0.965
7541
6351
6311
1966
754
6311
3003
1111
110%
7083
1211
0/45
030%
1211
8/0G
50000
2010
53055
2008
0.633
0113
0/05
15551
6.75%
BILT
11561
1355
1.55
11605
677
1716
3755
1380)
[106
11:00%
12551
3350
11833
0/05
12111
2200
22004
0.98
2200
11881
2200
2304
32063
8105
12361
0/05
22866
ch150
4155
6311
0.85%
6111
6111
0.55
3154
E111
6111
3216
2721
2546
25.5
0355
2596
2016
3525
2210
2288
7260
0.523
7320
0.563
0.803
2000
610%
221
0140
31500
510%
10100
6334
49451
0115
1:13
0040
201
26525
36925
0.96
26525
26125
20123
6105
2012
5105
561
08303
1154
1200
1200
2615
6000
0
0630
41313
4024
0105
0:46
42187
41353
56.3
42301
44383
5J05
0.0%
0.55%
(229)
40001
4655
0160
852
007%
46230
0968
4151
0.86%
50L
4035
0.16%
40113
605%
45:55
0.1%
u159
4200)
4080
0,65
(9R)
0.8%
4380
0.6%%
(39)
0.60
075%
4338
0105
42366
0J05
42866
105311
1995
109441
105191
1.25%
109176
1.17%
110001
1.59
10600
0.1%
19M54
2.31
(h15)
6578
6538
6528
0.88%
6538
0.85%
6538
8515
6538
010%
6538
0101%
6536
BJ0SS
6M:
365477
1830
0.95%
56118
0.972
20233
047%
3037
034S
0350%
Awrigg
15781
0.79%
1034
0.7%%
14155
0.088
1909
0.15%
35580
1.73%
35165
0.58%
3033
0.105
35331
0.776
(b) Medium instances (500-2000 nodes)
Ieazzo:
Uytinal
Lengh
Zaro
[leegh]
AB-OCN
Gpp.
Lirghh.
DIMES
1ap
|eeggh
Gap
[Zeggh)
SciDs
Gop.)
[.ngh
DIFUSCO
Cop-1
Linghh 1
Fai-T21
Gap
Laagh
Cop_1
51715
57618
1.560
1.5%%
51631
0.75
5T666
0.355
51348
0.655
197733
5905
8903
1.00%
1987
0925
1952
0.58%
9229
1.25%
1954
02075
1943
641%
5575
0.70%
1831
03105
27606
15 35.655
26380
73955
35467
4.50
35343
45.00
21509
6925
29567
15915
31534
15.9%
232233
235000
0.5%
257.99
1.75
254312
0.10%
245331
3025
20H066
1
240035
140%
243057
0.3%%
26/06
15795
13575
6523
0.33%
6014
2.1%
5.0%
6977
13.305
12.35%
111EE1
116879
1166
d1399
313330
479282
$1.41%
464154
0011%
357840
25
44134)
327774
155%
334242
540%
133535
4.0%
431655
42.14%
6724
10925
41105
0479
1.00%
42317
107%
42181
0
6.22%
41285
0426
71473
813
1.06
159045
365781
2.7%
N5538
7.4%%
763164
1.50
1415
307901
1.57
263173
1176
M.5%
7009
1995
B1577
31.595
21805
24.0%%
33330
35,005
2081
32.0%
25302
16,85
12.1%
25111
31.4%
167641
13309
31 11.00
3660
25336
11600
15.9%
164781
35005
1855
1515
15385)
1,75
2066
17:85
D400
4033
0.30%
40230
002%
49894
0.25
20075
6.2%%
41111
0-25
60175
66005
6.16
6551T
5.0%
6131
4316
65977
6.05
63466
1.95
61351
1190
3716
6361
1416
11817
S731
51
116
717%
31.0%%
1009
56878
88507
1.45%
75111
41333
130090
356 64
133355
50145
0
105970
13.00 1.34%
13 100
776.00
575
314104
1.4%
373507
1,35%
20006
8.5%%
Aecuge
443445
15.2%
1303
11.4%
13666
10649
135544
12.00%
125305
6.0%%
123631
(2414)
4.18%
135000
10000
(c) Large instances (2000+ nodes)
Iastax
Opizal
Zon
AI-GCN
HIMBS
U17P
Seflke
Largt:
DIFU000
Fat/12
Cip.1
GT.Pher
Cup.1
42152
64335
56710
3,505
5630]
3.35%
07244
4.07%
72225
23,22%
66334
3.21%
66311
1,5%%
6033)
3.11%
65487
1,0%
10794
10TM)
1.90
141118
330%
1477
193341
1.91%
13451
1150
141446
1136
14778
116%
19105
11NG
384127
1.75
388315
1375
137%
385057
1.55
35372
126%
35321
1545
390244
2177
397722
0.1%
16118)
186885
183155
15589
183677
0325
18971
1116
1160
187766
1316
K1.07
19004
556045
503550
5.5%
S11330
417%
19396
141155
$1.00%
57885
286%
34607
1350
038C3
215%
57006
133%
19901999
4.5%
38/999
355%
31073016
3.390
41/8
6.6%
1672480
1716
5475
347%
402090
455012
3.5%
45776
1866
45300
110%
47/13
247%
H1 1843
925088
164054
1.56
903581
3.4%
013542
3,206
198653
(12
$68548
2.4%%
Sx7744
1.50
1902/9
5.11
30200
4.44%
Arctgg
005663
3595
355%
133644
258033
26.51%
194174)
4.5%%
1011534
3.88%
194394
531%
1883550
3.5%
22

---

Published as a conference paper at ICLR 2026
Table 10: Performance of different methods on TSPLIB instances of varying sizes. The hyperparame- ter settings are the default settings as used by Fu et al. (021).
(a) Small TSPLIB instances (0-500 nodes)
Optinal
Zaro
Cep
AR-GEN
Cay
1eeggh
LTTSP
Gip
Leegh
Eap-1
|Lengh..
Bac-TST
Cap
Cip
675
67%
0.15%
676
0.15%
1055
$5.4455
676
6.15%
694
2,516
676
0.15%
679
0.596
676
6.15%
kmv3300
2230
20835
0011
20368
0.10%
20464
16.15
21539
25085
11.0%%
20611
1.3%
24621
23377
58537
58554
0/36
67633
15:305
73455
23 23.505
68537
0,88%
06101
13.00%
1000
0.536
59630
0.186
88537
6,96%
mits5
1333
2565
1816
2323
0.00%
2331
0.330
2153
2133
070%
2337
0.005
0.76
2316
0.56
118891
118713
188282
14370
14379
0.00%
14399
0.0%%
1647
14316
16379
1907
16991
1621
0.56
1479
BAYS
pr152
72580
33682
0.6%
12462
73662
0.0%%
14053
0.47%
74121
0.505
TAME
0.00%
AnvA000
21282
21383
1.00%
21383
016%
15166
14.28%
21332
0.8%%
2120
510%
21366
0358
21704
2235
21262
11111
60000
15810
1.5%%
15413
0355
19820
3.585
15500
15418
0.50%
15200
0.45%
6.16
15251
22141
22103
02355
22341
0105
25014
17.405
23141
0.80%
2114
530%
22011
258%
22554
3245
21141
15284
15010
1-22%
15804
1300
1209
0277
1923
1578)
630
0.100
41345
41350
151%
$1350
2/45%
43503
13055
<53
03359
1:00
42312
1
2218
2011
2251
0:15
2012
1-226
2214
2121
2298
2180
2209
berlaS2
20744
1542
20140
7242
020%
030%
20719
010%
11689
21000
11000
43360
20790
1543
0.8%
2000
4543
20011
4541
(364%
01150
21177
7545
080%
24
2100
2774
1543
0.00%
2417
23365
11961
19110
15551
22068
010%
15615
21268
12504
0255
0100
1242
14096
2600
13305
5 131552
151199
1000
61.0
0.5%
365228
2300
1050
15505
-305
13157
22133
19577
13.545
0.50%
3200
1251
22111
0310
0240
2306
R00%
6425
0.35%
1gg22
1510
1016
1254
7016
010%
1972
2411
700
0125
0105
16555
10516
$1502
1.245
2300
2255
0.0%
1
1006
2221
00091
2500
0229
1920
4124
2310
0815
41135
1500
5.0%
(v134
54130
54690
0205
51600
0/0%
16655
3.3000
5000
080%
02075
0555
Bas
25225
5000
29611
0.25
100
0129
2053
11:0
54055
5.0%
M103
15111
0050
Re115
56355
5615
0 0189
36151
50/9
0005
5639
6335
5113
pelin
41311
41116
1173
11311
8123
1861
0.55
6663
0196
4010
010
4191
p9156
95771
51555
66512
016%
10014
23.09
16765
5.0%
9651
0.1%
06744
0.39
1072
6.0%
(679
49141
18539
194%
1875
6305
K105
(396
0315
0011
1246
0256
a280
1579
100%
159
016%
258
005%
2395
0.5%%
2551
0.56%
3559
5.0%
2559
2555
0.5%
(4530
107217
109072
148%
19901
1353
109902
1.2%%
105434
1.15%
155530
7.5%%
108855
1.5%
181425
6225
101856
0418
6195
1658
55:30
177
141%
189%
pc3442
30775
52392
1.99
51086
0.3
51147
0.73%
51775
1.595
51177
0.79%
50076
0.3%%
51297
110%
51955
0.62%
Aserag
35306
16,010
35570
0.365
(b) Mcdium TSPLIB instances (500-2000 nodes)
Inwonee
Optiral
Ixegt
Zero
Capp
1mggh
DIMES
1eegth
UTSP
Cap
11agg::
ScfiDii
Cup1
[Eapph]
DIFUSCO
Gpp
1regth
Faa-121
Gay
|Teggh:
Cap_
657c
36905
36171
3.45%
57545
1.356
33833
2,455
35015
3.63%
57545
1.75%
37836
0.33%
37633
1.5%
37641
1.45%
175
56853
00031
5.87%
36453
37655
59654
3.16
59761
5.44
5009
2316
57317
1,4%
57166
0
58251
92300
4.87%
8590
1486
3.30%
9134
3.5%%
$525
1.48%
1863
0685%
1864
1031%
5580
2.045
B1.000
33337
2191
3.0%%
20587
15.0%%
23832
4.005
17910
$5.075
3011
22008
12.3%
20915
45.025
21272
7053
413%
6801
1330
6843
336050
332355
4.3%
144077
347000
3331
372187
10.755
344103
2275
540000
1.5%%
524007
572%
343913
22095
41380
336530
S13841
8.44%
123210
338164
335530
13.205
130879
2875
120359
43351
45400
1.500
01291
53851
<3257
3.5%
5306
1406
53833
5870
54531
6.55%
53550
2816
51937
234%
53543
5856
52553
3456
ge000
20005
273143
5.15
366647
166
367609
1445
200531
3.35
365458
3.770
263242
1.43%
23153
4.55
364704
57681
1305
57737
194%
55399
15,775
5921
2.445
57297
1335
51800
1.4%
59654
1.99
41304
25175
6115
155661
106
270077
6116
205135
6:25
264664
4725
15297)
119%
30163
104%
263145
4376
15366
191%
1400
31811
1556
16611
11105
E306
35.955
17456
1.514
0.66
1907
c1685
02113
16610
7.5%%
6070
2186
64558
4.0%%
75575
22115
43575
2.1%
05316
5.2%%
63600
2399
+1817
60671
602:9
10:45%
1.7%
58798
23655
30015
3.80
137340
1.45%
1.80
190167
215866
577580
1.56
41333
270199
343707
5.000
176363
1355
762400
4.5%%
343076
1.67
236379
1.00%
17
1.13%
777387
2.66%
238383
1.995
Avtrage
136143
4.9%%
12479
3.35%
13990
4.00%
|
132922
13.50%
125010
7.29
123073
2.7%
12025
5.33%
12536)
3,666
(c) Large TSPLIB instances (>2000 nodes)
Optia
Zeno
A3-0UN
DIMLS
U1S
1/E-Prir
7,575
20:25%
72822
13.15
42513
14980
227114
1.22
231123
280143
225844
1.155
231150
0,515
143312
1145
153000
1854%
341143
143977
14.7%
15610
13.90
143372
1.0%
318222
3.87
360 301
1399
435154
12:89
411135
4136
13485
49014
15.0%
4316
38500
1.5%%
4210
9827
10600
01.39
120
4.30
1896
1139h
18822
15400
$9662
5070
12.0%
5008
1349
K711
185%
505500
6766
30511
1815
13
$3001
43.00%
1106
16155
11766
31955
5U511
4.25
18635
4.7%
11%
121115
366-1%
1190651
0757 13
9056
11366
19011
135%
12.005
1415
C1150
1014115
411%
099.44
40991557
4338.555
155366
1,295
775555
5865
1421977
55.75
507%
415112
1970044
6005
1330025
340%
1997717
1141109
T1N0391
4453 18/
H65441
240%
163223
359%
244040
$5.199
2309
Nowage
1953.6
6516
1413533
1515
3435711
55%
9441669
1481 56%
1955775
1136%
303643
15,00
3500150
35.7%%
1913477
551G
23

---

Published as a conference paper at ICLR 2026
Table 11: Performance of different methods on TSPLIB instances of varying sizes. The hyperparame- ter settings are obtained by grid search.
(a) Small instances (0-500 nodes)
Instanos
Optirna
Zee
AB-OCN
DIMES
LTTSP
SofDii
DIFUSCO
FIu-TIT
GTiPNkr
Cop-2
Langhh..
Lzagth
Cop
LLnnph...
Cap
Cap.1
|Zeegh:
670
.75
675
8.08%
6776
0.115
675
0.00%
676
0.15%
67%
0.15%
676
0.11%
676
0.15%
676
0.15%
20168
0.08%
39965
1..0%
20368
0.03%
29/05
0.80%
20168
2006
0.815
2016
0
20364
0.015
pe141
59537
58537
0.30%
F8517
1
56537
0.89%
59837
0.00%
55537
58517
58537
0.88%
58537
0.01%
3325
2523
0.00%
2133
1
2523
5.0%%
2335
0.05%
2323
100%
2333
0.05
2323
0.0%
2113
0.0%
405)
476
437
0.31%
0..5%
6.31%
437
0.31%
427
0.25%
437
0.33%
427
14370
14179
1857
14379
14379
14379
1417
koaD100
21204
21334
0.00%
1124
0.00%
21284
5.0%%
21234
010%
21354
600
11234
0.86
21384
0.88%
21244
0.0%
73682
0.00%
0.00%
21383
0.000
0000
3130
3.00
21180
0.9%%
21291
0.00
1225
136943
13644
6.06%
136445
0.00%
13644
684%
136645
0000
010%
13664
6685
139445
0.00c
13643
6.0%%
136643
15251
15250
0.03%
15255
1
11500
01.
15027
15:1
0.00
15234
15281
0/884
1220
0.0%%
0193
15150
625
1214
639
15500
69645
124
100
22444
63V
22511
629
0000
0000
000
2218
021
0.10
21161
420
15500
624
1578
0.00
41345
42280
1358
40024
1863
42113
2016
2050
42080
1656
4000
41829
1455
4302
1241
1231
030/
1511
1361
1311
1111
6151
beriia22
22:48
1302
2226
1523
2545
200
2008
20:00
7562 1542
0200
2000
3541
2006
1541
0.0%
11551
1141)
110655
19962
1196
100%
1559
01000
11000
1992
11966
11563
19977
23048
189799
:3005
10913
23368
010%
191177
2206
19817
2265
0705
108179
22008
188270
2305
0.0%
0.0%
E304
1511
020%
5000
1850
02060
5950
0.0%
2010
2501
250
010%
2016
1550
0105
206
1580
0.0%
40556
18425
68850
E30/
4922
0105
24000
6030
0.0%
2553
2552
76554
0/00
1658
1985
2011
23417
180/
21113
2010
010
44331
200
46961
6201
22511
6631
0.85
13230
-1280
1302
4111
12041
0.35
1310
0355
43829
0.0%
W022
96772
19777
1672
9672
6154
13560
11660
42960
100
1316
42860
0.0%%
(36
0.8%
X3M1
(4439
107217
2579
2579
0.08%
197319
257
0.00%
10740)
2579
107910
3579
0.55
010%
557
0.0%
101346
1579
0.05
0.26
2579
2570
0.56
010%
6634
6628
6/8%%
6538
0913
38002
35367
1.9
35017
0.04%
35100
0.20%
35151
0,11%
55066
0.27%
35142
0.4%%
35030
0.11%
59545
0.12%
1d1442
90776
90918
0.06%
50615
0.7%
50510
0 0.009
50609
0066
54778
0/00%
30003
0
50607
0.009
50785
0.266
Awraae
(b) Medium instances (500-2000 nodes)
Oytirol
Zao
AB-OCK
DOMES
UTSP
ScRIKM
DIRUSCO
Rai-727
GT.Pike
Tengh.
Tengh.
tengh.1
Fop
Tergh.
Cop
Tzegh..
Gap
Exrgh
Gap.
Ezegh.
Gxp
Eargh.
Gop.
4554
J8M15
37130
0.66%
3W575
0.31%
5/064
03485
311855
03305
3/1812
0125%
36535
0.16%
1500
0.57%
31001
0.20%
33892
S988:
1.58%
51281
0.89%
5/263
0.89%
51487
1.5%
56006
0.13%
5/084
0.34%
35/82
0.15%
513M
0.33%
01412
1829/0
133811
1.00%
131977
0.99%
183925
0.56%
134276
0.30%
183651
0/43%
153316
0.54%
183999
041%
185542
0.57%
B1400
20127
0.34%
31015
0.99%
0.554
0205
20051
1..1
20233
20071
672%
20191
0.32%
va1054
239295
24.
105%
231533
0.24%
242120
1188
24155
181%
240675
0.35%
239492
018%
29144]
0226
201242
0.39%
55575
0.4%%
6307
0.50%
0.50%
0364
6788
0.00%
0.2%%
6767
0.11%
508155
61889
316536
32.620
141%
321775
186%
323176
2.00
325917
2564
521654
1,2%
318314
0.5%%
319161
1826
521451
1.55%
M724
41910
62134
0.1%%
42111
0.48%
43125
0.2%%
42215
0.00%
42001
0.21%
41982
811%
43004
0.25%
4204]
0.1%
01291
0.30%
0.1%%
0416
0.54%
299045
25.595
1024
500363
2W1556
B1577
212.9
2309
2
12531
1.2%
12451
0.91%
12022
3.02%
12686
1,55
12422
0.11%
1344
537%
13580
0.5%
35638
50PL
0.22
5093
0.5%%
57013
0562
5T112
024%
5T010
0.56
56797
0.66
0:58
56881
040%
8557
45912
255681
0,0%
254405
0.1%%
255372
0.59
4015L
0.7%
4M61
0.46
-30
4993
0.66
4904
0.15
p554
34643
3467
0.8%
1460
0.6%%
34674
0.0%
14714
020
14557
0336
34645
6015
34655
0036
3464
0.06
disss
63125
64245
3.1%
62855
1.0%
1,7%
6412)
330%
63658
1.55
62530
0.25
6556
0746
53758
1006
u1817
1.516
254054
53435
224534
55884
0.32
41333
270199
272320
0.75%
273431
0.33%
273488
0.59
275511
1.97%
271577
0.11
371
0.34%
0.26
271751
0.57
Awaag
133335
1.8%
133359
0
17318
0.7%
173801
1.50%
1736
0715
12244
0.35%
13333
0.45
125:4
0.11%
(c) Large instances (2000+ nodes)
Optizal
Zon
AHGGCN
DINES
UTS2
Solibal
DIFUSCO
Ral-127
GT-Pria
Teegts
1eegh:
Gg.
Teephy
Gpp
Ireph.
Day:
Tesph:1
Gep 1
Teagh.
Gay
|Eaghh
Gg
Tangh:
Gip
43152
64553
67471
3.01%
66363
1.225
65342
4.0%%
53491
6655%
65330
2.47
45516
1.51%
65106
2.55%
65551
30026
83319
3.50%
255175
0.395
25863
24000
1179%
23660
0.15%
236121
1491%
238115
0.285
231029
0.295
133952
143834
1,2%%
28772
13786
12.315
30941
1562
11561
1962
11347
M13%%
30140
4.75%
22891
131%
2000
1965
315/6
617%
1919901
193566
155775
1384
18800
1355
1967/4
1.3%
18861
363%
18636
6585
18601
2335
187610
2.05
181111
43153
30550
33671
4100
13114
2/05
1380
4.85
$1507
413%
13323
1.5%
133
175%
C35
2/02
81010
4.0%
45915
5189
963M
17%
(WAAT
6.35%
1585
561122
53385
581110
1.3%
EML 1500
(9382530
21133600
0.80%
2077246
4.0%
2134766
6300
21-2330
2.26
21520025
6.44
2116111
592%
200144
4.7%
31443533
1.4%
418512
672200
3.25%
67280)
4.2%
015778
4.5%
663915
393%
671251
4.3%
16618]
5.3%
616615
107
663199
2.4%
90:001
WONEE
6995
1035491
86.%%
V18110
96719
0718K1
018155
19.5
3558.37
1953455
5.39%
1933641
3.505
1854340
4.5%%
2933796
5.1%
3254557
5.33%
194903
3.0%
102012
5.27%
[NOUS
145
24

---

Published as a conference paper at ICLR 2026
(a) Hard instances at small, medium, and large scales.
12319
(b) Easy instances at small, medium, and large scales.
Figure 6: Representative TSPLIB instances visualization.
Table 12: The MCTS hyperparameter search space. Bolded configurations indicate default settings from prior works.
Hyperparameter
Range
Alpha
[0, 1,
Beta
110, 100, 150]
Max_Depth
10. 50, 100, 200
Vax_Candidate__Ne
5, 20,50, 1000]
Param_H
2,5, 5, 10
_ee_He
True, False]
I HYPERPARAMETED TUNING WITH SMAC3
In addition to the grid search method employed in the main content of this paper, we also conducted hyperparameter tuning using the Sequential Model-based Algorithm Configuration (SMAC3) frame- work (Lindauer et al. 2022). SMAC3 is designed for optimizing algorithm configurations through an efficient and adaptive search process that balances exploration and exploitation of the hyperparameter space.
The SMAC3 framework utilizes a surrogate model to guide sequential model-based (Bayesian) hyperparameter optimization. This model is iteratively refined as configurations evaluated, allowing SMAC3 to identify promising areas of the search space more effectively than traditional methods. This provides principled and reproducible way select MCTS settings under fixed evaluation budget.
Table 13: The Comparison of Tuning Time Between Grid Search and SMAC3. "h" indicates hours.
Grid Search
SMAC3
TSP-500
24h
1.39h
TSP-1000
48h
2.78h
TSP-10000
6h
3.47h
25

---

Published as a conference paper at ICLR 2026
Prior for Uniform Distribation
GT Prior for Cluskered Distribttion
ESP
75P 1000
1000
TSP
TSP 1900
1.0
Comislation Distrhhitted Function
-10
Probabslity Mass Function
10.5
Probobality Mass Funzilon
0.
-0.
.0/000
3350
0.3
01911
-00044
0.2
10.4
0.2
00/00
0.1
0.1
0.0
0.0
0.0
0.
15
the mearett boighbor
neighbor
(a) Uniform
(b) Clustered
GT-Prrice for Explosion Distribution
GT Prior for Impplosion Distribation
0.5
0.5
Canmiativv Distabation Punction
Prdability Mass Functin
0.4-
0.8
Probbiiiky Mas Fundion
0.4
0.8
8665
0.3-
0.6
0.3
-06
83353
0,2
0:2
0.4
0
6
10 11
12
13
14
15
9 10
12
14
15
Rank of the k-ncarest neightbor
Rank of the k-nearest neighhor
(c) Explosion
(d) Implosion
Figure 7: Empirical distribution of k-nearest neighbor in optimal TSP tours of different distributions.
For our experiments, we configured SMAC3 to optimize the same hyperparameters as those previously tuned via grid scarch. The search space remains identical to that demonstrated in Table [2] However, we set SMAC3 to search for 50 epochs (50 different hyperparameter combinations) instead of exploring the entire search space (864 different combinations) and the time limit for MCTS set to 50 seconds for TSP-500, 100 seconds for TSP-1000, and 1000 seconds for TSP-10000. We show the time cost of each tuning method in Table 13
The results of these experiments, including the hyperparameter settings identified by SMAC3 and their corresponding performance metrics, are presented in Tables 14 and 15] As shown, the performance achieved by SMAC3 is comparable to that of grid search. Specifically, for TSP-500 and TSP-1000, SMAC3 produces results similar to those of Att-GCN DIFUSCO and GT-Prior, with even better outcomes observed on 10000 This improvement can be attributed to the extended tuning time allowed by SMAC3 compared to grid search. Given the significant difference in time costs, SMAC3 proves to be efficient and economical option for tuning MCTS hyperparameters.
J N--EEREST NEIGHBOR PRIOR IN TSP INSTANCES WITH DIFFERENT DISTRIBUTIONS
We solved and analyzed TSP problem instances across several different distributions and found that their k-Nearest Neighbor Prior distribution similarities were quite high, as shown in the Figure 7
K ABLATION STUDY ON THE EFFICACY OF HYPERPARAMETER TUNING
To better understand the efficacy of hyperparameter tuning in MCTS for solving TSP, we conducted an ablation study focusing two critical aspects: the relationship between search time and solution quality, and the sample efficiency of our tuning process. These experiments provide valuable insights into algorithm's 's performance characteristics and highlight areas for potential optimization.
26

---

Published as a conference paper at ICLR 2026
Method
Training
Mathod
Training
ZERO
5s
ZERO
105
DIFUSCO
DIFUSCO
Optimality Cap (80 log Scale
SoftDist
50s
Optimality Scale
SoftDist
100s
GT-Prior
18-1
380 Inference (5)
(a) TSP-500
(h) TSP-1000
Figure 8: Impact of search time solver performance across different hyperparameter confguguttonnoooooooo
K.1 IMPACT OF TUNING STAGE TIME LIMIT
LIMIL ON SOLVER PERFORMANCE
The relationship between Time Limit and hyperparameter quality is crucial in MCTS hyperpa- rameter tuning. While longer search times might intuitively yield better results, they also lead to significantly increased tuning time. We conducted an ablation study to investigate this trade-off and seek balance between performance and efficiency.
Experimental Setup We examined the impact of search time solver performance for TSP-500 and ISP-1000 instances, varying the tuning stage Time _imetttimtttttt from 0.1 to 0.05 and 0.01.
Figure g shows the performance of different methods with varying inference times, each with three hyperparameter sets tuned using different Time_Iimi values. Surprisingly, the relative performance remains largely consistent across search durations, suggesting that hyperparameter effectiveness can be accurately assessed within limited time frame.
all tuning stage Ti Time_ fiimit values, with Zero and GT-Prior methods showing nearly identical performance curves. The best learning-based method, DIFUSCO. displays small performance gap at the default 50-second inference time limit. However, this gap widens with longer inference times, suggesting that optimal MCTS settings for high-quality heatmaps may vary with different Time Limit values during tuning phase. Efficiently tuning hyperparameters for such high-qualij heatmaps remains future research direction. Notably, TSP- results show even smaller performance gaps between different tuning stage Time__iii _imm values, indicating that shorter tuning times can yield satisfactory hyperparameter settings for larger problem instances.
For TSP-500, most heatmaps exhibit similar performance
Time__imii
The consistency of relative performance across search times has significant implications for efficient hyperparameter tuning in large-scale TSP solving. This insight enables the development of accelerated evaluation procedures that can identify promising hyperparameter settings without exhaustive, long- duration searches.
K.2 SAMPLE EFFICIENCY
Experiments were conducted to evaluate the sample efficiency of the hyperparameter tuning procedure for our proposed k-nearest prior heatmap. By varying the number TSP instances in the training set and measuring the resulting solution quality the tuned hyperparameter setting, insights were gained into the computational efficiency of our method. With only 64 samples for hyperparameter tuning, our proposed GT-Prior achieved a gap 0.493% on TSP-500 and 0.866% on TSP- rivaling the performance of hyperparameter tuning with 256 samples, which achieved 0.493% TSP-500 and 0.858% on TSP- 1000. These results demonstrate the high sample efficiency of our approach, enabling effective tuning with minimal computational resources.
27

---

Published as a conference paper at ICLR 2026
L GT-PRIOR INFORMATION
Table 14: Tuned hyperparameters of all the methods for TSP-500, TSP-1000 and TSP-10000 by grid search (the left table) and SMAC3 (right). UH: O=False, I=True.
METION
BETA
H
MCN
METHOD
RETA
MCN
ZERO
2
10
2
100
ZERO
Q
150
2
ATT-GCN
0
150
5
5
0
100
ATT-GCN
2
150
2
5
100
DIMES
0
100
5
5
200
DIMES
0
100
5
200
TSP-500
UTSP
DIFUSCO
150
TSP-500
DIFUSCO
150
5
SOFTDIST
100
20
200
SOFTDIST
100
20
200
FAST-T2T
150
20
200
FAST-T2T
10
20
50
GT-PRIOR
10
200
GT-PRIOR
10
5
200
ATE-CCN
AVL-GCN
150
DIMES
150
200
DIMES
150
100
TSP-1000
DIFUSCO
UTSP
0
150
100
5
5
100
TSP-1000
DIFUSCO
UTSP
0
100
150
5
5
200
50
SOFTDIST
150
SOFTDIST
100
FAST-T2T
150
1000
FART-T2T
10
50
GT-PRIOR
10
5
200
GT-PRIOR
150
200
ZIRO
100
2
20
D
10
ZERD
0
100
2
20
10
ALT-GUN
150
AFL-GCN
150
TSP-10000
DIFUSCO
100
20
TSP-10000
DIFUSCO
100
20
SoFTDisT
100
20
Suriius
100
20
FAST- T2T
2
150
2
20
0
10
PASI-T2T
10
10
50
200
GT CT-PRIOR
100
10
1000
GT-PRIOR
100
10
1000
100
Table 15: Results of Hyperparameter Tuning using SMAC3. The underlined figures in the table indicate results that are equal to better than those of Grid Search, rounded to two decimal places.
TSP-500 GAP
METHOD
TYPE
LENGTH J
TIME
LENOTH 4
GAP 1
TIME J
LENGTH
GAP
TIME
CONCORDE
(R(AXCT
16.55"
17.65s
23.12"
3.12M
N/A
NIA
N/A
N/A
LKHI3 (DEFAULT)
OR(HEURISTIC)
16.55
0.00%
14.84s
23.12
0.00%
1.02st
71.77"
28.73M
ZERO
MCTS
16.67
0.73%
0.00x
50.06s
23.39
1.17%
0.00m
1.67M
24.44
3.71%
0.00M4
16.65M
ATT-GON!
SL+MCTS
0.69%
50.068
23.38
1.15%
1.67M
73.87
2.92%
16.65M
DIMES
RL+MCTS
16.67
0.73%
0. 0.97
50.06s
23.42
1.31%
2.0KM
1.67ML
74.17
3.33%
16.65M
6555+
30.066
1.67M
SOFIDIST!
SOFIDISI-MCTS
16.62
0.46%
0.000
50.066
23.33
0.90%
0.00N
1.67M
75.34
4.97%
0. 0.00M
16.65M
DIFUSCO
SL+MCTS
3.6134+
11.86M+
28.5
0.50M+
1,78M+
7.73
FASI-T2T
SL+MCTS
16.60
0.34%
50.06s
23.29
0.744
1.67M
75.11
4.65%
16.65M
GT-PRIOR
PRIOR+MCTS
0.50%
0.00x4+
23.32
0.85%
0.00M+
2.07%
0.0034+
We provide detailed information about GT-Prior for constructing the heatmap for TSP-500, TSP-1000, and 1SP-10000 follows:
GT-PRIOR raw raobabiiiiii TSP-500:
4. 2220772.ee2222222211222202222222
4. 44570000555500000001111000000410
TSP-1000:
4. 6.2256ae00..11110......113233313
28

---

Published as a conference paper at ICLR 2026
TSP-10000:
4. 44004422000001,,0000440004033333
2. 2.7.000002.41100..00000000006660
2. 0,880008522220003300000000000000
6. |:0.0.00...000222222200622200000
M LIMITATIONS AND FUTURE WORK
Our study, while highlighting the critical role of MCTS configuration and the efficacy of simple priors, has several limitations that suggest avenues for future research:
The current analysis, including the GT-Prior, focuses on Euclidean TSP, and the MCTS framework utilizes TSP-specific k-opt moves. The direct upplicability of our findings and the GT-Prior to non-Euclidean TSPs, other combinatorial optimization problems, or different MCTS action spaces warrants further investigation.
Scope of TSP Variants and MCTS Adaptation:
Empirical Nature of MCTS Tuning: While we demonstrate the profound impact MCTS tuning, approach to finding optimal configurations is empirical. A deeper theoretical understanding of the relationship between TSP instance properties (or heatmap characteristics) and optimal MCTS hyperparameters could lead to more principled, instance-adaptive tuning strategies, reducing the reliance on extensive offline searches.
Hyperparameter Tuning Efficiency: While the proposed GT-Prior heatmap is computationally inexpensive inference, the MCTS hyperparameter tuning process itself (using grid search in our current implementation) can be pesource-intensive especially if the search space is large or if tuning performed on very large-scale instances. Although this is a one-time offline cost, optimizing the tuning process itself (e.g., using more sophisticated Bayesian optimization, evolutionary algorithms,, or meta-learning for hyperparameter optimization as hinted in Appendix would be beneficial for practical adoption and for exploring even larger parameter spaces.
Exploration of Alternative Search Mechanisms: This study operates within the MCTS framework as the search component. While MCTS is powerful, exploring whether the insights on the heatmap vs. search balance extend to other search metaheuristics (e.g., guided local search, iterated local search, or even learned search policies) when paired with various heatmap generation techniques could be valuable research direction.
Addressing these aspects could lead to more versatile, theoretically grounded, and practically efficient learning-based solvers for TSP and other challenging optimization problems.
N LLM USAGE STATEMENT
During the preparation of this manuscript, utilized large language model (LLM) writing assistant. The LLM's role was strictly limited to improving the clarity, grammar, and readability of our text through sentence polishing and paragraph restructuring. The LLM did not contribute to research ideation, experimental design, data analysis, or the formulation of conclusions. All scientific content and claims are the sole responsibility of the human authors.
29


Reviews:
[{"review_id": "VQGtXlghfK", "reviewer": "Reviewer_5EC7", "summary": "The paper presents an investigation of the effect of tuning MCTS hyperparameters\nand \"simple\" heatmaps on the results of TSP solving with heatmaps and MCTS. The\nauthors describe the shortcomings of the current literature, their experimental\nsetup including a new method to develop heatmaps, and the results they obtained.", "questions": "How does the GT-Prior heatmap compare to learned heatmaps?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This is a very nice paper that investigates an angle mostly ignored by the\nliterature. The results nicely support the conclusions the authors come to, and\nsuggest that research efforts should be focused in a different direction for\nmore impact. The paper complements the existing literature very nicely.\n\nThe proposed GT-Prior is, to the best of my knowledge, novel and seems to work\nvery well in practice. It would be interesting to investigate to what extent it\ndiffers from heatmaps learned in other ways; in particular whether learned\nheatmaps \"converge\" towards the GT-Prior heatmap. It would be great if the\nauthors could comment on this.\n\nThe time_limit hyperparameter for MCTS should be explained in the main paper,\nnot just in the appendix. It is mentioned as being set to specific values on\npage 6 without having been introduced before, which is confusing (especially as\nthe values are counter-intuitive).", "weaknesses": "None major.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uebRpdLcgl", "reviewer": "Reviewer_yJZG", "summary": "This paper focuses on the classic \"heatmap + MCTS\" pipeline for solving the Traveling Salesman Problem (TSP). The authors examine the extent to which different MCTS parameter settings affect the solution quality and further perform tuning accordingly. Additionally, they propose an approach named ``GT-PRIOR`` to generate the initial heatmap based on K-nearest neighbors.", "questions": "1. See ``Weakness``\n\n2. As the problem size grows, the time spent on the ``Two-Opt`` step inside ``MCTS`` increases sharply. I would like to know what is the performance difference between running the full MCTS and running plain 2-opt alone on TSP-1000 and TSP-10000. This result might reveal whether MCTS actually makes any meaningful difference at these scales.", "limitations": "", "rating": 2, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "1. This paper is written in an accessible manner, offering a clear explanation of the ``MCTS`` method implemented in ``Att-GCN``, and provides a thorough analysis of how each MCTS parameter influences the solution.\n\n2. This paper conducts sufficient generalization tests across different distributions and scales, including experiments on ``TSPLIB``.", "weaknesses": "1. The authors state that ``The underlying assumption is often that heatmap sophistication directly translates to superior solution quality``, yet they provide no experiments to substantiate this claim. They lack analytical experiments to compare the heatmaps produced by different methods, such using greedy strategy.\n\n2. It can be inferred from ``Table 1`` and the sentence ``The Time_Limit for MCTS was set to 0.1 for TSP-500 and TSP-1000, and 0.01 for TSP-10000`` that the authors run MCTS in parallel. However, they never state this explicitly in the table (64 threads for TSP-500/1000 and 2(maybe?) threads for TSP-10000). Moreover, the baseline solvers ``LKH`` and ``Concorde`` are executed in single-thread mode, so the comparison is unfair and likely to mislead readers about the actual efficiency of MCTS. Additionally, previous study [1] suggests that the ``LKH`` and ``Concorde`` figures reported in the table may be outdated or stem from sub-optimal configurations; it is therefore advisable to adopt the updated baseline results.\n\n3. This paper concentrates **solely on the TSP** with ``heatmap+MCTS`` pipeline tailored to it. This approach is hard to extend to richer problems such as the CVRP.\n\n4. In general, as problem size increases, the quality of heatmaps learned by ML methods deteriorates. Previous studiy [2] has shown that heatmaps achieve strong performance on small-scale TSP instances, while this paper does not include experiments on TSP50 or TSP100. \n\n5. Both ``MCTS`` and ``LKH`` are K-opt algorithms; the former adds a heatmap guidance. In my view, once the instance size exceeds 500, LKH dominates MCTS in both speed and solution quality by a large margin. Hence the authors’ hope that ``heatmap + MCTS`` will ``develop TSP solvers that are not only high-performing but also more robust, efficient, and genuinely impactful`` is questionable.\n\n\n[1] *COExpander: Adaptive Solution Expansion for Combinatorial Optimization, ICML 2025*\n\n[2] *Unify ML4TSP: Drawing Methodological Principles for TSP and Beyond from Streamlined Design Space of Learning and Search, ICLR 2025*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "piBIv0Yzjo", "reviewer": "Reviewer_pNGG", "summary": "This paper revisits the widely adopted \"Heatmap + Monte Carlo Tree Search (MCTS)\" paradigm for large-scale Traveling Salesman Problem (TSP) solvers. It critically analyzes the respective roles of the heatmap and the MCTS search procedure. Contrary to prior trends that emphasize increasingly complex heatmap design, the paper offers a systematic, empirical evaluation. This evaluation demonstrates that the configuration of MCTS—often taken as a fixed backbone—can have as much, if not greater, impact on solution quality as the heatmap itself. The authors propose a parameter-free GT-Prior heatmap based on the empirically observed k-nearest neighbor edge structure of optimal TSP tours. By tuning MCTS hyperparameters via a robust pipeline for each heatmap, they show that this simple baseline matches or outperforms state-of-the-art learning-based and distance-based heatmaps. This holds across scale, distributional shift, and standard benchmarks, challenging current assumptions in the field. The work argues for more balanced and transparent component evaluation in future research. It provides tools and ablation studies to support reproducibility.", "questions": "1. Practicality of GT-Prior: For deployment on genuinely new, real-world TSPs where high-quality solutions are not available, how would one construct GT-Prior (since you need optimal/near-optimal tours to compute the empirical k-nearest distribution)? Did you try synthesizing priors from random/greedy solutions as a further baseline?\n2. Tuning cost: Can you provide the absolute time and computational resources required for your grid/SMAC3 MCTS hyperparameter search (including how many instances, search depth, etc.), especially for the largest TSP-10k and TSPLIB cases?\n3. Have you considered (or could you comment on the prospects for) transfer of either your analysis framework or GT-Prior construction to other vehicle routing or graph-based optimization problems?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper systematically assesses the \"Heatmap + MCTS\" paradigm for large-scale TSP, isolating and quantifying each component's impact.\n- The work challenges a key assumption: that more complex heatmap models always improve TSP solver performance. With a well-tuned baseline, it shows that optimizing MCTS often matters more than increasing heatmap sophistication.\n- A parameter-free k-nearest neighbor heatmap (GT-Prior) matches or outperforms complex learned heatmaps when paired with optimized MCTS. It generalizes well to new distributions and larger instances.", "weaknesses": "- Scope: The analysis, experiments, and proposed GT-Prior heatmap are specialized to the Euclidean TSP. It remains unclear whether the insights transfer to other TSP variants (non-Euclidean, with constraints) or different combinatorial optimization problems (e.g., VRP, graph matching).\n- Dependency on optimal solutions: GT-Prior construction relies on empirical distributions extracted from near-optimal solutions. In scenarios where such solutions are expensive or unavailable—a typical motivation for using learning-based solvers—how practical is GT-Prior?\n- MCTS parameter tuning: While a one-time cost, tuning can be significant for large search spaces or new problem distributions. The paper suggests SMAC3 and other efficient approaches, but more discussion of practical deployment costs would be helpful.\n- Incomplete time metrics: Table 1 includes heatmap and MCTS time but omits training time for learning-based models, data preparation, and other one-off costs. This makes it difficult to fully compare runtime and resource requirements across methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z527VF9dNB", "reviewer": "Reviewer_eu88", "summary": "This paper critically evaluates the \"Heatmap + Monte Carlo Tree Search\" paradigm for solving TSP, challenging the prevailing focus on increasingly complex learned heatmaps. Also, the authors propose a learning-free heatmap baseline (GT-Prior) with shown efficiency and synergy accompanying MCTS.", "questions": "1. How do you define the \"complexity\" or \"sophistication\" of a heatmap? Is it defined by the parameter quantity of neural models that produce the heatmap, or by any mathematical or statistical metrics computed upon individual heatmaps? The authors criticize complex or sophisticated heatmaps but the definition seems obscure. E.g., in Sec 5 the authors say \"the prevailing view that increasingly sophisticated heatmap models are the primary drivers of performance in the \"Heatmap + MCTS\" TSP paradigm.\" Similar statements do not seem grounded enough.\n2. Could you provide comparative results free of intricate search algorithms like MCTS and using a greedy decoder instead, to compare different heatmap baselines including the proposed GT-Prior?\n3. What are the results on smaller-sized instances (e.g., 50/100/200)? Do the main conclusions still hold? What about the MCTS parameters and the GT-Prior's performance?\n4. Could you report comparisons using more recent heatmap methods, like the successors of DIFUSCO, e.g. Fast-t2t?\n5. What is the principle for choosing the specific search space for MCTS configuration instead of a wider or finer-grained range of parameters? The authors stated the settings are \"optimally tuned\", then how is such optimality guaranteed?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "1. The tuning in search of optimal MCTS configurations and impact study on the respective parameters is valuable.\n2. The proposed parameter-free GT-prior is sensible and computationally efficient.\n3. The experiments are relatively well-structured.", "weaknesses": "Please correct me if I made mistakes or ignored important statements already addressed in the initial submission.\n1. Foremost, there might be a fundamental misposition that the authors put forward in this work regarding the research line of developing more complex heatmap models: heatmaps do not merely serve for the specific MCTS serching, instead, most recent heatmap-related methods inherently embody advancements in backbone design, training schemes, or data representation, etc., aligning major focuses in the broader ML community. So the criteria for assessing a heatmap should probably not be whether it helps MCTS perform better. Rather, increasing consensus has been inclined to testing neural TSP solvers in a \"heatmap + greedy\" paradigm to evaluate the raw efficacy of neural parts without the results being disguised by post-inference tricks like MCTS, which I personally also deem more reasonable. \n2. The contribution is a bit limited. Though I appreciate the systematic \"tuning\" of MCTS settings, the grid-search-based evaluations seem more of an engineering practice than some technical innovation. Second, the proposed GT-Prior, though interesting and computationally efficient, is also learning-free and straightforward. So, from a holistic view, the performance reported basically stems from the established MCTS algorithm, leaving the incremental efforts by the authors (conducting parameter search) somewhat simple and limited under the threshold of a top-tier conference.\n3. The performance is not sufficiently impressive. The proposed method fails to outperform DIFUSCO on 2 out of 3 benchmarks, while recent literature has proposed much stronger heatmap models than DIFUSCO.\n4. Minor issues. The language needs further consideration. \"Figure 2 compellingly illustrates...\", \"directly answering Q1 by unequivocally demonstrating...\", and many similar expressions, seem to indicate a slight abuse of adverbs throughout the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)