LLM : 논문리뷰 : Boosting Multimodal Reasoning with MCTS-Automated Structured Thinking

Overall Summary:
본 논문은 MCTS 기반의 자동 구조화 사고 패러다임인 AStar 를 제안하여 multimodal reasoning 의 성능과 효율성 간의 균형을 효과적으로 달성했다. AStar 는 제한된 데이터로 고차원 인지 추론 패턴을 자동 도출하고, 모델 내부 능력과 외부 가이드라인을 통합하여 효율적인 추론을 가능하게 한다. 실험적으로 AStar 는 다양한 benchmark 에서 SOTA 성능을 입증했으며, 특히 복잡한 시각적 추론 task 와 OOD generalization 에서 강점을 보였다. AStar 는 multimodal reasoning 연구 분야에 새로운 방향을 제시하고, 더 강력하고 접근성 높은 reasoning 시스템 개발에 기여할 것으로 기대된다.

 

 

쉬운 설명: AStar 는 마치 "자동 운전 내비게이션" 과 같습니다. 기존 MLLM 추론 방식은 "지도 없이 운전하는 것" 과 비슷해서 복잡한 문제에서 길을 잃기 쉽고 비효율적입니다. 반면 AStar 는 MCTS 라는 "자동 탐색 엔진" 을 사용하여, "과거 운전 경험 데이터 (thought cards)" 를 기반으로 최적 경로를 탐색하고, "실시간 교통 정보 (external guidelines)" 를 반영하여 효율적이고 정확하게 목적지 (정답) 에 도달하도록 돕습니다. 특히, AStar 는 "적은 데이터" 만으로도 "뛰어난 내비게이션" 을 만들 수 있다는 점이 핵심입니다.

 

논문 학습 노트: Boosting Multimodal Reasoning with MCTS-Automated Structured Thinking

Purpose of the Paper:

• 기존 multimodal large language models (MLLMs) 은 복잡한 시각적 추론에서 여전히 어려움을 겪고 있음.
• 최근 연구들은 OpenAI o1-like structured thinking 을 MLLMs 에 통합하려 시도했지만, 성능과 효율성 사이의 균형을 맞추기 어려움.
• 기존 방법들은 과도한 데이터와 탐색 공간에 의존하여 낮은 효율성과 데이터 활용률을 보임.
• 본 논문은 이러한 한계를 극복하고자, 제한된 데이터만으로 고차원 인지 추론 패턴을 자동 도출하는 새로운 패러다임인 AStar 를 제안함.

Key Contributions:

• Automated Reasoning Paradigm (AStar):
  • MCTS 기반 자동화 접근 방식을 통해 최적의 추론 패턴을 생성 및 선택하는 새로운 패러다임 제시.
  • Novelty: 제한된 데이터 (500 samples) 만으로 MCTS 기반 계층적 구조를 활용하여 고차원 인지 추론 패턴을 자동 도출하는 독창적인 방법론.
• Efficient Action-Chain Guided Reasoning:
  • 시각적 추론 과정의 각 단계에 명시적인 가이드라인을 제공하여 구조화된 사고 능력 향상.
  • Novelty: 모델 내부의 추론 능력과 외부 추론 가이드라인을 통합하여 최소한의 tree iteration 으로 효율적인 추론 가능.
• Superior Performance:
  • MathVerse benchmark 에서 7B backbone 모델로 54.0% 정확도를 달성, GPT-40 (50.2%) 능가.
  • Novelty: 오픈 소스 MLLM backbone 만으로 closed-source 모델인 GPT-40 을 능가하는 뛰어난 성능.
• Improved Efficiency:
  • 기존 tree-based method 대비 6.4배 inference overhead 감소, training-based method 대비 520배 적은 데이터 요구.
  • Novelty: 성능과 효율성 사이의 균형을 효과적으로 달성, 특히 제한적인 데이터 환경에서 강점.

Experimental Highlights:

• Datasets: ChartQA, MMStar, MathVista, MathVerse, Math-Vision, GAOKAO-MM (총 6개 datasets, 3가지 reasoning tasks).
• Baselines: Qwen2-VL, InternVL2 series, URSA, Math-LLaVA, GPT-4V, GPT-40, AR-MCTS, Mulberry 등 다양한 open-source 및 closed-source MLLMs, tree-based methods.
• Metrics: Accuracy (MathVerse, MathVision, GAOKAO-MM), ALL, ARI, LOG, STA, VQA (MathVista), MMStar/ChartQA accuracy (general VQA).
• Key Results:
  • MathVerse benchmark 에서 AStar (Qwen2.5-7B) 는 54.0% 정확도로 GPT-40 (50.2%) 를 능가.
  • MathVerse benchmark 에서 AStar (Qwen2-VL-7B) 는 InternVL2-8B 대비 18.1% 높은 정확도 달성.
  • MathVision benchmark 에서 AStar (7B) 는 GPT-40 과 comparable 한 성능 달성 (AStar 32.3%, GPT-40 30.4% average accuracy).
  • GAOKAO-MM benchmark 에서 AStar framework 적용 시 모든 모델 (Qwen2-VL-2B, Qwen2-VL-7B, GPT-40) 의 성능 향상 확인, 특히 OOD generalization 성능 향상 (Geography task 에서 Qwen2-VL-7B accuracy 26.9% -> 51.6%).
  • Ablation study 를 통해 AStar 의 각 component (thought card construction, card match, verification) 의 필요성 입증.

Limitations and Future Work:

• 논문에서 명시적인 한계점을 강조하지는 않았지만, 다음과 같은 Future Work 를 통해 잠재적 한계점을 보완하고 발전시킬 수 있음을 시사:
  • High-quality verification model 과의 통합을 통해 성능 향상 가능성 제시 (현재는 off-the-shelf ORM model 사용).
  • PCC 기반 card matching 외에 더 발전된 matching strategy 탐구 가능성 언급 (card matching precision 이 MathVerse 와 같이 복잡한 task 에서 성능에 더 큰 영향).
  • SFT (Supervised Fine-Tuning) 기법과 AStar framework 의 추가적인 통합 연구를 통해 시스템 성능 극대화 가능성 제시 (SFT 와 AStar 결합 시 synergistic effect 확인).
  • Weak-to-strong generalization 실험을 통해 AStar framework 의 잠재력 입증, 더 scalable 하고 sophisticated 한 전략 개발 가능성 암시.

 

 

Abstract

Multimodal large language models (MLLMs)는 인상적인 능력을 보여주지만, 복잡한 visual reasoning에서는 여전히 어려움을 겪고 있습니다. 최근 연구들은 explicit search structures 또는 teacher-guided distillation을 통해 OpenAI o1과 유사한 structured thinking을 통합하여 MLLMs의 reasoning을 향상시키려 노력하지만, 성능과 효율성 사이의 균형을 맞추는 데 어려움을 겪는 경우가 많습니다. 중요한 한계는 방대한 데이터와 search spaces에 대한 의존도가 높아 low-efficiency implicit insight extraction 및 데이터 활용을 초래한다는 것입니다.

이를 해결하기 위해, 우리는 Monte Carlo Tree Search (MCTS)를 통한 multimodal reasoning을 위한 Automated Structured thinking paradigm인 AStar를 제안합니다. AStar는 MCTS-powered hierarchical structures를 사용하여 제한된 데이터에서 automatically high-level cognitive reasoning patterns을 도출합니다. 이러한 explicit patterns을 기반으로, 우리는 models의 internal reasoning capabilities와 external reasoning guidelines을 seamlessly 통합하는 unified reasoning framework를 설계하여, minimal tree iterations로 efficient inference를 가능하게 합니다. 이 novel paradigm은 성능과 효율성 사이의 매력적인 균형을 이룹니다.

Extensive experiments는 AStar의 효과를 입증하며, MathVerse benchmark에서 7B backbone으로 superior accuracy (54.0%)를 달성하여 GPT-4o (50.2%)를 능가하면서도 상당한 데이터 및 computational efficiency를 유지합니다.

 

 

 

 

Figure 1. Performance comparison on the MathVerse benchmark.

Our AStar framework는 most open-sourced MLLMs 및 closed-source ones에 대해 competitive results를 달성하여, outstanding structured thinking and reasoning abilities를 보여줍니다.

 

 

 

1. Introduction

Multimodal Large Language Models (MLLMs)는 autonomous driving, visual question answering과 같은 diverse tasks and domains에서 impressive capabilities를 demonstrated 했습니다. visual content를 포함하는 mathematical tasks에서 complex multimodal reasoning에 대한 MLLMs의 숙련도는 strong artificial intelligence를 향한 fundamental cognitive abilities를 evaluating 하기 위한 critical benchmark로 부상했습니다. Multi-step visual reasoning을 마스터하려면 multimodal information의 integration과 함께 complex rules 및 sophisticated problem-solving strategies에 대한 rigorous adherence가 필요하며, 이는 existing MLLMs에 significant challenges를 제기합니다.

OpenAI o1 및 QVQ와 같은 System 2 slow-thinking reasoning systems의 recent advances에서 영감을 받아, structured thinking을 MLLMs에 incorporating 하는 데 대한 관심이 growing 하고 있습니다. 이 방향은 high-quality long-chain reasoning data의 scarcity로 인해 종종 simple 'direct prediction' modes에 rely 하는 conventional MLLMs의 limitations를 address 하는 것을 aim 합니다. existing literature에 따르면, slow-thinking reasoning systems를 implementing 하기 위한 two primary approaches가 emerged 했습니다: explicit search and teacher supervision-guided training.

The first approach는 solution paths의 exploration을 guide 하기 위해 specialized reward models를 갖춘 explicit search structures (e.g., Monte Carlo tree search, MCTS)를 leverages 합니다. The second approach는 long-form Chain-of-Thought (CoT) instruction data를 통해 structured reasoning patterns을 distilling 하는 데 focuses 하며, typically data synthesis를 위해 GPT-4o와 같은 closed-source models의 supervision이 required 됩니다.

이러한 advances에도 불구하고, current reasoning paradigms은 three critical limitations에 face 합니다 (Figure 2). First, search-based methods는 extensive solution space iterations로 인해 computational inefficiency로 suffer 합니다. Second, teacher-guided training methods는 typically substantial training data (≥100K) and computational resources를 require 하여 implicitly reasoning patterns을 extract 하므로, low efficiency and poor data utilization을 result 합니다. 또한 data synthesis를 위해 GPT-4o와 같은 proprietary models에 heavily depend 하여 major enterprises 외부의 researchers에게는 impractical 합니다. Third, static and predefined reasoning processes는 flexibility를 constrain 하여 MLLMs의 reasoning potential을 underexplored 상태로 leave 합니다.

이러한 challenges를 address 하기 위해, 우리는 MCTS를 통한 multimodAl Reasoning을 위한 Automated Structured Thinking paradigm인 AStar를 propose 합니다. Our approach는 MCTS-powered hierarchical structures를 사용하여 limited data (500 samples)에서 automatically high-level cognitive reasoning patterns을 deriving 하는 novel mechanism을 introduces 합니다 (second limitation을 address 하는 것을 aim). 이러한 explicit patterns을 기반으로, 우리는 internal and external advantageous attributes를 seamlessly integrates 하는 unified reasoning framework를 design 하여, minimal tree iterations로 efficient adaptive inference를 enabling 하므로, first and third limitations를 tackling 합니다. 이 novel reasoning paradigm은 MLLMs의 internal implicit reasoning capabilities와 external explicit reasoning guidelines을 effectively combines 하여, performance and efficiency 사이의 compelling balance를 achieving 합니다.

Specifically, our method는 three steps로 comprises 됩니다: (1) visual reasoning action definition, (2) MCTS-powered thought card construction, and (3) adaptive reasoning and verification. First, 우리는 chain-structured reasoning patterns (inference 동안 reference insights 역할을 하는 "thought cards"라고 term 됨)의 building blocks로서 six atomic reasoning actions을 define 합니다. 이러한 actions은 problem decomposition 및 reasoning step reflection을 including 한 human-like cognitive behaviors를 simulate 합니다. Second, a small seed dataset (500 samples)를 using 하여, 우리는 MCTS를 apply 하여 reference reasoning patterns을 derive 하여 multiple thought cards를 construct 합니다. Finally, in the reasoning stage에서, 우리는 target problem의 cognitive complexity와 most aligned 한 five optimal thought cards를 select 합니다. 이러한 reasoning guidelines을 통해, 우리는 visual reasoning을 perform 하고 self-consistency checks 또는 outcome reward models를 통해 final solutions를 validate 합니다. Experiments는 AStar가 enhanced efficiency와 함께 impressive reasoning performance를 exhibits 하여, GPT-4o와 같은 powerful closed-source models와 comparable 함을 demonstrate 합니다 (Figure 1).

Our main contributions are:

• Automated Reasoning Paradigm: optimal reasoning patterns을 generating and selecting 하기 위한 MCTS-based automated approach를 proposing.
• Efficient Action-Chain Guided Reasoning: visual reasoning process의 each step에 대한 explicit guidance를 providing 하여, structured thinking capabilities를 enhancing.
• Superior Performance: 7B backbone으로 challenging MathVerse benchmark에서 54.0% score를 achieving 하여, GPT-4o (50.2%)를 surpassing.
• Improved Efficiency: recent tree-based methods에 comparable performance를 achieving 하면서 inference overhead를 6.4배 reducing 하고, training-based methods와 matching 하면서 520배 less prior data를 requiring.

 

 

Figure 2. Schematic comparison between AStar and two mainstream structured reasoning methods.

L(·)은 training optimization objective를 denotes 합니다.

(a) Search-based methods는 extensive solution space iterations로 인해 computational inefficiency로 suffer 합니다.

(b) Teacher-guided training은 GPT-4o와 같은 powerful models에서 distilled 된 rationales를 사용하여 models를 optimizes 하지만, substantial data and computational resources를 requires 하므로, low-efficiency pattern extraction and poor data utilization을 resulting 합니다.

(c) Our approach는 MLLMs의 internal implicit reasoning capabilities와 explicitly extracted 된 insights를 effectively combines 하여, performance and efficiency 사이의 compelling balance를 achieving 합니다.

 

 

 

 

 

Figure 3. Flowchart of our proposed method AStar.

This framework는 three main parts로 consists 됩니다: (1) Visual Atomic Reasoning Action Definition; (2) MCTS-Powered Thought Card Construction; (3) Adaptive Reasoning and Verification.

 

 

 

 

Introduction 섹션 정리 노트 (AI 연구자 대상)

• 문제 제기:
  • MLLMs (Multimodal Large Language Models)는 impressive capabilities를 보이지만, visual content가 포함된 mathematical tasks와 같은 complex multimodal reasoning에서 어려움을 겪음.
  • 기존 MLLMs는 high-quality long-chain reasoning data 부족으로 'direct prediction'에 의존하는 경향.
  • Current reasoning paradigms은 (1) search-based methods의 computational inefficiency, (2) teacher-guided training methods의 low efficiency 및 proprietary models 의존성, (3) static reasoning processes로 인한 flexibility 부족이라는 세 가지 limitations에 직면.
• 제안하는 해결책 (AStar):
  • MCTS를 활용한 Automated Structured Thinking paradigm (AStar) 제안.
  • 핵심 아이디어: Limited data (500 samples)에서 MCTS-powered hierarchical structures를 사용해 automatically high-level cognitive reasoning patterns 도출.
  • Explicit patterns 기반으로, internal & external reasoning capabilities를 통합하는 unified reasoning framework 설계 → minimal tree iterations로 efficient adaptive inference 가능.
  • 세 단계 구성: (1) Visual reasoning action definition (6 atomic actions), (2) MCTS-powered thought card construction, (3) Adaptive reasoning and verification.
• 주요 Contributions:
  • Automated reasoning paradigm (MCTS-based).
  • Efficient action-chain guided reasoning.
  • Superior performance (MathVerse benchmark에서 7B backbone으로 54.0% 달성, GPT-4o 능가).
  • Improved efficiency (inference overhead 6.4배 감소, training data 520배 감소).
  • 이 논문만의 차별점: 기존 연구들이 방대한 데이터와 search space에 의존하여 implicit reasoning을 비효율적으로 추출하는 데 반해, AStar는 제한된 데이터에서 MCTS를 통해 explicit reasoning patterns을 automatically 추출하고, 이를 MLLM의 internal capability와 효율적으로 통합하여 성능과 효율성을 모두 잡음.

---

쉬운 설명 :

• 상황: MLLMs는 똑똑해 보이지만, 복잡한 그림과 관련된 수학 문제 같은 건 어려워함. 기존 방법들은 너무 많은 데이터를 필요로 하거나, 계산량이 너무 많거나, 아니면 너무 정해진 방식대로만 생각해서 유연성이 부족함.
• AStar의 등장: AStar는 바둑에서 쓰는 AI 기술(MCTS)을 활용해서, 적은 데이터만 가지고도 "생각하는 패턴"을 스스로 학습함. 마치 사람이 문제 풀 때 머릿속에 떠오르는 여러 가지 아이디어들을 "thought cards" 형태로 만들어 놓고, 문제에 맞게 골라 쓰는 것과 비슷함.
• AStar의 장점: AStar는 이렇게 학습한 "생각하는 패턴"과 MLLM 자체의 능력을 잘 조합해서, 계산은 적게 하면서도 정답은 더 잘 맞힘. 즉, 똑똑하면서도 효율적인 문제 해결 방식을 제시함.
• 결론: 한마디로, AStar는 제한된 정보를 가지고 스스로 생각하는 방법을 터특해서, 더 효율적이고 정확하게 어려운 문제에 접근할 수 있게 해주는 새로운 multimodal reasoning 방법.

 

 

 

 

2. Related Work

Multimodal Reasoning

최근 MLLMs의 advancements는 visual understanding, mathematics, scientific inquiries를 포함한 diverse domains에서 robust capabilities를 demonstrated 했습니다. 이러한 achievements에도 불구하고, complex multimodal reasoning은 visual perception과 high-level cognition 모두에 대한 demands 때문에 여전히 challenging 합니다. OpenAI o1의 impressive performance에 inspired 되어, recent approaches는 pre-defined stages를 사용하여 structured reasoning을 attempt 하여 MLLMs의 CoT capabilities를 enhancing 합니다. 그러나, அவற்ற의 rigid structure는 different tasks에 대한 flexibility를 limits 하여, multimodal reasoning potential을 unleashing 하는 데 있어 adaptive reasoning의 importance를 overlooking 합니다. Our approach는 task-specific reasoning path generation and selection을 enables 하는 hierarchical tree structure를 introducing 하여 이를 address 합니다.

Tree-based Search

Tree structures는 language models에서 significant potential을 demonstrated 했습니다. Recent efforts는 이러한 tree search methods를 MLLMs를 위한 effective reasoning paths를 search 하는 데 applying 하는 것을 explore 합니다. AR-MCTS는 MCTS를 active retrieval과 integrating 하여 multimodal reasoning을 enhances 하지만, extensive iteration requirements and computational overhead는 practical applications를 limit 합니다. Similarly, Mulberry는 tree structures를 leverages 하여 powerful models (GPT-4o 등)로부터 260K long-chain reasoning data를 distill 하지만, substantial computational resources and high-capacity teacher models를 requires 합니다. 이러한 methods는 performance and efficiency 사이의 optimal balance를 achieve 하는 데 struggle 합니다. 이러한 limitations를 address 하기 위해, 우리는 high-level reasoning abstractions을 MCTS에 incorporating 하여 higher efficiency로 competitive performance를 achieving 하는 것을 propose 합니다.

Related Work 섹션 정리 노트 (AI 연구자 대상)

• Multimodal Reasoning:
  • MLLMs가 여러 분야에서 발전했지만, visual perception과 high-level cognition을 모두 요구하는 complex multimodal reasoning은 여전히 과제.
  • OpenAI o1에 영감을 받은 기존 연구들은 pre-defined stages를 사용한 structured reasoning으로 MLLMs의 CoT capabilities 향상 시도.
  • 문제점: 이러한 방식은 rigid structure 때문에 다양한 task에 대한 flexibility가 부족하고, adaptive reasoning의 중요성을 간과.
  • 본 논문의 차별점: hierarchical tree structure를 도입하여 task-specific reasoning path generation & selection 가능하게 함.
• Tree-based Search:
  • Tree structures가 language models에서 가능성을 보임.
  • 최근 연구들은 tree search methods를 MLLMs의 effective reasoning paths 탐색에 적용.
  • AR-MCTS: MCTS와 active retrieval을 통합하여 multimodal reasoning 향상.
    • 문제점: extensive iteration requirements, computational overhead로 인해 practical application 제한.
  • Mulberry: tree structures를 활용하여 GPT-4o와 같은 powerful models에서 260K long-chain reasoning data distill.
    • 문제점: substantial computational resources, high-capacity teacher models 필요.
  • 공통적인 문제점: performance와 efficiency 사이의 optimal balance 달성에 어려움.
  • 본 논문의 차별점: high-level reasoning abstractions을 MCTS에 통합하여 higher efficiency로 competitive performance 달성.

쉬운 설명:

• Multimodal Reasoning
  • 상황: MLLM은 똑똑해지고 있지만, 여전히 복잡한 추론은 어려워함. 기존 연구들은 정해진 틀 안에서 생각하도록 (structured reasoning) 시도.
  • 문제점: 틀이 너무 빡빡해서 다양한 문제에 유연하게 대처하기 어렵고, 상황에 맞게 생각을 바꾸는 (adaptive reasoning) 능력이 부족.
  • AStar: AStar는 트리 구조를 써서 문제마다 다른 "생각의 경로"를 만들고 선택할 수 있게 해줌.
• Tree-based Search:
  • 상황: 트리 구조를 사용해서 AI가 더 잘 생각하게 만드는 연구들이 있음.
  • 예시 1 - AR-MCTS: 바둑처럼 탐색(MCTS)과 정보 검색(retrieval)을 합쳐서 추론 능력을 높임.
  • 문제점: 계산량이 너무 많아서 실제로 쓰기 어려움.
  • 예시 2 - Mulberry: 트리 구조로 엄청난 양(260K)의 데이터를 학습.
    • 문제점: 엄청난 컴퓨터 파워와 선생님 역할(teacher models, GPT-4o)이 필요.
  • 공통 문제점: 성능은 좋은데 효율성이 떨어짐 (계산량이 많거나, 데이터가 많이 필요하거나).
  • AStar: AStar는 "생각의 추상화"라는 아이디어를 MCTS에 더해서, 더 효율적으로 좋은 성능을 낼 수 있도록 함.
• 핵심: AStar는 기존의 MLLMs의 complex reasoning의 문제점을 지적하고 tree-base search의 한계점(계산량, 데이터)을 극복하고자 high-level reasoning abstractions 과 MCTS를 융합한 방법을 제시.

 

 

3. Methodology

Overview of AStar

이 섹션에서는 AStar에 대해 자세히 introduce 합니다. Figure 3과 Algorithm 1에서 shown 된 것처럼, our approach는 three steps로 consists 됩니다:

• Visual Reasoning Action Definition: chain-structured thought cards를 위한 building blocks로서 six human-like reasoning actions을 establish 합니다.
• MCTS-Powered Thought Card Construction: MCTS를 leverage 하여 thought cards를 systematically construct 하며, 이는 inference 동안 reference insights로 serve 합니다.
• Adaptive Reasoning and Verification: problem complexity에 based on optimal reasoning patterns을 dynamically select and execute 하고, solution verification을 합니다.

3.1. Visual Reasoning Action Definition

Human complex reasoning을 understanding 하는 것은 cognitive processes를 modeling 하는 데 crucial 합니다. Existing studies는 two cognitive systems를 distinguish 합니다: System 1 and System 2. "System 1"은 fast, intuitive, yet error-prone thinking을 represents 하는 반면, "System 2"는 superior performance를 가진 slow, deliberative thinking을 involves 합니다. OpenAI o1 및 QVQ와 같은 advanced models의 emergence와 함께, human cognitive processes를 emulate 하는 efficient "System 2" approaches를 developing 하는 것이 significant research attention을 gained 했습니다.

이에 inspired 되어, 우리는 model reasoning과 human cognition 사이의 gap을 bridge 하기 위해 six vision-language reasoning actions을 introduce 합니다: Visual Parsing (VP, a1), System Analysis (SA, a2), One-Step Thought (OST, a3), Chain-of-Thought (CoT, a4), Divide and Conquer (DC, a5), Self-Reflection (SR, a6). Details는 Appendix B.1에 provided 됩니다.

3.2. MCTS-Powered Thought Card Construction

Action definition에 following 하여, 우리는 Sec. 3.3에서 inference를 guide 하기 위한 structured reasoning templates로서 "thought cards"를 introduce 합니다. a small seed dataset을 using 하여, 우리는 먼저 reasoning paths를 derive 하고 (Phase 1), 그 다음 அவற்றை high-level thought cards로 distill 합니다 (Phase 2). 이러한 cards는 inference 동안 prior insights로 serve 하여, efficient problem-adaptive reasoning을 위한 structured guidance를 providing 합니다.

Phase 1: Acquire reasoning paths for seed data

Figure 3에서 shown 된 것처럼, 우리는 MCTS를 employ 하여 solution search process를 iteratively optimize 하고, seed dataset을 위한 high-quality reasoning paths를 generating 합니다. 이 design은 MCTS의 systematic exploration과 MLLMs의 inherent reasoning capabilities를 leverages 합니다. 우리는 each multimodal reasoning problem x (input question and images로 consisting 됨)를 tree search problem으로 formulate 하며, 여기서 x는 root node를 represents 하고 subsequent nodes는 policy MLLM πθ에 의해 generated 된 reasoning steps (actions and corresponding outcomes)를 denote 합니다. 우리는 state St-1을 trajectory x, s1, ..., st-1로 define 하며, 여기서 S0 = x입니다.

The next step은 st ∼ πθ(St-1)로 sampled 됩니다. tree expansion을 guide 하기 위해, 우리는 node s에 대한 reward value로 Q(s)를 define 합니다. Initially, all unexplored nodes는 Q(si) = 0으로 assigned 됩니다. They are updated using a weighted average between the parent’s current value and its child node’s value:

Q(p) ← (1 − α)Q(p) + αQ(s) (1)

여기서 α는 future rewards에 대한 discount factor입니다. terminal nodes의 경우, self-consistency majority voting의 likelihood를 reward value로 adopt 하여, supervision-free generalization을 enabling 합니다.

Specifically, 이 phase는 four MCTS operations으로 comprises 됩니다:

(1) Selection. 이 operation은 expansion을 위한 promising nodes를 identifies 합니다. root node에서 starting 하여, 우리는 leaf node에 reaching 할 때까지 Trees (UCT)에 applied 된 Upper Confidence Bounds를 using 하여 child nodes를 iteratively select 합니다:

UCT(s) = Q(s) + w * sqrt(lnN(p) / N(s)) (2)

여기서 Q(s)는 node s에 대한 reward value, N(s)는 visit count, p는 parent node, w는 exploration weight입니다. The node with the highest UCT value는 exploration and exploitation의 balancing을 하면서 subsequent phases를 위해 selected 됩니다.

(2) Expansion. The selected node s는 πθ에서 n actions을 sampling 하고 corresponding reasoning outcomes를 generating 하여 expanded 됩니다. These n child nodes는 tree에 added 되고 external memory structure에 stored 됩니다.

(3) Simulation. Starting from the selected node, 우리는 terminal state (maximum depth or answer node)에 reaching 할 때까지 nodes를 iteratively sample and expand 합니다.

(4) Backpropagation. simulation completion 시, node information은 simulation path s0, ...sd를 along 하여 updated 됩니다. Visit counts는 incremented 되고 (N(s) ← N(s) + 1), node value Q(s)는 Equation 1을 using 하여 parent node p로 backward propagated 됩니다. These updated values는 subsequent UCT-based node selection을 guide 하기 위해 used 됩니다.

Phase 2: Distill paths into thought cards

MCTS를 executing 한 후, 우리는 each seed dataset question에 대한 tree structure를 obtain 하여, path set P를 constitute 하는 multiple valid reasoning paths를 yielding 합니다. computational benefits and costs 사이의 trade-off를 optimizes 하는 Value of Computation (VOC)의 concept에 inspired 되어, 우리는 candidate solutions에서 optimal reasoning trajectory를 identify 하기 위해 VOC-inspired selection metric을 propose 합니다:

Score(x, px) = k · R(px|x) − (1 − k) · C(px) (3)

여기서 x는 task input, px는 P의 candidate reasoning path, k는 computational benefits against costs를 balances 합니다. 여기서, simplicity를 위해, R(px|x)는 path의 final reward (leaf node의 Q-value로 defined 됨)를 denotes 하는 반면, C(px)는 reasoning cost (sequence의 actions 수로 defined 됨)를 measures 합니다.

그런 다음, seed dataset의 each question에 대해, one-to-one mappings을 가진 Question-path repository D를 build 하기 위해 highest Score(x, px)를 가진 path pbest를 select 합니다. adaptive reasoning strategies를 advocate 하는 meta-reasoning principles에 inspired 되어, 우리는 이러한 question-path pairs를 complex reasoning을 위해 designed 된 cognitive complexity metric인 Problem Condition Complexity (PCC)를 using 하여 abstract thought cards C로 distill 합니다. Each card는 multiple prior problems에서 abstracted 된 high-level reasoning pattern을 represents 하여, next step에서 inference 동안 reasoning insights의 efficient transfer를 enabling 합니다.

3.3. Adaptive Reasoning and Verification

Inference 동안, multimodal test query xt가 given 되면, 우리는 그것의 PCC를 compute 하고 pre-constructed thought cards C에 대해 nearest neighbor matching을 perform 하여 complexity level과 best align 하는 most relevant five cards를 identify 합니다. The selection process는 다음과 같이 formalized 됩니다:

NN5(xt, C) = arg min_{Cxt⊆C,|S|=5} ( Σ_{c∈Cxt} d(xt, c) ) (4)

여기서 NN5(xt, C) ⊆ C는 distance d : R × R → R에 의해 determined 되는 xt에 closest subset입니다. 이러한 reasoning templates를 leveraging 함으로써, our method는 extensive node expansion 없이 tree-structured reasoning의 benefits를 maintains 하여, candidate solutions의 efficient generation을 enabling 합니다.

이러한 candidates 중에서 optimal reasoning trajectory를 identifying 하는 것은 critical challenge을 represents 합니다. visual domain에서 verification models의 scarcity를 Given 하여, 우리는 self-consistency checks and text-domain outcome reward models를 both employ 하여 final solution을 select 합니다.

In summary, our approach는 tree search algorithms의 optimized variant로 viewed 될 수 있습니다. extensive exploration을 require 하는 traditional MCTS methods와 unlike 하게, 우리는 thought cards를 통해 prior insights를 incorporating 하여 computational complexity를 strategically reduce 합니다. Figure 3에서 shown 된 것처럼, 이는 high performance를 maintaining 하면서 promising trajectories를 along 한 efficient tree traversal을 enables 하여, efficient reasoning strategies를 developing 하기 위한 valuable insights를 offering 합니다.

 

 

 

3. Methodology 섹션 정리 노트 (AI 연구자 대상)

• 핵심 구성 요소 (AStar):
  • Visual Reasoning Action Definition: Human-like reasoning을 모방한 6가지 atomic actions 정의 (VP, SA, OST, CoT, DC, SR).
    • 이 논문에서는 이것을 "thought cards"를 구성하기위한 building blocks라고 표현.
  • MCTS-Powered Thought Card Construction: MCTS를 사용해 "thought cards" (structured reasoning templates) 생성.
    • Phase 1: Seed data에 대해 MCTS로 high-quality reasoning paths 생성 (exploration & exploitation).
      • Reward: self-consistency majority voting likelihood (supervision-free).
      • MCTS operations: Selection (UCT 사용), Expansion, Simulation, Backpropagation.
    • Phase 2: Reasoning paths에서 VOC-inspired selection metric으로 optimal path 선정 후, PCC(Problem Condition Complexity, 인지 복잡도)를 이용해 abstract thought cards로 distill.
      • VOC-inspired selection metric: Score(x, px) = k * R(px|x) - (1-k) * C(px)
        • R: path의 final reward (leaf node의 Q-value).
        • C: reasoning cost (sequence의 actions 수).
  • Adaptive Reasoning and Verification: 문제의 PCC에 따라 가장 relevant한 5개의 thought cards를 선택 (nearest neighbor matching)하여 reasoning, self-consistency checks 또는 text-domain outcome reward models로 final solution 검증.
• 이 논문만의 차별점:
  • Traditional MCTS와 달리, thought cards를 통해 prior insights를 통합하여 computational complexity를 줄임 (efficient tree traversal).
  • "Thought cards"라는 개념을 통해 reasoning 과정을 structured templates 형태로 구성, 재사용성 및 효율성 증대.
  • Cognitive complexity metric (PCC)를 사용하여 thought cards와 문제 간의 matching 수행.
  • 핵심: 제한된 데이터를 활용하여 MCTS로 high-quality reasoning path를 만들고, 이를 정제하여 재사용 가능한 "thought card"를 만들고, 문제에 맞는 카드를 골라서 추론에 사용하여 효율성과 성능을 모두 높임.

---

쉬운 설명:

• AStar의 작동 방식:
  1. 기본 동작 정의: 사람이 생각하는 방식을 6가지 기본 동작(Visual Parsing, System Analysis 등)으로 정의함.
  2. 생각 카드 만들기:
     • Phase 1: 바둑 AI (MCTS)처럼, 적은 양의 데이터(seed data)를 가지고 여러 번 시도하면서 좋은 "생각의 경로"를 찾음. 각 경로의 점수는 "정답을 맞힐 확률" 같은 걸로 매김 (사람의 도움이 필요 없음).
     • Phase 2: 찾은 경로들 중에서 제일 좋은 것을 골라서, "생각 카드"라는 요약본을 만듦. 이 카드는 나중에 다른 문제를 풀 때 참고 자료로 쓰임. 제일 좋은 경로를 고르는 기준은 (성능) - (계산 복잡도)를 고려, 가장 높은 점수를 가지는 경로를 선택.
  3. 맞춤형 추론 및 검증: 새로운 문제가 들어오면, 문제의 복잡도를 평가해서 미리 만들어둔 "생각 카드" 중에 제일 비슷한 거 5개를 고름. 이 카드들을 참고해서 답을 추론하고, 최종 답이 맞는지 확인.
• AStar가 특별한 이유:
  • 기존 MCTS는 계산량이 많은데, AStar는 "생각 카드" 덕분에 계산량을 줄이면서도 성능은 유지함.
  • "생각 카드"라는 아이디어로 추론 과정을 재사용 가능한 형태로 만듦.
  • 문제와 "생각 카드"를 매칭할 때 "인지 복잡도"라는 개념을 사용.
• 핵심 비유: AStar는 숙련된 장인이 사용하는 "도구 세트"(thought cards)와 같습니다. 각 도구는 특정 유형의 작업(reasoning)에 최적화되어 있으며, 장인은 문제(problem)를 보고 가장 적합한 도구를 선택하여 효율적이고 정확하게 작업을 수행합니다.

 

 

 

 

 

• Action Definition (6가지 행동 정의): MLLM이 수행할 기본 행동 6가지(VP, SA, OST, CoT, DC, SR)를 정의.
• MCTS-Powered Thought Card Construction (MCTS 기반 Thought Card 생성):
  • 500개 seed data 각각에 대해 MCTS 적용, 다양한 reasoning paths 생성.
  • 각 문제별로 VOC score 기준 best path 선택, "Question-path Repository" 구축.
  • Repository 내 문제들의 PCC (복잡도) 계산.
  • PCC 비슷한 문제들끼리 그룹화, 각 그룹의 path들에서 공통 pattern 추출 → "Thought Cards" 생성.
• Adaptive Reasoning and Verification (적응형 추론 및 검증):
  • 새로운 문제의 PCC 계산.
  • PCC 가장 가까운 k개 Thought Cards 선택.
  • 선택된 Thought Cards 기반으로 MLLM 추론 유도.
  • Self-consistency check 등으로 최종 solution 선택.

 

 

1. Question-path Repository 구축: 500개 각 문제와, 해당 문제에서 가장 점수 높았던 path를 짝지어 저장.
2. Problem Complexity (PCC) 계산: Repository에 있는 500개 문제 각각의 난이도(PCC) 계산.
3. Thought Card 생성: 비슷한 PCC를 가진 문제들을 그룹화, 각 그룹 내 path들의 공통 패턴(action sequence) 추출 → Thought Cards 생성.
4. Adaptive Reasoning: 새 문제의 PCC 계산, 가장 가까운 k개 Thought Cards 선택, 해당 카드들의 action sequence 따라 추론.
5. Verification: 여러 solution candidates 중 self-consistency check 등으로 최종 solution 결정.