ToT·ReAct·Reflexion·MCTS를 트리 탐색 하나로 묶어 후보 해를 탐색하는 에이전트 프레임워크입니다.
개념
LATS(Language Agent Tree Search)는 ToT·ReAct·Reflexion·MCTS 네 기법을 통합한 프레임워크입니다.
- Tree of Thought (ToT): 다중 경로 탐색
- ReAct: 외부 도구 상호작용
- Reflexion: 실패로부터 학습
- Monte Carlo Tree Search (MCTS): 탐색 최적화
flowchart LR
S["Selection"] --> E["Expansion"]
E --> V["Evaluation"]
V --> M["Simulation"]
M --> B["Backpropagation"]
B --> R["Reflection"]
R --> S
6가지 핵심 작업
- Selection (선택): 탐색할 노드를 선택합니다.
- Expansion (확장): 새로운 가능성을 생성합니다.
- Evaluation (평가): 유망함을 평가합니다.
- Simulation (시뮬레이션): 행동을 실행하고 관찰합니다.
- Backpropagation (역전파): 결과를 역전파합니다.
- Reflection (성찰): 실패 시 반성합니다.
각 단계 상세
| 단계 | 설명 | 기반 기법 |
|---|---|---|
| Selection | 탐색할 노드 선택 | MCTS (UCB1) |
| Expansion | 새로운 가능성 생성 | ToT |
| Evaluation | 유망함 평가 | ToT |
| Simulation | 행동 실행 및 관찰 | ReAct |
| Backpropagation | 결과 역전파 | MCTS |
| Reflection | 실패 시 반성 | Reflexion |
통합된 기법들
| 기법 | LATS에서의 역할 |
|---|---|
| Tree Search | 다중 경로 탐색 구조 |
| ReAct | 외부 도구 상호작용 |
| Reflexion | 실패로부터 학습 |
| MCTS | 탐색 효율 최적화 |
성능
ICML 2024 최종 논문(arXiv:2310.04406)은 GPT-4 기반 HumanEval pass@1 92.7%를 보고합니다. GPT-3.5 기반 WebShop 평균 점수는 75.9입니다. HumanEval 결과에는 탐색과 테스트 피드백이 포함됩니다. 두 과제의 모델과 지표가 다르므로 점수를 직접 비교하거나 단일 호출 정확도로 해석해서는 안 됩니다.
아래 코딩 예제와 점수는 동작 설명용이며, 논문의 실행 기록이나 재현 결과가 아닙니다.
코딩 문제
문제: "파이썬으로 병합 정렬 구현하기"
Selection: UCB1 점수가 높은 노드를 선택합니다. 재귀적 구현 접근을 선택합니다.
Expansion: 세 가지 구현 방식을 생성합니다: 방식 1: 기본 재귀, 방식 2: 최적화된 재귀(in-place), 방식 3: 반복적 구현.
Evaluation: 각 방식의 유망함을 평가합니다: 방식 1: 0.7(간단하지만 메모리 비효율), 방식 2: 0.9(균형 잡힌 접근), 방식 3: 0.6(복잡함).
Simulation (ReAct): 방식 2를 구현합니다.
- Thought: 배열을 반으로 나누고 재귀 호출
- Action:
def merge_sort(arr): ...코드 작성- Observation: 코드 작성 완료
- Thought: 테스트 실행
- Action:
merge_sort([3,1,4,1,5,9])실행- Observation:
[1,1,3,4,5,9]성공Backpropagation: 테스트 통과로 점수를 역전파하고, 방식 2 경로의 UCB1 점수가 상승합니다.
완료: 최종 코드를 반환합니다.
실패 시 Reflection
Simulation 실패:
merge_sort([])실행 시IndexError: list index out of range발생Reflection: "빈 배열에 대한 경계 조건 처리가 없었습니다. 재귀의 기저 조건에 빈 배열 체크를 추가해야 합니다."
재시도:
if len(arr) <= 1: return arr경계 조건을 추가하여 문제를 해결합니다.
UCB1 알고리즘
LATS는 MCTS의 UCB1(Upper Confidence Bound)을 사용해 탐색과 활용의 균형을 맞춥니다.
- (\bar{x}) (평균 보상): 이 경로가 얼마나 좋았는가 (활용)
- (\sqrt{\frac{\ln(N)}{n}}) (탐색 항): 덜 방문한 경로에 보너스 (탐색)
- (C): 탐색-활용 균형 상수
기존 기법과의 비교
- CoT: 단일 경로 탐색, 도구 사용 X, 학습 X, 최적화 X
- ToT: 다중 경로 탐색, 도구 사용 X, 학습 X, 최적화 X
- ReAct: 단일 경로 탐색, 도구 사용 O, 학습 X, 최적화 X
- Reflexion: 단일 경로 탐색, 도구 사용 O, 학습 O, 최적화 X
- LATS: 다중 경로 탐색, 도구 사용 O, 학습 O, 최적화 O
구현 구조
아래 코드는 실행하지 않은 의사코드이며 원 논문의 전체 구현이 아닙니다. 실제 실행에는 탐색 예산과 종료 조건, 환경 상태 복구가 필요합니다.
class LATS:
def __init__(self, llm, tools):
self.llm = llm
self.tools = tools
self.memory = [] # Reflexion 메모리
def solve(self, problem):
root = Node(state=problem)
while not self.is_solved(root):
# 1. Selection
node = self.select(root)
# 2. Expansion
children = self.expand(node)
# 3. Evaluation
for child in children:
child.value = self.evaluate(child)
# 4. Simulation (ReAct)
best_child = max(children, key=lambda x: x.value)
result = self.simulate(best_child)
# 5. Backpropagation
self.backpropagate(best_child, result)
# 6. Reflection (실패 시)
if not result.success:
reflection = self.reflect(best_child, result)
self.memory.append(reflection)
return self.get_solution(root)solve 루프의 메서드는 앞의 6단계 표와 대응합니다. select, expand, evaluate, simulate, backpropagate가 차례로 각 단계를 맡습니다. 실패한 경우에만 reflect가 교훈을 memory에 쌓고, 다음 확장에서 참조합니다.
비용과 선택
후보 생성, 평가, 시뮬레이션에는 추가 호출이 필요합니다. LATS가 모든 작업에서 가장 정확하거나 가장 비싸다는 보편적인 순위는 없습니다. 같은 모델과 문제 집합에서 탐색 예산별 성공률, 호출 수와 지연을 비교해야 합니다.
관련 개념
- Tree of Thought (ToT): 다중 경로 탐색
- ReAct: 도구 사용
- Reflexion: 실패로부터 학습
- Monte Carlo Tree Search: 게임 AI 탐색 알고리즘
정리
LATS는 행동과 환경 피드백을 트리 탐색에 연결합니다. 선택부터 반성까지의 절차로 후보를 탐색하지만, 평가 오류나 제한된 예산 때문에 해를 놓칠 수 있습니다. 추가 호출의 효과는 해당 작업에서 측정해야 합니다.
단순 생성이나 ReAct를 기준선으로 두고 LATS의 추가 탐색을 평가할 수 있습니다. 벤치마크 수치는 논문 보고치이며, 적용 환경에 따라 결과가 달라질 수 있습니다.