Iterative Deployment Improves Planning Skills in LLMs

TL;DR

LLMs are notoriously bad at multi-step planning, and the usual fix — reinforcement learning with a hand-designed reward — is expensive and brittle for open-ended tasks. This paper shows a cheaper path: take a model, let it attempt a fixed pool of planning problems, keep only the traces that verifiably solved the problem, fold those into the training set, and fine-tune the next generation. Repeat. Within five generations a 4B model more than doubles (and sometimes 5בs) the number of tasks it can solve, and crucially it starts finding much longer plans than it ever could before — evidence of real generalization, not just formatting tricks. The kicker is theoretical: they prove this supervised-fine-tuning-on-valid-traces loop has the exact same gradient direction as REINFORCE (classic policy-gradient RL) with a binary reward. The unsettling implication is that this loop is already happening in the wild — GPT-3.5 trained on web text that included curated GPT-3 outputs — meaning every deployed model is being shaped by an implicit, uncontrolled reward function defined by which outputs users chose to publish.

Problem & Motivation

Two pains collide here.

Pain 1: LLMs can’t plan. Ask a model to solve a Sokoban puzzle or rearrange a stack of blocks to a target configuration, and it falls apart as soon as the solution requires more than a handful of steps. Prior work (Valmeekam et al., Stechly et al.) showed that chain-of-thought helps a little but does not generalize — models that handle short-horizon problems collapse on longer-horizon ones. You can fix this with RL, but designing a reward function for “good plan” across open-ended tasks is genuinely hard, and RL training (PPO, GRPO) is finicky and compute-hungry.

Pain 2: nobody is watching the feedback loop that already exists. Here’s the observation that makes this paper more than another self-improvement trick. Every frontier model is trained on web data. That web data increasingly contains outputs from previous models — and not a random sample of them. When a user gets a good answer from ChatGPT, they paste it into their codebase, their blog, their Stack Overflow reply. Bad answers get deleted. So the web acts as a giant, invisible curation filter: only the outputs that satisfied a human survive to become training data for the next generation. This is not hypothetical — GPT-3.5 was trained on web data that included curated GPT-3 text; GPT-4 on GPT-3.5 and GPT-3 text. With agent traces about to flood the web, this loop is accelerating.

The paper asks: what does this loop do to model behavior, and what is it equivalent to? They isolate the phenomenon in a clean lab — classical planning, where a deterministic verifier can say “valid plan / invalid plan” with zero ambiguity — and study it.

What’s New (Core Contribution)

• The “iterative deployment” framing as a first-class training regime. Before: self-improvement methods like STaR were studied as intentional training procedures you run on purpose. Now: the same loop is reframed as an unintentional, outer-loop process that happens whenever models are deployed and their curated outputs re-enter the training set. The novelty is the lens, plus the off-policy twist (see below).

• A theorem: deploy-curate-retrain ≡ REINFORCE with a binary reward. Before: people had a vague intuition that “training on your own good outputs is RL-ish.” Now: there’s a proof. Supervised fine-tuning on only the valid traces produces a gradient in the identical direction to REINFORCE with reward = 1 for valid, 0 for invalid. And mixing in valid traces from older generations is shown to equal REINFORCE augmented with importance-weighted off-policy contributions. This turns a hand-wave into a precise statement.

• Empirical proof of genuine generalization, not memorization. Before: it was unclear whether self-training just teaches surface tricks (format the output right, avoid syntax errors). Now: plan-length distributions show later generations discover plans far longer than anything the base model could produce — Blocksworld base tops out near 20 steps, generation 5 reaches 35+. That’s out-of-distribution generalization.

• Curation is the load-bearing ingredient — and it’s cheap. Before: model-collapse work (Shumailov et al.) said training on your own outputs degrades models. Now: they show the curation step is exactly what separates collapse from improvement, and that curated training uses a fraction of the data (356 traces vs. 4017) while delivering 94% better performance. The contrast with model-collapse assumptions is the bridge between two literatures.

• An AI-safety alarm. Because the reward is implicit and defined by whatever users chose to publish, it can silently conflict with the explicit safety training baked into the model. Nobody specified this reward; it could push the model in directions that clash with alignment. They flag studying these implicit rewards as a community priority.

How It Works (Technically)

The mechanism is a loop over “generations” of the model. Call the starting model M₀ (the base / generation 0). One turn of the loop produces Mₙ₊₁ from Mₙ:

1. Deployment & trace collection. Take a fixed pool of planning tasks D_tasks (no solutions provided). Prompt the current model Mₙ on every task. For task x, the model samples a trace y from its policy πθₙ(y|x). A “trace” = the chain-of-thought reasoning plus the proposed plan. This simulates real deployment: the model attempts things users threw at it.

2. Validation. Run every trace through a deterministic external validator V(x, y) → {true, false}. In this paper V is VAL, the standard PDDL plan checker used in planning competitions — it mechanically verifies whether the plan actually reaches the goal. Keep only valid traces: D_valid = {(x,y) | V(x,y) = True}. In early generations the vast majority of outputs are invalid and get thrown away.

3. Curation & aggregation. Union the current generation’s valid traces with valid traces from all previous generations: T_{n+1} = ⋃_{i=0}^{n} D_valid^(i). Aggregating across generations is what prevents catastrophic forgetting and (they argue) staves off model collapse. Then a second curation pass enforces one trace per task: if several generations solved the same task, keep only the highest-quality solution — defined here as the shortest plan, ties broken by fewest reasoning tokens. (They tried keeping multiple traces or breaking ties randomly; both hurt performance.)

4. Supervised fine-tuning. Fine-tune Mₙ on T_{n+1} with plain next-token-prediction (the standard SFT objective) to get Mₙ₊₁. In practice they fine-tune the base Qwen3-4B fresh each time using the accumulated traces (rather than stacking LoRA adapters), with LoRA (rank 16, alpha 32) so it’s cheap.

The beautiful part is that nobody designs a curriculum. The model + validator build one automatically. Generation 0 can only solve easy tasks (1-box Sokoban). Those become training data. Generation 1, having internalized the easy solutions as “building blocks,” can now solve some 2-box tasks. Those become training data for generation 2. The frontier of solvable difficulty creeps outward on its own.

Why “train on valid traces” = reinforcement learning (the math, demystified)

This is the theoretical heart. Let me translate the proof of Proposition 1.

REINFORCE (Williams, 1992) is the simplest policy-gradient RL algorithm. Its goal is to maximize expected reward J(θ) = E[R(x,y)] over traces the policy produces. The gradient that tells you how to nudge the weights is:

∇J(θ) = E[ R(x,y) · ∇log πθ(y|x) ]

In plain English: “for each trace, push the model’s weights in the direction that makes that trace more likely, scaled by how much reward it got.” A trace with reward 1 gets reinforced; a trace with reward 0 contributes nothing.

Now suppose the reward is binary — 1 if the plan is valid, 0 if not. Then R(x,y) is a light switch: invalid traces (R=0) drop out of the sum entirely, and the gradient becomes a simple average of ∇log πθ(y|x) over only the valid traces.

Compare that to supervised fine-tuning. SFT minimizes the loss L_SFT = −(1/N₊) Σ log πθ(y|x) over your training set (here, the valid traces). Its gradient is ∇L_SFT = −(1/N₊) Σ ∇log πθ(y|x) — i.e., “push weights to make each training trace more likely.”

Look at the two: REINFORCE-with-binary-reward averages ∇log πθ over valid traces; SFT-on-valid-traces averages ∇log πθ over valid traces. They’re the same vector up to a positive scalar (N₊/N, the fraction that were valid). A gradient ascent step on reward and a gradient descent step on SFT loss move the weights in the identical direction. That’s the whole proof. Filtering then fine-tuning is policy gradient; the “reward” is just the validator’s pass/fail, applied as a hard data filter instead of a multiplier.

Proposition 2 (the off-policy twist). Real deployment mixes traces from the current model (on-policy, drawn from πθ) with traces from older generations (off-policy, drawn from some behavior policy πβ). If you model the training data as a mixture p_data = (1−λ)·p_π⁺ + λ·p_β⁺, the off-policy term can be rewritten using importance sampling — reweighting old traces by the ratio πβ(y|x)/πθ(y|x) so they count as if drawn from the current policy. The result: SFT on this mixture equals REINFORCE with an effective reward R_eff ∝ (1−λ) + λ·πβ(y|x)/πθ(y|x). Translation: old traces still count, but their influence is scaled by how plausible they are under the current model — traces the current model would never produce get up-weighted (they carry new information), traces it already produces get the baseline weight. This is exactly the off-policy correction RL practitioners use, falling out of the deployment loop for free.

Architecture & data flow

flowchart LR
  T[Fixed task pool<br/>D_tasks, no solutions] --> M[Model gen n<br/>policy pi_theta_n]
  M -->|samples trace y = CoT + plan| V{Validator V<br/>VAL / PDDL checker}
  V -->|valid| K[Keep trace]
  V -->|invalid| X[Discard]
  K --> A[Aggregate with valid traces<br/>from gens 0..n-1]
  P[(Past valid traces)] --> A
  A --> C[Curate: one trace per task<br/>shortest plan, fewest tokens]
  C --> S[SFT base model<br/>next-token prediction + LoRA]
  S --> M2[Model gen n+1]
  M2 -.->|next iteration| M

Schematic of the self-built curriculum: each generation can only solve tasks up to some difficulty (the moving frontier). Its valid solutions become training data, letting the next generation push the frontier outward. Drag the slider to step through generations and watch which task difficulties become solvable. Numbers are illustrative of the mechanism, not the paper's exact per-task data.

The algorithm, simplified

# Iterative deployment: deploy -> validate -> curate -> fine-tune -> repeat.
# llm(model, x) -> trace (chain-of-thought + proposed plan)
# validate(x, trace) -> bool        (deterministic, e.g. VAL on a PDDL plan)
# plan_len, n_tokens -> quality keys used to pick the single best trace per task

def iterative_deployment(base_model, tasks, generations=5):
    model = base_model
    archive = {}                       # task -> best valid trace seen across ALL gens

    for gen in range(generations):
        # 1. DEPLOY: current model attempts every task
        for x in tasks:
            trace = llm(model, x)      # on-policy sample from pi_theta_n
            # 2. VALIDATE: keep only verifiably-correct traces (the binary "reward")
            if validate(x, trace):
                # 3. CURATE: keep the single highest-quality trace per task,
                #    aggregating across generations (prevents forgetting/collapse)
                prev = archive.get(x)
                if prev is None or better(trace, prev):   # shorter plan, then fewer tokens
                    archive[x] = trace

        # 4. FINE-TUNE next generation on the curated archive (plain SFT).
        #    Refit the BASE model from accumulated traces, not a stack of adapters.
        model = sft(base_model, list(archive.values()))   # next-token prediction, LoRA

    return model

def better(a, b):
    return (plan_len(a), n_tokens(a)) < (plan_len(b), n_tokens(b))

The entire “reward” is the if validate(...) line. There is no reward model, no advantage estimate, no PPO clipping — the validator’s pass/fail is the learning signal, and it’s applied by deciding which data survives.

Built on Prior Work

Results & Evidence

Setup. Base model: Qwen3-4B-Thinking. Three classical-planning domains (1000 tasks each), all from the IPC 2023 learning track:

• Blocksworld (rearrange stacks of blocks; polynomial, solvable in ≤2n steps)
• Rovers (Mars-rover task scheduling; polynomial plan existence)
• Sokoban (push boxes to targets; PSPACE-complete, plans can be exponentially long)

One model per domain, 5 generations, 3 runs each. Plans validated by VAL. Fine-tuning via LoRA.

Headline numbers (avg solved tasks, base → gen 5):

• Blocksworld: 52 → 154 (+196%)
• Rovers: 41 → 206 (+401%)
• Sokoban: 33 → 97 (+196%)

In all three, generation 5 more than doubles the base; Rovers 5בs it.

Genuine generalization, not tricks. Plan-length histograms show later generations discovering substantially longer plans (Blocksworld: base ~20 steps max → gen 5 ~35+). The model solves harder, longer-horizon tasks, not just cleaner versions of easy ones.

Reasoning tokens don’t balloon. Unlike RL fine-tuning (DeepSeek-R1), the number of reasoning tokens stays roughly flat across generations (~2000-token swing either way). So the gains aren’t bought by simply thinking longer.

Curation is decisive. Blocksworld with vs. without curation at gen 5: 154 vs. 79 solved. And curation used 356 traces vs. 4017 — 94% better performance on ~9% of the data. This is the single most actionable finding: the filter matters more than the volume.

Robustness improves. The unanimous@3 metric (tasks solved in all 3 independent runs) hits its best value at the latest generation in every domain — the model isn’t just getting lucky, it’s getting consistent.

What the evidence does NOT establish — read this honestly:

• One small model, narrow domains. Qwen3-4B on three (then ten) toy planning domains with a perfect deterministic verifier. The whole thing leans on the validator being cheap, available, and unbiased. In real deployment your “validator” is messy human revealed preference — far noisier and possibly biased.
• Diminishing returns + noise. Most gains land in generations 1–3; later generations fluctuate (Blocksworld even dips at gen 4: 142). They ran to 10 generations and saw “no imminent hints” of collapse — but explicitly say it’s unknown whether curation prevents collapse or merely delays it.
• The RL equivalence is about gradient direction, not full equivalence. It’s REINFORCE with a binary reward and a particular off-policy weighting — not a claim that this matches modern RL (PPO/GRPO) in dynamics or sample efficiency.
• No comparison to actually running RL on the same tasks, so “alternative to RL” is argued, not benchmarked head-to-head.

How You’d Use It

This maps cleanly onto an AI-services practice, and the core insight — a cheap verifier plus a data filter can replace an expensive reward model — is the part to internalize.

• Self-improving vertical agents for clients. If a client’s task has a programmatic success check — code that compiles and passes tests, a SQL query that returns the right rows, a config that deploys clean, a form that validates, an invoice that reconciles — you have a free validator. Stand up the loop: run your agent on the client’s real task stream, keep the traces that verifiably succeeded, fine-tune a small open model (Qwen, Llama) on them, redeploy. The agent gets better at that client’s distribution without you writing a reward function or labeling data. This is a sellable, compounding capability: “your agent gets sharper every month from its own wins.”

• Curation > collection. The 356-vs-4017 result is the commercial headline. You don’t need a giant proprietary dataset; you need a good filter. For a services firm this lowers the cost of building a defensible fine-tuned model dramatically — the moat is your verifier and your task pool, not data volume.

• Multi-agent angle. In a MAS, you already produce mountains of traces. Add a “validator agent” (or deterministic checker) as a gate, archive the validated trajectories per role, and periodically fine-tune each specialist on its own best traces. The off-policy result (Prop 2) says it’s fine — even helpful — to keep traces from older versions of the agent in the mix.

• Risk awareness you can sell. The safety finding is a consulting service in itself. If a client fine-tunes on their own deployment logs, they’re running an implicit RL loop with an unspecified reward. You can audit: what is the implicit reward (what gets logged/kept)? Does it conflict with the model’s safety behavior? Is the validator biased? That’s a real governance offering as agentic systems proliferate.

Build Your Own (Minimal Recipe)

Smallest version that captures ~80% of the value:

1. Pick a task domain with a cheap, reliable verifier. This is the whole game. Code with unit tests is the easiest real-world analog to PDDL+VAL. Start there.
2. Assemble a fixed task pool mixing easy and hard instances. Don’t pre-solve them — the model must bootstrap. Diversity of difficulty is what enables the self-built curriculum.
3. Generation loop:
   • Sample a trace per task from the current model (temperature ~0.6, generous context).
   • Run each trace through the verifier; keep the passes.
   • Archive one trace per task, keyed by quality (shortest / cleanest). Aggregate with prior generations’ archive.
   • Fine-tune the base model on the archive with SFT + LoRA (rank 16ish). Refit from base each round, don’t stack adapters.
   • Repeat 3–5 times.
4. Track the right metrics: solved-count per generation, solution-length distribution (to prove generalization, not memorization), and a consistency metric like unanimous@k.

The two genuinely hard parts:

• The verifier. Everything hinges on a validator that’s cheap, deterministic, and unbiased. The moment your filter is noisy or has a systematic bias, that bias compounds across generations (the paper warns of exactly this). For fuzzy tasks you’ll be tempted to use an LLM-as-judge — be very careful, its biases become your implicit reward.
• Avoiding silent collapse. Aggregating across generations and the one-best-trace-per-task rule are what kept the paper’s models healthy. Get the curation policy wrong (keep duplicates, random tie-breaks) and you degrade — they observed exactly that.

Tooling: any open instruct model (Qwen3-4B is a fine starting point), Hugging Face transformers + peft for LoRA SFT, a single A100-class GPU, and a domain-specific verifier you write or borrow.

How to Improve It

1. Swap the deterministic validator for a learned or LLM verifier — and measure bias drift. The paper’s safety section flags validator bias as the central risk but doesn’t quantify it. Run the loop with a deliberately biased verifier and measure how fast the bias amplifies across generations. That’s both a research result and an audit methodology you could productize.
2. Add explicit off-policy reweighting. Proposition 2 says old traces should be importance-weighted by πβ/πθ, but the experiments just use a hard one-best-per-task filter. Actually implementing the importance weights (up-weighting traces the current model finds surprising) might accelerate the frontier and squeeze more from later generations, where gains currently stall.
3. Attack the diminishing-returns wall. Gains concentrate in gens 1–3. Inject mild exploration — higher temperature, best-of-k sampling, or occasional harder-task seeding — so later generations keep finding novel longer plans instead of recycling known ones.
4. Test the collapse boundary directly. They ran 10 generations and saw no collapse “yet.” Run 50. Vary aggregation policy (sliding window vs. full history). Find where curation stops protecting you — that boundary is the practically important unknown.
5. Combine with real RL as a warm start. Use iterative deployment (no reward function needed) to bootstrap a competent planner cheaply, then switch to GRPO/PPO for the last mile where you do have a reward. Bootstrapping the policy this way could cut the expensive RL phase substantially.

Glossary

• Classical planning — Finding a sequence of actions (a “plan”) to get from a start state to a goal state in a deterministic, fully-observable, discrete world. The clean lab setting here.
• PDDL — Planning Domain Definition Language; the standard format for describing planning problems used in competitions.
• VAL — The standard automatic validator that checks whether a PDDL plan actually achieves the goal. The paper’s “reward signal.”
• Trace — A model’s full output for a task: its chain-of-thought reasoning plus the proposed plan.
• Policy (πθ) — In RL, the thing that chooses actions; here, the LLM itself, parameterized by weights θ, outputting traces given a prompt.
• REINFORCE — The original policy-gradient RL algorithm: nudge the policy to make rewarded trajectories more likely.
• Policy gradient — The family of RL methods that directly optimize the policy’s parameters via the gradient of expected reward.
• Binary reward — A reward that’s only 0 or 1 (here: invalid plan / valid plan).
• SFT (supervised fine-tuning) — Standard training: show the model input→output examples and minimize next-token-prediction loss.
• On-policy / off-policy — On-policy data comes from the current model; off-policy from a different (e.g., older) model or source.
• Importance sampling — A reweighting trick to estimate quantities under one distribution using samples drawn from another, via the ratio of their probabilities.
• Model collapse — Degradation that happens when models are trained recursively on their own outputs, narrowing their output distribution until quality craters.
• Catastrophic forgetting — When fine-tuning on new data erases previously learned capabilities; mitigated here by aggregating traces across all generations.
• Out-of-distribution (OOD) generalization — Solving problems harder/longer than anything in the training distribution — here, finding plans longer than the model previously could.
• LoRA — Low-Rank Adaptation; a cheap fine-tuning method that trains small adapter matrices instead of all weights.
• unanimous@3 — Tasks solved in all 3 independent runs; a robustness/consistency metric.
• GRPO / PPO — Modern policy-gradient RL algorithms used to fine-tune LLMs for reasoning (the expensive, explicit-reward alternative this paper contrasts against).