Agentic AI 논문 읽기: LATS — 트리 탐색으로 추론과 행동을 통합하다

논문 정보

• 제목: Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models
• 저자: Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, Yu-Xiong Wang (University of Illinois Urbana-Champaign, Lapis Labs)
• 출판: ICML 2024 (PMLR 235)
• arXiv: 2310.04406

앞선 글에서 Reflexion을 읽었다. 에이전트가 실패하면 자연어로 반성하고, 그 반성을 다음 시도의 컨텍스트에 추가한다. 직선적인 되감기였다. 한 번 실패하면, 실패를 복기하고, 다시 처음부터 시도한다.

하지만 직선에는 한계가 있다. 미로에서 막다른 골목을 만났을 때, "아까 왼쪽으로 가지 말았어야 했다"라고 반성한 뒤 입구로 돌아가 처음부터 다시 걷는 것은 비효율적이다. 더 나은 전략은 갈림길로 돌아가서, 아직 가보지 않은 오른쪽 길을 시도하는 것이다. 이것이 트리 탐색의 발상이다.

2023년 10월, University of Illinois의 연구팀이 이 발상을 논문으로 발표했다. LATS — Language Agent Tree Search. 몬테카를로 트리 탐색(MCTS)을 LLM 에이전트에 적용하여, 추론과 행동과 계획을 하나의 프레임워크로 통합한다. Reflexion이 실패 후 전체를 되감았다면, LATS는 실패 지점의 갈림길로 돌아가 다른 가지를 뻗는다.

왜 직선이 아니라 트리인가

시리즈에서 읽어온 방법들을 나란히 놓으면, 각각이 무엇을 할 수 있고 무엇을 못하는지가 선명해진다.

CoT는 생각만 한다. ReAct는 생각하며 행동한다. Reflexion은 실패를 되돌아보며 다시 시도한다. 하지만 이 모든 방법은 한 가지 공통 제약을 가진다 — 단일 궤적만 탐색한다. 한 번에 하나의 길만 걷는다. 갈림길에서 하나를 선택하면, 나머지는 버린다.

LATS가 추가하는 것은 계획이다. 여러 가능한 경로를 동시에 열어두고, 가장 유망한 곳을 체계적으로 탐색한다. 실패하면 그 지점을 기억하고, 아직 탐색하지 않은 다른 경로로 이동한다. 버린 길을 다시 주울 수 있다.

몬테카를로 트리 탐색 — 바둑에서 온 알고리즘

LATS의 핵심 엔진은 몬테카를로 트리 탐색(MCTS)이다. AlphaGo가 바둑에서 인간 챔피언을 이길 때 사용한 바로 그 알고리즘이다.

MCTS의 핵심 아이디어는 탐색과 활용의 균형이다. 이미 좋은 결과를 보인 경로를 더 깊이 탐색(활용)하면서도, 아직 시도하지 않은 경로에도 기회를 준다(탐색). 이 균형을 수학적으로 제어하는 것이 UCT(Upper Confidence bounds for Trees) 공식이다.

바둑에서 MCTS가 작동하는 이유는, 이전 수로 돌아갈 수 있기 때문이다. 논문의 핵심 관찰은 LLM 과제에서도 같은 조건이 성립한다는 것이다. 텍스트 기반 과제에서 "이전 상태로 되돌리기"란, 이전 단계의 텍스트 입출력을 그대로 복사하여 다시 시작하는 것에 불과하다. 물리적 환경과 달리, 텍스트 세계에서는 시간을 되감는 비용이 사실상 제로다.

여섯 개의 연산 — LATS가 돌아가는 방식

LATS는 여섯 개의 연산을 반복한다. 각 연산이 하나씩 트리를 성장시키고 정제한다.

선택: 루트에서 시작하여, UCT 값이 가장 높은 자식 노드를 따라 리프까지 내려간다. 이미 많이 방문한 노드보다 덜 방문한 노드에 가산점을 주어, 탐색이 한쪽으로 편향되지 않도록 한다.

확장: 선택된 리프 노드에서 LLM으로 n개의 행동을 샘플링한다. 각 행동이 새로운 자식 노드가 된다. 한 번에 하나의 행동만 선택하는 ReAct와의 핵심 차이다 — LATS는 한 시점에서 여러 가능성을 동시에 열어둔다.

평가: 새로 생성된 자식 노드에 가치를 매긴다. LATS의 가치 함수는 두 요소의 결합이다. 하나는 LLM 자체를 가치 함수로 재활용하여 궤적의 정확성을 평가하는 것이고, 다른 하나는 자기 일관성(self-consistency) 점수 — 같은 상태에서 여러 번 샘플링했을 때 일관된 행동이 나올수록 높은 점수를 부여하는 것이다. ToT와의 핵심 차이는, LATS가 환경으로부터 피드백을 받은 뒤에 가치를 평가한다는 점이다. 행동의 결과를 보고 나서 판단하는 것이 행동 전에 판단하는 것보다 정확하다.

시뮬레이션: 선택된 노드에서 터미널 상태까지 진행한다. 최고 가치 노드를 우선 탐색하여 깊이 방향으로 확장한다.

역전파: 터미널 상태에 도달하면, 그 결과(보상)를 루트까지 거슬러 올라가며 경로상 모든 노드의 가치를 업데이트한다. 성공한 경로의 노드들은 가치가 올라가고, 실패한 경로의 노드들은 내려간다.

반성: 실패한 터미널 노드에서 Reflexion과 같은 방식으로 자기 반성을 수행한다. 오류를 요약하고, 더 나은 대안을 제시하는 텍스트를 생성하여 메모리에 저장한다. 이 반성이 이후 반복에서 추가 컨텍스트로 활용된다.

Reflexion과의 관계 — 경쟁이 아니라 확장

LATS는 Reflexion을 부정하지 않는다. 오히려 품는다.

Reflexion의 핵심 요소 — 자기 반성과 에피소드 메모리 — 는 LATS의 여섯 번째 연산으로 그대로 통합된다. 차이는 반성이 작동하는 맥락이다. Reflexion에서 반성은 전체 시도가 실패한 후 일어난다. LATS에서 반성은 트리의 한 가지가 실패할 때마다 일어나고, 그 반성이 다른 가지의 탐색을 안내한다.

제거 실험이 이 관계를 수치로 보여준다. HotPotQA에서 자기 반성을 제거하면 성능이 0.63에서 0.58로 떨어진다. 하지만 LM 가치 함수를 제거하면 0.63에서 0.37로 급락한다. LATS에서 가장 중요한 구성요소는 반성이 아니라 가치 함수, 즉 체계적 탐색 자체다. 반성은 탐색을 보조하는 역할이다.

이것이 함의하는 바는 명확하다. Reflexion의 "되감기 후 재시도"보다, LATS의 "갈림길로 돌아가서 다른 길 탐색"이 더 효과적인 구조적 이유가 있다.

실험 결과 — 세 전장에서의 검증

논문은 네 가지 도메인에서 실험했다. 2023년 말~2024년 초 기준의 결과다.

HotPotQA (GPT-3.5 기준): LATS(CoT+ReAct)가 EM 0.71을 달성하여, ReAct(0.32)의 두 배 이상, Reflexion(0.51)보다 20%p 높은 성능을 보였다. 흥미로운 관찰은, 단순히 ToT에 ReAct를 추가하거나 RAP에 ReAct를 추가하면 오히려 추론만 했을 때보다 성능이 떨어진다는 것이다. 추론과 행동의 결합은 단순한 합산이 아니라, MCTS라는 체계적 탐색 알고리즘을 통해야 효과적으로 통합된다.

프로그래밍 (HumanEval): GPT-3.5에서 LATS가 83.8%로 Reflexion(68.1%)을 15.7%p 앞섰다. GPT-4에서는 92.7%로, 바로 앞 글에서 읽은 Reflexion의 91.0%를 다시 넘어 당시 새로운 SOTA를 수립했다. 같은 모델, 같은 벤치마크에서 탐색 전략의 차이만으로 성능이 달라진다.

WebShop (GPT-3.5): LATS가 75.9점으로, Reflexion(64.2)과 ReAct(53.8)을 크게 앞섰다. 더 놀라운 것은 지도학습+강화학습(IL+RL) 파인튜닝(62.4)을 추론만으로 넘어섰다는 점이다. 가중치를 건드리지 않고, 탐색 전략만으로 파인튜닝에 필적하는 성능을 달성한 것이다.

비용과 한계 — 공짜 점심은 없다

LATS의 강력한 성능에는 대가가 있다. 트리 탐색은 본질적으로 다중 경로를 탐색하므로, LLM 호출 횟수가 ReAct나 Reflexion보다 많다. 논문은 이 비용을 솔직하게 인정하면서, 점근적으로 같은 샘플 복잡도를 가지며 평균적으로 더 적은 노드를 확장한다고 주장한다.

더 근본적인 한계는 되돌리기 가정이다. MCTS는 이전 상태로 되돌아갈 수 있어야 한다. 프로그래밍, 웹 탐색, 텍스트 게임에서는 이전 입력을 복사하면 되므로 자연스럽게 성립한다. 하지만 물리적 로봇 조작이나 비가역적 트랜잭션에서는 이 가정이 깨진다. 이메일을 보내는 행동은 되돌릴 수 없다.

탐색 폭 n이 성능과 비용의 자연스러운 조절 장치가 된다. n=1이면 ReAct와 같은 단일 궤적이고, n이 커질수록 더 넓은 탐색이 이루어지지만 비용도 비례하여 증가한다. 논문은 이 트레이드오프가 환경의 복잡도에 따라 조정되어야 한다고 제안한다.

2026년의 시선 — 트리 탐색의 현재

논문이 발표된 2023년 가을로부터 2년 반이 지났다.

실현된 것: MCTS와 LLM의 결합이라는 아이디어는 에이전트 연구의 주요 줄기가 되었다. OpenAI의 o1 시리즈가 "추론 시간 컴퓨팅(inference-time compute)"이라는 개념으로 이를 대규모로 실현했다. 더 많이 생각하면(더 많은 토큰을 생성하면) 더 정확한 답을 낼 수 있다는 발상은 LATS가 보여준 "더 넓게 탐색하면 더 좋은 경로를 찾을 수 있다"와 같은 근본 원리다.

확장된 것: LATS가 제기한 비용 문제는 여전히 유효하지만, 모델 추론 비용의 급격한 하락으로 실용성의 경계가 넓어졌다. 2023년에 비용 때문에 n=2~3이 한계였다면, 현재는 더 넓은 탐색이 경제적으로 가능해졌다.

여전히 열린 것: 되돌리기 불가능한 환경에서의 계획은 여전히 미해결 과제다. 실세계 에이전트가 물리적 행동을 취할 때, 잘못된 행동을 되감을 수 없다. 시뮬레이션 환경에서 먼저 탐색한 후 실세계에 최적 경로만 실행하는 접근이 탐구되고 있지만, 시뮬레이션과 현실의 간극은 별도의 문제를 만든다.

CoALA 좌표계 위의 LATS

Reflexion이 CoALA의 판단 축에 시간 차원을 추가했다면, LATS는 판단 축에 공간 차원을 추가한다. 하나의 시점에서 여러 가능한 미래를 동시에 평가하고, 가장 유망한 방향을 선택한다. 판단이 되감기에서 갈림길 탐색으로 진화한 것이다.

마무리 — 탐색의 범용성

LATS가 보여준 것은 체계적 탐색이 에이전트의 능력을 끌어올리는 범용적 전략이라는 점이다. 추론, 행동, 반성 — 이 모든 것이 탐색 알고리즘이라는 하나의 우산 아래서 시너지를 만든다. 하지만 그 범용성에는 조건이 붙는다. 되돌리기가 가능한 환경, 충분한 추론 예산, 그리고 적절한 가치 함수.

다음 글에서는 에이전트 학습의 세 번째 방식을 읽는다. Reflexion이 반성으로, LATS가 탐색으로 학습했다면, ETO(Trial and Error)는 실패 궤적과 성공 궤적의 대조 학습으로 에이전트를 직접 훈련시킨다.

이 글은 "Agentic AI 논문 읽기" 시리즈의 아홉 번째 글입니다. 시리즈 전체 목록은 시리즈 페이지에서 확인할 수 있습니다.