생각의 나무: 숙고하며 문제 풀기 (Tree of Thoughts)

생각의 나무: 숙고하며 문제 풀기 (Tree of Thoughts)

생각의 사슬처럼 풀이를 한 줄로 죽 쓰는 대신, 중간 단계('생각')를 여러 갈래로 만들어 보고, 언어 모델 스스로 각 갈래가 유망한지 평가하며, 나무를 탐색(앞서 보기 · 되돌아가기) 하게 한 프레임워크입니다. 24 게임에서 GPT-4 + CoT가 4%를 풀 때 74%를 풀었고, 창작 글쓰기 · 미니 십자말풀이에서도 크게 앞섰습니다.

들어가기 전에

이 해설은 아래 내용을 안다고 보고 씁니다. 처음이라면 먼저 읽고 오면 수식과 손계산을 훨씬 쉽게 따라올 수 있습니다.

• 자기 일관성으로 생각의 사슬 추론 높이기 (Self-Consistency) — 생각의 사슬을 여러 번 샘플링해 가장 많이 나온 답을 고르는 단순한 디코딩 방법

한눈에 보기

• 왼쪽에서 오른쪽으로 한 토큰씩 정하는 생성 방식이 탐색 · 앞서 보기 · 되돌아가기 가 필요한 문제에 왜 약한지 알게 됩니다.
• ToT를 이루는 네 가지 질문 — 생각을 어떻게 쪼갤지, 어떻게 만들지, 어떻게 평가할지, 어떻게 탐색할지 — 를 이해합니다.
• 24 게임을 예로 BFS + '확실/아마/불가능' 평가가 어떻게 돌아가는지 손으로 따라가 봅니다.
• 성능과 비용의 맞바꿈, 그리고 언제 ToT가 필요 없는지 판단할 수 있게 됩니다.

초록 (번역)

언어 모델은 점점 더 폭넓은 과제에서 일반적인 문제 해결에 쓰이고 있지만, 추론 시점에는 여전히 토큰 단위로 왼쪽에서 오른쪽으로 결정하는 과정에 갇혀 있습니다. 이 때문에 탐색이나 전략적 앞서 보기가 필요하거나, 처음 내린 결정이 결정적인 역할을 하는 과제에서는 부족할 수 있습니다. 이런 문제를 넘기 위해, 우리는 언어 모델 추론을 위한 새로운 프레임워크인 생각의 나무(ToT)를 소개합니다. ToT는 언어 모델을 프롬프팅하는 대표적 방법인 생각의 사슬을 일반화한 것으로, 문제 해결을 향한 중간 단계 역할을 하는 일관된 텍스트 단위(생각)들 위에서 탐색할 수 있게 합니다. ToT는 언어 모델이 여러 다른 추론 경로를 고려하고 선택을 스스로 평가해 다음 행동을 정하며, 필요할 때 앞서 보거나 되돌아가 전체적인 선택을 내리는 숙고형 의사결정을 하게 합니다. 실험 결과 ToT는 쉽지 않은 계획이나 탐색이 필요한 세 가지 새로운 과제, 24 게임 · 창작 글쓰기 · 미니 십자말풀이에서 언어 모델의 문제 해결 능력을 크게 높였습니다. 예를 들어 24 게임에서 생각의 사슬 프롬프팅을 쓴 GPT-4는 과제의 4%만 풀었지만, 우리의 방법은 74%의 성공률을 달성했습니다. 모든 프롬프트가 담긴 코드 저장소를 공개합니다.

무엇을 풀었나

언어 모델의 생성은 기본적으로 한 방향 · 한 번 입니다. 토큰을 왼쪽부터 하나씩 정하고, 정한 것은 되돌리지 않습니다. 논문은 이것을 사람 인지의 '시스템 1'(빠르고 자동적인 판단)에 비유하고, 어려운 문제에는 '시스템 2'(느리고 숙고하는 계획)가 필요하다고 봅니다.

기존 프롬프트 방법들의 한계는 이렇습니다.

• 입출력(IO) 프롬프팅: 바로 답을 냅니다.
• 생각의 사슬(CoT): 중간 생각 $z_1, \dots, z_n$을 차례로 쓰지만 한 줄뿐이고, 생각을 어떤 단위로 쪼갤지도 모호합니다.
• 자기 일관성(CoT-SC): 사슬을 여러 개 뽑아 다수결하지만, 각 사슬 안에서 다른 갈래를 탐색하지 않고, '가장 많이 나온 답' 규칙은 답의 종류가 한정된 경우에만 통합니다.

논문은 뉴웰 · 사이먼의 고전적 문제 해결 이론(문제 공간을 나무로 탐색)을 빌려 두 가지 결함을 짚습니다. ① 지역적으로 한 생각 과정 안에서 다른 이어 가기를 탐색하지 않고, ② 전역적으로 계획 · 앞서 보기 · 되돌아가기가 없습니다.

핵심 아이디어

12345678flowchart TD
  X[문제 입력 x] --> S0[상태 s0 = x]
  S0 --> G[생각 생성기: 후보 생각 k개 제안]
  G --> V[상태 평가기: LM이 '확실 · 아마 · 불가능' 또는 투표]
  V --> SEL{탐색 알고리즘}
  SEL -->|BFS: 상위 b개 유지| G
  SEL -->|DFS: 유망한 쪽 깊이 · 불가능하면 되돌아감| G
  SEL --> OUT[최종 출력]

1. 생각을 '노드'로 하는 나무 탐색

직관. 바둑 기사가 한 수를 두기 전에 여러 수를 떠올리고, 각 수가 몇 수 뒤 어떻게 될지 가늠해 보고, 가망 없는 수는 버리는 것과 같습니다. 다만 ToT의 '수'는 한 줄의 수식이나 한 단락의 계획 같은 의미 있는 글 덩어리 입니다.

정의. 나무의 각 노드는 상태 $s = [x, z_{1 \dots i}]$, 즉 입력과 지금까지의 생각들입니다. ToT를 구체적으로 만들려면 네 가지를 정해야 합니다.

생각의 크기 원칙. 생각은 모델이 다양하고 그럴듯하게 만들 만큼 작고(책 한 권은 너무 큼), 모델이 유망한지 평가할 수 있을 만큼 커야(토큰 하나는 너무 작음) 합니다.

수식 (생성과 평가).

왜 '언어 모델이 평가'하나. 탐색 휴리스틱은 보통 사람이 프로그래밍하거나(딥블루) 학습시킵니다(알파고). ToT는 세 번째 길로, 언어 모델이 상태를 두고 직접 추론 하게 합니다. 논문은 이것이 규칙보다 유연하고 학습 모델보다 표본 효율적일 수 있다고 봅니다. 평가가 완벽할 필요는 없고 의사결정에 대략 도움이 되면 됩니다.

2. 24 게임: BFS + '확실/아마/불가능' 평가

과제. 숫자 4개와 사칙연산으로 24를 만듭니다. 예: 입력 "4 9 10 13" → "(10 − 4) × (13 − 9) = 24". 4nums.com의 1,362문제 중 사람이 오래 걸린 어려운 문제(901~1,000번) 100개로 시험했습니다.

단계별 설명.

1. 생각 = 수식 한 줄, 3단계로 쪼갭니다(숫자 두 개를 연산해 하나로 줄이기를 세 번).
2. 각 노드에서 남은 숫자를 보여 주고 '가능한 다음 단계'를 제안하게 합니다.
3. 각 후보를 "24에 도달 가능: 확실 / 아마 / 불가능"으로 평가하게 하고, 후보마다 3번 평가합니다.
4. 단계마다 상위 $b = 5$개만 남기는 BFS를 합니다.

숫자로 해 보기 (논문 예시 입력을 따라 정리). 입력 4, 9, 10, 13.

• 1단계 후보: "13 − 9 = 4 (남은 수: 4 4 10)", "4 + 9 = 13 (남은 수: 10 13 13)", "10 − 4 = 6 (남은 수: 6 9 13)" …
• 평가: (4, 4, 10)은 "10 − 4 = 6, 6 × 4 = 24"처럼 몇 수 앞을 보면 바로 되므로 '확실'. (10, 13, 13)은 어떻게 해도 24를 만들기 어렵다고 보면 '불가능'으로 잘라 냅니다.
• 2단계: (4, 4, 10)에서 "10 − 4 = 6 (남은 수: 4 6)" → 3단계 "4 × 6 = 24".

평가는 두 가지 근거를 씁니다. 짧은 앞서 보기(예: 5, 5, 14는 5 + 5 + 14로 바로 확인)로 좋은 상태를 올리고, 상식(예: 1, 2, 3은 너무 작아 24 불가)으로 나쁜 상태를 버립니다.

왜 효과가 컸나. 오류 분석에서 CoT 샘플의 약 60%가 첫 단계(처음 세 단어, 예: "4 + 9")에서 이미 실패 했습니다. 왼쪽에서 오른쪽으로 바로 쓰면 첫 선택을 되돌릴 수 없다는 문제가 그대로 드러납니다. ToT는 첫 단계부터 여러 갈래를 남겨 둡니다.

3. 창작 글쓰기: 계획을 투표로 고르기

과제. 무작위 문장 4개를 받아, 각 단락이 그 문장으로 끝나는 4단락 글을 일관되게 씁니다. 정답이 없어 GPT-4가 매긴 1~10점 일관성 점수(5번 평균)와 사람의 맞비교로 평가했습니다.

설정. 깊이 2짜리 나무입니다. 모델이 계획 5개 를 만들고 5번 투표해 가장 좋은 계획을 고른 뒤, 그 계획으로 글 5개 를 쓰고 다시 투표로 고릅니다($b = 1$). 투표 프롬프트는 "아래 선택지를 분석하고 지시에 가장 유망한 것을 결론 내라" 정도의 간단한 제로샷입니다.

숫자로 해 보기 (설명용). 계획 5개에 대한 투표 5번의 결과가 (계획 2, 계획 2, 계획 4, 계획 2, 계획 1)이면 계획 2가 3표로 선택됩니다. 글이 어떻게 이어질지 직접 점수 매기기 어려운 문제에서는, 이렇게 비교해 고르는 편이 더 자연스럽다 는 것이 투표 방식을 쓴 이유입니다.

4. 미니 십자말풀이: DFS + 가지치기 + 되돌아가기

과제. 5×5 십자말풀이(가로 5 · 세로 5 단서). GooBix 156문제 중 20개로 시험하고, 글자 · 단어 · 게임 단위 성공률을 쟀습니다.

단계별 설명.

1. 생각 = 단서 하나에 단어 하나 채우기. 이미 채운 글자는 바꾸지 않게 해 최대 10단계입니다.
2. 현재 상태를 남은 단서들의 글자 제약(예: "v1. 쌓다: tm___")으로 바꿔, 다음에 채울 단어 후보를 5번 제안받고 확신도를 합쳐 우선순위 큐를 만듭니다.
3. DFS 로 가장 유망한 후보부터 깊이 들어갑니다.
4. 각 상태에서 남은 단서마다 "이 제약으로 채울 수 있나"를 평가하고, 하나라도 '불가능'이면 그 아래를 잘라 내고(가지치기) 부모로 되돌아갑니다.
5. 탐색은 100단계로 제한하고, 가장 깊이 간 상태를 출력합니다.

결과

24 게임 (성공률, GPT-4)

• CoT를 100번 뽑아 그중 최고를 고르는 '오라클' 설정도 49%로, ToT($b > 1$)보다 낮았습니다.

창작 글쓰기 (GPT-4 일관성 점수, 1~10): IO 6.19, CoT 6.93, ToT 7.56. 사람 맞비교 100쌍에서 ToT 선호 41, CoT 선호 21, 비슷함 38. 반복 수정을 더하면 IO 6.19 → 7.67, ToT 7.56 → 7.91로 올랐습니다.

미니 십자말풀이 (성공률)

• 되돌아가기를 빼면(가장 유망한 단서를 덮어쓰며 계속 채우기) 단어 단위 20%로 크게 떨어져 되돌아가기의 중요성 을 확인했습니다. 가지치기 평가가 불완전해(옛날 단어를 GPT-4가 오타로 봄) 정답을 잘라 내는 경우도 있었습니다.

다른 모델 · 쉬운 과제: GPT-3.5로도 'ToT > CoT > IO' 순서는 유지됐지만, 24 게임에서 GPT-3.5 + ToT는 19%로 GPT-4 + ToT(74%)보다 크게 낮았습니다. GSM8K · StrategyQA처럼 GPT-4 + CoT가 이미 잘하는 과제에서는 ToT 향상이 작았습니다.

비용: 24 게임 한 문제에 ToT는 완성 토큰 약 5,500개를 써서, CoT 100번(약 6,700개)에 가까웠습니다. 그래도 CoT 100번 중 최고보다 성능이 좋았습니다.

왜 중요한가 · 이후 영향

• '추론 시간 탐색' 을 언어 모델 프롬프팅에 본격적으로 들여왔습니다. CoT(한 줄) → CoT-SC(여러 줄 다수결) → ToT(나무 탐색)로 이어지는 흐름의 정점이며, 논문은 IO · CoT · CoT-SC · 자기 수정이 모두 깊이 · 너비가 제한된 ToT의 특수한 경우라고 정리합니다.
• 모듈식 설계: 생각 단위 · 생성 · 평가 · 탐색을 독립적으로 바꿀 수 있어, 문제에 맞게 조합하는 '추론 레시피'의 틀이 됐습니다.
• 에이전트 · 계획 연구의 재료: 같은 1저자의 ReAct가 추론 + 행동이라면, ToT는 추론 내부의 탐색입니다. 이후 LLM으로 MCTS 같은 탐색을 하는 연구들이 이 흐름을 잇습니다.

한계 · 주의할 점

• 비용이 큽니다. 생성 · 평가를 여러 번 하므로 IO · CoT보다 훨씬 많은 계산(API 비용)이 듭니다. 논문은 모듈식 구조로 성능-비용 균형을 사용자가 조절할 수 있다고 덧붙입니다.
• 모든 과제에 필요하지 않습니다. GPT-4가 이미 잘하는 과제에서는 이득이 작았습니다. 논문도 세 가지 비교적 단순한 과제만 탐구했다고 밝힙니다.
• 평가기 품질에 좌우됩니다. 십자말풀이에서 드문 단어를 '불가능'으로 잘못 판단해 정답을 잘라 낸 사례처럼, 휴리스틱이 틀리면 탐색이 엇나갑니다.
• 과제별 설계가 필요합니다. 생각 단위, 제안 · 평가 프롬프트, 탐색 방법을 문제마다 정해야 해서 범용 적용에는 손이 많이 갑니다.
• 기성 모델만 썼고, ToT식 의사결정으로 모델을 미세조정하는 것은 향후 과제로 남겼습니다.

스스로 점검

1. CoT-SC와 ToT의 가장 큰 차이는?

   CoT-SC는 완성된 사슬 여러 개를 따로 만들어 최종 답만 다수결합니다. ToT는 사슬 안의 중간 단계마다 여러 갈래를 만들고 평가해 유망한 쪽만 키우며, 필요하면 되돌아갑니다.

2. 24 게임에서 남은 수가 (1, 1, 2)인 상태를 평가기가 어떻게 볼까요?

   가장 크게 만들어도 $(1 + 1) \times 2 = 4$ 정도라 24에 못 미치므로, 상식 근거로 '불가능'으로 잘라 낼 가능성이 큽니다.

3. 십자말풀이에서 되돌아가기를 빼면 어떻게 됐나요?

   단어 단위 성공률이 60%(ToT)에서 20%로 떨어졌습니다. 잘못 채운 단어를 되돌릴 수 없으면 뒤의 단서가 연쇄로 막히기 때문입니다.

용어 정리

이어서 읽을 것

• 앞: 생각의 사슬 프롬프팅 · 자기 일관성 · ReAct
• 뒤: Reflexion · 생성형 에이전트

다음에 볼 것

이 글을 이해했다면 이어서 보면 좋은 항목입니다.

• 미세조정: 전체 미세조정 · 지시 미세조정(SFT) · LoRA · QLoRA — 프롬프트로 부족할 때 모델 자체를 고치는 방법
• Reflexion: 말로 하는 강화학습 에이전트 — 실패를 글로 반성해 기억에 쌓고 다음 시도에 쓰는, 가중치를 안 바꾸는 에이전트 학습법

출처

• 원문: arxiv.org/abs/2305.10601 (2023 · Shunyu Yao 외)