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

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.