搜索、失败、恢复：一种面向纠错感知推理的训练框架

# 搜索、失败、恢复：面向纠正感知推理的训练框架  
来源：https://arxiv.org/html/2607.07492  

德米特里·贝列斯涅夫¹,³，弗拉基米尔·马哈列夫¹,²，罗曼·哈利科夫³，伊万·奥塞列德茨²，彼得·阿诺欣²,³  

¹ 俄罗斯因诺波利斯大学，因诺波利斯  
² AXXX，莫斯科，俄罗斯  
³ 莫斯科国立大学，莫斯科，俄罗斯  
[email protected]  

###### 摘要  

许多推理任务并不适合用单一的自左向右链条来描述：求解器可能需要探索一个看似合理的分支，观测到延迟的失败，然后返回到仍然可以完成的最新前缀。我们引入Pyligent，一个受"勤奋学习器"(Diligent Learner)框架启发的训练与推理框架，它将推理表示为经过验证的部分解链搜索。任务验证器对生成的连续动作和失败进行标注，生成的搜索树被转换为三种动作的监督目标：继续、完成和回溯，并带有可选的轨迹摘要，用以总结被放弃的分支。我们在一个旨在隔离"延迟失败恢复"能力的隐藏有向图任务上，以及具有精确验证器的结构化推理领域（包括4×4数独、含推理轨迹的数独和积木世界）上评估Pyligent。与仅使用完美轨迹的监督微调相比，Pyligent在隐藏图上的求解率提高了72.7个百分点，在混合与专家数独上分别提高了17和18个百分点，在含推理轨迹的混合与专家数独上分别提高了27和14个百分点，在积木世界上提高了13个百分点。这些结果表明，显式的失败分支监督可以教会有用的恢复行为，而不仅仅是模仿完美的求解链。  

## 1 引言  

推理经常被表示为中间步骤的线性链条，但许多困难任务本质上并非线性。求解器可能需要尝试一个看似合理的方向，直到后来才发现该分支无法导向解，并返回到决策点，那里还存在其他可行的继续方式。标准的思维链监督隐藏了这一过程：训练数据通常只包含打磨好的成功路径，而不包含产生该路径的失败尝试和恢复过程。(Shalev-Shwartz and Shashua,2025 (https://arxiv.org/html/2607.07492#bib.bib15))在"勤奋学习器"方法中将这一观点形式化。他们的理论将"搜索"解的能力与"验证"推理链的能力分开，并论证验证通常比生成要容易得多。相应的充分条件因此是行为层面的，而非词元级别的：学习器应该以固定的非零概率生成正确的下一步推理步骤，当一个分支被揭示为错误时，它应该学习回溯到仍然可以完成的最新前缀。他们的构造性证明表明，在这些假设下，采用学习到的回溯的深度优先搜索过程可以避免朴素搜索、思维树式分支和纯粹完美路径模仿所面临的指数级爆炸问题。  

本文研究该理论留下的一个实际问题：能否将这些条件转化为一个对当代相对较小的大语言模型可实现训练流水线？我们引入Pyligent，这是一个框架，它将推理表示为部分链的树，使用任务验证器标注生成的连续动作，并将成功与失败的分支都转换为监督训练示例。由此产生的动作空间包含普通的继续和终止动作，外加显式的恢复动作。Pyligent用任务特定的检查器实例化了理论中假设的验证器，用它来标注成功的连续动作和失败叶节点，并在三个对应的动作类型上训练模型：继续、完成和回溯。由此产生的实验将勤奋学习器条件落实到了当代大语言模型训练中，我们的回溯类别衡量的是生成的恢复动作是否返回到可修复的前缀，而不仅仅是匹配恢复动作的语法。  

我们最可控的测试是隐藏有向图任务。模型仅观察当前节点的出边，因此一个局部合法的动作可能随后揭示死胡同或失败状态。因此，求解该任务需要尝试下一步动作，从延迟反馈中识别错误，并返回到相关的早期选择点。我们用这个任务来度量恢复能力是否可以直接学习，然后研究Pyligent如何迁移到更结构化的推理领域，如数独和积木世界。  

## 2 相关工作  

思维链(CoT)提示(Wei et al.,2022 (https://arxiv.org/html/2607.07492#bib.bib19))表明暴露中间推理步骤可以显著提高大语言模型在算术、常识和符号任务上的表现。然而，大多数CoT监督仅呈现成功的轨迹：解是自左向右生成的，失败分支通常不在训练信号中出现。这使得CoT成为一种有用的推理表示，但它本身并不是一种学习何时放弃无效分支并从更早状态恢复的训练过程。  

几条工作线通过增加搜索、批评或修订来解决这一限制。思维树(Yao et al.,2023 (https://arxiv.org/html/2607.07492#bib.bib21))和基于MCTS的方法，如Reasoning-via-Planning(Hao et al.,2023 (https://arxiv.org/html/2607.07492#bib.bib5))和AlphaLLM(Tian et al.,2024 (https://arxiv.org/html/2607.07492#bib.bib18))，将探索外部化为显式的推理时树，使用模型或判别器评估来选择有前景的连续动作。提示级别的精炼方法，包括Self-Refine(Madaan et al.,2023 (https://arxiv.org/html/2607.07492#bib.bib11))、Reflexion(Shinn et al.,2023 (https://arxiv.org/html/2607.07492#bib.bib16))和CRITIC(Gou et al.,2023 (https://arxiv.org/html/2607.07492#bib.bib2))，则通过交替生成与反馈或批评，将交互保持在上下文中。这些方法表明推理通常受益于非线性探索，特别是在可靠的反馈可用时(Huang et al.,2023 (https://arxiv.org/html/2607.07492#bib.bib6); Kamoi et al.,2024 (https://arxiv.org/html/2607.07492#bib.bib7))。  

一个互补的方向是直接在类似搜索的轨迹上训练模型。Stream of Search(Gandhi et al.,2024 (https://arxiv.org/html/2607.07492#bib.bib3))序列化DFS和BFS轨迹；Searchformer(Lehnert et al.,2024 (https://arxiv.org/html/2607.07492#bib.bib10))和DualFormer(Su et al.,2024 (https://arxiv.org/html/2607.07492#bib.bib17))将规划器轨迹蒸馏到Transformer模型中；Self-Backtracking(Yang et al.,2025 (https://arxiv.org/html/2607.07492#bib.bib20))引入显式的动作；ASTRO(Kim et al.,2025 (https://arxiv.org/html/2607.07492#bib.bib24))将MCTS rollout转换为包含反思和恢复的推理轨迹。更大规模的纠正策略也通过强化学习训练，包括SCoRe(Kumar et al.,2024 (https://arxiv.org/html/2607.07492#bib.bib9))、RISE(Qu et al.,2024 (https://arxiv.org/html/2607.07492#bib.bib12))、DeepSeek-R1(DeepSeek-AI et al.,2025 (https://arxiv.org/html/2607.07492#bib.bib4))和Kimi k1.5(Team et al.,2025 (https://arxiv.org/html/2607.07492#bib.bib8))。我们的工作遵循这种广泛的搜索训练观点，但专注于一个特定的监督来源：由任务验证器产生的失败分支，这些分支被转换为显式的恢复示例。  

最近的实证研究有助于解释这种监督为何重要。(Gandhi et al.,2025 (https://arxiv.org/html/2607.07492#bib.bib27))发现搜索轨迹的结构可能比最终答案标签对引发验证和回溯行为更重要。同时，回溯并非在每个领域或每种频率下都普遍有用：(Qin et al.,2025 (https://arxiv.org/html/2607.07492#bib.bib13))和(Cai et al.,2025 (https://arxiv.org/html/2607.07492#bib.bib23))表明回溯的有用性强烈依赖于任务结构和训练分布。这些观察结果促使我们对轨迹使用、探索策略和失败分支权重进行消融实验。  

我们工作最接近的概念基础是(Shalev-Shwartz and Shashua,2025 (https://arxiv.org/html/2607.07492#bib.bib15))的勤奋学习器方法。他们的理论将生成与验证分开，并给出了CoT可学习性在两个行为能力方面的充分条件：模型应以非零概率生成一个有效的下一步语义步骤；当一个分支被判定为错误时，它应回溯到β(c)（即仍然可以完成的最大前缀）。他们的分析进一步表明为什么回溯的目标重要：仅返回到直接父节点在子分支全部无效时可能不够，而过度回溯可能会丢弃有用的进展。  

## 3 框架方法论  

Pyligent将思维链生成转化为经过验证的部分解链搜索（图1 (https://arxiv.org/html/2607.07492#S3.F1)）。它不再仅仅在打磨好的完美轨迹上训练，而是记录成功的连续动作和失败的分支，然后将它们转换为用于继续、终止和恢复的监督示例。用(Shalev-Shwartz and Shashua,2025 (https://arxiv.org/html/2607.07492#bib.bib15))的语言来说，求解器提供近似的下一步生成，任务验证器提供回顾性的正确性标签。  

（图1：Pyligent框架。流水线迭代t=1,...,T_max轮，交替进行教师生成的完美链上的微调（SFT-A）和基于探索的微调（SFT-B），后者在*ChainTree*结构化的轨迹上训练，包含成功路径、回溯路径和跟踪路径。）  

### 3.1 表示与组件  

对于每个问题实例，我们维护一棵部分推理状态的树。一个状态是一个前缀 ct = (a0, a1, ..., at)，其中每个动作使用受限的标记词汇：  
`ID CONTENT`，`ANSWER`，`ID REASON`。  
这里追加一个中间步骤，提出最终答案，并将控制权返回到更早的节点。显式的节点标识符使得分支结构对数据生成流水线和推理运行时都可见。  

框架包含四个组件。*求解器*是可训练的语言模型，一次发出一个动作。*探索器*选择求解器应从中采样连续动作的前缀，并控制分配的宽度或深度。*验证器*检查每个提议的动作对于任务状态是否合法。*ChainTree*存储接受和拒绝的分支，为失败分支分配回溯目标，并将得到的搜索树转换为前缀到动作的训练示例。我们在实验中使用了线性和树状探索器；前者通过扩展有限数量的并行链来保持成本可预测，后者开始时宽，然后集中预算到更深的连续动作上。探索器的完整定义见第8.1节 (https://arxiv.org/html/2607.07492#S8.SS1)。  

### 3.2 训练流水线  

训练分三个阶段进行。首先，SFT-A用完美解链训练求解器，教给动作格式，并让模型有非零概率提出有效的下一步。其次，验证器引导的探索从选定的前缀运行求解器，记录有效的连续动作和失败的分支。第三，SFT-B在从生成的ChainTree构建的示例上进行微调。SFT-B包含成功对、失败对，以及对于追踪恢复，还包含追踪后连续动作对。成功对训练模型扩展有效的生成或黄金分支。失败对训练模型在分支违反任务约束时发出 `ID REASON` 动作。对于在节点i处偏离并到达无效叶节点j的失败分支，ChainTree创建目标 `cj -> ID i r`，其中r是验证器推导出的原因。我们对前缀使用反向课程：探索从接近黄金链末尾处开始，那里剩余的连续动作很短，然后向根移动，使求解器必须处理更长的恢复感知轨迹。对构建和课程细节见第8.2节 (https://arxiv.org/html/2607.07492#S8.SS2)。  

### 3.3 推理与追踪恢复  

推理时，求解器一次生成一个动作。`CONTENT`动作被追加到当前链，`ANSWER`动作终止并提出答案，`ID REASON`动作会在运行时检查目标是否有效，然后将上下文截断到该节点。推理在求解器发出`ANSWER`或耗尽固定步数预算时停止。  

简单回溯将失败分支从上下文移除，这可能导致求解器重复相同的错误。为了保留紧凑的失败信息，追踪恢复在截断后插入运行时生成的`ID trace`。追踪记录验证器原因和被放弃分支的简短摘要；它从来不是模型的目标。在SFT-B期间，我们为匹配的失败示例注入合成追踪，产生连续动作对，教会模型如何在恢复后继续。确切的追踪格式见第8.3节 (https://arxiv.org/html/2607.07492#S8.SS3)。  

## 4 任务方法论  

### 4.1 隐藏有向图任务  

隐藏有向图任务是一个受控基准，用于测试求解器是否已学会有效的搜索和回溯策略。每个实例是一个有向图，具有特殊节点START、GOAL和FAIL。模型必须找到一条从START到GOAL、同时避免FAIL的路径，但它只能观察到当前节点的出边。在模型选择合法的非终止移动后，环境会揭示新到达节点的出边作为下一个观测。这使得该任务在勤奋学习器假设下对评估Pyligent很有用：模型不能通过复制静态问题描述来求解，一个局部有效的移动仍可能暴露一个必须放弃的分支。  

这个任务有意接近于(Shalev-Shwartz and Shashua,2025 (https://arxiv.org/html/2607.07492#bib.bib15))中的搜索理论例子。难点不在于解析局部动作格式：从任何可见节点选择一条出边很容易验证。难点在于，局部有效的边可能在全局上是错误的，而且错误的证据可能要在几步之后才出现。因此，一个成功的求解器必须学会在部分信息下提出合理的移动，并且一旦揭示死胡同或FAIL节点，就返回到最新的有用选择点。  

形式上，一个实例是一个有向图 G=(V,E)，包含开始节点 s，目标节点 g，以及禁止的失败节点 d。在步骤 t，环境状态是已探索路径 pt = (s, v1, ..., vt)，但模型面对的观测仅暴露当前节点 vt 的出边邻居 O(vt) = {u: (vt,u) ∈ E}。求解器必须选择一个可见的邻居，当目标可见时终止，或者当前分支无效或被揭示无解时回溯。  

（图2：隐藏有向图交互。环境包含完整图，但提示只显示当前节点的出边。）