PaperlayerView exact revision on arXiv

Source-linked AI summary

REPOT: Recoverable Program-of-Thought via Checkpoint Repair

Parsa Mazaheri

arXiv:2605.30052v1cs.SEcs.AIcs.CL

TL;DR

One-shot Program-of-Thought plans can fail completely after a single illegal action, while existing fixes either cannot resume or incur branching costs. RePoT uses deterministic verified replay to preserve a trusted prefix and make one suffix-repair call, improving performance across several planning benchmarks while showing that checkpoint information is the key recovery signal.

  • Problem

    One-shot PoT cannot resume after a mid-rollout error, and tree-search alternatives incur branching costs even when the initial trajectory is mostly correct.

  • Method

    RePoT verifies a candidate action sequence deterministically until its first invalid transition, then asks the model to repair only the unverified suffix from the trusted state.

  • Results

    RePoT improves over PoT across PuzzleZoo-775 and PlanBench Blocksworld, while Derail-550 shows that checkpoint information—not the specific verified-prefix tail—is the load-bearing recovery signal.

  • Takeaways & Limitations

    RePoT is a low-cost middle ground between one-shot PoT and tree search for verifier-backed planning, but its generalization to other agentic settings remains open.

  • Takeaways & Limitations

    The evaluation is restricted to deterministic verifier-backed puzzle and planning environments, so generalization to coding, SQL, or browser agents remains unaddressed.

Abstract

from arXiv · show

One-shot Program-of-Thought (PoT) emits a Python program that prints a primitive-action plan; a single invalid action silently invalidates the trajectory. We introduce RePoT (Recoverable PoT): a deterministic verified replay that walks the plan through the environment to its first invalid transition, then one LLM call that resumes from the verified prefix. RePoT costs at most one extra LLM call on the ~14% of problems where PoT fails. RePoT beats PoT by +3 to +11pp across four closed-model configurations on PuzzleZoo-775 and peaks at 96.9% vs 86.3% on gpt-5.4-mini-medium; against the matched-budget PoT-retry baseline, RePoT wins decisively on Gemini (+3.8pp, 95% CI [+2.2,+5.4]), is within sampling noise on GPT-medium and Claude, and loses on GPT-mini -- a capability-scaling pattern we begin to address with Adaptive RePoT, a rule-based dispatcher that routes between suffix repair and a fresh PoT retry based on verified-prefix length (preliminary). We replicate on PlanBench Blocksworld (+1.1 to +11.4pp) and on four open-weights models (+3.3 to +20.0pp on three of four). On Derail-550, our controlled recovery benchmark, every condition with access to checkpoint information clears >=30% on GPT-medium and >=70% on Gemini, vs <=3.1% for error-only feedback -- showing that checkpoint information, not the specific verified-prefix tail, is the load-bearing recovery signal.

1 Introduction

RePoT makes one-shot Program-of-Thought planning recoverable by verifying actions, preserving the valid prefix, and repairing only the unverified suffix. Across planning benchmarks, it improves over PoT while using an extra LLM call only when the initial plan fails.

  • One-shot PoT can silently invalidate an entire trajectory when a single generated action is illegal.
  • RePoT runs PoT once, replays its actions deterministically, and either returns a verified goal-reaching prefix or repairs from the first failure boundary.
  • The verifier supplies the trusted state, while the model is asked only to repair the unverified suffix with one repair call.
  • +3 to +11pp: RePoT improves over PoT across four PuzzleZoo-775 configurations and also improves on PlanBench Blocksworld by +1.1 to +11.4pp.
  • DERAIL-550 shows that trusted checkpoint information is the load-bearing recovery signal, while the explicit verified-prefix tail adds a smaller, model-dependent benefit.

2 Background

The background identifies recoverable execution failures as a distinct target for checkpoint-based repair. RePoT addresses failures with long valid prefixes and mid-rollout missteps, while avoiding the costs of broad search or learned scoring when exact environment verification is available.

  • Planning traces often fail after a long valid prefix and a single mid-rollout misstep, creating a recoverable execution-collapse regime.
  • RePoT targets recoverable execution collapse rather than claiming to solve reasoning collapse in general.
  • Self-consistency and best-of-k methods spend O(k) LLM calls per problem, while tree-search methods branch during generation.
  • Process reward models require a learned scorer, whereas RePoT uses the environment itself as an exact, immediately available verifier.

3 Related Work

RePoT is positioned as per-trajectory recovery conditioned on a verified failure boundary, distinct from coordination checkpoints, mode routing, and benchmark infrastructure.

  • RePoT routes per trajectory after a verified failure boundary, unlike decoupled reasoning–observation methods that route between thinking modes per input.
  • Concurrent checkpoint methods target multi-agent coordination, while PlanBench supplies the PDDL-grounded planning evaluation used here.

4 Method

RePoT treats planning as deterministic execution over a verified environment: replay finds the maximal valid prefix and failure boundary, then a bounded repair policy resumes from the checkpoint or chooses a fresh retry. Its benefit depends on recoverable prefixes and can diminish when the prefix is empty or short.

  • 4.1 Problem setting: A planning task consists of an initial state, goal, and deterministic environment whose step function returns a next state and validity flag.
  • 4.2 Verified replay: Verified replay walks a candidate action sequence until the first invalid transition, returning the maximal valid prefix, boundary state, and verifier error without LLM calls.
  • 4.3 REPOT algorithm: RePoT returns the verified prefix if it reaches the goal; otherwise it issues a bounded suffix-repair call conditioned on the checkpoint.
  • 4.3 REPOT algorithm: RePoT’s recovery advantage is favorable when suffix repair succeeds more often than a fresh resample on the recoverable subset.
  • 4.4 Adaptive recovery policy: When the verified prefix is empty or very short, the checkpoint collapses toward the initial state and fresh POT retry can outperform anchored repair on weaker models.
  • 4.4 Adaptive recovery policy: Adaptive RePoT routes to fresh retry when the verified-prefix fraction is below 0.15 and otherwise uses suffix repair under the same R=1 budget.

5 Experimental Setup

The evaluation compares RePoT with several planning baselines across PuzzleZoo, PlanBench, and controlled recovery settings using closed-source and open-weights models. RePoT receives a matched-budget from-scratch retry control to isolate checkpoint-based recovery.

  • Benchmarks: PuzzleZoo-775 spans four classical planning environments with 775 stratified problems and controllable complexity.The environments are Tower of Hanoi, Checker Jumping, River Crossing, and Blocksworld.
  • Benchmarks: PlanBench Blocksworld contributes 378 instances spanning 3–12 blocks through an adapted PDDL-based interface.The adapter uses predicate states, four primitive operations, and partial-goal subset checking.
  • Benchmarks: DERAIL-550 injects one wrong action after an oracle plan reaches a checkpoint approximately one-third through each trajectory.The benchmark compares 11 recovery conditions, including RePoT’s three prefix ablations.
  • Models: The study evaluates four closed-model configurations and four open-weights models under deterministic sampling.Open-weights models run on one NVIDIA H100 80GB GPU via vLLM with extended thinking disabled.
  • Methods compared: POT-retry is a matched-budget control that makes a second from-scratch POT call after failure, unlike RePoT’s checkpoint-based repair.POT, POT-retry, and RePoT emit Python code, while COT and self-consistency emit prose plans.

6 Results

RePoT improves over POT across closed-model PuzzleZoo results and replicates gains on PlanBench and most open-weights models. Against matched-budget POT-retry, its advantage depends on model capability, while PlanBench does not externally test that matched-budget comparison.

  • 6.1 Headline cross-model accuracy: +2.7 to +10.6pp: RePoT beats POT on every closed model in PuzzleZoo-775.The largest gain is 96.9% versus 86.3% on gpt-5.4-mini-medium.
  • 6.1 Headline cross-model accuracy: +3.8pp on Gemini: RePoT beats matched-budget POT-retry, while GPT-medium and Claude are within sampling noise and GPT-mini loses by −6.6pp.The reported Gemini 95% CI is [+2.2, +5.4].
  • 6.2 Per-environment results: +9.2 to +17.2pp: RePoT’s gains concentrate in Blocksworld on every reasoning model, while Gemini River Crossing improves by +24.0pp.Hanoi and River Crossing are otherwise saturated by POT on most models at ≥99%.
  • 6.3 External replication: RePoT improves over POT on all three PlanBench Blocksworld models, with the largest gains at 4–6 blocks.The external replication uses no-thinking variants and reports only the POT-versus-RePoT comparison.
  • 6.3 External replication: The PlanBench replication omits POT-retry, so it validates raw RePoT lift but not the matched-budget claim from Table 1.This is an explicit limitation of the external replication.
  • 6.5 Multi-seed variance: The REPOT−POT improvement is positive on every seed for all three reasoning-thinking-on configurations.Per-seed deltas range from +1 to +10pp.
  • 6.4 Open-source replication and capability scaling: +3.3 to +20.0pp on three of four open-weights models: RePoT improves over POT, while Nemotron underperforms POT by 15pp.The Nemotron result is associated with a predicted capability-floor failure.
  • 6.4 Open-source replication and capability scaling: Across model-environment cells, longer verified prefixes correlate positively with the RePoT−POT-retry success-rate delta.The reported regression slope is +35.

7 Mechanism Analysis

DERAIL-550 identifies checkpoint information as the decisive recovery signal, while the specific verified-prefix tail provides a smaller and model-dependent effect. RePoT costs 1.11–1.39× POT calls and can fail when repair budgets are exhausted or no prefix exists.

  • 7.1 Checkpoint information is the load-bearing signal: Checkpointed recovery conditions clear 30% on GPT-medium and 70% on Gemini, whereas error-only feedback reaches only 3.1% and 20.7%.The benchmark compares 11 recovery methods over 550 injected errors per model.
  • 7.2 Capability scaling: The positive slope in Figure 3 relates verified-prefix fraction to the RePoT−POT-retry success delta across model-environment cells.The x-axis is a proxy for q, and the y-axis is the success-rate delta in percentage points.
  • 7.1 Checkpoint information is the load-bearing signal: +3.8 / +5.8pp: RePoT full beats RePoT no-prefix on Gemini / GPT-medium, but RePoT restart beats full on both models.Restart reaches 94.5 versus 59.6 on GPT-medium, indicating that retaining the verified-prefix tail can hurt.
  • Cost: 1.11–1.39× POT LLM calls: RePoT’s average call cost across the four configurations.The repair budget is one additional LLM call after verified failure.
  • Failure modes: Repair-budget exhaustion is the dominant RePoT failure on hard Blocksworld, often after an empty initial POT plan leaves no prefix.The authors identify empty-plan retry as future work.

8 Discussion

RePoT helps most when failed PoT plans contain long valid prefixes, while fresh retries can be better when failures occur immediately or models cannot produce useful prefixes. DERAIL-550 and matched-budget comparisons identify checkpoint state as the main recovery signal and motivate adaptive routing and further evaluation.

  • RePoT’s lift concentrates on plans with long valid prefixes, is negligible when failure occurs at the first action, and is a no-op in saturated easy regimes.On Gemini Hanoi, PoT already reaches 99.5%, while first-action failures reduce replay to a restart from the initial state.
  • Checkpoint information, rather than textual error feedback or the specific verified-prefix tail, is the load-bearing recovery signal.The within-RePoT comparison finds the prefix tail provides a smaller, model-dependent additional benefit.
  • +0.3pp and +3.6pp are RePoT’s gains over POT-retry on gpt-medium and Gemini, whereas POT-retry leads by 1.4pp and 6.6pp on Claude and gpt-mini.The comparison supports a capability-scaling pattern: useful valid prefixes favor repair, while weaker models benefit more from fresh independent samples.
  • Adaptive repair based on verified-prefix fraction and broader benchmarks are identified as future work.The paper specifically lists empty-plan retry, adaptive repair budgets, open-source replication, and PDDLGym and ALF-World evaluations.

9 Conclusion

RePoT combines verified replay with bounded suffix repair and improves recovery over one-shot PoT while using a matched-budget strategy that is model-dependent. DERAIL-550 shows that checkpoint information is the central recovery signal, with broader generalization left open.

  • RePoT combines deterministic verified replay with one bounded suffix-repair call, adding checkpoint-based recovery to PoT.The method is presented as a structural addition rather than tree search.
  • ∼60pp separates checkpointed from no-checkpoint conditions in DERAIL-550, establishing the load-bearing role of checkpoint information.The full 11-condition table appears in Table 3; Figure 4 shows headline conditions only.
  • RePoT costs one extra LLM call on the ∼14% of problems where PoT initially fails, while other problems run at PoT cost.Against POT-retry, RePoT wins on Gemini, is within sampling noise on GPT-medium and Claude, and loses on GPT-mini.
  • Generalization to verifier-backed coding, SQL, and browser-automation settings remains future work.

Limitations

The paper’s evaluation is limited to deterministic-verifier puzzle and planning environments, with several open questions about repair budgets, prefix conditioning, statistical scope, and adaptive routing.

  • Scope: Verifier-backed scope limits REPOT’s evidence to puzzle and planning environments; generalization to other verifier-backed agents remains untested.Free-form reasoning would require a learned scorer, and coding, SQL, and browser-agent settings are explicitly left open.
  • Repair budget: R = 1 is a cost-conservative repair budget, so multi-call repair that may help long-horizon Blocksworld is not evaluated.The limitation concerns the chosen repair budget rather than the verified-replay mechanism itself.
  • Conditioning: Prefix-tail conditioning is model-dependent and can hurt in controlled mid-rollout errors, despite checkpoint state remaining the load-bearing signal.On GPT-medium, REPOT restart reaches 94.5% versus 59.6% for REPOT full.
  • Negative cells: −8.3pp and −9.1pp REPOT versus POT occur for GPT-mini at PlanBench complexities c = 8 and c = 11.These cells occur where POT base accuracy is low and repair can extend a misleading prefix.
  • Statistical scope: PlanBench does not include POT-retry, and the open-source study uses a smaller 120-problem subset than the closed-model headline evaluation.Thus the matched-budget comparison is not externally replicated on PlanBench.
  • Adaptive routing: Adaptive RePoT uses a hand-picked prefix-fraction threshold, while sensitivity sweeps and alternative dispatcher rules remain future work.The threshold is ϕ < 0.15.

G Cost decomposition appendix

The appendix decomposes REPOT’s cost and gains: most problems incur no repair, while the remaining repairs add modest average cost and combine fresh resampling with suffix repair.

  • Cost: 86% of problems require no repair, with REPOT cost identical to POT at a mean of 1,820 tokens.Verified replay confirmed that the initial POT plan reached the goal on these problems.
  • Cost: 14% of problems trigger one suffix-repair call, costing 1.4–1.7× POT per problem.The repair prompt is shorter than the initial prompt but requires additional reasoning at the failure boundary.
  • Cost: 1.06× POT is REPOT’s aggregate cost on the 100-problem stratified slice.The aggregate includes both no-repair and one-repair runs.
  • Cost: 1.11–1.39 LLM calls per problem is REPOT’s closed-model average, matching the POT-retry budget.The same accounting covers REPOT and Adaptive RePoT across 775 problems.
  • Recovery decomposition: REPOT’s recovery decomposition separates fresh POT resampling from suffix repair after a doubly failed initial attempt.Figure 10 labels these as the second-attempt and mechanism contributions, respectively.
  • Failure analysis: Five headline failures share an empty or non-goal-reaching initial REPOT plan that the single repair call could not bridge.Four are PoT-call resampling losses, while one is an incomplete-plan stall.
  • Failure analysis: −8.3pp and −9.1pp REPOT versus POT occur at PlanBench c = 8 and c = 11, where repair sometimes extends a misleading prefix.The appendix reports these negative cells transparently as a limitation of single-call repair.
  • Complexity: Figure 11 reports per-complexity success rates, with REPOT’s gains concentrated in the mid-complexity band.The two negative GPT-mini cells appear at c = 8 and c = 11.

N Open-source results: routing, cost, and capability scaling

On open-weight models, Adaptive RePoT routes mainly to fresh retries rather than suffix repair, with mixed performance and higher cost than POT; capability strongly shapes the routing pattern.

  • Results: Adaptive RePoT achieves 60.0%, 64.2%, 62.5%, and 13.3% on Gemma, GPT-OSS, Qwen, and Nemotron-3, respectively.These rates use the same 120-problem stratified subset.
  • Routing: On Gemma, GPT-OSS, and Qwen, most non-initial-success cases route to fresh retry, while suffix repair activates on only 1–3 of 120 problems.This differs from closed thinking-on models, where suffix repair is the dominant value channel.
  • Routing: Nemotron-3 routes mostly to short-prefix retries and has a 3% rescue rate.The routing pattern is presented as evidence for a capability-floor interpretation.
  • Cost: Open-source REPOT costs 1.5–2× POT in mean total tokens on Gemma, GPT-OSS, and Qwen, with 40–110 seconds wall-clock per problem.The closed-model range is 1.06–1.4×, providing a cost comparison across settings.
  • Capability scaling: The capability-scaling analysis relates REPOT−POT-retry performance to the mean verified-prefix fraction of failed initial POT plans.This regression is reported across model–environment cells.
  • Routing: Figure 13 encodes Adaptive RePoT routing distributions across four open-source models, revealing distinct branch profiles.The three workable rows are dominated by initial success and fresh retry, whereas Nemotron-3 differs markedly.
Loading 2605.30052v1…