← News

ResearchSources: arXiv · 19 Nov 2026

Study finds uneven sampling budgets help neural routing solvers mainly on shifted workloads

A preprint measures when giving some problem instances more samples than others pays off for neural solvers, and reports the gain is usually small.

In plain words

Neural routing solvers generate many candidate solutions per problem and keep the best one, normally spending the same sampling effort on every instance. The paper asks whether splitting that effort unevenly works better. The authors report the benefit is modest on familiar data but larger when the workload shifts to unfamiliar instances.

What was announced

The arXiv preprint evaluates three pretrained solvers on the traveling salesman problem: POMO, the Attention Model and Sym-NCO. On the training distribution, reallocating a fixed sampling budget cuts the total optimality gap by at most 2.5 percent, which the authors read as uniform allocation being nearly optimal there. When workloads mix in out-of-distribution instances, the two solvers that degrade under the shift improve by 11.8 to 13.3 percent, equal to 1.1 to 1.8 percent of tour length, while the solver that holds up barely gains.

Across two heterogeneity mechanisms, three solvers, two confirmation collections and budgets of 25 to 200 samples per instance, the authors report the gain tracks how unevenly difficult the instances are, not the average difficulty. A power-law fit to twenty paid probe samples per instance recovers 88 to 93 percent of the uncharged optimum, beating successive halving. The authors also caution that a 2-opt local search step removes most of the gap at negligible cost, leaving reallocation to add only a few hundredths of a percent of tour length.

What it does not show

  • The source is the paper's abstract only, so the full article's methods and results were not reviewed.
  • The findings cover three named solvers on the traveling salesman problem and may not extend to other models or tasks.
  • The reported gains come from the authors' own experiments and have not been independently confirmed.

Sources

Source-support review completed 20 Nov 2026. This story was drafted with AI assistance and checked against retained source passages. Automated checking is not independent verification.

Coverage: arXiv: abstract.

Updates and corrections

No corrections so far.

First published 20 Nov 2026

New to the subject? AI from the Ground Up starts from the beginning.