DAGs, Topological Sort, and AI Systems

A DAG of AI pipeline steps in topological order

A lot of “AI engineering” looks magical from the outside. Underneath, a surprising amount of it is an old graph problem wearing a new jacket:

Do these steps in an order that respects dependencies — and never get stuck in a loop.

That shape is a DAG: a directed acyclic graph. The algorithm that turns the graph into a safe execution order is topological sorting.

This post is a practical tour: what a DAG is, how topo sort works, and where that combo shows up in modern AI systems.

What a DAG is (in one breath)

A graph is boxes (nodes) and arrows (edges).

Directed means arrows have a direction: A -> B means “B depends on A” (or “A must happen before B”).
Acyclic means you cannot follow arrows and return to where you started. No loops.

Why AI likes that:

Real work has prerequisites (embed needs chunk, generate needs retrieve).
Loops in a plan are dangerous: infinite tool calls, circular feature definitions, “wait for myself.”
Independent branches can run in parallel once their parents are done.

If there is a cycle, topological sort fails — and that failure is a feature. It means your plan is inconsistent.

Topological sorting

A topological order is any linear sequence of the nodes such that every arrow goes forward in the sequence.

For this graph:

A -> B
A -> C
B -> D
C -> D

valid orders include:

A, B, C, D
A, C, B, D

Invalid:

B, A, ...   # B cannot run before A

There can be many valid orders. That freedom is exactly where schedulers find parallelism: B and C do not depend on each other, so they can run together after A.

Kahn topological sort intuition

Kahn’s algorithm (the queue version)

Count incoming edges (indegree) for every node.
Put all indegree == 0 nodes into a queue (they are ready).
While the queue is not empty:
- pop a ready node, append it to the order
- “remove” its outgoing edges (reduce neighbors’ indegrees)
- if a neighbor hits 0, enqueue it
If you finish and some nodes never became ready, there is a cycle.

function topoSort(nodes, edges) {
  const indegree = Object.fromEntries(nodes.map((n) => [n, 0]));
  const graph = Object.fromEntries(nodes.map((n) => [n, []]));
 
  for (const [from, to] of edges) {
    graph[from].push(to);
    indegree[to] += 1;
  }
 
  const queue = nodes.filter((n) => indegree[n] === 0);
  const order = [];
 
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
 
    for (const next of graph[node]) {
      indegree[next] -= 1;
      if (indegree[next] === 0) queue.push(next);
    }
  }
 
  if (order.length !== nodes.length) {
    throw new Error("Cycle detected - not a DAG");
  }
 
  return order;
}
 
topoSort(
  ["ingest", "chunk", "embed", "retrieve", "generate"],
  [
    ["ingest", "chunk"],
    ["chunk", "embed"],
    ["embed", "retrieve"],
    ["retrieve", "generate"],
  ],
);
// -> ["ingest", "chunk", "embed", "retrieve", "generate"]

DFS-based topo sort exists too (finish times, reverse postorder). Same contract: respect edges, detect cycles.

Where this solves AI problems

ML pipelines, compute graphs, and agent plans as DAGs

1. ML / data pipelines

Training a model is rarely one script. It is a dependency graph:

raw logs -> clean -> features -> train -> evaluate -> register
                \-> features_v2 -/

Tools like Airflow, Prefect, Dagster, Kubeflow, and cloud pipeline products lean on DAGs so they can:

run only what changed
retry a failed node without redoing the world
parallelize independent branches
refuse circular task definitions

Topological order is the schedule.

2. RAG and document AI workflows

A typical retrieval-augmented generation path is a DAG whether you draw it or not:

pdf -> parse -> chunk -> embed -> index
query -----------------> embed_q -> retrieve -> prompt -> llm -> answer

You cannot retrieve before embeddings exist. You should not call the LLM before context is assembled. Topo sort (or an equivalent scheduler) turns that dependency map into an executable plan — including parallel parse of many files when they do not depend on each other.

3. Autodiff and compute graphs

Neural nets are compositions of ops. Frameworks build a graph of tensor computations:

x -> MatMul -> ReLU -> MatMul -> loss

Forward pass: evaluate nodes in topological order.
Backward pass: propagate gradients in reverse topological order.

Cycles would break the “finite tape” story of backpropagation. Dynamic frameworks still respect an acyclic execution trace for a given forward run. Compilers (XLA-style) fuse and schedule ops using the same dependency ideas.

So: the math looks like calculus; the engine looks like graph scheduling.

4. Multi-step agents and tool calling

LLM agents often need a plan:

search_docs ----\
                 }-> synthesize -> write_report
query_db -------/
call_weather --/

If synthesize needs all three inputs, those tool calls are parents in a DAG. A scheduler can:

fire independent tool calls in parallel
wait for joins
avoid circular “ask tool A that asks tool B that asks tool A”

Agent frameworks that expose “graphs” or “workflows” are rediscovering this. Even when an LLM proposes steps in natural language, a reliable system validates them as a DAG before execution.

const agentPlan = {
  nodes: ["search", "sql", "merge", "answer"],
  edges: [
    ["search", "merge"],
    ["sql", "merge"],
    ["merge", "answer"],
  ],
};
 
// search and sql can run concurrently after validation
const order = topoSort(agentPlan.nodes, agentPlan.edges);

5. Feature stores and training-serving consistency

Features often depend on other features:

user_id -> account_age
user_id -> last_purchase_at -> days_since_purchase

A feature DAG + topological evaluation prevents circular definitions and ensures training and serving compute features in the same order. That quiet consistency problem is where many “model worked in notebook, failed in prod” bugs hide.

6. Prompt / workflow compilers

Some systems compile a high-level AI workflow into executable steps with caching:

summarize(doc) -> extract_claims(summary) -> verify(claims)

If verify depends on extract_claims, and two claims branches are independent, topo order + memoization means you recompute only the dirty subgraph when an input changes — the same trick build systems (Make, Bazel) have used for decades.

Cycles: when AI needs loops anyway

Wait — agents loop. Training iterates. Chat is multi-turn. Are those DAGs?

Distinguish control loops from dependency cycles:

Kind	Example	Graph trick
Dependency cycle	Feature A needs B needs A	Forbidden in a plan DAG
Iteration over time	training epoch 1, 2, 3…	Unroll into steps, or loop outside the DAG
Agent retry	“tool failed, try again”	New node instance / new run, not an edge back to yourself
Feedback in conversation	user replies	New message state; still acyclic per turn plan

So systems often use a DAG per run or per plan, while a higher-level loop creates the next DAG. That keeps each execution finite and analyzable.

A mini AI scheduler

Here is a tiny sketch of “run independent AI steps when ready”:

async function runDag(nodes, edges, runners) {
  const order = topoSort(nodes, edges); // validates + gives a sequence
  const results = {};
 
  // Smarter versions keep a ready-queue and Promise.all independent nodes.
  for (const node of order) {
    const parents = edges.filter(([, to]) => to === node).map(([from]) => from);
    const inputs = Object.fromEntries(parents.map((p) => [p, results[p]]));
    results[node] = await runners[node](inputs);
  }
 
  return results;
}
 
await runDag(
  ["chunk", "embed", "retrieve", "generate"],
  [
    ["chunk", "embed"],
    ["embed", "retrieve"],
    ["retrieve", "generate"],
  ],
  {
    chunk: async () => chunkDocuments(docs),
    embed: async ({ chunk }) => embedChunks(chunk),
    retrieve: async ({ embed }) => search(embed, query),
    generate: async ({ retrieve }) => llmAnswer(query, retrieve),
  },
);

Production versions add caching, retries, timeouts, and true parallelism on the ready set. The core idea stays: dependencies first, then work.

Why this matters more as AI systems grow

A single ChatGPT box hides the graph. The moment you build:

multi-tool agents
evaluation harnesses
training pipelines
RAG indexers
human-approval steps

…you are designing a DAG whether you name it or not.

Teams that skip the graph model tend to invent ad-hoc await spaghetti, circular imports of “steps,” and heisenbugs where step 4 sometimes runs before step 2. Teams that make the DAG explicit get:

clearer mental models
safer parallelism
cycle detection as a test
selective recomputation
better observability (“which node failed?”)

Mental model to keep

DAG = directed dependencies with no loops.
Topological sort = a valid execution order (and a cycle detector).
AI pipelines schedule data/model work as DAGs.
Autodiff evaluates forward in topo order, backward in reverse.
Agents can plan tool calls as DAGs to parallelize and stay finite.
Loops over time sit above the per-run DAG, not inside its edges.

LLMs generate language. Graphs decide what is allowed to run when. A surprising fraction of shipping AI systems is the second problem — and topological sorting is how we keep that problem honest.