[Substack] (번역)Understanding Three-Of-Thoughts in LLM Reasoning

• 오픈 스택의 아래 포스팅 내용 정리
• https://open.substack.com/pub/thesequence/p/edge-359-understanding-tree-of-thoughts?utm_source=share&utm_medium=android&r=1ni8x5

In this Issue

• An overview of the tree-of-thought(ToT) LLM reasoning method.
• A review of the original ToT paper. from Princeton University
• Evaluating LLMs with the Language Model Evaluating Harness Framework.

Tree-Of-Thoughts의 장점

• 현재 LLM이 많은 영역에서 많은 문제를 해결 하고 있지만 그들의 inference process는 sequential decisions, 즉 left-to-right 방식에 의존한다.
• 따라서, exploration, strategic foresight or 초기 결정의 영향이 상당히 큰 문제의 경우 LLM의 추론 방식이 적절하지 않을 수 있다.
• ToT는 기본적으로 CoT의 Approach에서 출발하지만, 문제 해결을 위한 intermediate Step이자 text로 표현되는 ‘thoughts’에 대해서 exploration이 가능하게 한다.
• ToT를 적용하게 되면 LM이 여러 reasoning paths를 고려 할 수 있기 때문에 조금 더 deliberate 한 decision-making을 가능하게 한다.
• 종국에는 탐색해온 reasnoing path들을 backtrack하는 것도 가능하다.

Tree-Of-Thoughts의 특징

• Thoughts-Centric tree 기법이 필요함
• 여기서 말하는 ‘생각’은 meaningful하고 coherent한 language sequence인데, 문제를 해결하기 위한 stepping stone이라고 보면 된다.
• 이 approach를 통해서 LLM이 purposeful한 인지 과정(cognitive process)을 할 수 있거나, 꼼꼼한 계획을 통해서 문제 해결을 해나갈 수 있게 된다.
• 이를 위해서는 생각을 generation 하고 evluation하는 과정이 조화롭게 이루어져야 한다.
• 이 과정에서는 마치 bredth-first search나 depth-first search 같은 알고리즘들이 ‘생각’이라는 영역에서 필요 할 수 있다.
• 

Original ToT Paper

• 23.05 Tree of Thoughts: Deliberate Problem Solving with Large Language Models
  • 벌써 Cite 300회?? DPO 페이퍼도 130회인데…;
• Combinatorial Problem space를 tree structure로 본다면, nodes가 partial solutions이고 branches를 solution을 수정하는 operator로 본다.
• 특정 브랜치를 선택하는 것이 문제 해결 과정이며 인간은 heuristic하게 branch를 선택함.
• LLM을 활용한 ToT famework은 다음 component를 포함
  • 1. Thought decomposition: 주어진 문제의 속성에 따라 생각을 분해하는 과정
    2. Thought generator: 주어진 상태에서 다음 상태에 대한 candidates를 생성하는 과정
    3. State Evaluator: 각기 다른 상태에서 발전한 progress들을 평가하고 further investigation을 할지 결정함
    4. Search Algorithm: 주어진 Tree structure를 탐색하는 다양한 알고리즘
• 페이퍼에서는 Game of 24를 예시로 설명
  • 주어진 4개의 숫자를 3번의 연산을 통해서 24로 만드는 것. 4,9,10,13 -> (10-4) * (13-9) = 24
  • 우선 3개의 스텝으로 나눔.
  • 매 스텝마다 5개의 선택지를 keep해야 함
  • LM은 각 candidate를 sure, maybe, impossible로 평가하기 위해 Prompting 됨.
•