LangGraph实现tree-of-thought

https://github.langchain.ac.cn/langgraph/tutorials/tot/tot/#expander

image.png

根据提供的教程，LangGraph 框架通过定义一个有状态的图（StateGraph）来构建和实现 Tree of Thoughts (ToT) 算法。其核心是模拟一个“扩展-评分-剪枝”的搜索循环，具体步骤如下：

  1. 定义核心组件：

    • 任务 (Task)：教程以“24点游戏”为例，即给定4个数字，生成一个使用这些数字一次且结果为24的数学方程。
    • 扩展器 (Expander)：这是一个由大语言模型（LLM）驱动的组件。它的作用是根据当前问题（4个数字）和可选的先前候选解（作为种子），生成一批新的候选方程（k 个）。这一步对应了在“思维树”中生成新的分支节点。
    • 评分器 (Scorer)：这是一个确定性函数，用于评估每个候选方程的质量。在24点游戏中，评分规则很简单：方程必须使用所有4个数字且仅使用一次，然后根据其计算结果与24的接近程度打分（例如，score = 1 / (1 + abs(24 - result))）。这一步为树中的每个节点赋予一个价值。
    • 剪枝器 (Pruner)：根据评分结果，只保留得分最高的前 beam_size 个候选解，舍弃其余的。这一步确保搜索过程聚焦于最有希望的路径，控制了树的宽度，防止计算爆炸。

  2. 构建状态图 (StateGraph)：

    • 状态 (State)：定义图的状态 ToTState，其中最关键的是 candidates（当前待评估的候选解列表）和 scored_candidates（已评分的候选解列表）。
    • 节点 (Nodes)：将“扩展”、“评分”、“剪枝”三个步骤分别定义为图的节点。
    • 边与条件 (Edges & Conditional Edges)：
      • 连接 expand -> score -> prune，形成一个基本的处理循环。
      • 从 prune 节点引出一条条件边。该条件会检查：
        • 是否有候选解的分数达到了预设阈值（如0.9，表示找到满意解）。
        • 或者搜索深度是否超过了最大限制。
      • 如果满足终止条件，则流程结束 (__end__)。
      • 如果不满足，则为 prune 保留下来的每一个最佳候选解，向 expand 节点发送一个 Send 消息，将该候选解作为“种子”进行下一轮的扩展。这一步是构建“树”结构的关键，它使得搜索可以从多个当前最优解并行地向更深层次探索，从而形成树状的搜索路径。

  3. 运行流程：

    • 从起始节点开始，进入 expand，生成第一批候选解。
    • 进入 score，为所有候选解打分。
    • 进入 prune，保留Top-K个最佳解。
    • 检查终止条件。如果未满足，则将这K个最佳解分别作为新的起点，再次触发 expand 节点，生成下一层的候选解。这个过程不断循环，直到找到满意解或达到最大深度。

总结来说，这个教程通过 LangGraph 的状态管理和消息传递机制，将 ToT 的抽象概念（生成多个思路、评估、选择最优路径进行深入探索）转化为一个可执行的、循环的图计算流程。其中，“树”的结构是通过“剪枝后，为每个保留的节点并行发起下一轮扩展”这一机制来动态构建的。