Spread and Scale: What Determines Whether Test-Time Budget Allocation Pays
Abstract
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.
Related
- Comparing Socially-Equitable Renewable Energy Budget Allocation MDP Policies in Mature and Emerging Economies
- Random Forest-Informed Cellular Automaton for Large-Scale Wildfire Spread Modelling
- Certifying Whether to Adapt: Baseline-Relative PAC-Bayes-MMD Guarantees for Test-Time Adaptation
- Perfect Reconstruction Cannot Show Whether Two Codebooks on a VAE's Latent Space Agree
- Stand-In Effects and Pooling Amplification: Design-Based Tests of Whether Biological World Models Use Actions
BibTeX
@misc{bae2026spread,
title = {{Spread and Scale: What Determines Whether Test-Time Budget Allocation Pays}},
author = {Jinhyung Bae},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27917},
eprint = {2609.27917},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27917},
}
RIS
TY - UNPB
TI - Spread and Scale: What Determines Whether Test-Time Budget Allocation Pays
AU - Jinhyung Bae
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.27917
UR - https://arxiv.org/abs/2609.27917
AB - 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.
ER -