4. 源码分析¶

本章用 DeepWiki 风格组织。所有代码引用形如 file.py:Lx-Ly 可点回 GitHub 指定 commit。

本章使用的 commit：8050e67d（截至 2026 年 5 月）。

4.1 项目结构¶

tree-of-thought-llm/
├── run.py                          # CLI 入口
├── setup.py                        # pip install -e .
├── src/tot/
│   ├── models.py                   # GPT-4 API 封装 (gpt() + gpt_usage())
│   ├── methods/
│   │   └── bfs.py                  # BFS 求解器 + naive_solve (IO/CoT)
│   │                               # ⚠️ 没有 dfs.py！见 4.5
│   ├── tasks/
│   │   ├── base.py                 # Task 基类
│   │   ├── game24.py               # Game24Task
│   │   ├── text.py                 # Creative Writing
│   │   └── crosswords.py           # MiniCrosswordsEnv + MiniCrosswordsTask
│   └── prompts/
│       ├── game24.py               # 5 个 prompt (standard, cot, propose, value, value_last_step)
│       ├── text.py
│       └── crosswords.py
└── scripts/                        # 跑实验的 bash + ipynb
    ├── game24/
    ├── text/
    └── crosswords/
        └── search_crosswords-dfs.ipynb   # ⚠️ DFS 实现在这里，不在 src/

4.2 架构总览¶

ToT 的整个系统可以画成一张"4 个钩子 + 1 个求解器"图：

graph TB
    USER[user CLI args] --> RUN[run.py: run]
    RUN -->|task=game24| TASK[Game24Task]
    RUN -->|method| SOLVE[bfs.solve]

    SOLVE -.->|generate| GEN{method_generate}
    GEN -->|sample| SAMPLES[get_samples]
    GEN -->|propose| PROPOSE[get_proposals]
    SAMPLES --> TASK
    PROPOSE --> TASK

    SOLVE -.->|evaluate| EVAL{method_evaluate}
    EVAL -->|value| VALUE[get_values]
    EVAL -->|vote| VOTE[get_votes]
    VALUE --> TASK
    VOTE --> TASK

    SOLVE -.->|select| SEL{method_select}
    SEL -->|greedy| GR[top-b by value]
    SEL -->|sample| SP[softmax sample]

    TASK -->|propose_prompt_wrap| GPT[gpt: OpenAI API]
    TASK -->|value_prompt_wrap| GPT

    style SOLVE fill:#bef
    style TASK fill:#fec
    style GPT fill:#fcc

关键观察：Task 是"配置盒"——它定义了 prompt、解析函数、value 映射；solve 是"调度器"——它根据 args 决定调哪个 generator/evaluator/selector 钩子。两者用 task 对象作为接口契约。

4.3 核心子系统¶

4.3.1 求解器 · bfs.solve()¶

solve() 是 ToT 的核心循环，实现了论文 Algorithm 1（methods/bfs.py:49-88）。

算法骨架¶

# 来自 methods/bfs.py:49-88
def solve(args, task, idx, to_print=True):
    gpt = partial(gpt, model=args.backend, temperature=args.temperature)
    x = task.get_input(idx)
    ys = ['']  # 当前 beam，初始为空字符串

    for step in range(task.steps):
        # ① 生成：扩展每个 y 的候选
        if args.method_generate == 'sample':
            new_ys = [get_samples(task, x, y, args.n_generate_sample, ...) for y in ys]
        elif args.method_generate == 'propose':
            new_ys = [get_proposals(task, x, y) for y in ys]
        new_ys = list(itertools.chain(*new_ys))  # flatten

        # ② 评估：value 或 vote
        if args.method_evaluate == 'vote':
            values = get_votes(task, x, new_ys, args.n_evaluate_sample)
        elif args.method_evaluate == 'value':
            values = get_values(task, x, new_ys, args.n_evaluate_sample)

        # ③ 选择：保留 b 个
        if args.method_select == 'greedy':
            select_ids = sorted(ids, key=lambda x: values[x], reverse=True)[:args.n_select_sample]
        elif args.method_select == 'sample':
            ps = np.array(values) / sum(values)
            select_ids = np.random.choice(ids, size=args.n_select_sample, p=ps).tolist()

        ys = [new_ys[i] for i in select_ids]

    return ys, infos

API 表¶

数据流¶

sequenceDiagram
    participant U as User
    participant R as run.py
    participant S as bfs.solve
    participant T as Task
    participant G as gpt API

    U->>R: --task game24 --method_generate propose --method_evaluate value
    R->>S: solve(args, task, idx)
    loop for step in task.steps (3 for Game24)
        S->>T: propose_prompt_wrap(x, y) for each y in ys
        T-->>S: prompt
        S->>G: gpt(prompt, n=1)
        G-->>S: candidate thoughts
        S->>T: value_prompt_wrap(x, y) for each new_y
        T-->>S: value_prompt
        S->>G: gpt(value_prompt, n=3)
        G-->>S: value outputs (sure/likely/impossible)
        S->>T: value_outputs_unwrap → numeric
        T-->>S: scores
        S->>S: greedy top-b
    end
    S-->>R: final outputs

4.3.2 任务实现 · Game24Task¶

Game24Task 是任务的具体配置盒（tasks/game24.py:14-92）。

关键字段¶

# 来自 tasks/game24.py:27-36
def __init__(self, file='24.csv'):
    super().__init__()
    path = os.path.join(DATA_PATH, '24', file)
    self.data = list(pd.read_csv(path)['Puzzles'])
    self.value_cache = {}                # 评估器结果缓存
    self.steps = 4                       # ⚠️ 论文说 3 步，代码是 4
    self.stops = ['\n'] * 4

⚠️ 论文 vs 代码差异 #1：论文 Section 4.1 说 Game of 24 用 3 步思维，但代码 self.steps = 4。多出来的第 4 步是"输出最终 answer 字符串"——形式上是 thought，但实质是 finalize。论文里没解释这个细节。

状态评估的"魔法常数"¶

最值得注意的代码片段：

# 来自 tasks/game24.py:85-92
@staticmethod
def value_outputs_unwrap(x: str, y: str, value_outputs: list) -> float:
    if len(y.strip().split('\n')) == 4 and 'answer' not in y.lower():
        return 0
    value_names = [_.split('\n')[-1] for _ in value_outputs]
    value_map = {'impossible': 0.001, 'likely': 1, 'sure': 20}  # TODO: ad hoc
    value = sum(value * value_names.count(name) for name, value in value_map.items())
    return value

这 4 行代码决定了 ToT 在 Game of 24 上 74% 的成绩。三个数字：

代码注释直白写着 # TODO: ad hoc——作者自己也承认这是工程拍脑袋。

💡 个人见解（关键）：

观察：这个 {0.001, 1, 20} 映射决定了 BFS 的选择倾向——只要有一个"sure"分支，BFS 会完全无视所有"likely"分支（因为 20 > 5 × 1，beam_size=5 时即使 5 个 likely 加起来也敌不过 1 个 sure）。

判断：如果你把它改成 {0, 0.5, 1}，会得到完全不同的搜索行为——LLM 评估器的"sure"很少出现（只有真的能直接算出 24 时），所以 ToT 会更多探索 "likely" 分支。预期成绩会从 74% 跌到 50% 左右。

延伸：要复现 ToT 的 74%，你必须复制这个 value_map。这不是论文写的。这是开源 LLM 推理论文最常见的"代码-论文鸿沟"。

API 表¶

4.3.3 Prompt 工程 · prompts/game24.py¶

5 个 prompt 是 ToT 在 Game24 上最依赖的"知识"：

Value Prompt 内的 "lookahead simulation"¶

# 来自 prompts/game24.py:84-88
5 7 8
5 + 7 + 8 = 12 + 8 = 20
(8 - 5) * 7 = 3 * 7 = 21
I cannot obtain 24 now, but numbers are within a reasonable range
likely

关键技巧：value prompt 的 demonstrations 不只是"输入 → 标签"，而是让 LLM 先试几种运算再下判断。这把lookahead search 编码在 prompt 里而不是搜索算法里。是 ToT 论文里没充分强调但实际很关键的设计。

💡 个人见解：

观察：value prompt 用了 8-shot demonstrations，每个示例都包含"尝试 2-3 种运算"的过程。这相当于让 LLM 每次评估都在 prompt 内部跑一遍 lookahead。

判断：这意味着 ToT 实际上是"两层 lookahead"——外层 BFS（深度 3） + 内层 prompt-encoded lookahead（每次评估 2-3 步预演）。论文公平地说，把 "lookahead 嵌入 prompt 中" 这个设计藏在了 prompt 里，没在算法描述里强调。

延伸：在新任务上想用 ToT，复制 value prompt 的 lookahead demonstrations 风格 比照抄 algorithm 更重要。

4.4 端到端关键流程：Game of 24 一次推理¶

下面追一次完整调用（./scripts/game24/bfs.sh）：

sequenceDiagram
    participant CLI as $ python run.py
    participant R as run.py:9-39
    participant T as Game24Task
    participant S as bfs.solve
    participant G as gpt() / OpenAI

    CLI->>R: --task game24 --method_generate propose
--method_evaluate value --n_select_sample 5
    R->>T: get_task('game24')
    R->>S: solve(args, task, idx=901)

    Note over S: step=0, ys=['']
    S->>T: propose_prompt_wrap('4 9 10 13', '')
    T-->>S: prompt with "Input: 4 9 10 13\nPossible next steps:"
    S->>G: gpt(prompt, n=1)
    G-->>S: "13-9=4 (left: 4 4 10)\n10-4=6 (left: 4 6 9)\n9-4=5 (left: 5 10 13)\n..."
    S->>S: split lines → 8 candidates

    Note over S: 评估每个
    S->>T: value_prompt_wrap('4 9 10 13', '13-9=4 (left: 4 4 10)\n')
    T-->>S: prompt with "4 4 10\n4 + 4 + 10 = ...\n..."
    S->>G: gpt(prompt, n=3) ⨯ 8 candidates
    G-->>S: ['sure', 'likely', 'sure'] × 8
    S->>T: value_outputs_unwrap → [20+1+20=41, 20+0.001+1=21, ...]

    Note over S: greedy top-5
    S->>S: ys = top 5 by value

    Note over S: step=1, 2, 3 重复

    S-->>R: ys = ['(13-9)*(10-4)=24\n']
    R->>T: test_output(901, ys[0])
    T->>T: sympy.simplify("(13-9)*(10-4)") == 24
    T-->>R: {'r': 1}
    R-->>CLI: success

LLM 调用次数估算（Game24, \(b=5\), 3 步）：

• Step 0: 1 propose + 8 × 3 value = 25 calls
• Step 1: 5 propose + ~40 × 3 value = 125 calls
• Step 2: 5 propose + ~40 × 3 value = 125 calls
• Step 3: 5 propose + 5 × 3 value_last = 20 calls
• 总计约 300 GPT-4 calls / 题 → ~70k tokens（与论文附录 B.3 一致）

4.5 论文 vs 代码差异表（重磅）¶

💡 个人见解（重磅）：

观察：仓库里只有 BFS 是清洁实现——methods/bfs.py 96 行，可单独 import 复用；DFS 整个躺在一个 notebook 里。

判断：这暗示了 ToT 框架被实际工程化的"完成度"远不如论文给的印象。Game of 24 这条线很完整，Crosswords 这条线是研究代码（一次性 notebook）。如果你想把 ToT 套到你自己的"深而窄"任务上（如多跳问答、定理证明），你要重写 DFS 而不是直接复用。

延伸：这也解释了为什么后续工作（LATS、RAP）在框架的"工程一致性"上做了大改造——把 BFS/DFS/MCTS 都做成同一个抽象。ToT 是概念上的先驱，不是工程上的完整框架。

4.6 小结¶

• bfs.py:solve() 是 ToT 的算法核心，96 行实现 BFS + 3 个钩子（generate / evaluate / select）
• Game24Task 通过定义 5 个 prompt + 一个 value_map 完整配置了 Game of 24 行为
• value_map = {impossible: 0.001, likely: 1, sure: 20} 是论文未提的关键工程细节
• DFS 只在 notebook 中，不在主代码包结构里——这是 ToT 论文复现失败的最大坑
• value prompt 内嵌的 "lookahead simulation" 是另一个论文低估的设计

下一章 → 见解与扩展