DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Search

从原理层面看，该架构将蒙特卡洛树搜索（MCTS）的序列决策探索能力与强化学习（RL）的策略优化能力深度耦合，构建了“搜索-验证-学习”的闭环系统。形式化定理证明本质上是一个高维、稀疏奖励的马尔可夫决策过程（MDP），传统自回归生成模型极易因早期步骤的微小误差导致后续证明路径彻底偏离（误差累积效应）。为此，DeepSeek-Prover-V1.5采用基于策略梯度（如PPO或GRPO）的强化学习算法作为底层优化器，同时引入MCTS作为推理时的搜索引擎。具体实现上，模型基座采用经过Lean 4语法对齐的大语言模型（参数规模覆盖7B至14B），其输出被解耦为策略网络（Policy Network）与价值网络（Value Network）。在MCTS的四个阶段中，选择阶段采用PUCT算法，公式为U(s,a) = Q(s,a) + c * P(s,a) * sqrt(N(s))/(1+N(s,a))，其中P由策略网络先验提供，Q由价值网络与历史回报更新；扩展阶段利用策略网络采样生成候选战术（Tactics）；模拟阶段结合快速rollout与价值网络预测；回溯阶段沿搜索树更新节点访问次数与价值估计。状态表示采用战术状态快照（Tactic State Snapshot），包含当前目标列表、局部假设上下文及类型签名，经嵌入层映射为固定维度向量。训练流程采用离线数据预训练（SFT）初始化，随后进入在线RL微调阶段：模型在MCTS树中生成多条证明轨迹，Lean 4执行器提供奖励信号，优势函数（Advantage）经GAE估计后用于更新网络参数。关键技术参数包括：搜索树最大深度设为20-50层，单步并行rollout数量100-500条，探索常数c_puct动态调节在0.8-1.2之间，学习率初始设为1e-5并采用余弦衰减，训练批次大小256，累积步数超50万。为缓解RL训练的不稳定性，系统引入了KL散度惩罚项（β_KL≈0.1）限制策略偏离，并采用经验回放池缓存高质量证明片段。该架构有效打破了纯自回归生成的“短视”局限，通过MCTS的lookahead能力大幅压缩无效搜索空间，同时RL的长期回报优化使模型学会权衡局部战术正确性与全局证明可行性。实验表明，该架构在保持推理延迟可控的前提下，将复杂定理的证明成功率提升了近一倍，显著降低了算力消耗，为形式化推理提供了可扩展的工程范式。

该创新点突破了传统大模型在形式化证明中“幻觉战术”与“奖励稀疏”两大瓶颈，其核心在于将Lean 4证明助手作为可执行验证器与反馈源，深度嵌入MCTS的搜索与评估流程。从原理上看，Lean 4不仅提供语法检查，更能执行类型推导、目标简化与子目标生成，输出结构化、确定性的中间状态。系统将此反馈机制转化为MCTS的“真实模拟器”与RL的“密集奖励信号”。具体实现分为三个层次：其一，执行反馈层。模型每生成一个战术（Tactic），立即调用Lean 4 API进行解析与执行，返回执行状态（成功/失败/类型错误）、新生成的目标列表（Goals）及假设上下文。若执行失败，MCTS直接剪枝该分支，避免无效搜索；若成功，则更新节点状态并计算进度指标。其二，状态评估层。系统将Lean 4返回的战术状态转化为可量化的特征向量，包括目标数量变化ΔN、假设复杂度评分、类型签名匹配度等，输入价值网络进行状态价值估计V(s)。该估计替代了传统启发式函数，大幅提升评估准确性。其三，奖励塑形层。RL训练采用多目标奖励函数R = α·δ_goal + β·δ_complexity + γ·success，其中α、β、γ为可调权重（通常设为0.4/0.3/0.3），δ_goal衡量目标消解进度，δ_complexity反映证明难度降低程度，success为最终证明完成的二元奖励。该设计将稀疏的终点奖励转化为密集的过程奖励，有效引导模型探索高价值路径。在MCTS策略探索中，反馈信号直接用于更新Q值与先验概率P，使搜索树向Lean 4验证通过的区域倾斜。技术细节方面，Lean 4 API调用延迟控制在50-200ms/步，系统采用异步并发执行器池（并发数≥64）保障吞吐量；反馈数据经标准化后存入轨迹缓冲区，用于GRPO算法的优势估计。该创新彻底消除了模型“自说自话”的证明幻觉，确保每一步战术均符合形式化逻辑规则。实验数据显示，引入反馈机制后，无效战术生成率下降超70%，证明路径收敛速度提升2-3倍，模型在复杂引理组合与多步归纳证明中的鲁棒性显著增强，实现了从“语言生成”到“逻辑验证”的范式跃迁。

在形式化定理证明领域，ProofNet与MinF2F是衡量模型逻辑推理与代码生成能力的权威基准。ProofNet基于Lean 4构建，涵盖代数、分析、组合数学等核心数学分支，提供约数万条高质量证明轨迹，重点评估战术级准确性（Step Accuracy）与完整证明成功率（Proof Accuracy）；MinF2F则聚焦于形式化数学的细粒度推理，强调模型在缺乏人类提示下的自主证明能力。DeepSeek-Prover-V1.5在这两项基准上均取得SOTA（State-of-the-Art）成绩，其领先性源于架构与训练策略的深度优化。评估协议采用严格的零样本/少样本生成模式，推理阶段启用MCTS搜索（最大深度30，并行rollout 200），以Pass@k（k=1,5,10）作为核心指标。具体数据方面，在ProofNet测试集上，模型Step Accuracy达到68.4%，Proof Accuracy达到46.2%，较上一代DeepSeek-Prover-V1提升14.7%绝对值，超越GPT-4、Claude 3及开源基线模型15%-25%；在MinF2F基准上，Proof Accuracy突破51.8%，在复杂定理（如实分析引理、群论同构证明）子集上准确率超60%。成绩领先的关键技术支撑包括：其一，截断与恢复机制（Truncation & Recovery）。针对长证明易发散问题，系统在证明步骤超过阈值（如50步）时自动截断，保存当前战术状态快照，并在后续推理中从最近有效节点恢复，避免上下文溢出与误差累积。其二，统一生成范式。模型将战术生成与完整证明生成统一为序列到序列任务，通过动态上下文窗口管理（滑动窗口+关键假设缓存）平衡内存占用与信息完整性。其三，推理时计算分配。通过MCTS的自适应搜索预算分配，模型在简单步骤快速通过，在关键分歧点增加rollout数量，实现算力最优利用。硬件配置上，训练采用8×A100 80GB集群，推理单卡延迟控制在2-5秒/步。该成绩不仅验证了“RL+MCTS+反馈”架构的有效性，更标志着开源模型在形式化数学推理上首次逼近甚至超越闭源前沿系统，为自动化数学研究、代码验证与形式化验证工具链提供了可复现的基准参考。

形式化证明的策略空间是一个指数级庞大的组合空间，包含战术序列、引理调用顺序、子目标分解方式及证明结构拓扑。传统方法依赖人工启发式规则或固定模板，泛化能力受限。DeepSeek-Prover-V1.5的核心突破在于实现策略空间的自动探索与自适应导航，其原理基于强化学习的策略优化与MCTS的树状搜索协同。具体而言，系统将证明过程建模为状态转移图，每个节点代表一个战术状态，边代表合法战术应用。探索过程由MCTS驱动，通过PUCT算法平衡“利用”（高价值路径）与“探索”（低访问次数路径），避免陷入局部最优。策略学习则依赖RL算法，模型通过大量与Lean 4的交互，学习状态-动作值函数Q(s,a)，逐步构建对策略空间的隐式理解。关键技术实现包括：其一，策略分解与重组。模型学会将复杂定理自动拆解为可管理的子目标（Subgoals），并通过中间引理（Lemmas）桥接逻辑断层。训练时采用课程学习（Curriculum Learning），从基础代数恒等式逐步过渡到高阶分析定理，使策略网络逐步掌握组合逻辑。其二，跨轨迹经验复用。系统维护一个策略缓存库（Strategy Cache），记录历史证明中成功的战术-状态对。当新证明遇到相似子结构时，模型通过相似度匹配（基于目标向量余弦相似度>0.85）直接检索并复用已验证策略，大幅缩短搜索路径。其三，动态策略剪枝与回溯。在探索过程中，若某分支连续N步（N=5）未产生有效状态简化或触发Lean 4类型错误，系统触发软剪枝，降低该分支探索权重；同时支持多路径回溯，保留Top-K高价值节点供后续扩展。技术参数方面，策略空间探索预算设为每证明1000-3000节点，缓存库容量达百万级条目，相似度检索延迟<10ms。训练阶段采用对比学习辅助策略网络优化，正样本为Lean 4验证通过的战术序列，负样本为幻觉或死胡同路径，损失函数结合交叉熵与InfoNCE项。该机制使模型摆脱对人类证明范式的依赖，具备自主发现新颖证明路径的能力。实验表明，自动探索策略在未见定理上的泛化准确率提升22%，证明步骤平均长度缩短30%，且能处理非标准证明顺序与非常规引理组合，显著增强了形式化推理的灵活性与创造性，为AI辅助数学发现奠定了方法论基础。