acceptodds
Under review as a conference paper at ICLR 2027

Edge-aware Decoding for Neural Asymmetric Routing

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 to . 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.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Vehicle Routing Problem

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_8AyBOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper argues that neural ATSP solvers like RADAR encode directed costs in the encoder, but their final decoder score never explicitly sees the cost of the current edge. The authors add a small MLP bias to each candidate’s score, computed from edge-cost features read directly from the cost matrix, while keeping the backbone fixed. Trained on small instances and tested zero-shot on larger ones, it reduces the optimality gap, at the cost of noticeably slower inference.

Critical strengths
  1. Clear motivation. RADAR encodes distance information in the encoder but does not expose the current edge cost in the final decoder score.
  2. Simple method. It only adds a small MLP bias on the final logits with the backbone unchanged, so it is easy to reproduce.
Critical weaknesses
  1. High inference cost. The inference time is much higher than RADAR across sizes, and no equal-compute comparison is given: RADAR is never given sampling or augmentation under the same time budget, and the baseline timings are reproduced from the RADAR paper, so they may not come from the same hardware.
  2. Insufficient comparison with ReLD. ReLD is the closest general decoder-side baseline. The authors should compare more fairly, for example on TSP, and by applying ReLD’s decoder design on the RADAR backbone under the same training protocol.
Questions for authors
  1. How does the method compare with RADAR using sampling (or augmentation) under the same inference time budget, with all timings measured on the same hardware?
  2. Where does the overhead come from, given that Table 2 shows it barely depends on the number of features? Have the authors considered a more lightweight way to expose edge information, for example a single linear term on the edge cost, or computing the bias only for a subset of candidates?
  3. Could the authors provide more comparison with ReLD?
  4. Every model is trained once with a single seed, so small differences in the ablations are not reliable.
3 comments
AuthorsOpenReview ↗

Response (1/2)

Thank you for recognizing the motivation and simplicity of our method. We address the inference cost, lightweight alternatives, comparison with ReLD, and training-seed concern below.

W1/Q1: Same-hardware timing and comparison under an equal time budget.

The supplementary RADAR–Ours comparisons were measured on the same hardware. The added cost comes mainly from the decoder's edge-bias computation, particularly repeated MLP evaluation for candidates at every construction step. We will distinguish these measurements from the externally reported baseline timings in Table 1 and clarify the timing protocol.

In the ATSP matched-budget comparison, Ours first performs one greedy full-POMO pass, generating N trajectories per instance, and its measured runtime sets the RADAR budget. With the official checkpoint fixed, RADAR repeatedly performs stochastic full-POMO rollouts, generating N trajectories per instance per repetition by sampling subsequent nodes from the model's action probabilities. For each instance, we first select the lowest-cost trajectory among the N trajectories and then compare it with the best tour retained from previous repetitions. The random seed is set only at the start of the evaluation and is not reset inside the loop, so repetitions use fresh action samples.

Test NOurs: one greedy passRADAR: one passRADAR: matched-time sampling
1001.57411.57561.5726
2001.58521.58791.5829
5001.60321.60981.6073
10001.61701.63891.6323

Lower objective is better. RADAR uses the extra budget effectively at N=100/200 and slightly outperforms Ours. At N=500/1000, Ours remains better by 0.0041 and 0.0153, respectively. Thus, the equal-time benefit is concentrated on larger cross-size instances; the additional runtime alone does not explain these gains. We do not claim an equal-time advantage at every scale.

These ATSP inputs are directed cost matrices, so the usual eight-fold rotation/reflection augmentation of Euclidean coordinates is not directly applicable. We therefore use the stochastic trajectory sampling described above for this comparison.

Q2: Source of the overhead and lightweight alternatives.

Reducing the number of input features leaves the main repeated computation in place: the edge-bias network is still evaluated across candidates at every decoding step. The dominant added cost in the current implementation is the repeated bias MLP evaluation.

Independent profiling supports this explanation. On the first two ATSP-1000 batches, comprising four instances, the measured bias-MLP stream time is approximately 9.53 times the feature-gathering time.

We also compare two simpler score corrections under the same training and evaluation protocol: Learned-α\alpha, which uses only bt(j)=−αD^ct,jb_t(j)=-\alpha\widehat D_{c_t,j}, and Linear, which replaces the MLP with a single affine layer over the same six-dimensional feature vector.

MethodATSP-100 Obj / GapATSP-200 Obj / GapATSP-500 Obj / GapATSP-1000 Obj / Gap
RADAR1.5756 / 0.72%1.5879 / 1.01%1.6098 / 2.13%1.6389 / 4.13%
Learned-α\alpha1.5726 / 0.53%1.5844 / 0.78%1.6057 / 1.87%1.6269 / 3.37%
Linear1.5768 / 0.80%1.5927 / 1.31%1.6320 / 3.53%1.8499 / 17.54%
Ours1.5741 / 0.63%1.5852 / 0.83%1.6032 / 1.71%1.6170 / 2.73%

The scalar correction slightly outperforms the full model at N=100/200. The full MLP provides additional gains at N=500/1000. The affine variant deteriorates substantially at N=1000 despite containing the scalar correction as a special case. These results support the nonlinear mapping under the tested setup, without implying that the full MLP is necessary at every scale. In a separate same-hardware timing run, Learned-α\alpha takes 1.054 times RADAR's runtime at N=1000, compared with 3.868 times for the full model.

We also tested computing the bias only for a subset of candidates, as suggested. Using the existing full-model weights, we select the Top-K feasible candidates by the base decoder logits and evaluate the bias only for those candidates. Other feasible candidates retain their base scores. On the fixed first 100 ATSP-500 instances:

KSpeedup over full biasObjective increase
322.03×10.563%
1281.61×0.978%
2561.26×0.136%

Timing includes candidate selection and feature gathering/scattering. The experiment demonstrates an adjustable quality–time trade-off, but restricting the candidate set can exclude useful corrections and reduce solution quality. This is an approximate inference strategy, not an equivalent acceleration of the full decoder.

AuthorsOpenReview ↗

Response (2/2)

W2/Q3: Direct comparison with ReLD on ACVRP using the RADAR encoder.

Following your suggestion, we compare three models on ACVRP using the RADAR encoder architecture: the original RADAR, RADAR Encoder + ReLD Decoder, and RADAR + Edge Bias. All three are trained on ACVRP-20 instances for 100 epochs and evaluated on ACVRP-20, ACVRP-50, and ACVRP-100, with 1,000 test instances at each size. The latter two sizes test cross-size generalization.

MethodACVRP-20ACVRP-50ACVRP-100
Original RADAR2.21542.47522.7758
RADAR Encoder + ReLD Decoder2.13362.43472.6319
RADAR + Edge Bias2.11802.37732.4929

Objectives are rounded to four decimal places; the relative reductions below are calculated from unrounded values.

Lower objective is better. Both decoder modifications improve over the original RADAR, and RADAR + Edge Bias obtains the lowest objective at all three test sizes. Relative to RADAR Encoder + ReLD Decoder, it reduces the objective by 0.73%, 2.35%, and 5.28% at N=20, N=50, and N=100, respectively. Its advantage over ReLD becomes more pronounced as the test size increases. Under this training budget, the results support the benefit of explicitly exposing transition information beyond the tested ReLD decoder modification.

Due to time constraints, we report the comparison at 100 training epochs. All three models showed smaller improvements at this stage. These results therefore compare performance with a common encoder architecture and training-epoch budget.

Q4: Reliability of ablation differences and independent retraining.

We agree that a single training run for each ablation variant in Table 2 is insufficient to establish whether the small differences are stable across training seeds. We will therefore describe these differences as observations under the evaluated setup and avoid drawing definitive conclusions about component contributions from small numerical margins alone.

As an additional check on the consistency of the main result, we trained the full ACVRP model at N=100 with two independent random seeds and evaluated it at N=1000, obtaining objectives of 2.1156 and 2.1150. The mean is 2.1153 and the sample standard deviation is 0.0004; both results are close to the originally reported 2.1148. These results support the consistency of the main ACVRP-1000 result across two independent retraining runs; the stability of the Table 2 ablation differences across training seeds still requires separate validation.

Thank you for the response and the additional experiments.

My main remaining concern is that a lightweight design may already be sufficient. In your own ablation, the Learned-alpha is better than the full model at N=100/200, and recovers more than half of the gap reduction at N=500/1000. I appreciate the idea of exposing edge cost in the decoder, but I feel the current design is not the best one. I am keeping my score for now.

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

This paper presents a representation–decision mismatch in neural asymmetric routing, claiming that asymmetry-aware encoders do not necessarily expose the current directed transition cost effectively to the final decoder logits, and thus propose an edge-aware decoder that augments conventional context–node compatibility scores with explicit local edge costs, return-to-start costs, and static lookahead features. Experimental results show the effectiveness of the proposed method on ATSP and ACVRP.

Critical strengths
  1. The proposed modification to decoder is simple, which is specific to final action scoring and is potentially generic to existing asymmetric routing models.
  2. Experimental results show that the proposed edge-aware decoder is promising, which shows the consistent improvement over the backbone RADAR, especially on ACVRP.
Critical weaknesses
  1. The novelty seems to be limited. The proposed method essentially adds edge-cost features to the decoder logits, which is a relatively straightforward extension of existing cost-aware scoring methods. More importantly, the paper lacks comparisons with simpler alternatives, such as directly adding a weighted edge cost or using only local edge features.
  2. Despite achieving lower optimality gaps, the proposed method incurs considerably higher inference costs than RADAR (e.g., 3.75× longer on ATSP-1000). In addition, the results lack multi-seed evaluations, and the large improvement on ACVRP-1000 would benefit from further validation.
  3. The paper claims RADAR's limited scale generalization to its inability to reliably capture directed edge costs through learned representations. However, the experiments do not directly verify this hypothesis. The results mainly confirm that explicitly incorporating edge costs increases the decoder's sensitivity to them, rather than explaining why this leads to better generalization.
Questions for authors
  1. How much of the improvement can be obtained by adding only a scalar bias D_ij to RADAR's decoder logits?
  2. Could the authors isolate the claimed representation–decision mismatch more directly? For example, what happens when the pretrained RADAR encoder and decoder are frozen and only the edge-bias module is trained? Is there empirical evidence that the implicit edge-cost estimation error increases with problem size?
  3. Could the authors provide matched-hardware runtime comparisons and multi-seed statistics for ACVRP-1000? In particular, how does the method compare against simpler edge-aware baselines at equal inference time?
3 comments
AuthorsOpenReview ↗

Response (1/2)

Thank you for recognizing the simplicity and potential applicability of the decoder modification. We address the scalar-cost baseline, the frozen-backbone experiment and mechanism interpretation, the quality–time trade-off, and the reliability of the ACVRP-1000 result below.

W1/Q1: How much improvement comes from a scalar edge-cost bias?

We agree that a scalar-cost control is essential. We compare Learned-α\alpha, which adds only bt(j)=−αD^ct,jb_t(j)=-\alpha\widehat D_{c_t,j}, with the full model. We also include Linear, a single affine layer over the same six-dimensional transition descriptor used by the MLP. All variants retain the same backbone architecture, training schedule, rollout, clipping, masking, and evaluation protocol.

MethodATSP-100 Obj / GapATSP-200 Obj / GapATSP-500 Obj / GapATSP-1000 Obj / Gap
RADAR1.5756 / 0.7200%1.5879 / 1.0100%1.6098 / 2.1300%1.6389 / 4.1300%
Learned-α\alpha1.5726 / 0.5300%1.5844 / 0.7800%1.6057 / 1.8700%1.6269 / 3.3700%
Linear1.5768 / 0.8000%1.5927 / 1.3100%1.6320 / 3.5300%1.8499 / 17.5400%
Ours1.5741 / 0.6300%1.5852 / 0.8300%1.6032 / 1.7100%1.6170 / 2.7300%

Lower objective and gap are better. A learned scalar correction already captures much of the near-scale benefit and slightly outperforms the full model at N=100/200. At N=1000, it reduces the gap from 4.13% to 3.37%, while the full model reduces it further to 2.73%. The affine variant performs substantially worse at this size, despite containing the scalar correction as a special case. The evidence therefore supports a narrower claim: explicit current-edge information accounts for a substantial part of the improvement, while the richer nonlinear scoring function provides additional gains under larger size shifts. We do not claim that the MLP is necessary at every scale. The scalar control isolates the current directed cost; it is distinct from a three-feature local-edge-only MLP.

W3/Q2: Frozen pretrained RADAR and the connection between sensitivity and generalization.

Following your suggestion, we freeze the pretrained RADAR encoder, base decoder, and structural projections, and train only the added bias on fresh ATSP-100 instances. The scalar and MLP biases are initialized to zero. Zero-bias checks reproduce the pretrained model's outputs, and parameter checks confirm that all original weights remain unchanged during adaptation. We evaluate against a fresh RADAR control with matching frozen execution settings.

ModelN=100 objectiveN=500 objective
Pretrained RADAR, frozen control1.57561.6113
Frozen RADAR + Alpha1.57561.6106
Frozen RADAR + Full MLP1.57551.6083

N=100 uses 1,000 test instances, and N=500 uses 100 instances. The table reports the completed results of short adaptation runs. Alpha trains one parameter, while Full MLP trains 257 parameters.

These results show that adding a trainable transition bias can improve larger-instance decisions without changing the pretrained representation or base decoder.

The connection to generalization is an inductive-bias interpretation. The immediate directed transition cost is a known component of the Bellman action cost at every problem size. More reliable sensitivity to this quantity indicates that the decoder can use it more directly and consistently, reducing its reliance on recovering it from implicit representations whose behavior may change with scale. This supplies a reason why exposing the edge cost can help cross-size transfer. Figure 3 identifies weaker decision-time edge sensitivity in the baseline, while the frozen experiment shows that the same pretrained backbone leaves room for improvement at the scoring stage.

We agree that sensitivity alone does not prove the cause of the entire generalization gain. We have not directly measured an implicit edge-cost reconstruction error that increases with N. We will present that explanation in Equation (4) as a hypothesis, and distinguish it from the directly supported findings: stronger transition sensitivity and improved cross-size solution quality. Explicit cost exposure does not algebraically eliminate embedding error or guarantee optimal candidate rankings.

AuthorsOpenReview ↗

Response (2/2)

W2/Q3: Same-hardware runtime and equal-time comparisons.

The supplementary RADAR–Ours comparisons use the same hardware. The added latency is mainly associated with repeated evaluation of the decoder's edge-bias MLP. In the ATSP matched-budget comparison, Ours first performs one greedy full-POMO pass, generating N trajectories per instance, and its measured runtime sets the RADAR budget. With the official checkpoint fixed, RADAR repeatedly performs stochastic full-POMO rollouts, generating N trajectories per instance per repetition by sampling subsequent nodes from the model's action probabilities. For each instance, we first select the lowest-cost trajectory among the N trajectories and then compare it with the best tour retained from previous repetitions. The random seed is set only at the start of the evaluation and is not reset inside the loop, so repetitions use fresh action samples.

Test NOurs: one greedy passRADAR: one passRADAR: matched-time sampling
1001.57411.57561.5726
2001.58521.58791.5829
5001.60321.60981.6073
10001.61701.63891.6323

The extra search budget allows RADAR to slightly outperform Ours at N=100/200. Ours remains better at N=500/1000, by 0.0041 and 0.0153, respectively. Thus, the equal-time advantage is strongest under larger size shifts, rather than uniform across scales.

To directly address the simpler edge-aware alternative, we also conducted a separate matched-budget experiment with Learned-α\alpha. Alpha performs stochastic full-POMO rollouts within the one-pass Full MLP budget, retaining the best tour per instance. Each scale uses 1,000 fixed instances.

The Full MLP reference in this table uses results from a later, separate evaluation with a different protocol from the RADAR matched-budget experiment above. The respective N=500 objectives are 1.6033 here and 1.6032 in the preceding table.

Test NFull MLP: one passAlpha: matched time
5001.60331.6032
10001.61701.6258

At N=1000, Full MLP retains a lower objective even when Alpha is given more opportunities to search.

W2/Q3: Reliability of the ACVRP-1000 improvement and independent retraining.

We checked the large ACVRP-1000 improvement through independent feasibility and cost verification. For each model, the audit covers all 1,000 test instances and all 1,000,000 POMO candidate trajectories. Every customer is visited exactly once, each route starts and ends at the depot, and every depot-to-depot route satisfies the capacity constraint. Directed costs are independently recomputed from the original integer matrices, including return edges.

ModelRecomputed objectiveFeasible candidatesRelative inference time
RADAR2.4713100.0000%1.0000×
Ours2.1135100.0000%3.4387×

The largest discrepancy between the reported and independently recomputed costs is below 3.4×10−73.4\times10^{-7}. The mean objective reduction relative to the local RADAR rerun is approximately 14.48%. These results support the validity of the evaluated routes and cost calculations while also showing the runtime trade-off.

We also trained the ACVRP model at N=100 with two independent random seeds and evaluated it at N=1000, obtaining objectives of 2.1156 and 2.1150. The mean is 2.1153 and the sample standard deviation is 0.0004; both results are close to the originally reported 2.1148. This provides evidence of consistency across independent training runs for the large-scale result.

Reviewer_PjuaOpenReview ↗

Official Comment of Reviewer Pjua

Thank you for the responses. My concern about novelty still remains. The general idea of incorporating problem-specific biases into final decoder scores has already been explored in many prior NCO works (e.g., [1][2]). The Bellman formulation does not lead to a new cost-to-go modeling approach, as the lookahead features are merely static local heuristics. Moreover, the Learned-alpha baseline already achieves large improvement with much lower inference overhead, as additional experimental results shows. Thus, I keep my rating unchanged.

[1] Yang Wang. et al. Distance-Aware Attention Reshaping for Enhancing Generalization of Neural Solvers. IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 2025.

[2] Cong Dao Tran et al. Large Language Models Powered Neural Solvers for Generalized Vehicle Routing Problems. ICLR Workshop on Towards Agentic AI for Science, 2025.

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

This paper investigates the mismatch between representation learning and final decision making in existing neural approaches to asymmetric routing problems. To address this issue, it proposes an edge aware decoder that explicitly incorporates the current directed edge cost, return to start closure cost, and static lookahead information into candidate scoring while keeping the original encoder unchanged. Experiments on ATSP and ACVRP demonstrate the effectiveness of the proposed method.

Critical strengths

This paper addresses the mismatch between representation learning and final decision making in neural combinatorial optimization. While existing studies primarily focus on designing more powerful encoders, this work investigates whether decoders can effectively utilize problem structure information, offering a valuable research perspective. The paper analyzes the contributions of Local Edge, Closure, and Lookahead features separately and introduces directed edge perturbation experiments. The ablation studies are well designed and targeted.

Critical weaknesses
  1. The methodological novelty is relatively limited, as the proposed approach mainly extends existing neural architectures with an additional module. The proposed Edge Aware Decoder essentially combines an Attention Score with an MLP based on handcrafted features. Although the method is motivated by the representation and decision mismatch, its implementation remains a relatively minor modification to existing architectures.
  2. The proposed Lookahead features mainly rely on static minimum incoming and outgoing edge costs, essentially serving as local greedy heuristics that cannot accurately capture the optimal future routing cost. This represents a limitation of the method design.
  3. The proposed method introduces substantial additional inference overhead, particularly on large scale instances.
Questions for authors
  1. The proposed Lookahead features mainly rely on static minimum incoming and outgoing edge costs, essentially serving as local greedy heuristics that cannot accurately reflect the globally optimal future routing cost. Intuitively, it seems possible to construct instances where such greedy heuristics fail. How can the generalization and robustness of the proposed method be ensured? Alternatively, could more rigorous theoretical guarantees for cross scale generalization be provided?
  2. The proposed method mainly improves solution quality by introducing an additional MLP scoring module with lookahead information into existing neural decoders. Compared with directly incorporating such information into attention scores or using a simple linear scoring function, what are the advantages of the proposed approach? Could additional comparative experiments demonstrate the necessity of this design?
  3. The main experiments are conducted on randomly generated synthetic instances. It remains unclear whether the proposed method is effective on instances where local minimum edge costs are poorly correlated with optimal decisions. Therefore, additional experiments across different cost distributions would be valuable, along with comparisons of solution quality under matched computational budgets.
  4. Although additional experiments are conducted on POMO and ELG, the performance improvements are inconsistent across different neural architectures and datasets. What explains these differences, and under what conditions is the proposed Edge Aware Decoder most effective?
4 comments
AuthorsOpenReview ↗

Response (1/3)

Thank you for recognizing the value of studying decoder-side decision making and the targeted ablations. We address your concerns below.

W1: Contribution and the Bellman-motivated decoder design.

Our contribution is to identify a decoder-side limitation in asymmetric routing and provide a principled way to address it. In the examined backbone, directed costs enter the encoder, but the final candidate score is still parameterized as context–node compatibility. The directed transition being selected is therefore represented only implicitly. The diagnostics in Section 4.4 and Figure 3 show that RADAR's final scores have weaker sensitivity to the current directed edge and antisymmetric perturbations, particularly at larger sizes. This motivates strengthening the decision interface even when the encoder already models asymmetry.

The Bellman decomposition provides a design principle for this interface:

\qquad V^*(i,\varnothing)=D_{i,s_{\mathrm{start}}}.$$ It identifies the immediate directed cost, the return boundary, and continuation information as relevant quantities for action scoring. Our decoder exposes these quantities through a transition descriptor and learns their contribution to the final score. The encoder architecture is unchanged, and the model is trained end-to-end. The small MLP implements this design principle; the contribution lies in the representation–decision mismatch, the transition-aware formulation, and the controlled evidence supporting it. The Bellman equation motivates the descriptor but does not make its heuristic continuation features exact or establish a generalization guarantee. **Q2: Comparison with scalar and linear scoring.** Our method already injects structural information directly into the final attention compatibility score, before clipping and masked softmax. To assess the scoring function, we compare a learned scalar bias, $b_t(j)=-\alpha\widehat D_{c_t,j}$, and a single affine layer, $b_t(j)=w^\top\phi_t(j)+b$, against the full MLP. The affine variant uses the same six features as the MLP. The backbone architecture, training schedule, rollout, and evaluation protocol are held fixed. | Method | ATSP-100 Obj / Gap | ATSP-200 Obj / Gap | ATSP-500 Obj / Gap | ATSP-1000 Obj / Gap | |---|---:|---:|---:|---:| | RADAR | 1.5756 / 0.72% | 1.5879 / 1.01% | 1.6098 / 2.13% | 1.6389 / 4.13% | | Learned-$\alpha$ | **1.5726 / 0.53%** | **1.5844 / 0.78%** | 1.6057 / 1.87% | 1.6269 / 3.37% | | Linear | 1.5768 / 0.80% | 1.5927 / 1.31% | 1.6320 / 3.53% | 1.8499 / 17.54% | | Ours | 1.5741 / 0.63% | 1.5852 / 0.83% | **1.6032 / 1.71%** | **1.6170 / 2.73%** | Lower objective and gap are better. Near the training scale, explicitly exposing the current directed cost already accounts for much of the improvement. The full model's additional advantage is most evident under larger size shifts: at N=1000, it reduces the gap from 3.37% to 2.73% relative to Learned-$\alpha$. **W2/Q1: Static lookahead and the dynamic alternative.** We agree that static minimum incoming and outgoing costs cannot represent the optimal remaining tour cost. They summarize local connectivity and can be misleading when cheap edges have already been visited or cannot form a feasible low-cost continuation. We use them as inexpensive auxiliary descriptors. Their empirical contribution is modest: Table 2 shows that removing lookahead increases the ATSP-500/1000 gaps from 1.71%/2.73% to 1.87%/3.03%. The dynamic alternative is already evaluated in Appendix D, Table 5. It recomputes the minimum incoming and outgoing costs over the remaining unvisited nodes at each decoding step, while retaining the same local-edge and closure terms. It improves the ATSP-100 gap slightly, from 0.63% to 0.59%, but has slightly worse gaps at N=200/500/1000: 0.85%/1.76%/2.79%, compared with 0.83%/1.71%/2.73% for static lookahead. Its runtime rises from 43.44 to 844.16 minutes at N=1000, approximately 19.43 times the static variant's runtime. This comparison supports static lookahead as a practical quality–time choice in the evaluated setting. Neither variant provides an exact cost-to-go estimate or a worst-case robustness guarantee.
AuthorsOpenReview ↗

Response (2/3)

Q1: Zero-shot generalization to TSPLIB.

To test transfer beyond the synthetic training distribution, we evaluated the ATSP-100 checkpoints without finetuning on 19 TSPLIB95 ATSP instances, spanning N=17–443. Both methods use the same per-instance normalization, trajectory count, and greedy decoding protocol. Gaps are measured against known optima and averaged equally across instances.

Test subsetInstancesOfficial RADAR mean gapOurs mean gapOurs wins
N ≤ 1001414.53%11.60%8/14
N > 100549.26%17.60%5/5
All1923.67%13.18%13/19

The overall mean gap decreases by 10.49 percentage points; the median also decreases from 11.18% to 9.10%. The advantage is more pronounced beyond the training size, where Ours improves all five evaluated instances. These results provide empirical evidence of cross-distribution transfer and a stronger relative advantage under larger size shifts. They do not imply that absolute performance improves with size or that every unseen distribution will benefit. We will distinguish this empirical finding from a theoretical guarantee of cross-size generalization.

Q3: Robustness to changes in the cost distribution.

We also keep all checkpoints fixed and vary the asymmetry of the test matrices using

\qquad \lambda\in\{0,0.25,0.5,0.75,1\}.$$ All checkpoints were trained on the original distribution at $\lambda=1$. The table reports the relative objective reduction over RADAR, $100(\mathrm{Obj}_{\mathrm{RADAR}}-\mathrm{Obj}_{\mathrm{Ours}})/\mathrm{Obj}_{\mathrm{RADAR}}$, on paired test instances. | Test N | λ=0 | λ=0.25 | λ=0.5 | λ=0.75 | λ=1 | |---|---:|---:|---:|---:|---:| | 100 | 7.50% | 1.34% | 0.20% | 0.04% | 0.10% | | 200 | 10.88% | 2.43% | 0.57% | 0.15% | 0.17% | | 500 | 16.76% | 6.16% | 2.08% | 0.55% | 0.41% | | 1000 | 21.71% | 11.28% | 4.90% | 1.60% | 1.34% | Ours improves over RADAR at every tested setting, with larger relative gains at larger problem sizes for each λ. The benefit is greatest near the symmetric endpoint and generally decreases toward λ=1. Thus, the results support zero-shot robustness to changes in asymmetry, rather than a claim that the method becomes more beneficial as asymmetry increases. **W3/Q3: Inference overhead and equal-time comparison.** The additional inference cost is a real trade-off. In the ATSP matched-budget comparison, Ours first performs one greedy full-POMO pass, generating N trajectories per instance, and its measured runtime sets the RADAR budget. With the official checkpoint fixed, RADAR repeatedly performs stochastic full-POMO rollouts, generating N trajectories per instance per repetition by sampling subsequent nodes from the model's action probabilities. For each instance, we first select the lowest-cost trajectory among the N trajectories and then compare it with the best tour retained from previous repetitions. The random seed is set only at the start of the evaluation and is not reset inside the loop, so repetitions use fresh action samples. | Test N | Ours: one greedy pass | RADAR: one pass | RADAR: matched-time sampling | |---|---:|---:|---:| | 100 | 1.5741 | 1.5756 | **1.5726** | | 200 | 1.5852 | 1.5879 | **1.5829** | | 500 | **1.6032** | 1.6098 | 1.6073 | | 1000 | **1.6170** | 1.6389 | 1.6323 | Lower objective is better. With the additional budget, RADAR slightly outperforms Ours at N=100/200. Ours remains better at N=500/1000, with objective reductions of 0.0041 and 0.0153 relative to matched-time RADAR. Thus, the equal-time advantage is concentrated on larger cross-size instances. We will present this quality–time trade-off explicitly rather than claim an efficiency advantage at every scale.
AuthorsOpenReview ↗

Response(3/3)

Q4: Differences across architectures and the cross-size trend.

The clearest shared pattern is that the benefit grows under a larger shift from the training size. For POMO trained on TSP-100, Appendix E, Table 7 provides a comparison with matched epoch-210 checkpoints and ×8 augmentation:

MethodTSP-100 gapTSP-200 gapTSP-500 gapTSP-1000 gap
POMO0.59%3.13%15.23%27.40%
POMO + Ours0.36%2.16%7.43%11.61%

The gap reduction grows from 0.23 percentage points at the training size to 7.80 and 15.79 points at N=500 and N=1000. The TSP-20 experiment in Table 6 shows the same qualitative pattern: with ×8 augmentation, the gap changes from 0.02% to 0.00% at N=20, but from 9.88% to 4.96% at N=100.

ELG exhibits a weaker and mixed pattern. In Appendix F, Table 8, the large-instance gap improves from 8.9125% to 8.2614% on TSPLIB and from 7.8047% to 7.4471% on VRPLIB-X, while the middle-size groups worsen. Differences in training and test-time heuristics, including ensemble and distance-penalty settings, prevent a clean attribution of these differences to the decoder alone.

Our interpretation is that explicit transition information is particularly useful when a substantial size shift makes the learned final-score mapping less reliable. This is consistent with the directed-edge diagnostics, POMO transfer, and TSPLIB results. The strongest empirical support is for constructive autoregressive solvers tested substantially beyond their training size; the magnitude of the benefit remains dependent on the backbone and inference protocol. We will state these conditions without claiming uniform improvements across architectures or datasets.

Thank you for your detailed response and additional experiments. While several concerns have been addressed, I still have reservations about the limited methodological novelty and the robustness of the heuristic lookahead features. Therefore, I will maintain my original rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.