跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2609.27917 · v2

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

首次提交 2026-08-22 01:54
版本更新 2026-11-18 23:53
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

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.

作者备注: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: https://github.com/nepersoned/best-of-k-allocation

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-18 23:53 · 最新观测版本

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

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.

查看此版本解读 →查看此版本原文 ↗