"mcts" 태그로 연결된 1개 게시물개의 게시물이 있습니다.

[Stanford CS329A #5] 다단계 계획과 트리 탐색: ADaPT, LATS, SPRINT, 그리고 언어 에이전트 MCTS

2026년 11월 5일 · 약 14분

AI & Robotics Engineer

Stanford CS329A Multi-Step Planning and Tree Search

스탠포드 대학교의 2025 가을학기 최신 대학원 강좌, CS329A: Self-Improving AI Agents (스스로 발전하는 AI 에이전트) 다섯 번째 기술 해설에 오신 것을 환영합니다.

지난 제4강에서 우리는 언어 모델이 터미널에서 코드를 실행하고 컴파일러 에러를 독해하며 스스로 버그를 고치는 도구 사용과 실행 피드백 루프(ReAct, RLEF)를 배웠습니다. 그러나 주니어 개발자가 사소한 신택스 에러를 수정하는 것과, 수석 아키텍트가 10만 라인 규모의 분산 시스템을 설계하고 장기 과제를 완수하는 것은 차원이 완전히 다른 문제입니다.

기존의 ReAct나 CoT 방식은 본질적으로 **'눈앞의 한 걸음만 보고 내딛는 탐욕적(Greedy) 단일 경로 방식'**입니다. 체스를 둘 때 오직 다음 한 수만 보고 말을 움직이는 초보자가 3수 뒤에 외통수(Checkmate)에 걸려 패배하듯, 탐욕적 언어 모델 역시 복잡한 다단계 과제에서 초반에 잘못된 결정을 내리면 되돌아오지 못하고 막다른 골목에 갇히게 됩니다.

오늘 다룰 제5강은 강좌의 전반부인 **Part 1 (Foundation · 기초 기반)**을 집대성하는 웅장한 피날레입니다: 바로 **다단계 계획(Multi-Step Planning)과 트리 탐색(Tree Search)**입니다.

바둑에서 세계 챔피언을 꺾었던 알파고(AlphaGo)의 핵심 수학적 엔진, **몬테카를로 트리 탐색(MCTS)**을 자기회귀 언어 모델에 이식하여, 모델이 체스 그랜드마스터처럼 수십 수를 내다보며 자율적으로 계획을 세우고, 실패하면 과거 분기점으로 백트래킹(Backtracking)하여 다른 가능성을 탐색하는 놀라운 지능 시스템들을 해체하고 재설계합니다:

추론, 행동, 계획의 완벽한 삼위일체: 언어 에이전트 트리 탐색 LATS (Zhou et al., 2023)
실패할 때만 똑똑하게 쪼개는 적응형 분해: ADaPT (Allen AI, 2023)
추론 지연 시간을 53.5% 단축하는 병렬 DAG 패킹: SPRINT (Stanford Future Data, 2025)
톰슨 샘플링 기반의 적응형 브랜칭: 넓힐 것인가 깊게 팔 것인가를 해결하는 AB-MCTS (Sakana AI, 2025)
계획 능력을 모델 가중치에 새겨넣는: SWiRL (Step-Wise RL, 2025)

flowchart TD
    subgraph MCTS_Loop ["LATS 언어 에이전트 MCTS 엔진 라이프사이클"]
        direction TB
        Root["루트 노드: 사용자 문제 / PRD 목표"]
        --> Select["1. 선택 (Selection): UCT 지표 최대화 노드 탐색"]
        --> Expand["2. 확장 (Expansion): n개의 다양한 행동 후보 샘플링"]
        --> Eval["3. 평가 (Evaluation): LM 가치 점수 + 자가 일관성 앙상블"]
        --> Backprop["4. 역전파 (Backpropagation): 상위 경로로 스칼라 가치 전파"]
        --> Reflect["5. 언어적 반성 (Semantic Reflection): 실패 원인 자연어 메모리 저장"]
    end

    subgraph PlanningParadigms ["에이전트 계획 알고리즘의 진화 스펙트럼"]
        direction TB
        P1["LATS (트리 탐색 MCTS)<br/>• 프롬프트 히스토리 복원 기반의 무비용 백트래킹<br/>• HumanEval 92.7% 달성; HotpotQA 정답률 32%에서 71%로 폭증"]
        --> P2["ADaPT (적응형 재귀 분해)<br/>• 경직된 사전 계획 탈피, 단일 실행기로 먼저 시도<br/>• 실행기 실패 보고 시에만 AND/OR 하위 태스크로 유연하게 분기"]
        --> P3["SPRINT (의존성 DAG 패킹)<br/>• 장문 추론 체인에서 상호 독립적인 스텝 자동 식별<br/>• GPU 클러스터 분산 병렬 실행으로 추론 지연 시간 53.5% 압축"]
        --> P4["SWiRL (단계별 강화학습)<br/>• MCTS의 탐색 지혜를 모델 신경망 가중치에 직접 주입<br/>• 단일 패스 추론으로 그랜드마스터급 전략적 선견지명 발휘"]
    end

    MCTS_Loop ==> PlanningParadigms