A Field Guide to Planning Algorithms for Agents

Overview

Every agent framework answers the same question in different syntax: what should the model do next, and how does it decide. Each family commits to a shape before the model generates a token, and the shape survives however good the model gets. A linear planner can't recover from a wrong first step. A branching planner can't avoid combinatorial cost. Prompt tuning doesn't move a planner out of the failure mode its shape guarantees.

There is a prior question, and the planning research community has a blunt answer. Testing GPT-4 on competition-style planning domains, Valmeekam and colleagues found "the best model (GPT-4) having an average success rate of ~12%" at producing an executable plan unaided, and the ICML 2024 position paper from the same group argues that "auto-regressive LLMs cannot, by themselves, do planning or self-verification." Each family below puts a verifier, a tool or an interpreter where the model's own confidence would otherwise sit.

This guide covers Chain-of-Thought, Tree-of-Thought and its generalisation Graph-of-Thought, ReAct, PAL, multi-stage planners, and the classical PDDL tradition: what each won on, where it breaks, whether we'd ship it.

Figure 1 — Four planning topologies. A line can't revisit a wrong step. A tree can, but only inside the model's imagination. A loop grounds itself in what the world returns. A pipeline 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. Wei and colleagues introduced it in January 2022, and the original result still illustrates what it buys: prompting a 540-billion-parameter model "with just eight chain of thought exemplars" reached state of the art on GSM8K, the grade-school math word problem set, "surpassing even finetuned GPT-3 with a verifier." Eight examples beat a fine-tuning run, for the price of one call.

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

The trouble starts with feedback, or the lack of it. CoT assumes every intermediate step is correct, so a wrong early assumption collapses the rest of the chain and nothing notices: the only thing the planner can examine is its own prior reasoning, which already encoded the mistake.

The cheapest well-evidenced upgrade is not asking the model to check itself, it is sampling. Self-consistency draws several reasoning paths at non-zero temperature and takes the majority answer; Wang and colleagues measured "GSM8K (+17.9%), SVAMP (+11.0%), AQuA (+12.2%), StrategyQA (+6.4%) and ARC-challenge (+3.9%)" over greedy decoding. Note what it needs: a comparable final answer to vote over. It never asks the model to grade its own work.

Use CoT for short math and logic problems, and for the first sketch of a plan. Anywhere the agent touches a tool, treat it as a step you pass through.

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 candidate continuations, scores them and keeps the most promising, with breadth-first or depth-first search driving the frontier. That gives it what CoT structurally cannot have: the ability to back out of a dead end.

The published result is striking, and worth reading precisely. Yao and colleagues report that "in Game of 24, while GPT-4 with chain-of-thought prompting only solved 4% of tasks, our method achieved a success rate of 74%." Their three evaluation tasks were Game of 24, creative writing and mini crosswords, each a closed puzzle whose entire state sits inside the prompt. That is the regime ToT was built for.

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

The limit is worth stating just as plainly. ToT hedges only against uncertainty inside the model: every branch lives in the model's imagination, and the evaluator scoring those branches is the model that generated them. Where the uncertainty is the state of the outside world, searching harder over guesses does not help.

Graph-of-Thought generalises the tree into an arbitrary graph: thoughts can merge, an earlier sub-result can be reused, and the planner can re-enter an abandoned state. Besta and colleagues report at AAAI 2024 that this "increas[es] the quality of sorting by 62% over ToT, while simultaneously reducing costs by >31%." Sorting is a well-chosen headline task, because a sorted sublist is exactly the sub-result a graph computes once and reuses where a tree recomputes it per branch. The saving comes from the merge, not from better reasoning.

Expressiveness has a price: a graph with no termination condition wanders forever, and the scoring heuristics must hold across a bigger frontier. Our read is that GoT stays a research pattern except where a task has reusable sub-structure of the kind sorting has, and that ToT earns its branching factor times depth only where a task is search-shaped with its state inside the model.

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 happened. The observation is the whole point. After every action the planner gets a signal it did not generate, which breaks the self-confirmation loop that dooms CoT and confines ToT to its own head.

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, and the original ICLR 2023 paper is the reason. On the knowledge-intensive benchmarks HotpotQA and Fever, ReAct "overcomes issues of hallucination and error propagation prevalent in chain-of-thought reasoning by interacting with a simple Wikipedia API." On the interactive ones, ALFWorld and WebShop, it "outperforms imitation and reinforcement learning methods by an absolute success rate of 34% and 10% respectively," while "being prompted with only one or two in-context examples." A prompt pattern beating trained policies is the clearest evidence here that topology, not model scale, was the binding constraint.

Its failure modes are characteristic. An agent can loop without making progress, misread an observation and act on the wrong reading, or thrash between two tools. The fix for all three has the same shape: a hard step budget, a loop-detection rule, and a validation check that runs before an action fires. Frameworks hand you the first and none of the rest. LangGraph ships a recursion limit that "sets the maximum number of super-steps the graph can execute during a single execution," defaulting to 1,000 before it raises GraphRecursionError. That is a cost ceiling, not progress detection: an agent alternating two tools forever reaches it having accomplished nothing.

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

PAL asks the model to write a program instead of doing arithmetic in its head, and hands the computation to an interpreter. The model does what it is good at, translating a problem into a procedure; the interpreter does what it is good at, executing that procedure exactly.

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

The gap that buys is large and measured. Gao and colleagues paired Codex with a Python interpreter and reported state-of-the-art few-shot accuracy on GSM8K, "surpassing PaLM-540B which uses chain-of-thought by absolute 15% top-1." A smaller model with an interpreter beat a far larger one reasoning in its head on the same benchmark. That is why we treat PAL as a tool to attach rather than a family to choose between: any planner can call out to code.

The cost moves 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 argues against PAL; it argues for never running generated code near your main interpreter, a point we return to below with the Python core team's own advice.

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 jobs with different failure modes, so each gets its own role and its own prompt: a reasoning-heavy planner, a smaller tool-aware executor, and a critic that can veto a bad step. AutoGen calls the last of these its reflection pattern: two agents "continue to interact until they reach a stopping condition, such as a maximum number of iterations or an approval from the second agent."

1. Planner: break the task into subgoals
2. Executor: ReAct-style execution per subgoal
3. Reflector: find errors in what was produced
4. Repair: rewrite failed subplans, and repeat until the task completes or the budget runs out

This is the first family that combines what ReAct and ToT each do alone: it grounds itself in feedback, and it recovers from a structural mistake, because a bad subplan gets caught and rewritten rather than executed to completion. Three published results make the case from different angles. Plan-and-Solve prompting, at ACL 2023, split zero-shot CoT into an explicit plan step then an execute step and "consistently outperforms Zero-shot-CoT across all datasets by a large margin," with "comparable performance with 8-shot CoT prompting on the math reasoning problem." Reflexion added a verbal self-critique memory between attempts and "achieves a 91% pass@1 accuracy on the HumanEval coding benchmark, surpassing the previous state-of-the-art GPT-4 that achieves 80%." LATS wrapped Monte Carlo tree search around a ReAct-style loop, reporting 92.7% pass@1 on HumanEval with GPT-4 and a WebShop average of 75.9 with GPT-3.5 that its authors call "comparable to gradient-based fine-tuning."

One caveat on Reflexion-style self-critique: it works best where an external signal grades the attempt, such as a failing unit test, rather than where the model grades itself. That is the distinction the ICML 2024 position paper draws, and the reason we push critics toward checkable verdicts.

The failure mode worth naming is that a wrong high-level plan doesn't announce itself: the system can execute every subgoal competently and land on a confidently wrong result. This is also the most expensive family to build well, since role separation, a repair loop and a critic with real veto power are process design, not a prompt.

Classical Planners and PDDL

None of the above is what "planning algorithm" meant before 2022. The automated planning field has spent decades on solvers that take a formal problem description and search for a provably valid action sequence, and its lingua franca is PDDL, written up in October 1998 as "the problem-specification language for the AIPS-98 planning competition." A PDDL model splits in two. The (define (domain ...)) form declares :predicates, the facts that can hold, and actions carrying a :precondition that must be true to fire and an :effect that changes what is true afterwards. The (define (problem ...)) form declares an :init state and a :goal.

The contrast with an LLM planner is exact. A classical solver cannot return a plan whose preconditions are unmet, because the search space is defined so that such a sequence does not exist in it. An LLM planner can return anything, and on competition-style domains GPT-4 returned something executable roughly 12% of the time. The PlanBench suite generalises that test and finds that "on many critical capabilities-including plan generation-LLM performance falls quite short, even with the SOTA models."

The practical use of this is the hybrid the same authors propose: let the model translate a messy real-world request into a formal description, hand that to a sound planner, and let the model handle the parts that resist formalisation. Where a task has discrete actions with stateable preconditions, a solver removes a class of failure that prompt engineering cannot.

Choosing a Planner

The families aren't competitors so much as answers to different questions, and the table below hides more than it reveals unless you read it against what kind of uncertainty each one hedges.

Table 1 — What each family buys, what it proved, and what it cannot fix. The published wins are not comparable to each other: different benchmarks, different properties.

Tool use raises the stakes on all of it. Reasoning inside the model is, at worst, wrong on paper. Reasoning that calls tools can delete a record, send an email or move money, and CoT will happily write "the record was deleted" into its reasoning and proceed as if that were true. So regardless of family: separate read-only tools from side-effecting ones, and require explicit confirmation, a dry run or a critic's sign-off before anything mutates real state. Topology reduces the odds of a bad action; guardrails bound the damage when one gets through.

Two questions get you to a family faster than a leaderboard will, and grounding comes first.

Figure 2 — The two splits that decide a planner. Grounding comes first, because nothing downstream can fix a planner that cannot see the state it reasons about; cost of error comes second, because that is what buys the critic.

Two things the diagram leaves out. Horizon: once a run no longer fits in a single trace a human will read end to end, you want the explicit memory, verification and repair a multi-stage planner provides. And match robustness to the failure you are preventing, not to the task's apparent difficulty.

One caution before picking a planner off a leaderboard. WebArena's authors measured their "best GPT-4-based agent" at "an end-to-end task success rate of 14.41%, significantly lower than the human performance of 78.24%"; SWE-bench's measured Claude 2, the best model of the day, solving "a mere 1.96%" of 2,294 real GitHub issues across 12 Python repositories. Both numbers have moved since, which is the point: a headline figure tells you about a moment, while the benchmark's structure tells you whether it resembles your workload.

Turning This Into Code

What follows is CoT, ReAct, PAL and multi-stage, the four we'd put in a real codebase; the snippets above already carry the shape of ToT and GoT. Assume Python 3.10+, a generic call_llm(prompt, system=None) -> str, a small tool registry, and nothing beyond the standard library. These map onto LangGraph without much translation: nodes are "functions that encode the logic of your agents," edges "determine which Node to execute next," and its Command primitive combines an update to state with a goto — precisely the repair edge the multi-stage planner needs.

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

Treat the verify pass as convenience, not evidence: asking a model to check its own answer is the move the ICML 2024 position paper singles out as unsound. If the answer is comparable, spend that call on self-consistency instead.

ReAct: thought, action, observation

# 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 parser here is fine for a demo. In production, force structured JSON through native tool-calling or constrained decoding so parse_action never guesses: a malformed action that falls back silently 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, and take that from CPython's own maintainers. PEP 551 is explicit: "Do not attempt to implement a sandbox within the Python runtime. There is a long history of attempts to allow arbitrary code limited use of Python features ... but no general success." It recommends instead "at least hypervisor-level isolation." Attribute traversal defeats a builtins allowlist and an infinite loop hangs the process whatever you allowed, so: a separate process with a hard wall-clock timeout at minimum, a container or microVM for untrusted input, never 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 make this production-grade. Execute each subgoal individually and thread state between them rather than collapsing the plan into one ReAct call, which lets the critic localise a failure to a step instead of to the run. And give the critic teeth: let it gate side-effecting actions before they fire, not review the damage after.

FAQ

What is the difference between Chain-of-Thought and ReAct? CoT produces reasoning only. ReAct interleaves reasoning with tool calls and reads the result back, so it can be corrected by something it did not generate. CoT is one model call; ReAct is a loop with a budget.

Can LLMs actually plan on their own? On formal planning benchmarks, not reliably: GPT-4 produced an executable plan about 12% of the time on competition-style domains, and the ICML 2024 position paper from that group argues auto-regressive models cannot plan or self-verify unaided. Everything in this guide supplies the verification from outside.

Which planning algorithm should I use? ReAct if the task touches the outside world, plus PAL when a subgoal is numeric. Multi-stage when a wrong step is expensive to undo. ToT or GoT when the task is a closed search problem and you can afford the branching.

Is Tree-of-Thought worth the cost? On puzzles, measurably: 4% to 74% on Game of 24. On tasks whose uncertainty is environmental, you are paying branching factor times depth to search harder over the model's own guesses, which is the wrong axis.

Conclusion

Most of the debate about planning gets aimed at the wrong layer. The choice that matters happens before the first prompt: what shape does this task's reasoning need. A line, a tree, a graph, a loop or a pipeline, each buys one property and costs another.

Compressed to one move: start with ReAct, because grounding beats cleverness for almost everything agents do. Add PAL the moment a subgoal turns numeric. Reach for ToT or GoT only when the problem is genuinely search-shaped. Once a wrong step needs catching rather than surviving, graduate to multi-stage and give the critic authority to say no. The best systems we've seen are hybrids, so choose the topology per task.

Sources

All URLs read 29 September 2026.

• Chain-of-Thought Prompting Elicits Reasoning in Large Language Models, Wei et al. — the eight-exemplar GSM8K result on a 540B model, and "surpassing even finetuned GPT-3 with a verifier."
• Self-Consistency Improves Chain of Thought Reasoning in Language Models, Wang et al. — the per-benchmark gains over greedy decoding: GSM8K +17.9%, SVAMP +11.0%, AQuA +12.2%, StrategyQA +6.4%, ARC-challenge +3.9%.
• ReAct: Synergizing Reasoning and Acting in Language Models, Yao et al., ICLR 2023 — the ALFWorld and WebShop figures of 34% and 10% absolute success rate, the one-or-two in-context examples, and the HotpotQA/Fever hallucination claim.
• Tree of Thoughts: Deliberate Problem Solving with Large Language Models, Yao et al., NeurIPS 2023 — Game of 24 at 4% for CoT against 74% for ToT, and the three evaluation tasks.
• Graph of Thoughts: Solving Elaborate Problems with Large Language Models, Besta et al., AAAI 2024 — sorting quality up 62% over ToT at more than 31% lower cost.
• PAL: Program-aided Language Models, Gao et al. — Codex plus a Python interpreter "surpassing PaLM-540B which uses chain-of-thought by absolute 15% top-1" on GSM8K.
• Plan-and-Solve Prompting, Wang et al., ACL 2023 — the plan-then-execute split, its margin over Zero-shot-CoT, and parity with 8-shot CoT on math reasoning.
• Reflexion: Language Agents with Verbal Reinforcement Learning, Shinn et al. — 91% pass@1 on HumanEval against a GPT-4 state of the art of 80%.
• Language Agent Tree Search, Zhou et al. — MCTS around a ReAct loop: 92.7% pass@1 on HumanEval with GPT-4, and a WebShop average of 75.9 with GPT-3.5 called comparable to gradient-based fine-tuning.
• On the Planning Abilities of Large Language Models: A Critical Investigation, Valmeekam et al., NeurIPS 2023 — the ~12% average success rate for GPT-4 generating executable plans unaided, on International Planning Competition-style domains.
• PlanBench, Valmeekam et al., NeurIPS 2023 Datasets and Benchmarks — the extensible planning benchmark, and the finding that on plan generation "LLM performance falls quite short, even with the SOTA models."
• LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks, Kambhampati et al., ICML 2024 — "auto-regressive LLMs cannot, by themselves, do planning or self-verification," and the external-verifier architecture that follows from it.
• WebArena: A Realistic Web Environment for Building Autonomous Agents, Zhou et al. — the 14.41% end-to-end success rate for the best GPT-4 agent against 78.24% for humans.
• SWE-bench: Can Language Models Resolve Real-World GitHub Issues?, Jimenez et al., ICLR 2024 — 2,294 issues from 12 Python repositories, and Claude 2 solving "a mere 1.96%."
• PDDL: The Planning Domain Definition Language, AIPS-98 committee, Yale CVC TR-98-003, October 1998 — the original manual: the domain and problem forms, :predicates, :precondition, :effect, :init and :goal.
• LangGraph graph API, LangChain docs — nodes as "functions that encode the logic of your agents," edges, the Command primitive's update plus goto, and the recursion limit defaulting to 1,000 super-steps before GraphRecursionError.
• Reflection design pattern, AutoGen docs — the two-agent generate-then-critique loop, its stopping conditions, and the coder/reviewer worked example.
• PEP 551: Security transparency in the Python runtime — "Do not attempt to implement a sandbox within the Python runtime," and the recommendation of at least hypervisor-level isolation.