Spread and Scale: What Determines Whether Test-Time Budget Allocation Pays
cs.LG, cs.AI, math.OC
Submitted: 2026-08-21
Updated: 2026-08-21
Comments: 19 pages, 5 figures. Code, cost arrays, and the full pre-registration record (including every amendment and its direction) at https://github.com/nepersoned/best-of-k-allocation
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Terminology
Sources
- Sampling Luck Masquerades as Allocation Gain: Auditing Test-Time Budget Allocation for Neural Combinatorial Optimization
- RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark
- Large Language Monkeys: Scaling Inference Compute with Repeated Sampling
- Learning How Hard to Think: Input-Adaptive Allocation of LM Computation
- Neural Solver Selection for Combinatorial Optimization
- Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization
- Attention, Learn to Solve Routing Problems!
- POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
- How Good Is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problem
- Do ImageNet Classifiers Generalize to ImageNet?
- Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks