NL-229, An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models, ICLR 2025

◼ Comment

  • 맨마지막 conclusion에 잘 정리가 되어있다
  • 기억할점은, 친칠라 optimization과 비슷하지만 다른 접근으로 model size와 inference  전략 사이의 최적의 state을 찾으려고 한다는 것이다 (비용은 고정일때)
    • 이때 small model 여러번 돌리는게 llm 적게 돌리는것보다 나은 결과를 보여줄 때가 많다는 것이다
    • 그런대 이런 논문들은 항상 추론문제인 수학, 코딩 같은거에만 집중하는게 아쉽다
    • 즉 답을 정확히 매겨야 하는 상황에서는 어느정도 다양한 논문에서 입증한거 같지만, 일반적인 생성형 open QA같은 문제에서는 small model 여러번 돌려서 시도하려는 경우는 못봤다
    • small model로 다양하게 샘플링해서 llm으로 한번 요약하는 식은 어떨까?
  • 또한 REBASE라는 새로운 샘플링 기법을 제시하는데, MCTS와 reward 모델을 활용한 best-of-n의 중간느낌이다
    • MCTS는 특정 step에서 다양하게 뒤의 토큰들을 끝까지 완성시켜서 가장 좋은 next token을 생성하는 식이다. 즉 끝까지 토큰들을 생성해보고 value function을 통해 next step을 결정하는식? 같은데, 이는 계산량이 많이 드는게 문제이다.
    • best-of-n은 중간 결과에 상관없이 일단 다양하게 끝까지 샘플링해보고 reward 모델같은걸로 최적의 하나를 선택하는 방식이다. 이 방법은 다양하게 샘플링 해볼 수 있지만, 중간에 잘못된 결과가 나오더라도 끝까지 생성한다는 점이 문제이다
    • REBASE는 과정 보상 모델(process reward model, PRM)을 사용하여 각 깊이에서 어떤 노드를 확장할지 결정하는거라고 한다. 즉 과거부터 지금까지의 과정인 process의 보상을 측정하는 모델을 활용한다고 한다. PRM 이미 오픈된 데이터로 학습하는거 같음.
  • MCTS, REBASE 샘플링 방법을 통해 다양하게 응답을 샘플링 할 수 있고..
    • 여기에 majority voting, weighted majority voting 등을 결합할 수 있음
    • best-of-n과 greedy search또한 하나의 답을 뽑기 위한 인퍼런스 전략임
  • 이렇게 다양하게 샘플링하여 실험을 한 결과, 위에서 언급한 결론이 나오는 것

Abstract

  • 대규모 언어 모델(LLM) 훈련의 스케일링 법칙은 광범위하게 연구되었으나, LLM 추론의 최적 구성은 상대적으로 덜 연구되었습니다. 
  • 우리는 추론 스케일링 법칙과 컴퓨팅 최적 추론에 대해 연구하면서, 모델 크기와 다양한 추론 전략에 따른 추가 토큰 생성을 통해 발생하는 비용-성능 간의 상충관계를 탐구하였습니다. 
  • 컴퓨팅 최적 추론 방법을 이해하고 설계하는 첫 단계로서, 탐욕적 탐색, 다수결 투표, best-of-n, 가중치 투표, 두 가지 트리 탐색 알고리즘 등 여러 추론 전략에 대해 비용-성능 상충관계를 분석하였고, 다양한 모델 크기와 컴퓨팅 예산을 고려했습니다. 
  • 연구 결과, 동일한 컴퓨팅 예산 하에서는 작은 모델(예: Llemma-7B)이 큰 모델보다 더 우수한 성능을 발휘할 수 있으며, 작은 모델에 고급 추론 알고리즘을 결합하면 비용-성능 측면에서 파레토 최적의 결과를 얻을 수 있다는 것을 확인했습니다. 
    • "파레토 최적"이란 여러 목표나 기준이 있을 때, 하나의 목표를 더 이상 개선하면 다른 목표가 나빠지지 않고는 개선할 수 없는 상태를 말합니다. 이는 다목적 최적화에서 흔히 사용하는 개념으로, 한 목표를 더 좋게 만들려면 다른 목표에 어느 정도 손해를 감수해야 하는 상황을 의미합니다.
    • 예를 들어, 대규모 언어 모델에서 "비용"과 "성능"이라는 두 목표가 있다면, 비용을 줄이면서 성능을 높이는 것은 일반적으로 어렵습니다. "파레토 최적" 상태는, 더 작은 비용으로 성능을 높이거나 성능을 유지하면서 비용을 줄이는 것이 더 이상 불가능한 지점입니다. 따라서 파레토 최적의 결과란 주어진 조건에서 비용과 성능 간의 최상의 균형을 이루는 결과를 의미합니다.
  • 예를 들어, Llemma-7B 모델은 우리의 새로운 트리 탐색 알고리즘과 함께 사용될 때, MATH 벤치마크에서 모든 FLOPs 예산에 대해 표준 다수결 투표를 사용한 Llemma-34B보다 지속적으로 더 우수한 성능을 보였습니다. 
  • 이 연구가 LLM의 추론 스케일링 법칙에 대한 이해를 넓히는 데 기여하기를 바랍니다.

1 INTRODUCTION

  • 신경망의 scaling laws(Hestness et al., 2017; Rosenfeld et al., 2019)은 언어 모델링(Kaplan et al., 2020; Hoffmann et al., 2022; OpenAI, 2023), 이미지 모델링(Henighan et al., 2020; Yu et al., 2022; Peebles & Xie, 2023), 비디오 모델링(Brooks et al., 2024), 보상 모델링(Gao et al., 2023), 그리고 보드 게임(Jones, 2021) 등 다양한 분야에서 확립되었습니다. 
    • 이러한 연구들은 모델 성능이 모델 크기와 학습 계산량에 의해 어떻게 영향을 받는지 보여주었습니다. 
    • 그러나 훈련이 완료된 후 추론 중에 계산량을 변화시키는 것이 모델 성능에 어떤 영향을 미치는지에 대한 지식은 제한적입니다.
  • LLM의 작업 성능을 개선하기 위해 추론 기법에는 보통 성능을 최대화하기 위한 추가적인 계산이 포함됩니다(Nye et al., 2021; Wei et al., 2022; Wang et al., 2022b; Yao et al., 2023; Chen et al., 2024b). 
    • 이러한 기법의 계산 비용은 최적의 추론을 위해 고려되어야 합니다. 
    • 예를 들어, 몬테카를로 트리 탐색(MCTS) 방법(Jones, 2021)은 작업 성능을 개선할 수 있지만 단순히 여러 번 솔루션을 샘플링하는 것보다 훨씬 더 많은 계산을 요구할 수 있습니다. 
  • 일반적으로 다양한 추론 시점 방법(e.g., best-of-n, 다수결(Wang et al., 2022a; Li et al., 2023))이 성능과 비용 간에 어떻게 균형을 이루는지에 대한 포괄적인 이해가 필요합니다. 
    • 이를 위해 이 논문은 대표적인 LLM과 추론 알고리즘의 다양한 구성에 대해 신중하게 분석한 실험적 평가를 제시합니다.
    • 구체적으로, 우리는 언어 모델의 최적 크기와 효과적인 추론 전략(e.g., 탐욕적 검색, 다수결, best-of-n, 가중치 투표 및 트리 탐색 변형)을 선택하여 주어진 계산 예산으로 성능(정확도)을 극대화하는 방법을 탐구합니다. 
  • 우리는 언어 모델을 통해 더 많은 토큰을 생성하고, 추가 후보 솔루션을 샘플링하며, 이를 보상 모델을 통해 순위를 매김으로써 고정된 모델의 추론 계산(FLOPs)을 제어합니다. 
  • 수학적 추론 벤치마크(GSM8K 테스트 세트(Cobbe et al., 2021a)와 MATH500 테스트 세트(Hendrycks et al., 2021b; Lightman et al., 2023b))에서 다양한 크기의 미세 조정된 모델의 성능을 분석했습니다. 
  • 우리의 실험은 범용 LLM(e.g., Pythia (Biderman et al., 2023) 및 Mistral (Jiang et al., 2023))과 수학 특화 모델(e.g., Llemma (Azerbayev et al., 2023))을 다룹니다.
  • 모델: Pythia, Mistral, Llemma
    • 데이터: GSM8K, MATH500
    • 샘플링: greedy search, majority voting, best-of-n, weighted voting, and their tree-search variants
  • Pythia에서의 결과(Fig. 1)는 다양한 모델 크기에서 추론 계산이 증가함에 따라 성능이 어떻게 확장되는지를 보여줍니다. 
    • 일반적으로 계산 예산이 증가할수록 정확도도 증가하며, 이는 포화에 도달할 때까지 지속됩니다. 
    • 계산 예산이 증가함에 따라 작은 모델은 초기에는 더 나은 성능을 보이지만, 작은 모델의 정확도가 포화에 도달하면 큰 모델이 유리한 성능을 보입니다. 
  • Figure 1의 오른쪽 패널은 다른 계산량 수준에서 추론에 최적의 모델 크기가 어떻게 달라지는지 보여줍니다. 
    • 그러나 실제 배포 환경에서는 상대적으로 작은 모델의 정확도가 포화에 도달하는 지점보다 훨씬 낮은 수준의 계산만 사용할 수 있으며, 그 지점에서 큰 모델의 성능이 나타납니다(Figure 4에 나와 있는 것처럼 7B 모델이 34B 모델을 128개의 Llemma 7B 솔루션 샘플까지 능가함). 
    • 이는 상대적으로 작은 모델이 추론에 더 최적의 계산 성능을 가질 수 있음을 나타냅니다.
  • 우리는 샘플링 및 투표 기반 추론 전략의 점근적 행동을 분석하여, 이들의 수렴 상한과 수렴 속도를 보여줍니다. 
  • 데이터셋이 주어지면 언어 모델의 정확도는 궁극적으로 모델이 할당한 출력 확률에 따라 고정된 한계에 포화되며, 샘플링과 투표를 통해 기하급수적 수렴 속도를 보입니다. 
  • 이는, 오라클 검증기가 없는 경우 단순한 샘플링 전략으로는 무한한 샘플 수로도 완벽한 정확도를 달성할 수 없으며 수익이 감소한다는 것을 의미합니다. 
  • 따라서 보다 정교한 추론 알고리즘이 필요함을 강조합니다.
    • 또한, 일반적으로 사용되는 MCTS 방법은 weighted voting와 잘 작동하지 않으며, 많은 미완성 솔루션을 생성하여 효과적인 투표를 방해하는 경향이 있음을 발견했습니다. 
    • 이 문제를 해결하기 위해, weighted voting와 잘 짝을 이루며 정확도와 추론 계산 간의 파레토 최적 균형을 달성하는 새로운 트리 탐색 알고리즘인 REward BAlanced SEarch(REBASE)를 제안합니다. 
  • REBASE의 핵심 아이디어는 노드 품질 보상을 사용하여 노드 확장을 제어함으로써 명시적인 롤아웃이 필요 없으며 투표를 위한 충분한 후보 솔루션을 확보하도록 합니다.
  • 우리의 실험에서 REBASE는 모든 설정, 모델 및 작업에서 샘플링 및 MCTS 방법을 일관되게 능가했습니다. 
  • 특히, REBASE를 사용한 더 작은 언어 모델이 일반적으로 파레토 최적의 성능을 달성함을 확인했습니다. 
  • 단순 샘플링, MCTS은 한계가 있음..
    • 따라서 정교한 REBASE 샘플링이란 것을 제안했음
    • 이는 weighted voting과 잘 어울러진다고함
  • 예를 들어, Llemma-7B 모델이 MATH500 (그림 4) 또는 GSM8K (그림 5) 평가에서 Llemma-34B 모델과 유사한 정확도를 달성하면서 FLOPs는 절반만 사용한다는 점을 보여줍니다. 
  • 즉 같은 계산량으로 고정해두고 보면 REBASE(7B)가 젤 좋을때가 존재한다
    • 작은 모델로 더 많이 샘플링하는 것이 큰 모델로 적게 샘플링하는 것보다 좋음을 의미하는 것
  • 또한, REBASE와 함께 사용하는 Llemma-7B는 모든 계산 예산에서 표준 다수결 투표를 사용하는 Llemma-34B보다 뛰어난 성능을 보였습니다. 
  • 이러한 결과는 고급 추론 시간 알고리즘을 통해 작은 모델을 사용하는 것의 가치를 보여주며, 추론 시간 계산에서 더 나은 성능을 달성하기 위한 새로운 알고리즘의 이점을 강조합니다.
  • 우리의 기여는 다음과 같이 요약됩니다:
    • - 우리는 고정된 추론 전략 하에서 다양한 모델 크기의 성능을 평가하여 새로운 추론 스케일링 법칙을 탐구했습니다. 동일한 계산 예산 하에서 작은 모델이 샘플 수를 늘림으로써 큰 모델보다 우수한 성능을 낼 수 있음을 보여주었습니다.
    • - 투표 방법의 스케일링 동작에 대한 새로운 이론적 분석을 제공하며, 수렴 상한과 수렴 속도를 제시했습니다. 이러한 분석을 통해 샘플링으로 인한 성능 한계와 수익 감소를 보여주며, 보다 정교한 추론 알고리즘의 필요성을 강조했습니다.
    • - 새로운 계산 최적 추론 문제를 수립하고, 널리 사용되는 샘플링 및 MCTS 방법과 비교하여 계산 최적 성능을 보이는 새로운 트리 탐색 알고리즘인 REBASE를 제안했습니다. 우리의 결과는 고급 추론 알고리즘을 통해 작은 모델을 사용함으로써 비용 대비 성능에서 더 나은 성과를 달성할 수 있음을 보여줍니다.

2 RELATED WORKS

  • Mathematical Reasoning with LLMs.
    • 대규모 언어 모델(LLM)은 최근 몇 년간 큰 발전을 이루었으며, 강력한 추론 능력을 보여주었습니다 (Brown et al., 2020; Hoffmann et al., 2022; Chowdhery et al., 2022; Lewkowycz et al., 2022). 
    • 수학 문제 해결은 LLM의 추론 능력을 측정하는 중요한 과제입니다 (Cobbe et al., 2021a; Hendrycks et al., 2021b).
    • Ling et al. (2017)은 최종 답변에 도달하는 단계별 해결 과정을 제시하는 방법을 처음 개발했습니다. 
    • 이후, Cobbe et al. (2021b)은 해결 방안을 평가하고 순위를 매기는 검증기를 훈련하여 이를 확장했습니다. 
    • 이후 연구들(e.g., Lewkowycz et al. (2022))은 다수결(Majority Voting)과 가중 다수결(Weighted Majority Voting)(Li et al., 2023)과 같은 추론 시간 기법이 성능에 미치는 이점을 보여주었습니다. 
    • 우리는 수학 문제 해결을 연구 대상 과제로 선택하여 연산 자원을 최적화한 전략을 탐구하는데, 이는 문제 해결 능력을 정확하게 평가할 수 있기 때문입니다.
    • 수학문제로 추론능력을 평가하는게 일반적이긴 한가봄
  • Inference Strategies of LLM Problem Solving.
    • 훈련된 모델을 통해 일련의 결과를 생성하기 위해 다양한 추론 전략이 개발되었습니다. 
    • 탐욕적 디코딩과 빔 서치(beam search)(Teller, 2000; Graves, 2012)와 같은 결정적 방법은 높은 확률의 결과를 찾아내며, 종종 높은 품질의 결과를 산출하지만 다양성은 부족할 수 있습니다. 
    • 샘플링 알고리즘(e.g., 온도 샘플링(Ackley et al., 1985))은 다양한 결과 세트를 생성하고, 이를 집계하여 정확성을 높이는 데 사용됩니다(예: 다수결을 통해 (Wang et al., 2022a)). 
    • 최근에는 LLM과 검색 알고리즘을 결합하는 방법이 개발되었습니다. 
    • 여기에는 넓이 우선 또는 깊이 우선 탐색(Yao et al., 2023), 몬테카를로 트리 탐색(MCTS)(Zhang et al., 2023; Zhou et al., 2023; Liu et al., 2024; Choi et al., 2023), 가이드 빔 서치(guided beam search)(Xie et al., 2023)가 포함됩니다. 
    • 이러한 모든 방법들은 추론 시간에 검색을 사용함으로써 여러 과제에서 성능 향상을 가져올 수 있음을 보여줍니다. 
    • 그러나 성능 개선의 대가로 연산 자원이 소모됩니다. 
    • 이에 대한 비용-성능의 상충 관계 분석은 여전히 부족합니다. 
    • 본 논문에서는 연산 예산과 문제 해결 성능 간의 상충 관계를 체계적으로 분석하고, 경험적으로 파레토 최적을 달성하는 트리 탐색 방법을 제안합니다.
  • Process Reward Models. 
    • 프로세스 보상 모델(PRM)은 LLM의 추론 및 문제 해결 능력을 향상시키기 위한 기법으로 등장했습니다. 
    • 이러한 모델은 LLM이 생성한 일련의 중간 단계에 보상을 할당합니다. 
    • PRM은 낮은 오류율로 추론 경로를 선택하고, 강화 학습 스타일의 알고리즘에서 보상을 제공하는 데 효과적임이 입증되었습니다 (Uesato et al., 2022; Polu & Sutskever, 2020; Gudibande et al., 2023). 
    • Ma et al. (2023)은 PRM을 적용하여 중간 단계에 보상을 부여하고 다단계 추론 과정을 안내합니다. 
    • PRM은 사람에 의해 레이블된 데이터(Lightman et al., 2023a) 또는 모델이 레이블한 합성 데이터(Wang et al., 2023)를 통해 훈련될 수 있습니다. 
    • 본 연구에서는 PRM을 보상 모델로 사용하여 생성된 솔루션을 선택하고, 트리 탐색에서 탐색할 부분 솔루션을 선택하는 데 활용합니다.

3 COMPUTE-OPTIMAL INFERENCE FOR PROBLEM-SOLVING 

    • 추론전략과 모델 후보들을 고려해서 가장 좋은 결과를 내는 최적의 인퍼런스 방법을 찾는다?
  • 다음 질문을 탐구합니다: 
    • 주어진 FLOPs 예산에서, 정책 모델의 최적 모델 크기와 효과적인 추론 전략을 선택하여 성능(즉, 정확도)을 최대화하려면 어떻게 해야 하는가? 
    • 우리는 이 문제를 처음으로 공식화하고, 관련된 추론 시 스케일링 법칙을 연구하여 이전의 스케일링 법칙 연구와 차별화된 작업을 제시합니다(Fig. 2).
  • 이를 해결하기 위해, 문제 해결 오류율 E(N, T; S)를 모델 파라미터 수 N, 생성된 토큰 수 T, 추론 전략 S의 함수로 나타냅니다. 
  • 계산 예산 C는 N과 T에 기반하여 결정적인 함수 \( \text{FLOPs}(N, T; S) \)로 표현됩니다. 
  • 우리의 목표는 테스트 시 계산 제약 조건 \( \text{FLOPs}(N, T, S) = C \) 하에서 \( E \)를 최소화하는 것입니다:
  • 여기서 \( N_{\text{opt}}(C) \)와 \( T_{\text{opt}}(C) \)는 주어진 계산 예산 \( C \)에 대한 최적의 할당을 나타냅니다.
  • 특정 모델에 대한 추론 계산(FLOPs)은 정책 모델을 사용하여 더 많은 토큰을 생성하거나, 추론 전략을 통해 후보 솔루션을 추가로 샘플링하고 이를 보상 모델로 순위를 매기는 방법으로 조정할 수 있습니다. 
  • 추론 전략으로는 샘플링 및 트리 검색 접근법을 고려하며, 재순위 지정이나 다수결 투표와 결합합니다. 
  • 여기에는 탐욕적 검색(greedy search), 다수결 투표(majority voting), best-of-n, 가중 투표(weighted voting), 그리고 이들의 트리 검색 변형이 포함됩니다.
  • 모델 파라미터 N과 생성된 토큰 수 T, 이때 사용하는 추론 전략 S을 고려했을때 예산은 C만큼 들고 오류율은 E라고 하자
  • 즉 C=FLOPs(N,T;S)로 표현되고 E(N,T;S)로 표기되는데 같은 C에서 (N,T;S)의 다양한 쌍들중에서 E가 제일작게하는 N,T을 찾는 문제이다

3.1 INFERENCE STRATEGIES 

  • 다음과 같이 실제로 널리 사용되는 추론 전략들을 고려합니다:
  • 탐욕적 검색(Greedy Search): 
    • 이 전략은 각 단계에서 확률이 가장 높은 토큰을 선택하여 한 번에 하나의 토큰을 생성합니다. 
    • 계산 효율성이 높지만, 다양성 측면에서는 종종 최적이 아닙니다.
  • Best-of-n: 
    • rejection sampling으로도 알려진 이 전략은 여러 후보를 생성한 후, 보상 모델(reward model)에 의해 가장 높은 점수를 받은 후보를 선택합니다.
  • 다수결 투표(Majority Voting): 
    • 이 전략에서는 여러 후보를 생성하고, 생성된 모든 출력에서 가장 자주 나타나는 답변을 문제의 최종 답변으로 결정합니다.
  • 가중 다수결 투표(Weighted Majority Voting): 
    • 다수결 투표의 변형으로, 보상 모델이 부여한 점수를 기반으로 각 후보에게 가중치를 부여하여 최종 답변을 결정합니다.
  • 우리는 전략이 표준 자동회귀 샘플링 알고리즘(예: 온도 샘플링)을 사용하여 후보 집합을 생성할 경우 샘플링 기반(sampling-based) 전략이라고 정의합니다. (탐욕적 검색은 단일 결정론적 후보만 생성하기 때문에 별도로 취급합니다.) 
  • tree-search 변형은 후보 집합을 생성하기 위해 트리 검색 방식을 사용합니다. 
  • 트리 검색 방법을 논의하기 전에, 샘플링 기반 투표에 대한 분석을 아래에 제시합니다.
  • 샘플링 기반 투표의 이론적 분석
    • Theorem 1과 Theorem 2에서 무한 계산 리소스를 가정한 투표 기반 전략의 점근적(asymptotic) 행동에 대한 이론적 결과를 제시합니다. 
    • 간략히 말하면, 표준/가중 다수결 투표의 정확도는 무한 샘플 수를 가정할 때 수렴하며, 이 수렴 결과는 언어 모델(및 보상 모델)이 표현하는 분포에만 의존합니다. 
    • 이러한 이론적 결과는 **Sec. 4.2**에서 제시한 실험 결과와도 일치하며, 높은 샘플링 예산에서 포화(saturation) 현상이 나타남을 보여줍니다. 
    • 증명은 **Appendix A**에 포함되어 있습니다.
    • 무한 샘플링을 할 수 있다면, 표준/가중 다수결 투표의 정확도는 수렴하게 된다 => 증명도 부록에 있다고함
    • 아마도 샘플링할때마다 결과가 달라지면 분석도 달라질 수 있는거 아니냐? 에 대한 설명을 하기 위함인듯
  • 기호 및 가정
    • 어휘(Vocabulary) \(V\): 유한한 어휘를 \(V\)로 정의하며, \(V^*\)는 \(V\)의 Kleene 폐포(Kleene closure)로, 모든 문자열의 집합을 나타냅니다.
      • V가 {a,b}이면 V*는 {a,b,aa,ab,ba,bb,aaa,...} 무한한 집합을 의미한다
    • 문제 \(x\): 주어진 문제 \(x\)에 대해, 언어 모델이 \(y\)를 답변한다고 하면, \(r \in V^*\)와 \(e \in V\)를 사용하여 \(r e\) 형식의 출력을 생성합니다. 여기서 \(e\)는 추론의 끝을 표시하는 특별한 토큰입니다.
    • 문자열 길이 제한: 우리는 답변 문자열의 길이가 항상 \(L\) 토큰보다 짧다고 가정합니다. 즉, \( |y| \leq L \), 여기서 \(L \in \mathbb{N}^*\)는 고정된 값이고, \(|y|\)는 \(y\)의 길이를 나타냅니다.
    • 언어 모델 \( \pi \): \( \pi(v|w) \)는 입력 프롬프트 \(w\)를 기반으로 \(v\)를 생성할 확률을 나타냅니다.
    • 보상 모델 \( \rho \): \( \rho(v) \)는 문자열 \(v\)에 할당된 점수를 나타냅니다.
    • 지시 함수(Indicator Function): \( I \)는 지시 함수로 사용됩니다.
  • 아래 두 정리는 다수결 튜포와 가중 다수결 투포의 정확도가 무한샘플링과 어떤 관계있는지 보여주는 것
    • n이 샘플링수이다
    • 즉 n->무한대로 보냈을때의 acc는 rey|xi의 모델확률가 같아진다고 함
    • 여기서 sigma 첨자인 r이 V*이 속한 모든 경우에 대해 더하게 되는데
    • V*은 사실상 무한집합이고 r이 가능한 추론경로의 개념이 되는것
    • 즉 이러한 모든 추론경로를 고려했을때 xi에 답할 가장 확률높은 출력 y가 yi가 될때 정확도가 올라가는 것
    • 두번째식은 기댓값에 대한것으로 n이 무한대가 아닐때 기댓값 감소율 O(c^-n)을 빼주는 식
    • 보상 모델 ρ\rho이 추가되는 것이 다름
  • 주석(Remarks)
    • 정리 1과 정리 2는 샘플 수가 증가함에 따라 정확도가 수렴한다는 것을 나타내며, 이는 고정된 모델에서 더 많은 샘플을 사용하는 것의 성능 향상이 결국 포화 상태에 도달한다는 것을 의미합니다.
    • 수렴의 한계는 모든 가능한 추론 경로를 통해 정답을 생성할 확률에 의해 결정되며, 가중 다수결 투표의 경우 이 확률은 가중 합으로 해석되어야 합니다.
    • 이 결과는 3.1.1 및 3.1.2절에 자세히 설명된 트리 탐색 기반 변형(tree-search-based variants)과 같이 "좋은" 추론 경로를 탐색하는 추론 알고리즘을 고려해야 할 동기를 제공합니다.
    • 또한, 정리 1과 2는 일반 다수결 투표와 가중 다수결 투표를 비교할 수 있는 통찰을 제공합니다.
    • 비공식적으로, 보상 모델이 "무작위보다 더 나은", 즉 평균적으로 정답에 더 높은 보상을 할당하는 경우, 가중 다수결 투표의 정확도 한계는 일반 다수결 투표보다 더 높습니다.
    • 실험에서, 우리는 일관되게 가중 다수결 투표가 일반 다수결 투표를 능가한다는 것을 발견했습니다. 
    • 따라서, 본 논문에서는 주로 best-of-n과 가중 다수결 투표에 초점을 맞추었으며, 일반 다수결 투표 결과는 부록 D로 연기하였습니다.

3.1.1 MONTE CARLO TREE SEARCH (MCTS)

  • Monte Carlo Tree Search(MCTS)는 전략적 의사 결정이 요구되는 보드 게임과 같은 분야에서 효과적인 것으로 입증되었습니다(Silver et al., 2016; 2017; Jones, 2021). 
  • 최근 연구에서는 MCTS를 LLM(대형 언어 모델) 컨텍스트에 적용하여 텍스트 생성 프로세스를 향상할 수 있음을 보여주었습니다. 
  • 이 컨텍스트에서 MCTS는 탐색 단계를 점수화하고 안내하기 위해 가치 모델(value model)과 함께 사용됩니다. 
    • MCTS는 응답이 생성되면서 중간중간에 잘못됐다고 싶으면 가지치기를 하는거라고 함
    • 즉 수학문제에 대한 질문이 입력이고, 이에대해 답변을 생성할때 중간에 해설을 생성할때 틀리지 않게 틀리게 생성되는 부분을 가지치기 한다는 것이다
    • 이렇게 가지치기 할때 value model을 이용하는거 같다
    • 예를 들면, 12x12는 뭐야? 하면 중간에 "12x2=25"와 "12x2=24" 모두 확률적으로 생성될 수 있는데 이게 value 값이 높은 "12x2=24"가 생성되도록 유도해주는 느낌이랄까?
    • 근데 best-of-n은 이런거 상관없이 독단적으로 여러개 일단 생성하고 그 중에서 가장 좋은거 하나 뽑는 식이다
  • 추가적인 배경 설명은 부록 B에 제공합니다.
  • MCTS 또는 그 변형(Tree of Thoughts(Yao et al., 2023) 등)에 대한 최근 연구는 주로 연구된 작업에서 성능(예: 정확도)을 개선하는 데 초점을 맞추고 있습니다. 
  • 하지만 생성된 토큰 수나 처리 시간으로 측정된 계산 예산 측면에서 MCTS와 best-of-n 및 다수결 투표와 같은 기존 방법을 일반적으로 비교한 연구는 드물거나 비용-성능 트레이드오프가 잠재적으로 불리하다는 것을 시사합니다. 
  • 예를 들어, MCTS는 훨씬 더 많은 리소스를 소비하며, 종종 간단한 방법에 비해 수십 배 더 많은 생성된 토큰을 필요로 합니다. 
    • MCTS는 리소스가 많이 필요하다고함
  • 특히, 탐색 트리의 경로 중 상당 부분은 노드를 평가하고 선택하는 데 사용되며, 이러한 경로는 반드시 최종 후보 솔루션의 일부가 되지는 않습니다. 
  • 그러나 MCTS는 샘플링된 솔루션이 고품질의 중간 단계를 포함하도록 보장합니다.
  • 반면, 샘플링 방법은 여러 솔루션을 병렬적으로 독립적으로 생성하며, 생성된 모든 시퀀스가 후보 솔루션에 포함됩니다. 
  • 하지만 이들 시퀀스의 중간 단계가 반드시 고품질일 것이라고 보장할 수는 없습니다. 
  • 왜냐하면 저품질 단계를 제거하거나 유망한 단계를 활용할 메커니즘이 없기 때문입니다.
  • 이것은 MCTS와 비교 가능한(혹은 더 나은) 성능을 제공하면서도 계산 비용이 덜 드는 새로운 트리 탐색 방법의 필요성을 강조합니다. 
  • 특히, 가중 다수결 투표 및 best-of-n과 유사한 비용을 가진 방법이 필요합니다. 
  • 이러한 배경이 우리의 새로운 방법인 **Reward Balanced SEarch(REBASE)**를 고안하게 된 동기입니다.

3.1.2 REWARD BALANCED SEARCH (REBASE)

  • REBASE 트리 탐색 방법은 Fig. 3에서 보여지듯이 트리 탐색의 탐색(exploitation) 및 가지치기(pruning) 특성을 계승하면서도, 중간 노드의 품질을 추정하기 위해 보상 모델(reward model)만을 사용합니다. 
  • 이는 명시적인 롤아웃(rollouts)을 통해 노드 품질을 추정하지 않으므로 MCTS 같은 방법에 비해 계산 비용이 절약됩니다. 
    • 간단히 말하면, REBASE는 과정 보상 모델(process reward model, PRM)을 사용하여 각 깊이에서 어떤 노드를 확장할지 결정합니다. 
    • MCTS는 다음 토큰을 결정할때, 끝까지 생성 시뮬레이션을 해보고 value을 평가하는데.. 여기서는 현재까지의 과정만 보고 판단한다는 의미?
  • 구체적으로, REBASE는 주어진 깊이에서 노드의 소프트맥스 정규화된 보상 점수에 따라, 총 확장 예산 내에서 노드를 확장합니다. 
  • 아래에서 이 절차를 더 자세히 설명합니다.
  • Notations
    • 세분화된 LLM은 정책 \(\pi_\theta\)로 간주되며, 이를 통해 솔루션이 단계별로 생성됩니다.
    • 주어진 질문 \(x\)와 솔루션의 처음 \(k\)단계 \(r_1 \cdots r_k\)가 주어졌을 때, \((k+1)\)-번째 단계는 \(\pi_\theta(\cdot|xr_1 \cdots r_k)\)에서 샘플링됩니다.
    • REBASE는 추론 중에 **솔루션 트리**를 생성합니다.
    • 루트 노드는 질문 \(x\)이고,
    • 다른 노드는 솔루션의 단계에 해당합니다.
    • 트리의 각 단계는 \(\pi_\theta\)를 사용해 자식 노드를 생성하며, 노드는 해당 솔루션 단계를 나타냅니다.
    • 각 노드 \(r_k\)의 보상은 PRM을 사용해 계산되며 \(R(r_k) := R(qr_1 \cdots r_k)\)로 표현됩니다.
  • Initialization
    • 질문 \(x\), 균형 온도 \(T_b > 0\), 생성할 솔루션의 목표 개수 \(N\)이 주어졌을 때, 질문에 대한 첫 번째 단계를 \(N\)회 샘플링하여 깊이 1의 모든 노드를 생성합니다.
    • 초기화 시 깊이 0의 샘플링 예산 \(B_0\)를 \(N\)으로 설정합니다.
  • Reward assignment and update
    • \(i\)-번째 반복에서 PRM은 깊이 \(i\)에 있는 모든 노드에 보상을 할당합니다.
    • 이후 알고리즘은 깊이 \(i\)까지의 솔루션이 완료되었는지 확인합니다.
    • \(C_i\)개의 완료된 솔루션이 있다고 가정하면, 샘플링 예산을 다음과 같이 업데이트합니다:
    • \[B_i \leftarrow B_{i-1} - C_i\]
    • \(B_i = 0\)이면, 프로세스가 종료되며 \(N\)개의 솔루션을 얻게 됩니다.
    • B0=N으로 설정됐으므로 N개 응답이 나올때까지 탐색한다는 의미인듯
    • B1=B0-C1=N-C1, C1은 첫번째 토큰이 end-of-token이 된 것을 의미하는거겠지?
  • Exploration balancing and expansion.
    • 깊이 \(i\)에서 보상이 \(R(n_j)\)인 모든 노드 \(n_j\)에 대해 다음과 같은 확장 너비를 계산합니다:
    • 그런 다음, 깊이 \(i\)의 모든 노드 \(n_j\)에 대해 \(W_j\)개의 자식을 샘플링하고, 다음 반복을 시작합니다. 

4 EXPERIMENTS 

  • 우리 실험은 두 가지 주요 질문을 중심으로 진행됩니다:
    • Compute-optimal model size: 고정된 추론 전략을 사용하면서, 모델 크기를 변화시키며 추론 시간에 따른 계산이 증가할 때 성능이 어떻게 변하는가?
    • Compute-optimal inference strategy: 다양한 추론 전략(및 다양한 모델 크기)을 사용하여 추론 시간에 따른 계산이 증가할 때 성능이 어떻게 변하는가?
  • 우리는 아래에서 실험 설정을 자세히 설명합니다.

4.1 SETUP

  • Datasets: 
    • 우리는 추론 계산을 확장할 때 성능에 미치는 영향을 조사하기 위해 두 가지 수학 문제 해결 데이터셋에서 실험을 수행합니다. 
    • 구체적으로, MATH(Hendrycks et al., 2021a)와 GSM8K(Cobbe et al., 2021b)는 각각 고등학교 수학 경시대회 수준의 문제와 초등학교 수준의 수학적 추론 문제를 포함하는 데이터셋입니다. 
    • (Lightman et al., 2023b; Wang et al., 2024; Sun et al., 2024)의 방법에 따라, 우리는 **MATH500** 하위 집합을 테스트 세트로 사용합니다.
  • Policy model (solution generator): 
    • 고정된 전략을 사용하면서 추론 계산이 증가할 때 성능이 어떻게 변하는지 연구하기 위해, 주요 변화 축은 모델 크기입니다. 
    • 따라서 우리는 Pythia (Biderman et al., 2023)를 기본 모델로 선택합니다. 
    • Pythia는 다양한 모델 크기를 제공하므로 이를 사용합니다. 
    • 다양한 추론 전략(예: 트리 탐색, 가중 다수결)을 사용하여 추론 확장을 연구하기 위해, 우리는 수학 전문화된 Llemma 모델(Azerbayev et al., 2024)을 사용합니다. 
    • 이 모델은 MetaMath 데이터셋(Yu et al., 2024)에서 전체 매개변수를 사용한 감독 학습 방식(Full-SFT)으로 미세 조정(finetuning)됩니다. 
    • 미세 조정 구성은 부록에 제공됩니다. 
    • 또한, 우리는 **Mistral-7B**(Jiang et al., 2023)를 테스트하여 다양한 모델과 아키텍처에서 우리의 결과를 확장합니다.
  • Reward model: 
    • 모든 실험은 동일한 **Llemma-34B 보상 모델**을 사용하며, 이 모델은 합성 과정 보상 모델링 데이터셋인 **Math-Shepherd**(Wang et al., 2024)에서 미세 조정되었습니다. 
    • 우리는 모델에 보상 헤드를 추가하여 각 단계 끝에서 스칼라 보상을 출력할 수 있도록 했습니다.
  • Inference configuration: 
    • 우리는 샘플링 및 트리 탐색 방법을 사용하여 여러 후보를 생성하고, 이를 **best-of-n**, **다수결**, 또는 **가중 다수결**을 통해 답을 선택합니다. 
    • 각 설정은 여러 번 실행되어 평균과 분산을 계산하며, 이를 통해 무작위성의 영향을 완화하고 결론의 신뢰성을 향상시킵니다.

4.2 COMPUTE-OPTIMAL MODEL SIZE 

  • **다른 모델들의 추론 계산 예산 비교**: 우리는 추론 중 각 문제에서 사용되는 FLOP 수를 플로팅하여 서로 다른 모델들의 추론 계산 예산을 비교합니다. 추론 FLOP 수는 (Kaplan et al., 2020)의 표준 공식을 기반으로 계산합니다.
  • Scaling law of compute-optimal inference for model size: 
    • **그림 1**은 추론 계산과 오류율 간의 관계를 서로 다른 모델 크기에 대해 보여줍니다. 
    • 오류율은 처음에 꾸준히 감소하다가 점차 포화 상태에 도달합니다. 
    • 처음에는 작은 모델에서 여러 번 샘플링하는 것이 계산적으로 최적입니다. 
    • 그러나 더 큰 계산 예산에서는 성능이 포화된 작은 모델들보다 더 큰 모델이 선호됩니다. 
    • 계산비용이 조금 있을떄는 작은모델 여러번 돌리는게 효율적인데
    • 계산비용이 넉넉할때는 큰 모델 여러번 돌리는게 좋음
    • 즉 이는 이전의 논문에서 봤듯이, 문제의 난이도에 따라 달라지기도 하는 문제임
    • **그림 1**의 오른쪽 패널에서 강조된 바와 같이, 최적 모델 크기는 추론 예산에 따라 달라집니다. 
    • 우리는 추론 FLOP 수 C와 모델 크기 N에 대한 회귀 분석을 수행하여 주어진 계산 예산과 그에 최적인 모델 크기 간의 관계를 확립했습니다. 
    • 그 결과 나온 방정식은 **log10 (C) = 1.19 log10 (N) + 2.03**로, 이를 통해 특정 계산 예산에 대한 최적 추론 모델 크기를 추정할 수 있습니다.
  • Llemma-7B achieves competitive accuracy to Llemma-34B with less compute:
    • **그림 4**와 **그림 5**는 Llemma 7B와 Llemma 34B의 오류율과 추론 FLOP 수 간의 관계를 보여줍니다. 
    • Llemma-7B는 Llemma-34B와 유사한 정확도를 달성하는 데 필요한 총 FLOP 수가 약 2배 적습니다. 
    • 이 결과는 추론 전략(샘플링 전략, MCTS, REBASE)과 작업(MATH, GSM8K) 전반에서 일관되게 나타났습니다. 
    • 이 결과는 동일한 훈련 데이터셋과 모델 가족을 사용할 때, 더 작은 모델을 사용하여 적절한 추론 전략을 통해 더 많은 토큰을 생성하는 것이 더 큰 모델을 사용하는 것보다 비용-성능 측면에서 더 유리할 수 있음을 시사합니다.
    • 샘플링에서보면 REBASE가 제일 좋다는 것을 보여주기도 하고
    • 같은 샘플링으로 봤을때에도 작은 모델을 여러 번 돌리는게 좋다는것을 보여주기도 함

4.3 COMPUTE-OPTIMAL INFERENCE STRATEGY

  • REBASE는 파레토 최적이다:
    • REBASE는 모든 설정에서 모델과 평가 작업을 고정했을 때 샘플링 기반 방법들보다 뛰어난 비용-성능 트레이드오프를 보이며, 모든 추론 계산 예산에서 가장 좋은 성과를 냅니다 (그림 4, 5, 6, 7). 
    • 예를 들어, **그림 4**에서 REBASE는 모든 추론 계산 예산에서 계산 최적 전략으로, 7B 모델이 일반적으로 최적 모델 크기입니다. 
    • 반면 MCTS는 각 계산 예산에서 샘플링 기반 방법들보다 성능이 떨어지며, 이는 비용이 많이 드는 롤아웃 때문에 발생하는 것으로 보입니다 (그림 4)
    • – REBASE는 보상 모델을 효율적으로 사용하기 때문입니다.
    • 표 1은 REBASE가 샘플링 기반 가중치 투표 방식보다 더 적은 계산 예산으로 더 나은 정확도를 달성함을 보여줍니다. 
    • 7B 모델을 사용할 때, REBASE는 7배 적은 계산으로 더 높은 정확도를 달성합니다. 
    • 이 발견은 새롭고, 일반적으로 성능을 향상시키지만 계산 비용이 더 높은 기존 트리 탐색 방법들과는 다릅니다 (Chen et al., 2024a; Xie et al., 2023).
  • 약한 모델은 트리 탐색에서 더 많은 성과를 얻는다: 
    • 예를 들어, 제안된 REBASE는 Mistral-7B, Llemma-7B, Llemma-34B에서 각각 MATH 데이터셋에서 5.3%, 3.3%, 2.6% 성능 향상을 이끌어냈습니다. 
    • 정확도 증가의 순서는 해당 데이터셋에서 모델의 탐욕적 검색 정확도와 반비례합니다. 
    • 이는 탐욕적 검색 정확도가 낮은 약한 모델이 REBASE와 같은 트리 탐색 방법에서 더 큰 이점을 얻을 수 있음을 시사합니다.
  • REBASE는 샘플링보다 더 높은 정확도로 더 늦게 포화 상태에 이른다: 
    • **그림 6**과 **그림 7**에서, 샘플링과 REBASE가 각각 GSM8K에서는 일찍 포화되며, MATH에서는 상대적으로 늦게 포화된다는 것을 관찰할 수 있습니다. 
    • 우리는 이를 GSM8K와 MATH 간의 난이도 차이에 기인한다고 생각합니다. 
    • 구체적으로, LLM은 쉬운 문제에서는 올바른 답에만 높은 확률을 부여하지만, 더 어려운 문제에서는 다양한 답에 확률을 분산시킬 수 있습니다. 
    • 따라서 더 어려운 문제는 답에 대한 분포로 수렴하기 위해 더 많은 해결 경로를 집합적으로 모아야 할 수 있습니다 (이것은 **정리 1**과 **정리 2**에서 언급한 것처럼). 
    • **그림 6**에서 MATH에 대해 REBASE는 결국 샘플링보다 더 높은 정확도로 포화 상태에 도달하는 것을 볼 수 있습니다. 
    • 우리는 REBASE에서 샘플을 뽑는 것이 기본 언어 모델에서 샘플을 뽑는 것보다 올바른 답에 더 높은 확률을 부여하는 정책에서 샘플을 뽑는 것과 같다고 가정합니다. 
    • 만약 이것이 맞다면, **정리 1**과 **정리 2**에 따라 상한선은 더 높아질 것입니다. 
    • 트리 탐색 알고리즘의 행동을 공식적으로 분석하는 것은 흥미로운 미래 연구로 남겨두겠습니다.

5 CONCLUSIONS, LIMITATIONS, AND DISCUSSIONS ON CONCURRENT WORKS

  • 우리는 다양한 모델 크기, 모델 계열, 추론 전략에 대해 추론 시 소모되는 연산량과 과제 성능 간의 관계를 연구하여, 경험적 추론 스케일링 법칙을 도출했습니다. 
  • 이러한 관계를 통해 주어진 연산 예산 내에서 최적의 성능을 제공하는 **연산 최적화 추론(Compute-Optimal Inference)**을 설계할 수 있었습니다.
  • 우리의 결과는 세 가지 주요 시사점을 제공합니다.  
    • 1. **작은 모델의 활용**: 작은 모델을 사용하면서 더 많은 토큰을 생성하는 추론 전략이, 동일한 연산 예산에서 큰 모델을 사용하는 것보다 더 나은 성능을 보이는 경우가 많습니다. 이는 연산 자원이 제한된 실제 환경에서, 비용-성능 균형 측면에서 더 정교한 추론 전략을 사용한 작은 모델 배포가 유리할 수 있음을 시사합니다.  
    • 2. **무한 연산 자원의 한계**: 무한 연산 자원을 투입하여 더 많은 샘플을 생성하는 경우, 샘플링 기반 다수결 전략은 결국 생성 정책에 따라 제한된 분포로 수렴하게 됩니다. 따라서 대안적인 추론 전략을 설계하여 샘플링 분포를 변경하는 것이 중요합니다.  
    • 3. **REBASE 알고리즘의 설계 및 효과**: 우리는 REBASE라는 새로운 트리 탐색 기반 추론 전략을 설계했으며, 이를 통해 모든 테스트된 연산 예산에서 최상의 성능을 달성하는 **파레토 최적**임을 확인했습니다. REBASE는 널리 사용되고 관심을 받고 있는 가중치 기반 다수결 및 MCTS(Monte Carlo Tree Search) 방법을 능가합니다. 이 결과는 REBASE의 강점을 보여줄 뿐만 아니라, 추론 시간 알고리즘을 통해 언어 모델 성능을 더욱 향상시킬 수 있는 여지가 크다는 것을 나타냅니다.
  • 한계점  
    • - 본 연구의 경험적 분석은 수학 문제 해결에 초점을 맞추고 있습니다. 수학 문제 해결 외의 과제에 대해 추론 스케일링 법칙과 연산 최적화 추론 전략을 조사하는 것은 미래 연구에서 가치 있는 방향이 될 것입니다.  
    • - 우리는 주로 GSM8K와 MATH500 데이터셋에서 제안된 REBASE를 평가했습니다. REBASE 알고리즘은 노드에 점수를 할당하는 함수만을 활용한다는 가정을 기반으로 하며, 연구된 과제 외의 작업에서도 효과적일 것으로 추정됩니다.

Reference

댓글

댓글 쓰기