Tree of Thoughts: 인공지능의 새로운 문제 해결 패러다임

최근 대규모 언어 모델(LM, Large Language Model)은 다양한 작업에 적용되며 그 성능을 입증해왔습니다. 하지만 대부분의 LM은 토큰 단위로 좌에서 우로 순차적인 선택을 수행하는 auto-regressive 메커니즘에 의존합니다. 이는 단순한 작업에는 효과적일 수 있지만, 탐구와 전략적 결정이 필요한 복잡한 문제에서는 한계에 부딪힐 수 있습니다.

이 한계를 극복하기 위해, 논문 *"Tree of Thoughts: Deliberate Problem Solving with LMs"*는 새로운 프레임워크인 **Tree of Thoughts (ToT)**를 제안합니다. ToT는 기존의 CoT (Chain of Thought)를 확장하여 모델이 문제를 해결할 때 다양한 경로를 탐구하고 더 정교한 결정을 내릴 수 있도록 합니다. 이를 통해 LM은 단순 토큰 생성기를 넘어 진정한 문제 해결자로 진화할 가능성을 보여줍니다.

반응형

---

기존 Prompting 방식과 한계

ToT를 이해하기 위해 먼저 기존의 주요 prompting 방식을 살펴보겠습니다:

1. Input-Output (IO) Prompting

가장 기본적인 방법으로, 입력 ‘x’에 대해 출력 ‘y’를 생성합니다. Task instruction과 함께 몇 가지 예시를 제공하여 모델이 주어진 문제에 대해 예측을 수행하게 합니다.

2. Chain-of-Thought (CoT) Prompting

단순한 입출력 매핑의 한계를 해결하기 위해, 중간 추론 단계를 추가하여 문제 해결 과정을 상세히 기술합니다. 각 중간 단계는 논리적으로 일관된 텍스트 단위로 구성됩니CoT는 복잡한 문제 해결 과정에서 중간 추론 단계를 통해 성능을 높이는 데 기여하지만, 초기 결정의 제약으로 인해 종종 탐구 범위가 제한되며, 이를 통해 후속적인 계획적 수정과 전략적 검색이 어려운 경우가 있습니다.

3. Self-Consistency with CoT (CoT-SC)

CoT의 향상된 버전으로, 동일한 문제에 대해 여러 개의 chain of thought를 샘플링한 후 가장 빈번한 출력을 선택합니다. 다양한 경로를 탐색할 수 있지만, 여전히 문제의 해결 과정에서 계획적 탐구나 backtracking은 제한적입니다.

---

Tree of Thoughts: 새로운 문제 해결 접근법

ToT는 기존 LM의 한계를 극복하기 위해 문제를 트리 구조로 표현합니다. 여기서 각 노드는 부분적인 솔루션(상태)을 나타내며, 가지(branch)는 상태를 발전시키는 다양한 선택지를 의미합니다. 이를 통해 ToT는 탐구, 평가, 검색 과정을 통해 문제를 해결합니다.

핵심 개념

1. Thought Decomposition 문제를 해결하기 위해 thought(생각)을 작고 의미 있는 단위로 나눕니다. Thought는 문제 유형에 따라 다양하며, LM이 유망하고 다양한 샘플을 생성할 수 있는 크기로 설정됩니다.
2. Thought Generator LM은 주어진 상태에서 다음 단계의 후보를 생성합니다. ToT에서는 두 가지 전략을 사용합니다:
   • Sample: 다양한 thought를 샘플링
   • Propose: 문제의 문맥에 맞춘 thought를 제안
3. State Evaluator 생성된 상태를 평가하여 유망한 상태와 그렇지 않은 상태를 구분합니다. 평가 방법에는 두 가지가 있습니다:
   • Value: 각 상태를 독립적으로 평가
   • Vote: 여러 상태 간 비교를 통해 가장 유망한 상태 선택
4. Search Algorithm ToT는 BFS(Breadth-First Search)와 DFS(Depth-First Search) 알고리즘을 사용하여 트리를 탐색합니다. BFS는 탐구 폭을 넓히고, DFS는 깊이 있는 탐구를 수행하며 필요 시 backtracking으로 대체 경로를 모색합니다.

ToT의 장점

• 일반성: IO, CoT 등 기존 방법들을 포함하는 확장된 형태
• 모듈성: thought 생성, 평가, 검색을 독립적으로 조정 가능
• 적응성: 문제의 특성과 LM 성능에 따라 유연하게 조정
• 간편성: 추가 학습 없이 기본 LM을 활용

---

실험 및 성능 사례

ToT의 성능은 세 가지 복잡한 task에서 입증되었습니다:

1. Game of 24

• Task: 주어진 네 숫자로 사칙연산을 사용해 24를 만드는 문제
• 결과: CoT의 성공률이 4%였던 반면, ToT는 74%의 성공률을 기록
• 특징: BFS를 사용해 각 단계에서 가장 유망한 thought를 선택

2. Creative Writing

• Task: 4개의 주어진 문장으로 일관된 4문단 텍스트 생성
• 결과: ToT는 IO와 CoT 대비 더 높은 일관성을 보여줌
• 특징: thought를 단계적으로 평가하며 계획적인 텍스트 생성

3. Mini Crosswords

• Task: 5x5 크로스워드 퍼즐 해결
• 결과: CoT의 단어 성공률이 16% 미만인 반면, ToT는 60%로 개선
• 특징: DFS와 backtracking을 통해 탐구 범위를 확장

---

ToT와 CoT의 주요 차이점

구조	단일 경로	트리 구조
탐구 방식	순차적 탐구	병렬적, 계획적 탐구
결정 과정	초기 결정에 제약	다양한 경로 탐색 및 평가
검색 알고리즘	없음	BFS, DFS 및 backtracking 지원
성능	제한적	복잡한 문제에서 우수한 성능

---

728x90

결론

ToT는 단순한 텍스트 생성 도구를 넘어 LM이 인간과 유사한 문제 해결 능력을 발휘할 수 있도록 하는 혁신적인 접근법입니다. CoT와 비교하여 더욱 정교한 탐구와 평가를 통해 복잡한 문제를 효과적으로 해결할 수 있음을 입증했습니다. 앞으로 LM이 더욱 복잡한 real-world task를 다루기 위해, ToT와 같은 검색 기반 프레임워크는 필수적인 역할을 하게 될 것입니다.

ToT는 단순히 새로운 기술이 아니라, 언어 모델의 한계를 확장하는 중요한 발걸음입니다. AI와 NLP 분야에 관심이 있다면, ToT를 통해 문제 해결 패러다임의 새로운 가능성을 탐구해보세요!