LLM 추론의 경우의 수를 탐색하는 Tree of Thoughts로 성능 향상 – Yao 2023.5

Chain of Thought이 추론을 단어 하나씩 순차적으로 생성해 접근하는 linear search인 반면, 다양한 작은 단계로 쪼갠 추론을 tree search처럼 찾는 방식인 “Tree of Thoughts”를 제안하는 논문. 복잡한 추론에 높은 성능을 보임 2023 5/17

저자: Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, Karthik Narasimhan

원문: https://arxiv.org/abs/2305.10601

Introduction

Human congnition를 dual process model로 설명함. System 1: fast, automatic, unconscious mode
System 2: slow, deliberate, conscious mode
예를 들어 인간, 동물의 강화학습은 model free learning, model based learning이 가능함

LM의 token-level choice는 System 1과 비슷함. 그 말은 System 2에 해당하는 방식으로 도움을 받을 수 있는 가능성이 있음.

(1) 하나의 경로를 따라가지 않고 다양한 가능성을 탐색하고

(2) 현재 상태를 평가해 앞으로 나아가거나 되돌아가는 방식으로 global decision을 할 수 있을 것

Tree of Thoughts (ToT)에서 thought은 “a coherent language seq that serves as an intermediate step toward problem solving” 이 한 단위는 self-eval을 통해 deliberate reasoning process에 활용됨. 탐색 알고리즘도 breadth-first, depth-first search등을 적용해봄.

GPT-4로도 풀기 힘든 세가지 문제(Game of 24, Creative Writing, Crosswords)에서 우월한 결과를 내는 것을 보임.

IO prompting: x를 instruction이나 few-shot example와 함께 넣어 y가 나오게 함
CoT prompting: X를 넣어 z[1…i]를 거쳐 y에 도달하게 함
CoT-SC: most frequent argmax output of iid chains of thought

사람은 문제 해결을 위해 combinatorial problem space를 탐색하는 방식을 이용한다고 알려져 있음. 위에 언급한 3가지 방식의 문제는 locally 다른 branch를 탐색하지 않음. globally 계획을 세우거나 되돌아가 탐색하는 방식을 이요하지 않음. 이런 단점을 극복하기 위해 ToT를 제안

ToT는 한 문제에 대해 해결과정을 트리로 만들고 각 노드가 state가 된다고 보고

1. intermediate process를 추론 단계 단위로 어떻게 쪼갤 것인가
2. 각 state에서 가능한 thought을 어떻게 생성할 것인가
3. 어떻게 경험적으로 state를 평가할 것인가
4. 어떤 탐색 알고리즘을 쓸 것인가

Methods

1. Thought decomposition
Thought 단위는 몇 글자(Crosswords)나 수식 한 줄(24)이나 한 문단(Creative writing)이 될 수 있음. LM이 여러 단위를 생성할 정도로 작으면서 평가가 가능한 정도로 충분히 커야

2. Thought generator
한 state에서 다음 thought step 후보 k개 생성을 위해 두가지 전략
(a) Sample iid thoughts from CoT prompt. iid generation이 충분히 diverse한 경우
(b) Propose with so propose prompt. constrained 상황에서 다양한 thought를 생성하도록 prompting

3. State evaluator
Heuristics는 탐색문제를 해결하기 위해 사전에 결정된(딥블루) 걸 이용하거나 학습한다(알파고). 여기서는 제3의 방식 LM이 state에 대해 deliberate reason하는 것을 이용.
(a) Value each sate independently. 현재 state를 scalar 또는 class 값으로 평가
(b) Vote across states. vote prompt를 이용해 각 S를 비교.
value, vote 모두 다음과 같이 BFS, DFS로 LM을 여러번 prompting

4. Search algorithm
(a) Breadth-first search(BFS): a set of b most promising state per step
(b) Depth-first search(DFS): most promising state에 대해 final output이 나올 때까지 search. backtrack해서 exploration

ToT는 general problem-solving 방식으로 볼 수 있다.
(1) Generality: IO, CoT, CoT-SC, self-refinement 모두 ToT의 한가지 형태로 볼 수 있음
(2) Modularity: decomposition, generation, evaluation, search procedure를 각각 다른 방식으로 적용 가능
(3) Adaptability: 문제에 따라, LM에 따라, 자원 제약에 따라 유연하게 적용 가능
(4) Convenience: pretrained LM을 추가학습 없이 그대로 사용 가능

4.1. Game of 24

예를 들어 4, 9, 10, 13이 주어지면 (10-4) * (13-9) = 24를 만드는 방식의 문제.
Baseline

• IO: 5-shot
• CoT: 위 예시에 3단계 intermediate equation 추가
• CoT-SC: (설명 이해 안 됨)

결과: baseline은 한자리수 성공률인데 비해 ToT(b=1)에서 이미 45%, b=5이면 74%의 압도적인 성능 차이.
ToT의 b=1…5 값에 따른 연산 회수와 best of k samples를 비교했을 때 CoT가 49%까지 올라가긴 함 (Figure3a)

4.2. Creative writing

문장 4개를 생성해 각 문장으로 끝나는 4개 문단을 작성하기. 결과의 coherency를 GPT-4 또는 사람에게 1-10점으로 평가
Baseline:

• IO: zero-shot
• CoT: 계획을 세워서 만들도록
• IO결과에 Iterative-refine method

결과: GPT-4의 평가 ToT 점수가 가장 높음. 사람이 평가했을 때도 100개 중 41개를 ToT쪽을 선호함.
iterative refine이 효과가 매우 큼. IO+refine 6.19->7.67, ToT+refine 7.56->7.91 iid, sequential generation보다 만든 것을 refine해서 좋은 새로운 생각을 만드는 것이 가능한 문제.

4.3. Mini crosswords

기존의 얕은 문제에 비해 탐색할 경우의 수가 훨씬 많음
Baseline

IO: 5-shot

CoT: intermediate words를 추가해줌

ToT: DFS 방식으로 가능성이 높은 가지를 탐색하다가 가능성이 없어지면 backtrack해서 다시 탐색.

proposal prompt 5회 실행해 다음으로 어디에 어떻게 채울지 결정. 남아있는 clue 중 impossible로 판단되는 경우가 생기면 해당 state를 prune하고 backtrack해서 다시 탐색 시작하는 방식.

결과: IO, CoT 성적이 매우 낮음. ToT는 단어 60%, 게임 20% 성공
그런데 정답에 가장 근접한 state만 뽑아서 보면(oracle setup) 35%에서 성공했음. GPT-4가 오타로 인식하는 레어 단어가 정답인 경우 등에서 State evaluator가 잘못 판단한 것. 하지만 pruning, backtrack을 없앤 경우 성능 급감

Related work

• Planning and decision making
• Self-reflection: “self-eval guided decoding” 매우 유사하지만 코드형태로 생각을 정리하는 PAL을 사용해 creative writing같은건 못함
• Program-guided LLM generation: reflection, voting이 없음
• Classical search method

Discussion

• 이미 GPT-4가 잘하는 데는 필요 없음
• 복잡하다고는 하지만 그래도 간단한 작업들이었음
• Modular하기 때문에 리소스 제약에 따라 맞춰 쓰면 됨(ex: performance-cost tradeoff)
• ToT-style에 파인튜닝하면 문제해결능력이 더 높아질 가능성이 있다
• 스스로 지능적인 문제해결을 하는 방식이고, interpretability가 좋아 alignment에 활용할 수 있다
• 가능한 문제 해결 경로를 탐색하는 System 2 방식을 적용해 성능을 올렸다.
• 구조화하기 어려운 창의적 글쓰기 같은 문제에도 적용 가능했다

My thoughts

• 인간의 사고에 대한 내용을 끌어와서 필연적인 것처럼 잘 설명했다.
• Figure 1과 같은 도식을 정말 잘 그렸다.
• 인간 사고와 비교한다면 Bias로 인해 reasoning에 오류가 발생하는 경우를 인간과 LLM과 비교해 줄여나가는 것을 보이면 좋을 것 같다.
• performance-cost trade-off에 대한 이야기가 있었는데, inference cost가 떨어진 경우를 가정해 parallelize 가능한 부분과 아닌 부분(5개 경우의 수를 동시에 생성한 뒤에 voting 5회를 동시에 수행하는 식. Backtrack하려면 1회 끝까지 가야함 등)을 고려한 시간 factor를 고려해야하지 않을까