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

This paper investigates whether instance-wise allocation of a fixed test-time sample budget in neural combinatorial optimization (NCO) solvers provides measurable gains over the conventional uniform allocation, and audits the measurement procedure itself.

Research questions. The paper poses two questions: Q1 asks how much instance-wise allocation buys relative to uniform allocation under a fixed total sample budget; Q2 asks whether the natural measurement procedure—collecting samples, estimating each instance's best-of-k curve, computing the optimal allocation, and reporting the improvement using the same samples—produces trustworthy numbers. The authors note that the allocation step is an explicit maximization over instances, and maximization over noisy estimates is exactly the setting in which selection bias is known to be severe—the optimizer's curse in decision analysis.

Problem setup. The allocation problem is formulated as minimizing Σi fi(ki) subject to Σi ki = S, where fi(k) is the expected cost of the best of k solutions for instance i. Since fi is non-increasing and convex (being the expectation of a minimum order statistic), greedy marginal allocation is optimal. The paper considers two allocation units: Axis A (stochastic decoding rollouts, the canonical inference mode for the Attention Model) and Axis B (the finite pool of the standard protocol, e.g., POMO's 800 deterministic trajectories for TSP-100). The allocating agent is a single fixed solver, while the workload is unconstrained. All policies are evaluated via offline replay on stored cost arrays, normalized to gap-to-reference using LKH-3 tours as the deterministic denominator.

Estimands. The paper defines d = (uniform − oracle)/uniform, the relative improvement in mean gap, reported through two estimators: d in (allocation decided and evaluated on the same stored array) and d split (allocation decided on one half of the stored array, evaluated on the other half). "In expectation d in is biased upward, because the allocation exploits the realized noise of the array it is scored on, and d split is biased downward, because the allocation is decided from half as much data as is available."

In-distribution audit results. On homogeneous workloads (50 uniform TSP-100 instances) with Axis B, S/N = 100, K = 800 pool, the in-sample estimates show gains of 2.2–2.6% with confidence intervals excluding zero for all three solvers (POMO: 2.227 [1.63, 2.82]; AM: 2.567 [1.96, 3.10]; SymNCO: 2.206 [1.61, 2.72]). However, the out-of-sample estimates are indistinguishable from zero: POMO 0.457 [−0.44, 1.34], AM 0.015 [−1.08, 1.06], SymNCO −0.512 [−1.79, 0.38]. The paper states: Read the first numeric column alone and every row is a finding... Read the second column and there is nothing. Against the instance-wise noise floor (median of per-source p95 values), AM and SymNCO sit below both the median and p90 variants, while POMO's d in of 2.227 sits marginally above its median floor of 2.083 and below its p90 floor of 4.211.

Instance-wise null construction. To calibrate d in, the authors construct a null where the true allocation gain is zero by construction: resampling with replacement from a single instance's stored array creates N synthetic exchangeable instances sharing that instance's marginal cost distribution. The floor is reported as the median of per-source p95 values (with p90 as a conservative variant), not the maximum, because the maximum diverges with the number of source instances (for SymNCO on Axis A, growing from 20.1 at 8 sources to 90.4 at 50 sources due to heavy tails). The paper notes it discarded a pooled null because under a size- or distribution-mixed workload the pool has greater dispersion than any real instance, so the resulting floor is inflated.

Operating characteristics of the floor. The floor is approximately flat in both the number of stored samples per instance K (POMO: 1.705 at K=400 to 1.840 at K=800; AM: 3.157 to 3.080; SymNCO: 4.182 to 3.747) and the number of instances N (POMO: 2.072 at N=10 to 1.840 at N=50; AM: 3.049 to 3.080; SymNCO: 3.810 to 3.747). The paper concludes: The floor does not come down with more samples per instance, and it does not come down with more instances: over the ranges we test it does not come down with scale, and correction is the only exit we have found. The paper also retracts an earlier claim that the floor grows with N, noting this was produced under the discarded maximum-based definition and the comparison additionally confounded N with the number of source instances.

Distribution-shift confirmatory experiment. The paper constructs a mixed workload of 50 instances (25 uniform TSP-100 and 25 clustered TSP-100 with four Gaussian clusters, σ = 0.06), served by the same single checkpoint. A pre-registered confirmatory experiment with new instance and decoding seeds, N = 100 instances, K = 1,000, S/N = 100, declared endpoints, and no tests beyond them found: AM (primary endpoint) d split = 11.549 [7.401, 19.734], passing the CI lower ≥ 2% criterion; SymNCO (replication) = 12.017 [5.183, 19.982], also passing; POMO (negative control) = −0.290 [−0.720, 0.238], with interval covering zero as predicted. The residual over a frozen distribution-label baseline (greedy minus label, both out of sample) is 4.204 points [1.862, 7.702] for AM, showing roughly two thirds of the AM gain is available from the label alone, and a third requires per-instance information.

Gain tracks failure. The ordering of allocation gain matches the ordering of shift failure across solvers: AM (uniform gap 1.11%, clustered gap 38.63%, ratio 34.8×, d split 11.549), SymNCO (0.87%, 23.79%, 27.4×, 12.017), POMO (7.16%, 17.36%, 2.4×, −0.290). The paper states: We state this as an ordering across three solvers. With three points and a gap between 2.4× and 27.4×, we do not characterize the relationship as a dose–response.

Budget-charged probe policy (exploratory). A deployable policy draws a probe of m = 20 rollouts per instance (charged against the total budget S = 100N and retained as candidate solutions), allocates the remaining S − mN in proportion to each probe's coefficient of variation, and reports the best of each instance's ki samples. Results: AM 3.394 [0.609, 7.564], SymNCO 4.588 [1.623, 10.541], POMO −0.391 [−1.002, 0.126]. Probe size sensitivity for AM: 3.36 (m=5), 3.76 (m=10), 3.39 (m=20), 2.81 (m=40). The paper notes: The effect survives budget accounting but shrinks by roughly a factor of three.

Composition sweep (exploratory). Varying the out-of-distribution share with N = 50 and S/N = 100, averaging over 12 resampled workloads: at 0% OOD share, d split = 1.586 and d charged = −3.018; at 10%, 11.740 and 11.001; at 25%, 18.161 and 11.201; at 50%, 12.760 and 3.052. The paper states: Dependence on composition is real but it is not proportional. The sweep suggests an interior peak... the registered 50:50 composition is not the composition most favourable to allocation. At fully in-distribution workloads, the charged policy is negative (−3.0): it spends a probe budget on a discrimination that does not exist.

Prescriptions. The paper provides a checklist: (1) report allocation gains out of sample via splitting; (2) if an in-sample number must be reported, calibrate it against the instance-wise null at your own (N, K, S/N); (3) do not expect scale to fix the floor, which is flat in both K and N; (4) keep the budget shallow relative to stored depth (S/N ≤ K/4 as a hard assertion); (5) for in-distribution homogeneous workloads, uniform allocation is an adequate default within detection limits, while for shifted workloads allocation is worth measuring and retains 3–5% at 50:50 composition (11.0% at 10% shifted share, exploratory) even when the probe is charged.

Limitations. The paper acknowledges: only three points on the shift axis (2.4×, 27.4×, 34.8×); workload composition is a design choice and not the most favourable one; all results are TSP-100 (CVRP was gated out because the reference solver's seed-to-seed spread of 0.80% at 5 seconds exceeded the pre-registered 0.05% stability requirement); the registered endpoint is not budget-accounted (d split uses 500 samples to decide allocation against a 100-sample evaluation budget); and transparency of amendments is documented in Appendix B, including amendments that work against the paper's own narrative.

Conclusion. "Instance-wise allocation of a test-time sample budget buys nothing measurable for neural combinatorial optimization solvers on the workloads those solvers were trained for. On a workload half of which lies outside that distribution it buys 11–12% at equal evaluation budget with the guiding signal free, and an exploratory policy that charges a 20-sample probe against the same budget retains 3.4% at that composition and 11.0% at a more realistic 10% shifted share—in every case without needing to know that the shift occurred. The procedure conventionally used to measure such gains—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, an amount that, over the ranges we test, diminishes neither with more samples per instance nor with more instances. Reporting the gain out of sample removes the phantom and leaves the real effect standing."

Based on the paper, here are specific improvements to AI systems:

1. Add out-of-sample evaluation for adaptive resource allocation. When an AI system adaptively allocates compute or sampling budgets across instances, it must evaluate the allocation on held-out data (e.g., split the budget into a decision set and an evaluation set). This prevents the optimizer’s curse—where in-sample gains are inflated by noise exploitation. The improved system will report both in-sample and out-of-sample metrics, and only trust gains that persist out of sample.

2. Implement a null-calibration floor for adaptive gains. Before claiming any benefit from instance-wise allocation, the system should construct a null distribution by resampling from a single instance’s stored outcomes to create exchangeable synthetic instances. The system will compare its measured gain against the median (or p90) of this null floor at the same (N, K, S/N) settings. If the gain is below the floor, it is indistinguishable from noise. This prevents false positives in adaptive sampling.

3. Use a probe-then-allocate policy with budget accounting. For deployment, the system will draw a small probe (e.g., 20 rollouts per instance) charged against the total budget, compute the coefficient of variation from the probe, and allocate the remaining budget proportionally. This policy retains real gains under distribution shift (e.g., 3.4% at 50% shifted share) without needing to know the shift occurred. The improved system will always charge probe costs against the total budget, avoiding overestimation.

4. Detect distribution shift via allocation gain magnitude. The system will monitor the out-of-sample allocation gain (d split) as a signal for distribution shift. If the gain exceeds a pre-computed threshold (e.g., >2% CI lower bound), the system flags that the workload may be out-of-distribution and triggers re-training or adaptation. This works because gain tracks failure: solvers with high shift (e.g., 34.8× gap ratio) show large gains, while in-distribution workloads show near-zero gains.

5. Replace uniform allocation with label-aware allocation under shift. For workloads with known or suspected shift, the system will use a frozen distribution-label baseline (e.g., cluster vs. uniform) to allocate budget first, then add per-instance information only if it improves beyond the label. This captures two-thirds of the gain from labels alone, with the remainder from per-instance details. The improved system will combine both signals, not rely solely on instance-wise optimization.

6. Set budget depth relative to stored samples. The system will enforce a hard constraint that the per-instance sample budget (S/N) is at most one-quarter of the stored depth (K). This prevents overfitting to noise when the allocation is decided on the same samples used for evaluation. The improved system will automatically cap S/N ≤ K/4 to maintain valid measurements.

7. Avoid scale-based fixes for selection bias. The system will not assume that increasing the number of instances (N) or samples per instance (K) reduces the null floor—it is flat across tested ranges (e.g., POMO floor 1.705–1.840 for K=400–800). Instead, the system will use explicit correction (e.g., splitting) as the only reliable exit. This prevents wasted compute on larger experiments that do not reduce bias.

8. Use composition-aware allocation policies. For mixed workloads, the system will not assume a linear relationship between shifted share and gain. The gain peaks at intermediate compositions (e.g., 25% shifted share gives 18.2% d split vs. 12.8% at 50%). The improved system will sweep composition during validation to find the optimal operating point, rather than assuming a fixed 50:50 mix is best.

9. Implement a negative control for allocation policies. The system will always include a solver known to be robust to shift (e.g., POMO with low shift ratio) as a negative control. If the allocation gain for this control is not near zero, the measurement procedure is suspect. This provides a built-in sanity check for any adaptive allocation system.

10. Report confidence intervals and pre-registered endpoints. The system will pre-register primary endpoints, declare all tests, and report confidence intervals (not just point estimates) for allocation gains. This prevents p-hacking and ensures that reported improvements are statistically reliable. The improved system will automatically generate these reports for any adaptive resource allocation decision.