Planning means deciding several steps of a task before taking the first one. An agent that plans writes down the tool calls a task needs, runs the independent ones at the same time, and can check or search over its plan before it commits to it. Done well, this cuts an agent's waiting time and its token bill several times over. It also brings two dangers. A plan written in advance goes stale when the world surprises it, and trying out alternatives in the real world needs a way to undo what was tried.

The agent of §24.3 does not plan. It is called ReAct, for reasoning plus acting. At every step it writes a short note to itself, calls one tool, and reads the result before it decides the next step. Before every step the model also re-reads the whole conversation so far. That habit is right when each result can change what to do next.

Here is a task where no result can. Ask "which city has more people, the capital of France or the capital of Japan?" A step-by-step agent searches for the capital of France, then the capital of Japan, then the population of Paris, then the population of Tokyo, one after another. Say each model call takes 2 seconds and each search 1 second. Five model calls and four searches in a row take 14 seconds. Yet no search result changes which searches are needed, and the two capitals could be looked up at once. An agent that writes all four searches down first, and runs each one as soon as its input exists, answers in 6 seconds and reads less than half the tokens.

This section asks when thinking ahead pays, and builds four ways to do it.

• A plan can be written before acting and run as a small program, a graph of tool calls that a scheduler runs in parallel.
• A plan can be searched for, by trying several next steps and keeping the promising ones.
• A plan can be checked, by a classical planning algorithm or another verifier.
• A plan can be repaired. During an attempt the agent replans when an observation surprises it, and between attempts it writes down what went wrong.

Behind all four sits one difference between text and the world. A model that writes text can go back to any earlier point in its text for free and continue from there (§15.7). An agent acts on a world that changes and cannot be rewound (§24.1). So an agent's plans go stale, and any search over its actions needs a way back. By the end you will be able to compute how fast a plan can run, how many tokens planning saves, when to replan, and when search over actions is safe, which are the questions an interviewer asks about agent design.

A plan is a small program

Write the capitals question as a plan. Each line is one tool call and gets a name such as #E1. A later call can use an earlier result by writing that name in its argument.

#E1 = search[capital of France]
#E2 = search[capital of Japan]
#E3 = search[population of #E1]
#E4 = search[population of #E2]

A last model call reads the four results and writes the answer. The names #E1 to #E4 are called placeholders. Each one stands for a result that does not exist yet when the plan is written, the way a variable in a program stands for a value computed later.

This format comes from a system called ReWOO (Xu et al. 2023), short for "reasoning without observation", because the plan is written before any tool result is seen. It splits the work into three roles. A planner model writes the whole plan. A worker runs the tool calls. A solver model reads the plan and the results and writes the answer.

The references say what can run at the same time. $E_1$ and $E_2$ need nothing, $E_3$ needs $E_1$, and $E_4$ needs $E_2$. Let's count both ways by hand, with every model call taking 2 s and every search 1 s.

Neither saving is free. The planner had to know, before seeing any result, that it would need two population searches and nothing else. Suppose one search returns the population of the city proper and the other that of the whole metropolitan area. A step-by-step agent can notice the mismatch and search again. The planned executor hands both numbers straight to the solver, which then compares unlike things. We come back to this cost, and its fix, in the part on open and closed loops.

The cell below parses a plan, finds each step's parents (the steps it references), and computes when each step finishes if it starts the moment its parents finish.

All four searches add up to 4 s of work. But no chain of dependent searches is longer than 2 s, and 2 s is how long the searches take when independent calls overlap. The next part turns that observation into exact bounds.

How fast a plan can run

Draw each step as a node, and draw an arrow from step $u$ to step $v$ when $v$ needs $u$'s result. In a plan that can run at all, no chain of arrows leads back to where it started, since a step cannot wait for its own result. Such a picture is called a directed acyclic graph, or DAG, and we write it $\mathcal{D}$. Step $v$ takes $w_v > 0$ seconds, its latency. Two numbers describe how fast a DAG can run. One is all the work added up. The other is the slowest chain of steps that must run one after another.

In the capitals plan $W = 4$ s and $L_{\text{cp}} = 2$ s, the weight of $E_1 \to E_3$ and of $E_2 \to E_4$.

The cell computed finish times by a simple rule. With as many workers as you like, start each step the moment its last parent finishes. Its finish time is then

In plain words, a step finishes its own latency after its slowest parent finishes. Compute $f$ in a topological order, which is any order in which every step comes after its parents, such as the plan's own order. Each $f(v)$ then uses only values already computed. This is dynamic programming over the graph, the same pattern as the Bellman backups of §15.2, which compute each state's value from values already known. By induction on the order, $f(v)$ is the weight of the heaviest path that ends at $v$.

In plain words, with enough workers a plan runs as fast as its longest chain of dependent calls. A scheduler that never sits idle is within a factor of two of the best schedule, on any number of workers. The total work sets the pace when workers are scarce, and the critical path sets it when they are plentiful.

In practice this decides how an executor is built. Finding the exact optimum on $k$ workers is NP-hard in general, so no known algorithm finds it quickly for every plan. Real executors therefore use a greedy rule, and a good tie-breaker is to start ready steps on the critical path first. An interviewer who hands you a DAG of tool calls wants the critical path for unlimited workers and the two bounds for $k$ workers.

Here is greedy scheduling on a six-step plan that compares the prices of two flights to Tokyo in dollars. The two flight searches are slow (3 s each), the exchange-rate lookup is faster (1 s), and each conversion and the final comparison take 0.5 s.

The widget runs the same six calls. The grid on the left sets the dependencies. A filled cell means the row's step must finish before the column's step starts. The timeline below runs the six calls step by step on top and as a plan on $k$ workers underneath, on one time axis, with the steps of a critical path colored. The sliders set the number of workers and the latency of one model call, and the input tokens assume $P_0 = 3{,}000$ and $s = 400$.

What the token count says

Now the token count in general, using the count from §24.1. Every model call in an agent loop re-reads the initial prompt of $P_0$ tokens (instructions, tool descriptions, and the task) plus everything added since. If each turn adds $s$ tokens, the $t$-th call reads $P_0 + (t-1)s$ input tokens. A step-by-step agent that makes $T$ tool calls makes $T + 1$ model calls, one before each tool and one to answer.

Proof. The sum has $T + 1$ terms and $\sum_{t=1}^{T+1}(t - 1) = T(T+1)/2$. For the ratio, factor the first count, $(T+1)P_0 + sT(T+1)/2 = \tfrac{T+1}{2}(2P_0 + sT)$. ∎

In plain words, the step-by-step agent pays to re-read its prompt and its growing transcript at every step, and planning removes all of that repetition. The ratio grows linearly with the number of steps. The size of the prompt changes the absolute saving but not the ratio. With $T = 4$, as in the capitals question, the ratio is $5/2 = 2.5$, the factor counted by hand above.

The model is crude, but it lands near the measurements. HotpotQA is a benchmark of questions that each need facts from two Wikipedia articles. On it, with gpt-3.5-turbo, Xu et al. (2023) report 9,795 tokens per question for the step-by-step agent and 1,986 for the planned one, a ratio of 4.9. The step-by-step agent made about 5 model calls per question, so about 4 tool calls, for which the formula predicts a ratio of 2.5.

Much of the rest comes from something the formula leaves out, the worked examples of the task in each prompt, called few-shot examples. Both agents got six. The step-by-step agent re-reads its examples at every call, and each one is a whole run with every tool result included. The planned agent shows its examples only to the planner, and they are only plans.

The tool-failure result says something about robustness. When every tool failed, the step-by-step agent spent 851 more tokens per question, reasoning over each empty result and searching again. The planned agent spent 111 fewer, since its one solver call could still answer from what the model already knew. Keeping the reasoning apart from the evidence stopped one bad result from steering every later step.

One more practical point. Prompt caching, in which the provider stores the processed prefix of a prompt and charges less to read it again (§24.6), makes the re-read tokens of a step-by-step loop cheaper. It does not remove them. It also shortens each call a little, but the calls still run one after another.

import re

def run_plan(text, tools):
    raise NotImplementedError

def makespan(text, latency, k=None):
    raise NotImplementedError

Searching over thoughts

A planner writes one plan and commits to it. Sometimes an early choice decides everything, and a wrong first step cannot be recovered later. Then it pays to consider several candidate steps, rate them, and continue only from the promising ones.

Tree of thoughts (Yao et al. 2023) does this with a language model. A chain of thought, the step-by-step reasoning a model writes before its answer (§18.1), follows one path. That section listed tree of thoughts among the ways to do better than one chain, with its headline result on the Game of 24. Here we build it. Tree of thoughts cuts the reasoning into intermediate steps, called thoughts, and searches over them as a tree. Each node is a partial solution, and each branch out of it is one possible next thought.

The Game of 24 makes this concrete. You get four numbers and combine them with $+$, $-$, $\times$, and $\div$, using each number exactly once, to make 24. A natural thought combines two numbers into one, so every puzzle takes exactly three thoughts. There are 1,820 ways to choose four numbers from 1 to 13 when repeats are allowed, and exactly 1,362 of them can make 24. That matches the 1,362 puzzles the tree-of-thoughts paper drew from, and it tested on 100 hard ones.

Take the example from the paper, 4, 9, 10, 13. From a state with $n$ numbers there are $\binom{n}{2}$ pairs to combine. Each pair gives six results ($a + b$, $a \times b$, $a - b$, $b - a$, $a/b$, $b/a$). So four numbers give $6 \cdot 6 = 36$ first thoughts. Which of them keep 24 reachable?

How good must the evaluator be, and how much does a wider beam buy? In the simulation below, the evaluator stands in for a model's rating. It gives the true answer (1 if 24 is still reachable, 0 if not) plus Gaussian noise with standard deviation $\sigma$. After the first and the second thought, the search scores the children of every kept state and keeps the $b$ best. It checks the third thought exactly, since an arithmetic check costs nothing.

With a perfect evaluator a beam of one always succeeds, since some live child always ranks first. Noise makes the ranking partly random, and a wider beam is insurance against it. At $\sigma = 1$, success climbs from 25% with $b = 1$ to 72% with $b = 10$, for 4 times the evaluator calls (216 against 54). Rating the whole tree down to the second thought would take up to $36 + 36 \cdot 18 = 684$ calls.

The exact numbers depend on the noise model, but the shape is general. Search pays only when the evaluator ranks states better than chance, and its cost grows linearly with the beam.

The widget runs the same search on 40 puzzles of its own. Each bar is a candidate state, green if 24 can still be reached and grey if not. Press Play to watch one search rate its states, rank them by the noisy rating, and keep the $b$ best at each level. Then move the noise and the beam, and watch the success curve at the top.

The evaluator is also where tree of thoughts generalizes. Replace the model's rating with a process reward model, a network trained to score each intermediate step, and the same breadth-first search becomes the step-level beam search of §18.6. Add visit counts and values passed back up from the leaves, and it becomes Monte Carlo tree search. In an interview, expect to be asked what tree of thoughts costs against plain sampling at the same budget.

from fractions import Fraction

def tot_24(numbers, b, value):
    raise NotImplementedError

Decomposition, and why subgoals interact

A plan splits a task into steps, and language models split tasks readily. They can be prompted to break a problem into easier subproblems, to write a plan before carrying it out, or to send each subtask to a different tool or model. The box below lists the main results. Two failures recur in all of this work.

The first is that plans name actions or tools that do not exist. That one is easy to catch. Before executing anything, validate every step against the tool schemas of §24.2, the machine-readable descriptions of each tool's name and arguments. The second failure is that subgoals interact, so achieving one can undo another. Seeing that needs a model of what each action does. To talk about it precisely we need the language of classical planning.

Classical planning describes a world by facts that are true or false, and each action by three sets of facts. One holds the facts the action needs, one the facts it makes true, and one the facts it makes false. For example, picking block A up from the table needs A to be clear (nothing on top of it), A to be on the table, and the hand to be empty. It makes "holding A" true and makes those three facts false. The best-known formalism of this kind is STRIPS, named after the Stanford Research Institute Problem Solver (Fikes and Nilsson 1971).

Two details of the definition carry weight. The successor deletes first and then adds, so a fact that an action both deletes and adds ends up true. And the goal is a set of facts that must hold, not a whole state, so a final state with extra true facts still satisfies it. The set $\mathcal{A}$ plays the same part as an agent's set of actions in §24.1.

The standard test domain is the blocks world. Blocks sit on a table or on each other, and a hand holds at most one block. Four actions move them. pickup lifts a block from the table, and putdown sets the held block on the table. unstack lifts a block off another block, and stack sets the held block on another block.

The cell below runs a breadth-first planner on the most famous instance. Breadth-first search explores plans in order of length, so the first plan it finds is a shortest one. Block C sits on A, B is on the table, and the goal is the tower A on B on C.

The planner needs 6 steps. This instance is known as the Sussman anomaly, after the researcher who analyzed it (Sussman 1973), and it shows why decomposition is hard. The goal has two subgoals, A on B and B on C. Achieve them one at a time, each by its own shortest plan, and see what happens.

Either order fails, after 8 steps each. Putting A on B first buries B, so B cannot then go on C without taking A off again. Putting B on C first leaves A under C, and freeing A means taking the new tower apart. The subgoals interact, and the only way to see that is to reason about what each action deletes.

The breadth-first planner never had this problem, because it searches over whole states and so sees every interaction. It also never looks at the names. In the second half of the cell, renaming every action and fact to nonsense changes nothing for it, apart from the names in its answer. Keep that in mind for the next part.

from collections import deque

def apply(state, action):
    raise NotImplementedError

def validate(s0, goal, plan, actions):
    raise NotImplementedError

Can language models plan?

PlanBench (Valmeekam et al. 2023) turned that question into a benchmark. It poses problems from the domains of the International Planning Competition in natural language, and it checks each returned plan with a plan validator, a program that applies the actions one by one as in the STRIPS definition. Its sharpest test is called Mystery Blocksworld. It has the same problems with every action and fact renamed to an unrelated word. The logic stays the same, and anything a model might have memorized about blocks is gone. A classical planner cannot tell the two versions apart, as the renaming cell above showed. A language model can, and that is what the test measures.

Read the numbers both ways. A reasoning model that plans in its own chain of thought is a large step up from earlier models, and on familiar problems it is nearly perfect. But the drop from 97.8% to 52.8% when only the names change says that much of the success rests on knowing the domain. The drop with plan length says the planning is not yet systematic.

The design that follows is to pair the model with checkers. Kambhampati et al. (2024) argue that a model that generates one token at a time cannot by itself guarantee that a plan is correct, or verify one. But it is an excellent source of candidate plans, domain knowledge, and translations between formats. So they propose a loop they call LLM-Modulo. The model proposes a plan, and critics check it (a plan validator, constraint checkers, unit tests). Their criticism goes back to the model, until a plan passes or a budget runs out.

Call a critic sound if it never accepts an invalid plan. As long as the critics are sound, every plan that leaves the loop is correct, because only plans that pass get out. This is a guarantee by construction, and it holds however weak the model is. A weak model only makes the loop run longer.

Two concrete versions exist. LLM+P (Liu et al. 2023) has the model translate a natural-language problem into PDDL, runs a classical planner, and translates the plan back. It found optimal plans for most of its benchmark problems, while the model alone failed to produce even a feasible plan for most of them. TravelPlanner (Xie et al. 2024) is a benchmark of travel itineraries with many constraints, on which GPT-4 alone produced a fully valid plan for 0.6% of requests. An LLM-Modulo planner for it (Gundawar et al. 2024) raised GPT-4-Turbo's success rate by a factor of 4.6.

The debate is real. One side holds that claims of planning must survive renaming and verification. The other holds that reasoning models keep closing the gap. Both sides agree on the engineering, which is to verify plans whenever a verifier exists.

The guarantee has a price in attempts. If each proposal is valid with probability $p$, independently, then $n$ proposals give at least one valid plan with probability $1 - (1-p)^n$. With $p = 0.3$ and $n = 5$ that is $1 - 0.7^5 = 0.83$. This is the pass@$n$ of §18.2, the chance that at least one of $n$ samples is correct, with the validator picking it out. Proposals from one model are not independent, though, since it tends to make the same mistake again. That is why the criticism fed back between attempts matters as much as the number of attempts.

Open loop, closed loop, and when to replan

A plan written before acting rests on assumptions about the world. The flight is still available, the file is where it was, and the API returns what it did yesterday. Running the plan without looking at the results is called open-loop control. Looking after every step, and replanning when something surprises you, is called closed-loop control. Control engineers also name a strategy in between. You plan far ahead, execute a little, observe, and replan from where you are. That is receding-horizon control, also called model predictive control.

How often should an agent look? Here is the simplest model in which the trade-off can be computed. It has three assumptions.

• Each of $T$ steps, independently, makes the plan stale with probability $u$. That is, the world deviates from what the plan assumed.
• Acting on a stale plan is fatal. The next step does the wrong thing, and it cannot be undone.
• At a check the agent observes, notices any deviation, and replans successfully with probability $r$.

In plain words, only the steps right before a look are protected. Each look multiplies the success probability by $(1 - u(1-r))/(1-u) = 1 + ur/(1 - u)$.

This is the arithmetic of detection and repair from §24.1 again. There a step goes wrong with probability $\varepsilon$, a check detects the error with probability $d$, and a repair fixes it with probability $q$. So a step survives with probability $p_{\text{eff}} = 1 - \varepsilon(1 - dq)$. Here $u$ plays the part of $\varepsilon$ and $r$ the part of $q$, with every deviation detected. If a check notices a deviation only with probability $d$, a closed-loop step survives with probability $1 - u(1 - dr)$, the same form.

Periodic replanning barely helps here, because a deviation between checks does its damage before anyone looks. The cure is not more frequent planner calls but cheaper looks. In an agent, the observation arrives anyway as the tool's result. So the agent can compare every result with what the plan expected, and call the planner only when they disagree.

This event-triggered replanning reaches closed-loop success (0.90) with about $uT = 1$ replan on average instead of 20. It is what plan-and-execute systems with a replanner do. LLMCompiler, for example, sends results back to its planner when the plan needs to change. It requires the plan to state what it expects from each step, so that a disagreement can be detected at all. For the capitals plan, the expectation could be "a city-proper population in millions", and a metropolitan figure would then trigger a replan.

When acting on a stale plan is only sometimes fatal, the best interval between checks becomes a genuine trade-off. Exercise 24.4d adds a hazard $\phi$, the probability that a step taken on a stale plan is fatal, and a cost per check. With harmless staleness ($\phi = 0$), one check at the end is best. That is the "try, check, redo" pattern that works for reversible actions. With dangerous staleness, check after every step. In between, the answer depends on $\phi$ and on the cost. With $T = 30$, $u = 0.05$, $r = 0.9$, and a cost of 0.01 per check, the best interval is 15 steps at $\phi = 0.01$, 3 steps at $\phi = 0.1$, and every step at $\phi = 0.3$.

With a learned model of the environment, the same receding-horizon idea becomes planning by sampling candidate action sequences, scoring them in the model, executing only the first action, and replanning. That is how model-based agents act in robotics and games.

import math
import numpy as np

def p_success(T, u, r, phi, k):
    return (1 - u) ** T            # placeholder: the open-loop answer, whatever k is

def simulate(T, u, r, phi, k, n, seed):
    raise NotImplementedError

Reflecting between attempts

Replanning repairs a plan while an episode is still running. When an attempt has already failed, and the task can be started again from the same state, there is a second place to repair, between attempts. The cheapest repair is a plain retry, a fresh sample from the same agent. The next cheapest is to tell the next attempt what went wrong with the last one.

Suppose the capitals agent compared a metropolitan population with a city-proper one, and an evaluator rejected its answer. A retry may well make the same mistake. A note that says "the two figures covered different areas, so ask for the city proper both times" changes what the next attempt does. Writing that note is called reflection, and §24.3 listed it as one more kind of thought an agent can write. This part makes it exact and asks what it adds over plain retries.

The ALFWorld baseline is exactly the comparison this part needs, retries against lessons. Why do retries stop improving, and what does a lesson change? Let attempt $i$ succeed with probability $p_i$, given that attempts $1, \dots, i-1$ failed. Plain retries of one agent keep $p_i = p$, so all $n$ attempts fail with probability $(1-p)^n$. This is the pass@$n$ arithmetic of §18.2, the chance that at least one of $n$ independent tries succeeds.

But $p$ belongs to a task, not to the agent. Take a task the agent gets wrong for a systematic reason, such as misreading a tool's output the same way every time. Its $p$ is near 0, and resampling the same agent cannot reach it. A lesson can, because it changes the next attempt instead of redrawing it.

The simplest model of a lesson says that each one removes a fixed fraction $\nu$ of what was making the attempts fail. With $\nu = 0.3$, a task that fails 80% of the time fails 56% of the time after one lesson and 39% after two. In symbols, $1 - p_{i+1} = (1 - \nu)(1 - p_i)$ with $0 \le \nu \le 1$.

In plain words, retries shrink the failure probability by the same factor with every attempt. Lessons shrink it faster than that, since the exponent grows like $n^2/2$, and only lessons reach the tasks that a fresh sample always fails. All of the gain sits in $\nu$, and $\nu$ is not a property of the agent alone. It measures how often the diagnosis names the real cause and the next attempt acts on it, so it can be no better than the evaluator's signal.

The model is generous on purpose, since it lets every lesson help. Real lessons can be wrong. So whether they help depends on the evaluator. With an external signal, such as a failing unit test, an error message, or the environment's verdict, the lesson has something true to say, and $\nu$ can be large.

Without an external signal, the evaluator is the model judging itself. It can accept a wrong attempt and end the loop early, or reject a right one. A lesson about an error that is not there can lower $p$ instead of raising it. §26.1 weighs the evidence on self-correction without an external signal, which helps little or hurts. It also explains why the self-written tests helped on HumanEval but not on MBPP, a second benchmark of short Python problems. On MBPP, a program that passed its own tests was far more often wrong, so a wrong attempt ended the loop early.

Two conditions from this section apply as well. Every attempt must restart from the same state. ALFWorld provides that by resetting the environment, and code provides it by rerunning tests in a sandbox. So reflection needs the same reversibility that search over actions needs, as the next part shows. And every lesson costs a model call and lengthens every later prompt, so the fair baseline is retries at equal compute, as it was for tree of thoughts.

Searching over actions needs a way back

Tree of thoughts searched over text, and the STRIPS planner searched over states it computed from a description of the actions. Neither touched a world, so neither had anything to undo. To try a different thought, tree of thoughts goes back to an earlier prefix of its text and continues from there. A model's text can always be cut back to any prefix and continued, as §15.7 notes. The planner backtracks by taking another state from its queue.

Search over actions is different. Clicking a button, sending a message, or running a database migration changes the world, and the world has no "go back to the prefix" operation.

Monte Carlo tree search is the standard way to search over moves. It repeats four steps. It walks down a tree of states, choosing at each node the child that looks best after adding a bonus for children it has tried rarely. It expands the leaf it reaches. It scores the new state. And it passes the score back up the path, updating an average at every node. §18.6 used it over reasoning steps, with the selection rule of AlphaZero, the game-playing system of Silver et al. (2017),

Here $Q(s, a)$ is the average value backed up through action $a$ in state $s$, $P(s, a)$ is the policy's prior probability of $a$, $N$ counts visits, and $c$ is a constant that trades exploration against exploitation. In plain words, go where the value has been high, but also where the policy thinks a move is plausible and you have not looked much yet. §26.2 builds the whole search for a two-player game and runs it by hand on one small enough to solve.

Language Agent Tree Search, or LATS (Zhou et al. 2023), runs this kind of search with an agent's actions as the moves. It selects children with a closely related rule called UCT (upper confidence bounds applied to trees), $V(s) + w\sqrt{\ln N(p)/N(s)}$ for a child $s$ of node $p$. Here $V$ is the value estimate, $N$ counts visits, and $w$ sets how much to explore. LATS values a state by combining the model's own score with how often independent samples agree. It also feeds reflections on failed attempts into later ones, and it uses the environment's real feedback.

LATS reached 92.7% pass@1 on HumanEval with GPT-4, and an average score of 75.9 on WebShop, a simulated shopping site, with GPT-3.5. Its authors state the assumption plainly. LATS needs to return the environment to earlier states. That holds for code checked against tests and for questions answered from a fixed set of documents. It fails for most of the real world.

Koh et al. (2024) took search to realistic websites. Their agent runs best-first search over web pages, always expanding the page that a value function rates most promising. The value function is a multimodal model that reads the page and scores how likely it is to lead to completing the task. A browser's back button does not restore a page reliably, since going back can lose the scroll position and text already typed. So every backtrack resets the environment to the start and replays the stored action sequence to reach the chosen page.

They tested on VisualWebArena and WebArena, two benchmarks of tasks on realistic self-hosted websites such as an online shop, a forum, and a classified-ads site, each task checked by a script. With depth 5, branching factor 5, and a budget of 20 node expansions per step, search raised GPT-4o's success on VisualWebArena from 18.9% to 26.4%. On WebArena it raised success from 15.0% to 19.2%, a 28.0% relative improvement. The price was up to 20 times as many model calls. The authors also name the hard limit. For deployment, the search space must exclude destructive actions, such as placing an order, which cannot be undone.

There is another way back, which is never to leave. Search can run inside a model of the world instead of the world itself. The agent imagines what each candidate action would do and acts only on the best one. The box below describes two systems that do this.

The price is that the model can be wrong, and its errors compound like those of any other chain of steps. If each imagined step is right with probability $p$, an imagined rollout of $H$ steps is right with probability $p^H$, the compounding arithmetic of §24.1. With $p = 0.9$ and $H = 5$ that is $0.59$, so a value computed at the end of a long imagined rollout often scores a world that does not exist. So imagined rollouts should be short and end in a real check. The action finally executed should itself be reversible or confirmed. And the next step plans from the real observation that comes back, never from the imagined one.

Learning such models of an environment, and planning with them while keeping their errors in check, is a subject of its own, planning with learned world models.

Resets also cost. Suppose each expansion needs a reset and a replay of the path to its node. Then a budget of $n_{\text{exp}}$ expansions at depth at most $D_{\max}$ costs up to $n_{\text{exp}}$ resets and $n_{\text{exp}}D_{\max}$ replayed actions, on top of the model calls. With 20 expansions at depth 5 that is 20 resets and up to 100 replayed clicks for one step of the task. That is why sandboxed environments that can be saved and restored in milliseconds matter so much for agents, a point §24.5 takes up for code.

import heapq

def best_first(env, value, is_goal, budget):
    raise NotImplementedError

When planning pays

Put the pieces side by side. Each approach buys something and assumes something, and the table names the system that introduced or measured each one.

Reasoning models change the balance. A model trained to think at length before answering (§18.7) already decomposes, checks, and backtracks inside one chain of thought. That is why o1-preview jumped on PlanBench without any external help. It is also why prompting scaffolds, programs that wrap a model in a fixed pattern of calls such as tree of thoughts, add less with such models than they did with GPT-4.

What a better model does not replace is the part of planning that is about the world rather than about thinking. Independent calls still finish faster in parallel, and current APIs let a model request several tool calls in one turn so that the harness, the program that runs the loop, can execute them at once. Irreversible actions still need confirmation. Stale plans still need fresh observations. And a verifier, when one exists, is still the only way to a guarantee.

In practice

Production executors run a DAG of tool calls as asynchronous tasks. The model's own parallel tool calls give the same effect one layer at a time. The sketch below has both.

• The first function is a DAG executor. It starts each step when its parents finish, with at most max_workers steps running at once.
• The second is one turn of a tool-use loop. All the calls the model requested run at the same time, and their results return together, each tied to its call by an id.

When the model emits independent calls in one turn and the harness runs them together, the plan runs one layer of the graph per model call. A layer here is a set of steps whose parents all lie in earlier layers. So a plan with $D$ layers costs $D + 1$ model calls, plus the sum over layers of each layer's slowest call.

The capitals plan has two layers, the two capitals and then the two populations. With 2 s model calls and 1 s searches it takes $3 \cdot 2 + 1 + 1 = 8$ s, between the 6 s of the planned DAG and the 14 s of the step-by-step loop. In general this sits between the planned DAG ($L_{\text{cp}}$ plus two model calls) and the fully sequential loop. It keeps the model in the loop between layers, where it can react to surprises, such as the mismatched populations.

Read more

• Xu et al. (2023). ReWOO: Decoupling Reasoning from Observations for Efficient Augmented Language Models. The planner, worker, and solver design, its token analysis, and the tool-failure experiment.
• Kim et al. (2023). An LLM Compiler for Parallel Function Calling. Plans as DAGs executed in parallel, with streaming to the executor and replanning.
• Yao et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. The four components, breadth-first and depth-first search, and the Game of 24 with its cost analysis.
• Zhou et al. (2023). Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models. Monte Carlo tree search over an agent's actions, with model-based values, reflection, and its reversibility assumption stated.
• Koh et al. (2024). Tree Search for Language Model Agents. Best-first search on real websites, reset and replay for backtracking, and the discussion of destructive actions.
• Valmeekam et al. (2023). PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change, and Valmeekam et al. (2024), LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench. The benchmark, Mystery Blocksworld, and the reasoning-model results.
• Kambhampati et al. (2024). LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks, and Liu et al. (2023), LLM+P: Empowering Large Language Models with Optimal Planning Proficiency. Two ways to pair a model with sound planners and verifiers.
• Xie et al. (2024). TravelPlanner: A Benchmark for Real-World Planning with Language Agents, and Gundawar et al. (2024), Robust Planning with LLM-Modulo Framework: Case Study in Travel Planning. A planning benchmark with many hard constraints, and an LLM-Modulo system that raised success on it.
• Shinn et al. (2023). Reflexion: Language Agents with Verbal Reinforcement Learning. The actor, evaluator, and self-reflection loop with an episodic memory, and the ALFWorld and HumanEval results against plain retries.
• Gu et al. (2024). Is Your LLM Secretly a World Model of the Internet? Model-Based Planning for Web Agents, and Hao et al. (2023), Reasoning with Language Model is Planning with World Model. Search inside a model of the environment instead of the environment, on websites (WebDreamer) and over reasoning steps (RAP).
• Ahn et al. (2022). Do As I Can, Not As I Say: Grounding Language in Robotic Affordances, and Huang et al. (2022), Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents. Why model-written plans must be grounded in the actions an agent actually has.

Watch next

▶

▶

▶