Neural routing solvers use different ways to decide next steps
Understanding Decision-Making Mechanisms in Neural Routing Solvers
Machine LearningArtificial Intelligence
Summary
Solving routing problems like delivering packages or traveling sales routes involves making many choices step-by-step. This paper looks inside three types of neural network models that build these routes to understand how they make these choices. Some models follow simple, repeating patterns, while another thinks ahead about many future steps. They also differ in how they use information about the current location and starting point to guide their decisions. These insights help explain how different neural solvers work internally when planning routes.
What this means in practice
- •For logistics planners: Improve the selection of neural routing solvers by understanding their decision-making behaviors for route optimization problems.
- •For ai system engineers: Design more interpretable neural routing solvers by leveraging insights on how current-node and future-node information guides decisions.
Authors
Fatemeh Askari, Mazdak Teymourian, Mohammad Izadi, Mahdieh Soleymani Baghshah
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.