저는 Tree of Thoughts 다음에 무엇이 올지 계속 생각해 왔습니다 — 추론 단계를 검색할 수 있다면, 행동까지 검색할 수 있지 않을까요? 이것이 바로 LATS(Language Agent Tree Search)가 하는 일이며, 제가 지금 이 논문을 읽고 있는 이유입니다. Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, Yu-Xiong Wang(ICML 2024, arXiv:2310.04406)의 이 논문은 추론, 행동, 계획을 단일 에이전트 프레임워크로 통합한 가장 명확한 종합이며, 결과는 정말로 무시하기 어렵습니다.
논문 개요
LATS가 해결하는 핵심 문제는 이전 에이전트 연구의 구조적 공백입니다. ReAct는 추론과 행동을 교차하지만, 궤적이 잘못되었을 때 되돌아가 다른 경로를 시도할 메커니즘이 없습니다. Tree of Thoughts는 추론 단계에 걸친 분기를 가능하게 하지만 내부 LM 지식에 의존합니다 — 검색 중에 도구를 호출하거나 외부 피드백을 받을 수 없습니다. Reflexion은 언어적 자기 수정을 추가하지만, 선형 재시도 루프는 대안을 탐색하지 않고 새 궤적에 고정됩니다. LATS는 적절한 Monte Carlo Tree Search(MCTS) 백본으로 세 가지 아이디어를 모두 융합하여, LLM 에이전트가 여러 분기를 탐색하고 실제 환경 피드백을 받으며 경로가 실패하면 역추적할 수 있게 합니다.
기술적 메커니즘은 6단계 MCTS 루프입니다: 선택(UCT 공식을 통해 다음 탐색 노드 선택), 확장(LM에서 n개 후보 행동 샘플링), 평가(하이브리드 가치 함수로 각 노드 점수화), 시뮬레이션(종료 상태까지 롤아웃), 역전파(조상 값 업데이트), 성찰(실패 시 무엇이 잘못되었는지에 대한 언어적 요약을 생성하고 컨텍스트로 저장). 가치 함수는 주목할 만합니다: V(s) = λ·LM(s) + (1−λ)·SC(s), 여기서 LM(s)는 환경 피드백을 받은 후 LM 자체의 궤적 품질 추정치이고, SC(s)는 형제 노드들 간에 해당 행동이 샘플링된 빈도에 기반한 자기 일관성 점수입니다. 이것은 훈련된 보상 모델이 아닙니다 — 가치 함수는 전적으로 프롬프트 기반입니다.
핵심 아이디어
- HumanEval에서 GPT-4 + LATS는 92.7% pass@1에 도달하는 반면, GPT-4 + Reflexion은 91.0%, GPT-3.5 + ReAct 단독은 56.9%입니다. GPT-3.5 + LATS는 83.8%로 뛰어오릅니다.
- HotPotQA에서 LATS(CoT + ReAct)는 0.71 Exact Match에 도달하는 반면 ReAct 기준선은 0.32입니다 — 다중 홉 정확도를 두 배 이상 향상시킵니다.
- WebShop(웹 내비게이션 + 구매)에서 LATS는 75.9점(38.0% 성공률)을 기록했으며, Reflexion은 64.2점(35.0%)입니다 — 많은 페이지에 걸쳐 상태를 관리해야 하는 작업에서 의미 있는 격차입니다.
- Game of 24(순수 추론 퍼즐)에서 LATS는 동일한 GPT-4 백본을 사용하면서도 ToT의 0.20에 비해 0.44의 성공률에 도달합니다.
- 놀랍게도 LATS는 ToT보다 솔루션을 찾기 위해 더 적은 노드를 확장합니다(HotPotQA k=50에서 평균 66.65 vs 84.05 노드) 그리고 더 적은 토큰을 사용합니다(173,290 vs 210,215), 이론상 더 비싸 보임에도 불구하고.
타당한 부분 — 그리고 그렇지 않은 부분
벤치마크 수치는 실제이며 프레임워크는 개념적으로 명확합니다. UCT 공식은 ToT의 임시 BFS/DFS가 부족한 원칙적인 탐험-활용 트레이드오프를 제공합니다. 순수 LM 내성적 사고 대신 외부 환경 피드백을 가치 함수에 통합하는 것은 올바른 접근이며, 결과가 이를 보여줍니다.
그러나 이 논문은 저자들이 완전한 스트레스 테스트 없이 인정한 중요한 가정을 지니고 있습니다: LATS는 환경을 이전 상태로 되돌리는 능력을 요구합니다. 체크포인팅 없이는 트리를 분기할 수 없습니다 — 행동이 취해지면 고정됩니다. 저자들은 LM 작업의 경우 "과거 텍스트 입력을 복사-붙여넣기"로 관리 가능한 경우가 많다고 언급하지만, 실제 행동 환경(데이터베이스, 파일시스템, 부작용이 있는 API)에서는 많은 프로덕션 시스템이 충족할 수 없는 어려운 요구사항입니다. WebShop 결과는 기준선보다 낫지만, 복잡한 환경에서 자기 성찰이 구체적이기보다 일반적으로 변하는 경향을 보여줍니다 — 에이전트가 표면적으로 다르지만 구조적으로 동일한 실수를 반복하며 멈출 수 있습니다. 논문은 이를 언급하지만 해결책을 제시하지 않습니다.
또한 MCTS 구조의 기여와 가치 함수 설계의 기여를 분리하는 절제 실험(ablation)도 없습니다. 동일한 하이브리드 가치 함수를 가진 더 간단한 분기 접근 방식이 격차의 상당 부분을 줄일 수 있다는 것이 그럴듯하며, 저자들은 이를 직접 테스트하지 않습니다.
금융 AI에 중요한 이유
Beancount 원장은 한 가지 주요 이유로 LATS 스타일 트리 탐색에 거의 이상적인 환경입니다: 모든 원장은 git 저장소로 백업됩니다. 상태 되돌림 요구사항 — LATS를 많은 실제 설정에서 비실용적으로 만드는 어려운 제약 — 은 git checkout 또는 git stash로 사소하게 충족됩니다. 쓰기-백 에이전트는 여러 분기에 걸쳐 후보 분개 항목을 제안하고, 대차대조표 제약(가치 함수)에 대해 점수를 매기고, 가장 높은 점수의 경로만 커밋할 수 있습니다. 실패한 분기는 언어적 성찰을 받습니다: "게시된 항목이 자산 = 부채 + 자본을 위반했습니다. 계정 유형이 잘못 분류되었기 때문입니다."
하이브리드 가치 함수 설계도 직접 적용 가능합니다. 원장 에이전트의 경우 LM(s)는 제안된 항목의 의미적 적합성을 점수화하고(올바른 카테고리처럼 보이는가?), SC(s)는 에이전트가 유사한 과거 거래를 얼마나 일관되게 분류하는지 추적합니다 — 원장 자체의 역사에 뿌리를 둔 자연스러운 자기 일관성 검사입니다.
상태 되돌림은 금융 비유에 대해 제가 반대를 제기할 유일한 부분입니다. 실제 원장은 종종 하류 효과가 있습니다: 게시된 항목이 인보이스를 트리거하고, 그 인보이스가 지불 워크플로우를 트리거합니다. 이러한 경우 LATS의 가정은 깨집니다. 특히 Beancount의 경우, 원장이 git 제어하의 일반 텍스트 파일이고 변경이 하류 트리거 발생 전에 로컬에서 이루어지므로 가정이 유지됩니다 — 그러나 이것은 명시적으로 유지해야 할 설계 제약입니다.
다음에 읽을 것
- 환경 모델 없는 MCTS 기반 계획: "Reasoning with Language Model is Planning with World Model" (Hao et al., 2023, arXiv:2305.14992) — LATS가 기반하고 개선한 RAP.
- LM 가치 함수가 얼마나 잘 일반화되는가: "Let's Verify Step by Step" (Lightman et al., 2023, arXiv:2305.20050) — 프롬프트 기반 가치 함수의 대안으로서 프로세스 보상 모델.
- 비가역성 하에서의 안전한 다단계 계획: "Decision-Making with Language Models via Successive Prompting" (Creswell et al., 2023) — 상태 되돌림 요구사항을 피하는 더 간단한 계획 접근 방식.
