acceptodds
Under review as a conference paper at ICLR 2027

When Can Neural Routing Policies Discard Redundant Inputs?

Abstract

Fixing an executed route prefix in capacitated vehicle routing leaves a residual optimization problem, yet neural solvers can continue to use inputs that no longer determine its feasible continuations or costs. When can such task-redundant inputs be removed while preserving routing quality? We connect residual-task formulation to computational interventions and controlled retraining. We select POMO and ReLD for their contrasting mechanisms of information reuse: cross-token normalization and cached readouts from a normalization-free encoder. In both, local masking leaves served-customer influence in shared statistics or retained embeddings. Closing the identified paths removes this influence but worsens fixed-weight route quality, separating task sufficiency from the dependencies of a trained representation. Complementary retraining experiments on progress inputs show that, under mixed-size training, deleting dedicated step inputs maintains quality comparable to normalized retention, while normalized progress better supports transfer from a single small training size. These findings motivate a state-aware graph-pointer that retains observed context, represents unfinished customers beyond current feasibility, and uses normalized progress. Arrivals and demand realizations update this same observation interface, allowing the solver to transfer zero-shot to dynamic and stochastic tasks from a static supervised initialization and improve through complete-route adaptation. These adaptation gains recur across training lineages. The study establishes a basis for simplification that accounts for both residual-task sufficiency and learned computational dependence, with deletion and re-encoding evaluated by the quality of the resulting routes.

Primary area:
optimization
Keywords:
neural combinatorial optimization, vehicle routing, task-preserving interventions, input dependence, progress encoding, out-of-distribution generalization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_SZjmOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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.
  3. 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
  1. 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.
  2. 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

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.

Training on C50C20C50C100C50 cost difference [95% CI]Training time, full / residual
POMO, RL from scratch−2.33%−2.58%−3.24%−0.299 [−0.374, −0.225]4.4 / 65.7 min
ReLD, supervised fine-tuning from published weights+2.43%+1.84%+1.47%+0.199 [+0.185, +0.213]56.9 / 59.3 s

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.

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.

Reviewer_yDNaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies when neural routing policies can discard inputs that are redundant for the remaining task. It analyzes dependencies in POMO and ReLD, compares progress encodings through retraining, and applies the resulting representation choices to dynamic and stochastic routing.

Critical strengths
  1. The dependency analysis is carefully designed. The interventions identify how served customers continue to affect POMO through normalization and ReLD through cached representations and decoder readouts. This gives a concrete explanation for why masking an input does not necessarily remove its influence.

  2. The progress study includes useful controls, particularly the comparison between removing the counter and retaining normalized progress. The paired retraining experiments show that the conclusion depends on the training regime, rather than supporting a blanket recommendation to remove progress inputs.

Critical weaknesses
  1. The practical implications of the dependency analysis remain unclear. The POMO and ReLD experiments show that removing served-customer information hurts a frozen policy, but this does not necessarily mean the information is beneficial after retraining. BQ-NCO has already demonstrated effective learning on reduced states, and the paper's own compact-representation experiment preserves C20 quality. A retraining comparison on POMO or ReLD would help establish when retaining redundant inputs is actually useful.
Questions for authors
  1. Could the authors compare full observed context with compact residual context under the same online backbone and training protocol? This seems important for connecting the dependency study to the final solver.

  2. Could the authors clarify the waiting and dispatch rules in strict-D50? In particular, what prevents a distance-only policy from waiting until all requests are revealed?

1 comment

We are truly grateful for your recognition of our work and your valuable feedback. We have ran that comparison and will include it, along with a clarification of the strict D50 dispatch rule. We also hope that we could answer the questions.

1. Can the same online backbone learn without served customers? (Weakness 1 and Question 1)

On dynamic D50, the residual policy produced shorter routes both before and after adaptation. The full encoder sees all revealed customers. The residual encoder keeps the depot, the current node and every revealed unfinished customer, including those that can be served only after replenishment. The arms share initial weights, demonstrations, normalized progress, legal actions and training updates.

After static behavior cloning, dynamic D50 cost was 13.823 with full context and 13.712 with residual context. We then adapted each policy for the same number of RL updates on its target task.

Task after adaptationFullResidualResidual minus full [95% CI]
Dynamic D5013.65213.566−0.086 [−0.134, −0.039]
Stochastic D5014.13714.098−0.039 [−0.084, +0.006]

The 0.28% stochastic D50 difference has an interval that includes zero. In static C50, POMO trained from scratch also produced shorter routes with residual context (11.303 versus 11.603, a 2.58% reduction at equal updates). Re-encoding increased training time from 4.4 to 65.7 minutes. A frozen policy’s reliance on served customers can coexist with a retrained policy’s ability to omit them.

2. Does strict-D50 force dispatch when service is possible? (Question 2)

Yes. At the depot, any revealed customer that fits the remaining capacity forces dispatch. Customer service and depot return are the only actions, and a depot-to-depot move is illegal. After reset or an action, if no revealed unfinished customer fits the current load and some requests are still hidden, the environment advances the clock once to the next release. This can also happen at a customer before a possible depot return. The automatic advance adds no distance. Since the policy cannot select it, a distance-only objective cannot induce waiting at the depot while serviceable work is available.

Metrics. Cost is mean complete-route distance. The online table uses 1,024 dynamic and 512 stochastic instances, with paired 95% t intervals over eight training pairs. Static POMO uses eight seed pairs and best-of-50 decoding on 192 C50 instances.

Reviewer_rpDnOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates whether neural routing policies can remove input information that is unnecessary for defining the remaining optimization problem without sacrificing solution quality. The authors distinguish between task-relevant information, which is required to determine feasible decisions and future costs, and computationally useful information, which may be redundant for the underlying problem but can still influence a trained neural policy. First, it investigates frozen policies such as POMO and ReLD and finds that information about already-served customers can continue to affect decisions through mechanisms such as shared normalization statistics, intermediate representations, and cached embeddings. Simply masking these inputs is therefore insufficient to eliminate their influence, and restricting access to them can degrade solution quality. Second, the authors systematically compare seven ways of representing routing progress. Their results show that dedicated step-counter inputs can be removed in some training settings without materially degrading performance, while normalized progress information can improve generalization to larger problem sizes when training data cover only smaller instances. They also demonstrate that a compact representation retaining only the depot, current location, and unserved customers can reduce training time by 22.325% while keeping solution cost within 1% of the reference on C20 instances.

Critical strengths
  1. The paper investigates whether redundant inputs can be removed from neural routing policies without compromising solution quality. This is relevant to developing more efficient neural combinatorial optimization methods.

  2. The distinction between information required by the underlying optimization problem and information exploited by a trained neural policy provides a useful conceptual framework for understanding neural routing models.

  3. Rather than relying exclusively on comparisons of final solution quality, the authors conduct interventions on frozen policies to investigate how redundant information can influence decisions through normalization statistics, intermediate representations, and cached embeddings. This provides useful insights into the internal behavior of neural routing architectures.

Critical weaknesses

1 The detailed frozen-policy interventions focus mainly on POMO and ReLD. It remains uncertain how broadly the conclusions generalize to other architectures and normalization schemes.

2 The state-aware graph-pointer uses established ingredients such as graph attention, behavior cloning, and policy-gradient adaptation. The conceptual contribution lies more in the representation analysis and its design implications than in a fundamentally new architecture.

3 The after-action readout shows no statistically established improvement over the backbone. The benefits appear to come primarily from the common state representation and adaptation.

4 The dynamic and stochastic improvements are relatively modest in percentage terms. Stronger evidence of generalization across problem distributions, instance sizes, and computational budgets would help establish broader practical value.

5 Removing task-redundant inputs from a frozen model worsens performance, while retraining with a reduced interface can preserve it. This distinction is important, but it also means the results should not be interpreted as showing that removing redundant inputs is generally safe.

Questions for authors

How do the authors distinguish the effects of removing redundant inputs from disruptions to learned representations?

Why does removing the step counter work well with mixed-size training but normalized progress help generalization when training on smaller instances? Does the reported training-time reduction persist on larger instances under a fair computational budget?

How much improvement comes from the proposed representation versus behavior cloning and reinforcement-learning adaptation?

1 comment

We sincerely thank you for the review and pointing out the weakness distinguishing. We consider our main contribution is to test where an input reaches decisions and what removal costs after learning. We have also conducted extra experiments and will report the matched retraining and timing results below. We hope they answer the questions and inform the reviewer’s reassessment.

1. Can we distinguish dependence in a frozen solver from the value of an input after learning?

As an answer to question 1 and weakness 5. Exclusion hurt frozen POMO. Training from scratch with the same exclusion produced shorter routes. In static CVRP, moving a noncurrent served customer preserves every feasible continuation and its cost. With weights and feasible actions fixed, a change in action probabilities detects dependence. Restricting frozen POMO’s attention and normalization to the depot, current node and all unserved customers removed the sampled response and raised C50 cost by 4.306 distance units. That penalty includes disruption to the trained representation.

At 768 RL updates from scratch, residual POMO had lower C50 cost in all eight seed pairs. Mean cost fell from 11.603 to 11.303 (−2.58%, paired difference −0.299 [−0.374, −0.225]). Training took 4.4 min with full caching and 65.7 min with residual re-encoding. Under limited supervised fine-tuning of published POMO weights, residual cost was 14.47% higher. These protocols differ in initialization, objective, and decoding.

2. Does the diagnostic transfer beyond POMO and ReLD?

To address weakness 5 POMO mixes nodes through normalization. ReLD caches embeddings from a normalization-free encoder. Appendix A.6 tests BQ, LEHD and INViT. In INViT, a padding slot carries a served coordinate into normalization before masking. Replacing only the padding coordinates removed all 4870 observed probability responses. Across 512 C50 routes the cost change was −0.0031 [−0.0078, +0.0014] distance units. This preprocessing fix had little effect on route quality.

3. Can the counter be omitted, and does packing save time?

Across 16 paired starts, training without the counter on mixed C20/C50 changed cost by +0.14%, +0.15% and +0.03% relative to normalized progress on C20, C50 and C100. All three one-sided 97.5% upper bounds were below 1%. After C20-only training, the C100 increase was 2.83%. Normalizing the step by twice the customer count gives progress a common scale. Unfinished customers, location and load can also signal progress. Which cues the counter-free policy uses remains open.

The 22.3% time saving came from packing the residual graph in a separate C20 experiment. At equal updates, training took 74.69 s versus 96.15 s for the full graph over seven paired seeds. The one-sided 97.5% upper bound on excess cost was +0.523% on C20 and +3.239% on C50 transfer. A shorter full run also reached comparable C20 quality in 48.23 s. Training-time savings from this packing scheme on C50 or C100 remain unmeasured.

4. Can we separate the context effect from adaptation and the added readout?

Residual context already lowers D50 cost after static behavior cloning (BC). Both policies improve further with RL. The arms share backbone, initial weights, demonstrations, progress encoding and update counts.

Stage, same 1,024 D50 instancesFullResidualResidual minus full [95% CI]
Static BC13.82313.712−0.111 [−0.175, −0.047]
BC followed by D50 RL13.65213.566−0.086 [−0.134, −0.039]

RL reduced cost by 1.23% with full and 1.06% with residual context. Both arms start from BC, so its independent effect remains open. The afterstate readout cost 0.10% more than the normalized backbone on D50, with a paired interval spanning zero. We will present the normalized backbone as the default online solver and the afterstate readout as an ablation.

5. Do the gains extend across budgets and distributions?

At equal updates, residual cost on stochastic D50 was 0.28% lower (512 instances, distance CI [−0.084, +0.006]). For each arm’s selected BC model, we chose among source checkpoints validated within 180 s of recorded adaptation time. On fresh 256-instance panels, residual cost was 0.71% lower on dynamic D50 and 0.66% lower on stochastic D50 (Holm p = 0.0156 each). Across early arrivals, late arrivals and clustered locations, the pooled differences were −0.30% and +0.12%. Both intervals spanned zero, as did those on the 100-customer panel with changed capacity and release horizon. Reference D50 shows the clearest benefit across budgets.

Metrics. Cost is mean complete-route distance. POMO from scratch uses best-of-50 decoding on 192 C50 instances. POMO and online intervals are paired 95% t intervals over eight seed pairs. INViT uses an instance bootstrap.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.