测试时样本分配的伪收益被误认为真实提升，实证发现多数宣称增益是假象。
Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization
- 通过对比同批样本内最优解，验证非均匀分配能否提升性能
- 在标准测试集上，声称2%-2.6%的提升实际不可信，出样本后归零
- 仅在分布偏移场景下，基于样本统计的智能分配能带来11.5%真实增益
神经组合优化求解器对每个实例采样多次并取最优解，常规做法是所有实例分配相同采样数。是否非均匀分配固定总预算能带来实际收益尚未被验证。我们对此进行了测量，并审计了测量过程本身。首先，在分布内任务中，这种分配改进空间无法被检测到：在三个预训练求解器（POMO、AM、SymNCO）上，对统一的TSP-100问题，基于存储样本计算的最优分配在样本内报告2.2%-2.6%的增益（置信区间不包含零），但出样本测量后该增益与零无差异（分别为0.457%、0.015%、-0.512%）。若沿用传统样本内评估流程，三者均会错误支持2%量级的虚假增益。我们通过构造每实例零增益的基准，校准此偏差；在测试范围内，该偏差不随更多样本或实例减少。其次，同一校正方法可消除虚假增益，同时保留真实收益。在分布偏移工作负载（混合均匀与聚类实例）下，预注册确认实验显示，基于预留样本统计的分配策略使best-of-k性能提升11.5%（AM，主终点；95%置信区间[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）增益。本文提供校正流程与报告清单，并公开全部数据、代码及预注册记录。
原文摘要 · Abstract (English)
Neural combinatorial optimization (NCO) solvers report the best of many sampled solutions per instance, and the sample count is, by convention, identical for every instance. Whether a non-uniform allocation of a fixed total budget would buy anything has not been measured. We measure it, and we audit the measurement itself. First, on in-distribution workloads the allocation headroom is not detectable. Across three pretrained solvers (POMO, AM, SymNCO) on uniform TSP-100, an oracle allocation computed and evaluated on the same stored samples reports a 2.2-2.6% gain with intervals excluding zero; measured out of sample the same gain is indistinguishable from zero (0.457, 0.015, -0.512 percent). Following the customary in-sample procedure, all three solvers would have supported a published 2%-level gain that does not exist. We calibrate this bias against an instance-wise null in which the true gain is zero by construction; over the ranges we test it does not shrink with more samples or more instances. Second, the same correction that removes the phantom gains preserves a real one. Under distribution shift (a workload mixing uniform and clustered instances), a pre-registered confirmatory experiment finds that allocation guided by held-out sample statistics improves best-of-k by 11.5% (AM, primary endpoint; 95% CI [7.4, 19.7]) and 12.0% (SymNCO, replication) at equal evaluation budget, with the signal-acquisition cost not charged; a pre-registered negative control (POMO, an order of magnitude more robust to shift) shows -0.3% [-0.7, 0.24]. The gain exceeds a frozen distribution-label baseline by 4.2 points [1.9, 7.7]. An exploratory policy charging a 20-sample probe against the same budget retains 3.4% (AM) and 4.6% (SymNCO). We give a correction procedure and a reporting checklist, and release all data, code, and the pre-registration record.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。