✍🏼 한 줄 요약

• CoT를 넘어선 ToT를 제안하여, 단순한 Left-To-Right 문제 해결 방식을 뛰어넘는 방식을 제안. 단, 학습하는 방식이 아니라 Prompt 하는 방식임.

🔒 Problem

• 기존의 LLM은 Left-To-Right, Token-Level decision Process에 국한되어 있다.
• 그러므로, 탐험, 전략 예측 혹은 initial decision이 큰 영향을 끼치는(pivotal role) 문제에 대해서는 어려움을 겪을 수 있다.
• 인간의 의사결정에는 2가지 종류가 있다.
  • System1 : 빠르고 자동적인 무의식적 선택
  • System2 : 느리고 정교하고 의식적인 선택
  • 강화학습에서 associative Model Free, deliberative model based learning을 적용하는 연구를 진행

🔑 Main Ideas

• Chain of Thought에 기반한 ‘Tree of Thoughts(ToT)’ 라는 프레임워크를 제안
• 
• 적절한 Prompt를 사용해서, coherent unit of thought(text)를 문제를 풀기 위한 중간 step으로 만들어서 exploration.
• 이를 통해 multiple different reasoning path를 탐색하고 self-evaluation 하여 최적의 choice를 만들수 있음.
• ToT는 모든 문제를 Tree 구조로 만듦.
  • Each node: state, partial solution, input and the sequence of thought so far.
  • ToT를 만들기 위해서는 다음 4가지 질문에 답해야함
  • 1. How to decompose the intermediate process into thought steps
  • 1. How to generate potential thoughts from each state
  • 1. How to heuristically evaluate states
  • 1. What search algorithm to use.
• 1. Thought decomposition: 명시적으로 어떤 문제에 따라서 step을 나누지는 않지만, Task의 특성상 자연스럽게 추론이 가능한 step은 존재한다. a thought could be a couple of words (Crosswords), a line of equation (Game of 24), or a whole paragraph of writing plan (Creative Writing). thought의 사이즈는 너무 작아도 안되고, 너무 커도 안된다. 너무 작으면(예를 들어 토큰) 평가가 불가능하고, 너무 크면 다양한 path가 안나올 수도 있다.
• 2. Thought generator:
  • 1. CoT Prompt를 사용한 i.i.d Sampling 방법(thought가 paragraph 처럼 긴 경우 유리)
  • 1. Propose Prompt를 사용한 방법(thought 가 word, sentence 처럼 짧은 경우 유리)
• 3. State evaluator
  • Value 방식: Value Prompt를 사용해서 현재 상태에서 대해서 1-10까지 점수를 내거나 sure/likely/impossible 방식으로 classification함.
  • Vote 방식: Vote Prompt를 사용해서 가장 좋은 S를 찾음
• 4. Search
  • BFS 방식: 각 단계마다 가장 유망한 State를 b개(5) 저장. tree depth가 3개 정도로 작은 경우 유리
  • DFS 방식: 가장 유망한 State를 먼저 끝까지 탐색, 중간에 State Evaluator가 더 파고들지 판단
• 본 연구를 검증하기 위해 3가지 테스크를 만듦
  • 
  • Game of 24: 수리 추론 문제, 4개 숫자를 입력 받고 사칙연산으로 24를 만들어야함.
    • 
    • ‘4nums.com’에서 100개의 샘플만 뽑음(그러니까 학습 한 건 아니네)
    • 최대 3step, 각 step 당 5 state
  • Creative Writing: 4개 랜덤 문장을 입력받아서 4개의 문단을 만들되, 각 문단은 입력 받은 4개의 문장으로 끝나야함.(100개 샘플)
    • 이 Task는 groundtruth가 없으므로, GPT4에게 1~10점 사이로 평가하거나 사람이 직접 평가함.
    • 최대 2스텝
    • 
    • 처음에 이 문제를 해결하기 위한 5개의 Plan을 생성 -> Vote를 통해 최적의 Plan선택. -> Plan 기반으로 5개의 output을 생성 -> voting 해서 최적의 답을 선택
  • Crosswords: 5X5 단어퍼즐 게임
    • 5개의 세로, 5개의 가로 힌트가 주어지고 최종 output은 5x5=25개의 글자로 이루어짐
    • 평가를 위해 correct letters, words, games를 만들어 냈는지 평가
    • DFS 적용. 일단 가볼 수 있는데까지 가보고 막히면 다시 parent node로 backtrack.
    • 가로 5개 단어, 세로 5개 단어이므로 총 10개의 Step
    • 각 state 마다 지금까지 나온 단어들과 proposal prompt를 활용해서 5번 물어봐서 다음 단어를 생성함
    • 
    • 지금까지의 state(thought)를 입력할 때, LM에게 Confidence Level을 매기게 해서 가장 확신있는 답변이 가장 위로 오도록 해서 입력함.

📈 Results

• Game of 24 Results
  • 
  • CoT의 경우, 60%가 이미 시작부터 글러먹었는데, Left-to-right Decoding 방식의 경우 이를 다시 거스를 방법이 없으므로 ToT의 우수함을 엿볼 수 있다.
• Creative Writing
  • 
• Mini crosswords
  • 
  • +best state: DFS 할 때, 휴리스틱하게 ordering 하는게 아니라 진짜 최고 좋은 order로 search 할 경우
  • -prune: imposibble state에 대해 prune 하지 않음
  • -backtrack: backtracking하지 않고 greedy하게 가장 좋은 단어들로 채우기

Limitations

• 학습에 관한 논문이 아니라, prompt를 적절히 활용해서 문제를 해결해보는 Task.
• 저자가 말하는 한계
  • 많은 task에서 ToT가 다 필요한건 아님.
  • CoT 대비해서 Cost가 많이 듦

Appendix

• GSM8K, StrategyQA에도 적용해봄.

✏️ Conclusion

• ToT를 제안해서, 전통적인 LM의 문제 해결 방식을 보완할 수 있는 방법을 제시함

❔ Questions

• 우리가 풀어야 하는 5개 Task들에 대해서 CoT, ToT를 적용 할 수 있을까?