Tree of Thoughts (ToT)

사고 트리(ToT)는 프롬프트 엔지니어링 프레임워크로, 대규모 언어 모델(LLM)이 부분적으로 완성된 해법의 트리를 탐색하여 문제를 해결합니다. 매 단계에서 모델은 다음 단계 후보를 여러 개 제시합니다. 이를 사고라고 하며, 모델은 각 후보가 만든 상태의 유망성을 평가하고 탐색 알고리즘은 확장하거나 유지하거나 포기할 분기를 결정합니다. 첫 번째 토큰부터 하나의 추론 경로를 따라가는 연쇄 사고 프롬프팅과 달리 ToT는 앞을 내다보고 되돌아갈 수 있습니다. Princeton University와 Google DeepMind의 Shunyu Yao와 동료들은 NeurIPS 2023에서 발표된 사고 트리: 대규모 언어 모델을 이용한 숙고형 문제 해결 논문에서 ToT를 소개했습니다. Jieyi Long도 같은 달에 LLM으로 스도쿠를 풀기 위한 유사한 트리 탐색 시스템을 제안했습니다. 24 게임 퍼즐에서 ToT는 GPT-4의 성공률을 연쇄 사고 프롬프팅을 사용했을 때의 4%에서 74%로 높였습니다.

사고 트리 작동 방식#

Yao 등은 네 가지 설계 요소를 통해 ToT를 정의합니다.

• 사고 분해: 하나의 단계가 무엇인지 정합니다. 24 게임에서는 사고가 방정식 하나이고, 창의적인 텍스트 생성에서는 글의 계획이며, 십자말풀이에서는 놓을 단어 하나입니다.
• 사고 생성기: 후보를 생성하는 방법입니다. 모델은 개방형 단계에 적합하도록 여러 사고를 독립적으로 샘플링하거나, 선택지가 제한된 경우 중복을 피하기 위해 하나의 프롬프트에서 서로 다른 선택지 목록을 제안합니다.
• 상태 평가기: 진행 상황을 판단하는 방법입니다. 모델은 각 상태를 개별적으로 평가하여 목표에 도달할 가능성을 "확실", "가능성 있음", "불가능" 등으로 표시하거나 여러 상태 중 가장 나은 것을 투표로 선택합니다. 이러한 평가는 고전적 탐색에서 사람이 작성한 점수 함수가 담당하는 탐색 휴리스틱 역할을 합니다.
• 탐색 알고리즘: 트리를 탐색하는 방법입니다. 너비 우선 탐색은 각 단계에서 가장 좋은 b개 상태를 유지합니다. 깊이 우선 탐색은 가장 유망한 분기를 따라가며 평가기가 배제한 상태를 가지치기하고 되돌아갑니다.

예시: 24 게임#

24 게임에서는 네 개의 숫자를 각각 한 번씩 사용해 +, -, x, / 연산으로 24를 만들어야 합니다. ToT는 해법을 세 단계로 나누며 각 단계에서는 방정식 하나를 통해 숫자 두 개를 결합합니다. 입력이 4, 9, 10, 13일 때 제안 프롬프트는 다음과 같은 후보를 나열합니다.

13 - 9 = 4 (left: 4 4 10)
10 - 4 = 6 (left: 6 9 13)
4 + 9 = 13 (left: 10 13 13)
4 x 13 = 52 (left: 9 10 52)

그다음 값 프롬프트는 남은 숫자 집합으로 24를 만들 수 있는지 묻습니다. "4 4 10"은 (10 - 4) x 4 = 24이므로 확실하며, "6 9 13"도 (13 - 9) x 6 = 24이므로 확실합니다. 반면 "10 13 13"과 "9 10 52"는 불가능하므로 탐색은 앞의 두 분기만 확장합니다. 첫 번째 분기를 따라가면 10 - 4 = 6(남은 수: 4, 6), 이어서 4 x 6 = 24가 됩니다.

논문에서는 어려운 게임 100개를 대상으로 한 실험에서 너비 우선 탐색으로 단계마다 가장 좋은 상태 5개를 유지하고 각 상태를 세 번씩 평가했습니다. GPT-4를 사용한 ToT는 게임의 74%를 해결했습니다. 직접 프롬프팅은 7.3%, 연쇄 사고는 4.0%, 자기 일관성을 적용한 연쇄 사고는 9.0%를 해결했습니다. 연쇄 사고를 100개 샘플링한 결과 중 가장 좋은 것도 49%에 그쳤으며, 단계마다 상태 하나만 유지한 ToT는 45%를 해결했습니다.

사고 트리의 활용 분야#

초기 선택이 이후 단계의 선택을 제약하고 잘못된 첫 단계를 바로잡기 어려운 퍼즐, 계획 수립, 다단계 수학 문제에서 ToT가 유용합니다. 5×5 미니 십자말풀이에서는 가지치기를 적용한 깊이 우선 ToT가 단어의 60%를 정확하게 채우고 게임 20개 중 4개를 풀었습니다. 비용은 연산량입니다. 트리의 각 수준마다 생성 및 평가 호출이 여러 번 필요하므로 단일 답변에도 수십 회 이상의 모델 호출과 하나의 추론 경로보다 훨씬 많은 토큰이 필요하며, 이에 상응하는 추론 지연 시간이 발생합니다.

생성, 평가, 확장의 동일한 루프는 하이퍼파라미터 튜닝과 같은 자동화된 실험 탐색에서도 훨씬 큰 단위로 나타납니다. Ultralytics Platform AutoTrain에서 Ask AI는 이미지 크기가 640, 800, 960인 경우처럼 설정 하나만 다른 여러 Ultralytics YOLO 모델을 학습하고, 검증 mAP50-95를 기준으로 완료된 실행 결과를 비교한 뒤 가장 좋은 결과를 바탕으로 다음 실험을 제안할 수 있습니다.

사고 트리와 관련 방법 비교#

• 연쇄 사고 프롬프팅: 레벨마다 분기가 하나인 트리에 해당하는 단일 추론 경로입니다.
• ReAct 프롬프팅: 추론과 외부 환경에서의 검색 또는 도구 호출 같은 행동을 번갈아 수행하고, 행동의 결과를 바탕으로 다음 단계로 나아갑니다. ToT는 모델 자체가 생성한 사고 후보를 탐색합니다.
• 자기 일관성: 여러 개의 완전한 추론 경로를 샘플링하고 최종 답변에 대해 다수결을 적용하며, 중간 단계는 평가하지 않습니다.
• 생각 그래프: 생각을 병합하고 정제할 수도 있는 그래프로 트리를 일반화한 방식이며, ToT보다 비용을 31% 이상 낮추면서 정렬 품질을 62% 개선했다고 보고했습니다.
• 몬테카를로 트리 탐색(MCTS): AlphaGo의 기반이 된 탐색 알고리즘으로, 새로운 분기를 탐색하는 것과 유망한 분기를 활용하는 것 사이의 균형을 맞추며, 생각을 탐색할 때 너비 우선 탐색이나 깊이 우선 탐색을 대체할 수 있습니다.
• 추론 모델: 강화 학습으로 학습되어 한 번의 생성 과정에서 긴 추론 경로를 작성하며, ToT는 일반 모델 주변에서 외부 검색 프로그램을 사용해 분기와 백트래킹을 수행합니다.