Tree of Thoughts 완전 정리, 사슬을 트리로 바꾸면

요약

한 줄기 추론인 Chain-of-Thought를 트리 탐색으로 일반화한 추론 제어 프레임워크입니다. 새 모델이 아니라 LLM을 생성기와 평가기로 쓰고 그 위에 탐색을 얹는 방식입니다.
CoT의 약점이 명확합니다. 경로가 하나라 초반 실수가 치명적입니다. 토큰을 왼쪽에서 오른쪽으로 한 번 흘려보내면 되돌릴 수 없습니다.
프레임워크는 넷을 정의하는 것으로 끝납니다. 생각 분해, 생성기, 평가기, 탐색 알고리즘입니다.
성능 차이가 큽니다. Game of 24에서 GPT-4에 CoT는 4%, ToT는 74%입니다. 단 탐색형 문제에 한정된 이득입니다.
실무에서 진짜 급소는 탐색이 아니라 평가 함수입니다. 채점이 부정확하면 좋은 가지를 잘라버립니다.
공짜가 아닙니다. 노드마다 LLM을 생성과 평가로 호출해 비용과 지연이 급증합니다. 이건 test-time compute, 즉 추론 연산을 더 써서 정확도를 사는 기법입니다.

1장. 왜 나왔나

1.1 논문 정보

제목   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, Google DeepMind
출처   NeurIPS 2023, arXiv:2305.10601 (2023년 5월)

1.2 CoT의 구조적 약점

논문 초록이 문제를 정확히 짚습니다.

언어모델은 다양한 과제에서 범용 문제해결에 쓰이고 있지만
추론 시점에는 여전히
토큰 수준의, 왼쪽에서 오른쪽으로 가는 의사결정 과정에 갇혀 있다

   그래서 다음 세 경우에 부족해진다
   ① 탐색이 필요한 과제
   ② 전략적 예측(lookahead)이 필요한 과제
   ③ 초기 결정이 결정적 역할을 하는 과제

세 번째가 특히 아픕니다. 앞에서 방향을 잘못 잡으면 뒤에서 아무리 잘해도 소용이 없습니다.

1.3 사람은 어떻게 푸나

사람은 문제를 풀 때
   여러 가능성을 머릿속에서 굴려보고
   막히면 앞 갈림길로 돌아가 다른 길을 시도한다

   CoT 에는 이 탐색이 없다

논문은 인지과학의 빠른 직관적 사고(System 1)와 느린 심의적 사고(System 2)의 대비를 빌려, LLM에게 후자에 해당하는 숙고(deliberate) 능력을 주자고 제안합니다.

1.4 표현력의 계보

IO (입출력 한 방)
  ⊂ CoT (한 경로)
      ⊂ ToT (트리)
          ⊂ GoT (그래프)

각 단계가 이전을 포함합니다. ToT는 CoT를 일반화한 것이지 대체한 게 아닙니다. 너비를 1로 두면 CoT가 됩니다.

2장. 프레임워크

2.1 정의해야 할 네 가지

이게 프레임워크의 전부입니다. 넷을 정하면 ToT가 돕니다.

	무엇을 정하나	선택지
생각 분해	한 생각을 얼마나 잘게 쪼갤지	한 줄, 한 방정식, 한 문단
생성기	현 상태에서 다음 후보를 어떻게 만들지	무작위 샘플링, 순차 제안
평가기	각 상태가 목표에 얼마나 가까운지	독립 값 매김, 후보 간 투표
탐색 알고리즘	트리를 어떻게 훑을지	BFS, DFS

2.2 생각 분해

첫 결정이자 가장 과제 의존적인 결정입니다.

너무 잘게 쪼개면   트리가 깊어져 비용이 폭발한다
너무 크게 잡으면   분기의 의미가 없어진다

   Game of 24 에서는 "두 숫자를 골라 한 번 연산" 이 한 생각이다
   창작에서는 "한 문단의 계획" 정도가 한 생각이다

2.3 생성기

샘플링 (sample)
   같은 프롬프트로 여러 번 생성해 후보를 만든다
   후보 공간이 풍부할 때. 창작 같은 경우

제안 (propose)
   한 프롬프트로 여러 후보를 순차적으로 내게 한다
   후보 공간이 좁을 때. 수 조합 같은 경우

후보 공간의 크기가 선택 기준입니다. 좁은 공간에서 샘플링하면 중복이 많이 나옵니다.

2.4 평가기

독립 값 매김 (value)
   상태 하나하나에 "이 길이 목표에 닿을 수 있나"를 묻는다
   Game of 24 라면 유망 / 애매 / 막힘으로 채점

투표 (vote)
   여러 후보를 한 번에 놓고 "어느 게 가장 유망한가"를 고르게 한다
   절대 평가가 어려운 창작 같은 과제에 맞는다

절대 채점이 가능한 과제냐 아니냐가 갈림길입니다.

2.5 탐색 알고리즘

BFS   각 단계에서 상위 b 개만 유지하며 폭으로 넓힌다
      해가 얕은 깊이에 있을 때 유리

DFS   한 경로를 끝까지 파고 막히면 백트래킹
      깊이가 깊고 조기 판정이 가능할 때 유리

탐색 제어는 외부 코드가 맡습니다. LLM은 생성과 평가만 하고, BFS/DFS와 너비 b와 깊이 제한은 일반 프로그램이 관리합니다. LLM을 부품으로 끼워 넣고 그 위에 고전적 탐색을 얹은 구조입니다.

3장. 한 사이클

3.1 흐름

현재 상태 (부분해)
   │
   ▼
① 생성   다음 생각 후보들을 만든다
   │
   ▼
② 평가   각 후보를 LLM이 채점
         유망 / 애매 / 막힘
   │
   ▼
③ 탐색 결정
   │
   ├─ 유망 상위 b개 ──► 확장
   │                      │
   │                      ├─ 목표 도달 ──► 해
   │                      │
   │                      └─ 아직 ──► ①로 되돌아감
   │
   └─ 막힘 ──► 가지치기, 필요하면 백트래킹

3.2 미로 비유

CoT   갈림길마다 직감으로 한 길만 골라 끝까지 간다
      잘못 골랐으면 그대로 실패

ToT   갈림길에서 여러 길을 조금씩 가보고
      유망한 길만 더 들어가며
      막히면 갈림길로 되돌아온다

   한 번의 잘못된 선택이 전체를 망치지 않는다

4장. Game of 24로 보기

4.1 문제 설정

네 개의 숫자를 각각 한 번씩 사칙연산으로 조합해 24를 만드는 퍼즐입니다.

생각의 단위   두 숫자를 골라 한 번 연산하는 것

   매 단계마다 숫자 집합이 4개 → 3개 → 2개 → 1개로 줄고
   마지막에 24 가 남으면 성공

4.2 탐색 과정

시작: {4, 9, 10, 13}
  │
  ├─► 10 - 4 = 6    → {6, 9, 13}    평가: 유망, 확장
  │        │
  │        └─► 13 - 9 = 4  → {4, 6}  → 4 x 6 = 24  성공
  │
  ├─► 4 + 9 = 13    → {10, 13, 13}  평가: 막힘, 가지치기
  │
  └─► 13 - 9 = 4    → {4, 4, 10}    평가: 애매, 후순위

최종 해는 (10 - 4) x (13 - 9) = 6 x 4 = 24입니다.

각 상태에서 평가기는 "남은 숫자로 24에 닿을 수 있나"를 유망과 애매와 막힘으로 채점합니다.

4.3 왜 CoT가 4%였나

CoT 라면 첫 갈림길에서 하나를 고르고 끝까지 간다
   잘못 골랐으면 그대로 실패

   그런데 Game of 24 는
   첫 수를 잘못 고르면 24 에 절대 못 닿는 경우가 많다
   즉 초기 결정이 결정적인 과제다

   1.2 에서 본 CoT 약점 ③ 의 교과서적 사례

이 예시는 설명용으로 재구성한 것이고, 구체 분기와 평가 방식과 정량 수치는 원문을 따릅니다.

5장. 성능과 비용

5.1 논문이 보고한 것

검증 과제 세 가지
   Game of 24
   Creative Writing (창작)
   Mini Crosswords (미니 십자말풀이)

   셋 다 여러 경우를 따져야 하는 탐색형이자 계획형 문제다

방법	Game of 24 성공률
GPT-4 + CoT	4%
GPT-4 + ToT (너비 b=5)	74%

5.2 이 숫자를 그대로 일반화하면 안 된다

Game of 24는 ToT에 가장 유리한 조건입니다.

경우의 수가 많다              탐색의 이득이 크다
중간 상태 평가가 명확하다      "24에 닿을 수 있나"는 판정 가능
정답이 명확하다               채점에 모호함이 없다

   세 조건이 다 맞는 과제는 흔하지 않다

5.3 비용 구조

CoT   프롬프트 1회 → 답변 1회

ToT   노드마다 생성 호출 + 평가 호출
      너비 b, 깊이 d 면 호출이 급증한다

   너비와 깊이를 안 막으면 호출과 지연이 폭발한다

빔 제한과 가지치기와 조기 종료는 선택이 아니라 필수입니다.

5.4 test-time compute라는 관점

학습으로 정확도를 사는 것과
추론 연산으로 정확도를 사는 것은 다른 축이다

   ToT 는 후자의 대표적 참조점이다
   "호출 비용을 감수하고 정확도를 산다"

   반대편에는
   도구와 인자 결정을 단일 호출로 압축하는 비용 우선 설계가 있다
   둘은 정반대 방향이다

6장. 실무 판단

6.1 평가 함수가 진짜 급소다

여기가 실무에서 가장 중요한 부분입니다.

ToT 의 성능은 평가기가 얼마나 정확한가에 달려 있다

   각 상태가 유망한지 막혔는지를 LLM 이 스스로 채점하는데
   이 채점이 부정확하면 좋은 가지를 잘라버린다

   탐색 알고리즘을 아무리 잘 짜도 평가가 나쁘면 소용없다

과제별로 평가 난이도가 크게 다릅니다.

평가가 잘 되는 과제
   "남은 숫자로 24를 만들 수 있나"   판정 기준이 명확

평가가 흔들리는 과제
   "이 계획이 좋은 계획인가"        모호한 판단

ToT 도입을 검토할 때 "중간 상태를 신뢰할 만하게 평가할 수 있나"를 먼저 봐야 하는 이유입니다.

6.2 언제 쓰나

셋을 다 만족할 때입니다.

1. 여러 경로를 따져봐야 한다        퍼즐, 계획, 수 조합
2. 중간 상태를 평가할 수 있다       6.1 의 조건
3. 비용을 감당할 수 있다           호출이 수십 배로 늘어난다

6.3 언제 안 쓰나

요약, 번역, 분류
   탐색이 도움 안 되는 과제. 비용만 늘어난다

중간 상태를 평가할 수 없는 과제
   평가가 무작위면 탐색이 무작위가 된다

지연에 민감한 실시간 응답
   호출 수가 곧 지연이다

6.4 자주 하는 실수 셋

① 너비 b 와 깊이를 안 막는다
   호출과 지연이 폭발한다. 빔 제한과 조기 종료는 필수

② 평가기 품질을 안 본다
   좋은 가지를 잘라버리는 게 가장 흔한 실패

③ 비탐색형 과제에 적용한다
   비용만 늘고 이득이 없다

6.5 구현

공식 구현
   Princeton NLP 의 tree-of-thought-llm 저장소
   Game of 24, Creative Writing, Crosswords 실험과 재현 스크립트

LangChain
   langchain_experimental.tot 의 ToTChain

   ⚠ 이 구현은 Yao et al. 판이 아니라
     Jieyi Long 의 "LLM Guided Tree-of-Thought" 를 기반으로 한다
     같은 이름이지만 다른 설계다

마지막 주의가 실무에서 혼란을 부릅니다. "LangChain의 ToT를 썼는데 논문 결과가 안 나온다"는 경우, 애초에 다른 구현일 수 있습니다.

7장. 계보

7.1 이후 흐름

ToT는 "생각을 어떤 위상으로 조직할까"라는 흐름을 열었습니다.

시기	발전	요점
2023-05	Tree of Thoughts	CoT를 트리 탐색으로 일반화. Game of 24에서 4%에서 74%
2023-05	LLM Guided Tree-of-Thought	prompter, checker, memory, controller 모듈로 시스템화
2023-08	Graph of Thoughts	트리를 임의 그래프로 일반화. 부분해의 집계와 되먹임 도입
2023-10	LATS	ToT와 ReAct와 Reflexion을 MCTS로 통합. 도구와 환경 관찰까지 탐색
2024-12	Forest-of-Thought	여러 추론 트리를 앙상블하고 희소 활성화로 다관점 추론
2025-10	트리 탐색과 보상 설계 서베이	비용 통제를 정형화

7.2 ToT의 표현력 한계

ToT 는 분기와 백트래킹은 되지만
서로 다른 가지를 하나로 합치는(aggregate) 연산이 없다

   이 한계를 Graph of Thoughts 가
   트리를 임의 그래프로 일반화하며 메운다

7.3 셋 중 무엇을 고르나

추론만 탐색하면 되면          ToT
부분해를 합쳐야 하면           GoT
도구와 행동까지 탐색해야 하면   LATS

8장. 정리

8.1 핵심 셋

① ToT 는 CoT 의 "한 경로"를
   분기와 평가와 백트래킹이 가능한 트리 탐색으로 일반화했다

② LLM 이 생각을 생성하고 각 상태를 평가하며
   외부 탐색 코드가 유망한 가지를 확장하고 막힌 가지를 접는다

③ 탐색형 문제에서 크게 이기지만 비용이 커서 선택적으로 쓴다
   그리고 성능의 급소는 탐색이 아니라 평가 함수다

8.2 남는 질문

74%가 너비 b와 평가 방식에 얼마나 민감한가. 값 매김과 투표 중 무엇을 쓰느냐로도 결과가 달라질 수 있는데, 이 민감도가 충분히 보고되지 않았습니다.
평가기를 별도 모델로 두는 게 나은가. 같은 LLM이 생성과 평가를 다 하면 자기 편향이 생길 수 있습니다.
탐색 예산을 동적으로 배분할 수 있나. 지금은 너비 b가 고정인데, 어려운 분기에 더 쓰는 게 자연스러워 보입니다.

8.3 용어 정리

용어	한 줄 뜻
Tree of Thoughts	추론을 트리로 확장해 분기와 백트래킹을 가능하게 한 프레임워크
생각 (thought)	문제 해결을 향한 한 중간 단계. 트리의 한 노드
생성기	현 상태에서 다음 후보를 만드는 역할. 샘플링 또는 제안
평가기	각 상태가 목표에 얼마나 가까운지 채점. 값 매김 또는 투표
BFS / DFS	각 단계에서 상위 b개 유지 / 한 길을 깊이 파고 막히면 되돌아옴
가지치기	유망하지 않은 노드를 더 확장하지 않고 버리는 것
백트래킹	막혔을 때 앞 분기점으로 되돌아가는 것
너비 b	각 단계에서 유지할 후보 수. 비용을 좌우하는 상한
심의형 추론	여러 경로를 비교하고 선택하는 숙고형 의사결정
test-time compute	추론 시 연산을 더 써서 정확도를 올리는 기법군

8.4 참고자료

'LLM > Prompting' 카테고리의 다른 글

CoT(Chain of Thought) (0)	2024.05.24

ToT(Tree of Thoughts)