Auditing Reveals Bias in Neural Combinatorial Optimization Benchmarks

Neural Combinatorial Optimization (NCO) solvers typically report the best solution found from multiple samples per instance, with a uniform sample count across all instances. This paper critically examines whether a non-uniform allocation of a fixed total sampling budget could yield better results, and importantly, audits the measurement process itself. The findings reveal a significant bias in current evaluation practices. For in-distribution workloads, the study found that apparent gains from oracle-computed non-uniform allocations were largely attributable to "sampling luck" when evaluated on the same stored samples. When measured out-of-sample, these gains became statistically indistinguishable from zero. This suggests that many published 2%-level gains in NCO might not actually exist, a bias that does not diminish with more samples or instances. However, the same rigorous correction procedure that exposed these phantom gains also preserved a real one under distribution shift. In a pre-registered experiment involving mixed uniform and clustered instances, allocation guided by held-out sample statistics improved best-of-k solutions by 11.5% for AM and 12.0% for SymNCO, at equal evaluation budget. This gain significantly surpassed a frozen distribution-label baseline. The paper provides a correction procedure, a reporting checklist, and releases all data and code, advocating for more robust and unbiased NCO benchmarking.