Size Generalization for Diffusion Routing Solvers

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

cs.AIOct 12, 2026

Size Generalization for Diffusion Routing Solvers

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

Organizations: Bar-Ilan University · NVIDIA

Abstract

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.

Figures & tables

Figure 1: The three stages of ResizeCO. Yellow marks our novel contributions. (A) Supervised training. A masked-diffusion model is trained using small labeled instances with a Graph Transformer encoder. (B) RL training. Label-free GRPO training on larger instances. A node-walk decoder samples

G

routes from the heatmap. Each route is denoted

\mathrm{route}_{g}

, and their lengths alone determine the advantage. (C) Inference on large instances. Multiple correction cycles are executed. Each cycle runs

K

unmasking steps to build an edge heatmap and decodes the heatmap into a route with the node-walk decoder. The route is then “polished” with our GPU beam

k

-opt search. Before the next cycle, the route is partly re-masked.

Figure 2: Encoder attention, averaged over all layers and normalized per row. (a) One query node (star) at TSP-1000. (b) Mean attention by distance to the query node. Shaded bands denote std over query nodes.

Classical solvers
	CVRP-100 $\rightarrow$ CVRP-500			CVRP-500 $\rightarrow$ CVRP-1000			CVRP-1000 $\rightarrow$ CVRP-10000
Method	Obj	Gap	Time	Obj	Gap	Time	Obj	Gap	Time
HGS (reference) ( Vidal, 2022 )	62.15	0.000%	55 h	121.07	0.000%	197 h	1120.23	0.000%	512 h
HGS ( Vidal, 2022 )	63.99	2.96%	52 s	124.02	2.44%	2.4 m	1129.62	0.846%	2.2 h
Supervised learning
BQ-NCO (G) ( Drakulic et al., 2023 )	64.39	3.67%	26 s	-	-	-	-	-	-

Table 1: CVRP results. Dashes indicate a setting we could not evaluate. An asterisk (*) indicates a number quoted from its paper at a different capacity convention, not comparable to the other rows.

S

counts parallel samples and

T

total model forward passes. Bold font marks the best model at a comparable run time.

Figure 3: CVRP solution quality (gap) against total run time for three source-to-target pairs. Each line varies the compute budget of one method. Our approach ResizeCO in green achieves superior quality in short durations. From CVRP-1000 to CVRP-10000, ResizeCO’s routes are shorter than the HGS reference solutions (negative gap).

Figure 4: TSP solution quality (gap) against total run time for three source-to-target pairs. Each line varies the compute budget of one method. Our approach ResizeCO in green achieves superior quality in short durations. We limit runs on TSP-10000 to less than 5 minutes, which LKH-3 exceeds. Error bars correspond to 95% confidence intervals.

Classical solvers
	TSP-100 $\rightarrow$ TSP-500			TSP-500 $\rightarrow$ TSP-1000			TSP-1000 $\rightarrow$ TSP-10000
Method	Obj	Gap	Time	Obj	Gap	Time	Obj	Gap	Time
Concorde / LKH-3 (reference)	16.55	0.000%	37.66 m	23.12	0.000%	6.65 h	71.83	0.000%	8.8 h
LKH-3 (trials=32) ( Helsgaun, 2017 )	16.55	0.026%	22 s	23.13	0.036%	56 s	71.81	$-$ 0.023%	7.7 m
LKH-3 (trials=1) ( Helsgaun, 2017 )	16.57	0.118%	8.6 s	23.15	0.139%	23 s	71.89	0.085%	5.6 m
Supervised learning

Table 3: TSP size-generalization results. Bold font marks the best model at a comparable run time. “Time Limit” denotes cases that did not finish within 4 hours. A dash indicates a setting we did not evaluate.

C

counts correction cycles and

S

parallel samples. Inference budgets (

T

T_{s}

T_{g}

) follow each paper’s own notation. Larger sample counts lie on the curves of Figure 4 .

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Problem	Size	Instances	Reference	Instances	Labels
		Test		Training
TSP	100	1280	Concorde	1.26 M	LKH-3
TSP	500	128	Concorde	128 k	LKH-3
TSP	1000	128	Concorde	64 k	LKH-3
TSP	10000	16	LKH-3	6.4 k	-
CVRP	100	1280	HGS	1.54 M	HGS

Appendix

Table A.1: Test and training sets. A dash marks a training set without labels.

Parameter	TSP	CVRP
Input features	$2$ -D coordinates	$2$ -D coordinates $+$ demand
Encoder layers	16	16
Decoder layers	6	6
Embedding dimension	256	512
Attention heads	8	8
Structure-extractor GNN layers	2	2

Appendix

Table B.1: Architecture parameters.

Parameter	TSP	CVRP
Batch size	256 (100), 128 (500), 16 (1000)	512 (100), 64 (500), 16 (1000)
Training steps	500000	225000 (100), 150000 (500, 1000)
Warm start	from scratch (100), previous (500, 1000)	from scratch

Appendix

Table B.2: Supervised training parameters. Values in parentheses are training sizes.

Parameter	TSP	CVRP
Group size $G$	8, 16 (500 to 1000), 64 (to 10000)	8, 64 (to 10000)
Unmasking steps $K$	1	1
Sampling temperature	1.0	1.0
KL coefficient $\beta$	0.005, 0 (to 10000)	0.005, 0 (to 10000)
Batch size	64 (500), 24 (1000), 96 (500 to 1000), 4 (to 10000)	16 (500), 4 (1000), 1 (to 10000)
Training steps	200000, 150000 (500 to 1000), 30000 (to 10000)	200000, 30000 (to 10000)

Appendix

Table B.3: RL fine-tuning parameters. Values in parentheses are the target size or the source and target sizes of the run.

Parameter	TSP	CVRP
Decoder	node-walk	node-walk
Unmasking steps $K$	1	1
Correction cycles $C$	1	1
Batch size	16 (500, 1000), 1 (10000)	16 (500), 8 (1000), 1 (10000)

Appendix

Table B.4: ResizeCO inference parameters. Values in parentheses are test sizes.

Figure B.1: An example sweep of the GPU beam

k

-opt search on a 12-node instance. Every panel draws the same nodes and differs only in its edges. Each level extends every branch of the beam and keeps the branches with the largest gains, and the beam narrows with depth. Each level also closes every branch back to the start node, and a closing that splits the route into two loops is discarded. The sweep applies the kept closures that do not overlap on the route, here only the one with the largest gain. Sweeps repeat until no route improves.

Parameter	TSP	CVRP
Candidate set size	15	20
Largest $k$ of a $k$ -opt move (tree depth)	5	5
Beam width $M$	131072	32768
Beam width-shrink factor $f$	4	4
Closures kept per sweep	256	128
2-opt steps before the beam $k$ -opt search	0	500

Appendix

Table B.5: GPU beam

k

-opt search parameters.

Settings at test size 10000
Parameter	TSP	CVRP
Correction cycles $C$	1, 10	1, 10
2-opt moves per cycle	500 (500), 1000 (1000, 10000)	6000
Top-k edge slice	$2\times 10^{6}$	$10^{6}$
Batch size	1	1

Appendix

Table C.1: Correction-cycle baseline settings. Values in parentheses are test sizes.

Figure D.1: Gap on TSP-10000 against total device hours, the CPU hours of computing the LKH-3 labels plus the GPU hours of training. Every run starts from the same supervised model trained at size 1000. The green line is the label-free GRPO training of ResizeCO, and each red line is supervised training with a fixed number of labels.

Figure D.2: Gap on CVRP-10000 against total device hours, the CPU hours of computing the HGS labels plus the GPU hours of training. Every run starts from the same supervised model trained at size 1000. The green line is the label-free GRPO training of ResizeCO, and each red line is supervised training with a fixed number of labels.

Classical solvers
	CVRP-100 $\rightarrow$ CVRP-500			CVRP-100 $\rightarrow$ CVRP-1000			CVRP-100 $\rightarrow$ CVRP-10000
Method	Obj	Gap	Time	Obj	Gap	Time	Obj	Gap	Time
HGS (reference) ( Vidal, 2022 )	62.15	0.000%	55 h	121.07	0.000%	197 h	1120.23	0.000%	512 h
HGS ( Vidal, 2022 )	63.99	2.96%	52 s	124.02	2.44%	2.4 m	1129.62	0.846%	2.2 h
Supervised learning
BQ-NCO (G) ( Drakulic et al., 2023 )	64.39	3.67%	26 s	125.19	3.53%	36 s	1221.13	9.12%	1.3 h

Appendix

Table D.1: Size-generalization CVRP results from the models trained at size 100. Conventions follow Table 1 .

Classical solvers
	TSP-100 $\rightarrow$ TSP-500			TSP-100 $\rightarrow$ TSP-1000			TSP-100 $\rightarrow$ TSP-10000
Method	Obj	Gap	Time	Obj	Gap	Time	Obj	Gap	Time
Concorde / LKH-3 (reference)	16.55	0.000%	37.66 m	23.12	0.000%	6.65 h	71.83	0.000%	8.8 h
LKH-3 (trials=32) ( Helsgaun, 2017 )	16.55	0.026%	22 s	23.13	0.036%	56 s	71.81	$-$ 0.023%	7.7 m
LKH-3 (trials=1) ( Helsgaun, 2017 )	16.57	0.118%	8.6 s	23.15	0.139%	23 s	71.89	0.085%	5.6 m
Supervised learning

Appendix

Table D.2: Size-generalization TSP results from the models trained at size 100. Conventions follow Table 3 .

Classical solvers
	CVRP-500 $\rightarrow$ CVRP-1000			CVRP-1000 $\rightarrow$ CVRP-10000			CVRP-500 $\rightarrow$ CVRP-10000
Method	Obj	Gap	Time	Obj	Gap	Time	Obj	Gap	Time
HGS (reference) ( Vidal, 2022 )	121.07	0.000%	197 h	1120.23	0.000%	512 h	1120.23	0.000%	512 h
HGS ( Vidal, 2022 )	124.02	2.44%	2.4 m	1129.62	0.846%	2.2 h	1129.62	0.846%	2.2 h
Supervised learning
BQ-NCO (G) ( Drakulic et al., 2023 )	-	-	-	-	-	-	-	-	-

Appendix

Table D.3: Size-generalization CVRP results from the models trained at sizes 500 and 1000. Conventions follow Table 1 .

Classical solvers
	TSP-500 $\rightarrow$ TSP-1000			TSP-1000 $\rightarrow$ TSP-10000			TSP-500 $\rightarrow$ TSP-10000
Method	Obj	Gap	Time	Obj	Gap	Time	Obj	Gap	Time
Concorde / LKH-3 (reference)	23.12	0.000%	6.65 h	71.83	0.000%	8.8 h	71.83	0.000%	8.8 h
LKH-3 (trials=32) ( Helsgaun, 2017 )	23.13	0.036%	56 s	71.81	$-$ 0.023%	7.7 m	71.81	$-$ 0.023%	7.7 m
LKH-3 (trials=1) ( Helsgaun, 2017 )	23.15	0.139%	23 s	71.89	0.085%	5.6 m	71.89	0.085%	5.6 m
Supervised learning

Appendix

Table D.4: Size-generalization TSP results from the models trained at sizes 500 and 1000. Conventions follow Table 3 .

	TSP-100 $\rightarrow$ TSP-1000
Method	Gap	Time
ResizeCO (full)	0.813%	7.5 s
w/o label-free GRPO	3.23%	10.7 s
w/o small-model initialization	2.67%	10.6 s
w/o Graph Transformer encoder	2.42%	8.7 s
w/o GPU beam $k$ -opt search	1.29%	7.7 s

Appendix

Table D.5: Component ablation of ResizeCO from TSP-100 to TSP-1000. Conventions follow Table 5 .

Figure D.3: Three GRPO runs from the same supervised model. The runs differ only in how routes are sampled and scored during RL training. Blue: sampling with the greedy decoder and scoring with the node-walk likelihood, the TSP-1000 gap rises above the supervised starting point. Orange: sampling with the greedy decoder and scoring with its own exact likelihood, the gap stays flat. Red: sampling and scoring with node-walk decoding (our approach), the gap falls steadily.

Explore similar work

Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization
Sep 28, 2026Jiale Zhao, Sirui Mao, Zimu Chen +5Traveling Salesperson Problem Combinatorial Optimization
School of Automation Science and Electrical Engineering, Beihang University, Beijing, China · School of Computer Science and Engineering, Beihang University, Beijing, China · School of Cyber Science and Technology, Beihang University, Beijing, China +1
COMPASS: Ordered Clustered Routing at 100K Scale
Sep 17, 2026Ido Greenberg, Hugo Linsenmaier, Piotr Sielski +4Traveling Salesperson Problem Combinatorial Optimization
NVIDIA
EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization
Oct 4, 2026Ruogu Chen, Jie HanCombinatorial Optimization Neural Combinatorial Optimization
Department of Electrical and Computer Engineering University of Alberta Edmonton, AB, Canada T6G 1H9

Sep 28, 2026J/K move · Enter open · S save

Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

Jiale Zhao, Sirui Mao, Zimu Chen, Wentao Yang+4

School of Automation Science and Electrical Engineering, Beihang University, Beijing, China · School of Computer Science and Engineering, Beihang University, Beijing, China · School of Cyber Science and Technology, Beihang University, Beijing, China+1

Traveling Salesperson Problem Combinatorial Optimization Vehicle Routing

Open paper AskPDF arXiv

Large-scale routing problems are difficult to solve efficiently as their search spaces grow rapidly with problem size. Existing approaches primarily improve the optimization procedure itself, often at increasing computational cost. We instead shift the focus to a useful initialization that can be refined into a high-quality solution with limited downstream refinement. We propose Just Initialize, a training-free and solver-agnostic initialization component for large-scale routing optimization. Just Initialize compresses a large routing instance into a compact surrogate space, optimizes its global routing structure, and recovers the resulting solution as an optimization-friendly starting point in the original space. Extensive experiments on Traveling Salesman Problems (TSPs), Capacitated Vehicle Routing Problems (CVRPs), Vehicle Routing Problems with Time Windows (VRPTWs), and Prize-Collecting Traveling Salesman Problems (PCTSPs) demonstrate that Just Initialize achieves high-quality solutions comparable to or better than state-of-the-art methods while substantially reducing computational cost across instances ranging from 1K to 100K nodes, including an average speedup of approximately 70

\times

, sub-second runtimes on 10K-node instances, and runtimes within tens of seconds on 100K-node instances.

Abstract

Explore similar work

Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

COMPASS: Ordered Clustered Routing at 100K Scale

EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization