A First Guess is Rarely the Final Answer: Learning to Search in the Travelling Salesperson Problem

• URL: http://arxiv.org/abs/2604.06940v1
• Date: Wed, 08 Apr 2026 11:04:45 GMT
• Title: A First Guess is Rarely the Final Answer: Learning to Search in the Travelling Salesperson Problem
• Abstract summary: Most neural solvers for the Traveling Salesperson Problem (TSP) are trained to output a single solution, even though rarely stop there: at test time, they routinely spend extra compute on sampling or post-hoc search.<n>We argue that a key reason is design mismatch: many approaches reuse state representations, architectural choices, and training recipes inherited from single-solution methods, rather than being built around the mechanics of local search.<n>NICOTSP represents the current tour with exactly $n$ edge tokens aligned with the neighborhood operator, scores 2-opt moves directly without tour positional encodings, and trains via a two-
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Most neural solvers for the Traveling Salesperson Problem (TSP) are trained to output a single solution, even though practitioners rarely stop there: at test time, they routinely spend extra compute on sampling or post-hoc search. This raises a natural question: can the search procedure itself be learned? Neural improvement methods take this perspective by learning a policy that applies local modifications to a candidate solution, accumulating gains over an improvement trajectory. Yet learned improvement for TSP remains comparatively immature, with existing methods still falling short of robust, scalable performance. We argue that a key reason is design mismatch: many approaches reuse state representations, architectural choices, and training recipes inherited from single-solution methods, rather than being built around the mechanics of local search. This mismatch motivates NICO-TSP (Neural Improvement for Combinatorial Optimization): a 2-opt improvement framework for TSP. NICO-TSP represents the current tour with exactly $n$ edge tokens aligned with the neighborhood operator, scores 2-opt moves directly without tour positional encodings, and trains via a two-stage procedure: imitation learning to short-horizon optimal trajectories, followed by critic-free group-based reinforcement learning over longer rollouts. Under compute-matched evaluations that measure improvement as a function of both search steps and wall-clock time, NICO-TSP delivers consistently stronger and markedly more step-efficient improvement than prior learned and heuristic search baselines, generalizes far more reliably to larger out-of-distribution instances, and serves both as a competitive replacement for classical local search and as a powerful test-time refinement module for constructive solvers.

Related papers

• REVES: REvision and VErification--Augmented Training for Test-Time Scaling [53.197756110943395]
  We propose a two-stage iterative framework that alternates between online data/prompt augmentation and policy optimization.<n>We observe gains of +6.5 points over the RL baseline and +4.0 points over standard multi-turn training.
  arXiv  Detail & Related papers  (2026-06-17T10:37:23Z)
• Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces [63.82675722580452]
  OPT* is a family of optimization-style tasks for training and evaluating LLM step-by-step optimization-like reasoning.<n>Each task provides a feasibility checker and evaluator, while a complexity parameter expands the search space without requiring new human labels.<n>We show that training on OPT* improves step-by-step optimization-like reasoning.
  arXiv  Detail & Related papers  (2026-06-03T21:43:38Z)
• Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models [61.55758048622473]
  We introduce Neural Chain-of-Thought Search (NCoTS), a framework that reformulates reasoning as a dynamic search for the optimal thinking strategy.<n>By quantitatively characterizing the solution space, we reveal the existence of sparse superior reasoning paths that are simultaneously more accurate and concise than standard outputs.
  arXiv  Detail & Related papers  (2026-01-16T14:38:18Z)
• PROPA: Toward Process-level Optimization in Visual Reasoning via Reinforcement Learning [30.44007644340425]
  We introduce PROPA, a novel framework that integrates Monte Carlo Tree Search (MCTS) with GRPO to generate dense, process-level rewards and optimize reasoning at each intermediate step without human annotations.<n>Across seven benchmarks and four VLM backbones, PROPA consistently outperforms both SFT- and RLVR-based baselines.<n>It achieves up to 17.0% gains on in-domain tasks and 21.0% gains on out-of-domain tasks compared to existing state-of-the-art.
  arXiv  Detail & Related papers  (2025-11-13T13:06:12Z)
• Is Optimal Transport Necessary for Inverse Reinforcement Learning? [0.0]
  Inverse Reinforcement Learning (IRL) aims to recover a reward function from expert demonstrations.<n>We propose two simple, alternatives to Optimal Transport (OT) in IRL.<n>We show that our simple rewards match or outperform recent OT-based approaches.
  arXiv  Detail & Related papers  (2025-06-07T13:29:37Z)
• Stepwise Reasoning Checkpoint Analysis: A Test Time Scaling Method to Enhance LLMs' Reasoning [81.50681925980135]
  We propose Stepwise Reasoning Checkpoint Analysis (SRCA), a framework that introduces checkpoints between reasoning steps.<n>It incorporates two key strategies: (1) Answer-Clustered Search, which groups reasoning paths by their intermediate checkpoint answers to maintain diversity while ensuring quality, and (2) Checkpoint Candidate Augmentation, which leverages all intermediate answers for final decision-making.<n>Our approach effectively reduces path homogenization and creates a fault-tolerant mechanism by utilizing high-quality intermediate results.
  arXiv  Detail & Related papers  (2025-05-23T12:42:50Z)
• To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoning [37.179289850042764]
  Backtracking naturally scales test-time compute by enabling sequential, linearized exploration via long chain-of-thought (CoT) generation.<n>In this paper, we systematically compare these two approaches on two challenging reasoning tasks: CountDown and Sudoku.<n>Surprisingly, we find that sequential search underperforms parallel sampling on CountDown but outperforms it on Sudoku, suggesting that backtracking is not universally beneficial.
  arXiv  Detail & Related papers  (2025-04-09T17:12:49Z)
• Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization [83.65278205301576]
  We propose to learn direct mappings from different noise levels to the optimal solution for a given instance, facilitating high-quality generation with minimal shots.<n>This is achieved through an optimization consistency training protocol, which minimizes the difference among samples.<n>Experiments on two popular tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), demonstrate the superiority of Fast T2T regarding both solution quality and efficiency.
  arXiv  Detail & Related papers  (2025-02-05T07:13:43Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  We present efficient methods for optimizing dynamic regret and adaptive regret.<n>The proposed algorithms require only one gradient query and one function evaluation at each round.<n>We also study an even stronger measure, namely "interval dynamic regret", and reduce the number of projections per round from $O(log2 T)$ to $1$.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• Learning to Optimize for Reinforcement Learning [58.01132862590378]
  Reinforcement learning (RL) is essentially different from supervised learning, and in practice, these learneds do not work well even in simple RL tasks. Agent-gradient distribution is non-independent and identically distributed, leading to inefficient meta-training. We show that, although only trained in toy tasks, our learned can generalize unseen complex tasks in Brax.
  arXiv  Detail & Related papers  (2023-02-03T00:11:02Z)
• Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning [2.4565068569913384]
  We propose to learn a local search gradient based on 2-opt operators via deep reinforcement learning. We show that the learned policies can improve even over random initial solutions and approach near-optimal solutions at a faster rate than previous state-of-the-art deep learning methods.
  arXiv  Detail & Related papers  (2020-04-03T14:51:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.