- 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
-
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.
-
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
-
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.
-
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
-
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.
-
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.
-
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
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.
| Variant | U-50 | U-100 | U-200 | U-500 | T-50–100 | T-100–200 | T->200 |
|---|---|---|---|---|---|---|---|
| Full SPO (Top-2) | 0.212 | 0.642 | 1.274 | 3.139 | 0.408 | 0.574 | 4.040 |
| Top-1 | 0.668 | 1.005 | 1.466 | 3.230 | 0.750 | 0.950 | 3.631 |
| Mean-response | 0.576 | 1.097 | 3.388 | 7.768 | 1.223 | 2.060 | 8.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 .
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).
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).
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.
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.
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), 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).