Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling
Li and Long
It gives a time-uniform PAC-Bayes bound that stays valid after a test-time recipe is tuned on the same calibration data, and proves that plurality voting improves exponentially in the sample budget only where the correct answer is the generator’s unique mode; elsewhere more samples can amplify errors.
- Prerequisites
- PAC-Bayes bounds, martingale concentration for time-uniform bounds, and the basic analysis of majority voting.
- Focus on
- Sections 4, 6 and 7
- Reading time
- About 3 hours
arXiv:2611.21241
Optimal Autoregressive Chain-of-Thought Learning via Bagging
Altabaa et al.
A majority vote over \(O(\log(T/\delta))\) generators trained on bootstrap samples learns from chain-of-thought demonstrations with the optimal \(O((d_{\mathrm{VC}} + \log(1/\delta))/\epsilon)\) sample complexity, independent of the chain length \(T\).
- Prerequisites
- PAC learning and VC dimension, leave-one-out arguments, and the one-inclusion or bagging proofs of optimal PAC learners.
- Focus on
- Sections 3 and 5
- Reading time
- About 2 hours
arXiv:2611.21597