Pith. sign in

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 →

arxiv 2608.13087 v1 pith:BYIF5XAV submitted 2026-08-13 cs.LG cs.AImath.OC

classification cs.LGcs.AImath.OC
keywords neuralcombinatorialoptimizationtest-timecomputeallocationselectionbiasoptimizer'scursebest-of-ksamplingpre-registrationTSP-100out-of-sampleevaluation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether giving some test-time sample budgets more samples than others buys anything for neural combinatorial optimization, and whether the usual way of measuring that is trustworthy. It argues that the standard in-sample measurement—deciding and evaluating the allocation on the same stored samples—manufactures gains of 2.2-2.6% on data where the true gain is zero, and that this phantom gain does not shrink with more samples or more instances over the tested ranges. It then shows that reporting the gain out of sample removes the phantom gains on in-distribution workloads while preserving a real 11-12% gain under distribution shift for two of three solvers. A pre-registered confirmatory experiment, a negative control, and a budget-charged exploratory policy support the discrimination. The takeaway for a practitioner is that uniform allocation is an adequate default in distribution, but out-of-distribution allocation is worth measuring.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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)
  1. [§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.
  2. [§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)
  1. [§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.
  2. [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.
  3. [Appendix B] The appendix is labeled 'APPENDIXB PRE-REGISTRATIONTIMELINE' and then immediately repeated as 'PRE-REGISTRATIONTIMELINE'; please fix the duplicate heading.

Circularity Check

0 steps flagged · score 0.0 of 10

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 4 free parameters · 7 assumptions · 0 invented entities

The two headline estimates (phantom in-sample gain and out-of-sample true gain) are measured, not fit: d_in and d_split are direct computations on stored arrays. The only numbers fit to data are exploratory (probe size) and secondary (label baseline ratios), and none of them changes the sign or scale of the main result. The main burden is carried by standard convexity and exchangeability assumptions plus the integrity of the pre-registration record.

free parameters (4)
  • Label baseline ratio (AM) = 20:1
    Frozen from the exploratory pass and used in the pre-registered secondary endpoint measuring the residual over a distribution-label baseline. This ratio is fit to exploratory data, though the endpoint is evaluated on new confirmatory seeds.
  • Label baseline ratio (SymNCO) = 12:1
    Frozen from the exploratory pass for the replication arm's label-residual analysis. Same fit-to-exploratory-data status as the AM ratio.
  • Label baseline ratio (POMO) = 1.5:1
    Taken from the exploratory pass but not part of the registered freeze; the paper states that no endpoint depends on it.
  • Probe size m (charged policy) = 20
    Chosen from an exploratory sensitivity sweep over m equals 5, 10, 20, and 40. Used only in the descriptive, non-pre-registered budget-charged variant.
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.
    Invoked in Section II-A to justify the greedy marginal allocation and the convex minorant regularization of estimated curves.
  • standard math Greedy marginal allocation is optimal for convex separable resource allocation with integer budgets.
    Used in Section II-A to compute oracle allocations from estimated marginal gains.
  • domain assumption Randomized ordering of stored arrays and taking prefixes gives exchangeable draws, so E[min] is the same as for random subsets.
    Underlies all offline replay evaluations in Section II-D. For Axis B, this requires the 800 deterministic trajectories to be exchangeable after random ordering.
  • domain assumption LKH-3 reference tours are sufficiently accurate and deterministic that normalization to gap-to-reference does not bias relative policy comparisons.
    Assumed in Section II-D and discussed in Limitation 3, where CVRP was gated out because the reference was unstable, implying TSP reference stability is load-bearing.
  • domain assumption The instance-wise null, built by resampling within a single instance's stored array, has exactly zero true allocation gain in expectation.
    This is the foundation of the floor calibration in Section III-B. The paper argues exchangeability makes any allocation useless in expectation.
  • standard math Bootstrap resampling over instances yields valid confidence intervals for d_in and d_split.
    Used for all confidence intervals in the paper; a standard assumption not formally proven in the text.
  • domain assumption The pre-registration record is authentic and was fixed before results were seen.
    The confirmatory status of the shift experiment depends on the integrity of the timeline in Appendix B; no external timestamped registry is cited.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2608.13087 by the authors.

Figure 1
Figure 1. In-distribution audit (uniform TSP-100, Axis B, [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Operating characteristics of the floor (median definition). (a) Flat in the number of stored samples per instance [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. The same correction, applied to both workloads. Left (in-distribution): in-sample estimates (open markers) sit at the 2% level while out-of-sample [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Exploratory composition sweep (descriptive; no test): allocation [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 6 canonical work pages

  1. [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

  2. [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

  3. [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

  4. [4]

    Inference on winners,

    I. Andrews, T. Kitagawa, and A. McCloskey, “Inference on winners,” Quarterly Journal of Economics, vol. 139, no. 1, pp. 305–358, 2024

  5. [5]

    A reality check for data snooping,

    H. White, “A reality check for data snooping,”Econometrica, vol. 68, no. 5, pp. 1097–1126, 2000

  6. [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

  7. [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

  8. [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

Show all 15 references
  1. [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

  2. [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)

  3. [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

  4. [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

  5. [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

  6. [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

  7. [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

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.