Probing Neural Combinatorial Optimization Models
Authors: Zhiqin Zhang
Yining Ma
Zhiguang Cao
Hoong Chuin Lau
Venue: NeurIPS 2025 spotlight ()
Keywords: Neural Combinatorial Optimization
Probing
Vehicle Routing Problem
Primary area: optimization

Abstract: Neural combinatorial optimization (NCO) has achieved remarkable performance, yet its learned model representations and decision rationale remain a black box. This impedes both academic research and practical deployment, since researchers and stakeholders require deeper insights into NCO models. In this paper, we take the first critical step towards interpreting NCO models by investigating their representations through various probing tasks. Moreover, we introduce a novel probing tool named Coefficient Significance Probing (CS-Probing) to enable deeper analysis of NCO representations by examining the coefficients and statistical significance during probing. Extensive experiments and analysis reveal that NCO models encode low-level information essential for solution construction, while capturing high-level knowledge to facilitate better decisions. Using CS-Probing, we find that prevalent NCO models impose varying inductive biases on their learned representations, uncover direct evidence related to model generalization, and identify key embedding dimensions associated with specific knowledge. These insights can be potentially translated into practice, for example, with minor code modifications, we improve the generalization of the analyzed model. Our work represents a first systematic attempt to interpret black-box NCO models, showcasing probing as a promising tool for analyzing their internal mechanisms and revealing insights for the NCO community. The source code is publicly available [here](https://github.com/123zhangzq/NeurIPS2025_probing).

Probing Neural Combinatorial Optimization Models
Zhiqin Zhang Singapore Management University zqzhang 2020@phdcs. smu edu.
Yining Ma Massachusetts Institute of Technology yiningma@mit.ee edu
Zhiguang Cao
Hoong Chuin Lau"
Singapore Management University zgcao@smu. hwt.s/mmeedu.......ee.eee edu.sg
Singapore Management University hclau@smu edu.sg
Abstract
Neural combinatorial optimization (NCO) has achieved remarkable performance, yet its learned model representations and decision rationale remain a black box. This impedes both academic research and practical deployment, since researchers and stakeholders require deeper insights into NCO models. In this paper, we take the first critical step towards interpreting NCO models by investigating their representations through various probing tasks. Moreover, we introduce novel probing tool named Coefficient Significance Probing (CS- (SS-Probing) to enable deeper analysis of NCO representations by examining the coefficients and statistical signif- icance during probing. Extensive experiments and analysis reveal that NCO models encode low-level information essential for solution construction, while capturing high-level knowledge to facilitate better decisions. Using CS-Probing, we find that prevalent NCO models impose varying inductive biases their learned represen- tations, uncover direct evidence related to model generalization, and identify key embedding dimensions associated with specific knowledge. These insights can be potentially translated into practice, for example, with minor code modifications, we improve the generalization of the analyzed model. Our work represents first systematic attempt to interpret black box NCO models, showcasing probing as a promising tool for analyzing their internal mechanisms and revealing insights for the NCO community. The source code is publicly available
Introduction
Neural combinatorial optimization (NCO) has demonstrated remarkable performance in solving classic combinatorial optimization problems, such vehicle routing, achieving results comparable to, or even surpassing, specialized heuristic algorithms such as Concorde [1, ACO 2), LKH3 K.
HGS 4.. However, the underlying reasons behind these impressive results, particularly the nature of the knowledge learned by these neural models, remain largely unexplored and unclear.
In this paper, we take the first step towards interpreting NCO models by probing 5 6 7 powerful tool that has proven successful computer vision (CV) and natural language processing (NLP). We pioneer the first study that directly investigates the learned embeddings in deep NCO models, aiming to explore the internal mechanisms of these black-bo models. In this work, we aim to address two fundamental questions regarding the representations learned by NCO models: (i) What decision-relane knowledge do they acquire? (ii) How do they learn and utilize this knowledge?
"Corresponding author
"Source Code: http:/thubb.mmmm/2//agagggge//// http:////22aaaaaae/aa////2200000
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Addressing the First Question: Probing involves training auxiliary prediction tasks using the em- beddings learned by a trained deep learning model. In the context of NLP, for instance, if a simple model (particularly a linear model) can be trained to predict linguistic information about word (e.g.- its part-of-speech tag) or a pair of words (e.g., their semantic relation) from the emheddings, we can reasonably conclude that the embeddings successfully encode this information (see [8] for more details). However, unlike NLP tasks, which naturally involve intuitive subtasks that are well-suited for probing, combinatorial optimization (CO) problems typically lack such directly applicable subtasks. To address this gap, we systematically design a set of probing tasks specifically aimed at exploring both low- and high-level decision-relatee knowledge within NCO models.
Understanding how deep learning (DL) models learn and utilize decision-related knowledge remains a challenging problem. Different approaches have been proposed, such as using probing to explore decision boundaries [9] to understand in-context learning in large language models (LLMs), or identifying individual neurons whose input or output weights have high cosine similarity with the learned probe direction to detect specific neurons that encode particular knowledge [10]. In this paper, propose novel method called Coefficient Significance Probing CS-Probing) to investigate the representations of deep models. CS-Probing not only identifies the most informative embedding dimensions but also quantitatively assesses their statistical significance. providing deeper insights into the model's 's meaisioo-making process.
Addressing the Second Question:
Contributions. Our main contributions are as follows: (1) We systematically design probing tasks for NCO models and demonstrate that their representations capture both low-level decision- related information (e.g.. perceiving Euclidean distances) and high-level knowledge (e.g., avoiding myopie decisions based solely on distance) for sacision-making (2) Through our proposed CS- Probing, we discover that different NCO models introduce diverse inductive biases into the learned representations, resulting in varied decision-making patterns. (3) By applying CS- P-obbriing we identify the key embedding dimensions that encode specific knowledge within the model representations. (4) Leveraging these key dimensions, we provide evidence of the generalization capabilities of NCO models: models with superior generalization consistently utilize the same embedding dimensions across different tasks. In contrast, models whose knowledge becomes disorgamized across dimensions during generalization tend to experience performance degradation. Finally, based on probing insights, we show that modifying only a few lines of code in an NCO model holds the potential to improve its generalization performance, illustrating the practical value of our proposed probing analysis.
2 Preliminaries
NCO model. NCO models are a class of learning-based solvers for CO problems, with more details provided in Appendix [ This paper studies the most representative transformer-basee architectures (as illustrated in Figure [ as examples demonstrate how probing can explore their internal mechanisms. Taking the Traveling Salesman Problem (TSP) as an example, the raw features of nodes (c.g., xy coordinates in the Euclidean space) are first fed as inputs. These raw features are projected into a high-dimeensionl space through a linear projection layer. Subsequently, multiple attention mechanism layers are employed to integrate abstract features from different nodes, yielding the final representations for each node. These representations are then processed either through a compatibility calculation or directly projected to a scalar via a linear transformation, followed by softmax operation to obtain the selection probability of the next node. Recursively, this process connects all nodes to generate the complete TSP solution. this paper, we utilize probing to investigate the representations of three models: AM [1], POMO [1). and LEHDD 13
to explore the representations of NCO models. If this linear model can accurately predict the probing tasks based on the embeddings from the NCO models, it indicates that the knowledge relevant to the probing tasks can be easily extracted from the embeddings [3] g This also suggests that the pre-trained NCO model, from which the embeddings for the probing tasks are derived, has the ability to encode this knowledge in its representations. Other interpretability approaches, including gradient-base based attribution, visualization, and neuron ablation, lack the explanatory power of probing. For example, the first method reveals output sensitivity to input features but neither shows where or whether knowledge is encoded in hidden representations nor provides structural insight into how the model organizes the solution space. contrast, probing offers systematic interpretability framework by assessing the linear decodability of target properties
Probing. We use a linear probing 55 14 15 16

---

Confest Embedding
Mull-Hland Atontion
LivarPrajcciion
LisorPajidioon
Adantion Layars1
Linsar
Compaliiiit
Attertion Attertion Layer
P6
Liseed Projection
Deude
(a)
(b)
Figure 1: Two groups of NCO model architectures: (a) represents the HELD structure, as seen in AM and POMO, while (b) represents the LEHD structure. The red arrows in the figure indicate the positions where probe the model, extracting the embeddings.
from intermediate representations. For comprehensive discussion of the diverse applications of probing, the reader is referred to Appendix A.2
3 Probing for NCO
3.1 Probing Tasks and Setup
Since combinatorial optimization problems do not have suitable subtasks to serve as probing tasks, new task design is necessary for the specific CO problem being explored. Using the TSP problem as an example, we propose two probing tasks to investigate NCO models: whether the model can perceive the Euclidean distance between nodes (Probing Task I); and whether the model can learn to avoid constructing solutions in myopic manner, such greedily connecting to the nearest node (Probing Task 2). The former can be regarded low-level features of the TSP problem, while the latter is relatively higher-level and more closely aligned with the final decision-making process.
We also introduce two probing tasks for the CVRP problem, examining whether NCO models can understand constraints (Probing Task and Probing Task 4). Probing Task 3 investigates a relatively simple low-level feature: the linear additive relationship between node demands. In contrast, Probing Task 4 examines higher-level property: whether the embeddings encode information about two nodes belonging to the same route the optimal solution.
Figure in Appendix illustrate examples of probing dataset creation and label collection. For detailed definitions of these four probing tasks, the integration of domain knowledge from the CO field to create datasets, and the embeddings as probing input, please refer to Appendix
3.2 Probing the Decision-Relater Knowledge in NCO Models
Can NCO learn decision-related information from routing problems, exemplified by TSP?
We first examine whether NCO models capture a key low- level feature of the Euclidean distance between nodes. Next, explore higher-level and more abstract aspect of the embeddings: whether NCO models can capture decision-relater information that avoids the myopic strat- egy of always selecting the nearest node. Having estab- lished the presence of both low- and high-level features, we perform a layer- layer-wise analysis to understand how such information encoded and learned during training. This section summarizes key findings in Table [ In this table, "w/o ints" and "w/ ints" denote the absence and presence of interaction terms (see Appendix (.2.2), while the "Probing input" columns, 'Enc-Ix' and "Dec-Ix"
Table I: Highlights from Table 9 Here, we conduct the evaluation process 10 times to report the mean + SEM.
Probing ingut
Task 1 (R))
Task 2 (AUC)
vol lnts.
AM-Init
-00000 0.00000
0.49 0.00
AM-Fae-13
0.2529
0.00048
0.00
POMO-BBc-J6
8.1981
0.76 0.00
LEHD--Deo-6
0.9418 + 0.00051
0.86 = 0.00
AM-Init
0,7111 1. 0.00000
0.52 1. 0.00
10 LEES
AM AM-Enc-I1 13
0.9282 4: 0.00035
0.83 d: 0.00
POMO Enc-I8
0,7917
0.00000
0.86 0.00
refer the x-th layers in the encoder and decoder NCO models. Complete results and discussion
presented in Appendix C.I.I. with Table providing comprehensive summary.

---

Probing Task 1: Euclidean distance. We examine the ability of the three NCO models to linearly represent the Euclidean distances between pairs of nodes (specifically, the current node and any unvisited node) during decision-making by training línear probes and evaluating their performance.
As shown in the "w/o ints." rows of AM-Init in Table for both 20-node and 100-node examples, the values indicate that the initial embeddings of AM fail to capture the nonlinear relationship of Euclidean distance (with R2 values close to 0). These embeddings are derived by mapping the raw features, specifically the 2D coordinates in the TSP, through linear projection into the shared dimensional space of the encoder and decoder (128 dimensions for all three models discussed in this paper). In "Knowledge existence" section of Appendix [.1.1 we explain that the R of a Euclidean distance regression model using node coordinates as input is zero because it cannot capture the nonlinear nature of Euclidean distance. Thus, the initial embeddings essentially retain the properties of the raw features and similarly fail to linearly capture Fuclidean distances. The phenomenon of an R² value of zero for the initial embeddings can be observed across all NCO models.
However, after passing through the NCO model, the R²2 values for AM, POMO, and LEHD increase to 0.2529, 0. 1,19,1 and 0,9421, respectively, for 20-nodes example, as shown in Table Moreover, when considering interaction terms, the 1t2 values for all three models' embeddings after the encoder or decoder are significantly higher than those of the initial embeddings, approaching 1. This indicates that the representations in these NCO models contain linearly decodable Euclidean distance information, meaning they have learned how to linearly represent Euclidean distances.
Probing Task 2: Avoidance of myopia. Through Probing Task 2, explore whether NCO models can learn to avoid making decisions based solely on distance. As a first step, we train probing model using raw path feature (distance) as input. The resulting performance, with AUC close to 0.5, confirms that Probing Task 2 is not merely a trivial path discrimination task.
We use the "AM-Init" results the initial embeddings cannot linearly extract the knowledge needed to distinguish which nodes are connected to the current ones in the global optimal solutions (namely, the optimal edges). To confirm that Probing Task 2 is not relying on Euclidean distances for node differentiation, we further examine the initial embeddings with interaction terms, whose AUC values remain close to 0.5, suggesting they still fail to distinguish between optimal or greedy edges. In contrast, in Probing Task 1, the initial embeddings with interaction terms achieve R² above 0.7, indicating that the initial embeddings with interaction terms have linear explanatory power for Euclidean distances. This observation confirms that the two probing tasks are fundamentally different. It also implies that if the embeddings in an NCO model can be linearly distinguished in Probing Task 2, the model has learned to avoid myopic decision- makiing and capture the knowledge needed find the global optimal solution.
baseline reference, with AUC consistently at 0.5, indicating that
The results in Table I demonstrate that all three NCO models exhibit the ability to avoid myopic catisiionmmking. with AUC scores exceeding 0.8. Notebly, on both 20-node and 100-node instances, this ability is aligned with three models' performance on the optimization problem outcomes, as discussed in Section 3.3 where we analyze the relationship between probing performance and final model performance. Moreover, this ability is consistently stronger in the final layer compared to the first layer for all three models. In the next section, we provide more fine- mne-grained analysis to illustrate how the behavior of NCO models evolves across layers and how it changes during training.
Fine-grained analysis. In Figure 2 we present the results of two TSP probing tasks across different layers of embeddings for three trained models. The observation shows that the initial embeddings (before any attention layers) exhibit weak Euclidean distance perception. However, after just one attention layer, all models achieve strong distance awareness, which slightly weakens with depth. Despite this, deeper layers help NCO models develop high- avoiding myopic node choices. An exception occurs in the final layers of LEHD, where this ability slightly declines, possibly due to the emergence of more complex strategies. For an analysis of NCO model layers and their varying trends in capturing low- and high-level knowledge with increasing layers, the "Results by Model Layer" section in Appendix C.I.I Overall, NCO models transition from learning spatial relations in shallow layers to strategic reasoning in deeper layers.
eeccision-maiigg abilities, such as
Figure 3 illustrates the evolution of results for two TSP probing tasks during the training process. As shown, for AM and POMO, the model performance improvement during the initial epochs is the fastest, and the results for Probing Task 2 (related to avoiding myopic decisions) also improve rapidly in early learning epochs. In contrast, LEHD achieves peak performance on Probing Task

---

Probing Task Performance Across Different Layers
Probing Task 2 Performance Across Different Layer
1.0
0.8
AUC
Dre
20t0 Disc
LINO, poc
0.-
ma
0.0
LEMO Bec.res
1810 Doc.
Layers
enc
(b)
Figure 2: Probing results across different layers.
tec LIS-PL
potto dne ine em
Testing Scores
Probing Scares
Testing Scares
2.ar
posva 4ix-412
6.92
Testing Scores
2.00
3,93
5,325
Probing
Probing
3.800
2:00
(02
Epoch
Epoch
Epoch
Figure Probing results during NCO models training.
right from the start of training, indicating that the LEHD model has already learned how to avoid myopic decisions early the process. What additional information LEHD learns to make its node selection decisions could be further investigated in future research by designing new probing tasks.
Do NCO embeddings encode constraint information, as demonstrated with the CVRP?
We address this by investigating Probing Task 3 and Probing Task 4, which target a critical constraint in CVRP: the capacity constraint. The former focuses on low-level feature, the linear additive relationship among node demands, while Probing Task 4 explores a high-level aspect, examining whether the embeddings produced by NCO models encode information about whether nodes belong to the same route in the optimal solution. Through probing, we verify that NCO models are indeed capable of capturing such knowledge. Detailed results and analysis can be found in Appendix C.1.2
3.3 Probing for Border NCO
How robust is probing when used explore NCO models?
We further investigate the robustness of probing in analyzing NCO models through three additional studies: (1) Besides transformer-basee NCO models, can probing also be applied to other types of models? To examine this, we conduct a preliminary experiment on DIFUSCO (18), a diffusion- based NCO model in Appendix C.2.I The results confirm that the embeddings of diffusion basdd models can also be effectively analyzed using probing. More in-depth investigations, or explorations of additional diffusion- based NCO models 119 20), would be valuable to further illuminate their underlying mechanisms. (2) Can probing be used to explore information in non- Euclidean spaces? In Appendix C.2.2] examine this question using the Asymmetric Traveling Salesman Problem (ATSP) as a case study, and demonstrate that probing is indeed applicable in non-Euclidean settings. (3) Can probing be used analyze other combinatorial optimization problems, applied architectures beyond attention-based NCO models? Appendix C.2.3 we address these questions by applying probing the Job Shop Scheduling Problem (JSSP) and corresponding GNN-based neural model. We use probing to investigate whether the embeddings of NCO models can capture precedence constraint information. The results confirm that probing remains effective in interpreting other deep learning architectures and combinatorial optimization tasks.
Can probing be used to investigate the performance differences among NCO models?
In addition to revealing what types of knowledge are captured by the embeddings of NCO models, the traditional probing methods also provide indirect visions into why different NCO models exhibit varying performance. For example, by analyzing probing performance across problem sizes, we observe that LEHD achieves better probing results larger instances (200-TSP), which aligns with its
5

---

stronger performance in large scale TSP, thereby offering supporting evidence from representational perspective. Additionally, we perform ablation studies on LEHD to investigate the impact of different components and the performance when embedding different nodes, which further strengthens the structural design claims of LEHD. For detailed analysis, please refer to Appendix
However, a more compelling question is whether probing can reveal the internal mechanisms of black- explain performance
box DL models, thereby providing direct-rathe than indirect-evidence differences and uncover the factors contributing to generalization. In the following Section 4 we demonstrate how our proposed CS- CS-Probing method can effectively provide such direct evidence.
4 Opening the Black Box of NCO Models Using CS-Probing
In this section, we demonstrate how our proposed CS-Probing method leads to three key findings: (I) it reveals the distinct inductive biases learned by different NCO models; (2) uncovers the differing generalization mechanisms across models; and (3) it identifies and localizes key embedding dimensions that encode task-specific knowledge. Based on these findings, we further demonstrate the practical value of probing by validating how the analyzed model can enhance its generalization through insights derived from CS- CS-Proning.
4.1 CS-Probing: A New Tool
In addition to systematically designing two sets of high-level and low-level probing tasks tailored for the combinatorial optimization problem, we also propose novel probing analysis tool: analyzing both the absolute magnitude and of the coefficients method as Coefficient Significunce Probing (CS- (CS-Probing). Our proposed CS- enables more fine-grained analysis by examining the role of each individual embedding neuron (or dimension) in capturing specific knowledge. In this section, Probing Task and Probing Task 2) as examples to demonstrate how CS- CS-Probing analyzes NCO models. Other probing tasks can also be analyzed using CS- CS-Probing, and the corresponding results demonstrating that NCO models excel at capturing simple additive constraint-relater information when solving CVRP presented in Appendix D.5
a linear probing model. We refer to this
the first two TSP-related probing tasks (i.c.,
4.2 Inductive Biases
We began by examining the embeddings from different NCO models just before the decision output layer and observed clear differences in their activation patterns. Figure presents heatmap of node embeddings across the NCO models. Specifically, fifty instances are sam- pled from each of the three NCO model datasets, and the embedding of specific node from each instance visualized. The results show that LEHD exhibits strong activation concentrated in fewer than 20 fixed dimensions, with absolute values often in the tens. In contrast, AM and POMO exhibit different inductive biases, char- acterized by more dispersed activation patterns, with no consistently dominant dimensions and significantly smaller coefficient magnitudes (all below 4 in absolute value).
AM
88860
37
43
49
55
23
79
103
109
115
121
88850
3.0
25
77
43
49
55
23
07
103
109
115
122
127
2.8
88060
54.0
19
43
49
55
67
13
05
109
115
122
127
Figure 4: Hcatmaps of node embeddings. The x- axis represents different embedding dimensions, and the y-axis represents the instances.
We further investigate the distinct inductive bi- ases learned by the three NCO models through probing, specifically by analyzing the coefficients of the probing models i.e., via our proposed CS-Probing method. This analysis reveals how the embeddings from different NCO models encode information differently, reflecting their respective inductive biases. In doing so, we demonstrate how CS-Probing helps uncover the potential reasons behind the superior performance better- performing NCO models, validating the claim made in the original LEHD paper [3] that "such

---

(a) AM Probing Task
(b) AM Probing Task 2
0.10
P.S. 0.001
0.05
0.5
P.s 0.01
0.00
11
11
0.0
T1
P. 0.05
-0.05
0.5
1111
11:
-0.10
250
250
2000
200
(c) POMO Probing Task 1
(d) POMO Probing Task 2
0.04
0.4
0.02
0.00
0.0:
0.02
-0.2-
11
11
1111
11
III
250
250
1000
(e) LEHD Probing Task 1
(f) LEHD Probing Task 2
0.15
0.10
2.
0.05
0-
0.00
-2
II
11 18
150
230
Figure 5: Coefficients of probing models for two TSP-related probing tasks across all NCO models.
a dynamic learning strategy enables the model to adjust and refine its captured relationships between the starting/destination and available nodes".
Figure 5 presents the probing model coefficients obtained on the test sets for Probing Task / and Probing Task 2 across the three NCO models. In each subplot, the x-axis corresponds to latent feature dimensions, while the y-axis shows the coefficient values. The top portion of each subplot displays the raw coefficient magnitudes, and the bottom portion illustrates the statistical significance of each feature. The first 128 dimensions represent the embedding of the current node, which the node being visited during the autoregressive decision process of the NCO model, and the next 128 dimensions correspond to the embedding of candidate node, that is, an unvisited node.
we observe that LEHD, the best petttrrrfoming model among these three NCO models, exhibits more statistically significant features in its node embeddings for both TSP-related probing tasks compared to AM and POMO. Specifically, examining the coefficients of each node's ' embeddings of LEHD reveals that for the current node, the probing model's ' coefficients tend to have smaller absolute values, with only a few being statistically significant. In contrast, the embeddings of candidate nodes (those relevant the decision-making process for selecting the next node to visit in the current step) have greater number of statistically significant dimensions. Additionally, we confirm that during training. LEHD progressively develops this property, gradually learning to encode knowledge into specific embedding dimensions, illustrated in Figure 14 in Appendix D.I
From Figure 5]
If we disregard the absolute values of the coefficients and focus solely on statistical significance. this pattern is also observed in AM and POMO during the myopia-avoiddance task, albeit with far fewer statistically significant features in their embeddings compared LEHD. However, when comes to perceiving Euclidean distances, the embeddings of AM and POMO as features show no such distinction. In subplots (a) and (c), the coefficients and the number of significant features for the two nodes' embeddings are similar, regardless of their roles as the current node or other nodes.
4.3 Generalization Mechanisms
We extend the analysis to explore how CS-Probing can uncover direct evidence of generalization in NCO models. Specifically, we show that NCO models with superior generalization performance learn transferable representations, that is, features that generalize beyond the training distribution and enable robust performance on unseen problem instances.
Table 2 shows the CS-Probing results of AM, POMO, and LEHD on two TSP probing tasks, specifically the top 5 dimensions with the largest absolute coefficients. The numbers indicate the dimension indices (starting from 1), with parentheses indicating whether the dimension comes from the current node the candidate node. Bold entries highlight dimensions that are reused during
7

---

generalization, and underlined entries further indicate that their relative ranking remains consistent. To further ensure reliability. we perform multiple hypothesis testing. Specifically,, we apply the Benjamini-Hochher procedure to control the false discovery rate (FDR) ar 0.05 across the 256 tested dimensions. The key LEHD dimensions identified earlier remain significant after correction, consistent with the results in T
The results reveal that in less generalizable models (AM and POMO), the key embedding di- mensions associated with the probing tasks vary across gener- alization scenarios. In contrast, the more generalizable model (LEHD) consistently maintains the same top-2 dims, i.e., the 31th and 69th for Probing Task
Table 2: Top 5 dimensions from CS-Probing results two TSP probing tasks on TSP-20 and TSP- 100 across three models.
Top_n
Dim.
ma 29 rest
Coet.
Sig. level
Uim.
20 matn/ / 100
Coet.
Sig. level
54 (ssndiisee unde)
0.0917
(candidhuc male)
-011031
41 lcundilaee unde)
-0.054
34 (caerent sode]
0,1015
101 (cuereut ande)
8.0848
(candiduee male)
0.0770
95 (comdiiise nade)
-88967
(curmnt rode)
0,7748
134 (camdkdatc mode)
-087122
(candidatc made)
0,0740
Pooling Task
(current mode)
QU0539
89 (candidate mode)
POMO
(candidate uode)
0,0510
(current sode]
0.0404
70 (candiise:
00332
0,0359
1, and the 31th and 97th for
(candiiiaee
-00508
PA-
(candibiie male)
Probing Task 2. Figure 13 (i)-
LEHD
icandidate mode)
(candidate
00718
6 (candidate modk]
31 (candidute node)
0,1703
00093
19.
19+
(I) in Appendix D.2 visualizes this result for the LEHD model, intuitively demonstrating how it consistently utilizes fixed di- mensions to capture relevant in- formation during generalization.
icundilaze uola)
-00633
PA4
(canddda
0,0708
(cundiluee
0.0044
(candidue node)
0,0630
50 (cmmiiio mode)
00526
(cuniidato
0.0509
(currett node)
03561
(candidue nods)
(candidare node)
0.813
(candiduze node)
(condadate 55 (candicare node)
0.6612
(cundidate model
06606
(candbdore node)
Prohing Task
(cundicate node)
0.504
(candidate node)
0,7699
POMO
89 (candidare mode)
0.4088
(candidate node)
-0.989
*.4
In contrast, the visualizations for AM and POMO are pre- sented in Figures 15 (a)-(d) and 13 (e)-(h), respectively.
62 (candidare mode)
0.3236
(cantidore node)
0.5580
110 (condidate mode)
0.3217
(candisbte node)
-0.9100
7 (candidate sode)
0.3081
(candidize noda)
0.4776
***
31 (candidate node)
4.5236
51 icandidate mode)
2,7083
LER0
97 teandidate node)
40741
97 icandidate mude)
-1.556
25 (canditare node)
1,4000
126 (candidate node)
1.3297
85 (canditane node)
1.2421
30 (candidare node)
1 1,2525
These findings collectively sup- port the conclusion that CS-
118 (current mode)
-11650
42 (candidare node)
0.7562
Probing explains the generalization behavior of NCO models by revealing that they consistently reuse the same embedding dimensions to encode specific knowledge (as observed in LEHD). Besides, the results indicate that when the knowledge encoded in specific dimensions becomes disorganized during generalization, model performance deteriorates. To further support this argument, we examine whether AMM and POMO, trained on 20-node instances, can generalize not to the distant 100-node setting, but to instances that are closer in scale (e.g, with 21, 25, 30 nodes). The results show that both models exhibit similar reuse of embedding dimensions when generalizing to 2 21-node instances, suggesting that when generalization is achievable, NCO models tend to capture specific knowledge using a fixed (and small) set of dimensions. The results are listed in Table [4] in Appendix D.3
4.4 Key Embedding Dimensions
Previously, We identify key factors influencing NCO model generalization and provide direct evidence of their performance. Notably, the LEHD model consistently reuses the same top-2 embedding dimensions across different probing tasks and problem scales. Building on this insight, we further demonstrate the practical value of CS-Probing from multiple perspectives.
First, the two key dimensions identified by CS- CS-Probing offer interpretability into how NCO models make decisions within a high-dimensional latent space that is otherwise difficult for humans to comprehend. For example. we examine the LEHD model's behavior on Probing Task 2 (avoiding myopic decisions) by the 2D plane formed by the two key dimensions of LEHD's 's embedding (dimensions 31 and 97). Figure
the result for one instance with the random seed set to one. The left plot shows the optimal solution, and the middle shows the greedy solution. The right plot visualizes the values of the two key dimensions from the final node embeddings output by LEHD (before the softmax layer). In this case, the current node is node 4. A myopic decision based on Euclidean distance would choose node 5, whereas the optimal solution selects node 3. In the 2D space defined by the identified key dimensions, node 4 is indeed closer to node 3 than to node 5. Furthermore, other nodes that are closer to node in this space also appear nearby in the optimal tour, further supporting our interpretation.
8

---

Optimal TSP Tour
Best Greedy Tour (Starting Node 8)
Two Dimensions by CS CS-Probing
1.0
40
18
18
019
1
97th dimension
18
9
30
1
0.6
0.6-
25
12
20
17 16
0.4-
15
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
10
20
50
40
X
X
31th dimension
Figure 6: Routing solutions (see Appendix 1.2 for details on how to obtain) and the key two- dimensional embeddings in the node representation of LEHD.
These results reveal how -bx models make decisions by identifying the most informative embedding dimensions that encode the knowledge required for specific decision types. Additional results on other random seeds are in Appendix D.4
The second practical value of CS-Probing lies in its ability validate model architecture and provide insights for future model design. Regarding the relationship between CS-Probing findings and model structure, we observe from the 2D plots of the two key dimensions (Figures 6 16 that LEHD not only avoids myopic behavior but also consistently positions the current node in the bottom-left corner, clearly separated from other nodes. This spatial separation directly reflects the effect of LEHD's architectural design, in which candidate node embeddings are ce-encoded at each decision step to enhance the capture of recision-relevane information.
Table 3: Results of only two dimensions from LEHD's output embedding.
Table 4: Performance degradation from zeroing key vs. non-key dimensions in LEHD.
Prontem Dimensiente)
Oprimality
All 124
31,97
(1.55%
0,577
Zeroing Dimension(s)
Optimality Gap
32. 22.97
(8.75%
Nonetoriginal)
0.57%
31, 97
60.43%
7,78
384.195
31
0.90%
18852
97
1.80%
98
0.59%
1000 500
All 128
1.5R
0.60%
31,97
1.999
98, 126
0.62%
All 128
3.179
31.97
S.500
Thirdly, across multiple results and insights obtained by CS- CS-Probing above, we find that LEHD's final- layer embeddings, just before the output layer, can capture both low-level and high-level knowledge using only small number of dimensions. To explore whether the model can make decisions using only these key dimensions, we conduct an experiment where we retain only the two most important ' 1 28-dimensional output. Remarkably, the model still achieves nearly equivalent performance. In particular, we identify two key dimensions of LEHD model trained on 100-node instances using CS-Probing, as described in the previous sections. We then evaluate LEHD models trained on instances of other scales using only these two dimensions, and they continue to generalize effectively to 200- 500-, and even 1000-node problems, yielding results comparable to those obtained using the full embedding. See Table 3 for detailed results. To further validate, conduct neuron ablation: zeroing the two key dimensions (31 and 97) causes performance to collapse (more than 60% gap), while zeroing non-key but seemingly important dimensions yields little impact (Table 4. Specifically, dimension 98 is chosen because it exhibits large activation values in the embedding visualization (from Figure 4. and dimension 126 is selected because it has the highest probing coefficient among all non-key dimensions (from Table (2).
dimensions (as identified by CS- CS-Probing) from LEHD's
One key insight emerging from this finding is the potential benefit of imposing regularization or constraints on embedding dimensionality during LEHD model training. This raises important questions about whether dimensional efficiency could further improved through its architectural or training adjustments. In the following section, conduct preliminary exploration of this idea. For

---

future work, it would be valuable to explore how embedding dimensionality should be configured across different layers and training stages to enhance both efficiency and generalization.
4.5 Practical Implications
We conduct a simple yet effective experiment based on insights from CS-Probing. Since LEHD) generalizes better than other models by relying on small subset of embedding dimensions, we introduce a regularization term to promote sparsity in its final-layer embeddings. With only minor code changes, this improves generalization. As shown in Table 3 we train LEHD with different regu- larization strengths (A) on TSP100 and evaluate transfer to TSP200 and TSP1000, measuring the gap best known solutions. The baseline (origin, namely x=0) corresponds to the unregularized model, while moderate regularization (A=le-6 to 1e-3) improves generalization at larger scales. We also test cross- diss-iiistiittioon generalization by training on uniform instances and testing on TSPLib. These results provide preliminary evidence that regularization may enhance generalization performance and highlight the potential of probing insights as an analytical tool for informing model design.
Table 5: Results of LEHD models trained with different regularization strengths (A), demonstrating generalization performance across problem scales and distributions.
origin
le-6
le-5
le-4
le-3
TSP100
0.57%
0.58%
0.57%
0.57%
0.57%
TSP200 (generalization)
0.86%
0.88%
0.86%
0.73%
0.82%
TSP1000 (generalization)
3.17%
2.87%
2.93%
2.97%
3.05%
(apPribgeneralizzatoo)) 5.26%
4.94%
4.99%
5.05%
8.61%
It is important note that these analyses are not intended to argue that a particular transformer- based architecture is inherently superior, nor that all models should employ sparsity-inducig regularization. Rather, by using LEHD as a case study, we aim to validate the practical value of CS-Probing. Overall, this work presents the first systematic attempt to apply probing to NCO research, introducing the CS-Probing tool means of analyzing and better understanding the internal mechanisms of NCO models. This opens up new pathway for both analyzing and improving NCO models. We believe that extending these analyses to broader set of models the future will enable more transparent and trustworthy pathways for advancing research on NCO models.
5 Conclusion
In this paper, we introduce probing into the study of NCO models to systematically investigate their learned embeddings and to advance the understanding of the internal mechanisms underlying these black-box approaches. We systematically design probing tasks and employ proposed CS-Probing method to investigate what decissoon-relttd knowledge NCO models capture and how they encode this knowledge. Additionally, we demonstrate the practical value of probing by providing empirical support for claims regarding the design of NCO models, offering evidence to explain mechanisms such generalization performance, and generating insights to guide future research in the NCO field.
One of these insights is that inference can achieve comparable results using only two key dimensions discovered through CS-Probing. This finding highlights a potential avenue for compressing, distilling, and pruning the representation space of NCO models, as well as investigating the dimensionality of NCO model representations.
Another potential direction to explore additional knowledge to further enhance the transparency and interpretability of NCO models. Much like how DNA sequencing revolutionized genetics, our proposed CS- CS-Probing offers a powerful lens for understanding NCO models by identifying specific dimensions within high-dimensiona embeddings that encapsulate essential knowledge. As more probing tasks emerge, this approach has the potential to progressively transform black-box representations into interpretable, structured forms, offering promising and impactful direction for the field. Enhaneing transparency and interpretability could significantly promote the broader application of deep learning models in scientific and engincering domains.
10

---

Acknowledgments
This research supported by the National Research Foundation, Singapore under its Al Singapore Al Research Fundamental Research Collaborative (US-NSF Researcher Call) (AISG Award No: AISCI-RRP-022553--USNN7Y7 This research is also supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No: AISG2- 1002-1000-2202-11 18). Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore.
References
[1] D. Applegate, R. Bixby, V. Chvátal, and W. Cook, "Concorde tsp solver," 2006. [Online]. Available: https::/www.math.u www.tttuwwtteroooooomm www.terloo...assp/ooooooooo wwt.s///cooooodee.nni.
[2] H. Ye, J. Wang. Z. Cao, Liang, and Y. Li, "Deepaco: Neural-enhanced ant systems for combinatorial optimization," Advances in neural information processing systems, vol. 36, pp. 43 706 43 728, 2023.
[3] K. Helsgaun, "An extension of the fnt-kennighan-helsgaeen tsp solver for constrained traveling salesman and vehicle routing problems," Roskilde: Roskilde University, vol. 12, pp. 966 980, 2017.
[4] Vidal, "Hybrid genetic search for the evrp: Open-source implementation and swap* neigh- borhood," Computers & Operations Research, vol. 140, p. 105643, 2022.
[5] G. Alain and Y. Bengio. "Understanding intermediate layers using linear classifier probes," arxiv preprint arXiv: 1610.0164, 2016.
[6] Y. Adi, E. Kermany, Y. Belinkov, O. Lavi, and Y. Goldberg, "Fine-grained analysis of sentence embeddings using auxiliary prediction tasks," arXiv preprint arXiv: 1608. 0408004277, 2016.
[7] Y. Belinkov, "Probing classifiers: Linguistics, vol. 48, no. pp. 207-219, 2022.
Promises, shortcomings, and advances," Computational
[8] N. F. Liu, M. Gardner, Y. Belinkov, M. E. Peters, and N. A. Smith, "Linguistic knowledge and transferability of contextual representations." arXiv preprint WeXiv:/03..0850 2019.
[9] S. Zhao, T. Nguyen, and A. Grover, "Probing the decision boundaries of in-context learning in large language models," arXiv preprint arXiv:2406. /233, 2024.
[10] W. Gurnee and M. Tegmark, "Language models represent space and time," arXiv preprint WxXiv23300002201 2023.
[11] W. Kool, H. Van Hoof, and M. Welling, "Attention, learn to solve routing problems!" arXiv preprint arXiv: 18903008475 2018.
[12] Y.DD. Kwon, J. Choo. B. Kim, I. Yoon, Y. Gwon, and S. Min, "Pomo: Policy optimization with multiple optima for reinforcement learning," Advances in Neural Information Processing Systems, vol. 33, pp. 21 188 21 198, 2020.
[13] F. Luo, X. Lin, F. Liu, Q. Zhang, and Z. Wang, "Neural combinatorial optimization with heavy decoder: Toward large scale generalization," Advances in Neural Information Processing Systems, vol. 36, pp. 8845-8864, 2023.
[14] A. Conneau, G. Kruszewski, G. Lample, L. Barrault, and M. Baroni, "What you eram into a single vector: Probing sentence embeddings for linguistic properties," " arXiv preprint arXiv:1805.011
2018.
[15] D. Dai, L. Dong. Y. Hao, Z. Sui, B. Chang, and F. Wei, "Knowledge neurons in pretrained transformers," arXiv preprint SEEi:2104008690 2021.
[16] M. Geva, R. Schuster, J. Berant, and O. Levy, "Transformer feed-forward layers are keyuv memories," arXiv preprint rrXi::2012.14913 2020.
[17] B. Z. Li, M. Nye, and J. Andreas, "Implicit representations of meaning in neural language models," arXiv preprint arXiv:2106.00737. 2021.
[18] 7. Sun and Yang, "Difusco: Graph-based diffusion solvers for combinatorial optimization,"
Advances in Neural Information Processing Systems, vol. 36, pp. 3706-3731, 202.,

---

[19] Y. Li, J. Guo, R. Wang, and J. Yan, "T2t: From distribution learning in training to gradient search in testing for combinatorial optimization,"" "Advances in Neural Information Processing Systems, vol. 36, pp. 50 020-50 040,, 2023.
[20] Y. Li, Guo, R. Wang. H. Zha, and J. Yan, "Fast 12t: Optimization consistency speeds up diffusion-based srining-to-testing solving for combinatorial optimization," Advances in Neural Information Processing Systems, vol. 37, pp. 30 179-302066 2024.
[21] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L.. Song. "Learning combinatorial optimization algorithms over graphs," Advances in neural information processing systems, vol. 30, 2017.
[22] Y. Bengio, A. Lodi, and A. Prouvost, "Machine learning for combinatorial optimization: a methodological tour d' d'horizon," European Journal of Operational Research, vol. 290, no. 2, pp. 405-421, 2021.
[23] W. Kool, H. van Hoof, J. Gromicho, and M. Welling, "Deep policy dynamic programming for vehicle routing problems," " in International conference on integration of constraint programming. artificial intelligence, and operations research. Springer, 2022, pp. 190-213.
[24] J. Zhou, Y. Wu, 7. Cao, W. Song. J. Zhang, and Z. Chen, "Learnin large neighborhood search for vehicle routing in airport ground handling," " IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 9, pp. 9769-9782, 2023.
[25] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio, "Neural combinatorial optimization with reinforcement learning," arXiv preprint arXiv: 1.09940, 2016.
[26] M. Nazari, A. Oroojlooy, L. Snyder, and M. Takáe, "Reinforcement learning for solving the vehiele routing problem," Advances in neural information processing systems, vol. 31, 2018.
[27] H. Lu, X. Zhang, and S. Yang, "A learning-based iterative method for solving vehicle routing problems," in International conference on learning representations, 2019.
[28] Y. Ma, J. Li, Z. Cao, W. Song, L. Zhang, Z. Chen, and J. Tang. "Learning to iteratively solve routing problems with dual-aspect collaborative transformer," Advances in Neural Information Processing Systems, vol. 34, pp. 11 096-11 1 107, 2021.
[29] Y. Ma, Z. Cao, and Y. M. Chee, "Learning search feasible and infeasible regions of routing problems with flexible neural k-opt," " Advances in Neural Information Processing Systems, vol. 36, pp. 49 555-59 578, 2023.
[30] H. Ye, J. Wang, H. Liang, Z. Cao, Y. Li,, and F. Li, "Glop: Learning global partition and local construction for solving large-scale routing problems in real-time," in Proceedings of the AAAI conference on artificial intelligence, vol. 38, no. 18, 2024, pp. 20 292.
[31] í. Santana, A. Lodi, and T. Vidal, "Neural networks for local search and crossover in vehi- cle routing: a possible overkill?" in International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, 2023, pp. 184-199.
[32] K. Meng, D. Bau, A. Andonian, and Y. Belinkov, "Locating and editing factual associations in gpt," Advances in neural information processing systems, vol. 35, pp. 17 359-177777 372, 2022.
[33] K. Li, A. K. Hopkins, D. Bau, Viégas, H. Pfister, and M. Wattenberg, "Emergent world representations: Exploring sequence model trained on synthetic task," arXiv preprint ar 13382, 2022.
[34] J. Shah, Y. K. Singla, C. Chen, and R. R. Shah, "What all do audio transformer models hear? probing acoustic representations for language delivery and its structure," arXiv preprint 0XXiv:2101.00338 2021.
[35] J. Ngo and Y. Kim, "What do language models hear? probing for auditory representations in language models," arXiv preprint arXiv:2402. 16998, 2024.
[36] W. Zhang, A. GX-Chen, V. Sobal, Y. LeCun, and N. Carion, "Light-weight probing of unsuper- vised representations for reinforcement learning," arXiv preprint arXiv:2208. 12345, 2022.
[37] Z. Allen-Zhu and Y. Li, "Physics of language models: Part 3.1, knowledge storage and extrac- tion," arXiv preprint arXiv:2309. 14316, 2023.
[38] G. Reinelt, The traveling salesman: computational solutions for TSP applications. Springer, 2003, vol. 840.
12

---

[39] F. Liu, C. Lu, L. Gui, Q. Zhang, X. Tong, and M. Yuan, "Heuristics for vehicle routing problem: survey and recent advances," arXiv preprint arXiv:2303.04147, 2023. 2023.
[40] R. Bellman, "On routing problem." Quarterly of applied mathematics, vol. 16, no. pp. 87-90, 1958.
[41] E. Hart, J. Nilsson, and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths," IEEE transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968.
[42] C. Chekuri and M. Pal, "A recursive greedy algorithm for walks in directed graphs." in 46th annual IEFE symposium foundations of computer science (FOCS IEEE, 2005, pp. 245-253.
[43] A. Meliou, A. Krause, C. Guestrin, and J. M. Hellerstein, "Nonmyopic informative path planning in spatio-temporal models," in AAAI, vol. 10, no. 4, 2007, pp. 16-7.
[44] Gurobi Optimization, LLC, "Gurobi Optimizer Reference Manual," " 2024. [Online]. Available:
https:/wwwwguurbb.com
[45] Y. Wang, Y.-H. Jia, W.-N. Chen, and Y. Mei, "Distance-aware attention reshaping: En- hance generalization of neural solver for large-scale vehicle routing problems," arXiv preprint SKKiv22401.09973 2024.
[46] C. Zhou, X. Lin, Z. Wang, X. Tong, M. Yuan, and Q. Zhang, "Instance-conditioned adap- tation for large- scale generalization of neural combinatorial optimization," arXiv preprint 2024.
arXiv:2405.011
[47] Y.-D. Kwon, J. Choo, I. Yoon, M. Park, D. Park, and Y. Gwon, "Matrix encoding networks for neural combinatorial optimization," Advances in Neural Information Processing Systems, vol. 34, pp. 5138-5149, 2021.
[48] C. Zhang, W. Song, Z. Cao, J. Zhang, P. Tan, and X. Chi, "Learning to dispatch for job shop scheduling via deep reinforcement learning," Advances in neural information processing systems, vol. 33, pp. 1621-1632, 2020.
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 core claim of this paper is that introducing probing provides a more transparent and interpretable approach to exploring NCO models. Our experimental results and the insights gained from them demonstrate the significant value of probing, reinforcing our claim.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 as long as it is clear that these goals attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Appendix D titled "LLimitations". we discuss the potential challenges faced by the probing method and provide alternative solutions to address these challenges.
13

---

Guidelines:
The answer NA means that the paper has no 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 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 (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions 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 of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification: This study is empirical in nature and does not contain theoretical research components. The effectiveness of probing has been extensively validated in prior studies. For more details, please refer to the related works on probing presented in Appendix A.2
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 the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main 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]
we discuss the reproducibility of the codes and datasets. As described therein, codes provided in our link can directly generate the required datasets and facilitate the experiments presented in this paper.
Justification: In Appendix B.3
14

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to 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 NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- 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 to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Appendix B.3 we provide a link containing the codes for dataset generation
and probing experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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
/ ptaips.cc//uulic//uuu
for more details.
The authors should provide instructions on 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.
15

---

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: In Section 3. the main text, we present our experimental setup and provide references to the detailed descriptions in Appendix B
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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the standard deviation values, for example, in Table T presented in Section 3.2 The results include the mean and deviation values obtained from 10 independent probing training runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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.
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 out of range (e.g. negative enror 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 or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
16

---

Justification: In Appendix B.4 we discuss the computational resources used for the ex- periments and the dataset collection process. Additionally, Appendix we provide an overview of the estimated time required for the computationally intensive dataset collection process in Table
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or 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 well 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 make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have thoroughly reviewed the NeurIPS Code of Ethics and ensured that this study does not involve any violations.
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.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This study constitutes foundational research.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal 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 not 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 improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as 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).
17

---

11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This study does not involve data or models that pose high risk of misuse.
Guidelines:
The answer NA means that the paper poses 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 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: All models and other contributions from other authors referenced in this paper have been properly cited, and the corresponding URLs are provided Appendix A.I.I
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 or dataset.
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 are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pateessipppswiiiiee..... 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 is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide the URL in Appendix B.3
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
18

---

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 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: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, 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 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 NeurlPS 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
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
We only use LLMs for grammar correction and text polishing.
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 our L.LM for what should or should not be described.
19

---

A Related Work
A.1
NCO
Neural (deep borming-basedd methods have been applied to various combinatorial optimization problems for several years [21 [2]. With the rapid advancement of deep learning (DI.), an increasing number of approaches have been introduced to address these classical problems in operations research (OR). the context of the routing problem discussed in this paper, researchers have explored methods such as graph convolutional networks (GCNs) [23] 24], pointer networks with recurrent neural networks (RNNs) [25 26]. diffusion-based approaches [18 [9 20). and attention mechanisms
28
29
30
13 which are the primary focus of this study.
A.1.1 AM, POMO, LEHD
AM one of the earliest and most successful attention mechanisms- based models for routing tasks. It is pioncering in introducing the widely popular Transformer architecture to combinatorial optimization problems, inspiring a multitude of subsequent models. POMO [12), as a notable example, retains structure fundamentally similar to AM (with minor differences, such as in context embedding) but introduces a novel reinforcement learning (RL) training method.
AM not only introduces the Transformer architecture but also makes significant contributions to the model design for routing problems. A notable idea AM's context embedding the decoder, which focuses on the current node and the starting node (for TSP problems). Although many later models do not adopt this exact context embedding design, the core idea focusing on these two key nodes remains. For example, even though LEHD's decoder design differs from AM's, it fundamentally considers how to represent information from these two critical nodes.
Specifically, the difference between LEHD illustrates the architecture of both models. Figure T (). AM uses a multi multi-layer encoder to learn how to represent node information based on their input features (coordinates), while the decoder performs single attention computation on the node representations generated by the encoder, producing a global "glimpse" for decision-making without updating the node embeddings. This is known as the "Heavy Encoder Light Decoder" structure. contrast, LEHD adopts "Light Encoder Heavy Decoder" structure, where the encoder uses only a single attention layer to learn node representations, while the decoder, at each step, re-learns the embeddings of the current node, destination node, and candidate nodes through multiple attention layers. In LEHD, shown in Figure [ he and ha represent the embeddings of the current node (referred to as the starting node in LEHD) and the destination node, while the node embeddings located in the middle are filtered in LEHD to exclude previously visited nodes.
and AM lies in their architectural design. Figure
A.1.2 Concerns
Although NCO methods have rapid development in academia, industries remain cautious about deploying them to replace classical OR methods. This because these DL-based methods perceived as black-box models, lacking the reliability and interpretability of traditional OR approaches. As a result, even though some NCO models have achieved strong performance on certain instances, they are still met with skepticism. For example, (3I) raises concerns about the overuse of GNNs, noting that the improvements achieved by GNN-based methods over traditional distance- related approaches were minimal. To address this, we are the first to unveil the inner workings of NCO models, aiming to enhance understanding of their internal mechanisms.
A.2 Probing
The probing method used in this paper was initially applied to understand the representations of DL models in computer vision 5 and natural language processing 6 14 17 15] 32). Beyond traditional
DL tasks, probing has also demonstrated effectiveness in other domains, such as exploring world
representations 33 [0] and in-context Iearminn
[9] in large language models, auditory representations
20

---

34 351, and studying the quality of unsupervised reinforcement learning representations [36]. A systematic use of probing to analyze a deep model's ability to extract and store knowledge can be seen in [37,, which investigates how large language models encode vast amounts of world knowledge as case study.
In the field of NLP, prior work such as [1, [6 has explored the use of probing techniques to identify key neurons, aiming analyze the knowledge learned by deep learning models. Notably, [6 demonstrated that the learned patterns in the feed-forward layers of Transformer models are numan-interpretable: lower layers tend encode shallow syntactic features, while higher layers capture more abstract semantic representations. Similarly focusing on neurons in feed-fore forward layers, [10 identified individual "space neurons" and "time neurons" that consistently encode spatial and temporal coordinates in large language models, by computing the cosine similarity between each predefined probe direction vector. In contrast these studies, our work focuses on NCO models and investigates how they represent problem-specine input information-sue
neuron's 8 input or output weight vector
nodes routing problems. Accordingly, we primarily analyze the model's embeddings, where "neurons" in our context refer to individual dimensions within the embedding space. While our current analysis centers on the embedding layer, we believe that probing the feed-forward layers of Transformer-based NCO models presents promising direction for future research.
B Design and Setup of Probing Tasks
The steps for using probing to explore deep learning representations are as follows: first, define the probing task based the target information to be explored; second, collect the labels required for the probing dataset, ensuring they are relevant to the target information; third, combine the embeddings from the deep learning model with the labels to complete the probing dataset; and finally, train the probe and evaluate its performance on out-of-sample data. Figure 7 shows the process of creating and labeling the probing dataset.
Instances
Coordinates
Embeddings
Probing Data
11
NCO Model
Ag à
| - 21
Inatoncet
14
12
NCO Model
la
Rx
||
16
Trstaneed
Figure 7: The process creating the dataset for Probing Task I is illustrated from left to right. For given instance, input its complete data (all nodes) into the NCO model being probed (with the dashed box representing the same NCO model). We then extract the embeddings from the probed part (e.g., the encoder decoder) or layer of the model and select the corresponding embeddings of the required nodes as features. These features, combined with the label, form a single data point.
21

---

B.1
Four Probing Tasks
B.1.1
Probing Task I: Euclidean Distance
When solving routing problems in Euclidean space, the Euclidean distance between nodes is critical piece of information for all solution methods. For instance, a simple greedy algorithm for solving the TSP starts at arbitrary node, computes the Euclidean distance between the current node and all unvisited nodes, and selects the nearest one as the next destination. This process is repeated until all nodes are visited, returning the starting node to form Hamiltonian cycle. In traditional methods, whether using exact approaches (mathematical programming) that rely on the distance matrix of nodes as input or approximate (heuristic) methods [38 39), the Euclidean distance between any two nodes must be precomputed or computed on the fly. Therefore, for a TSP solver, recognizing the Euclidean distances between nodes is essential. Based on this, we aim to explore whether a trained learning- based NCO model can capture this critical Euclidean distance between the current node and any of the candidate nodes in its representations.
Probing task. Probing Task aims to examine whether the embeddings of NCO models encode the distance between the current node and any of the candidate nodes during decision-making. Given the embeddings of two nodes, a probing model is trained to directly predict the Fuclidean distance between them. This probing task, which takes two embeddings as input features, is similar to the probing tasks used in NLP to evaluate pairwise relations between words (8)
Dataset. Figure 7 jillustrates the process of creating sample for Probing Task I and its corresponding dataset. Given the current node n; and any randomly selected node n; from the candidate nodes, we extract their embeddings h, and h from the relevant layers of the NCO model we want probe. The embeddings of the two nodes are then concatenated into a feature vector [hg hyl. with the Euclidean distance between n; and n. serving as the label. By collecting sufficient data in this manner, construct the dataset for Probing Task 1. Since the label (i.e., the distance) is a continuous, Probing Task / is framed regression prediction task.
B.1.2 Probing Task 2: Avoidance of Myopia
Selecting the next unvisited node solely based on the nearest Euclidean distance, as in the greedy algorithm, will not result in the optimal solution from a global perspective. This approach is often described "myopic", and many efforts have been made to avoid such shortsighted strategies A well-designed NCO model must similarly learn to avoid myopic strategies and adopt more global perspective solve the problem effectively. To investigate this, we design Probing Task 2 to explore whether the embeddings of NCO models exhibit the ability to avoid shortsighted decisions at given step.
40
41
42 45
Probing task. We define Probing Task 2 as a binary classification task, where the probing model is trained to determine whether the current node (c.g., n2,) should be linked to node ny. Node n, could either be a myopic choice that leads to a local optimum or the node connected to n, in the global optimal solution. To assess whether the NCO models make myopic decisions by choosing the nearest Euclidean distance, we construct data points as illustrated in Figure
Dataset. First, we randomly generate an instance with N nodes, input it into a mathematical programming model, and use the Gurobi 44 solver obtain the theoretical optimal solution, as shown in Figure a).. Next, starting from each node, we use a greedy algorithm to generate N solutions and select the best one (as illustrated in Figure Bb). gradually comparing the next node selected by the greedy algorithm with the optimal solution. For example, in the instance shown in Figure g when the current node is node 4, the optimal solution selects node 3, whereas the greedy algorithm selects the nearest one, node 5. Ultimately, we obtain two data points for this instance: node connected to node 3 represents the optimal choice, labeled as a positive example (i.c., the feature is [/4, hy] and the label is 1), while node 4 connected to node 5 represents the myopic choice of the greedy algorithm, labeled as a negative example (i.e., the feature is [h4, ha] and the label is O).
Domain knowledge. Unlike the relatively straightforward probing tasks and datasets in CV and NLP, probing in the CO field requires incorporating domain-specifur knowledge. For instance, in this dataset, there may be multiple optimal solutions. Suppose one of them includes node 4 connected to node 5, which would render label of incorrect. To verify this, we add a constraint to the mathematical model that forces the connection between nodes 4 and 5. The new optimal solution
22

---

Optimal TSP Tour
Best Greedy Tour (Starting Node 8)
10
10
146
146
18
18
0.0
0.
1
0.6
0.6
16
16
15
15
0.4
0.4
17
17
0.2
0.2
9
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
1.0
x
(a)
(b)
Figure 8: An example of solutions to the TSP for specific instance: (a) represents the optimal
solution generated by the mathematical model and solved using Gurobi; (b) shows the best solution obtained through greedy algorithm.
obtained under this constraint is worse than the original solution without the constraint. Similarly, for data labeled 1, we add constraint preventing the connection between nodes 4 and and the resulting solution is also worse. This confirms that both labels are valid.
B.1.3 Probing Task 3: Perception of Constraints
For the TSP problem, the first two probing tasks provide a comprehensive analysis of the representa- tional capacity of NCO models. However, for more complex VRP, where additional constraints are introduced, we are curious whether NCO models can capture these constraint-related information. not, it suggests that NCO models might merely rely on masking to artificially limit their outputs. This would imply inherent limitation in how NCO models handle constraints.
Probing task. To answer this question, we design Probing Task 3 explore whether NCO models can capture the knowledge required to determine the feasibility of the capacity constraint in the CVRP problem. Since the capacity constraint primarily involves the linear (additive) relationship among the demands of nodes, we design Probing Task 3 to check whether the embeddings of two nodes can represent the sum of their demands. Thus, for Probing Task probing model trained to predict the sum of the demands given the embeddings of two nodes.
Dataset. We extract the embeddings of two nodes, h4 and h,, from the relevant layers of the NCO model being probed. Unlike the previous non-linear probing tasks, predicting the sum of two demands-a linear addition task-may be inherently
simple. Therefore, linear probing model might not be sufficient to demonstrate whether the NCO model can capture this knowledge. To delve deeper, in addition concatenating the embeddings of the two nodes ([h,, hyD as the input for the probing task, we also apply Hadamard product on the two embeddings, [h; O h,1. as an alternative input. The latter approach aims to simulate the attention computation process in attention-base models (as in most models where the decoder ultimately uses attention to compute compatibility score to determine node selection probability). allowing us examine whether the model can capture the additive effect of demand features.
NCO
B.1.4 Probing Task 4: Same Route
Probing Task 3 investigates low-level feature related to the capacity constraints in CVRP-whether embeddings of nodes contain information about their demands. Next, we explore a higher-level, more abstract feature: determining whether two nodes belong to the same route. In the CVRP solution, there are multiple routes, and if two nodes are on the same route the optimal solution, solution where they are not the same route is highly unlikely to be optimal. If NCO models
23

---

can perceive this information from a global perspective while solving CVRP, they are more likely to achieve higher-quality solutions closer to the optimal.
Probing task. We designed Probing Task 4 to explore this, formulating it as a binary classification problem. The input to the probe consists of the embeddings of two nodes, while the output is a binary value indicating whether the two nodes belong to the same route.
Dataset. After generating the CVRP instances, we use the HGS 4 to obtain approximate optimal solutions due to the large problem size. The other steps are similar to those in Probing Task 2 and will not be elaborated on here.
B.2
Summary and Statisties of Four Probing Task Datasets
B.2.1 Routing Instances and Probing Datasets
For Probing Task I and Probing Task 2, generate 10,000 TSP instances with 20 nodes, 100 nodes, and 200 nodes, respectively, following the method introduced in AM [11), which was subsequently used by both POMO and LEHD. For Probing Task 3 and Probing Task 4, we similarly generate 10,000 CVRP instances with 20 nodes and 10,000 instances with 100 nodes following the method used in AM.
After generating the routing problem instances, we feed them into the NCO model to extract embed- dings. Each probing dataset is split into training and test sets, with all reported results based on the test set, i.c., out-of-sample data.
B.2.2 Overview of Probing Inputs
For a finer- sher-grained analysis. we extract embeddings from different layers and positions, as indicated by the red arrows in Figure Here, we provide a detailed explanation of these extracted embeddings. Another reason for introducing these embeddings is to facilitate the understanding of the main results presented later, specifically the "Probing input" columns in Table 9 and Table T0
We use the names listed under the "Probing Input" column in these tables to clearly indicate the different embeddings used as inputs. The first segment (AM, POMO, LEHD) indicates from which NCO model the embeddings are extracted. The second segment (Init., Enc., Dec.) represents the different parts of the NCO model from which the embeddings are extracted: initial embeddings, encoder embeddings, and decoder embeddings, respectively.
In the encoder of the NCO model, the initial embeddings (Init.) are extracted before the attention layer, as shown at position P1 in Figure [ P2 and P5 represent the embeddings from the encoder's attention layers (Enc.), while P6 represents those from the decoder's attention layers (Dec.). We use "I" followed by a number indicate from which specific layer the embeddings are extracted. Specifically, AM's encoder has three layers, POMO's encoder has six layers, and LEHD's Dss encoder has only one layer, while its decoder has six layers.
Since AM and POMO do not update node embeddings in the decoder, their node embeddings in decoder are not included as probing inputs. However, they introduce context embeddings in the decoder to represent the information needed for routing decisions. For example, in solving TSP, the context embeddings are formed by concatenating the embedding of the starting node h,, the current node embedding, and the graph embedding To explore the representational capacity of this design, we also use the context embeddings [h, hj. h,, hyraph as probing inputs, denoted as "AM-Enc-/3-wec.. Additionally, AM uses the context embeddings as a query to compute attention with other node embeddings, generating a glimpse embedding h hglsmpse. To test this, we probe the input [h; hy. hggimpse] and denote it as "AM-Enc- 13-w/g.. In Figure[]] [ P3 and P4 represent the positions where the context embeddings and glimpse embeddings are extracted, respectively.
calculateee as the mean of all node embeddings.
Additionally, for the first two probing tasks, besides using [h;, hy] as input, we also consider the element- wise product of the two node embeddings as an interaction term [8] i.c., [h,, hj. h, @ hy] as input. Some parts of certain models may linearly combine node embeddings (for instance, many NCO models concatenate the embeddings of nodes and then pass them through a linear projection). In such components of the models, the embeddings are expected to capture decision-relevant information through simple linear combinations. However, embeddings from certain parts in attention-base
24

---

models, such as those used to compute a compatibility score among node embeddings through attention mechanisms, may behave differently. In this case, relying solely on the linear input [h h,] may not fully assess the model's 's representational capacity. Therefore, we introduce the interaction term hy @ hy to emulate the attention computation. We conduct probing experiments with both input methods: "w/o ints." refers to input without interaction terms [h, h21. and "w/ ints." refers to input with interaction terms [h,, hg. h2 O hjl. as shown in Table 9 and Table 10
For Probing Task 3, we use both [4, h;] and [h; C hj] as inputs (the rationale is discussed in the Probing Task 3 paragraph in Section B.1.3). In Table I0 the "w/o ints." " rows correspond to the results for [h,, hy], while the "w/ ints. rows correspond to the results for [h; @ hy]. Finally, for the 20-node and 100-node instances, we conduct the four probing tasks using NCO models trained on the corresponding scales. The results for both are grouped and presented in Table and Table I0]
Table 6 Table 7 and Table present the specific features, labels, and the number of observations for the different inputs across the four probing tasks.
Table 6: The details of Probing inputs of Probing task I.
Probing input
# Observations
Features
Label
Coordinates
[2,, 77gl
AM-Init
[hs. ht]
AM-Ene-[1
[hy. ht]
AM-Enn--3
[hi hy]
w/o ints.
AM-Enc-I3-wer /3-
[hg. hy. Rgraphl
10000
AM-Enc-13-w/g
[hg hj. Hylhmppel
|x - xyll
POMO-Ene-I1
[k, hyl
POMO-Enc-I6
[h, hyl
LEHD-Enc-Il
[hs. hg]
20 and 100
LEHD-Dec-ll
[hg hy]
GEHD-Dec-lt
[h., hyl
Coordinates
[at4 Tiy. 3y @ 2t,1
AM-Init
[hc. Rg.. his @ ht]
AM-Enc-I1
[h,, Ng. h1g @ [t]]
w/ Vntss.
AM-Enc-13
[h, hy, hg S hy]
AM-Enc-I3-we
[hs, hg. Agraphs h4 G
hy]
AM-Enc-13- Enc-13-w// w/g
10000
[hs, hg. Agtimpaes h4 ②
hy]
|
xyll
POMO-Enc-I1
[hr, h5. hg @ hy]
POMO-Enc-16
[he hy. h, < h,1
LEHD-Enc-A
[Rc, leg. h; @ h,]
LEHD-Dec-ll
[Rg le.. h1 @ h,]
LEHD-Dec-16
[h. Ny. h, @ h,
B.2.3 Analysis of Input Data
Before conducting each probing task, we begin by analyzing the input probing dataset, using the 20-node dataset as an example for dataset exploration and preprocessing. As this regression problem, we first analyze the target variable to observe whether the label distribution is skewed, whether there are outliers, and other characteristics. Figure P shows the label distribution for the 20-node dataset in Probing Task I and Probing Task 3, with the dataset generation process detailed previously. As seen, the distribution of distances between randomly selected nodes after current node is chosen approximates normal distribution. The distribution of demand follows similar pattern. For Probing Task 2, we generate one data point with label of and one with a label of 0 for each routing instance, resulting in 1:1 label distribution.
Next, we conducted feature correlation analysis on the probing dataset. For the probing dataset formed by the embeddings of two nodes (128 dimensions each), there are a total of 256 features. By examining the correlation heatmap in Figure TO, We observe some positive and negative correlations among the 128 dimensions within both single node's 's embedding, but their number is limited, far fewer than the statistically significant latent features presented Section 4.2 We can also observe that there are a few scattered stronger correlations in LEHD's embedding, which could be the source of its enhanced ability to retain the perception of Fuclidean distance. Additionally, there is no significant correlation between the embeddings of the two nodes.
25

---

Distribution
Demand Distribution
1000
500
Frequency
400
Frequency
600
100
200
100
200
0.00
0.25
0.50
0.75
1.00
1.25
0.1
0.2
0.3
0.4
0.5
0.6
Distancee
Demand
Figure 9: Label distribution for probing datasets in Probing Task I and Probing Task 3.
1.50
0.75
375
0.50
0.00
-2225
-525
-0.50
-2.00
-3.00
LEHD-Dwc-15
1.00
2.00
0.75
0.00
3.00
-.225
-2.15
-2.73
2.00
2.00
Figure 10: Correlation heatmap for all 256 features (comprising 128-dimensional node em- beddings) of the AM encoder embedding, POMO encoder embedding, and the LEHD decoder embedding.
26

---

Table 7: The details of Probing inputs of Probing task and Probing task 4.
Probing input
# Ohservations
Features
Label
AM-Init
D1g Nt]
AM-Enc-/1
Us. lt]]
AM-Enc-23
[h,, hy]
AM-Ennc/3-wW/
[1. bi.. Agraph]]
w/o ints.
AM-Enc-13-w/s
[1s, hy. Agtimppel
20000
Binary
POMO-Ene-I1
[/g, ht]
POMO-Enc-16
[h,, Rt]
L.E.D-Ene-I1
[hs. ht]
20 and 100
LEHD-Dec-Fh
[ss. Rt]]
L.H.D-Dec-16
[ha, hi]
AM-Init
[bg. hg. 14g @ hgg
AM-Enc-A1
[hg. hg. lgg O htg
AM-Enc-13
[ha hy. h4 Q hyl
AM-Enc-13-wwy
[bg, Ry. Migaphh ly h,]
AM-Enc-/3-w/g
[bs hi. Aglimppes by C h;]
w/
POMO-Ene-I1
20000
[4g hg. h4 G hy]
Binary
POMO-Ene-16
[hg, hy. hy Q hyg
LEHDD-Enc-I1
[hi, hj. hg @ hyl
LEHD-Dec-Il
[hg lt.. by @ hy]
LEHD-Dec-16
[b4, hy, h4 @ hyl
Table 8: The details of Probing inputs of Probing task 3. d, denotes the demand for node i.
Probing input # Obscrvations
Features
Label
AM-Init
[bg, h,]
AM-Ene-(1
[h,, h2]
AM-Ene-13
[/, hj]
POMO-Ene-Il
[h,, hj]
w/o ints.
POMO-Ene-16
[h, h,]
10000
d: dj
[h, hT]
LEHD-Dec-J1
[h. hy]
L.HDDDec-16
[h,, hy]
20 and 100
AM-Init
[hy G hy]
AM-Ene-[1
[hy ④ 8g)
AM-Enc-13
[/4 ④ hg]
w/ ints.
POMO-Ene-Il
[h: ④ hg]
POMO-Enc-16
[h; @ hgy
10000
de dj
LEHD-Enee
[hy @ hgy
LEHD-Dec-I1
[h4 @ hy)
LEHD-Dee-Be
[hy 3 hy)
B.3
Codes and Datasets for Reproducibility
provide GitHub repository containing all codes required to construct the probing datasets. The repository includes: (1) instance generation with theoretical and greedy solutions, (2) scripts for extracting embeddings from different NCO models, (3) an example probing experiment with CS-Probing and visualization, and (4) training code for the LEHD regularization experiment in Section
Although the repository already supports dataset generation, we plan to openly release all probing datasets to further facilitate research. This will save dataset preparation effort and enable more convenient usage.
27

---

B.4 Experiments Compute Resourees
In this study, we use NVIDIA A100-40G GPU with AMD EPYC Milan 7713 CPU. is important to note that the primary experimental processes involved in this study, namely training linear probing models or solving linear models using standard statistical methods (such as OLS for regression and MIEE for classification), require minimal computational resources and can be completed within seconds.
However, collecting datasets does consume some computational resources. For instance, solving combinatorial optimization problems using commercial solvers typically requires CPU computation. Additionally, even when not training NCO models but merely performing inference to obtain NCO model embeddings, the process is also completed within seconds when using a GPU.
C Detailed Results of All Probing Tasks
C.1 Main Results of Four Probing Tasks
Tables 9 and 10
present the complete results of the four probing tasks. In addition to the discussions we provide more results from these tables and their corresponding discussions here.
in Section 3.2
C.1.1 Probing Task 1 and Probing Task 2
Knowledge existence. For Probing Task 1 (the Euclidean distance regression task), it is important to note that a linear model cannot directly capture the nonlinear relationship of Euclidean distance. Thus, linear model would have no explanatory power if the input only consists of the nodes' coordinate information. the most extreme case, where the input for Probing Task (i.e., the features) are solely the two nodes' coordinates, the regression model's R² value would be zero, because the covariance between the label and the linear model's output is zero. This result is also reflected the experimental findings presented later in Section 3.2 On the other hand, when the probing model's Re value is greater than O, and the closer it is to I, the stronger the evidence that the NCO model has the ability perceive Euclidean distances. This indicates that the information related Euclidean distance, encoded in the model's embeddings, can be linearly extracted, therehy validating the NCO model's ability effectively represent this information.
For Probing Task 2, to verify whether NCO models can avoid myopia rather than merely distinguish between different paths, we train probing model using raw path features (i.e., the Euclidean distances of the paths) as input. This yields an AUC of 0.64, which close to random guessing (0.5), in contrast to the AUC of 0.86 achieved when using NCO model embeddings input. This result highlights that the model's behavior goes beyond simple path discrimination. Detailed results are shown in Figure 11
Distribution distance by Label
ROC Curve
1500
Label 0
1.0
Label 1
Count
True Positive
0.6
500
0.2
ROC (AUC 0.64) Random Classifier
0
0.00
0.25
0.50 0.75
1.00
0.0
0.2
0.4
0.6
0.8
1.0
Distance
False Pasitive Rate
Figure 11: A classifier is trained using only the raw path feature (namely distance) as input. The left plot shows the label distribution, and the right plot presents the ROC results.
More results about AM/POMO. We observe differences in how different model architectures represent Euclidean distances. In the results shown in Table 9 for both 20-node and 100-node instances, LEHD's approach, utilizing a single encoder layer followed by multi-layer attention recalculations between the current node and other nodes in the decoder for each decision, demonstrates a more robust method for capturing information. From the table, we observe that L.HHD achieves strong results regardless of the presence of interaction terms. In contrast, AM and POMO, which
28

---

Table Comparison of probing task results for NCO models. The underlined results indicate they are derived from the final node embeddings of the three models.
Probing task I
Probing task 2
Probing input
RMSE
MAE
score
Accuracy
Precision
Recall
Fl
score
AUC
AM-Init
0.2452
0.2028
-0.0003
49. 19.28%
0.49
0.47
11.48
0.49
AM-Enc-f1
0,2066
0.1665
0.2899
66.90%
0.70
0.59
0.64
0.72
AM-Fne-ft
0.2119
0.1711
0.2529
70.43%
0.73
0.65
0.69
0.76
AM-Ene-I3-w/e
0.2140
0.1724
0.2381
30%
0.72
0.63
0.67
0.75
AM Mer-Ene---vr
0.2134
0.1721
0.2423
70.97%
0.74
0.65
0.69
0.76
wio ints.
POMO-Emc-Il
0,2115
0,1711
0.2558
64.50%
0.68
0.56
0.61
0.67
POMO-Ene-16
0.2196
0.1787
0.1981
10%
0.71
0.69
POMO-SL-Eac-
0.2183
0.1770
0.2073
70.50%
0.72
0.66
0.69
0.76
POMO-Enc-I6-ww
0.2250
0.1809
0.1876
69. 75%
0.71
0.67
0.69
0.76
20 mode embeddings
POMO-Ene 1100--nc---- w/g
0.2266
LEHD-Enn--1
0.2115
0.1719
0.2554
64.08 08%
0.68
0.53
0.60
0.67
LEHD-Dec Dec--D
0.0062
0.0046
0.9994
74.10%
0.79
0.66
0.72
0.78
LEHD-Dec-16
0,0590
0.0451
0.9418
25%
0.78
0.86
AM-Ini
0.1318
0.1000
0.7111
51.95%
0.52
0.47
0.50
0.52
AM-Eac-il
0.0235
0.0171
0.9908
70.28%
0.74
0.63
0.68
0.77
AM-Enc-13
0.06$7
0.0514
0.9282
75.90%
0.75
AM-Enc-(3-wlc
0.0653
0.0512
0.9291
74.95%
0.77
0.72
0,74
0.82
AM-Enc-(3-w/g
0.0660
0.0518
0.9275
75.67%
0.78
0.72
0.75
0.83
ints.
POMO-Ene-Il
0,0543
0.0430
0.9510
69.23%
0.62
0.67
0.74
POMO-Enc-16
0.1119
0.0890
0.7917
78 88%
0.79
0.80
0.79
0.86
POMO-SI -Lc--nn--66
0.1044
0.0825
0.8186
76.35%
0.78
0.74
0.76
POMO-Fne-16-w//
0.1189
0.0942
0,7732
78.97%
0.79
0.80
0.79
0.86
POMO-Enc- E-c--------- w/g
0,1192
0.0942
0.7722
78. 78%9
0.79
0.79
0.79
0.87
LEHD-Ene-I1
0.0424
0.0325
0.9701
66.88%
0.71
0.57
0.63
0.72
LEHD-Dee-11
0.0069
0.0052
0.9992
74.12%
0.79
0.67
0.72
0.79
LEHD-Dec-16
0.0592
0.0452
0.9415
78.55%
0.80
0.77
0.78
0.86
AM-Init
0.2498
0.2084
-0.0012
50.48%
0.51
0.45
0.48
0,50
AM Enc-il
0,2186
0.1791
0.2332
56.00%
0.57
0.53
0.55
0.60
AM-Eac-13
0,2212
0.1800
0.2151
66,309
0.68
0.61
0.65
0.71
AM-Ene-(3-wie
0.2245
0,1830
0.1915
10%
0.69
0.62
0.65
0.72
AM-Eno-(3-w/f
0,2224
0.1806
0.2062
65 88%
0.68
0.60
0.64
0.71
w/o ints.
0.2210
0.1799
0.2166
60%
0.55
POMO-EB Enc-16
0,2231
0,1825
0.2014
71.8%%
0.72
0.72
0.72
0.79
POMO-SI Fl----666
0.2219
0.19
0.2102
72.65%
0.73
0.72
0.72
0.81
POMO-Ene-1G 1-00-Ee-----wo
0.2249
0.1818
0.1646
71.25%
0.72
100 made embeddings
POMO-Enc-16-w/g
0,2240
0,1817
0.1711
71.35%
0.71
0.72
0.72
0.78
LEHD-Enc-I1
0.2194
0.1796
0.2280
93%
0.56
0.54
0.55
0.60
LEHD-Dec-Il
0.0094
0.0068
0.9986
67.45 67.45%
0.57
0.64
LEHDD-Dec-66
0.0469
0.0370
0.9647
76.50%
0.77
0.75
0.76
0.85
AM-Init
0.1334
0.1033
0.7143
$1.82%
0.52
0.47
0.49
0.53
AM-Enc-f1
0.0262
0.0193
0.9890
0.61
AM-Enc-13
0,0444
0,0339
0.9684
69 69.08%
0.72
0.63
0.67
0.76
AM-Ime-(3-wWl
0.0587
0.0463
0.9448
70.33 70.33%
0.73
0.66
0.69
0.77
AM-Enc-i3-we
0.0447
0.0340
0.9679
69.15%%
0.67
w/ iis..
POMO--Fee Fnc--1
0.0276
0,0212
0.9877
1.5%
0.68
0.60
1164
0.71
POMO-EBe-16
0.0802
0.0640
0.8968
72.47 47%
0.72
0.73
0.73
0,80
POMO-SL-Eno-16
0.0797
0.0638
0.8980
60%
0.74
0.73
0.74
0.81
ROMO-Enc-IG-aae
0.0807
0.0645
0.8923
72.28%
0.72
0.73
0.72
0.80
Enno-EEn----//gg
0.0806
0.0645
0.8927
72.42%
0.72
0.73
0.73
LEHD-EEnc-[1
0.0421
0.0325
099166
61 82%
0.63
0.59
1166
0.66
BEHD-Dec-Il
0.0075
0.0054
0.9991
67. 20%
0.72
0.57
0.63
0.73
LEHD-Dec-16
29

---

Table 10: Results of probing task and probing task 4.
Probing task 3
Probing task 4 Rocall
Probing input
RMSE
MAE
R² score
Accuracy
Procision
Fl score
AUC
A--Init
0.0000
0.0000
1.0000
49.35%
0.49
0.52
0.51
0.50
w/o ints.
A.--nn-I1
0.0088
0.0070
0.9945
74.12%
0.74
0.74
0.74
0.81
20 node embeddings
AM-Enc-13
0.0273
0.0219
0.9471
77.03%
0.76
0.79
0.77
0.84
LEHD-Ene-Il
0.0038
0.0030
0.9990
71.78%
0.72
0.72
0.72
0.79
LEHD-Dec-I1
0.0100
0.0078
0.9929
69.73%
0.71
0.66
0.69
0.75
LEHD-Dec-16
0.0366
0.0288
0.9047
75.92%
0.75
0.78
0.76
0.84
AM-Inni
0.0000
0.0000
1.0000
62.82%
0.64
0.58
0.61
0.67
AM-Enc-[1
0.0269
0.0209
0 0.9488
81.45,
0.80
0.84
0.82
0.89
ints.
AM-Enc-(3
0.0955
0.0767
0.3533
83, 83.30%
0.82
0.85
0.84
0.91
LEHD-Eme-Il
0.0112
0.0087
0.9910
70%
0.76
0.76
0.84
LEHD-Dec-I1
0.0159
0.0125
0,9820
71.75%
0.73
0.69
0.71
0.77
LEHD-Dec-16
0,0632
0.0502
0.7169
77.78%
0.76
0.80
0.78
0.87
AM-Init
0.0000
0.0000
1.0000
49.83%
0.50
0,54
0.52
0.50
AM-Enc-I1
0.0137
0.0110
0.9878
77.95%
0.78
0.78
0.78
0.86
wlo ints.
AM-Ene-13
0.0237
0.0187
0.9635
78.08%
0.77
0.86
POMO-Ene-I1
0.0199
0.0157
0.9743
72.72%
0.74
0.70
0.72
0.81
100 node embeddings
POMO-Ene-16
0,0445
0.0356
0.8710
70.12%%
0.70
0.70
0.70
0.77
LEHD-Ene-Il
0.0052
0.0040
0.9950
65 65.75%
0.67
0.63
0.65
0.71
LEHD-Dec-I1
0.0069
0.0055
0.9913
66.22%
0.67
0.63
0.665
0.71
LEHD-Dec-16
0.0178
0.0140
0.9426
77.18%
0.76
0.77
0.85
AM-Init
0.0000
0.0000
1,0000
55.80%
0.56
0.51
0.54
0.58
A.M-Ene-(1
0.0356
0.0278
0.9177
85.79%
0.84
0.89
0.86
0.92
AM-Enc-13
0.0645
0.0510
0.7290
87.50%
0.85
0.91
0.88
0.93
ints.
POMO-Ene-I1
0.0272
0.0214
0.9517
78.72%
0.78
0.80
0.79
0.87
POMO-Eme-16
0.1157
0.0951
0.1281
72.67%
0.72
0.73
0.80
LEHD-Ene-Il
0.0069
0.0053
0.9915
66.57%
0.66
0.68
0.67
0.72
LEHD-Dec-I1
0.0086
0.0068
0.9867
66.15%
0.67
0.64
0.65
0.71
LEHD-Dee-16
0.0308
0.0243
0.8280
78.60%
0.77
0.81
0.79
0.86
embed all nodes through multiple encoder layers once, rely more heavily on the interaction terms between the embeddings the two nodes when perceiving Euclidean distances.
As shown in the results for " AMM-ncc/3-w/c" and "AM-Enc-/3-w/gg, even with the extra information provided by context embeddings or glimpse embeddings, AM and POMO do not improve the accuracy of perceiving the Euclidean distance between the current node and other nodes. Rows of "POMO- SL-Enc-16" represents the embeddings of POMO model trained using supervised learning (SL). The results show that the SL-trained POMO achieves similar probing task results to the RL-trained POMO. This observation aligns with the findings from the ablation study in [13] where SL-trained and RL-trained POMO models exhibit comparable performance.
Results by model layer. As shown in Figure (a., the initial embeddings (obtained by linearly projecting the coordinates into a dige-dimensional space) of all three models exhibit weak Euclidean distance perception. However, after passing through just one attention layer, all models achieve highly accurate Euclidean distance perception. This ability slightly diminishes as model depth increases.
Despite this slight decline in Euclidean distance perception, NCO models learn additional capabilities that enable better decision- -akiin.. For instance, the ability to avoid myopic node selection improves with increased model depth, illustrated in Figure (b.).. An exception is observed in the last two layers of LEHD, where the ability to avoid myopic decisions slightly decreases, potentially indicating that the model has learned more complex decision-making strategies. Future research could further explore this phenomenon and what LEHD learns in its deeper layers. Overall, through these two probing tasks, demonstrate that when NCO models solve TSP problems, they can perceive Euclidean distances (low-level features) in shallow layers and learn a decision space beyond the Euclidean distance space (high-level features) in deeper layers. In this decision space, NCO models can avoid making myopic decisions.
By comparing the results (including both node-scale instances and whether interaction terms are used) of the same model across different layers, we find that the ability of the embeddings to perceive Euclidean distances decreases as the number of attention layers increases in all three models. Notably, after six attention layers, POMO shows a more significant decline Fuclidean distance perception compared to AM, which has the same structure but only three attention layers. This suggests that
30

---

while deeper attention layers may enhance other decision making capabilities (as discussed in the Probing Task 2), the model's ability to perceive distances diminishes.
In subsequent research based on AM/POMO models, some models introduce node distance informa- tion to enhance performance: either by explicitly incorporating distance information adjust the model's output [45]. or by designing distance-awan attention mechanisms [46]. Through probing experiments, we verify that these approaches introduce Euclidean distance to mitigate its perception deficiency as the number of layers increases in NCO models. This provides important guidance for future improvements to AM and POMO-based models.
imprevempernn
C.1.2 Prohing Task 3 and Probing Task 4
This section provides a detailed discussion of Section 3.2, specifically addressing the question: Do NCO embeddings encode constraint information, as demonstrated with the CVRP?
Probing Task 3: Capacity constraint. Through Probing Task 3, using the capacity constraint in the CVRP problem as an example, we demonstrate that probing can be applied to study the ability of NCO models to represent low-level information related to constraints. From Table (T), we can see that the embeddings of NCO models unquestionably contain the linear information of demand. This is particularly evident in the initial embeddings, where the three-dimensional raw features (i.e., and y coordinates and demand) are directly projected into a high-dimensional space, allowing the demand information be fully extracted (Rt 1). Even after the embeddings undergo attention mechanisms and the nigh-dimensional features of nodes are fused, this information remains largely extractable, with R² values ranging from above 0.7 nearly 1.
We observe that, while all three NCO models can capture the linear (additive) relationship between node demands, this ability weakens with increasing number of layers, similar to the perception of Euclidean distances. This observation is particularly noteworthy in the Hadamard product probing input, [he O h,]. As discussed in Section B.1.3] we simulate attention calculations using this Hadamard product input. Many NCO models, including AM and POMO, calculate a compatibility score by attention calculations before applying the output Softmax. In this context, the Rt values for the final output layer decrease significantly compared to the first layer, as shown in the "w/ ints." rows in Table [0 In some results, R even drops to the 0.1 to 0.35 range, indicating that these NCO models may no longer accurately capture whether the demand exceeds vehicle capacity and, as a result, are unable to actively select a feasible next node. Instead, they rely passively on masking to enforce final output modifications and constraints.
Probing Task 4: Same route. Here, we take the example of using probing to explore whether the embeddings of the AM model can encode information about whether two nodes belong to the same route in the optimal solution, providing detailed analysis of how this conclusion is reached. The same reasoning process applies to other NCO models, with detailed results available in Table
Figure 12 presents the AUC results for Probing Task 4 using different input data for the probe. The results in Figures (a) and (b) (with AUC values close to 0.5) rule out the possibility that the two nodes can be linearly separated solely based on their Euclidean distance or their node coordinates. Therefore, if the embeddings learned by NCO models can be linearly separated by the probe (i.e., AUC larger than 0.5, approaching 1), it indicates that the embeddings contain information about whether two nodes should belong to the same route. As shown in Figures (c) and (d), when using AM embeddings as the probing input, the AUC is significantly greater than 0.5, demonstrating that AM can effectively encode information for determining whether two nodes should belong to the same route when solving the CVRP. Other NCO models also exhibit this capability, with detailed results provided in Table 10
Discussion. In the capacity constraint probing tasks, explored the decision rationales of two NCO models in handling this constraint. The probing results show that NCO models can perceive linearly additive demand information as well more abstract experiments reveal how NCO models handle capacity constraints, unlike the previous probing tasks on TSP, these results do not show strong correlation with the models' final performance. For instance, in Probing Task 4, AM achieved the best probing results, yet it is not the best berf-rrrn model on the CVRP.
supportiig information. While these
These two probing tasks raise interesting research questions regarding the design of NCO models for handling constraints in the future. Should additional constraint-related information be incorporated
31

---

(a) Dist
(b) Init
True Positive Rate:
1.0
RBC Guive (AUC- 0.53)
0.0
Random Claselier
Positive
0.6
0.6
0.4
0.2
ROC Carva (AUC 0.57)
0.2
0.0
Random Checxtee
0.0
0.50
False Positive
False Positive Rate
(c) Layer 1
(d) Layer 3
1.0
True Positive Rate
0.8
Positive
0.6
BOC Carve (AUC 0.80)
0.2
Random clssilir
Clsssfar
0.50
False Positive Rate
False Positive Rate
Figure 12: AUC results for Probing Task 4. The inputs from (a) to (d) are: (a) the Euclidean distance between nodes, (b) the initial embedding obtained by directly projecting the raw features into high-dimensional space (AM-Init), (c) the embedding after the first attention layer (AM-Ene-11), and (d) the embedding after the final attention layer (AM-Enc-13)
into NCO models, similar to how distance information is integrated in previous studies 45 46)
Are there other decision-related features in CVRP that exhibit stronger correlation with model performance and can help better understand the decision makiin process of NCO models? Future work can further explore these questions by designing and implementing additional probing tasks to deepen our understanding of how NCO models handle constraints.
C.2
Robustness Check
C.2.1 Other Models
We conduct preliminary experiment DIFUSCO [8] diffusion-based NCO model. After training the model for 20 epochs, we apply probing to analyze its learned representations. Table presents the node embedding results. As the number of GNN layers increases, the capacity to capture Euclidean distances slightly decreases, whereas the ability to identify optimal edges improves. This distinction between low-level and high-level feature encoding is consistent with the patterns observed in transformer-basee models discussed above. These results demonstrate that probing is also effective for analyzing alternative architectures, such diffusion-basser models where the GNN serves the denoising network.
Table 11: Probing results on node embeddings of DIFUSCO. Here, init denotes the initial embed- dings, and h 12 denotes the embeddings after 12 GNN layers.
Probing input
Probing Task 1 Probing Task 2
h init
0.9476
0.49
h_12
0.8710
0.73
C.2.2 Distance Perception in Non-Euclidean Space
To further validate the robustness of probing as a tool for analyzing NCO models and the probing tasks designed, demonstrate Probing Task / for distance perception in Eu-cliidea space. Specifically, we selected MatNet [77] -fate-of-the-ar model designed for solving asymmetric TSP.
We use MatNet's row embeddings and column embeddings for pairs of nodes features, and the distances between the corresponding nodes in the distance matrix as labels to construct the probing datasct. For example, the embeddings of node i and node j are used features, with the
32

---

corresponding label being the value in the distance matrix at the intersection of row and column j. denoted as di. Similarly, the column embeddings of node i and node j are used as features, with the label being d.
MatNet Probing Task PerfomanceeAcros Different Layers
MatNet_Emm
0.5
MatNet Enc int_ints
0.4
0.3
0.2
0.1
3
4
Layer
Figure 13: Probing results of MatNet across different layers.
The results are shown in Figure 13 As the number of layers in MatNet increases, the ability of its embeddings to perceive distances improves, with the R rising from less than 0.2 in the first layer to approximately 0.5 in the final layer. Additionally, we conduct supplementary comparison experiments. In the first experiment, serving used as inputs, but the labels are replaced with random distance values unrelated to both nodes from the distance matrix. The resulting probing R is -0.0232, indicating that the probe could not learn any distance information from random labels based on the embeddings. In the second experiment, we swap the labels between row and column embeddings, assigning the row embeddings of node and with the label dist(j i) and vice versa. The resulting probing R² is 0.2532. Comparing these results, we conclude the following: MatNet's dual-attention structure effectively learns information from the asymmetric distance matrix. Furthermore, regardless of whether the embeddings of two nodes are correctly aligned, they can still partially represent distance information. However, the model's s ability to capture correct distance information between two nodes is significantly stronger than its ability to capture incorrect distance information, with I22 values of approximately 0.5 versus 0.2, respectively.
baseline, the embeddings of node and node j are
C.2.3 JSSP Precedence Constraint
In addition to the routing problem analyzed earlier, we also apply probing to test the precedence constraints in the Job-shop Scheduling Problem. For JSSP, we evaluate a classic learning model [48]. which is based on graph neural network. The datasets for this probing task are constructed as follows: we extract embeddings for all nodes, pair two node embeddings that satisfy the precedence constraint with a label of ([h,,h,)-I) J-1), and pair two node embeddings that violate the constraint with a label of h, J-0). As an ablation, we also construct an alternative dataset where pairs that satisfy the precedence constraint are incorrectly labeled as O: [h4.hy]-1, [h,,.
The results show that for the correct dataset, the probing model achieves an AUC of 1, while for the ablation dataset, the AUC is 0.5. This indicates that the NCO model effectively captures the precedence constraint information between nodes in its embeddings. Here, we provide an initial demonstration of how probing can explore the NCO model's perception of constraints in the JSSP. In the future, more sophisticated probing tasks can be designed to further analyze how the NCO model perceives constraints and incorporates them into its decision-making making process, thereby offering deeper insights into the design of NCO models.
C,3 Probing NCO Model Performance
The two probing tasks discussed in the previous section not only validate that NCO models can embed decision-related information at different levels but also provide preliminary evidence that probing can be used to explore the performance of NCO models. For example, in Probing Task 2 with 20-node instances, the probing results show that AM (with an AUC of 0.83) slightly underperforms compared to POMO and LEHD (both 0.86). In 100-node instances, the probing results rank from
33

---

lowest to highest as AM (0.76), POMO (0.80), and LEHD (0.85). These probing results for both 20-node and 100-node instances are consistent with the final performance these models in solving TSP problems of the same sizes. Specifically, for 20 nodes, POMO and LEHDD perform similarly and slightly outperform AM, whereas for 100 nodes, LEHD outperforms POMO, which in turn outperforms AM (see the greedy inference methods results in the Table 2 in 12 and Table I in [13).
This section further explores how probing can be used to study the impact of NCO models' repre- sentational capabilities on their performance from multiple perspectives. Additionally, we introduce CS-Probing to examine the differences between internal representations and inductive biases across various NCO model architectures, providing direct evidence to explain generalization performance. For more details, please refer to Section 4 Here, we only provide the results of probing tasks as an indirect perspective to explore the generalization of NCO models.
Generalization to larger scale. One of the advantages of the LEHDD model is its superior generaliza- tion performance on large-scale problems compared to AM and POMO. To validate this, we create a dataset with 200 node instances. Based on this dataset, we obtained embeddings from three NCO models pretrained on 100-node problems when solving 200-node problems.
Table 12: Experimental results for the 200 node instances.
Probing imput
Probing task 1 (RP)
Probing task (AUC)
w/ intss wlo ints.
AM-Enc-13
0.1673
0.71
POMO-Ene-I6
0.1352
0.80
LEHD-Dec--Be
0.9563
0.86
AM-Encc-3
0,9458
0.76
POMO-Ene-16
0,9100
0.80
LFHD-Dec--6
0.9588
01.6
From Table we observe that the three NCO models pretrained on 100-node instances exhibit varying performance on the two probing tasks for 200-node instances. Notably, for Probing Task 2, which explores information more directly related to final decisions (distinguishing optimal edges from myopic ones), the results are fully consistent with their performance on the optimization problem outcomes, i.e., LEHD outperforms POMO, which in turn outperforms AM. Next, we conduct additional experiments to explore how the unique structure of L.HHD enhances its representational capability, enabling to better focus on nodes to be selected.
Further experiments on LEHD. LEHD's recalculation of the embeddings of candidate nodes in its decoder, through the attention mechanism with the current node embedding, may allow it to more effectively capture the relationships between the current node and other nodes, Specifically, as shown in the decoder of Figure bb,, the embedding of the current node, h, participates in the attention calculations with the remaining nodes after passing through a linear projection, updating their embeddings. In contrast AM and POMO, which treat all node embeddings equally and perform node embedding only once, LEHD's s decoder design allows for more accurate perception of the distances between the current node and the remaining nodes. To verify this, we conducted additional experiments on LEHD, and the results are presented in Table [3
Table 13: Experiments for LEHD. The first two rows show distance perception between non-current
nodes and others, while the third row shows the effect of removing attention from LEHD.
Probing input
RMSE
MAE
R2 score
SEGHD-Dec-l-oltee
0.2091
0.1694
0.2620
HHHHD-Dee-fG-other
0.2318
0.1898
0.0927
LEHD-Dec Dec-w/o-at
0.2115
0.1719
0.2555
LEHID-Dee-16
0.0590
0.0451
0,9421
First, we extract the embeddings of two remaining nodes (i.e., nodes to be selected) for probing and find that the probe achieves an R² of only 0.0927. This indicates that LEHD is indeed more focused on the relationship between the current node and other nodes. Additionally, when we probe the embedding from the linear projection below h, in the decoder (Figure Ib), before the attention calculation), its R² dropped to 0.2555, significantly lower than the original 0.9421. This suggests
34

---

that the attention mechanism in LEHD's decoder is crucial for accurately capturing the Euclidean distances between the current node and the remaining nodes (i.e., nodes to be selected).
This leads to an insight for future NCO model: recalculating node emheddings through the attention mechanism in the decoder enables more accurate perception of Fuclidean distances than relying solely on context embeddings, as in the case of AM and POMO, to provide current information (more details in Appendix C.I.Ip. To further validate this, we next examine probing from an entirely new perspective.
D
CS-Probing for NCO
D.1 LEHD Training
Figure 14 shows the CS-Probing results of the LEHD model at different training epochs. From the results, we observe that in the early stages of training, LEHD does not predominantly capture decision-related knowledge within a few specific dimensions. However, as training progresses, the model increasingly tends to fixate on small number of dimensions to encode this knowledge. This tendency is evident from the larger absolute values of probing model coefficients associated with certain dimensions, as well as the increased disparity between the coefficients of different dimensions. Eventually, after sufficient training, LEHD exhibits the inductive bias shown in Figure and (f).
(a) Epoch 1
(b) Epoch 10
(ra))
0.02
My
0.05
(+)
1
11
8116
0
50
100
150
200
250
50
100
150
200
250
(c) Epoch 20
(d) Epoch 40
a M
118111181111
18
RIGGI
-1
11001
111
50
100
150
200
250
50
100
150
200
250
Figure 14: CS-Probing results of LEHD at different training epochs.
D.2
Visualizing CS-Probing Outcomes for NCO Generalization
Figure 15 presents the CS-Probing analysis for the three NCO models, highlighting the key embedding dimensions (top-5) identified during generalization. These three figures provide visualization of the data presented in Table In each figure, the four sub-figures present the probing results of the specific NCO model on Probing Task (left two plots) and Probing Task 2 (right two plots), showing both the probe coefficients and their statistical significance. For each task, the top plot shows the result of the NCO model trained and tested on 20-node instances, while the bottom plot shows the result of the same model (training on 20-node instances) generalized to 100-node test instances. In each plot, the left section (in purple) represents the results for 128- 128-dimensional embedding of the current node, and the right section (in blue) represents the results for 1 128-dimensional embeddings of the candidate nodes-tor together forming a 256-dimensional results. Below each dimension its significance level. Red vertical lines highlight the top-n dimensions by absolute coefficient magnitude (n = to 5), with their ranks labeled above the lines. Note: if two top-n dimensions are close, the rank labels are slanted to avoid overlap.
D.3
Generalization of AM and POMO on Near Out-of-Distribution Data
In Section 4.3 we investigate the internal mechanisms underlying the generalization ability of the three models by analyzing whether they consistently retain specific knowledge dimensions during generalization. The results indicate that models with superior generalization performance tend to consistently use fixed set of dimensions to capture certain knowledge, reflecting the transfcrability of
35

---

(a) AM Probing Task 1: 20 Train / 20 Test
(b) AM Probing Task 2: 20 Train 20 Test
2
4
5
0.10
0.05
0.5
0.001 (**)
p < 0.01 (T)
-0.5
0.0.5
011
011001 Iiil
iliii
-0.10
top_n
150
200
250
(c) AM Probing Task 1: 20 Train / 100 Test
(d) AM Probing Task 2: 20 Train / 100 Test
9
21 5 4 3
0.10
0.00
0.10
1
1
100e
50
100
150
200
250
50
100
150
200
250
(e) POMO Probing Task 1: 20 Train / 20 Test
(f) POMO Probing Task 20 Train / 20 Test
0.050
0.4
0.025
0.000
0.0
-0.2
1
8131
50
100
150
200
250
50
100
150
200
250
(g) POMO Probing Task
20 Train / 100 Test (h) POMO Probing Task 2: 20 Train 100 Test
23
39
0.050
0.025
0.0
0.000
-0.025
-0.5
111
18
100
150
200
250
(i) LEHD Probing Task 1: 20 Train / 20 Test
(j) LEHD Probing Task 2: 20 Train 20 Test
51 32
4
31
42
5.0
0.1
2.5
Aep My M
0.0
0.0
-2.5
11 155
113
110111
111
BE
1
50
100
150
200
250
50
100
150
200
250
97
(k) LEHD Probing Task 1: 20 Train 100 Test
(I) LEHD Probing Task 2: 20 Train 100 Test
41
41.5
0.0
1133 1
0
-0.1
-2
50
100
150
200
100
150
200
976
250
Figure 15: CS-Probing results for the two probing tasks across three models, including both in- distribution and distribbutoonn generalization results. This corresponds the visualization the data presented in Table
36

---

learned representations. Conversely, when the knowledge encoded in specific embedding dimensions becomes disorganized during generalization, the model's performance deteriorates.
Table 14: Top 5 dimensions from CS-Probing results two TSP probing tasks on TSP-20 and TSP-21
across AM and POMO models.
20 train / 20 test
20 train / 21 test
Top__
Dim.
Coef.
Sig. level
Dim.
Coef.
Sig. level
54 (candidate node)
0.0917
8:8
101 (current node)
0.0803
41 (candidate node)
-0.0884
90 (current node)
0.0752
AM
101 (current node)
0..848
54 (candidate node)
0.0729
Probing Task
95 (candidate node)
-0.0767
48 (candidate node)
-0.0631
124 (candidate node)
-0.0712
35 (candidate node)
-0.0617
89 (current node)
0.0539
89 (current node)
0.0615
POMO
89 (candidate node)
0.0510
89 (candidate node)
0.0516
107 (current node)
0.0443
107 (current node)
0.0389
(candidate node)
0.0322
15 (candidate node)
-0.0376
(candidate node)
-0.0308
0
74 (current node)
0.0352
0.0
34 (current node)
0,8561
61 (candidate node)
-0,9994
$82
61 (candidate node)
-0.8153
225 (candidate node)
-0.7887
AM
55 (candidate node)
-0.6612
109 (candidate node)
0.7307
Prohing Task
109 (candidate node)
0.6406
SS (candidate node)
-0,7019
106 (candidate node)
-0.6329
124 (candidate node)
-0.6858
53 (candidate node)
0.5004
53 (candidate node)
0.4796
POMO
89 (candidate node)
0.4088
74 (candidate node)
0.3944
62 (candidate node)
0.3238
27 (candidate node)
0,3804
110 (candidate node)
0.3217
(candidate node)
0,3182
(candidate node)
0.3081
$:0-
42 (candidate node) 0.3067
To further validate this observed phenomenon and conduct a more in-depth exploration, we evaluate the CS-Probing results of AM and POMO when generalizing to datasets with smaller distributional differences specifically, those which they exhibit better generalization performance. We train the models on 20-TSP and test them on both 20-TSP and a similar distribution, 21-TSP. Table [4] presents the CS-Probing results for AM and POMO on both datasets. The results indicate that both models consistently use the same dimensions to capture knowledge across the two tasks.
Comparing these findings with Table 2 as LEHD when scaling up. or AM and POMO when generalizing to slightly different distribu- tions consisttnyl demonstrate the aforementioned characteristic. This further reinforces our claim that the ability to consistently use key dimensions during generalization is indicative of robust performance.
we observe that models capable of generalization such
D.4 Other Random Seeds
For the instance of random seed 2 (upper subplot of Figure T6), the current node is node 4. The myopic choice based on Euclidean distance would be node 2, while the correct choice in the optimal solution node 13. In the two identified key dimensions, node 4 indeed closer node 13 than to node 2.
For the instance of random seed 3 (lower subplot of Figure 16]. the current node is node 8. The myopic choice based on Euclidean distance would be node 1, while the correct choice in the optimal solution is node 9. In the two identified key dimensions, node 8 is indeed closer node 9 than to node 1, even though the difference is small. This is consistent with the node distribution shown in the left two plots, where nodes 9 and 1 very close each other, and their distances node 8 differ only slightly.
D.5 CS-Probing for Probing Task 3 and
The aforementioned CS- CS-Probing analysis for the two TSP-related probing tasks can similarly be applied to the two CVRP-related probing tasks. Here, we take the evaluation of generalization ability as an example, using models trained on 20-node instances and testing them on both 20-node and 100-node datasets. Since POMO does not provide a model trained on 20-node instances, we only test the other two NCO models. The experimental results presented in Table 15
37

---

Optimal TSP Tour
Best Greedy Tour (Starting Node 14)
Two Dimensions by CS-Probing
1.0
40
97th dimension
8
18
30
0.6-
0.6
20
14
13
0.4
12
0.4
1.2
10
13
10
0.0
0.2
0.6
0.8
1.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
-10
10
30
40
X
X
31th dimension
Optimal TSP Tour
Best Greedy Tour (Starting Node 6)
Two Dimensions by CS-Probing
1.0
1.0
40
97th dimension
10
10
10
0.4
0.4
10
131.9
131.5
0.2-
0.2
17
0.8.0
0.0
X
31th dimension
Figure 16: Solution results and key 2-d dimensions in node embedding.
Table 15: Top dimensions from CS CS-Probing results two CVRP probing tasks across AM and LEHD models. (POMO did not provide the pre-trained model on 20-CVRP)
20 train 20
20 train / 100
Top_n
Dim.
Coef.
Sig. level
Dim.
Coel.
Sig. level
61 (candidate node)
6.8
(current node)
0.1123
486
61 (current node)
0.0691
6.8
(candidate node)
0.0998
...
AM
Prohing 3
45 (candidate node)
-0.0631
8:5
106 (current node)
-0.0661
488
45 (current node)
-0.0624
45 (candidate node)
-0.0647
67 (current node)
-0.0464
67 (current node)
0.0639
30 (candidate node)
-0.0325
8:58
30 (current node)
-0.0262
$82
LEHD
30 (current node)
-0.0322
30 (candidate node)
-0.0223
118 (candidate node)
-0.0221
11 (current node)
0.0195
118 (current node)
-0.0202
13 (candidate nodc)
0.0182
5 (current node)
0.0202
16 (current node)
-0.0161
45 (candidate node)
-1,5845
87 (candidate node)
-2,2114
(candidate node)
1.1667
$12/2
(current node)
-1,9473
AM
Prohing 4
(candidate node)
-1.1331
0.0
87 (current nodc)
1.9408
66
(candidate node)
-1.0980
40 (candidate node)
1.8984
482
21 (candidate node)
-1.0775
45 (candidate node)
1.8825
(candidate node)
-0.7821
8:55
71 (candidate node)
1.4377
$82
LEHD
(candidate node)
0.6919
30 (candidate node)
1.1433
75 (candidate node)
0.6908
2 (candidate node)
-1.0100
76 (candidate node)
0.6904
99 (candidate node)
1.0020
102 (candidate node)
0.6737
30 (current node)
-0,9591
38

---

The results indicate that during generalization, NCO models can effectively capture linearly additive demand information, demonstrating strong ability to represent linearly additive knowledge. How- ever, when it comes to more complex, abstract high-level information related to the global optimal solution, the learned dimensions become disorganized. This suggests that while NCO models can robustly encode simple additive information, their ability to maintain structured representations of more complex knowledge requires further investigation.
In the future, designing more CVRP-related probing tasks and conducting CS-Probing experiments can help gain a deeper understanding of the internal mechanisms of NCO models on CVRP, such as how they perceive complex constraints.
E Limitations
One potential limitation using probing to explore NCO models is the cost associated with collecting probing datasets. The first challenge is the runtime cost. Regarding the data collection process in our study, we summarize the time required to collect 10,000 instances Table I6 As shown, although NCO model training typically takes several days to week, find this data collection cost to be reasonable.
Table 16: Computational cost of NCO training and optimization solver at different scales.
20-TSP
100-TSP
POMO Training
1-2 days
2-3 days
Exact Solver
1-2 hrs
2-3 days
Another limitation arises when probing requires the optimal solutions of instances to verify whether the model captures specific knowledge, commercial solvers are not freely available. Moreover, even when commercial solvers are accessible, this requirement can still be challenging for large-scale and complex combinatorial optimization problems. For instance, solving the CVRP with 100 nodes using exact solvers like Gurobi is computationally infeasible. To address this challenge, we employ validated heuristic-based solution methods, such the HGS algorithm. These open-source methods provide practical alternatives for researchers who may lack access to commercial solvers.
Lastly, we plan to release all datasets used in this study to facilitate future research. We believe that as more studies propose new probing tasks and make their datasets publicly available, will contribute advancing future research within the NCO community, promoting the transparency and interpretability of black-box NCO models.
39


Reviews:
[{"review_id": "xZXrsqvTXX", "reviewer": "Reviewer_MBie", "summary": "The paper investigates internal representations of attention-based models used for combinatorial optimisation (AM, POMO, LEHD). It does it in two ways: a. by using internal representations to solve auxiliary tasks b. by looking at significant dimensions of these vectors utilised by the models.", "questions": "Q1. One of the outcomes of your study is that CS-probing can identify the most significant dimensions, which helps to build a smaller model with similar performance. However, the same outcome can be achieved by using hyperparameter tuning methods. What are the other practical implications you envision?\n\nQ2. The second task focuses on the models ability to identify parts of the optimal solution. However, it isn't always unique. Moreover, there might be a drastically different solution with very similar optimisation cost. How do address this issue in your study?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Pros:\nThe use of probing for optimisation models is interesting, since it can identify limitations and potential improvement opportunities for existing models. It was interesting to see myopia avoidance and very small number of significant dimensions in the internal representations.\n\nThe study is extensive and provides a large number of experiments and data \n\nCons:\nLarge parts of the paper contained detailed discussions of internal embeddings (e.g. these are significant dimensions or the models are not purely greedy optimisers) rather than actionable conclusions. Table 3 is an example when this further step was taken based on CS-probing at least to reduce the model size, but the general probing idea with auxiliary tasks has unclear actionable implications.", "was_revised": true, "final_justification": "The authors have addressed my concerns and I recommend acceptance.", "rebuttal": "We appreciate the reviewer for the constructive feedback and for recognizing the importance of our interpretability exploration in NCO models, as well as the interesting and valuable findings we present. We are also grateful for the acknowledgment that our study is extensive and supported by a large number of experiments and data. The probing methodology and the dataset we constructed reflect the core contributions we hope to bring to the NCO field, and we sincerely appreciate your recognition of their value. We understand that the main concern lies in the lack of actionable implications of the probing results in the current manuscript, which we address through new experiments and additional discussions as outlined below.\n\n---\n\n**1. Cons-*The probing idea with auxiliary tasks has unclear actionable implications.***\n\n**To address the concern that CS-Probing lacks actionable implications, we added a simple yet effective new experiment based on the insights derived from CS-Probing in the original manuscript.** Specificly, we conducted an experiment inspired by our probing insight that LEHD generalizes more effectively when its decisions depend on a small subset of embedding dimensions, indicative of sparsity in its final layers. We therefore introduced a regularization term to further promote sparsity in LEHD’s final-layer embeddings, thereby demonstrating how our insights can inform model design.\n\nSpecificlly, we trained LEHD models with varying regularization strengths (λ) on TSP100 and evaluated their generalization on TSP200 and TSP1000. The table reports the performance gap to the best known solutions. The first column (origin, namely λ = 0) corresponds to the unregularized baseline. Moderate regularization (λ = 1e-6 to 1e-3) improves generalization. We will include this experiment to demonstrate the practical value of our probing approach. The current results are preliminary due to time constraints, and a more thorough analysis on more layers/models will be provided in the revised paper.\n\n|     | origin | 1e-6 | 1e-5 | 1e-4 | 1e-3 |\n|-----|-----|-----|-----|-----|-----|\n| TSP100  | 0.57%  | 0.58%  | 0.57%  | 0.57%  | 0.57%  | \n| TSP200 (generalization)   | 0.86%  | 0.88%  | 0.86%  | **0.73%**  | 0.82%  | \n| TSP1000 (generalization)  | 3.17%  | **2.87%**  | 2.93%  | 2.97%  | 3.05%  | \n\nBeyond this, we will enrich our discussions in Section 5 to outline several promising avenues for NCO models to enhance practical implications, including compression, distillation, and pruning of their representation space. Probing NCO layers across CO tasks and training stages may reveal task-specific dimensional requirements, thereby providing a systematic alternative to heuristic selection. We note that while no single study can encompass all possible experiments, our proposed probing pipeline and CS-Probing will serve as powerful tools for future research. We look forward to seeing how it can facilitate the discovery of further actionable insights to advance the field of NCO.\n\n---\n\n**2. Q1-*While probing helps to build a smaller model with similar performance, same outcome can be achieved by using hyperparameter tuning methods. What other practical implications?***\n\nFirst, we would like to clarify that regarding your point that \"the same outcome can be achieved by using hyperparameter tuning methods,\" this is somewhat incorrect. We apologize for any misunderstanding. Next, we would like to further explain the practical implications of probing and our proposed CS-Probing method.\n\nI. Why can't hyperparameter tuning methods achieve the outcomes obtained through probing? Specifically, what distinguishes the conclusions drawn from our probing methods from simply reducing the model's dimensionality while maintaining similar performance?\n\n- **Although LEHD relies on only two key dimensions, it cannot simply reduce its embedding dimensions at will.** Although the LEHD model appears to rely primarily on just two dimensions of the final-layer embeddings to make near-equivalent decisions, this does not imply that the entire model operates using only these two dimensions. The earlier layers still require high-dimensional representations to effectively learn and process information.\n- **CS-Probing provides valuable insights that can be used to improve NCO models, which experimental methods like hyperparameter tuning cannot achieve.** In our response above (under \"Cons\"), we demonstrate how insights obtained through CS-Probing can guide LEHD model improvements in generalization. This represents a concrete application that cannot be achieved through standard experimental practices such as hyperparameter tuning. Methods like hyperparameter tuning can only improve the model heuristically, rather than through the analysis and understanding of the model’s internal mechanisms, which allows for more evidence-based research.\n\nII. Practical implications of probing and our proposed CS-Probing method.\n\n- **Probing enhance transparency and address the key questions raised by the operations research (OR) community.** We uncover what knowledge NCO models capture and how they are leveraged to solve CO problems. These represent foundational questions raised by the OR community concerning the soundness of NCO methods. Our work directly studies them: NCO models capture both low-level features such as Euclidean distance and high-level strategies like avoiding myopic decisions.\n- **In the original manuscript, we have demonstrated how CS-Probing can be used to analyze and understand NCO models, providing actionable insights for improvement.** Through CS-Probing, we find that: (1) distinct inductive biases learned by different NCO models; (2) they encode decision rationales in specific embedding dimensions closely tied to generalization; and (3) in the subspace formed by these key dimensions, model decisions can be interpreted by examining only a few informative dimensions.\n\nIII. Conclusion.\n\nTo the best of our knowledge, we are the first to introduce probing techniques in the context of NCO. Our proposed probing tasks and the CS-Probing framework not only provide a new method comparable to hyperparameter tuning for improving model performance, but also allow us to verify whether specific knowledge is encoded in NCO representations and to reveal how black-box models make decisions by identifying the most informative embedding dimensions.\n\nThis is significant for future research, as it opens up new directions for understanding the inductive biases of NCO models, evaluating the presence and form of knowledge encoded in their embeddings, and guiding the design of more efficient and interpretable representations. As illustrated in the additional experiment presented in our response above (under “Cons”), probing can directly inform actionable strategies. This provides supporting evidence for the practical utility of probing in both interpreting and improving NCO models.\n\n---\n\n**3. Q2-*For Probing Task 2, how does your study address the issue of non-uniqueness in optimal solutions, especially when drastically different solutions have similar optimization costs?***\n\nThe answer to this question can be found in lines 624 to 631 on page 15 of the manuscript. Here, we summarize the relevant text from the manuscript to explain how we address the issue of non-uniqueness in optimal solutions, for your reference:\n\n- We first follow the procedure described in page 614 to 623 of the manuscript to collect positive and negative labels for a given instance. Specifically, we extract an edge from the optimal solution as the positive label (label 1), and the edge connected to the same node with the closest Euclidean distance that is not part of the optimal solution as the negative label (label 0). For example, the positive edge might be between node ***a*** and node ***b***, while the negative edge is between node ***a*** and node ***c***.\n- We then examine the edge labeled as 0. To verify its correctness, we add a constraint to the mathematical model that forces the connection between nodes ***a*** and ***c***. The new optimal solution obtained under this constraint has a higher cost than the original unconstrained solution, indicating that this edge is not part of any optimal solution for this instance.\n- Similarly, for the data labeled as 1, we add a constraint that prevents the connection between nodes ***a*** and ***b***. The resulting solution is also worse than the original, confirming that both labels are valid.\n\nUsing the above method, we ensure that the routing instance dataset we collect does not contain instances with multiple optimal solutions, thereby preserving the rigor and validity of the probing dataset."}, {"review_id": "YArBcXm7LB", "reviewer": "Reviewer_LZ81", "summary": "This paper proposes Coefficient Significance Probing (CS-Probing) to enable deeper analysis of representations for neural combinatorial models. Existing neural combinatorial models are black-box models that lack interpretability. CS-Probing reveals that different NCO models introduce diverse inductive biases into the representations. The authors also try to uncover the mechanisms of generalization in NCO models.", "questions": "1. Diffusion models have shown good performance in combinatorial optimizations. What about the analysis in diffusion models? Do the discoveries also hold in diffusion-based solvers?\n\n2. LEHD uses key dimensions for decision-making. Although the optimality gap increase as we use the two-dimension embeddings. Can we use less embeddings, such as 8, 16, 32 or 64 dimensions, while the performance does not decrease?", "limitations": "The paper does not propose an effective algorithm to enhance the representation learning or generalization of the neural combinatorial solvers.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper proposes a method to interpret the black-box neural combinatorial models. The task is meaningful in the field of combinatorial optimization.\n2. The paper offers insights into the representations, inductive biases and generalization mechanisms of the neural combinatorial models.\n\nWeaknesses:\n1. The authors focus on analyzing the representations of the neural combinatorial models. However, I encourage the authors to provides some representation learning methods to improve the performance and generalization ability of combinatorial solvers based on the discoveries.\n2. I find the paper uses instances with only 20, 100 and 200 nodes in the experiments. I wonder whether the results also hold in large scale combinatorial problems. In fact, we are more interested in the analysis and improvement in the large-scale problems.\n3. The details and the usage of linear probing model is not clear. The authors may explain the probing process.", "was_revised": true, "final_justification": "After reviewing the detailed response, I now understand the significance and technical challenges of integrating interpretability methods into the NCO domain. The novelty of the paper has been clarified, and the additional experiment has strengthened my confidence in the validity of the claims. I believe the authors have sufficiently addressed my concerns, and I trust that my primary feedback will be incorporated as promised.\n\nRegarding the camera-ready version, I recommend including the added experiments (such as the TSPLib experiment) in the main paper or at least in the appendix. Also, as mentioned in the author's response, a thorough discussion of further exploration of probing for diffusion-based models would further enhance the paper. I recommend to add it as well, e.g., in the conclusion part as a future work direction.\n\nUnder these conditions, I could support a score of 4.", "rebuttal": "We appreciate the reviewer’s constructive feedback and recognition of our contributions to interpreting NCO models, particularly our insights into representation learning, inductive biases, and generalization mechanisms. This was the core motivation of our study, and we appreciate your recognition. We understand the main concern is regarding how to leverage these findings and the broader probing applicabilitys, which we address with new experiments and discussions as follows.\n\n---\n\n**1. W1&Limitations-*The authors focus on analyzing representations in neural combinatorial models. I encourage them to propose representation learning methods to enhance solver performance and generalization.***\n\nThanks for the suggestion! Before we provide new experiments to directly show how to translate our findings into actionable designs, we would like to first emphasize that:\n\n* **We introduce the first probing framework for NCO and offers the first comprehensive study of internal representations in existing NCO models.** We regard our work as a meaningful and necessary step, as our interpretability framework can provide the foundation for more principled novel designs in the future. \n* **More importantly, we enhances transparency and address the key questions raised by the operations research (OR) community.** We uncover what knowledge NCO models capture and how they are leveraged to solve CO problems. These represent foundational questions raised by the OR community concerning the soundness of NCO methods. Our work directly studies them: NCO models capture both low-level features such as Euclidean distance and high-level strategies like avoiding myopic decisions.\n* **We provide new analytical tools (CS-Probing).** Through CS-Probing, we find that: (1) distinct inductive biases learned by different NCO models; (2) they encode decision rationales in specific embedding dimensions closely tied to generalization; and (3) in the subspace formed by these key dimensions, model decisions can be interpreted by examining only a few informative dimensions.\n\nWe believe our findings are worth sharing with the community, which aligns well with many related interpretability research in deep learning. For example: (1) In computer vision, [1] employs probing to evaluate CNN layer representations, revealing that deeper layers produce increasingly linearly separable features, which informs future representation evolution, skip connection design, etc; (2) In natural language processing, [2] demonstrates that probing enhances interpretability, guides architecture design, uncovers latent capabilities, and inspires representation manipulation and alignment.\n\n**We agree with the reviewer that designing methods based on our findings is exciting. To show such potential, we conducted an experiment inspired by our probing insight that LEHD generalizes more effectively when its decisions depend on a small subset of embedding dimensions, indicative of sparsity in its final layers. We therefore introduced a regularization term to further promote sparsity in LEHD’s final-layer embeddings, thereby demonstrating how our insights can inform model design.**\n\nSpecificlly, we trained LEHD models with varying regularization strengths (λ) on TSP100 and evaluated their generalization on TSP200 and TSP1000. The table reports the performance gap to the best known solutions. The first column (origin, namely λ = 0) corresponds to the unregularized baseline. Moderate regularization (λ = 1e-6 to 1e-3) improves generalization. We will include this experiment to demonstrate the practical value of our probing approach. The current results are preliminary due to time constraints, and a more thorough analysis on more layers/models will be provided in the revised paper.\n\n|     | origin | 1e-6 | 1e-5 | 1e-4 | 1e-3 |\n|-----|-----|-----|-----|-----|-----|\n| TSP100  | 0.57%  | 0.58%  | 0.57%  | 0.57%  | 0.57%  | \n| TSP200 (generalization)   | 0.86%  | 0.88%  | 0.86%  | **0.73%**  | 0.82%  | \n| TSP1000 (generalization)  | 3.17%  | **2.87%**  | 2.93%  | 2.97%  | 3.05%  | \n\nBeyond this, we will enrich our discussions in Section 5 to outline several promising avenues for enhancing NCO models, including compression, distillation, and pruning of their representation space. Probing NCO layers across CO tasks and training stages may reveal task-specific dimensional requirements, thereby providing a systematic alternative to heuristic selection. We note that while no single study can encompass all possible experiments, our proposed probing pipeline and CS-Probing will serve as powerful tools for future research.\n\n[1] Alain, Guillaume, and Yoshua Bengio. \"Understanding intermediate layers using linear classifier probes.\"\n\n[2] Allen-Zhu, Zeyuan, and Yuanzhi Li. \"Physics of language models: Part 3.1, knowledge storage and extraction.\"\n\n---\n\n**2. W2-*Large scale problems.***\n\nWhile we believe analyzing representations on a smaller scale is a meaningful way to isolate complexities and yield insightful findings, we follow your suggestion and include experimental results on TSP-500 and TSP-1000 instances to validate our probing-based approach at larger scales. Since solving large-scale TSPs to optimality is often infeasible, we use approximate solutions as labels instead of exact optima, consistent with prior work. All results are averaged over 1,000 instances. \n\nAs shown in the tables below, our key findings persist at larger problem scales. The superiority of LEHD over two heavier encoder-based models becomes even more pronounced in probing results, mirroring its strong performance on large instances and reinforcing our original conclusions. Moreover, LEHD continues to depend on the same key embedding dimensions across scales. This experiment confirms that probing remains an efficient and reliable method for interpreting model behavior in large-scale settings, since it only requires training a lightweight linear probe and thus presents no scalability barrier. We will integrate these results into Table 9 of the manuscript.\n\n| Probing input | *Probing Task 1* | *Probing Task 2* |\n|-----|-----|-----|\n|TSP500|||\n| AM | 0.9240  | 0.71 |\n| POMO |  0.8963  | 0.75 |\n| LEHD |  0.9512   | 0.85 |\n|TSP1000|||\n| AM | 0.9135 | 0.63 |\n| POMO |  0. 8981  | 0.66 |\n| LEHD | 0.9479 | 0.83 |\n\n---\n\n**3. W3-*The linear probing model and probing process are unclear.***\n\nThe linear probing model is a linear model, specifically\n\n$y=\\beta_0+\\beta_1 x_1 + ... \\beta_n x_n$\n\nwhere $y$ represents the information to be probed, $x_n$ is the activation value of the $n$-th dimension of the embedding of the NCO model, and $\\beta$ is the regression coefficient.\n\nThe probing process is detailed in Section 3.1 and Appendix B. Briefly, probing tests whether a deep model encodes specific information by training a simple (typically linear) model to predict target labels from the model’s internal activations. Successful prediction indicates that the relevant information is present in the embeddings. This approach is standard in other domains as well.\n\nWe will revise the paper to more clearly describe the linear probing model. Please let us know if there are any specific points of confusion that we can further clarify.\n\n---\n\n**4. Q1-*Do the probing analyses also apply to diffusion-based models?***\n\nYes, probing can also be applied to analyze diffusion-based NCO models. For example, the classic model in [1] uses a denoising network that is a GNN, and the node embeddings of the graph in this GNN can be analyzed in the same way as the node embeddings in Transformer-based NCO models for solving routing problems. Additionally, we demonstrate how probing can be applied to GNN models in Section 3.3 on page 5 of the manuscript.\n\nTo further address your question, we conducted a preliminary experiment on DIFUSCO. We trained the model for 20 epochs and then applied probing to analyze its representations. The table below presents node embedding results for DIFUSCO. As the number of GNN layers increases, the ability to capture Euclidean distances slightly declines, while the ability to identify optimal edges improves. This distinction between low-level and high-level feature encoding aligns with patterns observed in previous models in the manuscript. These results demonstrate that probing is also effective for analyzing diffusion-based models, where the GNN acts as the denoising network.\n\n| Probing input | *Probing Task 1* | *Probing Task 2* |\n|-----|-----|-----|\n| h_init | 0.9476 | 0.49|\n|  h_12 | 0.8710  | 0.73 |\n\n[1] Sun, Zhiqing, and Yiming Yang. \"Difusco: Graph-based diffusion solvers for combinatorial optimization.\"\n\n---\n\n**5. Q2-*Can we use less embeddings for LEHD, while the performance does not decrease?***\n\nInsightful questions! Dimensionality selection in deep learning models is a complex and interesting problem. To first answer the question: the LEHD model as a whole does not achieve comparable performance with very low-dimensional embeddings (e.g., 8 or 16 dimensions). Although the LEHD model appears to rely primarily on just two dimensions of the final-layer embeddings to make near-equivalent decisions, this does not imply that the entire model operates using only these two dimensions. The earlier layers still require high-dimensional representations to effectively learn and process information.\n\nWe agree with the reviewer that developing a principled method for determining the necessary dimensions of NCO models while retaining perforamnce is an exciting future work. Notably, the additional experiments in our response to W1 have already provided preliminary evidence that insights from our probing analysis can improve LEHD’s generalization performance while employing fewer active embeddings via sparsity regularization. We consider these findings both compelling and worthy of extension to other layers in future work, where our proposed probing pipeline/tools will furnish a systematic approach for identifyin key dimensions of each layer."}, {"review_id": "zQ0LNgrMRT", "reviewer": "Reviewer_ksMb", "summary": "This paper proposes probing techniques to Neural Combinatorial Optimization (NCO) models, addressing a fundamental gap in the interpretability of these \"black-box\" systems. The authors investigate the representations learned by SOTA NCO solvers (AM, POMO, LEHD) on the TSP and CVRP. They achieve this through a series of well-designed probing tasks that test for both low-level (e.g., Euclidean distance perception) and high-level (e.g., myopia avoidance) knowledge. The primary methodological contribution is Coefficient Significance Probing (CS-Probing), which analyzes both the magnitude and statistical significance of probe coefficients to identify key embedding dimensions responsible for encoding specific knowledge. The findings reveal that NCO models learn both geometric and strategic information, that different architectures possess distinct inductive biases, and that superior generalization correlates with the consistent reuse of a sparse set of key dimensions.", "questions": "My score would increase if the authors provide a stronger comparative context for CS-Probing against other methods or demonstrate the practical utility of their insights by using them to improve a model. And I have the following questions:\n\n1. How does CS-Probing compare, empirically or theoretically, to other interpretability methods like gradient-based attribution or attention visualization for NCO models? What unique insights does it provide? And what is your justification for the sufficiency of linear probes, given that the models themselves are highly non-linear?\n2. Have you considered the impact of multiple hypothesis testing when analyzing the significance of 256 dimensions? How might methods to control the false discovery rate (e.g., Benjamini-Hochberg procedure) affect your conclusions about which dimensions are truly important?\n3. The finding that two dimensions are sufficient for high performance is striking. How robust is this finding to different initializations or training runs? To establish causality, have you performed ablation studies where you zero out these specific dimensions and measure the performance degradation?\n4. Can you provide a concrete example or a proposal for how the insights from CS-Probing could be used to design a better NCO model? For instance, could you design a regularization term that encourages the model to learn sparse, disentangled representations like those you observed in the LEHD model?", "limitations": "The authors acknowledge practical limitations in the appendix.", "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\n1. The paper introduces CS-Probing, a novel and fine-grained analytical tool that moves beyond simply detecting the presence of information to identifying where it is encoded. The design of NCO-specific probing tasks is well-motivated and thoughtfully adapted from established practices in NLP and computer vision.\n2. This is the first systematic effort to apply probing to NCO models, addressing the critical barrier of model interpretability that currently limits their adoption in high-stakes applications.\n3. The experimental evaluation spans multiple models, tasks, and problem scales. The analysis across model layers, training epochs, and generalization scenarios provides a multi-faceted view of model behavior. The finding that just two dimensions can suffice for near-optimal performance is a powerful and actionable insight.\n4. The paper is well-written, organized, and effectively uses figures to communicate complex findings.\n\n# Weaknesses:\n1. The paper does not provide a theoretical justification for why linear probing is sufficient for analyzing NCO models, nor does it empirically validate this assumption against non-linear probes. Furthermore, the work is presented without comparison to other established interpretability techniques (e.g., gradient-based attribution, attention visualization, neuron ablation), making it difficult to assess the unique advantages of CS-Probing.\n2. The analysis involves simultaneously testing 256 dimensions for significance without discussing or applying corrections for multiple hypothesis testing. This raises concerns about the potential for a high false discovery rate, and the statistical validity of the identified key dimensions is not as rigorously established as it could be.\n3. The core claims are based primarily on three attention-based models for routing problems. While extensions are mentioned in the appendix, the paper would be far more compelling if it demonstrated the generality of the approach on a fundamentally different architecture (e.g., a GNN) or CO problem in the main text. Additionally, the sensitivity of the findings to the specific design of the probing tasks is not explored.\n4. While the insights are analytically interesting, the paper stops short of demonstrating their practical utility. A crucial missing piece is a demonstration of how these interpretability insights could be used to guide the design of a new or improved NCO model, for instance, by applying regularization to encourage sparsity or by building a model that explicitly leverages the identified key dimensions.", "was_revised": true, "final_justification": "Based on these substantial improvements in statistical rigor, practical utility, and empirical validation, I am increasing my score.", "rebuttal": "We thank the reviewer for the constructive and valuable feedback! We appreciate the recognition that our work addresses fundamental gaps, introduces a novel and well-designed framework, overcomes critical barriers, and provides powerful, actionable insights. We also especially thank you for your suggestion to investigate sparsity regularization, which we have found to be beneficial for enhancing generalization. Please find below our responses detailing the new experiments and expanded discussion; we trust these enhancements will further demonstrate the value of our work.\n\n---\n\n**1. W1&Q1-*Lack justification for using linear probing over non-linear probes and does not compare CS-Probing with other interpretability methods. What unique insights does it provide?***\n\n**I.Why linear probe?**\n\nIn representation analysis, linear probing tests whether a feature is encoded in a form that can be extracted by a simple affine transformation. If a property is linearly separable, then the network has organized its internal geometry to make that feature readily available downstream. While NCO models are globally non-linear, our interest lies precisely in whether certain combinatorial features are represented in a geometrically simple (i.e., linearly decodable) form, because the final output layers of NCO models use the embeddings in a linear manner.\n\nFor non-linear probes, consider Probing Task 1 (Euclidean distance): although non-linear models may yield better regression performance, it becomes unclear whether the gains stem from the NCO model’s embeddings or the probe’s capacity. Moreover, non-linear probing adds complexity that obscures the internal representations we aim to interpret. Therefore, we adopt linear probing to better align with our goal of understanding how NCO models encode information.\n\n**II. Compare to other interpretability methods**\n\n- Gradient-based attribution. It reveals output sensitivity to input features but does not indicate where or whether specific combinatorial concepts are encoded in hidden representations. It also lacks structural insight into how the model organizes or reasons over the solution space. In contrast, probing offers a systematic interpretability framework by evaluating the linear decodability of target properties from intermediate representations. Our CS-Probing further identifies the specific layers and embedding dimensions where each concept is encoded.\n- Visualization. Attention visualization highlights which nodes or edges the model attends to, but it neither quantifies representational separability nor reveals what specific information is encoded for decision-making in NCO models. In contrast, probing provides a systematic and quantitative assessment of linear separability and information content within embeddings, offering a layer-wise view of representational structure and deeper insight into how decision-relevant information is encoded. Besides, at the beginning of Section 4, we already employ activation visualization, a commonly used interpretability method, as shown in Figure 4. We will also add a discussion of attention visualization in the revised manuscript.\n- Neuron ablation. Eliminating units (by zeroing or randomizing) can help validate the importance of specific neurons, but it is not suitable for identifying which dimensions capture particular information. Zeroing a dimension reveals little about its meaning, and in high-dimensional spaces, it is impractical to test all dimensions or combinations exhaustively. **However, we still include a new experiment based on the neuron ablation method, where we use zeroing to validate the key dimensions identified by CS-Probing. Please refer to the response to Q3 for details.**\n\n**III. Unique insights the CS-Probing provides**\n\nCompared to existing probing methods, CS-Probing offers a deeper level of analysis. As detailed in the manuscript, it not only assesses whether certain information is captured by the deep model's embeddings, but also reveals how that information is encoded. For example, CS-Probing enables us to uncover why LEHD demonstrates better generalization, a capability that standard probing methods typically lack.\n\n**IV. Improvement of the manuscript**\n\nAdditional results on neuron ablation (see our response to Q3) and attention visualization will be included in the revised manuscript.\n\n---\n\n**2. W2&Q2-*No multiple hypothesis testing.***\n\nThank you for the suggestion. We have incorporated it and added new experiments accordingly. Specifically, we applied the Benjamini-Hochberg procedure to control **the false discovery rate (FDR) at 0.05** across the 256 tested dimensions. We found that the key LEHD dimensions previously identified as significant remain so after correction, **consistent with the results reported in Table 2 of the manuscript**. The updated results and a description of the correction procedure will be included in the revised manuscript.\n\nNotably, the original p-values of these dimensions were well below conventional thresholds (less than 1e-4, as shown in the sample_codes\\3_probing_exp\\example_probing_exp.ipynb in the anonymous link provided in the manuscript), and they remained significant after FDR correction, further supporting the robustness of our findings.\n\n---\n\n**3. W3-*Limited evidence of generality across architectures or problems.***\n\nTo address your concern, we conducted a preliminary experiment on DIFUSCO [1], a diffusion-based NCO. We trained the model for 20 epochs and then applied probing to analyze its representations. The table below presents node embedding results for DIFUSCO. As the number of GNN layers increases, the ability to capture Euclidean distances slightly declines, while the ability to identify optimal edges improves. This distinction between low-level and high-level feature encoding aligns with patterns observed in previous models in the manuscript. These results demonstrate that probing is also effective for analyzing other architectures, e.g., diffusion-based models, where the GNN acts as the denoising network.\n\n| Probing input | *Probing Task 1* | *Probing Task 2* |\n|-----|-----|-----|\n| h_init | 0.9476 | 0.49|\n|  h_12 | 0.8710  | 0.73 |\n\n[1] Sun, Zhiqing, and Yiming Yang. \"Difusco: Graph-based diffusion solvers for combinatorial optimization.\"\n\n---\n\n**4. W4&Q4-*Lack a demonstration of how the insights can inform the design of improved NCO models.***\n\nWe thank the reviewer for the valuable suggestion on applying regularization to encourage sparsity. We found that, based on CS-probing insights, simply regularizing the final-layer embeddings of the LEHD decoder can directly **improve its generalization**.\n\nIn this new experiment, we **simply regularize** the final-layer embeddings of the LEHD decoder to encourage sparsity in its representations, **without making any changes** to the original LEHD model architecture, training hyperparameters, or code implementation.\n\nSpecificlly, we trained LEHD models with varying regularization strengths (λ) on TSP100 and evaluated their generalization on TSP200 and TSP1000. The table reports the performance gap to the best known solutions. The first column (origin, namely λ = 0) corresponds to the unregularized baseline. Moderate regularization (λ = 1e-6 to 1e-3) improves generalization. The current results are preliminary due to time constraints, and a more thorough analysis on more layers/models will be provided in the revised paper.\n\n|     | origin | 1e-6 | 1e-5 | 1e-4 | 1e-3 |\n|-----|-----|-----|-----|-----|-----|\n| TSP100  | 0.57%  | 0.58%  | 0.57%  | 0.57%  | 0.57%  | \n| TSP200 (generalization)   | 0.86%  | 0.88%  | 0.86%  | **0.73%**  | 0.82%  | \n| TSP1000 (generalization)  | 3.17%  | **2.87%**  | 2.93%  | 2.97%  | 3.05%  | \n\nWe will include this simple yet effective generalization-enhancing experiment in the manuscript to demonstrate the practical value of our proposed probing approach. It provides direct evidence that insights obtained through probing can lead to tangible improvements in model generalization performance.\n\n---\n\n**5. Q3-*How robust is the two-dimensional finding across runs, and have ablation studies been conducted to test its causal impact (by zero the two key dimensions out) on performance?***\n- **Re-training.** We retrained the LEHD model under different random seeds. We found that although the key dimensions vary across different runs, the conclusion still holds: the LEHD model consistently relies on a small number of key dimensions to make decisions across different scales. Specifically, we find that the retrained LEHD model still relies on two key dimensions to capture decision-relevant information. Although these two dimensions differ from those listed in Table 2 of the manuscript, all of our conclusions remain valid.\n- **Neuron ablation.** We include **an new experiment based on the neuron ablation method**, where we use zeroing to validate the key dimensions identified by CS-Probing. As shown in the table below, zeroing LEHD’s **key dimensions (31 and 97)** results in a significant performance drop (over 60%). Even zeroing either one individually causes a larger gap than zeroing other dimensions. For comparison, we zeroed two non-key dimensions: 98 (with large activation in Figure 4 of the manuscript) and 126 (with the highest probing coefficient among non-key dimensions in Table 2). In addition to these new experimental results, the original results in Table 3 of the manuscript also show that LEHD continues to rely on the same two key dimensions when generalizing to larger problem sizes. These results further confirm the importance of the key dimensions identified by CS-Probing.\n\n| Zeroing Dimension(s)     | Gap |\n|--------|--------|\n| None(original) | 0.57% |\n| 31, 97 | 60.43% |\n| 31 | 0.90% |\n| 97 | 1.80% |\n| 98 | 0.59% |\n| 126 | 0.60% |\n| 98, 126 | 0.62% |\n\nWe will include this new experiment and observation in the updated manuscript to enhance the robustness of our findings."}, {"review_id": "b9DOckW1MB", "reviewer": "Reviewer_veN7", "summary": "This paper uses probing techniques to analyze the inner workings of neural combinatorial optimization (NCO) methods: the authors suggest that while these methods have achieved remarkable success, we lack an understanding of the reasons for this success particularly in terms of model representation and reasoning rationale. Therefore, the paper introduces Coefficient Significance Probing (CS-probing) to investigate the embedding space of transformer-based NCO models. The key finding is that models with better generalization tend to consistently rely on the same embedding dimensions across tasks. In contrast, models whose knowledge becomes disorganized across dimensions during generalization tend to suffer performance degradation.", "questions": "Recent works have introduced diffusion models for combinatorial optimization [1,2]. Could the proposed CS-probing technique be applied to analyze such models as well?\n\n[1] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization, NeurIPS 2023\n\n\n[2] A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization, ICML 2024", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths And Weaknesses:\n\nStrengths:\n\n1. This is the first work to apply probing techniques in the context of NCO, which helps reveal the internal mechanisms of these models.\n\n2. The paper is clearly written and well-structured.\n\nWeaknesses:\n\n1. The paper is purely empirical with no methodological innovation. While this is acceptable, the experimental setup is limited in scope—focused only on small-scale instances of TSP, CVRP, and JSSP. Broader empirical evaluation is necessary to draw robust conclusions.\n\n2. It is difficult to pinpoint where differences between model behaviors originate. Are they due to variations in neural architectures or differences in training algorithms?\n\n3. The conclusions drawn from CS-probing, while interesting, lack practical implications. It remains unclear how these insights could inform the design of improved NCO methods in future work.\n\n4. The benchmarked methods, such as POMO and AM, are relatively early approaches. It would be more compelling to evaluate with newer, state-of-the-art models.\n\nMinor comment: The paper relies heavily on the appendix. I understand that the page limit makes it difficult to keep main results in the main text. Nonetheless, and this is therefore I am keeping this as a minor comment that I hope the authors will find helpful, I suggest the authors attempt to restructure the paper to make key findings more accessible within the main text.", "was_revised": true, "final_justification": "The comprehensive rebuttal and new experimental results have addressed most of my concerns. I increased my score accordingly", "rebuttal": "We appreciate the reviewer for the constructive comments and for recognizing our contributions as the first to interpret NCO models and to provide a tool that helps reveal the internal mechanisms of these models. This aligns with the core objective of our work, and we are grateful for your recognition. We understand that the main concern lies in the need for broader empirical evaluation, particularly in terms of scalability to larger problem sizes and applicability to diffusion-based models, as well as how to effectively leverage the findings and extend the probing method’s practical implications. We have conducted additional experiments and provided further discussion to address these concerns, as outlined below.\n\n---\n\n**1. W1-*Experimental setup is limited in scope.***\n\nWhile we believe analyzing representations on a smaller scale is a meaningful way to isolate complexities and yield insightful findings, we follow your suggestion and include experimental results on TSP-500 and TSP-1000 instances to validate our probing-based approach at larger scales. Since solving large-scale TSPs to optimality is often infeasible, we use approximate solutions as labels instead of exact optima, consistent with prior work. All results are averaged over 1,000 instances. \n\nAs shown in the tables below, our key findings persist at larger problem scales. The superiority of LEHD over two heavier encoder-based models becomes even more pronounced in probing results, mirroring its strong performance on large instances and reinforcing our original conclusions. Moreover, LEHD continues to depend on the same key embedding dimensions across scales. This experiment confirms that probing remains an efficient and reliable method for interpreting model behavior in large-scale settings, since it only requires training a lightweight linear probe and thus presents no scalability barrier. We will integrate these results into Table 9 of the manuscript.\n\n| Probing input | *Probing Task 1* | *Probing Task 2* |\n|-----|-----|-----|\n|TSP500|||\n| AM | 0.9240  | 0.71 |\n| POMO |  0.8963  | 0.75 |\n| LEHD |  0.9512   | 0.85 |\n|TSP1000|||\n| AM | 0.9135 | 0.63 |\n| POMO |  0. 8981  | 0.66 |\n| LEHD | 0.9479 | 0.83 |\n\n---\n\n**2. W2-*Are the behavioral differences due to architectural variations or training algorithm differences?***\n\nYour confusion is completely understandable, as we also encountered this question frequently before conducting this study. It is precisely because it is difficult to pinpoint where differences in model behavior originate that we introduced probing, along with our newly proposed probing methods, to help address this challenge. Below, we first provide a direct answer to your question based on the conclusions from the original manuscript, and then summarize our findings from the manuscript regarding the impact of model architecture and training methods, respectively. \n\n- Directly answer your question: In our original manuscript, we provide an answer to this question: model architecture influences inductive bias, which in turn shapes how models capture decision-relevant information. Models with better generalization tend to encode information using a small number of key dimensions and consistently rely on the same dimensions across different problems. On the other hand, at least in the case of POMO, we find that the training method has relatively little impact on the model's internal behavior. We summarize the relevant findings from our manuscript for your reference below.\n\n- Model architecture: Through the probing analysis, we verify the impact of differences in model architecture. This includes the contrast between heavy encoder models, such as AM and POMO, and heavy decoder models, such as LEHD, in how they capture decision-relevant information. Specifically, LEHD with better generalization tend to consistently utilize the same embedding dimensions across different tasks. In contrast, models whose internal knowledge becomes dispersed or disorganized across dimensions during generalization tend to suffer performance degradation. These findings are discussed in detail in Section 4.3 in page 7 of the manuscript. Furthermore, the additional experiments presented in our response to W3, the details of which are provided below, offer further evidence supporting this conclusion.\n\n- Training methods: We compared different training methods for the POMO model in the manuscript. Using probing, we analyzed the ability of POMO models trained via supervised learning (SL) and reinforcement learning (RL) to capture decision-relevant information. The results show that the SL variant performs slightly worse than its RL counterpart (0.84 vs. 0.86 on Probing Task 2), which is consistent with their overall performance gap (0.571% for SL vs. 0.134% for RL on TSP100). The detailed results can be found in the manuscript, lines 795 to 799.\n\n---\n\n**3. W3-*The conclusions from CS-Probing lack practical implications and fail to show how they could inform the design of improved NCO methods.***\n\nTo address the concern that CS-Probing lacks practical implications, we added **a simple yet effective new experiment** based on the insights derived from CS-Probing in the original manuscript. **Specificly, we conducted an experiment inspired by our probing insight that LEHD generalizes more effectively when its decisions depend on a small subset of embedding dimensions, indicative of sparsity in its final layers. We therefore introduced a regularization term to further promote sparsity in LEHD’s final-layer embeddings, thereby demonstrating how our insights can inform model design.**\n\nSpecificlly, we trained LEHD models with varying regularization strengths (λ) on TSP100 and evaluated their generalization on TSP200 and TSP1000. The table reports the performance gap to the best known solutions. The first column (origin, namely λ = 0) corresponds to the unregularized baseline. Moderate regularization (λ = 1e-6 to 1e-3) improves generalization. We will include this experiment to demonstrate the practical value of our probing approach. The current results are preliminary due to time constraints, and a more thorough analysis on more layers/models will be provided in the revised paper.\n\n|     | origin | 1e-6 | 1e-5 | 1e-4 | 1e-3 |\n|-----|-----|-----|-----|-----|-----|\n| TSP100  | 0.57%  | 0.58%  | 0.57%  | 0.57%  | 0.57%  | \n| TSP200 (generalization)   | 0.86%  | 0.88%  | 0.86%  | **0.73%**  | 0.82%  | \n| TSP1000 (generalization)  | 3.17%  | **2.87%**  | 2.93%  | 2.97%  | 3.05%  | \n\nBeyond this, we will enrich our discussions in Section 5 to outline several promising avenues for NCO models to enhance practical implications, including compression, distillation, and pruning of their representation space. Probing NCO layers across CO tasks and training stages may reveal task-specific dimensional requirements, thereby providing a systematic alternative to heuristic selection. We note that while no single study can encompass all possible experiments, our proposed probing pipeline and CS-Probing will serve as powerful tools for future research on the design and analysis of NCO models.\n\n---\n\n**4. W4&Question-*The benchmarked methods are outdated. Could the proposed CS-probing technique be applied to analyze current Diffusion-based modals as well?***\n\nYes, probing can also be applied to analyze the current diffusion-based NCO models. For example, the classic model in [1] uses a denoising network that is a GNN, and the node embeddings of the graph in this GNN can be analyzed in the same way as the node embeddings in Transformer-based NCO models for solving routing problems. Additionally, we demonstrate how probing can be applied to GNN models in Section 3.3 on page 5 of the manuscript.\n\nTo further address your question, we add a prelimiary experiment of DIFUSCO. Due to version conflicts in DIFUSCO’s code, we rebuilt the environment with alternative packages compatible with our hardware, which prevented us from using its pretrained models. Instead, we present probing results from our own DIFUSCO training (20 epochs), showing that diffusion-based NCO models can also be effectively analyzed with probing.\n\nThe table below presents node embedding results for DIFUSCO. As the number of GNN layers increases, the ability to capture Euclidean distances slightly declines, while the ability to identify optimal edges improves. This distinction between low-level and high-level feature encoding aligns with patterns observed in previous models in the manuscript. These results demonstrate that probing is also effective for analyzing diffusion-based models, where the GNN acts as the denoising network.\n\n| Probing input | *Probing Task 1* | *Probing Task 2* |\n|-----|-----|-----|\n| h_init | 0.9476 | 0.49|\n|  h_12 | 0.8710  | 0.73 |\n\n[1] Sun, Zhiqing, and Yiming Yang. \"Difusco: Graph-based diffusion solvers for combinatorial optimization.\"\n\n---\n\n**5. Minor comment-*The paper relies heavily on the appendix.***\n\nThank you for this helpful suggestion. We appreciate your understanding of the page limit constraints. We will carefully reread the paper, and if we identify areas where the flow would benefit from additional context, we will incorporate the relevant key results from the appendix into the main text to improve clarity and accessibility."}]

Author rebuttal:

Meta-review: Neural combinatorial optimization (NCO) is an emerging and powerful approach for solving classical combinatorial problems. However, while NCO models have shown impressive performance, the internal representations they learn remain largely uninterpretable. This paper addresses this gap by introducing the first method for probing NCO models, revealing several interesting insights into their inner workings.

All the reviewers were enthusiastic about the paper with two of them recommending acceptance and two others recommending weak acceptance. They highlighted several key strengths, including the novel and practical use of probing to understand and improve NCO models, the extensive experimental validation, and the paper's overall clarity and high quality of writing.

Reviewers initially raised a few weaknesses, but the consensus is that the authors have addressed them all effectively in the rebuttal and subsequent discussions. Specifically, the authors clarified the actionable implications by demonstrating that their insights can directly improve model performance, added new experiments on larger-scale problems, and successfully applied their probing method to modern diffusion-based NCO models.

Given that the paper's strengths significantly outweigh any initial concerns, I am pleased to recommend **acceptance**. Furthermore, because this work provides the first look into the internal mechanisms of this important class of models and opens up new avenues for their analysis and improvement, I also recommend that it be highlighted as a **spotlight** presentation.

I strongly encourage the authors to incorporate the new experiments and discussions from the rebuttal into the revised paper.
Decision: Accept (spotlight)