Tree-of-thoughts는 더 많은 exploration과 중간 reasoning 과정의 평가를 통해 더 나은 의사 결정을 가능하게 하는 CoT의 발전된 버전 중 하나로, 줄여서 ToT라고도 부른다. 다양한 search나 planning 알고리즘들이 tree 형태로 의사 결정 과정을 expansion하여 이 중에 최적의 결정을 선택하고는 하는데, ToT도 이와 비슷하게 동시에 다양한 reasoning 과정들을 탐색하여 복잡한 문제를 더 정확하게 풀 수 있도록 한다. 이번 글에서는 이러한 ToT가 어떻게 작동하는지에 대해 알아보겠다.
Overview
Tree-of-thoughts는 앞서 설명한 것처럼 tree 형태로 다양한 reasoning 브랜치들을 생성하여, 이 중에 가장 나은 선택지들만을 선택하여 확장해나가는 방식으로 reasoning을 진행한다. 아래 그림에서 살펴볼 수 있듯이 기존의 CoT가 하나의 시퀀스 형태로 reasoning을 진행해왔다면, ToT는 tree 형태로 복수의 reasoning을 진행하여 그 중 가장 나은 reasoning을 선택하는 것이다.
ToT의 핵심 특징으로는 1) 동시에 다양한 reasoning을 진행함으로써 얻는 exploration 능력, 2) 중간 단계를 평가함으로써 얻는 높은 정확도, 그리고 3) hierarchical한 multi-level reasoning이 가능해 optimization이나 planning 문제 등을 더 잘 풀 수 있다는 점을 들 수 있다. 이러한 장점을 이해할 수 있는 예시를 하나 살펴보자. 아래 그림과 같이 네 개의 숫자를 활용해서 사칙연산으로 24를 만드는 게임을 하고 있다.
만약 우리가 기존의 CoT처럼 한 번에 하나의 reasoning 단계만을 거쳐왔다면, 맨 처음 오른쪽에 있는 4+9=13을 선택해서 절대로 답을 맞출 수 없는 상황이 될 수도 있을 것이다. 하지만 위 그림처럼 ToT를 활용하여 문제를 풀면, 동시에 생성한 reasoning step 중 정답으로 갈 수 있는 가능성이 있는 선택지가 있을 것이고, 해당 선택지에서 branching을 계속 진행하면 정답에 도달할 확률이 더 높아질 것이다.
Method
이제 이러한 ToT가 어떤 요소들로 구성되어 있는지를 알아보자. ToT는 1) thought decomposition, 2) thought generator, 3) state evaluator, 4) search algorithm으로 구성되어 있다.
Thought decomposition
Thought decomposition은 문제를 어떤 단계로 나눌지를 정의하는 것이다. 위에서 살펴본 예시처럼 우리가 24 게임을 할 때, 저렇게 하나의 식으로 하나의 단계를 표현할 수도 있겠지만, 두 개의 식으로 하나의 단계를 표현할 수도 있고, 하나의 숫자 혹은 연산자로 각 단계를 표현할 수도 있을 것이다. 각 단계를 작은 단위로 쪼개게 되면 더 다양한 생성을 할 수 있다는 장점을 가질 것이고, 각 단계를 큰 단위로 쪼개게 되면 단계를 평가하기가 쉽고 더 빠르게 답에 도달할 수 있다는 장점을 가진다.
Thought generator
Thought generator는 reasoning 단계를 어떻게 생성할 것인지를 결정한다. 이는 LLM을 활용해서 생성하는 것을 기본으로 하고, ToT 논문에서는 thought generator 방법을 두 개 제시한다. 첫 번째는 i.i.d sample prompt로, LLM의 input으로 propose prompt를 여러 번 넣어 thought를 생성하는 것을 말한다. 이러한 방법은 thought가 좀 더 풍부해진다는 장점을 가진다. 두 번째는, 아래 그림과 같은 sequential propose prompt이다. 즉, input을 여러 번 넣지 않고, 여러 thought를 한 번에 sequential하게 생성하는 것을 말한다.
State evaluator
State evaluator는 각 state가 계속 branch를 확장해도 될 만큼 좋은 state인지를 평가한다. 이 또한 LLM을 활용하는데, 이 방법에는 두 가지가 있다. 첫 번째는 각 state의 value를 LLM으로 평가하는 방법이다. 예를 들어, 아래 예시처럼 어떤 답을 만들었을 때 이 답이 확실한지(sure), 그럴듯한지(likely), 혹은 아예 불가능한 답인지(impossible)를 LLM이 평가하게 하여 sure과 likely들만 branching하는 식이다.
두 번째는 voting이다. 현재 단계에서 만들어진 모든 state들을 input으로 넣고, LLM이 이들을 대상으로 투표하게 하여 가장 그럴듯한 것들을 branching하는 식이다.
Search algorithm
Search algorithm은 여러 개의 reasoning 단계들을 어떻게 확장해나가는지의 방식을 의미한다. 이에는 BFS와 DFS가 있다. 우선, BFS의 경우 위에서 살펴봤던 예시(아래 그림)처럼 가장 가능성이 높은 state들을 각 단계마다 일정 개수만큼 남겨놓고, 이들을 확장해나가는 방식이다.
다음으로, DFS의 경우 아래 그림처럼 처음부터 끝까지 답을 한 번 sequential하게 만들고, 위로 한 단계 올라가서(backtracking) 다시 다른 답을 확장하고, 이를 반복하는 방식이다.
Experiments
실험 결과는, 예상할 수 있듯이 ToT 방식으로 다양한 문제들을 풀었을 때 CoT 방식보다 좋은 성능을 보였다고 한다.
하지만 ToT를 활용할 때는 다양한 reasoning 단계들을 생성하기 때문에 당연히 더 비용이 더 많이 들고, 시간도 오래 걸린다는 단점을 가진다.
이번 글에서는 ToT가 무엇인지에 대해 알아보았다. 앞으로 다양한 LLM 관련 연구들도 차차 다루어보겠다.
References
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., & Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. NeurIPS 2023.
최근댓글