Metraipolis › archive › dc_9dc202ac7154

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.13087
License (as archived)
CC0-1.0
Archived
2026-10-19T04:18:20.745Z
SHA-256 of the archived text
d5b5b74c9cc1f97ce08a8fd6238d2e75b88f774433070fd91aff0a052ed66ca5
Stable URL of this page
https://metraipolis.com/documento/dc_9dc202ac7154

How to cite

Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization — arXiv:2608.13087 — arXiv (en), https://arxiv.org/abs/2608.13087 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9dc202ac7154 (Metraipolis archive dc_9dc202ac7154, sha256 d5b5b74c9cc1f97ce08a8fd6238d2e75b88f774433070fd91aff0a052ed66ca5)
BibTeX
@misc{dc9dc202ac7154,
  title = {Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization — arXiv:2608.13087},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.13087},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9dc202ac7154; sha256 d5b5b74c9cc1f97ce08a8fd6238d2e75b88f774433070fd91aff0a052ed66ca5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.13087. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-14 in cs.AI).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.13087 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T04:13:06.736Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-08-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).