1 들어가며
Chain-of-Thought (CoT) 프롬프팅은 모델이 단계별로 추론하도록 유도하여 복잡한 문제 해결 능력을 크게 향상시켰다. 하지만 CoT에는 근본적인 한계가 있다: 한번 선택한 추론 경로를 되돌릴 수 없다는 것이다.
예를 들어, 수학 문제를 풀다가 중간에 잘못된 접근을 선택했다면? CoT는 그대로 진행하여 틀린 답에 도달한다. 하지만 사람은 어떻게 하는가? 막다른 골목에 다다르면 뒤로 돌아가서(backtrack) 다른 경로를 시도한다.
Tree of Thoughts (ToT)는 바로 이러한 인간의 문제 해결 방식을 모델링한 기법이다. 여러 추론 경로를 트리 구조로 탐색하고, 각 경로를 평가하며, 필요시 되돌아가서 더 나은 경로를 찾는다.
이번 포스트에서는 Yao et al. (2024)의 연구를 중심으로 ToT의 원리, 실험 결과, 그리고 실무 적용 가능성을 상세히 분석한다.
2 Tree of Thoughts란?
2.1 핵심 개념
Tree of Thoughts (ToT)는 언어 모델이 문제를 해결할 때 여러 가능한 추론 경로를 트리 구조로 탐색하는 프레임워크다.
주요 특징: - 트리 구조: 각 노드는 “생각(thought)”을 나타냄 - 백트래킹: 막다른 골목에서 되돌아가기 가능 - 평가 기반: 각 생각을 평가하여 최선의 경로 선택 - 전략적 탐색: BFS, DFS 등 탐색 알고리즘 활용
2.2 Chain-of-Thought vs Tree of Thoughts
시각적으로 비교하면 차이가 명확하다:
Chain-of-Thought (선형 탐색):
Input → Thought 1 → Thought 2 → Thought 3 → Output
↓ ↓ ↓
(고정됨) (고정됨) (고정됨)Tree of Thoughts (트리 탐색):
Input
↓
┌────────────────────┼───────┐
Thought 1a 1b 1c
↓ ↓ ↓
┌────┼────┐ │ (평가: 낮음, 제거)
2a 2b 2c 2d
↓ ↓ ↓ ↓
(평가) (평가) (선택)(백트래킹)2.3 기본 프로세스
- 생각 분해 (Thought Decomposition): 문제를 중간 단계로 나눔
- 생각 생성 (Thought Generation): 각 단계에서 여러 후보 생각 생성
- 생각 평가 (State Evaluation): 각 생각의 품질 평가
- 탐색 알고리즘 (Search Algorithm): 최적 경로 탐색 (BFS, DFS 등)
3 ToT의 4단계 프로세스
Yao et al. (2024)의 논문에 따르면, ToT는 다음 4단계로 구성된다.
3.1 생각 분해 (Thought Decomposition)
목적: 문제를 어떤 중간 단계로 나눌 것인가를 정의한다.
핵심 질문: - 각 “생각”은 무엇을 나타내는가? - 몇 단계로 나눌 것인가? - 각 단계는 얼마나 구체적이어야 하는가?
예시: Game of 24
문제: 네 개의 숫자 (4, 9, 10, 13)로 24를 만들 수 있는가?
생각 분해:
- 각 "생각" = 하나의 중간 수식
- 단계 수 = 3 (네 개 숫자를 24로 만들려면 세 번의 연산 필요)
예시 생각:
- "13 - 9 = 4" (남은 숫자: 4, 4, 10)
- "4 * 10 = 40" (남은 숫자: 4, 40)
- "40 - 4 = 36" (최종: 36) ← 24가 아니므로 실패예시: Creative Writing
문제: 4개의 무작위 문장으로 연결된 에세이 작성
생각 분해:
- 각 "생각" = 한 문단의 작성 계획
- 단계 수 = 1 (전체 에세이 계획을 한 번에)
예시 생각:
- "첫 문장으로 도입 → 두 번째 문장으로 전개 → ..."
- "시간 순서로 배열: 과거 → 현재 → 미래"
- "대조 구조: 문제 제기 → 해결책 제시"중요한 점: 생각의 “입도(granularity)”는 문제에 따라 다르다. - 너무 작으면: 탐색 공간이 폭발적으로 증가 - 너무 크면: 유연성 부족, CoT와 차이 없음
3.2 생각 생성 (Thought Generation)
목적: 각 단계에서 가능한 여러 생각 후보를 생성한다.
두 가지 방법:
3.2.1 Sample (샘플링)
독립적으로 여러 생각을 샘플링한다 (i.i.d.).
prompt = f"""
Possible next steps for the equation:
Current state: {current_state}
Generate a next step.
"""
# temperature > 0으로 설정하여 다양한 생각 생성
thoughts = []
for _ in range(k): # k개 생성
thought = model.generate(prompt, temperature=0.7)
thoughts.append(thought)장점: 생각의 다양성 확보 단점: 중복 가능성
3.2.2 Propose (제안)
한 번에 여러 생각을 제안하도록 요청한다.
prompt = f"""
Current state: {current_state}
Propose 3 possible next steps:
1.
2.
3.
"""
response = model.generate(prompt, temperature=0)
thoughts = parse_numbered_list(response)장점: 중복 방지, 다양성과 관련성의 균형 단점: 프롬프트 복잡도 증가
3.3 생각 평가 (State Evaluation)
목적: 각 생각이 문제 해결에 얼마나 유망한지 평가한다.
두 가지 방법:
3.3.1 Value (가치 평가)
각 생각에 점수를 부여한다.
prompt = f"""
Evaluate if the following equation is likely to reach 24:
Equation: {equation}
Remaining numbers: {remaining}
Rate on a scale:
- sure/likely: This will definitely/probably reach 24
- maybe: Uncertain
- impossible: This cannot reach 24
Your evaluation:
"""
evaluation = model.generate(prompt)
score = parse_evaluation(evaluation) # sure=1.0, likely=0.75, maybe=0.5, impossible=0.0장점: 세밀한 비교 가능 단점: 평가 자체가 어려울 수 있음
3.3.2 Vote (투표)
여러 평가를 생성하고 다수결로 결정한다.
votes = []
for _ in range(num_votes):
evaluation = model.generate(evaluation_prompt)
votes.append(evaluation)
# 다수결
from collections import Counter
final_evaluation = Counter(votes).most_common(1)[0][0]장점: 더 안정적인 평가 단점: 비용 증가 (여러 번 평가)
3.4 탐색 알고리즘 (Search Algorithm)
목적: 어떤 순서로 트리를 탐색할 것인가를 결정한다.
3.4.1 BFS (Breadth-First Search, 너비 우선 탐색)
전략: 각 단계에서 가장 유망한 b개의 생각을 유지한다.
def bfs_search(initial_state, b=5):
"""
b: beam width (각 단계에서 유지할 생각의 개수)
"""
states = [initial_state]
for step in range(max_steps):
all_new_states = []
# 각 현재 상태에서 새로운 생각 생성
for state in states:
new_thoughts = generate_thoughts(state, k=5)
for thought in new_thoughts:
new_state = apply_thought(state, thought)
score = evaluate_state(new_state)
all_new_states.append((new_state, score))
# 상위 b개만 유지
all_new_states.sort(key=lambda x: x[1], reverse=True)
states = [s for s, _ in all_new_states[:b]]
# 종료 조건 확인
for state in states:
if is_goal(state):
return state
return None특징: - 최적해를 놓칠 확률 낮음 - 메모리 사용량 많음 - “체계적 탐색”에 적합
3.4.2 DFS (Depth-First Search, 깊이 우선 탐색)
전략: 하나의 경로를 끝까지 탐색한 후 백트래킹한다.
def dfs_search(initial_state, max_depth=10):
"""
깊이 우선 탐색 + 백트래킹
"""
def dfs(state, depth):
# 종료 조건
if is_goal(state):
return state
if depth >= max_depth:
return None
# 새로운 생각 생성 및 평가
thoughts = generate_thoughts(state, k=5)
evaluated = [(t, evaluate_thought(state, t)) for t in thoughts]
# 가장 유망한 것부터 시도 (휴리스틱)
evaluated.sort(key=lambda x: x[1], reverse=True)
for thought, score in evaluated:
# 명백히 불가능한 경로는 가지치기
if score == 0.0: # "impossible"
continue
new_state = apply_thought(state, thought)
result = dfs(new_state, depth + 1)
if result is not None:
return result # 성공
# 모든 경로 실패 → 백트래킹
return None
return dfs(initial_state, 0)특징: - 메모리 효율적 - 백트래킹 자연스럽게 구현 - 최적해를 놓칠 수 있음 - “시행착오”에 적합
4 실전 예제: Game of 24
Yao et al.의 논문에서 가장 인상적인 실험은 “Game of 24”다. 이 게임은 네 개의 숫자를 사칙연산으로 조합하여 24를 만드는 퍼즐이다.
4.1 문제 정의
입력: 네 개의 숫자 (예: 4, 9, 10, 13) 목표: 사칙연산으로 24 만들기 정답 예시: (13 - 9) * (10 - 4) = 4 * 6 = 24
4.2 왜 어려운가?
- 탐색 공간 크기: 네 개 숫자의 모든 순열과 연산 조합 = 수천 가지
- 막다른 골목: 잘못된 중간 단계는 절대 24에 도달 불가
- 전략 필요: 무작위 시도로는 해결 어려움
4.3 ToT 구현
import anthropic
from typing import List, Tuple, Optional
from dataclasses import dataclass
@dataclass
class GameState:
"""Game of 24 상태"""
numbers: List[int] # 남은 숫자들
operations: List[str] # 지금까지의 연산들
current_value: Optional[int] # 현재 값 (마지막 단계에서)
class ToT_Game24:
"""
Tree of Thoughts for Game of 24
"""
def __init__(self, api_key: str):
self.client = anthropic.Anthropic(api_key=api_key)
self.model = "claude-sonnet-4-20250514"
def generate_next_steps(self, state: GameState, k: int = 5) -> List[str]:
"""
Step 1: 다음 가능한 단계들 생성 (Thought Generation)
"""
numbers_str = ", ".join(map(str, state.numbers))
operations_str = "\n".join(state.operations) if state.operations else "None"
prompt = f"""
You are solving the Game of 24.
Current state:
- Remaining numbers: {numbers_str}
- Operations so far:
{operations_str}
Generate {k} possible next steps. Each step should:
1. Pick two numbers from the remaining numbers
2. Apply one operation (+, -, *, /)
3. Show the result
Format: "a OP b = c" (e.g., "10 - 4 = 6")
List {k} different next steps:
"""
message = self.client.messages.create(
model=self.model,
max_tokens=300,
temperature=0.7, # 다양성을 위해 temperature > 0
messages=[{"role": "user", "content": prompt}]
)
response = message.content[0].text.strip()
# 줄 단위로 파싱
steps = []
for line in response.split('\n'):
line = line.strip()
if '=' in line:
# "10 - 4 = 6" 형태 추출
steps.append(line)
return steps[:k]
def evaluate_step(self, state: GameState, step: str) -> float:
"""
Step 2: 각 단계 평가 (State Evaluation)
Returns:
0.0: impossible
0.5: maybe
0.75: likely
1.0: sure
"""
numbers_str = ", ".join(map(str, state.numbers))
prompt = f"""
Evaluate if this step is promising for reaching 24:
Current numbers: {numbers_str}
Proposed step: {step}
Consider:
1. Does this step lead toward 24?
2. Are the remaining numbers manageable?
3. Is there a clear path to 24?
Evaluate as one of:
- "sure": This will definitely reach 24
- "likely": This probably will reach 24
- "maybe": Uncertain
- "impossible": This cannot reach 24
Your evaluation (one word only):
"""
message = self.client.messages.create(
model=self.model,
max_tokens=20,
temperature=0,
messages=[{"role": "user", "content": prompt}]
)
evaluation = message.content[0].text.strip().lower()
# 점수 매핑
score_map = {
"sure": 1.0,
"likely": 0.75,
"maybe": 0.5,
"impossible": 0.0
}
# 부분 매칭
for key, value in score_map.items():
if key in evaluation:
return value
return 0.5 # 기본값
def apply_step(self, state: GameState, step: str) -> Optional[GameState]:
"""
단계를 적용하여 새로운 상태 생성
"""
try:
# "10 - 4 = 6" 파싱
import re
match = re.match(r'(\d+)\s*([\+\-\*/])\s*(\d+)\s*=\s*(\d+)', step)
if not match:
return None
a, op, b, result = match.groups()
a, b, result = int(a), int(b), int(result)
# 숫자가 현재 상태에 있는지 확인
numbers = state.numbers.copy()
if a not in numbers or b not in numbers:
return None
# 숫자 제거
numbers.remove(a)
numbers.remove(b)
# 결과 추가
numbers.append(result)
# 새로운 상태 생성
new_state = GameState(
numbers=numbers,
operations=state.operations + [step],
current_value=result if len(numbers) == 1 else None
)
return new_state
except Exception as e:
return None
def is_goal(self, state: GameState) -> bool:
"""
목표 상태인가? (숫자가 하나 남고 그 값이 24)
"""
return len(state.numbers) == 1 and state.numbers[0] == 24
def solve_bfs(self, numbers: List[int], b: int = 5) -> Optional[List[str]]:
"""
BFS로 Game of 24 풀이
Args:
numbers: 초기 숫자들
b: beam width (각 단계에서 유지할 상태 수)
"""
print(f"🎮 Game of 24: {numbers}")
print(f"🔍 BFS 탐색 시작 (beam width: {b})\n")
initial_state = GameState(numbers=numbers, operations=[], current_value=None)
states = [(initial_state, 1.0)] # (state, score)
max_steps = 3 # 4개 숫자 → 3번 연산 필요
for step_num in range(max_steps):
print(f"{'='*60}")
print(f"Step {step_num + 1}")
print(f"{'='*60}")
all_candidates = []
# 각 현재 상태에서 확장
for state, prev_score in states:
print(f"\n현재 상태: {state.numbers}")
# 새로운 단계들 생성
next_steps = self.generate_next_steps(state, k=5)
print(f"생성된 단계들: {len(next_steps)}개")
# 각 단계 평가
for step in next_steps:
new_state = self.apply_step(state, step)
if new_state is None:
continue
score = self.evaluate_step(state, step)
print(f" - {step} → score: {score}")
# 불가능한 경로는 가지치기
if score > 0.0:
all_candidates.append((new_state, score))
# 상위 b개만 유지
all_candidates.sort(key=lambda x: x[1], reverse=True)
states = all_candidates[:b]
print(f"\n유지된 상태: {len(states)}개")
# 목표 상태 확인
for state, score in states:
if self.is_goal(state):
print(f"\n{'='*60}")
print("✅ 해결책 발견!")
print(f"{'='*60}")
for op in state.operations:
print(f" {op}")
print(f" 최종 값: {state.numbers[0]}")
return state.operations
print(f"\n❌ 해결책을 찾지 못했습니다.")
return None
# 사용 예시
def main():
solver = ToT_Game24(api_key="your-api-key")
# 테스트 케이스
test_cases = [
[4, 9, 10, 13], # 쉬움: (13-9)*(10-4) = 24
[1, 5, 5, 5], # 어려움: 5*(5-(1/5)) = 24
[2, 8, 8, 14], # 중간: (8/(2-8/8))*2 = 24
]
for numbers in test_cases:
print("\n" + "="*80)
solution = solver.solve_bfs(numbers, b=3)
print("="*80 + "\n")
if solution:
print(f"✅ 성공: {' → '.join(solution)}")
else:
print(f"❌ 실패")
if __name__ == "__main__":
main()4.4 실행 결과 예시
================================================================================
🎮 Game of 24: [4, 9, 10, 13]
🔍 BFS 탐색 시작 (beam width: 3)
============================================================
Step 1
============================================================
현재 상태: [4, 9, 10, 13]
생성된 단계들: 5개
- 13 - 9 = 4 → score: 0.75 (likely)
- 10 - 4 = 6 → score: 0.5 (maybe)
- 10 + 13 = 23 → score: 1.0 (sure)
- 9 * 4 = 36 → score: 0.0 (impossible)
- 13 - 4 = 9 → score: 0.5 (maybe)
유지된 상태: 3개
============================================================
Step 2
============================================================
현재 상태: [4, 4, 10] # from 13-9=4
생성된 단계들: 5개
- 10 - 4 = 6 → score: 0.75 (likely)
- 4 * 4 = 16 → score: 0.5 (maybe)
- 10 + 4 = 14 → score: 0.25 (unlikely)
현재 상태: [4, 9, 23] # from 10+13=23
생성된 단계들: 5개
- 23 + 9 = 32 → score: 0.0 (impossible)
- 23 - 9 = 14 → score: 0.5 (maybe)
- 23 + 4 = 27 → score: 0.0 (impossible)
현재 상태: [9, 10, 13] # from 13-4=9
... (생략)
유지된 상태: 3개
============================================================
Step 3
============================================================
현재 상태: [4, 6] # from 10-4=6
생성된 단계들: 2개
- 6 * 4 = 24 → score: 1.0 (sure)
- 6 + 4 = 10 → score: 0.0 (impossible)
============================================================
✅ 해결책 발견!
============================================================
13 - 9 = 4
10 - 4 = 6
6 * 4 = 24
최종 값: 24
================================================================================5 실험 결과 분석
5.1 벤치마크 성능 비교
Yao et al. (2024)는 ToT를 세 가지 태스크에서 테스트했다:
- Game of 24: 네 숫자로 24 만들기
- Creative Writing: 네 문장으로 일관된 에세이 작성
- 5×5 Crosswords: 십자말풀이
5.2 Game of 24 결과
| 방법 | 성공률 |
|---|---|
| IO prompt | 7.3% |
| CoT prompt | 4.0% |
| CoT-SC (k=100) | 9.0% |
| ToT (b=1) | 45% |
| ToT (b=5) | 74% |
| IO + Refine (k=10) | 27% |
| IO (best of 100) | 33% |
| CoT (best of 100) | 49% |
핵심 인사이트:
- CoT보다 ToT가 압도적으로 우수: 74% vs 4%
- CoT는 한 번 잘못된 경로를 선택하면 되돌릴 수 없음
- ToT는 백트래킹으로 다른 경로 탐색 가능
- Beam width의 영향:
- b=1 (greedy): 45%
- b=5: 74%
- 더 많은 경로를 탐색할수록 성능 향상
- 샘플링만으로는 부족:
- CoT (best of 100): 49%
- ToT (b=5): 74%
- 단순히 여러 번 시도하는 것보다 전략적 탐색이 효과적
5.3 오답 패턴 분석
논문에서는 CoT와 ToT의 오답 패턴을 분석했다:
CoT의 오답 패턴: - Step 1에서 실패: 62% - Step 2에서 실패: 31% - Step 3 이상: 7%
→ CoT는 첫 단계부터 잘못된 경로를 선택하면 바로 실패
ToT의 오답 패턴: - Step 1에서 실패: 8% - Step 2에서 실패: 6% - Step 3 이상: 3% - Correct: 83%
→ ToT는 초기 실수를 복구 가능
실제 예시:
문제: 4, 9, 10, 13으로 24 만들기
CoT 실패 케이스:
Step 1: 13 + 10 = 23
Step 2: 23 + 9 = 32
Step 3: 32 - 4 = 28 ❌
→ Step 1의 선택이 잘못됨. 되돌릴 수 없음.
ToT 성공 케이스:
Step 1:
Option A: 13 + 10 = 23 (score: 0.5, maybe)
Option B: 13 - 9 = 4 (score: 0.75, likely) ✓ 선택
Option C: 10 * 4 = 40 (score: 0.0, impossible)
Step 2 (from Option B):
Option A: 4 + 4 = 8 (score: 0.5)
Option B: 10 - 4 = 6 (score: 0.75) ✓ 선택
Option C: 4 * 10 = 40 (score: 0.0)
Step 3:
6 * 4 = 24 ✅5.4 노드 방문 횟수 vs 성능
연구팀은 방문한 노드 수에 따른 성능을 측정했다:
결과: - IO (best of k): 노드 100개 방문 → 33% 성공률 - CoT (best of k): 노드 100개 방문 → 49% 성공률 - ToT (b=1~5): 노드 20~50개 방문 → 45%~74% 성공률
결론: ToT는 더 적은 노드를 방문하면서도 더 높은 성공률을 달성한다. 이는 전략적 탐색의 효과를 보여준다.
6 Creative Writing 실험
6.1 태스크 정의
입력: 네 개의 무작위 문장
1. "The old lighthouse stood alone on the cliff."
2. "Sarah had always been afraid of the dark."
3. "The package arrived three days late."
4. "In his pocket, he found a key he didn't recognize."목표: 이 네 문장을 모두 포함하는 일관된 짧은 에세이 작성
6.2 ToT 적용
class ToT_CreativeWriting:
"""
Tree of Thoughts for Creative Writing
"""
def __init__(self, api_key: str):
self.client = anthropic.Anthropic(api_key=api_key)
self.model = "claude-sonnet-4-20250514"
def generate_plans(self, sentences: List[str], k: int = 5) -> List[str]:
"""
Step 1: 여러 작성 계획 생성
"""
sentences_str = "\n".join([f"{i+1}. {s}" for i, s in enumerate(sentences)])
prompt = f"""
You need to write a coherent passage using these 4 random sentences:
{sentences_str}
Generate {k} different plans for how to connect these sentences into a story.
Each plan should briefly describe:
- The overall narrative structure
- How each sentence connects to others
- The tone and style
List {k} different plans:
"""
message = self.client.messages.create(
model=self.model,
max_tokens=1000,
temperature=0.8, # 창의성을 위해 높은 temperature
messages=[{"role": "user", "content": prompt}]
)
response = message.content[0].text.strip()
# 계획들 파싱 (단순화를 위해 전체를 하나로 취급하거나 번호로 분리)
plans = []
current_plan = []
for line in response.split('\n'):
if line.strip().startswith(('1.', '2.', '3.', '4.', '5.', 'Plan')):
if current_plan:
plans.append('\n'.join(current_plan))
current_plan = []
current_plan.append(line)
if current_plan:
plans.append('\n'.join(current_plan))
return plans[:k]
def evaluate_plan(self, sentences: List[str], plan: str) -> float:
"""
Step 2: 계획 평가
"""
sentences_str = "\n".join([f"{i+1}. {s}" for i, s in enumerate(sentences)])
prompt = f"""
Evaluate the following story plan:
Required sentences:
{sentences_str}
Plan:
{plan}
Rate this plan on coherence and creativity (1-10):
- Does it naturally connect all four sentences?
- Is the narrative structure clear?
- Is it creative and engaging?
Provide only a number (1-10):
"""
message = self.client.messages.create(
model=self.model,
max_tokens=10,
temperature=0,
messages=[{"role": "user", "content": prompt}]
)
try:
score = float(message.content[0].text.strip())
return score / 10.0 # 0~1 범위로 정규화
except:
return 0.5
def write_passage(self, sentences: List[str], plan: str) -> str:
"""
Step 3: 계획에 따라 실제 글 작성
"""
sentences_str = "\n".join([f"{i+1}. {s}" for i, s in enumerate(sentences)])
prompt = f"""
Write a coherent short passage (4 paragraphs) that incorporates ALL of these sentences:
{sentences_str}
Use this plan:
{plan}
Requirements:
- Must include all 4 sentences word-for-word
- Create smooth transitions between sentences
- Maintain a consistent tone and narrative
Write the passage:
"""
message = self.client.messages.create(
model=self.model,
max_tokens=600,
temperature=0.7,
messages=[{"role": "user", "content": prompt}]
)
return message.content[0].text.strip()
def solve(self, sentences: List[str], b: int = 3) -> str:
"""
ToT로 창작 문제 해결
"""
print(f"📝 Creative Writing with ToT")
print(f"Sentences: {sentences}\n")
# Step 1: 여러 계획 생성
print("Step 1: 계획 생성 중...")
plans = self.generate_plans(sentences, k=5)
print(f"생성된 계획: {len(plans)}개\n")
# Step 2: 계획 평가
print("Step 2: 계획 평가 중...")
evaluated_plans = []
for i, plan in enumerate(plans):
score = self.evaluate_plan(sentences, plan)
evaluated_plans.append((plan, score))
print(f"Plan {i+1}: score = {score:.2f}")
# 상위 b개 선택
evaluated_plans.sort(key=lambda x: x[1], reverse=True)
top_plans = evaluated_plans[:b]
print(f"\n선택된 계획: {len(top_plans)}개")
# Step 3: 선택된 계획들로 글 작성
print("\nStep 3: 글 작성 중...")
passages = []
for plan, score in top_plans:
passage = self.write_passage(sentences, plan)
passages.append((passage, score))
# 최고 점수의 글 반환
best_passage, best_score = passages[0]
print(f"\n최종 선택: score = {best_score:.2f}")
return best_passage
# 사용 예시
def test_creative_writing():
sentences = [
"The old lighthouse stood alone on the cliff.",
"Sarah had always been afraid of the dark.",
"The package arrived three days late.",
"In his pocket, he found a key he didn't recognize."
]
writer = ToT_CreativeWriting(api_key="your-api-key")
passage = writer.solve(sentences, b=3)
print("\n" + "="*80)
print("최종 결과:")
print("="*80)
print(passage)
if __name__ == "__main__":
test_creative_writing()6.3 결과 예시
📝 Creative Writing with ToT
Sentences: ['The old lighthouse stood alone on the cliff.', ...]
Step 1: 계획 생성 중...
생성된 계획: 5개
Step 2: 계획 평가 중...
Plan 1: score = 0.85 (Mystery/thriller structure)
Plan 2: score = 0.72 (Coming-of-age narrative)
Plan 3: score = 0.68 (Time-travel concept)
Plan 4: score = 0.55 (Random connection)
Plan 5: score = 0.61 (Surreal approach)
선택된 계획: 3개
Step 3: 글 작성 중...
최종 선택: score = 0.85
================================================================================
최종 결과:
================================================================================
The old lighthouse stood alone on the cliff, its beam cutting through
the darkness that had haunted this coast for generations. Sarah had
always been afraid of the dark, but tonight she climbed the spiral
stairs with determination, clutching the mysterious package that had
finally arrived—three days late, but perhaps right on time.
The package arrived three days late, yet its contents seemed meant for
this exact moment. Inside, wrapped in aged newspaper, was a brass key
and a faded photograph of the lighthouse keeper from 1952. In his pocket,
he found a key he didn't recognize, the note had read, describing her
grandfather's final days at this very lighthouse.
As she inserted the key into the old keeper's lockbox, Sarah understood.
Her grandfather had left this for her, knowing that one day she would
need to face her fear. The lighthouse—isolated, dark, but steady—had
been waiting to teach her that some lights shine brightest in the deepest
darkness.
With trembling hands, she lit the old lamp. For the first time since
childhood, Sarah wasn't afraid of the dark. She had become the light.6.4 Creative Writing 성능
| 방법 | Coherence Score |
|---|---|
| IO prompt | 6.2/10 |
| CoT prompt | 6.8/10 |
| ToT (b=1) | 7.5/10 |
| ToT (b=5) | 7.9/10 |
ToT는 여러 계획을 평가하고 최선의 구조를 선택함으로써 더 일관성 있는 글을 작성한다.
7 한계점 및 비용 분석
7.1 연산 비용
ToT의 가장 큰 한계는 높은 연산 비용이다.
비용 계산 (Game of 24 예시):
설정:
- Beam width (b) = 5
- 각 단계에서 생성하는 생각 (k) = 5
- 단계 수 (d) = 3
총 API 호출 횟수:
Step 1:
- 생각 생성: b × k = 5 × 5 = 25회
- 평가: 25회
- 소계: 50회
Step 2:
- 생각 생성: 5 × 5 = 25회
- 평가: 25회
- 소계: 50회
Step 3:
- 생각 생성: 5 × 5 = 25회
- 평가: 25회
- 소계: 50회
총 API 호출: 150회비용 비교:
| 방법 | API 호출 | 상대 비용 |
|---|---|---|
| IO | 1회 | 1× |
| CoT | 1회 | 1× |
| CoT-SC (k=5) | 5회 | 5× |
| ToT (b=5, k=5, d=3) | 150회 | 150× |
현실적 비용:
Claude Sonnet 4 기준 ($3/MTok input, $15/MTok output):
Game of 24 문제 1개:
- 평균 input: 200 tokens/call
- 평균 output: 50 tokens/call
- 총 150회 호출
비용 = (200 × 150 × $3 + 50 × 150 × $15) / 1,000,000
= (90,000 + 112,500) / 1,000,000
= $0.20 per problem
CoT: $0.001 per problem
→ ToT는 CoT보다 200배 비쌈7.2 시간 지연
순차적 API 호출로 인한 레이턴시:
각 API 호출: 평균 2초
총 150회 → 300초 = 5분
병렬 처리로 개선 가능하지만 제한적:
- 생각 생성: 병렬 가능 (동시에 k개)
- 평가: 병렬 가능
- 단계 간: 순차적 (피할 수 없음)
최적화된 시간: 약 20-30초
CoT: 2초
→ ToT는 10-15배 느림7.3 적용 범위의 제한
ToT가 효과적인 문제는 매우 제한적이다:
ToT가 적합한 문제: - ✅ 명확한 중간 단계가 있음 - ✅ 각 단계를 독립적으로 평가 가능 - ✅ 백트래킹이 필요함 - ✅ 최적해를 찾는 것이 중요함
ToT가 부적합한 문제: - ❌ 단순한 Q&A - ❌ 요약, 번역 등 직접적인 변환 - ❌ 개방형 창작 (평가 기준 모호) - ❌ 실시간 응답이 필요한 경우
실제 적용 가능한 분야: 1. 전략 게임 / 퍼즐: 체스, 바둑, 수학 퍼즐 2. 복잡한 문제 해결: 알고리즘 설계, 증명 3. 창작 작업: 구조화된 글쓰기 (제약 조건 있음) 4. 코드 생성: 복잡한 로직 (여러 접근 방식 비교)
7.4 GPT-4/o의 성능 향상
논문 발표 이후 GPT-4, GPT-4o, Claude 3/4 등 최신 모델들이 등장했다:
현재 상황:
Game of 24 (4, 9, 10, 13):
GPT-3.5 (2022):
- IO: 7.3%
- CoT: 4.0%
- ToT: 74%
→ ToT가 압도적으로 필요
GPT-4 (2023):
- IO: 약 40%
- CoT: 약 60%
- ToT: 약 85%
→ 여전히 ToT가 좋지만 격차 감소
Claude Sonnet 4 (2024):
- IO: 약 50-60%
- CoT: 약 70-80%
- ToT: 약 90%
→ 대부분의 경우 CoT로 충분결론: 최신 모델은 단순 CoT만으로도 많은 문제를 잘 풀기 때문에, ToT가 실제로 필요한 경우는 더욱 줄어들었다.
8 Tree-of-Thought-Prompting (단순화 버전)
ToT의 전체 프레임워크는 복잡하지만, 핵심 아이디어를 단순한 프롬프트로 구현할 수 있다. Hulbert (2023)가 제안한 방법이다.
8.1 기본 패턴
SIMPLE_TOT_PROMPT = """
Imagine three different experts are answering this question.
All experts will write down 1 step of their thinking, then share it with the group.
Then all experts will go on to the next step, etc.
If any expert realizes they're wrong at any point then they leave.
The question is: {question}
"""8.2 고급 패턴 1: 협업 전문가
COLLABORATIVE_TOT_PROMPT = """
Simulate three brilliant, logical experts collaboratively answering a question.
Each one verbosely explains their thought process in real-time, considering the
prior explanations of others and openly acknowledging mistakes.
At each step, whenever possible, each expert refines and builds upon the thoughts
of others, acknowledging their contributions.
They continue until there is a definitive answer to the question.
For clarity, your entire response should be in a markdown table.
The question is: {question}
"""8.3 고급 패턴 2: 동료 평가
PEER_REVIEW_TOT_PROMPT = """
Identify and behave as three different experts that are appropriate to answering
this question.
All experts will write down the step and their thinking about the step, then
share it with the group.
Then, all experts will go on to the next step, etc.
At each step all experts will score their peers' responses between 1 and 5,
1 meaning it is highly unlikely, and 5 meaning it is highly likely.
If any expert is judged to be wrong at any point then they leave.
After all experts have provided their analysis, you then analyze all 3 analyses
and provide either the consensus solution or your best guess solution.
The question is: {question}
"""9 다른 기법과의 비교
9.1 ToT vs CoT
| 특성 | Chain-of-Thought | Tree of Thoughts |
|---|---|---|
| 구조 | 선형 (linear) | 트리 (tree) |
| 백트래킹 | ❌ 불가능 | ✅ 가능 |
| 탐색 | 한 경로만 | 여러 경로 |
| 비용 | 낮음 (1× ) | 매우 높음 (100×+) |
| 속도 | 빠름 | 느림 |
| 적용 범위 | 넓음 | 좁음 |
| 구현 복잡도 | 낮음 | 높음 |
언제 CoT를 사용하나? - ✅ 대부분의 추론 문제 - ✅ 실시간 응답 필요 - ✅ 비용 제약
언제 ToT를 사용하나? - ✅ 전략적 계획이 필수 - ✅ 정확도가 최우선 - ✅ 비용/시간 여유
9.2 ToT vs Self-Consistency
Self-Consistency:
같은 질문 → [CoT 1] → 답변 1
→ [CoT 2] → 답변 2
→ [CoT 3] → 답변 3
...
→ [CoT N] → 답변 N
다수결 → 최종 답변ToT:
질문 → [생각 1a, 1b, 1c] → 평가 → 선택
→ [생각 2a, 2b, 2c] → 평가 → 선택
→ [생각 3a, 3b, 3c] → 평가 → 선택
→ 최종 답변| 특성 | Self-Consistency | Tree of Thoughts |
|---|---|---|
| 다양성 | 높음 (독립 샘플) | 중간 (제약된 탐색) |
| 전략 | 없음 (무작위) | 있음 (평가 기반) |
| 효율성 | 낮음 | 높음 |
| 적용 | 답이 이산적인 경우 | 복잡한 계획 필요 |
조합 가능?: 네! ToT의 마지막 단계에서 Self-Consistency 적용 가능.
9.3 ToT vs RAG
비교 자체가 의미 없음: 다른 목적의 기법
- RAG: 외부 지식 활용
- ToT: 내부 추론 개선
조합 전략:
10 실무 적용 시나리오 (현실적 평가)
10.1 코드 리팩토링
문제: 레거시 코드 리팩토링 전략 수립
평가: - 추천 가능: 여러 리팩토링 전략 비교에 유용 - 효과: 단순 CoT보다 20-30% 나은 제안 - 활용법: Step 1: 여러 리팩토링 계획 생성 Step 2: 각 계획의 장단점 평가 Step 3: 최적 계획 선택 및 상세화
10.2 창작 지원 도구
문제: 소설/시나리오 구조 설계
평가: - 추천: 여러 플롯 구조 비교에 효과적 - 강점: 창의적 대안 제시 - 주의: 평가 기준이 주관적이라 조정 필요
11 정리 및 결론
11.1 핵심 요약
Tree of Thoughts의 핵심: - 여러 추론 경로를 트리로 탐색 - 백트래킹으로 실수 복구 - 평가 기반 전략적 탐색 - CoT를 뛰어넘는 복잡한 문제 해결
현실적 평가: - 학술적 가치: 매우 높음 (추론 메커니즘 이해) - 실무 적용: 매우 제한적 - 비용: 100배+ 비쌈 - 최신 모델: 단순 CoT로 충분한 경우 많음
11.2 언제 ToT를 사용할 것인가?
사용하라: - 전략 게임, 복잡한 퍼즐 - 최적해가 절대적으로 필요한 경우 - 비용/시간이 문제되지 않는 연구/데모 - 여러 접근법을 체계적으로 비교해야 할 때
사용하지 마라: - 일반적인 Q&A - 실시간 서비스 - 비용에 민감한 프로덕션 - 최신 강력한 모델 + CoT로 충분한 경우
11.3 미래 전망
개선 방향: 1. 효율성: 불필요한 탐색 줄이기 2. 자동화: 평가 함수 자동 학습 3. 하이브리드: 다른 기법과 결합 4. 경량화: Simple ToT 스타일의 실용적 변형
장기 전망: - 모델 성능 향상으로 필요성 감소 - 특수한 도메인에서만 생존 - 아이디어는 에이전트 시스템에 통합될 가능성
12 참고문헌
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., & Narasimhan, K. (2024). Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36.
Wei, J., et al. (2022). Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35, 24824-24837.
Hulbert, D. (2023). Tree-of-thought prompting. GitHub Repository. https://github.com/dave1010/tree-of-thought-prompting
Wang, X., et al. (2022). Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171.