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

Xiaoyu Li, Jiangxuan LongarXiv 2026 · arXiv

In the rapidly evolving world of Large Language Models (LLMs), we’ve moved beyond simple "one-shot" generation. Modern systems use test-time scaling—techniques like self-consistency, best-of-N sampling, and verifier-guided search—to trade extra compute for better accuracy.

But there’s a statistical catch. When a researcher sweeps through dozens of prompts, temperatures, and sample budgets on a validation set to find the "best" configuration, standard error bars lose their meaning. This "peeking" at the data leads to optimistic bias.

A new paper from researchers at the University of New South Wales and The University of Hong Kong, titled "Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling," provides a rigorous solution. They introduce a framework to certify the risk and compute cost of these adaptive systems without making parametric assumptions about the data.

TL;DR

The authors provide a "time-uniform" PAC-Bayes certificate that remains statistically valid even after you’ve adaptively searched for the best inference strategy. It offers a distribution-free way to report the risk-compute tradeoff of LLM pipelines, ensuring that reported performance isn't just a result of "overfitting" to your calibration set.

What Problem Does This Paper Address?

In practice, building an LLM reasoning pipeline is an iterative process. You might try five different prompts, three different sampling temperatures, and various "early stopping" rules. You look at a calibration (validation) curve, pick the point that looks best, and report that as your system's performance.

Statistically, this is a model-selection problem with optional stopping. Standard confidence intervals assume the model was fixed before seeing the data. If you choose the model after seeing the data, those intervals are "invalid"—they will frequently underestimate the true error rate.

The challenge is: how can we provide a "certificate" (a high-probability upper bound on error) that accounts for this adaptive search and holds true regardless of when we decide to stop our audit?

Methods

The authors leverage PAC-Bayes theory, specifically a "time-uniform" version. Here’s the breakdown of their approach:

  1. Randomized Recipes: They model any test-time scaling strategy (e.g., "sample 10 times and take the majority vote") as a recipe—a randomized predictor with an associated random cost.
  2. Time-Uniformity: Using a "stitching argument," they prove a certificate that holds simultaneously for all possible calibration sizes ($n$) and all possible "posteriors" (distributions over recipes chosen after seeing the data). This means you can monitor the audit in real-time and stop whenever you like.
  3. Binary-kl Bounds: The certificate is expressed using binary relative entropy ($kl$), which is particularly sharp for the low-error regimes common in LLM tasks.
  4. Margin Law for Self-Consistency: They specialize their theory to "self-consistency" (majority voting). They prove that more compute only helps exponentially if the correct answer is already the model's unique mode. If the model is "confidently wrong," more compute actually amplifies the error.
Table 1: Examples of test-time scaling recipes covered by the framework, with representative prior uses in LLM reasoning.

Datasets

The authors validated their framework using:

  • Synthetic Audits: To quantify the "optimism" caused by adaptive selection.
  • GSM8K (Grade School Math): A 192-example pilot audit and a full-scale audit using gpt-4.1-mini.
  • MATH-500: Used for scale-up tests with Qwen2.5-7B.

Key Insights and Ideas

  • The Selection Penalty: Choosing the best of $M$ recipes isn't free. It incurs a penalty of roughly $\sqrt{\log M / n}$. The authors show this penalty is fundamentally unavoidable for any distribution-free certificate.
  • Compute Isn't a Monotone Safety Guarantee: The "Margin Law" is a crucial "aha" moment. It explains why simply increasing the sample budget ($b$) can be dangerous. If a wrong answer is the mode of the generator, increasing $b$ makes that wrong answer more stable, not less.
  • Oracle Water-Filling: Based on their margin analysis, they derive an optimal way to allocate compute: don't waste samples on "easy" (high margin) or "impossible" (negative margin) questions. Instead, "pour" compute into "contestable" examples where the margin is small but positive.
Figure 1: Synthetic audit showing how majority voting helps only on the positive-margin side and how the PAC-Bayes certificate covers the true risk.

Key Results

  • Reliability: In random splits of GSM8K data, standard "naive" error bars fell below the true out-of-split risk in up to 22.5% of cases (at a nominal 5% failure rate). The PAC-Bayes certificate never failed to cover the true risk.
  • Tightness at Scale: On the full GSM8K test split ($n=659$), the certificate for a gpt-4.1-mini pipeline tightened to 0.109, providing a rigorous upper bound for a held-out risk of 0.039.
  • Audit Efficiency: The "anytime-valid" nature allows auditors to stop early. For example, an auditor targeting a risk of 0.15 could have stopped after only 153 examples on the GSM8K audit.
Figure 3: Real GSM8K audit for gpt-4.1-mini. The certificate (blue) provides a valid upper bound for the selected budget.

Limitations and Future Work

  • I.I.D. Assumption: The certificate assumes examples are independent and identically distributed. It does not account for distribution shift (e.g., if the deployment data looks different from the calibration data).
  • Numerical Looseness: For very small datasets (e.g., $n < 32$), the bounds can be quite loose, though they tighten rapidly as $n$ increases.
  • Scope of Certification: The framework certifies risk (error rate) and cost, but it doesn't certify the "truthfulness" of the model's reasoning steps or its safety in unmeasured ways.
  • Future Directions: The authors suggest extending this to "ranking" recipes (proving one is better than another) and developing more sophisticated priors for structured search spaces.

In summary, this work provides the "missing manual" for rigorously reporting the performance of adaptive LLM systems, moving us away from "vibe-based" validation toward verifiable engineering.

Summary updated

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 $\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.
BibTeX
@misc{li2026anytime,
  author = {Xiaoyu Li and Jiangxuan Long},
  title = {{Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling}},
  year = {2026},
  eprint = {2611.21241},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21241},
}
Figure