REVIEW 2 major objections 3 minor 15 references
Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization
T0 review · 2 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read This paper shows that the usual in-sample way of measuring test-time allocation gains manufactures 2.2-2.6% phantom gains on data where the true gain is zero, and that the same correction that removes them preserves real 11-12% gains…
desk verdict Careful audit with a strong core result; the 'zero gain' language is overstrong and the confirmatory arms were selected, but this deserves peer review. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is offline replay of stored sample arrays: for every instance, all sampled solution costs are stored, and any allocation policy is evaluated by taking the minimum of the first $k_i$ entries of a randomized permutation of that instance's array. This forces all policies to be compared on literally the same samples and makes the audit affordable. The two estimators are $d_{\mathrm{in}}$ (allocation decided and evaluated on the same array) and $d_{\mathrm{split}}$ (allocation decided on one half of the array, evaluated on the other); $d_{\mathrm{in}}$ is biased upward by selection, while $d_{\mathrm{split}}$ is the out-of-sample estimate. The calibration instrument is the instance-wise null: resampling with replacement from a single instance's array creates exchangeable synthetic instances with zero true allocation gain, and the distribution of per-source 95th percentiles defines the noise floor. Convex regularization—the greatest convex minorant of each estimated curve—restores the non-increasing marginal gains that greedy allocation requires.
What would settle it
Re-run the in-distribution audit with the allocation decided on stored samples but evaluated on freshly drawn independent samples from the same decoding distribution, at large N and K; if the out-of-sample gain exceeds the calibrated floor and replicates across new seeds, the claim that in-distribution allocation gain is zero would fall. Alternatively, show the noise floor dropping below, say, 0.5% as K or N grows far beyond the tested ranges, which would falsify the paper's scale-invariance claim.
Extended reading notes
Core claim
The central discovery is that the conventional evaluation protocol for test-time budget allocation in neural combinatorial optimization is dominated by selection bias: the allocation is chosen by maximizing over noisy per-instance estimates of best-of-$k$ curves, and then scored on the same realized samples, so the reported gain is the optimizer's curse in action. On uniform TSP-100 with three pretrained solvers, this in-sample procedure reports gains of 2.2-2.6% with confidence intervals excluding zero, while the same gains measured out of sample are 0.457, 0.015, and -0.512 percent, all indistinguishable from zero. The paper constructs an instance-wise null in which the true gain is zero by construction, and calibrates the in-sample estimate against it; the floor is flat in the number of stored samples and the number of instances over the tested ranges. Under distribution shift, the same out-of-sample correction leaves an 11.5% gain for AM and 12.0% for SymNCO at equal evaluation budget with the signal cost not charged, while a negative control solver shows no gain. The paper's own headline number is always stated with that signal-cost qualification, and an exploratory probe policy that charges a 20-sample probe retains 3.4% and 4.6%.
Load-bearing premise
The audit assumes that randomized prefix minima of stored per-instance cost arrays are unbiased estimates of true expected best-of-$k$, so the stored arrays faithfully emulate online sampling and are exchangeable under random ordering.
Editorial extensions
If this is right
- In-sample allocation gains at the 2% level should not be trusted unless the allocation is decided and evaluated on disjoint samples.
- The noise floor must be computed per solver and configuration; it varies by roughly a factor of two across the three solvers here, so borrowing another paper's floor is not valid.
- On in-distribution homogeneous workloads, uniform allocation is an adequate default within the detection limit of this audit.
- Under distribution shift, allocation guided by held-out sample statistics is worth measuring and works without a distribution label; a deployable probe policy retains 3-5% at a 50:50 composition.
- Increasing sample count or instance count did not shrink the phantom gain over the tested ranges, so scale is not a substitute for out-of-sample correction.
Reading between the lines
- The same split-sample audit would likely change reported gains in other best-of-$k$ test-time compute settings, such as repeated sampling from large language models, where allocation decisions and evaluations often share the same rollout data.
- The flatness of the noise floor suggests the bias is driven by per-instance estimation noise rather than sample size, which would imply that bigger experiments cannot rescue in-sample selection.
- Because the budget-charged probe retains most of its headroom at low out-of-distribution shares, an adaptive policy that spends little when instances look in-distribution could be a practical next step.
- The residual gain beyond the frozen distribution-label baseline hints that per-instance statistics carry information not contained in the shift label; a learned predictor of marginal sample value is a natural extension.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper measures whether non-uniform instance-wise allocation of a fixed test-time sample budget improves neural combinatorial optimization (NCO) solvers, and audits the measurement procedure itself. It defines an allocation gain d as the relative improvement of an oracle allocation over uniform allocation, evaluated through an in-sample estimator d_in (allocation decided and evaluated on the same stored samples) and an out-of-sample estimator d_split (allocation decided on one half of the stored array, evaluated on the other). On in-distribution TSP-100 workloads, d_in shows gains of 2.2-2.6% across POMO, AM, and SymNCO with confidence intervals excluding zero, while d_split is indistinguishable from zero. The paper constructs an instance-wise null where the true gain is zero by construction and shows that the in-sample procedure manufactures gains of the same order; the resulting noise floor is reported as roughly invariant to the number of stored samples per instance and to the number of instances. Under a distribution-shifted workload (50% clustered TSP-100), a pre-registered confirmatory experiment finds d_split gains of 11.5% for AM and 12.0% for SymNCO, with a POMO negative control showing -0.3%. An exploratory budget-charged probe policy retains 3.4-4.6% at the registered composition. The paper provides a correction procedure, a reporting checklist, and releases data, code, and the full pre-registration record.
Significance. The paper makes a useful and carefully controlled methodological contribution. The offline replay setup is a genuine strength: all policies are compared on identical stored samples, removing run-to-run noise, and the separation of decision and evaluation samples is enforced cleanly. The pre-registration, negative control, and full release of arrays, scripts, and amendment records are exemplary and enable independent verification. The in-sample selection-bias finding, calibrated against an instance-wise null, is a new and important caution for test-time compute allocation in NCO and parallels the optimizer's-curse literature. The distribution-shift experiment is well designed to show that the correction discriminates rather than merely deflates. The main weakness is that the negative in-distribution conclusion is stated more strongly than the d_split estimator's precision can support: the paper itself notes that d_split is downward-biased, and a confidence interval covering zero for a downward-biased estimator does not establish that the true gain is zero. This is a fixable overreach, either by calibrating detection power or by softening the language.
major comments (2)
- [§II-E, §VII (Limitation 4), §VIII] The statement that the 2.2-2.6% in-distribution gains are gains that 'do not exist' or that the data have 'true gain zero' is stronger than the d_split evidence can support. The paper explicitly says in §II-E that d_split is biased downward because the allocation is decided from only half the stored array, and Limitation 4 reiterates that the decision uses 500 samples versus an evaluation budget of 100. A confidence interval covering zero for a downward-biased estimator is compatible with a true gain of zero but also with a true gain of roughly 1-2% that d_split cannot resolve. The abstract and conclusion phrase this as an effect that does not exist, whereas Sections II-E and VII use the more defensible 'no detectable headroom' language. Please either calibrate the detection power of d_split (for example, by injecting known amounts of heterogeneity into synthetic instances and measuring the recovery rate of d_split) or revise the abstract and conclusion to state that the gain is not detectable at the precision of d_split. This is load-bearing for the negative in-distribution claim, which is a central result of the paper.
- [§II-B, §II-D] The offline replay estimator assumes that the stored cost arrays are exchangeable under random permutation, so that prefix minima under a random ordering estimate the expected best-of-k. This is plausible for stochastic rollouts on Axis A, but less obvious for Axis B, where the 800 stored costs come from 100 deterministic start-node trajectories each multiplied by 8 dihedral augmentations. If, for example, the eight augmentation copies of the same tour are highly correlated, or if the start-node trajectories have order-dependent correlations, then the replayed prefix minima may not correspond to the expected best-of-k of the actual multi-start procedure. Since d_in, d_split, and the instance-wise null all operate on these replayed arrays, any bias in the replay step propagates to all three. Please provide an empirical validation, e.g., compare the replay-based best-of-k curve against fresh online rollout best-of-k on a small set of instances, or otherwise justify exchangeability from the construction.
minor comments (3)
- [§III-D, Tables II-III] The claim that the noise floor is 'flat within Monte-Carlo error' is not accompanied by estimates of that error. Please report standard errors or confidence intervals for the floor values in Tables II and III, or state the number of Monte-Carlo repetitions used, so the scale-invariance claim can be checked.
- [Table VII] The header 'OOD shared_split' appears to be missing a space; it should read 'OOD share'. Also, 'd_charged(probe m = 20 charged)' is redundant; 'd_charged(probe m = 20)' would be clearer.
- [Appendix B] The appendix is labeled 'APPENDIXB PRE-REGISTRATIONTIMELINE' and then immediately repeated as 'PRE-REGISTRATIONTIMELINE'; please fix the duplicate heading.
Circularity Check
No circularity found: the split-half out-of-sample estimator, pre-registered new-seed confirmatory experiment, and explicit instance-wise null calibration keep the derivation self-contained.
full rationale
The paper's derivation chain does not reduce to its own inputs. The in-distribution audit (Section III) defines two estimators with opposite bias directions — d_in (decision and evaluation on the same stored array) and d_split (decision on one half, evaluation on the other) — and the "phantom gain" conclusion rests on the out-of-sample d_split column plus an instance-wise null in which the true allocation gain is zero by construction; that null is presented as a calibration instrument, not as evidence about real data. The distribution-shift result (Section IV) is a pre-registered confirmatory experiment with new instance and decoding seeds, a declared primary endpoint, a replication arm, and a negative control, with label baseline ratios frozen from the exploratory pass and applied only to new data, so the 11.5% effect is not a fitted parameter renamed as a prediction. Gap normalization uses deterministic LKH-3 references rather than sample-derived denominators, avoiding a normalization artifact. The paper also retracts an earlier N-scaling claim and records an amendment that moves against its own audit narrative, which is inconsistent with a forced-by-construction story. The only stated dependency is the exchangeability assumption of stored arrays in the offline replay (Section II-D), which is a transparent modeling premise rather than a circular reduction. No load-bearing step is defined in terms of its own target, and no relevant self-citation carries the argument.
Assumptions & free parameters
free parameters (4)
- Label baseline ratio (AM) =
20:1
- Label baseline ratio (SymNCO) =
12:1
- Label baseline ratio (POMO) =
1.5:1
- Probe size m (charged policy) =
20
assumptions (7)
- standard math The expected best-of-k cost f_i(k) is non-increasing and convex for any instance, as the expectation of a minimum of i.i.d. draws.
- standard math Greedy marginal allocation is optimal for convex separable resource allocation with integer budgets.
- domain assumption Randomized ordering of stored arrays and taking prefixes gives exchangeable draws, so E[min] is the same as for random subsets.
- domain assumption LKH-3 reference tours are sufficiently accurate and deterministic that normalization to gap-to-reference does not bias relative policy comparisons.
- domain assumption The instance-wise null, built by resampling within a single instance's stored array, has exactly zero true allocation gain in expectation.
- standard math Bootstrap resampling over instances yields valid confidence intervals for d_in and d_split.
- domain assumption The pre-registration record is authentic and was fixed before results were seen.
Cite this review
Pith. "Pith review of Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization." pith.science (2026). https://pith.science/paper/BYIF5XAV
@misc{pith2026260813087,
author = {Pith},
title = {Pith review of: Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/BYIF5XAV}},
note = {Machine review of arXiv:2608.13087}
}
read the original 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.
Figures
Reference graph
Works this paper leans on
-
[1]
Attention, learn to solve routing problems!
W. Kool, H. van Hoof, and M. Welling, “Attention, learn to solve routing problems!” inProc. Int. Conf. Learning Representations (ICLR), 2019, arXiv:1803.08475
arXiv 2019
-
[2]
POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
Y .-D. Kwon, J. Choo, B. Kim, I. Yoon, Y . Gwon, and S. Min, “POMO: Policy optimization with multiple optima for reinforcement learning,” in Advances in Neural Information Processing Systems, vol. 33, 2020, pp. 21188–21198, arXiv:2010.16011
work page Pith review arXiv 2020
-
[3]
The optimizer’s curse: Skepticism and postdecision surprise in decision analysis,
J. E. Smith and R. L. Winkler, “The optimizer’s curse: Skepticism and postdecision surprise in decision analysis,”Management Science, vol. 52, no. 3, pp. 311–322, 2006
2006
-
[4]
I. Andrews, T. Kitagawa, and A. McCloskey, “Inference on winners,” Quarterly Journal of Economics, vol. 139, no. 1, pp. 305–358, 2024
work page 2024
-
[5]
A reality check for data snooping,
H. White, “A reality check for data snooping,”Econometrica, vol. 68, no. 5, pp. 1097–1126, 2000
2000
-
[6]
A test for superior predictive ability,
P. R. Hansen, “A test for superior predictive ability,”Journal of Business & Economic Statistics, vol. 23, no. 4, pp. 365–380, 2005
2005
-
[7]
Scaling test-time compute optimally can be more effective than scaling LLM parameters,
C. Snell, J. Lee, K. Xu, and A. Kumar, “Scaling test-time compute optimally can be more effective than scaling LLM parameters,” inProc. Int. Conf. Learning Representations (ICLR), 2025, arXiv:2408.03314
arXiv 2025
-
[8]
Neural Solver Selection for Combinatorial Optimization
C. Gao, H. Shang, K. Xue, and C. Qian, “Neural solver selection for combinatorial optimization,” inProc. Int. Conf. Machine Learning (ICML), PMLR 267, 2025, arXiv:2410.09693
work page Pith review arXiv 2025
Show all 15 references
-
[9]
The deflated Sharpe ratio: Correcting for selection bias, backtest overfitting, and non-normality,
D. H. Bailey and M. López de Prado, “The deflated Sharpe ratio: Correcting for selection bias, backtest overfitting, and non-normality,” Journal of Portfolio Management, vol. 40, no. 5, pp. 94–107, 2014
2014
-
[10]
Towards reliable LLM evaluation: Correcting the winner’s curse in adaptive benchmarking,
Y . Xu, J. Zhang, H. Sun, Z. Zhou, T. Cao, and V . Aggarwal, “Towards reliable LLM evaluation: Correcting the winner’s curse in adaptive benchmarking,” arXiv:2605.05973, 2026 (preprint)
2026 arXiv
-
[11]
Learn- ing how hard to think: Input-adaptive allocation of LM computa- tion,
M. Damani, I. Shenfeld, A. Peng, A. Bobu, and J. Andreas, “Learn- ing how hard to think: Input-adaptive allocation of LM computa- tion,” inProc. Int. Conf. Learning Representations (ICLR), 2025, arXiv:2410.04707
2025 arXiv
-
[12]
Large language monkeys: Scaling inference compute with repeated sampling,
B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V . Le, C. Ré, and A. Mirhoseini, “Large language monkeys: Scaling inference compute with repeated sampling,” arXiv:2407.21787, 2024
2024 arXiv
-
[13]
Sym-NCO: Leveraging symmetricity for neural combinatorial optimization,
M. Kim, J. Park, and J. Park, “Sym-NCO: Leveraging symmetricity for neural combinatorial optimization,” inAdvances in Neural Information Processing Systems, vol. 35, 2022, pp. 1936–1949, arXiv:2205.13209
2022 arXiv
-
[14]
How good is neural combina- torial optimization? A systematic evaluation on the traveling salesman problem,
S. Liu, Y . Zhang, K. Tang, and X. Yao, “How good is neural combina- torial optimization? A systematic evaluation on the traveling salesman problem,”IEEE Computational Intelligence Magazine, vol. 18, no. 3, pp. 14–28, 2023
2023
-
[15]
Do ImageNet clas- sifiers generalize to ImageNet?
B. Recht, R. Roelofs, L. Schmidt, and V . Shankar, “Do ImageNet clas- sifiers generalize to ImageNet?” inProc. Int. Conf. Machine Learning (ICML), PMLR 97, 2019, arXiv:1902.10811
2019 arXiv
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.