RePoT recovers from a failed LLM-written plan by replaying actions through the real environment to the first illegal step, then asking the model to repair only the broken suffix from the verified state. Recovery from injected mid-plan errors jumps ~60 pp over text-only error feedback.
You’ve shipped a coding agent that drafts a 12-step plan and runs each step against your test suite. Step 9 fails. Today you either regenerate the whole plan or ask the model to critique its own mistake and try again, which is the Reflexion family of fixes. Both throw away the eight steps that actually worked. The dominant alternative, Program-of-Thought (PoT), runs the model’s plan all the way through and reports pass/fail with no notion of a recoverable midpoint. RePoT is the structural fix: keep the prefix the verifier already blessed, only ask the model to write a new tail.
The core idea is to make the environment, not the model, own the trusted state. A normal Program-of-Thought (PoT) call asks the model to emit a Python program that prints a list of primitive actions; you run the whole list and either hit the goal or you don’t. RePoT inserts a deterministic step in between called verified replay: walk the actions through the environment one at a time and stop at the first illegal transition. That gives you three things for free: the longest valid prefix, the exact state at the failure boundary, and the verifier’s error message.
If the prefix already reached the goal, you’re done. Otherwise you make exactly one more LLM call, the suffix-repair call, conditioned on the verified state plus the last few good moves. The repair budget is fixed at one extra call, so on the ~86% of problems where the first plan works you pay normal Program-of-Thought (PoT) cost; only the failing 14% pay double. A preliminary Adaptive RePoT dispatcher adds one rule: if the verified prefix is shorter than 15% of the plan, ignore it and do a fresh retry from scratch instead of anchoring on a near-empty prefix.
plan = llm(pot_prompt(s0, goal))
prefix, state, err = replay(env, s0, plan) # deterministic, no LLM
if is_goal(state, goal):
return prefix
suffix = llm(repair_prompt(s0, goal, state, prefix[-4:], err))
prefix2, state, _ = replay(env, state, suffix)
return prefix + prefix2
The standard fix when an LLM plan fails is to ask the model to critique its own attempt in text and try again. RePoT shows the opposite: skip the self-critique, hand the model the verified environment state at the failure boundary, and let it resume from a trusted checkpoint. The cleanest evidence is the controlled Derail-550 ablation where the only thing that varies is whether the model sees verified state or just an error string.
On Derail-550, every condition that sees verified checkpoint state recovers at ≥30% on GPT-medium and ≥70% on Gemini. Conditions that see only an error message sit at ≤3.1% and ≤20.7%. That ~60 pp gap is the load-bearing result: the checkpoint, not the error text, is what makes recovery work. Secondary findings line up behind it:
•
On the headline PuzzleZoo-775 suite, RePoT beats Program-of-Thought (PoT) by +3 to +11 pp across four closed-model setups, peaking at 96.9% vs 86.3% on a reasoning-enabled GPT config.
•
Against a matched-budget control that just retries Program-of-Thought (PoT) from scratch, RePoT wins decisively on Gemini (+3.8 pp), ties on the two mid-tier configs, and loses by 6.6 pp on the weakest closed model. The mechanism only helps when the first plan leaves a useful prefix.
•
Replication on PlanBench Blocksworld gives +1.1 to +11.4 pp; on four open-weights models, +3.3 to +20.0 pp on three of four, with the weakest one regressing.
•
A subtle wrinkle: within the checkpointed conditions, a variant that restarts from the initial state (keeping the verifier info but discarding the resume point) sometimes beats the full prefix-anchored version. The checkpoint information is what matters; anchoring on the exact failure-boundary state can confuse weaker models.
Reach for this when you’re shipping any agent whose plan runs through a deterministic verifier: a code agent with a test suite, a SQL agent with a schema checker, a browser agent with page-state assertions. Instead of regenerating from scratch on failure, replay the proposed actions yourself, stop at the first one that fails, and send the model back the verified state plus the verifier’s error. One extra call, bounded cost, and your prefix work is preserved.
Code is at GitHub under Apache-2.0, including the RePoT agent, the verified-replay primitive, four planning environments, the Derail-550 harness, and prompt templates. Both PuzzleZoo-775 and Derail-550 are released as evaluation suites under CC-BY-4.0.
Trust the verified environment state, not the model’s self-critique. This pays off when your base model is strong enough to produce a useful prefix before failing. On weaker models a fresh retry beats anchoring on a broken attempt, which is why a length-based dispatcher matters as much as the repair call itself.
•
The whole approach assumes a deterministic, fast verifier. Domains where checking a step is as expensive as generating one, or where validity is fuzzy, don’t fit.
•
Capability-scaling cuts both ways: on the weakest model tested, RePoT lost to plain Program-of-Thought (PoT) by 15 pp because short or empty prefixes mislead the repair call. You need the dispatcher, or a strong enough base model, to avoid this regression.
•
The within-prefix ablation is genuinely mixed: a variant that discards the resume point sometimes beats the full method. The headline mechanism is the checkpoint info, not specifically resuming from the failure-boundary state, so framing this as “resume execution” oversells what’s actually load-bearing.