跳到正文
arXiv cs.AI· Jinhyung Bae·· 2 小时前AI 评分36

神经路由求解器的逐实例采样预算重分配何时才划算?

When Does Reallocating a Sampling Budget Pay? Instance-wise Allocation for Neural Routing Solvers

AI 导读

一项研究量化了神经路由求解器将固定采样预算从均匀分配改为逐实例非均匀分配的收益。

正文 · 原文

View PDF HTML (experimental)

Abstract:Neural routing solvers sample many solutions per instance and keep the best, with the same number of samples for every instance. We measure how much a non-uniform split of the same total budget is worth and which property of a workload decides it. Best-of-k curves estimated by averaging random orderings of stored samples overstate the gain, and deciding on one half of the samples while evaluating on the other understates it; we use exact best-of-k curves, a U-statistic over all orderings. For three pretrained solvers (POMO, the Attention Model and Sym-NCO) on the traveling salesman problem, reallocation reduces the total optimality gap by at most 2.5% on the training distribution, so uniform allocation is close to optimal there. On workloads that mix in out-of-distribution instances it reduces the gap by 11.8-13.3% (1.1-1.8% of tour length) for the two solvers that degrade under the shift, and almost nothing for the one that does not. Across two heterogeneity mechanisms, three solvers, two confirmation collections and budgets of 25 to 200 samples per instance, the gain is predicted by the spread of difficulty within a workload, not its average. Allocating on a power-law curve fitted to twenty charged probe samples per instance recovers 88-93% of the uncharged optimum; successive halving does worse. A 2-opt local search, however, removes most of the gap at negligible cost, after which reallocation adds a few hundredths of a percent of tour length.
Comments: v2: merged and corrected version; supersedes v1 of this paper and arXiv:2608.13087, re-analysed with exact best-of-k curves, with new baselines and a local-search comparison. 27 pages, 5 figures. Submitted to the Journal of Heuristics. Code and data: this https URL
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC)
Cite as: arXiv:2609.27917 [cs.LG]
  (or arXiv:2609.27917v2 [cs.LG] for this version)
  https://doi.org/10.48550/arXiv.2609.27917

arXiv-issued DOI via DataCite

Submission history

From: Jinhyung Bae [view email]
[v1] Fri, 21 Aug 2026 17:54:00 UTC (2,281 KB)
[v2] Wed, 18 Nov 2026 15:53:35 UTC (85 KB)

来源:arXiv cs.AI · arxiv.org