acceptodds
Under review as a conference paper at ICLR 2027

Sparse Is Not Enough: A Scalable Inference Framework for Heatmap-Based Methods

Abstract

Heatmap-based methods have shown strong performance on large-scale vehicle routing problems (VRPs), yet their scalability remains limited by inefficient inference pipeline. We identify two bottlenecks in existing inference pipelines: (1) quadratic intermediate representations during candidate graph construction and heatmap representation. (2) inefficient autoregressive decoding due to substantial CPU-side overhead from launching numerous fine-grained GPU operations. To address these bottlenecks, we propose SIF, a scalable sparse inference framework. Specifically, SIF first employs sparse search strategies tailored to different sparsification criteria to construct candidate graphs, and then represents scores directly on the resulting sparse candidate pairs, thereby avoiding quadratic intermediate representations from both candidate graph construction and heatmap representation. To improve decoding efficiency, SIF fuses the entire autoregressive decoding loop into a single GPU-resident kernel, eliminating repeated CPU-side kernel launches. Moreover, a low-overhead rescue mechanism is introduced to mitigate the solution degradation caused by index-biased greedy fallback when sparsification leaves no feasible candidates. Notably, SIF can be integrated into existing heatmap-based solvers without modifying their learned models. Experiments on four representative heatmap-based methods show that SIF consistently extends the maximum solvable problem scale while substantially improving inference efficiency. On a single 24GB GPU, SIF enables representative heatmap-based solvers to process instances with up to 100,000 nodes and achieves up to a speedup in inference over the original inference pipelines.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Heatmap-Based Methods, Scalable Sparse Inference, Persistent Fused Decoding

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_12QaOpenReview ↗
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
  1. 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.

  2. 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
  1. Could the authors clarify the differences between SIF and earlier GPU-based sparse routing implementations, particularly in the decoder and rescue mechanism?

  2. Could the authors include the faster TTPL configurations and external large-scale TSP baselines, ideally under comparable computational settings?

7 comments
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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 designACS-GPUSIF
Parallel task assignmentMultiple 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 writesEach 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 blockThe 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 representationA 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.

MethodCVRP50K Time(s)CVRP100K Time(s)
GPU-resident decoding (ours)17.5235.82
CUDA Graphs25.8754.73
torch.compile, Graphs off43.8785.21
torch.compile, Graphs on28.6152.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.

AuthorsOpenReview ↗

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.

MethodsCVRP50K Obj.CVRP50K TimeCVRP100K Obj.CVRP100K Time
HGS1081.004.00h2087.506.30h
TTPL1143.531.20m2220.412.39m
TTPL-MDVF1110.861.18m2163.342.56m
INViT1330.182.30h2683.428.82h
GLOP+SIF1264.9346.58s2137.942.19m
HLGP+SIF1155.711.13m2101.692.93m
AGFN+SIF10754.971.59mOOMOOM
HBG-GFACS+SIF1681.2237.06s3380.932.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.

MethodsTSP50K Obj.TSP50K TimeTSP100K Obj.TSP100K Time
LKH-3159.9310.00h225.9925.00h
Random Insertion182.6515.40s258.131.70m
TTPL165.501.12m233.442.31m
TTPL-MDVF164.131.18m231.912.40m
GLOP168.271.76m237.862.89m
INViT170.981.34h242.175.02h
DIMES G193.9039.68s274.5480.03s
AGFN+SIF206.5113.21s303.3548.05s
HBG-GFACS+SIF936.362.48m1582.434.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%)

MethodsCVRP5K Obj.CVRP5K Gap (%)CVRP10K Obj.CVRP10K Gap (%)
LKH-3126.720.00240.530.00
AGFN163.5929.10358.0748.87
AGFN+SIF163.3428.90357.6148.68

(HBG-GFACS: CVRP5K: 180.79%–> CVRP10K: 271.84%)

MethodsTSP5K Obj.TSP5K Gap (%)TSP10K Obj.TSP10K Gap (%)
LKH-350.970.0071.780.00
HBG-GFACS143.12180.79266.91271.84
HBG-GFACS+SIF142.93180.42266.89271.82
Reviewer_gtQZOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents SIF, an inference framework for heatmap-based neural VRP solvers that targets two bottlenecks: quadratic intermediate representations in candidate graph construction and heatmap storage, and CPU-controlled autoregressive decoding with repeated fine-grained kernel launches. SIF replaces dense sparsification with exact angular-order or blocked KNN search, stores heatmap scores only on sparse candidate pairs, fuses the decoding loop into a single GPU-resident kernel, and adds a geometry-based rescue mechanism for cases where all candidates become infeasible. Integrated into four existing solvers (GLOP, HLGP, AGFN, HBG-GFACS) without retraining, SIF enables CVRP instances up to 100K nodes on a 24GB GPU with reported speedups up to 182× while preserving solution quality at scales where the original methods remain executable.

Critical strengths

The first strength is that the paper addresses a real, underexplored bottleneck with verifiable, large-magnitude gains. Rather than proposing another solver model, it targets the inference pipeline of existing heatmap-based methods and demonstrates, via careful stage-wise profiling (Tables 5–6) and ablations that hold model inputs fixed, that dense intermediate representations and CPU-controlled kernel launches are the actual limiting factors. The reported gains—extending solvable scale from 20K to 50K–100K nodes on a single 24GB GPU and speedups of up to two orders of magnitude with preserved solution quality—are practically consequential.

The second strength is model-agnosticism combined with breadth of validation. Because SIF reuses released checkpoints without retraining and is integrated into four diverse heatmap-based methods (decomposition-based GLOP/HLGP and GFlowNet-based AGFN/HBG-GFACS) across two problems and scales from 200 to 100K nodes, the results indicate the bottlenecks are systemic to the paradigm rather than artifacts of one implementation. This generality substantially raises the likelihood that the findings transfer to the broader class of heatmap-based neural CO methods.

Critical weaknesses

The main weakness is that the individual techniques have documented precedents, and the paper does not adequately delineate its contribution against them. Sparse kNN heatmaps without dense storage are already used in DIMES and DIFUSCO; blocked/tiled KNN computation is standard in GPU ANN libraries; fused or persistent GPU kernels are mature in LLM inference; and geometric fallback is standard in LKH-style candidate lists. As written, the novelty claim ("sparse is not enough") risks reading as rediscovery of known systems techniques applied to a new pipeline. This is consequential because the paper's contribution is best characterized as integration rather than new method, and the current framing overstates novelty—which bears directly on whether it clears the bar for a top-tier venue. (That said, the integrated treatment for heatmap VRP inference, and specifically the single-kernel fusion of the construction decoder and the exact dense-free angular construction, do not appear documented, so this weakness is one of positioning and citation, not of validity.)

Questions for authors

Q1. DIMES (Qiu et al., NeurIPS 2022) and DIFUSCO already generate heatmaps on sparse kNN subgraphs and decode from sparse representations at large N. The paper's bottleneck claim is that these methods still materialize a dense N×N matrix during graph construction and store scores in a dense heatmap. Can the authors confirm, ideally with profiling numbers on the original codebases, exactly where in each of the four integrated methods the O(N²) intermediate is materialized (e.g., does GLOP's released implementation construct a full distance matrix, or does it already use a kNN library)? Without this, it is unclear whether SIF removes a bottleneck that genuinely exists in these specific pipelines or one that a straightforward engineering change (e.g., calling FAISS) would also remove. Q2. Blocked KNN construction is standard practice in GPU nearest-neighbor libraries (e.g., FAISS tiled search), and ranking by cosine similarity via angular sorting is a known equivalence in ANN search. What does SIF's construction component add beyond applying these existing techniques? In particular, is the angular-order equivalence of Proposition 1 (depot-relative cosine → circular angular distance) the substantive novel element, and if so, would you consider the blocked-KNN component a straightforward adaptation rather than a contribution? Q3. Single-kernel fusion to eliminate CPU-side launch overhead is a mature technique in LLM inference (FlashDecoding-style fusion, persistent kernels). The fused decoder here is simpler—each step parallelizes over K candidate slots with no data-dependent cross-step dependencies beyond state. What prevents a generic kernel-fusion tool or a compiler-based approach (e.g., CUDA graphs, torch.compile) from achieving the same decoding speedup without hand-written kernels, and did the authors evaluate such baselines? If CUDA graphs capture the original per-step kernel sequence and remove launch overhead, how much of the reported 4.6–5.7× decoding speedup remains attributable to the hand-fused kernel itself versus simply avoiding CPU dispatch? Q4. The rescue mechanism resembles candidate-list repair and nearest-neighbor fallback used in classical LKH-style solvers, and pure geometric priors (k-nearest) have been shown to be non-trivial baselines for large TSP (e.g., GT-prior, 2024). How does the rescue list differ from simply enlarging the candidate set (K+R) and falling back to geometric order within it? Is the separation into main/rescue tiers motivated by anything beyond memory savings, and does the rescue mechanism change the distribution of constructed solutions relative to a method trained with the enlarged candidate set?

5 comments
AuthorsOpenReview ↗

Responses (1/3)

We thank the reviewer for the positive evaluation.

Weakness: The main weakness is that the individual techniques have documented precedents, … do not appear documented, so this weakness is one of positioning and citation, not of validity.)

Response: We thank the reviewer for clarifying where the value of our work lies. We agree that our original framing of “Sparse Is Not Enough” overstated the novelty of the individual techniques. 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. In addition, we have expanded Related Work to discuss the precedents for each component and explained the adaptations that connect graph construction, sparse heatmap storage, and GPU-resident decoding.

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.

AuthorsOpenReview ↗

Responses (2/3)

Q1: DIMES (Qiu et al., NeurIPS 2022) and DIFUSCO … genuinely exists in these specific pipelines or one that a straightforward engineering change (e.g., calling FAISS) would also remove.

Response: We inspected their official implementations and identified dense representations in both graph construction and heatmap preparation. We specify each code location using the format file → function → line numbers.

MethodTaskCode location
GLOPCVRPheatmap/cvrp/inst.py → gen_cos_sim_matrix() → lines 22–27; heatmap/cvrp/inst.py → gen_pyg_data() → lines 37–55; nets/partition_net.py → Net.reshape() → lines 100–111
HLGP (RL)CVRPgraph_partition/hlgp_rl/cvrp_env.py → OneShotCVRPEnv.reset() → lines 166–169; graph_partition/hlgp_rl/cvrp_model.py → reshape() → lines 36–45
AGFNCVRPcvrp/utils.py → gen_distance_matrix() → lines 67–71; cvrp/utils.py → load_test_dataset() → lines 112–118<br>cvrp/utils.py → gen_pyg_data() → lines 77–81; cvrp/net.py → Net.reshape() → lines 115–121
AGFNTSPtsp/utils.py → gen_distance_matrix() → lines 8–12; tsp/utils.py → gen_pyg_data() → lines 17–20; tsp/net.py → Net.reshape() → lines 115–121; tsp/test_tsp.py → search_result() → lines 49–59
HBG-GFACSCVRPGFACS/CVRP/utils.py → gen_distance_matrix() → lines 50–54; GFACS/CVRP/utils.py → load_test_dataset() → lines 95–101; GFACS/CVRP/utils.py → gen_pyg_data() → lines 60–64; GFACS/CVRP/net2.py → Net.reshape() → lines 120–126; GFACS/CVRP/test.py → infer_instance() → lines 45–54
HBG-GFACSTSPGFACS/TSP/utils.py → gen_distance_matrix() → lines 8–18; GFACS/TSP/utils.py → gen_pyg_data() → lines 32–35; GFACS/TSP/net_tbdb.py → Net.reshape() → lines 122–128; GFACS/TSP/test.py → infer_instance() → lines 24–30

These bottlenecks cannot be removed merely through engineering changes. Tools such as FAISS can avoid materializing a full distance matrix during graph construction, but any replacement must preserve the original candidate-selection criterion, particularly the cosine similarity used by GLOP and HLGP. Moreover, optimizing graph construction does not automatically eliminate the subsequent dense heatmap representation. Doing so requires coordinated changes to edge-score storage, candidate access, and decoding interfaces, enabling the decoder to operate directly on sparse representations. SIF provides a unified sparse design across stages, rather than replacing a single graph-construction operator.

In addition, to further evaluate the applicability of the SIF’s decoder in existing sparse heatmap methods, we conducted a transfer experiment on DIMES, replacing the original decoder with our designed GPU-resident decoder. The experimental results are as follows. After replacing with the SIF’s resident decoder, the objective values of DIMES G remained consistent on TSP50K and TSP100K. The decoding time decreased from 39.68 seconds and 80.03 seconds to 1.14 seconds and 2.48 seconds respectively, achieving approximately 34.8× and 32.3× acceleration.

MethodsTSP50K Obj.TSP50K TimeTSP100K Obj.TSP100K Time
DIMES G193.9039.68s274.5480.03s
DIMES G + GPU-resident decoding193.901.14s274.542.48s

Q2: Blocked KNN construction is standard practice … would you consider the blocked-KNN component a straightforward adaptation rather than a contribution?

Response: Our claim is not that the relationship between cosine similarity and angular distance is newly discovered, but that we exploit it to construct the original heatmap-based solver’s candidate graph exactly, without materializing a dense similarity matrix. The angular-order equivalence of Proposition 1 provides the correctness guarantee for this replacement, rather than serving as a standalone mathematical novelty.

We agree that blocked-KNN is an adaptation of established blocking techniques. Its role is to extend the same sparse inference framework to solvers with distance-based candidate rules, not to introduce a new nearest-neighbor search algorithm. According to the reviewers' suggestions, we have provided explanations at the corresponding positions in the methodology.

AuthorsOpenReview ↗

Responses (3/3)

Q3: Single-kernel fusion to eliminate CPU-side launch overhead is a mature technique in LLM inference … the hand-fused kernel itself versus simply avoiding CPU dispatch?

Response: We thank the reviewers for pointing out this important question. 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.

MethodCVRP50K Time(s)CVRP100K Time(s)
GPU-resident decoding (ours)17.5235.82
CUDA Graphs25.8754.73
torch.compile, Graphs off43.8785.21
torch.compile, Graphs on28.6152.32

This additional benefit reflects the execution design of our hand-written kernel, rather than merely reducing CPU-side kernel submissions. CUDA Graphs retains the captured multi-operation sequence, while our compiler-based baselines still rely on host-side control to advance decoding and check completion. Our GPU-resident fused kernel instead integrates the decoding loop, state updates, and termination checks on the GPU. Thus, reducing CPU dispatch overhead through generic tools does not automatically produce an equivalent fused execution path; the added comparisons demonstrate the practical benefit of our kernel design.

Q4: The rescue mechanism resembles candidate-list repair and nearest-neighbor fallback used in classical LKH-style solvers … change the distribution of constructed solutions relative to a method trained with the enlarged candidate set?

Response:

Reply to “Difference.” We would like to clarify that rescue candidates do not participate in the base model’s inference and are selected by Euclidean distance only when all KK main candidates are infeasible. In contrast, expanding the model’s candidate set to K+RK+R includes the additional candidates in model computation and ranks them by learned scores.

Reply to “Motivation.” The rescue mechanism not only saves GPU memory but also improves solution quality. When all main candidates become infeasible, rescue provides geometric guidance to mitigate quality degradation caused by limited sparse candidate coverage, improving the performance of existing heatmap-based solvers on large-scale instances. The GLOP ablation in Fig. 3(a) shows that rescue reduces the objective value on CVRP20K from 597.35 to 571.76, a 4.28% improvement.

Reply to “Change.” Rescue mechanism can change the distribution of the final constructed solution. For the same decoding state, as long as there is a feasible main candidate, rescue does not affect the selection of this step; however, once triggered, its selection may alter the subsequent access order, remaining capacity, and sub-route division.

Reviewer_DJtCOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the inference scalability of heatmap-based neural solvers for vehicle routing problems. The authors identify two bottlenecks in existing inference pipelines: • quadratic intermediate representations, arising when a dense N × N pairwise matrix is built to select candidate neighbors and when predicted scores are stored in a dense N × N heatmap; • a CPU-controlled autoregressive decoding loop that repeatedly launches fine-grained GPU kernels. They propose SIF, a training-free inference framework with three components: • memory-efficient exact sparse graph construction, using an angular-order search for the depot-relative cosine-similarity criterion and blocked KNN for the Euclidean criterion; • a sparse-aligned heatmap that stores scores only for retained candidate pairs, plus a geometry-based rescue list for when no main candidate is feasible; • a GPU-resident fused decoding kernel that runs the entire decoding loop within a single kernel launch. SIF is integrated into four existing solvers (GLOP, HLGP, AGFN and HBG-GFACS) without modifying their trained models. On a single 24 GB GPU, it extends the maximum solvable instance size from 20K to 50K–100K nodes on CVRP and TSP. It also reports speedups of up to 182.11× at the original benchmark scales, with comparable or slightly better solution quality.

Critical strengths

• Controlled evidence for useful memory reuse. The distinction between fusing history before the backbone and selectively retaining representations afterward is technically coherent. Table 5 tests both components separately and together across three scales, rather than relying only on comparisons with unrelated architectures. On TSP10K, full three-layer MiLoop obtains a 2.56% gap, compared with 5.63% without either memory component and 4.39% for a six-layer memory-free model; the reported times are 2.96s versus 5.84s for the latter comparison. Table 4 also tests an existing recurrent embedding design. • Strong large-scale generalization. In table 1, the model is trained on TSP100, but it achieves 1.56% and 1.81% gap on TSP5K and TSP10K, respectively. Sec 4.2 shows that the model can reaches high quality solutions in ultra large instances.

Critical weaknesses

The paper repeatedly presents two limitations as inherent to the common inference pipeline of heatmap-based methods (Introduction, Sec. 3.2, Sec. 4.1, Appendix A): (i) quadratic intermediate representations in candidate-graph construction and heatmap storage; (ii) a CPU-controlled autoregressive decoding loop. • In fact, both limitations are specific to the implementations of the evaluated baselines (GLOP, HLGP, AGFN and HBG-GFACS, which share the same DeepACO-derived codebase). Many other heatmap-based methods already address them in different ways: • For (i), DIFUSCO and Fast T2T build the sparse candidate graph with a KD-tree, without materializing any N × N matrix. DIMES keeps the predicted scores in a sparse (CSR) format throughout decoding. • For (ii), DIFUSCO and Fast T2T do not decode autoregressively with fine-grained GPU kernels. They extract tours by greedy edge insertion (compiled Cython on the CPU) followed by 2-opt. MCTS-based methods such as Att-GCN and UTSP run their search in C++. • Beyond the problem framing, the proposed components offer limited novelty: • Proposition 1 merely restates, via the identity s_ij = cos(θi − θj), the polar-angle ordering underlying the classical sweep algorithm (Gillett & Miller, 1974). • The rescue list is weaker than DIMES’s existing fallback. It only considers a fixed-length list of R precomputed neighbors, whereas DIMES selects the nearest unvisited node among all remaining nodes. Moreover, SIF still reverts to node-index order once the rescue list is exhausted. • The GPU-resident fused kernel, arguably the core contribution, is not described in detail in the Methodology. Eqs. (9)–(11) only restate masked greedy argmax, without explaining the kernel design (e.g., thread mapping, placement of the per-step state, support for sampling-based decoding). • 2. The experiments are insufficient to support the claimed contributions. • Insufficient baselines. SIF is only compared with the original pipelines of the four integrated solvers. The experiments include none of the following: • classical heatmap-based methods (e.g., DIFUSCO, Fast T2T, DIMES); • strong classical solvers such as LKH-3; • simple heuristics such as nearest neighbor. • At 50K/100K nodes, the only external baselines are INViT and TTPL on CVRP (Table 4), and their numbers are copied from the TTPL paper (Appendix C). On TSP50K/100K, there is no external comparison at all. • The reported results do not support the claimed contributions. • Solution quality. The main claim is that SIF extends the maximum solvable scale. At the newly reachable scales, however, the solutions are often far from competitive (Table 1). AGFN+SIF obtains 10754.97 on CVRP50K, about 9.7× the TTPL result (1105.6). “Solvable” thus mostly means “fits in 24 GB”, not “produces useful solutions”. • Efficiency. • The headline 182.11× speedup comes from HBG-GFACS on CVRP1000 with its local search disabled (Appendix C). This is a scale at which the original pipeline already runs, and a configuration in which its main improvement stage has been removed. • At the 5K–20K scales that motivate the paper, the end-to-end speedups of GLOP and HLGP are only 2.5–3.7× (Table 2). • At 50K/100K, where SIF is claimed to matter most, there is no controlled end-to-end runtime comparison at all: the original pipelines run out of memory, and the INViT/TTPL runtimes come from another paper and different hardware.

Questions for authors

• Q1. All four evaluated solvers descend from the DeepACO codebase. Have you applied SIF to heatmap-based solvers from other families that already use KD-tree graph construction and compiled decoders (e.g., DIFUSCO, Fast T2T, DIMES)? If so, what is the gain? • Q2. Please provide a breakdown of the speedup into its sources (sparse representation, kernel fusion, removal of per-step host synchronization) for all four solvers, not only GLOP. Please also compare against CUDA Graphs, torch.compile and a compiled CPU decoder that use the same sparse candidates. For HBG-GFACS, how is the dense N × N pheromone matrix represented and updated under SIF, and does this change the ACO algorithm? • Q3. What is the solution quality (gap / objective) at 50K and 100K compared with strong classical solvers (e.g., LKH-3, HGS) and simple constructive heuristics (e.g., nearest neighbor)? How do you interpret the AGFN+SIF result on CVRP50K (10754.97) and the HBG-GFACS+SIF results on TSP50K/100K (936.36 / 1582.43)? • Q4. How does the rescue mechanism differ from DIMES’s fallback, which selects the nearest unvisited node among all remaining nodes, and why is a fixed-length list of R neighbors preferable? Fig. 4b reports about 90 global-fallback hits per instance on CVRP20K even at R = 96. How often do the rescue list and the index-order global fallback trigger at 50K/100K? • Q5. Appendix C states that the INViT and TTPL results in Table 4 are taken from the TTPL paper, so their runtimes were measured on different hardware. Please re-run INViT and TTPL on the same hardware as SIF (RTX 3090 Ti + Xeon E5-2620 v4), and report objective and runtime under identical conditions. Without this, the claimed “better trade-off between runtime and solution quality” cannot be assessed.

6 comments
AuthorsOpenReview ↗

Responses (1/5)

We thank the reviewer for the insightful feedback. For clarity, we group the Critical Weaknesses into five points and respond to each below.

Weakness 1: The paper repeatedly presents two limitations as inherent to the … MCTS-based methods such as Att-GCN and UTSP run their search in C++.

Response:

Reply to“(i): quadratic intermediate representations”.

We would like to clarify that quadratic intermediate representations are not limited to DeepACO-derived codebase. During greedy decoding, the released implementations of both DIFUSCO and Fast T2T invoke .toarray() in merge_tours() to convert sparse candidate-edge scores into a dense N×NN \times N matrix before performing greedy edge insertion.

MethodFileFunctionLines
DIFUSCOdifusco/utils/tsp_utils.pymerge_tours()104 and 106
Fast T2Tdiffusion/utils/tsp_utils.pymerge_tours()125 and 128

Reply to“limitation (ii): CPU-controlled autoregressive decoding loop .”

In the revised manuscript, we have expanded Related Work to discuss the decoding strategies identified by the reviewer (Appendix A in the revised manuscript). We have clarified which decoding scenarios GPU-resident fused kernel is designed for (Section 4.3 in the revised manuscript). We would like to clarify that the CPU-controlled GPU autoregressive decoding mode is not exclusive to the derivative methods of DeepACO. The DIMES TSP-KNN mentioned by the reviewer, when running in the CUDA environment, also initiates GPU operations step by step through a C++ loop on the host side to complete the greedy decoding, as shown in the following table.

OperationFileFunctionLines
Host-side C++ decoding loopTSP/torch_sampling/csrc/tsp.cppTspBaseSampler::sample()68–84
CUDA dispatch for CSR reductionTSP/torch_sampling/csrc/torch_scatter.cpptorch_scatter::segment_csr_fw()14–27
AuthorsOpenReview ↗

Responses (2/5)

Weakness 2: Beyond the problem framing, the proposed components offer limited novelty. … support for sampling-based decoding).

Responses: We understand the reviewers' concerns regarding the "novelty" of our work. However, 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.

Below are the explanations for each component.

Proposition 1. Proposition 1 establishes an exact per-node candidate-ranking equivalence, rather than merely restating the global angular ordering used in the classical Sweep algorithm. Sweep only scans the customers in the global polar angle order to construct the route, while SIF combines this order with bidirectional search to construct the candidate graph. (This point is explicitly stated in Line 224 of the original manuscript.)

Rescue mechanism. We acknowledge that restricting the candidate range for rescue operations may sacrifice some solution quality. The purpose of this mechanism is not to enhance the nearest neighbor recovery capability, but to balance search efficiency and solution quality in large-scale decoding. To this end, we conducted a case study using the first instance of CVRP100K dataset. We compare rescue (K=200,R=64K=200, R=64) with the integrated DIMES-style global fallback under the same configurations. Decoding time is measured from passing the prepared heatmap candidates to the decoder until the initial route is generated and GPU synchronization is complete. The results are as follows.

Time, Rescue / DIMES-Style FallbackObj. (Rescue / DIMES-Style Fallback)
1.82s / 4.11s2279.67 / 2295.44

GPU-resident fused kernel. We have expanded the Section GPU-resident fused decoding from four aspects: thread mapping, state organization, parallel selection, and state transition to explain the design of the kernel in detail (Section 4.3 in the revised manuscript). Regarding sampling-based decoding, our current implementation focuses on greedy decoding.

AuthorsOpenReview ↗

Responses (3/5)

Weakness 3: The experiments are insufficient to support the claimed contributions. Insufficient baselines. … not support the claimed contributions.

Weakness 5: At 50K/100K, .., and the INViT/TTPL runtimes come from another paper and different hardware.

Q3: What is the solution quality (gap / objective) at 50K ... and simple constructive heuristics (e.g., nearest neighbor)?

Q5: Appendix C states that the INViT and TTP ... the claimed “better trade-off between runtime and solution quality” cannot be assessed.

Response:

We have conducted additional experiments with a broader set of baselines on the same machine. CVRP: HGS, TTPL, INViT TSP: LKH-3, Random Insertion, TTPL, GLOP, DIMES. Note that DIFUSCO and Fast T2T encountered out-of-memory (OOM) errors at both scales. The results are presented as follows. It can be seen that GLOP+SIF and HLGP+SIF offer competitive trade-offs between solution quality and runtime, particularly on CVRP100K.

MethodsCVRP50K Obj.CVRP50K TimeCVRP100K Obj.CVRP100K Time
HGS1081.004.00h2087.506.30h
TTPL1143.531.20m2220.412.39m
TTPL-MDVF1110.861.18m2163.342.56m
INViT1330.182.30h2683.428.82h
GLOP+SIF1264.9346.58s2137.942.19m
HLGP+SIF1155.711.13m2101.692.93m
AGFN+SIF10754.971.59mOOMOOM
HBG-GFACS+SIF1681.2237.06s3380.932.30m

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. For a detailed analysis of the results, please refer to our response to “weakness 4”.

MethodsTSP50K Obj.TSP50K TimeTSP100K Obj.TSP100K Time
LKH-3159.9310.00h225.9925.00h
Random Insertion182.6515.40s258.131.70m
TTPL165.501.12m233.442.31m
TTPL-MDVF164.131.18m231.912.40m
GLOP168.271.76m237.862.89m
INViT170.981.34h242.175.02h
DIMES G193.9039.68s274.5480.03s
AGFN+SIF206.5113.21s303.3548.05s
HBG-GFACS+SIF936.362.48m1582.434.94m

Weakness 4: Solution quality. … means “fits in 24 GB”, not “produces useful solutions”.

Q3: How do you interpret the AGFN+SIF ... HBG-GFACS+SIF results on TSP50K/100K (936.36 / 1582.43)?

Responses:

To clarify this distinction, 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%)

MethodsCVRP5K Obj.CVRP5K Gap (%)CVRP10K Obj.CVRP10K Gap (%)
LKH-3126.720.00240.530.00
AGFN163.5929.10358.0748.87
AGFN+SIF163.3428.90357.6148.68

(HBG-GFACS: cvrp5k: 180.79%–> cvrp10k: 271.84%)

MethodsTSP5K Obj.TSP5K Gap (%)TSP10K Obj.TSP10K Gap (%)
LKH-350.970.0071.780.00
HBG-GFACS143.12180.79266.91271.84
HBG-GFACS+SIF142.93180.42266.89271.82

Weakness 5: The headline 182.11× speedup comes ... GLOP and HLGP are only 2.5–3.7× (Table 2).

Responses: In the revised manuscript, we have replaced the peak figure with the 2.50–3.71× end-to-end speedups for GLOP and HLGP on CVRP instances with 5K–20K nodes, the scales that motivate this work (The abstract in the revised manuscript).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.