Antigravity Agent
3.9 KiB
3.9 KiB
Tree-of-Thought (ToT, 사고 트리)
📌 Brief Summary
Tree-of-Thought(ToT)는 LLM이 문제를 선형 단계(Chain-of-Thought)가 아닌 트리 구조로 탐색하여, 각 중간 단계에서 여러 가능한 사고 경로를 분기(Branch)하고 평가·선택하는 추론 프레임워크다. 체스나 수학 퍼즐처럼 초반 선택이 최종 결과에 결정적 영향을 미치는 문제에서 Chain-of-Thought보다 월등히 높은 정확도를 보인다.
📖 Core Content
1. CoT vs ToT 구조 비교
[Chain-of-Thought (CoT)]
S → T₁ → T₂ → T₃ → 답
(선형 단일 경로 → 한 번 틀리면 복구 불가)
[Tree-of-Thought (ToT)]
S
/ | \
T₁ T₂ T₃ ← 단계 1: 3가지 사고 분기 생성
/│\ │
A B C D ← 단계 2: 각 분기에서 추가 확장
↓
[평가] B가 가장 유망 → B만 계속 탐색
↓
최종 답 (유망한 경로만 깊이 탐색)
2. ToT의 4가지 핵심 요소
| 요소 | 설명 |
|---|---|
| Thought (사고 단위) | 중간 추론 단계 (문장·방정식·계획 등) |
| Generator (생성기) | LLM이 현재 상태에서 여러 Thought 후보 생성 |
| Evaluator (평가기) | 각 Thought의 유망도 점수화 (LLM 또는 별도 함수) |
| Search (탐색 전략) | BFS(너비 우선) 또는 DFS(깊이 우선) 선택 |
3. 탐색 전략
| 전략 | 방법 | 적합 문제 |
|---|---|---|
| BFS (너비 우선) | 현재 레벨의 모든 Thought 평가 후 상위 K개 유지 | 레벨별 평가 가능한 단계적 문제 |
| DFS (깊이 우선) | 유망한 경로 깊게 탐색, 막히면 backtrack | 해가 깊은 곳에 있는 탐색 문제 |
| MCTS (몬테카를로 트리 탐색) | 시뮬레이션 + 통계적 선택 | 게임·복잡한 의사결정 |
4. 성능 수치
| 벤치마크 | IO (직접 출력) | CoT | ToT | ToT 향상 |
|---|---|---|---|---|
| Game of 24 (수식 퍼즐) | 7.3% | 4.0% | 74% | +67%p |
| Creative Writing | — | — | +평가점수 향상 | 창의성+논리 균형 |
| Mini Crosswords | 0% | 3.7% | 20% | +16%p |
5. ToT 정확도 향상의 인과관계
[CoT의 한계]
한 번 잘못된 추론 → 이후 모든 단계 오염
(선형 경로의 구조적 취약점)
↓
[ToT의 해결]
여러 후보 Thought 동시 생성 (분기)
↓
LLM 스스로 "이 경로가 올바른 방향인가?" 평가
(자기 평가: Self-Evaluation)
↓
유망하지 않은 경로 조기 가지치기 (Pruning)
↓
계산 자원을 유망한 경로에 집중
↓
복잡한 다단계 문제에서 정확도 비약적 향상
6. ToT의 한계
- 계산 비용: Branch × Depth 만큼 LLM 호출 → CoT 대비 수십~수백 배 비용.
- 속도: 실시간 응답 시스템에 부적합.
- 평가기 신뢰성: "좋은 Thought" 판단 자체를 LLM이 하므로, 평가 오류 가능.
🔗 Knowledge Connections
- Related Topics: Chain-of-Thought (CoT, 사고 사슬), ReAct (Reasoning + Acting), 강화학습 (Reinforcement Learning), GRPO (Group Relative Policy Optimization), Multi-Hop Reasoning (다중 홉 추론), Self-Consistency (자기 일관성)
- Projects/Contexts: AI 추론 시스템
- Contradictions/Notes:
- ToT는 비용 대비 성능 트레이드오프가 극단적 → 실시간 서비스보다 오프라인 배치·연구용으로 적합.
- 신규 키워드:
MCTS (몬테카를로 트리 탐색),Self-Evaluation,Backtracking→ 탐색 큐 추가.