{"id":"7c1578ed-eec5-4980-a034-ab22ee3940b8","arxiv_id":"2411.09238","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"After per-heatmap tuning of MCTS hyperparameters, a simple k-nearest-neighbor heatmap (GT-Prior) matches or beats learned heatmaps on uniform, shifted-distribution, and TSPLIB benchmarks, while search settings alone swing gaps from under 1% to over 90%.","lead":"Recent neural TSP solvers pair a learned heatmap with a Monte Carlo tree search; this paper tests which of the two actually drives solution quality. It finds that search configuration matters as much as heatmap design, and a simple nearest-neighbor heatmap with a well-tuned search matches or beats sophisticated learned heatmaps on TSPs up to 10,000 cities.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Tuning-selection noise and absent variance estimates leave the 0.23pp TSP-10000 GT-Prior edge over DIFUSCO unestablished; a nested-resampling check is needed before the headline 'match or surpass' is accepted.","rationale":"The paper's first claim, that MCTS configuration strongly affects solution quality, is convincingly supported by Figure 2 and the tuned Zero control; I have no serious objection there. The second claim, that a simple k-NN heatmap with tuned MCTS matches or surpasses learned heatmaps, rests on two evidence pillars: same-distribution Table 1 and cross-distribution Table 3. The cross-distribution margins are large and unlikely to be pure noise. However, the same-distribution 'surpass' at TSP-10000 is a 0.23pp difference produced by selecting best-of-864 configurations on only 16 tuning instances, with no error bars or validation split. This is exactly the regime where selection noise and winner's-curse could flip the ordering. The nested-resampling test I propose would settle whether the head-to-head survives. I keep the reader's CONDITIONAL verdict rather than strengthening to reject, because the paper's broad direction is credible and the missing statistics are amendable. I also note that the 'parameter-free' label for GT-Prior is overstated since its PMF is fitted to optimal tours (Appendix K), but this is secondary: the prior is still far simpler than learned heatmaps and the cross-scale/distribution transfer tests mitigate the concern.","tokens_in":38470,"tokens_out":10235,"duration_ms":113239,"concrete_test":"Run a nested tuning validation for TSP-10000: bootstrap-resample the 16 tuning instances (e.g., 100 resamples), re-select the best MCTS configuration for GT-Prior and DIFUSCO from the Table 11 grid on each resample, and evaluate the selected configurations on a fixed hold-out test set. Report the distribution of (GT-Prior gap - DIFUSCO gap); if the 95% interval includes zero or the sign flips, downgrade 'surpass' to 'competitive' and add variance estimates. Apply the same nested check to TSP-500 and TSP-1000 before treating the head-to-head ordering as definitive.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.3 selects one MCTS configuration per method as the best average gap over 864 grid combinations (Table 11) on 128 tuning instances (TSP-500/1000) or only 16 instances (TSP-10000). Table 1 then reports these selected-best gaps, and the same-distribution 'surpass' rests on 2.13% vs 2.36% at TSP-10000. With 16 tuning instances and stochastic MCTS, the best-of-864 average is subject to winner's-curse and selection noise: the chosen configuration may be lucky on the tuning set and transfer poorly to the test set. No standard error, confidence interval, paired test, or tuning-to-test validation is reported anywhere. Consequently the observed 0.23pp ordering could flip under re-sampling, so the headline quantitative claim is not statistically established. The large cross-distribution margins in Table 3 (e.g., 0.35% vs 1.96% on clustered TSP-10000) are less exposed to this objection, but the same-distribution claim in Table 1 and the abstract is not yet secure.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper evaluates the \"Heatmap + MCTS\" paradigm for Euclidean TSP. It argues that MCTS hyperparameter configuration is a dominant, under-appreciated performance factor, and that a simple k-nearest-neighbor-based heatmap, called GT-Prior, combined with tuned MCTS can match or outperform sophisticated learned heatmaps such as DIFUSCO. The evaluation covers TSP-500, TSP-1000, and TSP-10000, multiple synthetic distributions, and TSPLIB instances. The proposed evaluation pipeline tunes MCTS hyperparameters separately for each heatmap via grid search over 864 configurations and reports performance as optimality gap against Concorde or LKH-3 references. The main quantitative support is Table 1, where GT-Prior achieves 0.50%, 0.85%, and 2.13% gaps versus DIFUSCO's 0.33%, 0.53%, and 2.36%, and Section 4.2, where tuning improves the Zero heatmap from 5.49% to 1.06% on TSP-1000.","tokens_in":38483,"tokens_out":3437,"duration_ms":40759,"significance":"If the claims are statistically supported, the paper would make a useful field-level contribution: it would show that default MCTS configurations are often far from optimal and that fair heatmap comparison requires per-heatmap search tuning. The concrete deliverables are valuable: code, exact per-instance TSPLIB results, full hyperparameter tables, and separate tuning/test splits. The paper also makes a falsifiable prediction that a simple distance-derived prior is competitive with learned heatmaps under tuned search. However, the central same-distribution claims rest on point estimates without variance or significance information, and the GT-Prior is not parameter-free in the sense claimed because its probability mass function is fitted to Concorde/LKH optimal tours. The cross-distribution numbers in Table 3 are surprising and unexplained. The potential contribution is substantial, but the current evidence is not yet rigorous enough for the headline conclusions.","major_comments":[{"comment":"No variance estimates, confidence intervals, or significance tests are reported anywhere. The TSP-10000 tuning set contains only 16 instances, and the selected configuration is the best average gap over 864 grid combinations. This selection process is vulnerable to winner's-curse: the best-of-864 average on 16 instances can be a lucky configuration that does not transfer to the test set. The same-distribution claim that GT-Prior 'surpasses' DIFUSCO rests on 2.13% versus 2.36% in Table 1, a 0.23 percentage-point difference that could flip under resampling. I ask for paired bootstrap or nested resampling across instances and repeated MCTS runs, reporting standard errors and tuning-to-test degradation, before the 'match or surpass' statement can be accepted.","section":"§3.3, Table 1, Section 4.2"},{"comment":"GT-Prior is described as 'parameter-free', but its distribution P_N(k) is an empirical histogram fitted to Concorde and LKH-3 optimal tours on uniform instances. This means the uniform benchmark partially measures transfer of a ground-truth-fitted distribution, not a purely assumption-free prior. The authors disclose the fitting in Appendix K and Figure 3, but the term 'parameter-free' is misleading and the comparison against learned heatmaps is not an apples-to-apples test of 'no learning'. I recommend either renaming this as an empirical prior with zero trainable parameters or adding an ablation using a fixed geometric prior (e.g., P(k) proportional to 1/k) to show that the specific fitted shape is not the source of the gains.","section":"§5.1, Eq. (5)-(7), Appendix K"},{"comment":"The cross-distribution results are internally surprising and undermine the generalization narrative as presented. GT-Prior achieves 2.13% gap on uniform TSP-10000 (Table 1) but 0.35% on clustered, 0.93% on explosion, and 0.58% on implosion TSP-10000 instances (Table 3). SoftDist similarly shows 2.94% on uniform but 0.33% on implosion. If these numbers are correct, the paper should explain the mechanism: does the uniform-tuned MCTS configuration transfer much better to non-uniform instances, or do the distribution-specific optimal tour lengths make the gap denominator more forgiving? As written, the table suggests either a large unmodeled interaction or a reporting inconsistency. At minimum, per-instance results and the specific MCTS configurations used for each distribution row should be provided.","section":"Table 3"},{"comment":"The 'Zero' heatmap is described as providing no edge guidance, but when Use_Heatmap is set to False the MCTS still uses Euclidean distance for candidate set construction. The text in Section 5.2 says the Zero heatmap relies on 'distance for candidate selection', which is itself a form of guidance. This makes the Zero baseline a distance-based candidate set, not a no-information control, and weakens the claim that tuned MCTS alone achieves 0.66% on TSP-500. Please clarify exactly what information the Zero baseline receives and how it differs from a truly uninformative uniform candidate set.","section":"§5.2, Section 3.5, footnote 1"},{"comment":"The row 'Tuned on TSPLIB' tunes MCTS hyperparameters on the same TSPLIB instances used for evaluation, so it is an in-sample tuning result rather than a generalization result. The paper does label this row clearly, but the abstract's claim of strong performance on 'established real-world TSPLIB benchmarks' should not be read as out-of-distribution generalization. I recommend moving 'Tuned on TSPLIB' out of the generalization table or explicitly stating in the main text that these are optimistic in-sample upper bounds.","section":"Appendix F, Table 7"}],"minor_comments":[{"comment":"The text says Max_Candidate_Num has a 'strong, often positive, impact' and then concludes that reducing the candidate set size can improve quality, but a positive SHAP value indicates longer tours, i.e., worse performance. The causal direction should be stated explicitly to avoid confusion.","section":"§4.1, Figure 1"},{"comment":"The caption calls these box plots, but the text describes green circles, red crosses, and blue stars. The figure appears to overlay point markers on distributions; the caption should describe the actual plot elements.","section":"Figure 2"},{"comment":"The table says 'Bolded configurations indicate default settings from prior works', but the bold formatting is not visible in the text. Please mark the defaults explicitly, for example with a footnote.","section":"Appendix G, Table 11"},{"comment":"The description of test sets says they are 'sourced from Fu et al. [9]', but the number of test instances and the exact instance seeds are not stated. Please add instance counts and seed-generation details to the appendix for reproducibility.","section":"Section 3.5"},{"comment":"The phrase 'crippling 91.31%' is unnecessarily strong and not supported by the quantitative framing used elsewhere. Consider replacing it with a neutral statement such as 'a 91.31% gap'.","section":"Section 4.2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper does the neural-CO field a service. It shows that MCTS configuration moves the needle more than heatmap choice in the heatmap+MCTS paradigm, and it backs that with an unusually transparent pipeline: per-heatmap grid search over 864 configurations, full hyperparameter tables, per-instance TSPLIB results, code, and cross-distribution tests. The tuning spectrum in Figure 2 (DIMES swinging from 4.86% to 91.31% at TSP-10000 by MCTS settings alone) makes the first claim convincing. The Zero heatmap control—tuned MCTS with no heatmap at all reaching 0.66% on TSP-500—is a strong piece of evidence that search configuration has been undervalued.\n\nThe second claim is more delicate. GT-Prior, a k-NN prior with tuned MCTS, matches DIFUSCO on TSP-500/1000 (0.50% vs 0.33%, 0.85% vs 0.53%) and edges ahead at TSP-10000 (2.13% vs 2.36%). But that 0.23pp edge is not statistically established. The TSP-10000 tuning set has only 16 instances, the paper selects the best of 864 configurations, and there are no standard errors, confidence intervals, or paired tests anywhere. Winner's curse is a real risk: the chosen hyperparameter set may be lucky on those 16 instances and transfer poorly. A nested-resampling check or at least per-instance variance reporting would settle whether the same-distribution 'surpass' is real. The cross-distribution margins (e.g., 0.35% vs 1.96% on clustered TSP-10000) are large enough to survive this objection, so the broader conclusion—simple, structurally grounded priors are strong baselines—is probably right. But the specific head-to-head ordering on uniform TSP-10000 is not yet secure.\n\nMinor quibble: calling GT-Prior 'parameter-free' overstates it. The PMF in Appendix K is an empirical histogram fitted to Concorde/LKH-3 optimal tours on uniform instances. It is reproducible and practical, but it is not assumption-free. The authors' own limitations section acknowledges the empirical, Euclidean-only scope, which I read as honest.\n\nOverall: this deserves a serious referee. The evaluation is extensive and the direction of both findings is likely correct, but the paper should add variance estimates or significance tests, clarify the fitted nature of the GT-Prior PMF, and address tuning-selection noise before the headline numbers become canonical. I would bring it to a reading group and would cite it for the tuning pipeline and the baseline comparison.","headline":"A useful, transparent evaluation study showing MCTS tuning dominates heatmap choice, but the headline 'surpass' claim needs variance estimates before it is treated as definitive.","tokens_in":805,"tokens_out":921,"would_cite":true,"duration_ms":40615,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","68T20"],"pacs":[],"model":"deepseek-v4-flash","headline":"For MCTS-based TSP solvers, tuning the search matters as much as the heatmap, and a parameter-free k-nearest-neighbor prior can match learned heatmaps.","keywords":["traveling salesman problem","Monte Carlo Tree Search","heatmap","k-nearest neighbor","hyperparameter tuning","combinatorial optimization","generalization"],"falsifier":"Re-run the TSP-10000 comparison with several tuning seeds and many fresh test instances, reporting confidence intervals for each method's mean gap; if GT-Prior's 2.13% gap is not statistically below DIFUSCO's 2.36%, the 'match or surpass' claim collapses. Alternatively, if tuning MCTS on the test distribution instead of a small uniform tuning set changes the ranking of the methods, the protocol-transfer assumption fails.","tokens_in":38032,"feed_emoji":"🗺️","tokens_out":6309,"duration_ms":68413,"temperature":0.7,"pith_summary":"This paper tries to show that in the 'heatmap + Monte Carlo Tree Search' recipe for the traveling salesman problem, the search component has been undervalued. It argues that MCTS hyperparameter settings can change solution quality by tens of percentage points, and that per-heatmap tuning is required before heatmap methods are compared fairly. It introduces GT-Prior, a parameter-free heatmap that assigns each edge a probability from the empirical distribution of k-nearest-neighbor ranks in optimal tours. With an optimally tuned MCTS, GT-Prior matches or beats learned heatmaps such as DIFUSCO: 0.50% versus 0.33% gap at TSP-500, 0.85% versus 0.53% at TSP-1000, and 2.13% versus 2.36% at TSP-10000. The paper's point is that heatmap sophistication is not the main driver of performance, so evaluation should balance learning and search.","feed_headline":"Search tuning rivals fancier heatmaps in MCTS TSP solvers","feed_subtitle":"A tuned search brings a no-parameter prior to 2.13% on TSP-10000, below DIFUSCO's 2.36%.","key_machinery":"The load-bearing object is GT-Prior, a parameter-free heatmap defined by $P^N_{ij} = \\hat{P}_N(k_{ij})$, where $k_{ij}$ is the rank of city $j$ among city $i$'s neighbors by Euclidean distance and $\\hat{P}_N(\\cdot)$ is the averaged empirical distribution of nearest-neighbor ranks in optimal tours. This heatmap carries the argument by supplying edge probabilities that are cheap to compute, scale-independent, and transferable across instance sizes and distributions. The other essential mechanism is the MCTS hyperparameter tuning pipeline: a grid search over six parameters (Alpha, Beta, Max_Depth, Max_Candidate_Num, Param_H, and Use_Heatmap) run separately for each heatmap, so that comparisons isolate heatmap quality from search configuration. The paper uses SHAP value analysis to attribute performance changes to individual hyperparameters, showing that parameters like Max_Candidate_Num and Use_Heatmap have large, context-dependent effects.","core_discovery":"The central claim is that in the 'Heatmap + MCTS' paradigm, the configuration of the MCTS search component is a dominant, often decisive factor for solution quality, and that a simple heatmap built from a k-nearest-neighbor prior can rival or surpass complex learned heatmaps when the search is tuned properly. The paper derives GT-Prior from the empirical observation that, in optimal Euclidean TSP tours, the next city is almost always among a city's closest neighbors: the probability that the optimal edge connects to one of the top-5 nearest neighbors exceeds 94%, and the top-10 exceed 99%, with little variation across problem scale or distribution. GT-Prior sets each edge probability to the empirical frequency of that neighbor rank, requiring no learning phase. When combined with MCTS hyperparameters tuned per heatmap, GT-Prior achieves 0.50%, 0.85%, and 2.13% optimality gaps on TSP-500, TSP-1000, and TSP-10000, respectively, and it shows minimal performance degeneration when scaled up or shifted to clustered, explosion, implosion, and TSPLIB instances. The paper also shows that even a 'Zero' heatmap that gives no edge guidance improves from a 5.49% gap to 1.06% on TSP-1000 simply through MCTS tuning, underscoring how much of the reported performance in this line of work comes from search rather than learned priors.","pith_inferences":["If MCTS tuning is as powerful as the paper reports, some of the performance gains attributed to new learned heatmaps in prior literature may actually come from differences in search configuration; re-benchmarking under a standardized tuned-search pipeline could reorder published rankings.","A practical extension would be a hyperparameter recommender that predicts near-optimal MCTS settings from instance features and heatmap statistics, replacing exhaustive grid search while preserving the tuned-search comparison protocol.","Because GT-Prior is parameter-free and costs nothing at inference, it doubles as an economic sanity check: a learned heatmap should beat it by a margin that justifies the cost of training and heatmap generation.","The stability of the k-nearest-neighbor prior across distributions suggests that similar locality-based priors could serve as strong baselines for other Euclidean geometric optimization problems, such as vehicle routing variants."],"forward_implications":["Per-heatmap MCTS tuning should become standard practice in this line of research, since default MCTS settings can produce misleading rankings of heatmap methods.","Researchers should report a tuned non-informative baseline: a Zero heatmap already reaches 0.66% gap on TSP-500 and 1.06% on TSP-1000 after tuning, so a learned heatmap should be measured against it.","Because the k-nearest-neighbor locality property holds across scales and distributions, restricting candidate edges to a small k-NN neighborhood is a principled way to sparsify heatmap-guided search.","GT-Prior's near-zero degeneration when moving from TSP-500 to TSP-10000 or from uniform to clustered data establishes that simple structural priors are a strong generalization baseline for Euclidean TSP.","The comparison protocol introduced here, with dedicated tuning for each heatmap and a parameter-free prior as reference, provides a reusable template for fair evaluation of future heatmap models."],"supporting_citations":[{"why":"Introduces the heatmap + MCTS framework whose search procedure, default settings, and test instances this paper reuses and re-tunes.","marker":"[9]"},{"why":"Provides the DIFUSCO diffusion-based learned heatmap, the strongest learned baseline that GT-Prior is compared against.","marker":"[31]"},{"why":"Provides the DIMES meta-learned GNN heatmap baseline with its differentiable meta-solver approach.","marker":"[29]"},{"why":"Provides the UTSP unsupervised learned heatmap baseline used in the comparison.","marker":"[25]"},{"why":"Supplies the SoftDist distance-based heatmap and the MCTS setup reused for several of the baseline methods.","marker":"[37]"},{"why":"Supplies the TSPLIB benchmark instances used to test generalization to real-world structured problems.","marker":"[30]"},{"why":"Concorde provides the ground-truth optimal tours used to compute k-NN rank statistics and optimality gaps for TSP-500 and TSP-1000.","marker":"[1]"},{"why":"LKH-3 provides the near-optimal reference tours used as ground truth for TSP-10000.","marker":"[10]"}],"fun_headline_variants":["Tuned MCTS, not heatmap complexity, sets TSP solver quality","Simple kNN heatmap beats learned ones when search is tuned","Search tuning alone shrinks TSP gap from 5.49% to 1.06%","MCTS hyperparameters, not heatmap learning, decide TSP success","Even zero heatmap excels with properly tuned MCTS search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The conclusions rest on the assumption that the MCTS hyperparameters selected on a small tuning set of uniform instances remain appropriate on the unseen test instances and the other distributions, and that the reported gap differences between methods are larger than run-to-run and instance-to-instance noise.","fun_headline_variants_meta":{"raw":{"variants":["Tuned MCTS, not heatmap complexity, sets TSP solver quality","Simple kNN heatmap beats learned ones when search is tuned","Search tuning alone shrinks TSP gap from 5.49% to 1.06%","MCTS hyperparameters, not heatmap learning, decide TSP success","Even zero heatmap excels with properly tuned MCTS search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000225,"raw_usage":{"total_tokens":1546,"prompt_tokens":1108,"completion_tokens":438,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":724,"completion_tokens_details":{"reasoning_tokens":340}},"tokens_in":724,"tokens_out":438,"duration_ms":5522,"temperature":1.0,"reasoning_tokens":340,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T20:53:50.667622+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the TSP-10000 comparison with several tuning seeds and many fresh test instances, reporting confidence intervals for each method's mean gap; if GT-Prior's 2.13% gap is not statistically below DIFUSCO's 2.36%, the 'match or surpass' claim collapses. Alternatively, if tuning MCTS on the test distribution instead of a small uniform tuning set changes the ranking of the methods, the protocol-transfer assumption fails.","supporting_citations":[{"cited_title":"Generalize a small pre-trained model to arbitrarily large tsp instances","cited_arxiv_id":null,"evidence_quote":"Introduces the heatmap + MCTS framework whose search procedure, default settings, and test instances this paper reuses and re-tunes."},{"cited_title":"Difusco: Graph-based diffusion solvers for combinatorial optimization","cited_arxiv_id":null,"evidence_quote":"Provides the DIFUSCO diffusion-based learned heatmap, the strongest learned baseline that GT-Prior is compared against."},{"cited_title":"Dimes: A differentiable meta solver for combinatorial optimization problems","cited_arxiv_id":null,"evidence_quote":"Provides the DIMES meta-learned GNN heatmap baseline with its differentiable meta-solver approach."},{"cited_title":"Unsupervised learning for solving the travelling salesman problem","cited_arxiv_id":null,"evidence_quote":"Provides the UTSP unsupervised learned heatmap baseline used in the comparison."},{"cited_title":"Position: Rethinking post-hoc search-based neural approaches for solving large-scale traveling salesman problems","cited_arxiv_id":null,"evidence_quote":"Supplies the SoftDist distance-based heatmap and the MCTS setup reused for several of the baseline methods."},{"cited_title":"Tsplib—a traveling salesman problem library","cited_arxiv_id":null,"evidence_quote":"Supplies the TSPLIB benchmark instances used to test generalization to real-world structured problems."},{"cited_title":"Certification of an optimal tsp tour through 85,900 cities","cited_arxiv_id":null,"evidence_quote":"Concorde provides the ground-truth optimal tours used to compute k-NN rank statistics and optimality gaps for TSP-500 and TSP-1000."},{"cited_title":"An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems","cited_arxiv_id":null,"evidence_quote":"LKH-3 provides the near-optimal reference tours used as ground truth for TSP-10000."}],"review_version":1}