acceptodds
Under review as a conference paper at ICLR 2027

Exposing Local Vulnerabilities in Neural Routing Solvers with an Efficient Black-Box Attack

Abstract

Neural routing solvers combine high solution quality with fast inference, yet a simple greedy probing attack exposes substantial local vulnerabilities: bounded coordinate perturbations subject to geometric constraints raise the mean solution gaps of representative neural solvers to roughly 4–35 times their original values on TSP instances with 100 nodes. To find stronger adversarial instances efficiently, we propose the **R**eference-Route **R**euse **A**ttack (RRA), a constrained black-box attack that maximizes the solution gap. Its Adam-ES update combines evolution strategies with adaptive momentum to aggregate candidate feedback within and across iterations. RRA further exploits local coordinate changes to reuse recent reference routes for candidate scoring, refreshing the reference after each update. At the same model-query budget, RRA increases the observed mean best-found gap over the greedy attack by 20–31% across three solvers on these instances. Relative to its full-reference variant, it reduces search-time reference solves by 96.94%, yielding 2.37–2.52× speedups on this TSP benchmark and 6.9–12.2× on CVRP with 50 customers. Fine-tuning a neural solver on these adversarial instances lowers its gaps under renewed fixed-budget attacks, linking local vulnerability analysis to model improvement.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Neural Combinatorial Optimization, Adversarial Robustness, Black-Box Attacks

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_hB4mOpenReview ↗
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
  1. 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.
  2. The paper provides relatively broad experimental coverage.
  3. The manuscript is generally well organized, progressing from the attack formulation and optimization strategy to reference-route reuse and empirical evaluation.
Critical weaknesses
  1. 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.
  2. 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%.
  3. 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
  1. 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?
  2. 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
AuthorsOpenReview ↗

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.

AttackAMPOMOPointerformerICAMAMDKDMDAM
RRA (SPSA)9.70 ± 0.141.87 ± 0.0333.41 ± 0.805.97 ± 0.024.77 ± 0.049.95 ± 0.05
RRA (ZO-AdaMM)14.42 ± 0.193.33 ± 0.0829.54 ± 2.638.89 ± 0.027.39 ± 0.0613.81 ± 0.12
RRA (CMA-ES)19.58 ± 0.135.15 ± 0.0626.73 ± 2.499.76 ± 0.077.96 ± 0.0515.30 ± 0.07
RRA20.14 ± 0.285.42 ± 0.1127.78 ± 3.6310.41 ± 0.148.57 ± 0.0516.01 ± 0.08

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):

AttackMeanMedian
RRA (SPSA)33.4112.736
RRA (ZO-AdaMM)29.5365.114
RRA (CMA-ES)26.7297.195
RRA27.7768.122

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.

SolverFrozen initial routeLatest routeLatest 32 routes
AM15.202 / 17.86216.130 / 18.97916.988 / 20.697
POMO3.338 / 5.2963.661 / 4.9123.874 / 5.742
Pointerformer37.421 / 8.17634.571 / 9.15556.495 / 7.438

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:

SolverGap MAE (pp)Rank correlationDirection cosine
AM0.4390.9730.983
POMO0.3280.8320.828
Pointerformer0.4100.8910.899

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.

AuthorsOpenReview ↗

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.

Solver100 s200 s300 s
AM14.866 / 8.78917.660 / 11.68819.256 / 13.711
POMO2.953 / 1.4204.121 / 2.2424.826 / 2.993
Pointerformer14.890 / 4.53323.234 / 7.84627.090 / 9.262
ICAM10.319 / 5.57110.415 / 6.86110.415 / 7.742
AMDKD-POMO7.612 / 4.3428.496 / 5.5118.572 / 6.249
MDAM15.004 / 9.27816.014 / 11.04116.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 / attackMean B100Median B100AAG
AM / Adam-ES19.41518.84616.086
AM / RRA (CMA-ES)19.61619.12114.343
AM / RRA19.94719.68616.329
POMO / Adam-ES6.3456.4074.806
POMO / RRA (CMA-ES)5.3735.7433.375
POMO / RRA5.2074.9723.693
Pointerformer / Adam-ES8.9018.5776.584
Pointerformer / RRA (CMA-ES)24.5326.41316.791
Pointerformer / RRA24.5537.70321.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 attackRemaining inputsMean (%)Median (%)
Adam-ES318.5708.561
RRA (CMA-ES)316.7756.373
RRA317.9297.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.

Reviewer_VgKzOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes adversarial attacks against neural solvers for TSP and CVRP. While many existing methods focus on improving solver performance, this paper investigates their vulnerabilities, with the aim of improving their robustness to small perturbations. The proposed RRA method employs black-box attacks to aggregate update directions from random perturbations, using a reference mechanism to improve attack efficiency. Finally, the paper conducts preliminary experiments to investigate whether the adversarially perturbed instances can improve the solving performance of neural solvers.

Critical strengths

This research topic is promising, as many existing studies focus on improving in-distribution performance without considering the robustness of neural solvers to potential perturbations. The proposed black-box attack is technically sound, although it still relies on LKH3 solutions. The reference mechanism improves attack efficiency, and the experimental results demonstrate the effectiveness of the proposed method and its key components. The paper also included many neural solvers to attack, though some of them are old.

Critical weaknesses

The writing is not good enough. Some texts in section 5 are hard to understand. It assumes the base domain knowledge from readers but it’s hard to read for broad readers. The experiment for figure 1 is hard to understand without giving the details of implementation. The experiment compared the method with Greedy without advanced baseline models and neural solvers. In table 2, there is no trend or clear performance file to see which neural solver is hard to attack, and it has no insightful conclusions or analysis. Further, the results of table 3 are only preliminary about how the performance can be improved and reattacked but still, I can not find clear conclusions that are useful to be inherited to future work. The results are not surprising: the method is built from Greedy and outperforms it. Reference improves the efficiency by using less solver calls.

Questions for authors

What is the main conclusion from appendix A.3? On page 3, it is claimed that the increase G_T will be reported but I didn't see it in experiments. Any problem with it? Why is the sum of squared marginal 2-Wasserstein distances used? How can the method extend to attack non-coordinate attributes? Can you give more analysis and a clear conclusion in section 5.6?

2 comments
AuthorsOpenReview ↗

Response to Reviewer VgKz (1/2)

Thank you for pointing out where the findings were unclear. We have rewritten Section 5 and added stronger comparisons.

What does this work contribute? We formulate local robustness with changing reference costs and design an efficient evaluation procedure. RRA combines Adam-ES with feasible-route reuse: its default core achieves the highest mean on five models and median on all six, and reuse strengthens attacks over plain Adam-ES at every reported time budget.

Stronger baselines. Following your and Reviewer hB4m's suggestions, we adapted SPSA, ZO-AdaMM and CMA-ES to our framework, sharing reuse, constraints and query budgets. Table 1 compares seven methods on 128 common inputs and three seeds per model. Below, mean / median B100 (%) are averaged over seeds; higher is stronger.

Bold / italics: best / second-best within each comparison.

SolverRRA (SPSA)RRA (ZO-AdaMM)RRA (CMA-ES)RRA
AM9.697 / 9.48614.420 / 13.86919.577 / 19.38120.142 / 19.605
POMO1.872 / 1.8023.326 / 3.2085.154 / 5.2095.424 / 5.337
Pointerformer33.411 / 2.73629.536 / 5.11426.729 / 7.19527.776 / 8.122
ICAM5.970 / 5.6778.886 / 8.6239.756 / 9.50510.415 / 10.117
AMDKD-POMO4.774 / 4.6697.394 / 7.3717.958 / 8.0008.572 / 8.534
MDAM9.953 / 9.78513.809 / 13.62615.298 / 15.11916.014 / 15.893

Among these variants, Adam-ES leads in mean on five models and median on all six.

Does reuse yield stronger attacks within the same time? Yes. Cells give RRA / plain Adam-ES mean gap (%), with time per 16-input batch and the same 128 inputs and three seeds:

Solver100 s200 s300 s
AM14.866 / 8.78917.660 / 11.68819.256 / 13.711
POMO2.953 / 1.4204.121 / 2.2424.826 / 2.993
Pointerformer14.890 / 4.53323.234 / 7.84627.090 / 9.262
ICAM10.319 / 5.57110.415 / 6.86110.415 / 7.742
AMDKD-POMO7.612 / 4.3428.496 / 5.5118.572 / 6.249
MDAM15.004 / 9.27816.014 / 11.04116.014 / 12.106

The advantage holds on all six models at all three budgets. Figure 3 shows all seven time curves; Table B3 gives these values.

Table 2: what do the cross-solver results reveal? All 39 TSP/CVRP configurations now use 64 instances. Section 5.3 explains four findings.

Accuracy can hide sensitivity. BQ-NCO beats POMO on Uniform and OOD, yet its attacked gap is larger (6.394% vs 5.357%). Their initial gaps differ by just 0.053 percentage points; attack-induced increases differ by 0.984 points. The reversed ranking reflects sensitivity to perturbations, beyond initial solution quality.

Refinement reduces that sensitivity. Directly attacking ten-step LEHD/SIL yields 63.8%/70.6% smaller final gaps than attacking their base solvers. After subtracting the starting errors, the attack-induced increases still fall by 63.4%/68.3%. Refinement therefore helps beyond improving clean solutions.

High averages can conceal different failures. Pointerformer has a 31.554% mean but a 7.895% median, with 3/64 above 100%; PolyNet has a 60.740% median. The former calls attention to extreme cases, the latter to widespread degradation. Reporting both statistics identifies what needs improving.

The observed mean ordering changes with the attack budget.

SolverB25 (%)B100 (%)AAG (%)
DGL12.81317.27614.190
ELG10.25719.12613.102

DGL has the lower final gap but is more exposed early in search. Figure C1 shows this TSP example; F1 gives the CVRP budget profiles. These findings give future evaluations concrete targets: local sensitivity, tail failures, and resilience across budgets. The solvers include recent URS [1], L2R [2], CaR [3] and ICAM [4].

Table 3: are local failures just OOD errors? The same 2-opt repair leaves a clear difference. Medians (%) use the original OOD and 16-input adversarial diagnostic sets:

SolverOOD median before → afterAdversarial median before → after
AM8.490 → 4.58920.697 → 12.016
POMO1.212 → 0.8575.742 → 5.687
Pointerformer2.225 → 1.4897.438 → 5.788

Repair leaves much larger errors on nearby adversarial inputs, so OOD testing alone misses this vulnerability. From the same 16 originals, ten-step LEHD/SIL repair base-model attacks to 0.446%/1.638%; attacks targeting the ten-step solvers generate new inputs with gaps of 4.526%/9.409%. Future defenses should be tested by attacking the complete inference procedure anew. Section 5.5 now makes this conclusion explicit.

AuthorsOpenReview ↗

Response to Reviewer VgKz (2/2)

Section 5.6: what is the value of adversarial examples? We compare adversarial libraries against unperturbed and random-noise controls under shared training settings. Each trained POMO model is attacked with RRA and RRA (CMA-ES), each on the same 256 new inputs. Mean gaps (%) are lower-is-better.

Bold / italics: best / second-best within each comparison.

Library (originals)RRARRA (CMA-ES)UniformOOD
Original POMO5.4105.1880.3572.509
Unperturbed (784)5.6705.4490.4142.591
Random noise (784)5.7875.5430.4082.616
AM→POMO (784)5.2315.2670.3832.585
Adam-ES (128)4.7174.7810.3632.615
Adam-ES (256)4.4684.6620.3512.633
RRA (128)4.6404.7710.3612.562
RRA (256)4.3974.6800.3542.574
RRA (784)4.4234.5660.3602.600

RRA (784) reduces re-attack gaps by 18.25%/11.98% and beats both non-adversarial controls. Local robustness improves while Uniform changes little and OOD does not improve, supporting our distinction between these evaluation axes. AM→POMO helps against RRA but worsens resistance to RRA (CMA-ES). Section 5.6 explains these findings; Appendix D gives configuration selection.

Can the attack change non-coordinate attributes? Yes. We added two tests with 32 common inputs per setting.

For CVRP demands, coordinates and capacity stay fixed; continuous capacity-normalized demands change by at most 0.03. Both attacks use fresh HGS references because changed demands can invalidate old routes. Mean gaps (%) are:

SolverCleanCMA-ESAdam-ES
ICAM2.3977.8068.797
AMDKD-POMO2.1946.7706.844
MDAM5.32912.40312.830

For ATSP directed edge weights, we preserve the directed metric and bound relative changes by 3% or 10%. Old visiting orders remain feasible, so both RRA variants use the same route cache. Mean gaps (%) are:

Solver / edge boundCleanAdam-ESRRA (CMA-ES)RRA
ICAM / 3%12.55918.75219.13218.772
ICAM / 10%12.55922.08421.88121.974
MatNet / 3%1.5154.2844.2874.326
MatNet / 10%1.5155.9685.4016.306

The two reuse variants have mean absolute reference-cost errors of 0.008–0.011%. These experiments identify when the extension works: reuse applies when the changed attributes preserve solution feasibility; otherwise references must be recomputed or repaired and checked. Appendices F.4 and G present these tests; Figure G1 adds ATSP gap-versus-time curves for all three methods.

What does Appendix A.3 establish? We use LKH as a fast proxy for exact TSP solutions and compare it with Concorde to check that the attack is not exploiting a weak reference. Their costs agree to numerical precision on the checked clean and attacked instances, using the original coordinates. The measured gaps therefore remain unchanged under this reference check. Section 5.4 now states the conclusion directly.

The missing gain and the Wasserstein penalty. Thank you for catching the missing column. Tables 2 and F1 now report the defined gain, ΔG_T = B_T − B_0. At T = 100, the AM/POMO/Pointerformer gains are 15.070/5.083/31.028 percentage points. The squared marginal 2-Wasserstein penalty discourages distribution drift: sorting makes it inexpensive, and squaring penalizes larger changes more strongly. It guides search alongside the hard constraints; reported gaps use route costs alone. Section 4.1 now explains this beside Eq. (5).

Figure 1 and readability. The caption now identifies the Table 1 Greedy setting and the POMO example's gap, 0.2409% → 4.8903%. Section 5.1 introduces the questions addressed by the experiments, and Section 5 has been reorganized to make the findings easier to follow.

We have included the experiment code, per-instance results and figure/table reproduction data in the supplementary materials.

Thank you again for helping us make the paper clearer. We hope the stronger comparisons and clearer conclusions address your concerns. We welcome further questions or suggestions for improving the paper.

References for both replies:

[1] Zhou et al. URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization. ICML 2026.

[2] Zhou et al. Learning to Reduce Search Space for Generalizable Neural Routing Solver. KDD 2026.

[3] Bi et al. Towards Efficient Constraint Handling in Neural Solvers for Routing Problems. ICLR 2026.

[4] Zhou et al. Instance-Conditioned Adaptation for Large-Scale Generalization of Neural Routing Solver. IEEE TITS 2026.

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

This paper studies the local robustness of neural routing solvers for TSP and CVRP. The authors argue that average in-distribution quality and OOD generalization say nothing about reliability under small perturbations of node coordinates, and show that even a simple greedy probing attack inflates solver gaps to roughly 4 to 35 times their original values while keeping both per-node displacement and the overall point geometry bounded. Because perturbing coordinates also moves the optimum, the attack maximizes the gap to a tracked reference solution rather than to a fixed one, which makes each candidate evaluation require a reference solve. They propose RRA, which addresses this cost in two ways: an Adam-ES update that estimates a search direction from all candidate scores and accumulates it across iterations, and a cache of recent reference routes that remain feasible under small coordinate changes and can therefore score candidates without re-solving. Experiments cover 24 TSP and 15 CVRP solver configurations, recovery through local search, learned refinement, diffusion budgets and symmetry views, attacks on solver ensembles, and fine-tuning a solver on the generated adversarial instances.

Critical strengths
  1. The question is well posed and the central finding does not depend on the proposed method. The vulnerability is established by a greedy probing attack, the simplest construction in the paper. Adding local robustness as a third evaluation axis is a reasonable angle, and Table 2 gives a concrete dissociation: BQ-NCO beats POMO on Uniform yet reaches a larger attacked gap.
  2. Empirical coverage is thorough: 24 TSP and 15 CVRP configurations spanning construction, diffusion, learned refinement, mixture-of-experts and construction–refinement hybrids; three sizes; accuracy reported on Uniform, eight OOD distributions and TSPLIB alongside the attacked gaps. Recovery is probed through four independent mechanisms (2-opt, refinement budgets, diffusion budgets, symmetry views), ensembles are attacked with two objectives, and sensitivity covers ε, candidate count, step size, noise and penalty weight.
  3. The analysis anticipates the obvious objections and runs the controls rather than asserting. The reference solver's optimality is certified against Concorde, and a model-blind baseline matched on reference length rules out the possibility that the gap increase merely reflects shortened reference tours. The reuse approximation is bounded analytically and then measured empirically.
  4. Reproducibility is strong: full hyperparameters, pseudocode, per-solver deployment configurations, dataset generators, exact query accounting, code with LKH/HGS adapters, and materials to rebuild the main tables without model inference.
Critical weaknesses
  1. The experiments rest on a single attack seed. This matters most for Pointerformer, whose mean is driven by a tail, and for Table 2 and most of the appendix diagnostics, which use a single small block of instances from one run. A handful of seeds on the main comparison would substantially strengthen the claims.
  2. "Linking local vulnerability analysis to model improvement" is over-claimed. The efficiency contribution is real and exactly verifiable, and it does buy a larger adversarial library at a fixed generation budget. But the resulting gain is confined to re-attack resistance on the same model: in Table 5 the untrained model has the best OOD gap and no training condition improves on it, while the in-distribution gain is marginal. The paired comparison between the two adversarial libraries spans zero, so the throughput advantage does not yield a better model. There is also no test of whether instances generated against one solver help a different solver. I would narrow this contribution to local-robustness fine-tuning of the attacked model.
Questions for authors

What structural property of the perturbed instances makes them simultaneously easier for the classical heuristic and harder for the neural solver? Appendix C.2 shows LKH's effort dropping as the attack progresses, and in an order that exactly inverses the three update rules' attack strength

3 comments
AuthorsOpenReview ↗

Response to Reviewer V2gi (1/2)

Thank you for recognizing local robustness as a useful evaluation axis and the breadth of our controls. Your comments helped us strengthen the statistical evidence and explain what the classical–neural discrepancy means.

W1. Stability across seeds and inputs. We have rerun the full Table 1 comparison with three seeds and 128 common inputs per model. Following Reviewer hB4m's baseline suggestion, we also compare SPSA, ZO-AdaMM and CMA-ES within RRA, replacing the Adam-ES core while keeping the external procedure fixed. Below are mean B100 (%) ± seed standard deviation; higher is stronger.

Bold / italics: best / second-best within each comparison.

SolverRRA (SPSA)RRA (ZO-AdaMM)RRA (CMA-ES)RRA
AM9.70 ± 0.1414.42 ± 0.1919.58 ± 0.1320.14 ± 0.28
POMO1.87 ± 0.033.33 ± 0.085.15 ± 0.065.42 ± 0.11
Pointerformer33.41 ± 0.8029.54 ± 2.6326.73 ± 2.4927.78 ± 3.63
ICAM5.97 ± 0.028.89 ± 0.029.76 ± 0.0710.41 ± 0.14
AMDKD-POMO4.77 ± 0.047.39 ± 0.067.96 ± 0.058.57 ± 0.05
MDAM9.95 ± 0.0513.81 ± 0.1215.30 ± 0.0716.01 ± 0.08

Among the four RRA cores, Adam-ES gives the highest mean on five models and the highest median on all six. Pointerformer's RRA mean/median is 27.776%/8.122%; Table 1 reports both to distinguish typical failures from the long tail. Appendix A.4 gives seed-level results and paired intervals.

What changes with 64 rather than 16 inputs? We expanded all 24 TSP and 15 CVRP configurations. In 28/39, the mean changes by less than 1 percentage point. GLOP and CaR-POMO retain the lowest observed mean gaps among the TSP/CVRP configurations. The main changes concern tails:

SolverMean, 16 → 64 (%)Median, 16 → 64 (%)
TSP Pointerformer68.509 → 31.5547.438 → 7.895
CVRP Sym-NCO17.912 → 22.56613.417 → 13.923

The means shift more than the medians: expansion changes the estimated tail contribution, while typical local failures persist. Appendix C.1 now explains this distinction.

Q. Why does stronger attack coincide with less LKH work? The inverse ordering persists when we replay the same POMO inputs with one CPU worker:

Update ruleFinal LKH CPU time (s)Finishes in ascent phase
ES-sign0.3095.5%
Greedy0.15221.9%
Adam-ES0.08547.7%

All start near 0.38 seconds. Thus the stronger neural attack increasingly finds inputs on which LKH finishes with little search. Meanwhile, POMO's excess tour length grows from 0.0227 to 0.3704.

We checked whether shorter references alone explain this effect. Model-blind shortening and Adam-ES produce almost identical reference lengths after matching, but very different neural gaps:

AttackReference lengthPOMO gap (%)
Model-blind shortening7.4450.232
Adam-ES7.4485.219

Fixing the denominator during search gives a similar conclusion: the final POMO gap is 4.77%, versus 5.30% with the original objective. Concorde checks also confirm that reduced LKH effort does not sacrifice reference quality.

How do the coordinates differ from Uniform inputs? In the 128-input POMO geometry audit (seed 42), the returned attacks retain similar coordinate marginals, with small changes in local spacing:

InputsMarginal W1 to UniformMean nearest-neighbor distance
Original Uniform0.002120.05192
Adam-ES attacks0.002080.05101
RRA attacks0.002220.05143

W1 averages the x/y marginal distances after pooling the nodes. The centroid is preserved, while node positions change locally. The controls show different sensitivities of learned routing and classical search, but do not yet identify the geometric pattern causing the failures. Appendix C.2 now presents these measurements and the explanation together. We hope future work can identify failure patterns specific to neural solvers and use them as priors for faster adversarial search.

AuthorsOpenReview ↗

Response to Reviewer V2gi (2/2)

W2. What does adversarial training improve? We agree that the original claim was too broad. The revised Table 5 separates local re-attack resistance from ordinary quality and cross-solver transfer. It includes both RRA and RRA (CMA-ES) re-attacks, matched-size Adam-ES libraries, non-adversarial controls and AM→POMO training on AM-generated examples.

Under the same cumulative six-hour generation budget, RRA supplies 784 originals and full-reference Adam-ES supplies 256. Training settings are shared across libraries. Each attack evaluates the same 256 new test inputs. Mean gaps (%) are lower-is-better.

Bold / italics: best / second-best within each comparison.

Library (originals)RRARRA (CMA-ES)UniformOOD
Original POMO5.4105.1880.3572.509
Unperturbed (784)5.6705.4490.4142.591
Random noise (784)5.7875.5430.4082.616
AM→POMO (784)5.2315.2670.3832.585
Adam-ES (128)4.7174.7810.3632.615
Adam-ES (256)4.4684.6620.3512.633
RRA (128)4.6404.7710.3612.562
RRA (256)4.3974.6800.3542.574
RRA (784)4.4234.5660.3602.600

RRA (784) reduces the two re-attack gaps by 18.25% and 11.98%, and improves over both the unperturbed and random-noise controls. The benefit therefore comes from the adversarial examples, beyond additional updates or noise.

Increasing the RRA library from 128 to 784 improves both re-attack means. The RRA results at 256 and 784 are close, while resistance to RRA (CMA-ES) improves at each size. Figure 3 separately shows stronger attacks at equal recorded search time. The six-hour budget sums generation time across resumed runs.

Local robustness, clean accuracy and OOD generalization respond differently to training. The local gains occur with small Uniform differences and no improvement in the original OOD mean, consistent with our distinction between these evaluation axes. AM→POMO slightly improves resistance to RRA but worsens resistance to RRA (CMA-ES); examples generated against POMO improve resistance to both. Section 5.6 and the abstract now emphasize this local training value; Appendix D gives the controls, development-set selection and paired statistics.

We have included the experiment code, per-instance results and figure/table reproduction data in the supplementary materials.

Thank you again for your careful review. We hope these additions address your concerns and strengthen your confidence in the contribution. We would be happy to clarify any remaining points.

Thanks for the author's response. I decide to maintain my current rating score for this paper.

Comments on the paper

1 comment
Area_Chair_HyCCOpenReview ↗

Author-Reviewer discussion reminder

Dear Reviewers,

Please spend some time reading the rebuttal and indicate whether the authors have clarified your concerns. Please do so before Nov 18 AoE to give the authors the chance to further clarify.

Best,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.