神经组合优化测试时预算分配审计:采样运气被误当作分配收益
Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization
AI 导读
一项预注册研究审计了神经组合优化(NCO)求解器中固定总预算的非均匀分配是否带来收益。在均匀 TSP-100 上,POMO、AM、SymNCO 三个求解器的 2.2-2.6% 分配收益在样本外无法与零区分,属采样运气;v2 更正指出同分布余量为 1.1-1.6%。
正文 · 原文
Abstract: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.
| Comments: | v2 adds a correction notice on page 1: the in-distribution headroom is 1.1-1.6%, not zero (see arXiv:2611.06372, Appendix B); the rest is unchanged. 10 pages, 4 figures, 8 tables. Pre-registered study; code, cost arrays, and the full pre-registration record (including every amendment and its direction) at this https URL |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC) |
| ACM classes: | G.1.6; I.2.8; G.3 |
| Cite as: | arXiv:2608.13087 [cs.LG] |
| (or arXiv:2608.13087v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2608.13087 arXiv-issued DOI via DataCite |
Submission history
From: Jinhyung Bae [view email]
[v1]
Thu, 13 Aug 2026 10:53:48 UTC (213 KB)
[v2]
Tue, 17 Nov 2026 04:36:36 UTC (214 KB)
来源:arXiv cs.AI · arxiv.org