Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling
Organizations: The University of Hong Kong
Abstract
Test-time scaling systems often choose how much to sample, which prompt to use, and which verifier or aggregation rule to trust after repeatedly inspecting a calibration set. Standard validation error bars are not valid after this adaptive selection. We model a test-time scaling recipe as a randomized predictor with a random cost and prove a time-uniform PAC-Bayes certificate that holds simultaneously over all calibration times, all posterior mixtures over recipes, and all data-dependent stopping rules. Thus the same event covers the recipe search that precedes deployment, not merely the fixed recipe finally reported. For a finite grid of budgets and verifiers, the penalty is the familiar , which in the worst case no certificate valid after selection can avoid, while non-uniform priors and localized posterior mixtures can give sharper certificates for structured searches. We specialize the result to self-consistency and show a complementary margin law: 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 provably amplify errors. The same margin analysis yields an oracle water-filling law for compute allocation. A synthetic audit quantifies the optimism caused by adaptive budget selection, and a 192-example GSM8K audit using gpt-4.1-mini generations illustrates risk-cost reporting for a real inference pipeline. At scale, with two models on GSM8K and MATH-500, selected-best error bars fall below the out-of-split GSM8K risk in up to 22.5% of random splits at a nominal 5% while the certificate never does, and on the full GSM8K test split it tightens to 0.109 (held-out risk 0.039). The results give a lightweight, distribution-free way to report risk and compute claims for adaptive inference systems.
Figures & tables
| Recipe family | Random prediction | Random cost |
| Self-consistency [ 33 , 31 ] | Sample traces and take deterministic plurality over extracted answers. | Total generated tokens or wall-clock time for the traces. |
| Verifier best-of- [ 11 ] | Generate candidates and return the candidate with the largest verifier score. | Generator cost plus verifier scoring cost. |
| Early stopping [ 1 , 21 ] | Sample until a vote-margin, entropy, or verifier threshold is reached, up to a maximum budget. | Bounded compute that depends on the stopping time. |
| Router or mixture [ 8 ] | Choose among prompts, models, or aggregators; a posterior may randomize among recipes. | Cost of the selected route, normalized by a predeclared envelope. |
| Data | Model | Selected | Calib. risk | Held-out risk | Certificate | ||
| GSM8K (192) | gpt-4.1-mini | 4 | 96 | 0.021 | 0.010 | 0.219 | |
| GSM8K | gpt-4.1-mini | 4 | 659 | 0.039 | 0.039 | 0.109 | |
| GSM8K | Qwen2.5-7B | 7 | 659 | 0.062 | 0.073 | 0.144 | |
| MATH-500 | gpt-4.1-mini | 4 | 250 | 0.280 | 0.296 | 0.470 | |
| MATH-500 | Qwen2.5-7B | 4 | 250 | 0.300 | 0.268 | 0.491 |
Appendix figures & tables19 assets
Supplementary material from the paper’s appendix.
Appendix
| Budget | Calib. risk | Held-out risk | Certificate | Mean calib. tokens |
| 1 | 3/96 | 4/96 | 0.240 | 205 |
| 3 | 2/96 | 1/96 | 0.219 | 616 |
| 5 | 2/96 | 2/96 | 0.219 | 1024 |
| 9 | 2/96 | 2/96 | 0.219 | 1839 |
| Selected | Calib. risk | Held-out risk | Certificate | Mean tokens | |
| 32 | 3 | 0.000 | 0.019 | 0.350 | 634 |
| 64 | 3 | 0.000 | 0.023 | 0.215 | 624 |
| 96 | 3 | 0.021 | 0.010 | 0.219 | 616 |
| 128 | 3 | 0.023 | 0.000 | 0.191 | 626 |
| 160 | 3 | 0.019 | 0.000 | 0.159 | 635 |
| Mean held-out risk | Median certificate | |||
| 32 | 0.482 | 0.518 | 0.028 | 0.350 |
| 64 | 0.198 | 0.802 | 0.022 | 0.264 |
| 96 | 0.065 | 0.935 | 0.018 | 0.193 |
| 128 | 0.013 | 0.987 | 0.017 | 0.174 |
| 160 | 0.001 | 0.999 | 0.015 | 0.159 |
| Sel. empirical | Sel. true | Sel. upper | Oracle true | Modal | Coverage | |
| 64 | 0.256 | 0.297 | 0.603 | 0.282 | 17 | 1.000 |
| 128 | 0.271 | 0.292 | 0.529 | 0.282 | 33 | 1.000 |
| 256 | 0.276 | 0.289 | 0.467 | 0.282 | 33 | 1.000 |
| 512 | 0.278 | 0.286 | 0.417 | 0.282 | 33 | 1.000 |
| 1024 | 0.280 | 0.285 | 0.381 | 0.282 | 65 | 1.000 |
| Sel. empirical | Optimism | Fixed upper | Fixed cov. | PB upper | PB cov. | |
| 2 | 0.482 | 0.018 | 0.558 | 0.986 | 0.666 | 1.000 |
| 4 | 0.467 | 0.033 | 0.544 | 0.970 | 0.655 | 1.000 |
| 8 | 0.456 | 0.044 | 0.532 | 0.943 | 0.648 | 1.000 |
| 16 | 0.445 | 0.055 | 0.521 | 0.890 | 0.641 | 1.000 |
| 32 | 0.435 | 0.065 | 0.512 | 0.789 | 0.635 | 1.000 |
| 64 | 0.427 | 0.073 | 0.503 | 0.620 | 0.630 | 1.000 |
| Budget | Uniform mass | Complexity mass | Uniform upper | Complexity upper |
| 1 | 0.143 | 0.723 | 0.073 | 0.067 |
| 3 | 0.143 | 0.108 | 0.073 | 0.074 |
| 5 | 0.143 | 0.065 | 0.073 | 0.076 |
| 9 | 0.143 | 0.042 | 0.073 | 0.078 |
| 17 | 0.143 | 0.028 | 0.073 | 0.079 |
| 33 | 0.143 | 0.020 | 0.073 | 0.080 |
| Sweep (GSM8K) | Sel. Wilson | Fixed Wilson | Sel. Hoeffding | Certificate | Optimism | |
| gpt-4.1-mini, budgets | 4 | 8.7% | 5.4% (6.9%) | 0.0% | 0.0% | 0.005 |
| Qwen, budgets | 5 | 8.1% | 4.2% (4.6%) | 0.0% | 0.0% | 0.008 |
| gpt-4.1-mini, recipe grid | 25 | 22.5% | 5.6% (9.1%) | 0.0% | 0.0% | 0.014 |
| Qwen, recipe grid | 27 | 21.6% | 6.8% (9.7%) | 0.0% | 0.0% | 0.020 |
| evaluation | recipe | cal. risk | held-out risk | certificate | mean tokens |
| GSM8K, gpt-4.1-mini | 39/659 | 0.052 | 0.138 | 162 | |
| 27/659 | 0.041 | 0.112 | 485 | ||
| 26/659 | 0.039 | 0.109 | 808 | ||
| 26/659 | 0.038 | 0.109 | 1454 | ||
| GSM8K, Qwen2.5-7B | 67/659 | 0.097 | 0.196 | 257 | |
| ES(2,5) | 46/659 | 0.080 | 0.154 | 582 |
| grid | recipe (template/temperature/rule) | cal. risk | held-out | certificate | tokens |
| Qwen, | P1/T1.0/ | 0.056 | 0.072 | 0.198 | 755 |
| P2/T1.0/ | 0.056 | 0.056 | 0.198 | 1624 | |
| P0/T1.0/ | 0.056 | 0.064 | 0.198 | 2337 | |
| P0/T1.0/ | 0.060 | 0.068 | 0.204 | 1306 | |
| P1/T1.0/ | 0.060 | 0.068 | 0.204 | 1355 | |
| P2/T0.7/ | 0.060 | 0.060 | 0.204 | 1606 |
| Risk | 0.01 | 0.02 | 0.05 | 0.10 | 0.20 |
| , grid of | 8,917 | 4,076 | 1,387 | 571 | 201 |
| , grid of | 9,546 | 4,388 | 1,507 | 626 | 223 |
| Recipes | Uniform: selected cal. / held-out / bound | Uniform: default winner | Localized |
| 337 | 0.052 / 0.076 / 0.203 | 0.203 | 0.199 |
| 1,012 | 0.048 / 0.056 / 0.201 | 0.207 | 0.199 |
| 2,787 | 0.044 / 0.072 / 0.198 | 0.212 | 0.199 |
| threshold | penalty | certified | certified |
| 512 | 1.39 | 1.000 | 1.000 |
| 1,024 | 2.48 | 1.000 | 1.000 |
| 2,048 | 3.18 | 0.979 | 0.732 |
| 4,096 | 3.69 | 0.688 | 0.054 |
| 8,192 | 4.09 | 0.410 | 0.036 |
| 16,384 | 4.43 | 0.251 | 0.036 |
| threshold | penalty | certified | true | certified | true |
| 256 | 1.39 | 0.975 | 0.914 | 0.888 | 0.775 |
| 512 | 2.48 | 0.882 | 0.777 | 0.657 | 0.525 |
| 1,024 | 3.18 | 0.713 | 0.576 | 0.394 | 0.264 |
| 2,048 | 3.69 | 0.519 | 0.368 | 0.227 | 0.093 |
| 4,096 | 4.09 | 0.349 | 0.207 | 0.109 | 0.022 |
| 8,192 | 4.43 | 0.233 | 0.108 | 0.066 | 0.003 |
Test-Time Scaling
Test-time scaling studies how extra inference-time computation can improve model answers, decisions, and generated outputs.
See all 242 papers