Tree-of-Thought（思维树）
Tree-of-Thought（ToT） 是 CoT 的扩展，由 Yao et al. 和 Long et al. 于 2023 年提出。其核心思想是将推理过程组织成树状结构，每个节点代表一个思考状态，通过搜索算法（BFS/DFS）探索多条推理路径，支持回溯和剪枝。
一、核心原理
1.1 ToT 的设计哲学
ToT 解决了 CoT 的线性推理限制：
┌─────────────────────────────────────────────────────────────┐
│ CoT vs ToT 结构对比 │
├─────────────────────────────────────────────────────────────┤
│ │
│ Chain-of-Thought（线性）： │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 问题 ─→ 思考1 ─→ 思考2 ─→ 思考3 ─→ 答案 │ │
│ │ │ │
│ │ ❌ 单一路径，无法回溯 │ │
│ │ ❌ 一旦走错，全盘皆输 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ Tree-of-Thought（树状）： │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 问题 │ │
│ │ │ │ │
│ │ ┌─────────┼─────────┐ │ │
│ │ ↓ ↓ ↓ │ │
│ │ 思考1a 思考1b 思考1c │ │
│ │ │ │ │ │ │
│ │ ↓ ↓ ↓ │ │
│ │ 思考2a 思考2b 思考2c │ │
│ │ │ │ │ │
│ │ ↓ ↓ │ │
│ │ 思考3a 思考3b │ │
│ │ │ │ │ │
│ │ ↓ ↓ │ │
│ │ 答案A 答案B │ │
│ │ │ │
│ │ ✅ 多路径探索，支持回溯 │ │
│ │ ✅ 剪枝优化，资源可控 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘1.2 ToT 核心组件
| 组件 | 作用 | 说明 |
|---|---|---|
| Thought Generation | 生成候选思考 | 为当前状态生成多个可能的下一步思考 |
| State Evaluation | 状态评估 | 评估当前思考状态的价值/可行性 |
| Search Algorithm | 搜索算法 | BFS（广度优先）或 DFS（深度优先） |
| Backtracking | 回溯机制 | 遇到死路时回退到上一状态 |
1.3 搜索策略对比
┌─────────────────────────────────────────────────────────────┐
│ BFS vs DFS 搜索策略 │
├─────────────────────────────────────────────────────────────┤
│ │
│ BFS（广度优先搜索）： │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 问题 │ │
│ │ │ │ │
│ │ ┌─────────┼─────────┐ │ │
│ │ ↓ ↓ ↓ ← 第 1 层 │ │
│ │ 思考1a 思考1b 思考1c │ │
│ │ │ │ │ │ │
│ │ ↓ ↓ ↓ ← 第 2 层 │ │
│ │ 思考2a 思考2b 思考2c │ │
│ │ │ │
│ │ 特点：逐层探索，保证找到最短路径 │ │
│ │ 适用：需要全局最优解 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ DFS（深度优先搜索）： │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 问题 │ │
│ │ │ │ │
│ │ ↓ │ │
│ │ 思考1a │ │
│ │ │ │ │
│ │ ↓ │ │
│ │ 思考2a ──→ 评估：差，回溯 │ │
│ │ ↑ │ │
│ │ 思考1b ← 回退 │ │
│ │ │ │ │
│ │ ↓ │ │
│ │ 思考2b │ │
│ │ │ │ │
│ │ ↓ │ │
│ │ 答案 │ │
│ │ │ │
│ │ 特点：深入探索，快速找到可行解 │ │
│ │ 适用：需要快速找到解，深度可控 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘二、工作流程
2.1 完整工作流程图
┌─────────────────────────────────────────────────────────────────────┐
│ ToT 完整工作流程 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────┐ │
│ │ 用户输入 │ │
│ │ (Query) │ │
│ └──────┬──────┘ │
│ │ │
│ ↓ │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ 初始化搜索树 │ │
│ │ root_state = {thought: None, children: [], depth: 0} │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │ │
│ ↓ │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ ToT 搜索循环 │ │
│ │ │ │
│ │ while not search_complete: │ │
│ │ │ │
│ │ ┌─────────────────────────────────────────────────┐ │ │
│ │ │ 1. 选择待扩展状态 │ │ │
│ │ │ current = select_state(frontier) │ │ │
│ │ └─────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ↓ │ │
│ │ ┌─────────────────────────────────────────────────┐ │ │
│ │ │ 2. 生成候选思考 │ │ │
│ │ │ thoughts = generate_thoughts(current, k) │ │ │
│ │ │ // k = 每次生成的候选数量 │ │ │
│ │ └─────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ↓ │ │
│ │ ┌─────────────────────────────────────────────────┐ │ │
│ │ │ 3. 评估每个候选 │ │ │
│ │ │ for thought in thoughts: │ │ │
│ │ │ score = evaluate(thought) │ │ │
│ │ │ if score < threshold: │ │ │
│ │ │ prune(thought) // 剪枝 │ │ │
│ │ └─────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ↓ │ │
│ │ ┌─────────────────────────────────────────────────┐ │ │
│ │ │ 4. 更新搜索树 │ │ │
│ │ │ add_children(current, valid_thoughts) │ │ │
│ │ └─────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ↓ │ │
│ │ ┌─────────────────────────────────────────────────┐ │ │
│ │ │ 5. 检查终止条件 │ │ │
│ │ │ - 找到目标状态？ │ │ │
│ │ │ - 达到最大深度？ │ │ │
│ │ │ - 资源耗尽？ │ │ │
│ │ └─────────────────────────────────────────────────┘ │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │ │
│ ↓ │
│ ┌─────────────────────┐ │
│ │ 返回最优解 │ │
│ │ (Best Solution) │ │
│ └─────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────┘2.2 关键步骤详解
| 步骤 | 输入 | 处理 | 输出 |
|---|---|---|---|
| 1. 状态选择 | 搜索边界（frontier） | 根据策略选择下一个要扩展的状态 | 当前状态 |
| 2. 思考生成 | 当前状态 + 问题 | LLM 生成 k 个候选思考 | 候选思考列表 |
| 3. 状态评估 | 候选思考 | LLM 评估每个思考的价值 | 评分列表 |
| 4. 剪枝 | 候选 + 评分 | 移除低分候选 | 有效候选列表 |
| 5. 树更新 | 当前状态 + 有效候选 | 将候选添加为子节点 | 更新后的树 |
三、代码实现
3.1 基础 ToT 实现
"""
Tree-of-Thought 基础实现
支持 BFS 和 DFS 两种搜索策略
"""
from typing import List, Optional, Callable
from dataclasses import dataclass, field
from enum import Enum
import heapq
from langchain_openai import ChatOpenAI
class SearchStrategy(Enum):
"""搜索策略"""
BFS = "bfs" # 广度优先
DFS = "dfs" # 深度优先
BEST_FIRST = "best_first" # 最佳优先
@dataclass
class ThoughtNode:
"""思维树节点"""
thought: str # 当前思考内容
depth: int # 深度
score: float = 0.0 # 评分
parent: Optional['ThoughtNode'] = None
children: List['ThoughtNode'] = field(default_factory=list)
is_solution: bool = False # 是否是解
solution: Optional[str] = None # 解的内容
def path(self) -> List[str]:
"""获取从根到当前节点的路径"""
if self.parent is None:
return [self.thought] if self.thought else []
return self.parent.path() + [self.thought]
def __lt__(self, other):
"""用于优先队列比较"""
return self.score > other.score # 分数高的优先
class TreeOfThought:
"""
Tree-of-Thought 推理器
支持 BFS、DFS 和 Best-First 搜索
"""
THOUGHT_GENERATION_PROMPT = """
你正在解决以下问题：
{problem}
当前推理路径：
{current_path}
请生成 {k} 个不同的下一步思考。每个思考应该是：
1. 有意义的推理步骤
2. 有助于解决问题
3. 与之前路径不同
请按以下格式输出：
思考1: ...
思考2: ...
思考3: ...
"""
EVALUATION_PROMPT = """
你正在评估一个推理步骤的有效性。
问题：{problem}
当前路径：{path}
待评估思考：{thought}
请评估这个思考对解决问题的贡献程度。
评分标准：
- 1分：错误或无意义的思考
- 2分：部分正确但有缺陷
- 3分：正确但进展有限
- 4分：很有帮助的思考
- 5分：关键性的突破
只输出一个数字（1-5）：
"""
SOLUTION_CHECK_PROMPT = """
基于以下推理路径，问题是否已经解决？
问题：{problem}
推理路径：{path}
如果问题已解决，请给出最终答案。
如果问题未解决，请回答"继续推理"。
输出格式：
状态：已解决/继续推理
答案：（如果已解决）
"""
def __init__(
self,
model_name: str = "gpt-4",
strategy: SearchStrategy = SearchStrategy.BFS,
max_depth: int = 5,
num_thoughts: int = 3,
beam_width: int = 3,
score_threshold: float = 2.0
):
"""
初始化 ToT 推理器
Args:
model_name: 模型名称
strategy: 搜索策略
max_depth: 最大深度
num_thoughts: 每次生成的候选思考数量
beam_width: Beam 宽度（保留的候选数量）
score_threshold: 剪枝阈值
"""
self.llm = ChatOpenAI(model=model_name, temperature=0.7)
self.strategy = strategy
self.max_depth = max_depth
self.num_thoughts = num_thoughts
self.beam_width = beam_width
self.score_threshold = score_threshold
def generate_thoughts(self, problem: str, current_path: List[str]) -> List[str]:
"""生成候选思考"""
prompt = self.THOUGHT_GENERATION_PROMPT.format(
problem=problem,
current_path="\n".join(current_path) if current_path else "（开始）",
k=self.num_thoughts
)
response = self.llm.invoke(prompt)
# 解析输出
thoughts = []
for line in response.content.split('\n'):
if line.strip().startswith('思考'):
# 提取思考内容
parts = line.split(':', 1)
if len(parts) > 1:
thoughts.append(parts[1].strip())
return thoughts[:self.num_thoughts]
def evaluate_thought(self, problem: str, path: List[str], thought: str) -> float:
"""评估思考"""
prompt = self.EVALUATION_PROMPT.format(
problem=problem,
path="\n".join(path),
thought=thought
)
response = self.llm.invoke(prompt)
# 解析评分
try:
score = float(response.content.strip())
return max(1, min(5, score)) # 限制在 1-5 范围
except:
return 3.0 # 默认中等评分
def check_solution(self, problem: str, path: List[str]) -> tuple[bool, Optional[str]]:
"""检查是否找到解"""
prompt = self.SOLUTION_CHECK_PROMPT.format(
problem=problem,
path="\n".join(path)
)
response = self.llm.invoke(prompt)
content = response.content
if "已解决" in content:
# 提取答案
for line in content.split('\n'):
if '答案' in line:
answer = line.split(':', 1)[1].strip() if ':' in line else line
return True, answer
return True, content
return False, None
def solve(self, problem: str) -> dict:
"""
使用 ToT 解决问题
Args:
problem: 问题文本
Returns:
包含解题过程的字典
"""
# 初始化根节点
root = ThoughtNode(thought="", depth=0, score=5.0)
# 根据策略选择数据结构
if self.strategy == SearchStrategy.BFS:
frontier = [root] # 队列
elif self.strategy == SearchStrategy.DFS:
frontier = [root] # 栈
else: # BEST_FIRST
frontier = [] # 优先队列
heapq.heappush(frontier, root)
visited_states = set()
best_solution = None
best_score = 0
while frontier:
# 选择下一个状态
if self.strategy == SearchStrategy.BFS:
current = frontier.pop(0)
elif self.strategy == SearchStrategy.DFS:
current = frontier.pop()
else:
current = heapq.heappop(frontier)
# 检查深度限制
if current.depth >= self.max_depth:
continue
# 获取当前路径
path = current.path()
# 检查是否已找到解
is_solved, solution = self.check_solution(problem, path)
if is_solved:
current.is_solution = True
current.solution = solution
if current.score > best_score:
best_solution = current
continue
# 生成候选思考
thoughts = self.generate_thoughts(problem, path)
# 评估并筛选
candidates = []
for thought in thoughts:
score = self.evaluate_thought(problem, path, thought)
if score >= self.score_threshold:
node = ThoughtNode(
thought=thought,
depth=current.depth + 1,
score=score,
parent=current
)
candidates.append(node)
# 按 Beam 宽度保留
candidates.sort(key=lambda x: x.score, reverse=True)
candidates = candidates[:self.beam_width]
# 添加到树和边界
for node in candidates:
current.children.append(node)
if self.strategy == SearchStrategy.BEST_FIRST:
heapq.heappush(frontier, node)
else:
frontier.append(node)
return {
"problem": problem,
"strategy": self.strategy.value,
"solution": best_solution.solution if best_solution else None,
"path": best_solution.path() if best_solution else None,
"tree": self._tree_to_dict(root)
}
def _tree_to_dict(self, node: ThoughtNode) -> dict:
"""将树转换为字典格式"""
return {
"thought": node.thought,
"depth": node.depth,
"score": node.score,
"is_solution": node.is_solution,
"children": [self._tree_to_dict(c) for c in node.children]
}
# 使用示例
if __name__ == "__main__":
# BFS 策略
tot_bfs = TreeOfThought(
strategy=SearchStrategy.BFS,
max_depth=4,
num_thoughts=3,
beam_width=2
)
result = tot_bfs.solve(
"用 24 根火柴棍摆成 9 个正方形，如何实现？"
)
print(f"问题：{result['problem']}")
print(f"策略：{result['strategy']}")
print(f"解答路径：")
for i, thought in enumerate(result['path'], 1):
print(f" {i}. {thought}")
print(f"最终答案：{result['solution']}")3.2 使用 LangChain 实现
"""
使用 LangChain 实现 ToT
"""
from langchain.chains import LLMChain
from langchain.prompts import PromptTemplate
from langchain_openai import ChatOpenAI
from typing import List, Optional
from pydantic import BaseModel
class ThoughtEvaluation(BaseModel):
"""思考评估结果"""
thought: str
score: float
reasoning: str
class LangChainToT:
"""基于 LangChain 的 ToT 实现"""
def __init__(self, model_name: str = "gpt-4"):
self.llm = ChatOpenAI(model=model_name, temperature=0)
self._setup_chains()
def _setup_chains(self):
"""设置推理链"""
# 思考生成链
thought_prompt = PromptTemplate(
input_variables=["problem", "history", "n"],
template="""
问题：{problem}
已进行的思考：
{history}
请生成 {n} 个可能的下一步思考。
每个思考应该是独立的、有意义的推理步骤。
格式：
1. [思考内容]
2. [思考内容]
...
"""
)
self.thought_chain = LLMChain(llm=self.llm, prompt=thought_prompt)
# 评估链
eval_prompt = PromptTemplate(
input_variables=["problem", "thought", "history"],
template="""
问题：{problem}
已进行的思考：
{history}
待评估思考：{thought}
请评估这个思考对解决问题的价值（1-10分）。
只输出一个数字。
"""
)
self.eval_chain = LLMChain(llm=self.llm, prompt=eval_prompt)
# 最终答案链
answer_prompt = PromptTemplate(
input_variables=["problem", "reasoning"],
template="""
问题：{problem}
推理过程：
{reasoning}
请根据以上推理给出最终答案。
"""
)
self.answer_chain = LLMChain(llm=self.llm, prompt=answer_prompt)
def solve(self, problem: str, max_depth: int = 5) -> dict:
"""解决问题"""
thoughts = []
for depth in range(max_depth):
# 生成候选
history = "\n".join(thoughts) if thoughts else "开始推理"
candidates_text = self.thought_chain.run(
problem=problem,
history=history,
n=3
)
# 解析候选
candidates = []
for line in candidates_text.split('\n'):
line = line.strip()
if line and line[0].isdigit():
thought = line.split('.', 1)[1].strip() if '.' in line else line
candidates.append(thought)
if not candidates:
break
# 评估候选
best_thought = None
best_score = 0
for thought in candidates:
score_text = self.eval_chain.run(
problem=problem,
thought=thought,
history=history
)
try:
score = float(score_text.strip())
except:
score = 5
if score > best_score:
best_score = score
best_thought = thought
if best_thought:
thoughts.append(best_thought)
# 生成答案
reasoning = "\n".join(thoughts)
answer = self.answer_chain.run(problem=problem, reasoning=reasoning)
return {
"problem": problem,
"thoughts": thoughts,
"answer": answer
}四、适用场景
4.1 最佳适用场景
| 场景类型 | 具体示例 | ToT 优势 |
|---|---|---|
| 复杂决策 | 多方案比选、策略制定 | 多路径探索，找到最优解 |
| 创意写作 | 故事创作、文案设计 | 支持发散思维和回溯 |
| 数学证明 | 复杂几何证明 | 分步推理，验证每步正确性 |
| 游戏博弈 | 棋类游戏、解谜 | 状态搜索，前瞻评估 |
4.2 场景详解
┌─────────────────────────────────────────────────────────────┐
│ ToT 典型应用场景 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. 创意写作场景 │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ 任务：为一个科幻故事设计三种不同的结局 │ │
│ │ │ │
│ │ 故事开头 │ │
│ │ │ │ │
│ │ ┌─────────────┼─────────────┐ │ │
│ │ ↓ ↓ ↓ │ │
│ │ 结局A： 结局B： 结局C： │ │
│ │ 悲剧收场 皆大欢喜 开放结局 │ │
│ │ │ │ │ │ │
│ │ ↓ ↓ ↓ │ │
│ │ 详细展开 详细展开 详细展开 │ │
│ │ │ │
│ │ ✅ 可以同时探索多个创意方向 │ │
│ │ ✅ 不满意可以回溯重写 │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ 2. 数学证明场景 │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ 问题：证明三角形内角和为 180° │ │
│ │ │ │
│ │ 已知三角形ABC │ │
│ │ │ │ │
│ │ ┌─────────────┼─────────────┐ │ │
│ │ ↓ ↓ ↓ │ │
│ │ 方法1： 方法2： 方法3： │ │
│ │ 作辅助线 坐标法 向量法 │ │
│ │ │ │ │ │ │
│ │ ↓ ↓ ↓ │ │
│ │ 过A作BC 建立坐标 向量计算 │ │
│ │ 平行线 系计算角度 证明结论 │ │
│ │ │ │ │ │
│ │ ↓ ↓ │ │
│ │ 利用平行 角度计算 │ │
│ │ 线性质 出结论 │ │
│ │ │ │ │
│ │ ↓ │ │
│ │ 证明完成 │ │
│ │ │ │
│ │ ✅ 尝试多种证明方法 │ │
│ │ ✅ 一种方法失败可尝试其他方法 │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘4.3 与 CoT 的适用场景对比
| 场景 | CoT | ToT | 推荐 |
|---|---|---|---|
| 简单计算 | ✅ 足够 | ❌ 过度设计 | CoT |
| 多步推理 | ✅ 足够 | ⚠️ 可选 | CoT |
| 需要回溯 | ❌ 不支持 | ✅ 支持 | ToT |
| 创意探索 | ❌ 单路径 | ✅ 多路径 | ToT |
| 决策分析 | ⚠️ 局限 | ✅ 适合 | ToT |
五、搜索策略详解
5.1 BFS（广度优先搜索）
┌─────────────────────────────────────────────────────────────┐
│ BFS 搜索过程 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 优点： │
│ • 保证找到最短路径 │
│ • 全局视角，不会错过浅层解 │
│ │
│ 缺点： │
│ • 内存消耗大（需存储整层节点） │
│ • 可能浪费时间探索无效分支 │
│ │
│ 适用场景： │
│ • 需要最短推理路径 │
│ • 解可能在较浅层 │
│ • 内存资源充足 │
│ │
│ 示例：24点游戏 │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ 第1层：尝试4个数字作为第一个操作数 │ │
│ │ 第2层：对每个操作数，尝试3种运算 │ │
│ │ 第3层：尝试第二个操作数... │ │
│ │ 逐层搜索直到找到解 │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘5.2 DFS（深度优先搜索）
┌─────────────────────────────────────────────────────────────┐
│ DFS 搜索过程 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 优点： │
│ • 内存消耗小（只存储当前路径） │
│ • 快速深入，可能快速找到解 │
│ │
│ 缺点： │
│ • 可能陷入深层无效分支 │
│ • 不保证最短路径 │
│ │
│ 适用场景： │
│ • 解可能在深层 │
│ • 需要快速找到可行解 │
│ • 内存资源有限 │
│ │
│ 示例：数独求解 │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ 选择一个空格 → 尝试填入1 → 继续 → 遇到冲突？ │ │
│ │ ↓ │ │
│ │ 回溯 │ │
│ │ ↓ │ │
│ │ 尝试填入2 → 继续... │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘5.3 Best-First Search（最佳优先）
┌─────────────────────────────────────────────────────────────┐
│ Best-First 搜索 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 核心思想：优先扩展评估分数最高的节点 │
│ │
│ 实现：使用优先队列（堆） │
│ │
│ 优点： │
│ • 结合了 BFS 和 DFS 的优点 │
│ • 更快找到高质量解 │
│ │
│ 缺点： │
│ • 依赖评估函数的准确性 │
│ • 评估函数可能有误 │
│ │
│ 评估函数示例： │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ score = 距离目标的相似度 + 路径质量 │ │
│ │ │ │
│ │ 例如对于创意写作： │ │
│ │ score = 情节连贯性(1-5) + 创意程度(1-5) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘六、ToT 的优化策略
6.1 剪枝策略
| 策略 | 描述 | 效果 |
|---|---|---|
| 分数剪枝 | 移除评分低于阈值的节点 | 减少无效探索 |
| 重复检测 | 跳过已访问的相同状态 | 避免重复计算 |
| 深度限制 | 设置最大深度 | 控制资源消耗 |
| Beam 搜索 | 每层只保留 top-k 节点 | 平衡效果与效率 |
6.2 评估优化
# 评估策略优化
class ImprovedToT(TreeOfThought):
"""改进版 ToT"""
def __init__(self, *args, **kwargs):
super().__init__(*args, **kwargs)
self.evaluation_cache = {} # 缓存评估结果
def evaluate_thought_with_cache(self, problem: str, path: List[str], thought: str) -> float:
"""带缓存的评估"""
cache_key = f"{problem}|{'|'.join(path)}|{thought}"
if cache_key in self.evaluation_cache:
return self.evaluation_cache[cache_key]
score = self.evaluate_thought(problem, path, thought)
self.evaluation_cache[cache_key] = score
return score
def evaluate_batch(self, problem: str, path: List[str], thoughts: List[str]) -> List[float]:
"""批量评估，减少 API 调用"""
prompt = f"""
问题：{problem}
当前路径：{' → '.join(path) if path else '开始'}
请评估以下每个思考的价值（1-5分）：
{chr(10).join(f'{i+1}. {t}' for i, t in enumerate(thoughts))}
请按以下格式输出：
1: 分数
2: 分数
...
"""
response = self.llm.invoke(prompt)
# 解析批量评分
scores = []
for line in response.content.split('\n'):
if ':' in line:
try:
score = float(line.split(':')[1].strip())
scores.append(max(1, min(5, score)))
except:
scores.append(3.0)
# 确保返回数量正确
while len(scores) < len(thoughts):
scores.append(3.0)
return scores[:len(thoughts)]七、面试高频问题
Q1: ToT 与 CoT 的核心区别是什么？
答案要点：
- 结构：CoT 是线性链，ToT 是树结构
- 回溯：CoT 不支持回溯，ToT 支持
- 路径：CoT 单一路径，ToT 多路径探索
- 适用场景：简单推理用 CoT，复杂决策用 ToT
Q2: BFS 和 DFS 如何选择？
答案要点：
- BFS：需要最短路径、解在浅层、内存充足
- DFS：需要快速找到解、解可能在深层、内存有限
- Best-First：有好的评估函数、需要高质量解
Q3: ToT 的主要开销在哪里？如何优化？
答案要点：
-
开销：
- 每个节点需要多次 LLM 调用（生成+评估）
- 树结构导致节点数量指数增长
-
优化：
- 剪枝：移除低分节点
- Beam 搜索：每层保留有限节点
- 缓存：避免重复评估
- 批量评估：减少 API 调用次数
Q4: ToT 适用于哪些场景？
答案要点：
- 需要探索多种可能方案的问题
- 初始方向不确定的问题
- 需要回溯修正的推理过程
- 创意性任务（写作、设计）
Q5: ToT 的评估函数如何设计？
答案要点：
- 可以使用 LLM 自身进行评估
- 评估维度：正确性、进展程度、创新性
- 可以结合外部验证器
- 评估可以分粗评和细评两个阶段
八、小结
| 概念 | 一句话总结 | 面试关键词 |
|---|---|---|
| ToT | 树状推理，支持多路径探索和回溯 | 思维树、搜索算法 |
| BFS | 广度优先，保证最短路径 | 逐层探索、内存消耗大 |
| DFS | 深度优先，快速深入 | 回溯、内存消耗小 |
| 剪枝 | 移除无效节点，提升效率 | Beam 搜索、分数阈值 |
一句话总结：ToT 将推理组织成树结构，通过搜索算法探索多条路径，解决了 CoT 无法回溯的问题，适合复杂决策和创意探索。
最后更新：2026年3月19日