← 返回 2026-05-29

通过检查点修复实现可恢复的思维程序（Program-of-Thought） REPOT: Recoverable Program-of-Thought via Checkpoint Repair

Parsa Mazaheri 📅 2026-05-28 👍 10 2026-07-13 08:36

LLM推理检查点机制程序化思维规划任务验证驱动恢复

为POT引入检查点恢复机制，一次LLM调用修复失败轨迹，在多个基准上提升3-11pp成功率

前置知识

Program-of-Thought (POT)

Chen等人（2023）提出的推理范式，提示模型编写Python程序，其标准输出编码为一个行动序列。程序在沙箱中运行，解析输出以得到计划，然后由环境模拟器执行该序列。POT将脆弱的状态跟踪、合法动作过滤等簿记负担以代码形式交给模型处理，这符合模型的专长（Wei等人，2022）。但成本也是其弱点：执行过程中一个非法动作会使整个轨迹失效，连同已验证的前缀一起丢弃。

理解POT是理解本文的基础；REPOT是POT的一个小而强大的扩展，在其上增加了基于检查点的恢复能力。若不了解POT的单次执行机制和一次出错即全盘皆输的失败模式，就难以体会REPOT的改进价值。

确定性验证重放（Verified Replay）

本文提出的一个确定性原语，它将候选行动序列逐步在环境中执行，逐步验证每个转换的有效性。给定起始状态和计划，定义轨迹等于状态转移函数应用于当前动作（若转换有效），否则为失败标记。设k为转换首次无效的最小索引（若每个动作都有效则为n+1）。则REPLAY函数返回最大有效前缀、失败边界处的验证状态和验证器的错误信息。该函数是完备的、确定性的，不涉及LLM调用，成本为O(n)个环境步。

验证重放是REPOT的核心组件；它将任意POT执行转换为可从检查点恢复的计算，无需额外LLM调用。理解这个原语对于掌握REPOT的三步流程（POT调用、验证重放、后缀修复）至关重要。

检查点恢复（Checkpoint-based Recovery）

在执行失败后，从最后一个验证状态（检查点）恢复的能力。传统POT失败时会丢弃整个轨迹；检查点恢复则保留验证状态和已验证前缀，仅要求模型修复未验证的后缀。这比从头重新规划（POT-retry）更高效，因为模型可以利用已验证状态的信息。本文提出的单次修复预算（R等于1）确保成本控制在POT基线的1.06-1.4倍：86%的问题不需要修复（已成功），仅14%需要一次额外LLM调用。

检查点恢复是REPOT相对于POT和树搜索方法（ToT、LATS）的本质优势。理解检查点恢复的工作原理和成本分析，有助于判断何时REPOT能提供价值（即模型产生长有效前缀后失败时），以及何时不如POT-retry（即前缀为空或很短时）。

验证器（Verifier）

环境提供的确定性步函数，它返回下一状态和有效性标志。在规划任务中，验证器通常就是环境模拟器本身（例如汉诺塔移动的合法性检查、积木世界的stack操作是否合法）。验证器可以免费、即时、精确地判断一个动作是否合法，无需训练。这使得REPOT能够跳过学习过程奖励模型（PRM），直接用环境作为验证器。DERAIL-550实验表明，访问检查点信息（验证状态、合法动作集、验证器错误）是恢复工作的负载信号，而非仅文本错误反馈。

验证器的可用性是REPOT适用范围的前提。理解验证器的角色有助于判断REPOT能否迁移到其他设置（如编码代理的测试套件、SQL代理的模式检查、浏览器自动化的页面状态验证），这是本文作为未来工作提出的开放问题。

研究动机

现有大语言模型规划方法存在关键失败模式。单次Program-of-Thought（POT）让模型编写Python程序输出计划，然后在环境中执行。但一个非法动作会静默地使整个轨迹失效——即使前99%的动作都是正确的，第100个非法动作也会让整个任务失败。典型修复方法要么在工具中运行单个样本（POT），要么采样多个独立轨迹并聚合（Self-Consistency、Tree of Thoughts）。两者都无法恢复：POT的单次计划包含中途错误无法从成功点恢复；树搜索方法（ToT、LATS）在生成过程中分支，无论第一条轨迹是否已基本正确都要承担分支成本。实证上，Shojaee等人（2025）在775个控制复杂度的规划问题中发现，失败通常在轨迹早期集中，首个无效动作往往出现在最优计划长度的小部分，但后续token被用于生成错误但一致的延续。这产生了一个可恢复失败的长尾巴：大部分失败轨迹都有长有效前缀和单个中途错误。

本文的目标是本文的目标是提出一个恢复扩展，让POT能够从验证器识别的失败点恢复，而不升级到树搜索。具体来说，REPOT（Recoverable POT）是一个对POT的小结构修改，添加基于检查点的恢复：确定性验证重放以找到失败边界，加上一个有界的后缀修复LLM调用，该调用基于验证状态而非文本批评进行条件化。目标是保持POT的成本效益（86%的问题在POT基线成本运行，仅14%需要额外LLM调用），同时在模型足够强以产生有用有效前缀时提升成功率。

与已有工作不同的是，本文的独特切入角度是将单次LLM推理重新构架为可恢复执行。而非全有或全无，验证器拥有可信状态，模型仅被要求修复未验证后缀。这与Reflexion式的文本批评形成对比——Reflexion要求模型以文本方式内省其错误，但批评可能错误（产生失败的模型现在也产生诊断）。REPOT使验证器成为真实源。关键洞察是检查点信息（验证状态、合法动作集、验证器错误）而非特定的验证前缀尾部是负载恢复信号。DERAIL-550实验显示，访问检查点信息的条件在GPT-medium上恢复大于等于30%的注入错误，在Gemini上恢复大于等于70%，而仅错误反馈的恢复率小于等于3.1%。这分离了恢复能力条件与仅错误反馈条件约60pp。

核心方法

REPOT的整体思路先从直观层面入手：当一个模型编写一个计划程序并执行它时，如果它在执行中途失败，我们不应该丢弃整个轨迹——我们应该从最后验证状态恢复。在技术路线层面，REPOT在POT上工作，方法分为三个步骤。首先，运行POT一次：模型发出Python程序，执行它，解析打印的动作列表。其次，确定性验证重放：将提议的动作通过环境逐步执行，累积最大有效前缀有效转换直到首次失败。如果前缀已达到目标，返回成功。否则，发出一个后缀修复LLM调用，条件化于验证前缀、失败边界的验证状态和验证器的错误消息。修复预算R等于1（默认），但可以调整。关键是在验证器识别真实失败点后才分支——ToT和LATS在生成期间分支，REPOT仅在确定性检查识别出真实失败点后才分支。这使成本保持在POT基线附近。

核心创新点是验证重放原语与单次后缀修复调用的组合，使单次LLM推理执行可恢复。与已有方法的本质区别：POT是全有或全无，一个错误使整个轨迹失效；Self-Consistency和树搜索方法采样多个轨迹，成本与轨迹数量成正比（O(k)）无论第一条轨迹是否已接近正确；Reflexion、Self-Refine、Self-Repair使用第二次LLM调用条件化于对先前尝试的文本批评，但批评可能错误且没有检查点机制——第二次调用从头开始重新规划。REPOT的验证重放是确定性的，不涉及LLM调用，其成本为O(n)环境步。后缀修复调用条件化于验证状态、验证前缀和验证器错误，而非文本批评。修复预算R等于1，所以成本在约86%的简单问题上保持在POT基线，仅在剩余问题上翻倍。

方法步骤详情

方法步骤的完整描述：第一步，运行POT：给定问题和环境E，调用模型M使用POT提示，模型发出Python程序，执行程序，解析打印的动作列表。第二步，验证重放：将提议的动作序列通过环境逐步执行，累积最大有效前缀，其中k是转换首次无效的最小索引。同时记录验证状态和验证器错误。验证重放函数返回最大有效前缀、失败边界处的验证状态和验证器的错误消息（或空字符串如果k等于n+1）。第三步，检查目标：如果前缀P已达到目标，返回成功。第四步，后缀修复：如果未达到目标，发出一次后缀修复LLM调用（修复预算R等于1），使用修复提示：稳定块（问题陈述、目标）在验证检查点标记上方，动态块（最后T个验证动作、当前验证状态、合法动作、验证器错误）在下方。T默认为4。模型发出后缀动作序列。第五步，验证修复：将后缀从验证状态开始通过验证重放，得到新的前缀。第六步，组合前缀：将原前缀与新前缀组合，得到完整计划。如果达到目标，返回成功，否则部分计划（预算耗尽）。完整算法见Algorithm 1。

技术新颖性

技术新颖性分析：REPOT将单次LLM推理重新构架为可恢复执行，而非全有或全无。三个组件构成新颖性：确定性验证重放原语，将任意POT执行转换为可从检查点恢复的计算，无需LLM调用；后缀修复调用条件化于验证状态而非对先前尝试的文本批评——一个良好类型的任务；单次修复预算（R等于1），所以成本在约86%的简单问题上保持在POT基线，仅在剩余问题上翻倍。新颖性还体现在检查点信息的角色：DERAIL-550显示检查点信息（验证状态、合法动作集、验证器错误）而非仅错误消息是负载恢复信号。此外，自适应恢复策略（ADAPTIVE REPOT）是初步扩展，它根据验证前缀长度路由到后缀修复或新鲜POT重试，当n等于0或前缀分数小于0.15时路由到新鲜POT重试，否则路由到后缀修复。这实现了式2暗示的最优分支预测：当可恢复子集为空时路由到新鲜采样，否则利用验证前缀。

**Figure 13**: Adaptive policy routing per open-source model

实验结果

核心发现包括：在PUZZLEZOO-775（775个控制复杂度的规划问题，跨四个经典规划环境：汉诺塔、跳棋跳跃、过河、积木世界）上，REPOT在四个封闭模型配置上超越POT 3到11pp。最大改进在gpt-5.4-mini-medium（96.9% vs 86.3%，+10.6pp）。与匹配预算POT-retry基线比较，REPOT在Gemini上决定性获胜（+3.8pp，95% CI [+2.2, +5.4]），在GPT-medium和Claude上在采样噪声内，在GPT-mini上失败（−6.6pp，[−9.4, −3.7]）。这个结果与核心主张一致：REPOT的机制贡献随首次POT计划的有效性缩放，而首次POT计划本身随模型能力缩放。在PLANBENCH BLOCKSWORLD（378个实例，3-12块）的外部复制上，REPOT在所有三个模型上超越POT：GPT-5.4-mini（64.3% vs 55.0%，+9.3pp），Claude Sonnet 4.6（91.3% vs 79.9%，+11.4pp），Gemini 3.5 Flash（100.0% vs 98.9%，+1.1pp）。所有三个模型的配对bootstrap 95% CI为正：GPT-mini [+3.5, +14.9]，Claude [+6.9, +15.9]，Gemini [+0.3, +2.1]。在四个开源模型（Gemma 4 26B、GPT-OSS 20B、Qwen 3.6 35B、Nemotron-3 Nano 30B）上，REPOT在三个上超越POT：Gemma（+20.0pp），GPT-OSS（+3.3pp），Qwen（−3.4pp在采样噪声内），Nemotron失败（−23.4pp）。DERAIL-550（550个错误乘以11条件）的机制分析显示，访问检查点信息的每个条件在GPT-medium上清除大于等于30%注入错误，在Gemini上清除大于等于70%，而仅错误反馈为3.1%和20.7%，无反馈为1.6%和3.8%。这个约30-80pp间隔是标题发现：检查点信息而非文本错误反馈或特定的验证前缀尾部是决定性恢复信号。成本方面，REPOT平均1.11-1.39乘POT LLM调用跨四个配置，86%的问题无需修复（初始POT成功），14%需要一次修复调用。

**Table 1**: Cross-model success rate (%)

**Table 2**: External replication on PLANBENCH BLOCKSWORLD

**Table 3**: DERAIL-550: success rate (%) on 550 injected errors per condition

**Figure 4**: DERAIL-550, headline conditions only

**Figure 5**: Delta(RePoT−PoT) per environment, in percentage points

**Figure 6**: Per-environment success rate vs problem complexity for gpt-5.4-mini-medium

**Figure 7**: One example per environment at small complexity

**Figure 8**: Paired recovery decomposition on the matched-difficulty subset

**Figure 9**: Cost vs accuracy, mean across the four closed-model configurations

**Figure 10**: Decomposition of REPOT's recovery on PUZZLEZOO-775

**Figure 11**: Per-complexity success rate on PLANBENCH BLOCKSWORLD

查看结构化数据

任务	指标	本文	基线	提升
PUZZLEZOO-775（封闭模型，reasoning/thinking=medium）	成功率	REPOT在gpt-5.4-mini-medium上96.9%	POT在gpt-5.4-mini-medium上86.3%	+10.6pp；跨四个配置平均+3到11pp
PUZZLEZOO-775（封闭模型，匹配预算比较）	REPOT vs POT-retry成功率差	Gemini +3.8pp（95% CI [+2.2, +5.4]），GPT-medium +0.3pp在噪声内，Claude −1.4pp在噪声内，GPT-mini −6.6pp（[−9.4, −3.7]）	POT-retry基线：运行POT，失败后从头s0运行POT第二次（无检查点，无前缀）	在reasoning/thinking-on模型上，REPOT机制贡献超越重采样边际
PLANBENCH BLOCKSWORLD（378实例，3-12块）	成功率（无thinking配置）	GPT-5.4-mini 64.3%，Claude Sonnet 4.6 91.3%，Gemini 3.5 Flash 100.0%	POT：GPT-5.4-mini 55.0%，Claude Sonnet 4.6 79.9%，Gemini 3.5 Flash 98.9%	+9.3pp，+11.4pp，+1.1pp；所有CI为正
DERAIL-550（注入错误恢复，550错误/条件）	恢复成功率	检查点条件在GPT-medium上大于等于40.4%，在Gemini上大于等于76.9%	非检查点基线在GPT-medium上3.1%，在Gemini上20.7%	约30-80pp间隔，显示检查点信息是负载恢复信号
PUZZLEZOO-775（成本分析，gpt-5.4-mini-medium，100问题子集）	平均LLM调用次数	REPOT平均1.11调用（86%问题1调用，14%问题2调用）	POT固定1调用	1.11倍成本，匹配POT-retry预算

局限与改进

局限性分析：作者承认的局限包括REPOT假设确定性验证器（谜题、规划、工具使用）；自由形式推理需要学习评分器（如过程奖励模型）。本文评估限于验证器支持的谜题和规划环境（PUZZLEZOO-775、PLANBENCH BLOCKSWORLD、DERAIL-550）。是否相同的可恢复执行抽象泛化到验证器支持的代理设置（带测试套件的编码代理、带模式检查的SQL代理、带页面状态验证器的浏览器自动化）是开放实证问题，本文未解决。单次修复预算：使用R等于1作为成本保守选择；多修复调用可能关闭长视界积木世界的尾部但本文未评估。匹配预算控制：PLANBENCH比较仅报告POT vs REPOT；本文未在PLANBENCH上运行POT-retry，因此表1的匹配预算主张未外部复制。统计范围：开源结果在120问题分层子集，小于封闭模型标题。ADAPTIVE REPOT是初步的：使用手选阈值（前缀分数小于0.15）；对前缀分数的敏感性扫描和替代调度器规则（如学习门控）留给未来工作。作者报告的负面发现包括：DERAIL前缀翻转：在Gemini和GPT (med)上，REPOT restart（从头s0重启）超越REPOT full（从验证状态s继续）（Gemini上82.4 vs 80.7，GPT (med)上94.5 vs 59.6）——间隔在GPT (med)上更大。PlanBench gpt-5.4-mini在c等于8和c等于11上为负Delta：REPOT在此两个复杂度上比POT低−8.3pp和−9.1pp。

独立分析的弱点

独立分析的弱点：首先，POT调用重采样损失：在gpt-5.4-mini-medium的100问题切片上，有5个问题POT成功但REPOT失败。全部5个共享相同签名：REPOT的初始POT调用返回空或不可解析计划，单修复调用无法桥接差距。这是采样方差，非机制弱点。其次，不完整计划停滞：初始POT调用发出9动作计划清洁重放但未达目标，修复调用无法在T等于4内扩展——这是genuine单次修复失败。再次，前缀条件可能有害：在DERAIL的受控中途错误设置上，从注入后状态继续有时混乱模型；从头s0的新鲜计划避免该陷阱。这显示在弱配置上，锚定修复于验证前缀尾部可能有害。最后，能力缩放失败模式：在PlanBench c等于8和c等于11，REPOT underperforms POT，因为POT基线准确率很低（33%和18%），REPOT从中途恢复的状态本身误导。单修复调用有时承诺扩展坏前缀。改进方向：空计划重试以关闭手工分析损失；自适应修复预算条件化于验证前缀分数；验证驱动的决策当验证前缀分数低时从头s0重启；扩展到其他验证器支持的代理设置（编码、SQL、浏览器自动化）；学习调度器规则而非手选阈值。

未来方向

未来研究方向：作者提出的方向包括空计划重试以关闭手工分析损失；自适应修复预算条件化于验证前缀分数；开源复制；更广泛基准（PDDLGym、ALFWorld）。基于成果可延伸的方向包括将可恢复执行抽象泛化到验证器支持的代理设置（编码代理带测试套件、SQL代理带模式检查、浏览器自动化带页面状态验证器）；学习调度器规则而非手选阈值；扩展到自由形式推理场景，需要学习评分器或过程奖励模型；探索多修复调用（R大于1）以关闭长视界问题尾部的成本效益；研究检查点信息与其他恢复机制的交互（如过程奖励模型、树搜索）；探索REPOT与其他规划方法（如分层规划、模块化规划）的组合。

复现评估

复现评估：代码在https://github.com/parsa-mz/RePot（Apache-2.0）开源：REPOT和ADAPTIVE REPOT代理、验证重放原语、四个环境、DERAIL装置、提示模板、CLI三个子命令（repot run / derail / judge）。PUZZLEZOO-775和DERAIL-550在CC-BY-4.0下发布；轨迹文件不重新分发但可从相同CLI复现。PUZZLEZOO-775（775问题）跨四个经典规划环境（汉诺塔8复杂度200问题、跳棋跳跃9复杂度225问题、过河4复杂度100问题、积木世界10复杂度250问题）在JSONL格式发布。实例schema包括problem_id、environment、complexity、显式initial_state和goal_state、oracle_plan、oracle_plan_length和natural_language_prompt。每个环境提供其验证器和目标谓词。所有方法（COT、POT、SC、REPOT）通过公共推理时控制器运行。控制器中介LLM与环境间的每次交互：构建提示、调用LLM、解析输出、然后要么提交整个计划到环境（POT、SC、COT）要么逐步通过验证器验证动作（REPOT）。这镜像Shojaee等人（2025）和Scholten等人（2024）提倡的将状态外化到权威模拟器的模式。控制器记录每次LLM调用的逐字模型提示和补全、每问题方法元数据、端到端延迟、提示和补全token计数、运行时异常。失败LLM调用（网络、JSON解析、沙箱超时）记录为runner_exception且问题对该方法视为未解决。数据可用性：PUZZLEZOO-775和DERAIL-550公开；PLANBENCH BLOCKSWORLD可从Valmeekam等人（2023a）获得。封闭模型（gpt-5.4-mini-medium、gemini-3.5-flash、claude-sonnet-4.6）通过API访问，需付费账户。开源模型（Gemma 4 26B、GPT-OSS 20B、Qwen 3.6 35B、Nemotron-3 Nano 30B）通过vLLM在单个NVIDIA H100 80GB GPU上服务。复现难度：中等。代码开源且文档化，数据公开，但封闭模型需API访问，开源模型需强GPU。实验设置（超参数、环境接口）在表4和附录H详细描述。跨三个种子的配对比较在表6报告，显示REPOT减POT在所有模型的所有种子上为正，指示相对稳定的结果。

论文图表

Figure 12: Verified-prefix-conditioned repair prompt

图展示验证前缀条件化的修复提示模板。两个主要块：稳定块（可缓存）在验证检查点标记上方：问题和目标。模型指示是编写Python代码，从当前验证状态输出包含最多K个原始动作的移动列表。动态块在验证检查点标记下方：模型看到已执行的P验证动作、最近验证动作（tail_T(P)，T默认为4）、当前验证状态s、合法动作、Blocked动作blocked(s)、验证器消息epsilon。标题说明验证检查点标记分隔可缓存的问题描述和每次调用动态状态。

这张图展示修复提示模板，帮助理解后缀修复调用的输入。它展示验证检查点信息（前缀、状态、错误）如何传递给模型以条件化修复调用。

Algorithm 1: REPOT— Recoverable Program-of-Thought

算法展示REPOT的完整伪代码。输入：问题、环境E、模型M、修复预算R。第1步：pi等于M POTPROMPT(s0, g)（单次POT）。第2步：(P, s, epsilon)等于REPLAY(E, s0, pi)（验证重放，式1）。第3步：如果ISGOAL(s, g)则返回P。第4步：结束如果。第5-11步：for r等于1 to R（从检查点的后缀修复）：pi'等于M REPAIRPROMPT(s0, g, s, P, epsilon)；(P', s, epsilon)等于REPLAY(E, s, pi')；P等于P concat P'；如果ISGOAL(s, g)则返回P；结束如果；结束for。第12步：返回P（部分；预算耗尽）。

这个算法是REPOT的完整形式化描述，对理解方法的技术细节至关重要。它精确描述三步流程（POT调用、验证重放、后缀修复）和修复预算的实现。