- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies when task-redundant inputs can be removed from neural routing models without sacrificing solution quality. It first formulates residual-state sufficiency for static CVRP and uses controlled interventions on POMO and ReLD to identify computational dependencies on already-served customers. It then studies 7 progress encodings via paired retraining experiments and proposes a state-aware graph-pointer solver for dynamic and stochastic VRP. Experimental results show that local masking does not necessarily eliminate information dependencies, while removing absolute-step inputs can preserve performance under mixed-size training. The proposed solver also benefits from task-specific adaptation.
Critical strengths
- The paper analyzes the distinction between task-redundant information and information still used by a trained policy. The controlled experiments on POMO and ReLD show how served-customer information can continue to affect decisions through normalization and cached embeddings. These findings provide useful insights into the behavior of existing neural routing solvers.
- The proposed solver can transfer from static supervised training to dynamic and stochastic routing tasks, with further improvements after RL adaptation. The consistent gains demonstrate that the proposed state representation can support different routing settings.
Critical weaknesses
- Prior works such as BQ-NCO, LEHD, and DR-DRL have already explored removing visited customers or dynamically encoding the remaining routing problem. Although this paper provides an interesting analysis of computational dependencies in POMO and ReLD, the findings largely reflect known properties of attention, normalization, and cached embeddings. More importantly, the paper does not clearly establish what new representation principle it offers beyond these existing approaches, or demonstrate its advantage over them.
- The main analysis focuses on redundant information in static CVRP, but the paper ultimately proposes a solver for dynamic and stochastic VRP. The motivation for this transition is unclear, and the earlier findings do not directly justify the final architecture. Specifically, although the paper investigates removing redundant served-customer information, the proposed solver retains it without demonstrating that this choice is beneficial. The dynamic/stochastic experiments primarily demonstrate the benefits of RL adaptation rather than validating the representation principles identified earlier. This weakens the coherence of the paper and makes it difficult to assess how the initial analysis contributes to the final method.
- The dynamic and stochastic VRP experiments lack comparisons with competitive neural routing methods. The reported improvements mainly come from RL adaptation, while the proposed action-afterstate readout does not significantly outperform the simpler backbone. Moreover, the computational cost of re-encoding the graph at every step is not evaluated.
Questions for authors
- Could the authors retrain POMO or ReLD with served-customer information removed, and compare route quality and computational cost across C20/C50/C100? This would directly test whether the dependencies identified in Section 4.1 can be eliminated through learning.
- Since the action-afterstate readout provides no statistically significant improvement over the backbone, why it is necessary? Would the simpler normalized GNN be a more appropriate final architecture?
3 comments
Thank you for the responses. The new experimental results address most of the my technical concerns. However, the benefits of residual representations still rely on the architecture and training strategy, while the novelty over existing residual-state methods such as BQ-NCO and LEHD is still limited. Moreover, the proposed solver does not demonstrate a clear performance advantage over BQ-NCO. Thus I keep the original score.
We thank you for considering the additional experiments. We consider our contribution is to predict which changes to a trained solver will remove or restore its dependence on a task-redundant input. We test those predictions on its action probabilities and measure the consequences for complete routes. Building on BQ-NCO’s reduced-state formulation and LEHD’s decoder over available nodes, we perturb a noncurrent served customer’s coordinates in static CVRP while preserving every feasible continuation and its cost. In ReLD, reopening just the current-node readout restored sensitivity to those coordinates, as predicted, and increased the C50 route-cost penalty from 2.59% to 6.77% relative to unmodified ReLD.
The state-aware graph-pointer serves as an application of this analysis. It lets us compare full and residual context on the same backbone as new requests arrive and demands are revealed. The benefit of residual context depends on the solver and its training protocol. Here the differences after retraining were modest. With matched adaptation updates, residual context lowered mean route cost by 0.63% on dynamic D50 and 0.28% on stochastic D50, where the paired confidence interval included zero. BQ-NCO achieved lower mean route cost on both panels.
We thank the reviewer for the careful reading and constructive comments. To address the concerns raised, we conducted additional experiments with POMO and ReLD using residual context that excludes served customers, and evaluated the published BQ policy in online settings. We summarize the results below and will incorporate these findings and clarifications into the revised manuscript.
1. Can the analysis predict which changes actually exclude an input? (Weakness 1)
BQ-NCO shows that an optimal policy on its reduced state solves the original problem. LEHD uses a heavy decoder to update relations among available nodes. DR-DRL explicitly identifies visited-node influence and removes visited nodes from its decoder context. BQ-NCO, LEHD, DR-DRL.
To exclude an input, trace its influence to feasible-action scores and recompute affected features from retained nodes. To decide whether to adopt that change, compare route quality and training time after relearning. In static CVRP, moving a noncurrent served customer leaves all feasible continuations and their costs fixed. A solver that excludes its coordinates should assign the same probabilities to feasible actions before and after the move.
POMO’s action probabilities still changed on all 128 C50 instances after attention masking. Restricting cross-node normalization as well removed every sampled response. Before generating C50 and C100 instances, we predicted the ReLD response for each of eight interventions at both sizes. All 16 predictions held. Restricting all six encoder layers and refreshing four cached decoder readouts yielded identical probabilities in 12144 sampled perturbation comparisons. Any one reopened readout restored sensitivity. When we reopened just the current-node embedding, routes grew longer still. The C50 penalty rose from 2.59% to 6.77% relative to native ReLD.
On shared late C50 states at a customer, four redraws of served coordinates changed the first executed action in 0/128 BQ instances and 4/128 LEHD instances.
2. Can POMO and ReLD learn the exclusion, and at what cost? (Question 1)
At equal updates, residual POMO learned shorter routes from scratch. Limited ReLD fine-tuning recovered part of the frozen loss. Both train on C50. C20 and C100 test transfer. Percentages are relative to full context.
Full POMO caches one encoding. Residual POMO re-encodes as customers are served. ReLD fine-tuning lowered residual C50 cost from 11.109 to 11.045, recovering 24% of the gap to full context (10.846).
Progress gives a second example. Omitting the counter raised C100 cost relative to normalized progress by 0.03% after mixed C20/C50 training and 2.83% after C20-only training.
3. Does the static analysis inform the online architecture? (Weakness 2 and Question 2)
New arrivals change the visible set and realized demand changes the load. The residual encoder keeps the depot, current node and all revealed unfinished customers. The full encoder also keeps served customers. Both policies share a backbone, demonstrations and update counts. On D50, residual context lowered cost from 13.823 to 13.712 after static behavior cloning and from 13.652 to 13.566 after RL adaptation. Adding the afterstate readout raised mean D50 cost by 0.10% relative to the normalized backbone (paired difference +0.0133 [−0.1134, +0.1400]). We will use the normalized backbone as the default and report afterstate as an ablation.
4. Is there a neural benchmark and a deployment timing? (Weakness 1 and 3)
Published BQ sees only revealed requests and commits to its chosen direct or via-depot action. It gave shorter routes on both panels. Dynamic and stochastic D50 costs were 13.261 and 13.926 for BQ, versus 13.566 and 14.098 for our adapted residual policy. Pretraining budgets differ. At batch size one on a GPU, a D50 route took 443 ms with full and 440 ms with residual context. These end-to-end times include graph encoding at each step. Its isolated overhead remains unmeasured.
Metrics. Cost is mean route distance. Table intervals are paired 95% t intervals over eight runs per protocol. POMO uses best-of-N decoding on 192/192/128 C20/C50/C100 instances. ReLD uses one published initialization and a fixed start on 512 per size. Online panels contain 1,024 dynamic and 512 stochastic instances. Timing uses one lineage, 128 instances and three repetitions.