A_ made by arjun

2026.09.01 · WRITING

How Agents Make Plans: From Task Decomposition to Search and Replanning

A useful plan is executable, verifiable, and willing to change. This article separates task decomposition, search, feedback, and formal planning into the problems they actually solve.

Give an Agent a complex task and it can produce a ten-step plan within seconds. The list may look complete, yet the execution often begins to drift by step two.

The problem is not necessarily that the model cannot plan. It is that the model turns unknowns into definite steps before it has inspected the code, logs, or constraints.

Consider this task:

Migrate the authentication logic of an unfamiliar Go service to a shared identity service. Keep the existing API compatible and provide a rollback-safe release plan.

Before opening the repository, an Agent can reasonably expect to inspect interfaces, change code, run tests, and prepare a release. It cannot yet know where authentication is distributed, what the current tests cover, or whether callers depend on undocumented behavior.

A useful plan therefore has to do more than list steps. It should state the current objective, the dependencies among steps, the evidence required to call a step complete, and which parts must change when new evidence appears.

Planning Is Not an Agent’s “Mysterious Brain”

Planning is often described as the dividing line between an Agent and a Chatbot. That is too absolute.

A system can choose the next tool from its current state without first producing a complete plan. ReAct is one example: reasoning traces and actions advance together, and returned information helps the system update its path and handle exceptions. In the other direction, a normal Workflow may generate a task list at the beginning while still following a path defined in advance.

The more useful questions are:

A plan is only one part of Agent state. It becomes useful inside a feedback loop that connects the plan, Actions, Observations, and the Runtime.

Chain-of-Thought Is Not a Plan

Chain-of-Thought (CoT) is primarily a prompting method for reasoning. In their 2022 paper, Wei and colleagues used few-shot examples that included intermediate reasoning steps and improved performance on arithmetic, commonsense, and symbolic reasoning tasks.

The familiar zero-shot prompt “Let’s think step by step” comes from a different 2022 paper by Kojima and colleagues. Zero-shot CoT should not be treated as the same experimental setup as the original few-shot CoT work.

CoT can help a model work through a problem, but reasoning text is not yet an executable engineering plan. A plan usually needs to become structured state that can be stored and updated:

[
  {
    "id": "inspect-auth-boundary",
    "goal": "Identify the current authentication entry points and callers",
    "depends_on": [],
    "done_when": "Entry points, dependents, and existing tests are recorded",
    "status": "in_progress"
  }
]

The important part is not asking the model to publish a long inner monologue. It is giving the Runtime enough information to determine which step is active, what evidence supports it, and how completion is judged.

Reasoning text passes through the Runtime before becoming a structured Plan State
Reasoning may help form a candidate judgment. Execution begins only after the Runtime turns that judgment into state it can save, validate, and update.

A Practical Starting Point: Plan-and-Execute

Plan-and-Execute separates planning from execution. A Planner decomposes the task; an Executor works through the resulting steps.

For the migration above, the initial plan might contain only four steps:

  1. Locate authentication entry points, callers, and data dependencies.
  2. Record the behavior that must remain compatible.
  3. Design the migration boundary, rollback path, and verification strategy.
  4. Make changes in batches and run the relevant tests.

This structure is useful when a task can be decomposed and its dependencies are reasonably clear. The Executor does not have to reinterpret the entire objective on every step.

But “plan first, execute second” should not mean that the plan becomes immutable. If the first step reveals three authentication mechanisms—cookies, JWTs, and an internal signature scheme—the remaining design and test steps must change. Following the original list anyway would only automate the wrong path.

Replanning Matters More Than a Complete First Plan

In real work, a plan is usually a hypothesis that holds for now.

Inspect → Draft current plan → Execute one step → Read result
   ↑                                               ↓
   └──── Keep valid facts; revise affected steps ──┘

Replanning does not mean discarding everything after every failure. A steadier approach is to preserve verified facts and replace only the steps affected by new evidence.

Suppose the Agent has already confirmed the API compatibility requirements, but a test shows that an old client depends on an undocumented error code. The compatibility layer and its test plan need to change. The Agent does not need to rediscover every authentication entry point.

In an implementation, these situations can become explicit Replan Triggers:

Explicit triggers are easier to control than asking the model to decide, by feel, whether it should “think again.”

An Agent inspects, plans, executes, observes, and selectively replans
Replanning should preserve verified facts and revise only the steps invalidated by new evidence.

Self-Consistency: More Samples, Not a Multi-Step Plan

Self-Consistency is often discussed beside planning methods, but it was introduced as a decoding strategy.

It samples multiple reasoning paths for the same problem and aggregates their final answers. The paper describes this as marginalizing over the sampled reasoning paths; the paths do not exchange information while they are being generated.

The method fits tasks with a reasonably well-defined answer and multiple plausible derivations, including some mathematics and commonsense reasoning problems. It does not directly answer which tool should be called next or how an execution plan should change after a failure.

The trade-off is straightforward: more samples require more model calls and tokens. When there is no reliable way to aggregate the outputs, generating several opinions does not necessarily move the result closer to the truth.

Tree of Thoughts (ToT) addresses a different problem: several directions are available, and committing too early to the wrong one can damage the final result.

ToT treats larger reasoning units as Thought nodes. It generates candidate states, evaluates them, and expands selected branches. The search can look ahead and, when appropriate, backtrack. The original paper evaluated the method on Game of 24, creative writing, and mini crosswords.

The difference from ordinary CoT is not that the same text is drawn as a tree. The Runtime explicitly manages candidate states, evaluation, and search.

ToT also has limits. More branches mean more model calls. If the evaluator scores candidates poorly, the correct branch may be pruned early. The method fits tasks with a bounded search space and intermediate states that can be compared; it is not a default wrapper for every Agent.

Graph of Thoughts: Let Branches Meet Again

In a tree, a node normally has one parent path. Graph of Thoughts (GoT) allows more general dependencies among Thoughts. It can aggregate several intermediate results into a new result and can use feedback loops to improve a Thought.

That is useful for tasks that fan out and then merge. A system could analyze several modules independently, then combine the migration risks into one global plan.

GoT is a more general research framework, but it is not automatically the next engineering tier above ToT. The paper reports gains on selected tasks. Whether graph scheduling is worth its extra complexity on a different task, model, and evaluation setup still has to be measured.

Reflexion: Store Verbal Feedback, Not New Model Weights

Reflexion focuses on improvement across attempts. After a failed attempt, an Agent produces a verbal reflection from the feedback, stores it in Episodic Memory, and reads it during later attempts.

The paper is explicit that Reflexion does not learn by updating model weights. It changes the language feedback available during later reasoning.

Its usefulness therefore depends on feedback quality. Reliable test results, environment rewards, or reviews can help the next attempt avoid the same mistake. Vague or incorrect feedback simply carries a bad lesson forward.

Reflexion can help a plan improve, but it is not the same layer as task decomposition or a search strategy.

LLM+P: Hand Strict Planning to a Classical Planner

Some tasks have explicit actions, preconditions, and goal states, such as robot operations in controlled environments or formal scheduling. LLM+P asks an LLM to translate a natural-language problem into PDDL, invokes a classical planner, and translates the resulting plan back into natural language.

This separates natural-language understanding from symbolic search. The LLM performs the translation; the planner searches the formal model for a feasible or optimal plan.

The planner’s correctness still depends on a correct formalization. If the LLM omits a precondition or mistranslates an action effect, a rigorous planner will solve the wrong problem rigorously.

Planning methods arranged by reasoning, orchestration, feedback, and formal planning layers
These methods live at different layers. They can be combined, but they do not form a single upgrade ladder.

Do Not Choose by “Chain, Tree, or Graph”

CoT, Self-Consistency, ToT, GoT, Reflexion, and LLM+P do not solve the same layer of the problem. Treating them as one upgrade ladder leads to poor engineering choices.

A better decision order is:

  1. If the next step can be determined in code, prefer a Workflow.
  2. If the task can be decomposed but results may change later steps, use Plan-and-Execute with Replanning.
  3. If several candidate paths exist and intermediate states can be compared, consider ToT-style search.
  4. If partial results from several branches must be merged, consider graph orchestration or an Orchestrator-Worker pattern.
  5. If actions and constraints can be formalized, an external planner may be more appropriate than text-only reasoning.
  6. If the system should improve from reliable feedback across attempts, add a memory mechanism such as Reflexion.

Self-Consistency is closer to “sample several routes to the same answer.” It can be combined with some of these structures, but it does not replace an execution plan.

A decision guide mapping task characteristics to planning structures
Choose from the structure of the task: fixed steps, feedback-driven paths, comparable branches, merged results, or formal constraints.

What Should an Executable Plan Store?

In a production system, I would rather see a short, explicit Plan State than a long reasoning essay. At minimum, it should contain:

These fields can be saved, inspected, and restored. After a system failure, the Runtime can determine what was already completed instead of asking the model to reread the entire conversation and guess.

A long plan does not mean an Agent can see farther. Often it only means the Agent guessed more while it knew less. A useful plan should be short enough to execute, explicit enough to verify, and willing to change when the evidence changes.

References