Edge-aware Decoding for Neural Asymmetric Routing
2026-06-01 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how neural routing models decide the next step in a path, especially when direction matters. They point out that usual models mismatch how they represent costs and how they make final decisions. To fix this, they design a decoder that explicitly considers the cost of moving along specific edges and other helpful hints. Testing this on various routing problems, their decoder improved results, showing the importance of including transition-level edge info during decision-making. Their analysis highlights that paying attention to directed edges at decision time is key for better routing performance.
Neural routing modelsAsymmetric routingDecoder designATSP (Asymmetric Traveling Salesman Problem)ACVRP (Asymmetric Capacitated Vehicle Routing Problem)Transition-level edge informationCost-to-goAttention mechanismSVD/Sinkhorn backboneZero-shot evaluation
Authors
Li Liang, Jinbiao Chen, Zizhen Zhang
Abstract
Neural asymmetric routing models increasingly encode directionality through matrix representations and asymmetry-aware attention. The final routing action, however, is not a node in isolation but a directed transition chosen under the current partial route. This creates a representation--decision mismatch: pairwise cost information may be encoded upstream while the final candidate logit is still largely parameterized as context--node compatibility. We propose a decoder-design principle for neural asymmetric routing: the final score should explicitly expose transition-level quantities suggested by the problem's cost-to-go structure. We instantiate this principle with an edge-aware decoder that adds candidate-specific terms for the current directed edge, return-to-start closure, and static lightweight lookahead, while keeping the representation backbone fixed. On a controlled SVD/Sinkhorn asymmetric backbone, the decoder improves over the RADAR reference when trained on ATSP-100 and evaluated zero-shot on ATSP-100/200/500/1000, reducing the ATSP-1000 gap from $4.13\%$ to $2.73\%$. On ACVRP, the same score-level modification shows the same qualitative trend under a richer routing state. ATSP ablations and directed-transition diagnostics sharpen the mechanism: the strongest evidence concerns sensitivity to the current directed edge, while closure and static lookahead act as heuristic continuation cues. The results support a mechanism study: a key decoder-side signal in neural asymmetric routing is decision-time exposure of transition-level edge information.