Rethinking Light Decoder-based Solvers for Vehicle Routing Problems
Authors: Ziwei Huang
Jianan Zhou
Zhiguang Cao
Yixin XU
Venue: ICLR 2025 Poster (2025)
Keywords: Combinatorial Optimization
Vehicle Routing Problem
Generalization
Primary area: optimization

Abstract: Light decoder-based solvers have gained popularity for solving vehicle routing problems (VRPs) due to their efficiency and ease of integration with reinforcement learning algorithms. However, they often struggle with generalization to larger problem instances or different VRP variants. This paper revisits light decoder-based approaches, analyzing the implications of their reliance on static embeddings and the inherent challenges that arise.  Specifically, we demonstrate that in the light decoder paradigm, the encoder is implicitly tasked with capturing information for all potential decision scenarios during solution construction within a single set of embeddings, resulting in high information density.  Furthermore, our empirical analysis reveals that the overly simplistic decoder struggles to effectively utilize this dense information, particularly as task complexity increases, which limits generalization to out-of-distribution (OOD) settings.  Building on these insights, we show that enhancing the decoder capacity, with a simple addition of identity mapping and a feed-forward layer, can considerably alleviate the generalization issue. Experimentally, our method significantly enhances the OOD generalization of light decoder-based approaches on large-scale instances and complex VRP variants, narrowing the gap with the heavy decoder paradigm. Our code is available at: https://github.com/ziweileonhuang/reld-nco.

Published as a conference paper at ICLR 2025
RETHINKING LIGHT DECODER-BASED SOLVERS FOR VEHICLE ROUTING PROBLEMS
Ziwei Huang',, Jianan Zhou?* Zhiguang Cao't, Yixin Xu'
School of Computing and Information Systems, Singapore Management University. Singapore "Colleee of Computing and Data Science, Nanyang Technological University, Singapore zi Liweihure iuuang smu edu. sg, jianan004 (@e. ntu. sdu zgcao smu . edu. sg, yixinxul smu. edu.
ABSTRACT
Light decoder-hased solvers have gained popularity for solving vehicle routing problems (VRPs) due to their efficiency and ease of integration with reinforce- ment learning algorithms. However, they often struggle with generalization to larger problem instances different VRP variants. This paper revisits light decoder-based approaches, analyzing the implications of their reliance on static embeddings and the inherent challenges that arise. Specifically, we demonstrate that in the light decoder paradigm, the encoder is implicitly tasked with cap- turing information for all potential decision scenarios during solution construc- tion within single set of embeddings, resulting in high information density. Furthermore, our empirical analysis reveals that the overly simplistic decoder struggles to effectively utilize this dense information, particularly task com- plexity increases, which limits generalization to out-of-distribution (OOD) set- tings. Building these insights, show that enhancing the decoder capac- ity, with a simple addition identity mapping and a feed-forward layer, can considerably alleviate the generalization issue. Experimentally, our method sig- nificantly enhances the OOD generalization of light decoder-based approaches on large-scale instances and complex VRP variants, narrowing the gap with the heavy decoder paradigm. Our code is available at: https::/se tubb. com/ ziweil wwweieenuunng// rel.-nco.
INTRODUCTION
Vehicle Routing Problems (VRPs) are a fundamental class of NP-hard combinatorial optimization problems (COPs) with wide-ranging applications in logistics (Konstantakopoulls et al., 2022), trans- portation (Garaix et al., 2010), and supply chain management (Dondo et al., 2011). Efficiently solving VRPs is critical for reducing operational costs and enhancing service quality in practice. Traditionally, VRPs have been tackled either using exact solvers (e.g.. Gurobi) or heuristic solvers (c.g.. LKH-3 (Helsgaun, 2017)). While these methods can yield high-quality (or even optimal) so- lutions for small to moderate- sized instances, they often face challenges in scaling larger problem sizes or adapting to different problem variants without extensive domain expertise or manual tuning.
Neural solvers have emerged as promising alternative by leveraging advanced deep learning tech- niques to learn solution strategies directly from data (Bengio et al., 2021). Numerous neural solvers have been proposed for solving VRPs (Bogyrbayeva al., 2024), with autoregressive construction solvers gaining particular popularity. These solvers sequentially build solutions by adding one fea- sible node at time and valued for their conceptual simplicity and flexibility across different VRP variants. Among them, (heavy encoder) light decoder- based solvers (Vinyals et al.. 2015; Kool for
al.. 2019; Kwon et al., 2020; Kim al.. 2022; Gao et al., 2024: Liu et al., 2024) stand their computational efficiency and ease of integration with reinforcement learning (RL.) algorithms. These methods typically employ a heavy wransformr-bbsee encoder to compute static node embed- dings, followed by a lightweight decoder to construct the solution by sequentially selecting the next
"Equal contribution.
Corresponding author.

---

Published as a conference paper at ICLR 2025
node based these embeddings. While this paradigm has shown promising in-distribution perfor- mance, it faces significant challenges in generalizing to out-of--istribution (OOD) instances (Joshi et al., 2021), especially those with larger problem sizes more complex constraints.
Recent works (Drakulic et al., 2023; Luo et al., 2023) propose a (light encoder) heavy decoder ar- chitecture to generate dynamic node embeddings, improving generalization on large-scale instances. Despite the impressive performance, they exhibit several limitations: 1) their solution construction process is computationally inefficient, as they must re-embed the remaining nodes each decod- ing step, resulting in much higher computational costs than light decoder-based solvers; 2) they require a considerable amount of high-quality solutions as labels for supervised training, which may be impractical for less-explored problem variants. Although self- self-improvement learning (Luo et al., 2025) can help reduce the label burden, advanced search techniques (Pirnay & Grimm, 2024) may be necessary to generate high-quality pseudo-labeh, labels for effective training, introducing an extra layer of complexity to the training process; 3) their versability may be compromised by the policy for- mulation, as they have to solve problems with an inherently tail-recursive nature. That said, both paradigms have their respective merits, and our goal is to narrow the performance gap between them.
In this paper, we revisit the light decoder paradigm by analyzing its inherent limitations, and identi- fying potential bottlenecks in current methods that hinder their performance. Firstly. we demonstrate that the architecture design of the light decoder paradigm imposes inherent challenge on the en- coder by assigning it an overly complex learning task. As nearly all embedding transformations performed in context-agnostic manner by the encoder, it has to encapsulate all relevant infor- mation necessary to address any possible future context of solution construction within single set of static embeddings, resulting in high information density. As the problem size grows, this task becomes exponentially more complex, as the encoder must anticipate and represent an increasingly vast amount of potential sub- sub-problems and decision paths within fxxed-ize static embeddings. In contrast, the dynamic node embeddings in the heavy decoder paradigm are only responsible for pre- dicting the next step based on the current state, simplifying the aecissionmmkinng task but sacrificing computational efficiency. Secondly, despite these inherent challenges of the light decoder paradigm, their heavy encoders are still capable of learning valuable static embeddings that effectively address a broad spectrum of sub-problems. However, our empirical analysis reveals that the overly simplis- tic decoder struggles to effectively leverage the dense information embedded in static embeddings during solution construction and fails to handle tasks with unseen levels of complexity, thereby lim- iting the model's ability to generalize to OOD problem instances. This suggests that enhancing the decoder's 's capacity could unlock the latent potential of existing approaches and potentially alleviate the burden on the encoder. Building on these insights into the light and heavy decoder paradigms, we propose a simple yet efficient method that leverages the strengths of each to compensate their respective weaknesses, significantly improving the performance of light decoder-based based solvers.
We systematically revisit the light decoder paradigm by thoroughly analyzing its inherent challenges and identifying potential bottlenecks in existing methods, with the goal of enhancing their generalization performance. 2) We provide in- sights into their poor generalization, including the overly complex learning task imposed on the encoder and the inability of the simplistic decoder to effectively leverage the dense information in static embeddings when addressing OOD instances. Based on these insights, we propose ReI.D, in- corporating simple yet efficient modifications, such as adding identity mapping and a feed-forwwadd layer. to enhance the decoder's capacity. 3) We conduct extensive experiments cross-problem benchmarks, and demonstrate the effectiveness of our method in significantly im- proving both in-distribution and OOD generalization performance of light decoder-based solvers. Notably, our work narrows the performance gap between light and heavy decoder paradigms, reaf- firming the potential of light decoder-based solvers when properly adjusted.
Our contributions are summarized as follows.
cross-size and
RETHINKING LIGHT DECODER-BASED SOLVERS
We introduce light decoder-based solvers, where the decoder leverages static node embeddings! as keys and values in its attention layers throughout the entire decoding process. Hereafter, with a slight abuse of terminology, the terms static embedding and light decoder will be used interchangeably.
In this paper, static embedding refers to set of node embeddings used for all key and value computations in the decoder's attention layers throughout the entire decoding process.
2

---

Published as a conference paper at ICLR 2025
steps
Probubility
Probabilty
Probabiitty
Probability
Probabiitty
Layer
Layer
Layer
Compatibiliy & Softmax
Compatibliity Softmax
Layer
Layer
Layer
Feed Forward (FF)
Layer
Layer 2
Layer 1
Layer 1
Layer 1
Attention
Attention
Inttal Embasiiings
Init Embeddlings
Inkial Embeddings
(4) Light Decoder
(b) Heavy Decoder
(c) Decodes-Oaly
(d) POMO Decoder
(e) Rel.D Decoder (Ours)
Figure 1: (a)-(c): The primary difference between light decoder, heavy decoder, and decoder-only paradigms lies in the number of prefix layers that are shared across decoding steps. (d)-(e): Decoder structures of POMO and ReLD, QKV in (d) (e) refers to the query, key and value matrices involve in the computation of MHA as presented in Eq. (4) or (9) (e.g.. Q = ho: K = V = He, in Eq. (4)).
2.1 PRELIMINARIES
VRP. VRP instance is defined over graph G (V, where is E V the node and e(va, 0z) E E represents the edge between node e; and 1/. A feasible solution is represented as a sequence of nodes that satisfies the problem-speciffe constraints. For example, feasible solution in CVRP consists of multiple sub-tours, each of which represents vehicle starting from the depot node vo. visiting a subset of customer nodes and returning to the depot node. It is feasible if each customer node is visited exactly once and the total demand in each sub-tour does not exceed the vehicle's capacity limit (i.e., capacity constraint).
fu represents
Policy Formulation. In theory, the Markov decision process (MDP) of light decoder-based solvers for generating a solution 7 (f....., FT) ) to a VRP instance should formulated as follows:
po = II (T Tt-1, 81, U.),
where po is the policy parameterized by 0, T is the total number of construction steps, тr represents the node selected at step i, encapsulates the state variables at step t. (e.g., remaining vehicle capacity for CVRP), and Uz denotes the sub-graph of consisting of only unvisited nodes at step t. It is important to note that at any step f, the policy should be conditioned only the immediate previous node T--1 and the initial node T1 (i.e., depot node Up), rather than the entire sequence of previously selected nodes. This reflects the property that the solution to the remaining sub- probpeo is independent of the sequence of earlier decisions made in VRPs (Drakulic et al., 2023).
Light Decoder-based Architecture. Typically, transformer- based encoder-decoder architecture is utilized to parameterize the policy pa. Given an instance of N customer nodes, each characterized
by raw features r; E Rdd the model first projects these features into initial embeddings (: E Rd, through a linear transformation. These initial embeddings are then processed through L encoder (L),
layers to generate final set of static node embeddings (L)) (ho ...., ....,,Nx) Formally, each encoder layer transforms ( = (n. DIN as follows:
(L)
(f-))
(e) NORM (n) MHA(H (2- )))
(2)
1 NORM (R.0 FF().)))
(3)
where NORM(-) is a normalization layer, MHA(-) is multi-head self-attention layer, and FF(() is a feed forward network with ReLU activation. We refer Kool et al. (2019) for further details. At
each decoding step t, the decoder takes as inputs the node embeddings He = {[h (T)) (1(()) with F denoting the set of feasible nodes at time and context vector h [ D.] E Rd taatr with
D, RRdater denoting dynamic features that capture the state variable 8, in Eq. (1). To aggregate
3

---

Published as a conference paper at ICLR 2025
information from node embeddings, the decoder refines the context vector he through a multi-head cross-attention layer, using he as the query and H₂ RlFa|xda as the key and value, as follows:
h²a = MHA(he. H₁, Hz).
(4)
Finally, with a hyperparameter to clip the logits so as to benefit the policy exploration, the probability p: of selecting node E Ft is calculated as follows:
p: = Softmax (c- (Canhhh
(K)TTH) He
(5)
ddn
Multi-trajectory Strategy. The multi- taaiiiitraectrrry strategy has been a default technique for light beseder-based solvers during training and inference since its introduction in Kwon al. (2020). Specifically, it exploits the symmetries in VRP solution representations by sampling multiple tra- jectories of an instance, each starting from a different initial node. This approach can be efficiently implemented due to the shared embedding design in light decoder-based solvers, where all trajec- tories share the same set of static node embeddings, significantly reducing memory consumption. During training, the model parameters 0 are optimized to minimize the expected tour length over the training data distribution using the REINFORCE algorithm (Williams. 1992). For each instance, multiple trajectories are generated by varying the starting move, with the baseline value for the pol- icy gradient set the mean reward (i.e., negative tour length) of all trajectories sampled from that instance. At inference time, multiple trajectories are sampled in parallel, and the one with the mini- mal cost is selected as the final solution for given test instance. This strategy effectively enhances exploration of the solution space without incurring significant computational overhead.
2.2 POLICY REFORMULATION
Light decoder-based solvers are characterized by their reliance on static embeddings, where the input node representations for computing keys and values in the decoder's s attention layers remain unchanged throughout all decoding steps. Most existing approaches reformulate the decoding policy (as in Eq. (1)) in terms of the encoder for and the decoder ge,, as follows:
T
Pes 8n GT = II 2=2
goo (Te (Telh Se, (hylseu.),
(6)
where (h:).10 = (G) represents the set of node embeddings for the entire graph computed by the encoder feg. In light decoder-based methods, the decoder ge, comprises a shallow network, such as a MHA and single-query attention layer (Kool et al., 2019; Kwon et al., 2020), while the en- coder feg is generally deeper network. In contrast, heavy decoder-based methods feature deeper decoder paired with a shallow encoder (Luo et al., 2023). Furthermore, designing fer as either an identity mapping or simple node-wise beed-forward network can approach what are essentially decoder-only solvers (Drakulic et al., 2023). We refer to Appendix B for a more comprehensive discussion the relationship between these paradigms within unified framework.
Gap between Policy Formulations. formulation in Eq. (6) and the principled policy formulation in Eq. (1). Concretely, each node em- bedding h2, used for decision-making at each decoding step, inherently contains information about all other (potentially irrelevant) nodes in the graph due the attention mechanisms in the encoder. Consequently, at each step, the decoder in Eq. (6) is implicitly conditioned on all previously selected nodes, which diverges from the principled policy formulation. This misalignment exhibits the gap between the theory and practical implementations in existing neural solvers. In the following, we explore this discrepancy from an alternative perspective.
Unfortunately, there is a gap between the practical policy
Static Embedding as KV Cache. Recent advancements in Large Language Models (LLM) involve using KV Cache techniques to store computed keys and values from previous tokens within attention layers in the decoder, reducing computational time (Shazeer, 2019; Brown, 2020; Ainslie et al., 2023: Touvron et al., 2023). Static embedding in COP shares similar motivation with KV Cache in NLP, aiming to prevent the re-computation of keys and values. However, fundamental difference exists in the MDP formulation between COP and NLP. In NLP, the process is generative: each predicted token is appended to the state (or context) for subsequent predictions, i.e., the context is
4

---

Published as a conference paper at ICLR 2025
increasing throughout the decoding process. Caching KV aligns naturally with the generative nature of the task, where each new token depends on the extended historical context, and hence it does not disrupt the original MDP formulation of the task. In contrast, the process in COP is selective: the context diminishes as each predicted element (or token) is removed from consideration in subsequent decisions. This reduction in context, contrary to the expansion observed in NL., implies that simply reusing KV computed on historical context may introduce irrelevant information to the decision on current sub-problem. This increases the learning task's complexity, as the decoder further needs to learn to disentangle irrelevant information from the inputs.
2.3 ANALYSES OF LIGHT DECODER PARADIGM
In the light decoder paradigm, the encoder takes on the complex task of producing context-agnostes node embeddings that are broadly applicable across various sub-problems within the original in- stance, yielding static embeddings with high information density. Despite the challenging nature of the task, we find that these embeddings are effective in addressing broad spectrum of uub-problems. Then, the decoder makes decisions based on the current sub-problem at hand to determine the next step. However, our empirical analysis reveals that the simplistic decoder struggles effectively leverage the dense information in static embeddings and fails to manage tasks with unseen levels of complexity, thereby limiting the model's ability to generalize OOI) problem instances. This high- lights the need for a more powerful decoder capable of effectively interpreting and adapting static embeddings to the current context, filtering out irrelevant information and focusing on the features most relevant to the sub-problem at hand. In the following, we delve into each point in detail.
Complex Learning Task for the Encoder. A weak decoder imposes substantial challenges on the encoder's 's learning task. Since 1) nearly all embedding transformations are performed in a context- agnostic manner by the encoder, and 2) the simplistic decoder lacks the capacity to effectively adjust static embeddings according to the context, the encoder has to encapsulate all relevant information to produce static embeddings that are sufficiently detailed and informative. These static embeddings are expected to handle any potential sub-problem (i.e. context) that may arise during solution con- struction, resulting in high information density within a single set of embeddings. As the problem size increases, the task becomes exponentially more difficult due to the combinatorial explosion of decision space. Intuitively, this exponential increase in complexity suggests that the optimal strate- gies for solving problems at different scales may diverge significantly. As the problem size grows, the interactions between nodes become more intricate, and additional constraints or patterns that are not prominent in smaller instances may emerge. Therefore, the strategies learned at smaller scales may not generalize well to larger instances, hindering the model's ability to adapt across various problem sizes. Additionally, since the encoder must allocate its representational capacity across a wide range of possible contexts, the quality of embeddings for individual situations may be diluted. This dilution may diminish the encoder's ability to capture specific features necessary for optimal performance. In contrast, in the heavy decoder paradigm, the model only needs to produce embed- dings tailored to predict the next step based on the current sub-problemt which is a much simpler task compared to the encoder's burden in the light decoder paradigm. By decomposing the complex task into predicting one step at a time based on dynamic embeddings, heavy decoder-based solvers avoid the exponentially increasing task complexity associated with larger problem sizes.
Capability of Static Embeddings in Solving Sub-problems. Despite the challenging nature of the encoder task in light decoder-based solvers, find that the embeddings generated by heavy encoders are effective in addressing a broad spectrum of sub-problems. To empirically support this, conduct an experiment using node embeddings obtained from CVRP instances to solve randomly sampled sub-instances. For simplicity, instead of generating a large instance and subsampling a set of nodes, we first generate a small instance (i.e.. a subproblem) and then add a random set of additional nodes. Note that these two processes are equivalent, as the generation of each node independent. Specifically, for a uniformly sampled CVRP instance of size n, we introduce an additional set of irrelevant nodes of size [ō x n] generated from the same distribution, where & denotes the extension rate. Then, the encoder processes all n + [ō x nı] nodes, but only the original node embeddings are used as inputs to the decoder for decision-making, We conduct experiments on 100 instances and report the average results in Table 1. It can be observed that using embeddings from larger instance does not significantly affect the performance of light decoder-based solvers, such as POMO (Kwon et al., 2020). Since the model is unaware of the specific sub-problem needs to solve in advance, this suggests that static embeddings contain valuable information to solve
5

---

Published as a conference paper at ICLR 2025
Table I: Impact of embeddings from an extended graph. Models are trained on CVRP100.
Table 2: Experiments on fine-tuning and model complexity. Models are trained on CVRP100.
CVRR100 Clap
CVRP200
CVRP500
CVRP100 Gap
CVRP200
CVRPS00
CVRP1000
Method
Method
Gap
Gap
Gap
POMO
8:
0.5
S587
1.405
1666
11.125%
10.172
POMO
1,0005
3.403%
11,135%
110,6328
Fine-cume Dec
2.600%
4,487%
7.148%
15. 2020
AM
1.0
7.6424
31555
11.00%
10.725%
23.756%
20 121229
Fine-lume Enc
3.061%
4,584%
4.863%
9.627%
LEHD
8.
648488
3,5126
3.178%
Fine-tume Lune-tum//Ae All
2.594%
4,132%
5.718%
11. 11.708%
1.3
12.95116
14,450%
12.123%
POMON
0.947%
3.864%
13,008%
31. 262662
0.0
2.72 72665
3.972%
3 3485
POMON Eice
0.990%
2.703%
9,578%
19.19816
0.5
12 271218
136475
11 1.23356
POMON-Des"
01682%
2.640%
8.18548
18.07696
various sub toobpprblems.. Moreover, conduct similar experiments on heavy decoder- based solvers, such as LEHD (Luo et al., 2023). In this setup, at each decoding step, we append [8 x n. random nodes to the model and filter them out before the final decoder layer, ensuring that the additional nodes pass through the same number of layers as in POMO's ' encoder. The results reveal that the LEHD model is highly sensitive the additional context, indicating that most of its layers, unlike those in POMO, are highly specialized for solving a specific sub-problem at each decoding step.
Inability of Simplistic Decoders. Our empirical results (in Table 2) highlight the inferior general- ization performance of light decoder-based solvers on large-scale instances. To further investigate the influence of the encoder and decoder on generalization, we conduct two experiments. First, in- spired by the linear probe protocol in self- ouf-suuprriieed learning (He et al., 2020; Chen et al., 2020), we fine-tune POMO (pretrained on CVRP100) on large-scale instances. We observe that fine-tuning only the decoder results in relatively poor performance compared to fine-tuning the encoder or per- forming full fine-tuning. This suggests a potential defect of the decoder architecture, which may complicate the fine-tuning process. Second, we attempt to strengthen the encoder and decoder of POMON (without the normalization layer), respectively. For example, POMON-Ene simply in- corporates two more layers into the encoder. The results suggest that the decoder may be overly simplistic, as increasing its capability can significantly improve its generalization performance and may reduce the burden the encoder. This observation is also supported by recent studies (Drakulic et al., 2023; Luo et al., 2023; Zhou et al., 2024b), which show that enhancing the decoder with deeper layers or conditional computation can substantially boost generalization performance. Therefore, we assume the potential bottleneck of light decoder-based solvers lies in their simplistic decoders, which struggle to effectively leverage the dense information in static embeddings and fail to manage tasks with increasing complexity.
3 METHODOLOGGY
Building on the insights into the light and heavy decoder paradigms discussed in Section 2, pro- pose ReLD, which incorporates simple yet efficient modifications to the decoder architecture and training process. ReLD effectively enhances the decoder's capability while preserving the advan- tages of light decoder-based solvers. The structure of ReL.) is illustrated in Fig. 1.
3.1 DIRECT INFLUENCE OF CONTEXT
Existing light decoder- based solvers typically employ a decoder architecture composed of an MHA layer followed by a compatibility layer. The MHA layer aggregates information from the static node embeddings using context vector he to form the query vector h'.. This query vector is then used by the compatibility layer to compute the probability distribution for the next step, based on the dot- product similarity between h/, and each node embedding. In this design. h' is the only component that captures the context, placing the entire burden of context representation on this single vector. To make the computation of the query vector M. clearer, we re-write Eq. (4) as follows:
S
S
h/= MHA He, H:)
Σ 1o Uz W. h4
ΣV
Σ
iEF.
s=1 iEP

---

Published as a conference paper at ICLR 2025
(W W. (o. H1 dh
where Uay = Softmax
Ua,i hy.
(8)
Here, S is the number of attention heads, W W W WY are the projection matrices in the s-th attention head, and He = (iF denotes the static node embeddings. We omit the superscript (L) for simplicity of notation. This design implies that the influence of the context he on hig is only mediated through the attention weights Ug.i, without directly modifying the combined vectors. Such an indirect incorporation of context may lead inefficient utilization of context information, especially in tasks with complex constraints, where dynamic context is crucial for decision-making.
To address this limitation, we propose directly integrating context information into the embedding space, rather than relying solely on the attention weights. Specifically, we suggest adding an resid- ual connection (He et al., 2016) between the context vector he and the query vector hig, thereby embedding context-aware information directly into the representation:
K' = MH H,, H.) + (DT.
In practice, he = [hr,..: De] typically has a different shape compared to h', so the identity mapping function IDT( must reshape the original input. To effectively preserve the information of the last node location hiast while maintaining simplicity, we define the function (DT(-) as follows:
IDT(he) = h + W. Dr,
(10)
where WIDT is a learnable parameter that projects De to the same dimension as h
3.2 POWERFUL QUERY
A key component of the decoder is the context-aware query vector W/- which is used to compute at- tention scores over the node embeddings and ultimately determine the probability distribution over the next possible nodes. This query vector crucial, as it is the only element in the computation that incorporates the current context of the decision makinng. In existing implementations, as shown in Eq. (7), R'. is computed as a weighted combination of the node embeddings. The computa- tion follows largely linear form with respect to the fixed sets of value vectors vs,i, with the only non-linesn non-linearity introduced through the attention weights Us This inherent linearity may limit the decoder's s capacity to model complex relationships and adapt the embeddings based the context.
Considering the importance of non-linearity enabling neural networks to model complex func- tions (Cybenko, 1989), we propose to enhance the decoder's representation capacity by introducing non-linearity into the computation of h'.. Intuitively, to more effectively transform the context infor- mation, son-lincarity should be introduced after the context has been fully aggregated. This suggests that adding non-linearity after the MHA layer, where the global context is integrated, would have a bigger impact. Drawing inspiration from the observation that the overall architecture of transformer blocks, rather than solely the self-attention mechanism, plays a significant role in the model's per- formance (Raghu al., 2021; Yu al., 2022), we propose incorporating feed-forward network with residual connections into the decoder as follows:
-== + FF(N) N. + (W2o + b1) + b2),
(11)
where Wi, W2, by, and b2 are the parameters of the feed-forward layer, and a denotes the ReLU activation function. This modification, along with the one presented in Eq. (9), transforms the decoder into a transformer block with a single query, adding non-linear processing capabilities to the query vector computation. In doing so, it provides the encoder with greater flexibility in designing the embedding space and potentially alleviates the burden imposed on it. Note that our modification computationally efficient, as the additional step-wise running time independent of the number of nodes, and therefore does not affect the overall asymptotic time complexity of the decoder. This makes a practical and effective enhancement for light decoder-bar baasde methods.
3.3 GENERALIZABLE TRAINING
Distance Heuristic. Recent advancements have incorporated distance heuristics into the learned policy (Jin et al., 2023; Gao et al., 2024; Wang et al., 2024; Zhou et al., 2024a) to enhance gener- alization on larger-scale instances. Building this idea, we add negative logarithmic distance
7

---

Published as a conference paper at ICLR 2025
Table 3: Results on synthetic CVRP instances.
Table 4: Results on CVRPLib Set-X instances.
CVRF200
CVRP1000
IV S
inclance))
Mothed
Time
Cop
Cap
Time
Cop
RKS
LKIB
12h
2.1
5.5
7.1h
LEDD prody"
11.35%
17.74%
12.53%
9,94%%
HGS
-0 50.533 4.5h -1.1266
1.4
-1799.
4h
-2.162%
5.3h
INVIT-3V+
6.52%
9.1 0.11%
10.21%
POMO
5.631
9.25%
18.85%
11 11.52%
GLOR-G (1 (1.8
6.003%
K.AM ro-ang"
1444
4.44%
5.17%
4. 435%
ELG no aug
6.25%
7.58%
10.00%
8.0%%
BQ greedy"
2.720% 1.3 m 2,972%
10
3.2485%
0.09m
5,892%
1.59m
ELG
4.51%
7.81%
6.00%)
LEHD gredly
3668%
D. 5.5 3,3128
2
3,1785
1.e
4.912%
34m
MF1
9.49%
10.6%
16.975
12.51
MVMoE
4,74%
9.97%
19. 19,00%
11 11.50%
MDAM
2.211%
25m 4.3045
10.408%
12mm
27.814%
Rel D-LM-I
1315
5.84%
9.85%
6.315
POMO augo8
1,048
1,07m 3,408%
11.125%
110.632%8
ReLD MaEL
3.14%
5.75%
8.83%
6. 1.16%
ReL.D MoEL
2.41%
3.40%
4.52%
3.54%
DLG ango8
1.20%%
3.18
2.553%
5,472%
0.44m
10,760%
1.42m
ReLD ReL.D
3,26%
3.93%
5.12%
4.18%
Rel. suga8
0.900%
1.34m 1.64%
2x
2.978%
1.s
6.757%
0.91m
2,538
3.449
4,64%
3,625
heuristic score to the output of the compatibility layer in the decoder, modifying Eq. (5) into:
C tanh( (g.)TH, He
p. Softmax
log(dist:))
(12)
Vdh
where dist, denotes the distance between node and the last selected node Tt-1.
Varying Attribute. Recent works have also introduced several strategies to improve the generaliza- tion on large-scale instances, such as training on varying instance sizes (Drakulic et al., 2023; Zhou al.. 2023; Luo et al., 2023; Wang et al., 2024; Zhou et al., 2024a) and vehicle capacities (Gao et al., 2024). We also adopt these strategies in our approach (see Section 4.1).
EXPERIMENTAL RESULTS AND ANALYSIS
In this section, we present empirical results from experiments on synthetic CVRP instances of vari- scales, multi-task cross cross-problem learning across 16 VRP variants, and the CVRPLib benchmark datasets to demonstrate the effectiveness of the proposed ReLD method. All experiments were con- ducted using single Nvidia A800 GPU with 80GB of memory.
Baselines. 1) Traditional Solvers: We utilize SOTA non-learning solvers LKH3 (Helsgaun, 2017) and HGS (Vidal, 2022), which are known for providing strong results VRPss In line with previous work (Luo et al., (023), the performance gaps are computed relative to LKH3, even though HGS generally produces slightly better results. 2) Learning-basee -bssed Solvers: We retrain the POMO model (Kwon et al., 2020) for 5,000 epochs, with 10,000 instances per epoch and batch size of 64. Addi- tionally, we utilize the publicly released available models MDAM (Xin al., 2021a), BQ (Drakulic et al., 2023), ELG (Gao et al., 2024). LEHD (Luo et al., 2023), and GLOP (Ye et al., 2024). Results for INViT (Fang et al., 2024) and ICAM (Zhou al., 2024a) are obtained from their original papers.
4.1 CROSS-SIZE
Problem Setting, We first evaluate performance on the CVRP using the test dataset introduced in (Luo et al., 2023), which consists of 10,000 instances with 100 nodes, and 128 instances for each problem size of 200, 500, and 1,000 nodes. The corresponding vehicle capacity settings for these problem scales are 50, 80, 100, and 250, respectively.
Model Setting, Based on POMO (Kwon et al., 2020), we remove normalization layers in the en- coder and add identity mapping (Section 3.1), feed forward layer (Section 3.2) and distance score (Section 3.3) to decoder to obtain Rel.D.
Training Setting, ReLD employs the same training algorithm as POMO (Kwon et al., 2020), but is trained over 90 epochs, with each epoch comprising 600,000 training instances and batch size of 120. We use the Adam optimizer with an initial learning rate of lc-4, which is decayed by a factor of 1 at the 70th and 80th epochs. Weight decay is set to zero. For generating the training data, first sample a problem size from discrete uniform distribution. Uniform(40, 100). Following the standard data generation procedure outlined in (Kool et al., 2019), node coordinates and demands are generated uniformly. To ensure adaptability to varying attribute (Section 3.3). we randomly sample an expected route size (average number of nodes in route) from triangular distribution
8

---

Published as a conference paper at ICLR 2025
Table 5: Performance on IK test instances of 16 VRP variants.
CVRP Gap
VRPTW Gap
OVRP Gap
VRPL
Method
Obj
Time
Obj
Time
Objj
Time
Obj.
Gap
Time
HGS
15,504
9. 1.m
24.339
6.6m
LK1B
15.500
0.5566
18.0m
24.721
1.584S
7.8m
10.010
5.3m
16.496
16. Dm
1.44%
POMO
15. 15.734
1.488%
9%
25.367
4.M07 %
10,044
2.192%
15. 15.785
0.092%
96
POMO-MTL
15 790
8840%
96
25.010
5.313%
11s
10.109
1458%
15846
0.470%
96
MV MV
15 15.71
10s
15.519
4.92%%
115
10.145
1.214%
15.21
3.32%%
10s
15 15.22
25-512
15812
Rel D-MITI
.416%
10c
4.561%
11s
10.057
5.521%
15.
0.020%
10s
ReLD-MoEL
15.713
1.354%
10s
25.403
4,444%
11s
10,050
2 2.260%
15.768
-0.016%
10s
Rel MoELL
15.739
1.515%
10s
25.445
4.621
11s
10.084
2.592%
15.788
0.113%
10s
VRPB
OVRPTW Clpp
OVRPB
OVRPL Gup
Method
Obj
Gup
Time
Obj.
Time
Ohj
Gap
Time
Obj.
Time
Tools
11.878
3,5h
14.380
3.5h
8.365
3.5h
9.790
3.5h
POMO
1.993
0.995%
06
14.728
2.467%
11s
POMO-MIL
1.674%
06
15.008
4-111%
11s
8.979
13355%
10.126
3.441%
94
12005
MVM
12.027
1285%
136
14.927
5.852%
126
8.959
1.88%%
10s
10.097
3. 3.1485
1]5
Rel D.D.DM D-MILL
11.98
0.90115 S6
10s
14818
1.107%
11s
8.814
10.014
3.110%
10s
ReL D-M
11,969
0.801 %
10s
14.804
3,00095
118
8.804
3.2399%
9%
10.007
2.2333%
10s
ReLD-MoEL
11.981
0.887%
10s
14.848
3.3049
11s
8.794
5.113%
9s
10.040
2.567%
10s
VRPBL Gup
VRPBTW Gup
VRELTW Gap
OVRPBL
Method
Obj.
Time
Obj.
Time
Objj
Time
Obj.
Gup
Time
OR-
790
3,5h
.949
3.5h
25. 25.195
3.5h
3,5h
POMO-MTL
11. 1908
1. 1.79%%
96
419
7 7.413%
11s
$5.619
1.920%
16
8. 1.96]
1.3435
MV Mo
11 1960
1,4 1.473%
[0s
26265
7.190%
11s
25.529
8.051
1.300%
10s
MVMoE
11.455
1.346%
13s
27 236
7.078%
12%
25.514
L471%
10s
8.942
7.115%
11s
MTT
ReLD-Mod MoEL
11.894
0.917%
10s
27.106
6.574%
11s
25,415
L0099
8.786
5 3.247%
10s
Rel ReEL
11,908
1.0245
10c
27. 166
6.806%
11s
25.456
1.258%
8.779
5.154%
10s
OVREBTW Gap
OVRPLTW Gap
VRPBLIW Gap
OVRPBLTW Cap
Method
Obj.
Time
Obj.
Time
Obj.
Time
Obj.
Time
OR Tools
14.184
3.5h
14:279
3.5h
25.
25.342
3.5h
14. 14:250
3,5h
4.3744%
1.746%
MVMoE-L
10.188%
10s
3.971%
22
3,706
10.2635
10s
MY Mol
15 800
9.948%
135
14.828
5.900%
126
12.142
10s
13.771
10 10.009%
[]s
ReLI-MIIL
15711
92288%
10s
14:221
3.1 1992
11s
37.043
60574
06
15 13-55
9.2155
10s
D-MELL
15.697
9.184%
10s
14.707
3.054%
118
6.915%
15.350
9.171%
10s
Rel D-MoEL
15.728
9.403
10c
14.744
3.318%
118
27:078
7.100%
9%
15,599
9.5166
10s
T(3, 6, 25) (Uchoa et al., 2017) for each instance, the vehicle capacity of which is set to [rD], where D represents the mean demand of the nodes in the instance.
Inference Setting. For all neural solvers, we adopt the greedy rollout strategy. To ensure comparable runtime across baselines, we set the number of rollout trajectories K for all light decoder-based methods (POMO, ELG, ReLD) to min(100, .V), where N represents the problem size. To initialize each trajectory, we input all the nodes with full capacity to the decoder and select top K moves with respect to the output probability distribution.
The results on uniformly generated CVRP instances are presented in Table 3 (the super- script asterisk (*) on method denotes that the results of the method are directly obtained from the original paper). ReLD consistently outperforms other learning-based solvers at all scales except for CVRP1000, while achieving similar or lower computational time. For CVRP1000, ReL.D re- mains highly competitive, surpassing most neural solvers. However, solvers like BQ and LEHD still demonstrate superior performance at this scale, indicating that a performance gap persists between light decode methods and architectures with more decoder layers for larger instances.
Results.
4.2 CROSS-PROBLEM
We follow all the problem setting, training setting, and evaluation setting used in Zhou et al. (2024b).
Model Setting, We remove all the normalization layers in the encoder and add identity mapping (Section 3.1), feed forward layer (Section 3.2) to the original POMO-MTL and MVMoE-light to obtain the ReI.DMMT and ReI.D-MoFL. Notably, original MVMoF-light utilizes an MoE layer to replace the linear layer in the decoder to transform the results obtained from multiple attention heads. For simplicity and fair comparison, we use the original POMO decoder architecture with added identity mapping and feed forward layer in both of the ReLD-MTL and ReLD-MoEL. We also employ the training techniques in Section 3.3 on ReLD-MoEL, denoted as ReL.DMoELL+
The results on all the VRP variants are shown in Table 5 and Table 7 (see Appendix). is quite clear that all the ReLD models outperform the POMO-MTL. MVMoE-L and MVMoE base- lines on all the studied VRP variants by a significant margin. Notably, both the ReLD-MTI and ReI.D D-MLD outperform the single-task POMO that is specifically trained on the CVRP, VRPL and
Results.

---

Published as a conference paper at ICLR 2025
VRPB. An more surprising result is that ReLD-MoEL surpasses the strong LKH3 traditional solver on VRPL, achieving a negative gap. The improvement becomes even more pronounced in the generalization to unseen VRP variants (the last 10 variaints in Table 5), with an average gap improvement of 1.1% and 1.0% for ReI.D-MTI. and Rel.D-MoFL, respectively, compared to their original counterparts. This demonstrates the superior ability of ReL.D to handle varying constraints effectively. On the other hand, ReLD-MoEL* underperforms relative to other ReLD models on most problems, though still significantly outperforms all baselines. This suggests that the tech- niques employed in Section 3.3 may trade off in-distribution performance to gain stronger out-of- distribution generalization, aligning with the observations in Section 4.4.
4.3 BENCHMARK PERFORMANCE
We also evaluate our ReLD on the well known benchmark dataset CVRPLib Set-X (Uchoa al., 2017) and Set-XXL. Specifically, we divide CVRPLib Set-X (Uchoa et al., 2017) into 3 subsets according to the scale the of instances, each with range N < 200, 200 N < 500 and 500- < N
1000. For Set-XXI, we select instances with size 3000 I N s 16000.
Inference. On both datasets, light decoder- based models run with maximum of 100 trajectory and augmentation x8 (Kwon et al., 2020) is used by default.
Results. The results on Set-X and Set-XXL are presented in Table and Table 8 (see Appendix), respectively. Interestingly, heavy decoder methods like LEHD show inferior performance on Set-X instances, especially when compared the lighter decoder-based methods. ReL.D models, including both ReI.DMTTL and ReI.D-MRLL consistently outperform the baseline methods without distance heuristic across all instance sizes. For the models that involve using advanced techniques like dis- tance heuristic, ReLD-MoEL+ achieves the best results. Such surprising results suggest that it is a generalizable foundational model. Furthermore, ReLD demonstrates a significant margin of im- provement over all baseline methods the four large scale real-world instances from Set-XXL, further validating the generalizability of the proposed methods.
4.4 ABLATION STUDY
We conduct an ablation study to gain insights for the contribution of each components in ReLD for the overall performance. The main results are summarized in Tables 10 and 11. We refer readers to Appendix G for further details and analysis.
Identity Mapping is Crucial for OOD Size Generalization. The introduction of identity mapping significantly improves generalization to larger problem sizes for both POMO and POMON (POMO without the normalization layer), highlighting its critical role in handling out-o--distribution (OOD) instances. Additionally, it provides minor improvements for smaller problem sizes, indicating that it enhances generalization without sacrificing in-distribution performance.
Feed Forward Layer is Crucial for In-Distribution Learning. Adding feed-forward layer to POMON reduces the gap on CVRP100 from 0.95% 0.66% (POMON v.s. POMON+FF), signif- icant improvement in in-distribution learning. However, this modification is less effective for larger scales without the identity mapping. as seen on CVRP1000.
5 CONCLUSION
This paper positions light decoder-based models as efficient approximations to the original MDP formulation of VRP by sharing computations across decoding steps. We provide valuable insights into potential bottlenecks of existing light decoder methods and introduce ReLD, simple yet ef- fective approach that narrows the performance gap between light and heavy decoder paradigms. Extensive experiments cross-size and cross-problem benchmarks demonstrate the effectiveness of our method. However, ReLD still trails behind heavy decoder-bart based solvers on very large-scale instances. This highlights an inherent trade-off between performance and computational efficiency. Future work includes exploring the boundaries of light decoder-bart based solvers and investigating op- timal performance-efficinn trade-offs by controlling the amount of computation sharing.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work is supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No. AISG3-RP-2022-031] and the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grant.
REFERENCES
Joshua Ainslie, James Lee- Lhorp. Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. GQA: Training generalized multi-query transformer models from multi-head check- points. arXiv preprint arXiv:2305. 13245, 2023.
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.0555 05205, 2020.
Thomas Bachlechner, Bodhisattwa Prasad Majumder, Henry Mao, Gary Cottrell, and Julian McAuley. Rezero is all you need: Fast convergence at large depth. In Uncertainty in Artificial Intelligence, pp. 1352 1361. PMLR, 2021.
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Representa- tions Workshop Track, 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: methodological tour d d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jicyi Bi, Yu Hu, Fei Liu, Hyconah Kim, Jiwoo Son, Haeycon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Jie Zhang, Kijung Shin, Cathy Wu. Sungsoo Ahn, Guojie Song, Changhyun Kwon, Lin Xie, and Jinkyoo Park. RLACO: an extensive reinforcement learning for combinatorial optimization benchmark. arXiv preprint arXiv:2306.17100 2023.
Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Kevin Tierney, and Jinkyoo Park. Routefinder: Towards foundation models for vehicle routing problems. arXiv preprint arXiv:2406. 15007, 2024.
Jieyi Bi. Yining Ma, Jiahai Wang. Zhiguang Cao. Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In Ad- vances Neural Information Processing Systems, volume 35, pp. 31226-31238, 2022.
Jieyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, and Jie Zhang. Learning to handle complex constraints for vehicle routing problems. In Advances in Neural Information Processing Systems, 2024.
Aigerim Bogyrbayeva, Meraryslan Meraliyev, Taukekhan Mustakhov, and Bissenbay Dauletbayev. Machine learning solve vehicle routing problems: survey. IEEE Transactions on Intelligent Transportation Systems, 2024.
Tom B Brown. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličkovié. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1-61, 2023.
Jinbiao Chen, Zizhen Zhang, Zhiguang Cao, Yaoxin Wu, Yining Ma, Te Ye, and Jiahai Wang. Neural multi-objective combinatorial optimization with diversity enhancement. In Advances in Neural Information Processing Systems, volume 36, pp. 39176-39188, 2023.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning visual representations. International conference on machine learning, pp. 1697-1607. PMLR, 2020.
11

---

Published as a conference paper at ICLR 2025
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In Advances in Neural Information Processing Systems, volume 32, pp. 6281-6292 2019.
Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Eren Akçay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning. pp. 465-480, 2020.
George Cybenko. Approximation by superpositions a sigmoidal function. Mathematics control, signals and systems, 2(4):303-314, 1989.
Rodolfo Dondo, Carlos A Méndez, and Jaime Cerdá. The multi-echelon vehicle routing problem with cross docking in supply chain management. Computers & Chemical Engineering, 35(12): 3002-3024, 2011.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. BQ-NCO: Bisimulation quotienting for efficient neural combinatorial optimization. In Advances in Neu- ral Information Processing Systems, volume 36, 2023.
Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. GOAL: A generalist combinatorial opti- mization agent Iearner. International Conference on Learning Representations, 2025.
Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. INVIT: A generalizable routing problem solver with invariant nested view transformer. International Conference on Machine Learning, 2024.
Zhang-Hur Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7474-7482, 2021.
Chengrui Gao, Haopu Shang, Ke Xue, Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In IJCAI, 2024.
Thierry Garaix, Christian Artigues, Dominique Feillet, and Didier Josselin. Vehicle routing prob- lems with alternative paths: An application to on-demand transportation. European Journal of Operational Research, 204(():62-755 2010.
Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations, 2022.
Nathan Grinsztajn, Daniel Furelos-Blanco, Shikha Surana, Clément Bonnet, and Thomas D Bar- rett. Winner takes it all: Training performant RL populations for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the JEEE/CVF conference on computer vision and pattern recognition, pp. 9729-9723 2020.
Keld Helsgaun. An extension of the wakeernighan-helsguae tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, pp. 24-50, 2017.
André Hottung, Mridul Mahajan, and Kevin Tierney. PolyNet: Learning diverse solution strategies for neural combinatorial optimization. In International Conference on Learning Representations, 2025.
Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In International Conference Learning Representations, 2023.
12

---

Published as a conference paper at ICLR 2025
Chuanbo Hua, Federico Berto, Jiwoo Son, Seunghyun Kang, Changhyun Kwon, and Jinkyoo Park. CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems. Proceed- ings of the 2025 International Conference on Autonomous Agents and Multiagent Systems, 2025.
Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 8132-8140, 2023.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprini
2019.
Chaitanya K Joshi, Quentin Cappart, Louis-Martnn Rousseau, and Thomas Laurent. Learning tsp requires rethinking generalization. In International Conference on Principles and Practice of Constraint Programming. 2021.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 35, pp. 1936-1949, 2022.
Minsu Kim, Sanghyeok Choi, Jiwoo Son, Hyeonah Kim, Jinkyoo Park, and Yoshua Ben- gio. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.07041, 2024.
Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias. Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational research, pp. 1-30, 2022.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pp. 21188-211 21198, 2020.
Yeong-Dae Kwon, Jinho Choo, Iijoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances Neural Information Processing Systems, volume 34, 2021.
Jingwen Li, Liang Xin, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning. IEEE Trans- actions Intelligent Transportation Systems, 23(3):2306-23111 2021a.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In Advances in Neural Information Processing Systems, volume 34, pp. 26198-26211, 2021b.
Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1898-1908, 2024.
Hao Lu, Xingwen Zhang, and Shuang Yang. learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances Neural Information Processing Systems, volume 36, pp. 8845-8864, 2023.
Fu Luo, Xi Lin, Yaoxin Wu, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang Boosting neural combinatorial optimization for large-scale vehicle routing problems. In Interna- tional Conference on Learning Representations, 2025.
Yining Ma, Jingwen Li. Zhiguang Cao, Wen Song. Le Zhang. Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems, volume 34, pp. 1 11096-11107, 2021.
13

---

Published as a conference paper at ICLR 2025
Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Advances in Neural Information Processing Systems, 2023.
Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. In Advances in Neural Information Processing Systems, 2023.
Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence V Snyder. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9861-9871, 2018.
Jonathan Pimma and Dominik G. Grimm. Seff-imprrvement for neural combinatorial optimization: Sample without replacement, but improvement. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combina- torial optimization problems. In Advances in Neural Information Processing Systems, volume 35, pp. 25531-25546, 2022.
Maithra Raghu, Thomas Unterthiner, Simon Kornblith, Chiyuan Zhang, and Alexey Dosovitskiy. Do vision transformers see like convolutional neural networks? Advances in neural information processing systems, 1112116-111 14:12116-12128, 2021.
Noam Shazeer. Fast transformer decoding: One write-head is all you need. arXiv preprint
arXiv:1911.02150, 2019.
Igor G Smit, Jianan Zhou, Robbert Reijnen, Yaoxin Wu, Jian Chen, Cong Zhang, Zaharah Bukhsh, Yingqian Zhang, and Wim Nuijten. Graph neural networks for job shop scheduling problems: A survey. Computers & Operations Research, pp. 106914, 2024.
Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based diffusion solvers for combinatorial opti- mization. In NeurlPS, volume 36, pp. 3706-3731 2023.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint wrxiv:2307.09288 2023.
Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-888) 888, 2017.
Thibaut Vidal, and Anand Subramanian.
Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap neigh- bothood. Computers Operations Research, 140:105647 2022.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances neural information processing systems, volume 28, 2015.
Yang Wang, Ya-Hui Jia, Wei-Neng Chen, and Yi Mei. Distance-aware attention reshaping: En hance generalization of neural solver for large-scale vehicle routing problems. arXiv preprint arXiv:2401.06977 2024.
Ronald J Williams.
Simple statistical learning. Machine learning, 8:229 6:229-256, 1992.
algorithms for connectionist reinforcement
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving routing problems, IEEE Transactions on Neural Networks and Learning Systems, 33()):0577-069, 2021.
Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, Jiang Bian. Position: Rethinking post-hoc search-hased neural approaches for solving large-scale traveling salesman problems. In International Conference Machine Learning, 2024.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12042-1 1049, 2021a.
14

---

Published as a conference paper at ICLR 2025
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. KeuroLKH: Combining deep learning model with lin bernighan-helsgune heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems, volume 34, pp. 7472- 11772-7433, 2021b.
Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. DeepACO: Neural-enhanced systems for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. GLOP: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinchao Wang. Jiashi Feng, and Shuicheng Yan. Metaformer actually what you need for vision. In Proceedings the IEEE/CVF conference on computer vision and pattern recognition, pp. (0819-10829, 2022.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Advances Neural Information Processing Systems, volume 33, pp. 1621-1632. 2020.
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with GFlownets. In Advances in Neural Information Processing Systems, 2023.
Changliang Zhou, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang- Instance-condittoned adaptation for large-scale generalization of neural combinatorial optimiza- tion. arXiv preprint urXiv:2405.01906, 2024a.
Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learning, pp. 42769942789. PMLR, 2023.
Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. MV- MoE: Multi-task vehicle routing solver with mixture-of-experts In International Conference Machine Learning, 2024b.
15

---

Published as a conference paper at ICLR 2025
A RELATED WORK
Neural VRP solvers typically learn construction heuristics, which can be broadly categorized into two types: autoregressive and non-autoregressive construction solvers. Autoregressive construction solvers build solutions sequentially by adding one feasible node at time. Within this category, light decoder-based solvers, characterized by static node embeddings generated in a heavy encoder and solution construction handled by lightweight decoder, have gained significant popularity for their computational efficiency and versatility. Vinyals et al. (2015) propose the Pointer Network, which solves the traveling salesman problem (TSP) using supervised learning (SL). Later works shift from SL to RL to solve TSP (Bello et al., 2017) and the capacitated vehicle routing problem (CVRP) (Nazari et al., 2018). Kool et al. (2019) introduce the attention model (AM), targeting range of COPs such as TSP and CVRP. Building on this, Kwon et al. (2020) propose the policy optimization with multiple optima (POMO), which improves AM by exploiting multi-trajectory strategy. Subsequent developments (Kwon et al., 2021; Li et al., 202 la; Kim et al., 2022; Grinsztajn al., 2023; Chen et al., 2023; Liu et al., 2024; Gao al., 2024: Zhou et al., 2024b; Berto et al., 2023; 2024; Bi et al., 2024; Hottung et al., 2025; Hua et al., 2025) are often built upon AM and POMO, further advancing their scalability (Li et al., 2021b; Hou et al., 2023; Ye et al., 2024) and generalization (Joshi et al., 2021; Bi et al., 2022; Geisler et al., 2022; Zhou et al., 2023). Heavy decoder-based solvers (Drakulic et al., 2023; Luo et al., 2023; 2025), characterized by dynamic node embeddings re-embedded at each decoding step, demonstrate impressive performance on large-scale instances, though at the expense of computational efficiency and training simplicity. Regarding non- autoregressive construction solvers, solutions are generated in one-shot manner, bypassing the need for iterative forward passes through the model. Early work (Joshi et al., 2019) employs graph convolutional network to predict the probability of each edge appearing on the optimal tour (i.e., a heatmap) using SL. More recent efforts (Fu et al., 2021; Qiu et al., 2022; Sun & Yang, 2023; Min et al., 2023; Ye et al., 2023; Kim al., 2024; Xia et al., 2024) further enhance performance by leveraging advanced models, training paradigms, and search strategies. Beyond construction solvers, some neural solvers learn improvement heuristics iteratively refine an initial feasible solution until a termination condition is met. These approaches often involve learning more efficient or effective search components within classical local search methods or specialized heuristic solvers (Chen & Tian, 2019; Lu et al., 2020; Costa et al., 2020; Wu et al., 2021; Ma et al., 2021; Xin et al., 2021 Ma et al., 2023). While improvement solvers generally outperform construction solvers in terms of solution quality, they come with the trade-off of significantly longer inference time. In this paper, we mainly focus on autoregressive construction solvers due to their efficiency and versatility in solving VRPs. Moreover, extensive research has focused on solving other COPs, such as the scheduling problem (Zhang et al., 2020; Smit et al., 2024) and graph COPs (Zhang et al., 2023). We refer readers to Bengio et al. (2021); Cappart al. (2023) for a comprehensive survey.
B MORE DISCUSSIONS ON LIGHT DECODER AND HEAVY DECODER
While the main text focuses the differences in encoder and decoder depth across paradigms, an alternative and unifying perspective is to view these architectures through the lens of layer sharing across decoding steps. Specifically, for model with L layers, the computation of the first L' layers are shared across K decoding steps. This general framework captures existing methods as special cases: decoder-only models (c.g., BQ (Drakulic al., 2023)) arise when L' 0. heavy decoder models (e.g., LEHD (Luo et al., 2023)) correspond to cases where L' < L - 1, and light decoder models (e.g.. AM (Kool et al., 2019), POMO (Kwon al., 2020)) are obtained when L' = L - 1. This flexible paradigm enables trade-offs between performance and efficiency by adjusting the number of shared layers and the frequency of updating shared embeddings. Under this framework, static embeddings are utilized for only constant number of decoding steps K, meaning they only need to encode information relevant to bounded span of future contexts rather than for all O(N) steps. This reduction in required information density by order of magnitude alleviates the complexity of the encoder's 's learning task and, in principle, should lead to improved performance. We leave comprehensive investigation of this framework for future work.
16

---

Published as a conference paper at ICLR 2025
C IMPACT OF CAPACITY
We found that the POMON+IDT+FF model, when trained with fixed capacity setting, struggles generalize to instances with capacity distributions that differ significantly from the training distri- bution, even on relatively small problem size (see Table 6). This suggests that capacity constraints may introduce generalization challenges that are independent of problem seale. Motivated by this observation, we explore training with varying capacity settings to expose the model to broader range of contexts, aiming to improve its adaptability to diverse instance distributions.
Table Investigation into the impact of capacity settings. The POMON+IDT-FT model, trained instances of size sampled from Uniform(40, 100) with a fixed capacity of 50, struggles to generalize varying capacity settings. "No-aug single" denotes inference using single trajectory without augmentation. "n100:Cap.M" represents instances of size 100 with capacity M.
n 100:Cap50 Obj.
n100:Cap100 Obj.
n100:Cap250 Obj.
1000:Cap500
Method
Ohj.
POMON+IDT+FF no-aug single
16.20 16.55
11.14
9.04
8.65
LEHD greedy
11.17
8.81
8.41
D AVERAGE GAP IN CROSS-PROBLEN SETTINGS
Table 7: Average gap of each model in cross-problen settings.
Method
6 Trained VRPs
10 Unseen VRPs
ALL
POMO-MTL
2.863%
6.231%
4.968%
MVMoE-L
2.584%
5.989%
4.712%
MVMoE
2.515%
5.844%
4.596%
ReLD-MTL
2.054%
5.059%
3.932%
ReLD-MoEL
1.974%
4.962 %
3.842%
ReL.DMoEL.*
2.172%
5.126%
4.019%
E RESULTS ON CVRPLIB SET-XXL
Table 8: Empirical results on real-world instances from CVRPLib Set-XXL with N < 16, 000. The
asterisk (*) denotes the results of methods directly obtained from the original paper.
(3K)
L2 (4K)
(6K)
A2 (7K)
(10K)
(LIK)
BI (1SK)
B2 (16K)
GLOP-LKH3*
16.60%
21.10%
19.30%
19.40%
18.30%
18.10%
27.50%
20.10%
BQ greedy*
13.27%
24.00%
11.21%
15.02%
LEHD greedy*
14.04%
26.30%
18.90%
26.40%
27.23%
38.45%
35.94%
40.76%
POMO*
75.30%
78.16%
112.27%
159.22%
Sym-POMO
170.44%
179.55%
79.72%
179.55%
Omni-POMO
22.79%
60.39%
42.52%
48. 58.599%
10.77%
21.80%
10.70%
17.69%
13.24%
18.93%
17.73%
20.05%
RcLD no-aug
7.74%
15.23%
7.61% % 7.43 %
13.53%
7.92%
15.44%
10.45%
15.59%
ReLD
7.45%
14.55 %
13.50%
7.63%
14.38 %
10.08 %
14.69%
F APPLICATION ON ATSP
We extend our approach to the Asymmetric Traveling Salesman Problem (ATSP), a more practical variant of TSP. Experiments conducted based on the MatNet model (Kwon al., 2021).
17

---

Published as a conference paper at ICLR 2025
F.1 ENCODER MODIFICATIONS
To create efficient and effective encoder, introduce simple yet impactful modifications to the original MatNet encoder. These modifications are applied to both MatNet and ReLD.
Initial Embedding. Original MatNet zero vectors and one-hot vectors for initial embeddings. However, using one-hot vectors limits the model's applicability to instances with size larger than embedding dimension (256). To resolve this, assign random number from Uniform(O, to each node as its initial node features (Drakulic et al., 2025). Then, a learnable linear layer transforms the ID random features into the embedding dimension inputs to the encoder.
Single Branch. MatNet employs a two-branch transformer architecture with cross-attention to model interactions between two sets of objects. However, this design is unnecessary for ATSP, where only a single set of objects (i.c., nodes) is present. To simplify the architecture while pre- serving effectiveness, we modify the encoder use single-branch self-attention mechanism. This adjustment reduces computational overhead without sacrificing performance.
Mixed Score Self-Attention. To modify the mixed score cross- attention proposed MatNet to self-ar attentinn we mix the distance matrix D and its transpose D simultaneously with the attention score of each head. This helps the network better understand the from-to dual relationship between nodes with self-attention. Notably, we observed that the model fails to converge when DJ is omitted.
Normalized Distance Matrix. Since the optimal solution is invariant the scale of the distance matrix, we normalize the distance matrix by dividing its maximum value before passing the network.
F.2 RELD FOR ATSP
We incorporate the proposed architectural enhancements- iddetttty mapping and feed-forward net- work-into the MatNet decoder. Specifically, let h,, denote the embedding of the th node of the constructed trajectory. At step + 1, the query vector h/. is obtained as follows:
K/ = MHA N,,), H,, Ht) + hT.:
where [ denotes the concatenation operator. Notice that we exclude the step-agnostic context information hr, in the identity mapping. To further refine Ki, we apply feed-forward network with a modified reZero (Bachlechner al., 2021) connection:
ae = ah' + FF(N)).
where FF is 2-layer feed-forward network with ReLU activation, a is learnable scalar initialized zero, applied the identity branch, slightly deviating from the original reZero formulation. The resulting de is then used in Eq. (5) of the main paper to output action probabilities. Note that we do not incorporate the distance heuristic varying-size training techniques this preliminary result.
F.3 TRAINING SETTING
We train the models on ATSP instances of size 100 for 2100 epochs, with each epoch consisting of 10,000 instances and batch size of 128. To reduce memory consumption, we use four attention heads with query-key-valuey dimension 64 in the encoder, while keeping all other hyperparame- ters identical to those in MatNet (Kwon al., 2021).
F.4 RESULTS
We evaluate the models on synthetic ATSP instances of sizes 20, 50, 100, 200, and 500. All models use greedy rollouts with full trajectories and no augmentation. For the original MatNet, we report results from the released checkpoint, which was trained for 12,000 epochs instances of size 100. M incorporates the encoder modifications described Section F.I. while ReLD builds upon MatNet with additional decoder enhancements. The results. presented in Table 9, show that the original MatNet model struggles to generalize across different instance sizes. MatNet* improves performance the original model, and ReL. further enhances results across all tested sizes.
18

---

Published as a conference paper at ICLR 2025
Table 9: Results on ATSP instances across different scales.
ATSP20
ATSP50
ATSP100 Obj. (Gap)
ATSP200 Obj. (Gap)
ATSP500 Obj. (Gap)
Method
Obj. (Gap)
Obj. (Gap)
CPLEX
1.540 (+)
1,560 (*)
MatNet official
2.608 (69.351 %))
2.556 (63.846%)
1.624 (3.439%)
MatNer*
1.651 (7.208%)
1.604 (2.821%)
1.616 (2.930%)
1.665 (1.216%)
2.126 (12.725%)
ReLD
1.623 (5.390%)
1.591 (1.987%)
1.607 (2.357%)
1.645 (*)
1.886 (*)
G ABLATION STUDY RESULTS
The ablation results for the architectural components are summarized in Table 10. The models ReLD w/o IDT FF, ReLD-7Layer, and ReLD are trained following the settings described in Section 4. while all other models are trained under the same conditions as the POMO baseline. To further assess the impact of the distance heuristic on acage instances, we train ReLD with and without distance heuristic using the training setup from ICAM (Zhou et al., 2024a), which primarily samples instance sizes from Uniform(106 500). The results of this experiment are presented Table 11.
ReLD Improves Generalization Performance to Larger Size. Integrating the feed-forwe forward layer with identity mapping leverages their complementary strengths, leading to significant improve- ments in both in-distribution performance and lem sizes (POMON vs. POMON+IDT+FF) Additionally, incorporating the distance heuristic and training with varying attributes further enhances generalization, albeit with minor trade-off in in- distribution performance. The combination of identity mapping and the feed-forward layer delivers consistent improvements across all problem scales, effectively narrowing the performance gap as problem size increases. These results underscore the effectiveness of the proposed architectural modifications in enhancing both scalability and adaptability.
(OOD) generalization across prob-
Where and How to Introduce Extra Parameters Matter. We explore three additional ways to increase the number of parameters in the decoder: (1) +FF replacing the query and key trans- formations in the MHA module with feed-forward networks, (2) +FF replacing the query, key, and value transformations in the MHA module with feed-forward networks, and (3) +MHA: adding an additional MHA layer top of the original one. Our findings reveal that simply increasing the number of parameters does not necessarily improve performance. In fact, certain modifications (+FFgg gl: and +kFg degrade performance significantly. This highlights the importance of thought- fully determining where and how additional parameters are introduced into the decoder.
Why Identity Mapping is Effective for Size Generalization? The effectiveness likely stems from its ability to explicitly preserve context information, such as the location of the last selected node. As problem sizes grow, the decoder must aggregate vast amount of global and local information into a fixed-size query vector, which can result in the loss of crucial locality information (Alon & Yahav, 2020). Identity mapping mitigates this issue by reinforcing the positional information of the last visited node, enabling the model to better distinguish local interactions in larger graphs.
Adding Additional Encoder Layers to ReLD Does Not Benefit Size Generalization. We also attempted to enhance the encoder capacity in ReLD by adding an additional layer (ReLD-7layer). Unfortunately, while this led a slight improvement in in-distribution performance, it had no posi- tive effect on OOD generalization, and in some cases, even worsened it. This supports the hypothesis that, with the same decoder structure, the encoder's learning task for small-scale instances has lim- ited overlap with that for larger-scale problems, as indicated by the intrinsic complexity gap. As a result, improving the encoder alone does not necessarily enhance OOD performance due to this misalignment. These findings suggest that efforts should focus improving the decoder structure to simplify the encoder's 's task and reduce the gap between the encoder's 's tasks across different scales.
Distance Heuristic is Crucial. It can be observed that the distance heuristic plays crucial role in enabling generalization across scales. When distance information is explicitly leveraged, models consistently achieve better performance across all problem sizes. For instance, ReL.D with distance
19

---

Published as a conference paper at ICLR 2025
heuristic outperforms its counterpart without distance heuristic in all configurations, particularly on larger-scale instances such as CVRP5000 and CVRP7000. Notably, even without leveraging distance information, ReLD remains highly competitive with the baselines, particularly problem sizes increase. This highlights the superiority of the proposed decoder modifications.
Table 10: Ablation study of components in ReLD.
CVRP100 Gap
CVRP200 Gap
CVRP500 Gap
CVRP1000 Gap
Method
POMO
1.004%
3.403%
11.135%
110.632%
POMO+IDT
0.936%
3.096%
9.349%
23.508%
POMON
0,947%
3.864%
13.008%
33,262%
POMON+FF
0.889%
3.907%
15.589%
169.461 %
POMON+FF phe
0.837%
3.894%
16.314%
424%
POMON+MHA
1.129%
4.478%
15. 15.80
47.132%
POMON+ITT
0.909%
3.623%
10,932%
20.687%
POMON+FF
0.663 %
3.142%
12.901 %
35,589%
POMON+IDT+FF
0.682%
2.640%
8.185%
18.076%
ReLD w/ IDT&FF
1.063%
1. 1.960%
1.10%%
9.623
ReI.D-7Layer
0.921% %
1.638 %
3.055%
6.834%
ReI.D
0.960%
1.690%
3.015% %
6.771 1
Table 11: Impact of training larger-scale instances. "w. dist" indicates that distance information is explicitly incorporated into the model, while "w/o dist" denotes its absence. "Single-trajec." refers to inference using single starting point, "100-traject. involves rolling out the top 100 starting points at the first step, and "full-traject." utilizes the total number of possible trajectories, as in POMO. Augmentation is disabled for all models.
CVRP100
CVRP1000 Obj.
CVRP2000 Obj.
CVRP5000 Obj.
CVRP7000
Method
Obj.
Obj.
HGS
15.56
36,29
57.20
126.20
172.10
GLOP-G
15.65
37.09
63.02
140.35
191.20
LEHD greedy
16.22
38.91
61.58
138.17
BQ greedy
16.07
39.28
62.59
139.84
ICAM dist single-trajec.
16.19
38.97
62.38
140.25
ICAM w. dist full-trajec.
15.94
38.42
61.34
136.93
ReLD w/o dist single-trajec.
16.28
38.83
61.37
135.30
183.79
ReLD w/o dist 100- 100-trajec.
15.98
38.41
60.78
134.45
182.75
ReLD w. dist single-trajec.
16.26
38.69
60.41
129.66
173.91
RcLD w. dist 100-trajec.
15.97
38.28
59.84
128.79
172.83
H RESULTS OF FINE-TUNING ON LARGE SCALE INSTANCES
We fine-tune the ReI.D model checkpoint from the 70th epoch (before the learning rate decay) for epoch (5000 batches). The instances are generarated with size N sampled from Uniform( (00), 500). The expected route size (average number of nodes a route) is sampled from triangular distribution T(8, 16, 45). The learning rate is decayed by factor of 0.1 at the 2500th batch. Batch size is set to [120 1000 remain identical training settings. For baseline,
) ).8)) around 150,000 instances are utilized total for fine-tuning. Other settings train ELG under the same fine-tuning setting, and the results are presented Table 12. It can be seen that ReLD also achieves better fine-tuning performance in both in-distribution data (100, 200, and 500) and nut-of-distribution data (1000).
20

---

Published as a conference paper at ICLR 2025
Table 12: Effects of fine-tuning on instances from Uniform(100, 500).
CVRP100 Gap
CVRP200 Gap
CVRP500 Gap
CVRP1000
Method
Gap
ELG
1.156% 1.895%
4.150%
8,527%
15.054%
ELG fine-tune
1.841 %
2.281%
5.631% %
ReLD
1.143% 1.148%
2.036% 1.675%
3.623% 1.952%
7.156%
ReLD fine-tune
3,947%
I RELD BENEFITS FROM MORE DECODER LAYER
To explore the potential gains of further increasing decoder capacity, we introduce ReI.D-Large, which stacks an additional decoder block on top of the original ReLD decoder while preserving the property of static keys and values.
In specific, the original ReLD decoder can be viewed as a transformer block with single query. We stack another single query block top of the original one further transform the query vector de obtained from Eq. (9): 2e = MHA((q- (qc. He, H₂) + qe, 9' = 2e + FF())). The transformed q. will be used input the compatibility layer. To minimize the additional memory cost, the new block shares the same cached keys and values used in Eq. (11) (i.e., share the W WV parameters with the MHA module Eq. (11)). To maintain the total number of transformer blocks consistent with the original ReLD, we reduce the number of encoder blocks in ReLD-Large to 5.
The results presented in Table 13. Both models 100-trajectories with instance augx8 during inference. Notably, these experiments are conducted on different hardware than specified in the paper, resulting ReLD's runtime differing from the values reported Table 3. It can observed that increasing the decoder's 's complexity further enhances model performance across all sizes, albeit with greater computational overhead.
Table 13: Results of stacking additional layer in the decoder.
CVRP100
CVRP200 Gap (time)
CVRP500 Gap (time)
CVRP1000 Gap (time)
Method
Gap (time)
ReLD
0.959% (2.16m)
1.654% (0.1 Im)
2.975% (0.48m)
6.757% (1.5 1.95m)
LeLge
0.891 % (3.6 (3.60m)
1.527% (0. 16m)
2.678% (0.73m)
6.265% (2.89m)
21


Reviews:
[{"review_id": "ITPVTfAgDM", "reviewer": "Reviewer_SfnF", "summary": "This paper presents an analysis of light decoder-based solvers for VRP, specifically addressing the challenges of generalization to out-of-distribution (OOD) problem instances. By identifying limitations due to the reliance on static embeddings, the authors propose a modified approach, ReLD (Rethinking Light Decoder), which incorporates identity mapping and a feed-forward layer to enhance the decoder’s capacity. The proposed model demonstrates improved OOD performance across a variety of VRP instances, narrowing the performance gap between light and heavy decoder approaches.", "questions": "How does ReLD manage complex or dynamic VRP constraints, such as real-time updates or varying demands?\nHow could larger decoder modifications enhance OOD performance?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper provides a detailed breakdown of the light decoder’s limitations in VRP, particularly the static embeddings’ burden on the encoder.\n\nReLD addresses an important need in VRP research generalization across problem scales. \n\nThe modifications retain the light decoder’s computational efficiency, which could be advantageous for applications needing faster routing solutions without the computational load of heavy decoders.", "weaknesses": "Limited Scalability for Large Instances: ReLD struggles to compete with heavy decoder architectures on very large instances, such as CVRP1000. This limitation suggests that ReLD’s current modifications might not be sufficient for all scales of VRP.\n\nThe proposed modifications are relatively minor adjustments. While effective, they lack substantial novelty within the machine learning field.\n\nWhile this paper makes a valuable contribution by revisiting the light decoder paradigm and identifying limitations in current architectures, its primary innovations are modest. The architectural modifications, though effective, are straightforward and may not sufficiently address scalability issues, particularly in very large instances or complex real-world VRP variants. Moreover, the method is not showing SOTA results on the biggest problem instances, which is assumed to be the main advantage of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4GLKx6g2Aj", "reviewer": "Reviewer_NKcN", "summary": "The paper revisits light decoder-based solvers for VRPs, recognized for their efficiency but limited in generalization to larger or varied problem instances. The authors attribute this limitation to the handling of static embeddings, which creates high information density in the encoder, overwhelming the simplistic decoder. To overcome these challenges, they propose an enhanced decoder structure, incorporating identity mapping and feed-forward layers to effectively boost the decoder’s capacity and improve generalization performance. The authors perform experiments to demonstrate that ReLD achieves better generalization performance on both in-distribution and out-of-distribution tasks, closing the performance gap with heavier decoders while maintaining computational efficiency.", "questions": "Besides the concerns raised in the weakness part, I have the following additional questions:\n\n1. In Table 5, please check whether all the numbers you are reporting are correctly documented. The bolded number in OVRPLTW and the bolded number in OVRPBLTW are either too big or too small and do not correspond to the reported gaps.\n2. the figure 1 could be further improved. E.g. the font size and the caption.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow\n2. A thorough empirical analysis is conducted to validate the potential limitation of current light decoder-based solvers\n3. A simple but effective modification is performed to improve the decoder part of the current decoder-based solvers\n4. Experiments are conducted on many datasets covering different distributions, problem sizes, and problem classes.", "weaknesses": "The analysis in this paper is largely 'end-to-end,' with a strong reliance on empirical results presented towards the conclusion. Several concerns regarding the encoder and decoder architectures are raised, and it may be beneficial to adopt a more direct investigative approach into these components.\n\nAdditionally, the limitations of the current light decoder-based model are inferred from empirical experiments conducted solely on CVRP problems, focusing on LEHD and POMO models. A broader analysis including more models with both light and heavy decoder architectures would provide a more comprehensive foundation for the conclusions drawn.\n\nThe insights presented offer valuable guidance on improving the decoder architecture to address limitations associated with overly simplified decoders. This work implements a minor modification in this direction; however, the extent to which further increases in model complexity would yield additional performance gains remains uncertain. This issue points to a trade-off between model performance and efficiency, though an optimal balance between the two has yet to be determined.\n\nOverall, I appreciate the discussions and architectural considerations raised by this paper concerning VRP model design. Currently, I lean toward borderline acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uvhqLL42jJ", "reviewer": "Reviewer_p2Jk", "summary": "This paper studies the limitations of light decoder-based solvers for Vehicle Routing Problems (VRP). Modern RL methods for VRP typically employ light decoders for solution generation due to their efficiency. However, the authors think the light decoders may not capture the problem structure well. So they proposed Revised Light Decoder (ReLD) which modified the original light decoder and make it contain richer information.\n\nThe experiment results show that their framework can improve the current state-of-the-art methods.", "questions": "1. Do you have any results on the large-scale instances, e.g., CVRP-10000?\n2. Can this method be transferred to TSP or other CO problems? Do you have any preliminary results?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper approaches the deep learning for VRP problem from a new perspective: make the decoder contain richer information.\n2. The modification is not complicated and the results looks good.", "weaknesses": "1. The scalability issue still exists. There are no large-scale experiments conducted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qAuXYImf7i", "reviewer": "Reviewer_nQhH", "summary": "The authors first address the challenges of light decoder-based approaches for vehicle routing problems (VRPs). Because the traditional approach relies on static embeddings that must capture complex information within a single set of representations, it is difficult for the simplistic decoder to fully leverage this information, particularly in out-of-distribution (OOD) scenarios (such as generalizing to larger instances or different VRP variants). Enhancements to the decoder is thus introduced, such as adding an identity mapping and a feed-forward layer, to mitigate this issue. Experimental results demonstrate that this adjustment improves both in-distribution and OOD generalization performance, narrowing the gap between light and heavy decoder paradigms.", "questions": "These are not questions, but rather minor shortcomings related to the paper’s writing.\n\n(1) There are too many versions of ReLD introduced in the paper, and it is difficult to follow what each version represents.\n\n(2) Shouldn't Figure 1 also reflect the changes described in Section 3.2, Powerful Query? Currently, it seems to only illustrate the changes discussed in Section 3.1, Direct Influence of Context.\n\n(3) Table 5 contains several mis-copied numbers and incorrect placement of bold formatting.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors effectively highlight a key issue with static embeddings: the gap between the information needed for optimal decoder performance and the information stored in the context vector. This insight is both logical and significant, emphasizing a critical area for future improvements in this field. The research in this direction holds promising implications for advancing VRP solutions.", "weaknesses": "(1) The issue of the overly complex context vector is not directly addressed. The authors’ solution is somewhat simplistic, adding only extra structures to the decoder without any modification to the encoder or main inference process. This solution still has the same 'complex context vector' problem as described in \"Gap between Policy Formulations\" subsection (LINE 195). Given this limited change, the improvement in performance, such as in CVRP100, is also marginal.\n\n(2) One of the paper's main claims is that their method improves out-of-distribution (OOD) performance. However, the practicality of the approach based on zero-shot generalization is unclear. Why is it necessary for a model trained on N=100 cases to perform well on N=1000 cases? There are many established methods to address OOD problems, such as fine-tuning before inference, tree search or active learning during inference. The proposed modifications should ideally be evaluated in these more practical and realistic settings rather than in zero-shot scenarios.\n\n(3) With additional parameters in the decoder, the training burden likely increases. The training details are largely missing, particularly regarding how the proposed modifications affect training time and resources. The authors should also compare their approach to other potential modifications that increase parameters in the decoder, such as adding an additional decoding layer, in terms of training efficiency and resource requirements, as well as the solver performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PtVpTK5Zks", "reviewer": "Reviewer_EM2N", "summary": "This paper discusses the limitations of the Heavy Encoder-Light Decoder based model, which is commonly used in combinatorial optimization. Specifically, it addresses the problem where the encoder must embed all possible contextual information required during the decoding process into a single embedding, resulting in excessively high information density. It also highlights how the decoder fails to utilize this information. As a solution, the authors propose ReLD. The proposed method is validated through experiments on CVRP and VRP variants, demonstrating its effectiveness. In particular, the method showed superior performance compared to existing Light Decoder-based solvers when faced with out-of-distribution (OOD) problems.", "questions": "- How $q_c$ in Equation (11) is used?\n\n- What are $W_S^OW_S^V$ in Equation (8)? Does this imply performing value projection followed directly by output projection? As far as I know, such an operation does not exist in the original transformer. Could you provide a more detailed explanation regarding this part?\n\n- The modification presented in this paper adds an FF layer to the POMO decoder, and the decoders in models like POMO operate almost as many times as the number of nodes in an auto-regressive manner. Therefore, it is expected that the model modification proposed in this paper will increase both training and inference (optimization) times. However, in line 361 of the paper, it states that the additional step-wise running time is independent of the number of nodes and is computationally efficient. Could you please provide a more detailed explanation on this? If possible, it would be helpful to provide numbers on the changes in training and inference times due to the model modification.\n\n- How effective is the Distance Heuristic($-log(dist_i)$) in Equation 12? Is there any information on how the model performs if this heuristic is removed?\n\n- In Table 3, the CVRP100 gap for POMO augx8 is 1.004%, which shows a significant difference from the 0.32% gap for CVRP100 presented in the original POMO paper. Could you explain the reason for this discrepancy?\n\n- In Table 3, the addition of the ff layer appears to provide little benefit for CVRP100. Why does adding the ff layer to the decoder not contribute to performance improvement for a problem size 100?\n\n- As a minor comment, the font size in Tables 3 and 4 is too small.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper analyzes the limitations of the Light Decoder-based model and demonstrates the complexity of the encoded information and lack of generalization performance through experiments.\n\n- This paper proposes a novel approach by modifying the decoder to overcome the issues inherent in Light Decoder-based models, and demonstrates the superiority of the proposed method through experiments.  \n\n- In the CVRP generalization experiments, it showed promising results than existing Light Decoder-based models and performed well across various VRPs.", "weaknesses": "- There are unclear parts in the equations and content of Section 3 Methodology. It also does not match well with Figure 1(e). It is unclear whether $Q$ in Figure 1 (e) is the same as $q_c$ in Equation (11) or not. And It is difficult to understand the structure of the proposed neural network in Equation (7) to (11). For example, it is not clear how $q_c$ in Equation (11) is used. Relevant questions can be found in the Question section. \n\n- In the experiments, it is unclear whether the improvement in VRPs solution accuracy is due to the addition of the feedforward network itself or simply the increase in decoder parameters caused by adding FF. It seems necessary to conduct a comparative evaluation with a decoder where the parameters are increased equivalently without FF. Furthermore, a more solid logical explanation is needed on how the FF helps overcome the limitations of the light decoder.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)