Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling
Li and Long
A time-uniform PAC-Bayes certificate stays valid after a test-time scaling recipe is chosen adaptively, and a margin law shows when plurality voting helps and when more samples hurt.
Source published · In the Daily Brief of 18 November 2026
Filed under Reasoning and inference, Learning theory
Test-time scaling systems pick a sample budget, a prompt and a verifier or aggregation rule after repeatedly looking at a calibration set, and ordinary validation error bars are not valid after such selection. The authors model a recipe as a randomised predictor with a random cost and prove a PAC-Bayes certificate that holds simultaneously over all calibration times, all posterior mixtures over recipes and all data-dependent stopping rules.
For a finite grid of \(M\) budgets and verifiers with \(n\) calibration examples the penalty is of order \(\log M / n\), which the authors show no certificate valid after selection can avoid in the worst case. Specialised to self-consistency, a margin analysis shows that plurality voting improves exponentially in the sample budget only on examples where the correct answer is the generator’s unique mode; otherwise more compute can amplify errors. The same analysis gives a water-filling rule for allocating compute.
On GSM8K, selected-best error bars fell below the out-of-split risk in up to 22.5% of random splits at a nominal 5%, while the certificate never did. The paper was accepted at NeurIPS 2026.