LATS: 통합 에이전트 프레임워크

Language Agent Tree Search

개념

LATS(Language Agent Tree Search)는 지금까지 등장한 거의 모든 에이전트 기법을 통합한 프레임워크입니다:

Tree of Thought (ToT): 다중 경로 탐색
ReAct: 외부 도구 상호작용
Reflexion: 실패로부터 학습
Monte Carlo Tree Search (MCTS): 탐색 최적화

6가지 핵심 작업

1. Selection (선택)
    ↓
2. Expansion (확장)
    ↓
3. Evaluation (평가)
    ↓
4. Simulation (시뮬레이션)
    ↓
5. Backpropagation (역전파)
    ↓
6. Reflection (성찰)

각 단계 상세

단계	설명	기반 기법
Selection	탐색할 노드 선택	MCTS (UCB1)
Expansion	새로운 가능성 생성	ToT
Evaluation	유망함 평가	ToT
Simulation	행동 실행 및 관찰	ReAct
Backpropagation	결과 역전파	MCTS
Reflection	실패 시 반성	Reflexion

통합된 기법들

기법	LATS에서의 역할
Tree Search	다중 경로 탐색 구조
ReAct	외부 도구 상호작용
Reflexion	실패로부터 학습
MCTS	탐색 효율 최적화

성능

LATS는 모든 기법을 통합한 만큼, 압도적인 성능을 보여줍니다:

벤치마크	이전 최고	LATS
HotpotQA	78%	83.8%
HumanEval	91% (Reflexion)	94.4%
WebShop	67%	75.9%

동작 예시: 코딩 문제

[문제] "파이썬으로 병합 정렬 구현하기"

[Selection]
UCB1 점수가 높은 노드 선택
→ 재귀적 구현 접근 선택

[Expansion]
세 가지 구현 방식 생성:
  - 방식 1: 기본 재귀
  - 방식 2: 최적화된 재귀 (in-place)
  - 방식 3: 반복적 구현

[Evaluation]
각 방식의 유망함 평가:
  - 방식 1: 0.7 (간단하지만 메모리 비효율)
  - 방식 2: 0.9 (균형 잡힌 접근)
  - 방식 3: 0.6 (복잡함)

[Simulation - ReAct]
방식 2 구현:
  Thought: 배열을 반으로 나누고 재귀 호출
  Action: [Code] def merge_sort(arr): ...
  Observation: 코드 작성 완료

  Thought: 테스트 실행
  Action: [Execute] merge_sort([3,1,4,1,5,9])
  Observation: [1,1,3,4,5,9] ✓

[Backpropagation]
테스트 통과 → 점수 역전파
방식 2 경로의 UCB1 점수 상승

[완료]
최종 코드 반환

실패 시 Reflection

[Simulation 실패 시]
Action: [Execute] merge_sort([])
Observation: IndexError: list index out of range

[Reflection]
"빈 배열에 대한 경계 조건 처리가 없었다.
 재귀의 기저 조건에 빈 배열 체크를 추가해야 한다."

[재시도]
def merge_sort(arr):
    if len(arr) <= 1:  # 경계 조건 추가
        return arr
    ...

UCB1 알고리즘

LATS는 MCTS의 UCB1(Upper Confidence Bound)을 사용하여 탐색과 활용의 균형을 맞춥니다:

UCB1 = 평균 보상 + C × √(ln(부모 방문 횟수) / 자식 방문 횟수)

평균 보상: 이 경로가 얼마나 좋았는가 (활용)
탐색 항: 덜 방문한 경로에 보너스 (탐색)
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)

비용-성능 트레이드오프

         성능
           ^
           |              LATS ★
           |             /
           |      Reflexion ★
           |           /
           |    ToT ★
           |       /
           |   CoT ★
           |   /
           +---------------> 비용

LATS는 가장 높은 성능을 제공하지만, 비용도 가장 높습니다.

언제 LATS를 사용해야 하는가?

상황	권장
단순한 작업	CoT로 충분
도구 필요	ReAct
탐색 필요	ToT
복잡한 코딩	Reflexion
최고 성능 필요	LATS

개념