acceptodds
Under review as a conference paper at ICLR 2027

SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization

Abstract

Large neighborhood search (LNS) relies critically on destroy and repair operators, whose effectiveness depends on both adaptation to the evolving LNS state and interaction between the two roles. We introduce Stackelberg Program Optimization (SPO), an LLM-based framework for discovering adaptive executable destroy–repair programs. SPO conditions operator decisions on a compact LNS state, allowing state-dependent behavior to emerge through program discovery, and organizes destroy–repair discovery as a Stackelberg interaction over program space that reflects their asymmetric dependency. Role-specific credits evaluate destroy programs as leaders and repair programs as conditional follower responses, guiding a coupled optimization process that combines LLM generator learning with population-based evolutionary search over programs. Experiments on the traveling salesperson problem and capacitated vehicle routing problem show that SPO outperforms strong baselines across a broad range of settings and generalizes beyond the discovery scale to larger instances and benchmark sets. Behavioral analyses further demonstrate state-dependent operator behavior and coupled destroy–repair improvement during discovery.

Primary area:
optimization
Keywords:
Large Language Models, Algorithm Discovery, Combinatorial Optimization, Large Neighborhood Search

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_4Z4GOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SPO discovers executable destroy–repair programs for large neighborhood search. It generates destroy programs first and repair programs conditionally on them, assigns role-specific rewards from LNS rollouts, and updates both the LLM generators and program populations through GRPO and evolutionary search. The resulting programs adapt their behavior using the number of iterations since the last improvement and execute without test-time LLM calls. Experiments evaluate solution quality and transfer across TSP and CVRP instance sizes and distributions.

Critical strengths
  1. Conditional destroy–repair generation and role-specific feedback provide a coherent approach to discovering interacting algorithmic components. Combining generator updates with population evolution allows both the generation policy and its program context to improve.

  2. Embedding state-dependent behavior directly in executable programs is practically appealing because adaptation does not require test-time LLM calls. The cross-scale results and state interventions provide encouraging evidence that the discovered programs exploit search history.

Critical weaknesses
  1. Appendix B.1 evaluates SPO on six instances with two rollouts per instance, whereas Appendix C states two rollouts per baseline candidate without clarifying whether the same instance-wise protocol applies. Matching generated-program counts also does not establish comparable evaluation work or total discovery cost, including cross-play and LoRA updates. Stopping and final-selection rules require clarification. These uncertainties make it difficult to separate the method’s contribution from differences in evaluation and selection budgets.

  2. The shared-credit ablation is useful, but the paper does not explain how multiple repair scores are assigned to the same destroy program or whether GRPO grouping remains unchanged. Comparisons of Top-1, Top-2, and mean-response rewards under otherwise identical settings would clarify the effect of reward aggregation. Moreover, stronger late-stage destroy–repair combinations do not by themselves distinguish pair-specific coordination from improvements in each operator’s individual quality.

Questions for authors
  1. Did all program-discovery baselines use the same six-instance, two-rollouts-per-instance evaluator as SPO? Please report realized generation and evaluation counts, total discovery costs, stopping criteria, and final-program selection rules.

  2. Could the authors extend wall-clock-matched evaluation to the LNS baselines and report final test performance across independent discovery seeds? This would clarify whether the observed advantages persist under comparable execution budgets and across independently discovered programs.

  3. In the shared-credit ablation, how are multiple repair scores assigned to one destroy program, and is GRPO grouping unchanged? Could the authors compare Top-1, Top-2, and mean-response rewards while keeping conditional generation, training, and evaluation budgets fixed? This comparison would materially affect my assessment of the claimed mechanism.

7 comments
AuthorsOpenReview ↗

Response to Reviewer 4Z4G (Part 1/4)

W1 & Q1. Evaluation Protocol, Computational Budgets, and Final Selection

We thank the reviewer for the insightful comments.

Evaluation protocol. All program-discovery methods run in our experiments (SPO, EoH, ReEvo, and FunSearch) use the same LLM backbone (Qwen3.5-9B), discovery instances, and LNS evaluator. For G-LNS, we directly use the authors' released operator programs. Each candidate pair is evaluated on six discovery instances, with two 100-step stochastic LNS rollouts per instance, yielding 12 rollouts per complete fitness evaluation. Thus, “two rollouts” in Appendix C refers to two per training instance rather than per candidate.

Discovery budgets and stopping criteria. Our original comparisons control the nominal program-generation budget. SPO follows a fixed 30-round discovery schedule, with a nominal budget of 900 destroy and 27,000 repair generations. Accordingly, EoH, ReEvo, and FunSearch are each assigned a budget of 13,950 jointly generated destroy–repair candidates, corresponding to the same nominal total of 27,900 operator programs. Within this budget, the baselines terminate early if their best-so-far discovery utility shows no improvement for 10 consecutive hours, avoiding continued search after prolonged saturation.

Realized computational costs. Table R1 summarizes the realized discovery costs of a representative SPO run on TSP.

Table R1: Realized discovery costs of SPO on TSP.

MetricCount / Time
Generated destroy / repair programs900 / 17,850
Discovery pair evaluations14,496
Recorded primary discovery rollouts173,784
Scheduled cross-play rollouts14,750
Validation rollouts450
Total discovery time17.3 h
Mean discovery time across runs≈ 22 h

Note: Some pair evaluations terminate early due to timeouts.

The reported discovery time includes program generation, rollout evaluation, cross-play, validation, and GRPO-based LoRA updates.

Comparable discovery-time budgets. While the original comparisons control the nominal program-generation budget and candidate-evaluation protocol, we agree that end-to-end discovery time provides a complementary measure of computational effort, accounting for differences in generation, evaluation, and optimization across methods.

We therefore additionally evaluate EoH, ReEvo, and FunSearch under a discovery-time budget of approximately 22 hours, corresponding to SPO's average discovery time on TSP. As shown in Table R2, SPO consistently outperforms all three baselines across the seven TSP evaluation groups, further supporting its effectiveness under comparable end-to-end discovery-time budgets.

Table R2: TSP performance under comparable offline discovery-time budgets. Final reference gaps (%; lower is better). SPO results are taken from the original submission, while each baseline is evaluated with a discovery-time budget of approximately 22 hours.

MethodU-50U-100U-200U-500T-50–100T-100–200T->200
SPO0.2120.6421.2743.1390.4080.5744.040
EoH0.5081.2173.9507.5021.3661.8357.777
ReEvo0.6711.5832.8034.5601.6442.7455.347
FunSearch1.8152.5933.3835.3241.6752.7575.893

U: Uniform instances; T: TSPLIB instances grouped by size.

Final-program selection. SPO retains the destroy–repair pair with the highest discovery utility J(D,R)J(D,R), as specified in Section 5.1 and Algorithm 1 (Appendix A.1). For EoH, ReEvo, and FunSearch, the best-so-far pair under the discovery utility is periodically evaluated on the validation set, and the pair with the highest validation score across checkpoints is selected (Appendix C).

Manuscript revision. Appendix A.3 (Lines 722–727) reports SPO's realized discovery costs and mean discovery time. Appendix C (Lines 888–899) specifies the shared evaluation protocol, nominal discovery budgets, stopping and final-selection criteria, and presents the additional comparisons under comparable discovery-time budgets (Table 3).

AuthorsOpenReview ↗

Response to Reviewer 4Z4G (Part 2/4)

W2.1 & Q3. Shared-Credit Implementation and Reward-Aggregation Ablations

Shared-credit implementation. We clarify that the shared-credit ablation refers to the w/o Stackelberg Credit variant in the original submission, which we rename w/o Stackelberg Mechanism to better reflect its scope. This variant removes the leader–follower mechanism as a whole, including conditional repair generation and role-specific credit assignment, while retaining the underlying GRPO and evolutionary optimization procedures.

Specifically, destroy and repair programs are generated independently and evaluated through full cross-play. Each destroy program receives the average utility across its evaluated repair partners, and each repair program similarly receives the average utility across its evaluated destroy partners. These aggregated program-level credits are used for both GRPO updates and population selection. GRPO retains the same role-specific generation-context grouping, with one training sample per generated program and no additional weighting by the number of pair evaluations. The remaining population-selection rules are unchanged.

Reward-aggregation ablations. We agree that a finer-grained comparison would help distinguish the contribution of leader-credit assignment from that of conditional generation. Accordingly, we evaluate Top-1, Top-2 (Full SPO), and Mean-response under otherwise identical discovery and evaluation settings.

Mean-response retains one-to-many conditional generation and pair-specific repair feedback but replaces the leader's top-L credit aggregation with the mean utility across all evaluated conditional repair responses. This isolates the contribution of emphasizing strong follower responses while keeping conditional generation unchanged.

Top-1 examines the sensitivity of leader-credit assignment to the number of follower responses used in the approximation. Both Top-1 and the default Top-2 retain the same Stackelberg credit structure, differing only in the number of highest-scoring repair responses used to compute leader credit.

All three variants follow the same 30-round discovery schedule, with the same conditional sampling configuration, GRPO training settings, evolutionary population-update rules, and rollout evaluation protocol. Final performance is evaluated using the same 500-step LNS protocol.

Table R3: TSP ablation of leader-credit aggregation. Final reference gaps (%; lower is better). Full SPO (Top-2) results are taken from the original submission.

VariantU-50U-100U-200U-500T-50–100T-100–200T->200
Full SPO (Top-2)0.2120.6421.2743.1390.4080.5744.040
Top-10.6681.0051.4663.2300.7500.9503.631
Mean-response0.5761.0973.3887.7681.2232.0608.034

U: Uniform instances; T: TSPLIB instances grouped by size.

Results and interpretation. As shown in Table R3, Top-1 and Top-2 outperform Mean-response in six and seven evaluation groups, respectively, supporting the contribution of emphasizing strong follower responses in leader-credit assignment beyond conditional generation alone. Top-2 achieves the lowest reference gaps in six of the seven groups, while Top-1 performs best on TSPLIB instances with more than 200 nodes.

Top-2 provides a balance between preserving the best-response principle underlying Stackelberg optimization and reducing sensitivity to individual high-scoring follower responses by aggregating multiple strong responses. These results support Top-2 as a reasonable default while indicating that the effectiveness of the proposed credit mechanism is not restricted to a particular choice of LL.

Manuscript revision. We have revised Section 5.5 (Lines 459–467) to clarify the scope of the w/o Stackelberg Mechanism ablation and added the Mean-response ablation to Table 2. Appendix D (Lines 958–963) details credit aggregation, GRPO grouping and weighting, and population-selection criteria, together with the controlled comparison of Top-1, Top-2, and Mean-response (Table 7).

AuthorsOpenReview ↗

Response to Reviewer 4Z4G (Part 3/4)

W2.2. Pair-Specific Operator Coordination

Operator coordination. We agree that stronger late-stage destroy–repair combinations alone cannot distinguish improvements in individual operator quality from pair-specific compatibility. To address this issue, we conduct an additional controlled cross-play analysis.

Specifically, using the final generator checkpoint and evolutionary populations from a single SPO discovery run, we generate six destroy–repair pairs through repeated conditional sampling and evaluate all 36 possible combinations on TSP50 (Figure R1). By keeping the sets of destroy and repair programs fixed and varying only their pairings, this analysis directly examines operator compatibility without confounding it with improvements in operator quality across discovery stages.

As shown in Figure R1, all six originally generated destroy–repair pairs achieve the lowest reference gap among the six repair candidates for their corresponding destroy programs. This demonstrates that conditional repair generation captures pair-specific operator compatibility, beyond improvements in individual operator quality.

Together with the improvements in combination performance throughout discovery shown in Figure 2(b2), these results support the effectiveness of SPO in discovering both high-quality individual operators and compatible destroy–repair combinations.

Figure R1: Controlled cross-play analysis of six destroy–repair pairs on TSP50. The pairs are generated through repeated conditional sampling using the final generator checkpoint and evolutionary populations from a single SPO discovery run. Each cell reports the mean reference gap (%; lower is better) of the corresponding destroy–repair combination. Highlighted diagonal cells indicate the original conditional pairings, while off-diagonal cells represent recombined operators. View Figure R1. The figure is also provided in Appendix H (Figure 4) of the revised manuscript.

Manuscript revision. We have revised the destroy–repair interaction analysis in Section 5.4 (Lines 453–456) and added a controlled cross-play analysis of pair-specific compatibility in Appendix H (Figure 4).

Reviewer_EkeZOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper proposes Stackelberg Program Optimization (SPO), an LLM-based framework for discovering executable destroy and repair programs for large neighborhood search. Destroy programs are generated first, followed by multiple repair candidates conditioned on each destroy program. Repair candidates receive their pairwise rollout scores, while a destroy candidate receives the average score of its two strongest sampled repair responses. These role-specific credits guide LoRA updates, and evolutionary populations provide context for subsequent generation. The paper distinguishes conditional repair training credits from common-panel scores used for repair population selection. Generated operators receive the number of iterations since the last improvement as a search-history signal. Experiments on TSP and CVRP report improvements over the included baselines, including G-LNS, and evaluate transfer beyond the discovery scale and to TSPLIB/CVRPLIB under a fixed final LNS iteration budget.

Critical strengths

S1. The framework addresses a meaningful dependency between destroy and repair operators.

Generating repair responses conditioned on a destroy program is well motivated by their functional dependence. The distinction between conditional training credit and common-panel repair selection also addresses a concrete comparability issue across different destroy contexts. Producing executable operators separates offline discovery from test-time optimization and makes the resulting heuristics inspectable.

S2. The reported results provide evidence of useful operators and transfer.

Table 1 includes the closely related G-LNS baseline and reports lower gaps for SPO across the tested groups, with a substantial improvement on TSP-500 (3.139% versus 6.305%). The selected program pairs are transferred to larger instances and benchmark distributions rather than rediscovered for each setting. Implementing EoH, FunSearch, and ReEvo with a common destroy–repair interface and LNS runner is also a useful experimental control. These results are encouraging, although the attribution and budget questions below limit the conclusions I can draw from them.

Critical weaknesses

W1. A relevant comparison is missing, and the incremental contribution is insufficiently isolated.

CALM already combines GRPO-based generator adaptation with evolutionary heuristic search, while G-LNS co-evolves destroy–repair operators with destroy-aware repair generation. Table 1 favorably compares SPO with G-LNS, but the contribution of SPO's one-to-many generation, role-specific credit, and search-history input still needs clearer isolation. CALM; G-LNS.

A relevant missing comparison is Li et al., “Large Language Models for Designing Heuristic Components in Vehicle Routing Problems” (IEEE CSIS-IAC 2026), which discovers destroy heuristics with a fixed neural repair backend for TSP/CVRP. Comparing both systems on common instances under matched wall-clock budgets would help assess the value of SPO's additional machinery. A fixed-repair control within SPO's runner would separately isolate the benefit of joint discovery from backend differences. Li et al..

Table 2's shared-credit ablation does not specify how multiple repair rewards are assigned to one destroy program, how training samples are grouped or weighted, or which population-selection rules remain fixed. It also covers only TSP. Top-1/top-2/mean-response and frozen-generator controls, with sampling and rollout budgets controlled, would strengthen the attribution on both tasks.

W2. Computational budgets and uncertainty are not sufficiently characterized.

Equal LNS iteration counts do not imply equal computation. Appendix C partially addresses this through approximate OR-Tools time limits, but comparable gap-versus-wall-clock curves are missing for the main methods. Time-matched comparisons, including LKH/PyVRP references, would clarify practical competitiveness. PyVRP's use to generate reference costs does not substitute for such a comparison.

Offline budgets match nominal generated-program counts, not total pair evaluations, cross-play, or validation. Appendix A.3 reports a representative SPO run with approximately 14,500 pairs and 17.3 hours, but comparable realized costs and the plateau stopping rule are missing for the other methods. These are needed to assess resource fairness.

Tables 1–2 also lack uncertainty estimates across independent discovery runs and test-time seeds. The six TSP discovery curves do not establish the robustness of every final comparison, particularly small differences such as 4.040% for SPO versus 4.106% for ALNS. Paired differences with uncertainty estimates would make these results more informative.

W3. The released code does not provide a complete reproduction path for the main experiments.

Although the archive contains substantive training/search code and example operators, it lacks essential artifacts needed to reproduce the main experiments. Both supplied configurations leave the training and validation dataset paths empty, and the TSP configuration explicitly rejects the empty training path. Neither datasets nor the data-generation scripts described in the README are included, so the documented training commands cannot run as supplied. Appendix E identifies TSP-1 and CVRP-1 as the pairs used for the main evaluation. However, the exact configurations, data-preparation steps, and commands needed to reproduce Tables 1–2 remain insufficiently documented.

Questions for authors

Q1. What are the actual computational conditions and variability behind the main comparisons?

Please clarify realized generation and rollout counts, including cross-play and validation, the baseline plateau stopping criterion, and whether “two rollouts” in Appendix C means two per training instance. Per-instance costs and runtimes, together with a representative equal-time comparison and uncertainty across independent discovery runs, would materially strengthen the performance assessment.

Q2. Can you provide the exact reproduction path with the paper?

The archive contains substantive implementation, but its dataset paths are empty, the data-generation scripts mentioned in the README are absent, and the main-table and ablation workflows are not provided. Please release the corresponding data preparation instructions, resolved configurations, code revision, and final operator pairs.

11 comments
AuthorsOpenReview ↗

Response to Reviewer EkeZ (Part 1/9)

W1.1. Core Contributions and Isolation of SPO's Key Mechanisms

Core contribution and mechanism clarification. We thank the reviewer for highlighting the need to clarify SPO's contributions. The central contribution of SPO is a Stackelberg formulation of adaptive LNS operator discovery that captures the asymmetric dependency between destroy and repair. While destroy defines the neighborhood to explore, its effectiveness depends on the quality of the corresponding repair responses. To account for this dependency, SPO couples one-to-many conditional generation with role-specific credit assignment: multiple repairs are generated conditionally for each destroy to approximate follower best responses, with leader credit aggregated over the top-L sampled responses and follower credit assigned from pair-specific utility. These credits guide both GRPO-based generator adaptation and evolutionary population updates. Beyond operator interaction, SPO discovers state-adaptive executable programs whose decisions depend on the evolving LNS state. Rather than prescribing adaptation rules or selecting among predefined operators, SPO enables state-dependent strategies to emerge through program discovery itself.

Isolation of the leader–follower mechanism. The existing w/o Stackelberg Credit variant in Section 5.5 and Table 2 (renamed w/o Stackelberg Mechanism in the revised manuscript) evaluates the contribution of the overall leader–follower mechanism by removing both conditional generation and role-specific credit assignment.

To further isolate the contribution of role-specific leader credit, we introduce a finer-grained Mean-response ablation. It retains one-to-many conditional generation and pair-specific repair feedback, but replaces the leader's top-L response aggregation with the mean utility across all evaluated conditional repairs. Thus, the two variants differ only in how leader credit is aggregated.

Table R1: Ablation of leader-credit aggregation on TSP. Final reference gaps (%; lower is better).

MethodU-50U-100U-200U-500T-50–100T-100–200T->200
SPO (Top-2)0.2120.6421.2743.1390.4080.5744.040
Mean-response0.5761.0973.3887.7681.2232.0608.034

U: Uniform instances; T: TSPLIB instances grouped by size.

As shown in Table R1, Mean-response consistently underperforms SPO across all seven TSP groups, demonstrating the effectiveness of top-L leader-credit aggregation when conditional generation is held fixed.

Contribution of search-history conditioning. The existing w/o State Conditioning ablation in Table 2 removes LNS-state conditioning while preserving the Stackelberg mechanism. The gap increases from 1.274% to 2.686% on TSP-200 and from 3.139% to 6.484% on TSP-500, supporting its contribution when transferring to larger instances.

Manuscript revision. We have revised Section 5.5 (Lines 459–467) to clarify the scope of the w/o Stackelberg Mechanism ablation and expanded Table 2 with the Mean-response ablation to isolate the contribution of leader-credit aggregation while retaining one-to-many conditional generation. We have also extended the ablations of the Stackelberg mechanism and LNS-state conditioning to CVRP, with results reported in Appendix D (Table 9).

AuthorsOpenReview ↗

Response to Reviewer EkeZ (Part 2/9)

W1.2. Comparison with Li et al. and Fixed-Repair Control

Comparison with Li et al. and fixed-repair control. Thank you for suggesting this comparison. We conduct additional experiments to compare SPO with Li et al. under comparable offline discovery budgets and equal test-time wall-clock budgets, and to examine the contribution of joint destroy–repair discovery.

Experimental setup. Li et al. discover destroy heuristics coupled with a pretrained neural repair model, whereas SPO jointly discovers executable destroy and repair programs. To provide both a system-level comparison and a controlled comparison with the same repair backend, we consider three methods:

  • SPO: jointly discovers destroy and repair programs.
  • SPO-DRHG: retains SPO's destroy discovery framework while fixing the repair operator to the pretrained DRHG model employed by Li et al.
  • EoH-DRHG: reproduces Li et al.'s EoH-based destroy discovery using the same DRHG repair backend.

We use a 22-hour offline discovery budget for the additional discovery experiments, corresponding to SPO's average discovery time on TSP. All three methods are evaluated on the same instances under identical per-instance wall-clock limits. To account for the additional neural inference costs of the DRHG repair backend, we increase the time budgets for TSP50 and TSP100 from 1 s and 5 s to 5 s and 15 s, respectively, allowing the neural repair-based methods more opportunity to perform neighborhood search. The remaining time budgets are unchanged. For SPO, we report the mean and standard deviation of final reference gaps across independent discovery runs.

Table R2: Comparison with Li et al. and the fixed-repair control under equal test-time wall-clock budgets. Final reference gaps (%; lower is better). All methods are evaluated under the same per-instance time budget within each problem group. SPO results are reported as mean ± standard deviation across five independent discovery runs.

MethodU-50U-100U-200U-500T-50–100T-100–200T->200
Time budget per instance5 s15 s35 s600 s5 s35 s600 s
SPO0.466 ± 0.1950.715 ± 0.1091.297 ± 0.1022.385 ± 0.6370.784 ± 0.2040.820 ± 0.1323.895 ± 0.936
SPO-DRHG5.7651.1732.2823.5603.0871.58912.975
EoH-DRHG0.9611.3672.3683.2552.4831.41812.062

U: Uniform instances; T: TSPLIB instances grouped by size.

Results. SPO achieves lower mean reference gaps than both SPO-DRHG and EoH-DRHG across all seven TSP evaluation groups, supporting the practical effectiveness of jointly discovered executable operators under equal execution-time budgets. With the repair backend held fixed, SPO-DRHG and EoH-DRHG exhibit mixed performance across instance groups, suggesting that the advantages of full SPO cannot be attributed solely to its destroy discovery framework. Together, these comparisons support the effectiveness of SPO's joint discovery framework, which enables both destroy and repair operators to adapt during discovery.

Manuscript revision. We have incorporated Li et al. into Section 2.2 (Lines 101–104) and extended the experimental setup in Section 5.1.1 (Line 323) to include the comparison with fixed-repair methods. Appendix C (Table 5) presents the corresponding experimental configurations, computational budgets, and results.

AuthorsOpenReview ↗

Response to Reviewer EkeZ (Part 3/9)

W1.3.1. Shared-Credit Implementation and Experimental Controls

Clarification of the Shared-Credit Ablation

We clarify that the shared-credit ablation refers to the w/o Stackelberg Credit variant in the original submission, which we rename w/o Stackelberg Mechanism to better reflect its scope. This variant removes the leader–follower mechanism as a whole, including conditional repair generation and role-specific credit assignment, while retaining the underlying GRPO and evolutionary optimization procedures.

Specifically, destroy and repair programs are generated independently and evaluated through full cross-play. Each destroy program receives the average utility across its evaluated repair partners, and each repair program similarly receives the average utility across its evaluated destroy partners. These aggregated program-level credits are used for both GRPO updates and population selection. GRPO retains the same role-specific generation-context grouping, with one training sample per generated program and no additional weighting by the number of pair evaluations. The remaining population-selection rules are unchanged.

Additional analyses. We agree that a finer-grained comparison would help distinguish the contribution of leader-credit assignment from that of conditional generation. Accordingly, we introduce a Mean-response ablation that retains one-to-many conditional generation and pair-specific repair feedback, but replaces the leader's top-L credit aggregation with the mean utility across all evaluated conditional repair responses. This isolates the contribution of emphasizing strong follower responses while keeping conditional generation unchanged.

We additionally evaluate Top-1 to examine the sensitivity of leader-credit assignment to the number of follower responses used in the approximation. Both Top-1 and the default Top-2 retain the same Stackelberg credit structure, differing only in the number of highest-scoring repair responses used to compute leader credit.

We also include Evolution only (the frozen-generator control requested by the reviewer), which keeps the LLM parameters fixed while retaining conditional generation, Stackelberg credit assignment, and evolutionary population updates.

Finally, to address the limited problem coverage of the original ablation study, we extend the w/o Stackelberg Mechanism and w/o State Conditioning ablations to CVRP.

Experimental controls. Top-1, Top-2, and Mean-response follow the same 30-round discovery schedule, with conditional sampling and rollout evaluation procedures unchanged. Evolution only is evaluated under both the same 30-round schedule and an extended 22-hour discovery budget, corresponding to SPO's average discovery time on TSP. The additional CVRP ablations follow the corresponding configurations of the original TSP ablation study. All variants use the same 500-step LNS protocol for final evaluation.

The corresponding experimental results and interpretation are provided in W1.3.2.

Manuscript revision. We have revised Section 5.5 (Lines 459–479) to clarify the Stackelberg mechanism ablation. Appendix D (Lines 958–963) details credit aggregation, GRPO grouping and weighting, and population-selection criteria.

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

This paper proposes Stackelberg Program Optimization (SPO), an LLM-based framework for discovering adaptive destroy and repair operators for large neighborhood search. It introduces search-state-conditioned executable programs and a leader–follower optimization process with role-specific credit assignment, GRPO-based generator training, and evolutionary population updates. Experiments on TSP and CVRP show consistent improvements across different instance sizes and benchmarks.

Critical strengths
  1. The motivation of this work is very clear. Modeling the asymmetric relationship between destroy and repair operators through a Stackelberg-inspired framework is intuitive and well motivated.
  2. The obtained numerical results seem strong. SPO achieves the best mean reference gaps across all reported TSP and CVRP benchmark groups, including larger problem sizes and different instance distributions.
Critical weaknesses
  1. It needs to train two LoRA adapters for each problem type. For example, the LoRA adapters for TSP and CVRP are different. This limits the application of the proposed method.
  2. I don't know if GRPO training is really needed. I would prefer an ablation study to be included, that also considers revising the prompting/memory/context of the LLM during the offline discovery. I don't see such ablation study in the paper.
Questions for authors
  1. Necessity of GRPO: How does SPO perform with frozen LLM generators while retaining conditional generation, Stackelberg credit assignment, and evolutionary population updates? What is the incremental benefit of GRPO relative to its training cost?

  2. Computational fairness: Were all LLM-based baselines evaluated with the same backbone and comparable actual discovery budgets, including rollout evaluations? How do the discovered operators compare under equal wall-clock time rather than equal LNS iteration counts?

4 comments
AuthorsOpenReview ↗

Response to Reviewer gXWX (Part 1/4)

W1. Problem-Specific LoRA Training and Generalization

In the current implementation, SPO trains separate destroy and repair LoRA adapters for each problem family (e.g., TSP and CVRP). We agree that this introduces additional training costs when extending SPO to a new problem family. However, different problem families have distinct solution structures and feasibility constraints, which naturally call for problem-specific destroy and repair operators. To support such specialization efficiently, SPO employs lightweight LoRA adapters while sharing a frozen LLM backbone, rather than training separate full models.

Importantly, this adaptation is performed only during offline program discovery. Once discovery is complete, the selected operators are standalone executable programs that can be directly applied to new instances across instance sizes and distributions, without requiring LLM inference or further adapter training. As demonstrated by our TSP and CVRP experiments, a single discovery run on small instances produces operators that generalize to larger instances and benchmark distributions. Thus, the task-specific adaptation cost is incurred once during discovery, rather than repeatedly for each new instance.

We acknowledge that the current implementation does not explore cross-task sharing of the trained adapters. Joint training or transfer of LoRA adapters across problem families is an interesting direction for future research. We thank the reviewer for this valuable suggestion.

Manuscript revision. We have clarified the problem-specific adapter setting in Section 5.1 (Lines 297–299) and Appendix A.2 (Lines 704–707), explicitly distinguished offline generator training from test-time program execution in Section 4 (Lines 149–151), and discussed joint training and cross-problem transfer of role-specific generators in Section 6 (Lines 493–495).

AuthorsOpenReview ↗

Response to Reviewer gXWX (Part 2/4)

W2 & Q1. Necessity of GRPO and Evolutionary Context Updates

Parameter adaptation versus context revision. To address the suggestion concerning prompting, memory, and context revision, we added an ablation that isolates GRPO-based parameter adaptation from evolutionary context updates. In SPO, the program populations serve as memory of discovered programs, and selected parents are incorporated into subsequent mutation and crossover prompts. Updating these populations therefore continuously revises the program context supplied to the LLM throughout discovery.

Evolution only disables GRPO-based parameter updates, keeping the LLM generators frozen throughout discovery, while retaining conditional generation, Stackelberg credit assignment, and evolutionary population updates. It follows the same 30-round discovery schedule as Full SPO, thereby isolating the effect of GRPO-based parameter adaptation while preserving population-based memory and evolving program contexts.

Benefit and discovery-time cost of GRPO. As shown in Table R1, Full SPO consistently outperforms Evolution only across all seven TSP evaluation groups under the same 30-round discovery schedule, demonstrating the additional benefit of GRPO-based parameter adaptation beyond evolutionary context updates alone. While evolution leverages previously discovered programs to guide generation through updated contexts, GRPO directly translates role-specific performance feedback into parameter updates, allowing the generators to learn from performance feedback across discovery rounds and progressively improve their generation policies, rather than relying solely on the examples provided in the current context. This complementary learning mechanism helps explain the observed improvements in program discovery.

To further assess whether the performance gains can be recovered through additional evolutionary search, we extend Evolution only to 22 hours, corresponding to the average discovery time of Full SPO on TSP. As shown in Table R1, Evolution only (extended) improves over Evolution only but still underperforms Full SPO across all seven TSP evaluation groups, further supporting the contribution of GRPO-based parameter adaptation beyond evolutionary search alone.

Table R1: Ablation of GRPO-based parameter adaptation on TSP. Final reference gaps (%; lower is better). Full SPO results are taken from the original submission, and Evolution only (extended) uses a discovery-time budget of approximately 22 hours.

VariantU-50U-100U-200U-500T-50–100T-100–200T->200
Full SPO0.2120.6421.2743.1390.4080.5744.040
Evolution only0.5931.6673.9738.4271.1812.0598.031
Evolution only (extended)0.3050.8972.8447.2861.0681.3477.241

U: Uniform instances; T: TSPLIB instances grouped by size.

Manuscript revision. We have extended Section 5.5 (Lines 475–479) to analyze the contribution of generator optimization. Appendix D (Table 8) provides the frozen-generator ablation under the same discovery-round schedule and a comparable discovery-time budget, together with the corresponding experimental settings.

AuthorsOpenReview ↗

Response to Reviewer gXWX (Part 3/4)

Q2.1. Computational Fairness in Offline Discovery

SPO and the program-discovery baselines implemented in our experiments (EoH, FunSearch, and ReEvo) use the same Qwen3.5-9B backbone and instance-wise evaluation protocol. The original comparisons use the same discovery instances, with two 100-step LNS rollouts per instance, yielding 12 rollouts across six discovery instances for each complete candidate evaluation. Using a fixed rollout budget provides a controlled basis for assessing candidate quality under comparable search effort.

We appreciate the reviewer's suggestion to further examine computational fairness in terms of actual discovery time, which complements the original evaluation-budget comparison by accounting for differences in computational overhead across discovery methods. Accordingly, we conduct additional baseline experiments with an offline discovery-time budget of approximately 22 hours, corresponding to SPO's average discovery time on TSP. As shown in Table R2, SPO's originally reported results consistently outperform EoH, ReEvo, and FunSearch across all seven TSP evaluation groups, further supporting its effectiveness under comparable computational budgets.

Table R2: TSP performance under comparable offline discovery-time budgets. Final reference gaps (%; lower is better). SPO results are taken from the original submission, and baselines are evaluated with a discovery-time budget of approximately 22 hours.

MethodU-50U-100U-200U-500T-50–100T-100–200T->200
SPO0.2120.6421.2743.1390.4080.5744.040
EoH0.5081.2173.9507.5021.3661.8357.777
ReEvo0.6711.5832.8034.5601.6442.7455.347
FunSearch1.8152.5933.3835.3241.6752.7575.893

U: Uniform instances; T: TSPLIB instances grouped by size.

Manuscript revision. We have clarified the shared backbone and discovery evaluation protocol in Section 5.1 (Lines 297–303) and Appendix C (Lines 888–896), supplemented the runtime statistics in Appendix A.3 (Lines 722–727), and added the discovery-time comparison in Appendix C (Table 3), with the main findings summarized in Section 5.2 (Lines 375–378).

AuthorsOpenReview ↗

Response to Reviewer gXWX (Part 4/4)

Q2.2. Computational Fairness in Test-Time Evaluation

The original test-time evaluation adopts a fixed LNS iteration budget, consistent with established evaluation practices in classical ALNS [1], neural adaptive LNS [2], and LLM-based LNS [3]. This setting provides a controlled comparison of operator effectiveness under the same number of search steps.

We appreciate the reviewer's suggestion to additionally consider equal wall-clock budgets, which provide a complementary perspective by accounting for differences in per-iteration computational costs.

We therefore evaluate the discovered operators under equal per-instance wall-clock budgets rather than fixed LNS iteration counts. As shown in Table R3, SPO achieves the lowest mean reference gaps across all seven TSP evaluation groups. We also report performance variability across independently discovered destroy–repair pairs. These results further support the effectiveness of SPO under comparable execution-time budgets.

Table R3: TSP performance under equal test-time wall-clock budgets. Final reference gaps (%; lower is better). All methods are evaluated under the same per-instance time budget within each problem group. SPO results are reported as mean ± standard deviation across five independent discovery runs.

MethodU-50U-100U-200U-500T-50–100T-100–200T->200
Time budget1 s5 s35 s600 s5 s35 s600 s
ALNS2.6262.1993.5654.3471.8731.9906.836
EoH1.3484.1588.33314.8392.9464.04712.062
FunSearch0.7921.2862.0654.6131.0031.2574.969
ReEvo1.4093.4286.01510.7422.0062.88710.762
G-LNS0.8411.7913.0486.5701.9141.1946.338
SPO0.507 ± 0.2490.792 ± 0.1481.297 ± 0.1022.385 ± 0.6370.784 ± 0.2040.820 ± 0.1323.895 ± 0.936

U: Uniform instances; T: TSPLIB instances grouped by size.

Manuscript revision. We have added the equal test-time wall-clock comparison to Appendix C (Table 4) and summarized its results in Section 5.2 (Lines 375–378).

References

[1] Ropke, S., and Pisinger, D. (2006). An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4), 455–472.

[2] Johnn, S.-N., Darvariu, V.-A., Handl, J., and Kalcsics, J. (2024). A Graph Reinforcement Learning Framework for Neural Adaptive Large Neighbourhood Search. Computers & Operations Research, 172, 106791.

[3] Zhao, B., Wang, H., and Zeng, L. (2026). G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design. arXiv preprint, arXiv:2602.08253.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.