REVIEW 5 major objections 5 minor 1 cited by
A heatmap-guided ant system decodes large-scale TSP heatmaps to near-optimal tours in seconds to minutes.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · deepseek-v4-flash
2026-08-03 07:45 UTC pith:PJK6HYCL
load-bearing objection Useful decoder engineering, but the headline no-tuning claim rests on unreported per-heatmap/scale gamma selection, and the advantage over MMAS+2opt is thin; still worth refereeing. the 5 major comments →
HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problems
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
On its own terms, the paper establishes that treating a neural heatmap as a soft prior rather than a hard filter fixes the brittleness of greedy decoding. In HeatACO the probability of an ant moving from node i to node j is proportional to (tau_ij)^alpha (eta_ij)^beta (H_ij)^gamma, so the heatmap only reweights standard MMAS sampling; pheromone evaporation and reinforcement then act as instance-specific feedback that down-weights consistently conflicting high-confidence edges while up-weighting edges that recur in short tours. Optional 2-opt or 3-opt restricted to sparse candidate lists tightens the tours further. With this design and four pretrained predictors, fixed heatmaps decode to 0.11
What carries the argument
The load-bearing mechanism is the heatmap-biased transition rule, which combines three multiplicative signals—pheromone (global learned evidence), the distance heuristic (geometric preference for short edges), and the clipped heatmap raised to a strength exponent (the network's edge confidence)—together with sparse per-node candidate lists built from high-confidence heatmap edges with nearest-neighbour fallback. Pheromone updates give the system global coordination: edges that keep appearing in short tours are reinforced, and spuriously confident edges are suppressed relative to them. The exponent is the single calibration knob that trades trust in the predictor against search diversity.
Load-bearing premise
The headline gaps rely on tuning the heatmap-strength knob on the same benchmark instances being scored rather than by a label-free rule, and the abstract's promised automatic scaling is not what the main text implements.
What would settle it
Run HeatACO on TSP500/TSP1K/TSP10K choosing the heatmap strength only from the entropy rule in the appendix, never looking at benchmark tours, and compare against the reported 0.11%/0.23%/1.15% gaps; if the gaps inflate materially, the headline quality-time claim depends on label-based tuning. A second check: if vanilla MMAS with the same 2-opt budget and no heatmap matches those sub-2% gaps at N=10K, the heatmap prior contributes nothing.
If this is right
- Fixed heatmaps from four pretrained predictors decode to gaps as low as 0.11% on TSP500, 0.23% on TSP1K, and 1.15% on TSP10K within seconds to minutes of CPU decoding, without retraining the predictor.
- Greedy heatmap merging is the weak link at scale: the same heatmaps that produce large greedy gaps yield sub-2% gaps under HeatACO, so decoder choice, not just predictor quality, determines non-autoregressive pipeline performance.
- With 3-opt, gaps drop by roughly one to two orders of magnitude—near zero on TSP500/1K and about 0.4% on TSP10K—at the cost of additional minutes, giving an explicit quality-time knob.
- Heatmap guidance consistently improves construction over vanilla MMAS with the same search budget, and the improvement persists even when local search is enabled.
- The decoder is predictor-agnostic: one configuration transfers across four heatmap sources and to out-of-distribution real-world instances, provided the heatmap's edge ranking stays informative.
Where Pith is reading between the lines
- Editorial flag: the abstract describes a 'capped, degree-aware evidence factor' whose strength scales automatically from the pheromone dynamic range, but the main text and appendix implement plain H^gamma bias with gamma chosen by coarse sweep or an entropy rule; the body's version is the reproducible claim behind the reported numbers.
- If these results hold, the practical frontier moves from decoder engineering to heatmap calibration: decoder gains are capped by how well the predictor preserves a sparse, well-ranked candidate set, so cheap diagnostics such as edges-per-node and low-confidence mass could tell practitioners when to trust the prior.
- A natural testable extension is using the same MMAS-with-heatmap-prior decoder on asymmetric TSP or vehicle-routing heatmaps, where greedy methods degrade even faster and the paper reports competitive asymmetric-TSP transfer.
- The entropy-targeted label-free gamma rule is the untested load-bearing extension: if it can reproduce the headline gaps without benchmark tours, HeatACO becomes genuinely plug-and-play; if not, gamma tuning remains a per-dataset expense.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes HeatACO, a Max–Min Ant System decoder for non-autoregressive TSP heatmaps. The heatmap is injected as a multiplicative prior into the MMAS transition rule (Eq. 9), with pheromone feedback serving as instance-specific global conflict resolution. On the TSP500/1K/10K benchmarks, using four fixed pretrained heatmap predictors, HeatACO+2opt reports gaps as low as 0.11%/0.23%/1.15% with seconds-to-minutes CPU decoding, improving over greedy decoding and published MCTS-guided decoding. The paper also analyzes heatmap reliability through candidate sparsity, confidence-mass concentration, and out-of-distribution TSPLIB transfer.
Significance. If the reported results hold under a properly validated configuration protocol, HeatACO would be a valuable plug-and-play decoder: it is predictor-agnostic, simple to implement, and offers a better quality–time trade-off than MCTS-guided decoding on large instances. The paper has clear strengths: the internal ablation against vanilla MMAS with identical budget is well controlled; the sparse-candidate complexity analysis is explicit; the fixed-heatmap evaluation cleanly isolates the decoding stage; and the TSPLIB transfer study extends the analysis beyond the uniform benchmark distribution. However, the central 'no per-predictor tuning' claim is currently not supported by the reported experimental protocol, because the main free parameter γ is selected on the same benchmark instances used for evaluation. This must be addressed before the headline numbers can be taken at face value.
major comments (5)
- [§6.2, Figure 4, Table 1] The headline gaps in Table 1 appear to be obtained after a coarse γ sweep over {0.1,0.5,1.0,2.0} conducted on the same benchmark instances that are used for evaluation. The paper does not report the γ values selected for each heatmap source and scale, and Appendix G.1 shows that the best γ varies with heatmap, scale, and whether local search is enabled. The only label-free alternative, the entropy-targeted rule in Appendix G.2, is not used in the main experiments and no evidence is provided that it recovers the Table 1 gaps. Since γ in Eq. (9) is the sole term that injects the heatmap into the transition policy, this makes the abstract's 'without per-predictor tuning' claim unsupported and turns the reported quality–time trade-offs into a test-set-selected result. Please report the γ values used, or better, fix γ via a validation split, and demonstrate that the label-free entropy rule gi
- [Abstract vs. §3.2] The abstract states that the strength of the heatmap evidence factor is 'scaled automatically from the pheromone dynamic range', but the method section (Eq. 9) introduces a free exponent γ and does not describe any automatic scaling mechanism. This mismatch is not merely cosmetic: it is central to the plug-and-play claim. If the automatic scaling claim is correct, the mechanism should be specified in §3.2 and the entropy-based tuning in Appendix G.2 should be presented as a fallback. If not, the abstract should be revised to acknowledge that γ is a hyperparameter requiring coarse tuning.
- [§4.4, Tables 1–3] The evaluation protocol reports averages over 10 random seeds per instance, but no standard deviations, confidence intervals, or per-heatmap spreads are given anywhere in the main tables. For the small gaps on TSP500 (e.g., 0.11% vs 0.17% across heatmap sources) and TSP1K, it is impossible to assess whether the differences are statistically meaningful. Please add variance information (e.g., std, CI, or min–max) for the main results, or explicitly state which differences are not significant.
- [Appendix B.2, Table 1] The quality–time comparison with MCTS uses published 128-core runtimes for the MCTS baseline while HeatACO runs on 16 threads. Appendix B.2 itself says these numbers are 'indicative rather than strictly comparable'. This weakens the headline claim of a 'better quality–time trade-off' than MCTS. Please either rerun the MCTS decoder on the same 16-thread hardware, or clearly present the MCTS comparison as order-of-magnitude and not a direct benchmark.
- [Table 3] The MMAS+3opt runtime on TSP1K is reported as 5.79s, identical to the vanilla MMAS runtime in Table 1 (5.79s). Adding a 3-opt pass should increase the runtime, so this exact match is implausible and suggests a reporting error. Please re-check all Table 3 runtimes; this is important because the 3-opt results are used to claim an additional order-of-magnitude gap reduction.
minor comments (5)
- [§4.4] The protocol says '10 random seeds per instance' but does not state the number of benchmark instances per scale. Please specify the instance counts (e.g., 10 instances per size, as in the AttGCN benchmark) so the reader can interpret the averages.
- [Table 1] The GLOP row is labeled 'NAR+AR', which is likely a typo; GLOP is not autoregressive in the usual sense. Please correct the Type column or clarify the abbreviation.
- [Appendix G.1] Figure 10's γ sensitivity with 2-opt/3-opt is described in the text but the figure labels are not referenced in a reader-friendly way. Adding a legend that names each heatmap source and scale directly in the caption would help.
- [Title and body] The method is written as 'HeatACO' in the title and 'HEATACO' throughout the body. Please standardize the spelling.
- [Appendix E] For the TSPLIB results, the exact source of the reference tour lengths (e.g., TSPLIB optimal values or best-known) should be explicitly cited, not just referred to as 'TSPLIB reference'.
Circularity Check
Headline gaps depend on a heatmap-strength gamma chosen on the benchmark test set; the advertised label-free rule is not validated.
specific steps
-
fitted input called prediction
[Section 6.2 / Figure 4; Appendix C.2; Table 1 (Section 4.5), Eq. 9]
"Empirically, the best γ depends on both the heatmap source and the instance scale ... In practice, a coarse sweep γ∈ {0.1,0.5,1.0,2.0} is sufficient ... When benchmark tours are unavailable, Appendix G.2 provides a label-free entropy-targeted rule to select γ from the heatmap scores alone. ... since the decoder directly optimises tour length, γ can be selected without labels by a short coarse sweep (e.g., {0.1,0.5,1,2}) with a small iteration budget and choosing the best tour; Section 6.2 shows that such coarse tuning is sufficient in practice."
The headline gaps in Table 1 are the paper's central empirical prediction. The only parameter that injects the heatmap into the decoder, γ in Eq. (9), is not fixed by the method; the paper states that its best value depends on heatmap source and scale and recommends choosing it by a coarse sweep. Because the sweep is conducted on the same TSP500/1K/10K benchmark instances and uses the decoder's tour length (equivalently gap) as the selection criterion, the reported 0.11%/0.23%/1.15% numbers are test-set-selected operating points rather than the output of the advertised untuned plug-and-play configuration. The paper does not report which γ produced Table 1, nor does it show that the label-free entropy rule (Appendix G.2) reproduces the headline gaps. Thus part of the claimed prediction is f
full rationale
The core MMAS transition rule (Eq. 9) is an independent algorithmic proposal: it is not derived from benchmark tours, and no load-bearing self-citations appear. The circular/contaminated element is evaluation of the central plug-and-play claim: the free heatmap exponent γ is the only term that injects H into the decoder, and the paper admits its best value varies with heatmap source and scale, recommending selection by a coarse sweep on the same benchmark instances used for the reported gaps. The label-free entropy rule in Appendix G.2 is a possible escape, but no evidence is given that it recovers the headline numbers, and the abstract's 'scaled automatically from the pheromone dynamic range' mechanism is not specified in Section 3. The MCTS runtime comparison is also explicitly only 'indicative' (Appendix B.2). These issues undermine the headline quality-time trade-offs as evidence for an untuned decoder, but they do not make the decoder derivation itself equivalent to its inputs, so a moderate score of 4 is appropriate.
Axiom & Free-Parameter Ledger
free parameters (4)
- gamma (heatmap exponent) =
0.1-2.0 per heatmap/scale via coarse sweep
- alpha, beta (MMAS exponents) =
not stated
- entropy targets S*_LS, S*_noLS =
8 and 4
- candidate list size k =
20
axioms (4)
- domain assumption The thresholded heatmap retains ~96-100% of optimal-tour edges at 3-12N candidates (Section 5.1, Table 4).
- standard math MMAS pheromone updates converge to useful global feedback under the fixed iteration budget (I=5000, m=32).
- domain assumption Published MCTS decoder numbers (Pan et al., 2025) are comparable despite different CPU core counts and tuning.
- domain assumption Pretrained heatmaps from AttGCN, DIMES, UTSP, and DIFUSCO are representative of NAR solvers.
read the original abstract
Non-autoregressive neural solvers predict an edge-confidence heatmap for the Travelling Salesman Problem (TSP) in one forward pass, but a decoder must still produce a feasible Hamiltonian cycle. As instance size grows, this stage must reconcile a quadratic number of edge scores with global tour constraints. Greedy edge merging is fast and deterministic but produces low-quality tours, whereas Monte Carlo Tree Search (MCTS) over k-opt moves recovers better tours at high computational cost and requires predictor-specific tuning. We propose HeatACO, a predictor-agnostic heatmap-to-tour decoder. Its key is a capped, degree-aware evidence factor that integrates a fixed heatmap into a Max--Min Ant System (MMAS). The factor rewards only edge confidence beyond a node's tour-degree capacity, and its strength is scaled automatically from the pheromone dynamic range, allowing one configuration to decode heatmaps from different predictors without retraining or per-predictor tuning. Across four heatmap sources, HeatACO produces higher-quality solutions in less decoding time than the MCTS baseline on TSP500, TSP1K and TSP10K. Against matched standard MMAS baselines with the same search budget, heatmap guidance improves construction for all four predictors at both scales and remains beneficial with local search. HeatACO also transfers competitively to several distribution shifts and the asymmetric TSP (ATSP). Our post-hoc analysis identifies measurable heatmap properties associated with the observed performance variation.
Figures
Forward citations
Cited by 1 Pith paper
-
Beyond Static Priors: Dynamic Neural Guidance for Large-Scale Ant Colony Optimization
DyNACO uses periodic observation of pheromone and incumbent solution for dynamic neural guidance in large-scale ACO, improving TSP and CVRP solvers with low overhead.
Reference graph
Works this paper leans on
-
[1231]
PMLR, April 2023. ISSN: 2640-3498. Costa, P. R. d. O., Rhuggenaath, J., Zhang, Y ., and Akcay, A. Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning. InProceed- ings of The 12th Asian Conference on Machine Learning, pp. 465–480. PMLR, September 2020. ISSN: 2640-3498. Davendra, D. (ed.).Traveling Salesman Problem: ...
Pith/arXiv arXiv 2023
-
[2000]
doi: 10.1016/S0167-739X(00) 00043-1
ISSN 0167-739X. doi: 10.1016/S0167-739X(00) 00043-1. Sun, Z. and Yang, Y . DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. November 2023. Vinyals, O., Fortunato, M., and Jaitly, N. Pointer Networks. ArXiv, June 2015. Wang, M., Zhou, Y ., Cao, Z., Xiao, Y ., Wu, X., Pang, W., Jiang, Y ., Yang, H., Zhao, P., and Li, Y . An Efficient D...
Pith/arXiv arXiv 2023
-
[2012]
ISSN 1943-0698. doi: 10.1109/TCIAIG.2012. 2186810. Chen, X. and Tian, Y . Learning to Perform Local Rewriting for Combinatorial Optimization, October 2019. arXiv:1810.00337 [cs, stat]. Cheng, H., Zheng, H., Cong, Y ., Jiang, W., and Pu, S. Se- lect and Optimize: Learning to solve large-scale TSP instances. InProceedings of The 26th International Con- fere...
Pith/arXiv arXiv 1943
-
[2022]
Huang, J., Chen, Z.-G., Jiang, Y ., and Zhan, Z.-H
arXiv:2106.05126 [cs, math]. Huang, J., Chen, Z.-G., Jiang, Y ., and Zhan, Z.-H. RsGCN: Subgraph-Based Rescaling Enhances Generalization of GCNs for Solving Traveling Salesman Problems, Septem- ber 2025. arXiv:2506.00533 [cs]. Hudson, B., Li, Q., Malencia, M., and Prorok, A. Graph Neural Network Guided Local Search for the Traveling Salesperson Problem, A...
Pith/arXiv arXiv 2025
-
[2023]
arXiv:2305.17010 [cs]. Zheng, Z., Zhou, C., Xialiang, T., Yuan, M., and Wang, Z. UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems, January 2025. arXiv:2407.00312 [cs]. Zhou, C., Lin, X., Wang, Z., and Zhang, Q. L2R: Learning to Reduce Search Space for Generalizable Neural Routing Solver, March 2025a. a...
Pith/arXiv arXiv 2025
-
[2024]
arXiv:2406.15007 [cs]. Bresson, X. and Laurent, T. The Transformer Network for the Traveling Salesman Problem.ArXiv, March 2021. Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. A Survey of Monte Carlo Tree Search Methods.IEEE Transactions on Computa- tional I...
arXiv 2021
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.