- 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
- Clear motivation. RADAR encodes distance information in the encoder but does not expose the current edge cost in the final decoder score.
- 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
- 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.
- 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
- 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?
- 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?
- Could the authors provide more comparison with ReLD?
- Every model is trained once with a single seed, so small differences in the ablations are not reliable.
3 comments
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.
| Method | ACVRP-20 | ACVRP-50 | ACVRP-100 |
|---|---|---|---|
| Original RADAR | 2.2154 | 2.4752 | 2.7758 |
| RADAR Encoder + ReLD Decoder | 2.1336 | 2.4347 | 2.6319 |
| RADAR + Edge Bias | 2.1180 | 2.3773 | 2.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.
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.
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-α, which uses only bt(j)=−αDct,j, and Linear, which replaces the MLP with a single affine layer over the same six-dimensional feature vector.
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-α 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:
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.