PaperlayerView exact revision on arXiv

Source-linked AI summary

Size Generalization for Diffusion Routing Solvers

Barak Itzchak Davidovitch, Eli Meirom, Ethan Fetaya, Gal Chechik

arXiv:2610.17192v1cs.AI

TL;DR

Large routing instances are slow to solve, and generalizing diffusion solvers across instance sizes presents statistical and computational challenges. ResizeCO adapts a small-instance diffusion model with label-free reinforcement learning and GPU beam k-opt search; on TSP and CVRP it dominates learning-based methods across the quality-time Pareto front and achieves state-of-the-art quality at short run times.

  • Problem

    Large routing instances can take hours to solve, while size generalization must address changing instance statistics and the efficiency of optimization.

    Source: §1 · p. 1

  • Method

    ResizeCO trains a diffusion model on small instances, then fine-tunes it without labels using reinforcement learning on large instances and GPU beam search for k-opt.

    Source: §1 · pp. 1–2, §4.3 · p. 6

  • Results

    ResizeCO dominates learning-based methods across the quality-time Pareto front and achieves state-of-the-art quality at short run times on several TSP and CVRP size-generalization setups.

    Source: §1 · p. 2

  • Takeaways & Limitations

    ResizeCO is the first diffusion solver adapted without labels to large instances, including CVRP instances of size 10000.

    Source: §1 · p. 2

Abstract

from arXiv · show

Routing problems, like the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), are NP-hard and slow to solve for large instances. Diffusion-based solvers can be trained in a supervised way using sets of optimal solutions, and then quickly solve new test instances. However, for large instances, optimal solutions are hard to find, and diffusion models fail to generalize to instance sizes outside their training distribution. Here we describe ResizeCO, a label free size-generalization approach that addresses both the change in statistical properties of larger instances, and the computational challenge of solving them quickly. It uses reinforcement learning on large-scale instances to adapt a diffusion model trained on small instances. Specifically, we adapt GRPO to this problem, using route length as the training signal. ResizeCO also formulates k-opt as a tree search, solved by a beam search on the GPU. In size-generalization experiments on TSP and CVRP instances with up to 10000 nodes, ResizeCO achieves a Pareto front over route quality and time that dominates learned solvers, and also outperforms other solvers at short run times, setting a new state of the art.

1 INTRODUCTION

ResizeCO adapts diffusion routing solvers trained on small instances to larger ones without labels. It combines architectural, training, and inference changes, and reports state-of-the-art short-run quality while dominating learned methods across the quality-time Pareto front.

1 INTRODUCTION

  • Large-instance supervision is costly because it requires many near-optimal solution labels, and diffusion models trained on small instances perform poorly on larger ones.The authors identify these as challenges to scaling supervised training.Source: §1 · p. 1
  • ResizeCO fine-tunes a diffusion model trained on small instances with reinforcement learning on large instances, without labels.Its design addresses changes in instance statistics and the computational challenge of optimizing larger instances.Source: §1 · p. 1
  • ResizeCO combines a size-generalizing Graph Transformer, GRPO fine-tuning, and GPU-parallel beam k-opt search.The search is designed to improve inference quality.Source: §1 · pp. 1–2
  • ResizeCO achieves state-of-the-art quality at short run times in several size-generalization setups and dominates learning-based methods across the full Pareto front.The evaluation covers TSP and CVRP and compares machine-learning and fast non-learned approaches.Source: §1 · p. 2
  • The paper presents ResizeCO as the first diffusion solver adapted from small to large instances without labels and the first diffusion solver trained for CVRP instances of size 10000.It also identifies exact route probabilities for weighting GRPO trajectories and GPU beam search over a k-opt tree as contributions.Source: §1 · p. 2

2 RELATED WORK

Prior routing solvers address larger instances through size-robust architectures, training across sizes, or decomposition, while label-free target-size fine-tuning has distinct precedents and limitations. ResizeCO combines target-size fine-tuning with a GPU beam search over Lin-Kernighan chains.

Size Generalization in Neural Routing Solvers

Label-Free Training at the Target Size

  • Existing label-free solvers train from scratch or use pseudo-labels, while CADO fine-tunes only at labeled sizes and EAS fine-tunes separately per test instance; ResizeCO fine-tunes before testing at the target size.The approach uses GRPO with route length as its reward.Source: §2 · p. 2

Size-Generalizing Architectures

  • Graph Transformers combine graph structure with attention for global and local views, and the authors adapt the architecture of Chen et al. (2022).The passage contrasts them with message-passing networks and transformers that provide only a local or global view, respectively.Source: §2 · p. 2

k-opt Local Search

  • ResizeCO runs Lin-Kernighan chains as a GPU beam search, retaining the best chains at each step across many routes rather than growing one chain at a time.Prior GPU k-opt approaches searched moves for one route in parallel, up to k=3 or k=6.Source: §2 · p. 2

3 PRELIMINARIES AND PROBLEM DEFINITION

The paper models routing as optimization over feasible edge selections on weighted graphs, with TSP and CVRP imposing different route constraints. It also introduces the masked-diffusion pipeline and GRPO background used by the solver.

Routing as Edge Selection

  • A routing instance is an undirected weighted graph with symmetric edge lengths, and a solution is a binary adjacency matrix whose selected edges define the route length to minimize over feasible solutions.The route length is defined as length(x) = 1/2 d^T x.Source: §3 · pp. 2–3

TSP and CVRP

  • TSP solutions are Hamiltonian cycles, whereas CVRP routes return to a depot and partition customers into vehicle routes whose demands do not exceed capacity.Each customer belongs to exactly one depot-to-depot sub-route.Source: §3 · p. 3

Masked Diffusion for CO

  • At inference, a masked diffusion denoiser predicts an edge heatmap, a decoder iteratively selects edges, and 2-opt improves the decoded route.MaskCO can also re-mask part of the route, rebuild it, and retain the best solution across correction cycles.Source: §3 · p. 3
  • Supervised diffusion training independently masks optimal-route edges and trains on the masked entries.Masking an edge also masks both symmetric adjacency entries.Source: §3 · p. 3

Group Relative Policy Optimization

  • GRPO uses the sampled group’s mean as a baseline and standardizes rewards into advantages; it increases probabilities for positive-advantage actions, decreases them for negative ones, and regularizes toward a frozen reference policy.For a T-step generator, it treats generation as a Markov decision process.Source: §3 · p. 3

4 OUR METHOD: RESIZECO

ResizeCO combines a locally sensitive Graph Transformer, label-free reinforcement learning at the target size, and parallel GPU inference to address size generalization and computational scalability.

4 OUR METHOD: RESIZECO

  • ResizeCO combines a scalable architecture, target-size training from route lengths without labels, and fast parallel inference to address size generalization and larger search spaces.The paper presents these as three parts of one pipeline.Source: §4 · p. 3, Figure 1 · p. 4

4.1 THE GRAPH TRANSFORMER ENCODER: LOCAL STRUCTURE IN EVERY LAYER

  • Graph Transformer attention uses local-structure features in queries and keys while retaining plain node states for values; only the Graph Transformer preserves neighbor preference when tested on TSP-1000.The encoder recomputes the extractor at every layer, while the decoder remains unchanged.Source: §4.1 · pp. 4–5, Figure 2 · p. 4

4.2 LABEL-FREE GRPO AT THE TARGET SIZE

  • Label-free GRPO adapts the small-instance diffusion model at the target size using polished route length as reward and an exact route-probability model from node-walk decoding.The decoder samples successive nodes from the heatmap; sequentially conditioned edge decisions yield an exact Markovian route probability.Source: §4.2 · p. 5

4.3 ACCELERATING INFERENCE USING A GPU BEAM k-OPT SEARCH

  • ResizeCO formulates k-opt as a decision tree and uses GPU beam search to advance the top M branches in parallel, recording feasible moves through depth k.The search applies recorded moves together when they do not overlap on the route.Source: §4.3 · p. 6

5 EXPERIMENTS

Experiments test transfer from smaller to larger TSP and CVRP instances, including real-world benchmarks. ResizeCO achieves strong quality at short run times, and removing any component increases the gap.

5 EXPERIMENTS

  • The evaluation tests models trained at one size on larger instances, using synthetic and real-world benchmarks and comparing classical, learned, and diffusion-based solver families.ResizeCO varies parallel samples as its compute-budget knob, with one unmasking step and one correction cycle.Source: §5 · pp. 6–7

5.1 CVRP RESULTS

  • Across all three CVRP transfers, ResizeCO has the lowest learned-solver gap at similar or lower time and leads the classical solver at short times; on CVRP-1000→10000, its routes beat HGS references.Figure 3 plots gap against run time across three source-to-target pairs.Source: §5.1 · p. 7, Figure 3 · p. 8
  • On CVRPLIB, ResizeCO has the lowest learned-solver gap in all three real-world groups at comparable run time.The instances differ in geometry from the synthetic training instances.Source: §5.1 · p. 8, Table 2 · p. 8

5.2 TSP RESULTS

  • At comparable times, ResizeCO has the lowest gap of every learned solver in all three TSP transfers; on TSP-500→1000, it beats the fastest LKH-3 setting at shorter run time.Figure 4 plots gap against total run time; TSP-10000 runs are limited to under five minutes, which LKH-3 exceeds.Source: Figure 4 · p. 8, §5.2 · p. 8
  • On TSPLIB, ResizeCO has the lowest learned-solver gap in the first two groups; in the last group, DIFUSCO has lower gap at 13× longer run time.Table 4 reports mean gap and run time for the real-world groups.Source: §5.2 · p. 9, Table 4 · p. 9

5.3 ABLATION STUDIES

  • Removing any ResizeCO component increases the gap in the size-generalization ablation.Table 5 removes one component per row.Source: §5.3 · p. 9, Table 5 · p. 9

6 CONCLUSION

ResizeCO adapts a small-instance-trained diffusion model to large routing instances using label-free reinforcement learning. The paper reports strong short-run-time results on TSP and CVRP up to 10000 nodes, while its appendix documents datasets, implementation, baselines, further results, and the training-loss derivation.

6 CONCLUSION

  • ResizeCO combines small-instance diffusion training with label-free RL on large instances, and reaches the lowest gap among learned solvers at comparable run time on TSP and CVRP up to 10000 nodes.The conclusion also reports shorter CVRP routes than HGS references from CVRP-1000 to CVRP-10000 and lowest learned-solver gap in five of six TSPLIB/CVRPLIB groups.Source: §6 · p. 9

APPENDIX

  • The appendix covers datasets, implementation, correction-cycle baseline configurations, additional results and ablations, and the training-loss derivation.Source: APPENDIX · p. 13

A DATASETS

The datasets span synthetic TSP and CVRP instances and real-world TSPLIB and CVRPLIB benchmarks, with tests covering sizes 100, 500, 1000, and 10000. Training at size 10000 uses instances without labels in the RL stage, and the CVRP reference solutions are heuristic rather than optimal.

A DATASETS

  • Synthetic training and test sets cover sizes 100, 500, 1000, and 10000; only the supervised stage uses training solutions, while RL also uses unlabeled size-10000 instances.The CVRP-10000 test set is generated from the same distribution as the other CVRP data.Source: A DATASETS · p. 13, Table A.1 · p. 13
  • Test references are optimal Concorde routes for TSP below size 10000 and long LKH-3 runs at size 10000; CVRP references come from HGS, so CVRP gap is not distance from the optimum.HGS runs for four hours on CVRP-10000.Source: A DATASETS · p. 13
  • TSPLIB and CVRPLIB contribute real-world groups matched to sizes 500, 1000, and 10000; size-100 models run on the two smaller groups and source-1000 models on size 10000 without further training.The groups contain 24 TSP and 22 CVRP instances in total.Source: A DATASETS · p. 13

B.1 ARCHITECTURE

The appendices describe ResizeCO’s architecture, training and inference settings, and a GPU-parallel beam search for k-opt. They also specify the CVRP adaptations and hardware used.

B.1 ARCHITECTURE

  • A two-layer message-passing structure extractor runs inside each denoiser encoder layer on a k-nearest-neighbor graph, while the decoder remains unchanged.Zero-initialized Wout makes the extractor start as the identity; the neighborhood size k is the only architectural setting changed with test size.Source: §B.1 · pp. 13–14

B.2 SUPERVISED TRAINING

  • The supervised stage trains the denoiser to complete partial solutions on the labeled training sets.Models warm-start from the previous size: TSP-500 from TSP-100 and TSP-1000 from TSP-500.Source: §B.2 · p. 14

B.3 LABEL-FREE GRPO TRAINING

  • RL batch size and group size use the largest settings that fit GPU memory, while 2-opt reward steps are limited to preserve advantage signal.At size 10000, CVRP uses fewer 2-opt steps; TSP keeps its step count but restricts the pass to each node’s 20 nearest neighbors.Source: §B.3 · p. 14

B.4 INFERENCE

  • At inference, ResizeCO builds S routes in parallel with node-walk decoding and returns the shortest after GPU beam k-opt local search.Each run uses one denoiser forward pass with one unmasking step and one correction cycle; CVRP decoding respects vehicle capacity and returns to the depot as needed.Source: §B.4 · pp. 14–15

B.5 THE GPU BEAM k-OPT SEARCH

  • The GPU beam search advances promising k-opt branches together, closes branches at each level, and repeats sweeps until no route improves.Candidate sets reduce root branching from Θ(N^2) to Θ(N); the beam keeps high-gain branches and narrows with depth. Each sweep also searches double bridges and applies non-overlapping kept moves together.Source: §B.5 · p. 16
  • For CVRP, moves are scored on route length and overload, and can transfer customers or segments between sub-routes.The penalized objective allows a search to pass through a briefly overloaded route; because beam search is expensive, it runs on the best route after a short 2-opt ranking pass.Source: §B.5 · pp. 16–18

B.6 HARDWARE

  • Evaluations used a single NVIDIA L40S GPU, while runs targeting size 10000 trained on a single NVIDIA B200 or H200 GPU.Classical solvers ran single-threaded on one CPU core.Source: §B.6 · p. 18

C CONFIGURATIONS OF MASKCO AND GENSCO

The appendices specify baseline configurations, compare label-based and label-free large-target training costs, and document the source-to-target pairs evaluated. The supplied passages describe the comparisons and table scope, but not their numeric outcomes.

C CONFIGURATIONS OF MASKCO AND GENSCO

  • MaskCO and GenSCO use released per-size decoding settings with specified exceptions, while MaskCO’s size-10000 rows extend its size-1000 settings.The appendix also describes MaskCO self-training from its released source-size model, using the best model by gap each round; the gap flattens within four rounds.Source: C CONFIGURATIONS OF MASKCO AND GENSCO · p. 18, Table C.1 · p. 18

D.1 THE COST OF LABELS AGAINST LABEL-FREE GRPO

  • The label-cost comparison measures TSP-10000 and CVRP-10000 gap against total device hours for supervised target-size training versus label-free GRPO.Total device hours include CPU time for computing LKH-3 or HGS labels plus GPU training time; both approaches start from the same size-1000 supervised model.Source: §D.1 · p. 18, Figure D.1 · p. 19, Figure D.2 · p. 19

D.2 ALL SOURCE-TO-TARGET PAIRS

  • The all-pairs experiments report six source-to-target pairs per problem, grouped by source size, with ResizeCO results across six compute budgets.ResizeCO rows vary parallel samples from S = 1 to S = 32 and use one correction cycle and one unmasking step.Source: §D.2 · p. 19, Table D.1 · p. 20, Table D.2 · p. 21

D.3 COMPONENT ABLATION FROM TSP-100 TO TSP-1000

The ablation removes one ResizeCO component at a time across two source-to-target pairs, with a third TSP pair reported separately. Removing any component increases the gap, most for label-free GRPO.

D.3 COMPONENT ABLATION FROM TSP-100 TO TSP-1000

  • Removing any component increases the gap, with removal of label-free GRPO causing the largest rise, from 0.813% to 3.23%.Table 5 covers two source-to-target pairs; Table D.5 repeats the ablation for TSP-100 → TSP-1000.Source: §D.3 · p. 22, Table D.5 · p. 22

D.4 WHY DOES NODE-WALK DECODING HELP TRAINING?

The decoder used for GRPO rollouts affects whether training improves the model. Node-walk decoding scored by its exact likelihood improves steadily, whereas greedy decoding does not learn even when scored by its own exact probability.

D.4 WHY DOES NODE-WALK DECODING HELP TRAINING?

  • Node-walk decoding with its exact likelihood improves steadily, while greedy decoding scored by its own exact probability stays flat and greedy decoding scored by node-walk likelihood rises above the supervised starting gap.The authors attribute the greedy/node-walk mismatch to the likelihood never sampling routes produced by random edge ranking, which biases the gradient; using the greedy decoder’s own probability removes that bias but does not make the model learn.Source: §D.4 · pp. 22–23, Figure D.3 · p. 23

E DERIVATION OF THE TRAINING LOSS

The appendix derives the training loss by adapting the standard GRPO objective for fresh, current-policy rollouts and a heatmap-wide KL penalty.

E DERIVATION OF THE TRAINING LOSS

  • Fresh rollouts from the current policy make the policy ratios one, disable clipping, and reduce the GRPO term to an advantage-weighted log-probability objective.Summed over route decisions, the loss is the route advantage times the route log-probability.Source: E DERIVATION OF THE TRAINING LOSS · p. 23
  • The KL penalty covers the whole edge heatmap because parameter updates change even rows no rollout visited, and inference reads those rows too.The per-state KL is replaced by a row average over the heatmaps in the rollout.Source: E DERIVATION OF THE TRAINING LOSS · pp. 23–24
  • The final loss averages route losses over the group and adds the KL penalty.Source: E DERIVATION OF THE TRAINING LOSS · p. 24

Related papers

Loading 2610.17192v1…