e2hang/Notes

Fork 0

Files

e2hang 2f5211d8fe New Notes

2026-05-16 17:16:51 +08:00

18 KiB

Raw Permalink Blame History

title, draft, tags

title

draft

CoT 与推理搜索：显式推理链的数学体系

一、为什么需要显式推理

1.1 标准语言模型的局限

标准语言模型的目标：

给定输入 $x$，直接预测输出 $y$：

P(y | x; \theta) = \prod_{t=1}^T P(y_t | x, y_{<t}; \theta) \tag{1.1}

问题：对于多步推理任务（如数学题），模型需要：

理解问题的隐含结构
执行多个推理步骤
整合中间结果得到最终答案

直接让模型"一步到位"预测最终答案，模型需要在内部隐式地完成所有推理——这对于复杂任务过于困难。

1.2 中间步骤的作用

关键观察：

如果要求模型显式地写出中间步骤 $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}

通过引入中间变量，模型可以：

每个 P(z_i | \cdot) 只负责当前一步推理
每个子任务比完整任务更简单
最终答案由清晰的推理链支撑

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 提示由以下三部分组成：

输入问题 x
中间步骤 $z_1, z_2, \ldots, z_k$（在提示中）
最终答案 $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 的场景：

数学应用题（有明确步骤）
简单代码生成
规则明确的逻辑推导

适合 Self-Consistency 的场景：

数学计算（多数投票）
常识推理（多角度验证）
事实性问题（多源确认）

适合 Least-to-Most 的场景：

复杂规划问题
需要分解的复合问题
依存关系复杂的问题

适合 ToT 的场景：

创意写作（多方案探索）
复杂搜索问题
需要回溯的证明问题

工业落地算力取舍：推理方法优先级为 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}