🤖 AI

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

이 논문은 비용이 많이 드는 LLM 추론을 계층적 월드 모델과 UCB1 기반의 트리 탐색으로 대체하여, 다양한 복잡한 작업에 대해 100%의 성공률과 결정론적이며 호출이 없는(zero-call) 계획 수립을 달 achieve함으로써 LATS 및 ReAct와 같은 기존 방식들을 크게 능가하는 계획 프레임워크인 GATS를 소개한다.

원저자: Maureese Williams, Dymitr Nowicki

게시일 2026-07-13

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Maureese Williams, Dymitr Nowicki

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

거대하고 까다로운 미로를 풀려고 노력하고 있다고 상상해 보세요. 당신에게는 당신에게 말을 걸며 어느 방향으로 갈지 제안해 줄 수 있는 아주 똑똑한 친구(대규모 언어 모델, 즉 LLM)가 있습니다. 하지만 여기 함정이 있습니다. 당신이 조언을 구할 때마다, 그 친구는 생각하기 위해 긴 낮잠을 자야 하며, 때로는 같은 질문을 할 때마다 매번 다른 답을 추측하기도 합니다. 만약 미로에 막다른 길이 있거나 긴 일련의 회전이 필요하다면, 매 단계마다 친구에게 도움을 요청하는 것은 비용이 많이 들고 혼란스러울 것입니다.

이것이 바로 연구원 모리스 윌리엄스(Maureese Williams)와 디미트르 노비키(Dymitr Nowicki)가 자신들의 새로운 시스템인 GATS(Graph-Augmented Tree Search)를 통해 해결한 문제입니다. 그들은 이 미로를 매우 효율적으로 탐색하는 방법을 찾아냈으며, 그 과정에서 똑똑한 친구를 거의 깨울 필요조차 없었습니다.

기존 방식: "매 단계마다 묻기" 접근법

ReAct나 LATS와 같은 이전 방법들은 마치 길의 갈림길이 나올 때마다 가이드에게 멈춰 서서 "어느 길로 가야 하나요?"라고 묻는 등산객과 같았습니다.

ReAct는 단 한 번 묻고 그냥 갑니다. 빠르긴 하지만, 종종 막다른 길로 들어섭니다. 테스트 결과, 이 방식은 까다로운 미로 시나리오에서 **64%**의 성공률만을 보였습니다.
LATS는 더 똑똑합니다. 가이드에게 묻고, 그다음 단계에 대해 다시 묻고, 또 묻는 식으로 가능성의 나무(tree)를 만들어 나갑니다. 하지만 나무의 모든 가지마다 가이드(LLM)에게 물어봐야 하기 때문에, 가이드는 지치고 비용도 많이 듭니다. 테스트에서 LATS는 **92%**의 성공률을 기록했지만, 작업당 가이드에게 약 37번이나 물어봐야 했습니다. 게다가 가이드는 가끔 무작위로 추측하기 때문에, 같은 미로를 두 번 시도하면 서로 다른 경로를 얻게 될 수도 있습니다.

새로운 방식: GATS ( "지도 제작자" 전략)

GATS는 게임의 판도를 바꿉니다. 매번 방향을 물어보는 대신, GATS는 **계층적 세계 모델(Layered World Model)**을 사용하여 자신만의 내부 지도를 구축합니다. 이 지도는 세 가지 층의 지식을 가지고 있다고 생각하면 됩니다:

1계층 (정확한 규칙집): 시스템이 이미 완벽하게 알고 있는 동작(예: "이 버튼을 누르면 문이 열린다")에 대해서는 단순하고 즉각적인 확인 과정을 거칩니다. 별도의 사고가 필요 없습니다. 이는 2+2가 항상 4라는 것을 아는 것과 같습니다.
2계층 (경험 로그): 동작이 일어난 적은 있지만 완벽한 규칙이 없는 경우, 시스템은 과거 여행의 일기를 확인합니다. "지난번에 이렇게 했을 때, 10번 중 9번은 성공했다." 이것은 추측이 아니라 데이터로부터 학습된 것입니다.
3계층 (초천재 친구): 시스템이 완전히 새롭고 알려지지 않은 상황에 직면했을 때만 LLM 가이드를 깨웁니다. 하지만 여기서 마법이 일어납니다. 가이드가 답을 하면, GATS는 그 답을 지도에 기록합니다. 다음에 동일한 상황이 발생하면, GATS는 그저 지도를 확인합니다. 특정 상황에 대해 가이드에게 다시는 묻지 않습니다.

결과: 속도, 확실성, 그리고 성공

연구진은 분기점이 있고 막다른 길이 있는 까다로운 설계인 **100개의 합성 계획 작업(synthetic planning tasks)**을 통해 이를 테스트했습니다.

GATS는 **100%**의 성공률을 달달했습니다.
LATS는 **92%**를 기록했습니다.
ReAct는 **64%**를 기록했습니다.

하지만 진짜 놀라운 점은, GATS가 이러한 작업들을 계획하는 동안 LLM 호출을 단 한 번도 하지 않았다는 것입니다. GATS는 자신의 지도와 규칙을 사용하여 모든 생각을 마쳤습니다. LLM의 무작위 추측에 의존하지 않았기 때문에, GATS는 실행할 때마다 정확히 똑같은 완벽한 계획을 만들어냈습니다. 즉, 변동성(variance)이 제로였습니다.

그들은 또한 코딩 워크플로우, 항공권 예약, 복잡한 미로 탐색 등 12개의 어려운 카테고리에 걸친 120개의 작업으로 대규모 "스트레스 테스트"를 실시했습니다.

GATS는 여전히 **100%**의 성공률을 유지했습니다.
LATS는 **88.9%**로 떨어졌습니다.
ReAct는 **23.9%**로 폭락했습니다.

왜 성공하는가 (비결)

논문은 GATS가 무작위 추측 대신 체계적인 탐색(UCB1이라 불리는)을 사용하기 때문에 승리한다고 설명합니다. 이는 단순히 직관을 따르는 것이 아니라, 모든 단서를 체계적으로 확인하는 탐정의 모습과 같습니다.

체계적 vs 무작위: LATS는 어떤 경로가 좋을지 추측하기 위해 LLM에 의존합니다. 만약 LLM의 "직감"이 틀리면 전체 계획이 실패합니다. 반면 GATS는 모든 옵션을 체계적으로 확인하므로, 가이드의 컨디션이 좋지 않다고 해서 올바른 경로를 놓치는 일이 없습니다.
결정론적 vs 확률적: GATS는 대부분의 단계에서 자신만의 지도를 사용하기 때문에 결과가 항상 동일합니다. LLM에 의존하는 LATS는 같은 작업을 두 번 실행할 때 다른 답을 줄 수 있습니다.

의미하는 바 (그리고 한계점)

저자들은 자신들의 성공에 대한 한계를 매우 명확히 밝히고 있습니다. 이 결과들은 규칙(액션 사양)이 미리 정해져 있는 시뮬레이션과 합성 작업을 기반으로 합니다. 이러한 통제된 환경에서 GATS는 챔피언입니다.

그러나 논문은 GATS가 현재 모든 것에 적용되는 마법의 탄환이라는 생각은 명시적으로 배제하고 있습니다. 만약 규칙도 없고 학습할 과거 로그도 없는 완전히 야생적이고 개방적인 세상에 GATS를 던져놓는다면, GATS는 LLM에 더 많이 의존해야 할 것이며, 이는 더 느리고 비효und 효율적이게 만들 것입니다. 저자들은 GATS가 현실 세계에서 빛을 발하기 위해서는, 먼저 인간이 실제로 도구를 사용하는 로그로부터 학습하는 등의 더 나은 지도(세계 모델)를 구축해야 한다고 제안합니다.

요약하자면, 이 논문은 규칙을 정의할 수 있는 계획 작업의 경우, 매 단계마다 초천재 AI에게 도움을 구할 필요가 없음을 보여줍니다. 우리는 100%의 성공률, 제로의 비용, 그리고 제로의 혼란으로 복잡한 문제를 탐색할 수 있게 해주는, 스마트하고 스스로 업데이트되는 지도를 구축할 수 있습니다.

기술 요약: GATS (계층형 월드 모델을 이용한 그래프 증강 트리 탐색)

문제 정의

대규모 언어 모델(LLM) 에이전트는 다단계 계획 수립 및 도구 사용 측면에서 잠재력을 보여주었으나, 현재의 ReAct 및 LATS(Language Agent Tree Search)와 같은 방식은 두 가지 결정적인 한계에 직면해 있습니다:

계산 비용: 기존 방식은 매 계획 단계나 탐색 노드마다 값비싼 LLM 추론에 의존하므로, 높은 지연 시간과 자원 소모를 초래합니다.
확률성: LLM 샘플링은 변동성을 도입하여, 실행 시마다 계획이 재현되지 않거나 일관되지 않은 성능을 보이는 결과를 낳습니다.

핵심 과제는 LLM의 추론 능력을 유지하면서도 상태 예측을 위한 추론 시점의 LLM 호출을 제거함으로써, 결정론적이고 효율적이며 확장 가능한 에이전트 계획 체계를 개발하는 것입니다.

방법론: GATS 프레임워크

저자들은 **GATS (Graph-Augmented Tree Search)**를 제안합니다. 이는 월드 모델(World Model)과 LLM을 분리하는 계획 아키텍처입니다. GATS는 체계적인 UCB1 기반 트리 탐색과 계층형 월드 모델(Layered World Model), 그리고 지속적인 **상태-전이 그래프(State-Transition Graph)**를 결합합니다.

1. 계층형 월드 모델 ( $W$ )

월드 모델은 현재 상태( $s$ )와 행동( $a$ )이 주어졌을 때 다음 상태( $s'$ )와 신뢰도( $p$ )를 예측합니다. 이 모델은 일반성과 계산 비용이 증가하는 순서대로 세 가지 레이어를 차례로 쿼리합니다:

L1 (기호적/Symbolic): 알려진 STRIPS 스타일의 명세가 있는 행동에 대해 정확한 전제 조건-효과 매칭을 수행합니다. 이 레이어는 최소한의 계산 비용(기호적 조회)으로 결정론적 예측( $p=1.0$ )을 제공합니다.
L2 (학습된 통계/Learned Statistics): 실행 로그로부터 도출된 통계적 예측입니다. 실행 중에 관찰되었으나 공식적인 명세가 없는 행동의 경우, 가장 빈번한 효과를 반환하며 신뢰도는 $p = \min(\text{count}(a)/10, 1.0)$ 으로 설정됩니다.
L3 (생성적/LLM/Generative): 진정으로 새롭거나 모호한 행동을 위한 LLM 기반 예측입니다. 결정적으로, L3의 예측은 **캐싱(cached)**되어 동일한 전이에 대한 반복적인 추론 호출을 방지합니다.

시스템은 L1과 L2를 우선시하여 커버리지를 극대화하고, L3는 꼭 필요할 때만 호출합니다. 이러한 방식은 LLM 비용을 매 단계의 추론 요구 사항에서 일회성 부트스트래핑 비용으로 전환하여 비용을 **분할 상환(amortize)**합니다.

2. 지속적인 상태-전이 그래프

독립적으로 노드를 확장하는 전통적인 트리 탐색과 달리, GATS는 노드가 정형화된 상태 키 $k(s)$ 를 나타내는 명시적인 그래프 $G = (V, E)$ 를 유지합니다.

상태 병합 (State Merging): 서로 다른 행동 시퀀스가 동일한 상태에 도달하면 하나의 노드로 병합됩니다. 이를 통해 경로 전반에 걸쳐 전이 예측, 방문 횟수, 가치 추정치를 재사용할 수 있습니다.
지속성 (Persistence): 그래프는 계획 단계 전반에 걸쳐 지속됩니다. 행동이 실행된 후, 계획은 탐색을 처음부터 다시 시작하는 대신 해당 그래프 노드로부터 재개되어, 가치 추정과 탐색 통계가 전체 에피소드에 걸쳐 분할 상환되도록 합니다.
막다른 길 탐지 (Dead-End Detection): 목표로 가는 경로가 없는 노드는 막다른 길(dead end)로 표시되어, 플래너가 해당 영역으로 이어지는 행동에 낮은 값을 할당할 수 있게 합니다.

3. UCB1 기반 탐색

GATS는 그래프 엣트에 대해 UCB1(Upper Confidence Bound) 선택 전략을 채택합니다.

행동 선택: 각 상태에서 알고리즘은 $Q(s, a) + c\sqrt{\frac{2 \ln N(s)}{N(s, a)}}$ 를 최대화하는 행동 $a$ 를 선택합니다. 이는 높은 가치의 경로에 전념하기 전에 모든 적용 가능한 행동을 체계적으로 탐색하도록 보장합니다.
가치 추정: 상태의 가치는 BFS 기반 휴리스틱을 사용하여 예측된 목표까지의 최단 거리( $d_G$ )로부터 도출됩니다: $StateValue(s) = \frac{\alpha}{d_G(s, G) + 1}$ .
신뢰도 통합: 백업 가치는 월드 모델의 신뢰도를 포함합니다: $v = p \cdot StateValue(s') - \lambda(1-p)$ . 이는 불확실한 예측에 대해 페널티를 부여합니다.

주요 기여

계층형 월드 모델 아키텍처: LLM 의존성을 최소화하면서 효율적인 상태 예측을 가능하게 하는 기호적, 학습적, 생성적 구성 요소의 새로운 통합.
그래프 메모리를 갖춘 체계적인 UCB1 탐색: 탐색 증거를 재사용하고 결정론적 결과를 보장하기 위해 지속적인 그래프를 활용함으로써, 무작위 LLM 유도 탐색보다 뛰어난 성능을 보이는 계획 알고리즘.
포괄적인 평가: 코딩, 웹 네비게이션, 장기 호라이즌(long-horizon) 시나리오를 포함하는 100개의 합성 계획 작업 및 12개 카테고리의 스트레스 테스트(120개 작업)에 대한 광범위한 테스트.
계획 중 LLM 호출 제로: GATS가 계획 단계 동안 0회의 LLM 호출로 100% 성공률을 달か성할 수 있음을 입증하였으며, 이는 작업당 수십 번의 호출이 필요한 베이스라인들과 극명하게 대조됩니다.

실험 결과

합성 계획 작업 (100개 작업)

성공률: GATS는 예산 $b=10$ 에서 100% 성공을 달성하여, LATS(92%)와 ReAct(64%)를 능가했습니다.
효율성: GATS는 계획 중 작업당 0회의 LLM 호출이 필요했던 반면, LATS는 약 37회의 호출이 필요했습니다.
결정론: GATS는 랜덤 시드에 대해 0%의 변동성을 보이는 계획을 생성했으나, LATS와 ReAct는 LLM의 확률적 특성으로 인해 1~5%의 변동성을 보였습니다.
최적성: GATS는 오라클(Oracle)과 일치하는 1.00의 최적성 비율을 달성했습니다.

스트레스 테스트 (12개 카테고리, 120개 작업)

스트레스 테스트에는 코딩 워크플로우, 웹 네비게이션, 깊은 호라이즌 작업, 되돌릴 수 없는 의사결정(막다른 길)과 같은 도전적인 시나리오가 포함되었습니다.

전반적인 성능: GATS는 모든 카테고리에서 100% 성공률을 유지했습니다.
비교 성능: LATS는 전체적으로 **88.9%**로 떨어졌으며, 특히 코딩(63.3%), 웹 네비게이션(63.3%), 깊은 호라이즌(63.3%) 작업에서 어려움을 겪었습니다. ReAct는 **23.9%**로 처참하게 실패했습니다.
구체적인 이점: GATS는 LATS와 비교했을 때 코딩, 웹 네비게이션, 깊은 호라이즌 작업에서 가장 큰 개선(+36.7%)을 보였습니다.

어블레이션 연구 (Ablation Studies)

탐색 예산: 성능은 예산 $b=10$ 에서 포화되었으며, 그 이상으로 늘리는 것은 한계 효용이 감소했습니다.
월드 모델 레이어: 합성 작업에서 L1 또는 L3를 개별적으로 제거해도 성공률에 영향을 미치지 않았는데, 이는 L2가 충분한 커버리지를 제공함을 검증하며 시스템의 점진적 성능 저하(graceful degradation) 능력을 입증합니다. 오픈 도메인 투영 시, L3(LLM)는 약 10%의 새로운 행동을 처리할 것으로 예상됩니다.

의의 및 주장

본 논문은 학습된 월드 모델을 통한 체계적인 탐색이 LLM 유도 탐색보다 실질적으로 더 우수할 수 있음을 주장합니다. GATS의 주요 의의는 다음과 같습니다:

추론 시점의 LLM 비용 제거: 예측을 캐싱하고 기호적/학습적 레이어에 의존함으로써, GATS는 반복적인 LLM 호출이라는 계산적 병목 현상을 제거합니다.
재현성 보장: 계층형 월드 모델과 UCB1 탐색의 결정론적 특성은 LLM 샘플링 고유의 확률적 변동성을 제거합니다.
복잡한 계획 처리: GATS 프레임워크는 순수 LLM 기반 방식(ReAct) 및 LLM 중심 트리 탐색(LATS)이 실패하거나 성능이 저하되는 분기 경로, 막다른 길, 장기 호라이즌 의존성을 성공적으로 탐색합니다.

저자들은 GATS를 행동 의미론을 공식화할 수 있는 도메인(예: API, 구조화된 도구 사용)에 최적화된 솔루션으로 제시하며, 더 효율적이고 신뢰할 수 있는 자율 에이전트로 가는 경로를 제안합니다. 또한, 행동 효과를 알 수 없는 개방형 도메인에서는 L3 레이어에 대한 의존도가 높아져 LATS 대비 효율성 이점이 줄어들 수 있음을 인정합니다.