跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.21241 · v1

Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling

首次提交 2026-11-16 23:23
版本更新 2026-11-16 23:23
雷达观测 2026-11-17 16:10
arXiv ↗PDF ↗

摘要

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 log⁡M/n\log M/n, 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.

作者备注:Accepted at NeurIPS 2026. Xiaoyu Li and Jiangxuan Long contributed equally. 31 pages, 7 figures, 15 tables

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 23:23 · 最新观测版本

Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling

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 log⁡M/n\log M/n, 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.

查看此版本解读 →查看此版本原文 ↗