VLM : 논문리뷰 : MCTS-RAG: Enhance Retrieval-Augmented Generation with Monte Carlo Tree Search

MCTS-RAG 학습 노트

용어 설명 (Glossary)

• MCTS (Monte Carlo Tree Search): 의사 결정 문제에서 최적의 선택을 찾기 위해 무작위 샘플링을 사용하여 탐색 트리를 구축하는 휴리스틱 검색 알고리즘. 이 논문에서는 reasoning 경로 탐색에 사용.
• RAG (Retrieval-Augmented Generation): 외부 knowledge source에서 관련 정보를 검색하여 language model의 생성 결과물을 향상시키는 방법.
• rStar: 추가적인 fine-tuning 없이 language model의 reasoning 능력을 향상시키기 위해 제안된 self-consistency framework. MCTS-RAG의 기반이 됨.
• UCT (Upper Confidence Bound for Trees): MCTS에서 exploration(탐험)과 exploitation(활용)의 균형을 맞추는 데 사용되는 공식.
• Action Space (A1-A6): MCTS의 각 decision point에서 모델이 취할 수 있는 이산적인 행동 집합. (A1: Direct Answer, A2: Quick Reasoning, A3: Decompose Question, A4: Retrieval Reasoning, A5: Retrieval Decompose, A6: Summarized Answer). A4, A5가 이 논문의 핵심 추가 액션.
• Retrieval Process (R1-R4): MCTS-RAG 내에서 retrieval이 수행되는 단계. (R1: Query Generation, R2: Query Execution, R3: Knowledge Reflection, R4: Summary Answer).
• Rollout: MCTS에서 특정 노드로부터 시뮬레이션을 실행하여 그 가치를 추정하는 과정. Rollout 횟수가 많을수록 탐색의 깊이와 너비가 증가.
• Datasets:
  • ComplexWebQA (CWQA): Web snippet 기반 multi-step reasoning QA dataset.
  • GPQA (Graduate-Level Google-Proof QA): 전문가 수준의 과학 QA dataset.
  • FoolMeTwice (FMT): Wikipedia 기반의 사실 확인 (fact-checking) benchmark dataset.

Purpose of the Paper

• 기존 연구 한계 극복:
  • 기존 MCTS 기반 reasoning 방법 (e.g., rStar)은 모델 내부 knowledge에 크게 의존하여 knowledge-intensive task에 취약함.
  • 표준 RAG 방법은 reasoning 과정과 retrieval이 독립적으로 수행되어 정보 통합이 suboptimal하며, 특히 small-scale LM에서는 query formulation 및 retrieved content 이해 능력이 부족하여 효과가 제한적임. 또한, 동적으로 retrieval 전략을 조절하지 못함.
• 새로운 접근 방식 제시:
  • MCTS의 structured reasoning/search 능력과 RAG의 adaptive retrieval 메커니즘을 동적으로 통합하는 MCTS-RAG framework 제안.
  • Inference-time compute를 효과적으로 scaling하여 small-scale LM의 reasoning 성능을 극대화하는 것을 목표로 함.

Key Contributions & Novelty

• Dynamic Integration of MCTS and RAG:
  • Contribution: MCTS의 iterative decision-making process 내부에 retrieval action을 통합하여, reasoning 경로 탐색과 external knowledge 획득을 동시에 최적화함.
  • Novelty: 기존 RAG처럼 reasoning과 독립적으로 정보를 검색하는 것이 아니라, MCTS 탐색 중 필요한 시점에 동적으로 정보를 검색하고 이를 reasoning 경로 평가 및 다음 action 결정에 활용하는 새로운 통합 방식.
• New RAG-specific Actions (A4, A5):
  • Contribution: MCTS action space에 Retrieval Reasoning (A4) 과 Retrieval Decompose (A5) 라는 새로운 action을 추가하여, 언제 retrieval을 수행하고 어떻게 활용할지를 모델이 명시적으로 결정하게 함.
  • Novelty: Reasoning tree 내에서 retrieval 자체를 하나의 전략적 선택으로 모델링하여 더욱 유연하고 상황에 맞는 knowledge 획득 가능.
• Synergy for Small-Scale LMs:
  • Contribution: Structured search(MCTS)와 adaptive retrieval(RAG)의 시너지를 통해 small-scale LM (e.g., 7B models)이 부족한 내부 knowledge를 효과적으로 보완하고 복잡한 reasoning task에서 높은 성능을 달성하게 함.
  • Novelty: Inference-time compute scaling을 통해 모델 파라미터 수정 없이 small-scale LM의 성능을 frontier LLM (e.g., GPT-4) 수준으로 끌어올리는 새로운 기준 제시.
• Reduced Hallucinations & Improved Accuracy:
  • Contribution: Structured search와 검증된 external knowledge 통합을 통해 사실 기반의 정확하고 일관성 있는 답변 생성을 유도하고 hallucination을 줄임.
  • Novelty: 명시적인 reasoning step과 retrieval 결과의 reflection 과정을 통해 retrieved information의 오해석 가능성을 낮추고, 보다 정확한 query 생성을 유도.

Experimental Highlights

• Setup:
  • Models: Llama 3.1-8B, Qwen2.5-7B (Small-scale LMs)
  • Datasets: ComplexWebQA (CWQA), GPQA, FoolMeTwice (FMT) (Knowledge-intensive, complex reasoning)
  • Baselines: CoT, Standard RAG, ReAct, Self-Ask, Search-O1, rStar
• Key Results:
  • MCTS-RAG는 모든 dataset과 model에서 기존 baseline들을 압도적으로 능가함.
    • CWQA: Llama +20% 이상, Qwen +6% 이상 향상.
    • GPQA: Llama +15% 이상, Qwen +10% 이상 향상.
    • FMT: Llama +10% 이상, Qwen +4% 이상 향상.
  • 기존 MCTS 방법인 rStar 대비 평균 17% 성능 향상.
  • 기존 RAG 기반 방법들 (Standard RAG, ReAct 등) 대비 평균 14% 성능 향상.
  • Small-scale LM으로 frontier LLM (GPT-40)과 비교 가능한 성능 달성.
• Ablation Study Insights:
  • Retrieval actions (A4, A5)가 성능 향상에 결정적 역할 (특히 GPQA, FMT). A4(Retrieve then Reason)의 영향력이 A5(Decompose then Retrieve)보다 약간 더 큼.
  • **Rollout 횟수 증가 (더 깊은 MCTS 탐색)**는 특히 GPQA에서 성능 향상에 기여, inference-time compute scaling의 효과 입증.

Limitations and Future Work

• Limitations:
  • Amplification Error: 초기 retrieval 오류가 MCTS 탐색 과정에서 증폭되어 최종 결과에 악영향. (Fig 3)
  • Factual Confusion: Retrieved text와 reasoning 과정 간의 semantic mismatch로 인한 혼동 또는 hallucination 발생. (Fig 4)
  • Information Overload: 과도한 retrieval 정보가 오히려 reasoning 경로를 방해하고 원래 질문에서 벗어나게 함. (Fig 5)
  • Search Latency: 깊은 MCTS 탐색 및 반복적인 retrieval은 inference 시간 증가시킴.
  • Action Selection Complexity: 최적의 action (A1-A6) 선택이 query 난이도에 따라 달라지므로 더 adaptive한 메커니즘 필요.
  • Inefficient Expansion: 효과적인 pruning 전략 부재 시 MCTS가 불필요한 reasoning 경로를 탐색하여 비효율 발생.
• Future Work:
  • Search Efficiency Optimization: Adaptive action selection, confidence 기반 retrieval filtering, error-aware pruning 메커니즘 개발을 통한 MCTS 탐색 효율 증대. (Latency, Inefficient Expansion 문제 해결)
  • Reinforcement Learning Integration: Dynamic search policy refinement을 위한 강화학습 도입으로 action 선택 및 탐색 전략 최적화. (Action Selection Complexity 해결)

Overall Summary

MCTS-RAG는 small-scale LM의 knowledge-intensive task 수행 능력을 향상시키기 위해 MCTS의 structured reasoning과 RAG의 adaptive retrieval을 동적으로 통합한 새로운 framework이다. 실험 결과, MCTS-RAG는 기존 MCTS 및 RAG 방법들을 크게 능가하며 small-scale LM으로도 frontier LLM 수준의 성능을 달성함을 보여주었다. 이는 inference-time compute scaling을 통해 small-scale LM의 한계를 극복하는 효과적인 접근법을 제시하며, 향후 복잡한 reasoning task 해결을 위한 연구에 중요한 기여를 할 것으로 기대된다.

쉬운 설명 (Easy Explanation)

MCTS-RAG는 복잡한 질문에 답하기 위해 "생각하는 과정(MCTS)"과 "정보 찾아보기(RAG)"를 아주 긴밀하게 연결한 방법입니다. 마치 똑똑한 탐정이 사건을 해결할 때, 처음부터 모든 단서를 다 모으는 것이 아니라, 현재의 추리(reasoning) 방향에 따라 '지금 어떤 정보가 더 필요할까?'를 판단하고(dynamic retrieval action), 딱 그 정보만 찾아서(adaptive retrieval) 다음 추리를 이어가고(integration) 전체적인 수사 방향(MCTS search)을 계속 수정해나가는 방식과 유사합니다. 이를 통해 정보가 부족한 소형 언어 모델도 마치 많은 것을 아는 대형 모델처럼 정확하게 추론하고 답을 찾을 수 있게 돕습니다.

 

 

 

Abstract

우리는 MCTS-RAG를 소개합니다. 이는 관련 context를 제공하기 위해 retrieval-augmented generation (RAG)을 활용하고 reasoning paths를 개선하기 위해 Monte Carlo Tree Search (MCTS)를 이용하여 knowledge-intensive 작업에서 소형 language models의 reasoning 능력을 향상시키는 새로운 접근 방식입니다.

MCTS-RAG는 반복적인 decision-making 과정을 통해 retrieval과 reasoning을 동적으로 통합합니다. 일반적으로 reasoning과 독립적으로 정보를 retrieve하여 knowledge를 차선으로 통합하는 표준 RAG methods나, 외부 facts 없이 내부 model knowledge에만 의존하는 기존의 MCTS reasoning과 달리, MCTS-RAG는 구조화된 reasoning과 적응형 retrieval을 결합합니다.

이러한 통합된 접근 방식은 decision-making을 향상시키고, hallucinations을 줄이며, 향상된 factual accuracy와 response consistency를 보장합니다. 여러 reasoning 및 knowledge-intensive datasets (즉, ComplexWebQA, GPQA, FoolMeTwice)에 대한 실험 결과는 우리의 방법이 inference-time compute를 효과적으로 확장함으로써 소규모 LMs가 GPT-4o와 같은 최첨단 LLMs에 필적하는 performance를 달성할 수 있게 하여, 소규모 models에서의 reasoning에 대한 새로운 표준을 설정함을 보여줍니다.

 

 

 

 

1 Introduction

MCTS-based reasoning의 최근 발전은 structured decision-making과 logical inference에서 주목할 만한 개선을 보여주었습니다. 예를 들어, rStar framework는 systematic search와 exploration이 reasoning performance를 크게 향상시켜 소규모 LMs(즉, 최대 7B parameters를 가진 models)가 훨씬 더 큰 models과 경쟁할 수 있게 함을 보여주었습니다. 그러나 이러한 접근 방식의 주요 한계는 internal knowledge에 크게 의존한다는 점이며, 이는 knowledge-intensive tasks에서의 효과를 저해합니다.

한편, RAG는 knowledge-intensive tasks를 해결하기 위해 널리 사용되어 왔지만, small-scale LMs에서의 효과는 여전히 제한적입니다. small-scale LMs는 query formulation과 retrieved content comprehension에 어려움을 겪으며, 종종 모호한 queries를 생성하고 핵심 세부 정보를 잘못 해석합니다. 더욱이, 기존 RAG systems는 변화하는 informational 또는 reasoning requirements에 따라 retrieval strategies를 동적으로 조정하지 않아 불필요하거나 반복적인 retrieval steps를 초래합니다. 예를 들어, "1994년에 최우수 작품상을 수상한 영화에 영감을 준 소설은 무엇인가?"와 같은 multi-hop question에 답할 때, 표준 retrieval system은 Forrest Gump(즉, 1994년 최우수 작품상 수상작)에 대한 documents를 retrieve할 수 있지만, Forrest Gump와 Winston Groom이 쓴 소설 사이의 connection을 설정하기 위한 추가적인 reasoning 또는 retrieval steps의 필요성을 인식하지 못할 수 있습니다. 이러한 한계는 small-scale language models이 종종 queries를 반복적으로 refine하고 retrieved information을 일관된 reasoning process로 통합하는 능력이 부족하기 때문에 발생합니다.

앞서 언급한 한계를 해결하기 위해, 우리는 MCTS의 reasoning 및 search capabilities를 adaptive retrieval mechanisms과 통합하는 새로운 framework인 MCTS-RAG를 제안합니다. high level에서 MCTS-RAG는 search-based process를 통해 retrieval과 reasoning을 반복적으로 refining하여 작동합니다. query가 주어지면, 여러 reasoning paths를 탐색하고 주요 decision points에서 retrieval actions를 동적으로 통합합니다. 그런 다음 retrieved knowledge를 사용하여 intermediate states를 평가하고, 유익한 retrieval pathways는 backpropagation을 통해 reinforced됩니다. 이 structured search mechanism은 model이 더 accurate reasoning을 위해 관련 정보를 효율적으로 acquire하고 utilize하도록 보장합니다. 대조적으로, retrieval을 search-based reasoning과 통합함으로써 MCTS-RAG는 관련 knowledge를 systematically explore하고 그 위에서 reason하여 correct answer를 얻을 수 있습니다.

MCTS-RAG는 다음과 같은 key features를 가지고 있습니다: 향상된 reasoning accuracy: 새로운 retrieval actions는 SLMs가 external knowledge를 acquire하고 question answering의 질을 향상시킬 수 있게 합니다. 최적화된 query formulation: refinement process는 각 query가 특정 information needs에 집중하도록 보장하여 retrieval query generation의 effectiveness를 향상시킵니다. 향상된 retrieval quality: retrieved information을 reflecting하고 summarizing하는 것은 semantic discrepancies를 줄이고 core problem과의 alignment를 보장하는 데 도움이 됩니다. MCTS-RAG는 ComplexWebQA (CMQA), GPQA, 및 FoolMeTwice (FMT)를 포함한 다양한 knowledge-intensive benchmarks에서 우수한 performance를 보여줍니다. 구체적으로, Llama 3.1-8B를 사용했을 때 CWQA에서 20% 이상, Qwen2.5-7B를 사용했을 때 6%의 개선을 달성했으며, GPQA에서는 각각 약 15%와 10%의 이득을, FMT에서는 10% 이상(Llama) 및 4%(Qwen)의 이득을 얻었습니다. 이는 hallucinations를 최소화하는 refined multi-step reasoning을 통해 evidence를 효과적으로 retrieving하고 integrating함으로써 Standard RAG, ReAct, Self-Ask, Search-O1, rStar와 같은 다른 baselines를 능가하는 성능입니다.

 

 

MCTS-RAG Introduction 정리노트 (for AI Researchers)

• Problem:
  • 기존 MCTS-based reasoning approaches (e.g., rStar)는 internal knowledge에 의존하여 knowledge-intensive tasks에 취약함.
  • 표준 RAG는 knowledge-intensive tasks에 사용되지만, small-scale LMs에서는 query formulation, content comprehension 능력이 떨어지고, retrieval 전략을 reasoning 과정에 맞춰 동적으로 조정하지 못함 (정보/reasoning 요구사항 변경 시 비효율적 retrieval 발생). 특히 multi-hop question 등 복잡한 reasoning 시 정보 통합에 한계.
• Proposed Solution: MCTS-RAG
  • MCTS의 structured search/reasoning 능력과 RAG의 adaptive retrieval mechanism을 통합한 novel framework.
  • 핵심 아이디어: MCTS search 과정을 통해 reasoning path 탐색과 retrieval action 수행을 동시에, 반복적으로 refinement.
    • Reasoning 중 필요한 시점에 동적으로 retrieval action을 통합.
    • Retrieved knowledge를 MCTS의 intermediate state 평가에 활용.
    • 유익한 retrieval 경로는 backpropagation을 통해 강화 (reinforce).
• Key Contributions & Features:
  • Adaptive Retrieval Integration: Reasoning 과정 중 필요한 정보를 얻기 위한 retrieval을 MCTS search loop 안에 통합하여, 정적인 RAG나 internal knowledge만 사용하는 MCTS의 한계를 극복.
  • Improved Reasoning for Small LMs: External knowledge를 효과적으로 acquire하고 integrate하여 small-scale LMs (SLMs)의 reasoning accuracy 향상.
  • Optimized Query & Retrieval: MCTS의 refinement process를 통해 더 구체적이고 효과적인 retrieval query generation 및 semantic discrepancy 감소.
  • State-of-the-Art Performance Claim (for Small LMs): ComplexWebQA, GPQA, FoolMeTwice 등 knowledge-intensive benchmarks에서 Llama 3.1-8B, Qwen2.5-7B 등 small LMs로 Standard RAG, ReAct, rStar 등 baselines 대비 큰 폭의 성능 향상 (e.g., CWQA +20%/+6%, GPQA +15%/+10%) 및 GPT-4o 수준 performance 달성 가능성 제시. Inference-time compute 확장을 통해 small model의 reasoning 능력 극대화.

---

쉬운 설명 :

이 논문의 Introduction 부분은 다음과 같은 이야기를 하고 있습니다:

기존의 작은 AI 모델들은 복잡한 질문에 답하거나 여러 단계로 생각해야 하는 문제(reasoning)를 잘 풀지 못해요. 특히, AI 모델 자체가 모르는 외부 지식(knowledge)이 필요한 질문에는 더 취약하죠.

이 문제를 해결하기 위해 두 가지 기술이 주로 쓰였어요:

1. MCTS (Monte Carlo Tree Search): 똑똑하게 여러 가능성을 탐색하며 계획을 세우는 방식인데, 주로 AI 모델이 이미 아는 지식 안에서만 생각해요. 외부 세계의 새로운 정보는 잘 활용하지 못하죠.
2. RAG (Retrieval-Augmented Generation): 질문이 들어오면 관련된 정보를 외부 문서에서 찾아와서 답변 생성에 활용하는 방식이에요. 하지만 작은 AI 모델들은 어떤 정보를 찾아야 할지(query formulation) 명확하게 질문하지 못하거나, 찾은 정보를 제대로 이해하고 활용(content comprehension, integration)하는 데 어려움을 겪어요. 또, 문제 풀이 과정에서 필요한 정보가 계속 바뀌는데도 똑같은 방식으로만 정보를 찾는 경향이 있어요.

그래서 이 논문은 MCTS-RAG라는 새로운 방법을 제안합니다. 이건 MCTS의 똑똑한 계획 능력과 RAG의 정보 검색 능력을 합친 거예요.

MCTS-RAG의 작동 방식: 문제를 풀 때, MCTS 방식으로 여러 생각의 경로(reasoning paths)를 탐색해요. 그런데 중간중간 "아, 이 부분은 외부 정보가 필요하겠다!" 싶으면 RAG를 이용해 필요한 정보를 딱 찾아와요(adaptive retrieval). 이렇게 찾아온 정보로 현재 생각이 맞는지 평가하고, 도움이 된 정보 검색 경로는 더 강화(reinforce)해서 다음 탐색에 활용해요. 마치 탐정이 단서를 찾아가며 추리하는 과정에서, 필요할 때마다 도서관에 가서 관련 자료를 찾아보고 다시 추리를 이어가는 것과 비슷해요.

결론적으로 MCTS-RAG는:

• 작은 AI 모델도 외부 지식을 효과적으로 찾고 활용해서, 복잡한 질문에 더 정확하게 답할 수 있게 도와줘요 (Improved reasoning accuracy).
• 필요한 정보를 더 똑똑하게 질문하고(Optimized query formulation), 찾은 정보의 질을 높여요(Enhanced retrieval quality).
• 이를 통해 작은 AI 모델이 마치 GPT-4o 같은 아주 큰 모델처럼 어려운 문제를 풀 수 있게 되는 것을 목표로 해요. 실제로 여러 어려운 테스트(ComplexWebQA, GPQA 등)에서 기존 방법들보다 훨씬 좋은 성능을 보여줬다고 주장합니다.

 

 

 

2 Related Work

Inference-time Scaling. Inference-time scaling은 generation 동안 computational allocation을 최적화하여 model parameters를 수정하지 않고 reasoning을 향상시킵니다. 핵심 접근 방식은 reasoning diversification과 selection을 포함합니다: 여러 candidates를 생성하고 voting이나 verifier-guided ranking을 통해 optimal outputs을 선택하는 것입니다. beam search 및 tree-of-thought frameworks와 같은 Structured search algorithms는 reasoning paths를 명시적으로 model합니다. 최근에는 Monte Carlo Tree Search (MCTS)가 reasoning tasks에서 exploration과 exploitation의 균형을 맞추기 위해 적용되었으며, selection, expansion, simulation, backpropagation을 통해 solutions을 iteratively refining합니다. 더 나아가, value functions이나 predefined reasoning heuristics를 사용하여 MCTS를 LLMs와 통합하는 것은 mathematical reasoning과 code generation에서 efficiency를 향상시켰습니다.

Retrieval-Augmented Generation. RAG system은 external information을 통합하여 knowledge-intensive tasks에서 LLMs를 향상시킵니다. expansion 및 transformation을 포함한 Query optimization techniques는 retrieval quality를 개선합니다. IRCoT 및 ITER-RETGEN과 같은 Iterative retrieval methods는 retrieval과 generation을 refine합니다. WebGPT 및 Toolformer와 같은 LLM-driven retrieval strategies는 large language models를 활용하여 external tools 또는 search engines와 상호 작용함으로써 relevant data 수집 과정을 간소화하여 efficiency에서 주목할 만한 개선을 보여주었습니다. 한편, Self-RAG 및 Auto-RAG와 같은 systems의 self-reflection mechanisms는 iterative introspection을 사용하여 intermediate outputs를 refine함으로써 retrieval relevance를 더욱 향상시킵니다. 이를 해결하기 위해 reasoning-intensive retrieval methods가 등장했습니다. 예를 들어, BRIGHT는 traditional retrieval approaches에 도전하는 complex, reasoning-driven queries를 도입했으며, Rank1은 standard methods가 놓치는 nuanced relationships를 식별하기 위해 고급 inference-time reranking을 활용합니다. 그러나 이러한 advancements에도 불구하고, 이러한 방법들은 종종 linear reasoning approach와 small-scale LMs의 제한된 capabilities 때문에 alternative solutions를 간과합니다.

 

 

Related Work (Section 2) 정리노트 (for AI Researchers)

• Context: 이 섹션은 MCTS-RAG가 기반하거나 개선하려는 기존 연구 분야 두 가지를 요약함: Inference-time Scaling (Reasoning 개선) 및 Retrieval-Augmented Generation (Knowledge 활용 개선).
• 1. Inference-time Scaling (Reasoning Structure Enhancement):
  • Goal: Model retraining 없이 inference 시 computational allocation 최적화를 통해 reasoning 능력 향상.
  • Methods:
    • Reasoning Diversification/Selection: Multiple candidates 생성 후 voting/verifier 기반 ranking.
    • Structured Search: Beam search, Tree-of-Thought (ToT), MCTS 등을 사용해 reasoning paths 명시적 모델링.
    • MCTS Focus: Exploration/exploitation 균형, iterative refinement (selection, expansion, simulation, backpropagation). LLMs와 value function/heuristics 결합으로 효율성 증대 (수학, 코드 생성 등).
  • Limitation (Implied): 주로 internal knowledge 기반의 reasoning 구조 강화에 초점. External knowledge 통합 메커니즘이 부족할 수 있음.
• 2. Retrieval-Augmented Generation (External Knowledge Integration):
  • Goal: External information 통합으로 LLM의 knowledge-intensive task 성능 향상.
  • Methods:
    • Query Optimization: Expansion/transformation으로 retrieval quality 개선.
    • Iterative Retrieval: IRCoT, ITER-RETGEN 등 retrieval/generation 단계 반복적 개선.
    • LLM-Driven Retrieval: WebGPT, Toolformer 등 LLM이 직접 tool/search engine 사용.
    • Self-Reflection: Self-RAG, Auto-RAG 등 iterative introspection으로 retrieval relevance/intermediate output 개선.
    • Reasoning-Intensive Retrieval: BRIGHT (complex queries), Rank1 (inference-time reranking) 등 reasoning 요소를 retrieval에 통합 시도.
  • Limitation (Explicitly Stated): Advancements에도 불구, 종종 linear reasoning approach에 머물며 alternative solutions를 놓침. 특히 small-scale LMs의 capabilities 한계로 어려움.
• Gap Addressed by MCTS-RAG: Inference-time scaling (특히 MCTS)의 structured search 능력과 RAG의 external knowledge 활용 능력을 결합하되, RAG의 한계인 linear reasoning 및 small LM 비효율성 문제를 MCTS의 탐색적, 적응적 특성으로 보완하려는 시도. 즉, structured reasoning 내부에 adaptive retrieval을 통합하여 시너지 창출.

---

쉬운 설명 :

이 "Related Work" 섹션은 MCTS-RAG라는 새로운 기술을 이해하기 위해 관련된 기존 연구들을 소개하는 부분입니다. 크게 두 가지 흐름이 있어요.

1. AI가 생각하는 시간(Inference-time)에 더 똑똑하게 만들기 (Inference-time Scaling): AI 모델을 처음부터 다시 학습시키는 건 시간과 비용이 많이 드니까, 이미 만들어진 모델이 답변을 생성하는 그 순간에 더 좋은 생각을 하도록 돕는 연구들이에요.

• 여러 가지 답변 후보를 만들어서 투표하거나, 검증 AI가 점수를 매겨 제일 좋은 답을 고르는 방식.
• 생각의 과정을 마치 나무가지 뻗듯이 체계적으로 탐색하는 방법 (Beam search, Tree-of-Thought, MCTS 등). 특히 MCTS는 여러 가능성을 효율적으로 탐색하고(exploration) 가장 좋아 보이는 길을 깊게 파고드는(exploitation) 균형을 잘 맞추는 방법으로 주목받고 있어요.
• 하지만, 이런 방법들은 주로 AI가 원래 알고 있던 지식 안에서 똑똑하게 생각하는 데 초점을 맞추는 경향이 있어요.

2. AI가 외부 정보를 더 잘 활용하게 만들기 (Retrieval-Augmented Generation - RAG): AI가 세상의 모든 정보를 다 알 수는 없으니, 질문을 받으면 인터넷 검색 등을 통해 외부 정보를 찾아 답변에 활용하는 RAG 관련 연구들이에요.

• 더 좋은 검색어를 만들거나(Query optimization), 여러 번 검색해서 정보를 보강하는(Iterative retrieval) 기술들.
• AI가 직접 검색 도구를 사용하거나(LLM-driven retrieval), 검색된 정보가 정말 쓸만한지 스스로 평가하고 개선하는(Self-reflection) 기술들.
• 심지어 검색 과정 자체에 복잡한 추론 능력을 요구하는(Reasoning-intensive retrieval) 방법들도 나왔어요.
• 하지만, 이런 RAG 기술들은 정보를 찾아오긴 하지만, 그 정보를 활용해서 여러 단계로 깊게 생각하는 과정(reasoning)이 단순하거나(linear reasoning), 작은 AI 모델에서는 그 능력이 제한적이라 다른 좋은 해결책(alternative solutions)을 놓칠 수 있다는 단점이 지적돼요.

결론적으로 이 섹션은: 기존 연구들이 (1) AI의 생각 구조를 발전시키거나 (2) 외부 정보 활용 능력을 키우는 데 집중했지만, 이 둘을 효과적으로 결합, 특히 작은 AI 모델에서도 잘 작동하도록 만드는 데에는 한계가 있었다고 말합니다. MCTS-RAG는 바로 이 지점에서, MCTS의 체계적인 생각 구조와 RAG의 정보 탐색 능력을 똑똑하게 합쳐서 기존의 한계를 넘어서려는 시도임을 암시합니다.

 

 

 

3 MCTS-RAG

3.1 Preliminaries

rStar는 추가적인 fine-tuning이나 더 강력한 teacher models에 의존하지 않고 language models의 reasoning capabilities를 향상시키기 위해 최근 제안된 self-consistency framework입니다. rStar는 reasoning process를 generation과 discrimination이라는 두 개의 구별되지만 상호 연결된 phase로 나누어 이를 달성합니다. Generation Phase에서, model은 step-by-step inference 및 question decomposition과 같은 인간과 유사한 reasoning actions를 통해 여러 reasoning trajectories를 능동적으로 탐색합니다. 그 후, Discrimination Phase는 이러한 candidate reasoning paths를 평가하고, 가장 logically consistent하고 accurate responses를 식별하기 위해 selecting 및 refining합니다.

그러나 원래 rStar framework는 external knowledge를 동적으로 acquire할 수 없다는 한계가 있어 knowledge-intensive queries에서의 performance가 제한됩니다. rStar의 이러한 inherent limitations를 해결하기 위해, 우리는 rStar의 iterative reasoning capabilities와 RAG를 결합한 integrated reasoning framework를 제안합니다. high level에서 우리의 approach는 rStar의 iterative generative-discriminative structure를 기반으로 구축되며, dynamic external knowledge retrieval을 용이하게 하기 위해 특별히 설계된 추가 operations를 도입합니다. 이를 통해 language model은 관련 external information을 reasoning process에 원활하게 integrate하여 factual accuracy와 decision robustness를 크게 향상시킬 수 있습니다. 다음 subsection들에서는 제안된 MCTS-RAG framework에 대해 자세히 설명합니다.

3.2 Action Space Definition

우리는 각 MCTS decision point에서 일련의 discrete actions를 설계합니다: rStar의 A1–A3와 함께, 두 개의 새로운 RAG-related actions A4와 A5, 그리고 summary action A6을 포함하여, dynamic knowledge acquisition과 향상된 reasoning synergy를 가능하게 하여 개선된 decision-making을 지원합니다.

• A1: Direct Answer: 기존 reasoning 또는 이전에 알려진 context를 기반으로 즉각적인 response를 제공합니다. straightforward queries나 추가 analysis가 불필요할 때 적합합니다.
• A2: Quick Reasoning: 현재 context를 기반으로 신속하고 incremental reasoning steps를 실행합니다. exploratory paths나 preliminary judgments에 이상적이며, search를 효율적으로 안내합니다.
• A3: Decompose Question: complex queries를 더 작고 관리 가능한 sub-questions로 분해하여, 더 명확한 problem-solving pathways와 향상된 reasoning efficiency를 가능하게 합니다. 특히 multi-part 또는 intricate problems에 유용합니다.
• A4: Retrieval Reasoning: 다음 reasoning step을 진행하기 전에 internal 또는 external sources에서 관련 knowledge를 적극적으로 retrieve합니다. supplementary information이 필요하거나 existing context가 불완전한 queries에 중요합니다.
• A5: Retrieval Decompose: decomposition과 retrieval을 모두 integrate하여, 먼저 complex questions를 분해한 다음 개별 sub-problems를 해결하기 위해 관련 knowledge를 acquire합니다. 이 action은 상세한 context-dependent sub-questions를 포함하는 queries에 매우 효과적입니다.
• A6: Summarized Answer: 이전 reasoning 및 retrieved information의 결과를 종합하는 간결하고 structured summary를 generate하여, summarization 또는 multifaceted information의 integration을 요구하는 queries에 특히 유용한 coherent하고 comprehensive responses를 제공합니다.

각 action은 reasoning-retrieval interplay의 특정 측면을 다루도록 설계되어, model이 problem space를 탐색하면서 동적으로 strategy를 adapt할 수 있도록 보장합니다. exploration을 더욱 향상시키기 위해, 우리는 MCTS framework에서 Upper Confidence Bound for Trees (UCT)를 사용합니다. 이는 exploitation과 exploration의 균형을 맞추는 중요한 method입니다. UCT formula는 다음과 같습니다: UCT(s,a)=Qˉ​(s,a)+C⋅N(s,a)lnN(s)​

​ 여기서 Qˉ​(s,a)=N(s,a)Q(s,a)​는 state s에서 action a에 대한 평균 reward이며, Q(s,a)는 cumulative reward이고 N(s,a)는 visit count입니다. N(s)는 state s에 대한 총 방문 횟수입니다. C는 exploitation과 exploration 간의 균형을 제어하는 exploration constant입니다.

MCTS-RAG 내에서, search depth는 search range를 제어하기 위해 root node에서 확장되는 level 수를 제한하는 반면, number of rollouts는 해당 value를 estimate하기 위해 selected node에서 termination 또는 preset limit까지 simulation이 실행되는 횟수를 나타냅니다. controlled depth 내에서 simulations를 실행하고 UCT를 통해 node statistics를 업데이트함으로써, MCTS는 finite computational resources 내에서 효과적으로 exploration과 exploitation의 균형을 맞추고 지속적으로 search strategy를 refine합니다.

3.3 Retrieval Process

우리의 approach는 진화하는 MCTS reasoning environment 내에서 동적으로 information을 retrieve하여, external knowledge의 시기적절하고 관련성 있는 integration을 가능하게 합니다. model은 retrieval이 필요한 시점을 autonomously determines하고, targeted queries를 generates하며, reasoning accuracy를 향상시키기 위해 external knowledge를 critically integrates합니다. retrieval과 reasoning을 엮음으로써, 우리는 information flow를 streamline하고 간결하면서도 informative한 outputs를 produce합니다. 만약 이전에 retrieved data가 현재 reasoning step에 충분히 답한다면(해당 information이 미리 정의된 accuracy thresholds를 만족시키거나 열려 있는 reasoning paths를 해결하는지 확인하여 결정됨), model은 추가 retrieval을 생략하여 redundancy를 피합니다.

• R1: Query Generation: knowledge gap이 detected되면, model은 search queries를 generates합니다.
• R2: Query Execution: External retrieval tools를 사용하여 가장 relevant information을 얻습니다.
• R3: Knowledge Reflection: Retrieved data는 relevance와 consistency에 대해 evaluated되어 reasoning process에 포함될지 결정됩니다.
• R4: Summary Answer: Refined information이 integrated되어 model이 sub-questions에 답하거나 reasoning을 진전시킬 수 있게 합니다.

이러한 interleaved retrieval process는 model의 reasoning이 external data에 대해 지속적으로 updated되고 validated되도록 보장하여, errors를 줄이고 final output의 robustness를 향상시킵니다.

3.4 Determing Final Answer

MCTS exploration이 끝나면, candidate solutions에 대한 voting mechanism과 consistency analysis를 통해 best answer가 selected됩니다. 구체적으로, MCTS에서 얻은 각 reasoning trajectory는 candidate answer cj​를 생성하며, 이는 candidate answer set C={c1​,c2​,…,cM​}을 형성합니다. 이러한 candidate answers는 semantic consistency를 기반으로 unique answers A={a1​,a2​,…,aN​}의 집합으로 grouped됩니다. 각 unique answer ak​에 대한 final score는 ak​ 아래에 grouped된 모든 candidates의 rewards의 합으로 computed되며, 각 candidate cj​의 reward는 해당 reasoning trajectory를 따라 모든 nodes의 rewards의 product입니다. Score(ak​)=∑cj​∈C​Reward(cj​)∑cj​∈C(ak​)​Reward(cj​)​ 여기서 C(ak​)는 ak​로 그룹화된 candidate answers의 집합입니다. (역자 주: 원문에는 분모가 ∑cj​∈C​Reward(cj​) 로 되어 있으나, 문맥상 ak​의 점수 비율을 나타내는 것이라면 ∑c∈C​Reward(c) 또는 ∑ai​∈A​∑cj​∈C(ai​)​Reward(cj​) 가 더 적합할 수 있습니다. 또는 단순히 정규화되지 않은 합 ∑cj​∈C(ak​)​Reward(cj​) 일 수도 있습니다. 원문의 수식을 그대로 번역했습니다.)

그런 다음 best answer는 다음과 같이 결정됩니다: a∗=argak​∈Amax​Score(ak​) 이를 통해 가장 frequent하고 consistent한 reasoning trajectory가 chosen되도록 보장합니다.

 

 

 

 

 

MCTS-RAG (Section 3) 정리노트 (for AI Researchers)

• Foundation & Goal:
  • rStar framework (iterative generation/discrimination phases)를 기반으로 확장.
  • rStar의 한계점인 dynamic external knowledge acquisition 부재를 RAG 통합으로 해결하여 knowledge-intensive queries 성능 향상 목표.
• Core Framework: MCTS + Expanded Action Space
  • Reasoning 과정을 MCTS tree search로 모델링.
  • 각 MCTS decision node에서 선택 가능한 Action Space 확장:
    • 기존 rStar actions (A1: Direct Answer, A2: Quick Reasoning, A3: Decompose Question) 유지.
    • Novel RAG-related actions 추가:
      • A4: Retrieval Reasoning: Reasoning 진행 전 선제적 knowledge retrieval 수행.
      • A5: Retrieval Decompose: Question decomposition 후 각 sub-problem 해결 위한 knowledge retrieval 수행.
    • Novel Summary action 추가:
      • A6: Summarized Answer: 이전 reasoning/retrieval 결과 종합하여 구조화된 요약 생성.
  • Action 선택 및 탐색 균형은 UCT (Upper Confidence Bound for Trees) 알고리즘 사용 (UCT(s,a)=Qˉ​(s,a)+C⋅N(s,a)lnN(s)​​).
  • Search depth 및 rollouts 수로 MCTS 탐색 범위/깊이 제어.
• Dynamic & Interleaved Retrieval Process:
  • Retrieval이 MCTS reasoning loop 내부에 동적으로 통합 (interleaved).
  • Model이 autonomously retrieval 필요성 판단 (knowledge gap 감지).
  • Retrieval steps:
    • R1: Targeted Query Generation.
    • R2: External Query Execution (retrieval tools 사용).
    • R3: Knowledge Reflection (relevance, consistency 평가 후 reasoning 포함 여부 결정).
    • R4: Summary Answer / Integration (정제된 정보 통합하여 sub-question 답변 또는 reasoning 진전).
  • Redundancy Avoidance: 기존 retrieved data가 충분하면 추가 retrieval 생략.
• Final Answer Determination:
  • MCTS exploration 완료 후 다수의 candidate answers (C={c1​,…,cM​}) 생성.
  • Semantic consistency 기반으로 unique answers (A={a1​,…,aN​}) 그룹핑.
  • Voting/Scoring Mechanism: 각 unique answer ak​의 score는 해당 그룹에 속한 candidate cj​들의 trajectory reward (경로상 모든 노드 reward의 곱) 합으로 계산 (정규화된 형태 제시됨: Score(ak​)=∑cj​∈C​Reward(cj​)∑cj​∈C(ak​)​Reward(cj​)​).
  • 가장 높은 score를 가진 unique answer를 최종 답으로 선택 (a∗=argmaxak​∈A​Score(ak​)). 가장 frequent하고 consistent한 reasoning trajectory 결과 선택 유도.

---

쉬운 설명 :

이 섹션에서는 MCTS-RAG라는 기술이 실제로 어떻게 작동하는지 자세히 설명합니다.

1. 기본 아이디어: 기존의 rStar라는 방법(여러 생각 경로를 만들고 평가해서 좋은 답 찾기)을 바탕으로 하지만, rStar가 못했던 외부 정보 검색(RAG) 기능을 추가해서 업그레이드했어요.

2. 핵심 작동 방식 (MCTS + 액션 선택): AI가 문제를 푸는 과정을 마치 나무가 가지를 뻗어나가듯 여러 단계로 탐색(MCTS)해요. 각 단계(decision point)마다 AI는 여러 가지 행동(Action) 중 하나를 선택할 수 있어요. 마치 연장통에서 도구를 고르는 것과 같아요.

• A1: 그냥 바로 답하기
• A2: 간단하게 한 단계 더 생각하기
• A3: 어려운 문제를 작은 문제로 쪼개기
• A4: (새로운 기능!) 다음 생각 전에 필요한 정보 찾아보기 (Retrieval Reasoning)
• A5: (새로운 기능!) 문제를 쪼갠 다음, 각 조각 해결에 필요한 정보 찾아보기 (Retrieval Decompose)
• A6: (새로운 기능!) 지금까지 생각하고 찾아본 내용 요약하기 (Summarized Answer)

AI는 어떤 행동을 선택할지 MCTS 규칙(특히 UCT라는 공식)에 따라 가장 좋아 보이는 경로를 탐색하면서 결정해요. 새로운 시도(exploration)와 유망한 경로 집중(exploitation) 사이에서 균형을 잡죠.

3. 정보 검색 과정 (Retrieval Process): AI가 생각하다가 "어? 이 부분은 내가 모르는 내용인데?" 또는 "외부 정보가 필요해!"라고 판단하면 (A4나 A5 액션 선택 시), 다음과 같은 절차로 정보를 찾아와요.

• R1: 뭘 검색할지 검색어 만들기 (Query Generation)
• R2: 검색 도구(retrieval tool)로 실제 검색 실행 (Query Execution)
• R3: 찾아온 정보가 진짜 관련 있고 믿을 만한지 검토하기 (Knowledge Reflection)
• R4: 검토 후 괜찮은 정보만 생각 과정에 반영해서 다음 단계 진행 (Summary Answer/Integration)

중요한 점은, 이 정보 검색 과정이 생각(reasoning) 중간중간에 필요할 때마다 동적으로 끼어든다는 거예요. 그리고 이미 아는 정보면 굳이 또 검색하지 않아 시간 낭비를 줄여요.

4. 최종 답변 결정: MCTS 방식으로 여러 생각 경로를 탐색하고 나면 여러 개의 답변 후보(cj​)들이 생겨요.

• 의미가 비슷한 답변끼리 그룹핑해서 고유한 답변(ak​) 목록을 만들어요.
• 각 고유 답변 그룹에 대해, 해당 답변을 내놓은 생각 경로들이 얼마나 좋았는지(reward 점수)를 모두 합산해서 최종 점수(Score(ak​))를 매겨요.
• 이 점수가 가장 높은 고유 답변(a∗)을 최종 정답으로 선택해요. 즉, 가장 많은 성공적인 생각 경로가 도달한 일관된 답변을 고르는 방식이에요.