Tree of Thoughts: Deliberate Problem Solving with Large Language Models 논문 리뷰

The overview of this paper

 LM들은 점점 광범위한 task에 적용되고 있는데 아직 token-level left-to-right decision-making 프로세스에 국한되어 있다. 이것은 탐구와 전략적인 방법을 필요로 하는 task에서는 모델이 한계를 겪거나 초기의 결정이 중심 역할을 수행할 수도 있다. 이를 해결하기 위해 LM 추론을 위한 새 프레임워크인 'Tree of Thoughts'(ToT)를 제안하였다. ToT는 CoT를 일반화하고 문제 해결에 대한 중간 스텝으로 여겨지는 일관성 있는 텍스트의 유닛에 대해 탐구를 가능하게 해 준다. ToT는 여러 서로 다른 reasoning path를 고려하고 다음 행동의 코스를 결정하기 위해 self-evaluating choice를 고려함으로써 정교한 decision making을 LM이 수행하게 한다.

 

 논문에서는 상당한 planning과 search를 필요로 하는 3개의 새로운 task에 대해 실험을 진행한다: Game of 24, Creative Writing, Mini Crosswords. GPT-4 with CoT는 4% 정도 문제 해결이 가능했지만, ToT는 이를 74%로 끌어올렸다.

 

 

Table of Contents

1. Introduction

2. Background

3. Tree of Thoughts: Deliberate Problem Solving with LM

4. Experiments

5. Discussion

 

 

1. Introduction

 텍스트를 생성하기 위해 기존에 디자인된 모델들은 GPT와 PaLM과 같은 LM의 scaled-up 버전들이다. 하지만 이들의 근본적인 progress는 기존의 auto-regressive 메커니즘이다. 이 방식은 left-to-right 방식으로 하나하나씩 token-level decision을 만들어가는 방식이다. 하지만 이 간단한 메커니즘이 general problem solver LM으로 충분할까? 그렇지 않다면 어떤 문제가 현재 패러다임에 도전하고 대체 메커니즘은 무엇일까?

 

 사람의 인지 과정은 이 질문에 대답하기 위한 몇 가지 실마리를 제공한다. 'dual process'에 대한 연구는 사람이 결정을 내릴 때 두 가지 모드를 가진다고 제안한다.

 

• System 1: fast & automatic. 무의식적 모드
• System 2: slow & deliberate(=계획적인). 의식적 모드

 

 LM의 간단한 연합적 token-level의 선택은 'System 1'을 연상시키고, 따라서 더욱 계획적인 'System 2' planning 프로세스에 의한 augmentation으로부터 이익을 얻는다. 여기서 'Systme 2'의 planning 프로세스는 다음과 같다.

 

1. 하나만을 뽑는 대신에 현재 선택에 대한 다양한 대안을 유지 & 탐구
2. 현재 상태를 평가하고 적극적으로 나아갈지 또는 더욱 전역적인 결정을 만들기 위해 backtrack 할 지 정함

 

 논문에서는 이러한 planning 프로세스를 디자인하기 위해 트리 구조를 사용한 Tree of Thoughts(ToT)를 제안하였다. ToT는 적극적으로 tree of thought를 유지하는데, 여기서 thought는 문제 해결을 위한 중간 스텝으로 여겨지는 일관된 language sequence이다(표 1). 이러한 high-level semantic unit은 LM이 서로 다른 thought에 대해 처리하는 것을 자연어로 되어 있는 계획적인 추론 프로세스를 통해 self-evaluate 하게 허락해 준다(그림 2, 4, 6). 마지막으로 다양한 thought를 생성하고 평가하기 위해 언어 기반 능력과 BFS와 DFS 같은 검색 알고리즘을 묶었다. 이것은 lookahead와 backtracking을 사용하여 tree of thoughts의 체계적 탐구를 허락해 준다.

 

 실험 쪽으로 논문에서는 기존의 LM들도 어려움을 겪고 있는 3개의 문제에 대해서 제안하였다: Game of 24, Creative Writing, Crosswords(표 1). 이 task들은 연역적, 수학적, 기본 상식, 어휘 추론 능력, 체계적 계획 세우기 또는 검색을 필요로 한다. 실험에 대한 결과는 뒤에서 더 자세하게 살펴보도록 하겠다.

 

 

2. Background

 ToT에 대해서 알아보기 전에 기존에는 어떤 prompting 방법들이 있었는지에 대해서 알아보도록 하겠다.

 

Input-output (IO) prompting.  입력 $x$가 주어졌을 때 $y$를 출력하는 가장 일반적인 방법이다: $y ~ p_{\theta}(y|prompt_{IO}(x))$. 여기서 $prompt_{IO}(x)$는 task instruction과 입력 $x$를 묶은 것으로 몇 개의 few-shot input-output example이 들어가기도 한다. 

 

Chain-of-thought (CoT) prompting.  input $x$와 output $y$의 매핑이 사소하지 않다는 문제를 해결하기 위해 제안되었다. 이 prompting 방식의 핵심 아이디어는 $x$와 $y$를 잇기 위해 생각의 고리(chain of thought) $z_1, \cdots, z_n$을 소개했다는 것이다. 여기서 각 $z_i$는 문제 해결을 위해 의미 있는 중간 스텝으로 여겨지는 일관된 language sequence이다. 

 

Self-consistency with CoT(CoT-SC).  CoT method의 ensemble 방식인 격으로 $k$ 개의 서로 다른 chain of thought를 샘플링한다. 그다음에 가장 빈번하게 출력된 output을 최종 output으로 반환한다. CoT-SC는 CoT를 개선시킨 method로 문제를 해결하는 데에는 여러 가지 서로 다른 output decision이 있을 것이라는 아이디어에서 착안되었다. 그리고 더 풍부한 thought 세트를 탐구함으로써 더욱 신뢰도 있는 output decision을 내릴 수 있을 것이라고 생각하였다. 

 

 다음의 그림 1을 보면 더 이해가 잘 될 것이다.

 

그림 1. 여러 prompting method의 문제 해결 방식

 

 

 

3. Tree of Thoughts: Deliberate Problem Solving with LM

 사람은 문제를 해결할 때 조합적 problem space에서 search를 수행한다. tree의 노드는 부분적 솔루션으로 표현되고, branch는 이들을 조정하는 연산자에 해당된다. 이러한 관점은 기존에 LLM이 사용하는 방법의 문제점을 강조한다.

 

1. Locally, thought process 간의 서로 다른 연결을 탐험하지 못한다. → tree의 branch
2. Globally, 어떠한 planning lookahead과 backtracking도 포함하지 못한다. → heuristic-guided search

 

 이러한 문제점을 해결하기 위해 논문에서는 LM이 thought에 대해 여러 reasoning path를 탐험할 수 있도록 허락해 주는 Tree of Thought(ToT)를 제안하였다(그림 1(c)). ToT는 모든 문제를 tree에 대한 검색으로 여긴다. 여기서 각각의 노드는 state $s = [x, z_{1\cdots i}]$로 thought의 input과 sequence와 함께 부분적 솔루션을 나타낸다. ToT의 구체적인 방법은 다음의 4가지 질문에 대답하는 것이라고 할 수 있다.

 

1. Thought decomposition.  CoT는 분명한 분해 없이 일관적으로 thought를 샘플링하는 반면에, ToT는 thought의 중간 스텝을 디자인하고 분해하기 위해 문제의 특성을 활용한다. 표 1에서 보이는 것처럼, 서로 다른 문제에 따라, thought의 형태는 변화한다. 일반적으로 thought는 LM이 유망하고 다양한 sample을 생성할 수 있도록 충분히 작아야 하고 LM이 이들의 예측을 평가할 수 있을 정도로는 커야 한다.

 

2. Thought generator $G(p_{\theta}, s, k)$.  tree state $s = [x, z_{1\cdots i}]$가 주어지면, 다음 thought step에 대해 $k$ 개의 후보를 생성하기 위한 두 가지 전략을 고려해 볼 수 있다:

 

• Sample: CoT prompt로부터 thought를 샘플링함. 이 작업은 thought space가 풍부할 때 더 잘 됨.
• Propose: 'propose prompt'를 사용해서 순차적으로 thought 제안함. 이 작업은 thought process가 더욱 제한될 때 잘 돼서, 똑같은 context에서 서로 다른  thought를 제안하는 것은 복제를 피하게 해 줌.

 

3. State evaluator $V(p_{\theta|, S)$. 서로 다른 state의 변경이 주어지면 state evaluator는 progress를 평가한다. 휴리스틱은 검색 문제를 해결하기 위한 일반적인 방법이었지만, 이들은 일반적으로 프로그래밍되어 있거나 학습되어 있다. 논문에서는 계획적으로 state를 추론하기 위해 LM을 사용하는 세 번째 대안을 제안하였다. 적용 시에 이러한 계획적 휴리스틱은 프로그래밍된 규칙보다 유연하고 학습된 모델보다 샘플 효율적이다. thought generator와 유사하게 논문에서는 state를 독립적으로 또는 함께 평가하기 위한 두 가지 전략을 제안하였다:

 

• Value: 각 state를 독립적으로 - 여기서 value prompt는 스칼라 값(1-10) 또는 휴리스틱 하게 값으로 변환될 수 있는 분류를 생성해 내기 위해 state $s$에 대해 추론한다. 이 작업에서는 소수의 lookahead 시뮬레이션 + commonsense를 통해 평가를 탐구하였다. 여기서 전자(소수의 lookahead 시뮬레이션)는 'good' state를 촉진하고, 후자(commonsense)는 'bad' state를 제거하는 것을 도와준다. 이러한 valuation은 완벽할 필요는 없고, 근사 정도만 되면 된다.
• Vote: state 간에 - 여기서 'good' state는 vote prompt에서 서로 다른 state $S$를 계획적으로 비교한 것에 기반해서 투표된다. problem success를 직접적인 값으로 나타내기 힘들 때는 서로 다른 부분적 솔루션을 비교하고 가장 유망한 것에 투표를 하는 방식으로 한다. 

 

4. Search algorithm.  논문에서는 비교적 간단한 2개의 검색 알고리즘에 대해 탐구하고 더욱 발전된 하나를 소개한다:

 

• Breadth-first search(BFS) (Alrorithm 1)은 스텝 당 가장 유망한 $b$개의 state 세트를 유지시킨다. 이 방법은 Game of 24에 사용되고, 여기서 tree depth는 제한되어 있다. 그리고 초기의 thought step이 평가될 수 있고, small set으로 가지치기가 될 수 있다.
• Depth-first search(DFS) (Algorithm 2)은 final output에 도달하기 전까지나 현재 state $s$에서 문제를 해결하기가 불가능하다고 보일 때 가장 유망한 state를 탐구해 나간다. 후자의 경우에 $s$의 하위 트리는 착취를 위해 탐색을 교환하기 위해 가지치기된다. 2개의 경우에서 탐구를 계속하기 위해 DFS는 $s$의 parent state를 backtrack 한다.

 

 ToT는 general problem-solving method로써 여러 이익을 가지고 있다.

 

1. Generality: IO, CoT, CoT-SC, self-refinement는 ToT의 스페셜 케이스로 볼 수 있음
2. Modularity: base LM 뿐만 아니라 분해, 생성, 평가, 검색 프로시저는 모두 독립적으로 평가될 수 있음
3. Adaptability: 서로 다른 문제 특성, LM 능력, 자원 제약 등을 수용할 수 있음
4. Convenience: 추가적인 학습이 필요하지 않고, 단지 PLM이면 충분함

 

4. Experiments

 논문에서는 기존의 SoTA LM으로부터 샘플링을 할 때에도 어려운 3개의 task를 제안하였다: Game of 24, Creative Writing, 5x5 Crosswords. 

 

표 1. Task overview. Input, output, thought example은 파란색

 

4-1. Game of 24

 

 Game of 24는 4개의 숫자가 주어졌을 때, 사칙연산을 사용하여 24를 만들 수 있는지 없는지 판단하는 task이다. 예를 들어 '4 9 10 13'이 입력으로 주어지면, output은 '(10 - 4) * (13 - 9) = 24'인 것이다.

 

그림 2. Game of 24에서의 ToT. LM은 (a) thought 생성과 (b) valuation을 위해 prompt된다

 

 Baselines.  논문에서는 5개의 in-context example과 함께 input-output(IO) prompt를 사용하였다. chain-of-thought(CoT) prompting을 위해 각 input-output 쌍을 3개의 중간 방정식으로 augment 하고, 각 방정식은 나머지 2개의 숫자에 대해 작동하게 하였다. 예를 들어 input으로 ' 4 9 10 13'이 주어지면, thought는 "13 - 9 = 4(남은 수: 4, 4, 10); 10 - 4 = 6(남은 수: 4, 6); 4 * 6 = 24(남은 수: 24)"가 될 수 있다. 또한 CoT self-consistency baseline와 IO sample 위에서 최대 10번의 반복을 하는 iterative-refine approach를 고려하였다. 각 반복에서 LM은 출력이 올바르지 않은 경우 "실수를 반성하고 개선된 답변을 생성"하기 위해 모든 이전 기록을 맞춘다. 그리고 방정식 정확성에 대한 groundtruth 피드백 신호를 사용한다.

 

ToT Setup.  Game of 24를 ToT에 맞추기 위해, thought를 각각이 중간 방정식인 3개의 step으로 분해하는 것이 자연스럽다. 그림 2(a)에서 보이는 것처럼 논문에서는 각 트리의 노드에서 남아있는 숫자를 요구하고 LM이 가능한 다음 스텝을 제안하도록 촉구한다. 그리고 ToT에서 BFS를 수행하였는데, 각 스텝에서 최고의 $b=5$ 후보를 유지하였다. 그림 2(b)에서 보이는 것처럼 ToT에서 계획적인 BFS를 수행하기 위해 각 thought 후보가 24에 도달하는지에 따라 평가하도록 LM을 촉구하였다. 목표는 몇 개의 lookahead 실험 간에 판단될 수 있는 알맞은 부분적 solution을 촉진하고 'too big/small' commonsense에 기반한 불가능한 부분적 solution을 제거하고 'maybe'는 유지시키는 것이다. 그리고 논문에서는 각 thought에 대해 3번 value를 샘플링하였다.

 

Results.  표 2에서 보이는 것처럼 IO, CoT, CoT-SC prompting method는 task에서 겨우 7.3%, 4.0%, 9.0%의 성능을 보여줄 정도로 안 좋은 모습을 보여준다. 이와는 반대로 폭이 $b=1$인 ToT는 이미 45%의 성공률을 가지고, $b=5$의 경우에 74%의 성공률을 가진다.

 

Error Analysis.  그림 3(b)은 CoT와 ToT에서 task에 대해 실패한 샘플을 분해해 본다. 특히 CoT 샘플의 약 60%는 첫 번째 단계 또는 동등하게 처음 세 단어를 생성한 후 이미 task에 대해 실패하였다. 이는 left-to-right decoding의 문제점을 강조한다.

 

표 2. Game of 24 결과 / 그림 3. Game of 24의 (a)규모 분석과 (b)에러 분석

 

4-2. Creative Writing

 

 논문에서는 4개의 랜덤 한 문장이 input으로 들어오고 이 문장으로 끝나는 일관된 4개의 문단을 작성하는 task를 고안하였다. 이 task는 창의적인 생각 뿐만 아니라 높은 수준의 계획을 필요로 한다.

 

Baselines.  논문에서는 task 당 10개의 IO & CoT 샘플을 생성하였다. 또한 각 task에 대해 랜덤한 IO 샘플의 위에 iterative-refine method를 고려하였는데, 여기서 LM은 입력 제약에 맞춰지고, 마지막으로 생성된 구절이 이미 "완벽하게 일관된"지 여부를 결정하고 그렇지 않은 경우 개선된 구절을 생성한다.

 

ToT Setup.  논문에서는 오직 하나의 중간 thought step을 가지는 깊이가 2인 ToT를 만들었다 - LM은 처음에 $k=5$개의 계획을 생성하고 최고의 하나에 대해 투표한다(그림 4). 그다음에 이와 유사하게 최고의 하나로 뽑힌 계획에 기반해서 $k=5$ 개의 구절을 만든다. 여기에서 단계당 하나의 선택만 유지되므로 폭 제한은 $b = 1$이다.

 

그림 4. 랜덤하게 뽑힌 Creative Writing task에서 계획적인 검색의 스텝

 

Results.  그림 5(a)는 100개의 task에 대해 GPT-4의 평균 score를 보여준다. 여기서 ToT(7.56)은 IO(6.19)와 CoT(6.93) 보다 평균적으로 더 일관적인 구절을 만드는 것으로 여겨진다. 이러한 automatic metric은 잡음이 섞일 수도 있지만, 그림 5(b)는 human preference 또한 CoT보다 ToT를 더 선호하는 것으로 보아 이 발견을 입증해 준다. 마지막으로, iterative-refine은 이 자연어 task에서 더욱 효과적인데, 여기서 IO 일관성은 6.19에서 7.67로 개선되고, ToT는 7.56에서 7.91로 개선된다. 논문에서는 이 방법이 ToT 프레임워크에서 thought 생성을 위한 3번째 방법이 될 수 있을 것이라 믿는다.

 

그림 5. Creative Writing 결과

 

4-3. Mini Crosswords

 

 Game of 24와 Creative Writing에서, ToT는 비교적 얕은 활약상을 보여준다 - 최종 output에 도달하기 위해 최대 3개의 thought step을 필요로 한다. 여기서는 5x5 mini crossword를 자연어를 포함하는 더 어려운 검색 문제로 탐구해보려 한다. 다시 말해 목표가 단지 task를 해결하는 것이 아니라, LM이 자신의 생각을 탐구하고 휴리스틱으로 의도적 추론을 통해 자신의 탐구를 가이드하는 일반적인 problem solver로써의 한계를 탐구하는 것을 목표로 한다.

 

Baselines.  논문에서는 IO prompt에서 5개의 example input-output 쌍을 제공하고, CoT prompt는 추가적으로 중간 단어를 포함한다. 그리고 10개의 샘플에 대한 각 prompt를 실행하고 결과를 평균 내었다.

 

ToT Setup.  논문에서는 state가 더 이상 유망하지 않을 때까지 가장 유망한 후속 단어 단서를 계속 탐색한 다음 parent state로 되돌아가 대체 thought를 탐색하는 DFS(Algorithm 2)을 활용한다. 검색을 다루기 쉽게 하기 위해 후속 thought는 채워진 단어나 문자를 변경하지 않도록 제한되므로 ToT에는 최대 10개의 중간 단계가 있다. thought 생성을 위해 각 state에서 모든 기존 thought를 나머지 단서, 그리고 다음 단어를 어디에 무엇을 채울 것인지에 대한 후보를 제시하기 위해 propose prompt를 5번 촉발한다. 또한 LM이 다양한 thought에 대한 신뢰 수준을 제공하고 탐색할 다음 생각의 정렬된 목록을 얻기 위해 제안 전체에서 이를 집계하도록 유도한다는 것이다(그림 6(a)). state 평가의 경우 각 state를 나머지 단서에 대한 문자 제약 조건으로 유사하게 변환한 다음 주어진 제약 조건을 채울 수 있는 경우 각 단서에 대해 평가한다. 나머지 단서가 채울 수 없는 것으로 간주되면 state의 하위 트리 탐색이 가지치기되고 DFS는 다음 유망한 thought를 탐색하기 위해 부모로 역추적한다. 우리는 DFS 검색 단계를 100으로 제한하고 가장 깊이 탐색된 state(여러 개가 있는 경우 첫 번째 탐색된 state)를 최종 출력으로 간단히 렌더링 한다.

 

그림 6. Mini Crossword에서 (a) DFS를 위한 우선순위 큐에서 thought들이 제안되고 모이는지와 (b) 남은 각 단어 단서를 채울 가능성에 따라 state를 평가하고 나머지 단서가 LM에서 채울 수 없다고 판단되는 경우 어떻게 가지치기하는지

 

Results.  표 3에서 보이는 것처럼, IO와 CoT prompting method는 word-level 성공률이 16%보다 낮지만, ToT는 모든 metric에서 개선된 모습을 보여주면서 word-level에서 60%의 성공률을 보여줬고 20개의 게임 중 4개를 해결하였다. 이러한 개선은 놀라운 것이 아닌 게 주어진 IO와 CoT는 서로 다른 단서, 결정에 변화주기, backtrack을 시도할 만한 메커니즘이 부족하기 때문이다.

 

표 3. Mini Crossword 결과

 

Oracle and ablation studies.  task 당 oracle best DFS state로부터 출력할 때, ToT 성능은 높아지고 7개의 게임을 풀어버린다. 이것은 논문의 간단한 output 휴리스틱이 개선되었다는 것을 가리킨다. 

 

 

5. Discussion

Limitations and future directions.  ToT는 이미 GPT-4가 충분히 좋은 성능을 보여주는 task에서 별로 필요하지가 않다. 그래서 이 논문에서는 기존의 LM들이 어려움을 겪던 3개의 task에 대해서 실험을 진행하였는데 좋은 모습을 보여주었다. 하지만 앞으로 LM은 real-world에서 사용될 것이기에 더욱 복잡한 task를 수행할 수 있는 능력이 필요하다. 또한 ToT 같은 검색 method는 task 성능을 향상하기 위해 일반 샘플링 method보다 더 많은 자원을 필요로 하지만, ToT의 modular 융통성은 사용자들이 이러한 performance-cost tradeoff를 커스터마이징 하도록 허락해 주고 계속 진행되는 open-source화는 가까운 미래에 이러한 비용을 순조롭게 줄여나갈 것이다. 마지막으로 이 논문에서는 off-the-shelf LM을 사용하는데 집중하였고, ToT-style의 high-level counterfactual decision making을 사용해서 LM을 fine-tune 하는 것은 LM의 문제 해결 능력을 향상시키는 기회를 줄 것이다.

 

 

 

 

출처

https://arxiv.org/abs/2305.10601

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

https://betterprogramming.pub/tree-of-thoughts-an-improvement-of-chain-of-thoughts-paper-review-7c52171602bd

Tree of Thoughts: An Improvement of Chain of Thoughts (Paper Review)