Yao, Shunyu, et al. "Tree of thoughts: Deliberate problem solving with large language models." Advances in neural information processing systems 36 (2023): 11809-11822.

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Shunyu Yao<br>Princeton University

Dian Yu<br>Google DeepMind

Jeffrey Zhao<br>Google DeepMind

Izhak Shafran<br>Google DeepMind

Thomas L. Griffiths<br>Princeton University

Yuan Cao<br>Google DeepMind

Karthik Narasimhan<br>Princeton University

Abstract

Language Model(LM)은 다양한 task에서 일반적인 문제 해결을 위해 점점 더 많이 배포되고 있지만, 추론(inference) 시에는 여전히 토큰 수준의 좌-우(left-to-right) 의사결정 과정에 국한되어 있다. 이는 LM이 탐색(exploration), 전략적 예측(strategic lookahead)이 필요하거나 초기 결정이 중요한 역할을 하는 task에서 부족함을 보일 수 있음을 의미한다. 이러한 문제들을 극복하기 위해 우리는 **언어 모델 추론을 위한 새로운 프레임워크인 "Tree of Thoughts" (ToT)**를 소개한다. ToT는 언어 모델에 prompt를 주는 인기 있는 "Chain of Thought" 접근 방식을 일반화하여, 문제 해결을 위한 중간 단계 역할을 하는 일관된 텍스트 단위("thoughts")에 대한 탐색을 가능하게 한다. ToT는 LM이 여러 다른 추론 경로를 고려하고 선택 사항을 자체 평가하여 다음 행동 방침을 결정할 수 있도록 하며, 필요할 때 예측(looking ahead)하거나 되돌아가기(backtracking)를 통해 전역적인(global) 선택을 할 수 있도록 한다. 우리의 실험은 ToT가 비자명한(non-trivial) 계획 또는 탐색이 필요한 세 가지 새로운 task(Game of 24, Creative Writing, Mini Crosswords)에서 언어 모델의 문제 해결 능력을 크게 향상시킨다는 것을 보여준다. 예를 들어, Game of 24에서 Chain of Thought prompting을 사용한 GPT-4는 task의 4%만 해결했지만, 우리의 방법은 74%의 성공률을 달성했다. 모든 prompt가 포함된 코드 저장소: https://github.com/princeton-nlp/tree-of-thought-llm.

1 Introduction

원래 텍스트 생성을 위해 설계된 GPT [25, 26, 1, 23] 및 PaLM [5]과 같은 **확장된 버전의 Language Model (LM)**은 수학적, 상징적, 상식적, 지식 추론을 요구하는 점점 더 광범위한 task를 수행할 수 있는 능력을 보여주었다. 이 모든 발전의 근간에 여전히 토큰 수준의 결정을 하나씩, 그리고 좌에서 우로 생성하는 원래의 autoregressive 메커니즘이 있다는 것은 놀라운 일일 수 있다. 과연 이러한 단순한 메커니즘이 LM이 **범용적인 문제 해결사(general problem solver)**로 발전하는 데 충분할까? 만약 그렇지 않다면, 현재의 패러다임에 도전할 문제는 무엇이며, 대안적인 메커니즘은 무엇이어야 할까?

인간 인지에 대한 문헌은 이러한 질문에 답할 몇 가지 단서를 제공한다. "이중 과정(dual process)" 모델에 대한 연구는 사람들이 의사결정에 참여하는 두 가지 모드, 즉 **빠르고 자동적이며 무의식적인 모드("System 1")**와 **느리고 신중하며 의식적인 모드("System 2")**를 가지고 있음을 시사한다 [30, 31, 16, 15]. 이 두 가지 모드는 이전에 머신러닝에서 사용되는 다양한 수학적 모델과 연결되어 왔다. 예를 들어, 인간 및 다른 동물들의 강화 학습에 대한 연구는 그들이 연관적인 "model free" 학습 또는 더 신중한 "model based" 계획에 참여하는 상황을 탐구했다 [7]. LM의 단순한 연관적 토큰 수준 선택은 "System 1"을 연상시키며, 따라서 다음과 같은 더 신중한 "System 2" 계획 프로세스의 증강으로부터 이점을 얻을 수 있다: (1) 단순히 하나를 선택하는 대신 현재 선택에 대한 다양한 대안을 유지하고 탐색하며, (2) 현재 상태를 평가하고 적극적으로 앞을 내다보거나 되돌아가서 더 전역적인 결정을 내리는 것.

Figure 1: LLM을 이용한 문제 해결의 다양한 접근 방식을 보여주는 개략도. 각 직사각형 상자는 **사고(thought)**를 나타내며, 이는 문제 해결을 위한 중간 단계 역할을 하는 일관된 언어 시퀀스이다. 사고가 어떻게 생성되고, 평가되며, 탐색되는지에 대한 구체적인 예시는 Figures 2|4|6에서 확인할 수 있다.

이러한 계획 프로세스를 설계하기 위해 우리는 인공지능(및 인지 과학)의 기원으로 돌아가, 1950년대부터 Newell, Shaw, Simon이 탐구한 계획 프로세스에서 영감을 얻었다 [21, 22]. Newell과 동료들은 문제 해결 [21]을 조합 문제 공간(combinatorial problem space)을 통한 탐색으로 특징지었으며, 이는 트리(tree)로 표현된다. 따라서 우리는 Language Model을 이용한 범용 문제 해결을 위한 Tree of Thoughts (ToT) 프레임워크를 제안한다. Figure 1이 보여주듯이, 기존 방법들(아래에서 자세히 설명)이 문제 해결을 위해 연속적인 언어 시퀀스를 샘플링하는 반면, ToT는 사고의 트리(tree of thoughts)를 적극적으로 유지한다. 여기서 각 사고(thought)는 문제 해결을 위한 중간 단계 역할을 하는 일관된 언어 시퀀스이다 (Table 1). 이러한 고수준의 의미 단위는 LM이 언어로 구현된 신중한 추론 프로세스를 통해 다양한 중간 사고들이 문제 해결에 기여하는 진행 상황을 스스로 평가할 수 있도록 한다 (Figures 2|4|6). 이전의 탐색 휴리스틱이 프로그래밍되거나 학습되었던 것과 달리, LM의 자기 평가 및 숙고를 통한 이러한 탐색 휴리스틱 구현은 새롭다. 마지막으로, 우리는 다양한 사고를 생성하고 평가하는 이러한 언어 기반 능력을 너비 우선 탐색(BFS) 또는 깊이 우선 탐색(DFS)과 같은 탐색 알고리즘과 결합한다. 이 알고리즘들은 미리 보기(lookahead) 및 되추적(backtracking)을 통해 사고의 트리를 체계적으로 탐색할 수 있도록 한다.

경험적으로, 우리는 최신 Language Model인 GPT-4 [23]로도 기존 LM 추론 방법으로는 해결하기 어려운 세 가지 새로운 문제를 제안한다: Game of 24, Creative Writing, Crosswords (Table 1). 이 task들은 연역적, 수학적, 상식적, 어휘 추론 능력과 체계적인 계획 또는 탐색을 통합하는 방식을 요구한다. 우리는 ToT가 다양한 수준의 사고, 사고를 생성하고 평가하는 다양한 방식, 그리고 다양한 문제의 특성에 적응하는 다양한 탐색 알고리즘을 지원할 만큼 충분히 일반적이고 유연하여 이 세 가지 task 모두에서 우수한 결과를 얻음을 보여준다. 또한 우리는 체계적인 ablation을 통해 이러한 선택이 모델 성능에 어떻게 영향을 미치는지 분석하고, LM을 더 잘 학습하고 사용하는 미래 방향에 대해 논의한다.

2 Background

우리는 먼저 문제 해결을 위해 대규모 language model을 사용하는 기존 방법들을 공식화한다. 이는 우리의 접근 방식에 영감을 주었으며, 이후 비교 대상이 된다. 우리는 파라미터 $\theta$를 가진 사전학습된 LM을 $p_{\theta}$로, 언어 시퀀스를 소문자 $x, y, z, s, \cdots$로 표기한다. 즉, $x = (x[1], \cdots, x[n])$이며 각 $x[i]$는 토큰이므로 $p_{\theta}(x) = \prod_{i=1}^{n} p_{\theta}(x[i] \mid x[1 \ldots i])$이다. 대문자 $S, \cdots$는 언어 시퀀스의 집합을 나타내는 데 사용한다.

Input-output (IO) prompting은 LM을 사용하여 문제 입력 $x$를 출력 $y$로 변환하는 가장 일반적인 방법이다: $y \sim p_{\theta}\left(y \mid \operatorname{prompt}_{I O}(x)\right)$. 여기서 $\operatorname{prompt}_{I O}(x)$는 입력 $x$를 task 지시사항 및/또는 few-shot input-output 예시와 함께 묶는 역할을 한다. 간단히 $p_{\theta}^{\text {prompt }}$ (output $\mid$ input) $= p_{\theta}\left(\right.$ output $\mid$ prompt(input))로 표기하면, IO prompting은 $y \sim p_{\theta}^{I O}(y \mid x)$로 공식화될 수 있다.

Chain-of-thought (CoT) prompting [38]은 입력 $x$에서 출력 $y$로의 매핑이 비자명한 경우(예: $x$가 수학 문제이고 $y$가 최종 숫자 답인 경우)를 해결하기 위해 제안되었다. 핵심 아이디어는 $x$와 $y$를 연결하는 일련의 사고 과정 $z_{1}, \cdots, z_{n}$을 도입하는 것이다. 여기서 각 $z_{i}$는 문제 해결을 향한 의미 있는 중간 단계 역할을 하는 일관된 언어 시퀀스이다(예: $z_{i}$는 수학 QA의 중간 방정식일 수 있다). CoT로 문제를 해결하기 위해, 각 사고 과정 $z_{i} \sim p_{\theta}^{C o T}\left(z_{i} \mid x, z_{1 \cdots i-1}\right)$는 순차적으로 샘플링된 다음, 출력 $y \sim p_{\theta}^{C o T}\left(y \mid x, z_{1 \cdots n}\right)$가 생성된다. 실제로는 $\left[z_{1 \cdots n}, y\right] \sim p_{\theta}^{C o T}\left(z_{1 \cdots n}, y \mid x\right)$가 연속적인 언어 시퀀스로 샘플링되며, 사고 과정의 분해(예: 각 $z_{i}$가 구, 문장 또는 단락인지 여부)는 모호하게 남겨진다.

Self-consistency with CoT (CoT-SC) [36]는 $k$개의 i.i.d. 사고 과정 체인을 샘플링하는 앙상블 접근 방식이다: $\left[z_{1 \cdots n}^{(i)}, y^{(i)}\right] \sim p_{\theta}^{C o T}\left(z_{1 \cdots n}, y \mid x\right)(i=1 \cdots k)$, 그런 다음 가장 빈번한 출력을 반환한다: $\arg \max _{y} \#\left\{i \mid y^{(i)}=y\right\}$. CoT-SC는 CoT를 개선하는데, 이는 일반적으로 동일한 문제에 대해 다른 사고 과정이 존재하고(예: 동일한 정리를 증명하는 다른 방법), 더 풍부한 사고 과정을 탐색함으로써 출력 결정이 더 신뢰할 수 있기 때문이다. 그러나 각 체인 내에서는 다른 사고 단계에 대한 국소적인 탐색이 없으며, "가장 빈번한" 휴리스틱은 출력 공간이 제한적일 때만 적용된다(예: 다지선다형 QA).

3 Tree of Thoughts: Deliberate Problem Solving with LM

진정한 문제 해결 과정은 사용 가능한 정보를 반복적으로 활용하여 탐색을 시작하고, 이 탐색을 통해 더 많은 정보가 드러나며, 마침내 해결책에 도달하는 방법이 발견될 때까지 계속된다. -- Newell et al. [21]

인간의 문제 해결에 대한 연구는 사람들이 **조합적 문제 공간(combinatorial problemspace)**을 탐색한다고 제안한다. 이 공간은 노드가 부분적인 해결책을 나타내고, 브랜치가 이를 수정하는 연산자(operator)에 해당하는 트리 구조이다 [21, 22]. 어떤 브랜치를 선택할지는 문제 공간을 탐색하고 문제 해결자를 해결책으로 안내하는 데 도움이 되는 휴리스틱(heuristics)에 의해 결정된다. 이러한 관점은 Language Model(LM)을 사용하여 일반적인 문제를 해결하는 기존 접근 방식의 두 가지 주요 단점을 강조한다:

1. 국소적으로(Locally), 이들은 사고 과정 내에서 다양한 연속(continuation)을 탐색하지 않는다 (트리의 브랜치에 해당).
2. 전역적으로(Globally), 이들은 이러한 다양한 옵션을 평가하는 데 도움이 되는 어떤 종류의 계획, lookahead, 또는 backtracking도 통합하지 않는다 (인간 문제 해결의 특징으로 보이는 휴리스틱 기반 탐색).

이러한 단점을 해결하기 위해 우리는 **Tree of Thoughts (ToT)**를 소개한다. ToT는 LM이 사고(thought)를 통해 여러 추론 경로를 탐색할 수 있도록 하는 패러다임이다 (Figure 1(c)). ToT는 모든 문제를 트리에 대한 탐색으로 구성하며, 여기서 **각 노드는 입력과 지금까지의 사고 시퀀스를 포함하는 부분적인 해결책을 나타내는 상태 $s=\left[x, z_{1} \cdots i\right]$**이다. ToT의 특정 구현은 다음 네 가지 질문에 답하는 것을 포함한다:

1. 중간 과정을 사고 단계(thought steps)로 어떻게 분해할 것인가?

2. 각 상태에서 잠재적인 사고를 어떻게 생성할 것인가?

3. 상태를 휴리스틱하게 어떻게 평가할 것인가?

4. 어떤 탐색 알고리즘을 사용할 것인가?

5. 사고 분해 (Thought decomposition). CoT(Chain-of-Thought)는 명시적인 분해 없이 사고를 일관되게 샘플링하는 반면, ToT는 문제의 속성을 활용하여 중간 사고 단계를 설계하고 분해한다. Table 1에서 보듯이, 문제에 따라 사고는 몇 단어(Crosswords), 한 줄의 방정식(Game of 24), 또는 전체 단락의 글쓰기 계획(Creative Writing)이 될 수 있다. 일반적으로, 사고는 LM이 유망하고 다양한 샘플을 생성할 수 있을 만큼 "작아야" 하지만(예: 책 전체를 생성하는 것은 일반적으로 너무 "커서" 일관성이 떨어짐), LM이 문제 해결에 대한 전망을 평가할 수 있을 만큼 "커야" 한다(예: 하나의 토큰을 생성하는 것은 일반적으로 평가하기에 너무 "작음").

6. 사고 생성기 $G\left(p_{\theta}, s, k\right)$ (Thought generator). 트리 상태 $s=\left[x, z_{1} \cdots i\right]$가 주어졌을 때, 다음 사고 단계에 대해 $k$개의 후보를 생성하는 두 가지 전략을 고려한다: (a) CoT prompt에서 i.i.d. 사고 샘플링 (Creative Writing, Figure 4): $z^{(j)} \sim p_{\theta}^{C o T}\left(z_{i+1} \mid s\right)=p_{\theta}^{C o T}\left(z_{i+1} \mid x, z_{1 \cdots i}\right)(j=1 \cdots k)$. 이 방법은 사고 공간이 풍부할 때(예: 각 사고가 단락일 때) 더 잘 작동하며, i.i.d. 샘플은 다양성을 유도한다. (b) "propose prompt"를 사용하여 사고를 순차적으로 제안 (Game of 24, Figure 2, Crosswords, Figure 6): $\left[z^{(1)}, \cdots, z^{(k)}\right] \sim p_{\theta}^{\text {propose }}\left(z_{i+1}^{(1 \cdots k)} \mid s\right)$. 이 방법은 사고 공간이 더 제약적일 때(예: 각 사고가 단어 하나 또는 한 줄일 때) 더 잘 작동하며, 동일한 맥락에서 다른 사고를 제안함으로써 중복을 피한다.

7. 상태 평가기 $V\left(p_{\theta}, S\right)$ (State evaluator). 서로 다른 상태들의 frontier가 주어졌을 때, 상태 평가기는 문제 해결을 향한 진행 상황을 평가하며, 탐색 알고리즘이 어떤 상태를 계속 탐색하고 어떤 순서로 탐색할지 결정하는 휴리스틱 역할을 한다. 휴리스틱은 탐색 문제를 해결하는 표준적인 접근 방식이지만, 일반적으로 프로그래밍되거나(예: DeepBlue [3]) 학습된다(예: AlphaGo [29]). 우리는 LM을 사용하여 상태에 대해 의도적으로 추론하는 세 번째 대안을 제안한다. 적용 가능한 경우, 이러한 의도적인 휴리스틱은 프로그래밍된 규칙보다 더 유연하고, 학습된 모델보다 샘플 효율적일 수 있다. 사고 생성기와 유사하게, 우리는 상태를 독립적으로 또는 함께 평가하는 두 가지 전략을 고려한다: (a) 각 상태를 독립적으로 평가: $V\left(p_{\theta}, S\right)(s) \sim p_{\theta}^{\text {value }}(v \mid s) \forall s \in S$, 여기서 value prompt는 상태 $s$에 대해 추론하여 스칼라 값 $v$(예: 1-10) 또는 분류(예: sure/likely/impossible)를 생성하며, 이는 휴리스틱하게 값으로 변환될 수 있다. 이러한 평가적 추론의 기준은 문제와 사고 단계에 따라 달라질 수 있다. 본 연구에서는 몇 가지 lookahead 시뮬레이션(예: 5, 5, 14가 $5+5+14$를 통해 24에 도달할 수 있음을 빠르게 확인하거나, "hot_l"이 "_"에 "e"를 채워 "inn"을 의미할 수 있음을 확인)과 상식(예: 123은 24에 도달하기에 너무 작거나, "tzxc"로 시작하는 단어는 없음)을 통한 평가를 탐구한다. 전자는 "좋은" 상태를 촉진할 수 있는 반면, 후자는 "나쁜" 상태를 제거하는 데 도움이 될 수 있다. 이러한 평가는 완벽할 필요는 없으며, 의사 결정에 대략적으로 도움이 되기만 하면 된다. (b) 상태 간 투표 (Vote across states): $V\left(p_{\theta}, S\right)(s)=\mathbb{1}\left[s=s^{*}\right]$, 여기서 "좋은" 상태 $s^{*} \sim p_{\theta}^{\text {vote }}\left(s^{*} \mid S\right)$는 vote prompt에서 $S$의 다른 상태들을 의도적으로 비교하여 투표를 통해 선택된다. 문제 성공을 직접적으로 평가하기 어려울 때(예: 문단 일관성), 대신 다른 부분적인 해결책들을 비교하고 가장 유망한 것에 투표하는 것이 자연스럽다. 이는 "단계별(step-wise)" self-consistency 전략과 유사하며, 즉 "어떤 상태를 탐색할 것인가"를 다중 선택 QA로 간주하고, LM 샘플을 사용하여 투표하는 방식이다. 두 전략 모두에서, 우리는 LM에 여러 번 prompt를 주어 값 또는 투표 결과를 집계하여 시간/자원/비용을 더 충실하고 견고한 휴리스틱과 교환할 수 있다.

Algorithm 1 ToT-BFS( \(x, p_{\theta}, G, k, V, T, b\) ) Algorithm 2 ToT-DFS( \(s, t, p_{\theta}, G, k, V, T, v_{t h}\) )
Require: Input \(x, \mathrm{LM} p_{\theta}\), thought generator \(G() \overline{\text { Require: Current state } s \text {, step } t, \mathrm{LM} p_{\theta} \text {, thought }}\)
    \& size limit \(k\), states evaluator \(V()\), step limit \(T\), generator \(G()\) and size limit \(k\), states evaluator
    breadth limit \(b\). \(\quad V()\), step limit \(T\), threshold \(v_{t h}\)
    \(S_{0} \leftarrow\{x\} \quad\) if \(t>T\) then record output \(G\left(p_{\theta}, s, 1\right)\)
    for \(t=1, \cdots, T\) do end if
        \(S_{t}^{\prime} \leftarrow\left\{[s, z] \mid s \in S_{t-1}, z_{t} \in \mathrm{G}\left(p_{\theta}, s, k\right)\right\} \quad\) for \(s^{\prime} \in G\left(p_{\theta}, s, k\right)\) do \(\quad \triangleright\) sorted candidates
        \(V_{t} \leftarrow V\left(p_{\theta}, S_{t}^{\prime}\right) \quad\) if \(V\left(p_{\theta},\left\{s^{\prime}\right\}\right)(s)>v_{\text {thres }}\) then \(\triangleright\) pruning
        \(S_{t} \leftarrow \arg \max _{S \subset S_{t}^{\prime},|S|=b} \sum_{s \in S} V_{t}(s) \quad \operatorname{DFS}\left(s^{\prime}, t+1\right)\)
    end for end if
    return \(G\left(p_{\theta}, \arg \max _{s \in S_{T}} V_{T}(s), 1\right) \quad\) end for

4. 탐색 알고리즘 (Search algorithm). 마지막으로, ToT 프레임워크 내에서는 트리 구조에 따라 다양한 탐색 알고리즘을 적용할 수 있다. 우리는 비교적 간단한 두 가지 탐색 알고리즘을 탐구하며, 더 고급 알고리즘(예: A* [11], MCTS [2])은 향후 연구로 남겨둔다: (a) 너비 우선 탐색 (BFS) (Algorithm 1)은 각 단계에서 가장 유망한 $b$개의 상태 집합을 유지한다. 이 방법은 트리 깊이가 제한적이고($T \leq 3$), 초기 사고 단계를 평가하고 작은 집합($b \leq 5$)으로 가지치기할 수 있는 Game of 24 및 Creative Writing에 사용된다. (b) 깊이 우선 탐색 (DFS) (Algorithm 2)은 가장 유망한 상태를 먼저 탐색하며, 최종 출력에 도달하거나($t>T$), 상태 평가기가 현재 $s$에서 문제를 해결하는 것이 불가능하다고 판단할 때까지($V\left(p_{\theta},\{s\}\right)(s) \leq v_{\text {th }}$ for a value threshold $\left.v_{\text {th }}\right)$ 탐색을 계속한다. 후자의 경우, $s$로부터의 서브트리는 탐색과 활용의 균형을 위해 가지치기된다. 두 경우 모두, DFS는 $s$의 부모 상태로 backtracking하여 탐색을 계속한다.

개념적으로, ToT는 LM을 이용한 일반적인 문제 해결 방법으로서 여러 이점을 가진다: (1) 일반성 (Generality). IO, CoT, CoT-SC, 그리고 self-refinement는 ToT의 특수한 경우로 볼 수 있다(즉, 제한된 깊이와 너비의 트리; Figure 1). (2) 모듈성 (Modularity). 기본 LM뿐만 아니라 사고 분해, 생성, 평가 및 탐색 절차는 모두 독립적으로 변경될 수 있다. (3) 적응성 (Adaptability). 다양한 문제 속성, LM 기능 및 자원 제약을 수용할 수 있다. (4) 편의성 (Convenience). 추가 학습이 필요 없으며, 사전학습된 LM만으로 충분하다. 다음 섹션에서는 이러한 개념적 이점이 다양한 문제에서 강력한 실증적 성능으로 어떻게 이어지는지 보여줄 것이다.

4 Experiments

우리는 **state-of-the-art language model인 GPT-4 [23]**를 사용하여 표준 IO prompting 또는 chain-of-thought (CoT) prompting을 사용할 때조차 어려운 세 가지 task를 제안한다. 우리는 사고의 트리(ToT) 내에서 신중한 탐색(deliberate search)이 어떻게 더 나은 결과를 도출하는지를 보여주며, 더 중요하게는 탐색 또는 계획이 필요한 문제를 해결하기 위해 language model을 사용하는 흥미롭고 유망한 새로운 방법을 제시한다. 별도로 명시되지 않는 한, 우리는 샘플링 온도 0.7의 Chat Completion 모드 GPT-4를 사용하여 실험을 수행한다.

Table 1: Task 개요. 입력, 출력, 사고(thought) 예시는 파란색으로 표시되어 있다.

4.1 Game of 24

Game of 24는 4개의 숫자와 기본 산술 연산자(+-*/)를 사용하여 24를 만드는 수학적 추론 챌린지이다. 예를 들어, "491013"이 주어졌을 때, 해답은 "(10-4) * (13-9) = 24"가 될 수 있다.

Figure 2: Game of 24에서의 ToT. LM은 (a) 사고 생성 및 (b) 가치 평가를 위해 prompt된다.

Task Setup. 우리는 4nums.com에서 데이터를 스크랩했으며, 이 사이트에는 인간의 해결 시간에 따라 쉬운 것부터 어려운 것까지 정렬된 1,362개의 게임이 있다. 이 중 상대적으로 어려운 게임인 인덱스 901-1,000번을 테스트에 사용한다. 각 task에 대해, 출력이 24와 같고 입력 숫자를 각각 한 번씩 정확히 사용하는 유효한 방정식이면 성공으로 간주한다. 100개 게임에 대한 성공률을 지표로 보고한다.

Baselines. 우리는 5개의 in-context 예시를 포함하는 표준 input-output (IO) prompt를 사용한다. Chain-of-thought (CoT) prompting의 경우, 각 input-output 쌍에 3개의 중간 방정식을 추가하며, 각 방정식은 남아있는 두 숫자에 대해 연산을 수행한다. 예를 들어, "491013"이 주어졌을 때, 사고 과정은 "13-9 = 4 (남은 숫자: 4410 ); 10-4 = 6 (남은 숫자: 46 ); $4 * 6=24$ (남은 숫자: 24 )"가 될 수 있다. 각 게임에 대해 IO 및 CoT prompting을 100번 샘플링하여 평균 성능을 측정한다. 또한 100개의 CoT 샘플에서 다수결 출력을 취하는 CoT self-consistency baseline과, 최대 10번의 반복으로 IO 샘플 위에 iterative-refine 접근 방식을 고려한다. 각 반복에서, 출력이 올바르지 않으면 LM은 이전 모든 기록을 조건으로 하여 "실수를 반성하고 개선된 답변을 생성"하도록 한다. 이는 방정식의 정확성에 대한 groundtruth 피드백 신호를 사용한다.

ToT Setup. Game of 24를 ToT 프레임워크에 맞추기 위해, 사고 과정을 각각 중간 방정식인 3단계로 분해하는 것이 자연스럽다. Figure 2(a)에 나타난 바와 같이, 각 tree node에서 우리는 남은 숫자를 추출하고 LM에게 가능한 다음 단계를 제안하도록 prompt한다. 동일한 "propose prompt"는 4개의 입력 숫자를 가진 하나의 예시만 포함하지만, 3가지 사고 단계 모두에 사용된다. 우리는 ToT에서 **너비 우선 탐색(BFS)**을 수행하며, 각 단계에서 가장 좋은 $b=5$개의 후보를 유지한다. ToT에서 의도적인 BFS를 수행하기 위해, Figure 2(b)에 나타난 바와 같이, LM에게 각 사고 후보를 24에 도달할 수 있는지 여부에 따라 "확실함/아마도/불가능함"으로 평가하도록 prompt한다. 목표는 몇 번의 lookahead 시도 내에서 판정될 수 있는 올바른 부분 해답을 촉진하고, "너무 크거나 작음"과 같은 상식에 기반하여 불가능한 부분 해답을 제거하며, 나머지는 "아마도"로 유지하는 것이다. 각 사고에 대해 3번 값을 샘플링한다.

Table 2: Game of 24 결과.

Figure 3: Game of 24 (a) 스케일 분석 및 (b) 오류 분석.

Results. Table 2에 나타난 바와 같이, IO, CoT, CoT-SC prompting 방법은 이 task에서 저조한 성능을 보이며 각각 7.3%, 4.0%, 9.0%의 성공률을 달성했다. 이와 대조적으로, ToT는 너비 $b=1$일 때 이미 45%의 성공률을 달성했으며, $b=5$일 때는 74%를 달성했다. 우리는 또한 IO/CoT에 대한 oracle 설정을 고려했는데, 이는 $k$개 샘플 중 최상의 샘플($1 \leq k \leq 100$)을 사용하여 성공률을 계산하는 방식이다. IO/CoT (best of k)와 ToT를 비교하기 위해, ToT에서 $b=1 \cdots 5$에 걸쳐 task당 방문한 tree node 수를 계산하고, Figure 3(a)의 5가지 성공률을 매핑하여 IO/CoT (best of k)를 bandit에서 $k$개의 node를 방문하는 것으로 간주했다. 놀랍게도 CoT는 IO보다 더 잘 확장되며, 100개의 CoT 샘플 중 최상은 49%의 성공률을 달성했지만, ToT에서 더 많은 node를 탐색하는 것($b>1$)보다는 여전히 훨씬 낮다.

Error analysis. Figure 3(b)는 CoT 및 ToT 샘플이 task에 실패하는 단계를 분석한다. 즉, CoT에서는 사고(thought)가, ToT에서는 모든 $b$개의 사고가 유효하지 않거나 24에 도달할 수 없는 경우이다. 특히, CoT 샘플의 약 60%는 첫 번째 단계, 또는 첫 세 단어(예: "4+9")를 생성한 후 이미 task에 실패했다. 이는 직접적인 좌에서 우로의 디코딩(left-to-right decoding) 방식의 문제점을 강조한다.

4.2 Creative writing

다음으로, 우리는 입력으로 4개의 무작위 문장을 주고, 출력은 각 문장으로 끝나는 4개의 단락으로 구성된 일관성 있는 글이 되도록 하는 창의적 글쓰기 task를 고안했다. 이러한 task는 open-ended하고 탐색적이며, 창의적 사고와 고수준 계획 능력을 요구한다.

Task 설정. 우리는 randomwordgenerator.com에서 무작위 문장을 샘플링하여 100개의 입력을 구성했으며, 각 입력 제약 조건에 대한 정답(groundtruth) 글은 존재하지 않는다. GPT-4가 대부분의 경우 입력 제약 조건을 잘 따르는 것을 확인했으므로, 우리는 글의 일관성(coherency) 평가에 중점을 두었다. 평가는 두 가지 방식으로 진행되었다:

• GPT-4 zero-shot prompt를 사용하여 1-10점의 스칼라 점수를 부여하는 방식,
• 인간 평가를 통해 다른 방법론으로 생성된 글 쌍을 비교하는 방식.

전자의 경우, 각 task 출력에 대해 5개의 점수를 샘플링하여 평균을 냈으며, 이 5개의 점수는 일반적으로 일관성이 있었고, 출력별 평균 표준 편차는 약 0.56이었다. 후자의 경우, 저자 중 일부가 블라인드 스터디에 참여하여 CoT와 ToT로 생성된 글 쌍의 일관성을 비교했으며, 100개의 입력에 대해 글의 순서는 무작위로 뒤바뀌었다.

기준 모델 (Baselines). task의 창의적인 특성을 고려하여, IO와 CoT prompt 모두 zero-shot으로 설정되었다. IO는 LM이 입력 제약 조건에 따라 일관성 있는 글을 직접 생성하도록 prompt하는 반면, CoT는 LM이 먼저 간략한 계획을 세운 다음 글을 작성하도록 prompt한다. 즉, 계획이 중간 사고 단계(intermediate thought step)의 역할을 한다. 우리는 각 task당 10개의 IO 및 CoT 샘플을 생성했다. 또한, 각 task에 대해 무작위 IO 샘플 위에 반복-정제(iterative-refine) 방법($k \leq 5$)을 고려했다. 이 방법에서는 LM이 입력 제약 조건과 마지막으로 생성된 글을 조건으로 받아, 글이 이미 "완벽하게 일관성 있는지"를 판단하고, 그렇지 않다면 정제된 글을 생성한다.

ToT 설정. 우리는 **깊이 2 (중간 사고 단계는 1개)**의 ToT를 구축했다. LM은 먼저 $k=5$개의 계획을 생성하고 가장 좋은 계획에 투표(vote)한 다음 (Figure 4), 유사하게 가장 좋은 계획을 기반으로 $k=5$개의 글을 생성하고 가장 좋은 글에 투표한다. 여기서 **너비 제한(breadth limit) $b=1$**인데, 이는 각 단계에서 하나의 선택만 유지되기 때문이다. 두 단계 모두에서 5개의 투표를 샘플링하기 위해 간단한 zero-shot 투표 prompt ("아래 선택지들을 분석한 다음, 지시에 가장 유망한 것이 무엇인지 결론 내리시오")가 사용된다.

결과. Figure 5(a)는 100개 task에 대한 평균 GPT-4 점수를 보여주는데, ToT(7.56)가 IO(6.19) 및 CoT(6.93)보다 평균적으로 더 일관성 있는 글을 생성하는 것으로 나타났다. 이러한 자동 측정 지표는 노이즈가 있을 수 있지만, Figure 5(b)는 인간 평가를 통해 이 결과를 확인시켜준다. 인간은 100개의 글 쌍 중 41개에서 ToT를 CoT보다 선호했으며, CoT를 ToT보다 선호한 경우는 21개에 불과했다 (나머지 38개 쌍은 "유사하게 일관성 있다"고 판단됨). 마지막으로, 반복-정제(iterative-refine) 방법은 이 자연어 task에서 더 효과적이었는데, IO의 일관성 점수를 6.19에서 7.67로, ToT의 일관성 점수를 7.56에서 7.91로 향상시켰다. 우리는 이를 ToT 프레임워크 내에서 사고(thought)를 생성하는 세 번째 접근 방식으로 볼 수 있다고 생각한다. 즉, 새로운 사고가 i.i.d. 또는 순차적으로 생성되는 대신 이전 사고를 정제하는 과정에서 발생할 수 있다는 것이다.

Figure 4: 무작위로 선택된 창의적 글쓰기 task에서 의도적인 탐색(deliberate search)의 한 단계. 입력이 주어지면, LM은 5개의 다른 계획을 샘플링한 다음, 5번의 투표를 통해 어떤 계획이 가장 좋은지 결정한다. 다수결로 선택된 계획은 동일한 샘플-투표 절차를 거쳐 출력 글을 작성하는 데 사용된다.

Figure 5: 창의적 글쓰기 결과.

Table 3: Mini Crosswords 결과.

4.3 Mini crosswords

Game of 24와 Creative Writing에서 ToT는 비교적 얕은(shallow) 탐색을 요구한다. 최종 결과에 도달하기 위해 최대 3단계의 사고(thought) 과정만 필요하다. 여기서는 자연어를 포함하는 더 어려운 탐색 문제로서 $5 \times 5$ 미니 크로스워드를 탐구한다.
다시 말하지만, 목표는 단순히 task를 해결하는 것이 아니다. 더 일반적인 크로스워드는 LM 대신 대규모 검색(retrieval)을 활용하는 전문화된 NLP 파이프라인 [34]으로 쉽게 해결될 수 있기 때문이다. 대신 우리는 LM이 자체적인 사고를 탐색하고, 의도적인 추론을 휴리스틱으로 사용하여 탐색을 안내하는 일반적인 문제 해결자로서의 한계를 탐구하고자 한다.

Task 설정.
우리는 156개의 $5 \times 5$ 미니 크로스워드 게임을 포함하는 GooBix에서 데이터를 스크랩한다. 인접한 게임들이 유사한 단서를 포함하고 있음을 관찰했기 때문에, 테스트용으로 인덱스 $1, 6, \cdots, 91, 96$의 20개 게임을 사용하고, **프롬프팅용으로 게임 $136, 141, 146, 151, 156$**을 사용한다. 각 task에 대해 입력은 5개의 가로 단서와 5개의 세로 단서를 설명하며, 출력은 크로스워드를 풀기 위한 $5 \times 5 = 25$개의 글자로 구성된 보드여야 한다. 평가를 위해 우리는 세 가지 성공 수준을 고려한다: 정확한 글자(게임당 25개), 단어(게임당 10개), 그리고 게임의 비율이다.

Baselines.
우리는 IO prompt에 5개의 입력-출력 예시 쌍을 제공하고, CoT prompt에는 추가적으로 h1..5, v1..5 순서로 중간 단어들을 포함한다. 각 prompt를 10개의 샘플에 대해 실행하고 결과를 평균한다.

ToT 설정.
우리는 **깊이 우선 탐색(depth-first search, Algorithm 2)**을 활용한다. 이 탐색은 상태가 더 이상 유망하지 않을 때까지 가장 유망한 다음 단어 단서를 계속 탐색한 다음, 부모 상태로 되돌아가 대체 사고(alternative thoughts)를 탐색한다. 탐색을 다루기 쉽게 하기 위해, 후속 사고는 이미 채워진 단어나 글자를 변경하지 않도록 제약을 두어, ToT가 최대 10개의 중간 단계를 갖도록 한다.
사고 생성을 위해, 각 상태에서 우리는 모든 기존 사고(예: Figure 6(a)의 상태에 대한 "h2.motor; h1.tasks")를 남은 단서에 대한 글자 제약(예: "v1.To heap: tm___;...")으로 변환하고, 다음 단어를 어디에 무엇으로 채울지에 대한 후보를 생성하기 위해 제안 프롬프트(proposal prompt)를 5번 실행한다. 중요하게도, 우리는 LM에게 다른 사고에 대한 신뢰도 수준을 제공하도록 프롬프트하고, 이러한 제안들을 집계하여 탐색할 다음 사고의 정렬된 목록을 얻는다(Figure 6(a)).
상태 평가를 위해, 우리는 유사하게 각 상태를 남은 단서에 대한 글자 제약으로 변환한 다음, 각 단서가 주어진 제약 조건에서 채워질 수 있는지 여부를 평가한다. 만약 남은 단서 중 하나라도 채우는 것이 "불가능"하다고 판단되면(예: "v1. To heap: tm_s_"), 해당 상태의 하위 트리 탐색은 **가지치기(pruned)**되고 DFS는 부모 상태로 되돌아가 다음 유망한 단서 사고를 탐색한다. 우리는 DFS 탐색 단계를 100으로 제한하고, 가장 깊이 탐색된 상태(여러 개일 경우 첫 번째 탐색된 상태)를 최종 출력으로 렌더링한다.

Figure 6: 미니 크로스워드에서, (a) 깊이 우선 탐색(DFS)을 위해 사고가 어떻게 제안되고 우선순위 큐에 집계되는지, 그리고 (b) 각 남은 단어 단서를 채울 가능성을 기반으로 상태가 어떻게 평가되고, LM에 의해 남은 단서 중 하나라도 채우는 것이 불가능하다고 판단되면 어떻게 가지치기되는지. 그런 다음 DFS는 부모 상태로 되돌아가 단서에 대한 다음 유망한 사고를 탐색한다.

결과.
Table 3에서 보듯이, IO 및 CoT 프롬프팅 방법은 단어 수준 성공률이 16% 미만으로 저조한 성능을 보이는 반면, ToT는 모든 지표를 크게 향상시켜 단어 수준 성공률 60%를 달성하고 20개 게임 중 4개를 해결한다. 이러한 개선은 IO 및 CoT가 다른 단서를 시도하거나, 결정 사항을 변경하거나, 되돌아가는 메커니즘이 부족하다는 점을 고려할 때 놀라운 일이 아니다.

Oracle 및 Ablation 연구.
task별로 oracle이 결정한 최적의 DFS 상태(휴리스틱으로 결정된 최적 상태 대신)에서 출력할 때, ToT 성능은 훨씬 더 높으며 실제로 20개 게임 중 7개를 해결한다(Table 3, "+best state"). 이는 우리의 간단한 출력 휴리스틱이 쉽게 개선될 수 있음을 나타낸다. 흥미롭게도, 때때로 크로스워드 게임이 실제로 해결되었음에도 불구하고, 상태 평가자가 일부 단어를 "불가능"하다고 판단하고 가지치기할 수 있다. 이는 $5 \times 5$ 크로스워드가 설계상 GPT-4가 인식하지 못하는 희귀하거나 구식 단어를 포함할 수 있기 때문일 수 있다.
가지치기 휴리스틱으로서의 상태 평가가 불완전하다는 점을 고려하여, 우리는 가지치기를 제거하는 ablation도 탐색했으며, 성능이 일반적으로 더 나빠지는 것을 발견했다(Table 3, "-prune"). 그러나 이 방법은 실제로 20개 게임 중 4개에 대해 올바른 해결책을 찾을 수 있었다(비록 휴리스틱을 통해 1개만 출력되었지만). 이 중 3개는 ToT+가지치기가 100단계 내에서 해결할 수 없는 게임이었다. 따라서 이 경우 DFS 가지치기를 위한 더 나은 휴리스틱이 문제 해결에 중요하다.
마지막으로, 우리는 최대 20단계 동안 가장 유망한 단서를 계속 채우고 덮어쓰기를 허용하는 ablation을 실행하여 되돌아가기(backtracking)의 중요성을 확인한다. 이는 너비 제한이 $b=1$인 "탐욕적인(greedy)" BFS 탐색과 유사하며, 단어 수준 성공률이 20%에 불과하여 저조한 성능을 보인다(Table 3, "-backtrack").

5 Related Work

계획 및 의사 결정 (Planning and decision making)
스마트한 계획 수립과 의사 결정은 미리 정의된 목표를 달성하는 데 매우 중요하다. Language Model(LM)은 방대한 양의 세계 지식과 인간의 예시를 통해 학습되었기 때문에, 문제 설정과 환경 상태에 따라 합리적인 계획을 제안할 수 있는 풍부한 상식을 이미 습득하고 있는 것으로 알려져 있다 [12, 42, 37, 13, 35, 41, 40]. 우리가 제안하는 ToT(Tree-of-Thought) 접근 방식은 각 문제 해결 단계에서 여러 잠재적으로 실현 가능한 계획들을 동시에 고려하고, 가장 유망한 계획들을 진행함으로써 기존의 계획 수립 방식을 확장한다. 사고 샘플링(thought sampling)과 가치 피드백(value feedback)의 통합은 계획 및 의사 결정 메커니즘을 유기적으로 결합하여 솔루션 트리(solution tree) 내에서 효과적인 탐색을 가능하게 한다. 반면, 전통적인 의사 결정 절차는 일반적으로 강화 학습(예: CHAI [33])에서처럼 전용 보상(reward) 및 정책(policy) 모델 학습을 요구하는 반면, 우리는 LM 자체를 사용하여 의사 결정을 위한 가치 추정치를 제공한다. **RAP [9]**는 Language Model의 추론을 내부 세계 모델을 통한 계획으로 간주하고, ToT와 유사한 MCTS(Monte Carlo Tree Search) 기반 방법을 제안하는 동시 연구이다. 그러나 RAP의 task는 우리보다 단순하며, 그 프레임워크는 다양한 트리 탐색 알고리즘을 통합할 수 있는 모듈성(modularity)이 부족하다.

자기 성찰 (Self-reflection)
LLM(Large Language Model)이 자신의 예측 타당성을 스스로 평가하는 것은 문제 해결에서 점점 더 중요해지는 절차가 되고 있다. [28, 20, 24]는 LM이 자신의 생성 후보에 피드백을 제공하는 "self-reflection" 메커니즘을 도입했다. [4]는 LM 자체의 코드 실행 결과에 기반하여 LM이 생성한 피드백 메시지를 주입함으로써 LM의 코드 생성 정확도를 향상시킨다. 유사하게, [17] 또한 행동(action)과 상태(state)에 대한 "critic" 또는 검토 단계를 도입하여 컴퓨터 운영 task 해결에서 다음 행동을 결정한다. 우리 연구와 매우 관련이 깊은 또 다른 최근 연구는 **"self-eval guided decoding" [39]**이다. self-eval decoding은 우리 방법과 유사하게 확률적 빔 탐색(stochastic beam search) 디코딩에서 샘플링된 리프(leaf)를 가진 트리 탐색 절차를 따르며, 이 리프들은 신중하게 준비된 self-eval prompt를 통해 LLM 자체에 의해 평가된다. 그러나 그들의 접근 방식은 사고를 코드로 표현하는 PAL(Program-Aided Language) [8] 방식을 사용하는데, 이는 본 논문에서 다루는 창의적 글쓰기와 같은 도전적인 task를 해결하기 어렵게 만든다. 따라서 우리의 Tree-of-Thought(ToT) 방식은 더 다재다능하며, GPT-4가 표준 prompt로는 매우 낮은 정확도를 보이는 도전적인 task들을 처리할 수 있다.

프로그램 기반 LLM 생성 (Program-guided LLM generation)
우리의 제안은 또한 LM의 동작을 체계적인 절차 [14, 44, 6, 43] 또는 상징적 프로그램 지침으로 조직화하는 최근의 발전과도 관련이 있다. 예를 들어, Schlag et al. [27]은 LM을 알고리즘적 탐색 절차에 내장하여 질문 응답과 같은 문제를 단계별로 해결하는 데 도움을 주는데, 이 과정에서 탐색 트리는 답변을 제공할 수 있는 관련 단락(paragraph)에 의해 확장된다. 그러나 이 접근 방식은 트리가 LM 자체의 사고 대신 외부 단락을 샘플링하여 확장되고, 반영(reflection) 또는 투표(voting) 단계가 없다는 점에서 우리와 다르다. 또 다른 접근 방식인 **LLM+P [18]**는 한 단계 더 나아가 실제 계획 프로세스를 고전적인 플래너(classical planner)에 위임한다.

고전적 탐색 방법 (Classical search methods)
마지막으로, 우리의 접근 방식은 문제 해결을 위한 고전적 탐색 방법의 현대적 재해석으로 볼 수 있다. 예를 들어, 이는 A* [10]와 같은 휴리스틱 탐색 알고리즘으로 간주될 수 있으며, 각 탐색 노드의 휴리스틱은 LM의 자기 평가에 의해 제공된다. 이러한 관점에서 우리의 방법은 **A* 탐색에서 영감을 받았지만, 빔 탐색(beam-search) 또는 top-k 샘플링 디코딩을 개선하기 위해 LM에 효율적인 look-ahead 휴리스틱을 도입한 NeuroLogic A*esque decoding [19]**과도 관련이 있다. 그러나 이 방법은 문장 생성 task에 국한되는 반면, 우리의 프레임워크는 가치 피드백(value feedback)에 의해 제어되는 복잡한 다단계 문제 해결을 위해 설계되었다.

6 Discussion

한계점 및 향후 방향
ToT와 같은 **심층적인 탐색(deliberate search)**은 GPT-4가 이미 뛰어난 성능을 보이는 많은 기존 task에서는 불필요할 수 있으며 (Appendix B.1 참조), 본 연구는 초기 단계로서 GPT-4에 도전이 되는 비교적 간단한 세 가지 task만을 탐구한다 (일부 GPT-3.5 실험 결과는 Appendix B.2 참조). 이는 LM에 더 나은 탐색 및 계획 능력을 통합할 필요성을 시사한다. 그러나 LM을 더 많은 실제 의사결정 애플리케이션(예: 코딩, 데이터 분석, 로봇 공학 등)에 배포하기 시작하면서, 더 복잡한 task들이 등장할 수 있으며, 이는 이러한 연구 질문들을 탐구할 새로운 기회를 제공할 것이다.
또한, ToT와 같은 탐색 방법은 task 성능을 향상시키기 위해 샘플링 방법보다 더 많은 자원(예: GPT-4 API 비용)을 요구하지만, ToT의 모듈식 유연성은 사용자가 이러한 성능-비용 trade-off를 맞춤 설정할 수 있도록 하며, 현재 진행 중인 **오픈 소스 노력 [32]**은 가까운 미래에 이러한 비용을 쉽게 절감할 수 있을 것이다. 비용 및 효율성에 대한 자세한 내용은 Appendix B.3에 있다.
마지막으로, 본 연구는 기성(off-the-shelf) LM을 사용하는 데 중점을 두었으며, ToT 스타일의 고수준 반사실적 의사결정(예: 다음 토큰을 예측하는 대신 다음 단락에 대한 잠재적 선택 사항을 심사숙고하는 것)을 사용하여 LM을 fine-tuning하는 것은 LM의 문제 해결 능력을 향상시킬 기회를 제공할 수 있다.

결론
LM의 연상적인 "System 1"은 문제 해결을 위한 가능한 경로의 트리를 탐색하는 "System 2"를 기반으로 유익하게 증강될 수 있다. Tree of Thoughts (ToT) 프레임워크는 문제 해결에 대한 고전적인 통찰력을 현대 LM을 위한 실행 가능한 방법으로 전환하는 방법을 제공한다. 동시에 LM은 이러한 고전적인 방법의 약점을 해결하여 창의적 글쓰기와 같이 쉽게 형식화하기 어려운 복잡한 문제를 해결하는 방법을 제공한다. 우리는 LM과 AI에 대한 고전적인 접근 방식의 이러한 교차점을 흥미로운 방향으로 보고 있다.

Broader Impact

ToT는 LM이 더욱 자율적이고 지능적으로 의사결정을 내리고 문제를 해결할 수 있도록 지원하는 프레임워크이다. 현재 task는 추론 및 탐색 문제에 국한되어 있지만, 외부 환경이나 인간과의 상호작용을 포함하는 미래 애플리케이션은 잠재적인 위험을 초래할 수 있다. 예를 들어, LM의 유해한 사용을 촉진할 수 있다.
반면에 ToT는 모델 결정의 **해석 가능성(interpretability)**과 인간 정렬(human alignment) 기회를 향상시킨다. 이는 결과로 생성되는 표현이 암묵적이고 저수준의 token 값 대신, 읽기 쉽고 고수준의 언어 추론이기 때문이다.

Acknowledgements

SY와 KN은 Oracle Collaborative Research award와 국립과학재단(National Science Foundation)의 Grant No. 2239363 지원에 감사드립니다. 본 자료에 표현된 의견, 발견, 결론 또는 권고 사항은 전적으로 저자(들)의 것이며, 반드시 국립과학재단의 견해를 반영하는 것은 아닙니다. SY는 또한 Princeton 대학의 Harold W. Dodds Fellowship의 지원을 받습니다.

A Code, Prompts, Trajectories

모든 코드는 https://github.com/princeton-nlp/tree-of-thought-llm 에서 확인할 수 있다. 모든 prompt는 https://github.com/princeton-nlp/tree-of-thought-llm/tree/master/src/tot/prompts 에서 확인할 수 있다. Trajectory는 https://github.com/princeton-nlp/tree-of-thought-llm/tree/master/logs 에서 확인할 수 있다.

B Additional Experiment Results

언어 모델의 능력 한계를 탐구하고 확장하려는 동기에 따라, 본 논문의 주요 실험에서는 **state-of-the-art 언어 모델(GPT-4)**과 이를 도전하기 위해 고안된 세 가지 어려운 task에 초점을 맞추었다. 여기서는 성능이 낮은 LLM 또는 더 쉬운 task에 대한 추가 실험 결과를 보고하고, 비용 및 효율성에 대해 논의한다.

Table 4: zero-shot ToT와 GPT-4를 사용한 새로운 task 결과.

Table 5: GPT-4 vs GPT-3.5의 Game of 24 결과.

Table 6: GPT-4 vs. GPT-3.5의 Creative Writing 결과.

B. 1 Extension to new tasks (GSM8k, StrategyQA) with zero-shot ToT

일반적인 NLP task는 GPT-4에게 너무 쉬워서 ToT가 필요하지 않을 수 있지만(이것이 우리가 더 어려운 새로운 task를 고려한 이유이다), 우리는 새로운 task에 ToT를 적용하는 것이 간단할 수 있다고 생각한다. 예를 들어, 우리는 GSM8K와 StrategyQA에 대해 창의적 글쓰기(5가지 문제 해결 전략을 샘플링한 다음 가장 좋은 것을 투표하고, 그 다음 가장 좋은 전략을 기반으로 5가지 솔루션을 샘플링한 다음 가장 좋은 것을 투표)와 유사한 간단하고 일반적인 zero-shot ToT-BFS를 몇 줄의 코드만 추가하여 구현했다:

# define the answer format of new tasks

gsm8k_format = '"the answer is n" (n은 숫자)'
strategyqa_format = '"the answer is yes" 또는 "the answer is no"'

# define zero-shot io prompting

standard_prompt = 'Answer the following question with {format}: {input}'


# define thought format for zero-shot cot and zero-shot tot

cot_prompt = '''Answer the following question: {input}
Make a strategy then write. Your output should be of the following format:
Strategy:
Your strategy about how to answer the question.
Answer:
Your answer to the question. It should end with {format}.
,",
'''

# define zero-shot voting used for zero-shot tot

vote_prompt = '('지시문과 여러 선택지가 주어졌을 때,
가장 유망한 선택지를 결정하세요.
각 선택지를 자세히 분석한 다음, 마지막 줄에
"The best choice is {s}"라고 결론을 내리세요. 여기서 s는 선택지의 정수 ID입니다.
,"

우리는 무작위로 추출한 GSM8K test 문제 100개와 StrategyQA dev 문제에 대한 subset으로 평가를 수행했다. Table 4에서 볼 수 있듯이, 예상대로 ToT는 CoT보다 두 task 모두에서 성능을 향상시켰다. (하지만 GPT-4 + CoT가 이미 이러한 task에서 매우 우수하고, StrategyQA의 병목 현상이 추론이 아닌 외부 지식이라는 점을 고려하면 그 향상 폭은 크지 않다.) 계산 비용을 고려할 때, 전통적인 NLP task에는 더 작은 LLM + ToT를 시도하는 것이 더 적합하며, GPT-4 + CoT의 추론 능력을 시험하는 어려운 task에는 GPT-4 + ToT를 사용하는 것이 더 적합하다.

B. 2 Extension to new LMs (GPT-3.5)

다른 LLM과 ToT가 어떻게 작동하는지 이해하기 위해, 우리는 Creative Writing (Table 6)과 Game of 24 (Table 5) task에 대해 GPT-3.5-turbo를 실행했다. 두 task 모두에서 "ToT > CoT > IO" 관계는 GPT-3.5에서도 유지되었다. Creative Writing task에서 우리는 GPT-3.5+ToT가 GPT-4+IO보다 우수하며, GPT-4+CoT와 유사한 성능을 보인다는 것을 발견했다. 이는 ToT가 더 약한 language model에서도 잘 작동할 수 있음을 시사한다.

Game of 24 task (1-shot proposal prompt를 3-shot으로 변경하여 작동하도록 함)에서 GPT-3.5+ToT의 성공률은 19%로, GPT-4+ToT의 74%보다 훨씬 낮았다. 생성(generation)과 평가(evaluation)의 중요성을 더 깊이 이해하기 위해, 우리는 **GPT-4 생성 + GPT-3.5 평가 (64%)**와 GPT-3.5 생성 + GPT-4 평가 (31%) 조합으로 실험을 진행했다. 이 결과는 Game of 24 task의 병목 현상이 사고 생성(thought generation)에 있음을 시사하며, 서로 다른 생성/평가 language model을 조합하여 비용을 절감하면서도 괜찮은 결과를 얻을 수 있음을 보여준다.

B. 3 Cost and efficiency

ToT를 실행하는 데는 IO 또는 CoT prompting보다 훨씬 더 많은 연산량이 필요하다. 예를 들어, Game of 24 (아래 Table 7)에서 ToT로 문제를 해결하려면 5.5k completion token이 필요하며, 이는 100번의 CoT 시도(6.7k token)에 가까운 양이다. 하지만 ToT의 성능은 100번의 독립적인 CoT 시도 중 최고 성능보다 더 우수하다.

Table 7: Game of 24에 대한 비용 분석.

Creative Writing (아래 Table 8)에서는 ToT가 약 5배의 completion token과 비용을 소모하는 것을 확인했는데, 이는 $b=5$이고 대부분의 token이 생성된 passage이기 때문에 직관적인 결과이다.

Table 8: Creative Writing에 대한 비용 분석.

따라서 Game of 24와 Creative Writing의 주요 ToT 실험을 완료하는 데는 약 $0.74 \times 100 + 0.32 \times 100 = 106$ 달러가 소요되었다. Crosswords의 DFS 실험 또한 100달러 이내일 것이다. 일반적으로 ToT의 비용과 효율성은 사용된 prompt와 search algorithm에 크게 의존하며, CoT보다 5~100배 더 많은 생성 token을 요구할 수 있다. 몇 가지 실행 가능한 통찰은 다음과 같다:

• CoT가 어려움을 겪는 신중한 추론이 필요한 task에는 ToT를 사용하는 것을 권장한다.
• ToT의 유연성은 성능-비용 trade-off를 가능하게 한다. 예를 들어, BFS에서 beam size나 vote number를 변경하거나, few-shot vs. zero-shot prompting, GPT-3.5 vs. GPT-4 등을 활용할 수 있다. 자원 제약이나 성능 목표에 따라 설정을 구성할 수 있다.
• 효율성을 개선할 여지가 많다. 예를 들어, BFS는 해답을 찾으면 조기에 중단하거나, 일부 thought가 "불가능"할 때 beam size를 줄일 수 있다.
• 우리는 모델이 더 강력한 지능을 달성하기 위해서는 더 많은 연산이 실제로 필요하다고 믿으며, 장기적으로 (오픈소스) LM이 훨씬 저렴하고 효율적이 될 것이므로 이것이 방해 요소가 되어서는 안 된다고 생각한다. 또한 thought generation 및/또는 evaluation을 위해 LM을 더 잘 학습/fine-tuning하는 방법도 훌륭한 연구 방향이다.