Tree of Thoughts: 심층적 문제 해결을 위한 사고의 나무
Digest: LLM은 토큰 단위의 좌→우 자기회귀 생성에 갇혀 있어, 탐색·전략적 예측·백트래킹이 필요한 과제에서 실패한다. Tree of Thoughts(ToT)는 이 한계를 극복하기 위해 “사고(thought)“를 의미 있는 중간 추론 단위로 정의하고, 이를 트리 구조로 확장하여 BFS/DFS 탐색 알고리즘으로 다수의 추론 경로를 체계적으로 탐험한다. 핵심 통찰은 LLM 자체를 사고 생성기 + 상태 평가기로 동시에 활용하여, 외부 학습 없이 프롬프팅만으로 deliberate reasoning을 구현한다는 점이다. Game of 24에서 CoT(4%) 대비 74% 성공률, Mini Crosswords에서 단어 정확도 15.6% → **60%**를 달성하여 구조화된 탐색의 극적인 효과를 입증했다.
왜 이 연구를 하는가?
핵심 질문
LLM의 추론을 토큰 수준의 단선적 생성에서 벗어나, 트리 구조의 탐색 기반 문제 해결로 확장할 수 있는가?
기존 접근법의 한계
| 한계 | 설명 |
|---|---|
| 좌→우 고정 생성 | 토큰 단위 자기회귀 디코딩은 한 번 생성한 결정을 되돌릴 수 없음 |
| CoT의 단선성 | Chain-of-Thought는 단일 추론 경로만 탐색하여 초기 잘못된 결정에서 회복 불가 |
| 전략적 예측 부재 | 현재 단계의 선택이 미래에 미칠 영향을 고려하지 않음 (lookahead 없음) |
| Self-Consistency의 한계 | 다수 샘플링은 독립적 경로를 생성하지만, 경로 간 정보를 공유하지 않음 |
핵심 통찰
- “사고(thought)“를 탐색 공간의 노드로 정의하면, 고전적 탐색 알고리즘(BFS/DFS)을 LLM 추론에 적용할 수 있다
- LLM은 사고를 생성하는 동시에 각 상태를 평가하는 이중 역할을 수행할 수 있다
- 기존 방법론(IO, CoT, CoT-SC)은 모두 깊이·너비가 제한된 트리의 특수 케이스로 통합된다
방법 (Method)
프레임워크 개요
graph TB subgraph "ToT Framework" A["입력 문제 x"] --> B["사고 분해<br/>(Thought Decomposition)"] B --> C["사고 생성<br/>(Thought Generator)"] C --> D{"사고 평가<br/>(State Evaluator)"} D -->|"유망"| E["탐색 확장<br/>(BFS/DFS)"] D -->|"불가능"| F["가지치기/백트래킹"] E --> C F --> E E --> G["최종 해답 출력"] end subgraph "기존 방법과의 관계" H["IO: 깊이=0"] --> I["CoT: 깊이=n, 너비=1"] I --> J["CoT-SC: 깊이=n, 너비=k (독립)"] J --> K["ToT: 깊이=n, 너비=b (탐색)"] end
핵심 구성요소
1. 사고 분해 (Thought Decomposition): 문제의 성격에 따라 중간 사고 단위의 크기를 결정한다. Game of 24에서는 “하나의 수식”(예: 4 + 9 = 13)이 한 사고이고, Creative Writing에서는 “전체 계획”이 한 사고이며, Crosswords에서는 “한 단어 채우기”가 한 사고이다. 사고의 크기는 LLM이 의미 있는 후보를 생성하면서도 상태 평가가 가능할 정도로 적절해야 한다.
2. 사고 생성 (Thought Generation): 두 가지 전략이 존재한다.
| 전략 | 방식 | 적합한 경우 |
|---|---|---|
| 샘플링 (Sample) | CoT 프롬프트에서 i.i.d.로 k개 사고 추출 | 사고 공간이 풍부하고 다양성이 중요할 때 (Creative Writing) |
| 제안 (Propose) | 순차적으로 사고를 제안하여 중복 회피 | 사고 공간이 제약적일 때 (Game of 24, Crosswords) |
3. 상태 평가 (State Evaluation): LLM 자체를 휴리스틱 평가 함수로 활용한다.
| 방법 | 설명 | 적용 |
|---|---|---|
| 독립 평가 (Value) | 각 상태를 “sure/maybe/impossible”로 분류, 3회 샘플링 평균 | Game of 24 |
| 투표 (Vote) | 여러 상태를 비교하여 가장 유망한 것에 투표, 5회 다수결 | Creative Writing |
4. 탐색 알고리즘:
BFS (너비 우선 탐색): 각 단계에서 b개의 가장 유망한 상태만 유지한다. Game of 24에서 b=5로 설정하면, 각 단계에서 5개 최우수 부분 해답만 다음 단계로 진행시킨다.
DFS (깊이 우선 탐색): 가장 유망한 경로를 끝까지 탐색한 후, 임계값 이하면 백트래킹한다. Crosswords에서 사용하며, 제약 전파(constraint propagation)와 결합하여 탐색 효율을 높인다.
발견 (Findings)
주요 결과
Game of 24 (수학적 추론)
| 방법 | 성공률 |
|---|---|
| IO prompting | 7.3% |
| CoT prompting | 4.0% |
| CoT-SC (k=100) | 9.0% |
| ToT (b=1) | 45% |
| ToT (b=5) | 74% |
- CoT 대비 18.5배 성능 향상 (4% → 74%)
- b=1 → b=5로 너비를 증가시키면 45% → 74%로 개선: 탐색 너비의 직접적 효과 확인
- 비용: ToT 0.13/case (5.7배 비쌈) → 그러나 성공률은 74% vs 33%
Creative Writing (창의적 글쓰기)
| 방법 | GPT-4 점수 (/10) |
|---|---|
| IO | 6.19 |
| CoT | 6.93 |
| ToT | 7.56 |
- 인간 평가: ToT 선호 41% vs CoT 선호 21% (38% 유사)
- GPT-3.5 + ToT(6.62) > GPT-4 + IO(6.19): 약한 모델 + 좋은 탐색 > 강한 모델 + 단순 추론
Mini Crosswords (5×5 퍼즐)
| 메트릭 | IO | CoT | ToT |
|---|---|---|---|
| 글자 정확도 | 38.7% | 40.6% | 78% |
| 단어 정확도 | 14% | 15.6% | 60% |
| 완성 게임 (/20) | 0 | 1 | 20 |
- 가지치기 제거 시: 60% → 41.5% (단어 정확도)
- 백트래킹 제거 시: 60% → 20%: 백트래킹이 핵심 메커니즘임을 입증
추가 분석
- Zero-shot ToT (표준 벤치마크): GSM8K 86→90, StrategyQA 82→83 — 이미 잘 풀리는 과제에서는 개선 폭이 작음
- ToT의 진정한 가치는 기존 방법으로는 해결이 어려운 과제에서 발휘됨
기존 방법론과의 비교
graph LR subgraph "Reasoning Topology 발전" A["IO<br/>입력→출력<br/>(탐색 없음)"] --> B["CoT<br/>입력→사고₁→...→사고ₙ→출력<br/>(단일 체인)"] B --> C["CoT-SC<br/>k개 독립 체인<br/>+ 다수결 투표"] C --> D["ToT<br/>트리 탐색<br/>+ 평가·가지치기·백트래킹"] D --> E["GoT<br/>임의 그래프<br/>+ 합류·루프"] end style A fill:#f9f,stroke:#333 style B fill:#bbf,stroke:#333 style C fill:#bfb,stroke:#333 style D fill:#fbf,stroke:#333 style E fill:#ff9,stroke:#333
| 차원 | IO | CoT | CoT-SC | ToT |
|---|---|---|---|---|
| 추론 경로 수 | 1 | 1 | k (독립) | b^d (탐색) |
| 백트래킹 | ✗ | ✗ | ✗ | ✓ |
| 전략적 가지치기 | ✗ | ✗ | ✗ | ✓ |
| 경로 간 정보 공유 | ✗ | ✗ | ✗ | ✓ (평가) |
| 중간 상태 평가 | ✗ | ✗ | ✗ | ✓ |
한계 및 논의
| 한계 | 설명 |
|---|---|
| 높은 비용 | BFS/DFS 탐색으로 인한 API 호출 수 증가 (Game of 24: 5.7배 비용) |
| 과제 특화 설계 | 사고 분해, 평가 방법, 탐색 알고리즘을 과제별로 수동 설계 필요 |
| 이미 쉬운 과제에는 비효율적 | GSM8K 등에서는 CoT 대비 미미한 개선 |
| 탐색 공간의 한계 | 트리 구조만 지원 — 추론 경로 간 합류(merge) 불가 → GoT에서 해결 |
| LLM 평가기의 한계 | 상태 평가를 LLM에 의존하므로, 평가 자체의 정확도가 병목 |
의의 및 후속 연구
학술적 기여
- “사고”의 형식적 정의: 추론의 중간 단위를 탐색 가능한 노드로 개념화
- 통합 프레임워크: IO, CoT, CoT-SC를 트리의 특수 케이스로 통합
- LLM = 생성기 + 평가기: 외부 모듈 없이 LLM만으로 탐색 수행 가능함을 입증
후속 연구 방향
- Graph of Thoughts (GoT): 트리 → 임의 그래프로 확장 (분할정복 가능)
- Reasoning via Planning (RAP): MCTS(몬테카를로 트리 탐색) 적용
- 자동 사고 분해: 과제별 수동 설계를 학습으로 대체
- ToT + RL: 강화학습으로 탐색 전략 자체를 최적화
BibTeX
@inproceedings{yao2023tree,
title={Tree of Thoughts: Deliberate Problem Solving with Large Language Models},
author={Yao, Shunyu and Yu, Dian and Zhao, Jeffrey and Shafran, Izhak and Griffiths, Thomas L. and Cao, Yuan and Narasimhan, Karthik},
booktitle={Advances in Neural Information Processing Systems (NeurIPS)},
year={2023}
}