[Paper Review] Majority of the Bests: Improving Best-of-N via Bootstrapping

문제

방안

주요 기여

1. BoN의 출력이 불완전한 Reward에서 확률적 특성을 갖는다는 점을 분석하고, 분포의 mode가 단일 샘플보다 신뢰할 수 있음을 보임

2. 부트스트래핑 기반으로 BoN 출력 분포를 추정하고 mode를 선택하는 MoB 알고리즘 및 적응적 서브샘플 크기 선택 절차 제안

3. 부트스트래핑 추정의 consistency에 대한 이론적 보장 제공

배경 및 동기

기존 선택 메커니즘의 구도

• N개 출력을 생성하고, 최종 답 중 가장 빈번한 것을 선택 (다수결)

• Reward Model 불필요

• 정답이 최빈값일 때 효과적이지만, 기저 모델의 생성 확률에 전적으로 의존

• N개 출력을 생성하고, Reward Model이 가장 높은 점수를 준 출력을 선택

• 완벽한 Reward Model이면 거의 100% 정답 선택 가능

• 현실적으로 Reward가 불완전하여 성능 저하 발생

• 각 최종 답에 대해, 해당 답에 도달하는 모든 출력의 Reward를 합산

• 가장 높은 총 Reward를 가진 답을 선택

BoN의 근본적 한계: 확률적 행동

• : 정답에 도달하는 번째 출력, 개

• : 오답에 도달하는 번째 출력, 개

• : Reward Model의 점수

1. 정답/오답 출력 개수 비율 — 기저 모델이 정답을 많이 생성할수록 유리

2. Reward 분포의 분리도 — 정답 출력의 Reward 분포 와 오답 출력의 Reward 분포 가 잘 분리될수록 유리

핵심 방법

전체 아키텍처

입력: 질문 x, 생성 예산 N

1. N개의 출력 생성: Y₁, ..., Y_N ~ p_ref
2. 각 출력에 대해 Reward 계산: r(Y₁), ..., r(Y_N)
3. 부트스트래핑으로 BoN 출력 분포 추정:
   - 크기 m의 서브셋을 복원 추출로 B번 생성
   - 각 서브셋에서 최고 Reward 출력의 답을 선택
4. B개의 선택된 답 중 최빈값을 최종 답으로 출력

Oracle MoB: 이상적 경우

부트스트래핑을 통한 분포 추정

Bootstrapping (statistics)

Bootstrapping is a procedure for estimating the distribution of an estimator by resampling (often with replacement) one's data or a model which is estimated from the data.[1] Bootstrapping assigns measures of accuracy (bias, variance, confidence intervals, prediction error, etc.) to sample estimates.[2][3] This technique allows estimation of the sampling distribution of almost any statistic using random sampling methods.[1]

https://en.wikipedia.org/wiki/Bootstrapping_(statistics)

서브샘플 크기 의 적응적 선택

• 이 클수록: BoN의 성공 확률이 높아져 의 mode가 정답일 가능성 증가. 하지만 이 에 가까워지면 부트스트래핑 추정의 정확도 저하 (극단값 추정 실패 문제)

• 이 작을수록: 부트스트래핑 추정은 정확하지만, Best-of- 자체의 성공 확률이 낮아짐

1. 후보 값 생성: (단, )

2. 인접 후보 간 분포 차이 최소화:

이론적 보장

결론