부제: Yao et al., Tree of Thoughts: Deliberate Problem Solving with Large Language Models (NeurIPS 2023)
1. 이 논문을 한 문장으로 요약하면
LLM의 추론을 “한 번에 한 줄로 생성하는 과정”이 아니라, 여러 중간 생각을 만들고 평가하며 탐색하는 “검색(search) 문제”로 바꾼 논문입니다.
즉, CoT(Chain-of-Thought)가 하나의 추론 경로를 따라가는 방식이라면, ToT(Tree of Thoughts)는 여러 경로를 분기시키고, 중간 상태를 평가하고, 필요하면 되돌아가며 더 나은 해를 찾습니다.
(원문 p.1–4)
2. 왜 이 논문이 나왔나
논문이 문제로 본 지점은 단순합니다.
- 기존 LLM 추론은 토큰 단위의 좌→우 생성에 묶여 있다.
- 그래서 초기 선택이 틀리면 이후 전체 경로가 무너질 수 있다.
- CoT는 추론 과정을 드러내 주지만, 여전히 하나의 체인을 따라가는 경우가 많다.
- Self-Consistency는 여러 체인을 뽑아볼 수는 있지만, 체인 내부에서 로컬하게 분기하고 되돌아가지는 못한다.
논문은 이 한계를 보완하려고, “중간 생각(thought)”을 하나의 탐색 단위로 보고 트리 탐색을 결합합니다.
(원문 Abstract, p.1–4)
3. 핵심 아이디어: Tree of Thoughts(ToT)
3-1. “Thought”란 무엇인가
논문에서 thought는 문제를 풀기 위한 의미 있는 중간 단계입니다.
중요한 점은 thought가 “토큰 1개”가 아니라는 것입니다.
- Game of 24에서는 thought = 중간 식 1줄
- Creative Writing에서는 thought = 글의 짧은 플랜
- Mini Crosswords에서는 thought = 다음에 채울 단어 후보
즉, thought는 너무 작지도, 너무 크지도 않은 의미 단위여야 합니다.
(원문 p.3, Table 1)
3-2. ToT를 이루는 4가지 구성요소
논문은 ToT를 사실상 4개의 모듈로 설명합니다.
(원문 p.3–4)
- Thought decomposition
문제를 어떤 중간 단계들로 쪼갤지 결정합니다. - Thought generator
현재 상태에서 다음 thought 후보들을 생성합니다.- 독립 샘플링(sample) 방식
- 순차 제안(propose) 방식
- State evaluator
지금 상태가 얼마나 유망한지 평가합니다.- 각 상태를 개별 채점(value)
- 여러 상태를 비교 투표(vote)
- Search algorithm
어떤 후보를 계속 볼지 결정합니다.- 얕은 문제에는 BFS
- 되돌아가기 중요한 문제에는 DFS
3-3. 요약하면 ToT는 이렇게 돌아간다
생성 → 평가 → 선택/가지치기 → 확장 또는 백트래킹의 반복입니다.
- CoT: 한 줄로 계속 전진
- ToT: 여러 후보를 잠깐씩 보고, 덜 유망한 건 버리고, 좋은 경로를 더 깊게 탐색
이 차이가 논문의 핵심입니다.
4. Figure 1로 보는 ToT의 위치
Figure 1 설명
이 그림은 IO → CoT → CoT-SC → ToT로 갈수록, LLM이 문제를 푸는 방식이 어떻게 더 “탐색적”이 되는지를 보여줍니다.
- IO: 입력에서 바로 출력
- CoT: 중간 추론을 한 줄로 이어감
- CoT-SC: 여러 체인을 샘플링한 뒤 다수결
- ToT: 중간 생각을 여러 갈래로 분기하고, 평가하며, 필요하면 되돌아감
블로그용 포인트
ToT의 본질은 “추론을 더 길게 쓰게 만든 것”이 아니라, 추론을 탐색 구조로 바꿨다는 데 있습니다.
(원문 Figure 1, p.2)
5. 이 논문의 방법론을 블로그에서 어떻게 설명하면 좋은가
5-1. CoT를 확장한 것이 아니라, 탐색을 붙인 것이다
겉으로 보면 ToT는 CoT의 확장처럼 보이지만, 실제로는 다릅니다.
- CoT의 기본 질문: “다음 생각은 무엇인가?”
- ToT의 기본 질문:
“지금 가능한 다음 생각 후보들은 무엇이고, 그중 무엇이 더 유망한가?”
즉, LLM은 단순 생성기(generator)가 아니라,
- 후보를 만드는 역할
- 후보를 평가하는 역할
을 동시에 맡습니다.
5-2. LLM을 “휴리스틱 함수”처럼 쓴다
고전 탐색 알고리즘에서는 보통 사람이 휴리스틱을 짜거나, 별도 모델이 가치 함수를 학습합니다.
이 논문은 그 부분을 LM 자체의 자기평가(self-evaluation)로 처리합니다.
이 시점에서 ToT는 단순 프롬프트 기법을 넘어,
“LLM + 탐색 알고리즘” 조합으로 읽는 것이 더 정확합니다.
(원문 p.4)
6. 실험 설정 한눈에 보기
| 과제 | 입력 | 출력 | thought 단위 | 주요 탐색 |
|---|---|---|---|---|
| Game of 24 | 숫자 4개 | 24를 만드는 식 | 중간 계산식 1줄 | BFS |
| Creative Writing | 랜덤 문장 4개 | 각 문장으로 끝나는 4문단 글 | 짧은 글쓰기 플랜 | 투표 기반 2단계 선택 |
| Mini Crosswords | 가로/세로 단서 10개 | 5x5 보드 | 다음에 채울 단어 후보 | DFS + 가지치기 + 백트래킹 |
포인트
논문은 하나의 ToT만 제시하지 않습니다.
문제 성격에 따라 thought의 크기, 생성 방식, 평가 방식, 검색 알고리즘이 달라질 수 있음을 보여줍니다.
(원문 Table 1, p.5 / Method, p.3–4)
7. 실험 1: Game of 24
7-1. 무엇을 했나
Game of 24에서는 숫자 4개를 가지고 + - * /만 써서 24를 만들어야 합니다.
논문은 이 문제를 3단계 thought로 쪼갭니다.
- 중간 식 1개 생성
- 남은 숫자로 중간 식 1개 더 생성
- 마지막 식으로 24 도달
그리고 각 단계에서 후보 식들을 제안한 뒤,
그 상태가 24에 도달할 가능성을 sure / maybe / impossible로 평가합니다.
이후 BFS로 상위 후보만 유지합니다.
(원문 p.5)
7-2. Figure 2: Game of 24에서의 ToT 동작
Figure 2 설명
이 그림은 ToT가 Game of 24에서 실제로 어떻게 쓰였는지를 보여줍니다.
- 위쪽: 다음 중간 식 후보 제안
- 아래쪽: 현재 상태가 24로 이어질 수 있는지 평가
- 그 결과를 바탕으로 BFS가 다음 노드를 선택
즉, ToT는 “더 많이 생성”하는 것이 아니라
생성한 후보를 중간중간 걸러가며 탐색합니다.
(원문 Figure 2, p.5)
7-3. 핵심 결과
논문에서 가장 유명한 숫자가 여기서 나옵니다.
| 방법 | 성공률 |
|---|---|
| IO prompt | 7.3% |
| CoT prompt | 4.0% |
| CoT-SC (k=100) | 9.0% |
| ToT (b=1) | 45% |
| ToT (b=5) | 74% |
| IO + Refine | 27% |
| IO (best of 100) | 33% |
| CoT (best of 100) | 49% |
해석 포인트
- 단순 CoT는 오히려 잘 안 풀립니다.
- Self-Consistency를 100번 돌려도 9%에 그칩니다.
- ToT는 breadth를 5로 두었을 때 74%까지 올라갑니다.
- 심지어 CoT 100개 중 최선(best of 100)보다도 ToT가 더 좋습니다.
즉, 이 논문은
“많이 뽑는 것”보다 “중간 상태를 보고 탐색하는 것”이 더 중요하다는 점을 보여줍니다.
(원문 Table 2, Figure 3, p.6)
7-4. Figure 3: 왜 ToT가 이기는가
Figure 3 설명
- 왼쪽 그래프: 같은 수준의 샘플 수를 써도 ToT가 더 높은 성공률을 보임
- 오른쪽 그래프: CoT는 첫 단계에서 이미 많이 실패함
논문은 CoT 샘플의 약 60%가 첫 단계에서 이미 실패한다고 분석합니다.
이는 좌→우로 한 번만 밀고 가는 방식의 약점을 잘 보여줍니다.
(원문 Figure 3, p.6)
블로그용 핵심 문장
Game of 24 결과는 ToT의 강점을 가장 선명하게 보여준다.
ToT의 핵심 가치는 “추론을 길게 쓰게 하는 것”이 아니라, 초기 실수를 빠르게 버리고 다른 경로를 시도할 수 있게 하는 것이다.
8. 실험 2: Creative Writing
8-1. 무엇을 했나
Creative Writing 과제에서는 랜덤 문장 4개가 주어지고,
각 문단의 마지막 문장이 그 문장들로 끝나는 4문단 글을 써야 합니다.
이 문제의 특징은 수학처럼 정답 여부를 바로 판정하기 어렵다는 점입니다.
그래서 논문은 value보다 vote를 적극적으로 씁니다.
구성은 2단계입니다.
- 플랜 5개 생성 → 투표로 1개 선택
- 선택된 플랜으로 글 5개 생성 → 투표로 1개 선택
즉, Creative Writing에서 ToT는 “플랜 탐색 + 결과물 탐색” 구조로 동작합니다.
(원문 p.6)
8-2. Figure 4: 플랜을 먼저 탐색한다
Figure 4 설명
이 그림은 창의적 글쓰기처럼 정답이 고정되어 있지 않은 문제에서도 ToT가 작동하는 방식을 보여줍니다.
핵심은 두 가지입니다.
- 먼저 플랜 수준에서 후보를 비교
- 그다음 완성 글 수준에서 다시 비교
즉, ToT는 수학 퍼즐만이 아니라
고수준 구조가 중요한 생성 과제에도 적용된다는 것을 보여줍니다.
(원문 Figure 4, p.7)
8-3. Figure 5와 결과 해석
자동 평가(GPT-4 coherency score)
| 방법 | 평균 점수 |
|---|---|
| IO | 6.19 |
| CoT | 6.93 |
| ToT | 7.56 |
| IO + refine | 7.67 |
| ToT + refine | 7.91 |
인간 비교(CoT vs ToT)
| 비교 결과 | 개수 |
|---|---|
| CoT가 더 좋음 | 21 |
| 비슷함 | 38 |
| ToT가 더 좋음 | 41 |
해석 포인트
- ToT는 자동 평가에서 IO와 CoT보다 모두 높습니다.
- 사람 비교에서도 ToT가 CoT보다 우세합니다.
- 특히 이 실험은 “정답이 분명하지 않은 생성형 과제에서도 ToT가 통한다”는 점을 보여줍니다.
이 부분이 중요합니다.
ToT는 수학 문제를 풀기 위한 기법으로 보이기 쉽지만,
실제로는 생성 전에 구조를 선택하게 만드는 메타-추론 기법에 가깝습니다.
(원문 Figure 5, p.6–7)
9. 실험 3: Mini Crosswords
9-1. 무엇을 했나
Mini Crosswords는 5x5 미니 크로스워드를 푸는 문제입니다.
이 과제에서는 한 번의 잘못된 선택이 이후 많은 단서를 망칠 수 있기 때문에,
논문은 DFS + 가지치기 + 백트래킹을 사용합니다.
절차는 대략 이렇습니다.
- 현재 채워진 보드 상태를 바탕으로 다음 단어 후보를 제안
- 각 후보에 confidence를 붙여 우선순위를 만듦
- 남은 단서가 “채울 수 있는 상태”인지 평가
- 불가능하다고 판단되면 서브트리 전체를 prune
- 막히면 부모 상태로 backtrack
즉, 이 과제는 ToT가 단순 “샘플링 개선”이 아니라
진짜 탐색 문제 해결 프레임워크라는 점을 가장 잘 드러냅니다.
(원문 p.7–8)
9-2. Figure 6: DFS, prune, backtrack
Figure 6 설명
이 그림은 Mini Crosswords에서 ToT가 어떻게 동작하는지 압축해서 보여줍니다.
- 왼쪽: 다음에 채울 단어 후보들을 제안
- 오른쪽: 남은 단서들이 가능한 상태인지 평가
- 불가능하면 가지치기(prune)
- 다른 후보를 보기 위해 되돌아감(backtrack)
이것이 CoT와의 결정적 차이입니다.
CoT는 잘못된 단어를 넣고 계속 갈 가능성이 높지만,
ToT는 “지금 상태 자체가 틀린 방향인지”를 중간에 판단합니다.
(원문 Figure 6, p.8)
9-3. 핵심 결과
| 방법 | Letter | Word | Game |
|---|---|---|---|
| IO | 38.7 | 14.0 | 0 |
| CoT | 40.6 | 15.6 | 1 |
| ToT | 78.0 | 60.0 | 20 |
| ToT + best state | 82.4 | 67.5 | 35 |
| ToT - prune | 65.4 | 41.5 | 5 |
| ToT - backtrack | 54.6 | 20.0 | 5 |
해석 포인트
- Word-level 성능이 15.6% → 60%로 크게 상승합니다.
- 실제 게임도 4/20개 해결(20%)합니다.
- 가지치기(prune)와 백트래킹(backtrack)을 제거하면 성능이 크게 떨어집니다.
즉, 이 실험은 ToT의 성능 원천이
단순히 “다양한 후보를 많이 생성”하는 데 있지 않고,
상태 평가 + 탐색 제어에 있음을 보여줍니다.
(원문 Table 3, p.7–8)
10. 이 논문에서 꼭 짚어야 할 진짜 포인트
포인트 1. ToT의 핵심은 “더 긴 추론”이 아니라 “탐색”
많은 사람이 ToT를 CoT의 강화판 정도로 이해하지만,
정확히는 생성(decoding)을 탐색(search)으로 바꾼 것이 핵심입니다.
포인트 2. thought의 단위가 중요하다
thought를 너무 작게 잡으면 평가가 어렵고,
너무 크게 잡으면 후보 다양성이 떨어집니다.
논문은 문제마다 thought의 적절한 크기가 다르다는 점을 잘 보여줍니다.
포인트 3. LLM이 스스로 휴리스틱이 된다
별도 보상모델 없이도 LM이 “이 상태가 괜찮은가?”를 어느 정도 판단할 수 있다는 점이 중요합니다.
포인트 4. 정답형 문제뿐 아니라 생성형 문제에도 적용된다
Creative Writing 실험은 ToT를 퍼즐용 트릭이 아니라
구조적 생성 전략으로 읽어야 한다는 근거입니다.
포인트 5. 백트래킹이 성능 차이를 만든다
Mini Crosswords 결과는 ToT가 왜 필요한지를 가장 강하게 증명합니다.
정답에 가까워지는 과정에는 종종 되돌아가기가 필요합니다.
11. 한계와 비판적으로 볼 지점
논문도 한계를 분명히 적습니다.
11-1. 계산량이 크다
ToT는 IO나 CoT보다 더 많은 토큰과 호출을 씁니다.
논문은 설정에 따라 CoT보다 5~100배 정도 더 많은 생성 비용이 들 수 있다고 봅니다.
(원문 p.14)
11-2. 휴리스틱 품질이 중요하다
상태 평가가 잘못되면 좋은 가지를 잘라낼 수 있습니다.
Mini Crosswords에서 실제로 이런 문제가 관찰됩니다.
희귀/고어 단어 때문에 “가능한 상태”를 불가능하다고 판단하기도 합니다.
(원문 p.8)
11-3. 모든 문제에 항상 필요한 것은 아니다
논문은 GPT-4가 이미 잘하는 쉬운 과제에서는 ToT의 이득이 크지 않을 수 있다고 봅니다.
즉, ToT는 계획·탐색·백트래킹이 중요한 문제에서 특히 가치가 큽니다.
(원문 p.9, Appendix B)
12. 이 논문의 의미
이 논문의 의미는 간단히 정리하면 세 가지입니다.
- 추론을 탐색 구조로 본다
LLM inference를 search problem으로 재해석했다. - LLM을 생성기이자 평가기로 쓴다
LLM 자체가 휴리스틱 역할을 한다. - 문제별로 조합 가능한 프레임워크를 제시했다
thought 단위, generator, evaluator, search algorithm을 독립적으로 바꿀 수 있다.
이 때문에 ToT는 단일 프롬프트 기법이라기보다,
“LLM 기반 문제해결 프레임워크”로 보는 편이 정확합니다.
(원문 p.4, p.9)
13. 핵심 문장 5개
아래 문장들은 블로그 본문에 바로 넣기 좋게 다듬은 버전입니다.
- Tree of Thoughts는 LLM 추론을 한 줄짜리 체인이 아니라 탐색 트리로 바꾼다.
- CoT가 하나의 경로를 끝까지 밀어붙인다면, ToT는 여러 경로를 잠깐씩 보고 더 유망한 쪽으로 간다.
- ToT의 성능 향상은 “더 많이 생성해서”가 아니라 “중간 상태를 평가하고 버릴 줄 알아서” 나온다.
- 이 논문은 LLM을 텍스트 생성기에서 휴리스틱 기반 문제해결기로 확장한다.
- 계획, 가지치기, 백트래킹이 필요한 문제일수록 ToT의 가치가 커진다.
14. 요약
Tree of Thoughts(ToT)는 LLM의 추론을 단일 체인 생성에서 벗어나, 여러 중간 생각을 만들고 평가하며 탐색하는 구조로 바꾼다. 이 논문은 thought를 의미 있는 중간 단계로 정의하고, 후보 생성(generator), 상태 평가(evaluator), 탐색 알고리즘(BFS/DFS)을 결합해 문제를 푸는 방식을 제안한다. 그 결과 Game of 24에서는 CoT 4% 대비 ToT 74%의 성공률을 기록했고, Creative Writing과 Mini Crosswords 같은 생성형·탐색형 과제에서도 뚜렷한 향상을 보였다. 핵심은 “더 길게 생각하는 것”이 아니라, 잘못된 경로를 빨리 버리고 다른 경로를 시도할 수 있는 탐색 능력이다.
15. 참고 정보
- 논문명: 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
- 학회: NeurIPS 2023
- 주요 참조 위치:
- Abstract / Introduction: p.1–2
- Method: p.3–4
- Game of 24: p.5–6
- Creative Writing: p.6–7
- Mini Crosswords: p.7–8
- Discussion / Limitations: p.9
- Additional experiments / cost: p.13–14
'AI 생성 글 정리 > agent' 카테고리의 다른 글
| Meta-Harness 논문 핵심 정리 (0) | 2026.04.03 |
|---|---|
| Mamba 논문 핵심 정리 (0) | 2026.04.02 |
| ReAct 논문 핵심 정리 (0) | 2026.04.02 |
| Graph of Thoughts 논문 정리 (0) | 2026.04.02 |
| MedGemma Technical Report 핵심 정리 (0) | 2026.04.01 |
