--- title: CoT 与推理搜索：显式推理链的数学体系 draft: false tags: - Chain-of-Thought - Self-Consistency - Tree-of-Thoughts - 推理 - 大语言模型 --- # CoT 与推理搜索：显式推理链的数学体系 --- ## 一、为什么需要显式推理 ### 1.1 标准语言模型的局限 **标准语言模型的目标**： 给定输入 $x$，直接预测输出 $y$： $$P(y | x; \theta) = \prod_{t=1}^T P(y_t | x, y_{ 如果要求模型显式地写出中间步骤 $z_1, z_2, \ldots, z_k$，然后基于这些步骤得到最终答案 $y$，推理难度被分散到多个更简单的子任务。 **数学表示**： 设原始问题为 $x$，目标是 $y$，中间推理链为 $z_1, \ldots, z_k$。 原问题：$P(y | x; \theta)$ 改为条件分解： $$P(y | x; \theta) = \sum_{z_1, \ldots, z_k} P(y | x, z_{1:k}; \theta) \cdot \prod_{i=1}^k P(z_i | x, z_{1:i-1}; \theta) \tag{1.2}$$ 通过引入中间变量，模型可以： 1. 每个 $P(z_i | \cdot)$ 只负责当前一步推理 2. 每个子任务比完整任务更简单 3. 最终答案由清晰的推理链支撑 ### 1.3 从隐式到显式推理 **隐式推理**（直接预测）： $$x \rightarrow y$$ **显式推理**（链式）： $$x \rightarrow z_1 \rightarrow z_2 \rightarrow \cdots \rightarrow z_k \rightarrow y$$ **核心收益**： - 可解释性：可以看到推理过程 - 错误定位：可以找出哪一步出了问题 - 纠错能力：可以通过提示引导回到正确方向 --- ## 二、Chain-of-Thought（CoT） ### 2.1 CoT 的核心思想 **提示式推理的统一核心边界**：以上四类方法（CoT、Self-Consistency、Least-to-Most、ToT）全部属于**无参数提示工程**，仅通过文本引导生成逻辑，**不修改模型任何底层权重**，无法从根本修正模型固有知识缺陷与逻辑漏洞。 **CoT**（Wei et al., 2022）的核心是：在提示（prompt）中包含中间推理步骤的示例，引导模型生成类似的推理链。 **形式上**，CoT 提示由以下三部分组成： 1. **输入问题** $x$ 2. **中间步骤** $z_1, z_2, \ldots, z_k$（在提示中） 3. **最终答案** $y$（在提示中） **关键设计**：提示中包含的是 "reasoning steps"，而非仅仅 "input-output pairs"。 ### 2.2 CoT 的数学分析 **定理（CoT 的条件化效应）**： 设 $P_\theta(y | x)$ 是原始模型对问题 $x$ 输出 $y$ 的概率。 CoT 诱导的分布为： $$P_\theta(y | x) = \sum_{z_{1:k}} P_\theta(y | x, z_{1:k}) \cdot P_\theta(z_{1:k} | x) \tag{2.1}$$ **物理意义**： - 模型首先生成中间推理 $z_{1:k}$（这本身就是一个推理过程） - 然后基于中间结果给出最终答案 **引理（CoT 的计算分解）**： 对于加法/乘法等可分解操作，CoT 显式地展示了计算过程： $$(23 + 45) \times 7$$ $$\rightarrow z_1: 23 + 45 = 68$$ $$\rightarrow z_2: 68 \times 7 = 476$$ $$\rightarrow y: 476$$ 每一步的输出空间比原问题小得多。 ### 2.3 CoT 的 prompting 策略 **Few-shot CoT**： 在提示中提供 $K$ 个 (问题, 推理链, 答案) 示例： ``` 示例 1： 输入: 小明有3个苹果，小红给了他2个，他又买了5个。他现在有多少个？ 推理: 3 + 2 = 5（得到后的苹果）... 答案: 10 示例 2： 输入: ... 推理: ... 答案: ... ``` **示例划分**：Few-shot CoT 需区分**通用推理示例**与**领域专属示例**。领域专属示例在垂直场景（如医疗、法律）效果远优于通用示例，应优先注入领域固定推理范式。 **Zero-shot CoT**（Kojima et al., 2022）： 不需要手工编写示例，只需要添加标准提示语： ``` Let's think step by step. ``` **数学形式**： $$P_\theta(y | x) = P_\theta(y | x, \text{"Let's think step by step"}) \tag{2.2}$$ ### 2.4 CoT 在不同任务上的效果 **实验结论**（Wei et al., 2022）： | 任务类型 | 标准 prompting | CoT prompting | 提升 | |---------|---------------|---------------|------| | **数学 word problems** | 17.9% | 46.9% | +29% | | **Commonsense QA** | 53.3% | 64.9% | +11.6% | | **Symbolic manipulation** | 78.6% | 92.1% | +13.5% | **关键发现**：CoT 对**需要多步推理的任务**效果显著，对**单步推理或记忆类任务**效果有限。 **关键前提**：CoT 属于**大模型涌现能力**，小参数量模型使用 CoT 几乎无效果，仅**百亿级以上**大模型才能稳定生成合规推理链。这是工业落地核心边界。 **推理方法选择**： - 短推理任务（单步或少量步骤）：直接用 Zero-shot CoT（`Let's think step by step.`） - 长复杂推理任务：优先 Few-shot 注入领域固定推理范式，减少模型推理自由度过高导致的幻觉风险 **所有提示推理通用优化**：加入**推理终止符**（如 `∴` 或 `Therefore, the answer is`），限制无效长文本生成，大幅提升答案收敛速度。 ### 2.5 CoT 的局限性 **局限性 1：推理链质量依赖模型能力** 模型必须有能力生成**正确**的推理链。如果模型在推理链上犯错，最终答案也会错。 **局限性 2：无法回溯和纠错** 一旦推理链生成，模型不会主动检查和修正中间的步骤。 **局限性 3：长推理链的误差累积** 在长推理链中，前面的错误会导致后续所有推理错误。CoT 线性推理误差单向累积，自洽性仅能缓解单链错误，无法彻底根除系统性逻辑错误。 **局限性 4：推理链易产生事实幻觉（最致命工业痛点）** 推理链看似逻辑通顺实则中间结论违背客观事实。模型可能生成流畅但虚构的推导步骤，例如错误地引用历史数据、捏造不存在的逻辑关系。这是实际落地最大阻碍。 --- ## 三、Self-Consistency（自洽性） ### 3.1 核心思想 **Self-Consistency**（Wang et al., 2023）的核心是：与其只采样一条推理链，不如采样**多条不同的推理链**，然后通过投票选出最自洽的答案。 **关键洞察**： > 正确的推理路径应该比错误的路径产生更多**一致**的最终答案。即使每条路径都有随机性，多条路径的交集更可能是正确答案。 ### 3.2 数学形式化 **定义（推理路径采样）**： 对于问题 $x$，模型采样 $M$ 条独立的推理路径： $$\{(z_{1:k}^{(m)}, y^{(m)})\}_{m=1}^M \sim P_\theta(\cdot | x) \tag{3.1}$$ 每条路径包含： - 推理链 $z_{1:k}^{(m)}$ - 最终答案 $y^{(m)}$ **定义（自洽性投票）**： 统计每个答案的出现频率： $$V(y) = \sum_{m=1}^M \mathbf{1}_{y^{(m)} = y} \tag{3.2}$$ **自洽性答案**： $$y^* = \arg\max_y V(y) \tag{3.3}$$ ### 3.3 与抽样温度的关系 **定理（Self-Consistency 的采样多样性）**： Self-Consistency 的效果与采样温度 $T$ 正相关。 - **低温度**（$T \to 0$）：几乎所有采样都产生相同的推理路径和答案 - **高温度**（$T > 1$）：采样产生多样化的推理路径，但可能包含无意义路径 **最优配置**（细分场景）： - **理科数学推理**：温度 $T \in [0.7, 0.9]$，采样数 $M \in [20, 40]$ - **常识问答**：温度 $T \in [0.5, 0.7]$，采样数 $M \in [10, 20]$ 除温度外，Top-P 核采样、重复惩罚等生成策略同样极大影响推理路径多样性与投票准确率。 ### 3.4 自洽性的信息论解释 **定义（推理链的信息熵）**： 对于答案 $y$，定义其推理链的条件熵： $$H(Z | Y=y, X=x) = -\sum_{z} P(z | y, x) \log P(z | y, x) \tag{3.4}$$ **自洽性度量的信息论含义**： 前提：推理链 $Z$ 对 $Y$ 条件独立，即 $P(y|z,x) = P(y|x)$（推理链完备、无冗余信息）。 在此前提下可证： $$H(Y | X) \leq H(Z | X) \tag{3.5}$$ 最终答案的信息量不超过完整推理链的信息量。投票机制通过压缩多个推理路径来降低不确定性。 ### 3.5 自洽性的实验结果 **主要结论**： | 模型 | GSM8K（数学）| SVAMP（数学）| GAIR（推理）| |------|------------|------------|------------| | **CoT only** | 40.1% | 52.7% | 55.3% | | **+Self-Consistency** | 60.3% | 62.1% | 67.4% | | **提升** | +20.2% | +9.4% | +12.1% | --- ## 四、Least-to-Most（从少到多） ### 4.1 核心思想 **Least-to-Most**（Zhou et al., 2023）的核心是：对于复杂问题，先让模型自己把问题**分解成一系列子问题**，然后逐一解决这些子问题。 **与 CoT 的区别**： | 方法 | 问题分解 | 解决顺序 | |------|---------|---------| | **CoT** | 隐式（在推理链中） | 顺序执行 | | **Least-to-Most** | 显式（分解步骤） | 可以指定依赖 | ### 4.2 算法步骤 **Algorithm: Least-to-Most** **Step 1：问题分解**（Prompt） ``` Given problem X, break it down into sub-problems: 1. [sub-problem 1] 2. [sub-problem 2] ... ``` **Step 2：子问题解决**（顺序执行） ``` For each sub-problem i: - If all dependencies solved: - Solve sub-problem i - Add to known facts ``` ### 4.3 数学形式化 **定义（问题分解）**： 设原问题为 $Q$，分解后的子问题为 $\{q_1, q_2, \ldots, q_K\}$。 分解满足： $$Q \iff \{q_1, q_2, \ldots, q_K\} \tag{4.1}$$ 即原问题的解决等价于所有子问题的解决。 **定义（依赖图）**： 每个子问题 $q_i$ 有一个依赖集合 $D(q_i) \subseteq \{q_1, \ldots, q_{i-1}\}$。 解决顺序必须满足： - $D(q_i)$ 中的所有子问题先于 $q_i$ 被解决 **子问题依赖图类型**：Least-to-Most 拆解出的子问题依赖大多为**无环 DAG 有向无环图**，几乎不存在循环依赖，贴合现实绝大多数推理任务。 **核心优势——逐层纠错**：可逐层校验子问题答案，提前阻断错误向后传播，优于 CoT 线性误差累积。 **数学约束**： $$q_i \text{ can be solved} \iff D(q_i) \subseteq \text{Solved} \tag{4.2}$$ ### 4.4 Least-to-Most 的示例 **数学问题**： ``` Q: "如果小明有23美元，他想买3本书，每本书7美元，他还能剩多少钱？" 分解： q1: "每本书的价格是多少？" → q1 = 7美元 q2: "3本书总价是多少？" → q2 = q1 × 3 = 21美元 q3: "小明买书后还剩多少钱？" → q3 = 23 - q2 = 2美元 答案: 2美元 ``` ### 4.5 与 CoT 的对比 | 维度 | CoT | Least-to-Most | |------|-----|--------------| | **分解方式** | 隐式在推理链中 | 显式分解步骤 | | **子问题依赖** | 自然顺序 | 显式依赖图 | | **适合问题类型** | 有自然顺序的多步问题 | 需要规划的问题 | | **错误传播** | 线性累积 | 可通过依赖检测 | --- ## 五、Tree of Thoughts（思维树） ### 5.1 核心思想 **Tree of Thoughts**（Yao et al., 2023）的核心是：将推理过程建模为**搜索树**，允许**回溯和分支**。 **与 CoT 的区别**： | 方法 | 推理结构 | 回溯能力 | |------|---------|---------| | **CoT** | 链式（一条路） | 无 | | **Self-Consistency** | 多链（并联） | 无 | | **ToT** | 树状（分支+回溯） | 有 | ### 5.2 ToT 的数学框架 **定义（思维节点）**： 在 ToT 中，每个节点表示一个**中间推理状态**： $$s = (x, z_{1:i}, \text{context}) \tag{5.1}$$ 其中 $x$ 是原始输入，$z_{1:i}$ 是当前推理序列，context 是相关上下文。 **定义（思维树）**： 树结构为 $\mathcal{T} = (S, E, s_0)$： - $S$ 是节点集合 - $E \subseteq S \times S$ 是边集合 - $s_0$ 是根节点 **定义（候选生成）**： 从节点 $s$ 生成候选下一步： $$P_\theta(\text{expand}(s) | s) \tag{5.2}$$ 这通常通过 prompt 或采样实现。 ### 5.3 ToT 的算法框架 **Algorithm: Tree of Thoughts** ``` Function ToT(x): S = {s_0 = (x, [], [])} for depth = 1 to K: For each s in frontier(S, depth): # 生成候选 candidates = generate_candidates(s) For each c in candidates: # 评估 if evaluate(c) == "continue": add c to S if evaluate(c) == "terminal": record solution # 从所有解中选择最优 return select_best(S, solution_set) ``` ### 5.4 节点评估函数 **定义（评估函数）**： $$V(s) = \mathbb{E}_{y \sim P_\theta(\cdot | s)}[\text{score}(s, y)] \tag{5.3}$$ 其中 $\text{score}(s, y)$ 可以是： - 完整性（是否解决了子问题） - 一致性（是否与已知事实矛盾） - 前景（是否能导向最终解决） **具体实现**（Prompt 形式）： ``` 评估这个推理步骤： - 正确性：[肯定/可能正确/不确定/错误] - 完整性：[完整/部分/不完整] - 继续价值：[高/中/低] ``` **工程落地评估简化方案**：理论中精细打分评估在纯文本场景难以实现，**实战主流方案**是改用二元对错判别（正确/错误）+ 事实一致性校验替代精细分值评估，降低评估复杂度同时保证效果。 ### 5.5 BFS vs DFS 搜索策略 **广度优先搜索（BFS）ToT**： ``` Level 1: [s1, s2, s3] Level 2: [s1's children] ∪ [s2's children] ∪ [s3's children] ... ``` 适合：评估每个分支成本较低的场景 **深度优先搜索（DFS）ToT**： ``` Follow s1 to leaf Then backtrack to s2 ... ``` 适合：某些分支可以快速到达解 **最佳优先搜索（Best-First）**： 优先探索评估分数最高的节点。**是目前 ToT 落地主流方法**，兼顾效率与解题成功率。 ### 5.6 ToT 与 MCTS 的联系 **ToT 可以看作简化的 MCTS**： | MCTS | ToT | 说明 | |------|-----|------| | **UCB 置信上界选择** | 评估 + 剪枝 | MCTS 使用 UCB 公式平衡探索/利用，ToT 用评估函数替代 | | **随机 rollout** | 采样评估 | 两者均通过随机采样估算节点价值 | | **反向传播** | 候选生成 | MCTS 统计访问计数更新父节点，ToT 将候选向下传播 | | **虚拟访问计数** | 探索广度控制 | MCTS 通过 $N(s)$ 控制节点访问次数，ToT 通过深度/广度限制替代 | ToT 与 MCTS 并非完全等价，ToT 省略了 MCTS 的核心 UCB 选择策略和访问计数机制，在工程实现上更为简化。 --- ## 六、推理方法的对比与适用场景 ### 6.1 方法对比表 | 方法 | 推理结构 | 并行性 | 回溯 | 适合问题类型 | |------|---------|--------|------|-------------| | **CoT** | 链式 | 低 | 无 | 有自然顺序的多步推理 | | **Self-Consistency** | 并联多链 | 高 | 无 | 答案可枚举的问题 | | **Least-to-Most** | 分层树 | 中 | 部分 | 需要规划的问题 | | **ToT** | 搜索树 | 中 | 完全 | 需要探索的问题 | ### 6.2 适用场景分析 **适合 CoT 的场景**： 1. 数学应用题（有明确步骤） 2. 简单代码生成 3. 规则明确的逻辑推导 **适合 Self-Consistency 的场景**： 1. 数学计算（多数投票） 2. 常识推理（多角度验证） 3. 事实性问题（多源确认） **适合 Least-to-Most 的场景**： 1. 复杂规划问题 2. 需要分解的复合问题 3. 依存关系复杂的问题 **适合 ToT 的场景**： 1. 创意写作（多方案探索） 2. 复杂搜索问题 3. 需要回溯的证明问题 **工业落地算力取舍**：推理方法优先级为 **CoT > 自洽性 > Least-to-Most > ToT**，算力有限场景优先轻量化链式推理。算力充足时，复杂问题可用 ToT 探索，自洽性可显著提升数学推理准确率。 ### 6.3 计算成本分析 **定义（总计算量）**： 对于每个问题 $x$，设： - $M$ 是采样数量 - $K$ 是平均推理长度 - $C$ 是每次评估的成本 | 方法 | 总计算量 | |------|---------| | **CoT** | $O(K)$ | | **Self-Consistency** | $O(M \cdot K)$ | | **Least-to-Most** | $O(K^2)$（仅无环子问题依次求解理想情况，实际需叠加问题分解开销，不可单一定论） | | **ToT** | $O(B^D)$（最坏情况，$B$=分支数，$D$=深度） | --- ## 七、数学公式速查 ### 7.1 CoT 公式 **条件推理链分解**： $$P(y | x) = \sum_{z_{1:k}} P(y | x, z_{1:k}) \cdot \prod_{i=1}^k P(z_i | x, z_{1:i-1}) \tag{7.1}$$ **Zero-shot CoT**： $$P_\theta(y | x) = P_\theta(y | x, \text"Let's think step by step") \tag{7.2}$$ ### 7.2 Self-Consistency 公式 **投票计数**： $$V(y) = \sum_{m=1}^M \mathbf{1}_{y^{(m)} = y} \tag{7.3}$$ **自洽性答案**： $$y^* = \arg\max_y V(y) \tag{7.4}$$ ### 7.3 Least-to-Most 公式 **依赖约束**： $$D(q_i) \subseteq \text{Solved} \tag{7.5}$$ ### 7.4 ToT 公式 **节点评估**： $$V(s) = \mathbb{E}_{y \sim P_\theta(\cdot | s)}[\text{score}(s, y)] \tag{7.6}$$ --- ## 八、总结 **推理方法演进**： ``` 直接预测 ↓ CoT（显式推理链） ↓ Self-Consistency（多链投票） ↓ Least-to-Most（显式分解） ↓ ToT（搜索树+回溯） ``` **核心洞察**： 1. **CoT**：通过中间步骤分散推理复杂度 2. **Self-Consistency**：用多数投票对抗单链的不确定性 3. **Least-to-Most**：显式规划子问题依赖 4. **ToT**：在搜索树上进行探索，允许回溯 **这些方法共同指向一个方向**：推理不是一次性的前向传播，而是**迭代式的、可以分支和回溯的搜索过程**。 --- **延伸阅读**： 1. Wei et al., "Chain-of-Thought Prompting Elicits Reasoning in Large Language Models" (NeurIPS 2022) 2. Wang et al., "Self-Consistency Improves Chain of Thought Reasoning in Language Models" (ICLR 2023) 3. Zhou et al., "Least-to-Most Prompting Enables Complex Reasoning in Large Language Models" (ICLR 2023) 4. Yao et al., "Tree of Thoughts: Deliberate Problem Solving with Large Language Models" (NeurIPS 2023) 5. Kojima et al., "Large Language Models are Zero-Shot Reasoners" (NeurIPS 2022)