acceptodds
Under review as a conference paper at ICLR 2027

Understanding Decision-Making Mechanisms in Neural Routing Solvers

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 supplementary material.

Primary area:
interpretability and explainable AI
Keywords:
Neural Combinatorial Optimization, Mechanistic Interpretability, Interpretability, Planning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Lr1JOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This work investigates the internal decision-making mechanisms of three representative autoregressive NCO solvers for routing problems: AM and POMO (HELD) and LEHD. The authors build a multi-level interpretability framework combining geometric trajectory analysis, linear representation probing, and causal activation interventions. The key findings are: 1) HELD rely on a rigid geometric scanning strategy with systematic layer-wise oscillations and fixed rotational bias; 2) LEHD adopts a two-component navigation strategy: local multi-step look-ahead planning and global directional guidance from the start node; 3) LEHD organizes node representations into role-specific canonical latent spaces across instances.

Critical strengths
  1. This work moves beyond prior purely correlational probing studies and introduces causal activation interventions to the mechanistic analysis of NCO solvers. The tiered pipeline establishes a rigorous methodological template for the field.
  2. The study systematically contrasts two dominant encoder-decoder paradigms and links architectural capacity allocation to qualitatively distinct solution strategies.
  3. Core findings are replicated across both TSP and CVRP.
Critical weaknesses
  1. The core comparison between HELD models (Trained via RL) and LEHD (trained via SL) is fundamentally confounded. There is no way to disentangle whether the observed differences in strategy rigidity and look-ahead capability stem from encoder-decoder allocation or from the training paradigm.
  2. The work remains entirely descriptive and does not translate its mechanistic findings into concrete design improvements, nor does it include ablation or validation experiments demonstrating that leveraging these insights yields measurable performance gains. 
  3. The claim that start/depot nodes provide global angular guidance is well supported in TSP, but evidence is weak in CVRP. As shown in the reported results, depot patching produces very low LCS values across all angle ranges, as capacity constraints dominate route partitioning.
  4. The high cross-instance similarity of current-node representations is interpreted as a canonical functional reference frame, but the analysis does not control for inherent geometric similarities of current nodes (e.g., local neighborhood statistics). It remains ambiguous whether the alignment reflects role-specific encoding or simply shared local geometric properties.
  5. The probe-guided steering experiment only performs activation amplification along the probe direction, with no corresponding inhibition/ablation condition to verify causal necessity. Additionally, only joint steering across horizons 2–5 is tested, without single-horizon ablations.
Questions for authors

See weaknesses.

10 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/3): Experimenting on Different Training Paradigms and Design Improvements (W1, W2)

Dear Reviewer Lr1J,

Thank you for your detailed feedback. We appreciate that you found our experimental framework to be a rigorous methodological template for this field, as well as your recognition of the breadth of our experiments across different architectures and routing problems. Below, we address each of your concerns. We have also uploaded the revised manuscript incorporating these additions, along with references to the updated sections:

W1: Thank you for pointing this out. Since both the training paradigm and the encoder-decoder configuration can influence the final decision-making mechanism, the most direct way to disentangle their respective roles is to evaluate cross-combinations of architectures and training paradigms—specifically, POMO trained with supervised learning (POMO-SL) and a light-encoder, heavy-decoder architecture trained outside standard SL. As explained in detail in our response to W2 and Q1 of Reviewer 3J3R, due to the substantial computational cost of training LEHD-RL to full convergence within the rebuttal window, we evaluated POMO-SL alongside SIL-SIT [1], a heavy-decoder model trained via self-improved reconstruction. Across all of our mechanistic evaluations—future-action linear probes (Figure 4b), start-node patching probability drop (Figure 5b), LCS and Rev. LCS rollout reversal (Table 1), and onion-layer oscillations (Figure 3a)—POMO-SL behaves just like standard POMO (except that its unidirectional angular bias is eliminated), whereas SIL-SIT behaves just like LEHD. This demonstrates that multi-step look-ahead, start-node global directional guidance, and layer-oscillation behavior stem from the encoder-decoder architectural allocation rather than the training paradigm, while only the rotational sweeping bias stems from RL training. We are also running LEHD-RL and are committed to including it in the final manuscript. For the full quantitative tables across all benchmarks, please see our response to W2 and Q1 of Reviewer 3J3R; the results for POMO-SL and SIL-SIT are presented in Section 6 and Appendix C of the revised manuscript, respectively.

W2: As discussed in Section 7 and Section 8 of our revised manuscript, our findings directly inform three concrete avenues for performance and efficiency improvements:

  1. First, we showed that training on clustered data rather than uniform data significantly reduces the optimality gap of both POMO and LEHD across distributions and problem scales (Section 4.2 and Appendix D.1, Tables 5–10).
  2. Second, our analysis of encoder-decoder configurations, combined with our new results across training paradigms, provides actionable insights into the decision-making characteristics of neural solvers (showing that light-encoder, heavy-decoder architectures enable multi-step local adaptivity and global anchor guidance, whereas RL training induces a global angular bias in HELD tours).
  3. Third, to demonstrate a direct practical application of our look-ahead finding for LEHD, we monitored the Layer 4 linear probe softmax confidence for h=2 (two steps ahead) during greedy tour construction (Section 7, Table 3). Whenever the h=2 probe confidence exceeds a threshold , we simultaneously select both the immediate next node and the two-step-ahead node, skipping a full heavy-decoder forward pass. As shown in the table below, high thresholds ({0.98,0.99}) eliminate 20–30% of decoder forward passes across TSP instances while maintaining solution quality within 0.05–0.12% of standard greedy decoding.

Probe-Guided Decoding Acceleration of LEHD on Uniform TSP (Section 7, Table 3)

Gap: Optimality gap (%); Steps: Mean decoder forward passes (percentage reduction relative to baseline).

MethodN=20 GapN=20 StepsN=50 GapN=50 StepsN=100 GapN=100 Steps
LEHD Greedy1.1519.000.4949.000.5699.00
Probe (τ=0.99)1.1616.04 (−15.6%)0.5436.51 (−25.5%)0.6173.23 (−26.0%)
Probe (τ=0.98)1.1715.00 (−21.1%)0.5934.44 (−29.7%)0.6869.24 (−30.1%)

References

[1] Luo et al., "Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems," ICLR 2025.

AuthorsOpenReview ↗

Rebuttal (Part 2/3): Capacity Constraints and Cross-Instance Representation Alignment (W3, W4)

W3: Thank you for your thoughtful observation. As you noted and as we discussed in Appendix G.3, because CVRP tours are constrained by vehicle capacity limits, these constraints affect how the intervention alters the route's overall direction and thus lower the LCS values. Similarly, because each individual CVRP route consists of far fewer nodes than a full TSP tour, this also lowers the Reverse LCS values. To isolate the effect of capacity constraints, we ran this experiment on CVRP-500 instances with unconstrained vehicle capacities (1.05 ×∑idi\times \sum_i d_i) so that the model is not forced to return to the depot multiple times. The results are shown below (and in Table 27 of the revised manuscript). We observe that under unconstrained capacity, forward LCS increases across all angle ranges, and as the donor angle range increases, Rev. LCS rises consistently from 0.144 to 0.321, mirroring the behavior observed in TSP. Interestingly, even when the vehicle capacity is large enough that a single route is optimal, LEHD still returns to the depot an average of 2.58 times (compared to 20.44 under the original capacity), showing how the learned policy interacts with route partitioning.

CVRP-500 Route Rollout-Order Similarity Under Depot-Node Patching (Appendix G.3, Table 27)

C: Original capacity; Unconstr.: Unconstrained capacity. LCS: Forward-order similarity; Rev.: Reverse-order similarity.

AngleLEHD-CLEHD-C Rev.LEHD-ULEHD-U Rev.POMO-CPOMO-C Rev.
0°–30°0.4960.1230.5930.1440.1680.079
30°–60°0.3180.1260.4310.2420.1080.065
60°–90°0.2210.1170.3650.2660.0800.064
90°–120°0.1550.1070.3000.2810.0800.071
120°–150°0.1170.1070.2670.2940.1040.083
150°–180°0.1150.1110.2930.3210.1510.118

W4: Please note that in the average cross-instance cosine similarity reported in Table 2 (and Table 28 for CVRP), for each layer we compare representations across independent random problem instances at the same decoding step t and then again averaged across these decoding steps, so the compared current nodes occupy arbitrary coordinates and varied local neighborhoods across instances. Furthermore, the encoder layer (Enc. 1 in Table 2), which processes pure instance and local neighborhood geometry prior to role-conditioned decoding, serves as a direct control: in Enc. 1, the cross-instance similarity of the current node (0.194) is virtually identical to that of random unvisited nodes (0.193) and the start node (0.188), whereas the strong alignment of the current node (0.767–0.886) emerges only in the deeper decoder layers (Dec. 2–5), confirming that the alignment reflects role-specific encoding in the decoder rather than shared local geometric properties.

AuthorsOpenReview ↗

Rebuttal (Part 3/3): Causal Steering Controls and Horizon Ablations (W5)

W5: Per your suggestion, we have added an inhibition condition for the alternative branch (using a negative =-5 for probe-guided steering). As shown below, the logit gap shift (ΔGt\Delta G_t) becomes negative, weakening the preference for the alternative branch as expected. We also steered the main (greedy) branch using both positive and negative (toward and away from the probe direction) and observed the exact opposite trend compared to the alternative branch: when we steer the main branch toward the probe direction (>0), ΔGt\Delta G_t becomes negative (the main branch becomes even more favorable), whereas when we steer it away from the probe direction (<0), ΔGt\Delta G_t becomes positive (shifting preference toward the alternative branch), verifying causal necessity.

We have also conducted single-horizon ablations (h{2,3,4,5} individually), observing the same directional response across both branches and finding that the steering effect is strongest at H2 and gradually diminishes at further horizons (H3,H4,H5). All of these results, along with representation-space off-manifold diagnostics, are presented in Appendix E.3 (Tables 20–24) of the revised manuscript.

Joint H2–H5 Main-Branch Steering on Uniform TSP-100 (Table 22)

HorizonProbe-GuidedRandom DirectionRandom Horizon
H2–H5-5+0.326 ± 0.047-0.046 ± 0.020-0.015 ± 0.017
H2–H5+5-0.396 ± 0.054+0.035 ± 0.019+0.057 ± 0.018

Joint H2–H5 Alternative-Branch Steering on Uniform TSP-100 (Table 24)

HorizonProbe-GuidedRandom DirectionRandom Horizon
H2–H5-5-0.191 ± 0.042+0.045 ± 0.024+0.014 ± 0.022
H2–H5+5+0.430 ± 0.064+0.025 ± 0.028-0.001 ± 0.029

Single-Horizon Main-Branch Steering on Uniform TSP-100 (Table 21)

HorizonProbe-GuidedRandom DirectionRandom Horizon
H2-5+0.205 ± 0.033-0.020 ± 0.013+0.010 ± 0.006
H2+5-0.273 ± 0.047+0.032 ± 0.015+0.017 ± 0.009
H3-5+0.079 ± 0.017-0.012 ± 0.008+0.004 ± 0.006
H3+5-0.108 ± 0.018+0.003 ± 0.008+0.017 ± 0.009
H4-5+0.040 ± 0.011-0.003 ± 0.007-0.002 ± 0.006
H4+5-0.079 ± 0.014-0.014 ± 0.007+0.020 ± 0.009
H5-5-0.025 ± 0.011-0.006 ± 0.011+0.002 ± 0.007
H5+50.000 ± 0.013+0.001 ± 0.008+0.030 ± 0.010

Single-Horizon Alternative-Branch Steering on Uniform TSP-100 (Table 23)

HorizonProbe-GuidedRandom DirectionRandom Horizon
H2-5-0.124 ± 0.026+0.043 ± 0.014+0.008 ± 0.013
H2+5+0.299 ± 0.049-0.034 ± 0.021+0.006 ± 0.012
H3-5-0.068 ± 0.017-0.009 ± 0.010+0.014 ± 0.012
H3+5+0.094 ± 0.018+0.015 ± 0.010+0.017 ± 0.011
H4-5-0.012 ± 0.013-0.008 ± 0.008+0.022 ± 0.011
H4+5+0.059 ± 0.016+0.032 ± 0.008+0.012 ± 0.011
H5-5+0.031 ± 0.014+0.015 ± 0.010-0.008 ± 0.012
H5+5-0.011 ± 0.018+0.007 ± 0.010-0.002 ± 0.010
Reviewer_3J3ROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the decision-making mechanisms of three autoregressive neural routing solvers: AM, POMO, and LEHD. Through geometric trajectory analysis, the authors identify relatively rigid geometric patterns in AM and POMO, while linear probing suggests that LEHD's representations contain information about multiple future actions. Causal interventions further support the role of future-node representations in immediate decisions and suggest that LEHD combines local look-ahead with global directional guidance. The findings are validated on TSP and CVRP across different problem sizes and spatial distributions, using behavioral analysis, representation probing, and causal interventions to characterize the models' decision-making behaviors.

Critical strengths
  1. This multi-level analysis provides useful empirical evidence about how different solvers construct solutions and offers a valuable methodological starting point for interpretability research in neural combinatorial optimization.

  2. The linear probing results reveal that LEHD's hidden representations contain information about multiple future actions. This provides an interesting perspective on how neural routing solvers may use information beyond the immediate next decision.

  3. The experiments cover different problem sizes, spatial distributions, and both TSP and CVRP. The findings provide useful insights into the relationship between learned geometric biases and generalization performance.

Critical weaknesses
  1. Potential overinterpretation of observed behaviors. The geometric patterns observed in AM/POMO do not necessarily imply that these models follow rigid heuristics. Similarly, LEHD's future-action predictability and sensitivity to future-node interventions do not uniquely establish an MPC-like planning mechanism. Alternative explanations, such as implicit geometric scoring, remain plausible.

  2. AM/POMO and LEHD differ in training paradigms and other design choices, not just encoder/decoder allocation. Without controlled ablations, attributing the observed behavioral differences primarily to architectural differences is not fully justified.

  3. The mechanistic experiments focus on autoregressive append-based solvers, while L2C-Insert is used mainly for behavioral comparison. It remains unclear whether the proposed explanations extend to insertion-based, iterative-improvement, or non-autoregressive approaches.

Questions for authors
  1. Can the authors provide controlled experiments that vary encoder/decoder depth while keeping the training paradigm fixed? This would help establish whether the observed differences are truly attributable to architectural allocation.

  2. How can the authors distinguish LEHD's proposed multi-step planning mechanism from implicit geometric scoring or dependencies among candidate nodes? Could controlled experiments isolate future-path quality from local geometric features?

  3. Recent neural routing solvers, including diffusion-based methods, have demonstrated strong performance. Can the proposed interpretability framework be extended to these approaches? In particular, would similar decision-making mechanisms and geometric patterns emerge, or are the reported findings specific to autoregressive solvers?

9 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/4): Clarifying Geometric Rigidity and Testing Look-Ahead Mechanisms (W1/Q2)

Dear Reviewer 3J3R,

Thank you for your thorough and insightful review. We are glad that you found our multi-level analysis valuable and recognized the potential of our work to motivate further interpretability research in neural combinatorial optimization. Below, we address your questions and concerns in detail. We have also uploaded the revised manuscript incorporating these additions, along with references to the updated sections:

W1 and Q2: We apologize if any of our terminology was ambiguous. By describing AM and POMO as "rigid," we meant that although optimal solutions across different problem instances have diverse geometric structures—such that averaging the angular progression over many instances cancels out to zero, as seen in both Concorde and LEHD—AM and POMO exhibit a persistent, monotonic angular bias regardless of the instance. This indicates that the specific geometric structure of an instance has less influence on the macro-level trajectory of AM and POMO than on models such as LEHD. Furthermore, AM and POMO oscillate across onion layers substantially more frequently than optimal Concorde tours. We have clarified this precise definition of rigidity (Section 4.1) and softened our analogy to MPC in the revised manuscript to avoid any overinterpretation.

Regarding LEHD's look-ahead mechanism, thank you for raising this important question. We fully agree that in geometric routing problems, candidate nodes have spatial dependencies, making it essential to disentangle multi-step trajectory evaluation from immediate local geometric scoring. Since any causal experiment alters some aspect of the problem (either the internal embeddings in Section 3.3 or the node coordinates in Appendix E.2), and tours depend on instance geometry, we designed two complementary controls to isolate multi-step look-ahead from naive local geometric scoring:

  1. Isolating Future-Path Quality While Holding Immediate Candidate Geometry Fixed (Appendix E.2 & Section 3.3): In our behavioral-causal node perturbation experiment (Appendix E.2, Figures 9–11), the coordinates of the current node and both immediate candidate actions (a1 and a1') are held completely fixed—so all immediate local geometric features of a1 and a1' remain unchanged—while we only perturb the coordinates of subsequent future nodes (a2′,…,a5′a_2', \dots, a_5') along the a1' branch to shorten (Toward) or lengthen (Away) the future continuation path. Shortening the future path a2′,…,a5′a_2', \dots, a_5' strongly shifts LEHD's immediate logit preference toward a1', whereas lengthening it shifts preference away. Similarly, in our activation steering experiment (Section 3.3), we only modify the representations of future nodes (h{2,3,4,5}) while leaving the representations of the immediate candidates a1 and a1' untouched.
  2. Controlling for Nearest-Neighbor Heuristics (Appendix E.1): As a sanity check to rule out the possibility that LEHD's future-action probe simply predicts nearest-neighbor transitions, in Appendix E.1 (Table 19) we restricted the probe evaluation strictly to decoding states where LEHD does not select the nearest neighbor to the current node. Even under this restriction, multi-step probe accuracy remains substantial across horizons, ruling out a naive local-proximity explanation for the probe's performance.
AuthorsOpenReview ↗

Rebuttal (Part 2/4): Experimenting on Different Training Paradigms (W2/Q1)

W2 and Q1: Thank you for pointing this out. To directly evaluate the role of the training paradigm vs. encoder-decoder allocation on the learned decision-making mechanisms, we contacted the authors of the LEHD paper, who kindly shared their checkpoints for the reinforcement learning version of LEHD (LEHD-RL) and the supervised learning version of POMO (POMO-SL). As the LEHD authors noted in their original paper, because training LEHD-RL is computationally expensive due to the heavy decoder's memory footprint, their checkpoint was trained for significantly fewer iterations than the SL version and had not fully converged, making it unreliable for direct mechanistic evaluation. Training LEHD-RL to full convergence on our current GPU hardware takes approximately two weeks, which extends beyond the rebuttal period; however, we are committed to including the converged LEHD-RL results in the final manuscript.

As an immediate, reliable alternative and to broaden our model coverage, we evaluated POMO-SL (Heavy-Encoder, Light-Decoder trained with Supervised Learning) alongside Self-Improved Training (SIL-SIT) [1] (a Heavy-Decoder architecture similar to LEHD, but trained via iterative self-reconstruction rather than standard SL) across our full suite of geometric, probing, and causal patching experiments:

  • POMO-SL vs. POMO: In POMO-SL, the future-action linear probe accuracies (Figure 4b), the start-node patching next-node probability drop (Figure 5b), the rollout-order LCS and Rev. LCS (Table 1), and the high onion-layer oscillation count (Figure 3a) all closely match standard RL-trained POMO. The only difference is that the global clockwise/counter-clockwise angular bias (Figure 3c) is eliminated in POMO-SL.
  • SIL-SIT vs. LEHD: Conversely, across all evaluations—lack of angular bias, low onion-layer oscillation count, high linear probe accuracy across future horizons, strong directional sensitivity in start-node patching probability drop, and decreasing LCS / increasing Rev. LCS across angle ranges—SIL-SIT behaves just like LEHD. The results for POMO-SL are presented in Section 6 of the revised paper, and the results for SIL-SIT are presented in Appendix C.

These results cleanly disentangle the two factors: the core decision-making mechanisms—multi-step look-ahead planning, global directional guidance from the start node, and low onion-layer oscillation—are governed by the Encoder-Decoder architectural allocation (LEHD vs. HELD), whereas the unidirectional angular bias is a byproduct of the RL training paradigm.

Mean Onion-Layer Oscillation Count (± STD) — Uniform TSP

ModelN=200N=500N=1000
LEHD4.98 ± 1.374.53 ± 1.455.86 ± 1.58
POMO5.48 ± 1.376.70 ± 1.5612.77 ± 2.51
POMO-SL5.56 ± 1.406.49 ± 1.6310.95 ± 2.03
SIL-SIT5.15 ± 1.394.85 ± 1.456.63 ± 1.93
Concorde (Optimal)5.00 ± 1.364.65 ± 1.396.16 ± 1.57

Mean Unwrapped Angle (°) — Uniform TSP-500

Model1–100101–200201–300301–400401–500
LEHD-0.741.241.08-0.32-1.43
POMO-10.44-28.64-54.79-90.18-135.81
POMO-SL3.715.6410.089.968.96
SIL-SIT-3.92-4.32-1.621.617.82
Concorde (Optimal)0.700.951.381.330.22

Future-Node Probe Accuracy (%) — TSP-50

ModelH1H2H3H4H5H6
POMO99.7035.6623.5116.7013.3011.62
POMO-SL99.1616.1713.1410.108.587.98
LEHD L595.6386.5260.4732.4122.5117.24
LEHD L699.8184.1654.0931.0121.4515.77
SIL-SIT L591.8765.5337.5323.0015.5611.19
SIL-SIT L699.0064.4031.9321.1313.6310.74

Future-Node Probe Accuracy (%) — TSP-100

ModelH1H2H3H4H5H6
POMO99.8720.9916.7114.4412.3310.33
POMO-SL99.5310.178.988.237.326.53
LEHD L595.5685.9658.0532.9122.3816.68
LEHD L699.9582.3750.4231.1620.8815.47
SIL-SIT L594.2378.4750.3727.8718.3515.65
SIL-SIT L699.7076.9043.1023.6718.1814.88

Future-Node Probe Accuracy (%) — TSP-500

ModelH1H2H3H4H5H6
POMO99.428.085.164.454.113.86
POMO-SL99.275.493.563.062.932.72
LEHD L594.5377.7143.5828.2020.4215.41
LEHD L699.9575.9839.9724.9817.9013.82
SIL-SIT L593.7583.9260.0139.3524.4619.66
SIL-SIT L699.8083.8552.5531.8020.9017.86

References

[1] Luo et al., "Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems," ICLR 2025.

AuthorsOpenReview ↗

Rebuttal (Part 3/4): Experimenting on Different Training Paradigms (W2/Q1 Continued)

Maximum Angle Without Distance Constraints — Mean Next-Node Probability Drop (TSP-100)

Model20–3940–5960–7980–99
LEHD0.21480.24300.29920.3445
POMO0.01830.01550.01250.0110
POMO-SL0.04380.03710.02950.0375
SIL-SIT0.17310.19260.20790.1997

Maximum Angle Under Similar Distance — Mean Next-Node Probability Drop (TSP-100)

Model20–3940–5960–7980–99
LEHD0.05600.06590.10630.2226
POMO0.00660.00580.00730.0093
POMO-SL0.00660.00870.01280.0253
SIL-SIT0.04300.06410.07980.1252

Similar Angle With Different Distance — Mean Next-Node Probability Drop (TSP-100)

Model20–3940–5960–7980–99
LEHD0.06130.04270.02590.0195
POMO0.01130.01080.00890.0072
POMO-SL0.02180.01410.01060.0129
SIL-SIT0.07910.05140.03920.0513

Start-Node Activation Patching — Rollout-Order Similarity (TSP-100)

LCS: Forward-order similarity; Rev.: Reverse-order similarity.

AngleLEHDLEHD Rev.POMOPOMO Rev.SIL-SITSIL-SIT Rev.POMO-SLPOMO-SL Rev.
0°–30°0.7690.1470.9630.0300.6890.1960.7860.129
30°–60°0.6840.2260.9630.0330.6660.2240.7720.152
60°–90°0.6120.3020.9650.0360.6350.2730.8120.142
90°–120°0.5160.3980.9660.0390.6170.3110.8070.161
120°–150°0.4890.4280.9630.0420.5600.3680.7930.177
150°–180°0.3910.5440.9630.0520.5690.4230.7860.234
Reviewer_inWXOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper explores the internal mechanisms of neural combinatorial optimization. It empirically founds that the direction of constructing route is differ from method between AM and POMO. LEHD traverse differently depending on navigation.

Critical strengths

The problem setting is convinced with considering the trend that there emerge many NCO method but few works consider its internal behavior.

Steering of NCO has not well explored and the result that marginal gap compared random direction is interesting. It can lead to consider kind of test-time scaling of NCO.

Critical weaknesses

It is not clear that the behavior can be consistently observed; for example, AM sweeps nodes with anti-clockwise direction.

It is not sure the tendency of each method exploration can consistently observed by different distribution of nodes.

It seems that the discussion about AM and POMO and discussion about LEHD separately. Writing quality can be improved to connect among them.

Questions for authors

Are behaviors that AM searches for anti-clockwise direction and POMO for clock-wise direction across different seeds?

With earlier training steps, are behaviors of POMO and AM different from training with sufficient steps?

6 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/3): Robustness Across Random Seeds and Node Distributions (W1/Q1, W2)

Dear Reviewer inWX,

Thank you for your valuable review and for highlighting the connection between our steering results and test-time scaling in NCO. Below, we address the questions and experiments you raised. We have also uploaded the revised manuscript incorporating these additions, along with direct references to the updated sections and figures:

W1 and Q1: Thank you for this insightful question. Because Euclidean TSP and CVRP are reflection-symmetric (meaning clockwise and counter-clockwise tours have identical costs) and the Transformer architectures in AM and POMO have no innate chiral bias, neither model is inherently restricted to a single fixed rotational direction. Following your suggestion, we trained these models with two additional random seeds and observed that the same monotonic unidirectional angular sweep is present across all seeds (consistent with the sweeping behavior reported in the paper), while the specific direction (clockwise vs. counter-clockwise) is determined by spontaneous symmetry breaking during training. For example, our first seed of POMO sweeps clockwise while the second seed sweeps counter-clockwise, and vice versa for AM (which also explains why our CVRP checkpoint for AM in Figure 23c swept clockwise). These multi-seed results are presented in Appendix E.6 (Figure 16) of the revised paper.

Below is the numerical breakdown of the mean unwrapped angular progression (°) across decoding step intervals on Uniform TSP-500 for each seed:

ModelSeed1–100101–200201–300301–400401–500
AMPaper34.4574.51105.20109.99150.24
AMSeed 42-74.45-95.66-113.82-124.53-147.30
AMSeed 123-22.66-62.91-89.72-101.46-143.27
POMOPaper-10.44-28.64-54.79-90.18-135.81
POMOSeed 422.5628.9762.7097.01136.67
POMOSeed 123-12.28-41.15-74.13-109.19-148.74

W2: Per your suggestion, we measured the oscillation count and angular progression for all models across all seven node distributions from Figure 2. As presented below, the angular progression for all models remains consistent with their counterparts in Figure 3c of the manuscript. Similarly, the oscillation count behaves consistently with Figure 3a across five of the seven distributions, with the exception of the Expansion and Explosion distributions (please see Figures 1k and 1m of [1] for visual examples). This occurs because Explosion is hollow in the middle and Expansion compresses nodes into thin linear corridors; because both distributions lack dense interior onion layers, deep radial oscillations do not arise during tour completion. Notably, this also explains why Expansion and Explosion are the exact two distributions where AM and POMO exhibit near-zero convex-hull violations in Figure 2b and Table 7. The full results are presented in Appendix E.6 (Figures 14 and 15) of the revised paper.

Mean Onion-Layer Oscillation Count (± STD) — TSP-200

DistributionAMPOMOLEHDL2C-InsertConcorde
Uniform6.38 ± 1.455.48 ± 1.374.98 ± 1.375.09 ± 1.395.00 ± 1.36
Clustered6.66 ± 1.815.00 ± 1.334.40 ± 1.294.29 ± 1.304.26 ± 1.29
Expansion3.05 ± 0.223.12 ± 0.343.08 ± 0.303.13 ± 0.353.16 ± 0.40
Explosion3.75 ± 0.813.78 ± 0.823.78 ± 0.823.78 ± 0.823.78 ± 0.81
Grid6.90 ± 1.555.71 ± 1.354.75 ± 1.404.97 ± 1.384.81 ± 1.39
Implosion7.55 ± 1.605.52 ± 1.384.99 ± 1.395.03 ± 1.384.96 ± 1.39
Mixed3.90 ± 1.333.52 ± 1.172.94 ± 1.223.00 ± 1.192.93 ± 1.20

Mean Onion-Layer Oscillation Count (± STD) — TSP-500

DistributionAMPOMOLEHDL2C-InsertConcorde
Uniform6.90 ± 1.856.70 ± 1.564.53 ± 1.454.78 ± 1.434.65 ± 1.39
Clustered8.47 ± 2.276.59 ± 1.634.57 ± 1.304.42 ± 1.324.24 ± 1.29
Expansion3.00 ± 0.053.08 ± 0.283.01 ± 0.143.06 ± 0.233.09 ± 0.28
Explosion3.70 ± 0.773.66 ± 0.743.62 ± 0.753.61 ± 0.733.64 ± 0.74
Grid8.06 ± 2.098.79 ± 1.994.73 ± 1.565.09 ± 1.544.93 ± 1.49
Implosion10.14 ± 1.856.70 ± 1.584.78 ± 1.484.85 ± 1.454.63 ± 1.39
Mixed3.72 ± 1.564.80 ± 1.402.97 ± 1.252.98 ± 1.262.94 ± 1.22

References

[1] Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation, NeurIPS 2022

AuthorsOpenReview ↗

Rebuttal (Part 2/3): Robustness Across Node Distributions (W2 Continued)

Mean Onion-Layer Oscillation Count (± STD) — TSP-1000

DistributionAMPOMOLEHDL2C-InsertConcorde
Uniform13.15 ± 2.7512.77 ± 2.515.86 ± 1.586.25 ± 1.576.16 ± 1.57
Clustered13.90 ± 4.2310.28 ± 2.385.93 ± 1.715.70 ± 1.635.12 ± 1.53
Expansion3.00 ± 0.003.18 ± 0.413.06 ± 0.423.05 ± 0.263.08 ± 0.27
Explosion4.06 ± 0.913.89 ± 0.914.09 ± 0.954.23 ± 1.003.96 ± 0.89
Grid17.39 ± 2.6216.06 ± 3.146.01 ± 1.886.69 ± 1.696.70 ± 1.59
Implosion18.18 ± 2.2012.34 ± 2.346.58 ± 1.836.55 ± 1.886.33 ± 1.49
Mixed5.51 ± 2.107.48 ± 2.043.67 ± 1.283.53 ± 1.453.69 ± 1.22

Mean Unwrapped Angle (°) — Uniform, TSP-500

Model1–100101–200201–300301–400401–500
AM34.4574.51105.20109.99150.24
POMO-10.44-28.64-54.79-90.18-135.81
LEHD-0.741.241.08-0.32-1.43
L2C-Insert-1.39-2.28-3.39-4.16-4.61
Concorde (Optimal)0.700.951.381.330.22
POMO (Cluster-Trained)3.01-9.96-43.72-78.77-119.50

Mean Unwrapped Angle (°) — Clustered, TSP-500

Model1–100101–200201–300301–400401–500
AM21.6447.5263.7081.68107.12
POMO-0.49-11.81-36.10-70.73-108.39
LEHD3.346.767.958.998.70
L2C-Insert-0.391.362.462.541.78
Concorde (Optimal)-0.270.130.170.631.33
POMO (Cluster-Trained)4.59-19.51-53.91-89.12-125.57

Mean Unwrapped Angle (°) — Expansion, TSP-500

Model1–100101–200201–300301–400401–500
AM31.6980.13112.39129.61169.90
POMO-8.30-30.75-60.41-99.32-147.08
LEHD1.41-3.85-8.05-9.26-12.22
L2C-Insert-0.45-2.22-1.83-1.43-4.12
POMO (Cluster-Trained)5.29-13.85-47.47-82.93-120.72

Mean Unwrapped Angle (°) — Explosion, TSP-500

Model1–100101–200201–300301–400401–500
AM35.4180.32110.30134.82170.27
POMO-12.95-32.31-63.78-103.17-149.63
LEHD7.042.97-0.44-2.53-4.93
L2C-Insert-1.71-3.47-4.42-5.75-6.81
POMO (Cluster-Trained)3.49-17.75-53.51-89.52-126.16

Mean Unwrapped Angle (°) — Grid, TSP-500

Model1–100101–200201–300301–400401–500
AM37.8976.07107.23110.32150.00
POMO-5.09-14.27-30.79-67.09-116.05
LEHD5.6210.1112.3311.466.99
L2C-Insert0.571.991.640.50-1.09
Concorde (Optimal)1.292.181.891.100.75
POMO (Cluster-Trained)13.195.58-27.30-61.79-103.67

Mean Unwrapped Angle (°) — Implosion, TSP-500

Model1–100101–200201–300301–400401–500
AM22.0560.7182.16101.20134.42
POMO-11.93-30.08-56.98-92.82-137.56
LEHD1.122.663.031.55-1.97
L2C-Insert1.231.251.581.35-1.02
Concorde (Optimal)3.173.944.104.713.30
POMO (Cluster-Trained)0.22-16.68-50.27-85.20-125.19

Mean Unwrapped Angle (°) — Mixed, TSP-500

Model1–100101–200201–300301–400401–500
AM40.8875.8298.81105.10136.95
POMO-11.11-24.64-46.32-80.92-124.88
LEHD6.089.059.198.978.49
L2C-Insert2.435.999.1010.278.87
Concorde (Optimal)1.091.211.912.783.14
POMO (Cluster-Trained)1.77-13.08-44.25-79.27-117.63
AuthorsOpenReview ↗

Rebuttal (Part 3/3): Early Training Stages (Q2, W3)

Q2: Thank you for proposing this interesting experiment. We compared the behaviors of AM and POMO across different stages of training, as presented below. We observe that the oscillatory behavior is already present in the earlier training stages (stabilizing after the initial epochs in AM and remaining consistent throughout training in POMO), while the unidirectional angular bias emerges rapidly in AM and becomes progressively more pronounced in POMO as training advances. The results are presented in Appendix E.6 (Figure 17) of the revised paper.

AM — Mean Onion-Layer Oscillation Count (± STD) Across Training, Seed 42, Uniform TSP-500

EpochMean Oscillation Count (± STD)
012.43 ± 1.88
109.25 ± 1.93
207.74 ± 1.80
307.97 ± 1.81
407.76 ± 1.71
507.86 ± 1.67
606.98 ± 1.79
708.82 ± 1.74
807.91 ± 1.78
907.36 ± 1.73
997.72 ± 1.69

POMO — Mean Onion-Layer Oscillation Count (± STD) Across Training, Seed 42, Uniform TSP-500

EpochMean Oscillation Count (± STD)
1006.44 ± 1.61
2006.67 ± 1.66
3006.92 ± 1.61
4006.77 ± 1.61
5006.94 ± 1.53

AM — Mean Unwrapped Angle (°) Across Training, Seed 42, Uniform TSP-500

Epoch1–100101–200201–300301–400401–500
0-42.30-69.94-99.46-121.34-150.82
10-79.80-104.08-129.41-134.84-165.20
20-58.91-80.54-98.53-107.89-132.17
30-82.87-105.69-127.69-134.02-159.70
40-74.95-92.59-116.29-123.20-149.77
50-92.23-117.26-142.92-153.11-181.10
60-73.61-93.28-116.43-121.21-147.16
70-91.03-116.68-132.89-147.29-170.61
80-86.84-113.17-133.74-142.33-172.17
90-86.79-112.50-132.96-141.57-167.11
99-74.45-95.66-113.82-124.53-147.30

POMO — Mean Unwrapped Angle (°) Across Training, Seed 42, Uniform TSP-500

Epoch1–100101–200201–300301–400401–500
1000.07-21.22-41.41-2.5350.95
2001.4534.4665.5897.11135.91
3007.5238.3468.75103.32143.28
4004.3633.1867.39100.14139.36
5002.5628.9762.7097.01136.67

W3: We separated the sections discussing AM and POMO (Section 4) and LEHD (Section 5) because AM and POMO share a heavy-encoder, light-decoder (HELD) architecture and behave much more similarly to each other than to LEHD. We evaluated each experiment across both model families, though certain analyses naturally highlighted more distinctive characteristics for specific models (such as angular progression and oscillation count for AM and POMO, and the future-action probing and steering experiments for LEHD). In the revised manuscript, we have clarified this unified comparative structure in Section 1 and added a bridging comparison between Sections 4 and 5 to more clearly highlight the connections between these models.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.