Plan-and-Patch: Diffusion Language Models for Agentic Planning

Motivation

• Planning coordinates subgoals, tool use, and intermediate outcomes, but environmental changes, unexpected tool results, or failed actions can invalidate plans.Agents must generate plans and revise them in response to environment feedback.Source: §1 · p. 3

Plan representation

• The structured plan representation makes subgoals and executable steps explicit, providing meaningful units for revision that remain compatible with preceding and subsequent context.The plan format’s performance can depend on both representation and planner–executor pairing (Zambrano et al., 2026).Source: §1 · p. 3

Plan-and-Patch

• Because revisions often affect only part of a plan, Plan-and-Patch models repair as infilling the affected region while preserving the prefix and suffix.This contrasts with plan-and-act agents that commonly revise globally.Source: §1 · p. 3
• A single diffusion planner generates complete structured plans and infills selected regions using repair feedback, while an executor translates steps into actions and selects regions after failures.The preserved surrounding plan text remains fixed during repair.Source: §1 · p. 3, Figure 1 · p. 4

Evaluation

• On ALFWorld and TextCraft, diffusion and AR had similar observed plan-generation success, while diffusion cut mean latency by 39–46%; on Natural Plan, diffusion repair success was 53.7% versus AR’s 27.0%.Natural Plan was evaluated without task-specific training.Source: §1 · p. 4

Contributions

• The data pipeline combines synthetic repairs from structured perturbations of verified plans with naturally occurring execution failures and successful trajectories for joint training.The training recipe uses objective-specific block-size sampling and decoding, and analyzes plan representation, executor choice, and repair-region selection.Source: §1 · p. 4

Diffusion language models and agents

• Diffusion models have been studied as world models and ReAct-style agents, while matched fine-tuning work compares diffusion and AR agents; this work instead studies plan generation and repair through feedback-guided infilling.Prior agent studies report retry loops and imprecise tool-call formats as failure modes.Source: §2 · pp. 4–5

Plan repair and program repair

• Plan-repair approaches vary in scope, from rewriting suffixes or affected subgraphs to localizing constraint violations; this evaluation fixes failed plans and repair regions across planners and separately assesses region selection.Controlled replay helps distinguish plan changes from execution variation.Source: §2 · p. 5
• Program repair uses test failures for fault localization and validation, while diffusion infilling supports replacing spans of different lengths and motivates feedback-guided plan repair.AR infilling can use fill-in-the-middle serialization or training to condition on both surrounding contexts.Source: §2 · p. 5

Diffusion models for planning

• Diffusion planning has been explored for continuous-control trajectories, discrete dependency-rich tasks, and graph planning; Plan-and-Patch applies generation and repair to interactive environments.It uses execution history for region selection and repair feedback for infilling.Source: §2 · p. 5

Structured plans

• A structured plan is a goal with an ordered hierarchy of subgoals and executable steps; each leaf step specifies an action, arguments, and an expected observation.Subgoals and steps have identifiers locating contiguous, addressable spans in the serialized plan.Source: §3 · p. 6

Masked diffusion language models

• Autoregressive models predict tokens left to right, whereas masked diffusion models reconstruct independently masked target tokens from surrounding context.Training samples a uniform mask rate and minimizes a masked-token objective over the resulting corruption.Source: §3 · pp. 6–7

Decoding schedules

• Generation uses confidence-based parallel unmasking in left-to-right blocks; repair jointly infills selected spans with a threshold relaxed near reliable positions.Resolved tokens remain fixed during decoding.Source: §3 · p. 7

Repair decoding

• Repair replaces each selected span with a padded masked-token canvas and ends the replacement at the first deletion token, allowing different replacement lengths.The AR baseline generates replacements in one left-to-right sequence using fill-in-the-middle serialization conditioned on the preserved prefix, suffix, and repair feedback.Source: §3 · p. 7

4 The Plan-and-Patch Framework

• The framework pairs a diffusion planner that generates and repairs plans with a separate executor that translates steps into environment actions and supplies repair feedback after failure.The executor selects a repair region using the plan, execution history, and environment feedback; the planner infills that region while preserving the surrounding plan text.Source: §4 · p. 7

4.1 Plan generation and repair

• Repair replaces a selected plan region using its preserved prefix and suffix plus repair feedback; replacements may change length, and multiple spans retain their order and intervening text.The executor can select steps or abstain; failure may be observed at a different step from the one requiring repair.Source: §4.1 · p. 8

4.2 Reference plans and repair examples

• Reference plans store actions, arguments, and observed feedback as leaf steps grouped into subgoals by domain rules; generation-only planners’ failures and verified-plan perturbations supply repair examples.An LLM rewrites only reasoning and intents, with invalid rewrites reverted; both model families receive the same generation and repair examples.Source: §4.2 · pp. 8–9

4.3 Joint training and decoding

• Generation and repair are jointly trained from each planner’s original checkpoint, with separate block-size distributions emphasizing short generation blocks and large repair blocks.Generation assigns 61.2% of sampling weight to blocks of at most 16 tokens, while repair assigns 49.0% to the 4,096-token block.Source: §4.3 · p. 9

5.1 Experimental settings

• Evaluation covers household tasks in ALFWorld and dependency-constrained crafting in TextCraft, with one repair attempt followed by execution from the initial state.Generation uses 134 ALFWorld and 100 TextCraft test tasks; history-based repair uses 126 and 49 failures, respectively.Source: §5.1 · pp. 10–11

5.2 Plan quality and latency

• 39–46% lower mean plan-generation latency accompanies similar observed generation and repair performance, with AR slightly ahead and differences of at most 3 percentage points on the trained benchmarks.Latency uses synchronized, unbatched bf16 decoding on one A100; prompt construction, parsing, and environment execution are excluded.Source: §5.2 · p. 11, Figure 5 · p. 12
• On Natural Plan, AR has higher generation success, while diffusion nearly doubles repair success; both judges agree on the rankings, and diffusion’s repair advantage is concentrated in trip planning.Natural Plan evaluates travel and scheduling plans without task-specific training.Source: §5.2 · pp. 11–12

5.3 What limits execution and repair?

• Reference-assisted region selection exceeds history-based selection by 12 percentage points for diffusion and 8.6 for AR on the same 175 eligible failures.Repair feedback is fixed across the comparison.Source: §5.3 · p. 12
• Under Qwen3-8B, prose plans improve generation success by 17.9–22.4 percentage points on ALFWorld and 6–12 on TextCraft, but diffusion’s repair success is lower than with delimited plans.Diffusion’s reference-assisted repair success is 21.3% versus 28.4% on ALFWorld and 5.0% versus 15.5% on TextCraft; AR has higher prose-plan repair success in both environments.Source: §5.3 · pp. 12–13
• Diffusion solves 23/134 ALFWorld and 13/100 TextCraft tasks that AR fails; leaf-step failures are the most common stopping reason among tasks failed by only one planner.Cooling favors AR, cleaning favors diffusion, and invalid-action limits are also frequent in ALFWorld.Source: Table 3 · p. 13, §5.3 · p. 13

• Diffusion reduces mean plan-generation latency by 39–46% on ALFWorld and TextCraft, where the planners achieve similar observed generation success.Source: §6 · p. 13
• History-based repair enables recovery without reference plans, with higher pooled success for autoregressive planners.Source: §6 · p. 13
• Without task-specific training on Natural Plan, autoregressive planners achieve higher generation success, while diffusion achieves higher repair success.Source: §6 · p. 13
• Future work includes learning repair-region selection and infilling from execution feedback, adapting repair and decoding to uncertainty, and extending to longer horizons while maintaining local–global consistency.Source: §6 · p. 13

• Section A.1 defines the data and evaluation populations.Source: A Supplementary Material · p. 20
• Section A.2 reports the complete primary results, while Section A.3 collects representation, executor, region-selection, Natural Plan, and long-horizon analyses.Source: A Supplementary Material · p. 20
• Section A.4 records training, decoding, and prompt details.Source: A Supplementary Material · p. 20

• ALFWorld combines household navigation and manipulation, whereas TextCraft requires dependency-constrained crafting.Source: §A.1 · p. 20
• Natural Plan contains trip, meeting, and calendar scheduling problems, with programmatic validators checking completed plans against task constraints.Source: §A.1 · p. 20
• ScienceWorld is used only for the long-horizon generation analysis in Section A.3.4.Source: §A.1 · p. 20

• Task identity separates ALFWorld and TextCraft into train-gen, train-rep, dev, and test splits; primary interactive evaluation uses test.Train-gen supplies complete-plan targets, while dev determines training convergence.Source: §A.1.1 · p. 20
• Generation-only DreamReasoner-8B and Qwen3-8B checkpoints are trained separately per environment, and both model families use the same task splits and training examples.Source: §A.1.1 · p. 20
• Table A.1 covers task splits and repair-training examples, while Table A.2 covers reference-plan candidate counts and execution-based success.The captions specify that task counts precede reference-plan execution filtering, and verified train-gen and train-rep references supply generation and repair targets, respectively.Source: Table A.1 · p. 20, Table A.2 · p. 21
• Reference plans use expert demonstrations for ALFWorld and a deterministic backward recipe-dependency solver for TextCraft, with actions replayed to record observations and form ordered leaf steps.Claude Sonnet 5 rewrites reasoning and intent fields while preserving actions and arguments; invalid rewrites fall back to the original plan, and candidates require positive terminal reward under verification execution.Source: §A.1.1 · p. 20
• Repair training combines failed plans with execution histories and first failure observations, plus structured perturbations to parsed-plan fields.A reference-assisted judge selects the smallest addressable failure-associated region, whose replacement target comes from the verified reference; perturbations that alter text outside the region or duplicate remaining prompt text are rejected.Source: §A.1.1 · p. 21
• Claude Sonnet 5 serves once as the reference-assisted judge, receiving the goal, failed plan, execution history, failure observation, and reference plan to identify the smallest failure-explaining step set.Source: §A.1.1 · p. 21

A.1.2 Interactive evaluation populations

• 148 ALFWorld and 71 TextCraft failed plans form the primary reference-assisted repair populations, including plans without a usable repair region, which count as unsuccessful.A task failed by both planners contributes two examples.Source: §A.1.2 · p. 21
• Each failed plan gets one repair attempt, and the repaired plan is executed from the task’s initial environment state.Reported repair success is terminal task success after repair and restart.Source: §A.1.2 · pp. 21–22
• Diffusion–AR differences in observed success are at most three percentage points in generation and reference-assisted repair.Figure A.1 covers 134 ALFWorld and 100 TextCraft generation tasks, and pooled failed plans for repair.Source: Figure A.1 · p. 22

A.2 Complete primary results

• Table A.3 compares generation outcomes on the same test tasks and reference-assisted repair outcomes on pooled failed plans; Figure A.1 plots the results.Repair comparisons may include two failed plans from one task.Source: Table A.3 · p. 22, §A.2 · p. 22
• 95% confidence intervals for the diffusion-minus-AR generation difference are [−11.6, 8.6] percentage points on ALFWorld and [−13.5, 7.5] on TextCraft.These paired normal-approximation intervals describe held-out task variation conditional on the trained checkpoints and recorded execution outcomes.Source: §A.2 · p. 22
• Mean generation latency is 14.3 seconds on ALFWorld and 21.7 on TextCraft for Diff-Plan, versus 23.3 and 40.2 seconds for AR-Plan.Measurements use synchronized, unbatched bf16 decoding on one A100 and exclude prompt construction, parsing, and environment execution.Source: §A.2 · p. 22

A.2.1 Shared and model-exclusive failures

• Across ALFWorld and TextCraft, both planners share failures on many tasks, while ALFWorld task-family outcomes differ: cooling has more diffusion-only failures (9 versus 2), and cleaning has more AR-only failures (7 versus 3).Both planners fail on 12/18 light-inspection tasks and 10/17 two-object placement tasks, versus 3/24 simple placement tasks; these are descriptive comparisons on small subsets.Source: §A.2.1 · p. 23, Table A.4 · p. 23

A.2.2 Worked repair and preservation

• After reference-assisted repair, completed-step text is parsed and preserved unchanged in 40% and 38% of ALFWorld plans for diffusion and AR, and 55% and 74% of TextCraft plans.The analysis covers failed executions with at least one completed step; repaired plans are executed from the initial state.Source: §A.2.2 · p. 25, Figure A.3 · p. 26

A.3.1 Representation and executor

• With Qwen3-8B as executor, prose plans raise ALFWorld success from 44.0% to 61.9% for Diff-Plan and from 45.5% to 67.9% for AR-Plan.Holding plan text fixed, Sonnet 5 achieves higher success than Qwen3-8B for both planners and representations.Source: §A.3.1 · p. 26, Table A.7 · p. 26

A.3.2 Repair from execution history

• History-based region selection lowers repair success on ALFWorld and increases it on TextCraft for both planners relative to reference-assisted selection.The comparison holds repair feedback fixed; history-based selection is evaluated only where a judge supplies a step-level reference target.Source: §A.3.2 · p. 27, Table A.9 · p. 27

A.3.3 Natural Plan generation and repair

• Exact replacement recovery on Natural Plan is 22.7% for Diff-Plan and 5.0% for AR-Plan.The validator and judges agree on model ordering; the aggregate repair advantage is concentrated in trip planning, and Diff-Plan has higher validator acceptance under each of five constructions.Source: §A.3.3 · pp. 28–29

A.3.4 Long-horizon generation in ScienceWorld

• ScienceWorld parser acceptance for Diff-Plan falls from 74.7% in the shortest reference-plan bin to 7–9% at 28 or more steps; pooled acceptance is 34.3% for Diff-Plan and 73.8% for AR-Plan.Of 758 rejected generations, 754 reach the generation limit without closing the plan hierarchy; rejected outputs also contain repeated actions.Source: Figure A.6 · p. 30, §A.3.4 · p. 30

A.4.1 Training and decoding

• ALFWorld and TextCraft planners are jointly fine-tuned on generation and repair with one training seed; reported evaluation uncertainty excludes variation across training seeds.Diffusion repair uses a padded canvas across selected spans, while the AR decoder generates one token per forward pass using a key–value cache.Source: §A.4.1 · pp. 30–31

A.4.2 Executor behavior; A.4.3 Plan representation and prompts

• The Qwen3-8B executor follows planned leaf steps and stops at success, environment failure, action or progress limits, 60 leaf steps, or 1,000 episode tokens; prompts specify structured-plan and repair inputs.The repair prompt supplies the goal, failure explanation, expected and observed outcomes, and preserved plan context, requesting only corrected editable content.Source: §A.4.2 · p. 31, §A.4.3 · p. 31