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 (성찰) — 실패 시 반성한다.

각 단계 상세

통합된 기법들

성능

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

동작 예시: 코딩 문제

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

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)을 사용하여 탐색과 활용의 균형을 맞춥니다:

$\text{UCB1} = \bar{x} + C \times \sqrt{\frac{\ln(N)}{n}}$

• $\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)

비용-성능 트레이드오프

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

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

관련 개념

• Tree of Thought (ToT): 다중 경로 탐색
• ReAct: 도구 사용
• Reflexion: 실패로부터 학습
• Monte Carlo Tree Search: 게임 AI 탐색 알고리즘