Tree of Thoughts - Deliberate Problem Solving with Large Language Models

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%**를 달성하여 구조화된 탐색의 극적인 효과를 입증했다.

---

메타데이터

항목	내용
제목	Tree of Thoughts: Deliberate Problem Solving with Large Language Models
저자	Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, Karthik Narasimhan
소속	Princeton University, Google DeepMind
연도	2023
발표	NeurIPS 2023
링크	arXiv · GitHub
키워드	Tree of Thoughts, Deliberate Reasoning, BFS, DFS, Problem Solving, Prompting
인용수	3,527+

---

왜 이 연구를 하는가?

핵심 질문

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.74/casevsIObest-of-100$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에 의존하므로, 평가 자체의 정확도가 병목

---

의의 및 후속 연구

학술적 기여

1. “사고”의 형식적 정의: 추론의 중간 단위를 탐색 가능한 노드로 개념화
2. 통합 프레임워크: IO, CoT, CoT-SC를 트리의 특수 케이스로 통합
3. 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}
}