Ensembling Large Language Models with Process Reward-Guided Tree Search for Better Complex Reasoning

2412.15797

Sungjin Park et el.

🤗 2024-12-25

↗ arXiv ↗ Hugging Face ↗ Papers with Code

TL;DR
#

최근 대규모 언어 모델(LLM)의 발전에도 불구하고, 복잡한 추론 문제에서 일관된 성능을 보이는 것은 여전히 어려운 과제입니다. 기존의 토큰 또는 출력 레벨에서의 앙상블 기법들은 이러한 문제를 해결하는 데 한계를 보였습니다. 본 논문에서는 이러한 문제를 해결하기 위해, 단계별 추론 과정을 마르코프 결정 과정으로 공식화하고, 프로세스 기반 보상 모델과 몬테카를로 트리 탐색(MCTS) 기법을 활용한 새로운 프레임워크인 LE-MCTS를 제시합니다.

LE-MCTS는 여러 LLM을 활용하여 단계별 추론을 수행합니다. 각 LLM은 추론 과정의 다음 단계를 생성하고, 프로세스 기반 보상 모델은 각 단계의 정확성을 평가하여 MCTS가 최적의 추론 경로를 찾도록 안내합니다. 실험 결과, LE-MCTS는 기존의 단일 LLM 기반 방법 및 다른 앙상블 기법들을 능가하는 성능을 보였으며, 특히 MATH와 MQA 데이터셋에서 눈에 띄는 성능 향상을 달성했습니다. 이는 LE-MCTS가 복잡한 추론 문제 해결에 효과적임을 보여줍니다.

Key Takeaways
#

Why does it matter?
#

본 논문은 복잡한 추론 문제 해결을 위한 새로운 프레임워크를 제시하여, 기존의 언어 모델 앙상블 방법의 한계를 극복하고 성능을 향상시켰다는 점에서 중요합니다. 프로세스 기반 보상 모델과 몬테카를로 트리 탐색을 활용하여 언어 모델들을 단계적으로 앙상블하고, 복잡한 문제 해결에 효과적임을 다양한 벤치마크를 통해 입증하였습니다. 이는 추론 과정의 오류를 조기에 수정하고 정확도를 높이는 데 기여하며, 향후 연구에서 다양한 복잡한 추론 문제에 적용될 수 있는 가능성을 제시합니다.

Visual Insights
#

🔼 그림 1은 LE-MCTS의 예시 출력을 보여줍니다. LE-MCTS는 여러 개의 언어 모델을 사용하여 단계별 추론을 수행합니다. 각 노드는 추론 과정의 중간 단계를 나타내고, 각각의 언어 모델이 생성한 추론 단계가 표시됩니다. 루트 노드는 노란색으로 강조 표시되어 있으며, 각 노드와 해당 언어 모델은 같은 색상 코드로 표시되어 각 단계에서 어떤 언어 모델이 사용되었는지 쉽게 파악할 수 있도록 합니다. 이를 통해 LE-MCTS가 다양한 언어 모델의 강점을 결합하여 더욱 정확한 추론을 수행하는 과정을 보여줍니다.
read the caption
Figure 1: Example output of LE-MCTS. The reasoning steps in the LE-MCTS output can be generated by different LLMs. We highlight the root node in yellow and apply the same color coding to the corresponding nodes and the language model.

Algorithm: LE-MCTS

Input: input q, language models {π₁, …, π_L}, max MCTS iterations n_iter,
UCT constant C, max # child nodes n_child, threshold ε, PRM ϕ
// Initialize
1: s₀ ← CreateNode(T,q)
2: for i=1,…,n_iter do
3: s←s₀
// Selection
4: while s is not a leaf node do
5: S←{}
6: for s′∈child(s) do
7: if n(child(s′))<n_child and v_s′−max_{s′′∈child(s′)}v_s′′≥ε then
8: S←S+{s′}
9: end if
10: end for
11: s←_s′∈Sargmax v_s′+C√(lnN_s/N_s′)
12: end while
// Expansion
13: π_l←RandomSelect({π₁, …, π_L})
14: p_1:k−1←GetPath(s)
15: while p_k,t is not \n do
16: p_k,t←_w∈Vargmax π_l(w	p_k,<t;q,p_1:k−1)
17: end while
18: s′←CreateNode(T,{p_1:k−1,p_k})
// Evaluation and Value Backpropagation
19: v_s′←ϕ(q,p_k),N_s′←1
20: while s′ is not a root node do
21: s′←GetParent(s′)
22: N_s′←N_s′+1
23: v_s′←((N_s′−1)v_s′+max_{s′′∈child(s′)}v_s′′)/N_s′
24: end while
25: end for
Output: Highest-rewarded solution p_1:K^*
26: Return ChooseBest(T)

🔼 이 표는 LE-MCTS 알고리즘의 의사 코드를 보여줍니다. 입력값으로는 문제(q), 언어 모델 집합, MCTS 반복 횟수 제한, UCT 상수, 자식 노드 수 제한, 임계값 및 PRM(Process Reward Model)이 있습니다. 알고리즘은 노드 선택, 확장, 평가 및 백전파 단계를 반복하여 최적의 추론 경로를 찾습니다. 각 단계는 UCT 알고리즘, 무작위 언어 모델 선택, PRM을 사용한 보상 계산, 그리고 낙관적인 역전파를 포함한 세부적인 과정을 포함합니다.
read the caption
Table 1: Pseudocode for LE-MCTS.

In-depth insights
#

Process-Level Ensembling
#

본 논문에서 제안하는 ‘프로세스-레벨 앙상블’은 기존 토큰 또는 출력 레벨 앙상블 방식의 한계를 극복하기 위한 새로운 접근법입니다. 단순히 최종 결과만을 비교하는 것이 아니라, 복잡한 추론 과정을 단계별로 모델링하여 각 단계의 정확성을 평가함으로써, 오류를 조기에 수정하고 보다 정확한 추론 경로를 찾아낼 수 있다는 점이 핵심입니다. 이는 마치 한 문제를 풀 때, 중간 과정을 확인하고 오류를 수정해나가는 사람의 추론 방식과 유사합니다. 마르코프 결정 프로세스(MDP)와 몬테 카를로 트리 탐색(MCTS)을 활용, 각 단계마다 여러 언어 모델의 출력을 비교하여 최적의 경로를 선택함으로써, 개별 모델의 약점을 보완하고 강점을 결합하는 효과를 보입니다. 특히 복잡한 수학적 추론 문제에서 기존 방법보다 훨씬 우수한 성능을 보임으로써, 프로세스 레벨 앙상블이 복잡한 추론 문제 해결에 효과적임을 보여줍니다. 하지만, 프로세스 기반 보상 모델(PRM)의 정확도에 의존하는 점과 베이스 모델 선택의 중요성은 향후 개선 과제로 남아있습니다.

MCTS for Reasoning
#

본 논문에서 제시된 LE-MCTS는 복잡한 추론 문제를 해결하기 위한 새로운 프레임워크로, 언어 모델의 앙상블을 MCTS(Monte Carlo Tree Search)와 결합하여 단계별 추론 과정을 Markov 결정 과정(MDP)으로 공식화합니다. MCTS 알고리즘은 각 언어 모델의 강점을 활용하여 최적의 추론 경로를 찾는 데 중점을 두며, 프로세스 기반 보상 모델(PRM)의 안내를 받아 최적의 추론 사슬을 식별합니다. 이를 통해 단일 언어 모델 디코딩 알고리즘이나 기존의 언어 모델 앙상블 방법보다 성능이 향상되며, 특히 복잡한 수학적 추론 문제에서 효과적임을 보여줍니다. 단계별 추론 평가를 통해 오류를 조기에 수정하고 더욱 정확한 솔루션으로 이끄는 점이 LE-MCTS의 핵심 강점입니다. 하지만, PRM의 정확성에 의존하고, 계산 비용이 높아질 수 있다는 점은 한계로 지적될 수 있습니다.

Reward Model Impact
#

본 논문에서 다루는 ‘Reward Model Impact’에 대한 심층적인 분석은 보상 모델의 설계 및 선택이 모델 성능에 미치는 영향을 다각적으로 조명합니다. 단순히 정확도 향상에만 초점을 맞추는 것이 아니라, 보상 모델의 종류 (예: PRM vs. ORM), 매개변수 조정, 그리고 보상 모델의 과제 유형 적합성 등을 종합적으로 고려하여 최적의 성능을 도출할 수 있는 방안을 제시하는 것이 중요합니다. 과정 기반 보상 모델 (PRM)의 효과는 특히 복잡한 추론 과제에서 두드러지게 나타나며, 단계별 추론의 정확성을 높여 전체적인 성능 개선으로 이어집니다. 낙관적 역전파 전략을 통한 보상 모델 개선 또한 성능 향상에 기여하며, 이는 특히 복잡한 문제 해결에 유용함을 보여줍니다. 하지만, 보상 모델의 일반화 능력과 다양한 유형의 과제에 대한 적용성을 높이는 연구가 더 필요하며, 이는 향후 연구의 주요 과제가 될 것입니다. 보상 모델의 선택에 따른 계산 비용 증가와 같은 trade-off 또한 고려되어야 할 중요한 요소입니다.

Backprop Strategies
#

본 논문에서 제시된 백프로퍼게이션 전략은 단순히 오류를 역전파하는 것을 넘어, 모델의 학습 과정에 대한 심층적인 이해를 바탕으로 설계되었습니다. 특히, 낙관적 백프로퍼게이션은 저성능 자식 노드의 영향을 배제함으로써, 고품질 추론 경로 발견에 초점을 맞춰 효율성을 높입니다. 이는 복잡한 추론 문제 해결에 유리하지만, 단순 문제에서는 오히려 과도한 탐색으로 비효율성을 야기할 수 있습니다. 표준 백프로퍼게이션은 모든 자식 노드의 정보를 고려하여 안정적인 학습을 보장하지만, 낙관적 전략만큼 높은 정확도를 달성하지 못할 수 있습니다. 따라서, 문제의 복잡도에 따라 적절한 백프로퍼게이션 전략을 선택하는 것이 중요하며, 본 논문은 이를 위한 실험적 근거를 제시합니다. 이러한 전략들의 비교 분석을 통해, 모델의 성능과 효율성 사이의 균형점을 찾는 데 중요한 통찰력을 제공합니다.

Future Enhancements
#

본 논문에서 제시된 LE-MCTS 프레임워크의 미래 개선 방향은 크게 세 가지로 나눌 수 있습니다. 첫째, 프로세스 보상 모델(PRM)의 일반화입니다. 현재 사용된 PRM은 수학 문제 풀이에 특화되어 있으므로, 다양한 유형의 복잡한 추론 문제에 적용 가능하도록 PRM의 일반화가 필요합니다. 둘째, 기저 모델(base model) 선택 알고리즘의 개선입니다. LE-MCTS의 성능은 기저 모델의 질에 크게 의존하므로, 약한 기저 모델을 효과적으로 식별하고 제외하는 알고리즘을 개발해야 합니다. 마지막으로, 계산 효율성 향상을 위한 연구가 필요합니다. 특히 복잡한 추론 문제에 대해서는 LE-MCTS의 계산 비용이 상당히 높으므로, 계산 효율성을 높이는 새로운 기법이나 알고리즘을 개발하여 실용성을 높여야 합니다. 이러한 개선 방향들을 통해 LE-MCTS는 더욱 폭넓고 효율적인 언어 모델 앙상블 프레임워크로 발전할 수 있을 것입니다.

More visual insights
#

More on figures

🔼 그림 2는 LE-MCTS의 단일 반복 과정을 보여줍니다. 세 개의 대규모 언어 모델(LLM) 앙상블을 예시로 사용하여, 루트 노드에서 시작하여 각 노드에서 자식 노드를 선택하고, 확장하고, 평가하며, 값을 역전파하는 과정을 시각적으로 나타냅니다. 트리의 탐색은 최대 반복 횟수(niter)에 도달하거나, 트리에 더 이상 확장할 수 있는 노드가 없을 때까지 반복됩니다. 각 단계(선택, 확장, 평가, 역전파)는 색상 코드로 구분되어 이해도를 높였습니다.
read the caption
Figure 2: Single iteration of LE-MCTS. This example illustrates an ensemble of three LLMs. The iteration is repeated until the maximum number of iterations, ni⁢t⁢e⁢rsubscript𝑛𝑖𝑡𝑒𝑟n_{iter}italic_n start_POSTSUBSCRIPT italic_i italic_t italic_e italic_r end_POSTSUBSCRIPT, is reached or no further nodes in the tree can be expanded.

🔼 그림 3은 LE-MCTS 알고리즘에서 사용되는 두 가지 다른 값 역전파 전략(표준 및 낙관적)의 성능을 비교 분석한 결과를 보여줍니다. 각 전략에 따른 다섯 가지 수학 추론 벤치마크(GSM8K, MATH, SVAMP, ASDiv, MQA)에 대한 정확도를 비교하여, 낙관적 역전파 전략이 모든 데이터셋에서 일관되게 성능 향상을 가져온다는 것을 보여줍니다. 이는 낙관적 역전파 전략이 트리 내에서 높은 값을 가진 노드에 집중함으로써 효율적인 탐색을 가능하게 하기 때문입니다.
read the caption
Figure 3: Ablation study on value backpropagation strategies.

🔼 그림 4는 N=3, 빔 크기가 1일 때 프로세스 보상 기반 디코딩 알고리즘을 보여줍니다. 세 개의 언어 모델(LLM1, LLM2, LLM3)이 각각 독립적으로 추론 단계를 생성하고, 생성된 각 단계는 프로세스 보상 모델(PRM)에 의해 평가됩니다. 각 모델은 최고 보상을 가진 단계를 선택하고, 그 단계에 따라 다음 단계를 생성하는 과정을 반복합니다. Best-of-N (BoN)과 Beam Search(BS) 알고리즘은 단일 LLM에 대한 보상 기반 디코딩 방식을 보여주는 반면, Best-of-Ensemble (BoE)과 Ensemble Beam Search (EBS)는 다수의 LLM을 사용하여 보다 광범위한 검색 공간을 활용하는 방식을 보여줍니다.
read the caption
Figure 4: An illustration of process reward-guided decoding algorithms with N=3𝑁3N=3italic_N = 3 and a beam size of 1.

🔼 그림 5는 GSM8K 데이터셋과 유사한 난이도, 필요한 기술 및 스타일을 가진 16개의 합성 수학 문제 생성을 위한 프롬프트를 보여줍니다. 프롬프트는 각 문제에 대한 단계별 솔루션과 최종 답변을 생성하도록 지시합니다. 이를 통해 본 논문에서 제안하는 LE-MCTS 모델의 성능을 평가하기 위한 합성 데이터셋을 생성하는 과정을 보여줍니다. 합성 문제들은 GSM8K와 같은 유형의 문제를 다루도록 설계되었으며, 모델의 일반화 능력을 평가하는 데 사용됩니다.
read the caption
Figure 5: A prompt for generating 16 synthetic examples analogous to those in GSM8K.

🔼 이 그림은 논문의 MATH 데이터셋과 유사한 16개의 합성 수학 문제 생성을 위한 프롬프트를 보여줍니다. 프롬프트는 문제의 난이도, 필요한 기술, 스타일 등이 MATH 데이터셋과 일치하도록 16개의 새로운 문제를 생성하도록 지시합니다. 각 생성된 문제에 대해 단계별 솔루션과 최종 답변을 제공하고, 문제의 주제와 난이도 레벨을 지정하도록 요구합니다. 이는 모델이 실제 MATH 데이터셋 문제와 유사한 문제를 생성하고 해결할 수 있는지 평가하기 위한 것입니다. 즉, MATH 데이터셋과 유사한 문제를 생성하는 방법을 보여주는 예시 프롬프트입니다.
read the caption
Figure 6: A prompt for generating 16 synthetic examples analogous to those in MATH.

🔼 그림 7은 논문의 SVAMP 데이터셋과 유사한 난이도, 요구되는 기술, 스타일을 가진 16개의 합성 수학 문제 생성을 위한 프롬프트를 보여줍니다. 프롬프트는 각 생성된 문제에 대한 단계별 솔루션과 최종 답변을 생성하고, ‘Answer’, ‘Question’, ‘Equation’, ‘Body’, ‘Type’, ‘ID’, ‘idx’ 필드를 포함하는 특정 형식으로 출력하도록 지시합니다. Body는 문제의 본문이고, Question은 실제 질문이며, Type은 덧셈, 뺄셈 등 문제 유형을 나타냅니다. 이 프롬프트는 모델이 SVAMP 데이터셋의 특징을 잘 반영하여 합성 문제를 생성하도록 유도합니다.
read the caption
Figure 7: A prompt for generating 16 synthetic examples analogous to those in SVAMP.

🔼 그림 8은 논문의 실험에서 사용된 ASDiv 데이터셋과 유사한 난이도, 요구되는 기술, 스타일을 가진 합성 수학 문제 16개를 생성하기 위한 프롬프트를 보여줍니다. 프롬프트는 모델이 각 문제에 대한 단계별 풀이와 최종 답변을 생성하고, 문제 유형, 난이도 등의 추가 정보를 포함한 특정 형식으로 출력하도록 지시합니다. 이는 ASDiv 데이터셋의 특징을 반영하여 모델의 일반화 성능을 평가하기 위한 것입니다. ASDiv 데이터셋과 유사한 문제들을 생성하는 과정을 보여줌으로써, 모델이 실제 데이터셋과 비슷한 유형의 문제에 대해 얼마나 잘 일반화하는지 확인하는 데 도움이 됩니다.
read the caption
Figure 8: A prompt for generating 16 synthetic examples analogous to those in ASDiv.

🔼 그림 9는 논문의 실험을 위해 MQA 데이터셋과 유사한 16개의 합성 수학 문제 생성을 위한 프롬프트를 보여줍니다. 프롬프트는 MQA 데이터셋의 문제 유형, 난이도, 그리고 스타일을 반영하여 합성 문제를 생성하도록 지시하고 있습니다. 생성된 합성 문제들은 LE-MCTS 모델의 성능 평가에 사용됩니다. 즉, MQA 데이터셋과 유사한 특징을 가진 새로운 데이터를 생성하여 모델의 일반화 능력을 평가하는 데 활용하기 위함입니다.
read the caption
Figure 9: A prompt for generating 16 synthetic examples analogous to those in MQA.

🔼 그림 10은 GSM8K 데이터셋에서 각 문제에 대한 leaf 노드의 평균 보상 분포를 나타냅니다. 두 가지 다른 역전파 전략 (표준 및 낙관적)에 따른 분포를 비교하여 보여줍니다. x축은 평균 보상 값을 나타내고, y축은 각 보상 값에 해당하는 leaf 노드의 비율을 나타냅니다. 이를 통해 각 역전파 방법이 leaf 노드의 보상 분포에 미치는 영향을 시각적으로 확인할 수 있습니다. 낙관적 역전파가 더 높은 보상을 가진 leaf 노드의 비율을 높이는 경향을 보여줍니다.
read the caption
Figure 10: The distribution of the average reward for leaf nodes per example in GSM8K.

🔼 그림 11은 MATH 데이터셋에서 각 문제에 대한 리프 노드의 평균 보상 분포를 보여줍니다. 두 가지 다른 백프로퍼게이션 전략(표준 및 낙관적)에 따른 분포를 비교하여 보여줍니다. x축은 평균 보상을 나타내고, y축은 각 보상 값에 해당하는 리프 노드의 비율을 나타냅니다. 이 그림을 통해 낙관적 백프로퍼게이션이 표준 백프로퍼게이션보다 더 높은 평균 보상을 가진 리프 노드를 생성하는 것을 확인할 수 있습니다. 이는 낙관적 백프로퍼게이션 전략이 더 정확한 추론 경로를 찾는 데 효과적임을 시사합니다.
read the caption
Figure 11: The distribution of the average reward for leaf nodes per example in MATH.

🔼 그림 12는 SVAMP 데이터셋에서 각 문제에 대한 리프 노드의 평균 보상 분포를 보여줍니다. 두 가지 다른 역전파 전략(표준 및 낙관적)에 따른 결과를 비교하여 보여줍니다. x축은 평균 보상을, y축은 밀도를 나타내며, 두 전략의 분포 차이를 통해 낙관적 역전파가 보상이 높은 경로를 효과적으로 찾는 데 도움이 됨을 시각적으로 보여줍니다. 즉, 더 나은 성능을 위해서는 보상이 높은 리프 노드를 발견하는 것이 중요하며, 낙관적 역전파 전략을 통해 이를 달성할 수 있습니다.
read the caption
Figure 12: The distribution of the average reward for leaf nodes per example in SVAMP.

🔼 그림 13은 ASDiv 데이터셋의 각 문제에 대한 리프 노드의 평균 보상 분포를 보여줍니다. 두 가지 다른 역전파 전략(표준 및 낙관적)에 따른 분포를 비교하여, 낙관적 역전파가 더 높은 평균 보상을 가진 리프 노드를 발견하는 데 효과적임을 보여줍니다. x축은 평균 보상을, y축은 밀도를 나타냅니다. 각 곡선은 특정 역전파 전략 하에서 리프 노드의 평균 보상 분포를 나타내며, 수직선은 각 분포의 평균을 나타냅니다.
read the caption
Figure 13: The distribution of the average reward for leaf nodes per example in ASDiv.

🔼 그림 14는 MQA 데이터셋에서 각 문제에 대한 리프 노드의 평균 보상 분포를 보여줍니다. 두 가지 다른 백프로퍼게이션 전략(표준 및 낙관적)에 따른 분포를 비교하여 보여주는 KDE 플롯이 포함되어 있습니다. 낙관적 백프로퍼게이션이 평균 보상을 높이는 경향이 있음을 보여줍니다. 이는 낙관적 백프로퍼게이션이 더 높은 보상을 가진 경로를 우선적으로 탐색하기 때문입니다.
read the caption
Figure 14: The distribution of the average reward for leaf nodes per example in MQA.

🔼 그림 15는 GSM8K 데이터셋에 대한 LE-MCTS 알고리즘의 평균 리프 노드 깊이 분포를 보여줍니다. x축은 리프 노드의 깊이를, y축은 각 깊이에 해당하는 리프 노드의 비율을 나타냅니다. 세 개의 곡선은 각각 UCT 상수 C 값이 0.5, 1.0, 1.414일 때의 분포를 보여줍니다. 이 그래프는 C 값이 감소함에 따라 리프 노드의 평균 깊이가 증가하는 것을 보여주는데, 이는 C 값이 작을수록 LE-MCTS가 더 깊이 있는 추론 경로를 탐색한다는 것을 의미합니다. 즉, 문제의 복잡성이 높아질수록 더 깊은 탐색이 필요하다는 것을 시각적으로 보여주는 그림입니다.
read the caption
Figure 15: The distribution of the average depth of leaf nodes per example in GSM8K.

🔼 그림 16은 MATH 데이터셋의 각 문제에 대한 leaf 노드의 평균 depth 분포를 보여줍니다. 세 가지 다른 UCT 상수 C 값 (0.5, 1.0, 1.414)에 따른 분포를 비교하여, C 값이 감소함에 따라(탐험을 더 강조함에 따라) leaf 노드의 평균 depth가 증가하는 경향을 보여줍니다. 이는 LE-MCTS가 더 복잡한 문제에 대해 더 깊이 있는 추론 경로를 탐색함을 시사합니다. 각 곡선은 커널 밀도 추정(KDE)을 사용하여 생성되었으며, 괄호 안의 숫자는 평균 depth를 나타냅니다. 아래의 히스토그램은 각 depth 값에 대한 빈도를 보여줍니다.
read the caption
Figure 16: The distribution of the average depth of leaf nodes per example in MATH.

🔼 그림 17은 SVAMP 데이터셋에서 각 문제에 대한 리프 노드의 평균 깊이 분포를 보여줍니다. 세 가지 다른 UCT 상수 C 값(0.5, 1.0, 1.414)에 따른 분포를 비교하여 보여주는 그래프입니다. x축은 리프 노드의 평균 깊이를 나타내고, y축은 각 깊이에 해당하는 문제의 비율을 나타냅니다. 이 그래프는 LE-MCTS 알고리즘의 탐색 과정에서 C값에 따라 탐색 깊이가 어떻게 달라지는지 보여줍니다. C 값이 작을수록(탐색이 더 깊어질수록) 평균 깊이가 더 깊어지는 것을 확인할 수 있습니다.
read the caption
Figure 17: The distribution of the average depth of leaf nodes per example in SVAMP.

🔼 그림 18은 ASDiv 데이터셋에서 각 문제에 대한 leaf node의 평균 깊이 분포를 보여줍니다. x축은 leaf node의 평균 깊이를 나타내고, y축은 해당 깊이를 가진 leaf node의 비율을 나타냅니다. 세 개의 곡선은 각각 C 값이 0.5, 1.0, 1.414일 때의 분포를 보여줍니다. C 값은 UCT 알고리즘에서 탐험과 활용 간의 균형을 조절하는 상수입니다. 그림을 통해 C 값에 따른 leaf node의 평균 깊이 변화를 관찰할 수 있으며, 이는 LE-MCTS 알고리즘의 탐색 전략과 성능에 대한 분석에 유용한 정보를 제공합니다.
read the caption
Figure 18: The distribution of the average depth of leaf nodes per example in ASDiv.

🔼 그림 19는 MQA 데이터셋에서 각 문제에 대한 평균 leaf 노드의 깊이 분포를 보여줍니다. 세 개의 다른 UCT 상수 C 값 (0.5, 1.0, 1.414)에 따른 분포를 비교하여 보여주는 히스토그램과 밀도 추정 그래프가 포함되어 있습니다. 이 그래프는 C 값이 감소함에 따라 (탐험을 더 강조함에 따라) leaf 노드의 평균 깊이가 증가함을 보여줍니다. 이는 더 복잡한 추론 문제를 해결하기 위해 더 깊이 있는 추론 경로를 탐색하는 LE-MCTS의 동작을 시각적으로 보여줍니다.
read the caption
Figure 19: The distribution of the average depth of leaf nodes per example in MQA.

More on tables

Category	Base LLM	Method	GSM8K	MATH	SVAMP	ASDiv	MQA	Average
Single LLM	LLaMA-3	Greedy	69.4	12.0	81.2	77.9	21.4	52.4
		SC	69.3	11.8	79.5	76.4	18.9	51.2
		BS	74.2	19.0	81.0	79.8	21.7	55.1
		BoN	74.6	13.4	83.3	77.7	16.6	53.1
	Gemma-2	Greedy	80.9	40.4	69.2	65.6	27.9	56.8
		SC	80.6	39.4	68.1	66.2	27.0	56.3
		BS	81.4	40.8	67.3	67.2	28.6	57.1
		BoN	82.7	41.6	73.2	69.5	29.1	59.2
	DeepSeek-Math	Greedy	46.6	28.6	64.0	70.6	63.8	54.7
		SC	47.1	27.8	60.2	68.0	60.9	52.8
		BS	52.4	29.0	60.1	67.5	66.8	55.2
		BoN	65.9	35.0	73.0	83.5	66.1	64.7
	Rho-Math	Greedy	67.6	29.6	76.6	77.8	55.8	61.5
		SC	66.9	28.2	74.2	77.3	57.5	60.8
		BS	69.9	28.8	77.7	81.1	58.2	63.1
		BoN	74.8	34.6	79.8	82.2	61.6	66.6
Ensemble	Top-3	BoE	80.0	36.0	84.5	83.8	65.1	69.9
	Top-3	EBS	66.7	41.0	80.8	78.2	64.0	66.1
	All	Blender †	51.9	1.4	71.3	69.0	21.9	43.1
	Top-3	MoA †	42.5	22.2	44.3	47.4	60.4	43.4
	All	EVA †	66.3	26.0	73.8	81.4	54.6	60.4
	Top-3	Ours	84.1 (+1.4)	45.2 (+3.6)	84.0 (-0.5)	84.4 (+0.6)	71.1 (+4.3)	73.8 (+3.9)

🔼 표 2는 다섯 가지 수학 추론 벤치마크의 테스트 세트에 대한 정확도를 측정한 주요 결과를 요약한 것입니다. 오른쪽 열에는 다섯 개 데이터 세트의 성능 평균을 보고합니다. 최고 성능 모델은 굵게 표시하고 두 번째로 우수한 모델은 밑줄로 표시했습니다. †는 실험을 위해 공식 코드를 재사용했음을 나타냅니다. 이 표는 다양한 언어 모델과 방법론의 성능을 비교하여 LE-MCTS의 효과를 보여줍니다.
read the caption
Table 2: Summary of main results. We measure the accuracy on the test set of five math reasoning benchmarks. We also report the average of the performances on five datasets in the rightmost column. We highlight the best model in bold and the second-best model with an underline, respectively. †: we reuse the official code for experiments.

C	GSM8K	MATH	SVAMP	ASDiv	MQA
0.5	81.7	45.2	82.7	84.2	71.1
1.0	83.7	43.6	84.0	84.4	69.0
1.414	84.1	44.4	83.8	84.2	68.6

🔼 표 3은 UCT 상수 C의 영향을 보여줍니다. UCT(Upper Confidence Bound 1 applied to Trees) 알고리즘에서 C는 탐험(exploration)과 활용(exploitation) 간의 균형을 조절하는 상수입니다. C 값이 높으면 알고리즘은 덜 탐험하고 더 많은 보상을 받을 가능성이 높은 노드를 선택합니다. 반대로 C 값이 낮으면 알고리즘은 더 많이 탐험하고 미지의 노드를 더 많이 방문합니다. 이 표는 다양한 C 값에 따른 다섯 가지 수학 추론 벤치마크(GSM8K, MATH, SVAMP, ASDiv, MQA)에서의 정확도를 보여주어 최적의 C 값을 선택하는 데 도움을 줍니다. 다양한 문제의 복잡성에 따라 최적의 C 값이 다르게 나타남을 보여줍니다.
read the caption
Table 3: Effect of the UCT constant C𝐶Citalic_C.

n_{iter}	GSM8K	MATH	SVAMP	ASDiv	MQA
10	79.8	43.8	82.9	82.4	65.7
25	81.0	43.4	82.9	83.5	65.5
50	81.5	44.4	82.7	83.2	68.9
100	82.9	45.2	83.1	83.5	68.2
200	84.1	45.2	84.0	84.4	71.1

🔼 이 표는 논문의 실험 결과 중 MCTS 반복 횟수(niter)가 성능에 미치는 영향을 보여줍니다. 다양한 niter 값(10, 25, 50, 100, 200)에 따른 다섯 가지 수학 추론 벤치마크(GSM8K, MATH, SVAMP, ASDiv, MQA)의 정확도를 비교하여, 최적의 niter 값을 찾는 과정을 보여줍니다. 표에서 알 수 있듯이 niter 값이 증가함에 따라 성능이 향상되지만, 특정 값을 넘어서면 성능 향상이 미미해지는 것을 확인할 수 있습니다.
read the caption
Table 4: Effect of the maximum number of MCTS iterations ni⁢t⁢e⁢rsubscript𝑛𝑖𝑡𝑒𝑟n_{iter}italic_n start_POSTSUBSCRIPT italic_i italic_t italic_e italic_r end_POSTSUBSCRIPT.

Method	ASDiv VRAM (↓)	ASDiv min/ex (↓)	MATH VRAM (↓)	MATH min/ex (↓)
BoE	76.7	17.6	64.8	71.1
EBS	79.2	12.3	71.8	47.2
Blender	70.4	22.2	66.5	59.1
MoA	67.4	84.4	79.8	93.7
EVA	69.9	92.2	70.3	480.2
Ours_{n_iter=25}	76.7	34.6	64.6	129.1
Ours_{n_iter=200}	77.4	112.2	71.0	342.2

🔼 표 5는 제안된 LE-MCTS 방법의 효율성을 기존 앙상블 방법들과 비교 분석한 결과를 보여줍니다. 비교 대상은 최대 VRAM 사용량과 처리량(throughput) 두 가지 지표입니다. 처리량은 예시당 평균 처리 시간(분 단위)으로 측정되며, VRAM 사용량은 추론 과정에서 관찰된 최대 값(GB 단위)으로 측정됩니다. 두 지표 모두 값이 낮을수록 효율성이 높음을 의미합니다. 즉, 더 적은 메모리와 더 빠른 처리 시간으로 동일한 성능을 달성했는지를 보여줍니다.
read the caption
Table 5: Efficiency analysis. We compare the efficiency of our method with existing ensemble approaches based on peak VRAM usage and throughput. Throughput is measured as the average time per example, reported in minutes per example (min/ex). VRAM usage is quantified as the maximum value observed during inference, expressed in gigabytes (GB). For both metrics, lower values indicate higher efficiency.

Model	GSM8K	MATH	SVAMP	ASDiv	MQA
Rho-Math	81.2	56.2	87.5	100	62.5
LLaMA-3	81.2	31.2	87.5	100	25
Gemma-2	87.5	81.2	37.5	100	37.5
DeepSeek-Math	56.2	43.8	87.5	87.5	87.5

🔼 표 6은 논문에서 제시된 다섯 가지 수학 추론 데이터셋(GSM8K, MATH, SVAMP, ASDiv, MQA) 각각에 대해 16개의 합성 예시를 사용하여 언어 모델 성능을 평가한 결과를 보여줍니다. 각 데이터셋의 특징을 반영하여 생성된 합성 예시는 실제 데이터셋의 문제 유형 및 난이도를 반영하도록 설계되었습니다. 표는 각 모델(Rho-Math, LLaMA-3, Gemma-2, DeepSeek-Math)이 각 데이터셋의 합성 예시에 대해 달성한 정확도를 보여줍니다. 또한 앙상블 기법(Top-3, All, BoE, EBS, Blender, MoA, LE-MCTS)들을 적용한 결과도 함께 제시하여 단일 모델과 앙상블 기법의 성능 차이를 비교 분석하고 있습니다. 이를 통해 다양한 모델과 앙상블 전략의 효과를 수학적 추론 문제 해결 능력 측면에서 평가할 수 있습니다.
read the caption
Table 6: Performance on 16 synthetic examples.

Method	Base Model	GSM8K	MATH	SVAMP	ASDiv	MQA
EBS	Top-3	66.7	41.0	80.8	78.2	64.0
	All	54.6	41.8	78.8	78.2	61.3
BoE	Top-3	80.0	36.0	84.5	83.8	65.1
	All	79.4	29.0	85.1	83.8	51.2
MoA	Top-3	42.5	22.2	44.3	47.4	60.4
	All	43.3	10.4	48.4	47.4	61.2
Blender	Top-3	49.9	1.4	69.0	69.0	21.9
	All	51.9	1.4	71.3	69.0	21.9
LE-MCTS	Top-3	84.1	45.2	84.0	84.4	71.1
	All	84.2	40.0	79.7	84.4	67.5

🔼 표 7은 두 가지 기본 모델 구성(Top-3 및 All)을 사용한 언어 모델 앙상블 방법에 대한 전체 실험 결과를 보여줍니다. Top-3 구성은 각 데이터셋에 대해 성능이 가장 좋은 세 가지 언어 모델을 사용하고, All 구성은 모든 네 가지 기본 언어 모델을 사용합니다. 이 표는 다양한 앙상블 방법들의 GSM8K, MATH, SVAMP, ASDiv 및 MQA 데이터셋에 대한 정확도를 비교하여 각 방법의 강점과 약점을 보여줍니다. 특히, 다양한 데이터셋에 대한 평균 정확도를 통해 각 방법의 전반적인 성능을 비교할 수 있습니다.
read the caption
Table 7: Full experimental results of language model ensemble approaches with two base model configurations: Top-3 and All.

| Question: Josh decides to try flipping a house. He buys a house for $80,000 and then puts in $50,000 in repairs. This increased the value of the house by 150%. How much profit did he make?| LE-MCTS, Correct answer (reward: 0.932)| LLaMA-3: Let’s break it down step by step!| Gemma-2: 1. Calculate the total investment: Josh spent $80,000 (house) + $50,000 (repairs) = $130,000| Gemma-2: 2. Calculate the increase in value: A 150% increase means the house’s value went up by 1.5 times its original price. So, the increase is $80,000 * 1.5 = $120,000| Gemma-2: 3. Calculate the new value: The house is now worth $80,000 (original) + $120,000 (increase) = $200,000| Rho-Math: 4. Calculate the profit: The profit is the difference between the new value and the total investment. So, $200,000 - $130,000 = $70,000| LLaMA-3: 5. Answer: Josh made a profit of $70,000.| LE-MCTS, Wrong answer (reward: 0.755)| Gemma-2: Here’s how to solve the house flipping problem:| Gemma-2: 1. Calculate the total investment:| Gemma-2: * Josh spent $80,000 on the house + $50,000 on repairs = $130,000 total investment.| LLaMA-3: 2. Calculate the increased value of the house:| Rho-Math: * 150% of $130,000 = 1.5 * 130,000 = 195,000. So the house is now worth 195,000.| Gemma-2: 3. Calculate the profit:| Gemma-2: * The house is now worth $195,000 - $130,000 (investment) = $65,000 profit.| LLaMA-3: The answer is $65,000.| BoE, Wrong answer (reward: highest among candidates)| The original value of the house was $80,000. He put in an additional $50,000 in repairs. This increased the value of the house by 150%. So the new value of the house is $80,000 + 150% of $80,000 + $50,000. This is $80,000 + 1.5 * $80,000 + $50,000. This is $80,000 + $120,000 + $50,000. This is $250,000. So he made a profit of $250,000 - $130,000 = $120,000.

🔼 표 8은 GSM8K 데이터셋의 한 예시 문제에 대해 LE-MCTS와 BoE 모델이 생성한 답변을 보여줍니다. LE-MCTS는 여러가지 언어 모델을 사용하여 단계별 추론을 수행하고, 보상 모델의 안내를 받아 가장 정확한 추론 경로를 찾습니다. 반면 BoE는 여러 모델의 출력 중 가장 높은 보상을 받은 하나의 출력을 선택합니다. 표에서는 LE-MCTS가 정답을 생성한 과정과 중간에 오류를 낸 과정을 보여주고, BoE가 잘못된 답을 생성한 과정을 비교하여 LE-MCTS의 강점을 보여줍니다. 빨간색으로 표시된 부분은 각 모델이 처음으로 오류를 범한 부분입니다.
read the caption
Table 8: An example of the outputs generated by LE-MCTS and BoE to solve a test case in GSM8K. We highlight the first error made by the model in red.

TL;DR#

Key Takeaways#

Why does it matter?#

Visual Insights#

In-depth insights#

Process-Level Ensembling#

MCTS for Reasoning#

Reward Model Impact#

Backprop Strategies#

Future Enhancements#

More visual insights#

Full paper#