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에 도달하는 과정을 보여준다.

성능 향상

ToT 원논문(Yao et al. 2023, arXiv:2305.10601)이 GPT-4로 측정한 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(Language Agent Tree Search)는 다음을 추가한다:

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

정리

ToT는 한 경로만 따라가는 대신 여러 후보 경로를 만들고, 각 노드의 유망함을 평가해 가망 없는 경로는 백트래킹으로 버린다. 24 만들기처럼 탐색이 필요한 문제에서는 CoT보다 성공률이 크게 오르지만, 후보 생성과 평가에 추가 API 호출이 들어 비용도 함께 늘어난다. 따라서 단계가 명확한 단순 추론에는 CoT를, 여러 접근법을 시도하고 실패 시 다른 길을 찾아야 하는 문제에는 ToT를 쓰는 편이 맞다. 탐색 공간이 너무 크거나 유망함 평가가 부정확하면 효율이 떨어지므로, 전략(BFS/DFS/Best-First)과 평가 방식을 문제에 맞게 골라야 한다.

개념

구조