Neural Combinatorial Optimization (NCO) has achieved strong empirical success, yet the internal mechanisms driving model decisions remain largely unexplored. In this paper, we investigate three representative autoregressive NCO models spanning two encoder-decoder configurations: AM and POMO (heavy-encoder, light-decoder), and LEHD (light-encoder, heavy-decoder). Through behavioral analyses, representation probing, and causal interventions, we examine how these models construct solutions and use internal representations during decoding. Our results suggest that AM and POMO predominantly follow a persistent geometric pattern throughout solution construction, whereas LEHD contains linearly accessible information about multiple future actions. Causal experiments further provide evidence for the role of future-node representations in LEHD's decision-making. We also observe that LEHD relies strongly on the current-node representation for immediate local decisions, while the start-node representation plays a broader navigational role over the subsequent route. Cross-instance alignment analyses additionally indicate that LEHD maps current-node representations into a relatively shared latent region, which may provide a stable reference for evaluating subsequent decisions. Across the Traveling Salesman Problem and the Capacitated Vehicle Routing Problem, these results reveal distinct decision-making patterns across these architecturally distinct solvers and provide a foundation for more interpretable analyses of NCO solvers. Code and additional visualizations are provided in the https://github.com/NCO-Interpretability/NCO-Interpretability.
Figures & tables
Figure 1: Comparison of POMO and LEHD tour construction strategies. Left: POMO constructs the tour in a clockwise manner while oscillating between shallow and deep onion layers, with each oscillation highlighted in a distinct color. Middle: LEHD local navigation across consecutive steps. Colored dashed lines represent candidate multi-step plans, which LEHD dynamically revises at each step. Right: LEHD global navigation. LEHD evaluates candidate branches based on the relative angular position of the start node relative to the current node. It prioritizes the branch visiting nodes further from the start first ( orange branch ) over the branch visiting closer nodes first ( blue branch ), minimizing the final return cost to the start node.
Figure 2: Behavioral comparison of NCO solvers on TSP-500 under seven synthetic distribution shifts. AM, POMO, LEHD, L2C-Insert, and cluster-trained POMO are compared by optimality gap and convex-hull order violations across Clustered, Expansion, Explosion, Grid, Implosion, Mixed, and Uniform distributions, together with inference runtime. The results highlight differences in solution quality, geometric consistency, and computational efficiency under diverse instance geometries.
Figure 3: Tracking geometrical properties of generated tours. (a) Onion layers are segmented into B bins to calculate the average number of oscillations between shallow and deeper layers, where higher values indicate a greater number of deep oscillations. (b) Each cluster is partitioned into binwise onion layers to count high-intensity oscillations within individual clusters. (c) The average start-to-current node angle relative to each tour’s first edge is tracked throughout tour construction. A decreasing angle indicates a clockwise rotation of the start-to-current displacement vector.
Figure 4: (a) LEHD attention heatmap from the current node to the unvisited nodes. (b) Probe accuracy across planning horizons for the decoder layers of LEHD, AM, and POMO. (c) Probe-guided counterfactual steering for LEHD on TSP-100 at α=5 , compared against random-direction and random-horizon baselines. Bars show the mean change in logit gap between the clean top-two actions
Figure 5: Causal interventions on node representations. (a) Drop in the clean next-node probability after mean ablation of the current and start nodes. (b) Effect of start-node activation patching under three geometric donor conditions for LEHD and POMO. (c) Example clean and patched LEHD trajectories showing route changes over 22 decoding steps.
Table 6
Appendix figures & tables33 assets
Supplementary material from the paper’s appendix.
Appendix
Distribution
L2C-Insert
LEHD
POMO
AM
POMO (Cluster-Trained)
LEHD (Cluster-Trained)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Clustered
0.55
0.06
3.83
0.49
0.07
4.86
9.41
0.49
8.22
26.68
2.99
51.24
3.37
0.18
3.00
0.19
0.01
0.95
Expansion
3.55
0.39
20.96
3.04
0.30
13.78
6.51
0.50
8.36
17.72
2.04
26.15
4.48
0.23
2.00
0.93
0.07
2.97
Explosion
2.67
0.26
9.99
1.13
0.08
3.66
5.62
0.34
6.11
9.70
0.72
13.48
3.83
0.37
5.00
0.59
0.03
0.90
Grid
2.22
0.21
8.90
0.96
0.07
3.16
5.33
0.31
5.75
8.12
0.52
10.34
3.63
0.16
2.00
0.61
0.02
0.77
Implosion
2.04
0.20
8.48
0.95
0.07
3.24
5.27
0.30
5.39
8.36
0.54
10.15
3.68
0.24
4.00
0.62
0.02
0.77
Appendix
Table 3: Solution quality and geometric consistency under greedy decoding on TSP-20 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
POMO (Cluster-Trained)
LEHD (Cluster-Trained)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Clustered
0.65
0.05
2.24
0.91
0.14
7.10
5.26
0.27
2.31
33.42
6.57
41.24
1.72
0.04
0.00
0.26
0.02
0.42
Expansion
2.61
0.43
17.21
4.21
0.67
28.55
2.69
0.31
3.26
13.38
2.76
11.25
3.12
0.21
2.00
0.94
0.10
4.00
Explosion
0.36
0.02
0.75
0.55
0.05
1.41
1.37
0.09
0.74
5.71
0.24
1.93
2.19
0.11
1.00
0.66
0.05
0.95
Grid
0.39
0.02
0.51
0.50
0.03
0.74
0.85
0.02
0.07
4.36
0.12
0.57
2.34
0.05
0.00
0.73
0.04
0.97
Implosion
0.38
0.02
0.50
0.50
0.03
0.84
0.89
0.03
0.09
4.54
0.13
0.73
2.28
0.04
0.00
0.69
0.04
0.92
Appendix
Table 4: Solution quality and geometric consistency under greedy decoding on TSP-50 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
POMO (Cluster-Trained)
LEHD (Cluster-Trained)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Clustered
1.06
0.13
3.17
1.49
0.36
12.71
7.00
1.19
8.26
41.40
13.61
39.81
2.61
0.23
0.00
0.45
0.04
0.70
Expansion
2.55
0.62
20.14
5.16
1.51
49.94
4.59
1.29
9.99
12.63
3.29
7.38
3.86
0.24
1.00
1.09
0.16
5.07
Explosion
0.45
0.02
0.37
0.63
0.08
1.37
2.12
0.46
3.49
6.55
0.45
0.47
2.75
0.19
1.00
0.75
0.09
1.28
Grid
0.47
0.01
0.19
0.56
0.03
0.42
0.90
0.07
0.07
4.32
0.19
0.03
3.20
0.24
0.00
0.85
0.06
1.19
Implosion
0.46
0.02
0.13
0.59
0.04
0.70
0.87
0.07
0.04
4.50
0.22
0.07
3.06
0.18
0.00
0.83
0.06
0.83
Appendix
Table 5: Solution quality and geometric consistency under greedy decoding on TSP-100 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
POMO (Cluster-Trained)
LEHD (Cluster-Trained)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Clustered
2.39
0.48
6.74
2.61
0.71
18.70
14.59
7.83
22.10
33.81
15.57
21.70
7.72
1.99
1.00
1.36
0.10
2.06
Expansion
0.86
0.10
0.30
1.52
0.33
0.92
3.61
0.71
0.02
7.07
0.46
0.00
7.42
1.01
0.00
1.29
0.16
0.68
Explosion
0.92
0.08
0.62
1.08
0.09
0.92
4.03
0.67
0.14
7.16
0.43
0.08
7.97
0.90
3.00
1.41
0.14
2.02
Grid
1.01
0.09
2.32
0.90
0.08
1.86
5.23
1.39
0.52
8.64
0.53
0.04
8.92
1.64
1.00
1.10
0.16
2.26
Implosion
1.41
0.20
3.22
1.53
0.34
9.60
4.71
1.57
0.74
17.76
2.14
0.94
7.73
1.66
2.00
0.89
0.10
1.98
Appendix
Table 6: Solution quality and geometric consistency under greedy decoding on TSP-200 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
POMO (Cluster-Trained)
LEHD (Cluster-Trained)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Clustered
5.58
6.45
41.06
5.41
3.86
47.98
43.54
70.07
59.50
51.78
50.90
25.04
24.71
15.83
3.00
1.91
0.69
14.36
Expansion
2.29
1.00
3.46
2.72
1.52
3.52
34.72
27.80
1.72
18.27
2.98
0.00
24.14
10.49
0.00
1.75
0.61
2.24
Explosion
2.16
0.77
7.26
2.05
0.76
5.46
33.14
22.83
3.16
18.78
3.12
0.52
24.92
9.31
2.00
1.90
0.60
5.60
Grid
2.29
1.35
17.86
1.77
0.87
19.22
26.94
30.47
8.88
21.14
2.79
0.10
22.19
9.16
3.00
1.34
0.61
12.78
Implosion
4.30
3.69
34.22
3.80
2.19
35.60
32.98
49.08
16.46
34.14
6.57
1.36
24.21
14.69
5.00
1.27
0.51
13.12
Appendix
Table 7: Solution quality and geometric consistency under greedy decoding on TSP-500 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
POMO (Cluster-Trained)
LEHD (Cluster-Trained)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Gap (%)
Cross.
Hull Viol. (%)
Clustered
9.45
29.76
69.00
9.58
13.44
65.00
66.42
212.07
75.00
75.53
188.73
40.00
37.36
38.42
7.00
2.76
2.77
48.00
Expansion
9.38
14.97
22.00
5.58
5.99
13.00
56.92
92.10
7.00
30.35
8.11
0.00
36.85
27.91
0.00
2.37
1.94
6.00
Explosion
4.65
4.78
41.00
3.83
3.60
11.00
52.55
73.73
4.00
31.19
8.31
1.00
38.35
29.75
3.00
2.45
1.69
15.00
Grid
4.50
7.54
52.00
3.56
4.11
39.00
39.61
86.19
22.00
33.42
8.62
2.00
32.19
26.03
11.00
1.79
2.49
35.00
Implosion
8.16
20.62
73.00
7.96
8.81
50.00
50.52
152.14
38.00
49.82
14.59
1.00
36.47
41.76
14.00
1.85
1.98
45.00
Appendix
Table 8: Solution quality and geometric consistency under greedy decoding on TSP-1000 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Clustered
6.99
0.02
1.42
5.02
0.04
3.47
71.63
0.27
16.87
14.27
0.24
18.84
Expansion
6.65
0.02
1.68
5.59
0.04
3.45
66.78
0.21
14.07
12.97
0.21
16.50
Explosion
6.80
0.01
1.10
5.76
0.04
3.11
66.77
0.18
12.36
12.72
0.17
14.15
Grid
6.91
0.01
1.15
5.76
0.03
2.83
65.97
0.15
10.92
12.71
0.17
13.97
Implosion
6.98
0.01
1.16
5.82
0.03
2.96
66.68
0.16
11.14
12.80
0.17
13.97
Appendix
Table 9: Solution quality and within-route geometric consistency under greedy decoding on CVRP-20 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Clustered
5.82
0.02
1.27
5.19
0.04
2.90
13.76
0.18
12.49
11.96
0.31
19.25
Expansion
5.24
0.02
1.27
4.73
0.04
2.99
11.89
0.16
11.13
9.83
0.25
16.55
Explosion
5.30
0.01
0.80
4.80
0.03
2.37
10.40
0.13
9.18
9.12
0.19
13.36
Grid
5.29
0.01
0.68
5.01
0.03
2.19
10.17
0.12
8.45
8.72
0.17
11.53
Implosion
5.33
0.01
0.73
5.00
0.03
2.33
10.26
0.12
8.37
8.74
0.17
12.06
Appendix
Table 10: Solution quality and within-route geometric consistency under greedy decoding on CVRP-50 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Clustered
4.96
0.02
1.38
5.05
0.05
3.48
5.49
0.12
8.30
12.91
0.45
23.67
Expansion
4.38
0.02
1.17
4.43
0.04
3.26
3.91
0.10
6.76
9.70
0.32
17.83
Explosion
4.12
0.01
0.77
4.28
0.03
2.46
3.37
0.07
4.61
8.63
0.23
13.05
Grid
3.87
0.01
0.54
4.16
0.03
1.92
2.98
0.06
3.59
7.65
0.17
9.98
Implosion
3.91
0.01
0.60
4.29
0.03
2.02
3.03
0.06
3.70
7.76
0.17
10.38
Appendix
Table 11: Solution quality and within-route geometric consistency under greedy decoding on CVRP-100 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Clustered
5.81
0.05
2.52
5.11
0.09
5.27
10.50
0.31
13.50
21.96
0.93
37.94
Expansion
5.97
0.05
2.44
4.34
0.07
4.81
9.62
0.33
12.47
13.77
0.58
24.98
Explosion
5.29
0.03
1.59
3.84
0.05
3.53
9.26
0.28
10.58
12.09
0.39
17.16
Grid
4.89
0.03
1.42
3.43
0.04
2.65
9.00
0.23
8.58
10.52
0.26
12.05
Implosion
5.15
0.07
3.17
3.78
0.07
4.18
9.17
0.32
11.66
13.41
0.41
15.71
Appendix
Table 12: Solution quality and within-route geometric consistency under greedy decoding on CVRP-200 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Clustered
6.00
0.18
6.27
6.72
0.34
14.97
59.38
3.67
49.81
74.56
2.07
48.33
Expansion
5.05
0.15
5.72
4.80
0.25
13.20
52.37
4.25
54.58
33.24
1.86
48.68
Explosion
4.75
0.11
4.16
4.08
0.19
10.38
49.54
3.32
51.04
28.88
1.44
40.05
Grid
4.24
0.08
3.30
3.36
0.14
8.63
39.47
2.52
47.73
21.74
0.96
30.62
Implosion
4.26
0.18
5.84
3.58
0.27
10.93
44.40
3.22
51.94
33.76
1.08
28.25
Appendix
Table 13: Solution quality and within-route geometric consistency under greedy decoding on CVRP-500 across seven test distributions.
Distribution
L2C-Insert
LEHD
POMO
AM
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Gap (%)
Cross./Route
Hull Viol. (%)
Clustered
10.77
1.04
21.95
10.84
1.02
26.28
265.92
19.10
75.78
303.36
1.82
22.42
Expansion
6.58
0.72
16.67
6.08
0.82
28.04
308.93
19.57
73.11
118.61
2.64
37.37
Explosion
6.83
0.49
13.38
5.24
0.54
24.21
304.22
17.29
76.34
123.33
1.92
32.32
Grid
5.78
0.30
9.32
4.25
0.42
20.62
303.32
18.03
81.67
61.48
1.94
39.11
Implosion
5.36
0.60
14.41
4.21
0.77
23.57
289.05
18.20
80.75
109.97
1.52
26.42
Appendix
Table 14: Solution quality and within-route geometric consistency under greedy decoding on CVRP-1000 across seven test distributions.
Distribution
TSP-20
TSP-50
TSP-100
L2C-Insert
LEHD
POMO
AM
L2C-Insert
LEHD
POMO
AM
L2C-Insert
LEHD
POMO
AM
Clustered
0.91
1.17
22.97
61.24
1.08
1.77
9.03
72.37
1.56
2.39
11.61
79.98
Expansion
13.21
7.69
19.82
42.53
5.00
6.52
8.64
22.26
4.25
5.62
12.76
20.04
Explosion
7.70
3.75
17.03
32.03
0.77
1.23
4.10
11.90
0.83
1.16
6.30
8.75
Grid
6.58
2.81
16.40
26.12
0.82
1.11
2.44
6.90
0.81
1.03
1.76
4.81
Implosion
6.21
2.84
16.51
27.93
0.84
1.12
2.55
7.15
0.78
1.09
1.80
4.89
Appendix
Table 15: Rotation sensitivity across test distributions for TSP-20, TSP-50, and TSP-100.
Distribution
TSP-200
TSP-500
TSP-1000
L2C-Insert
LEHD
POMO
AM
L2C-Insert
LEHD
POMO
AM
L2C-Insert
LEHD
POMO
AM
Clustered
1.94
2.38
16.87
96.41
3.03
2.93
20.59
101.45
3.45
3.46
24.60
113.51
Expansion
4.82
7.18
5.66
7.46
24.23
11.62
15.75
9.25
92.33
12.44
14.95
9.93
Explosion
1.46
2.55
6.14
6.22
4.44
6.34
16.15
6.69
21.71
9.71
14.35
6.42
Grid
1.05
1.10
6.00
4.22
1.89
1.56
10.30
4.21
2.65
1.94
9.28
3.72
Implosion
1.67
1.87
6.68
174.96
2.67
2.36
12.24
193.60
3.30
2.64
10.32
269.56
Appendix
Table 16: Rotation sensitivity across test distributions for TSP-200, TSP-500, and TSP-1000.
Own-Trajectory Future
Own-Trajectory Future (Non-NN)
Size
Layer
h=1
h=2
h=3
h=4
h=5
h=6
h=1
h=2
h=3
h=4
h=5
h=6
TSP-50
L5
95.6
86.5
60.5
32.4
22.5
17.2
85.4
70.5
40.2
30.6
19.6
16.0
TSP-50
L6
99.8
84.2
54.1
31.0
21.4
15.8
99.4
67.6
38.6
27.9
18.9
14.8
TSP-100
L5
95.6
86.0
58.1
32.9
22.4
16.7
83.4
68.4
39.4
30.1
19.7
15.2
TSP-100
L6
99.9
82.4
50.4
31.2
20.9
15.5
99.8
65.1
35.5
27.7
19.0
14.3
TSP-500
L5
94.5
77.7
43.6
28.2
20.4
15.4
78.2
56.2
30.3
22.5
17.4
13.7
Appendix
Table 17: Top-1 future-node probe accuracy (%) for LEHD on TSP-50, TSP-100, and TSP-500. Own-Trajectory Future evaluates prediction of LEHD’s own future nodes from its greedy decoding trajectory. Own-Trajectory Future (Non-NN) restricts evaluation to states where LEHD’s greedy next action is not the nearest currently unvisited node.
Figure 6: A sample visualization of node perturbation. (a) Shows the original instance. (b) Shows the perturbed instance.
Figure 7: LEHD ΔG with probability threshold.
Figure 8: POMO ΔG with probability threshold.
α
Norm ratio
Cosine similarity
Relative perturbation
3
1.031±0.002
0.9873±0.0004
0.151±0.002
5
1.060±0.003
0.9676±0.0008
0.250±0.003
10
1.156±0.006
0.8959±0.0022
0.495±0.007
Appendix
Table 18: Representation-space diagnostics for probe-guided counterfactual steering on Uniform TSP-100 across future horizons and decoder layers.
Figure 9: Start-node intervention sensitivity in AM on Uniform TSP-100. (a) Policy-selected start; (b) forced start at node 0, followed by greedy decoding. Previously visited donors are selected by maximum angular separation (red), maximum angle with matched distance (blue), or similar direction with different distance (green). The y-axis shows the mean drop in clean next-action probability after patching.
Table 27
Figure 10: Layer-wise PCA of LEHD node-role representations. Faint points show instance-level representations across 128 Uniform TSP-50 instances, while larger markers indicate their means. Numbered markers denote LEHD’s next six actions under greedy decoding.
Figure 11: Onion-depth structure of POMO tours. Representative Uniform TSP-50, TSP-100, and TSP-200 rollouts illustrate POMO’s repeated oscillation between outer and deeper onion layers. Colored segments highlight example outer-to-deep-to-outer excursions, while node colors indicate normalized onion depth.
Figure 12: Onion-depth structure of AM tours. Selected Uniform TSP-50, TSP-100, and TSP-200 rollouts illustrate outer-to-deep-to-outer excursions in AM. Colored segments highlight example excursions, while node colors indicate normalized onion depth.
Figure 13: Radial route structure of POMO, LEHD, and AM on CVRP. Selected Uniform CVRP-200 and CVRP-500 solutions are shown, with POMO on the left, LEHD in the center, and AM on the right. Each vehicle route is displayed in a distinct color; black stars indicate depot locations, and enlarged circular markers identify the farthest customer from the depot along each route. In these selected examples, radial backtracking is most visually pronounced in POMO, followed by AM, while LEHD exhibits more regular outward-then-inward route structures.
Figure 14: Layer-wise attention heatmaps of the current node during decoding. Each panel illustrates the attention weight distribution assigned by the current node (query) to remaining unvisited nodes (keys) for each decoder layer at a representative decoding step. Red dashed lines denote the nodes actually visited in subsequent steps.
Figure 15: Geometric trajectory properties on CVRP routes. (a) Average onion-layer oscillations across problem scales; values remain low due to short individual route lengths. (b) Step-wise radial distortion along individual routes, showing heightened back-and-forth movement in POMO compared to baselines, with AM exhibiting intermediate distortion at larger scales. (c) Mean current-to-depot angle relative to each route’s first edge, averaged within instances and then across instances, showing POMO’s persistent clockwise progression and a weaker clockwise tendency in AM.
Figure 16: Future-action representations and causal steering on CVRP. (a) Linear probing accuracy across planning horizons for LEHD, POMO, and AM, revealing differences in the accessibility of future-action information from decoder representations. (b) Change in the logit gap under probe-guided steering and control interventions on CVRP-100, measuring the effect of modifying future-node representations on the current decision.
Figure 17: Causal interventions on node representations in CVRP. (a) Probability drop in clean next-node predictions following mean ablation of current versus depot node representations in LEHD. (b) Effect of start/depot-node activation patching under three geometric donor conditions, comparing directional sensitivity in LEHD and POMO.
Angle Range
LEHD
POMO
LCS
Rev. LCS
LCS
Rev. LCS
0∘ – 30∘
0.496
0.123
0.168
0.079
30∘ – 60∘
0.318
0.126
0.108
0.065
60∘ – 90∘
0.221
0.117
0.080
0.064
90∘ – 120∘
0.155
0.107
0.080
0.071
120∘ – 150∘
0.117
0.107
0.104
0.083
Appendix
Table 21: CVRP-500 route rollout-order similarity under depot-node activation patching. Results evaluate maximum-angle donor selection without distance constraints. LCS measures forward-order sequence agreement with clean rollouts, while Rev. LCS measures agreement with reversed clean rollouts.
Layer
Current Node
Depot Node
Random Node
Enc. 1
0.513±0.330
0.514±0.342
0.514±0.327
Dec. 1
0.671±0.251
0.464±0.296
0.279±0.383
Dec. 2
0.792±0.176
0.502±0.279
0.344±0.331
Dec. 3
0.772±0.146
0.684±0.155
0.395±0.298
Dec. 4
0.764±0.135
0.774±0.113
0.401±0.307
Dec. 5
0.715±0.145
0.755±0.135
0.431±0.263
Appendix
Table 22: Layer-wise cross-instance alignment of node representations in LEHD on Uniform CVRP-100. Values denote mean cosine similarity ( ± std) across different problem instances and decoding steps for current, depot, and random customer node representations. Enc. and Dec. denote encoder and decoder layers.
Donor condition
Angular constraint
Distance constraint
Maximum angle without distance constraints
Maximize θd
None
Maximum angle under similar distance
Maximize θd
0.80≤rd≤1.20
Similar angle with different distance
θd≤15∘
rd≤0.70 or rd≥1.30
Appendix
Table 23: Geometric constraints used for donor selection in the targeted start-node intervention.
Setting
Value
Training/validation/test split
70%/15%/15%
Random seed
123
Training epochs
3
Learning rate
10−3
Weight decay
10−4
Gradient clipping norm
1.0
Appendix
Table 24: Training settings for the future-action planning probes.
The primary paradigm in Neural Combinatorial Optimization (NCO) consists of construction methods, where a neural network is trained to sequentially add one solution component at a time until a complete solution is formed. We observe that the typical changes to the state between two steps are small, since usually only the node added to the solution is removed from the state. An efficient model should be able to reuse computation from prior steps. To that end, we propose a recurrent encoder that computes state embeddings based not only on the current state but also on embeddings from the previous state. We show that this recurrent encoder can achieve equivalent or better performance than a non-recurrent encoder even with 3× fewer layers, thus significantly improving latency. We demonstrate our findings on three different problems: the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Orienteering Problem (OP), and integrate the models into a large neighborhood search algorithm to showcase the practical relevance of our findings.
Tim Dernedde, Daniela Thyssens, Lars Schmidt-Thieme
Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim
Neural Combinatorial Optimization (NCO) achieves strong performance, yet its black-box nature remains a key roadblock to deployment and scientific diagnosis. Standard interpretability tools, such as Concept Bottleneck Models (CBMs), are ill-equipped for NCO, whose decisions are dynamic, state-dependent, and lack proper concept vocabulary definition. To close this gap, we introduce Evolving Programmatic Bottlenecks (EPB), to our knowledge, the first framework for interpreting NCO policies by distilling black-box NCO models into human-readable program portfolios. EPB employs an LLM to autonomously evolve a bank of programs, where each program's per-step action distribution serves as the bottleneck. EPB works through an iterative framework: Block I fixes program bank capacity and introduces a hybrid textual-numerical gradient descent scheme that couples numerical gradients for student router updates and textual gradients for LLM-based program revision; Block II dynamically adapts bank capacity via fault-targeted expansion and redundancy pruning. Extensive experiments demonstrate EPB's effectiveness and broad applicability, where the distilled program portfolios largely match original performance. EPB also reveals that NCO behavior shifts across optimization stages and can be approximated as a composition of classic heuristic variants. Our work advances interpretable NCO and establishes EPB as a promising tool for interpreting sequential decision-making models.
Haocheng Duan, Yuxin Guo, Jieyi Bi +4
1Carnegie Mellon University · 2Nanyang Technological University · 3Microsoft Research +1
Constructive neural routing solvers usually score the next action by matching a decoder context to candidate embeddings, leaving deterministic one-step consequences such as travel, waiting, slack, and capacity changes implicit. We propose LINC, a decoder-side candidate decision architecture that computes these consequences explicitly. LINC uses them according to their decision role: candidate-level consequences are scored by a state-conditioned shared linear comparator, while feasible-set summaries modulate the decoder context. This preserves standard global matching while reducing the burden on the hidden state to reconstruct transition arithmetic. The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) serves as the main constrained-routing testbed, and the same interface extends to the Capacitated Vehicle Routing Problem (CVRP) and Traveling Salesman Problem (TSP). Across external benchmarks and no-retraining scale-transfer settings, LINC consistently improves strong neural baselines, with the advantage becoming more pronounced as test size moves further beyond the training scale, especially on constrained routing problems.
Shaofeng Qin, Li Wang
Beijing University of Posts and Telecommunications