Plans as graphs

A plan is a graph

A plan is a set of steps. Each step names a tool and its arguments, and may use the result of an earlier step. That makes it a graph, not just a list.

Take "What is the total population of the capitals of Norvia, Sundra and Ilmar?". Finding each capital needs nothing else, so the three lookups are independent. Finding a capital's population needs that capital's name, so each is blocked on its own first step. Group the steps into rounds, where a round only needs earlier rounds:

Steps in one round can run together, so the time is set by the longest chain of dependent steps (the critical path), not by the number of steps. The example computes rounds with a short function: repeatedly take every step whose dependencies are done. If it finds steps but no ready one, the plan has a cycle and is invalid, which is worth checking before running any plan a model wrote.

Three ways to run the same work

1. Adaptive (ReAct). One model call per step. After each observation the model decides what to do next. Nothing is decided before it is needed.
2. Plan only. One model call writes the whole plan. Code runs it (rounds in parallel). One last model call writes the answer. If a step errors, it stops.
3. Plan with replanning. Like plan only, but when a step fails or the plan turns out to be missing steps, the model is called again to repair the plan, up to a limit (three here).

With all tools working, on ten tasks (eight answerable, two about a country that is not in the knowledge base so the right answer is "unknown"):

(Per task, averaged. A model call counts 3 time units and a tool call 1; a round of parallel tool calls counts once. "Prompt words" is the instructions plus history sent each call, summed.)

Reading it:

• Cost. Adaptive makes about twice the model calls and sends about three times the words, because each call re-sends the history so far (module 1's growth).
• Speed. The plans take under half the time, mostly because rounds run together and the model is not in the loop between steps.
• The 10% miss. Plan only fails the task "Which country has the capital with the largest population?". The right steps depend on the list of countries, which the planner has not seen. This is the central limit of planning ahead.

The task that cannot be planned up front

The plan for the largest-capital question has one step: list the countries. Only after reading the result can the agent write the other twelve (a capital lookup and a population lookup per country). Plan only has no move for that moment and returns nothing. Adaptive just keeps going (14 model calls, 13 tool calls). Plan with replanning makes one extra model call at the point where the plan runs out ("now that the list is known, here are the next steps"), then runs all twelve lookups in parallel rounds: 3 model calls in all.