acceptodds
Under review as a conference paper at ICLR 2027

When Does Learned Move Selection Help Local Search? The Role of Descent

Abstract

Iterated local search (ILS) runs a best-improvement descent after each perturbation, which turns even random perturbations into an effective search. We find that this descent helps random move selection far more than learned local-search policies for combinatorial optimization, so that in five of the six methods we study the learned policy loses most or all of its advantage over random selection once descent is added. We call the number of descent steps run after each applied move the commit depth (cd). In a controlled job-shop study, a random-forest scorer beats random selection by 220 makespan units at cd=1 but trails it by 126 with descent to a local optimum, because a scorer trained on the outcome after one descent step prefers moves that change the solution least. In six published methods, with each selector at its best commit depth, the advantage of the learned selector shrinks by a factor of 34 to 69 in ECO-DQN and 42 in NeuOpt, and disappears or reverses in DACT, L2S, and a learned SAT heuristic that we trained. Where the published policy is still ahead of random selection with descent, fine-tuning it with descent in the training loop helps: the fine-tuned ECO-DQN and NeuOpt policies beat four baselines at equal wall-clock time on the instance sizes used for fine-tuning, and in ECO-DQN they close 45 to 87% of the published policy's remaining gap to the best known cut by selecting flips from which descent finds larger improvements. Where the published policy is not ahead (DACT, MIStar, L2S), the fine-tuned policy does not beat random selection with descent. Whether the published policy is ahead can be checked with evaluation runs alone; of the fine-tuning outcomes we recorded as predictions before the runs, two held and a third held in part. We recommend reporting learned-versus-random comparisons with and without descent, with the same number of evaluated candidates per step.

Primary area:
optimization
Keywords:
learned local search, iterated local search, combinatorial optimization, evaluation methodology, fine-tuning, commit depth

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_9qAaOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper investigates whether learned move-selection policies genuinely outperform random selection when both are integrated into local-search algorithms with descent. It introduces commit depth (cd), which controls the number of descent steps performed after each selected move, and systematically evaluates how descent affects the relative performance of learned and random selectors. The main contribution is demonstrating that descent substantially reduces the apparent advantage of learned move selection. In a controlled job-shop scheduling experiment, the learned selector’s advantage over random selection shrinks as descent depth increases and reverses when descent continues to a local optimum. The authors extend this analysis to six published learned local-search methods across several combinatorial optimisation problems, finding that the advantage of five methods shrinks substantially or disappears. They also identify a candidate-budget confound in MIStar: its apparent advantage largely disappears when random selection evaluates the same number of candidates. Finally, the authors investigate fine-tuning policies with descent included in the training loop. Fine-tuning improves performance over random-plus-descent baselines for ECO-DQN and NeuOpt, but not consistently for DACT, MIStar, or L2S. Validation includes controlled experiments, statistical analyses, robustness checks across instances and search budgets, comparisons at equal wall-clock time, and evaluations of published methods. Overall, the paper provides empirical evidence that learned local-search methods should be evaluated against computationally matched random baselines within the complete search pipeline, rather than in isolation.

Critical strengths
  1. Identifies a genuinely important evaluation problem: a learned move selector should not be evaluated independently of the descent mechanism surrounding it.
  2. The controlled JSSP experiment is quite convincing. The authors hold the search framework fixed and systematically change only the commit depth.
Critical weaknesses
  1. The central causal explanation is demonstrated most strongly on JSSP. It does not establish equally clearly that the same “conservative move” mechanism causes the shrinkage in other domains like DACT, NeuOpt
  2. Fine-tuning evidence is relatively small - at most 8.7 hours of GPU per run; 2 seeds per method are far from convincing.
Questions for authors
  1. Can the authors provide evidence that the same mechanism explains the performance collapse for DACT, NeuOpt, ECO-DQN, L2S, MIStar, and SAT?
  2. How sensitive are the conclusions to the choice of neighbourhood and descent operator? Could a learned policy retain a substantial advantage if descent uses a different neighbourhood, randomised descent or a cheaper local improvement model?
Reviewer_LQaoOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this paper, the authors propose a critical study of the performance of methods that learn heuristics compared with random approximations. Specifically, the authors propose a local search scheme in which, in a first step, a move is made – either guided by a learnt model or chosen at random – followed by cd best-improvement steps of local search. The authors indicate that in the vast majority of the cases studied (a significant number of combinatorial optimisation problems and benchmark NCO models in each instance), the initial use of the model to determine a move is outperformed by the random option as the number of cd steps increases. The study is comprehensive, and the results presented are extensive and rigorous. It is a very interesting paper to read and well worth the effort.

Critical strengths
  • This paper proposes a self-critical assessment of the performance of NCO models (learned heuristics) and draws some simple comparisons with classical strategies from the field of meta-heuristics. Of course, the paper does not invalidate the entire body of literature on NCOs, but it does provide the community with much food for thought. Papers of this kind aim to start the discussions that are needed for science to progress.
  • I enjoyed reading the paper.
Critical weaknesses
  • The presentation of the work is poor, both in the abstract and in the introduction. None of the terminology used – ‘move’, ‘descent’, ‘perturbation’, ‘action’ and ‘scorer’ – is at all clear. It is only when Algorithm 1 is referred to in Section 2 that some light begins to be shed on the matter, but even then, not entirely. And this is a problem. Some content related to the Neural Improvement setting in NCO could be helpful. Actually, the use of ILS is in some sense weird. Algorithm 1 does not include the ILS since it does not include a loop within it.
  • Something is missing, and I think it’s motivation. The paper presents very interesting evidence, but once you’ve read it and reached the conclusion, you find yourself wondering… what's next? Where should we be heading?
Questions for authors

Reformulating the weaknesses above:

  • In general, it is well known that the benefit of running a neural improvement method instead of a local search is in saving computational time [Garmendia et al. 2023 TNNLS], so to me the motivation of the work lacks something. In my view, the results are not surprising, so could you extend the motivation somehow that sheds some light for the future.
  • Why the local search scheme adopted in Algorithm 1 is the adequate one? Why not others?
Reviewer_SJV5OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper investigates learned local search policies for classical combinatorial optimization problems like TSP, Max-Cut, SAT, or job scheduling. Interestingly, despite what is typically assumed in TCS, the learned baseline policies are allowed to take steps that yield a locally worse objective value than that of the current solution. Rather, these steps of the baseline heuristics are interpreted as perturbations of the current solution and then coupled with a pivot rule that always takes the locally best improvement, called descent, within a framework called iterative local search (ILS). The paper provides a systematic investigation of how commit depth, i.e., the number of descent steps inserted into the loop, influences differences in convergence rates within ILS. The main question is then whether learned policies still have an advantage over randomly selected moves when effectively acting as perturbations in the ILS loop. The main findings of the paper are that: Coupling a learned local search policy with descent steps noticeably increases performance.

  1. The advantage of a learned policy compared to random selection diminishes in the ILS loop.
  2. Training a policy with descent can increase its performance.
  3. The authors conduct experiments with six state-of-the-art policy-learning methods across several combinatorial optimization problems. Further experiments show that fine-tuning with descent yields additional gains for ECO-DQN and NeuOpt, while the other three fine-tuned methods remain unable to outperform random selection with descent.
Critical strengths

The paper asks relevant and natural questions about local search policies and offers a broad investigation of current heuristics for relevant problems like SAT, routing, TSP, scheduling, etc.

The authors implement some controls to better pinpoint where the measured improvement of the heuristic coupled with descent is coming from, e.g., through tabu rules that prevent descent from immediately undoing a move made by the learned policy, or by providing baseline training without descent for comparison.

The authors make the decisions, restrictions, and limitations of their experiments quite transparent and document the experiments well. Overall, the strength of the paper lies in the combination of a broad empirical investigation, selected experimental controls, and some diagnostics that aim to explain where the concrete performance of the investigated search procedures comes from. This might be useful for further benchmarks and the training of policies.

Critical weaknesses

The combination of a random perturbation with descent is the classical ILS loop and is already well investigated, both theoretically and practically. In particular, the broader observation that coupling with strong search procedures can limit the value of learned components has already been made in similar contexts, e.g., by Böther et al. (ICLR ‘22) or Xia et al. (ICLR ‘24).

The finding that the insertion of descent into a pre-trained local search policy makes its advantage disappear seems unsurprising: During training, a policy might learn patterns or consecutive moves that are then interrupted by the descent steps. The authors address this to some extent through fine-tuning, where they report that fine-tuning might produce moves from which descent might yield larger improvements; however, it remains unclear how fully these observations can account for the performance difference.

A particular problem arises with NeuOpt, where capacity constraints may be violated through the perturbation; the random moves will often fail to recover a feasible solution. The authors address this by considering a variant with repair-descent, but this is not the baseline used for comparison with the fine-tuned variant.

The data from the fine-tuning experiments are, in my opinion, not strong enough to assess in general whether fine-tuning actually helps improve the combination of state-of-the-art pivot rule learners with descent (as there are only small instances and small improvements over the baseline). This limits the conclusions that can be drawn from this original component, though it is also not entirely new, as fine-tuning in optimization has precedents in active search (Bello et al. (ICLR ‘16) ; Hottung et al. (ICLR ’22).

The proposed decision rule for assessing whether fine-tuning may be useful is still rather speculative.

Also, for SAT, the results reproduced by the authors are significantly weaker than those reported for the model (Appendix F.5), which may limit the conclusions that can be drawn about the original model.

Questions for authors
  1. Based on their results, do the authors find themselves in a better position to explain why the pre-trained models offer so little advantage over a random pivot rule when coupled with descent steps, beyond the obvious interruptions to their learned long-term patterns?

  2. Can the authors explain how their approach and the conclusions that can be drawn differ from those of Böther et al. or Xia et al.? What further insights are provided by their experiments?

  3. How broadly do the authors believe their developed criterion for successful fine-tuning might generalize?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.