생각의 나무(Tree of Thoughts): LLM 검색을 통한 신중한 문제 해결

자기 수정을 수행하는 에이전트인 Reflexion과 도구 상호작용 비판인 CRITIC을 다룬 지난 두 편의 포스팅에 이어, 이번에는 좀 더 구조적인 접근 방식을 살펴보려 합니다. '에이전트가 애초에 단일한 추론 경로에만 의존하지 않는다면 어떨까?' 하는 질문입니다. Yao 등(NeurIPS 2023)이 제안한 생각의 나무(Tree of Thoughts, ToT)는 바로 이를 제안합니다. LLM이 하나의 선형적인 사슬이 아니라 중간 추론 단계들이 분기되는 검색 공간을 탐색하는 프레임워크입니다. 제가 지금 이 논문을 읽는 이유는 이것이 LLM 추론을 위한 '신중한 검색(deliberate search)'을 가장 명확하게 공식화하고 있기 때문입니다. 재무 계산에서 단 한 번의 잘못된 중간 단계가 후속 과정 전체를 조용히 망가뜨릴 수 있는 상황에서, 바로 이 신중한 검색이 필요합니다.

논문 요약

Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, Karthik Narasimhan은 생각의 사슬(Chain-of-Thought, CoT) 프롬프팅을 일반화한 '생각의 나무(Tree of Thoughts)'를 소개합니다. 핵심은 중간 추론 단계를 '생각(thought)'—독립적으로 평가할 수 있는 일관된 텍스트 단위—으로 취급하고, 이를 사슬이 아닌 트리 구조로 조직하는 것입니다. 각 노드에서 모델은 여러 개의 후보 생각을 생성하고, 별도의 LLM 호출을 통해 각 상태를 평가(예: "확실함 / 가능성 있음 / 불가능함"으로 점수 매기기)한 후, 표준 검색 알고리즘(BFS 또는 DFS)을 적용하여 트리를 탐색합니다. 특정 분기가 막다른 길로 보이면 모델은 이를 가지치기(pruning)하거나 백트래킹(backtracking)할 수 있습니다. 이는 CoT나 CoT-SC(Self-Consistency)가 할 수 없는 일입니다.

논문은 세 가지 과제에서 이를 평가합니다: 24 게임(사칙연산을 사용하여 4개의 숫자로 24 만들기), 창의적 글쓰기(4개의 무작위 문장 결말을 사용하여 일관된 문단 작성), 미니 십자말풀이(5×5 십자말풀이 해결). 세 과제 모두 탐색과 백트래킹의 이점을 얻을 수 있는 추론을 요구하며, 이는 저자들이 의도한 설정과 정확히 일치합니다.

핵심 아이디어

• 24 게임에서 빔 너비(beam width) b=5인 ToT는 74%의 성공률을 기록했습니다. 이는 표준 CoT를 사용한 GPT-4의 4%, **100개의 샘플을 사용한 CoT-SC의 9%**와 비교할 때 놀라운 격차입니다.
• GPT-3.5 + ToT는 동일한 작업에서 **19%**의 성공률만 기록했습니다. 이 방법의 이점은 모델 성능에 크게 의존합니다. 이득의 대부분은 GPT-4의 생각 생성 품질에서 나옵니다. GPT-4 생성 + GPT-3.5 평가는 64%를 달성한 반면, GPT-3.5 생성 + GPT-4 평가는 31%에 그쳤습니다.
• 창의적 글쓰기에서 ToT는 GPT-4 일관성 척도 기준 7.56점을 기록하여 CoT의 6.93점보다 높았으며, 인간 평가자들은 41/100 비율로 ToT 결과물을 CoT(21/100)보다 선호했습니다.
• 미니 십자말풀이: ToT는 60%의 단어 수준 정확도를 달성했지만(CoT: 40.6%, IO: 15.6%), 전체 게임을 해결한 경우는 20개 중 4개(20%)에 불과했습니다. 단어 수준과 게임 수준 성공률 사이의 격차는 백트래킹이 있더라도 전역 제약 조건(global constraint) 충족이 여전히 어렵다는 것을 보여줍니다.
• 평가 단계 자체가 LLM 호출입니다. 십자말풀이에서 평가자가 생소한 어휘 때문에 올바른 부분 상태를 "불가능함"으로 판단하는 경우가 가끔 발생했는데, 이는 평가자의 실수가 검색 전체를 오염시키는 복합적인 실패 모드입니다.
• 컴퓨팅 비용: ToT는 24 게임의 경우 사례당 약 $0.74가 소요되었으며, 이는 100개 샘플 CoT의 $0.47과 비교됩니다. 저자들은 GPT-4가 이미 잘 처리하는 작업의 경우 이러한 오버헤드를 감수할 가치가 없다고 지적합니다.

유효한 점과 그렇지 않은 점

중간 생각에 대한 트리 검색이 백트래킹이 필요한 작업에서 순차적 CoT보다 월등한 성능을 보인다는 핵심 결과는 실질적이며 재현 가능합니다. 24 게임에서 74% 대 4%의 격차는 단순한 오차가 아닙니다. 그 설명은 메커니즘적으로 타당합니다. CoT에서 단 하나의 잘못된 중간 방정식은 나머지 사슬을 엉뚱한 곳으로 보내버리지만, ToT는 해당 분기를 가지치기하고 다른 분해 방식을 시도할 수 있습니다.

설득력이 다소 떨어지는 부분은 일반화 가능성에 대한 주장입니다. 평가에 사용된 세 가지 작업은 수학 퍼즐, 구조적 제약이 있는 창의적 글쓰기, 단어 게임 등 비교적 인위적입니다. 실제 운영 환경의 재무 워크플로우에서 나타나는 개방적이고 모호한 문제와는 거리가 있습니다. 또한 저자들은 GPT-4(및 절제 연구를 위한 GPT-3.5)에서만 평가했기 때문에, 더 작거나 미세 조정된 모델에서 ToT가 어떻게 작동할지는 알 수 없습니다. GPT-3.5의 19%라는 수치는 "그다지 좋지 않을 것"임을 시사합니다.

게임 수준의 십자말풀이 실패(단어 정확도 60%에도 불구하고 해결률 20%)는 더 깊은 문제를 시사합니다. ToT는 국소적 평가자에 의해 유도되는 국소적 검색입니다. 하위 솔루션 간의 상호작용이 밀접한 문제에서 꼭 필요한 전역 제약 모델을 유지하지 못합니다. 후속 논문인 생각의 그래프(Graph of Thoughts, Besta 등, AAAI 2024)는 이 점을 명시적으로 비판하며, 생각을 트리에 가두지 않고 병합하거나 순환 구조를 형성하게 함으로써 정렬 작업에서 ToT보다 비용을 31% 이상 절감하면서 품질을 62% 개선했음을 입증했습니다.

마지막으로, 실제 적용 시 비용 구조가 중요합니다. 반복적인 평가자 호출을 포함하는 b=5 설정에서 ToT는 단일 CoT 패스보다 API 호출 비용이 대략 15~20배 더 비쌉니다. 지연 시간이나 비용에 민감한 애플리케이션의 경우, 이를 쉽게 받아들이기 어렵습니다.

금융 AI에 주는 시사점

솔직히 말해서, ToT는 Beancount 문제 영역의 좁은 부분에서 가장 중요하지만, 그 부분은 매우 실질적입니다.

백트래킹이 필요한 전형적인 재무 작업은 모호한 트랜잭션의 다단계 계정 분류입니다. LLM이 수입된 은행 명세서를 계정과목표에 매핑할 때, 체인의 초기 단계에서 잘못된 할당(예: 대출금 지급을 수입으로 처리)을 하면 몇 단계 후에 잔액 확인(balance check) 실패로 이어질 수 있습니다. CoT 에이전트에서는 잔액 확인이 실패할 때쯤이면 모델이 원래의 분류를 재검토할 메커니즘이 없습니다. 반면 ToT 에이전트는 해당 노드로 백트래킹하여 대신 Liabilities:Loans를 시도해 볼 수 있습니다.

마찬가지로, 전체 회계 연도에 걸친 세금 최적화는 진정한 트리 검색 문제입니다. 항목별 공제와 표준 공제 선택, 자본 이득 실현 시점 결정, 기부금 몰아내기(bunching) 등은 비선형적으로 상호작용하며, 결정을 내리기 전에 여러 분기를 평가해야 합니다. ToT의 BFS/DFS 프레임워크는 이러한 구조에 자연스럽게 들어맞습니다.

ToT가 도움이 되지 않는 부분은 Beancount의 대다수 사례인 일상적인 트랜잭션 입력 및 조정입니다. 장부에 명확한 대응 항목이 있는 트랜잭션의 경우, CoT + PAL(산술 계산을 코드 인터프리터에 위임)이 더 빠르고 저렴하며 이미 충분히 정확합니다. expenses:groceries 분류에 ToT를 사용하는 것은 압정을 박는 데 대형 해머를 사용하는 격입니다.

데이터 쓰기 안전성(write-back safety) 측면에서 더 시급한 문제는 평가자의 신뢰성 문제입니다. 상태 평가자 또한 LLM인 경우 틀릴 수 있으며, 잘못된 평가는 검색 속도를 늦출 뿐만 아니라 올바른 경로를 가지치기해 버립니다. ToT를 사용하는 실제 재무 에이전트는 평가자로 또 다른 LLM 호출을 사용하는 대신, 외부 오라클(잔액 확인, 스키마 검증기, 규칙 엔진)을 사용해야 할 것입니다.

더 읽어볼 거리

• Graph of Thoughts: Solving Elaborate Problems with Large Language Models (Besta et al., AAAI 2024) — arXiv:2308.09687. ToT를 트리에서 임의의 그래프로 확장하여 생각 병합 및 피드백 루프를 가능하게 합니다. 31% 이상의 비용 절감 주장은 ToT의 오버헤드 없이 검색 기반 추론을 원하는 경우 직접적으로 관련이 있습니다.
• Large Language Models Cannot Self-Correct Reasoning Yet (Huang et al., ICLR 2024) — arXiv:2310.01798. 비판적인 관점: 외부 피드백 없이는 내재적인 자기 수정이 추론 성능을 저하시킨다는 내용입니다. 이는 ToT의 LLM 기반 평가자가 검색을 유도할 만큼 충분히 신뢰할 수 있다는 가정에 의문을 제기합니다.
• RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation (arXiv:2409.09584) — BFS/DFS 대신 몬테카를로 트리 검색(MCTS)을 생각 검색에 적용하고, 실행 피드백을 외부 오라클로 사용합니다. 코드 생성 환경은 구조적으로 장부 기록과 유사합니다. 검증 가능한 정답(코드가 실행되는가? 잔액 확인이 통과되는가?)이 존재하며, 이는 MCTS 롤아웃이 가치를 더하는 지점입니다.