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

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

개념

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

구조

CoT vs ToT

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

동작 과정

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

예시: 24 만들기 게임

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

방법 1: $3+3+8+8 = 22$ -- 실패
방법 2: $3 \times 8 = 24$ -- 남은 3, 8 처리 불가 -- 실패
방법 3: $8/(3-8/3) = 24$ -- 성공!

탐색 과정

성능 향상

24 만들기 게임:

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

탐색 전략

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

BFS (너비 우선 탐색)

레벨 단위로 모든 후보를 동일하게 확장한다.
예시: Level 1 = A, B, C -> Level 2 = A1, A2, B1, B2, C1, C2
장점: 해를 놓치기 어렵고, 짧은 경로를 찾기 쉽다.

DFS (깊이 우선 탐색)

한 경로를 끝까지 파고든 뒤, 실패하면 백트래킹한다.
예시: A -> A1 -> A1-1 (실패) 후 A -> A2 -> A2-1 (성공)
장점: 메모리를 덜 쓰고, 유망한 경로를 빠르게 검증한다.

Best-First Search

유망함 점수에 따라 우선순위를 정한다.

후보	점수	탐색 순서
A	0.9	1
B	0.7	2
C	0.3	3

유망함 평가

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

Value 프롬프팅

질문 예시: "이 상태에서 문제를 풀 수 있을 확률은?"
출력 형식: 1~10점으로 각 후보 상태를 평가

Vote 프롬프팅

질문 예시: "다음 중 가장 유망한 상태는?"
후보: A: 상태1, B: 상태2, C: 상태3
다수결 또는 가중 투표로 다음 탐색 경로를 결정

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

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

비용-성능 트레이드오프

기법	API 호출 비용	문제 해결 성능
CoT	낮음	보통
ToT	높음	높음 (복잡 문제에서 강점)

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

한계

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

발전: LATS

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

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

개념

구조