Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment

이 논문은 실제 환경에 더 부합하는 승률 (win-rate) 지표를 분석 대상으로 삼아, 적절히 조정된 Best-of-N 방법이 통계적 최적성을 가지며 reward hacking 을 방지하는 개선된 변형을 제안함으로써 기존 연구의 한계를 극복하고 이 방법론의 실용적 성공을 이론적으로 설명합니다.

핵심

🍎 핵심 비유: "과일 장터와 맛없는 사과"

생각해 보세요. 당신은 사과를 사러 장터에 갔습니다. 하지만 당신은 사과가 정말 맛있는지 직접 맛볼 수 없습니다. 대신, **가짜 맛 평가원 (학습된 보상 모델)**이 사과 하나하나를 보고 "이건 100 점, 저건 90 점"이라고 점수를 매겨줍니다.

당신의 목표는 이 가짜 평가원의 점수를 믿고, **가장 맛있는 사과 (진짜 보상)**를 고르는 것입니다.

1. 기존 방법: "Best-of-N (N 개 중 최고)"

기존의 일반적인 방법은 다음과 같습니다.

1. 장터에서 사과 N 개를 무작위로 줍습니다.
2. 가짜 평가원이 이 N 개 사과를 모두 검사해서 점수를 매깁니다.
3. 점수가 가장 높은 사과 하나를 골라 구매합니다.

문제점 (보상 해킹):
만약 N 이 너무 많다면, 가짜 평가원의 실수를 이용해 속는 사과를 고를 확률이 생깁니다.

• 상황: 진짜 맛있는 사과 (진짜 보상) 는 90 점인데, 가짜 평가원은 95 점이라고 합니다. 반면, 진짜 맛없는 사과 (보상 해킹) 는 80 점인데, 가짜 평가원은 실수로 99 점이라고 매길 수도 있습니다.
• 결과: N 이 아주 많으면, 가짜 평가원이 실수해서 99 점이라고 한 '맛없는 사과'를 골라낼 확률이 높아집니다. 즉, 점수는 높지만 실제로는 맛없는 사과를 고르게 되는 것입니다. 이를 논문에서는 **'보상 해킹 (Reward Hacking)'**이라고 부릅니다.

2. 이전 연구의 결론 (Huang et al.)

이전 연구자들은 "N 을 늘리면 보상을 해킹할 수 있으므로, Best-of-N 방법은 통계적으로 최적이 아니다. 더 복잡하고 어려운 수학적 방법을 써야 한다"고 주장했습니다. 마치 "가장 맛있는 사과를 고르려면 단순히 많이 고르면 안 되고, 복잡한 계산기를 써야 한다"는 뜻입니다.

3. 이 논문의 발견: "우리가 잘못 생각했다!"

이 논문은 **"아니요, Best-of-N 은 사실 매우 훌륭합니다!"**라고 반박합니다. 하지만 조건이 하나 있습니다.

• 기존의 기준: "점수 (Expected Reward) 가 얼마나 높은가?"
• 이 논문의 기준: "다른 사과와 비교했을 때 **이 사과가 이길 확률 (Win-rate)**이 높은가?"

비유로 설명하면:

• 기존 기준: "이 사과가 100 점 만점에 몇 점일까?" (정확한 점수 측정)
• 이 논문의 기준: "이 사과를 다른 사과와 싸우게 하면 몇 번 이길까?" (승률)

실제 AI 평가에서는 "이 답변이 저 답변보다 낫다"는 **승률 (Win-rate)**이 더 중요합니다. 논문은 **"승률을 기준으로 볼 때, Best-of-N 은 실제로 최적의 방법"**이라고 증명했습니다.

왜 그랬을까요?
이전 연구는 '점수'에 너무 집착했습니다. 하지만 '승률' 관점에서는, 가짜 평가원이 약간의 실수를 하더라도 N 개를 많이 뽑으면 결국 진짜 맛있는 사과를 찾을 확률이 가장 높다는 것이 수학적으로 증명되었습니다. 즉, 복잡한 수식을 쓸 필요 없이, 단순히 많이 뽑고 좋은 걸 고르는 게 가장 효율적이라는 것입니다.

---

🛡️ 새로운 해결책: "EM-정규화 Best-of-N"

하지만 여전히 '보상 해킹' (N 이 너무 많으면 점수만 높은 맛없는 사과를 고르는 문제) 은 존재합니다. 이 논문은 이를 해결하면서도 Best-of-N 의 장점을 살리는 새로운 방법을 제안합니다.

새로운 방법의 비유: "신뢰할 수 있는 장터 가이드"

가짜 평가원의 점수만 믿고 N 개를 다 뽑는 대신, **"원래 장터 (참고 모델) 에서 나올 법한 사과"**만 골라내되, 그중에서 점수가 높은 것을 고르는 것입니다.

• 기존 Best-of-N: "점수가 가장 높은 사과를 고르세요." (N 이 많으면 장터에 없는 이상한 사과도 고를 수 있음)
• 새로운 방법 (EM-정규화): "장터에서 나올 법한 사과들 중에서, 점수가 상위 10% 에 드는 사과만 고르세요."

이 방법은 두 마리 토끼를 다 잡습니다.

1. 보상 해킹 방지: 장터에서 나올 법한 범위 (Reference Model) 를 벗어나지 않으므로, 점수만 높고 실체가 없는 '괴상한 사과'를 고를 확률이 줄어듭니다.
2. 최적 성능 유지: 여전히 Best-of-N 과 같은 통계적 효율성을 가지며, N 을 늘려도 성능이 떨어지지 않습니다.

---

💡 요약: 이 논문이 우리에게 주는 메시지

1. Best-of-N 은 나쁘지 않습니다: 복잡한 수학적 분석을 거친 이전 연구와 달리, 실제 AI 평가에서 중요한 '승률 (Win-rate)' 기준으로는 Best-of-N 이 이미 최고의 방법 중 하나입니다.
2. 단순함이 승리합니다: 복잡한 정규화나 추가 학습 없이, 단순히 "많이 뽑고 좋은 걸 고르는" 방식이 실제로 매우 효과적입니다.
3. 해킹 방지법 발견: 하지만 N 을 무한정 늘리면 '보상 해킹'이 일어날 수 있습니다. 이를 막기 위해 "원래 모델의 범위를 벗어나지 않으면서 상위 점수를 고르는" 아주 간단하고 실용적인 변형 방법을 제안했습니다.

결론적으로, 이 논문은 AI 개발자들이 "복잡한 알고리즘을 만들려고 애쓰지 말고, 잘 다듬어진 단순한 Best-of-N 방법을 쓰되, 약간의 규칙 (정규화) 만 추가하면 된다"는 것을 수학적으로 증명해 주었습니다. 마치 **"복잡한 요리 레시피보다, 신선한 재료를 많이 사서 가장 좋은 것을 고르는 게 더 맛있는 요리를 만드는 길"**이라는 뜻입니다.

기술 요약

논문 요약: Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment

이 논문은 언어 모델 (LM) 의 추론 시간 (Inference-time) 정렬 (Alignment) 방법 중 널리 사용되는 Best-of-N (BoN) 샘플링 알고리즘의 이론적 최적성을 재조명합니다. 기존 연구들은 BoN 이 통계적으로 비최적 (suboptimal) 이고 보상 해킹 (reward hacking) 에 취약하다고 주장했으나, 본 논문은 실제 적용 환경에 더 부합하는 가정 하에 BoN 이 승률 (Win-rate) 기준으로는 통계적 및 계산적으로 최적임을 증명하고, 보상 해킹을 방지하는 새로운 변형 알고리즘을 제안합니다.

---

1. 문제 정의 및 배경

• 배경: 최근 언어 모델의 성능 향상은 추론 시간 계산 (Inference-time compute) 을 확장하는 '병렬 확장 (Parallel Scaling)' 전략에 크게 의존합니다. 이는 N 개의 후보 응답을 생성한 후 가장 좋은 하나를 선택하는 방식입니다.
• Best-of-N (BoN): 학습된 보상 모델 (Reward Model, $b_r$) 이 예측한 보상이 가장 높은 응답을 선택하는 방식입니다.
• 기존 연구의 한계 (Huang et al., 2025):
  • 목표 함수: 기존 연구는 '기대 실제 보상 (Expected True Reward)'을 최적화하는 관점에서 BoN 을 분석했습니다.
  • 결론: 이 관점에서는 BoN 이 통계적으로 비최적이며, 보상 해킹 (보상 모델의 약점을 이용해 실제 성능은 낮지만 예측 보상은 높은 응답을 선택하는 현상) 에 취약하다고 주장했습니다. 이를 해결하기 위해 복잡한 $\chi^2$ 정규화 변형 알고리즘이 제안되었습니다.
  • 실제와의 괴리: 실제 LLM 평가 (예: AlpacaEval) 에서는 기대 보상보다 승률 (Win-rate, 비교 대상 모델 대비 이긴 비율) 이 더 자연스러운 지표입니다. 또한, 보상 모델은 주로 쌍별 비교 (Pairwise comparison) 로 학습되므로, 기대 보상을 최적화하는 가정이 실제와 맞지 않을 수 있습니다.

2. 방법론 및 가설

본 논문은 기존 연구의 가정을 실제 환경에 맞게 수정하여 분석을 재수행했습니다.

2.1 새로운 평가 지표: 승률 (Win-rate)

• 정의: 학습된 정책 $\pi$가 기준 정책 $\pi_{ref}$ (또는 비교 정책 $q$) 보다 실제 보상 $r^*$이 더 높은 확률로 이기는 비율.
  $$R_{r^*}(\pi) = P(r^*(y) > r^*(y')) + \frac{1}{2}P(r^*(y) = r^*(y'))$$
• 의의: 보상 모델이 쌍별 비교 데이터로 학습된다는 점을 반영하며, 실제 LLM 평가 파이프라인과 일치합니다.

2.2 새로운 오차 및 거리 측정 기준

• 보상 모델 오차: 기존 연구의 제곱 오차 (MSE) 대신 쌍별 승률 오차 (Pairwise Win-rate Error, $\epsilon_{pw}$) 를 사용합니다.
  • 이는 보상 모델이 두 응답 간의 우열을 실제 보상과 얼마나 일치하게 예측하는지를 측정하며, 스케일 불변성 (Scale-invariant) 을 가집니다.
• 참조 모델과 비교 모델의 거리: 기존 $\chi^2$ 발산 대신 EM-발산 (EM-divergence) 을 사용합니다.
  • 이는 표본 추출 (Sampling) 관점에서 참조 분포 $\pi_{ref}$에서 비교 분포 $\pi^*$를 근사적으로 생성하는 데 필요한 복잡도를 더 잘 설명합니다.

2.3 알고리즘 제안: EM-정규화 Best-of-N

• 보상 해킹을 방지하면서도 최적 성능을 유지하기 위해, EM-정규화 (EM-regularized) 변형 알고리즘을 제안합니다.
• 핵심 아이디어: 참조 모델 $\pi_{ref}$ 하에서 발생 확률이 낮은 (즉, EM-발산이 큰) 응답을 패널티로 부과합니다.
• 구현: 이 변형은 단순히 보상 모델 $b_r$의 상위 $1/M$ 분위수 (Top-quantile) 에 해당하는 응답들 중에서 균등하게 선택하는 방식으로 구현됩니다.

3. 주요 결과 및 정리

3.1 BoN 의 최적성 (Theorems 3 & 4)

• 결과: 적절한 쌍별 승률 오차 ($\epsilon_{pw}$) 와 EM-발산 조건 하에서, 적절히 튜닝된 N 값을 가진 BoN 은 승률 (Win-rate) 기준에서 통계적 및 계산적으로 최적 (Optimal) 입니다.
• 의미: 기존 연구가 주장한 BoN 의 비최적성은 '기대 보상'이라는 부적절한 목표 함수와 가정에서 비롯된 인공적 결과 (Artifact) 였음을 보여줍니다. 승률이라는 더 자연스러운 목표 하에서는 BoN 이 단순함에도 불구하고 최적의 성능을 냅니다.

3.2 보상 해킹 방지 및 EM-정규화 BoN (Theorem 5)

• 문제: BoN 은 N 이 커질수록 보상 해킹으로 인해 성능이 비단조적으로 감소할 수 있습니다.
• 해결: 제안된 EM-정규화 BoN 알고리즘은 N 이 증가해도 성능이 감소하지 않는 (Monotone) 성질을 가지며, 동시에 통계적으로 최적의 성능을 보장합니다.
• 이점: 기존에 제안된 $\chi^2$ 정규화 알고리즘보다 구현이 훨씬 간단하며 (상위 분위수 선택기), 추가적인 온라인 추정이나 복잡한 학습이 필요 없습니다.

3.3 기존 알고리즘의 한계 (Proposition 2)

• 결과: Huang et al. [14] 가 제안한 $\chi^2$ 정규화 BoN 알고리즘은 승률 (Win-rate) 기준으로는 본 논문이 제안한 EM-정규화 BoN 보다 임의의 비율로 더 나쁜 성능을 보일 수 있음을 증명했습니다. 이는 기존 접근법이 승률 최적화에는 부적합함을 시사합니다.

4. 의의 및 기여

1. 이론과 실무의 간극 해소: 기존 이론적 분석이 실제 LLM 평가 방식 (승률, 쌍별 비교) 과 괴리되어 BoN 을 불필요하게 비하했다는 점을 지적하고, 올바른 목표 함수 하에서 BoN 의 성공을 이론적으로 설명했습니다.
2. 새로운 최적성 증명: 단순한 Best-of-N 알고리즘이 복잡한 정규화 기법 없이도 승률 최적화 문제에서 최적임을 증명했습니다.
3. 실용적인 개선 알고리즘: 보상 해킹을 이론적으로 제거하면서도 구현이 간단한 EM-정규화 BoN 을 제안하여, 실제 시스템에 바로 적용 가능한 솔루션을 제공했습니다.
4. 평가 지표의 중요성 강조: 추론 시간 정렬 알고리즘을 분석할 때 '기대 보상' 대신 '승률'과 같은 실제적인 지표를 사용해야 함을 강조했습니다.

5. 결론

본 논문은 Best-of-N 샘플링이 언어 모델의 추론 시간 정렬에서 단순함에도 불구하고 매우 효과적일 수 있음을 이론적으로 입증했습니다. 특히, 실제 환경에 부합하는 '승률' 지표를 사용할 때 BoN 이 최적임을 보였으며, 보상 해킹 문제를 해결하기 위해 구현이 간편한 EM-정규화 변형을 제안했습니다. 이는 향후 언어 모델의 효율적인 정렬 및 확장 전략 수립에 중요한 이론적 기반을 제공합니다.