Understanding Decision-Making Mechanisms in Neural Routing Solvers

Fatemeh Askari; Mazdak Teymourian; Mohammad Izadi; Mahdieh Soleymani Baghshah

cs.LGSep 28, 2026

Understanding Decision-Making Mechanisms in Neural Routing Solvers

Authors: Fatemeh Askari, Mazdak Teymourian, Mohammad Izadi, Mahdieh Soleymani Baghshah

Organizations: Department of Computer EngineeringSharif University of Technology

Abstract

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.

Panel of Figure 3 — 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.

Panel of Figure 4 — 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 $\alpha=5$ , compared against random-direction and random-horizon baselines. Bars show the mean change in logit gap between the clean top-two actions

Panel of Figure 5 — 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)
Distribution	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)
Distribution	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)
Distribution	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)
Distribution	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)
Distribution	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)
Distribution	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
Distribution	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
Distribution	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
Distribution	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
Distribution	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
Distribution	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
Distribution	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
Distribution	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
Distribution	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.

Panel of Figure 6 — Figure 6: A sample visualization of node perturbation. (a) Shows the original instance. (b) Shows the perturbed instance.

Figure 7: LEHD

\Delta G

with probability threshold.

Figure 8: POMO

\Delta G

with probability threshold.

$\alpha$	Norm ratio	Cosine similarity	Relative perturbation
3	$1.031\pm 0.002$	$0.9873\pm 0.0004$	$0.151\pm 0.002$
5	$\mathbf{1.060\pm 0.003}$	$\mathbf{0.9676\pm 0.0008}$	$\mathbf{0.250\pm 0.003}$
10	$1.156\pm 0.006$	$0.8959\pm 0.0022$	$0.495\pm 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.

Panel of Figure 13 — 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.

Panel of Figure 15 — 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.

Panel of Figure 16 — 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.

Panel of Figure 17 — 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
Angle Range	LCS	Rev. LCS	LCS	Rev. LCS
$0^{\circ}$ – $30^{\circ}$	0.496	0.123	0.168	0.079
$30^{\circ}$ – $60^{\circ}$	0.318	0.126	0.108	0.065
$60^{\circ}$ – $90^{\circ}$	0.221	0.117	0.080	0.064
$90^{\circ}$ – $120^{\circ}$	0.155	0.107	0.080	0.071
$120^{\circ}$ – $150^{\circ}$	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\pm 0.330$	$0.514\pm 0.342$	$\mathbf{0.514}\pm 0.327$
Dec. 1	$\mathbf{0.671}\pm 0.251$	$0.464\pm 0.296$	$0.279\pm 0.383$
Dec. 2	$\mathbf{0.792}\pm 0.176$	$0.502\pm 0.279$	$0.344\pm 0.331$
Dec. 3	$\mathbf{0.772}\pm 0.146$	$0.684\pm 0.155$	$0.395\pm 0.298$
Dec. 4	$0.764\pm 0.135$	$\mathbf{0.774}\pm 0.113$	$0.401\pm 0.307$
Dec. 5	$0.715\pm 0.145$	$\mathbf{0.755}\pm 0.135$	$0.431\pm 0.263$

Appendix

Table 22: Layer-wise cross-instance alignment of node representations in LEHD on Uniform CVRP-100. Values denote mean cosine similarity (

\pm

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 $\theta_{d}$	None
Maximum angle under similar distance	Maximize $\theta_{d}$	$0.80\leq r_{d}\leq 1.20$
Similar angle with different distance	$\theta_{d}\leq 15^{\circ}$	$r_{d}\leq 0.70$ or $r_{d}\geq 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.

Explore similar work

Recurrent State Encoders for Efficient Neural Combinatorial Optimization
Sep 5, 2025Tim Dernedde, Daniela Thyssens, Lars Schmidt-ThiemeNeural Combinatorial Optimization Vehicle Routing Problem
Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim
Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks
Jun 18, 2026Haocheng Duan, Yuxin Guo, Jieyi Bi +4Neural Combinatorial Optimization Concept Bottleneck Models
1Carnegie Mellon University · 2Nanyang Technological University · 3Microsoft Research +1
LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing
May 7, 2026Shaofeng Qin, Li WangVehicle Routing Problem Neural Combinatorial Optimization
Beijing University of Posts and Telecommunications

Sep 5, 2025, cs.LGJ/K move · Enter open · S save

Recurrent State Encoders for Efficient Neural Combinatorial Optimization

Tim Dernedde, Daniela Thyssens, Lars Schmidt-Thieme

Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim

Neural Combinatorial Optimization Vehicle Routing Problem Recurrent State Neural Network Optimization

Open paper AskPDF arXiv

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\times

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.

Abstract

Explore similar work

Recurrent State Encoders for Efficient Neural Combinatorial Optimization

Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing