Tree of Thoughts의 평가 함수와 가지치기 설계: 추론 정밀도와 API 비용을 양립하는 Python 구현

이 기사에서 알 수 있는 것

• Tree of Thoughts (ToT)에서의
  평가 함수의 3가지 설계 패턴과 활용 방법 -
  **임계값 기반(Threshold-based)・빔 컷오프(Beam Cutoff)・적응형 가지치기(Adaptive Pruning)**의 구현 방법과 정밀도·비용에 미치는 영향 -
  BFS・DFS・빔 서치(Beam Search)의
  탐색 전략별 비용 계산식과 선정 기준 -
  평가용 모델과 생성용 모델을 분리하여
  API 비용을 50-75% 절감하는 구현 패턴 -
  2026년 최신 기법(DST・LiteSearch)을 도입한
  적응형 빔 서치 구축 방법

대상 독자

상정 독자: LLM 애플리케이션 개발 중급자~상급자 -
필요한 전제 지식:- Python 3.11 이상의 기본 문법(dataclass, asyncio) - OpenAI API (gpt-4o)의 기본적인 사용법 - 트리 탐색 알고리즘(BFS・DFS)의 기초 개념 - Tree of Thoughts의 기본 개념(기존 기사로 예습 가능)

• Python 3.11 이상의 기본 문법

결론·성과

ToT 구현에 있어서, 평가 함수와 가지치기(Pruning) 전략의 설계는 추론 정밀도와 API 비용 모두를 좌우합니다. 원 논문의 LLM 자기 평가 방식에서는, Game of 24 태스크에서 CoT(4%) 대비 74%의 정답률을 달성했으나, 탐색 노드당 3-5회의 API 호출이 필요하여 CoT의 10-100배의 토큰 소비가 발생합니다.

본 기사에서 소개하는 설계 패턴을 조합함으로써, 다음과 같은 개선이 보고되었습니다.

기법	정밀도에 미치는 영향	비용 절감률	출처
평가 모델 분리 (생성: GPT-4o / 평가: GPT-4o-mini)	정밀도 유지 (-2% 이내)	약 50% 절감	원 논문의 실험 설정에 기반한 추정
...

평가 함수의 3가지 설계 패턴을 이해하기

ToT의 성능은 평가 함수의 질과 직결됩니다. Yao et al. (2023)의 원 논문에서는, 랜덤 평가 함수로 교체할 경우 정답률이 74%에서 약 10%로 급락한다고 보고되었습니다. 여기서는 실무에서 구분하여 사용해야 할 3가지 평가 패턴을 정리합니다.

패턴 1: LLM 자기 평가 (분류 방식)

원 논문에서 제안된 방식입니다. LLM 스스로 중간 상태를 평가하게 하여, sure / likely / impossible의 3가지 분류로 판정합니다.

from openai import OpenAI
from dataclasses import dataclass
EVALUATE_PROMPT = """다음 추론 상태를 평가해 주세요.
...

이 방식의 포인트는 여러 번 샘플링하여 확률적으로 스코어를 산출한다는 점입니다. 원 논문에서는 샘플 수

여기서

장점과 제약:

장점: 도메인 지식 없이 범용적으로 적용 가능 -
제약: 평가 1회당 회의 API 호출이 필요. 노드 수 $n$인 탐색 트리 전체에서는 $N$회의 호출이 되어 비용이 급증함 $N \times n$ -
주의점: temperature=0.7로 샘플링하는 것이 중요. temperature=0에서는 모든 샘플이 동일한 레이블이 되어 확률 추정의 의미가 없어짐

패턴 2: 스코어링 방식 (수치 평가)

LLM에게 1-10의 수치 스코어로 직접 평가하게 하는 방식입니다. 분류 방식보다 더 세밀한 평가가 가능하지만, LLM의 수치 출력은 불안정하기 때문에 공학적 기법이 필요합니다.

SCORE_PROMPT = """다음 추론 상태를 1부터 10까지의 스코어로 평가해 주세요.
문제: {problem}
현재 추론 상태: {state}
...

분류 방식과의 활용 구분:

관점	분류 방식 (sure/likely/impossible)	스코어링 방식 (1-10)
입도(Granularity)	거침 (실질적 3단계)	세밀함 (10단계)
...

패턴 3: 도메인 특화 휴리스틱 (Heuristic)

LLM을 사용하지 않고, 태스크 고유의 평가 함수를 프로그램으로 구현하는 방식입니다. API 비용이 전혀 들지 않으며 빠르게 동작합니다. Game of 24를 예로 들어 구현해 보겠습니다.

from itertools import combinations
def domain_heuristic_evaluate(numbers: list[float], target: float = 24.0) -> float:
"""Game of 24을 위한 도메인 특화 휴리스틱 (Domain-Specific Heuristic).
...```

2026년에 발표된 DST (Domain-Specialized Tree of Thought) 논문에서는 이 개념을 더욱 발전시켜, **경량화된 지도 학습 모델 (plug-and-play predictor)을 평가 함수로 삽입하는** 접근 방식을 제안합니다. 이 접근 방식은 표준 ToT와 동등하거나 그 이상의 정밀도를 유지하면서 계산 비용을 **26-75% 절감**할 수 있다고 보고되었습니다 (Nie et al., 2026).

## 가지치기 (Pruning) 전략 구현하기

평가 함수에서 점수가 매겨진 노드를 어떻게 선별하느냐가 바로 가지치기 (Pruning) 전략입니다. 여기서는 실무에서 사용되는 4가지 패턴과 그 구현을 보여줍니다.

### 임계값 기반 가지치기 (Threshold-based Pruning)

가장 단순한 전략입니다. 점수가 일정 임계값 (Threshold) 미만인 노드를 즉시 제거합니다.

```python
def threshold_pruning(
    nodes: list[ThoughtNode],
    threshold: float = 0.3,
    ...

임계값 설정이 매우 중요합니다. 너무 낮으면 불필요한 탐색이 늘어나고, 너무 높으면 유망한 경로를 잘라버릴 수 있습니다.

임계값	경향	적합한 케이스
0.1-0.2	탐색 범위가 넓음, 비용 높음	정답률을 최대화하고 싶은 경우
...
주의사항: 임계값은 평가 함수의 점수 분포에 따라 달라집니다. 분류 방식에서는

빔 컷오프 가지치기 (Beam Cutoff Pruning)

각 깊이 레벨에서 상위

def beam_cutoff_pruning(
    nodes: list[ThoughtNode],
    beam_width: int = 5,
    ...

빔 폭 (Beam width)

예를 들어

여기서

다양성을 고려한 가지치기 (Diversity-aware Pruning)

점수 상위 노드만 남기면 의미적으로 유사한 사고가 집중되는 문제가 발생할 수 있습니다. 다양성 가지치기에서는 점수와 다양성의 균형을 맞춥니다.

def diversity_pruning(
    nodes: list[ThoughtNode],
    beam_width: int = 5,
    ...

diversity_weight

조정 지침:

: 점수만 고려 (일반적인 빔 컷오프와 동일) 0.0 -
-0.2 : 권장값. 점수를 중시하면서 유사 해답을 배제 0.3 -
이상: 다양성 중시. 탐색적 작업 (브레인스토밍 등)에 적합 0.5

적응형 가지치기 (Adaptive Pruning, 2026년 최신 접근 방식)

DST 논문과 LiteSearch (AAAI 2025)의 지견을 통합한 방식입니다. 문제의 난이도에 따라 빔 폭을 동적으로 조정합니다.

def adaptive_pruning(
    nodes: list[ThoughtNode],
    min_beam: int = 2,
    ...

이 방식의 개념을 그림으로 정리합니다.

이 접근 방식의 장점: 간단한 추론 단계에서는 계산 비용 26-75% 절감이 보고되었습니다.

탐색 전략 선정 및 비용 추정 수행하기

평가 함수와 가지치기를 결합한 완전한 ToT 파이프라인을 구축합니다. BFS, DFS, 빔 서치 (Beam Search)의 세 가지 탐색 전략을 비교하고, 작업에 따른 선정 기준을 제시합니다.

빔 서치 방식 (권장)

많은 작업에서 정밀도와 비용의 균형을 맞출 수 있는 권장 방식입니다.

import asyncio
from openai import AsyncOpenAI
THOUGHT_GEN_PROMPT = """문제: {problem}
...```

### 탐색 전략 비교

각 전략의 비용 특성을 정리합니다. 분기 수

| 전략 | 최대 노드 수 | 비용 예측 가능성 | 정밀도 경향 | 권장 작업 |
|---|---|---|---|---|
| BFS (전폭 탐색) |
| | 낮음 | 높음 | 정답이 하나인 퍼즐 |
| DFS |
| 최악 | | 중간 | 깊은 추론 체인 |
| 빔 서치 |
| | 높음 | | 범용적으로 권장 |

**비용 예측 구체적 예시** (빔 서치, 평가에 LLM 자기 평가 3회 샘플링 사용):

- 파라미터: k=5, b=3, d=3, n=3
- 최대 노드 수: 5 × 3 × 3 = 45
- 생성 API 호출 횟수: 45회
- 평가 API 호출 횟수: 45 × 3 = 135회
- 총 API 호출 횟수: 180회

GPT-4o의 입출력 토큰 단가를 고려하면, 문제당 비용은 다음과 같이 추산할 수 있습니다.

### 모델 분리 전략의 구현

비용 절감 효과가 즉각적인 방법은 **생성용 모델과 평가용 모델을 분리**하는 것입니다.

```python
async def cost_optimized_tot(
    problem: str,
    gen_model: str = "gpt-4o",
    ...

이 분리가 유효한 이유는 평가 태스크가 생성 태스크보다 단순하기 때문입니다. "이 상태가 유망한가?"라는 판정은 "다음 추론 단계를 생각하라"는 것보다 인지적으로 가벼운 태스크입니다. 원 논문의 실험 설정을 참고하면, 평가에 GPT-3.5(현재의 GPT-4o-mini 상당)를 사용하더라도 정확도 저하는 -2% 정도로 억제될 수 있음이 시사되었습니다.

비용 최적화 실천 패턴 적용하기

지금까지의 컴포넌트를 조합하여 실제 태스크에 적용할 때의 패턴을 제시합니다.

패턴 1: 단계적 에스컬레이션 (Stepwise Escalation)

먼저 저렴한 설정으로 탐색하고, 해답을 찾지 못하면 단계적으로 탐색 범위를 확대하는 방식입니다.

async def escalating_tot(
    client: AsyncOpenAI,
    problem: str,
    ...

첫 단계에서 해결된다면 API 호출은 [비용 절감된 수치]로 충분합니다. 단계 3까지 진행하더라도 총 노드 수는 약 250개 정도입니다. 모든 문제를 단계 3 설정으로 풀 경우(200 노드)와 비교했을 때, 쉬운 문제가 많을수록 비용을 대폭 절감할 수 있습니다.

패턴 2: 탐색 예산 제어 (Search Budget Control)

LiteSearch (AAAI 2025)의 개념을 도입하여, 노드 전개 총수에 상한을 두고 탐색을 중단하는 방식입니다.

async def budget_controlled_tot(
    client: AsyncOpenAI,
    problem: str,
    ...

max_nodes=30과 같이 설정하면 API 호출 횟수의 상한이 확정됩니다. 이를 통해 문제당 최대 비용을 사전에 계산할 수 있습니다.

비용 추산 요약표

실무에서 사용할 수 있는 추산표를 준비했습니다. 평가에 GPT-4o-mini (샘플 수 3)를 사용하는 경우의 개략적인 수치입니다.

설정	노드 수	API 호출	예상 비용 (USD/문제)
최소:	8	32	~$0.01
표준:	45	180	~$0.05
풍부:	200	800	~$0.20
예산 제어: max=30	30	120	~$0.03
CoT (1-pass, 참고치)	1	1	~$0.002

이 수치는 GPT-4o로 생성(~200 토큰), GPT-4o-mini로 평가(~50 토큰)하는 것을 가정한 참고치입니다. 실제 비용은 프롬프트 길이 및 모델 가격 정책에 따라 달라집니다.

흔한 문제와 설계 판단 지침

ToT를 구현할 때 직면하기 쉬운 문제와 그 대응 방침을 정리합니다.

문제 1: 평가 함수가 너무 관대하거나 너무 엄격함

증상: 모든 노드가 높은 점수를 받음 (가지치기가 작동하지 않음), 또는 모든 노드가 낮은 점수를 받음 (탐색이 즉시 중단됨).

대응법: 평가 프롬프트에 구체적인 판정 기준을 기술합니다. "이 상태에서 정답에 도달할 수 있는가"뿐만 아니라, "남은 단계 수", "이용 가능한 정보" 등의 관점을 명시하면 점수의 분산이 개선됩니다.

문제 2: 탐색의 다양성 부족

증상: 빔(Beam) 내의 노드들이 의미론적으로 거의 동일한 추론 경로를 가짐.

대응법: 사고 생성 시 temperature를 조절해야 합니다. 다만, temperature를 너무 높이면 품질이 저하될 수 있으므로 주의가 필요합니다.

문제 3: 비용이 예상치를 초과함

증상: 탐색 트리가 예상보다 커져서 API 호출 횟수가 허용 범위를 넘어섬.

대응법: 예산 제어 방식을 사용하여 max_nodes로 상한을 고정합니다. 또한, 먼저 CoT로 답변을 시도하고 신뢰도가 낮은 경우에만 ToT로 전환하는 "CoT-first" 전략도 유효합니다.

문제	원인	권장 대처
모든 노드가 높은 점수	평가 프롬프트가 모호함	판정 기준의 구체화
...	temperature가 낮음
비용 초과	빔 폭(Beam width)·깊이가 과도함	max_nodes로 상한 고정
해를 찾지 못함	탐색 깊이 부족	단계적 에스컬레이션

설계 판단 플로우차트

요약 및 다음 단계

요약:

• ToT의 평가 함수는 **LLM 자기 평가 (Self-evaluation, 분류/스코어링)**의 3가지 패턴이 있으며, 태스크의 성격과 비용 제약에 따라 구분하여 사용한다.
• 도메인 특화 휴리스틱(Heuristic) - 가지치기(Pruning) 전략은 임계값 기반(Threshold-based) → 빔 컷오프(Beam cutoff) → 다양성 고려 → 적응형(Adaptive) 순으로 고기능화되며, DST 논문(2026)의 적응형 방식으로 계산 비용을 26-75% 절감할 수 있다고 보고되었다.
• 생성 모델과 평가 모델의 분리는 즉각적인 효과가 높으며, 정확도 저하를 -2% 이내로 억제하면서 API 비용을 약 50% 절감할 수 있다.
• **예산 제어(Budget control)**를 통해 문제당 최대 비용을 고정할 수 있어, 실제 운영 시 비용 예측이 가능해진다.
• CoT로 충분한 태스크에 ToT를 적용하는 것은 오버스펙이므로, 먼저 CoT를 시도해보고 정확도가 부족할 경우 ToT를 검토하는 것이 실무적인 판단이다.

다음 단계:

• 자신의 태스크에서 CoT의 정확도를 측정하여 ToT가 필요한지 판단한다.
• 필요한 경우, 빔 서치(Beam Search) 방식($k=5, b=3, d=3$)부터 시작하여 평가 함수를 조정한다.
• DST 논문의 plug-and-play predictor 방식을 참고하여, 도메인 특화된 경량 평가 함수를 검토한다.

참고

• Yao et al., "Tree of Thoughts: Deliberate Problem Solving with Large Language Models" (2023)
• Nie et al., "Domain-Specialized Tree of Thought through Plug-and-Play Predictors" (2026)
• Wang et al., "LiteSearch: Efficient Tree Search with Dynamic Exploration Budget" (AAAI 2025)
• Wu et al., "ToTRL: Unlock LLM Tree-of-Thoughts Reasoning Potential through Puzzles Solving" (ICLR 2026)
• Li et al., "Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey" (2025)
• OpenAI API Documentation - Models

관련 기사:

Discussion