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

神经组合优化测试时预算分配审计:采样运气伪装成分配增益

Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization

AI 导读

研究审计了神经组合优化(NCO)求解器的测试时预算分配:在均匀 TSP-100 上,POMO、AM、SymNCO 三个预训练求解器的 oracle 分配在样本内报告 2.2-2.6% 增益,但样本外测量与零无异(0.457、0.015、-0.512 个百分点),按惯例的样本内流程会支持一个并不存在的 2% 级增益。

正文 · AI 翻译

查看 PDF HTML(实验性)

摘要:神经组合优化(NCO)求解器会为每个实例报告多次采样解中的最优解,而按照惯例,每个实例的采样次数完全相同。对于固定总预算进行非均匀分配是否能带来收益,此前尚未被测量。我们对此进行了测量,并对测量本身进行了审计。
首先,在分布内工作负载上,分配带来的提升空间无法被检测到。在均匀 TSP-100 上,对三个预训练求解器(POMO、AM、SymNCO)而言,在同一批存储样本上计算并评估的 oracle 分配报告了 2.2-2.6% 的增益,且置信区间不包含零;而在样本外测量时,同样的增益与零无法区分(0.457、0.015、-0.512 个百分点)。按照惯常的样本内流程,这三个求解器本都会支持一项并不存在的、达到 2% 水平的已发表增益。我们以逐实例的零假设(其真实增益按构造为零)来校准这一偏差;在我们测试的范围内,该偏差不会随样本数或实例数增加而缩小。
其次,消除虚假增益的同一校正方法保留了一个真实增益。在分布偏移下(一种混合均匀实例与聚类实例的工作负载),一项预注册的验证性实验发现,在相同评估预算下,由留出样本统计量引导的分配将 best-of-k 分别提升 11.5%(AM,主要终点;95% CI [7.4, 19.7])和 12.0%(SymNCO,重复实验),且未计入信号获取成本;一项预注册的阴性对照(POMO,对分布偏移的鲁棒性高出一个数量级)显示为 -0.3% [-0.7, 0.24]。该增益比冻结的分布标签基线高出 4.2 个百分点 [1.9, 7.7]。一项探索性策略在同一预算中计入 20 个样本的探测成本后,仍保留 3.4%(AM)和 4.6%(SymNCO)的增益。
我们给出了一种校正流程和一份报告清单,并公开了所有数据、代码和预注册记录。
评论: v2 在第 1 页增加了一则更正说明:分布内提升空间为 1.1-1.6%,而非零(见 arXiv:2611.06372,附录 B);其余内容不变。10 页,4 幅图,8 张表。预注册研究;代码、成本数组和完整预注册记录(包括每一项修订及其方向)见 此 https URL
主题: 机器学习(cs.LG);人工智能(cs.AI);优化与控制(math.OC)
ACM 分类: G.1.6; I.2.8; G.3
引用为: arXiv:2608.13087 [cs.LG]
  (或本版本的 arXiv:2608.13087v2 [cs.LG])
  https://doi.org/10.48550/arXiv.2608.13087

由 DataCite 颁发的 arXiv DOI

提交历史

来自:Jinhyung Bae [查看邮箱]
[v1] 2026 年 8 月 13 日星期四 10:53:48 UTC(213 KB)
[v2] 2026 年 11 月 17 日星期二 04:36:36 UTC(214 KB)

来源:arXiv cs.AI · arxiv.org