Dependency-Aware Planning: Ordering Work That Blocks

Ask an agent to plan a task and you get a numbered list. The list is executed top to bottom, which quietly asserts that every step depends on the one before it. That assertion is almost never true, and believing it costs you both speed and recoverability.

The alternative is to treat a plan as a graph rather than a sequence. Each step declares what it needs and what it produces, and the executor derives the order. This is not a novel idea — build systems have worked this way for decades — but agent frameworks have been slow to adopt it.

What a flat list hides

Three things, each of which shows up as a real cost.

It hides parallelism. Writing tests for module A and updating documentation for module B have nothing to do with each other, but a linear plan runs them one after the other. On a task with ten independent leaves, that is roughly ten times the wall-clock latency you needed.

It hides the true blast radius of a failure. If step three fails in a linear plan, the honest answer to "what else is invalid" is unknown, so most systems either restart everything or blindly continue. With declared dependencies you know precisely which downstream steps are now unsafe and which are untouched.

It hides ordering bugs. A model producing a list will sometimes put migration after the code that uses the new column, because nothing in the representation forces it to be consistent. If steps declare their inputs, the contradiction becomes a cycle you can detect before running anything.

Make the edges explicit

The mechanism is straightforward: every step declares the artefacts it consumes and the artefacts it produces. An artefact can be a file path, a database table, a running service, a named piece of information, or a symbolic marker like schema_migrated.

The edges then fall out of the declarations. Step D consumes api_client.ts, step B produces it, so B precedes D. Nobody had to sequence anything by hand, and there is no way for the plan to be internally inconsistent without producing a detectable cycle.

Ask the planning model for this shape directly rather than for a numbered list. Structured output makes it enforceable — a schema with id, consumes, produces and description per step is easy to validate, and a plan that fails validation can be regenerated before anything runs. Structured outputs and JSON mode covers making the model comply.

Validate the graph before you spend a token

A dependency graph supports checks that a list does not, and all of them are cheap.

Detect cycles with a topological sort. A cycle means the plan is impossible as stated, and the failure message tells the model exactly which steps are mutually blocking, which makes the retry far more likely to succeed than a generic "that did not work".

Detect unproduced inputs. If a step consumes an artefact that no earlier step produces and that does not already exist, the plan has a hole. This catches the common case where the model assumed a file exists because the name sounded plausible.

Detect write conflicts. Two steps that both produce the same artefact and have no ordering between them will race. Either they should be merged, or one depends on the other and the model forgot to say so. This check alone eliminates a large share of the mess that comes from parallel file edits.

Execution becomes scheduling

Once the graph is valid, running it is a scheduler problem. Maintain a ready set of steps whose dependencies are all satisfied, dispatch as many as your concurrency limit allows, and re-evaluate the ready set as each completes.

Concurrency limits matter more than they do in a build system, because each concurrent step is an agent session with its own token spend and its own rate-limit footprint. Four in flight is usually a reasonable ceiling before you start hitting provider limits and losing the gains to retries. Rate limits and retries covers what happens when you push past it.

Failure handling gets sharper too. When a step fails, mark its transitive dependents as blocked and let everything independent continue. You end a partially failed run with a precise picture: these twelve steps succeeded, these three are blocked on one failure, and the retry has a scope of four steps rather than the whole task. Agent error recovery patterns covers what to do with the failed one.

Replanning without starting over

Plans made before exploration are made in ignorance, so most of them need revision once real information arrives. The graph makes revision surgical instead of wholesale.

When a step discovers something that invalidates the plan — the module is structured differently than assumed, a dependency does not exist — you regenerate only the unstarted portion of the graph, keeping completed nodes and their produced artefacts as fixed inputs. The model plans forward from a known state rather than re-deriving everything.

This is the practical advantage over rigid plan-and-execute, and it keeps most of the structure that makes plan-and-execute worth having in the first place. Agent planning strategies covers where each approach sits.

Where it is not worth it

For a three-step task, the graph machinery costs more than it returns. The planning tokens, the validation code and the scheduler are overhead on work that a linear loop would finish in a minute.

It also fights tasks that are genuinely sequential and exploratory, where each step's existence depends on what the previous one found. You cannot declare dependencies for steps you have not conceived of yet, and forcing a graph on that work produces elaborate plans that get discarded immediately.

The sweet spot is medium-to-large tasks with a knowable structure and several independent branches: a multi-module refactor, a migration touching several services, a batch of related fixes. Below that, keep the loop simple. Above that, you are into orchestration territory where how you draw the subtask boundaries matters more than how you schedule them.

What to build first

Ask your planner for steps with explicit consumes and produces lists. Validate for cycles, missing inputs and write conflicts, and regenerate on failure with the specific violation in the message. Execute with a ready set and a concurrency cap of about four. On failure, block only the transitive dependents. Replan only the unstarted subgraph.

The scheduler is under a hundred lines. The validation is what pays for itself, because it turns a category of silent mid-run failures into an error you see before spending anything.