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

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 $182.11\times$ speedup in inference over the original inference pipelines.