UniteFormer: Unifying Node and Edge Modalities in Transformers for Vehicle Routing Problems
Authors: Dian Meng
Zhiguang Cao
Jie Gao
Yaoxin Wu
Yaqing Hou
Venue: NeurIPS 2025 spotlight ()
Keywords: Neural solver
Transformer
Reinforcement Learning
VRP
Primary area: optimization
TL;DR: We propose UniteFormer, a unified neural solver that supports node-only, edge-only, and hybrid input types through a single model trained via joint edge-node modalities.

Abstract: Neural solvers for the Vehicle Routing Problem (VRP) have typically relied on either node or edge inputs, limiting their flexibility and generalization in real-world scenarios. We propose UniteFormer, a unified neural solver that supports node-only, edge-only, and hybrid input types through a single model trained via joint edge-node modalities. UniteFormer introduces: (1) a mixed encoder that integrates
graph convolutional networks and attention mechanisms to collaboratively process node and edge features, capturing cross-modal interactions between them; and (2) a parallel decoder enhanced with query mapping and a feed-forward layer for improved representation. The model is trained with REINFORCE by randomly sampling input types across batches. Experiments on the Traveling Salesman
Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that UniteFormer achieves state-of-the-art performance and generalizes effectively to TSPLib and CVRPLib instances. These results underscore UniteFormer’s ability to handle diverse input modalities and its strong potential to improve performance across various VRP tasks.

UniteFormer: Unifying Node and Edge Modalities in Transformers for Vehicle Routing Problems
Dian Meng!.
Zhiguang Cao²
Jie Gao
Yaoxin Wu+
Yaqing Hou
School of Computer Science and Technology, Dalian University Technology (DUT)
2School of Computing and Information Systems, Singapore Management University
Department of Transport and Planning, Delft University of Technology
Depaartment of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology Key Laboratory of Social Computing and Cognitive Intelligence (DUT), Ministry of Education, China mengdi an@mail. dlut. edu. en, zhi thinaanccaooottlook com, J. Gao-1@tudelft.ni. wyxacc@hotmar www.chhhotmmil...mmmmcm com, houyq@dlut. edu. cn
Abstract
Neural solvers for the Vehicle Routing Problem (VRP) have typically relied on either node or edge inputs, limiting their flexibility and generalization real-world scenarios. We propose UniteFormer, unified neural solver that supports node- only, edge-only, and hybrid input types through single model trained via joint edge-node modalities. UniteFormer introduces: (I) mixed encoder that integrates graph convolutional networks and attention mechanisms to collaboratively process node and edge features, capturing cross-modal interactions between them; and (2) a parallel decoder enhanced with query mapping and a ferwad layer for improved representation. The model is trained with REINFORCE by randomly sampling input types across batches. Experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that UniteFormer achieves state-of-the-ard performance and generalizes effectively to TSPLib and CVRPLib instances. These results underscore UniteFormer's ability to handle diverse input modalities and its strong potential to improve performance across various VRP tasks.
Introduction
Vehicle Routing Problems (VRPs) are fundamental in logistics [21). navigation systems [2] and drone delivery [45), with significant theoretical and practical relevance. Recent advances have increasing interest in deep baaning-bbssed neural solvers for VRPs, offering strong generalization and improved computational efficiency over traditional exact and heuristic algorithms [14] 3 4 These
methods include both autoregressive models that learn construction policies from data [24 10 31 as
well as learning-based improvement solvers that enhance classical optimization procedures. However, many of these models, particularly construction- based ones, make an overly simplifying assumption: they rely solely on either node coordinates or edge distances as input. This leads to several limitations. First, training separate models for each input modality (node or edge) is inflexible and impractical for real-world applications. Second, switching between different input types requires retraining from scratch, incurring substantial computational costs. Third, such single-mode modality training neglects the complementary information between node and edge inputs, preventing the model from learning transferable features and reducing its capacity to discover high-quality solutions.
"Corresooniing author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

We argue that hybrid training with both node and edge information offers a more general and informative representation of the problem. While existing methods train only on single modality, our approach allows joint encoding and interaction across modalities, leading to better-informed policies and improved solution quality. To this end, we propose Unrmerrrmer, a unified neural solver for VRPs that supports hybrid training and generalizes across input modalities. Unlike conventional solvers, UniteFormer is trained once and can handle node-only, edge-only, or mixed edge-node inputs without retraining, This makes it more flexible and applicable to diverse real-world scenarios.
Specifically, UniteFormer consists of mixed encoder and a parallel-attention decoder. The mixed encoder includes two sub-encoders: edge-aware sub-encoder and node-focusee sub-encoder. The edge-aware sub-encoder integrates residual gated graph convolutional networks (GCNs) with self- attention to jointly process node and edge features, facilitating cross-modality interaction. The node- focused sub-encoder encodes node features independently using attention mechanisms, thereby further enhancing the ability to encode node information. Together, they produce rich global embeddings that capture complementary structural information. The decoder features a parallel architecture and nonlinear query mechanisms, incorporating query mapping and feed-forward (FF) layer to enhance its representational capacity. Our contributions are outlined as follows:
We present UniteFormer, the first unified neural solver capable of solving VRPs with node-only, edge-only, or hybrid inputs using a single trained model.
We introduce novel mixed encoder that combines residual gated GCNs with attention mechanisms, which can effectively and jointly process node and edge features to capture cross-modal interactions between them.
We design a decoder with a parallel-attention architecture and nonlinear query mechanisms, which enhance the expressiveness of the policy network.
Experiments on TSP and CVRP with all three input types show that UniteFormer achieves state-of-the-ane results. It also generalizes well to real-world TSPLib and CVRPLib bench- marks, and supports applications such as the Asymmetric TSP (Appendix (
2 Related Work
Modality-Specifii Neural Solvers for VRPs. Neural approaches have emerged as powerful al-
ternatives for solving VRPs by leveraging advances in deep learning and neural combinatorial optimization 3
35
32
47
26
27 17]. The introduction of pointer networks (42) and the Trans-
former architecture 40
laid the foundation for early neural VRP solvers such as in and (34).
1) Node-based models: Most existing neural solvers focus on node coordinate inputs. Notable examples include AM (22), POMO (24), and Sym-NCO (19), which significantly improved solution quality for classical VRPss More recent works have advanced training strategies. For instance, Bdeir et al. (T) Drakulic et al. [10), and Luo et al. [3] applied dynamic imput re-encoding during training to enhance generalization. Among them, Drakulic et al. (10] introduced Bisimulation Quotienting (BQ) to reformulate the MDP for more robust generalization. Luo et al. [3I] proposed light encoder heavy decoder (LEHD) model trained via supervised learning on partially reconstructed 100-node instances. These methods are all fundamentally built node coordinate inputs, capturing spatial structure through positional embeddings.
Edge-centric models are a more recent development. Kwon et al. (3 introduced MatNet, a matrix encoding network that operates on pairwise distance matrices, and demonstrated strong performance on the asymmetric traveling salesman (ATSP) and flexible flow shop (FFSP) problems. Lischka et al. (28) proposed GREAT, a sparse graph edge attention model that constructs high-quality solutions by exploiting sparse edge relationships. Building on this, Meng et al. (33) proposed an efficient edge-based EFormer, which further extends and optimizes edge-based problems and achieves excellent results on the TSP and CVRP.
2) Edge-based models:
3) Hybrid edge-node models: A smaller body of work explores models that jointly use node and edge information. Joshi et al. [18) proposed GCN- based edge probability predictor that uses both node coordinates and edge weights to guide beam search. Wang et al. [44] developed distance- aware reshaping method (DAR) that biases attention mechanisms using Euclidean distances. Zhou et al. [49] introduced an instance-conditional adaptive model (ICAM) that integrates both node and edge features to improve adaptability across instance sizes.

---

Input
Mixed Encoder
Linear
Inpur
Skip
Edge
Edge-aware Sub-enender
Decoder
Edge embedding
Query Mapping
Edge
GCN
MLP
MILA
Feed Forward
Attention
Self-attention
Graph embodding Node embeddi.
Add
heud Attention
Vode
Node-focused eec-enc
Q
Mask &
embedding
K
MHA
Multi-Head
Feed Forward
Figure I: Overview of the UniteFormer framework.
Unified Neural Solvers for VRPs. Unified models that generalize across VRP variants have gained attention due to their versatility and practicality. Wang and Yu (43) proposed a multi-task neural solver using multi-armed bandit framework train across multiple combinatorial optimization problems. Drakulic et al. [9] introduced GOAL,, supervised learning-based agent capable of solving diverse COPs. Within the VRP domain, Ruis al. [37] used attribute composition for zero-shot generalization across multiple VRP variants. Liu et al. [29] extended the reinforcement learning-
POMO model multi-task setting (POMO-MTL), and Zhou et al. (50) further proposed MVMOE, a mixture-of-expen model to improve generalization. Building on this, Liu et al.. (30] proposed curvature- aware pre-training framework that effectively improved their performance. Federico et al. [5] introduced RouteFinder, modular baseline framework for VRP variant modeling. Our work aligns with this line of research but focuses on input-modaligg unification rather than task-level generalization. UniteFormer is the first model that simultaneously processes VRPs defined by node, edge, or hybrid representations in single framework, offering strong generalization, improved efficiency, and broad applicability to real-world VRPs.
UniteFormer
Transformer-batt neural VRP solvers typically adopt light decoder architectures 22 24 where the decoder uses static node embeddings keys and values throughout the attention layers. In contrast, we replace these static embeddings with two context-aware embeddings that encode both edge relationships and node coordinates, and process them in parallel within the decoder. To effectively encode heterogeneous input modalities, we introduce a novel mixed encoder architecture that combines residual gated GCNs with attention mechanisms. The mixed encoder includes two sub-encoders: an edge-aware sub-encoder and a node-focused sub-encoder, collaboratively processing node and edge features capture cross-modal interactions between them. In addition, the parallel-attention decoder with query mapping and feed-forward layer to form our proposed UniteForme: The overall architecture of UniteFormer' is illustrated in Figure [ In the following, first present three input modalities in UniteFormer, then introduce the two sub-encoders of the mixed encoder detail, and finally report the specific implementation of the decoder.
enhance
3.1 Input Modalities in UniteFormer
VRP instance is defined over graph G= = (X, F). where X = (x denotes the nodes (with To as the depot), and e, E E represents the edge between nodes and zy. UniteFormer

---

Edge Features
Node
Edge
Node
Edge Features
Node
Fentures
Features
Features
Features
Mixed-Seure
Mixed-Score
Mixed Score
MHA
MILA
MILA
MHA
M
MHA
Residual Gated
Residual Gated
Residual Gated
GCN
GC.N
GCN
Feed Forward
Feed Forward
Feed Forward
MLP
Self-Attention
Add Norm
Self-Attention
Add & Norm
Self-Attention
Add Norm
graph encoded
embedding
graph encoded
node encoded
graph encoded
node encoded
Decoder
Decoder
Decoder
Edge
Node
Noge
(a)
(b)
(0)
Figure 2: Three input modalities for UniteFormer: (a) Edge-only input. (b) Node-only input. (c)
Hybrid input. The Mixed Encoder includes: Edge-aware (left) and Node-focused Sub-encoder (right).
supports three input modalities: edge-only imput, where only edge weights E are provided; node-only input, where only node coordinates X are provided; hybrid input, where both node coordinates X and edge weights E are available.
The three input configurations are shown in Figure Different input types activate different branches of the edge-aware uub-encoder (left) and the node-focused sub-encoder (right). A single unified model trained, with encoder components dynamically adapted to each input type. Specifically, Edge-only input (Figure [(a)): The node-focused sub-encoder is disabled (i.c., replaced with zero embedding), and only the edge-aware sub-encoder processes edge features; Node-only input (Figure bb)): Without edge weights, node features are passed to the GCNs directly, while the edge features are set to zero embeddings. Hybrid input (Figure [(c)): Both node and edge features are used. The mixed-score Multi-Head Attention (mixed-score MHA) is bypassed, and the GCNs receive the raw edge and node features.
3.2 Edge-aware Sub-encoder: Efficient Fusion of GCNs and Attention Mechanisms
To simultaneously capture edge and node information, we propose a novel sub-encoder architecture, ie., the Edge-aware Sub-encoder, that integrates GCNs with attention mechanisms. When edge information is provided, we apply mixed-score MHA block to derive intermediate node features. Across all three input modalities, we then apply residual gated GCNs to jointly process edge and node features in unified representation space. Finally, we introduce an additional self-attention layer, which proves especially effective in edge-based settings.
Mixed-Score Attention Layer. Inspired by [23 we adopt multi-head mixed-score attention mechanism to encode the edge weight matrix. This module follows the structure of standard Transformer attention [40], but replaces the traditional scaled dot-product computation with mixed- score formulation (see Appendix A). Inputs to this block include: zero vector hg. a randomly selected one-hot vector ht from predefined pool, and the edge weight matrix Dij. This setup allows dynamic embedding generation and facilitates instance-level augmentation by feeding the same instance multiple times with varying vector combinations. The zero vector can optionally be replaced by another one-hot vector, though we default to using the zero vector. The encoded relation matrix h computed only when edge inputs present:
h NORM(h, mixeed-scoreMHAA(n h,, D:y)),
(1)
h PP) NORM(6. FF (P))))))))
(2)
where mixed--scoreMHAA. denotes the mixed-score attention layer, FF(-) is feed-forware network with one hidden layer and ReLU activation, and NORM(-) denotes batch normalization [16]

---

Residual Gated Graph Convolution Layer. We next feed node and edge features into residual gated GCNs. Node coordinates 2; are embedded as h-dimensional vectors. The edge weight matrix Dij and the edge adjacency matrix by are embedded as á -ddimensional vectors:
= w + bi, B, Di + b2 |w0 O.y
(3)
(4)
where wi IRA, w2, w3 E R bj. b2 are biases, and || denotes vector concatenation. The input node and edge embeddings for the GCN are adaptively initialized according to input types. Particularly, 1)
Edge-only: vf ( el B.y 2) Node-only: vf = a4, ei = he: 3) Edge and Node: yf 0s.
el Big. We denote node and edge embeddings at layer as y and ety, respectively. Following (6).
we apply ReLU activation and residual connections to obtain the next-layer embeddings:
aclls)
vt 5t ReLU(NORM(W''s 0i W295)), with 0i. = E
jul - (5)
ReLUUNORM((Wd Winl WobhD),
where W are learnable weight matrices, a is the sigmoid function, E is a small constant for nu- merical stability, and @ denotes element-wise multiplication. This formulation enables anisotropic information diffusion on graphs by incorporating learned edge attention maps oty, To further process the node embeddings, we apply the MLP the GCN output v yielding values m MLP( constrained to [0. 1)2.
Self-Attention Layer. To enhance the model's capacity for global context encoding, introduce an additional self-attention layer after the MI.. This is particularly important in the edge-only setting, where the model's 's ability to propagate and transform information across the graph:
sub-encoder is disabled. In such cases, this layer significantly improves the
7 self-attention(m"²)
where m² is the MLP output, and h is the final output of the edge-aware sub-encoder. The detailed computational process in self-attention layer provided in Appendix
3.3 Node-focused Sub-encoder: Expressive Encoding of Node Information
The edge-aware sub-encoder, which is built on GCNs and augmented with a self-attention layer for encoding, offers significant boost for edge-based input. However, it falls short in handling node features compared to the conventional encoder mechanism (24). Therefore, we introduce the classic attention mechanism (i.e., Mocusfd Sub-encoder) to make up for this deficiency, which can effectively improve the performance of node-based input. The node-focused sub-encoder consists of L stacked layers, each comprising two sublayers: multi-Heaa attention (MHA) sublayer and feed-forward (FF) sublayer. Each sublayer incorporates residual connections [13 and layer normal-
ization [16). Let 1. denote the embedding of node i layer and let 17()) (M
(1) ./ ,..., ,....... (2)
represent the node embeddings at layer l. The forward computation at the 1-th layer is given by:
R NORM (N MHA (1-1) (N--),H(((-))
-H((-1))
(8)
( NORM (A.9 + FF (R())).
where MHA(-) denotes the multi-head attention, FF(-) feed-forward network, and NORM(-) applies layer normalization. This structure allows the sub-encoder to capture complex dependencies between nodes in a permutation-invarial manner. (L)) represents the final output of the L-th attention layer. Specifically, when the input consists of edges only, the sub-encoder is deactivated, and its output set as h (0);; when the input includes nodes, the output is taken h (L).
3.4 Decoder: Garallel-Attettiin Decoding with Enhanced Query Representation
critical component of the decoder is the context query vector q, which is used to compute attention scores over node embeddings and generate the probability distribution for the next node. In prior
5

---

works, is often constructed as linear combination of node embeddings, which limits its represen- tational capacity due to its inherent linearity [15]. To better capture contextual dependencies, we design decoder architecture with two key enhancements: (1) a parallel-attention architecture that separately computes attention scores using two sets of encoded embeddings, and (2) a nonlinear query mechanism that increases the expressive power of the query vector. Specifically, we apply query mapping and a feed-forward network with residual connections following the MHA layers.
Parallel-Attention Decoding. The edge- aware sub-encoder and node-focused sub uubenncoder produce two global embeddings, denoted h and hy, where the superscripts M and N indicate the edge-aware and node-focused encoding paths, respectively. During decoding, these embeddings are processed in parallel to obtain the decoder context vectors decoding step I, given by H. [hr h and H [hr ). These vectors are used to form temporary queries:
gM = W. N + W h.M.
(10)
q N W + h
(11)
nTh +
(12)
where W.M. W WN and W are learnable matrices that transform the start node embeddings hM, hy and current node embeddings h, &&,, respectively. Next, apply MHA (4 separately to each set of context embeddings to obtain two intermediate outputs:
MM MHA(q, A.M (.").
(13)
A MHA(q. K. v.))
(14)
where MM, w. and N.N V. are the keys and values derived from h and h respectively. These outputs are linearly projected and aggregated:
A WSM AM W.AA..
(15)
where W&M and W are learnable matrices.
Query Mapping and Feed-Forward Layer. To further enrich the query representation, we intro- duce a query mapping transformation and a feed-forward layer with residual connection:
g' = A + QMT(c),
(16)
/ = + FF(g).
(17)
where QMT(-) is linear projection that maps g to the same dimensionality as A?, defined as:
QMT(g) JQMTq q.
(18)
Here, 8QMT is learnable weight matrix. Given the final context vector A we compute a score 7 for each node using masked single-head attention mechanism:
+ Vd,
C -anh
j unvisited
(19)
-0,
otherwise
where de is the dimensionality of the key vectors, and C' is scaling constant. The final selection probability for node j computed via the softmax function:
= softmax(71))
(20)
At each decoding step, a node Ty is sampled according to Pý- Repeating this process for n steps yields the full solution = (Ti,..., T. In addition, we report the training algorithm in Appendix B
Experiments
We evaluate the performance of UniteFormer synthetic TSP and CVRP instances of varying sizes, under three input settings: node-only, edge-only, and hybrid. We also report results on standard real-world benchmarks from TSPLib and CVRPLib. The code is publicly available")

---

Baselines. 1) Traditional Solvers: Concorde 8
LKH3
14
OR-Took Tools 25 and HGS
41
2) Learning- bassd Solvers: MatNet (23), GREAT 28
POMO
(4
LEHD
[3 GCN-BS
[8]]
DAR [44] and ICAM 49). In order to compare POMO with UniteFormer on edge-base input, we re-implement POMO using edge-only inputs (denoted as POMO-edge). More detailed descriptions
of these baselines are presented in Appendix D
Problem Setting. We follow the standard data generation procedures from prior work 24 to create training and testing datasets for TSP and CVRP with = 20, 50, 100, where n denotes the number of nodes. The problem setups and implementation details are presented in Appendix C
Model Setting. The edge-aware sub-encoder consists of one layer of mixed-score MHA, three layers of GCN and MLP, and one self-attention layer. The node-focused sub-encoder consists of three attention layers. In each attention layer, the head number of MHA is set to 16, the embedding dimension is 256, and the feed-forward layer dimension is set 512.
Training and Inference. We use the REINFORCE algorithm [46). training each model for 1,010 epochs with 100,000 instances per epoch. The Adam 20] optimizer is used with an initial learning rate of 4e- and weight decay is set to le-6. We adopt the POMO inference algorithm (24) and report both the optimality gap and inference time. A separate set of 10,000 uniformly generated instances is used for testing. All experiments were conducted on a single Tesla V100-SXM2-32GB
GPU. More experiment setup details are presented in Appendix D
4.1
Experimental Results
We train a single unified model capable of handling three input types: edge-only, node-only, and hybrid input. Table reports the performance of UnimeFormer uniformly distributed TSP and CVRP instances across various problem sizes and input modalities. UniteFormer consistently outperforms existing learning-basee methods in both greedy (x1) and instance-augmented (x8) inference, while maintaining competitive inference times. Additionally, following MatNet [23). we also report results under large-scale augmentation (x128) for edge-based input.
TSP. For edge-based input, UniteFormer significantly outperforms both POMO-edge, MatNet and GREAT across all sizes studied. Notably, its performance with x8 augmentation exceeds that of MatNet's x128 augmentation, highlighting the efficiency of the UniteFormer. For node-based input, UniteFormer achieves superior results over node-based neural solvers, including POMO and even the strong LEHD model, in both greedy and x8 inference. For hybrid edge-node input, UniteFormer also surpasses methods such as GCN-BS, DAR, and ICAM across all scales studied. The advantage is particularly evident on TSP100, where UniteFormer achieves the lowest optimality gap of just adge-based UniteFormer
0.0589% among all neural baselines in Table I Furthermore, outperforms not only node-based models like POMO, but also hybrid models like DAR and ICAM, demonstrating its strong generalization and representational capacity.
CVRP. Similarly, for CVRP, UniteFormer exhibits robust performance across all input types. In the edge-based setting, UniteFormer outperforms both POMO-edge and MatNet in greedy and instance-augmented inference. Its performance with x8 augmentation even exceeds MatNet's x128 augmentation results. In the node-based and hybrid settings, UniteFormer again achieves the best results among all compared neural solvers. Specifically, on CVRP100, the hybrid-input version of UniteFormer achieves the lowest average optimality gap of 0.5963%. Notably, in the edge-only setting. UniteFormer even surpasses several node-basee or hybrid methods, including POMO, DAR, and ICAM. These results comprehensively demonstrate the effectiveness, robustness, and versatility of UniteFormer across a range of problem sizes and input modalities.
4.2 Ablation Study
Edge only vs. Node only vs. Edge and Node only vs. UniteFormer. Table 2 presents the results of our ablation study comparing UniteFormer with three training variants. test time, we evaluate models under three input configurations: Input-edge (only edge features are provided). Input-node (only node features are provided), and Input-XE (both edge and node features are available). The first variant, denoted w.o. UF-Edge, is trained exclusively with edge inputs. The second variant,
7

---

Table 1: Experimental results on TSP and CVRP with uniformly distributed instances. The results of methods with asterisk (#) are directly obtained from the original paper. BS: Beam search, BS*: Beam search and shortest tour heuristic. UniteFormer-E: E: Our UniteFormer takes edge as input; "-X": the UniteFormer takes node as input: "XE': the UniteFormer takes edge and node as input.
TSP20
TSP50
TSPI00
Method
Len.
Gap(%)
Time(m)
L.en.
Gap(%)
Time(m)
Lenn
Gap(%)
Time(m)
Concorde
3.831
0.000
4.43
5.691
0.000
23.53
7.763
0.000
66.45
LKH3
3.831
0.000
2.78
5.691
0.000
17.21
7.763
0.000
49.56
OR-Tools
3.864
0.864
1.16
5.851
2.795
10.75
8.057
3.782
39.05
POMO-edge
3.837
0.164
0.10
5.719
0.482
0.24
7.919
2.003
1.34
Ma(Net(xI)
3.832
0.044
0.11
5,709
0.303
7.836
0.940
0.52
MatNet(x8)
3.831
0.002
0.22
5.694
0.050
1.24
7.795
0.410
5.28
edge
M2)N
3.831
0.000
5.71
5.692
0.013
16.47
7.776
0.170
60.11
GREAT(x1)#
7.850
1.210
2.00
GREAT(x8)#
7.820
0.810
18.00
HiiteFormer-E(xl)
3,831
0.020
0.11
5.697
0.095
0.32
7.789
0.332
1.61
UniteFormer-F(x88
3.831
0.000
0.22
5.692
0.004
1.05
7.770
0.086
5.12
MhiteFormer-E(x1222
3.831
0.000
2.74
5.691
0.000
19.67
7.765
0.019
65.21
POMO(x))
3.831
0.018
5.698
0.119
7.792
0.364
1.03
POMO(x8
3.831
0.001
0.11
5.693
0.024
0.45
7.774
0.142
2.01
LEHD Greedy
3.867
0.961
0.14
5.721
0.519
0.24
7.808
0.577
1.37
mode
UniteFormer-X(xi)
3.831
0.011
0.11
5.696
0.072
0.32
7.788
0.316
1.62
UniteFormer-X(ctt
3.831
0.000
0.22
5.692
0.004
1.04
7.770
0.085
5.15
GCN
3.855
0,650
0.25
5.901
3.678
1.21
8.413
8.373
6.25
GCN-BS
0.128
0.81
5.710
0.317
7.931
17.73
edgetnode
GCN-BS*
3,831
0.000
21.25
5.694
0.041
37.63
7.869
58.34
DAR(xI)
3,831
0.021
0.08
5.702
0.181
7.803
0.512
1.12
DAR(x8)
3.831
0.001
0.12
5.694
1,040
0.52
7.779
0.201
1.72
ICAM(x1)
3.831
0.022
0.07
5.701
0.172
0.22
7.806
0.55
0.99
ICAM(x8)
3,831
0.002
0.11
5.694
0.417
0.48
7.780
0.22
1.34
UniteFormer- XE(xl)
3,831
0.009
0.11
5.695
0.055
0.32
7.782
0.243
1.62
UniteFormer-XE(xe
3.831
0.000
0.22
5.692
0.003
1.06
7.768
0.059
5.19
CVRP20
CVRP50
CVRP100
Method
Len.
Gap(%)
Time(m)
Len.
Gap(%)
Time(m)
T.en.
Gap(%)
Time(m)
LKH3
6.117
0.000
2.15h
10.347
0.000
15.647
13.46h
HGS
6.112
-0.079
1.48h
10.347
-0.001
4.67h
15,584
-0.401
6.54h
OR-Tools
6.414
4.863
2.37
11.219
8.430
19.35
17.172
9.749
2.61h
POMO-edge
0.700
0.12
10.525
1.725
15,943
1.53
Ma(Net(xI)
6.172
0.907
0.12
10.787
4.253
0.21
16.280
4.401
1.02
MatNet(x8)
6.146
0.469
0.58
10.635
2.787
1.23
16.117
3.356
4.65
edge
Ma(Net(x128)
6.131
0.229
9.93
10.538
1.847
17.93
15.989
2.530
69.05
UniteFormer--((I)
6.146
0.486
0.06
10.471
1.204
0.56
15.868
1.416
1.95
UniteFormer-F(xxl F(x8)
6.125
0.140
0.23
10.416
0.668
1.29
15.766
0.765
6.01
UniteFormer-E(xIl
6.119
0.036
3.47
10.387
0.384
19.44
15.705
0.374
76.43
POMO(x1)
6.160
0.698
0.06
10.533
1.799
15.837
1.216
0.64
POMOix8)
6.132
0.254
0.20
10.437
0.875
0.48
15.754
0.689
2.11
LEHD Greedy
6.462
5.647
0.07
10.872
5.075
0.18
16.217
3.648
0.55
node
UniteFormer-X(xl
6.145
0.454
0.06
10.472
1.210
0.56
15.856
1.335
1.95
UniteFormer X(x88)
6.126
0.155
0.22
10.419
0.694
1.26
15.753
0.672
6.05
DAR(xI)
6.161
0.715
0.08
10.537
1.842
0.19
15.906
1.659
1.02
DAR(x8)
6.132
0.240
0.13
10.441
0.907
15.783
0.873
2.23
edge+node
ICAM(xI)
6.160
0.703
0.08
10.502
1.504
0.13
15.955
1.972
0.62
ICAM(x8)
0.246
0.12
10.439
0.886
15,833
1.192
1.77
6.143
0.430
0.06
10.465
1.139
0.56
15.837
1.219
1.95
UniteFormer-XE(66)
1.6
0.146
0.22
10.415
0.660
15.740
0.596
6.05
w.o. UF-Node, is trained only with node inputs. The third variant, w.o. UF-XE, trained solely on combined edge-node node inputs. In contrast, our full UniteFormer model is trained using hybrid strategy, where the input type (edge, node, or both) is randomly selected for each batch during training. As shown in Table each variant performs well on its respective training input type but shows significant performance drops on other types. contrast, UniteFormer consistently performs well in all input settings, demonstrating its ability to generalize effectively regardless of the input

---

Table 2: Ablations of three input variants of UniteFormer on uniformly distributed instances.
w.s. UF-Edge Time((n)
w.o. Uo-N
w.u. UF-XE
Unitel'urmer
TSPS0
Len.
(l)(%)
Lon.
Gap(%)
Time(o))
Gap(%) Timeta))
Len.
Gap(%) Timo(())
Concorde
5.691
0.000
23.53
5.691
0.000
23:53
5.691
0.000
23.53
5.691
0.000
23.53
inpur-cdgetx()
5.694
0.041
0.32
11.922
109.479
0.32
12.349
116.976
0.32
5,697
0.095
0.32
input-odgetx8)
5.692
0.002
1.05
10.033
76.278
1.05
10.161
78.524
1.04
5.692
0.004
1.05
input-nodo(xt)
8.424
48.010
0.32
5.698
0.121
0.32
5,951
4.566
0.32
5.696
0.072
0.32
input-node(x8)
7,473
31.293
1.04
5.692
0.011
1.05
5,801
1.929
1,05
5,692
0,004
1.04
impui (E(xl)
6.620
16.316
0.32
5.726
0.604
0.32
5.695
0.069
0.32
5.695
0.055
0.32
input-XE(x8)
6.225
9.370
1.04
5.696
0.085
1.04
5.692
0.003
1.04
5.692
0,003
1.04
CVRP50
Len.
(ap(%)
UF-EEdge
Timo(r))
Len.
Gap(3t)
Node
Timo(m))
Len.
Gap(%)
UF-XE
Time(o))
Len.
Unitel'ormer
Gap(%)
(Tmm(
[.KH3
10.347
0.000
8.52h
10.347
0.000
8.52h
10.347
0.000
8.52h
10.347
0.000
8.52h
inpur-edgetxl)
10.457
1.069
0.56
$2.755
216.567
0.56
28.768
178.041
0.36
10.471
1.204
0.56
input-adge(x4)
10.412
0.633
1,26
31.360
203.092
1.26
27,555
166.317
1.27
10.416
0.668
1.26
input-nodo(xI)
24.763
139.332
0.56
10.455
1.048
0,56
11,280
9.018
0.56
10.472
1.206
0.56
input-nodexx))
17,780
71.840
1.26
10.410
0.614
1.26
10.966
5.987
1.26
10.419
0.694
1.26
(nput-XE(<()
12.491
20.720
0.56
10.455
L,48
0.56
10.449
0,991
0.56
10.465
1.139
0.56
input-XE(xd)
11.576
11.877
1.26
10.410
0.614
1.26
0.577
1.27
10.415
1.26
Table 3: Experimental results on TSPLIB and CVRPLIB.
TSPLIB1-100
ISPLIB101-300
TSP30I-500
Method
Len.
Gap(5) Time(m)
Len.
Gap(%)
Time(m)
Len.
Gap(
Time(m)
[PP
19499.583
0.000
56902.800
0.000
35772.500
0.000
POMO-edge
26434.493
38.177
0.11
86680.094
52.557
0.13
66931.099 L.06
85,899
0.24
MaiNet(xI)
20222.358
4.948
0.09
63182.822
9.061
0.19
50811 I. 1.844
41,948
0.28
MatNet(x8)
19748.707
2.119
0.16
61892.651
7.426
0.26
49611 1.249
38.678
0.37
odge
UniteFoormer-
20263.171
4.419
0.09
62497.070
11.322
0.12
49688.931
38,359
0.21
UniteFormer- B(x8)
19723.757
1.621
0.17
589 18975
3,028
0.25
42414.251
18.308
0.35
POMO(x1)
19625,737
1.069
0.08
59779.102
3,405
0.11
48074.882
33,955
0.10
POMO08)
19552.937
0.781
0.14
59595.007
2.838
0.23
45171.99 .911
26.200
0.11
LEHD Greedy
19891.001
2.382
0.11
58443.261
2.382
0.24
39391 .629
10.630
0.32
mode
UniteForme-
20079.525
4,316
0.09
58632.537
2.678
0.12
39599.271
10,807
0.22
UniteFormer-Xtee
19549.664
0.614
0.18
57726.770
1.092
0.26
38983 657
9.252
0.35
DAR(x))
19767.780
1.981
0.08
58354.624 624
2.014
0.11
41488.965
15.856
0.21
edge+node
(AR(x8)
19616.985
1.123
0.14
57948.545
1.447
0.23
39834.717
12.376
0.33
ICAM(xI
19657.984
1.066
0.08
59456.423
3.125
0.11
41754.691
16.507
0.21
ICAM(x8)
19622.840
0.843
0.14
58512.789
2.004
40771 3396
13,923
UniteForee-
19916.707
2.585
0.10
58051.055
1.919
0.12
40213.122
12.482
0.21
UniteFormer-
19567,880
0.653
0.18
57848.545
1.238
0.24
39775.667
11.111
0.35
CVRPLIBI-100
CVRP101-300
CVRP301-500
Method
Len.
Gap(6)
Time(m)
Len.
Gup(%)
Time(m)
Len.
Gap(%)
Time(m)
OPT
915.574
0.000
33184.483
0.000
97160.000
0.000
POMO-edge
1787.383
94.693
0.21
61130.353
108.337
0.23
193349.248
135.174
0.45
MaiNet(x])
990.186
8.355
0.16
41257.808
27.962
0.25
119378.472
24.976
0.42
MatNet(x88
974.015
6.485
0.22
37060.391
12.766
0.32
111725. 107
16.338
0.68
adge
UniceFormes-(ox)
968.487
5.783
0.19
40601.853
23.299
0.25
112460.491
18.192
0.45
UnieeFormer-Exe))
942.392
3.040
0.23
36259.083
9.485
0.38
110828.859
14.657
0.72
POMO(x1)
980.137
7.893
0.11
36514.578
9.260
0.18
113101.594
17.037
0.35
POMO(x8)
953.564
4.727
0.22
36004.930 930
7.561
0.26
110642.211
14.488
0.45
LEHD Greedy
1411.705
5.517
0.28
43841,532
11.734
116158.490
15.194
node
UniteFormer- X(x)
953.203
4.266
0.19
35784.084
8.945
0.26
112799.944
13.897
0.45
UniteFormer-
934.185
2.116
0.22
3497 1.075
5.353
0.38
105541.708
7.855
0.73
DARixI)
959.278
5.060
0.18
35482.000 062
7.426
0.26
109347.025
0205
9.449
0.44
edge+node
DAR(x))
937.261
2.568
0.24
34990.418
5.530
0.37
104165.243
7.758
0.62
ICAM(x1)
960.942
5.272
0.17
38232,511
11.489
0.25
117786..10 2019
15.771
0.42
ICAM(x8)
940.882
3.003
0.24
35881.780
7.338
0.39
I 100088.66 655
10.823
0.67
UniteFormer- XF(x1)
951.386
3.994
0.19
36184.185
7.306
0.25
107.979981
8.79%
0.45
SuiteFormer-XE(x4
932.698
1.940
0.22
34989.507
5.146
0.38
104911.999
6.889
0.72
modality. This result highlights the strength of our unified training approach in producing a robust and versatile model.
Further architectural ablation studies of the three components of the UniteFormer architecture are reported in Appendix E These experimental results also demonstrate their positive contribution to the UniteFormer, proving the effectiveness and indispensability of each component.

---

4.3 Generalization
Table summarizes the results on real-world TSPLIB 36) and CVRPLIB 39
instances of various sizes and distributions. We categorize them into three groups by size: N01-100, N=101-300, and N=301-500. Generalization results show that the UniteFormer performs best on instances with no more than 100 nodes and slightly less effectively on 101-300 node instances. Overall, UniteFormer shows excellent generalization ability on both TSPLIB and CVRPLIB. For TSP, UniteFormer generalizes better with node-only input. For CVRP, it performs exceptionally well with hybrid input.
Additionally, to demonstrate UniteFormer's s strong generalization and scalability, we extend our investigation to the Asymmetric Traveling Salesman Problem (ATSP). Due to the asymmetric nature of ATSP, can naturally solve using the edge-based UniteFormer framework, which also exhibits superior performance. The detailed experimental results are shown in Appendix
5 Conclusion, Limitation and Future work
In this work, we propose UniteFormer, a unified neural solver that supports three input types through a single model trained via joint edge-node modalities. We propose mixed encoder that integrates GCNs and attention mechanisms to collaboratively process node and edge features, capturing cross-moda interactions. Furthermore, and enhance the decoder's ss representation ability by adding query mapping and nonlinear layers. Extensive experimental comparisons with other modality-specine models demonstrate UniteFormer's promising performance. Due to the efficiency and practicality of UniteFormer, we believe it can provide valuable insights and inspire follow-up work explore more powerful unified neural solvers for edge-node modalities.
Conclusion:
implement parallel decoding strategy
Limitation and Future Work: Although our UniteForrmrr performs well on all three input types, its heavy encoder results in high training and equipment demands, making large-scale problem training challenging. Trimming UniteFormer into a lightweight model for large-scale VRPs (48) is worthwhile direction for future research. Another promising future work is to extend UniteFormer to with joint modalities.
solve multi-task VRPs (5 5
Acknowledgments
This work was supported in part by the National Natural Science Foundation of China under Grant 62372081, the Young Elite Scientists Sponsorship Program by CAST under Grant 2022QNRC001, the Liaoning Provincial Natural Science Foundation Program under Grant 2024010785-JH3/100 the Dalian Science and Technology Innovation Fund under Grant 6024JJ12GX00 Projects of Basic Research under Grant 2023JJ1 1 CG002 and the 111 Project under Grant D23006. This research/project is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG3-RP-2000 202222-031..
the Dalian Major
References
[1] Ahmad Bdeir, Jonas K Falkner, and Lars Schmidt-Thieme. "Attention, filling in the gaps for generalization in routing problems". In: Joinl European Conference on Machine Learning and Knowledge Discovery in Databases. 2022, pp. 505-520.
[2] Irwan Bello et al. "Neural Combinatorial Optimization with Reinforcement Learning". In: 5th International Conference on Learning Representations, ICLR, Toulon, France, Workshop Track Proceedings. 2017.
[3] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. "Machine learning for combinatorial optimization: a methodological tour d' d'horizon". In: European Journal of Operational Research 290.2 (2021), pp. 405-42)
[4] Federico Berto et "RL4CO: an Extensive Reinforcement Learning for Combinatorial Opti- mization Benchmark". In: Proceedings of the 31 ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2025.
[5] Federico Berto et al. "RouteFinder: Towards Foundation Models for Vehicle Routing Prob-
lems". In: Transactions Machine Learning Research (2025). ISSN: 2835-8856.
10

---

[6] Xavier Bresson and Thomas Laurent. "Residual gated graph convnets". In: arXiv preprint arXiv:1711.0755 (2017).
[7] Jill Cirasella et al. "The asymmetric traveling salesman problem: Algorithms,, instance genera- tors, and tests". In: Workshop on algorithm engineering and experimentation. Springg.. 2001, pp. 32-59.
[8] William J Cook et al. The traveling salesman problem: a computational study. Princeton university press, 2011.
[9] Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. "GOAL: A Generalist Combinatorial Optimization Agent Learner". In: The Thirleenth International Conference Learning
Representatiinss ICLR. 2025.
[10] Darko Drakulic et al. "BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization". In: Advances in Neural Information Processing Systems, NeurIPS. 2023,
[11] Vijay Prakash Dwivedi and Xavier Bresson." "A Generalization of Transformer Networks to Graphs". In: AAA/ Workshop on Deep Learning on Graphs: Methods and Applications (2021). [12] Mouhcine Elgarej, Mansouri Khalifa, and Mohamed Youssfi. "Optimized path planning for electric vehicle routing and charging station navigation systems". In: Research Anthology on Architectures, Frameworks, and Integration Strategies for Distributed and Cloud Computing. IGI Global, 2021, pp. 1945-1967.
[13] Kaiming He et al. "Deep residual learning for image recognition". In: Proceedings of the IEEE conference on computer vision and pattern recognition. 2016, pp- 770-778.
[14] Keld Helsgaun. "An extension of the Lin- Hon-Kernighan--Hoee Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems". In: Roskilde: Roskilde University 12 (2017),
pp. 966-980.
[15] Ziwei Huang et al. "Rethinking Light Decoder-based Solvers for Vehicle Routing Problems". In: The Thirteenth International Conference on Learning Representations, ICLR. 2025.
[16] Sergey loffe and Christian Szegedy. "Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift". In: Proceedings of the 32nd International Conference on Machine Learning, ICML. Vol. 37. 2015, pp. 448-456.
[17] Xia Jiang et al. "DRoC: Elevating large language models for complex vehicle routing via decomposed retrieval of constraints". In: 13th international Conference Learning Represen- tations, ICLR. 2025.
[18] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. "An efficient graph convolutional network technique for the travelling salesman problem". In: arXiv preprint arXiv:1906.00 10020229066012227 (2019).
[19] Minsu Kim, Junyoung Park, and Jinkyoo Park. "Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization". In: Advances in Neural Information Processing Systems, NeurIPS. Vol. 35. 2022, pp. 1936-1944
[20] Diederik P. Kingma and Jimmy Ba. "Adam: A Method for Stochastic Optimization". In: 3rd International Conference on Learning Representations, ICLR. 2015.
[21] Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias. "Vehicle routing problem and related algorithms for logistics distribution: literature review and classification". In: Operational research 22.3 (2022), pp. 2033-2062.
[22] Wouter Kool, Herke Van Hoof, and Max Welling. "Attention, learn solve routing problems!"
In: the 6th International Conference on Learning Representations, ICLR. 2019.
[23] Yeong-Dae Kwon et al. "Matrix encoding networks for neural combinatorial optimization". In:
Advances in Neural Information Processing Systems, NeurIPS. Vol. 34. 2021, pp. 5138-5149.
[24] Yeong- Dae Kwon et al. "POMO: Policy Optimization with Multiple Optima for Reinforcement Learning" In: Advances in Neural Information Processing Systems, NeurIPS. Vol. 33. 2020, pp. 21188-21198
[25] Laurent Perron and Vincent Furnon. Or-tools.
https / developers google. com /
optimization/ 2023.
[26) Qi Li et al. "Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning". In: Proceedings of the 31th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2025.
11

---

[27] Zhuoyi Lin et al. "Cross-problens learning for solving vehicle routing problems". In: Proceed- ings of the Thirty-Thite Third International Joint Conference on Artificial Intelligence, IJCAI. 2024, pp. (958-6966
[28] Attila Lischka et al. "A GREAT Architecture for Edge-Bases linge-Based Graph Problems Like TSP". In: arXiv preprint arXiv:2408. 16717 (2024).
[29] Fei Liu al. "Multi-task learning for routing problem with cross-problem zero-shot general- ization". In: Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining. 2024, pp. 1898-1908.
[30] Suyu Liu et al. "A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver". In: International Conference on Machine Learning, ICML. 2025.
[31] Fu Luo et al. "Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization". In: Advances in Neural Information Processing Systems, NewrIPS. Vol. 36. 2023, pp. 8845-8864
[32]
Nina Mazyavkina et al. "Reinforcement learning for combinatorial optimization: A survey".
In: Computers & Operations Research 134 (2021), 105400.
[33] Dian Meng et al. "EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems". In: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI. 2025, pp. 8582-8590.
[34] MobammadReza Nazari et al. "Reinforcement Learning for Solving the Vehicle Routing Problem". In: Advances in Neural Information Processing Systems, NeurIPS. 2018, pp. 9861 9871.
[35] Yun Peng, Byron Choi, and Jianliang Xu. "Graph learning for combinatorial optimization: a survey of state-of-the-an art". In: Data Science and Engineering 6.2 (2021). pp. 199-141.
[36] Gerhard Reinelt. "TSPLIB-A traveling salesman problem library". In: ORSA journal on computing 3.4 (1991), 376-344..
[37] Frank Ruis, Gertjan J. Burghouts, and Doina Bucur. "Independent Prototype Propagation for Zero-Shot Compositionality" In: Advances in Neural Information Processing Systems, NeurIPS. Vol. 34. 2021, pp. 10641-10653.
[38] Quinlan Sykora, Mengye Ren, and Raquel Urtasun. "Multi-agent routing value iteration
network". In: International Conference on Machine Learning, ICML. 2020, pp. 9300-9310. Eduardo Uchoa et al. "New benchmark instances for the capacitated vehicle routing problem". In: European Journal of Operational Research 257.3 (2017), pp.
[39]
[40] Ashish Vaswani et al. "Attention is all you need". In: Advances in neural information process-
ing systems, NeurlPS 30 (2017).
[41] Thibaut Vidal. "Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood". In: Computers Operations Research 140 (2022), p. 105643.
[42] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. "Pointer Networks". In: Advances in Neural Information Processing Systems, NeurIPS. 2015, pp. 2692-2700.
[43] Chenguang Wang et al. "Efficient Training of Multi-task Neural Solver for Combinatorial Optimization". In: Transactions on Machine Learning Research 2025 (2023).
[44] Yang Wang et al. "Distance-Aware Attention Reshaping for Enhancing Generalization of Neural Solvers".. In: IEEE Transactions on Neural Networks and Learning Systems PP (July 2025).
[45] Zheng Wang and Jiuh- Huih-Bing Sheu. "Vehicle routing problem with drones". In: Transportation research part B: methodological 122 (2019), pp. 350-364.
[46] Ronald J Williams. "Simple statistical gradient-following algorithms for connectionist rein- forcement learning". In: Machine learning (1992), pp. 229-256.
[47] Yaoxin Wu et al. "Learning improvement heuristies for solving routing problems". In: IEEE transactions on neural networks and learning systems 33.9 (2021). pp. 5057-5069.
[48] Haoran Ye et al. "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, pp. 20284-20292.
[49] Changliang Zhou et al. iunstance-conditiones adaptation for large-scale generalization of neural combinatorial optimization". In: arXiv preprint arXiv:2405.0 00090 (2024). [50] Jianan Zhou et al. "MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of oixture-ofEExperts.. In: Forty-first International Conference Machine Learning, ICML. 2024.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims presented in the abstract and introduction of this article clearly
reflect the contribution of the paper and are consistent with the experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of our method is addressed in the conclusion, Limitation and Future (Section 5).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [NA]
Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Our experiments are reproducible, as we clearly articulate our methodology in the manuscript. In Section we provide the architecture of the main model, and in Section and Appendix
D we detail the experimental settings including parameters, optimizers, and other configurations.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: Due to certain corporate restrictions, we are unable to release the code at this time, but it will be made available publicly upon acceptance. The implementation methods and detailed descriptions of the experiments can be found Section 3 and Section 4 as well in Appendix Cand Appendix
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Posicccy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
www.c//ggieeeeeeee htt////ooebuissseeeeeeeee SusSSuubissss bolbbmmsssins sssisssssiccciyiii for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provided the all experimental settings in Section 4 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
The experimental results are obtained by testing set of 10,000 uniformly generated instances from different problems, and report relevant metrics, such path length and gap, to evaluate the performance. Our model follows the POMO training algorithm [24]. which has been subjected to t-test.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The GPU used in experiments is detailed in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have thoroughly examined the NeurIPS Code of Ethics to ensure that submission adheres to the anonymization requirements and does not include any identifying details that could compromise the double-blind review process.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
16

---

Justification: Both potential positive and negative societal impacts of our work are analyzed in Section [ and Appendix G
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [No]
Justification: The data utilize consists of node coordinates, detailed in Section 4 and Appendix C Additionally, the unified Neural Solver is employed to construct tours for VRPs. We assess that there significant risks of misuse associated with paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have cited the original paper of the assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
17

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: We will make our source code publicly available upon the acceptance this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
18

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, and non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM for what should or should not be described.
19

---

A Details of Attention Computation
A.1 Mixed-Score Attention
To incorporate external relational priors-such as graph adjacency or edge aettances-alonssiee content-based similarity scores, we replace each head's standard scaled dot-product attention with mixed-score attention mechanism, while preserving the remaining components of the Transformer's multi-head attention block (as in MatNet (23). The original scaled dot- not-product attention computes attention weights by applying SoftMax to the pairwise scaled dot- not-products of queries and keys and then uses those weights to form a weighted sum of the value vectors. By contrast, the mixed-score attention supplements these internal attention scores with externally given relationship scores for every query-key pair. Specifically, the mixed-score attention mechanism mixes the internal attention scores and the external relationship scores before passing them to the next "SoftMax" stage. Similar mixing strategies have been explored by (38) and [II..
Formally, by defining dimensions dy and d,, we compute the key k E Rd,, value Us E Rd, and query qi E IRd for each node by projecting the embedding hy:
Qi hi,
h; = =W U/ = W his
(21)
where we& E Rd W E Rd xd,, and W. E Rddxdd are learnable weight matrices.
Internal and External Scores: Afterwards, we compute the internal attention scores Shy by taking the scaled dot produrtsstts of each query-key pair and derive the external relationship scores Siz from the edge weight matrix Diy:
Sint ka dd
Sint E R
(22)
Si go Pij);
S E RR*
(23)
where Sigt denotes internal attention scores, S denotes the external relationship scores, Dij E Raxx encodes known relationship (edge weight matrix) between positions (i,j), and ge is an optional learnable scalar or nonlinear mapping applied element-wise.
Mixed Score via Element-Wise MLP: For each attention head h, we employ a compact two-layer perceptron føx : I I., parameterized by Φn (WT, bf. Wh, bb), to fuse the internal and external scores on an element-wise basis:
Smix ij
for (Sigi (ty' = whth a (WT [S STAT T + bt) + bz.
(24)
where a is the ReLU function, and Synis denotes the mixed scores.
Softmax Normalization:
Then, we perform softmax normalization on the mixed scores Styx
exp
Sunix
(25)
Crnix
Subsequently, the attention vector a is transformed into convex combination of the messages rj and the specific-head attention output 2/ is obtained:
z²=
1 = E Rd xdd,
(26)
j=1
A.2 Self-Attention
Self-attention is a mechanism that dynamically assigns weights to each position within sequence, capturing global dependencies by allowing each element in the sequence to interact with itself and other elements. We interpret the attention mechanism in (40] as a weighted message-passing algorithm between nodes in graph. The weight of the message value that node receives from
20

---

its neighbors depends on the compatibility of its query with the keys of its neighbors. Formally, we define dimensions dę and d, and compute the key Kę E R2 value v; E R2 and query qi R for each node by projecting the embedding h4:
q: W his
h = W. h4, vs = W h4,
(27)
where W R Rdd W E Rd xda and WV E RRda are learnable weight matrices. From the queries and keys, we compute the compatibility Way of the query qE of node i with the key k, of node j as the (scaled) dot product:
g kg
if adjacent to
Wij
Vol OC.
(28)
otherwise
From the compatibilities Wej, we compute the attention weights dij [0, 1] using a softmax function:
engy
Oij
Eje e"
(29)
After that, the vector M that is received by node is the convex combination of messages Uyt
Σ aizlz-
(30)
Finally, we normalize the vector h; and use the feed-forward sublayer to compute the node-by-node projection:
Mg = NORM (h: + +h)),
(31)
h = NORM (K: + FF (M)),
(32)
where, FF(.) is a feed-forward layer, and NORM(-) applies batch normalization. The feed-forward
sublayer computes node-wise projections using hidden (sub)sublayer with dimension du 512 and ReLU activation. We use batch normalization with learnable da dimdemmesia affine parameters bn and bbn The two sublayers are defined in detail as follows:
Fh ffff1 ReLU(W fh; + bf..0) bft.1
(33)
BN(h)) wh @ BN(()) + bbn.
(34)
Here, @ denotes the element-wise product and BN refers to batch normalization without affine transformation.
B Training Details
We adopt the same reinforcement learning framework as POMO (24), using the REINFORCE algorithm (46) train the UniteFormer. At each training step. we sample a set of solution trajectories [ .".T"", compute their corresponding rewards f(r'), and apply approximate gradient
ascent maximize the expected return L. The gradient of the objective L(() with respect to model parameters 0 is estimated as:
VoL(O) R DlUG)) - (*()) V log logpo(7"1s))
(35)
where 6' (ss) is baseline used reduce variance in the gradient estimate. Following common practice, we use a shared baseline defined as the average reward across the sampled trajectories:
8' (s) = bahaved (s) = f(r))
(36)
and the probability of trajectory
7¹ under the policy is factorized as:
M
po
8) II
po(af 8, aa.
(37)
1=2
where af denotes the action at step in trajectory T¹, and M is the length of the solution.
21

---

Table 4: Experiment Hyperparameters.
Hyperparameter
Value
Hyperparameter
Value
Model
Training
Embedding dimension da
256
Input choice &
cdge/nodeledge+node
Number of attention heads MA
16
Batch size
1024/256/64
Number of encoder layers L.
3
Optimizer
Adam
Number of GCN layers Lg
3
Learning rate (LR)
4e
Number of MLP layers Lm
3
Weight decay
le-6
K-nearest neighbors
20
LR scheduler
MultiStepLR
Feedforward hidden dimension d,
512
LR milestones
[901,1001]
Feedforward activation
ReLU
LR gamma
0.1
Tanh clipping E
10.0
Train data per epoch
100,000
Normalization
Batch
Training epochs
1010
C Implementation Details for TSP and CVRP
C.1
Problem Setup
Solving TSP instance with nodes requires finding the shortest loop that visits each node exactly once and eventually returns to the first visited node, where the distance between two nodes the Euclidean distance. We generate TSP instances following AM [22). where the coordinates of nodes are randomly and uniformly sampled from the unit square.
TSP.
CVRP. The CVRP instance involves customer nodes and one depot node, where the coordinates of the customer nodes and the depot node are uniformly sampled from the unit square. Each customer node has normalized demand & D, where & is sampled from the discrete set {1, 2, ..., 9} and the vehicle capacity D 30, 40, 50 for problem sizes N = 20, 50, 100, respectively. A delivery vehicle with unit capacity makes round trips starting and ending at the depot, delivering goods to customer nodes according their demands and replenishing inventory at the depot, where each customer node is only allowed to be visited once. Our objective is to determine the shortest feasible of routes that visits all nodes while respecting the vehicle's capacity constraint D.
C.2 Implementation Details
For TSP/CVRP instance G E}. the node features {x1, .... Σn are the -ccoorddinaess of the n nodes in the graph, and the edge features e(z,, Iz) E E are the edges between nodes and z; in the graph G. Our UniteFormer supports three input modalities: 1) Edge-only input, where only edge weights E are provided; 2) Node-only input, where only node coordinates X are provided; 3) Hybrid imput, where both node coordinates X and edge weights are available.
To formalize this, we introduce modality- function the {0, 2), where
0, edge-only input, d
1, node-only input,
(38)
2, hybrid input.
During training, we employ the REINFORCE algorithm to randomly select the at each batch. This stochastic modality sampling encourages the model to learn robust representations under all three input scenarios.
D Experimental Details for UniteFormer
D.1 Experiment Baselines
1) Traditional Solvers: For TSP, we use the non-learning solvers Concorde 8
LKH3 14), and
OR-Tools 25), which are known for providing strong results on TSP. Consistent with prior works (4
22

---

Table 5: Ablations of three key components of UniteFormer on uniformly distributed instances.
TSPS0
Len.
w.o. self-atiention (ap(%%
Time((n)
w.o. node Locused sub (la((%)
Time((n)
w.4. edge-aware aware sub E
Gap(%)
TTmm((n)
Len.
Uniteforrner Cap(%)
Timo(())
Conconde
5.691
0.000
23,53
5.691
0.000
23,53
5.691
0.000
23,53
5.691
0.000
23.53
I
5.699
0.126
0.32
5.697
0.097
0.34
6.402
12.490
0.32
5.697
0.095
0.32
input-edge(x8))
5,692
0.007
1.01
5.692
0.004
1.15
5.765
1.294
1.06
5.692
0.004
1.05
inpui-nade(xI)
5.697
0.098
0.31
5.695
0.069
0.34
5.6978
0.111
0.33
5.696
0.072
0.32
input-node(x8)
5.692
0.009
1.02
5.692
0.004
1.14
5.692
0.006
1.06
5.692
0.004
1.04
ioput-XE(xl)
5.695
0.068
0.31
5.695
0.054
0.35
5.697
0.105
0.35
5.695
0.055
0.32
input-XF(xx5
5.692
0.004
1.02
5.692
0.003
1.16
5.692
0.005
1.08
5.692
0.003
1.04
CVRP50
w.o. self-attention
w.o, mode-focused
w.o. edge adge-aware sub- Bi
UniteFoomer
Lon.
Gap(%)
Timo(or)
Len.
Gap(%)
Timotr)))
Len.
(ap(%)
Time((n)
Len.
Cap(%))
Time(m))
LKI13
10.347
0.000
10.347
0.000
10.347
0,000
8.52h
10.347
0.000
8.52h
input-edgetx))
T0:483
1,312
0.54
10:529
1.763
0.58
15.111
46,045
0.56
10:471
1.204
0.50
input edgee())
10.426
0.770
1.24
10.43
0.841
14.203
37.266
1.29
10.416
0.668
1.26
input-node(x()
10.490
1,379
0.54
10.544
1.909
0.58
10.677
3.192
0.56
10,472
1.206
0.56
input-node(xe)
10.421
0.721
1.24
10.461
1.103
10.537
1.835
10.419
0.694
1.26
()put-XE(x1)
10.470
1.192
0.56
10.531
1.781
0.59
10.660
3.028
0.56
10.465
1.139
0,56
input-XE(x8)
10.417
0.680
1.25
10.453
1.028
1.35
10.526
1.754
1.28
10.415
0.660
1.26
31). we calculate the performance gap relative to Concorde. For CVRP, we use the non-learning solvers LKH3 [4]. HGS 411. and OR-Tools [25] We calculate the performance gap relative to LKH3.
2) Learning-based Solvers: Edge-only input: We compare with the current state-of-the-art Mat- Net (23) and GREAT (28). both of which use edge relationships as input for the problems. Among them, MatNet is retrained and evaluated on symmetric instances according to the original model design. Since GREAT has not published the code and data, the results are taken from their paper. Additionally, to fairly compare POMO-based models with UniteFormer, we also re-implemented POMO using edge-only input (denoted as (0MO-edge), Node-only input: We use the public models of the classic bode-based POMO 24 and LEHD [3] for comparative testing. Hybrid input: GCN- BS [18), DAR (44) and ICAM [49] all use edge and node as model input. Since the codes of DAR and ICAM are unavailable, we re-implement and retrain DAR and ICAM according to the official settings, and the number of training epochs and data sets are consistent with our UniteFormer.
D.2 Experimental Hyperparameters
We report the hyperparameter details common across the main experiments in Table 4 In the table, "Input choice" indicates that during training we randomly select one of the three input modalities for each batch. We employ three layers for the GCN, the MLP, and the mode-focused sub-encoder. All normalization operations within the model are implemented using batch normalization [16).
E
Ablation Study of UniteFormer Architecture
Table reports ablation studies comparing UniteFormer against three structural variants to isolate the contributions of each component. One may ask: why incorporate self-attention into the odge-aware sub-encoder? Why disable the node-focused sub-encoder when edge-only input is used? And what if the edge-aware sub-encoder were to operate solely on edge features, ignoring node attributes?
To answer these questions, we design three ablations: edge-awan sub-encoder (denoted by w.o. self-attention). The second variant adds the node-focused sub-encoder, transferring temporary node features to it when edge is as input (denoted by w.o. node- focused sub). The third variant feeds only edge features into the edge-aware sub-encoder, setting node features to zero embeddings (denoted as w.o. edge-aware sub-E). Across all input modalities, each variant trails the full UniteFormer configuration, as shown in Table [5] These results confirm that (a) self-attention in the edge-aware encoder is crucial for capturing node interactions, (b) adding the node-focused sub-branch under edge-only input degrades performance, and (c) jointly leveraging both node and edge features yields superior representations. Overall, the ablation study demonstrates each component's positive contribution to the model and validates the effectiveness and design rationality of the UniteFormer architecture.
The first variant removes self-attention from the
23

---

Table 6: Experimental results on 10,000 instances of ATSP.
ATSP20
ATSP50
ATSP100
Method
Len.
Gap(%)
Time(m)
Len.
Gap(%)
Time(m)
Len.
Gap(%)
Time(m)
CPLEX
1.540
0.000
12.14
1.559
0.000
60.03
1.571
0.000
5.01h
Nearest Neighbor
2.010
30.390
2.101
34.610
2.140
36.100
Nearest Insertion
1.800
16.560
1.950
25.160
2.050
30.790
Furthest Insertion
1.710
11.230
1.840
18.220
1.940
23.370
LKH3
1.540
0.000
0.12
1.560
0.000
0.24
1.570
0.000
1.12
MatNet(XI)
1.548
0.533
0.06
1.580
1.350
0.15
1.622
3.242
0.62
MatNet(x8)
1.542
0.084
0.31
1.566
0.472
1.23
1.603
2.086
4.24
MatNet(x128)
1.540
0.012
4.72
1.561
0.144
16.55
1.590
0.934
61.03
UniteFormer(x1)
1.543
0.245
0.15
1.573
0.917
0.24
1.621
3.170
0.76
(nimer)o)))
1.540
0.043
0.36
1.564
0.339
1.22
1.600
1.841
5.07
UniteFormer(11222
1.540
0.001
4.01
1.561
0.129
18.09
1.585
0.880
1.32h
Asymmetric Traveling Salesman Problem (ATSP)
F1
Problem Setup
In the classic TSP, the objective is to determine tour over N nodes that minimizes the total round-trip distance. For any two nodes 2; and æ,, the edge distance satisfies d(r,, = d(zy, yielding an N x N symmetric distance matrix. To demonstrate UniteFormer's strong generalization and scalability beyond this symmetric setting, we extend our investigation to the Asymmetrie Traveling Salesman Problem (ATSP). In ATSP, one seeks the shortest Hamiltonian circuit in directed, weighted graph that visits each vertex exactly once and returns to the start. Unlike the classic TSP, the ATSP's distance matrix is non-symmetric, with edge weights satisfying (r,),,,,)) + (Iz.. 24). Thus, it must accommodate both directional and weight asymmetries.
Our edge-only UniteFormer framework naturally accommodates these asymmetric instances without modification and continues to exhibit excellent performance. Following MatNet's experimental protocol, we evaluate on tmat class ATSP instances that satisfy the triangle inequality and are widely used the operations-researc (OR) community [7). We solve three problem sizes (N=20, 50, and 100) and confirm that UniteFormer retains its robustness and scalability under the more general ATSP setting.
F.2 Experiment Results
Our UniteFormer is able to take edge-only information input and can be easily extended solve ATSP. We use randomly generated asymmetric distance matrices as input. Both the training and test datasets follow the data generation method of MatNet.
Table the performance of our trained model compared with other representative baseline algorithms 10,000 test instances of tmat class ATSP. For each method, we report the average tour length (shown units of 10") and the percentage gap relative to CPLEX's optimal solutions. One of the key basclines compared in the table is the MatNet, which is edge-based construction method designed for solving ATSP.
The results in Table demonstrate that UniteFormer consistently outperforms MatNet under both greedy inference (x and instance augmentation (x8, x 128) inference, while maintaining relatively reasonable inference times. In particular, on the largest ATSP100 instances, our UniteFormer attains a modest performance advantage, albeit with a slightly increased runtime. These experiments confirm that our edge-driven UniteFormmrr achieves competitive performance on ATSP, showcasing its extensive adaptability and strong generalization. Collectively, they validate the effectiveness of the UniteFormer architecture for broad spectrum of optimization challenges.
24

---

G
Broader impacts
The paper introduces UniteFormer, unified neural solver for VRPs that flexibly accommodates three distinct input modalities through joint edge-node training. This design significantly enhances the practicality of neural solvers for real-world applications. Moreover, the underlying techniques generalize beyond VRPs, opening the door to wide array of combinatorial optimization tasks.
Our experiments demonstrate that, compared state-of-the-art neural solvers trained single input modality, UniteFormer consistently delivers superior performance across diverse VRP variants. This unified approach not only streamlines training by eliminating the need for separate models modality but also reduces overall engineering complexity. Nonetheless, the heavy encoder underpinning UniteFormer demands substantial computational resources, which poses challenge for scaling to very large problem instances. Future work will focus on architecting more lightweight yet expressive models bridge this gap.
25


Reviews:
[{"review_id": "YUNpGVJilM", "reviewer": "Reviewer_fzsN", "summary": "This manuscript introduces UniteFormer, a novel neural solver designed to address the Vehicle Routing Problem (VRP) by integrating both node and edge modalities within a single model. This approach aims to enhance the flexibility and generalization of neural solvers in real-world scenarios by supporting node-only, edge-only, and hybrid input types.", "questions": "My concerns refer to weaknesses.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- **S1.** The paper presents a unified approach to solving VRPs by integrating multiple input modalities. The mixed encoder integrates graph convolutional networks (GCNs) and attention mechanisms to process both node and edge features collaboratively. The decoder's parallel architecture and nonlinear query mechanisms enhance the model's representational capacity.\n\n- **S2.** The experimental results demonstrate that UniteFormer achieves state-of-the-art performance on both TSP and CVRP tasks across multiple input modalities.\n\n**Weaknesses**\n\n- **W1.** The manuscript lacks relevant computational complexity analysis and efficiency experiments. The heavy encoder architecture results in high computational demands, which can limit the model's scalability to very large problem instances. It might be a concern for practical applications where resources are limited. \n\n- **W2.** The manuscript lacks a problem description and formalization. While the paper briefly mentions the setup for TSP and CVRP in the experimental section, it lacks a detailed description and formalization of the problems. This omission might make it difficult for readers to grasp how the model aligns with the specific requirements of the problem.\n\n- **W3.** The manuscript fails to analyze hyperparameter sensitivity. It can limit the model's practical application and scalability, as readers cannot evaluate the model's stability and reliability across various scenarios. A hyperparameter sensitivity analysis helps researchers and practitioners understand how different hyperparameter settings affect model performance, thereby enabling the selection of optimal hyperparameter combinations.\n\n- **W4.** The manuscript lacks publicly available code, which limits the reproducibility of the results.", "was_revised": true, "final_justification": "The authors have addressed my concerns.", "rebuttal": "Thank you for your constructive and valuable comments and suggestions. We address your concerns point-by-point as follows:\n \n>  **Q1: Computational complexity analysis.**\n\n**A1:** Thank you for raising this important point. We acknowledge that our encoder architecture in UniteFormer might be heavier and increase computational demands, particularly for large-scale instances. This design was motivated by the need to learn rich structural representations across multiple input modalities, which has shown strong empirical benefits in terms of solution quality.\n\nHowever, we would like to emphasize that UniteFormer is more practical in real-world scenarios due to its unified architecture: it can handle three different input modalities within a single model. In contrast, existing methods typically require separate training for each input setting, leading to higher cumulative training cost and reduced flexibility. UniteFormer's ability to generalize across modalities without retraining helps reduce overall training overhead and model maintenance cost, making it more efficient in deployment settings. \n\nIn terms of inference efficiency, our model achieves comparable inference time to baseline methods, as shown in **Table 1** of the main paper. In addition, we also explicitly acknowledge the computational trade-off in the original paper. In **Appendix G**, we have highlighted that reducing the computational footprint of UniteFormer while preserving its expressive power is an important direction for future work. We are dedicated to the design of more lightweight yet expressive encoder modules to improve scalability for large instances.\n\nWe appreciate your suggestion and will incorporate a formal complexity analysis and efficiency discussion in the final version to make these trade-offs more transparent.\n\n>  **Q2: Problem Description and Formalization.**\n\n**A2:** Thank you for your valuable feedback. We have provided the problem descriptions and formalizations in the paper (see **Appendix C**). Due to space constraints in the main text, we have already included the detailed problem descriptions and formalizations for both the TSP and CVRP in **Appendix C**, and referenced them in the **Problem Setting** subsection of the experimental section (see **Section 4**).\n\nWe acknowledge that a more explicit formulation in the main paper would improve clarity, especially for readers less familiar with these problems. If space permits in the final version, we will include a concise but formal problem definition in the main text to ensure that the model's alignment with the problem requirements is clearly understood.\n\n> **Q3: Hyperparameter Sensitivity.**\n\n**A3:** Thank you for your thoughtful suggestion. In this work, our primary focus is on analyzing the impact of the three input modalities and the architectural components of the proposed model. As such, we have conducted extensive ablation studies on both input types and architecture modules, which are presented in **Section 4.2** and **Appendix E**. \n\nFor hyperparameter settings, we follow the configurations used in strong baselines such as POMO and MatNet to ensure fair comparison. Therefore, we did not include a detailed hyperparameter sensitivity analysis in the initial submission. However, we appreciate the importance of evaluating model robustness across different settings. In response to your comment, we conducted a sensitivity analysis on hyperparameter $K$, which controls the number of nearest neighbors used in the KNN graph for the GCN modules. We tested values of $K = 10, 20, 30, 40, 50$ on TSP50, and found that $K = 20$ yields the best performance, with relatively stable results across the range. The results are summarized in the table below.\n\n| TSP50  | K=10  | K=20  | K=30  | K=40  | K=50  |\n| --- | --- | --- | --- | --- | --- |\n| input-edge | 0.0039% | **0.0036%** | 0.0045% | 0.0055%  | 0.0046%   |\n| input-node | 0.0044% | **0.0038%** | 0.0048% | 0.0054%  | 0.0043%   |\n| input-XE | 0.0029% | **0.0026%** | 0.0033% | 0.0035%  | 0.0031%   |\n\nWe will include this analysis in the final version and additionally plan to expand the hyperparameter sensitivity study to better support practical deployment and reproducibility.\n\n> **Q4: Reproducibility.**\n\n**A4:** Following common practice, we will release the full source code and all trained models upon acceptance of the paper. As external links are not permitted during the rebuttal phase, we promise to include links to the public code in the final version."}, {"review_id": "aHKMZPMPdD", "reviewer": "Reviewer_HhBh", "summary": "The paper proposes a novel neural network architecture that can take different kinds of inputs (edge only, node only, or both) for solving routing problems.", "questions": "1. What's the model size of UniteFormer compared to the other neural solvers used as baselines?\n\n2. On which instance size UniteFormer is trained on? For instance, is it trained on TSP-n and then evaluated on TSP-n?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The idea of training a unified network to be accept different inputs is novel as far as I know. The trained solvers seem to be robust and have excellent performance. \n\nThe weaknesses seem to be larger model size and possible generalization issues.\n\nThe presentation of the neural architecture is not explained in sufficient details, e.g.,\n\n- The mixed-scoreMHA layer is not explained properly, even in Appendix A. For instance, it's not clear where h_0 and h_v are used in Appendix A.\n- Some notations are not explained, such as \\Theta_{ij}^{knn} in Equation 4.\n- The MHA function is used with different parameters: MHA(h, H) or MHA(q, k, v). Again, for completeness, the notations should be explained.\n\nThe experimental set-up is missing some details:\n\n- What's the model size of UniteFormer compared to the other neural solvers used as baselines?\n- On which instance size UniteFormer is trained on? For instance, is it trained on TSP-n and then evaluated on TSP-n?\n\nSince the proposed architecture is relatively complex, the authors should do an ablation study to demonstrate that different components of this architecture are useful (e.g., mixed-score attention layer, parallel-attention decoding…)\n\nMinor remarks:\n\nIn line 20, \"These methods learn solution strategies autoregressively from data\": This sentence seems to ignore all the machine learning based methods used as improvement solvers.\n\nIn line 41: \"capture complementary structural information\": In Euclidean TSP, the node positions and the distances seem to include the same information. What do you mean by \"complementary\"?\n\nIn line 115: \"node features are passed to the GCN directly\": In Fig. 1, there's no arrow from node embedding to GCN. Is it normal?", "was_revised": true, "final_justification": "The authors have address the weaknesses I mentioned. Although the size of the proposed model is large, it's comparable to other ones. In addition, its generalization capability seems to be good.", "rebuttal": "Thank you for your constructive and valuable comments and suggestions. We address your concerns point-by-point as follows:\n\n> **Q1: Notation Explanation.**\n\n**A1:** We appreciate your concern regarding the clarity of the **mixed-score MHA layer** and the associated notation in Appendix A. In the main text, the mixed-score MHA layer is briefly introduced by listing the required input arguments, specifically, $\\text{mixed-scoreMHA}(h_0,h_v,D_{ij})$, to emphasize the functional interface rather than the internal details. A more detailed explanation of this mechanism has already been provided in **Appendix A.1**, particularly in Equation 1, where the general input embedding is denoted as $h_i$. In our implementation, $h_i$ corresponds to: a zero vector $h_0$, and a randomly selected one-hot vector $h_v$. These two are used to construct the inputs to the MHA layer as follows: \n$$q = W^Q h_0,\\quad k = W^K h_v,\\quad v = W^V h_v.$$ \nWe opted for generic notation in the appendix to reflect the flexibility of $h_i$ as a general embedding, without tying it to specific choices like $h_0$ and $h_v$, which are task- and design-specific. That said, we agree that clarifying this correspondence more explicitly would improve readability, and we will incorporate this clarification in the final version.\n\n**Regarding your other points:**\n\n**(1) The notation $\\Theta_{ij}^{knn}$** refers to the edge adjacency matrix derived from the KNN graph structure. Although this has already been mentioned in line 139 of the main text, we acknowledge that it still lacks a detailed explanation. We will provide a more detailed description in the final version to improve clarity and completeness.\n\n**(2) The notation $\\text{MHA}(h,H)$** is a shorthand representation of a generic attention layer, where the output from the previous layer (e.g., hidden states) serves as both the query and context input for the next layer. In contrast, $\\text{MHA}(q,k,v)$ explicitly denotes the multi-head attention computation used in the decoder stage, where the query, key, and value inputs may come from different sources. We will clearly distinguish and define these usages in the final version to avoid ambiguity.\n\n> **Q2: Model Size of UniteFormer.**\n\n**A2:** Thank you for your question. We provide a comparison of the model size (in terms of parameter count and storage footprint) between UniteFormer and other baseline neural solvers. Specifically, UniteFormer has approximately 4.48 million parameters, resulting in a model size of 47,287 KB, which is larger than POMO (as UniteFormer needs to deal with different types of input simultaneously), but smaller than MatNet.\n||POMO-edge|MatNet|POMO|LEHD|GCN-BS|DAR|ICAM|UniteFormer|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|**Parameters**|1,282,304|5,601,696|1,269,760|1,431,681|11,053,802|1,269,760|2,457,088|4,478,736|\n|**Storage Footprint**|15,172KB|67,887KB|15,045KB|16,743KB|129,732KB|15,025KB|29,035KB|  47,287KB|\n\nThis increase in size is due to UniteFormer’s unified architecture, which supports all three input modalities within a single model, without requiring separate training runs for each modality. In contrast, baseline methods typically require separate models to be trained independently for each input type. Moreover, our inference time remains competitive and is on par with most baseline methods, as shown in **Table 1** of the main paper.\n\nWe will include a detailed table comparing parameter counts for all methods in the final version to improve transparency and reproducibility.\n\n> **Q3: Training Settings of UniteFormer.**\n\n**A3:** Following the standard practice in prior works like POMO and MatNet, our UniteFormer trained on TSP-n is mainly evaluated on the same instance size TSP-n. However, we have also included the generalization test on TSPLib and CVRPLib (i.e., trained on 100-node instances but tested on various sizes) in **Table 3 of the paper**. To further demonstrate strong generalization to larger problem sizes, we apply models trained on TSP-100/CVRP-100 to solve TSP-200/CVRP-200 instances (see **the table below**, which provides the gap values under three input modalities). Here, UniteFormer still achieves competitive performance, highlighting its capacity to generalize beyond the training size. \n\n|Gap|POMO-edge|MatNet|UniteFormer-E|POMO|LEHD-greedy|UniteFormer-X|GCN-BS|DAR|ICAM|UniteFormer-XE|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|TSP100|2.010%|0.213%|**0.092%**|0.153%|0.531%|**0.099%**|1.379%|0.194%|0.212%|**0.066%**|\n|TSP200|60.017%|5.408%|**2.778%**|2.144%|**0.859%**|1.424%|48.697%|1.432%|2.146%|**1.058%**|\n|CVRP100|1.843%|3.086%|**0.810%**|0.790%|3.607%|**0.727%**|--|0.890%|1.240%|**0.662%**|\n|CVRP200|181.072%|7.648%|**2.102%**|4.866%|3.312%|**1.725%**|--|2.627%|4.925%|**1.420%**|\n\n> **Q4: Ablation Study.**\n\n**A4:** Thank you for your valuable suggestion. As part of our original submission, we have already conducted ablation studies on three input modalities and three major architectural components, as detailed in **Section 4.2** and **Appendix E**. These experiments were selected to highlight the most representative design choices under the space constraints of the main paper.\n\nFollowing your suggestion, we have further performed **four additional ablation studies** to assess the impact of the following components:\n\n* Removing the **mixed-score attention layer** (denoted by w.o. mixeMHA),\n* Changing the **parallel-attention decoding** to a single-layer decoding architecture (denoted by w.o. decoding),\n* Removing the **GCN layer** (denoted by w.o. GCN), and\n* Placing the **self-attention layer before the GCN module** (denoted by w.o. Order).\n\nThe experimental results are summarized in the table below and further confirm that each of these components contributes meaningfully to the model’s performance.\n\n|TSP50|w.o.mixeMHA|w.o.decoding|w.o.GCN|w.o.Order|UniteFormer|\n|-|:-:|:-:|:-:|:-:|:-:|\n|input-edge|123.029%|25.055%|3.261%|0.074%|**0.004%**|\n|input-node|0.192%|**0.003%**|0.616%|6.735%|0.004%|\n|input-XE|0.129%|0.003%|0.616%|0.069%|**0.003%**|\n\n|CVRP50|w.o.mixeMHA| w.o.decoding|w.o.GCN|w.o.Order|UniteFormer|\n|-|:-:|:-:|:-:|:-:|:-:|\n|input-edge|100.430%|2.271%|3.467%|45.704%|**0.668%**|\n|input-node|0.801%|0.820%|0.936%|31.186%|**0.694%**|\n|input-XE|0.799%|0.785%|0.936%|18.521%|**0.660%**|\n\nWe appreciate your feedback and will include these new ablation studies in the final version to provide a more comprehensive analysis of the architecture.\n\n> **Q5: Minor remarks [line 20]: Improvement solvers.**\n\n**A5:** Thank you for the valuable comment. You're right that there exists a broad class of machine learning–based methods that function as improvement solvers (e.g., learning local search heuristics or integrating with classical optimization frameworks), which are not necessarily autoregressive in nature.\n\nOur original sentence was indeed narrow in scope. We have revised it as follows to better reflect the diversity of neural methods for VRPs:\n\n> These methods include both autoregressive models that learn construction policies from data[21, 9, 25], as well as learning-based improvement solvers that enhance classical optimization procedures. However, many of these models, particularly construction-based ones, make an overly simplifying assumption: they rely solely on either node coordinates or edge distances as input.\n\n> **Q6: Minor remarks [line 41]: Complementary.**\n\n**A6:** Thank you for your insightful question. While node positions in Euclidean TSP do determine pairwise distances, we use the term \"**complementary structural information**\" to highlight that our model learns distinct yet mutually reinforcing aspects of the problem via separate encoders.\n\nSpecifically, the edge-aware sub-encoder directly models pairwise distances, which are critical for evaluating tour costs and capturing local geometric structure. In contrast, the node-focused sub-encoder uses attention to extract global, node-centric patterns, such as a node’s relative position in the graph (e.g., centrality, clustering). Although both sub-encoders ultimately rely on the same raw coordinates, they capture complementary views: one encodes pairwise relational structure, while the other emphasizes global positional context.\n\nIn addition, although distances can be derived from coordinates in Euclidean space, we find that neural networks benefit from directly learning the true distance values rather than relying on implicitly inferred ones. This direct modeling of edge-level information leads to more effective learning and improved solution quality.\n\nMoreover, the notion of complementary becomes even more pronounced in non-Euclidean settings, such as the ATSP (the results are presented in **Appendix F**), where distances cannot be solely inferred from coordinates. This demonstrates that our model provides a flexible interface for directly handling real-world problems where true pairwise distances are explicitly defined and cannot be inferred from positions alone.\n\n> **Q7: Minor remarks [line 115]: Figure.**\n\n**A7:** Thank you for your careful observation. The sentence in line 115-\"Without edge weights, node features are passed to the GCNs directly\" is specifically referring to the Node-only input modality illustrated in **Figure 2(b)**. In this subfigure, the arrows clearly indicate the direct flow of node embeddings into the GCNs under the Node-only setting, and are intended to highlight the different input modes handled by our framework. In contrast, **Figure 1** is designed to provide a high-level overview of the model architecture, emphasizing the modular composition and interactions between the main components. It does not explicitly depict the detailed flow of inputs for the three input modalities, which are instead elaborated in Figure 2. As image updates are not permitted during the rebuttal phase, we will revise Figure 1 in the final version to better reflect these input pathways and avoid confusion."}, {"review_id": "38xsEEiJoP", "reviewer": "Reviewer_Fawv", "summary": "This paper introduces UniteFormer, a Transformer-based method that processes nodes and edges simultaneously to solve vehicle routing problems (VRPs). The authors present a network architecture that can handle multimodal inputs. This architecture enables edge and node features to interact while maintaining the independence of their respective subnetworks.", "questions": "- Are existing methods inadequate simply because they use masked inputs for training? Graph neural networks are generally assumed to learn to complement node and edge features internally.\n- If the network architecture is novel, then it should not be confined to VRPs. Could it benefit other tasks? Alternatively, is there a specific argument that handling edge-, node-, and hybrid inputs simultaneously is uniquely important for VRPs?\n- The order and interplay of GCNs and attention are nontrivial. If attention alone is expected to yield rich, modality-independent features, then the absence of a GCN seems odd. Can you provide evidence supporting the soundness of this architectural choice?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strengths\nThe loosely coupled design enables a single model to uniformly handle edge-, node-, and hybrid-only inputs. The method is evaluated in a reinforcement-learning setting for VRPs and demonstrates strong performance.\n\n### Weaknesses\nThe review of existing work is insufficient, which leaves the novelty of the method unclear. Similar architectures to the proposed one are well known in graph-based neural networks, including works such as [*1] and [*2]. Comparable ideas have also been introduced in diverse fields, such as graph anomaly detection [*3], bipartite graph matching [*4], point-cloud registration [*5], and molecular modeling [*6]. Therefore, a broader survey with appropriate citations is desirable.\n\nSuch a survey would clarify the paper's contribution. It would demonstrate that a network capable of handling edges and vertices can accommodate edge-only, vertex-only, or hybrid inputs, particularly for VRPs. However, this is mainly a case study, so the degree of novelty is limited.\n\n### Comment\nPlease change \"Related Works\" to \"Related Work.\"\n\n- [*1] Z. Hu+. Heterogeneous Graph Transformer. WWW2020.\n- [*2] Z. Gao. A Graph is Worth K Words: Euclideanizing Graph using Pure Transformer. ICML2024.\n- [*3] S. Yang. AHEAD: A Triple Attention Based Heterogeneous Graph Anomaly Detection Approach\n- [*4] S. Sone+. WeaveNet for Approximating Two-sided Matching Problems. arXiv:2310.12515.\n- [*5] R. Yanagi+. Learning 3D Point Cloud Registration as a Single Optimization Problem. ACCV2024.\n- [*6] M. Anselmi+, Molecular graph transformer: stepping beyond ALIGNN into long-range interactions. Digital Discovery, 2024.", "was_revised": true, "final_justification": "Taking into account the responses to my concerns, as well as the discussions and evaluations provided by other reviewers, I agree with the positive overall sentiment and am inclined to support acceptance.", "rebuttal": "Thank you for your constructive and valuable comments and suggestions. \n> **Q0:Related Work**\n\n**A0: (1) Scope of prior work:** Our study builds on an established body of research in neural VRP solvers. Prior works such as POMO, LEHD, RELD, GCN-BS, and Pointerformer (most of them are published in NeurIPS/ICLR) predominantly adopt GNNs or Transformer-based architectures within the VRP domain. To remain focused and highlight our specific contribution to modality-flexible neural solvers, we limited our related work to this area. Our motivation further stems from the lack of models that effectively integrate GNNs and Transformers for VRPs under varying or incomplete input modalities, which guided the design of our unified architecture.\n\n**(2) Broader works outside VRPs:** We appreciate the reviewer highlighting six relevant works[*1]–[*6] from other domains. While they share certain architectural elements, our method differs fundamentally in both objective and design, e.g.,: HGT[*1] models type-specific message passing in heterogeneous graphs, whereas UniteFormer addresses modality heterogeneity (node/edge/hybrid) for route optimization. GraphGPT[*2] focuses on Euclideanizing graphs for representation learning; we focus on path construction by jointly encoding structure and distances. AHEAD[*3] detects graph anomalies via triple-attention, while UniteFormer uses REINFORCE-based training to generate feasible tours in VRPs. WeaveNet[*4] solves bipartite matching over complete graphs; UniteFormer supports incomplete or partial input modalities, which is critical for real-world VRPs. [*5] addresses 3D point cloud registration using geometric alignment; our work is focused on graph-based sequential decision-making. MGT[*6] models long-range molecular interactions for property prediction, while UniteFormer focuses on combinatorial path generation and input-modality adaptation, not regression or graph-level inference.\n\nAlthough there may be surface-level architectural similarities (e.g., use of attention or GNNs), UniteFormer is fundamentally designed for path construction under modality-variant inputs, which is non-trivival and crucial for real-world VRPs. To our knowledge, UniteFormer is the first unified model to support all three modalities within a single framework. Each component is purposefully designed to handle node, edge, and hybrid in a scalable and flexible manner, combining the strengths of GNNs (for edge reasoning) and attention mechanisms (for node embedding). However, we agree that referencing broader literature like [*1]–[*6] will strengthen the generality and novelty of our method. \n> **Q1:Existing methods inadequate?**\n\n**A1: (1) The core limitation of existing methods** lies not in the use of masked inputs, but in their reliance on a single input modality, i.e., node-only, edge-only, or hybrid, making them less adaptable to real-world scenarios with missing or varying input types. For example: (i)Edge-only methods like MatNet may underutilize node coordinates even when available; (ii)Node-only methods such as POMO and LEHD cannot directly process edge input without redesign and retraining; (iii)Models like GCN-BS or DAR, built for hybrid inputs, perform poorly when only one modality is present due to their architectural dependence on both. To our knowledge, no existing work offers a unified framework that flexibly handles node-only, edge-only, and hybrid inputs within one model, despite its clear practical value. This motivates our design of a unified architecture that adapts to all modalities without the need for retraining.\n\n**(2) Regarding your point on** GNNs learning to internally complement node and edge features: we agree in principle. In fact, our model includes GCNs as a core component, precisely to capture structural dependencies from edge and node. However, through extensive experiments and ablation studies, we find that GCNs alone struggle to perform consistently across all input modalities, especially when only node or edge data is provided. To address this, we design a parallel mixed encoder combining GCNs and attention, enabling effective capture of both node- and edge-level semantics. This design ensures robust performance across all input modalities, as evidenced by:\n(i)Quantitative comparisons in Table 1,\n(ii)Component-level ablations in Section 4.2, and\n(iii)Additional targeted ablations (see A3).\n>**Q2:Other Tasks and Three Inputs**\n\n**A2: (1)** VRPs are a core class of combinatorial optimization problems (COPs) with widespread applications in logistics and transportation. Given their practical relevance and structural complexity, developing specialized and efficient models for VRPs is both common and well-justified in existing literature, such as LEHD, GCN-BS, DAR, ICAM, focusing solely on VRPs. Our work follows this tradition, ensuring fair comparisons with established baselines. Moreover, our model further extends this research by supporting all three input modalities, offering greater flexibility than those prior single-modality methods. Moreover, UniteFormer can also handle asymmetric problems like ATSP, which node-only models such as POMO and LEHD cannot directly address.\n\nHowever, UniteFormer's architecture is inherently general and we extend it to the **0-1 Knapsack Problem(KP)**. The results below for KP50 with 200 training epochs on both POMO and UniteFormer show that UniteFormer maintains impressive performance beyond VRPs. This further confirms its potential of UniteFormer as a general-purpose neural solver for other tasks beyond VRPs. \n|KP50|Optimal|POMO|UniteFormer|\n|-|-|-|-|\n|score|20.127|20.113|20.120|\n|gap|--|0.069%|**0.029%**|\n\n**(2)** While prior methods like POMO is restricted to a single input modality and require architectural changes to accommodate others, real-world VRPs demand greater flexibility. Node-based inputs are common in Euclidean settings, edge-based inputs are essential for non-Euclidean or asymmetric tasks like ATSP, and hybrid inputs combining coordinates and distances are increasingly important in practical logistics scenarios. UniteFormer is the first framework, to our knowledge, that supports all three modalities, i.e., node, edge, and hybrid, within a unified architecture, reducing the need for retraining. As shown in Table 1 and Section 4.2, it delivers strong and consistent performance across all input types. This modality flexibility is crucial in real-world deployments, e.g., node coordinates may be unavailable or noisy, while edge-level data is often more reliable.\n>**Q3:Structural Rationality**\n\n**A3:** First, to clarify, our architecture includes both GCNs and attention, and there is no absence of GCNs. So we guess what you mean by this sentence is: \"If attention alone... then the inclusion of a GCN seems odd.\" \n\n**(1) Complementarity:** \nAs described in Section 3.2, we adopt a parallel GCN-attention encoder to jointly process node and edge features and capture their cross-modal interactions. While attention mechanisms (e.g., POMO, LEHD) are effective for node-centric representations, GCNs are well-suited for learning from structured graph data, especially when edge input is available or critical. This hybridization is particularly beneficial in tasks like CVRP and ATSP, where edge weights (e.g., asymmetries, capacities) encode essential semantics that attention alone may overlook. In fact, Section 3.3(lines 157–161) further explains that attention modules are introduced to complement the limited node-level expressiveness of GCNs, ensuring a balanced and expressive node embedding. \n\n**(2) Input Modality:**\nUniteFormer is designed to handle three input modalities. Given this, attention and GCNs serve distinct yet complementary roles: GCNs are naturally suited for Edge-only and hybrid inputs, enabling relational reasoning over graphs. Attention excels in processing Node-only data, especially when no explicit graph structure is available. Empirically, attention-only methods like POMO work well for Node-only inputs but perform poorly when edge features dominate. As shown in Table 1, our variant \"POMO-edge\"(a modified POMO model applied to edge-based input) performs notably worse than UniteFormer. This confirms that attention alone is insufficient for edge-dominant tasks. Moreover, in problems like ATSP, where edge asymmetry is key and node coordinates cannot infer distance, GCN-based reasoning is indispensable. As demonstrated in Appendix F, our hybrid model surpasses attention-only methods like MatNet on ATSP.\n\n**(3) Empirical Validation:**\nTo validate our architectural design, we conducted **four additional ablation studies** (see response A4 to Reviewer HhBh), examining (i) the complete removal of the GCNs module and (ii) reordering by placing self-attention before GCNs. As shown in the table below, both changes led to noticeable performance drops, underscoring the necessity of GCN and the soundness of our original design.\n\nIn addition, we further conducted ablation studies on the mixed-score attention and parallel encoding structures (see the table below), confirming their effectiveness, particularly for edge-only inputs. Our initial submission already included ablation results for three architectural components (see Appendix E), further demonstrating the value of self-attention and the overall structure.\n|TSP50-Gap%|w.o.GCN|w.o.Order|w.o.mixeMHA|w.o.decoding|w.o.self-attention| w.o.node-focused|w.o.edge-aware|UniteFormer|\n|-|-|-|-|-|-|-|-|-|\n|input-E|3.261|0.074|123.029|25.055|0.007|0.004|1.294|0.004|\n|input-X|0.616|6.735|0.192|0.003|0.009|0.004|0.006|0.004|\n|input-XE|0.616|0.069|0.129|0.003|0.004|0.003|0.005|0.003|\n\n|CVRP50-Gap%|w.o.GCN|w.o.Order|w.o.mixeMHA|w.o.decoding|w.o.self-attention| w.o.node-focused|w.o.edge-aware|UniteFormer|\n|-|-|-|-|-|-|-|-|-|\n|input-E|3.467|45.704|100.430|2.271|0.770|0.841|37.266|0.668|\n|input-X|0.936|31.186|0.801|0.820|0.721|1.103|1.835|0.694|\n|input-XE|0.936|18.521|0.799|0.785|0.680|1.028|1.734|0.660|"}, {"review_id": "6lChWnRCHL", "reviewer": "Reviewer_HjGY", "summary": "This paper introduces UniteFormer, a novel neural solver for Vehicle Routing Problems (VRPs) designed to overcome the limitations of existing methods that typically rely on either node-only or edge-only inputs. UniteFormer proposes a unified framework that can handle node-only, edge-only, and hybrid (node and edge) input types using a single trained model, eliminating the need for retraining for different input modalities.\n\nThe core contributions of UniteFormer are:\n\nA novel mixed encoder that integrates residual gated Graph Convolutional Networks (GCNs) with attention mechanisms. This encoder consists of an edge-aware sub-encoder and a node-focused sub-encoder, collaboratively processing both node and edge features to capture cross-modal interactions.\n\nA parallel-attention decoder enhanced with query mapping and a feed-forward layer to improve its representational capacity.\nThe model is trained using REINFORCE by randomly sampling input types across batches, allowing it to generalize across modalities.\n\nExtensive experiments on TSP and CVRP, including real-world TSPLib and CVRPLib instances, demonstrate that UniteFormer achieves state-of-the-art performance across all three input types and shows strong generalization capabilities.", "questions": "Question: Given that REINFORCE can suffer from high variance, what specific techniques (e.g., baseline choices, larger batch sizes, other variance reduction methods) were employed to ensure stable and efficient training of UniteFormer? Were other policy gradient algorithms (like Actor-Critic variants or PPO) considered, and if so, what were the reasons for choosing REINFORCE over them?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nQuality: UniteFormer's architecture is robust and well-designed, effectively addressing the challenge of unifying node and edge modalities. The mixed encoder with its two sub-encoders (edge-aware and node-focused) and the parallel-attention decoder show a sophisticated approach to integrating diverse information. The experimental results are comprehensive, covering TSP and CVRP on synthetic and real-world benchmarks (TSPLib, CVRPLib) across all three input settings (node-only, edge-only, hybrid), demonstrating state-of-the-art performance. The authors also re-implemented POMO for edge-only input for a fair comparison, which adds to the quality of the experimental setup. \n\nClarity: The paper is clearly written and well-structured. The problem statement regarding single-modality limitations is articulated effectively. The architecture of UniteFormer is explained logically, with a helpful overview diagram (Figure 1) and detailed breakdowns of the input modalities , sub-encoders , and decoder. Mathematical formulations are provided for key components, enhancing understanding. \n\nSignificance: The primary significance lies in proposing the first unified neural solver for VRPs that inherently supports node-only, edge-only, and hybrid inputs within a single trained model. This addresses a major practical limitation in current neural VRP solvers, offering greater flexibility and applicability to diverse real-world scenarios where input data might vary. The improved generalization and state-of-the-art performance contribute to advancing the field of neural combinatorial optimization for VRPs. \n\nOriginality: The concept of a single model capable of handling multiple input modalities (node, edge, hybrid) without retraining is highly original in the context of neural VRP solvers. The specific architectural designs, particularly the mixed encoder with its dual sub-encoders and their collaborative processing of heterogeneous features, represent a novel approach to information fusion. The random sampling of input types during REINFORCE training is also an original aspect of their methodology for achieving modality generalization. \n\nWeaknesses:\n\nTraining Complexity and Hyper-parameter Sensitivity: The paper utilizes the REINFORCE algorithm for training, which is known for its high variance and potential training instability. However, the paper does not provide detailed insights into how these challenges were managed (e.g., specific variance reduction techniques, choice of baselines, or batch size considerations). While performance is good, a discussion on the robustness of the training process would be beneficial.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive and valuable comments and suggestions. We address your concerns point-by-point as follows:\n \n>**Q1: Given that REINFORCE can suffer from high variance, what specific techniques (e.g., baseline choices, larger batch sizes, other variance reduction methods) were employed to ensure stable and efficient training of UniteFormer?**\n\n**A1:** Thank you for your question regarding the stability of REINFORCE training in UniteFormer. To mitigate the known high variance issue of REINFORCE, we adopt a shared baseline strategy, as detailed in **Appendix B**, which is also widely used and validated in prior works such as POMO and MatNet.\n\n**(1) A shared baseline strategy:** Specifically, we sample multiple trajectories per instance (e.g., via augmentation or diverse decoding), and use the average reward across these trajectories as the baseline. This shared baseline significantly reduces gradient variance and has been shown to improve training stability in VRP tasks. Empirical evidence from POMO shows that this shared baseline is more robust to local minima than the greedy rollout baseline in AM. This technique ensures that the advantage term $R(\\tau_i)-b(s)$ has zero mean, and detailed formulas for the gradient variance can be found in **Appendix B**.\n\nIn addition, we have adopted Batched Trajectory Sampling and Large Mini-Batch Training techniques to ensure more stable and efficient training of UniteFormer.\n\n**(2) Batched Trajectory Sampling:** Similar to POMO, we employ parallel exploration from diverse starting states, which leads to multiple diverse yet optimal solution representations. This practice effectively acts as a kind of entropy-regularized exploration, and avoids overfitting to narrow trajectory spaces, i.e., a common cause of instability in REINFORCE. Moreover, by leveraging the symmetries in routing problems (e.g., permutation invariance in TSP tours), we encourage the policy to generalize more robustly, thereby improving sample efficiency.\n\n**(3) Large Mini-Batch Training:** As suggested in prior literature (e.g., AM and POMO), we train the policy network with larger mini-batches (e.g., 64–256 problem instances per batch), which smooths out noisy gradients and contributes to more stable convergence.\n\nIn summary, we combine a low-variance shared baseline, multiple trajectory rollouts, and large batch training to ensure that the REINFORCE training of UniteFormer remains stable and sample-efficient. These strategies have been shown to be effective in prior work (especially POMO) and are further validated in our empirical results across TSP, CVRP, and ATSP tasks. \n\nWe appreciate your feedback again and will include a more explicit discussion in Appendix B.\n\n\n> **Q2: Were other policy gradient algorithms (like Actor-Critic variants or PPO) considered, and if so, what were the reasons for choosing REINFORCE over them?**\n\n**A2:** Thank you for your thoughtful question. In our work, we adopt the REINFORCE algorithm as the underlying policy gradient method, following a widely recognized and empirically validated precedent in neural combinatorial optimization, especially for routing problems. This choice is grounded in both empirical evidence and practical considerations, as discussed and validated in prior influential works such as AM and POMO. Particularly, \n\n* AM explicitly states in the abstract:\n\n  > *\"We show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function.\"*\n\n* Similarly, POMO adopts REINFORCE and addresses variance through a shared baseline:\n\n  > *\"We optimize the model using the REINFORCE algorithm, with a shared baseline across the multiple trajectories per instance. This baseline significantly reduces the variance of the gradient and improves stability.\"*\n\nThese works demonstrate that, when paired with appropriate variance reduction techniques (e.g., rollout or shared baselines), REINFORCE can train powerful and generalizable neural solvers. As a result, REINFORCE has become a de facto standard in the VRP literature.\n\nIn addition, we chose REINFORCE over more complex policy gradient algorithms such as Actor-Critic variants or PPO for several reasons:\n\n**(1) Simplicity and robustness in discrete, structured action spaces:** Routing problems involve large, dynamic, and discrete action spaces (e.g., permutations). Designing a stable critic network that generalizes over such combinatorial structures is highly non-trivial and often leads to convergence issues.\n\n**(2) Compatibility with autoregressive decoding:** Our decoder constructs solutions sequentially over permutations. REINFORCE allows us to compute unbiased policy gradients directly from sampled trajectories, without the need for approximating value functions over structured outputs.\n\n**(3) Lack of evidence for superior performance of Actor-Critic methods:** To our knowledge, actor-critic or PPO-style algorithms have not shown consistent advantages over REINFORCE in VRP tasks. In fact, empirical attempts to integrate these methods (e.g., applying PPO to POMO according to our preliminary experiments) have often resulted in non-convergent training. This further explains why recent state-of-the-art models continue to rely on REINFORCE-based frameworks.\n\nAs detailed in **Appendix B**, our training setup with REINFORCE, which is combined with shared baselines, large batches, and architecture design, results in stable convergence and high-quality solutions across TSP, CVRP, and ATSP benchmarks.\n\nWe acknowledge that more advanced policy gradient algorithms could be interesting for future work, especially if tailored to handle structured action spaces with learned critics. However, for the scope of this paper, REINFORCE strikes the best balance between effectiveness, reproducibility, and compatibility with our architecture. So we find REINFORCE to be the most suitable and efficient choice for our setting."}]

Author rebuttal:

Meta-review: The paper received four ratings of 5 for acceptance from the reviewers. This paper presents a new neural solver for Vehicle Routing Problems (VRPs) that integrates node and edge modalities with state-of-the-art performance across various tasks. The approach has a well-designed architecture that enhances flexibility and generalization. There were some concerns regarding the computational complexity analysis and hyperparameter sensitivity, but the authors have addressed reviewers' concerns during the rebuttal by clarifying the model's efficiency and providing additional analyses. The paper has significant contributions in neural combinatorial optimization strong experimental results. Given the unanimous support from the reviewers, the AC recommends acceptance.
Decision: Accept (spotlight)