PaperlayerView exact revision on arXiv

Source-linked AI summary

Spread and Scale: What Determines Whether Test-Time Budget Allocation Pays

Jinhyung Bae

arXiv:2609.27917v1cs.LGcs.AImath.OC

TL;DR

The paper asks which workload properties determine whether reallocating a fixed sampling budget pays, and whether a policy still pays after charging for its own probe. Using registered workload comparisons, it finds that spread of severity is the stable predictor and that a charged policy recovers 60–82% of estimated headroom, while conclusions remain bounded by single-run confirmations.

  • Problem

    The companion study left open which workload properties predict allocation value and whether a policy remains worthwhile when its signal cost is counted.

    Source: §1.1 · p. 1

  • Method

    The study analyzes registered collections of 40-instance sets, measuring their spread, level, and allocation gain with level as a covariate.

    Source: §4.1 · p. 6

  • Results

    Spread of shift severity predicts allocation value across confirmations, and a policy charging for its probe recovers 60–82% of signal-free headroom.

    Source: §12 · p. 16

  • Takeaways & Limitations

    Within the studied workloads, spread is the stable workload statistic for estimating allocation value, whereas the level result is unsettled across knobs.

    Source: §12 · p. 16

    Confirmations are single runs, so further experiments require a new pre-registration.

    Source: §10 · p. 15

Abstract

from arXiv · show

Neural combinatorial optimization solvers generate many candidate solutions per instance and report the best one found, using the same sample budget for every instance regardless of difficulty. A companion study showed that reallocating a fixed budget toward harder instances can improve solution quality, but that the standard way of measuring this improvement is biased: deciding an allocation and evaluating it on the same data can manufacture an apparent gain even when none exists. This left open what property of a workload determines whether reallocation is worth doing, and whether a policy that spends part of the budget to decide how to allocate the rest still pays once that cost is counted. This paper answers both questions through pre-registered confirmatory experiments -- analysis and verdict criteria fixed before data collection -- across three independently trained solvers and two ways of constructing harder workloads on the traveling salesman problem. Within the workloads we study, the deciding property is how varied the instances within a workload are in difficulty, not how difficult the workload is on average: a uniformly easy or uniformly hard workload offers little room for reallocation, while a mixed workload offers substantial room. A budget-aware policy that pays for its own information about instance difficulty recovers most, though not all, of the improvement available when that information is assumed free. Every experiment was independently recomputed from its written specification, and every correction to an earlier version -- including two that weakened the paper's own claims -- is reported with the direction it moved the conclusion. The paper offers a specific empirical answer and a template for verifying that answer is not an artifact of how it was measured.

1. Introduction

The paper asks which workload properties predict whether budget reallocation pays and whether it remains worthwhile when the policy pays for its own signal. Its findings center on workload spread, while level-related results and several earlier claims require qualification.

1.1 What the companion paper left open

  • The companion study left open broader shift coverage, workload composition beyond a fixed 50%, and whether charging for the allocation signal changes the result.It had reported no detectable in-distribution gain, 11–12% out-of-sample gains under shift, and apparent same-data gains despite zero true gain.Source: §1.1 · p. 1

1.2 What we find

  • Within the studied workloads, spread of shift severity predicts whether allocation pays, while average severity level does not provide the same stable result.The spread finding was confirmed twice under one knob and on a replication solver under a second knob.Source: §1.2 · p. 2
  • The average-level endpoint passed under one knob but reversed under a second; post-hoc analysis linked it to instance scale.The scale interpretation survived a pre-specified check against unit normalization, but was not itself a registered endpoint.Source: §1.2 · p. 2
  • The budget-aware policy recovered a majority of estimated headroom, but did not significantly outperform a trivial label rule.The authors also report that workload composition adds nothing beyond spread for one solver and adds something for the other after controlling for level.Source: §1.2 · p. 2

1.3 Contributions

  • The contributions include preregistered confirmations, a second knob that disqualifies the level finding, a scale interpretation, composition tests, and a budget-accounted policy.The paper also reports amendment logs, including two amendments favorable to the authors and an unresolved internal inconsistency.Source: §1.3 · p. 2

1.4 What we do not claim

  • The authors do not claim an asymptotic theorem, causation, an independent level effect, or that their probe beats the audit’s statistic.Sets were constructed, but instances were not randomly assigned to severities; the level result reversed across knobs.Source: §1.4 · p. 2

1.5 What changed across versions

  • Earlier versions’ claims changed after reanalysis: a powered analysis reversed an initial null, same-array accounting reduced recovery to 60–82%, and a probe comparison remained nonsignificant.An independently written reimplementation matched the registered endpoints; the authors also report that the scale check survived while a range-restricted result fell between preregistered verdicts.Source: §1.5 · pp. 2–3

2. Setup

The setup formulates budget allocation as minimizing expected best-sample cost under a fixed total budget, then specifies the sampling, evaluation, and workload measures used to test it. A three-way split separates severity measurement, allocation decisions, and evaluation.

2.1 The allocation problem

  • The allocation problem minimizes total expected best-of-k cost under a fixed budget; because each cost curve is non-increasing and convex, greedy marginal allocation is optimal.If all instances share the same cost curve, uniform allocation is optimal, so observable workload properties must be tested to explain when allocation gains vary.Source: §2.1 · p. 3

2.2 Inherited machinery

  • The study uses stochastic decoding rollouts, offline replay on shared stored samples, and a gap-to-reference metric based on a frozen LKH-3 tour.Its primary d_split measure decides allocation and evaluates it on disjoint portions of each stored array; uncertainty uses instance bootstraps, and noisy gain curves are convexified before greedy allocation.Source: §2.2 · pp. 3–4

2.3 The three-way split

  • The three-way split assigns samples 0–200 to severity, 200–600 to allocation, and 600–1000 to evaluation; severity is measured at k = 1.This prevents sampling luck in the severity estimate from also making an instance appear allocation-friendly, though defining severity from a best-of-k curve would leave a subtler dependence.Source: §2.3 · p. 4

2.4 Shift severity and workload statistics

  • Instance severity is its expected k = 1 gap relative to the mean for 40 in-distribution instances; workload spread is the standard deviation of log severity, and level is its median.Severity is a multiple of the gap, not tour length; in one collection, a 257.1× severity corresponded to a gap of 772.6%, or a tour 8.73 times optimal.Source: §2.4 · p. 4

2.5 Solvers, instances, seeds

  • The experiments use pretrained POMO, AM, and Sym-NCO checkpoints on TSP instances, with two workload knobs: clustered points and varying instance size.Clustered instances use 100 nodes and four Gaussian centers; the size knob varies n from 100 to 200 while using a single 100-node checkpoint, and the paper calls both forms workload heterogeneity as seen by a fixed solver.Source: §2.5 · p. 4

3. Two Ways to Get the Wrong Answer

The section identifies two ways the earlier design could mislead: instance scale confounded severity, while the eight-bin analysis lacked power and made workloads too homogeneous to expose allocation headroom.

3.1 Why the knob is drawn per instance

  • Drawing σ per instance recovered a strong severity relationship (Spearman(σ, severity) = −0.846, p = 6 ×10−67); fixed levels were disrupted by cluster-centre placement.With sixteen instances per level, the largest adjacent severity ratio was 3.36×, above the pre-registered 3× criterion.Source: §3.1 · p. 5

3.2 The confound: severity is partly instance scale

  • Tightening clusters shortens optimal tours, making the same absolute error a larger gap; tour length and measured severity correlate −0.855 to −0.880 across solvers.Because gap divides excess by tour length, instance scale is entangled with the severity axis under the cluster knob.Source: §3.2 · p. 5
  • With scale uncontrolled, best-of-200 severity correlated negatively with gain (Spearman = −0.714, p = 0.047); controlling for scale changed it to +0.095.The negative association ran opposite to the natural expectation and was checked after the most severe instances were found to be shorter.Source: §3.2 · p. 5

3.3 The power failure: eight bins reject nothing

  • The eight-bin analysis could not establish that severity fails to predict gain: eight points lack power, especially after controlling for a covariate correlated at −0.88 with the axis.Its reported correlations were mostly nonsignificant, including AM severity (gap ratio) −0.095 (p = 0.82) and POMO severity (gap ratio) −0.333 (p = 0.42).Source: §3.3 · p. 5
  • Sorting and binning by severity made each bin homogeneous, suppressing the workload variation that allocation needs to have headroom.The paper identifies this as a design problem that more statistical power alone could not fix.Source: §3.3 · p. 5

4. Spread

The registered confirmations support spread as a predictor of allocation gains, but the level result reverses under a second workload-construction knob. Follow-up analysis ties that reversal to instance scale, while the size arm’s restricted spread range limits interpretation of its endpoint failure.

4.1 Design / 4.2 Two confirmations, cluster knob

  • Mean d_split in the top spread quartile was 9.13 (AM), 6.09 (SymNCO), and −0.45 (POMO) in confirmation 1.The registered design analyzed 200 sets of 40 instances drawn from random windows, with level as a covariate and confidence intervals bootstrapped over instances; Figure 1 shows spread’s partial rank correlation with out-of-sample gain.Source: §4.2 · p. 6, Figure 1 · p. 6, §4.1 · p. 6

4.3 Controlling for level strengthens the spread result

  • Controlling for level strengthened the spread association: AM rose from +0.655 to +0.744 and +0.661 to +0.791; SymNCO rose from +0.576 to +0.773 and +0.740 to +0.810.The authors conclude level variation obscures rather than manufactures the spread signal.Source: §4.3 · p. 6

4.4 The negative control, and where it failed

  • POMO’s spread range was six to eight times narrower than AM’s and its gain was negative across that range; confirmation 2’s registered negative-control interval nevertheless marginally excluded zero.The pipeline audit found no anomaly, and the registration documents gave conflicting definitions of the condition; the paper reports the governing document’s interval-based verdict.Source: §4.4 · p. 7

5.1 A registered endpoint that passed

  • Under the cluster knob, the registered level | spread endpoint passed: +0.544 [+0.308, +0.668] for AM and +0.599 [+0.187, +0.638] for SymNCO.The endpoint had been registered for a second confirmation after appearing as a post-hoc correction in an earlier manuscript version.Source: §5.1 · p. 7

5.2 A registered second knob that reversed it

  • The level term reversed under the size knob: AM and SymNCO level | spread estimates were −0.560 [−0.694, −0.363] and −0.598 [−0.712, −0.338], unlike their positive cluster-knob estimates.The second knob was registered because its scale confound was expected to run in the opposite direction; Figure 2 displays the severity- and length-axis comparisons.Source: §5.2 · p. 8, Figure 2 · p. 8

5.3 The size arm also failed the spread endpoint on the primary solver

  • The size arm missed AM’s registered spread | level endpoint: +0.157 [−0.030, +0.301] includes zero, and its spread range was roughly a quarter as wide as the cluster knob’s.POMO did move under the size knob, with a spread association of +0.270 [+0.161, +0.358], resolving that its cluster-knob flatness reflected the knob at least in that setting.Source: §5.3 · p. 9

5.4 What the level term tracks (post hoc, pre-specified)

  • Across both knobs, replacing severity with median optimal tour length yielded level | spread correlations from −0.53 to −0.60, consistent with shorter-instance workloads gaining more.That reading survived the pre-specified pure-absolute-length check: all four cells remained negative and excluded zero, so the authors conclude it is not a normalization artefact.Source: §5.4 · p. 9

6. Composition

The composition analysis finds no additional association beyond spread for AM, but SymNCO retains one after controlling for both spread and level. Composition itself is non-monotone in spread, with mixed workloads showing greater spread than uniformly shifted ones.

6.1 The mediation endpoint

  • With spread controlled, composition’s association with gain included zero for both AM (+0.092 [−0.197, +0.198]) and SymNCO (+0.069 [−0.047, +0.227]).The authors describe this as composition adding nothing beyond spread, not as a causal mediation result.Source: §6.1 · p. 10

6.2 With level also controlled, the solvers diverge

  • After controlling for spread and level, composition retained an association for SymNCO (+0.217 [+0.057, +0.314]) but not AM (+0.080 [−0.043, +0.183]).The registered interpretation therefore weakens the claim for SymNCO while retaining the original statement for AM.Source: §6.2 · p. 11

6.3 Why composition is non-monotone

  • Spread rises steeply from pure in-distribution composition, then falls as workloads become uniformly shifted; all-out-of-distribution workloads are homogeneous again in the relevant sense.This non-monotonic pattern accounts for the interior maximum in gain reported in an exploratory figure.Source: §6.3 · p. 11, Figure 4 · p. 11

7. A Policy That Pays for Its Own Signal

The policy spends part of its fixed budget probing each instance, then allocates the remainder using predicted value. Charging that probe reduces the apparent gain, and the learned signal is not shown to beat either comparison policy at significance.

7.1 Design

  • A probe of m rollouts per instance is charged against the budget, retained as candidate solutions, and used to allocate the remainder by predicted value.Seven probe-only features use no reference tour, including coefficient of variation and a decay exponent fitted to the probe’s best-of-j curve.Source: §7.1 · p. 12

7.2 Result, against a same-collection baseline

  • Reporting only the signal-free estimate would overstate the deployable gain by a factor of 1.7× on AM and 1.2× on SymNCO, respectively.Source: §7.2 · p. 12

7.3 Two comparisons that did not reach significance

  • The learned signal is not shown to outperform either the distribution-label rule or the coefficient-of-variation probe at significance.The CV comparison is significant only on the SymNCO replication arm; the label comparison reaches significance on neither arm.Source: §7.3 · pp. 12–13

7.4 Which statistic carries the signal

  • An exploratory held-out-feature attribution ranks median-to-minimum distance highest for AM and SymNCO, but does not establish that the CV statistic was the wrong choice.The paired test of that claim does not reach significance on the primary solver.Source: §7.4 · p. 13

7.5 Label allocation is actively harmful without shift

  • On POMO, label-based allocation returns −3.38 against signal-free headroom of 0.01, consistent with harm when the label is uninformative.The passage describes this as the most robust positive statement in the section.Source: §7.5 · p. 13

8. Why There Is No Single Scaling Law

The real-data results do not support a single ratio law for allocation bias. The ratio performs worst among the tested groupings, and the governing variable differs by solver.

8.1 The ratio law does not hold on real data

  • The ratio is the worst of the three tested groupings for all three solvers, and the governing variable differs by solver.This tests the audit’s synthetic-check-based ratio prescription on real data; the paper describes its account as empirical, not a derivation.Source: §8.1 · pp. 13–14, §8 · p. 13

8.2 An ordering, and a parameter we cannot yet use

  • The decay exponent α orders POMO, AM, then SymNCO, but its level changes with measurement setting, so it is used only as an ordinal descriptor.With three solvers, the reported ordering is explicitly not more than an ordering.Source: §8.2 · p. 14

8.3 Relation to the companion paper

  • This section tests the companion paper’s ratio prescription and replaces it with a solver-dependent account; it is presented as a continuation, not a refutation.The companion paper had stated that the prescription rested on synthetic checks, not real-data support.Source: §8.3 · p. 14

9. Prescriptions

The prescriptions emphasize workload spread, budget-accounted evaluation, and caution about average severity and allocation comparisons. They are framed within the paper’s tested setting.

9. Prescriptions

  • Estimate allocation value from the spread of shift severity across the workload; it is the only workload statistic that held under repeated confirmation.Controlling for level strengthens rather than weakens the result.Source: §9 · p. 14
  • Treat an apparent effect of average severity with suspicion: it passed a registered endpoint under one knob and reversed sign under another.The paper’s interpretation is that the level term measures instance scale.Source: §9 · p. 14
  • Do not use out-of-distribution share as the allocation variable: it adds nothing beyond spread on one solver and little on the other.The relation is non-monotone: an entirely shifted workload is described as as poor a candidate as one not shifted at all.Source: §9 · p. 14
  • Charge the probe against the budget when reporting a policy; signal-free and budget-accounted numbers differ by 40% on the same arrays.Source: §9 · p. 14
  • Do not allocate by a distribution label on a solver the workload does not disturb; label-driven allocation returned −3.38% against zero available headroom.Source: §9 · p. 14
  • Report out of sample, bootstrap over instances, and check confounds and power before treating a null as informative.The study produced a significant result in the wrong direction and a null that a better-powered design overturned.Source: §9 · p. 14

10. Limitations

The paper limits its claims by solver, workload construction, and problem class, and reports unresolved or unestablished findings. It also notes observational design and single-run confirmations.

10. Limitations

  • The spread result did not replicate under the size knob on the primary solver: AM’s registered endpoint failed, with an interval containing zero.The supplied passage gives AM’s interval as [−0.030, +0.301].Source: §10 · p. 14
  • Range restriction explains part, but not all, of the discrepancy between knobs; the estimate drops by roughly a quarter to a third when range is matched.Both range-restricted estimates remain positive and above the size knob’s +0.157, but the pre-specified verdict criteria did not fit the result cleanly.Source: §10 · p. 15
  • The level term remains unresolved: it passed a registered endpoint under one knob and reversed under another, while its proposed reading was post hoc.Source: §10 · p. 15
  • The negative control marginally failed in confirmation 2, and the two registration documents defined that condition inconsistently.Source: §10 · p. 15
  • Neither the label baseline nor the coefficient-of-variation probe is beaten at significance on the primary solver.Composition’s mediation is solver-dependent once level is controlled.Source: §10 · p. 15
  • The evidence is observational and limited to TSP on the stochastic-sampling axis; generalization to other NCO problem classes remains untested.Confirmations are single runs, and further experiments require a new pre-registration.Source: §10 · p. 15

11. Related Work

The paper argues that workload variation in shift severity predicts whether test-time budget allocation pays, while the average severity result remains unsettled. It also situates this question among simulation allocation, language-model test-time compute, and neural-solver selection research.

11. Related Work

  • Supplementary to its companion audit (Bae, 2026), this paper supplies new results rather than reusing that audit's findings.The audit provides estimators, reporting discipline, and the motivating open questions.Source: §11 · p. 15
  • It links instance-budgeting to OCBA, contrasts verifier-checked language-model budgets, treats shifted-instance degradation as given, and leaves runtime-aware solver selection open.The OCBA correspondence is structural, while a tail statistic rather than dispersion dominated probe attribution.Source: §11 · pp. 15–16

12. Conclusion

  • Workload spread in shift severity predicts whether test-time sampling-budget allocation pays; the result held across two pre-registered confirmations, three solvers, and a negative control.Controlling for average severity strengthened rather than weakened the relationship.Source: §12 · p. 16
  • The average-level endpoint passed and replicated on a second solver, but its sign reversed under a second registered shift knob, leaving its interpretation unsettled.Replacing severity with instance length made the two knobs agree: shorter-instance workloads gained more in gap and absolute-length units.Source: §12 · p. 16
  • A policy charging for its own probe recovered 60–82% of signal-free headroom, without significantly beating a distribution-label rule.The policy's recovery was reported on the same arrays used for the signal-free estimate.Source: §12 · p. 16
  • Across four manuscript versions, corrections weakened claims, and the scale reading that survived a unit check was independently recomputed before reporting.The authors report this correction history as part of the evidence in a setting where measurement discipline matters.Source: §12 · p. 16

Appendix A — Reproducibility

The appendices detail the materials and procedures used to reproduce the analyses, alongside a registration record that discloses amendments, their direction, and unresolved issues.

Appendix A — Reproducibility

  • Reproducibility checks specify legacy-checkpoint remapping, 280-instance collections with frozen LKH-3 references, and fixed severity, allocation, and evaluation slices.Checkpoint loading asserts zero missing and unexpected keys; each collection has 40 reference and 240 shifted instances.Source: Appendix A · pp. 17–18
  • Confirmatory analysis was hashed before collection completed, figures reuse stored arrays, and analyses run without a GPU after under-two-hour collection on one T4.Seeds, ordering, and bootstrap settings were frozen throughout.Source: Appendix A · p. 18
  • Registered endpoint tables and two pre-specified post-hoc tests were independently reimplemented from the pre-registration and matched to full precision.The archive includes file hashes and the frozen analysis-script hash for repeat recomputation against the same bytes.Source: Appendix A · p. 18

Appendix B — Pre-registration record

  • Supplementary registration documents disclose exploratory results and log amendment direction; two amendments were marked favorable to the conclusions.These redefined the negative control as a gain-magnitude bound and changed level control to a covariate with before/after reporting.Source: Appendix B · p. 18
  • The authors marked registering level as an endpoint and dropping the more favorable best-of-K severity scale as unfavorable amendments; inconsistent negative-control definitions remained unresolved.They judged the negative control by the document governing the run.Source: Appendix B · p. 18
  • The level endpoint had a pre-run estimated replication probability of 68% and passed; pre-specified post-hoc tests covered a scale unit check and a size-arm failure reanalysis.The unit check landed on a registered branch, while the range-restricted reanalysis did not.Source: Appendix B · pp. 18–19

Related papers

Loading 2609.27917v1…