적응형 테스트 시점 스케일링을 위한 언제나 유효한 PAC-베이즈 보증
Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling
한국어 초록
테스트 시점 스케일링 시스템은 보정 데이터셋을 반복해 살펴본 뒤 표본을 얼마나 생성할지, 어떤 프롬프트를 쓸지, 어떤 검증기나 집계 규칙을 사용할지 고르는 경우가 많다. 이렇게 적응적으로 선택한 뒤에는 표준 검증 오차 막대가 유효하지 않다. 본 연구는 테스트 시점 스케일링 구성을 비용이 확률적으로 정해지는 무작위 예측기로 모델링한다. 모든 보정 시점, 구성에 대한 모든 사후 혼합분포, 데이터에 의존하는 모든 중단 규칙에 동시에 성립하는 시간 균일 PAC-베이즈 보증을 증명한다. 따라서 동일한 확률 사건은 최종 보고한 고정 구성뿐 아니라 배포 이전의 구성 탐색까지 포괄한다. 연산 예산과 검증기 후보가 유한한 경우 페널티는 익숙한 $\log M/n$이다. 최악의 경우 선택 이후에도 유효한 보증이라면 이 페널티를 피할 수 없다. 다만 구조가 있는 탐색에서는 균일하지 않은 사전분포와 국소화한 사후 혼합분포로 더 타이트한 보증을 얻을 수 있다. 이 결과를 자기 일관성에 적용해 상보적인 마진 법칙을 보인다. 최다 득표 방식은 정답이 생성기의 유일한 최빈값인 예시에서만 샘플 수에 따라 성능이 지수적으로 개선된다. 다른 예시에서는 연산을 늘릴수록 오차가 커질 수 있음을 증명할 수 있다. 같은 마진 분석으로 연산 배분을 위한 오라클 물 채우기 법칙도 도출한다. 합성 데이터를 이용해 적응적 예산 선택이 일으키는 낙관적 편향을 정량화했다. 또 gpt-4.1-mini의 출력을 사용한 GSM8K 예시 192개로 실제 추론 파이프라인의 위험과 비용을 함께 보고하는 방법을 보였다. 두 모델을 GSM8K와 MATH-500에서 더 큰 규모로 평가했을 때, 명목 수준이 5%인 상황에서 최선의 사후 선택 구성에 대한 오차 막대는 무작위 분할의 최대 22.5%에서 분할 밖 GSM8K 위험보다 낮았다. 제안한 보증은 그런 경우가 한 번도 없었다. GSM8K의 전체 테스트 분할에서는 보증이 0.109까지 좁아졌다. 별도 평가 분할에서 측정한 위험은 0.039였다. 이 결과는 적응형 추론 시스템의 위험과 연산량을 보고하는 데 사용할 수 있는 가볍고 분포 가정이 없는 방법을 제공한다.
원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
Accepted at NeurIPS 2026. Xiaoyu Li and Jiangxuan Long contributed equally. 31 pages, 7 figures, 15 tables