Tree of Thoughts: Deliberate Problem Solving with Large Language Models

https://arxiv.org/abs/2305.10601

---

Abstract:

• LLM 이 다양한 작업에서 일반적인 문제 해결에 점점 더 많이 활용되고 있지만 여전히 추론 작업에서는 왼쪽에서 오른쪽으로 한방향으로만 진행되도록 처리하는 한계점이 있다고 함.
• 이러한 제한적인 탐색 방법은 한계가 있다라고 한다:
  • 탐색이 필요한 작업에 적합하지 않음:
    • 이건 문제 해결 과정에서 가능한 여러 해결 경로를 살펴보고 시험해 보는 과정을 의미함.
    • 모델은 여러 가지 옵션을 시도해 보면서 어떤 경로가 가장 적절한지 탐색하는게 필요한데, 이것에서 어려움을 겪는다고 한다.
  • 전략적으로 미래의 일을 보고 현재의 선택을 조정하는데 적합하지 않음:
    • 모델이 한 단계씩 단순히 이동하는 것이 아니라 향후 발생할 가능성을 예측하면서 그에 따라서 자신의 경로를 조정하는게 필요하다고 한다.
    • 예를 들면 체스와 같은 게임을 말함.
    • backtracking 이 가능해야함.
  • 문제 해결에서 초기 결정에 유연함을 주기에 적합하지 않음:
    • 첫 결정에 너무 영향을 받지 않도록 하고, 만약 검토 후 적합하지 않다면 다시 다른 선택을 할 수 있도록 가능해야함.
• 이러한 한계점을 해결하기 위해서 저자는 ToT (Tree of Though) 를 제안한다. ToT는 문제 해결을 위한 중간 단계로서 여러 생각들을 탐색할 수 있도록 함으로써 추론 능력을 향상시키는 기법임.
• ToT 에서는 언어 모델이 여러 가지 다양한 추론 경로를 고려하고, 스스로 선택을 평가하여 다음 행동을 결정할 수 있도록 될거임. 필요에 따라서 앞으로의 결과를 예측하거나, 이전 단계로 돌아가 전반적인 선택을 조정하는 등을 할 수 있을 것.
• ToT 를 24 게임(Game of 24), 창의적 글쓰기(Creative Writing), 미니 크로스워드(Mini Crosswords) 등 세 가지 새로운 작업에서 실험했을 때 성능이 크게 향상되었다고 함.
• 특히 24게임에서 GPT-4 는 4% 만이 문제를 해결했지만 ToT 를 쓸 경우 74% 의 성공률을 달성했다고 한다.
• 24게임은 덧셈, 뺄셈, 곱셈, 나눗셈을 사용해서 24가 되도록 만드는 것이 목표임.

 

 

Introduction:

• LLM 의 추론 매커니즘은 여전히 오토회귀(autoregressive) 메커니즘이 있음:
  • 이는 텍스트를 생성할 때 토큰 수준의 결정을 좌에서 우로 하나씩 진행하는 방식이다.
• 이런 방법은 LLM 이 인간과 같은 사고 모델을 가지기에는 적합하지 않음. 왜냐하면 인지 과학에 대한 문헌을 보면 인간은 사고 모델이 2개가 있기 때문임:
  • 빠르고 자동적이며 무의식적인 모드(“시스템 1”)
  • 느리고 신중하며 의식적인 모드(“시스템 2”)
• 현재의 Autoregressive 매커니즘은 시스템 1임.
• 시스템 2의 기능은 현재 상황에 대해서 하나의 전략만 고려하는게 아니라 다양한 대안을 유지하고 탐색하고 backtracking 이 가능하고 미래를 보고나서 전반적인 결정을 내리는게 가능해야함.
• 그래서 저자는 ToT 를 제안한다. 문제 해결을 위한 탐색이 Tree 구조와 유사하다고 생각하기 때문에.
• ToT는 생각의 나무(tree of thoughts)를 유지하며, 여기서 각 “생각(thought)“은 문제 해결을 향한 중간 단계로서의 일관된 텍스트 시퀀스임. 이러한 고수준의 의미 단위는 언어 모델이 스스로 평가하여 다양한 중간 생각들이 문제 해결을 향해 얼마나 진행되고 있는지를 판단할 수 있게 해준다.
• ToT 에서는 다양한 생각을 해보고 평가하는 방법으로 BFS 또는 DFS 와 결합해서 탐색하는 매커니즘을 소개함.

 

 

Tree of Thought:

• "진정한 문제 해결 과정은 가용한 정보를 반복적으로 사용하여 탐색을 시작하고, 이를 통해 더 많은 정보를 밝혀내며, 마침내 해결책에 도달하는 방법을 발견하는 것이다." - 뉴웰(Newell)
• 기존 언어 모델이 문제 해결 과정에서 겪는 두 가지 주요한 제약:
  • 지역적 한계 (local limitations):
    • 언어 모델이 문제 해결 과정에서 하나의 특정 경로에만 집중하고, 다양한 경로(가지)를 충분히 탐색하지 못하는 점을 의미.
    • 기존 언어 모델은 일반적으로 토큰 수준에서 다음 단어를 예측하는 방식으로 텍스트를 생성함. 이 방식은 이전 문맥에 따라 좌에서 우로 하나의 고정된 경로만을 따라가면서 선택을 이어가는 형태임. 즉, 한 번 선택한 경로에 따라 다른 가능성을 탐색할 기회를 놓치게 된다.
    • 문제 해결에 필요한 다양한 사고 과정을 충분히 고려하지 못하게 됨.
    • ToT는 문제를 트리 형태의 구조로 표현하고, 노드를 생각(thought) 단위로 구성하여 여러 가지 가능한 사고 경로를 동시에 탐색할 수 있게 해준다.
  • 전역적 한계 (Global Limitations):
    • 문제 해결 과정에서 전반적인 계획, 앞보기, 그리고 백트래킹과 같은 전략적 접근이 부족함.
    • 오토회귀 방식을 따르기 때문에, 과거의 선택이 앞으로의 선택에 미칠 영향을 깊이 있게 평가하거나, 현재 선택이 전체 해결 과정에서 어떻게 기여할지 고민하지 못함.
    • 뭔가가 잘못되었다면 되돌아가는 방법을 택하지 못하거나, 문제 해결에 있어서 장기적인 계획을 세우지 못함.
• ToT의 구체적인 구현은 다음 네 가지 질문에 답하는 것을 포함한다:
  • 중간 과정을 어떻게 생각 단계(thought steps)로 분해할 것인가?
  • 각 상태에서 잠재적인 생각들을 어떻게 생성할 것인가?
  • 상태들을 어떻게 휴리스틱하게 평가할 것인가?
  • 어떤 탐색 알고리즘을 사용할 것인가?
• ToT 프레임워크의 구성요소:
  • 생각 분해(Thought Decomposition):
    • 문제 해결 과정을 작은 단위의 사고(thought) 단계로 나누는 것을 의미함.
    • 이 과정은 문제를 보다 체계적이고 효과적으로 풀기 위해 생각을 적절한 크기로 나누는 중요한 전략임.
    • 생각을 적절한 크기로 나누면 언어 모델이 한 번에 지나치게 많은 내용을 처리하지 않게됨.
    • 생각 분해는 각 생각(thought)을 언어 모델이 충분히 평가할 수 있을 정도로 적당히 크고 의미 있는 단위로 나누는 것이 목표.
    • 24 게임에서는 생각이 한 줄의 방정식일 수 있고, 창의적 글쓰기에서는 생각이 단락 단위의 아이디어가 될 수 있음.
  • 생각 생성기(Thought Generator):
    • 언어 모델이 문제 해결 과정에서 각 단계마다 다음 생각(thought)을 생성할 수 있도록 돕는 메커니즘임.
    • 즉, 현재 상태에서 가능한 여러 가지 다음 생각을 만들어 내어 문제 해결의 경로를 확장하는 역할을 한다.
    • 생각 생성기는 다양한 가능성을 탐색할 수 있도록 여러 가지 후보 생각들을 생성하고, 어떤 경로가 문제 해결에 적합할지 선택할 수 있게됨.
    • ToT는 생각 생성기에서 두 가지 전략을 사용:
      • 독립적인 샘플링(i.i.d. 샘플링):
        • 생각의 공간이 넓고, 각 생각이 비교적 긴 텍스트 단위(예: 창의적 글쓰기에서 한 단락)일 때 적합함.
        • CoT 프롬프트를 사용하는 기법.
        • 독립적으로 여러개의 생각을 만드는 것. 다양한 생각을 만드는 것이기도 하다.
        • 예시로 창의적 글쓰기 문제에서는 다음 단락을 작성하기 위해 다양한 스토리 전개 가능성을 독립적으로 샘플링하여 여러 후보 생각을 얻을 수 있다.
      • 순차적인 제안(propose prompt):
        • 생각의 공간이 제한적이고, 각 생각이 짧은 텍스트 단위(예: 24 게임의 한 줄 방정식, 크로스워드의 단어)일 때 효과적
        • 각 생각을 순차적으로 생성하는 방식으로, 동일한 문맥에서 여러 가지 후보를 제안하는 방식으로 중복을 피할 수 있다는 장점이 있음.
        • 예시로 24 게임 문제에서는 특정 계산을 통해 24에 도달할 수 있는 다양한 수학적 조합을 순차적으로 제안할 수 있음.
  • 상태 평가기(State Evaluator):
    • 언어 모델이 문제 해결 경로 중에서 가장 유망한 경로를 선택하고 탐색할 수 있도록 각 단계(상태)의 진행 상황을 평가하는 역할을 함.
    • 상태 평가기는 각 생각(thought)이 문제 해결에 얼마나 기여하는지 판단하여, 어떤 경로를 계속 탐색할지 또는 중단할지 결정함.
    • ToT는 문제를 여러 가지 경로로 풀어보며 최적의 해결 방법을 찾고자 할텐데, 모든 경로를 무작정 탐색하기에는 시간이 오래 걸리고 비효율적일 수 있음.
    • 따라서 상태 평가기가 각 상태의 진행 상황을 평가하여, 모델이 더 유망한 경로를 우선적으로 탐색하고 불필요한 경로를 가지치기(pruning) 하도록 돕는다.
    • ToT에서 상태 평가기는 문제의 특성에 따라 두 가지 평가 전략을 사용하여 각 상태의 가치를 판단함:
      • 독립적인 상태 평가 (Value Each State Independently)
        • 각 상태를 개별적으로 평가하여, 상태의 가치나 가능성을 수치로 나타냄.
        • 예를 들어, 상태가 얼마나 유망한지 1에서 10까지의 점수로 평가하거나, “가능성 있음”, “불가능함”과 같은 분류를 통해 상태의 가능성을 표현함.
        • 예를 들어, 24 게임에서 현재 상태에서 24에 도달할 가능성을 평가할 수 있음. 특정 숫자 조합이 24에 가까워지는지를 판단하거나, 잘못된 방향으로 가고 있는 상태를 가지치기하여 비효율적인 탐색을 가지치기 할 수 있다.
      • 상태 간 투표를 통한 비교 (Vote Across States):
        • 여러 상태를 서로 비교하여 가장 유망한 상태에 투표하는 방식임.
        • 이 방법은 각 상태가 문제 해결에 얼마나 기여할지를 비교하여 가장 유망한 상태를 선택하는 것.
        • 문제의 성공 여부를 직접 평가하기 어려울 때(예: 창의적 글쓰기에서 글의 일관성 평가), 여러 상태를 비교하여 가장 유망한 것을 선택하는 방식이 효과적임.
        • 예로 창의적 글쓰기 문제에서는 여러 가지 스토리 전개 방안을 비교하여, 가장 흥미롭고 일관성 있는 방향에 투표하여 선택할 수 있을 것.
  • 탐색 알고리즘(Search Algorithm):
    • 생성된 여러 생각(thought) 경로 중에서 가장 적합한 경로를 선택하고 탐색하는 메커니즘임.
    • 탐색 알고리즘은 트리 구조에서 각 노드를 탐색하는 순서와 방식을 정의하며, ToT의 효과적인 문제 해결 과정에서 핵심 역할을 할 것.
    • ToT 프레임워크는 여러 경로를 동시에 생성하고 평가하여 다양한 해결 방안을 탐색하지만 모든 경로를 탐색하는 것은 시간과 자원을 낭비할 수 있으므로, 가장 유망한 경로를 선택해 우선 탐색하고, 불필요한 경로는 가지치기(pruning)하는 것이 중요함.
    • ToT 프레임워크는 트리 구조를 탐색하기 위해 너비 우선 탐색(BFS) 과 깊이 우선 탐색(DFS) 의 두 가지 간단한 탐색 알고리즘 사용함:
      • 너비 우선 탐색 (Breadth-First Search, BFS):
        • BFS는 각 단계에서 가장 유망한 상태들 중 일부를 선택하여 모든 상태를 조금씩 탐색하는 기법임.
        • 즉, 한 단계씩 내려가면서 트리의 각 노드를 모두 탐색해 나가는 방식
        • 문제 해결 경로의 깊이가 깊지 않은 경우 (예: 트리의 깊이가 3 이하) 효과적임.
        • 따라서 24 게임이나 창의적 글쓰기와 같은 문제에서 사용할 수 있다.
        • 초기 단계에서 다양한 경로를 동시에 탐색하기 때문에, 여러 가능성을 고려하면서 각 경로를 평가할 수 있다.
        • 경로가 깊어질수록 많은 자원을 필요로 할 수 있어, 깊이가 깊은 문제에서는 비효율적일 수 있음.
      • 깊이 우선 탐색 (Depth-First Search, DFS):
        • DFS는 가장 유망한 경로를 먼저 깊게 탐색하는 방법.
        • 즉, 한 경로를 따라 가능한 깊이까지 내려가며 문제 해결을 시도하고, 실패하면 다시 부모 노드로 돌아가 다른 경로를 탐색하는 방식임.
        • 문제 해결 경로의 깊이가 깊거나 중간에 가지치기가 필요할 때 유용하다.
        • 특정 경로를 깊게 탐색할 수 있어, 빠르게 유망한 결과를 발견할 가능성이 있음.

 

 

Game of 24 실험 및 결과:

• 24 게임은 수학적 추론 능력을 요구하는 도전 과제로, 주어진 네 개의 숫자와 기본 사칙연산(+, -, ×, ÷)을 사용하여 결과값이 24가 되도록 만드는 것이 목표인 게임임.
• 실험 설정:
  • 4nums.com에서 데이터를 수집하였는데, 이 사이트에는 난이도에 따라 정렬된 총 1,362개의 게임이 있는데 이 중에서 901번부터 1,000번까지의 비교적 어려운 게임을 테스트에 사용함.
  • 각 과제에서, 입력된 숫자를 각각 정확히 한 번씩 사용하고, 결과가 24가 되는 유효한 등식을 출력하면 성공으로 간주했음.
• Baseline:
  • IO(Input-Output) 프롬프트: 5개의 인-컨텍스트 예제를 포함한 표준 입출력 프롬프트를 사용
  • CoT(Chain-of-Thought) 프롬프트:
    • 각 입출력 쌍에 세 개의 중간 계산식을 추가한 프롬프트.
    • 예를 들어, 입력이 “4 9 10 13”인 경우, 생각(thought)은 다음과 같을 수 있음:
      • 13 - 9 = 4 (남은 숫자: 4, 4, 10)
      • 10 - 4 = 6 (남은 숫자: 4, 6)
      • 4 * 6 = 24 (남은 숫자: 24)
  • CoT-SC (Chain-of-Thought Self-Consistency): CoT-SC 방식에서는 CoT 프롬프트에서 100개의 샘플을 생성한 후, 가장 많이 생성된 결과를 선택했다고 함.
  • IO-반복적 개선(Iterative-Refine):
    • IO 프롬프트를 기반으로 반복적인 개선 과정을 추가한 방식
    • 모델이 첫 번째 IO 출력이 정확하지 않다고 판단되면, 이전 히스토리를 참고해서 실수를 반영하고 답을 개선해라라는 피드백을 최대 10회까지 준 프롬프트
  • 각 게임에 대해, IO와 CoT 프롬프트, CoT-SC, IO-Iterative Refine를 사용하여 100번씩 샘플링하여 평균 성능을 측정했다고 함.
• ToT 설정:
  • 24 게임을 ToT로 구성하기 위해, 생각(thought)을 세 단계의 중간 계산식으로 분해했다고 함. (4개의 숫자가 있다면 두 번째 과정을 거치면 숫자가 두 개가 남을 것이니, 세 번째 과저에서 정답을 낼 수 있을 것)
  • BFS 탐색 알고리즘을 적용했다고 함.
  • ToT 프레임워크의 생각 생성기 구성 요소의 방법 중 하나인 생각 제안 (Propose Prompt) 를 써서 다음에 이어질 생각을 제안함:
    • 입력으로 "4 9 10 13" 이 주어진다면 제안 프롬프트에서는 다양한 생각을 만들어내는 역할을 함.
    • 다음에 이어질 생각 1: 4+9 = 13, 다음에 이어질 생각 2: 10 - 4 = 6 등등
    • 여러 경로를 동시에 고려하기 위한 것.
  • Propose Prompt 로 여러 다양한 탐색할 수 있는 생각을 만들어보고, Value Prompt 로 가능성을 판단해서 가지치기 하는거임.
  • Value Prompt 에서는 24에 가깝거나 도달 가능성이 높으면 “확실함(sure)”, 애매하면 “아마도(maybe)”, 그리고 도달 가능성이 낮거나 불가능할 것 같으면 “불가능함(impossible)” 으로 분류함.
  • 논문에서는 Value Prompt 로 각 단계에서 가장 유망한 5개의 생각만 남긴다고 함. 각 경로마다 5개의 유망한 생각을 남기는 것이 아니라, 현재 단계 전체에서 가장 유망한 상위 5개의 생각만 유지한다고 함.
• 실험 결과:
  IO, CoT, CoT-SC 프롬프트 방법은 이 과제에서 성능이 낮아 성공률이 각각 7.3% 달성했지만 ToT 에서 (b=5) 일 때 74%의 성공률을 보였다고 함.

 

 

Creative writing:

• 창의적 글쓰기 과제는 주어진 4개의 무작위 문장을 사용해 4단락으로 구성된 일관된 글을 작성하는 것임. 글의 마지막 문장은 각각 입력된 4개의 문장으로 끝나야 함.
• 실험 설정:
  • Random Word Generator에서 무작위 문장을 추출하여 100개의 입력을 구성.
  • 각 입력에 대해 정답 텍스트는 존재하지 않으므로, GPT-4의 제로샷 프롬프트를 사용하여 글의 일관성에 대해 1-10 점수를 매기거나, 사람의 평가를 통해 CoT와 ToT로 생성된 글의 일관성을 비교
  • 각 과제 출력에 대해 5개의 점수를 샘플링해 평균을 계산했으며, 평가 간 일관성이 있어 표준 편차는 약 0.56으로 나타남.
  • 저자 중 일부가 블라인드 테스트 방식으로 CoT와 ToT로 생성된 결과물의 일관성을 비교했고, 100개의 입력 중 각 결과물의 순서를 무작위로 섞어 평가함.
• baseline:
  • IO 프롬프트: 모델이 직접 일관된 글을 생성하도록 요청했음.
  • CoT 프롬프트: 먼저 짧은 계획을 세운 다음 글을 작성하도록 하였으며, 이 계획이 중간 생각(thought) 단계로 작동
  • 각 과제에 대해 IO와 CoT 샘플을 각각 10개 생성해서 사용
  • 반복적 개선(Iterative-Refine): 각 과제의 무작위 IO 샘플을 바탕으로 최대 5회까지 반복적으로 글을 개선하도록 설정.
• ToT 설정:
  • ToT 프레임워크에서는 깊이 2, 중간 생각 단계 1개로 구성된 트리를 설정했음.
  • 먼저 모델은 5개의 계획을 생성하고, 가장 적합한 계획에 투표한다.
  • 이후 가장 적합한 계획을 바탕으로 5개의 글을 생성하고, 가장 좋은 글에 투표한다.
  • BFS 탐색을 하며, b=1 로 각 단계마다 하나의 선택만 남긴다.
  • 각 단계에서 제로샷 투표 프롬프트를 사용하여 선택지 중 가장 유망한 것을 선택하도록 하였음.
• 실험 결과:
  • GPT-4 점수 비교: ToT는 평균 7.56점을 기록하며, IO (6.19점) 과 CoT (6.93점) 보다 더 일관된 글을 생성했다고 함.
  • 사람 평가: 사람 평가에서도 ToT가 CoT보다 더 일관성이 높다는 결과를 확인했음.
  • 반복적 개선 효과: 자연어 과제에서 반복적 개선 방법이 더 효과적임을 확인했음.

 

 

Limitaitons and Conclusion:

• GPT-4가 이미 뛰어난 성능을 보이는 많은 기존 작업에서는 필요하지 않을 수 있음.
• ToT와 같은 탐색 방법은 작업 성능을 향상시키기 위해 샘플링 방법보다 더 많은 자원(예: GPT-4 API 비용)이 필요하긴 함. 하지만 ToT의 모듈식 유연성은 사용자로 하여금 성능과 비용 간의 균형을 맞춤화할 수 있다.
• Tree of Thoughts 프레임워크는 문제 해결에 대한 고전적인 통찰을 현대의 언어 모델에 적용 가능한 방법으로 변환하는 방식을 제공함