Pith. sign in

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 →

arxiv 2601.19041 v2 pith:PJK6HYCL submitted 2026-01-26 cs.NE cs.LG

HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problems

classification cs.NE cs.LG MSC 90C2790C5968T20
keywords traveling salesman problemheatmap decodingMax-Min Ant Systemant colony optimizationnon-autoregressive neural solverslocal searchcombinatorial optimizationlarge-scale TSP
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper targets the decoding step of large-scale neural TSP solvers: after a network emits a dense edge-confidence heatmap, something must still assemble a feasible tour. HeatACO claims that the right way to use that heatmap is as a soft multiplicative bias inside a Max-Min Ant System—ants prefer edges the network trusts, while pheromone feedback over many sampled tours corrects edges that look good locally but break globally. On the standard TSP500/1K/10K benchmarks, with four fixed pretrained heatmaps, HeatACO plus 2-opt reaches gaps as low as 0.11%, 0.23%, and 1.15% within seconds to minutes of CPU time, beating greedy merging and matching or beating published MCTS-guided decoding at a fraction of the engineering cost. The authors also show the benefit is bounded by heatmap reliability: under distribution shift, miscalibrated or collapsed-confidence heatmaps shrink the decoder's advantage toward vanilla search.

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

5 major / 5 minor

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)
  1. [§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
  2. [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.
  3. [§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.
  4. [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.
  5. [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)
  1. [§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.
  2. [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.
  3. [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.
  4. [Title and body] The method is written as 'HeatACO' in the title and 'HEATACO' throughout the body. Please standardize the spelling.
  5. [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

1 steps flagged

Headline gaps depend on a heatmap-strength gamma chosen on the benchmark test set; the advertised label-free rule is not validated.

specific steps
  1. 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

4 free parameters · 4 axioms · 0 invented entities

The central claim depends on one fitted hyperparameter gamma, a few hand-set constants, and the quality of the pretrained heatmaps. No new physical or conceptual entities are introduced. The label-free gamma rule reduces the fitting burden but is not used for the headline results.

free parameters (4)
  • gamma (heatmap exponent) = 0.1-2.0 per heatmap/scale via coarse sweep
    Controls heatmap strength in Eq. (9); selected on the test benchmarks, with main results likely using the best value per condition. A label-free entropy rule is given but not used for headline numbers.
  • alpha, beta (MMAS exponents) = not stated
    Standard MMAS hyperparameters in Eq. (9), but values are not reported in the paper, hurting reproducibility.
  • entropy targets S*_LS, S*_noLS = 8 and 4
    Hand-chosen defaults for the label-free gamma rule in Appendix G.2.
  • candidate list size k = 20
    Standard MMAS default from Stützle & Hoos (2000), not fitted in this paper.
axioms (4)
  • domain assumption The thresholded heatmap retains ~96-100% of optimal-tour edges at 3-12N candidates (Section 5.1, Table 4).
    If this recall drops (e.g., under distribution shift), HeatACO's k=20 candidate lists with KNN fallback may miss needed edges, degrading the decoder.
  • standard math MMAS pheromone updates converge to useful global feedback under the fixed iteration budget (I=5000, m=32).
    Assumed from the ACO literature; Figure 2 shows convergence on these benchmarks, but there is no guarantee at larger scales or under distribution shift.
  • domain assumption Published MCTS decoder numbers (Pan et al., 2025) are comparable despite different CPU core counts and tuning.
    Appendix B.2 acknowledges the comparison is 'indicative' only, yet the headline quality-time claim relies on it.
  • domain assumption Pretrained heatmaps from AttGCN, DIMES, UTSP, and DIFUSCO are representative of NAR solvers.
    Four sources are used; results may not transfer to other heatmap predictors with different calibration.

pith-pipeline@v1.3.0-alltime-deepseek · 25769 in / 12289 out tokens · 129164 ms · 2026-08-03T07:45:47.041985+00:00 · methodology

0 comments
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

Figures reproduced from arXiv: 2601.19041 by Bo-Cheng Lin, Mengjie Zhang, Yi Mei.

Figure 1
Figure 1. Figure 1: Overview of heatmap-based decoding. Left: heatmap prediction (NAR), producing an edge-confidence matrix H from node coordinates. Top-right: standard ACO decoding constructs a tour using distance heuristics and pheromone feedback. Bottom-right: HEATACO injects H as a soft prior into ACO/MMAS sampling while preserving pheromone feedback to correct globally inconsistent local choices. heatmap ranking more clo… view at source ↗
Figure 2
Figure 2. Figure 2: Convergence without local improvement across scales. Let Li(t) be the mean best-so-far tour length at iteration t for method i (averaged over instances and 10 seeds). For each panel we define a common final baseline B = mini Li(I) at the last iteration I, then plot yi(t) = log10(Li(t) − B + c) with c = max(α mediani(Li(tmid) − B), ϵ), tmid = 0.5I, α = 0.03, and ϵ = max(|B| · 10−8 , 10−12). This highlights … view at source ↗
Figure 3
Figure 3. Figure 3: Interval contribution analysis of heatmap confidence values across instance scales. We partition heatmap scores into confidence intervals on [0, 1]. Bars report the (normalised) number of candidate edges per node whose confidence falls in each interval. The curve is normalised over the optimal-tour edges: for each interval, it reports the fraction of optimal-tour edges whose confidence falls in that interv… view at source ↗
Figure 4
Figure 4. Figure 4: Sensitivity of HEATACO (no local search) to the heatmap exponent γ across instance scales. Each cell reports the optimality gap (%) achieved by HEATACO when using a fixed heatmap source and a coarse γ ∈ {0.1, 0.5, 1.0, 2.0} sweep [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Decoding gap versus auxiliary heatmap cross-entropy diagnostics on TSP500/1K/10K benchmarks. Lines show the optimality gap (%) achieved by different decoders for each heatmap source; bars show the corresponding CE and WCE values from [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Instance geometry shift from standard random benchmark instances (top row) to real-world TSPLIB instances (bottom row). TSPLIB layouts are more structured and contain many locally similar configurations, which makes confidence calibration and downstream decoding more challenging. TSPLIB as a substantial distribution shift. The standard TSP500/1K/10K benchmarks draw node coordinates i.i.d. from a uniform di… view at source ↗
Figure 7
Figure 7. Figure 7: Decoding gaps on TSPLIB versus auxiliary CE/WCE diagnostics ( [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Interval contribution analysis on TSPLIB instances (pcb442, pr1002, pr2392). Each row corresponds to a heatmap predictor and shows how candidate edges distribute across confidence intervals (bars) and how optimal-tour edges concentrate (curve; normalised over optimal-tour edges). 19 [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Convergence of MMAS and HEATACO with 2-opt local improvement across scales. 20 [PITH_FULL_IMAGE:figures/full_fig_p020_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Sensitivity of HEATACO with local improvement to γ across instance scales (gap %). UTSP does not provide TSP10K heatmaps. Top row: 2-opt. Bottom row: 3-opt. rial optimisation; see the methodological overview by Ben￾gio et al. (Bengio et al., 2021) and the NCO survey of Liu et al. (Liu et al., 2023). Despite rapid progress, classical solvers such as Concorde (Applegate et al., 2006) and LKH￾3 (Helsgaun, 20… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Beyond Static Priors: Dynamic Neural Guidance for Large-Scale Ant Colony Optimization

    cs.NE 2026-06 unverdicted novelty 7.0

    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

6 extracted references · 5 linked inside Pith · cited by 1 Pith paper

  1. [1231]

    ISSN: 2640-3498

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

  2. [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...

  3. [2012]

    doi: 10.1109/TCIAIG.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...

  4. [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...

  5. [2023]

    NAR+G” rows in Table 1 are computed by running the DIFUSCO-released greedy decoder on the SoftDist-released heatmaps (Xia et al., 2024). The “+MCTS

    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...

  6. [2024]

    Bresson, X

    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...