Language Agent Tree Search는 언어 모델에서 추론, 행동 및 계획을 통합한다
Source: Dev.to
선정 이유
평가점
| 평가 | 라벨 |
|---|---|
| 높음 | S |
| 중 | A |
| 낮음 | B |
| 낮음 | C |
| 낮음 | D |
일관성
B: LLM에 의한 상태 가치 평가로 탐색과 활용의 트레이드오프를 해결하는 점은 비즈니스 니즈가 높다.
신뢰성
S: Proceedings of Machine Learning Research 2024 채택. 저자는 전 DeepMind.
건전성
S: 이론 설계(MCTS 도입, LM 평가 활용, 반성 통합)는 정돈되어 있으며 명확한 알고리즘 구성을 가지고 있다.
범용성
A: langgraph에서도 구현 예시가 있어 범용성이 높지만, 하이퍼파라미터에 대한 민감도와 실행 비용이 과제이다.
발전성
A: 다양한 발전이 기대되지만, 트리 구조에 제한되는 점과 상태가 명확히 정의되지 않은 작업에 적용하기는 어렵다.
논문 정보
Paper: Language Agent Tree Search (LATS)
LLM의 사고를 트리 구조로 관리하고 선읽기를 가능하게 함으로써, 적은 시도와 오류로 올바른 결론에 도달한다.
제안 방법
몬테카를로 트리 탐색(MCTS)을 사용해 여러 행동 후보를 탐색하고, LLM이 가치 평가·반성을 수행함으로써 장기적이고 일관된 의사결정을 구현한다.
- 특징
- 추론, 행동, 계획, 반성, 기억이라는 모든 구성 요소를 통합(LATS가 최초).
- MCTS와 벨만 백업 개념을 LLM의 추론 시 탐색에 적용.
효과와 과제
-
효과
- LLM의 근사 환경 예측에 의존하기 때문에 편향이 겹치기 쉽고 초기값 민감성이 발생하기 쉽다.
- 그러나 LLM은 장기 구조와 의미적 일관성을 포착하는 능력이 있어, 엄밀한 환경 모델이 없어도 유용한 휴리스틱으로 작동한다.
-
그림 2의 해석
- 벨만 방정식에서 백업 선도를 belief 공간에서 근사 평가.
- 노드가 상태(이력), 엣지가 행동 선택을 나타낸다.
알고리즘 전체 모습
비교표
| 관점 | LATS | 몬테카를로법(MC) | TD 방법(TD(0)) | SARSA |
|---|---|---|---|---|
| 분류 | 추론 시 탐색 | 강화학습(가치 추정) | 강화학습(가치 추정) | 강화학습(제어) |
| 주요 목적 | 추론·행동 최적화 | 가치 함수 학습 | 가치 함수 학습 | 정책과 가치 동시 학습 |
| 상태·행동 공간 | 자연어(thought/action) | 이산/연속 | 이산/연속 | 이산/연속 |
| 탐색 구조 | 트리 구조(MCTS) | 없음 | 없음 | 없음 |
| 롤아웃 | LLM에 의한 롤아웃 | 실제 에피소드 | 실제 전이 | 실제 전이 |
| 평가 기준 | LM 평가+자기 일관성 | 실제 보상 | 실제 보상+추정 가치 | 실제 보상+추정 가치 |
| 부트스트랩 | 있음 | 없음 | 있음 | 있음 |
| 업데이트 대상 | 탐색 트리 통계량 | 가치 함수 파라미터 | 가치 함수 파라미터 | 행동 가치 함수 (Q) |
| 학습(가중치 업데이트) | 하지 않음 | 함 | 함 | 함 |
| 정책과의 관계 | 탐색으로 암묵적으로 결정 | 고정 or 임의 | 고정 or 임의 | On‑policy |
| 실패 활용 | Reflection(자연어) | 샘플 평균 | TD 오차 | TD 오차(행동 의존) |
탐색 절차
UCB 기반 노드 선택
전체 노드 중 다음에 확장할 노드를 UCB (Upper Confidence Bound) 기반 평가로 선택한다. 상태 가치 함수 $V(s_t)$와 탐색 횟수 $N(s_{t+1})$의 균형을 맞춰 가장 유망한 노드를 선택한다.
$$ a_t = \arg\max_{a_t}\Bigl[ V(S_t) + c \sqrt{\frac{\log N(S_t)}{N(S_{t+1})}} \Bigr] $$
$$ N(S_{t+1}) \leftarrow N(S_t) + 1 $$
이후, 기억에 따라 관측 $o_{t}$를 획득한다. 이는 Experience Replay와 달리 탐색 트리에 저장된 관측을 그대로 재사용해 동일한 탐색 경로를 따라가는 메커니즘이다.
노드 확장과 샘플링
선택된 노드 $s_t$에서 $n$개의 자식 노드를 파라미터 $\theta$를 가진 모델 $p_\theta$에서 샘플링해 생성한다.
$$ a_t^{(i)} \sim p_{\theta}(S_t), \qquad S_{t+1} = \text{Env}(S_t, a_t^{(i)}) $$
Evaluation(평가)
새로 확장된 노드의 상태 가치(스칼라량)를 LLM으로 평가한다.
$$ V(s) = \lambda \cdot \mathrm{LM}(s) + (1-\lambda)\cdot \mathrm{SC}(s) $$
- $\mathrm{LM}(s)$: LLM에 의한 가치 예측
- $\mathrm{SC}(s)$: Self‑Consistency(자기 일관성)
기존 ToT (Yao 2023)가 “사고의 타당성”만을 평가한 것과 달리, LATS는 외부 환경으로부터 관측을 얻은 후 평가한다. 이를 통해 코드 실행 오류나 웹 검색 결과에 기반한 보다 정확한 가치 판단이 가능해진다.
Backpropagation(트리 구조 통계량 업데이트)
시뮬레이션으로 얻은 미래 가치 추정 결과 $\hat{R}(h_t)$를 탐색 트리를 거슬러 각 노드에 반영한다.
$$ V(h_t) \leftarrow \frac{N(h_t),V(h_t) + \hat{R}(h_t)}{N(h_t) + 1} $$
$$ N(h_t) \leftarrow N(h_t) + 1 $$
Reflection(반성)
Reflection은 지금까지의 사고와 행동을 되돌아보고, 오류와 개선점을 LLM에게 지적시켜 탐색 방침을 수정하는 단계이다.
- 일반성: 명시적 환경 모델이나 보상 설계가 필요 없으며, LLM의 생성·평가 능력을 그대로 탐색과 가치 추정에 활용할 수 있다.
- 탐색 효율: 실제 환경과의 상호작용을 최소화하면서, 트리 탐색과 가치 백업으로 유망한 사고 경로에 계산 자원을 집중할 수 있다.
- 유연성: 상태와 트리 구조를 설계하면 다양한 환경에 적용 가능하다.
실험
Programming 데이터셋 결과
| 방법 | 데이터셋 1 | 데이터셋 2 |
|---|---|---|
| LATS | SOTA | SOTA |
| 기타 방법 | - | - |
표 4·5가 보여주듯이, LATS는 두 데이터셋 모두에서 최첨단(SOTA) 성능을 달성했다.