Tree of Thoughts: Deliberate Problem Solving with Large Language Models

---

type: paper
source: https://arxiv.org/abs/2305.10601

---

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

항목	내용
저자	Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, T. Griffiths, Yuan Cao, Karthik Narasimhan
연도	2023
arXiv	2305.10601
분야
인용 수	3700 (Semantic Scholar 기준)

---

1. 배경 및 문제 정의

1.1 대규모 언어 모델의 구조적 추론 한계

대규모 언어 모델(LM, Language Model)은 본질적으로 토큰 단위 좌→우(autoregressive) 디코딩으로 텍스트를 생성한다. 이는 Kahneman이 제시한 이중 처리 이론(Dual Process Theory)의 System 1(빠르고 자동적인 직관적 처리)에 해당하며, 한 번 생성한 토큰 시퀀스를 되돌리거나 분기하여 대안을 탐색하는 능력이 없다. 즉 LM의 기본 추론은 단일 경로를 따라 앞으로만 진행하는 선형적 의사결정이다.

반면 인간의 복잡한 문제 해결은 System 2(느리고 의도적인 숙고적 처리)를 요구한다. 여러 가능성을 머릿속에서 시뮬레이션하고, 막다른 길에 도달하면 되돌아가(backtrack) 다른 경로를 시도하는 과정이 핵심이다. ToT(Tree of Thoughts)는 LM에 이 System 2 사고 방식을 부여하기 위해 설계되었다.

1.2 Newell-Simon의 문제 공간 탐색 이론

ToT의 설계 철학은 Newell과 Simon(1972)의 문제 공간(problem space) 이론에 직접 근거한다. 이 이론에 따르면 문제 해결이란 다음 세 가지로 구성된다:

1. 초기 상태에서 목표 상태까지의 경로를 찾는 것
2. 중간 상태들의 집합이 문제 공간을 구성
3. 탐색 과정에서 휴리스틱(heuristic, 경험적 판단 규칙)을 사용해 유망한 경로를 우선 탐색

ToT는 이 고전적 프레임워크를 LM에 이식한다. 각 중간 상태는 LM이 생성한 일관성 있는 사고 단위(thought)이고, LM 자체가 휴리스틱 평가 함수 역할을 수행하여 각 사고의 유망성을 판단한다.

1.3 기존 추론 방법의 구조적 한계

기존 LM 추론 패러다임은 모두 트리의 특수 사례(제한된 깊이·너비)로 볼 수 있다:

• IO(Input-Output): 깊이 1, 너비 1의 트리. 입력에 대해 단일 출력을 바로 생성하며 탐색이 없다.
• CoT(Chain-of-Thought): 깊이 N, 너비 1의 트리. 중간 사고 단계를 거치지만 단일 경로만 추종하여 막다른 길에서 되돌아갈 수 없다.
• CoT-SC(Self-Consistency): 깊이 N, 너비 K의 트리이나 각 경로가 독립적이다. 경로 간 상호작용이나 중간 평가 없이 최종 답에서만 다수결 투표를 수행한다.
• Self-Refine: 깊이 N의 단일 경로에서 반복 수정한다. 근본적으로 다른 방향을 탐색하지 못한다.

ToT는 이 모든 한계를 극복하여 임의 깊이·너비의 트리 탐색 + 중간 노드 평가 + 백트래킹을 가능하게 한다.

---

2. 핵심 기여 및 방법론

2.1 형식적 프레임워크: 기존 방법의 통합

ToT는 기존 프롬프팅 방법들을 트리 탐색의 특수 사례로 통합하며, 이를 위해 각 방법을 확률적 생성 과정으로 형식화한다.

IO 프롬프팅은 입력 $x$에서 출력 $y$를 단일 스텝으로 직접 생성한다:

$$y \sim p_\theta^{\text{IO}}(y \mid x)$$

여기서 $p_\theta$는 파라미터 $\theta$를 가진 언어 모델의 조건부 분포다. 트리 관점에서 보면 깊이 1, 너비 1인 퇴화된 트리로, 중간 추론 단계가 전혀 없다.

CoT 프롬프팅은 중간 사고 단계 $z_1, z_2, \ldots, z_n$을 순차적으로 생성한 뒤 최종 출력을 도출한다:

$$z_i \sim p_\theta^{\text{CoT}}(z_i \mid x, z_1, \ldots, z_{i-1}), \quad y = f(z_1, \ldots, z_n)$$

각 $z_i$는 "일관성 있는 사고 단위"로, 문제에 따라 한 단어, 한 문장, 수식 한 줄 등 다양한 크기를 가진다. 핵심 제약은 단일 경로라는 점이다. 한번 $z_i$를 생성하면 되돌아갈 수 없고 분기도 불가능하여, 트리 관점에서는 깊이 $n$, 너비 1인 선형 체인이다.

CoT-SC는 CoT를 $k$번 독립 샘플링하여 다수결로 최종 답을 선택한다:

$$y^{(j)} \sim p_\theta^{\text{CoT}}(\cdot \mid x), \quad j = 1, \ldots, k$$
$$\hat{y} = \arg\max_y \sum_{j=1}^{k} \mathbf{1}[y^{(j)} = y]$$

트리 관점에서는 깊이 $n$, 너비 $k$이지만 각 체인이 완전히 독립적이어서 체인 간 상호작용이 없다. CoT-SC의 다수결 메커니즘은 출력 공간이 이산적이고 제한적일 때만 유효하다. 수학 문제처럼 답이 단일 숫자인 경우 다수결이 작동하지만, 창작 글쓰기나 코드 생성처럼 출력 공간이 사실상 무한한 경우 $k$개 체인이 모두 다른 출력을 생성하여 다수결 자체가 무의미해진다.

방법	트리 깊이	트리 너비	탐색/백트래킹	Game of 24 성공률
IO	1	1	불가	7.3%
CoT	n	1	불가	4.0%
CoT-SC (k=100)	n	k	체인 간 독립	9.0%
ToT (b=5)	n	b	BFS/DFS 가능	74%

2.2 ToT 프레임워크의 4가지 설계 축

ToT는 LLM의 문제 해결 과정을 트리 탐색으로 구조화하며, 이를 위해 4가지 설계 질문에 답해야 한다.

축 1: Thought Decomposition (사고 분해)

문제를 어떤 크기의 "사고" 단위로 쪼갤지 결정한다. 사고 단위는 몇 단어(예: Game of 24에서 4 + 9 = 13)부터 한 문단(예: Creative Writing에서 문단 하나)까지 가변적이다. 핵심 원칙은 LLM이 해당 단위를 생성할 만큼 작되, 해결 진행 여부를 평가할 만큼 커야 한다는 것이다. 이 설계는 탐색 트리의 깊이와 분기 수 간 트레이드오프를 결정한다.

축 2: Thought Generator $G(p_\theta, s, k)$

현재 상태 $s$에서 $k$개의 후보 사고를 생성하는 함수다. 두 가지 전략이 존재한다.

• Sample 전략: CoT 프롬프트를 사용하여 i.i.d.(독립 동일 분포)로 $k$개 사고를 독립 샘플링한다. 사고 공간이 풍부하고 다양성이 필요할 때 적합하다. Creative Writing처럼 자유도가 높은 과제에서 사용한다.

• Propose 전략: 하나의 LLM 호출로 순차적으로 $k$개 후보를 한꺼번에 제안한다. 사고 공간이 제한적일 때(예: Game of 24에서 가능한 수식이 한정적) 중복을 피하면서 효율적으로 후보를 생성한다.

Game of 24에서의 Propose 전략 프롬프트 예시:

Input: 2 8 8 14
Possible next steps:
2 + 8 = 10 (left: 8 10 14)
8 / 2 = 4 (left: 4 8 14)
14 + 2 = 16 (left: 8 8 16)
14 - 8 = 6 (left: 2 6 8)
14 / 2 = 7 (left: 7 8 8)

축 3: State Evaluator $V(p_\theta, S)$

상태 집합 $S$의 각 상태가 얼마나 유망한지 평가하는 함수로, 외부 모듈 없이 LLM 자체를 휴리스틱 평가기로 활용한다. 두 가지 전략이 있다.

• Value 전략: 각 상태 $s$를 독립적으로 평가하여 스칼라 값 또는 분류(sure / likely / impossible)를 부여한다. Game of 24에서 남은 숫자로 24를 만들 수 있는지 판단하는 데 사용된다.

Value 프롬프트 예시:

Evaluate if given numbers can reach 24 (sure/likely/impossible)
10 14
10 + 14 = 24
sure

11 12
11 + 12 = 23, 12 - 11 = 1, 11 * 12 = 132, 11 / 12 = 0.91
impossible

• Vote 전략: 여러 상태를 비교하여 "가장 유망한 것에 투표"하는 방식이다. Creative Writing처럼 절대 평가가 어려운 과제에서 상대 비교가 더 효과적이다.

축 4: Search Algorithm (탐색 알고리즘)

트리 구조에서 어떤 순서로 노드를 확장할지 결정한다.

BFS (너비 우선 탐색): 각 단계에서 가장 유망한 $b$개 상태만 유지하며 다음 단계로 확장한다. 트리 깊이가 제한적이고 각 단계의 평가가 중요한 과제에 적합하다.

Algorithm: ToT-BFS
입력: LM p_θ, 프롬프트 x, 깊이 T, 너비 b
S_0 ← {x}
for t = 1 to T:
    S'_t ← {[s, z] : s ∈ S_{t-1}, z ∈ G(p_θ, s, k)}  // 후보 확장
    V_t ← V(p_θ, S'_t)                                  // 각 후보 평가
    S_t ← arg top-b(S'_t, V_t)                          // 상위 b개만 유지
return G(p_θ, S_T, 1)                                    // 최종 답 생성

DFS (깊이 우선 탐색): 유망한 경로를 끝까지 탐색하되, 평가값이 임계치 $v_{th}$ 이하이면 가지치기(pruning)하고 부모 노드로 백트래킹한다. 탐색 트리가 깊고 각 노드에서 빠른 판단이 가능한 과제에 적합하다.

Algorithm: ToT-DFS
입력: LM p_θ, 프롬프트 x, 깊이 T, pruning 임계치 v_th
함수 DFS(s, t):
    if t > T: record output G(p_θ, s, 1); return
    for z in G(p_θ, s, k):
        v ← V(p_θ, [s, z])
        if v > v_th:
            DFS([s, z], t+1)
DFS(x, 1)
return 최선 출력

$v_{th}$(pruning threshold)는 impossible로 판정된 경로를 조기에 차단하여 불필요한 탐색을 줄이고 API 호출 비용을 절감하는 역할을 한다.

2.3 ToT의 4가지 구조적 장점

• 일반성(Generality): IO, CoT, CoT-SC, Self-Refine이 모두 특수 사례로 포함되는 범용 프레임워크
• 모듈성(Modularity): 사고 분해, 생성, 평가, 탐색의 4개 모듈이 독립적이어서 과제별로 조합 가능
• 적응성(Adaptability): 과제 특성에 맞게 사고 단위 크기, 생성 전략, 평가 전략, 탐색 알고리즘을 자유롭게 선택
• 편의성(Convenience): 별도 학습(fine-tuning) 없이 사전훈련된 LLM만으로 구현 가능하며, 프롬프트 설계만으로 동작

---

3. 실험 결과 및 분석

3.1 Game of 24

태스크 개요. 주어진 4개의 숫자에 사칙연산(+, −, ×, ÷)을 적용하여 결과가 24가 되는 수식을 만드는 수학 퍼즐이다. 4nums.com에서 수집한 1,362개 문제 중 901~1,000번(총 100개, 난이도 상위 구간)을 사용했다.

사고 분해 설계. 각 사고 단위는 하나의 중간 수식이다. 4개 숫자에서 출발해 3단계를 거치면 최종 하나의 숫자가 남고, 그것이 24이면 성공이다. 예시:

• 1단계: 1 + 2 = 3 → 남은 숫자 3, 3, 4
• 2단계: 3 × 4 = 12 → 남은 숫자 3, 12
• 3단계: 12 + 3 = 15 (실패) → 백트래킹하여 다른 경로 탐색

생성·평가·탐색 전략. Propose 전략으로 후보를 생성하고, Value 전략(sure / maybe / impossible 3등급, 동일 상태 3회 샘플링 다수결)으로 평가하며, BFS(너비 $b=5$)로 탐색한다.

핵심 결과.

방법	성공률
IO	7.3%
CoT	4.0%
CoT-SC (k=100)	9.0%
IO + Refine (최대 10회, 정답 피드백 사용)	27%
IO best-of-100 (오라클 기준)	33%
CoT best-of-100 (오라클 기준)	49%
ToT (b=1, greedy)	45%
ToT (b=5)	74%

CoT가 IO보다 오히려 낮은 성공률(4.0% vs 7.3%)을 기록한 원인. CoT의 좌→우 순차 생성 특성 때문이다. 초기 단계에서 잘못된 연산을 선택하면 이후 단계에서 복구가 불가능하며, 실제 CoT 실패 사례의 약 60%가 첫 번째 연산 단계 시점에서 이미 24에 도달 불가능한 상태에 진입한다.

IO + Refine이 외부 정답 정보를 사용하면서도 27%에 그친 이유. 단일 경로 내에서의 반복 수정이 근본적으로 다중 경로 탐색을 대체할 수 없음을 시사한다. 한 경로의 오류를 고치는 것보다 처음부터 다른 경로를 시도하는 것이 효과적인 과제가 존재한다.

스케일 분석. 탐색에 사용된 총 노드 수(LM 호출 횟수에 비례)를 x축, 성공률을 y축으로 놓으면, ToT는 적은 노드 수에서도 가파르게 성공률이 상승한다. CoT는 샘플 수를 100개까지 늘려도(best-of-100 = 49%) ToT($b=5$)의 74%에 도달하지 못하며, ToT($b=5$)의 연산량은 단일 CoT 대비 약 5.5배에 불과하다. 동일 연산 예산 대비 ToT의 효율이 압도적으로 높다.

3.2 Creative Writing

태스크 설계. 4개의 무작위 문장이 각 문단의 마지막 문장으로 고정된 상태에서, 전체적으로 일관성(coherence) 있는 4문단 글을 작성하는 과제다. 총 100개의 입력이 주어지며, 정해진 정답이 없는 개방형(open-ended) 태스크라는 점에서 Game of 24와 근본적으로 다르다.

ToT 구조: 얕은 트리 + Sample-Vote 전략. 깊이 2, 너비 1($b=1$)의 매우 얕은 트리를 사용한다. 사고 단위는 짧은 작문 계획(writing plan)이다.

1. Plan 생성(Sample): 동일 프롬프트로 $k=5$회 독립 호출하여 5개의 작문 계획 생성
2. Plan 선택(Vote): 5개 계획을 LLM에 보여주고 투표를 5회 반복하여 최다 득표 계획 선택
3. 글 작성: 선택된 계획 기반으로 실제 4문단 글 생성

Game of 24의 순차적 생성 + 상태 평가(Value)와 달리, 독립 샘플링 + 투표(Vote) 조합을 채택한 이유는, 개방형 태스크에서는 절대 평가보다 후보 간 상대 비교가 더 적합하기 때문이다.

평가 방법.
- GPT-4 자동 평가: 1~10점 척도로 coherence를 평가하며, 각 글에 대해 5회 반복 평가한 평균을 사용한다. 표준편차가 약 0.56으로 안정적이다.
- 인간 블라인드 평가: 두 방법의 출력을 익명으로 제시하고 비교 판정한다.

방법	GPT-4 점수 (1-10)
IO (직접 생성)	6.19
CoT (사고 연쇄)	6.93
ToT (트리 탐색)	7.56
IO + Iterative Refine	7.67
ToT + Iterative Refine	7.91

인간 블라인드 비교	건수
ToT 승	41
CoT 승	21
동등	38

반복 정제(Iterative Refinement)와의 결합. IO는 정제로 +1.48 향상(6.19→7.67)되지만, ToT는 +0.35(7.56→7.91)에 그친다. ToT가 이미 계획 단계에서 품질을 끌어올렸기 때문에 정제의 추가 개선 여지가 줄어드는 수확 체감(diminishing returns) 현상이 나타난다. 반복 정제는 ToT의 제3의 사고 생성 전략으로도 해석 가능하다. (1) i.i.d. 독립 샘플링, (2) sequential 순차 생성에 더해, (3) 이전 출력을 입력으로 받아 개선하는 iterative 방식이 된다.

인간 평가에서 동등 판정 38건. 100건 중 약 4할에서 ToT의 추가 계산이 체감 가능한 품질 차이를 만들지 못했다. 개방형 태스크에서 트리 탐색의 효용에는 구조적 상한이 존재한다.

3.3 Mini Crosswords (5×5 미니 십자말풀이)

태스크 설정. 가로 5개 + 세로 5개 = 총 10개 단서로부터 25개 글자를 채워야 한다. GooBix 퍼즐 사이트에서 수집한 156개 게임 중 20개를 테스트에 사용했다. ToT 실험 중 가장 깊은 탐색을 요구하며, 최대 10개의 중간 단계를 거치고 총 탐색 스텝은 100으로 제한된다.

탐색 전략: DFS + 가지치기 + 백트래킹. Game of 24(BFS)와 달리 DFS를 채택한 이유는, 탐색 깊이가 최대 10단계로 깊고 중간 상태에서 경로 불가능 판정이 가능하기 때문이다.

1. Proposal(후보 생성): 각 단서에 대해 LLM이 5회 독립적으로 후보 단어를 생성한다. 동일 단어의 출현 빈도를 기준으로 우선순위 큐를 구성하여, 신뢰도가 높은 단어부터 시도한다.
2. Value(상태 평가): 현재 격자 상태를 LLM이 평가하여, 나머지 빈 단서들에 유효한 단어를 채울 수 없다고 판정하면 해당 경로를 가지치기한다.
3. 백트래킹: 가지치기로 현재 경로가 차단되면, 가장 최근 선택을 되돌리고 우선순위 큐에서 다음 후보를 꺼내 탐색을 재개한다.

핵심 결과.

방법	Letter %	Word %	Game %
IO	38.7	14	0
CoT	40.6	15.6	1
ToT	78	60	20
ToT (Oracle)	82.4	67.5	35
ToT (-prune)	65.4	41.5	5
ToT (-backtrack)	54.6	20	5

• Letter/Word/Game: 각각 25개 글자 중 정답 비율, 10개 단어 중 정답 비율, 20개 게임 중 완전 정답 비율
• Oracle: 각 단계에서 정답과 가장 가까운 후보를 선택하는 이론적 상한
• -prune / -backtrack: 각각 가지치기 / 백트래킹 제거 ablation

Oracle vs 실제 성능 격차. Oracle(game 성공률 35%) 대비 LLM 휴리스틱(20%)은 약 57% 수준이다. 탐색 알고리즘 자체보다 출력 선택 휴리스틱의 품질이 병목임을 시사하며, 더 나은 평가 함수를 설계하면 추가 성능 향상이 가능하다.

백트래킹 제거 시 극심한 성능 붕괴. 백트래킹을 제거하면 word 성공률이 60%→20%로 급락한다. 이는 greedy BFS($b=1$)와 동일한 상황으로, 십자말풀이처럼 제약 전파(constraint propagation)가 강한 태스크에서 백트래킹이 필수적임을 보여준다.

LLM의 어휘 한계. 실험 중 GPT-4가 AGEND와 같은 고어(archaic word)를 인식하지 못하는 사례가 관찰되었다. LLM의 학습 코퍼스에 희귀 단어가 충분히 포함되지 않으면 근본적으로 풀 수 없는 단서가 존재하며, 외부 사전 검색이나 웹 상호작용으로 LLM의 내부 지식을 보강해야 할 필요성을 보여준다.

3.4 모델 스케일 및 추가 실험

GPT-4 zero-shot ToT (GSM8K / StrategyQA). CoT만으로도 높은 정확도를 달성하는 태스크에서 ToT는 소폭 개선에 그친다.

태스크	IO	CoT	ToT
GSM8K (초등 수학)	51	86	90
StrategyQA (상식 질문)	73	82	83

GSM8K에서 CoT 86 → ToT 90으로 +4 개선에 불과하며, StrategyQA는 +1(82→83)로 거의 무의미하다. 이는 CoT로 충분한 태스크에 ToT를 적용하면 비용 대비 이득이 정당화되지 않는다는 점을 실증한다.

GPT-3.5 실험.

태스크	IO	CoT	ToT
Game of 24	6%	3%	19%
Creative Writing	4.47	5.16	6.62

GPT-3.5에서 Game of 24 CoT(3%)가 IO(6%)보다 낮은 것은, 약한 모델에서 CoT가 잘못된 추론 경로를 장황하게 전개하여 오히려 오류를 누적시키는 현상이다. ToT는 이를 19%까지 끌어올렸지만, GPT-4의 74%에 비하면 여전히 낮다. GPT-3.5는 평가 정확도가 낮아 maybe를 과다 생성하는 경향이 있으며, 이것이 GPT-4 대비 낮은 성공률의 주요 원인이다.

---

4. 한계 및 역효과

4.1 계산 비용 폭증

ToT는 각 노드에서 여러 사고를 생성하고 각각을 평가해야 하므로, LM API 호출 횟수가 IO/CoT 대비 수십~수백 배 증가한다. Game of 24에서 BFS 너비 5 × 3단계만으로도 단일 문제당 수십 회의 LM 호출이 필요하며, Mini Crosswords에서는 각 스텝마다 5회 proposal + value 평가로 단일 게임당 수백 회에 달한다. 비용과 지연(latency)이 실용적 병목이 된다.

4.2 단순 태스크에서의 과잉 설계

System 1으로 충분히 해결 가능한 문제(단순 산술, 사실 검색 등)에 ToT를 적용하면 불필요한 탐색으로 동일한 성능에 비용만 증가한다. GSM8K(+4), StrategyQA(+1)의 미미한 개선이 이를 실증한다. ToT는 "숙고적(deliberate) 추론이 필요한 태스크"에 한정해야 효과적이다.

4.3 LLM 자체 평가의 불안정성

State Evaluator가 LLM에 의존하므로, LLM이 잘못된 평가를 내리면 유망한 경로가 가지치기되거나 잘못된 경로가 확장된다. Mini Crosswords에서 가지치기를 제거한 ablation(-prune)에서 전체 성능은 word 60%→41.5%로 하락했지만, 가지치기가 있을 때 풀지 못했던 게임 3개를 오히려 풀었다. 이는 LLM 기반 가지치기 판정이 불완전하여 실제로는 유망한 경로를 impossible로 잘못 판정해 차단하는 경우가 있음을 의미한다.

4.4 사고 분해의 과제 종속성

사고 단위 크기를 과제마다 수동으로 설계해야 하며, 잘못된 분해는 성능을 크게 저하시킨다. 너무 작은 단위는 평가가 불가능하고, 너무 큰 단위는 탐색 이점이 사라진다. 범용적으로 사고 단위를 자동 결정하는 메커니즘은 제시되지 않았다.

4.5 모델 스케일 의존성

보고된 핵심 수치는 GPT-4 급 대형 모델 기준이다. GPT-3.5에서는 Game of 24 성공률이 74%→19%로 급감하며, 사고 생성의 다양성과 평가 정확도가 모두 떨어져 트리 탐색 자체가 저품질 노드들 사이를 헤매는 결과를 낳는다. ToT의 효과는 기반 모델의 능력에 크게 의존한다.

4.6 Propose 전략의 고정 편향

하나의 LLM 호출로 $k$개 후보를 순차 생성하면, 앞서 생성된 후보가 뒤의 후보에 영향을 주어(anchoring bias) 진정한 다양성이 확보되지 않을 수 있다. Sample 전략은 이를 피하지만 중복 생성 위험이 있다.

4.7 DFS의 pruning 임계치 민감도

$v_{th}$가 너무 높으면 유망한 경로도 조기 차단되고, 너무 낮으면 불필요한 경로까지 탐색하여 비용이 증가한다. 최적 $v_{th}$는 과제와 LLM 성능에 따라 달라지며, 체계적인 설정 방법이 부재하다.

4.8 GPT-4 자동 평가의 자기 편향

Creative Writing에서 생성과 평가를 동일 모델(GPT-4)이 수행하므로, 자기 출력 스타일에 높은 점수를 부여하는 편향 가능성이 있다. 인간 평가와 방향이 일치하긴 하나, 절대 점수의 신뢰성은 제한적이다.

4.9 형식화와 실제 추론 사이의 간극

$p_\theta$ 표기는 모델이 각 토큰을 조건부 확률에 따라 정확히 샘플링한다고 가정하지만, 실제로는 temperature, top-k, nucleus sampling 등 디코딩 전략에 따라 분포가 크게 변형된다. 형식화가 전제하는 이상적 샘플링과 실제 추론 사이에 간극이 존재한다.

---

5. 관련 연구 및 위치

ToT는 기존 연구를 네 가지 범주로 정리하며 자신의 위치를 명확히 한다.

5.1 Planning / Decision Making

LLM의 계획 수립 능력을 활용하는 연구 흐름이다. RAP(Reasoning via Planning)은 ToT와 동시기에 발표된 연구로, MCTS(Monte Carlo Tree Search, 무작위 시뮬레이션 기반 트리 탐색 알고리즘)를 LLM 추론에 적용한다. 그러나 RAP은 ToT에 비해 평가 태스크가 더 단순하고, 사고 생성·평가·탐색을 모듈로 분리하는 설계가 부족하다. ToT는 BFS/DFS만 실험했으며, MCTS를 사용하는 RAP과의 탐색 효율성 직접 비교는 없다.

5.2 Self-reflection

Reflexion, Self-Refine 등 LLM이 자기 출력을 되돌아보며 개선하는 연구 흐름이다. Self-eval guided decoding은 PAL(Program-Aided Language Models) 기반으로, LLM 출력을 코드 표현으로 변환한 뒤 실행 기반 검증으로 디코딩을 유도한다. 코드로 표현 가능한 태스크(수학, 코딩)에서는 실행 기반 검증이 ToT의 자연어 평가보다 신뢰도가 높을 수 있으나, Creative Writing 같은 자유 형식 텍스트 생성에는 적용할 수 없다. ToT는 자연어 사고 단위를 직접 평가하므로 태스크 유형에 제약이 없지만, 이 범용성은 평가 정확도의 트레이드오프를 수반한다.

5.3 Program-guided LLM

외부 알고리즘이 전체 흐름을 제어하고 LLM을 서브루틴으로 내장하는 접근이다. LLM+P가 대표적으로, 고전적 플래너(classical planner)에 LLM을 결합한다. ToT도 외부 탐색 알고리즘을 사용하지만, 사고 생성과 평가 모두 LLM이 수행한다는 점에서 LLM의 자율성이 더 높다.

5.4 Classical Search

A 알고리즘, NeuroLogic Aesque 디코딩 등 고전적 탐색을 텍스트 생성에 적용한 연구다. ToT는 토큰 수준이 아닌 LLM 수준의 "사고" 단위로 탐색을 끌어올린 것으로 볼 수 있다.

---

6. 미래 방향

• ToT 스타일 fine-tuning: 트리 탐색 과정에서 생성된 반사실적 의사결정(counterfactual decision making — "다른 경로를 선택했다면?") 데이터를 학습에 활용하여, 추론 시 트리 탐색 없이도 더 나은 추론이 가능한 모델을 만드는 것
• 고급 탐색 알고리즘 적용: A*(휴리스틱 기반 최단 경로 탐색), MCTS(시뮬레이션 기반 트리 탐색) 등 현재 BFS/DFS를 넘어서는 탐색 전략
• 복잡한 실세계 태스크: 코딩, 데이터 분석, 로봇 제어 등으로의 확장
• 외부 도구 통합: Mini Crosswords에서 드러난 LLM 내부 지식의 한계를 사전 API, 웹 검색 등 외부 도구 연동으로 보강

---

7. 종합 요약

ToT(Tree of Thoughts)는 LLM의 추론 과정을 트리 탐색으로 구조화하여, 기존 IO/CoT/CoT-SC/Self-Refine 방법들을 모두 특수 사례로 포괄하는 일반 프레임워크다. 사고 분해·생성·평가·탐색의 4개 독립 모듈을 과제별로 조합할 수 있으며, 별도 학습 없이 사전훈련된 LLM만으로 동작한다.

Game of 24에서 CoT 4% → ToT 74%, Mini Crosswords word 성공률 15.6% → 60%로 숙고적 추론이 필요한 태스크에서 대폭 개선을 달성했다. 그러나 CoT로 충분한 태스크(GSM8K, StrategyQA)에서는 이득이 미미하며, API 비용 증가·LLM 평가 불안정성·사고 분해의 수동 설계·모델 스케일 의존성 등 실용적 한계가 존재한다.

핵심 기여는 "LM이 스스로 사고를 생성하고 평가하며 전략적으로 탐색"할 수 있다는 개념적 전환에 있으며, 이후 MCTS 적용(RAP), fine-tuning 기반 내재화, 외부 도구 통합 등의 후속 연구로 이어지고 있다.

태스크	IO	CoT	ToT	개선 배율 (CoT→ToT)
Game of 24 (GPT-4)	7.3%	4.0%	74%	18.5x
Creative Writing (GPT-4)	6.19	6.93	7.56	1.09x
Crosswords Word% (GPT-4)	14%	15.6%	60%	3.85x
Game of 24 (GPT-3.5)	6%	3%	19%	6.3x
GSM8K (GPT-4)	51	86	90	1.05x

---

참고: 핵심 선행 연구

• Chain-of-Thought Prompting (CoT): LLM에게 중간 추론 단계를 명시적으로 생성하도록 유도하는 프롬프팅 기법. ToT에서 깊이 N, 너비 1의 특수 사례에 해당한다.
• Self-Consistency (CoT-SC): CoT를 여러 번 독립 샘플링하여 다수결 투표로 최종 답을 선택하는 기법. 경로 간 상호작용이 없다는 한계를 가진다.
• Self-Refine: LLM이 자기 출력을 반복적으로 평가·수정하는 기법. 단일 경로 내 반복 수정으로, 대안 경로 탐색이 불가능하다.
• RAP (Reasoning via Planning): MCTS를 LLM 추론에 적용한 동시기 연구. ToT와 유사한 방향이나 모듈 분리 설계가 부족하다.
• PAL (Program-Aided Language Models): LLM 출력을 프로그램 코드로 변환하여 실행 기반 검증을 수행하는 접근. 코드 표현 가능 태스크에 한정된다.
• Newell-Simon 문제 공간 이론 (1972): 문제 해결을 초기 상태에서 목표 상태까지의 경로 탐색으로 정의하는 인지과학 이론. ToT의 설계 철학적 근거다.