- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates the adversarial robustness of neural routing solvers under locally bounded coordinate perturbations. The authors demonstrate that even small perturbations satisfying geometric constraints can substantially degrade solution quality on the TSP and CVRP. To identify such vulnerabilities efficiently, the paper proposes the Reference-Route Reuse Attack, a black-box attack framework that integrates Adam-ES updates with reference-route reuse. Adam-ES combines evolution strategies and adaptive momentum to aggregate feedback from multiple perturbation candidates, while reference-route reuse reduces the computational overhead of repeatedly solving reference instances. Extensive experiments involving constructive, diffusion-based, and refinement-based neural solvers demonstrate substantial local vulnerabilities while highlighting the computational advantages of the proposed attack.
Critical strengths
- Unlike approaches primarily targeting out-of-distribution generalization or hard-instance generation, this work explicitly constrains the node set and coordinate perturbations while directly maximizing the solution gap relative to a reference solution.
- The paper provides relatively broad experimental coverage.
- The manuscript is generally well organized, progressing from the attack formulation and optimization strategy to reference-route reuse and empirical evaluation.
Critical weaknesses
- Although RRA offers practical value, its methodological novelty remains relatively limited. Adam-ES essentially combines established evolution-strategy gradient estimation with Adam-based adaptive momentum, while reference-route reuse exploits the feasibility invariance of routing solutions under coordinate perturbations with a fixed node set. The integration of these components is reasonable, but the paper does not sufficiently establish why this particular combination offers advantages that cannot be achieved by existing zeroth-order optimization methods or alternative caching strategies. Furthermore, the approximation bound in Appendix A.1 follows primarily from the triangle inequality and does not directly guarantee candidate-ranking consistency or reliable optimization directions. Consequently, the theoretical analysis supports the intuition behind reference-route reuse but provides relatively limited new algorithmic insight.
- The empirical evidence does not consistently establish the superior attack strength of RRA. According to Table 1, on TSP100, RRA achieves final attack gaps of 20.078% and 5.385% for AM and POMO, respectively, both below those achieved by full-reference Adam-ES (21.383% and 6.132%). For Pointerformer, ES-sign achieves the highest final attack gap of 29.282%, exceeding RRA's 24.018%.
- Despite evaluating a large number of neural solvers, the main cross-solver robustness comparison relies on only 16 original TSP100 instances, while the CVRP50 evaluation is also primarily based on 16 instances. This limits the statistical reliability of broad architecture-level robustness conclusions. In particular, Pointerformer's attack results exhibit a pronounced heavy-tailed distribution. Table 2 reports a mean adversarial gap of 68.509%, whereas Table 3 indicates a corresponding median of only 7.438%.
Questions for authors
- Why are representative zeroth-order optimization methods such as SPSA, ZO-AdaMM, and CMA-ES not included? Does Adam-ES retain a clear advantage under identical feasibility constraints and computational budgets?
- Eq. (6) estimates update directions using candidate feedback before enforcing the complete geometric constraints. What proportion of candidates violate these constraints? How would attack performance change if every candidate were mapped into the feasible set before evaluation?
3 comments
Response to Reviewer hB4m (2/2)
W2. Is RRA always the strongest attack? No. At the same iteration count, full-reference Adam-ES remains stronger on some models, including POMO. Reuse reduces reference cost: on the same 128 inputs and three seeds, RRA has a larger mean gap on all six models at each reported time budget. Each cell is RRA / Adam-ES mean gap (%), with time per 16-input batch.
Bold / italics: best / second-best within each comparison.
| Solver | 100 s | 200 s | 300 s |
|---|---|---|---|
| AM | 14.866 / 8.789 | 17.660 / 11.688 | 19.256 / 13.711 |
| POMO | 2.953 / 1.420 | 4.121 / 2.242 | 4.826 / 2.993 |
| Pointerformer | 14.890 / 4.533 | 23.234 / 7.846 | 27.090 / 9.262 |
| ICAM | 10.319 / 5.571 | 10.415 / 6.861 | 10.415 / 7.742 |
| AMDKD-POMO | 7.612 / 4.342 | 8.496 / 5.511 | 8.572 / 6.249 |
| MDAM | 15.004 / 9.278 | 16.014 / 11.041 | 16.014 / 12.106 |
Reuse removes 96.94% of search-time reference solves and permits more updates before the deadline. Section 5.2 now distinguishes this benefit from equal-query strength, and Appendix B.5 specifies the timing sources. Figure 3 shows all seven methods against elapsed time; Table B3 gives the values above.
Q2. How many candidates violate the geometric constraints? Default direction queries are box-constrained; recorded updates and returned attacks satisfy all constraints. Checking the queries against the full output constraints gives a 100% centroid violation rate at the 1e-10 tolerance across 819,200 candidates per model. The mean maximum per-axis error is about 0.00055. Nearest-neighbor-distance violations are 1.83% for AM, 1.36% for POMO and 1.40% for Pointerformer; box and marginal-distance violations are 0%.
We also map every candidate into the feasible set before evaluation. All audited candidates then pass the checks. The comparison below uses the same 32 inputs and one seed per model. CMA-ES is included because it is the closest overall challenger among the three new RRA cores; plain Adam-ES separates the effect of reuse. All values are percentages.
| Solver / attack | Mean B100 | Median B100 | AAG |
|---|---|---|---|
| AM / Adam-ES | 19.415 | 18.846 | 16.086 |
| AM / RRA (CMA-ES) | 19.616 | 19.121 | 14.343 |
| AM / RRA | 19.947 | 19.686 | 16.329 |
| POMO / Adam-ES | 6.345 | 6.407 | 4.806 |
| POMO / RRA (CMA-ES) | 5.373 | 5.743 | 3.375 |
| POMO / RRA | 5.207 | 4.972 | 3.693 |
| Pointerformer / Adam-ES | 8.901 | 8.577 | 6.584 |
| Pointerformer / RRA (CMA-ES) | 24.532 | 6.413 | 16.791 |
| Pointerformer / RRA | 24.553 | 7.703 | 21.046 |
Compared with box-only queries on these same inputs, RRA's mean changes from 19.876% to 19.947% on AM, 5.373% to 5.207% on POMO, and 38.515% to 24.553% on Pointerformer. Pointerformer's median barely changes (7.774% → 7.703%): the tail shrinks, while typical failures persist. POMO's mean ranking reverses, as RRA (CMA-ES) rises from 5.146% to 5.373%. Fully feasible queries still expose vulnerabilities, but they can change attack strength and ranking. RRA retains higher AAG than its CMA-ES variant in all three strict comparisons. Section 4.1 and Appendix C.11 now explain these distinctions.
W3. Sample size and Pointerformer's extreme cases. The cross-solver tables now use 64 inputs for every configuration, and Table 1 uses 128 inputs and three seeds. In Table 2, Pointerformer's mean/median is 31.554%/7.895%, with 3/64 above 100%; the earlier 68.509%/7.438% pair came from 16 inputs.
For the strict-query comparison just above, RRA and RRA (CMA-ES) encounter the same extreme input, with gaps of 539.903% and 574.997%. Removing that input from all three methods gives the following sensitivity check; the main table retains all 32.
| Strict-query attack | Remaining inputs | Mean (%) | Median (%) |
|---|---|---|---|
| Adam-ES | 31 | 8.570 | 8.561 |
| RRA (CMA-ES) | 31 | 6.775 | 6.373 |
| RRA | 31 | 7.929 | 7.665 |
This makes the contribution of the tail visible without changing the primary evaluation. The revised tables report means and medians together, and the supplementary data retain every instance.
We have included the experiment code, per-instance results and figure/table reproduction data in the supplementary materials.
Thank you again for the detailed suggestions. We hope these controlled comparisons and larger evaluations resolve your concerns. We are happy to clarify any remaining issues.
Thank you for the detailed rebuttal and additional experiments. The new optimization baselines, expanded evaluations, and feasibility analyses have substantially addressed my main concerns. Although some limitations regarding methodological novelty and statistical robustness remain, I appreciate the authors' efforts and the improved empirical evidence. I have therefore decided to raise my recommendation from 2 to 3.
Response to Reviewer hB4m (1/2)
Thank you for recognizing the local formulation and for suggesting stronger evidence about the algorithmic choices. We have added the suggested zeroth-order baselines, cache controls and larger evaluations.
W1. What is the contribution, and why Adam-ES with reuse? We formalize local evaluation of a fixed solver while the input and its optimum change, and design an efficient reference-reuse procedure. ES estimates directions from perturbation scores; Adam accumulates and scales them. ES-sign ablates Adam: restoring Adam improves the median gap on all six models (Table 1). Among the four RRA cores, Adam-ES leads on five models by mean and all six by median. Route reuse lowers candidate scoring cost, while a fresh solve after each update measures the attained gap and refreshes the cache. RRA therefore finds stronger attacks than plain Adam-ES at every reported time budget on all six models. These comparisons support both the core and its combination with reuse.
The evidence now tests these choices separately. Q1. Search core: all seven Table 1 methods use 128 common inputs, three seeds and the same query budget per model. The four RRA variants share reuse and the external procedure; the replaced core covers candidate generation and search-state updates, including CMA-ES distribution adaptation. These are controlled core adaptations in the common procedure. Entries are mean B100 (%) ± seed standard deviation; Table 1 also includes Greedy, ES-sign and plain Adam-ES.
Bold / italics: best / second-best within each comparison.
Among the four RRA cores, Adam-ES has the highest mean on five models and the highest median on all six. Pointerformer illustrates why both statistics matter (medians are averaged over seeds):
The typical-input advantage supports Adam-ES as the default core. The time-budget results in our second reply show why adding reuse is useful. The broader finding is that ordinary and OOD rankings can miss local weaknesses: BQ-NCO is more accurate than POMO on both, but less robust to our attacks. Our formulation makes this difference measurable and lets future solvers be tested against renewed attacks on their complete inference procedure.
W1. Why a recent-route cache, and what does the bound establish? With Adam-ES fixed, we compare frozen, single-route and recent-route caches. Entries are AAG / median B100 (%) on 16 inputs per model.
The recent-route cache gives the highest AAG on all three models. Multiple nearby tours offer alternatives as edge lengths change, while refreshing avoids relying on the initial route throughout search.
You are right that the cost bound alone does not guarantee candidate rankings. We have made this distinction explicit in Appendices A.1–A.2 and checked the actual rankings and directions against fresh LKH on identical candidates:
These measurements directly test the information used by the optimizer: errors are small and rankings and directions remain closely aligned. Appendix C.3 and the supplementary code contain the cache controls and matched-candidate audits. Together, the core, cache and time comparisons explain the practical advantage of the combination in this routing setting.