Research map / Large language models / Reasoning and chain of thought
Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling
Xiaoyu Li, Jiangxuan Long
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves a time-uniform, anytime-valid PAC-Bayes certificate for test-time scaling recipes that stays valid under adaptive selection over sampling budget, prompt, and verifier choices on a calibration set.
Problem
Test-time scaling systems select sampling budget, prompt, and verifier/aggregation rule by repeatedly inspecting a calibration set, so standard validation error bars become invalid after this adaptive selection.
Approach
Models a test-time scaling recipe as a randomized predictor with a random cost and derives a PAC-Bayes bound that holds simultaneously over all calibration times and adaptive choices (anytime-valid), rather than a fixed-sample validation bound.
Experimental setup
Builds on: PAC-Bayes bounds
Closest papers by meaning
- Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification (ICML 2025 · similarity 0.86)
- Kinetics: Rethinking Test-Time Scaling Law (NeurIPS 2025 · similarity 0.86)
- ATTS: Asynchronous Test-Time Scaling via Conformal Prediction (ICLR 2026 · similarity 0.86)
- Evaluation of Test-Time Adaptation Under Computational Time Constraints (ICML 2024 · similarity 0.85)
- Calibration without labels in multiple testing (NeurIPS 2026 · similarity 0.85)
- Scaling Test-Time Compute Without Verification or RL is Suboptimal (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
