arXiv:2611.21241v1 cs.LG

적응형 테스트 시점 스케일링을 위한 언제나 유효한 PAC-베이즈 보증

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

Xiaoyu Li, Jiangxuan Long

제출 2026-11-16

저자 비고

arXiv Comments

Accepted at NeurIPS 2026. Xiaoyu Li and Jiangxuan Long contributed equally. 31 pages, 7 figures, 15 tables

한국어 초록

테스트 시점 스케일링 시스템은 보정 데이터셋을 반복해 살펴본 뒤 표본을 얼마나 생성할지, 어떤 프롬프트를 쓸지, 어떤 검증기나 집계 규칙을 사용할지 고르는 경우가 많다. 이렇게 적응적으로 선택한 뒤에는 표준 검증 오차 막대가 유효하지 않다. 본 연구는 테스트 시점 스케일링 구성을 비용이 확률적으로 정해지는 무작위 예측기로 모델링한다. 모든 보정 시점, 구성에 대한 모든 사후 혼합분포, 데이터에 의존하는 모든 중단 규칙에 동시에 성립하는 시간 균일 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 원문에서 확인하세요.

  1. arXiv:2611.21241v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.