왜 단일 경로 에이전트는 실패하는가

LLM 에이전트를 코드 수정이나 버그 픽스에 붙이면, 대부분 한 번 세운 계획을 끝까지 밀어붙인다. 초반에 잘못된 가정(틀린 파일 경로, 잘못 읽은 스택트레이스)을 하면 그 뒤의 모든 단계가 오염된다. 온도(temperature)를 올려 여러 번 재시도해도, 각 시도가 서로의 실패에서 배우지 못하면 성공률은 로그 스케일로만 오른다.

핵심 문제는 되돌아가기(backtrack)의 부재다. 사람은 막히면 두세 단계 전으로 돌아가 다른 선택지를 시도하지만, 순차 에이전트는 이미 소비한 컨텍스트에 갇혀 같은 실수를 반복한다.

트리 탐색의 기본 구조

해법은 문제 해결 과정을 하나의 직선이 아니라 트리로 모델링하는 것이다. 각 노드는 "현재 상태 + 지금까지의 행동 이력"이고, 엣지는 하나의 액션(파일 수정, 테스트 실행 등)이다. 루트에서 시작해 유망한 노드를 확장(expand)하고, 실패하면 형제 노드로 되돌아간다.

class Node:
    def __init__(self, state, parent=None, action=None):
        self.state = state          # 코드베이스 스냅샷 + 대화 이력
        self.parent = parent
        self.action = action
        self.children = []
        self.visits = 0
        self.value = 0.0            # 지금까지 관측된 평균 보상

    def ucb(self, c=1.4):
        import math
        if self.visits == 0:
            return float('inf')
        exploit = self.value / self.visits
        explore = c * math.sqrt(math.log(self.parent.visits) / self.visits)
        return exploit + explore

UCB(Upper Confidence Bound) 점수로 "지금까지 좋았던 노드"와 "덜 탐색한 노드" 사이 균형을 잡는다. 이것이 MCTS(Monte Carlo Tree Search)의 선택 단계다.

보상 신호를 어떻게 정의할까

트리 탐색의 성패는 어떤 노드가 좋은지 판정하는 신호에 달렸다. 코딩 작업이라면 "판정 가능한(verifiable) 보상"을 최대한 활용해야 한다. LLM 자기평가만으로는 편향이 크다.

보상 소스신뢰도비용
단위 테스트 통과 수높음중간(실행 필요)
컴파일/타입체크 성공높음낮음
정적분석 경고 감소중간낮음
LLM 리뷰어 점수낮음중간(토큰)

실무에서는 값싼 신호(타입체크)로 먼저 가지치기하고, 살아남은 노드에만 비싼 신호(전체 테스트 스위트)를 돌리는 계층적 평가가 효율적이다.

탐색 루프 구현

선택 → 확장 → 평가 → 역전파(backpropagation)의 한 사이클이다. 확장 시 LLM에게 서로 다른 접근을 주문해 형제 노드의 다양성을 확보하는 것이 중요하다.

def search(root, budget=20):
    for _ in range(budget):
        node = root
        while node.children:                 # 1. 선택
            node = max(node.children, key=lambda n: n.ucb())

        if not is_terminal(node.state):       # 2. 확장
            actions = propose_actions(node.state, k=3)  # LLM이 다른 3가지 제안
            for a in actions:
                child = Node(apply(node.state, a), node, a)
                node.children.append(child)
            node = node.children[0]

        reward = evaluate(node.state)         # 3. 평가(테스트 실행)

        while node:                           # 4. 역전파
            node.visits += 1
            node.value += reward
            node = node.parent

    return best_leaf(root)

budget는 탐색 예산이다. 무한정 넓히면 비용이 폭발하므로, 노드 확장 폭(k)과 총 반복 횟수로 명시적으로 제한한다.

비용 폭발을 막는 실전 장치

트리 탐색은 성공률을 올리는 대신 토큰·실행 비용을 몇 배로 늘린다. 통제 없이 켜면 CI 한 번에 수만 토큰이 사라진다. 다음 가드레일을 걸어야 한다.

  • 깊이·폭 상한: 예) 최대 깊이 8, 노드당 자식 3개 이하.
  • 조기 종료: 테스트 전부 통과하는 노드가 나오면 즉시 반환.
  • 중복 상태 병합: 같은 diff에 도달한 노드는 해시로 합쳐 재탐색 방지.
  • 가지치기: 타입체크 실패 노드는 확장 대상에서 제외.
# 실행 격리 + 예산 상한을 함께 거는 예시
export MAX_NODES=20
export MAX_DEPTH=8
timeout 600 python run_tree_search.py \
  --sandbox docker \
  --early-stop-on-green \
  --dedup-by-diff-hash

언제 쓰고 언제 쓰지 말아야 하나

트리 탐색은 검증 가능한 목표가 있고, 정답 경로가 좁은 문제에 잘 맞는다. 버그 픽스, 테스트를 통과시키는 구현, SQL 쿼리 최적화처럼 "맞았는지 자동 판정"이 되는 작업이다. 반대로 명세가 모호하거나 보상을 정의할 수 없는 창작성 작업에서는, 탐색이 잘못된 방향으로 자원만 태운다.

또한 sandbox 격리는 선택이 아니라 필수다. 트리의 각 노드가 파일 시스템이나 DB를 실제로 건드리므로, 격리 없이는 형제 노드끼리 상태를 오염시킨다. Docker 컨테이너나 git worktree로 노드별 작업공간을 분리하라.

정리

단일 경로 에이전트의 성공률 한계는 되돌아가기의 부재에서 온다. 문제 해결을 트리로 모델링하고, 값싼 신호로 가지치기한 뒤 비싼 검증을 계층적으로 적용하면, 같은 모델로도 성공률을 유의미하게 끌어올릴 수 있다. 다만 비용 상한과 실행 격리를 먼저 설계하지 않으면 실전에 투입할 수 없다는 점을 기억하자.