When does an agent plan need a dependency DAG instead of a linear todo list?

## Two ways to write the same plan A plan is a set of subtasks plus an ordering. The cheapest representation is a linear todo list — an ordered sequence, worked top to bottom, each item ticked off as it completes. The richer representation is a directed acyclic graph: nodes are subtasks, edges are "must finish before", and anything with no path between it is independent. The difference is not cosmetic. A list encodes a **total order**: every item is claimed to come after every item above it. A DAG encodes a **partial order**: only the stated edges are real, and everything else is free. Most real work is partially ordered, so a list systematically over-constrains it. ## Where the edges actually come from A genuine edge exists when one subtask consumes something another produces, or changes state the other reads. In practice they come from three places: 1. **Data flow** — step B's input is step A's output artifact. 2. **State mutation** — A writes to a resource B reads, so B sees a different world depending on order. 3. **Gating decisions** — A determines whether B should run at all, or with what scope. Everything else is incidental sequencing: an artifact of the order the model happened to emit the steps in, not a constraint. ## A worked example An M&A due-diligence agent is given 12,000 documents. Its decomposition is roughly: **collect** the documents from the data room, **dedupe** near-identical versions, **privilege-screen** for attorney-client material, **summarize** each contract family, and **assemble** the final memo. The real edges are: collect → dedupe; dedupe → privilege-screen; dedupe → summarize; privilege-screen → assemble; summarize → assemble. Note what is *missing*: there is no edge between privilege screening and summarization. They read the same deduplicated corpus and write different artifacts. Written as a list, those two sit one above the other and look ordered. Two consequences follow. First, you serialize work that could have run as two branches, roughly doubling wall-clock for that stage. Second, when privilege screening fails on a batch, the list gives you no way to answer "what is still safe to proceed with?" — the graph answers it immediately: summarization is untouched, assembly is blocked. ## When the edges do not matter A DAG is not free. It is more structure for the model to emit correctly, more state to keep in sync, and more machinery in whatever executes the plan. Keep the list when: - the plan is short and genuinely sequential — each step consumes the last one's output; - there is no concurrency available anyway, because a single bottleneck resource serializes everything; - the steps are cheap enough that serializing them costs less than the complexity of the graph. The honest rule of thumb: introduce edges when you will *use* them — to run branches concurrently, or to compute what a failure blocks. Modelling dependencies you never query is ceremony. ## Representing it so a model can hold it The graph has to survive contact with an LLM that re-reads it every turn. What works is keeping it small and explicit: each node gets a stable id, a one-line description, a status, and a `depends_on` list of ids. Anything not listed is independent — stating that convention in the plan itself matters, because otherwise the model re-imposes reading order as if it were dependency order. A flat file of such nodes reads as a list *and* carries the edges, which is usually the right compromise over a nested structure the model has to mentally flatten. A middle option is a **staged plan**: an ordered sequence of stages, with the items inside a stage unordered and independent. That captures most of the available concurrency with far less structure than arbitrary edges, and it is easy for a model to maintain. It is the right default for pipelines whose shape is stage-like. ## What interviewers are listening for Strong answers frame this as "is the work totally ordered or partially ordered?" and then name the two things edges buy — concurrency and blast-radius reasoning — rather than asserting that graphs are simply better. They also acknowledge the cost, and they note the crucial caveat: a DAG makes the *claimed* structure explicit, it does not make it *correct*. The model can assert an edge that does not exist or omit one that does, which is exactly why edges should be justified by data flow or shared state rather than by narrative plausibility.