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

TL;DR: Neural combinatorial optimization solvers report the best of many sampled tours per instance, always sampling the same number for every instance. This paper asks whether spending a fixed sampling budget non-uniformly across instances helps — and discovers that the obvious way to measure this manufactures a ~2.3–2.6% phantom gain out of pure noise, on data where the true gain is provably zero. The bias doesn't shrink with more samples or more instances. The fix (decide the allocation on one half of the samples, evaluate on the other) kills the phantom, and — this is the part that makes the paper more than a cautionary tale — the same fix preserves a real 11–12% gain that appears under distribution shift, verified in a preregistered experiment with a negative control that behaves exactly as predicted. It's a small-scale, TSP-only, single-author study, but it's one of the cleanest examples of measurement discipline in the test-time-compute literature, and the lesson transfers well beyond routing problems.

The convention nobody audited

Constructive neural solvers for routing problems — the Attention Model (AM), POMO, SymNCO — don't emit one tour per instance. They emit hundreds and keep the best. AM samples 1,280 tours; POMO rolls out one greedy trajectory per starting node times eight symmetry augmentations, 800 trajectories for a 100-node TSP. In every published pipeline, the sample count is a single global hyperparameter: every instance gets the same number of attempts.

That's a resource allocation decision made by default. Some instances' best-of-k curves flatten after ten rollouts; others keep descending at a hundred. If the marginal value of a sample differs across instances, uniform allocation leaves solution quality on the table. Formally: let f_i(k) be the expected cost of the best of k samples for instance i. With N instances and total budget S, minimize \sum_i f_i(k_i) subject to \sum_i k_i = S. Since f_i is the expectation of a minimum order statistic, it's non-increasing and convex in k — the hundredth sample can't help as much as the tenth — so greedy marginal allocation (give the next sample to the instance with the largest f_i(k_i) - f_i(k_i{+}1)) is exactly optimal if f is known.

The catch, of course, is that f_i must be estimated from samples. And the natural procedure — sample a lot, estimate each curve, compute the optimal allocation, report the improvement — uses the same samples to decide and to score. That's the setup for the optimizer's curse, and the paper's contribution is to measure how badly it bites here, and to show that correcting for it doesn't just deflate everything: it discriminates between phantom gains and real ones.

Why the same-sample measurement lies

Here's the intuition. Suppose all instances are genuinely exchangeable — same difficulty, same best-of-k curve. Convexity then says uniform allocation is optimal; the true allocation gain is exactly zero. But your estimated curves aren't identical. Some instances' stored sample arrays happen to contain an unusually deep tail — a few lucky draws far below the typical cost. The greedy allocator sees a steep estimated marginal curve for those instances and pours budget into them. When you then evaluate the allocation on those same stored arrays, the allocation "harvests" exactly the lucky draws that made it look attractive. Gain appears. On fresh samples, the luck doesn't repeat, and the gain evaporates.

The paper makes this precise with two estimators of the relative improvement d = (\text{uniform} - \text{oracle})/\text{uniform}: d_{\text{in}} (decide and evaluate on the same array) and d_{\text{split}} (decide on one half, evaluate on the other). d_{\text{in}} is biased upward in expectation, d_{\text{split}} mildly downward (the decision uses half the data).

The audit: phantom gains that scale doesn't cure

Everything runs on an offline replay design: for each instance, all K sampled costs are stored (up to K = 1{,}000 stochastic rollouts, or the full 800-trajectory POMO pool), and any allocation policy is scored by taking the minimum of the first k_i entries of a randomized ordering. Every policy is compared on literally the same samples, and — crucially — the null calibration becomes affordable, because it's just resampling stored arrays. Costs are normalized to gap over an LKH-3 reference tour, deliberately a deterministic denominator: a denominator estimated from the same samples would correlate with the dispersion driving the allocation and inflate the gain as a normalization artifact. (That level of care is representative of the whole paper.)

On in-distribution uniform TSP-100 (50 instances, budget of 100 samples each), the customary in-sample estimate looks like a solid finding on all three solvers — confidence intervals excluding zero. Out of sample, there is nothing:

Following standard practice, all three solvers would have supported a published 2%-level allocation gain that does not exist.

To calibrate how much gain pure selection noise can manufacture, the paper builds an instance-wise null: resample with replacement from a single instance's stored array to create N synthetic instances that share its cost distribution but are exchangeable — so no allocation can help in expectation, and the true gain is zero by construction. Push that through the identical pipeline and you get a "noise floor": the in-sample procedure reports gains of 1.8–3.6% on data where the truth is zero — the same order as the phantom gains above, and as the 2% "proceed" threshold the author had preregistered.

Two operating characteristics of this floor deserve attention. First, it is flat in both K (samples per instance) and N (instances) over the tested ranges — e.g., AM's floor is 3.16, 3.17, 3.08 at K = 400/600/800, and 3.05–3.44 across N = 10 to 50. You cannot buy your way out with a bigger experiment; a larger in-sample study is not a more trustworthy one. Second, the floor varies by 2× across solvers on the same problem (1.8 to 3.7), so nobody can borrow this paper's floor; it must be recomputed per configuration.

There's a nice technical detail buried here: naive greedy allocation on estimated curves isn't even feasible, because estimated marginals violate convexity 42% of the time (samples of a minimum order statistic are noisy), and sorting violated marginals can select an instance's j-th marginal without its (j{-}1)-th. The fix is taking the greatest convex minorant of each estimated curve before differencing — regularization toward a known property of the true f_i, not a modeling choice.

Where allocation is real: distribution shift

An in-distribution i.i.d. workload is the worst case for allocation: exchangeable instances plus convexity means uniform is optimal. The interesting regime is when the deployed workload departs from the training distribution — which is the ordinary condition in deployment. The author constructs a mixed workload: 50% uniform TSP-100, 50% clustered (four Gaussian clusters), served by a single fixed checkpoint. Clustered instances are out-of-distribution for all three checkpoints, with sharply different severity: AM's mean gap goes from 1.11% (uniform) to 38.63% (clustered), a 34.8× degradation; SymNCO 27.4×; POMO only 2.4× (it's mediocre everywhere and degrades mildly).

Rather than cherry-picking from an exploratory sweep (12 cells, 2 positive), the author preregistered a confirmatory experiment: new instance and decoding seeds, everything else frozen, endpoints declared in advance, no other tests. AM on stochastic sampling is the primary endpoint (sampling is AM's canonical inference mode); SymNCO is the replication; POMO — predicted in advance to show nothing, because it barely fails under shift — is the negative control.

All four registered endpoints passed. The gain ordering across solvers matches the shift-failure ordering (34.8× → 11.5%, 27.4× → 12.0%, 2.4× → −0.3%), and the negative control is the most informative cell: the same out-of-sample estimator that reads ~zero everywhere in-distribution, and ~zero on the shift-robust solver, reads 11–12% precisely where a solver collapses under shift. One procedure removes the phantom and keeps the real effect — that two-sidedness is what makes the correction credible rather than merely conservative.

Two more registered checks sharpen the result. A frozen distribution-label baseline — "if clustered, allocate 20× more" with ratios fixed from the exploratory pass — captures roughly two thirds of AM's gain; the residual of per-instance allocation over that baseline is 4.2 points [1.9, 7.7]. So the signal is more than the label, but the trivial rule is strong. And critically, the allocator never sees a distribution label: it consumes only the solver's own sample statistics on each instance. Allocation is available in the interval between a shift occurring and anyone noticing it — an asymmetry the paper rightly emphasizes over the cost argument versus retraining.

Paying for the signal

The registered 11–12% is headroom, not a deployable policy: d_{\text{split}} decides the allocation from 500 held-out samples per instance — five times the evaluation budget — without charging for them. An exploratory budget-accounted variant fixes this: spend 20 rollouts per instance as a probe (charged against the total budget, and kept as candidate solutions), allocate the remainder proportional to each probe's coefficient of variation, no reference tour needed. This retains 3.4% (AM) and 4.6% (SymNCO) at the 50:50 composition, with the negative control still at −0.4%.

The dependence on workload composition is surprising and non-monotone:

Three readings. At 0% OOD the charged policy is negative (−3.0%): it spends probe budget on a discrimination that doesn't exist — the audit result restated as a deployment cost. At a realistic 10% OOD share, the executable policy retains almost all the headroom (11.0 vs 11.7). And the registered 50:50 composition turns out to be less favorable than lower shares — so the headline can't be dismissed as an upper bound obtained by stacking the deck with hard instances. The author explicitly notes he expected proportionality, was contradicted by the sweep, and reports the correction rather than dropping it.

What to make of it, and what to be skeptical about

The prescriptions are simple and generalizable: report allocation gains out of sample; if you must report in-sample, calibrate against an instance-wise null at your own (N, K, S/N); don't expect scale to fix the bias; keep the evaluation budget shallow relative to stored depth (S/N \le K/4 enforced in code here). The mechanism is classical — optimizer's curse, White's Reality Check lineage — but the paper's point is that in NCO test-time allocation no such correction is standard, and the bias is exactly the size of the effects people would want to publish. The warning plausibly extends to the LLM test-time-compute literature, where adaptive-allocation gains are often reported without stating that decision and evaluation samples are disjoint (the paper credits Snell et al. as a published exception using cross-validation).

Reasons for caution. Everything is TSP-100 — CVRP was gated out because the reference solver's seed-to-seed spread (0.56–0.80%) exceeded a preregistered 0.05% stability bar, an honest but limiting exclusion. Three solvers substitute only partially for problem diversity, and the shift axis has three points with a chasm between 2.4× and 27.4×, so "gain orders with shift failure" is an ordering, not a dose–response. The 11–12% number always carries the "signal uncharged" qualification; the deployable version is 3–5% at 50:50. The composition sweep and charged policy carry no statistical tests. And this is a single-author study at small scale, though one whose reproducibility appendix (bit-for-bit array reproduction, SHA-256 digests, every number traceable to a named file) is unusually strong.

The most instructive part of the paper may actually be Appendix B, the full preregistration timeline: every amendment tabulated with the direction it moves the verdict, including two self-retractions — a discarded pooled null, and a retracted "floor grows with N" claim that was an artifact of a maximum-based floor definition, dropped even though it supported an appealing extreme-value narrative. The registered termination rule, keyed to d_{\text{in}}, returned "signal absence" on all four gate cells, and the paper reports that verdict as registered rather than repairing it retroactively. If you read one section beyond the tables, read Section III (the audit and floor construction) and then Appendix B — it's a working template for how to preregister an ML methods study, which is nearly nonexistent in this field and arguably the paper's most exportable artifact.