Tree of Thought (ToT): 다중 경로 탐색

나뭇가지처럼 펼쳐지는 다중 경로 추론

개념

Tree of Thought(ToT)는 하나의 경로만 따라가는 Chain of Thought와 달리, 여러 가능한 경로를 동시에 탐색하고 가장 유망한 것을 선택하는 기법입니다.

구조

        [문제]
          |
    ┌─────┼─────┐
    |     |     |
 [방법1] [방법2] [방법3]
    |     |     |
 (성공) (실패)   |
                ├────┬────┐
                |    |    |
            [3-1] [3-2] [3-3]
                |
             (성공)

CoT vs ToT

CoT	ToT
단일 경로	다중 경로
실패 시 종료	실패 시 백트래킹
빠름	느림 (탐색 비용)

동작 과정

여러 가능한 다음 단계 생성
각 단계의 "유망함" 평가
유망한 경로 계속 탐색
막힌 경로는 폐기
성공까지 반복

예시: 24 만들기 게임

주어진 숫자: 3, 3, 8, 8로 24를 만들기

방법 1: 3+3+8+8 = 22 → 실패
방법 2: 3×8 = 24 → 남은 3, 8 처리 불가 → 실패
방법 3: 8÷(3-8/3) = 8÷0.33 = 24 → 성공!

탐색 과정

        [3, 3, 8, 8로 24 만들기]
                |
    ┌───────────┼───────────┐
    |           |           |
 [3+3=6]     [3×8=24]    [8÷(3-8/3)]
 [6,8,8]      [3,8]         |
    |           |         (성공!)
 [6+8=14]    처리 불가
 [14,8]
    |
  실패

성능 향상

24 만들기 게임:

CoT: 4%
ToT: 74% (약 18배 향상!)

탐색 전략

ToT는 다양한 탐색 전략을 사용할 수 있습니다:

BFS (너비 우선 탐색)

Level 1: [A] [B] [C]
Level 2: [A1] [A2] [B1] [B2] [C1] [C2]
Level 3: ...

모든 가능성을 균등하게 탐색

DFS (깊이 우선 탐색)

[A] → [A1] → [A1-1] → 실패
      ↓
     [A2] → [A2-1] → 성공!

유망한 경로를 끝까지 탐색

Best-First Search

점수: A(0.9) > B(0.7) > C(0.3)
→ A 먼저 탐색

유망함 점수에 따라 우선순위 결정

유망함 평가

각 노드의 "유망함"을 평가하는 방법:

Value 프롬프팅

"이 상태에서 문제를 풀 수 있을 확률은?"
→ 1-10점 평가

Vote 프롬프팅

"다음 중 가장 유망한 상태는?"
A: 상태1
B: 상태2
C: 상태3
→ 투표로 결정

언제 ToT를 사용해야 하는가?

상황	권장 기법
단순한 추론	CoT
명확한 단계가 있는 문제	CoT
여러 접근법이 가능한 문제	ToT
탐색이 필요한 문제	ToT
실패 시 다른 방법 시도 필요	ToT

비용-성능 트레이드오프

         성능
           ^
           |        ToT ★
           |       /
           |      /
           |     /
           |   CoT ★
           |   /
           |  /
           | /
           +---------------> 비용(API 호출)

ToT는 더 많은 API 호출이 필요하지만, 복잡한 문제에서는 그 비용이 충분히 가치 있습니다.

한계

계산 비용: 여러 경로 탐색으로 비용 증가
평가 정확도: 유망함 평가가 부정확할 수 있음
탐색 공간: 너무 큰 탐색 공간은 비효율적

발전: LATS

ToT의 발전형인 LATS는 다음을 추가합니다:

ReAct (외부 도구 사용)
Reflexion (실패로부터 학습)
Monte Carlo Tree Search (더 효율적인 탐색)

개념

구조