Atom of Thoughts for Markov LLM Test-Time Scaling¶

会议: NeurIPS 2025 / arXiv: 2502.12018 / 代码: 随论文提交（将公开） / 领域: LLM推理 / 关键词: test-time scaling, Markov process, atomic reasoning, DAG decomposition, reasoning framework

一句话总结¶

提出 Atom of Thoughts (AoT)，将 LLM 推理建模为马尔可夫链，每个状态是与原问题答案等价但复杂度递减的自包含子问题，通过 DAG 分解+收缩的两阶段转移机制消除历史依赖，可与 ToT/反思等方法无缝集成，在数学/代码/多跳QA等6个benchmark上全面领先现有推理框架。

研究背景与动机¶

领域现状：测试时缩放 (test-time scaling, TTS) 是提升 LLM 推理能力的核心范式。现有方法包括链式推理 CoT、树搜索 ToT、图结构 GoT、以及推理模型 O1/R1 等。这些方法的共同逻辑是：在推理时投入更多计算换取更好结果。
核心痛点——历史依赖累积：所有现有框架都严重依赖历史信息。CoT 必须保留完整推理轨迹来生成下一步（prompt token 随步数线性增长）；ToT 维护父子兄弟关系用于分支决策；GoT 通过任意节点连接引入更复杂的依赖关系。论文 Figure 1(b) 量化分析了各方法在每次 LLM 调用时的 prompt token 和 completion token 数量，清晰展示了这一开销。
矛盾所在：TTS 的核心是"多算多收益"，但历史依赖使得每一步的边际计算效率递减——花越多 token 推理，后续每一步需要处理的历史上下文就越长，真正用于"当前问题推理"的有效计算比例越低。
切入角度：借鉴马尔可夫过程的无记忆性——如果每个推理状态只需依赖前一个状态而非全部历史，就能将推理计算完全聚焦于当前问题。关键挑战是如何让每个状态"自包含"，不丢失解题所需的信息。
核心 idea：将推理链的节点从"中间思维步骤"重定义为"与原问题答案等价但复杂度更低的独立子问题"。通过 DAG 分解+收缩实现状态转移，推理链自然收敛到不可再分解的"原子"结构。

方法详解¶

整体框架¶

输入原问题 \(Q_0\)，通过迭代的马尔可夫状态转移生成状态序列 \(Q_0 \to Q_1 \to \cdots \to Q_N\)。核心约束有两个：(a) 答案等价——每个 \(Q_i\) 的答案就是 \(Q_0\) 的答案；(b) 复杂度单调递减——\(Q_{i+1}\) 比 \(Q_i\) 更简单。每次转移包含分解和收缩两个阶段，最终状态 \(Q_N\) 可直接求解。

关键设计 1：马尔可夫状态定义¶

传统 CoT 建模为 \(A \sim p(A|\mathcal{T}, Q_0) \prod_{i=0}^{N} p(T_i | \mathcal{T}_{<i}, Q_0)\)，每步思维 \(T_i\) 依赖所有历史思维 \(\mathcal{T}_{<i}\)。Least-to-Most 将节点改为子问题 \(Q_i\)，但仍保留历史依赖 \(p(Q_i|\mathcal{Q}_{<i})\)。

AoT 的马尔可夫建模为：

\[A \sim p(A|S_N) \prod_{i=0}^{N} p(S_{i+1}|S_i)\]

其中 \(S_i\) 用子问题 \(Q_i\) 表示，每个 \(Q_i\) 是与 \(Q_0\) 答案等价的自包含问题。关键洞察：答案等价性 + 复杂度递减自然获得马尔可夫性，因为 \(Q_{i+1}\) 本身就包含了解题所需的一切信息，不需要回看历史。

关键设计 2：DAG 分解-收缩两阶段转移¶

直接让 LLM 做"把问题简化为等价但更简单的问题"是困难的。AoT 设计了两阶段机制：

分解阶段：构建临时 DAG \(\mathcal{G}_i = (\mathcal{N}, E)\)，其中 \(E \subseteq \{(N_j, N_k) \mid j < k\}\)。节点 \(N_k\) 为子问题或思考步骤，有向边 \((N_j, N_k)\) 表示 \(N_j\) 为 \(N_k\) 提供必要信息。这一步显式建模了推理步骤间的依赖结构。

收缩阶段：识别 DAG 中无入边的节点——这些是独立子问题，可以直接求解并丢弃（因为它们的答案已被吸收进依赖它们的节点）。剩余的依赖节点被重新组合为一个新的等价问题 \(Q_{i+1}\)。

完整的马尔可夫转移概率为：

\[A \sim p(A|Q_N) \prod_{i=0}^{N} p(Q_{i+1}|\mathcal{G}_i) \cdot p(\mathcal{G}_i|Q_i)\]

关键设计 3：质量感知终止策略¶

马尔可夫链的无记忆性是双刃剑——CoT 可以通过上下文修正早期错误，而 AoT 一旦某步转移质量差后续推理就会偏离。为此设计了终止机制：

每次转移 \(Q_i \to Q_{i+1}\) 后，用 LLM-as-a-judge 从三个候选中选择最优答案：\(\text{solve}(Q_i)\)、\(\text{solve}(\mathcal{G}_i)\)、\(\text{solve}(Q_{i+1})\)
如果 \(Q_{i+1}\) 未被选中则终止链并返回当前最佳答案
这隐式地强制执行了答案等价性：如果 \(Q_{i+1}\) 语义偏离了 \(Q_0\)，它的解不会是 \(Q_0\) 的有效答案，自然不会被 judge 选中

关键设计 4：模块化集成与原子结构涌现¶

模块化集成：由于每个马尔可夫状态 \(Q_i\) 都是 \(Q_0\) 的等价简化表示，任何 \(Q_i\) 都可以作为其他推理方法（ToT、反思等）的入口点。AoT 不是替代现有方法，而是为它们提供结构化预处理。

原子结构涌现：通过树搜索+反思扩展马尔可夫链后，深层推理状态的 reasoning token 数逐渐收敛到一个稳定值——接近最小 DAG 中独立子问题集合的 token 数。这意味着问题被分解到了不可再简化的"原子"粒度。原子性不是预先设计的，而是推理过程中自然涌现的——不同问题在不同深度收敛，同一问题在不同能力模型上也展现不同的原子粒度。

训练策略¶

AoT 是纯推理时 (inference-time) 方法，不需要额外训练或微调。通过 prompt 模板实现分解和收缩阶段。默认超参：温度 1.0，最大马尔可夫链长度 3。由于终止机制的存在，链长增加提升性能上限但不会线性增加成本。

实验关键数据¶

主实验：非推理模型¶

模型	方法	MATH	GSM8K	MBPP	LongBench
GPT-4o-mini	CoT	78.3	90.9	72.4	57.6
GPT-4o-mini	CoT-SC	81.8	92.0	73.2	58.6
GPT-4o-mini	AFlow	83.0	93.5	74.0	61.0
GPT-4o-mini	FoT	82.6	94.2	74.8	60.8
GPT-4o-mini	AoT	83.6	95.0	75.2	68.5
DeepSeek-V3	CoT	94.4	96.2	75.7	58.8
DeepSeek-V3	AFlow	96.1	97.8	77.3	63.5
DeepSeek-V3	AoT	96.5	98.2	79.6	71.0

主实验：推理模型¶

模型	方法	AIME	LiveCodeBench	LongBench
O3-mini	CoT	79.6	23.6	56.3
O3-mini	AFlow	82.5	26.5	58.0
O3-mini	FoT	81.8	27.8	57.9
O3-mini	AoT	83.0	32.2	65.3
DeepSeek-R1	CoT	78.3	24.5	55.1
DeepSeek-R1	AFlow	81.2	27.4	58.7
DeepSeek-R1	AoT	81.7	30.9	67.9

消融实验¶

配置	说明	效果
无分解（直接收缩）	跳过 DAG 构建，直接尝试简化问题	性能显著下降
无 DAG 引导收缩	构建 DAG 但收缩时不利用其结构	比无分解还差，部分结构线索反而造成干扰
完整 AoT	DAG 分解 + 结构引导收缩	最优

DAG 质量指标：答案等价维持率 >99%（所有数据集），复杂度缩减率 74-82%。

集成实验（Scaling Up）¶

集成方式	MATH	AIME
ToT 单独	82.0	78.0
FoT 单独	82.6	--
AoT state 作为 ToT 入口	性能提升 + 计算成本降低	--
AoT + ToT + Reflection (full)	84.9	81.2

关键发现¶

LongBench 提升最显著：GPT-4o-mini 上 AoT 比 AFlow 高 7.5 分（68.5 vs 61.0），O3-mini 上比 AFlow 高 7.3 分（65.3 vs 58.0）。多跳 QA 任务的历史依赖最重，从马尔可夫化受益最大。
性能随迭代持续提升不退化：Figure 3 展示了 AoT 在增加推理迭代（更长马尔可夫链）时性能稳步上升，验证了终止策略有效防止了错误传播。
原子收敛现象：深层马尔可夫链的 reasoning token 数自然趋向一个下界——接近最小 DAG 的独立子问题集合大小，证实原子结构是涌现而非预设的。
State Integration 双赢：用 AoT 的中间状态 \(Q_1\) 作为 FoT 的入口，不仅提升准确率，还降低计算成本——因为简化后的问题需要更少的搜索。
推理模型同样受益：AoT 不仅对 GPT-4o-mini 等非推理模型有效，对 O3-mini、DeepSeek-R1 等原生推理模型也能带来显著提升，说明马尔可夫化与推理能力正交。

亮点与洞察¶

视角新颖：首次将马尔可夫过程的无记忆性系统性地引入通用 LLM 推理，不是简单类比而是严格的概率建模（公式 1到3 的推导很清晰）
DAG 分解-收缩设计精巧：把"简化问题"这个模糊目标拆解为结构化两步操作，降低了对 LLM 的要求，让状态转移变得可靠
原子概念的涌现性：不是人为设定原子粒度，而是让推理过程自然收敛到不可再分解的状态，比硬编码分解深度更优雅
即插即用的架构设计：AoT 可以作为任何推理框架的预处理模块，不需要修改下游方法，这种正交性使其具有很高的实用价值
对多跳 QA 的不对称收益：LongBench 上的巨大提升（+7到12分）暗示历史依赖是多跳推理的主要瓶颈之一

局限性 / 可改进方向¶

纯推理时方法的天花板：AoT 当前完全依赖 prompt engineering，如果能通过 SFT 或 RL 让模型内化马尔可夫推理模式（如在分解-收缩轨迹上训练），可能获得更大提升
DAG 构建质量依赖模型能力：分解阶段需要 LLM 正确识别子问题间的依赖关系，对弱模型可能不稳定
终止策略的保守性：LLM-as-a-judge 可能过早终止有潜力的链，限制了深层原子结构的涌现频率
链长度上限为 3：主实验固定最大链长为 3，更长的链是否能持续收益尚未充分探索
代码任务提升有限：在 MBPP 等代码生成任务上提升相对较小（+1到2分），可能因为代码任务的历史依赖形态不同于自然语言推理

评分¶

新颖性: 5/5 -- 马尔可夫建模+原子涌现的视角非常新颖，从概率论出发重新定义推理结构
实验充分度: 4/5 -- 4个模型x6个benchmark全面覆盖，集成实验设计巧妙，但消融只在 GPT-4o-mini 上做缺少其他模型的消融
写作质量: 5/5 -- 公式推导自洽，图示清晰（Figure 1 的 token 分配对比），概念解释到位
价值: 4/5 -- 即插即用的实用设计加深刻的理论洞察，但纯推理时方法的提升幅度在强推理模型上可能有限