Best-of-$\infty$ -- Asymptotic Performance of Test-Time LLM Ensembling

이 논문은 무한한 테스트 시간 예산을 가정하는 'Best-of-$\infty$' 접근법의 한계를 극복하기 위해 답변 일치도에 기반한 적응형 생성 방식을 제안하고, 최적의 가중치를 혼합 정수 선형 계획법으로 계산하여 다중 LLM 앙상블의 성능을 극대화하는 방법을 연구합니다.

핵심

🎒 1. 문제: "정답을 찾으려면 몇 번이나 물어봐야 할까?"

마치 어려운 수학 문제를 풀기 위해 친구들에게 물어보는 상황을 상상해 보세요.

• 기존 방식 (Best-of-N): "친구 100 명에게 물어보고, 가장 많이 나온 답을 고르자."
  • 장점: 확실히 정답에 가까워집니다.
  • 단점: 친구 100 명을 모두 불러모으는 데 시간과 돈 (컴퓨팅 비용) 이 너무 많이 듭니다. 100 명을 다 불러오기 전에 지쳐버릴 수도 있죠.
• 이 논문의 제안 (Best-of-∞): "친구들이 답을 내놓을 때마다, '아, 이제 정답이 확실해졌네!'라고 판단되면 바로 멈추자."

🛑 2. 핵심 기술 1: "적응형 샘플링" (Adaptive Sampling)

비유: "스마트한 퀴즈 진행자"

이 논문은 친구들에게 무조건 100 번을 물어보는 게 아니라, **상황에 따라 멈출 타이밍을 재는 '스마트한 진행자'**를 도입했습니다.

1. 친구 1 명이 "정답은 42!"라고 말하면 기록합니다.
2. 친구 2 명이 "정답은 42!"라고 하면, "오, 의견이 모이고 있네!"라고 생각합니다.
3. 친구 3 명이 "정답은 42!"라고 하면, "이제 42 가 정답일 확률이 99% 이상이야. 더 물어볼 필요 없어!"라고 판단하고 즉시 멈춥니다.
4. 하지만 친구들이 "42", "105", "702"로 의견이 분열되면, "아직 확실하지 않네. 더 물어봐야겠다"라고 생각하며 계속 질문합니다.

결과: 쉬운 문제는 3 번만 물어봐도 정답을 찾고, 어려운 문제는 더 많이 물어봅니다. 불필요한 시간과 비용을 아껴주면서 정답률은 그대로 유지하는 것입니다.

🤝 3. 핵심 기술 2: "최고의 팀 구성" (LLM Ensemble)

비유: "다재다능한 스포츠 팀"

이제 친구 한 명만 있는 게 아니라, 서로 다른 특기를 가진 친구들 (다른 AI 모델들) 이 팀을 이루는 경우를 생각해 보세요.

• 친구 A: 수학은 천재지만, 과학은 약합니다.
• 친구 B: 과학은 천재지만, 수학은 조금 느립니다.
• 친구 C: 두 가지 모두 평균적인 실력입니다.

기존에는 "가장 똑똑한 친구 A 만 믿고 100 번 물어보는 것"이 최선이라고 생각했습니다. 하지만 이 논문은 **"A, B, C 를 적절히 섞어서 팀을 꾸리면, A 혼자일 때보다 더 좋은 결과를 낼 수 있다"**고 증명했습니다.

• 수학 문제: A 의 목소리를 더 크게 들으면 됩니다.
• 과학 문제: B 의 목소리를 더 크게 들으면 됩니다.

🧮 4. 어떻게 팀을 구성할까? (MILP 최적화)

비유: "요리사의 레시피 조합"

"어떤 친구의 말을 얼마나 믿어야 할까?"라는 비율 (가중치) 을 정하는 것은 매우 어렵습니다. 너무 복잡해서 수학적으로 계산하기 힘든 문제죠.

하지만 이 논문은 **"이 복잡한 문제를 마치 퍼즐처럼 맞추는 수학적 방법 (혼합 정수 선형 계획법, MILP)"**을 개발했습니다.

• 마치 최고의 요리를 만들기 위해 각 재료 (친구들) 를 얼마나 넣어야 가장 맛있는지 (정답률이 높은지) 계산하는 레시피를 찾는 것과 같습니다.
• 이 방법을 쓰면, 컴퓨터가 자동으로 "A 는 30%, B 는 50%, C 는 20% 씩 섞어라"라고 최고의 조합을 찾아줍니다.

🚀 5. 결론: 왜 이것이 중요한가요?

이 논문의 성과는 다음과 같습니다.

1. 효율성: 무작정 많은 시도를 하는 게 아니라, 정답이 확실해질 때까지만 노력합니다. (비용 절감)
2. 성능: 여러 AI 모델을 섞어 쓰면, 단일 모델이 아무리 똑똑해도 넘을 수 없는 벽을 넘을 수 있습니다. (성능 향상)
3. 실용성: 이 모든 복잡한 계산을 컴퓨터가 빠르게 해결할 수 있게 만들었습니다.

한 줄 요약:

"이 논문은 AI 가 문제를 풀 때, 불필요한 시도는 줄이고 (적응형 샘플링), 서로 다른 AI 들의 장점을 섞어 최고의 팀을 구성하는 (최적화) 방법을 찾아, 적은 비용으로 더 높은 정답률을 달성하는 비법을 공개했습니다."

이 방법은 앞으로 AI 가 더 똑똑해지고, 더 저렴하게 사용될 수 있는 중요한 발걸음이 될 것입니다.

기술 요약

1. 문제 정의 (Problem)

대형 언어 모델 (LLM) 의 추론 능력을 향상시키기 위해, 여러 개의 답변을 생성하고 그중 가장 좋은 것을 선택하는 Best-of-N (BoN) 전략이 널리 사용됩니다. 특히 **다수결 투표 (Majority Voting)**는 추가적인 모델 학습이나 보상 모델 (Reward Model) 없이도 강력한 성능을 보여줍니다.

그러나 기존 BoN 방식에는 두 가지 주요 한계가 존재합니다:

1. 무한한 계산 비용: 이론적으로 정확도가 최대가 되는 지점은 $N \to \infty$ (Best-of-$\infty$) 인 경우이지만, 이는 현실적으로 무한한 추론 시간과 계산 자원을 요구하여 비현실적입니다.
2. 고정된 샘플 수의 비효율성: 모든 문제에 대해 고정된 수의 샘플 (예: N=100) 을 생성하는 방식은 쉬운 문제에서는 자원을 낭비하고, 어려운 문제에서는 여전히 불충분할 수 있습니다.
3. 단일 모델의 한계: 단일 LLM 만으로는 특정 도메인에서 한계가 명확하며, 여러 모델의 장점을 결합 (Ensemble) 할 때의 최적 가중치 설정에 대한 체계적인 방법이 부족했습니다.

2. 방법론 (Methodology)

이 논문은 Best-of-$\infty$의 성능을 유한한 샘플로 효율적으로 근사하고, 여러 LLM 을 최적화하여 결합하는 두 가지 핵심 기법을 제안합니다.

A. 적응형 샘플링 (Adaptive Sampling)

• 개념: 정해진 N 개를 무조건 생성하는 대신, **베이지안 모델링 (Bayesian Modeling)**을 기반으로 답변의 분포를 추정하며, 다수결 (Majority) 이 특정 신뢰 수준에 도달했을 때만 샘플링을 중단하는 방식입니다.
• 수학적 배경:
  • LLM 이 생성하는 답변의 지원 (Support) 이 불확실하므로, **디리클레 프로세스 (Dirichlet Process, DP)**를 사전 분포 (Prior) 로 사용하여 답변 공간의 분포를 모델링합니다.
  • **베이지인 팩터 (Bayes Factor, BF)**를 계산하여 "현재 가장 빈번한 답변이 진정한 다수결 (True Majority) 이다"라는 가설 ($H_1$) 을 지지하는 증거가 충분한지 판단합니다.
  • 알고리즘 1: 최대 샘플 수 ($N_{max}$) 와 베이지인 팩터 임계값 ($B$) 을 설정하고, BF 가 임계값을 넘거나 $N_{max}$에 도달할 때까지 반복적으로 샘플을 생성합니다.
• 이점: 쉬운 문제는 적은 샘플로, 어려운 문제는 더 많은 샘플로 처리하여 주어진 계산 예산 내에서 정확도를 극대화합니다.

B. 최적 LLM 앙상블 (Optimal LLM Ensemble)

• 개념: 단일 LLM 대신 여러 LLM 을 가중치 $w = (w_1, \dots, w_K)$를 부여하여 혼합 (Mixture) 한 후, 다수결을 수행하는 방식입니다.
• 최적화 문제: Best-of-1 (단일 모델 선택) 은 가장 성능 좋은 모델 하나만 선택하는 것이 최적이지만, Best-of-$\infty$에서는 여러 모델의 상호 보완성 (Complementarity) 을 활용하기 위해 **비볼록 (Non-concave)**한 목적 함수를 최적화해야 합니다.
• MILP (Mixed-Integer Linear Programming) 공식화:
  • $N \to \infty$ 극한에서 각 문제의 정답 결정은 결정론적 (Deterministic) 이며, 이는 가중치 공간에서 다면체 (Polytope) 구조를 형성합니다.
  • 정답을 맞춘 문제의 수를 최대화하는 가중치 벡터 $w$를 찾는 문제를 혼합 정수 선형 계획법 (MILP) 문제로 변환하여 효율적으로 해결합니다.
  • 이는 기존에 지수적으로 많은 조합을 탐색해야 했던 문제를 다항 시간 내에 해결 가능한 형태로 바꿉니다.
  • Max-Margin 해: 최적 해가 여러 개일 수 있으므로, 해의 내부에 가장 깊게 위치하는 (Margin 이 최대인) 해를 선택하여 유한한 $N$에서의 성능도 안정적으로 유지하도록 합니다.

3. 주요 기여 (Key Contributions)

1. Best-of-$\infty$의 실용적 근사: 무한한 샘플을 가정하는 이상적인 성능을, 베이지안 적응형 샘플링을 통해 유한한 계산 비용으로 달성할 수 있는 체계를 제시했습니다.
2. 최적 앙상블 가중치 계산의 이론적 돌파구: LLM 다수결 앙상블의 최적 가중치 탐색을 MILP로 변환하여, 이론적으로 증명 가능한 최적 해를 효율적으로 구할 수 있음을 보였습니다. 이는 기존에 불가능하거나 근사적이었던 접근을 넘어선 것입니다.
3. 대규모 실험 데이터셋 구축: 11 개의 오픈 가중치 LLM 과 4 가지 고난도 추론 벤치마크 (AIME2024/2025, GPQA-DIAMOND, MATH500) 에 대해, 모델당 최소 80 회 이상의 생성 (총 수만 건의 답변) 을 수행하여 기존 연구보다 훨씬 큰 규모의 테스트 타임 컴퓨팅 데이터를 구축하고 공개했습니다.
4. 상위 모델 성능 달성: 단일 최강 모델보다 약한 모델들이라도 상호 보완적으로 작용할 때, 최적화된 앙상블이 단일 최강 모델의 Best-of-$\infty$ 성능을 능가함을 실험적으로 증명했습니다.

4. 실험 결과 (Results)

• 적응형 샘플링의 효율성:
  • 고정된 $N$ (예: $N=100$) 을 사용하는 방식과 비교하여, 제안된 적응형 방식은 동일한 정확도를 달성하는 데 필요한 샘플 수와 토큰 수를 2 배에서 5 배까지 절감했습니다.
  • 특히 쉬운 문제에서는 샘플을 일찍 중단하여 자원을 절약했습니다.
• 앙상블의 성능 향상:
  • AIME2025 데이터셋에서 GPT-OSS-20B (Best-of-$\infty$ 정확도 90.0%) 와 Nemotron-Nano-9B-v2 (73.0%) 를 앙상블했을 때, 최적 가중치로 결합한 결과 **93.3%**의 정확도를 기록하여 단일 최강 모델보다 3.3%p 향상되었습니다.
  • MILP 로 최적화된 가중치는 균일 가중치 (Uniform) 나 단일 모델 선택보다 모든 벤치마크에서 일관되게 우수한 성능을 보였습니다.
• 다른 선택 방법과의 비교:
  • 보상 모델 (Reward Model), LLM-as-a-Judge, 자기 확신 (Self-certainty) 등 다른 답변 선택 기법들과 비교했을 때, 다수결 투표가 가장 안정적이고 높은 성능을 보였습니다 (AIME2025 기준 Bo5 설정에서 다수결 85.42% vs LLM-as-Judge 82.92%).

5. 의의 및 결론 (Significance)

이 논문은 LLM 의 추론 능력을 향상시키기 위해 **테스트 타임 컴퓨팅 (Test-Time Compute)**을 확장하는 새로운 패러다임을 제시합니다.

• 이론적 엄밀성: Best-of-$\infty$라는 이상적인 개념을 수학적 모델 (Dirichlet Process, MILP) 을 통해 정량화하고 최적화할 수 있는 틀을 마련했습니다.
• 실용적 가치: 고정된 계산 예산 하에서 적응형 샘플링을 통해 효율성을 극대화하고, 여러 모델을 지능적으로 결합하여 단일 모델의 한계를 극복하는 방법을 제시했습니다.
• 미래 연구 방향: 제안된 방법론과 공개된 대규모 생성 데이터셋은 추후 LLM 의 스케일링 법칙, 앙상블 학습, 그리고 테스트 타임 최적화 연구에 중요한 기반이 될 것입니다.

결론적으로, 이 연구는 "더 많은 계산"을 단순히 "더 많이" 사용하는 것이 아니라, 어디에, 얼마나, 어떻게 집중할지 결정하는 지능적인 추론 전략의 중요성을 강조하며, LLM 의 성능 한계를 확장하는 데 있어 다중 모델 앙상블과 적응형 샘플링이 핵심 요소임을 입증했습니다.