사고 트리(Tree of Thoughts; ToT)와 LATS(Language Agent Tree Search): 의도적 탐색(Deliberate Search)

하나의 사고 연쇄(Chain-of-Thought; CoT) 궤적에는 되돌아갈 여지가 없습니다. 사고 트리(Tree of Thoughts; ToT, Yao et al., 2023)는 추론을 트리로 바꾸고 각 노드에서 자기 평가(self-evaluation)를 수행합니다. LATS(Zhou et al., 2024)는 ToT를 ReAct, Reflexion과 함께 몬테카를로 트리 탐색(Monte Carlo Tree Search; MCTS) 아래에 통합합니다. Game of 24는 CoT에서 4%였던 정확도가 ToT에서 74%로 올라가며, LATS는 HumanEval에서 pass@1 92.7%를 기록합니다.

유형: Build 언어: Python (stdlib) 선수 학습: Phase 14 · 01 (에이전트 루프), Phase 14 · 03 (Reflexion) 소요 시간: 약 75분

학습 목표

• 추론을 탐색(search)으로 바라봅니다. 노드(node)는 "생각(thought)", 간선(edge)은 "확장(expansion)", 값(value)은 "얼마나 유망한가"를 뜻합니다.
• 자기 평가 점수를 사용하는 표준 라이브러리(stdlib) 기반 ToT 스타일 너비 우선 탐색(Breadth-First Search; BFS) 트리 탐색을 구현합니다.
• 선택(select), 확장(expand), 시뮬레이션(simulate), 역전파(backpropagate)를 갖춘 간단한 LATS MCTS 루프로 확장합니다.
• 언제 탐색이 토큰 배수(token multiplier)를 감수할 만큼 가치가 있는지(Game of 24, 코드 생성)와, 언제 하나의 궤적이면 충분한지(단순 질의응답)를 판단합니다.

문제

사고 연쇄는 한 방향으로만 걸어가는 선형적인 흐름(linear walk)입니다. 첫 단계가 틀리면 이후의 모든 단계는 잘못된 전제 위에서 작동하게 됩니다. Game of 24(네 숫자를 +, -, *, /로 조합해 24를 만드는 문제)에서 GPT-4 CoT는 정확도 4%에 그칩니다. 모델은 초기에 잘못된 부분식(subexpression)을 고르고, 이후에는 그 선택을 되돌리지 못합니다.

추론에 필요한 것은 여러 후보를 제안하고, 평가하고, 유망한 후보를 고르고, 막다른 길이 나오면 되돌아가는 능력입니다. 이것이 곧 탐색(search)입니다. 사고 트리(ToT)와 LATS는 이 아이디어를 대표하는 두 가지 형식화입니다.

개념

사고 트리(Tree of Thoughts; Yao et al., NeurIPS 2023)

각 노드는 일관된 중간 단계, 즉 "하나의 생각(thought)"입니다. 각 노드는 K개의 자식 생각으로 확장될 수 있습니다. LLM은 채점 프롬프트(scoring prompt)를 사용해 각 노드를 자기 평가합니다. 탐색은 BFS, 깊이 우선 탐색(Depth-First Search; DFS), 또는 빔 탐색(beam search) 방식으로 트리를 살펴봅니다.

                     (root: "find 24 from 4 6 4 1")
                    /               |            \
           ("6 - 4 = 2")    ("4 + 1 = 5")    ("4 * 6 = 24")  <- Score: HIGH
              /   \              |                  |
          ...    ...          ...                finish

자기 평가는 이 구조에서 가장 핵심이 되는 요소입니다. 논문은 세 가지 변형을 보여줍니다. sure / likely / impossible 분류, 1..10 숫자 점수, 후보 간 투표(vote)가 그 세 가지입니다. 세 방식 모두 Game of 24에서 CoT보다 크게 앞서며, GPT-4 기준으로 4%에서 74%까지 상승했습니다.

LATS(Zhou et al., ICML 2024)

LATS는 ToT, ReAct, Reflexion을 MCTS 아래에서 통합합니다. LLM은 세 가지 역할을 수행합니다.

• 정책(Policy): 다음 행동(action) 후보를 제안합니다. ReAct 스타일입니다.
• 가치 함수(Value function): 부분 궤적(partial trajectory)을 채점합니다. ToT 스타일의 자기 평가입니다.
• 자기 회고기(Self-reflector): 실패했을 때 자연어로 회고(reflection)를 작성합니다. Reflexion 스타일이며, 작성된 회고는 이후 롤아웃(rollout)을 다시 시작하는 데 사용됩니다.

환경 피드백(environment feedback), 즉 관찰(observation)은 가치 함수에 섞여 들어갑니다. 그래서 탐색은 단순한 모델 의견뿐 아니라 실제 도구 결과로부터도 정보를 얻습니다. 논문 발표 당시의 결과는 다음과 같습니다. GPT-4를 사용한 HumanEval pass@1은 92.7%(당시 SOTA)였고, GPT-3.5를 사용한 WebShop 평균 점수는 75.9로, 경사 기반 미세 조정(gradient-based fine-tuning)에 근접하는 수준이었습니다.

최소한의 MCTS

각 반복(iteration)은 네 단계로 진행됩니다.

1. 선택(Select) — UCT(Upper Confidence Bound for Trees)를 사용해 뿌리(root)에서 잎(leaf)까지 내려갑니다.
2. 확장(Expand) — 정책을 사용해 K개의 자식 노드를 생성합니다.
3. 시뮬레이션(Simulate) — 정책을 사용해 자식 노드에서 잎까지 롤아웃하고, 가치 함수 또는 환경 보상(environment reward)으로 잎을 채점합니다.
4. 역전파(Backpropagate) — 방문 횟수(visit count)와 가치 추정값을 경로 위쪽으로 갱신합니다.

UCT 공식은 Q(s, a) + c * sqrt(ln N(s) / N(s, a))입니다. 첫 번째 항은 활용(exploitation), 두 번째 항은 탐색(exploration)을 의미합니다. c는 작업별로 조정합니다.

비용의 현실

탐색은 토큰 사용량을 폭발적으로 늘립니다. Game of 24에서 ToT는 CoT 대비 토큰을 100~1000배 사용하며, LATS도 비슷한 수준입니다. 이는 결코 공짜가 아닙니다. 탐색은 다음과 같은 경우에만 아껴서 사용하는 것이 좋습니다.

• 하나의 궤적만으로는 명백히 부족한 작업. Game of 24나 복잡한 코드 생성이 여기에 속합니다.
• 실행 시간(wall-clock time)보다 정답성(correctness)이 더 중요한 작업.
• 저렴하면서도 신뢰할 수 있는 가치 함수가 존재하는 작업. 코드의 단위 테스트(unit test)나 수학의 명시적 목표값이 좋은 예입니다.

만약 작업에 단 하나의 정답만 존재하는데 평가자(evaluator)가 잡음이 많은(noisy) 경우, 탐색은 오히려 상황을 악화시키는 경우가 많습니다. "점수는 좋아 보이지만 실제로는 틀린 답"을 찾아내기 때문입니다.

2026년의 위치

대부분의 프로덕션 에이전트는 LATS를 실행하지 않습니다. 대신 도구 기반 검증(tool-grounded verification, CRITIC, 05강)을 붙인 ReAct를 실행합니다. 탐색은 특수한 영역에서 모습을 드러냅니다.

• 테스트를 가치 함수로 실행하는 코딩 에이전트(HumanEval 스타일).
• 여러 질의 경로를 탐색하는 심층 리서치(deep-research) 에이전트.
• LangGraph 하위 그래프(subgraph) 안의 계획 중심 워크플로(planning-heavy workflow).

AlphaEvolve(11강)는 2025년의 극단적인 사례입니다. 코드 위에서 진화적 탐색(evolutionary search)을 수행하고, 기계로 확인 가능한 적합도(machine-checkable fitness)를 사용해 최전선의 성능 향상을 냅니다. 56년 만의 첫 4x4 행렬 곱셈(matmul) 개선이 그 예입니다.

만들어보기

code/main.py는 다음을 구현합니다.

• 양식화된 "산술 연산 고르기" 작업 위에서 동작하는 작은 ToT BFS.
• 같은 작업 위에서 UCT 선택을 사용하는 간단한 LATS MCTS 루프. 선택, 확장, 시뮬레이션, 역전파를 포함합니다.
• 기호적 점수(symbolic score)와 자기 평가 점수를 조합하는 가치 함수.

다음과 같이 실행합니다.

python3 code/main.py

실행 추적(trace)을 보면, ToT는 BFS로 노드마다 세 개의 후보를 확장하는 모습을 보여줍니다. LATS는 MCTS를 통해 가장 좋은 롤아웃으로 수렴해 가는 모습이며, 두 방식이 사용한 토큰 수가 함께 출력됩니다.

사용해보기

LangGraph는 ToT 스타일 탐색을 하위 그래프(subgraph) 패턴으로 제공합니다. LangChain 팀의 2024년 5월 LATS 블로그 글이 참고할 만한 튜토리얼입니다. LlamaIndex는 TreeOfThoughts 에이전트를 제공합니다. 2026년 대부분의 프로덕션 에이전트에서는 이 패턴이 if task_complexity > threshold: use_search() 같은 조건문 뒤에 숨어 있습니다. 자세한 내용은 05강의 평가자-최적화기(evaluator-optimizer) 패턴을 참고하세요.

산출물 만들기

outputs/skill-search-policy.md는 작업 형태(task shape), 예산(budget), 평가자 충실도(evaluator fidelity)에 따라 선형 ReAct, ToT, LATS, 진화적 탐색 중 무엇을 쓸지 선택해 줍니다.

연습문제

1. 간단한 LATS를 UCT c=0.1과 c=2.0으로 각각 실행해 보세요. 실행 추적에서 무엇이 달라지나요?
2. 가치 함수를 더 잡음이 많은 채점기(noisier scorer)로 바꿔 보세요. 무작위 흔들림(random jitter)을 추가하면 됩니다. MCTS는 여전히 가장 좋은 잎을 찾을 수 있나요? 견딜 수 있는 최소 신호 대 잡음비(signal-to-noise ratio)는 어느 정도인가요?
3. 빔 탐색 ToT를 구현해 보세요. 각 수준에서 상위 k개만 유지합니다. 토큰 예산이 빠듯할 때 BFS와 비교하면 어느 쪽이 더 나은가요?
4. LATS 논문 5.1절을 읽어 보세요. HumanEval 궤적 수를 재현해 봅니다. 보고된 pass@1에 도달하려면 몇 번의 롤아웃이 필요한가요?
5. LATS 논문의 "LATS가 덜 도움이 되는 경우(when LATS helps less)" 논의를 읽어 보세요. 작업 형태를 탐색 전략에 매핑하는 한 문단짜리 결정 규칙을 작성해 봅니다.

핵심 용어

더 읽을거리

• Yao et al., Tree of Thoughts (arXiv:2305.10601) — 사고 트리(ToT)의 표준이 되는 원 논문입니다.
• Zhou et al., LATS (arXiv:2310.04406) — Reflexion 피드백을 포함한 MCTS 기반 LATS 논문입니다.
• LangGraph overview — 탐색을 위한 하위 그래프 패턴 가이드입니다.
• AlphaEvolve (arXiv:2506.13131) — 프로그램 기반 평가자를 사용하는 진화적 탐색의 사례입니다.