A Field Guide to Planning Algorithms for Agents

Overview

Every agent framework is answering the same question in different syntax: what should the model do next, and how does it decide. The planning algorithm is the answer, and it's easy to underrate, since most of them read like a page of prompt template. That undersells them. Different planning families commit to different shapes before the model ever generates a token, and the shape is what survives no matter how good the underlying model gets.

That's a structural limit, not a matter of prompt skill. A linear planner can't recover from a wrong first step no matter how good the model behind it is. A branching planner can't avoid combinatorial cost no matter how clever the prompt gets. Tuning a prompt doesn't move a planner out of the failure mode its shape guarantees.

This guide covers six families: Chain-of-Thought, Tree-of-Thought and its generalization Graph-of-Thought, ReAct, PAL, and multi-stage planners. We'll walk through what each one looks like, where it breaks, and which of them we'd actually reach for shipping an agent this quarter versus which belong in a research notebook. Working code for the ones worth shipping is in the last third of this guide.

Plan (a pipeline that can send itself --ok--> answer back to an earlier stage) -->

Figure 1 — Four planning topologies. A line can't revisit a wrong step. A tree can, but only inside the model's own imagination. A loop can ground itself in what the world actually returns. A pipeline is the only shape that does both.

Chain-of-Thought (CoT): Linear, Elegant, and Fatally Overconfident

CoT is the simplest structured reasoning you can ask for: think step by step. Forcing the model to externalize its intermediate steps gives it more tokens to compute over and a scaffold that keeps its logic from wandering. For a large class of single-shot reasoning problems, that scaffold is enough, and it costs exactly one model call.

prompt = f"""
Solve the problem step by step.
Question: {task}
"""

The trouble starts with feedback, or the total lack of it. CoT assumes every intermediate step is correct. If the model makes a wrong early assumption, the rest of the chain collapses, and nothing in the process notices, because the only thing the planner can examine is its own prior reasoning, and that reasoning already encoded the mistake. That's why CoT struggles on any environment where the agent has to interact with something outside its own head: it commits to a path before it has the information to know whether the path is right, then follows it off a cliff with total confidence.

We'd reach for CoT in three places and nowhere else: short math and logic problems, local reasoning that doesn't depend on external state, and the first sketch of a plan before something more robust takes over. Anywhere the agent touches a tool, a database, or a live page, treat CoT as a step you pass through, not a destination.

Tree-of-Thought and Graph-of-Thought: Search, With and Without a Budget

ToT explores multiple reasoning paths instead of committing to one. At each step the planner generates several candidate continuations, scores them, and keeps the most promising, typically with breadth-first, depth-first, or beam search driving the frontier. That gives it something CoT structurally cannot have: the ability to back out of a branch that turns out to be a dead end.

def expand_thoughts(node):
    return llm.generate(f"Expand this partial plan: {node}")

def evaluate(thought):
    return llm.generate(f"Rate the promise of this idea (0-10): {thought}")

# BFS or beam search over candidate thoughts

It's a real improvement, and it comes with a limit worth stating plainly. ToT only hedges against uncertainty inside the model. Every branch it explores lives in the model's own imagination. If the actual source of uncertainty is the state of the outside world, what an API returns, what a page contains, searching harder over imagined possibilities doesn't help, because the model is scoring its own guesses with the same judgment that produced them.

Graph-of-Thought generalizes the tree into an arbitrary graph: thoughts can merge, a sub-result computed earlier can get reused, and the planner can re-enter a state it had abandoned. That's strictly more expressive than ToT, and correspondingly harder to keep bounded. A graph with no termination condition can wander forever, and the scoring heuristics have to hold up across a much bigger frontier than a tree ever produces.

We think GoT is mostly a research pattern outside of narrow cases: genuinely reusable sub-structure, or a search space large enough that deduplication pays for the machinery it costs. Most production agents don't have that shape. Reach for ToT when a task is genuinely search-shaped and the state lives entirely inside the model, puzzles, constraint satisfaction, "find the right decomposition" problems, and budget accordingly: the number of model calls grows with branching factor times depth, and every branch that touches a real tool multiplies that tool's side effects right along with it.

ReAct: Reasoning and Acting in a Single Loop

ReAct interleaves three things: a thought about what to do next, an action that calls a tool, and an observation that reads back what actually happened. The observation is the whole point. After every action, the planner gets a fresh signal it did not generate itself, and that's what breaks the closed loop of self-confirmation that dooms CoT and limits ToT to its own head. The model reasons to act, then acts to reason, adjusting its plan against what the world actually returned rather than what it expected to return.

while not done:
    thought = llm(f"Thought: {history}")
    action = parse_action(thought)
    observation = tools[action.name](action.args)
    history.append((thought, action, observation))

This is the default we'd start almost any tool-using agent on. It handles uncertainty better than CoT because it checks its inferences against reality instead of trusting them, and it's a strong fit for web tasks, QA, and anything grounded in fact retrieval.

It isn't free of failure modes, and they're characteristic ones. An agent can loop when no progress is being made, misread an observation and act on the wrong reading, or thrash between two tools without settling on either. The fix for all three is the same in shape: a hard step budget, a loop-detection rule, and a validation check that runs before an action actually fires, not after.

PAL: Program-Aided Language Models, Code as the Plan

PAL asks the model to write a program instead of performing arithmetic or symbolic manipulation in its head, where it is genuinely unreliable, and hands the actual computation to an interpreter. The model does the part it's good at, translating a problem into a procedure, and the interpreter does the part it's good at, executing that procedure exactly, every time.

# LLM output
def solve():
    x = compute_something()
    return x + 10

For math, algorithms, and data transformation, this is close to a solved problem. An interpreter doesn't make arithmetic mistakes the way a language model does, and the reliability gap between a model computing an answer in its head and a model writing code that computes it is not a small one.

The cost moves somewhere else: to the sandbox. Generated code can carry side effects nobody intended, hang in an infinite loop, or reach for filesystem and network access it should never have had. None of that is a reason to avoid PAL. It's a reason never to run generated code anywhere near your main interpreter, a point we'll come back to below.

Multi-Stage Planners: Plan, Act, Reflect, Repair

Multi-stage planners stop asking one model in one loop to do everything. Planning, execution, and criticism are different cognitive jobs with different failure modes, so each gets its own role, its own prompt, and sometimes its own model: a large reasoning-heavy planner, a smaller tool-aware executor, and a critic that can flag or veto a bad step before it does damage.

1. Planner: break the task into subgoals
2. Executor: ReAct-style execution per subgoal
3. Reflector: find errors in what was produced
4. Repair phase: rewrite subplans that failed
5. Repeat until the task is complete or a budget is exhausted

The result is the first family that combines what ReAct and ToT each do alone. It grounds itself in feedback the way ReAct does, and it recovers from a structural mistake the way ToT does, because a bad subplan gets caught by the critic and rewritten rather than executed to completion. That combination is why we'd default to a multi-stage planner over a single ReAct loop for anything running more than about twenty steps.

The failure mode worth naming is that a wrong high-level plan doesn't announce itself. If the planner's first decomposition is bad, the rest of the system can execute every subgoal competently and still land on a confidently wrong result. Competent execution says nothing about whether the plan being executed was right. This is also the most expensive family to build well: role separation, a repair loop, and a critic with real veto power are process design, not a clever prompt.

Choosing a Planner

The families aren't competitors so much as answers to different questions, and a side-by-side table hides more than it reveals unless you read it against what kind of uncertainty each one is actually hedging.

Tool use raises the stakes on every one of these choices. Reasoning that stays inside the model is, at worst, wrong on paper. Reasoning that calls tools can delete a record, send an email, or move money, and the cost of a planning mistake changes from a bad answer to a bad action. CoT will write "the record was deleted" into its reasoning and proceed as if that were true, without ever checking. ReAct's feedback loop can misread an observation and repeat a harmful action. ToT and GoT multiply real side effects right along with the branches they explore: ten branches that each write to a system means ten writes, not one. Multi-stage planners concentrate the risk one level up, since a single bad plan gets carried out competently across every subgoal, which is exactly the failure the critic role exists to catch.

The practical rule holds regardless of which family you're running: separate read-only tools from side-effecting ones, and require explicit confirmation, a dry run, or a critic's sign-off before anything that mutates real state. Topology reduces the odds of a bad action. Guardrails bound the damage when one gets through anyway.

Four questions get you to the right family faster than a benchmark leaderboard will.

Does the task touch external state? If the agent has to read from or write to the outside world, search, query a database, call an API, it needs grounding. That means ReAct or a multi-stage planner with a ReAct executor. Pure CoT and ToT are off the table the moment correctness depends on something the model can't see.

Is the hard part computation or decomposition? Exact calculation and data transformation want PAL and an interpreter doing the arithmetic. Finding the right way to break a problem apart wants ToT, GoT, or the planning stage of a multi-stage system.

How long is the horizon? Short, self-contained reasoning lives comfortably in CoT. Past roughly twenty steps, an unchecked mistake compounds faster than most people expect, and you want the explicit memory, verification, and repair that only a multi-stage planner provides.

What does being wrong cost? Low-stakes, reversible tasks tolerate a cheap planner. High-stakes or irreversible ones justify the overhead of a critic and a repair loop. Match the robustness of the planner to the cost of the failure it exists to prevent.

A useful default: start with ReAct, add PAL as a tool the moment computation shows up, and graduate to multi-stage only once the horizon or the stakes actually demand it. Reach for ToT or GoT when the problem is genuinely search-shaped and the budget exists to pay for the branching.

One caution before picking a planner off a leaderboard: a headline number on WebArena, SWE-Bench Pro, or AgentBench says very little about whether that planner will work for your task specifically. These benchmarks differ in horizon length, in how much they depend on tool feedback, and in whether the uncertainty they're testing is internal to the model or genuinely environmental. Read the failure breakdown, not just the top-line accuracy, and weight the benchmark whose structure looks most like your real workload.

Turning This Into Code

Six patterns above, and four of them are the ones you'll actually deploy. We're skipping runnable implementations of ToT and GoT here, not because they don't work, but because the snippets already shown carry the shape, and a full beam-search-over-guesses implementation is exactly the kind of code that looks impressive and gets used twice. What follows is CoT, ReAct, PAL, and multi-stage: the four we'd put into a real codebase.

Assume Python 3.10+, a generic call_llm(prompt, system=None) -> str you can wire to any provider, a small tool registry for ReAct and multi-stage, and nothing beyond the standard library. Drop this into a single planning.py and adapt; the skeletons map cleanly onto LangChain, LangGraph, or a bespoke runtime once you decide where orchestration should live.

Shared LLM and tool abstractions

# planning_core.py
from dataclasses import dataclass
from typing import Any, Callable, Dict, List, Optional, Tuple
import json
import textwrap
import traceback

# ---------- LLM CLIENT HOOK ----------
def call_llm(prompt: str, system: Optional[str] = None) -> str:
    """
    Replace this with your actual LLM client.
    For example, OpenAI, Anthropic, etc.
    """
    raise NotImplementedError("Wire this to your model provider.")

# ---------- TOOL REGISTRY (for ReAct / multi-stage) ----------
ToolFunc = Callable[[Dict[str, Any]], Any]

@dataclass
class Tool:
    name: str
    description: str
    schema: Dict[str, Any]  # JSON-schema-like, or just a contract
    func: ToolFunc

TOOLS: Dict[str, Tool] = {}

def register_tool(tool: Tool) -> None:
    TOOLS[tool.name] = tool

def call_tool(name: str, args: Dict[str, Any]) -> Any:
    if name not in TOOLS:
        raise ValueError(f"Unknown tool: {name}")
    return TOOLS[name].func(args)

Chain-of-Thought

# cot_planner.py
from typing import Optional
from planning_core import call_llm
import textwrap

COT_SYSTEM_PROMPT = "You are a helpful assistant that solves problems step by step."

def cot_solve(question: str,
              few_shot_examples: Optional[str] = None,
              verify: bool = True) -> str:
    """
    Basic Chain-of-Thought planner.
    - question: the user problem
    - few_shot_examples: optional CoT examples to condition behavior
    - verify: whether to ask the model to double-check its own answer
    """
    examples_block = few_shot_examples or ""

    prompt = textwrap.dedent(f"""
    {examples_block}

    Now solve the following problem step by step.

    Question:
    {question}

    Show your reasoning as 'Thought:' lines and provide a final answer as:
    'Final Answer: <answer here>'
    """)

    raw = call_llm(prompt, system=COT_SYSTEM_PROMPT)

    if not verify:
        return raw

    verify_prompt = textwrap.dedent(f"""
    You previously produced this solution:

    {raw}

    Double-check whether the final answer is correct.
    If you find an error, provide a corrected 'Final Answer' and updated reasoning.
    Otherwise, confirm that the original final answer is correct.
    """)

    verified = call_llm(verify_prompt, system=COT_SYSTEM_PROMPT)
    return verified

The optional verify pass is the cheapest reliability upgrade in this whole guide: one extra model call catches a meaningful share of arithmetic and logic slips. It's not a substitute for grounding, but for pure-reasoning tasks it's almost always worth the extra round trip.

ReAct: thought, action, observation

This is a real skeleton, not pseudocode.

# react_planner.py
import json
from typing import Any, Dict, List, Tuple
from planning_core import call_llm, call_tool, Tool, register_tool
import textwrap

REACT_SYSTEM = "You are an agent that reasons and acts using tools. Follow the Thought/Action/Observation format."

def format_history(history: List[Tuple[str, str, str]]) -> str:
    """
    History is a list of (thought, action, observation).
    """
    lines = []
    for i, (thought, action, obs) in enumerate(history, start=1):
        lines.append(f"Step {i}:")
        lines.append(f"Thought: {thought}")
        lines.append(f"Action: {action}")
        lines.append(f"Observation: {obs}")
        lines.append("")
    return "\n".join(lines)

def parse_action(line: str) -> Tuple[str, Dict[str, Any]]:
    """
    Expect something like:
        Action: search(query="python logging")
    We'll parse the tool name and args via a crude parse; you will likely want
    to tighten this with a structured format (e.g., JSON).
    """
    if not line.lower().startswith("action:"):
        raise ValueError("No Action: prefix found.")
    content = line.split(":", 1)[1].strip()
    # e.g. search(query="python logging")
    name, rest = content.split("(", 1)
    name = name.strip()
    args_str = rest.rsplit(")", 1)[0]
    # naive parse: treat as JSON-ish
    # Better: force the model to output JSON.
    try:
        args = json.loads(args_str)
    except Exception:
        args = {"raw": args_str}
    return name, args

def react_solve(question: str,
                max_steps: int = 10) -> str:
    """
    Core ReAct loop.
    """
    history: List[Tuple[str, str, str]] = []

    for step in range(max_steps):
        history_text = format_history(history)
        prompt = textwrap.dedent(f"""
        You are solving the following task:

        Question:
        {question}

        You must follow this strict format:

        Thought: <your reasoning>
        Action: <tool_name(args_as_JSON)>

        After each action, you will receive an Observation.
        Continue until you have enough information, then output:

        Thought: ...
        Action: finish(answer="<final answer here>")

        Here is the history so far:
        {history_text}
        """)
        resp = call_llm(prompt, system=REACT_SYSTEM)

        # find the last "Thought:" and "Action:" lines
        thought_line = ""
        action_line = ""
        for line in resp.splitlines():
            line = line.strip()
            if line.lower().startswith("thought:"):
                thought_line = line.split(":", 1)[1].strip()
            elif line.lower().startswith("action:"):
                action_line = line

        if not action_line:
            raise RuntimeError(f"No Action produced by LLM:\n{resp}")

        tool_name, args = parse_action(action_line)

        if tool_name == "finish":
            answer = args.get("answer", "")
            return answer

        try:
            raw_obs = call_tool(tool_name, args)
            observation = str(raw_obs)
        except Exception as e:
            observation = f"Tool error: {e}"

        history.append((thought_line, action_line, observation))

    raise RuntimeError("Max ReAct steps reached without finish().")

You can register tools like:

# tools_example.py
from planning_core import Tool, register_tool

def search_tool(args):
    query = args["query"]
    # call your search API here
    return f"[fake search results for: {query}]"

register_tool(Tool(
    name="search",
    description="Search the web.",
    schema={"type": "object", "properties": {"query": {"type": "string"}}},
    func=search_tool,
))

The regex-ish parser here is fine for a demo. In production, force the model to emit structured JSON for its actions, through native tool-calling or a constrained-decoding library, so parse_action never has to guess. A malformed action that silently falls back to a raw string is a bug waiting to surface at the worst time.

PAL: generate, then execute in a sandbox

# pal_planner.py
from typing import Any, Dict
from planning_core import call_llm
import textwrap
import traceback

PAL_SYSTEM = "You write correct, pure Python functions to solve problems. Avoid side effects."

def pal_generate_code(question: str) -> str:
    prompt = textwrap.dedent(f"""
    You are a Python coding assistant.

    Write a single Python function 'solve()' that returns the answer to the problem below.
    The function should not read or write files or access the network.

    Problem:
    {question}

    Only output valid Python code. Do not wrap it in backticks.
    """)
    code = call_llm(prompt, system=PAL_SYSTEM)
    return code

def pal_execute(code: str, timeout_sec: int = 5) -> Any:
    """
    Execute generated code in a restricted namespace.
    This is a minimal sandbox - tighten for production.
    """
    # Very minimal sandbox - in production, restrict builtins harder.
    safe_globals: Dict[str, Any] = {
        "__builtins__": {
            "range": range,
            "len": len,
            "min": min,
            "max": max,
            "sum": sum,
            "abs": abs,
        }
    }
    local_vars: Dict[str, Any] = {}

    try:
        exec(code, safe_globals, local_vars)
    except Exception:
        raise RuntimeError(f"Error executing code:\n{traceback.format_exc()}")

    if "solve" not in local_vars:
        raise RuntimeError("No solve() function defined in code.")

    solve_fn = local_vars["solve"]
    # You can wrap this in a timeout via multiprocessing / threads if you want.
    result = solve_fn()
    return result

def pal_solve(question: str) -> Any:
    code = pal_generate_code(question)
    result = pal_execute(code)
    return result

Treat the restricted-builtins trick above as a speed bump, not a wall. A determined model can still reach dangerous capabilities through attribute traversal, and an infinite loop hangs the process regardless of which builtins you've allowed. For anything facing untrusted input, run generated code in a real isolation boundary, a separate process with a hard wall-clock timeout, a container, or a microVM, and never inside your main interpreter.

Multi-stage: plan, execute, critique, repair

# multistage_planner.py
from dataclasses import dataclass
from typing import Any, Dict, List
from planning_core import call_llm, call_tool
from react_planner import react_solve  # reuse ReAct for execution
import json
import textwrap

PLANNER_SYSTEM = "You are a senior planner that breaks tasks into safe, coherent steps."
CRITIC_SYSTEM = "You are a strict critic that finds flaws in plans or results."

@dataclass
class PlanStep:
    id: int
    description: str

def make_plan(task: str, max_steps: int = 8) -> List[PlanStep]:
    prompt = textwrap.dedent(f"""
    You are planning a solution for this task:

    {task}

    Break the solution into at most {max_steps} high-level steps.
    Each step should be a short imperative phrase, like:
    "Collect user requirements"
    "Query the database"
    "Summarize findings"

    Respond as a JSON list of objects with fields:
    - id: integer step number starting at 1
    - description: string

    Example:
    [
      {{"id": 1, "description": "Read the input data"}},
      {{"id": 2, "description": "Filter invalid records"}},
      ...
    ]
    """)
    resp = call_llm(prompt, system=PLANNER_SYSTEM)
    try:
        data = json.loads(resp)
    except Exception:
        raise RuntimeError(f"Planner returned invalid JSON:\n{resp}")
    return [PlanStep(id=s["id"], description=s["description"]) for s in data]

def critic_review(task: str, plan: List[PlanStep], result: str) -> str:
    steps_text = "\n".join(f"{s.id}. {s.description}" for s in plan)
    prompt = textwrap.dedent(f"""
    Task:
    {task}

    Executed plan:
    {steps_text}

    Result:
    {result}

    As a critic, identify any flaws, safety issues, or missing steps.
    Then answer in JSON with:
    - "verdict": "ok" or "needs_repair"
    - "comment": explanation
    """)
    resp = call_llm(prompt, system=CRITIC_SYSTEM)
    return resp

def repair_plan(task: str, plan: List[PlanStep], critic_resp: str) -> List[PlanStep]:
    steps_text = "\n".join(f"{s.id}. {s.description}" for s in plan)
    prompt = textwrap.dedent(f"""
    Task:
    {task}

    Current plan:
    {steps_text}

    Critic feedback:
    {critic_resp}

    Based on the critic's feedback, repair or improve the plan.
    Respond with a new JSON list in the same format as before.
    """)
    resp = call_llm(prompt, system=PLANNER_SYSTEM)
    data = json.loads(resp)
    return [PlanStep(id=s["id"], description=s["description"]) for s in data]

def multistage_solve(task: str,
                     max_replans: int = 2) -> str:
    """
    Multi-stage planner:
    1. Plan
    2. Execute (here: reuse react_solve per subtask)
    3. Critic review
    4. Optionally repair + re-execute
    """
    plan = make_plan(task)

    for attempt in range(max_replans + 1):
        # naive execution: join plan step descriptions into a single question for ReAct
        # In a serious system, you'd execute each step individually and maintain state.
        execution_prompt = textwrap.dedent(f"""
        You must follow this plan:
        {chr(10).join(f"{s.id}. {s.description}" for s in plan)}

        Solve the overall task step by step using tools, then provide a final answer.
        """)
        result = react_solve(execution_prompt, max_steps=12)

        critic_json = critic_review(task, plan, result)
        try:
            critic = json.loads(critic_json)
        except Exception:
            # If critic is broken, just return the result
            return result

        if critic.get("verdict") == "ok":
            return result

        # Otherwise, repair and retry
        plan = repair_plan(task, plan, critic_json)

    # If we exhaust re-plans, return the last result anyway (and log)
    return result

Two changes turn this skeleton into something production-grade. Execute each subgoal individually and thread state between them, rather than collapsing the whole plan into one ReAct call. That's what lets the critic localize a failure to a specific step instead of to the entire run. And give the critic real teeth: let it gate side-effecting actions before they happen, not just review the final result after the damage is done.

Observability: Seeing What Your Planner Actually Did

Every planner above produces a structured trace: thoughts, actions, observations, scores, verdicts. That trace is the most valuable artifact you have for debugging an agent, and most teams throw it away. If you can't reconstruct why the agent took a step, you can't fix the planner that produced it.

Instrument each planning stage as a span in a tracing system, and attach the prompt, the raw model output, the parsed action, and the observation to each one. OpenTelemetry works well here and is increasingly what agent-tracing tools build on. The payoff shows up the first time an agent fails in production: instead of reading a wall of logs, you open a trace and watch the exact branch where reasoning drifted, the tool call that returned garbage, or the critic verdict that got overruled.

Capture, at minimum: the full prompt and raw response at each step, not just the parsed result; every tool call with its arguments, latency, and outcome; step counts and token spend, so runaway branching is visible immediately; and critic verdicts and repair decisions, so you can audit when and why a plan changed.

We'd treat the trace as a first-class output, not a debugging afterthought. The planner is the skeleton. Observability is how you find out which bone broke.

Conclusion

Most of the debate about planning gets aimed at the wrong layer. The choice that matters most happens before the first prompt gets written: what shape does this task's reasoning need to take. A line, a tree, a graph, or a loop, each one buys a specific property and costs a specific one, and no amount of prompt tuning moves a planner out of the failure mode its shape guarantees.

If we had to compress this whole guide into one move: start with ReAct, because grounding beats cleverness for almost everything agents actually do. Add PAL the moment a subgoal turns numeric. Reach for ToT or GoT only when the problem is genuinely search-shaped and the branching is affordable. And once the horizon or the stakes get serious enough that a wrong step needs to be caught rather than merely survived, graduate to a multi-stage planner and give the critic real authority to say no.

Don't treat these as mutually exclusive, either. The strongest production agents tend to be hybrids, not single-family systems: a multi-stage planner whose executor runs ReAct, calls PAL when a subgoal turns numeric, and falls back to plain CoT for the steps too trivial to deserve the overhead. Choose the topology per task, not per project.