Efficient Decoder Scaling Strategy for Neural Routing Solvers

Qing Luo; Fu Luo; Ke Li; Zhenkun Wang

cs.LGFeb 28, 2026

Efficient Decoder Scaling Strategy for Neural Routing Solvers

Authors: Qing Luo, Fu Luo, Ke Li, Zhenkun Wang

Organizations: Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China. · Department of Computer Science, City University of Hong Kong, Hong Kong SAR, China.

Abstract

Construction-based neural routing solvers, typically composed of an encoder and a decoder, have emerged as a promising approach for solving vehicle routing problems. While recent studies suggest that shifting parameters from the encoder to the decoder enhances performance, most works restrict the decoder size to 1-3M parameters, leaving the effects of scaling largely unexplored. To address this gap, we conduct a systematic study comparing two distinct strategies: scaling depth versus scaling width. We synthesize these strategies to construct a suite of 12 model configurations, spanning a parameter range from 1M to ~150M, and extensively evaluate their scaling behaviors across three critical dimensions: parameter efficiency, data efficiency, and compute efficiency. Our empirical results reveal that parameter count is insufficient to accurately predict the model performance, highlighting the critical and distinct roles of model depth (layer count) and width (embedding dimension). Crucially, we demonstrate that scaling depth yields superior performance gains to scaling width. Based on these findings, we provide and experimentally validate a set of design principles for the efficient allocation of parameters and compute resources to enhance the model performance.

Figures & tables

Figure 1: Decoder Parameters Count vs. Optimality Gap. The results demonstrate that simply increasing model size does not guarantee performance gains. The green circles highlight depth-prioritized models (constructed by prioritizing depth scaling over width), which dominate at least one larger model.

Depth	Width	Head Num	QKV Dim	FFN Dim	Parameters
	128	8	16	512	1.32M
6	256	16	16	1024	5.26M
	512	16	32	2048	21.00M
	128	8	16	512	2.60M
12	256	16	16	1024	10.38M
	512	16	32	2048	41.46M

Table 1: Configuration of neural models with different depths and widths. “Depth” represents the number of layers in the decoder, and “Width” represents the dimension of the node embeddings.

Figure 2: Scaling Law Analysis for Decoder-only Models. (a) Global Fit: Fitting a single power law (blue dashed line) to all models results in a poor fit (

R^{2}=0.794

) with a high average prediction error of

34.39\%

, indicating that parameter count alone is insufficient to predict performance. (b) Scaling Width vs. (c) Scaling Depth: We decouple the scaling behaviors by fixing one dimension. Comparing the scaling exponents (

\alpha_{n}

), we observe that scaling depth (c) yields significantly steeper slopes (

\alpha_{n}\approx 0.98\text{--}1.05

) compared to scaling width (b) (

\alpha_{n}\approx 0.24\text{--}0.40

). This quantitatively demonstrates that Depth-Prioritized Models exhibit a much faster rate of performance improvement than width-prioritized ones as parameters increase.

Figure 3: Data Efficiency Analysis. The log-log plot compares the optimality gap against training data size across different architectures. Prioritizing depth yields superior data efficiency: deeper models (e.g.,

D=42

) exhibit steeper scaling exponents (up to

0.71

) compared to wider models (e.g.,

W=512

, exponent

0.55

Figure 4: Compute Efficiency Analysis. Comparison of optimality gap vs. inference compute budget per instance (GFLOPs) for (a) width scaling and (b) depth scaling. Depth scaling demonstrates superior efficiency, achieving a significantly higher scaling exponent (

\alpha=1.71

for

D=42

) compared to width scaling (

\alpha=1.34

for

W=512

Figure 5: Visualization of the performance gap against model parameters (

N

) in log scale for varying depth-to-width ratios (

A

). The consistent drop in the gap as lines shift from cyan (low

A

) to pink (high

A

) illustrates that prioritizing deeper, narrower architectures effectively reduces the optimality gap under constrained parameter budgets.

Model	Parameters	TSP100	TSP200	TSP500	TSP1000
$D=6,W=128$	1.32M	0.464%	0.669%	1.559%	2.172%
$D=24,W=64$	1.29M	0.297%	0.449%	0.857%	1.259%
$D=96,W=32$	1.30M	0.184%	0.307%	0.678%	0.991%

Table 2: Validation of Design Principle: Performance comparison of model variants with varying depth-to-width ratios under a fixed parameter budget (

\approx 1.3

Model (Parameters)	Training Data Size	TSP100	TSP1000
$D=6,W=128$ (1.32M)	0.1M	1.715%	5.678%
$D=6,W=512$ (21.0M)	0.1M	0.949%	3.871%
$D=42,W=128$ (9.02M)	0.1M	0.547%	2.572%

Table 3: Validation of Data Efficiency Policy: Performance comparison of depth versus width scaling under a limited training budget (

10^{5}

samples).

Figure 6: Scaling laws of inference performance across different model configurations. The plot depicts the relationship between optimality gap and inference time (minutes) on a log-log scale. Dashed lines indicate best-fit curves using a shifted power-law model (

y=\alpha_{t}t^{-\beta_{t}}+\gamma

), where

t

denotes inference time. Here,

\alpha_{t}

serves as the scaling coefficient, and

\gamma

represents the asymptotic lower bound of the gap as

t\to\infty

. The parameter

\beta_{t}

denotes the decay exponent, indicating the magnitude of performance gain for every doubling of the inference budget.

(Depth,Width,Params)	Limited Budget			Sufficient Budget ( $>$ 1h)
(Depth,Width,Params)	bs	Gap (%)	Time	bs	Gap (%)	Time
(6, 128, 1.3M)	32	0.0127	12m	512	0.0059	2.75h
(6, 512, 21.0M)	8	0.0138	12m	128	0.0007	3.24h
(24, 128, 5.2M)	10	0.0044	12m	128	0.0002	2.60h
(42, 128, 9.0M)	6	0.0056	12m	64	0.0001	2.29h

Table 4: Performance comparison under different inference budgets. We report the Optimality Gap (%) and total inference time. ‘bs’ denotes Beam Search.

	TSP 100		TSP 1000
	Gap	Time	Gap	Time
LEHD greedy	0.577%	0.29m	3.168%	1.17m
LEHD bs16	0.038%	4.4m	1.874%	22m
BQ greedy	0.348%	1.18m	2.274%	1.18m
BQ bs16	0.015%	17.6m	1.35%	18m
SIGD greedy	0.851%	2.4m	2.791%	2.71m

Table 5: Performance of recent advanced NCO constructive methods on TSP instances with different problem sizes and data distribution. Ground truth solutions are obtained via LKH3 ( Helsgaun, 2017 ) for uniform datasets. ‘bs’ denotes Beam Search.

TSPLib	Baselines			Ours (Depth,Width)
TSPLib	BQ	SIGD	LEHD	(6,128)	(6,512)	(42,128)	(42,512)
$<500$	2.828%	2.176%	2.287%	2.582%	1.553%	1.364%	0.811%
$>500$	10.288%	10.812%	9.720%	7.249%	4.127%	3.631%	1.942%
All	5.812%	5.631%	5.260%	5.235%	3.108%	2.346%	1.288%

Table 6: Performance comparison (Gap %) between baselines and our models in TSPLib. Ground truth solutions are obtained from TSPLib ( Reinelt, 1991 ) .

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Convergence: w/ vs. w/o Gated Attention

	TSP100	TSP200	TSP500	TSP1000
Ours greedy (Depth=42,Width=128) w/ gated attention	0.070%	0.178%	0.477%	0.869%
Ours greedy (Depth=42,Width=128) w/o gated attention	0.105%	0.245%	0.614%	1.023%

Appendix

Table 7: Performance Comparison: w/ Gated Attention and w/o Gated Attention.

Figure 8: Convergence: w/ vs. w/o Rezero Normalization.

Setting	Model	TSP100	TSP200	TSP500	TSP1000
w/o $\log(n)$	Ours ( $D=6,W=128$ )	0.464%	0.644%	1.645%	4.050%
	Ours ( $D=6,W=256$ )	0.190%	0.341%	0.880%	2.239%
	Ours ( $D=42,W=128$ )	0.070%	0.184%	0.532%	1.594%
w/ $\log(n)$	Ours ( $D=6,W=128$ )	0.464%	0.669%	1.559%	2.172%
	Ours ( $D=6,W=256$ )	0.264%	0.498%	0.969%	1.504%
	Ours ( $D=42,W=128$ )	0.070%	0.178%	0.477%	0.869%

Appendix

Table 8: Performance Comparison: w/ and w/o

\log(n)

parameters	values
Batch size	1024
Total training steps	60,000
optimizer	AdamW
Weight decay	0.01
Learning rate	$1.25\times 10^{-4}$
Scheduler	Exponential

Appendix

Table 9: Training hyperparameters.

Configuration	Device	Configuration	Device
$D=6,W=128$	4090 $\times 2$	$D=24,W=128$	4090 $\times 2$
$D=6,W=256$	4090 $\times 2$	$D=24,W=256$	4090 $\times 8$
$D=6,W=512$	4090 $\times 8$	$D=24,W=512$	4090 $\times 8$
$D=12,W=128$	4090 $\times 2$	$D=42,W=128$	4090 $\times 4$
$D=12,W=256$	4090 $\times 2$	$D=42,W=256$	4090 $\times 8$
$D=12,W=512$	4090 $\times 4$	$D=42,W=512$	4090 $\times 8$

Appendix

Table 10: Hardware Specifications.

Figure 9: Convergence comparison of the model (

\text{Depth}=12,\text{Width}=128

) trained on datasets of varying sizes (1M vs. 10M). The model trained on 10 million training samples (orange curve) demonstrates faster convergence and achieves a lower optimality gap compared to the 1 million sample baseline.

	Training Dataset Size	TSP100	TSP200	TSP500	TSP1000
Ours greedy (Depth=12,Width=128)	1M	0.337%	0.615%	1.062%	1.606%
Ours greedy (Depth=12,Width=128)	10M	0.302%	0.461%	0.972%	1.357%

Appendix

Table 11: Performance comparison on TSP instances of varying sizes (TSP100 to TSP1000) using models trained on datasets with sizes of 1M and 10M.

		TSP 100
		Gap	Time
Uniform	LKH3	0.000%	56m
	Ours greedy (Depth=6,Width=128)	0.464%	0.34m
	Ours greedy (Depth=6,Width=256)	0.264%	0.75m
	Ours greedy (Depth=6,Width=512)	0.190%	1.7m
	Ours greedy (Depth=12,Width=128)	0.225%	0.62m

Appendix

Table 12: Performance of different configurations on TSP 100 instances.

		TSP 200		TSP 500		TSP 1000
		Gap	Time	Gap	Time	Gap	Time
Uniform	LKH3	0.000%	17m	0.000%	50m	0.000%	10h
	Ours greedy (Depth=6,Width=128)	0.669%	0.035m	1.559%	0.23m	2.172%	1.6m
	Ours greedy (Depth=6,Width=256)	0.498%	0.059m	0.969%	0.48m	1.504%	3.2m
	Ours greedy (Depth=6,Width=512)	0.375%	0.1m	0.856%	0.75m	1.291%	4.2m
	Ours greedy (Depth=12,Width=128)	0.550%	0.054m	0.803%	0.44m	1.357%	3.1m

Appendix

Table 13: Performance of different configurations on TSP 200, 500, and 1000 instances.

		TSP 100		TSP 200		TSP 500		TSP 1000
		Gap	Time	Gap	Time	Gap	Time	Gap	Time
Explosion	LKH3	0.000%	56m	0.000%	17m	0.000%	50m	0.000%	10h
	Ours greedy (Depth=6,Width=128)	0.496%	0.35m	0.767%	0.037m	1.905%	0.23m	3.819%	1.6m
	Ours greedy (Depth=6,Width=256)	0.301%	0.75m	0.506%	0.059m	1.143%	0.48m	2.430%	3.2m
	Ours greedy (Depth=6,Width=512)	0.222%	1.7m	0.403%	0.1m	0.974%	0.75m	2.029%	4.2m
	Ours greedy (Depth=12,Width=128)	0.245%	0.64m	0.420%	0.055m	1.044%	0.44m	1.987%	3.1m

Appendix

Table 14: Performance of different configurations on TSP instances with different problem sizes and the distribution of explosion. Ground truth solutions are obtained via LKH3 for the test dataset.

		TSP 100		TSP 200		TSP 500		TSP 1000
		Gap	Time	Gap	Time	Gap	Time	Gap	Time
Implosion	LKH3	0.000%	56m	0.000%	17m	0.000%	50m	0.000%	10h
	Ours greedy (Depth=6,Width=128)	0.895%	0.35m	1.424%	0.035m	2.909%	0.23m	3.507%	1.7m
	Ours greedy (Depth=6,Width=256)	0.529%	0.74m	0.646%	0.06m	1.660%	0.48m	2.580%	3.2m
	Ours greedy (Depth=6,Width=512)	0.436%	1.7m	0.634%	0.1m	1.494%	0.75m	2.164%	4.2m
	Ours greedy (Depth=12,Width=128)	0.491%	0.63m	0.824%	0.055m	1.725%	0.44m	2.246%	3.1m

Appendix

Table 15: Performance of different configurations on TSP instances with different problem sizes and the distribution of implosion. Ground truth solutions are obtained via LKH3 for the test dataset.

		TSP 100		TSP 200		TSP 500		TSP 1000
		Gap	Time	Gap	Time	Gap	Time	Gap	Time
Cluster	LKH3	0.000%	56m	0.000%	17m	0.000%	50m	0.000%	10h
	Ours greedy (Depth=6,Width=128)	2.742%	0.34m	2.440%	0.035m	4.018%	0.23m	6.639%	1.6m
	Ours greedy (Depth=6,Width=256)	1.253%	0.74m	1.240%	0.063m	2.345%	0.48m	4.276%	3.2m
	Ours greedy (Depth=6,Width=512)	1.377%	1.7m	1.164%	0.1m	2.002%	0.75m	3.542%	4.2m
	Ours greedy (Depth=12,Width=128)	1.134%	0.63m	1.178%	0.055m	1.943%	0.44m	3.539%	3.1m

Appendix

Table 16: Performance of different configurations on TSP instances with different problem sizes and the distribution of clusters. Ground truth solutions are obtained via LKH3 for the test dataset.

	Compute per solution	Batch size =50	Batch size =100	Batch size =1000
Ours greedy (Depth=12,Width=512)	843.2 GFLOPs	4.0m	3.4m	3.3m
Ours greedy (Depth=24,Width=256)	434.4 GFLOPs	4.4m	3.2m	2.8m

Appendix

Table 17: Inference time with different batch sizes.

	greedy	beam=2	beam=4	beam=8	beam=16	beam=32	beam=64
Ours ( $D=6,W=128$ )	0.4640%	0.2456%	0.1155%	0.0571%	0.0269%	0.0127%	0.0059%
Ours ( $D=6,W=256$ )	0.2635%	0.1397%	0.0647%	0.0289%	0.0125%	0.0008%	0.0017%
Ours ( $D=6,W=512$ )	0.1895%	0.0904%	0.0359%	0.0138%	0.0050%	0.0019%	0.0007%
Ours ( $D=12,W=128$ )	0.2253%	0.1122%	0.0512%	0.0223%	0.0088%	0.0032%	0.0010%
Ours ( $D=12,W=256$ )	0.1149%	0.0523%	0.0200%	0.0069%	0.0024%	0.0008%	0.0002%
Ours ( $D=12,W=512$ )	0.0827%	0.0354%	0.0133%	0.0044%	0.0016%	0.0005%	0.0002%

Appendix

Table 18: The inference performance of different model configurations with different beam sizes on the TSP100 (10,000 instances). When Beam = 1, beam search degenerates into greedy search.

TSP100 (1,000 instances)	Greedy	RRC 100	RRC 200	RRC 500	RRC 800	RRC 1000
Ours ( $D=6,W=128$ )	0.4228%	0.0103%	0.0068%	0.0040%	0.0030%	0.0024%
Ours ( $D=6,W=512$ )	0.1824%	0.0033%	0.0018%	0.0007%	0.0006%	0.0005%
Ours ( $D=42,W=128$ )	0.0656%	0.0015%	0.0012%	0.0004%	0.0004%	0.0004%
Ours ( $D=42,W=512$ )	0.0332%	0.0008%	0.0006%	0.0003%	0.0002%	0.0002%

Appendix

Table 19: Results on TSP100 and TSP1000 with different budgets.

Figure 10: 2D-PCA visualization for features of available nodes (a): Background nodes exhibit a dispersed distribution with multiple isolated outliers. (b): The background distribution remains scattered. (c): Background nodes form a compact cluster, with the optimal node clearly separated from the background.

Panel of Figure 11 — Figure 11: Cosine similarity for all available node feature pairs. Node indices are sorted according to the optimal solution. (a) : has distinct green blocks, indicating the presence of multiple clusters. (b) : The green area has noticeably become lighter, but has several distinct green lines, indicating the presence of a few outliers. (c) : The single dark line is clearly distinguishable from the yellow block.

Figure 12: The success rate when the optimal next node is located at different ranks of nearest neighbors.

Model (Parameters)	TSP100	TSP200	TSP500	TSP1000
LEHD $(D=6,W=128)$ (1.43M)	0.577%	0.859%	1.560%	3.168%
LEHD $(D=24,W=64)$ (1.25M)	0.419%	0.597%	1.025%	1.844%

Appendix

Table 20: Performance comparison of LEHD before and after modification on TSP100, TSP200, TSP500, and TSP1000.

Neural Combinatorial Optimization

Neural combinatorial optimization uses neural networks to find high-quality solutions to discrete problems such as routing, scheduling, and graph partitioning.

See all 138 papers

Survey on Neural Routing Solvers
Feb 25, 2026Yunpeng Ba, Xi Lin, Changliang Zhou +7Neural Combinatorial Optimization Vehicle Routing
Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China. · the School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China. · the Institute of Big Data Science and Industry, Shanxi University, Taiyuan, China. +1
Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver
May 11, 2026Canhong Yu, Changliang Zhou, Rongsheng Chen +2Neural Network Optimization Combinatorial Optimization
College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, China · School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China · Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University of Science and Technology, Shenzhen, China +1
Understanding Decision-Making Mechanisms in Neural Routing Solvers
Sep 28, 2026Fatemeh Askari, Mazdak Teymourian, Mohammad Izadi +1Mechanistic Interpretability Neural Network Interpretability
Department of Computer EngineeringSharif University of Technology

Feb 25, 2026J/K move · Enter open · S save

Survey on Neural Routing Solvers

Yunpeng Ba, Xi Lin, Changliang Zhou, Ruihao Zheng+6

Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China. · the School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China. · the Institute of Big Data Science and Industry, Shanxi University, Taiyuan, China.+1

Neural Combinatorial Optimization Vehicle Routing Automated Heuristic Design

Open paper AskPDF arXiv

Neural routing solvers (NRSs) that leverage deep learning to tackle vehicle routing problems have demonstrated notable potential for practical applications. By learning implicit heuristic rules from data, NRSs replace the handcrafted counterparts in classic heuristic frameworks, thereby reducing reliance on costly manual design and trial-and-error adjustments. This survey makes two main contributions: (1) The heuristic nature of NRSs is highlighted, and existing NRSs are reviewed from the perspective of heuristics. A hierarchical taxonomy based on heuristic principles is further introduced. (2) A generalization-focused evaluation pipeline is proposed to address limitations of the conventional pipeline. Comparative benchmarking of representative NRSs across both pipelines uncovers a series of previously unreported gaps in current research.

Abstract

Neural Combinatorial Optimization

Explore similar work

Survey on Neural Routing Solvers

Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver

Understanding Decision-Making Mechanisms in Neural Routing Solvers