- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes SIF, an inference framework for heatmap-based routing solvers. It combines memory-efficient candidate graph construction, sparse heatmap storage, and GPU-resident decoding, with a geometric rescue mechanism for infeasible candidate lists. Experiments on four existing solvers show reduced inference time and improved scalability without retraining.
Critical strengths
The paper addresses a practical bottleneck in existing heatmap-based solvers. The framework can be applied without retraining, and the experiments show reductions in runtime and memory usage. The component ablations are also helpful in explaining where the gains come from.
Critical weaknesses
-
The technical novelty is somewhat limited. Sparse candidate representations, GPU-resident tour construction, and geometric backup candidates have precedents in routing and ant-colony optimization, including GPU ACS [1] and NeuFACO [2]. The value here seems to lie mainly in combining these ideas into a reusable inference pipeline for existing neural solvers. I think the paper should position this contribution more carefully and explain what is technically new beyond these earlier designs.
-
The comparison with competing large-scale solvers is incomplete. Table 4 reports only the TTPL configuration with 1,000 reconstruction iterations, while the original TTPL paper [3] also reports much faster variants. For example, on CVRP50K, TTPL-MVDF achieves an objective of 1110.9 in 40.5 seconds, compared with 1155.71 in 67.80 seconds for HLGP+SIF. These timings come from different hardware, so they are not a controlled speed comparison, but the omitted variants could materially change the claimed quality–runtime trade-off. Moreover, the TSP50K/100K experiments compare only the original solvers and their SIF versions, without external large-scale baselines. A broader comparison is needed to establish how competitive the accelerated solvers are.
[1] The GPU-based Parallel Ant Colony System. 2016.
[2] NeuFACO: Neural Focused Ant Colony Optimization for Traveling Salesman Problem. 2025.
[3] Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning. 2025.
Questions for authors
-
Could the authors clarify the differences between SIF and earlier GPU-based sparse routing implementations, particularly in the decoder and rescue mechanism?
-
Could the authors include the faster TTPL configurations and external large-scale TSP baselines, ideally under comparable computational settings?
7 comments
Responses (2/3)
Q1: Could the authors clarify the differences between SIF and earlier GPU-based sparse routing implementations, particularly in the decoder and rescue mechanism?
Response:
Reply to the differences in decoding. We compared the differences between SIF and earlier GPU-based sparse routing from four aspects, as shown in the following table.
| Kernel design | ACS-GPU | SIF |
|---|---|---|
| Parallel task assignment | Multiple thread blocks construct multiple solutions in parallel, with one ant per block. | Each single-instance decoding call launches only one thread block, which processes the candidates at each step in parallel. |
| Scope of state writes | Each block updates its own construction state as well as pheromone values shared across blocks. | Only the current solution’s construction state is updated, with no writes shared across blocks. |
| Candidate selection within a block | The greedy branch performs a max reduction; the stochastic branch uses prefix sums and voting to implement roulette-wheel sampling. | A max reduction is performed over feasible candidates, with ties broken by the smallest node ID. No roulette-wheel sampling is performed. |
| Visited-state representation | A Boolean array records whether each node has been visited. | A packed bitmap records visited states; bits are tested to check visits and set to mark them. |
In addition, we have added CUDA Graphs and torch.compile baselines using the same sparse candidate construction strategy. The results are presented as follows. As shown in table, compared with CUDA Graphs, our decoder remains 1.48×/1.53× faster on CVRP50K/CVRP100K, reducing decoding time by an additional 32.3%/34.6%. Against the fastest evaluated generic baseline at each scale, it retains 1.48×/1.46× speedups.
| Method | CVRP50K Time(s) | CVRP100K Time(s) |
|---|---|---|
| GPU-resident decoding (ours) | 17.52 | 35.82 |
| CUDA Graphs | 25.87 | 54.73 |
torch.compile, Graphs off | 43.87 | 85.21 |
torch.compile, Graphs on | 28.61 | 52.32 |
Reply to the differences in rescue. The key difference between SIF and NeuFACO is that SIF prioritizes nearby nodes only within its backup candidate list, whereas NeuFACO still searches for the globally nearest unvisited node after its backup list is exhausted. This design aims to balance local candidate selection with decoding efficiency on large-scale instances. SIF retains the preference for nearby nodes within the bounded backup list. Once the search must extend beyond the list, SIF stops as soon as it finds a feasible node, without comparing distances to all remaining nodes to identify the nearest one.
Responses (3/3)
Weakness 2: The comparison with competing large-scale solvers is incomplete… A broader comparison is needed to establish how competitive the accelerated solvers are.
Q2: Could the authors include the faster TTPL configurations and external large-scale TSP baselines, ideally under comparable computational settings?
Response: We thank the reviewer for the valuable suggestion.
CVRP: We have included faster TTPL variants (TTPL and TTPL-MDVF) and re-evaluated them under same machine. The results are presented below. It can be seen that GLOP+SIF and HLGP+SIF offer competitive trade-offs between solution quality and runtime, particularly on CVRP100K. AGFN+SIF yields a substantially higher cost than the external baselines on CVRP50K (10,754.97). Furthermore, we analyze AGFN+SIF’s substantially higher cost relative to the baselines on CVRP50K in more detail below.
| Methods | CVRP50K Obj. | CVRP50K Time | CVRP100K Obj. | CVRP100K Time |
|---|---|---|---|---|
| HGS | 1081.00 | 4.00h | 2087.50 | 6.30h |
| TTPL | 1143.53 | 1.20m | 2220.41 | 2.39m |
| TTPL-MDVF | 1110.86 | 1.18m | 2163.34 | 2.56m |
| INViT | 1330.18 | 2.30h | 2683.42 | 8.82h |
| GLOP+SIF | 1264.93 | 46.58s | 2137.94 | 2.19m |
| HLGP+SIF | 1155.71 | 1.13m | 2101.69 | 2.93m |
| AGFN+SIF | 10754.97 | 1.59m | OOM | OOM |
| HBG-GFACS+SIF | 1681.22 | 37.06s | 3380.93 | 2.30m |
TSP: We have added external large-scale baselines for TSP50K/100K, with all methods evaluated on the same hardware. Compared with these baselines, HBG-GFACS+SIF yield higher costs on both TSP50K and TSP100K. We would like to clarify that SIF is designed to enable existing solvers to handle larger instances under a fixed GPU memory budget while reusing their pretrained checkpoints. At these larger scales, solution quality still depends on how well the underlying solvers generalize with those checkpoints.
| Methods | TSP50K Obj. | TSP50K Time | TSP100K Obj. | TSP100K Time |
|---|---|---|---|---|
| LKH-3 | 159.93 | 10.00h | 225.99 | 25.00h |
| Random Insertion | 182.65 | 15.40s | 258.13 | 1.70m |
| TTPL | 165.50 | 1.12m | 233.44 | 2.31m |
| TTPL-MDVF | 164.13 | 1.18m | 231.91 | 2.40m |
| GLOP | 168.27 | 1.76m | 237.86 | 2.89m |
| INViT | 170.98 | 1.34h | 242.17 | 5.02h |
| DIMES G | 193.90 | 39.68s | 274.54 | 80.03s |
| AGFN+SIF | 206.51 | 13.21s | 303.35 | 48.05s |
| HBG-GFACS+SIF | 936.36 | 2.48m | 1582.43 | 4.94m |
Generalization analysis
To verify this claim, we conducted generalization experiments under the problem scales that can be handled by AGFN and HBG-GFACS. For AGFN, we tested its generalization performance on cvrp5K and 10K datasets using models trained on cvrp1k dataset. For HBG-GFACS, we tested its generalization performance on cvrp5K and 10K datasets using models trained on cvrp100 dataset. The results are presented as follows. It can be seen that the original solver shows significant quality degradation as the problem size increases. Thus, the low-quality solutions at a large scale mainly reflect the limitations of the underlying solver itself.
(AGFN: CVRP5K: 29.10%–> CVRP10K: 48.87%)
| Methods | CVRP5K Obj. | CVRP5K Gap (%) | CVRP10K Obj. | CVRP10K Gap (%) |
|---|---|---|---|---|
| LKH-3 | 126.72 | 0.00 | 240.53 | 0.00 |
| AGFN | 163.59 | 29.10 | 358.07 | 48.87 |
| AGFN+SIF | 163.34 | 28.90 | 357.61 | 48.68 |
(HBG-GFACS: CVRP5K: 180.79%–> CVRP10K: 271.84%)
| Methods | TSP5K Obj. | TSP5K Gap (%) | TSP10K Obj. | TSP10K Gap (%) |
|---|---|---|---|---|
| LKH-3 | 50.97 | 0.00 | 71.78 | 0.00 |
| HBG-GFACS | 143.12 | 180.79 | 266.91 | 271.84 |
| HBG-GFACS+SIF | 142.93 | 180.42 | 266.89 | 271.82 |
Responses (1/3)
We thank the reviewer for the positive evaluation.
Weakness 1: The technical novelty is somewhat limited … is technically new beyond these earlier designs.
Response: We understand the reviewers' concerns regarding the "novelty" of our work. Following the reviewer’s suggestions, we have revised the introduction and contribution statements to position SIF as a reusable inference framework for existing heatmap-based solvers.
We wish to clarify that our contribution is to develop a scalable inference framework based entirely on sparse graphs , which addresses the representation and execution bottlenecks faced by existing heatmap-based solvers during large-scale inference.
1.SIF is not simply a combination of existing technologies. SIF ensures that the candidate edges and their scores remain sparse throughout the entire inference process, including candidate graph construction, heatmap prediction and storage, and GPU path construction.
During the graph construction stage, SIF follows the candidate selection criteria of the original solver. Through angle-ordered bidirectional circular search or blocked precise search, it directly generates Top-K main candidates for each node, avoiding the construction of a dense matrix.
During the heatmap generation stage, SIF aligns the K main candidate indexes of each node with the corresponding model prediction scores slot by slot, forming a sparse heatmap representation that can be directly read by the decoding kernel.
To enable the decoder to complete the entire solution construction on this sparse heatmap representation, we rewrote the candidate reading, feasibility check, and state update. The kernel directly reads the K main candidates of the current node at each step, checks feasibility in parallel, selects the next node, and updates the access state. The access state is recorded as a bitmap for each node.
These adaptations significantly improves the inference efficiency of these original models (e.g., SIF reduces the solution time of GLOP on CVRP20K instances from 30.22s to 10.52s). Moreover, SIF substantially expanded the maximum problem scale they can handle (GLOP: 20K—>100K; HLGP: 20K—>100K; AGFN: 20K—>50K; HBG-GFACS: 20K—>100K).
2.Actionable Insights for the Community. Our research reveals a problem that is often overlooked in existing large-scale neural combinatorial optimization studies. We demonstrate that the scalability of neural solvers is not only dependent on the model design but is also significantly constrained by the inference framework. Our work provides a new technical path for fully leveraging existing models and promoting their expansion to super-large-scale problems.