논문: Tree of Thoughts: Deliberate Problem Solving with Large Language Models 저자: Yao et al. (Princeton, Google DeepMind) 링크: https://arxiv.org/abs/2305.10601

논문 핵심

Chain-of-Thought(CoT)는 단일 추론 경로만 따릅니다. Tree of Thoughts(ToT)는 여러 추론 경로를 동시에 탐색하고, 각 경로를 평가하여 최적의 해답을 찾습니다.

CoT vs ToT

"ToT allows LLMs to perform deliberate decision making by considering multiple reasoning paths."

CoT: 입력 → 생각1 → 생각2 → 생각3 → 답 (단일 경로) ToT: 입력 → [생각1a, 생각1b, 생각1c] → 평가 → [생각2a, 생각2b] → 평가 → 답 (트리 탐색)

탐색 전략

  • BFS (너비 우선 탐색): 각 단계에서 상위 k개의 유망한 경로만 유지
  • DFS (깊이 우선 탐색): 유망한 경로를 끝까지 탐색, 막히면 백트래킹

결과

  • Game of 24: CoT 4% → ToT 74%
  • Creative Writing: 일관성과 품질에서 CoT 대비 큰 개선

실무 시사점

전략 수립, 복잡한 의사결정, 문제 해결 등에서 ToT 방식의 프롬프팅을 적용하면 LLM의 성능을 크게 향상시킬 수 있습니다. 이는 이후 o1의 Test-time Compute 아이디어의 전신이기도 합니다.