Agent Planning: From Plausible Plans to Verifiable Replanning

A clear, orderly plan in text does not mean an agent can plan. A real plan must keep updating under partial observations, hard constraints, tool failures, authority limits, resource budgets, and environment changes, then be accepted by an independent terminal state rather than the agent's explanation. The research object is not “a plan that sounds reasonable,” but a control process that an environment can refute, that can replan safely, and that correctly stops when work is infeasible.

1. Separate Five Objects First

Agent Planning Benchmark (APB) starts from this gap. It separates holistic planning, feedback-conditioned step-wise planning, distracting/broken tools, and unsolvable tasks as upstream diagnostics for end-to-end execution benchmarks. Its evidence is scoped to its tasks and models, but it supports a necessary rule: do not assign final failure automatically to planning, or a good-looking plan automatically to execution ability.

2. A Contract for an Executable Plan

A natural-language plan in chat drops boundaries needed for execution, comparison, and recovery. A minimal plan version should retain:

GoalSpec       = target_postcondition, hard_constraints, soft_preferences, budget, authority
PlanVersion    = parent, state_digest, assumptions, subgoals, dependencies, stop_conditions
PlanStep       = precondition, authorized_action, expected_observation, expected_cost, recovery_boundary
Observation    = source, timestamp, provenance, state_delta | uncertainty | tool_failure
ReplanEvent    = trigger, invalidated_steps, alternatives, chosen_action, budget_delta, rationale
Acceptance     = independent_postcondition, evidence_digest, verifier_version, outcome

This does not require every agent to emit verbose JSON. It requires the harness to preserve equivalent information externally. It creates six auditable questions:

1. Is the goal acceptable? A goal points to a checkable postcondition, not merely “finish the research” or “handle the request.”
2. Are constraints explicit? Time, cost, authority, irreversible actions, privacy, and policy are hard or soft constraints, not prose that can disappear.
3. Why is each step allowed? Preconditions, authority, and expected observations prevent a vaguely related tool call from concealing an unauthorized or ineffective action.
4. When should replanning occur? Failure, absent signal, state drift, concurrent conflict, budget change, and uncertainty are explicit triggers.
5. What does replanning affect? Record invalidated steps to avoid repeating committed side effects or treating a failed branch as current fact.
6. When should the system refuse or stop? Infeasibility, missing critical information, insufficient authority, or exhausted budget make refusal/safe stop correct outcomes, not low-scoring trajectories.

3. A Plan Must Face Global Constraints, Hidden Tools, and Real Failure

DeepPlanning requires active information gathering, local constraints, and optimization under global constraints such as time and money. It shows why a sequence of locally plausible actions can still violate overall feasibility.

PlanBench-XL combines a large tool ecosystem, limited tool visibility, implicit subgoals, and optional missing, broken, or distracting tools. It distinguishes planning over a known fixed tool list from planning that must discover tools and use returned evidence to choose the next step. Failures without explicit error signals especially cannot be judged by one successful tool-call response.

This is why browser, terminal, scientific, and cross-application API tasks need different verifiers. In AutomationBench, a cross-application REST workflow additionally requires endpoint discovery, layered business policy, and correct data writes; the paper grades programmatic end states. It is a useful example of backend terminal state constraining planning, not a generalization to every UI, browser environment, or business process.

4. Replanning Is a Controlled Change, Not Infinite Retry

High-quality replanning does not turn every failure into “try again.” Each ReplanEvent should name the triggering observation, invalidated assumptions or steps, affected artifact/state, any irreversible effect, remaining budget, and how the replacement plan will be independently checked.

Making these explicit actions lets us measure recovery quality: replan_trigger_precision, invalidated_step_accuracy, duplicate_side_effect, recovery_cost, safe_stop, and verified_success_after_replan. For long horizons, replanning connects to the checkpoint/branch contract in Agent Memory: plan versions and environment state must recover together; a chat summary is not enough.

5. Multi-Agent Systems, Harness Edits, and GPU Scheduling Are Not Planning

ClawArena-Team evaluates a leader managing a fixed subagent pool and jointly scores task correctness with least privilege and modality routing. It separates team management from workers’ raw task solving, showing why delegation plans need separate authority, cost, and final-outcome measures.

Agentic Harness Engineering (AHE) makes editable harness components, trajectory experience, and each edit’s prediction/later verification observable. In its coding-agent setting, this edit-to-outcome connection is a controlled form of harness evolution. It does not establish that arbitrary self-editing harnesses or workflow search are RSI; evaluator, authority, and held-out acceptance must remain external to the candidate.

SAGA tackles a different layer: treating complete agent workflows as GPU scheduling units to improve task-completion latency. It is a resource-scheduling contribution for deployment, not evidence of policy planning. A system that executes the same workflow faster still needs a separate check that the workflow picked the right tools, respected constraints, and reached the terminal state.

6. An Evaluation Matrix That Can Falsify “Can Plan”

Under the same base model, tool policy, action authority, environment initial state, total token/wall-clock/worker budget, and hidden verifier, compare at least:

The minimum counterexample set contains correct endpoint plus wrong payload; successful response with no commit; missing or silently failing tools; stale state; unsolvable tasks; budget conflicts; late subagent returns; and trajectories that improve a process score without passing hidden postconditions. A rising plan score must then meet execution, integrity, and terminal-state evidence together.

7. Synthetic Instances and Agentic RL: Train Replanning Without Leaking Evaluation

A synthetic instance cannot supply only one successful plan. A training-useful planning instance has initial-state and visibility boundaries, goal and hard constraints, candidate tools and authority, executable transitions, perturbation/failure branches, alternate paths, refusal conditions, and an independent verifier. Training traces may show when a plan is proposed, revised, or abandoned; they cannot contain the final evaluator, hidden postcondition, successful evaluation trace, or unique answer template.

Compare SFT-only, RL-only, and SFT+RL on the same action surface, and separate final tasks by environment, workflow/rule, tool-schema/generator family, and failure/security family. Reward must report verified_outcome, hard-constraint violations, integrity violations, recovery cost, and correct refusal separately. One scalar writable by the planner or agent cannot decide every conclusion. See Synthetic Instances for Agent Training and Agentic RL.

8. Return to the Five Core Threads

The conclusion is deliberately modest: a plan is an inspectable intermediate artifact, not a capability declaration. Only when it updates, refuses, or completes safely under changing state, limited tools, real failures, global constraints, and an independent verifier does “the agent can plan” become an engineering conclusion. See Harness Engineering for runtime authority, traces, budgets, and evaluator design; together they form an accountable agent loop.