생각의 나무

Tree of Thoughts; 생각의 나무
언어 모델이 중간 추론 단계(생각)를 여러 갈래로 만들어 스스로 평가하고, 너비 우선·깊이 우선 탐색으로 유망한 갈래를 고르거나 되돌아가며 문제를 푸는 추론 프레임워크

생각의 나무(Tree of Thoughts, ToT)는 2023년 5월 프린스턴 대학교와 구글 딥마인드 연구진(Shunyu Yao 외)이 발표하고 NeurIPS 2023에 실린 대형 언어 모델 추론 방식이다. 사고 사슬(CoT)이 왼쪽에서 오른쪽으로 한 줄의 추론만 쓰는 데 비해, ToT는 문제 풀이를 "생각"이라는 중간 단계들의 나무로 보고 언어 모델 자신을 후보 생성기와 평가기로 써서 고전적인 탐색 알고리즘을 돌린다. 24 게임에서 GPT-4의 사고 사슬 프롬프팅은 4%만 풀었지만 ToT는 74%를 풀었다.^[1]

논문은 사람의 빠르고 연상적인 "시스템 1"과 느리고 숙고하는 "시스템 2"라는 이중 처리 이론, 그리고 1950년대 앨런 뉴얼과 허버트 사이먼이 문제 해결을 조합적 문제 공간에서의 탐색으로 본 관점을 출발점으로 삼았다. 토큰을 하나씩 고르는 언어 모델은 시스템 1에 가깝고, 여기에 여러 대안을 유지하며 앞을 내다보고 되돌아가는 시스템 2식 계획을 더하자는 것이다.^[1] 같은 주에 Jieyi Long도 같은 이름(Tree-of-Thought)의 방식을 독립적으로 발표했는데, 프롬프터 에이전트, 검사 모듈, 기억 모듈, ToT 제어기를 둔 시스템으로 스도쿠를 풀었다.^[2]

앞선 방식과의 관계

입력 $x$ , 출력 $y$ , 언어 모델 $p_{θ}$ , 중간 생각을 $z_{1}, \dots, z_{n}$ 이라 하자.^[1]

입출력(IO) 프롬프팅: $y \sim p_{θ} (y ∣ x)$
사고 사슬(CoT): $z_{i} \sim p_{θ} (z_{i} ∣ x, z_{1 \dots i - 1})$ 를 차례로 뽑은 뒤 $y \sim p_{θ} (y ∣ x, z_{1 \dots n})$
자기 일관성(CoT-SC): 사고 사슬을 $k$ 번 독립 표본 추출하고 가장 많이 나온 답을 고른다. $\hat{y} = {a r g m a x}_{y} \sum_{j = 1}^{k} 𝟏 [y^{(j)} = y]$ . 사고 사슬의 탐욕 디코딩을 대체하는 디코딩 전략으로 제안되었고 GSM8K에서 정확도를 17.9%p 올렸다.^[3] 다만 갈래들은 끝까지 독립적이고, 중간 단계에서 서로 비교하거나 되돌아가지 않는다.
ToT: 매 단계 여러 생각을 만들고 평가해 일부만 남긴다. IO, CoT, CoT-SC는 깊이나 너비가 제한된 ToT의 특수한 경우로 볼 수 있다.^[1]

구성 요소

ToT를 한 문제에 적용하려면 네 가지를 정한다. 나무의 각 노드는 상태 $s = [x, z_{1 \dots i}]$ , 즉 입력과 지금까지의 생각들이다.^[1]

요소	선택지	논문의 예
1. 생각의 단위	모델이 서로 다른 후보를 여럿 낼 만큼 작고, 그 가치를 평가할 수 있을 만큼 커야 한다	24 게임: 식 한 줄. 창작 글쓰기: 문단 계획 하나. 크로스워드: 단어 몇 개
2. 생각 생성기 $G (p_{θ}, s, k)$	(a) 사고 사슬 프롬프트로 i.i.d. 표본 $k$ 개: 생각의 공간이 넓을 때 다양성 확보 (b) 제안(propose) 프롬프트 하나로 후보 $k$ 개를 한 번에 나열: 공간이 좁을 때 중복 방지	창작은 (a), 24 게임과 크로스워드는 (b)
3. 상태 평가기 $V (p_{θ}, S)$	(a) 상태마다 따로 값 매기기(1~10점이나 sure/likely/impossible) (b) 여러 상태를 한꺼번에 보여 주고 가장 유망한 것에 투표	24 게임: (a), 크로스워드: (a), 창작: (b)
4. 탐색 알고리즘	너비 우선 탐색(BFS): 단계마다 상위 $b$ 개 유지 / 깊이 우선 탐색(DFS): 가장 유망한 갈래로 끝까지, 가망 없으면 가지치기 후 되돌아감	24 게임·창작: BFS, 크로스워드: DFS. A*, 몬테카를로 트리 탐색은 후속 과제로 남김

평가기는 완벽할 필요가 없다. 몇 단계 앞을 빨리 시뮬레이션해 보거나("5, 5, 14면 5+5+14로 24가 된다"), 상식으로 가망 없는 상태를 지우는("1, 2, 3으로는 너무 작아 24가 안 된다") 정도의 근사 휴리스틱이면 된다. 같은 평가를 여러 번 샘플링해 합치면 비용을 더 쓰는 대신 안정성이 오른다.

탐색 알고리즘

너비 우선 탐색(논문 알고리즘 1)은 다음과 같다. $T$ 는 단계 수, $b$ 는 단계마다 남기는 상태 수다.

$S_{0} = {x}, S'_{t} = {[s, z] ∣ s \in S_{t - 1}, z \in G (p_{θ}, s, k)}, S_{t} = {a r g m a x}_{S \subset S'_{t}, | S | = b} \sum_{s \in S} V (p_{θ}, S'_{t}) (s)$

깊이 우선 탐색(알고리즘 2)은 후보를 평가값 순으로 하나씩 내려가다가, 평가값이 문턱값 $v_{th}$ 이하면 그 아래를 잘라 내고 부모로 돌아가 다음 후보를 본다.

최소 구현

아래 tot_bfs는 생성기와 평가기를 함수로 받는 너비 우선 ToT다. 실제로는 두 함수가 언어 모델을 부른다. 예를 들어 24 게임 공개 구현은 제안 프롬프트로 "4 + 9 = 13 (left: 10 13 13)" 같은 다음 단계를 나열하게 하고, 평가 프롬프트를 3번 샘플링해 sure, likely, impossible에 각각 20, 1, 0.001점을 줘 더한다. 단계마다 상위 5개를 남긴다.^[4] 아래 시험 코드는 동작 확인을 위해 두 함수를 프로그램으로 대신했다(평가기는 남은 수로 24를 만들 수 있는지 끝까지 계산해 보는 식으로 "앞을 내다보는" 언어 모델 평가를 흉내 낸다). 입력 4, 9, 10, 13에서 $(4 - 10) \times (9 - 13) = 24$ 를 찾는다.

import heapq, itertools

def tot_bfs(x, propose, value, steps, breadth):
    """propose(s): 다음 생각 후보 목록, value(s): 상태 점수(클수록 유망)"""
    frontier = [x]
    for _ in range(steps):
        candidates = [c for s in frontier for c in propose(s)]
        if not candidates:
            break
        frontier = heapq.nlargest(breadth, candidates, key=value)  # 상위 b개만 남김
    return max(frontier, key=value)

# 24 게임 시험용: 상태 = (남은 수, 지금까지 쓴 식)
def propose(state):
    nums, hist = state
    out = []
    for i, j in itertools.permutations(range(len(nums)), 2):
        a, b = nums[i], nums[j]
        rest = [n for k, n in enumerate(nums) if k not in (i, j)]
        for op, r in (("+", a + b), ("-", a - b), ("*", a * b), ("/", a / b if b else None)):
            if r is not None:
                out.append((tuple(rest + [r]), hist + [f"{a:g}{op}{b:g}={r:g}"]))
    return out

def reachable(nums):        # 남은 수로 24를 만들 수 있는지 끝까지 확인
    if len(nums) == 1:
        return abs(nums[0] - 24) < 1e-6
    return any(reachable(s) for s, _ in propose((nums, [])))

def value(state):           # 논문의 sure/likely/impossible 판정을 흉내 낸 점수
    nums, _ = state
    if len(nums) <= 3:
        return 1.0 if reachable(nums) else 0.0
    return 0.5

print(tot_bfs(((4, 9, 10, 13), []), propose, value, steps=3, breadth=5))
# ((24,), ['4-10=-6', '9-13=-4', '-6*-4=24'])

실험 결과

모두 GPT-4를 썼다.^[1]

과제	방법	결과
24 게임(4nums.com 1,362문제 중 사람 풀이 시간 기준 어려운 901~1,000번, 성공률)	IO 프롬프팅	7.3%
	CoT 프롬프팅	4.0%
	CoT-SC( $k = 100$ )	9.0%
	IO 100번 중 최선(오라클)	33%
	CoT 100번 중 최선(오라클)	49%
	ToT( $b = 1$ )	45%
	ToT( $b = 5$ )	74%
5×5 미니 크로스워드(20문제)	IO, CoT	단어 단위 성공률 16% 미만
5×5 미니 크로스워드(20문제)	ToT(DFS, 최대 100단계)	단어 단위 60%, 20문제 중 4문제 완전 해결

24 게임에서 CoT 표본의 약 60%는 첫 단계(첫 식 세 단어)를 쓰자마자 이미 실패가 정해졌다. 왼쪽에서 오른쪽으로만 쓰는 디코딩의 약점을 보여 준다.
창작 글쓰기(무작위 문장 4개로 끝나는 문단 4개 쓰기)에서 GPT-4가 매긴 일관성 점수(10점 만점)는 IO 6.19, CoT 6.93, ToT 7.56이었다.

비용

24 게임	생성/프롬프트 토큰	문제당 비용	성공률
IO(100번 중 최선)	1.8k / 1.0k	0.13달러	33%
CoT(100번 중 최선)	6.7k / 2.2k	0.47달러	49%
ToT	5.5k / 1.4k	0.74달러	74%

^[1] 당시 GPT-4 가격 기준이다. ToT는 CoT 100번과 비슷한 생성 토큰으로 더 높은 성공률을 냈지만, 한 번의 CoT보다는 수십 배 비싸다. 창작 글쓰기에서는 생성 토큰과 비용이 IO의 약 5배였다.

생각의 그래프와 비교

생각의 그래프(Graph of Thoughts, GoT, AAAI 2024)는 생각을 임의의 방향 그래프로 확장했다. 정점은 생각, 간선은 의존 관계다. 나무에서는 불가능한 집계(여러 생각을 하나로 합치기, 예: 부분 정렬 결과 병합)와 정제(한 생각을 고리로 되먹여 고치기)를 넣었다. 정렬 과제에서 ToT보다 품질을 62% 높이면서 비용을 31% 넘게 줄였다고 보고했다.^[5]

GoT 논문은 생각 하나에 도달하는 데 거치는 단계 수(지연)와 그 생각에 기여할 수 있는 이전 생각의 수(부피, volume)로 방식들을 비교했다. 생각 $N$ 개, 분기 수 $k$ 일 때 다음과 같다.^[5]

방식	구조	중간 평가·되돌아가기	생각 합치기	지연	부피
사고 사슬(CoT)	사슬 하나	없음	없음	$N$	$N$
자기 일관성(CoT-SC)	독립 사슬 $k$ 개	없음(마지막 투표만)	최종 답 투표	$N / k$	$N / k$
생각의 나무(ToT)	나무	있음	없음	$\log_{k} N$	$O (\log_{k} N)$
생각의 그래프(GoT)	방향 그래프	있음	있음(집계)	$\log_{k} N$	$N$

GoT는 하위 문제로 나눠 풀고 합칠 수 있는 과제(정렬, 집합 연산, 문서 병합)에 잘 맞고, ToT는 단계마다 선택지를 고르고 막다른 길에서 돌아와야 하는 탐색형 과제(퍼즐, 계획)에 맞는다. 자기 일관성은 가장 싸고 구현이 쉬워서, 답이 하나로 정해지는 수학·상식 문제의 기본 선택지다.

한계와 이후

비용: 단계마다 생성과 평가 호출이 여러 번 들어가 토큰과 지연이 크게 늘어난다. 논문도 GPT-4가 이미 잘 푸는 과제에는 필요 없을 수 있다고 밝혔다.^[1]
과제별 설계: 생각의 단위, 제안·평가 프롬프트, 탐색 방식을 문제마다 사람이 정해야 한다. 범용 챗봇에 그대로 붙이기 어렵다.
평가기 의존: 크로스워드에서 평가기가 GPT-4가 모르는 옛 단어를 "불가능"으로 잘라 정답 경로를 버리는 일이 있었다.^[1]
이후 흐름: 논문은 다음 문단 고르기 같은 ToT식 반사실적 의사 결정으로 언어 모델을 미세 조정하는 방향을 과제로 남겼다.^[1] 이후 나온 추론 모델은 외부 탐색 프레임워크 없이, 강화 학습으로 긴 사고 사슬 안에서 여러 풀이를 시도하고 고쳐 나가도록 훈련된다.

같이 보기

각주

↑ ^1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, Karthik Narasimhan, 〈Tree of Thoughts: Deliberate Problem Solving with Large Language Models〉, NeurIPS 2023. arXiv:2305.10601
↑ Jieyi Long, 〈Large Language Model Guided Tree-of-Thought〉, 2023. arXiv:2305.08291
↑ Xuezhi Wang 외, 〈Self-Consistency Improves Chain of Thought Reasoning in Language Models〉, ICLR 2023. arXiv:2203.11171
↑ princeton-nlp/tree-of-thought-llm, GitHub.
↑ ^5.0 ^5.1 Maciej Besta 외, 〈Graph of Thoughts: Solving Elaborate Problems with Large Language Models〉, AAAI 2024. arXiv:2308.09687

참고 문헌

[tot-1] 1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, Karthik Narasimhan, 〈Tree of Thoughts: Deliberate Problem Solving with Large Language Models〉, NeurIPS 2023. arXiv:2305.10601

[long-2] Jieyi Long, 〈Large Language Model Guided Tree-of-Thought〉, 2023. arXiv:2305.08291

[sc-3] Xuezhi Wang 외, 〈Self-Consistency Improves Chain of Thought Reasoning in Language Models〉, ICLR 2023. arXiv:2203.11171

[repo-4] rinceton-nlp/tree-of-thought-llm, GitHub.

[got-5] 5.0 ^5.1 Maciej Besta 외, 〈Graph of Thoughts: Solving Elaborate Problems with Large Language Models〉, AAAI 2024. arXiv:2308.09687

[1]

[2]

[3]

[4]

[5]