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, expand, evaluate, simulate, backpropagate가 차례로 각 단계를 맡습니다. 실패한 경우에만 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는 정확도가 비용보다 중요한 복잡한 작업에 씁니다. 벤치마크 수치는 논문 보고치이며, 적용 환경에 따라 결과가 달라질 수 있습니다.