A First Guess Is Rarely the Final Answer: Learned Local Search That Generalizes to Larger Routing Problems
arXiv:2604.06940v3 Announce Type: replace-cross Abstract: Neural routing solvers rarely stop at their first solution: constructed tours are usually refined by search, such as sampling or local search. Neural improvement methods learn this search as a policy that repeatedly applies local moves, but existing policies degrade sharply beyond their training size. We argue that size generalization depends on whether the information that determines the value of a move reaches the policy in a size-inde…