Tree of Thoughts Review

논문 관련 링크

1. arXiv 논문 링크
2. 프롬프트 엔지니어링 가이드 링크
3. 깃허브 레포지토리 링크
4. 논문 리뷰어의 원 글

1. 논문의 동기

1) 풀고자 하는 문제

언어 모델의 추론은 한 방향으로의 의사 결정 과정에 제한되어 전략적 탐색이나 초기 결정이 중요한 태스크에 한계가 있다. 필요하다면 추론에서의 더 앞을 예측하거나, 이전 과정을 되돌아가면서 선택을 할 수 있어야 한다. 어떻게 언어 모델이 추론 중에 의도적인 결정을 할 수 있을까?

2. 관련 논문과 기여

1) 문제의 이전 접근법

• IO (Input-Output) - 기본 LLM의 동작
• CoT (Chain of Thought) - 주어진 문제에 대해서 차례대로 해결하도록 중간 생각을 강요
• CoT-SC (Self Consistency with CoT) - CoT를 여러 갈래로 수행하고 이를 Voting
• ToT (Tree of Thoughts) - Search와 back tracking을 최적의 해를 찾는 시도

2) 이전 접근법의 한계

논문에서 저자들은 크게 기존 LLM의 접근 방법의 단점에 대해서 언급.

1. 지역적 관점: 사고 과정 내에서 연속성을 탐색하지 않음.
2. 전역적 관점: 생각을 한방향으로만 진행함. 백트래킹을 수행하지 않음.

3) 이 논문의 기여점

연구는 사람의 의사 결정을 다음과 같이 구분한다.
1. System 1 : 빠르고 무의식적으로 하는 행위들 → 현재 LLM과 유사
2. System 2 : 정교하고 의식적으로 천천히 하는 행위들 → LLM이 이것과 같이 행동하도록 만들어보자는 아이디어.
따라서 Tree of Thought (ToT) 프레임워크는 중간 단계인 "생각"을 고려하여 의도적인 결정을 수행할 수 있도록 함.

3. 논문의 방법

논문은 이 프레임워크를 Combinatorial Problem Search으로 간주하여 수행함.

• Node : 중간 단계의 생각
• Edge : 생각의 순서, 흐름
• Search Algorithm : BFS, DFS
• Lookahead and Backtracking : Self-Evaluate

구체적으로 ToT는 다음 네 가지 질문에 대한 답변을 기반으로 프로세스가 구성되어 있음.

1. How to decompose the intermediate process into thought steps.
2. How to generate potential thoughts from each state.
3. How to heuristically evaluate states/
4. What search algorithm to use.

1. Thought Decomposition :

• CoT는 명시적 분해 없이 일관된 형태로 사고를 샘플링.
• ToT는 문제 특성을 활용하여 중간 사고 단계를 설계하고 분해.

2. Thought generator - Sample, Propose :

• 다음 사고 step에 어떤 후보 답변을 생성할지
  Sample : CoT와 같이 i.i.d로 부터 답변을 생성. 사고의 space가 넓은 경우 (창의적 답변 생성)
  Propose : Sequentially하게 답변을 생성. 문제의 제약이 있는 경우 (Game of 24)
  

3. State evaluator :

• 문제 해결에 대한 진행 사항을 평가.
  Value : 각 상태를 독립적으로 평가.
  Vote : 다른 상태와의 비교를 통해 투표로 평가.
  

4. Search algorithm :

• BFS
• DFS

4. 논문의 실험

1) Game of 24

• 이미 b=1부터 성능이 45%로 기존의 방법론들보다 훨씬 좋은 결과를 내는 것을 볼 수 있음.
  (여기서 의문은 b=1이면 사실 CoT와 큰 차이를 보이면 안될 것 같은데..)
• CoT의 경우 첫 단추에서부터 실패하는 경우가 많음. ToT의 경우 각 스텝별로 5개의 생각을 하기 때문에 상대적으로 초반의 오답율이 적음.

2) 창의적 글쓰기, 크로스워드

• 해당 Task에서도 ToT를 활용하는 경우가 더 성능이 좋게 나온 것을 확인할 수 있음
• backtrack을 하는 것이 성능에 영향을 크게 주는 것을 확인할 수 있음

5. 한계와 결론

1) 한계와 결론

• ToT가 아니더라도 GPT-4에서는 잘 되는 많은 태스크들이 있음.
• 코드 실행에서 알 수 있지만 비용이 들어가는 구조
• Fine tuning한 LLM이 ToT에 알맞는 구조로 답변을 생성한다면 더 잘 될 여지가 있음.

2) Tree of Thoughts Git Repository 실행

---

https://github.com/princeton-nlp/tree-of-thought-llm

Game24 Task에 대해서 ToT Task 수행 결과.

• Task 자체는 각 API마다 다르지만 대략 3~5분 정도 안에 모든 Task가 수행되는 것을 확인.
• 논문에서도 나와있듯이 gpt-4로 수행을 했을 때, 정확한 결과를 얻을 수 있음.
• Base 탐색 Rule은 BFS를 사용함.

gpt-3.5-turbo :

import argparse
from tot.methods.bfs import solve
from tot.tasks.game24 import Game24Task

args = argparse.Namespace(backend='gpt-3.5-turbo', temperature=0.7, task='game24', naive_run=False, prompt_sample=None, method_generate='propose', method_evaluate='value', method_select='greedy', n_generate_sample=1, n_evaluate_sample=3, n_select_sample=5)

task = Game24Task()
ys, infos = solve(args, task, 900)
print(ys[0])

5 * 6 = 30 (left: 4 30 10)
30 - 10 = 20 (left: 4 20)
20 - 20 = 0 (left: 0 20)
20 - 0 = 20 (left: 0 20)

결과적으로 보았을 때, 정답에 도달하지 못함.

gpt4 :

import argparse
from tot.methods.bfs import solve
from tot.tasks.game24 import Game24Task

args = argparse.Namespace(backend='gpt-4', temperature=0.7, task='game24', naive_run=False, prompt_sample=None, method_generate='propose', method_evaluate='value', method_select='greedy', n_generate_sample=1, n_evaluate_sample=3, n_select_sample=5)

task = Game24Task()
ys, infos = solve(args, task, 900)
print(ys[0])

10 - 4 = 6 (left: 5 6 6)
5 * 6 = 30 (left: 6 30)
30 - 6 = 24 (left: 24)
Answer: (5 * (10 - 4)) - 6 = 24

정확한 결과를 도출할 수 있음.

다만, 논문에도 언급된 바와 같이 gpt4를 사용하는 경우 billing이 조금 더 나온다.

GPT-4를 호출한 경우 $1.41 / GPT-3.5-Turbo를 호출한 경우 $0.09

3) Tree of Thoughts Prompting 실행

---

Tree of Thoughts (ToT) – Nextra
해당 페이지 가장 하단에 있는 글을 인용해보면 다음과 같다.

Hulbert (2023)(opens in a new tab)은 Tree-of-Thought 프롬프팅을 제안했는데, 이는 ToT 프레임워크의 주요 개념을 단순한 프롬프팅 기법으로 적용하여 LLM이 단일 프롬프트에서 중간 생각을 평가하게 합니다. 샘플 ToT 프롬프트는 다음과 같습니다.

세 명의 다른 전문가들이 이 질문에 답하고 있다고 상상해보도록 해.
모든 전문가들은 자신의 생각의 한 단계를 적어내고,
그것을 그룹과 공유할거야.
그런 다음 모든 전문가들은 다음 단계로 넘어가. 등등.
만약 어떤 전문가가 어떤 시점에서든 자신이 틀렸다는 것을 깨닫게 되면 그들은 떠나.
그렇다면 질문은...

그렇다면 해당 프롬프팅을 이용해서 위의 Game24Task를 수행하면 어떤 결과가 나올까?
→ chat.openai.com에서 GPT-4로 해당 프롬프팅을 수행하였음

세 명의 다른 전문가들이 이 질문에 답하고 있다고 상상해보도록 해.
모든 전문가들은 자신의 생각의 한 단계를 적어내고,
그것을 그룹과 공유할거야.
그런 다음 모든 전문가들은 다음 단계로 넘어가. 등등.
만약 어떤 전문가가 어떤 시점에서든 자신이 틀렸다는 것을 깨닫게 되면 그들은 떠나.
그렇다면 질문은...

[4, 9, 10, 13]이 있을 때,
이 네가지 수를 전부 이용해서 사칙연산으로 24를 만드는 방법을 알려줘

물론, 세 가지 다른 전문가들의 협력을 통해 24를 만드는 방법을 찾아보겠습니다.

**전문가 1:**

1. 먼저 13을 4로 나눕니다. (13 / 4 = 3.25)
2. 그런 다음 10에서 3.25를 빼줍니다. (10 - 3.25 = 6.75)
3. 이제 6.75를 9로 나눠줍니다. (6.75 / 9 = 0.75)
4. 마지막으로 0.75에 4를 더해줍니다. (0.75 + 4 = 4.75)

**전문가 2:**

1. 먼저 9와 4를 더합니다. (9 + 4 = 13)
2. 그런 다음 13을 10으로 나눕니다. (13 / 10 = 1.3)
3. 이제 1.3에 13을 곱합니다. (1.3 * 13 = 16.9)
4. 마지막으로 16.9에 9를 빼줍니다. (16.9 - 9 = 7.9)

**전문가 3:**

1. 먼저 10을 4로 나눕니다. (10 / 4 = 2.5)
2. 그런 다음 13에 2.5를 더합니다. (13 + 2.5 = 15.5)
3. 이제 15.5에 9를 빼줍니다. (15.5 - 9 = 6.5)
4. 마지막으로 6.5에 4를 더합니다. (6.5 + 4 = 10.5)

세 전문가 모두 자신의 방법으로 24를 만들지 못했고,
결과적으로 그들 중 어떤 전문가도 틀렸음을 깨닫고 떠납니다.
따라서 현재까지의 시도로는 24를 만드는 방법을 찾지 못했습니다.

이후에 전문가를 여러명 고용해보았지만, 원하는 답을 얻을 수는 없었음. 해당 프롬프팅은 너비 기준으로는 동작하였지만, 깊이 있는 탐색을 수행하지 못함. 이러한 차이점이 Prompting으로 수행한 Game24Task가 잘 수행되지 않은 이유로 보임