LATS(Language Agent Tree Search)

ToT·ReAct·Reflexion·MCTS를 트리 탐색 하나로 묶어 단일 기법보다 나은 해를 찾는 에이전트 프레임워크다.

개념

LATS(Language Agent Tree Search)는 ToT·ReAct·Reflexion·MCTS 네 기법을 통합한 프레임워크이다:

• 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는 추론·도구·탐색·성찰을 결합한다. 아래 수치는 LATS 논문(arXiv:2310.04406) 보고치로, 같은 조건에서 ReAct·Reflexion 등 단일 기법보다 높다. 다만 벤치마크마다 지표가 달라 단순 % 비교는 주의해야 한다.

동작 예시: 코딩 문제

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

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)

solve 루프의 메서드는 앞의 6단계 표와 그대로 대응한다. select는 Selection, expand는 Expansion, evaluate는 Evaluation, simulate는 Simulation(ReAct), backpropagate는 Backpropagation을 맡는다. 실패한 경우에만 reflect가 실행되어 교훈을 memory에 쌓고, 다음 확장에서 참조한다.

비용-성능 트레이드오프

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

선택 기준

관련 개념

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

정리

LATS는 ToT의 다중 경로 탐색, ReAct의 도구 사용, Reflexion의 실패 학습, MCTS의 UCB1 탐색을 한 트리 안에서 묶는다. Selection부터 Reflection까지 6단계를 반복하며, 유망한 경로에 자원을 몰아주고 실패에서는 교훈을 남긴다. 그만큼 호출 비용이 가장 높으므로, 단순 작업에는 CoT나 ReAct로 충분하고 LATS는 정확도가 비용보다 중요한 복잡한 작업에 쓴다. 벤치마크 수치는 논문 보고치이며, 적용 환경에 따라 결과가 달라질 수 있다.