AI Workflows Need Topological Sort

AI workflows require topological sorting to ensure tasks execute in correct dependency order, as consumers cannot run before their producers finish. Directed acyclic graphs (DAGs) model these workflows, and topological sort computes an execution sequence where producers always precede consumers, enabling parallel execution of independent tasks. This approach is critical for correctness and scalability in complex AI pipelines like document processing and retrieval-augmented generation systems.

Every AI workflow is a dependency problem. You have steps that produce outputs, other steps that consume those outputs, and a hard constraint: consumers cannot run before their producers finish. Get the order wrong and you read stale data, call a tool with missing context, or trigger an agent before its inputs are ready. Directed acyclic graphs DAGs https://en.wikipedia.org/wiki/Directed acyclic graph are the right model for this. Topological sort https://en.wikipedia.org/wiki/Topological sorting turns a DAG into an execution order. Together they form a primitive in applied AI system execution, and understanding them at a first-principles level is important when you design, debug, and scale workflows. The Dependency Problem in AI Workflows Take a realistic document processing pipeline https://en.wikipedia.org/wiki/Pipeline computing : - Fetch raw documents from storage - Chunk and clean the text Embed https://en.wikipedia.org/wiki/Word embedding each chunk- Store embeddings in a vector index https://en.wikipedia.org/wiki/Vector database - Run a retrieval query https://en.wikipedia.org/wiki/Information retrieval against the index - Pass retrieved chunks into a prompt template https://en.wikipedia.org/wiki/Prompt engineering - Call the LLM https://en.wikipedia.org/wiki/Large language model - Parse and validate the output Each step depends on the one before it. If you run step 3 before step 2 finishes, you embed dirty text. If you run step 5 before step 4, you query an incomplete index. The dependencies are not optional constraints - they are correctness constraints. In a simple linear pipeline you can just run steps 1 through 8 in order. But real workflows branch. Some steps are independent of each other. Some steps fan out into parallel subtasks and fan back in. A linear list breaks down fast. This is where a DAG becomes the right abstraction. Modeling Workflows as DAGs A DAG represents a workflow as a set of nodes tasks and directed edges dependencies . An edge from A to B means “A must complete before B starts.” The acyclicity constraint means there are no circular dependencies - a task cannot transitively depend on itself. Here is a branching RAG pipeline https://arpitbhayani.me/blogs/rag-production modeled as a DAG: keyword filter and retrieve are independent of each other once store index finishes. They can run in parallel. merge context cannot start until both finish. A linear list cannot express this. A DAG can. Topological Sort A topological ordering of a DAG is a sequence of all nodes such that for every edge , node appears before . Producers always precede consumers. Kahn’s algorithm https://en.wikipedia.org/wiki/Topological sorting Kahn's algorithm computes this in time. Applied to the pipeline above, this produces an order where fetch documents runs first, call llm runs last, and keyword filter and retrieve appear before merge context but without any ordering constraint between each other. That freedom is what enables parallelism. Topological Sort Beyond Ordering Parallelism for Free Nodes at the same “level” of the topological order have no dependency between them. They can run concurrently. A smarter scheduler groups nodes by their earliest possible start time: php def execution levels graph: dict str, list str - list list str : in degree = defaultdict int for node in graph: for dep in graph node : in degree dep += 1 levels = ready = n for n in graph if in degree n == 0 while ready: levels.append ready next ready = for node in ready: for dep in graph node : in degree dep -= 1 if in degree dep == 0: next ready.append dep ready = next ready return levels Each list in levels is a batch of tasks that can execute in parallel. Tools like Prefect https://www.prefect.io/ and Airflow https://airflow.apache.org/docs/apache-airflow/stable/index.html compute exactly this to maximize executor throughput https://en.wikipedia.org/wiki/Throughput . Cycle Detection Before Execution If a user or a config declares a circular dependency, len order = len graph catches it before a single task runs. This is not a nice-to-have. A cycle means a deadlock https://en.wikipedia.org/wiki/Deadlock : A waits for B, B waits for A, nothing makes progress. Detecting it at definition time rather than runtime is the difference between a clear error message and a hung pipeline at 2am. Multi-Agent Systems Are DAGs Multi-agent orchestration frameworks like LangGraph https://langchain-ai.github.io/langgraph/ model agent interactions as DAGs for the same reason: to enforce correct execution order across agents that produce and consume each other’s outputs. Consider a research workflow with four agents: The orchestrator cannot dispatch writer agent until critic agent finishes, and cannot dispatch critic agent until summarizer agent finishes. Topological sort produces this order automatically from the dependency declarations. The orchestrator does not need to hardcode sequencing logic. Now add a parallel branch: search agent and retrieval agent are independent. They can run simultaneously. summarizer agent waits on both. The topological sort respects this: both search agents appear in the same execution level, and summarizer agent appears in the next level only after both have zero remaining dependencies. This scales. Add ten agents, add conditional branches, add fan-outs - the DAG model and topological sort handle the complexity. Hardcoded sequential dispatch does not. Incremental Re-execution When an upstream task fails or an input changes, you do not need to re-run the entire pipeline. Traverse the graph forward from the affected node and recompute only the nodes in its subgraph. Every node outside that subgraph has valid cached output. This is standard in build systems Bazel https://bazel.build/ , Buck https://buck.build/ and is increasingly common in AI pipeline frameworks. The DAG structure is what makes it tractable. Without explicit dependency edges you cannot know which downstream nodes are affected. What to Watch Out For Fan-in bottlenecks https://en.wikipedia.org/wiki/Bottleneck software are real. If ten parallel tasks all feed into one merge node, the merge node cannot start until the slowest of the ten finishes. Topological sort tells you the order correctly but does not automatically balance work. Profile the critical path https://en.wikipedia.org/wiki/Critical path method - the longest chain of dependent tasks - to find where parallelism gains are actually limited. Cycles in configuration are a user error, not a framework bug. Build validation that catches them at workflow definition time, surfaces a clear error with the offending cycle identified, and rejects the workflow before any execution begins. The Mental Model to Keep A DAG is a contract. It says: here are the tasks, here are their dependencies, and here is the guarantee that there are no circular waits. Topological sort is the mechanism that converts that contract into an actionable execution schedule. When you design an AI workflow, draw the dependency graph first. Identify which tasks are truly sequential and which are independent. That graph is your specification. The topological ordering is your scheduler’s input. Everything else - parallelism, cycle safety, incremental recomputation - falls out of the structure you have already declared. Footnote: DAGs model AI workflows and multi-agent systems as dependency graphs where edges encode execution order constraints. Topological sort converts this graph into a valid task schedule in time, detects circular dependencies before execution begins, and reveals which tasks can run in parallel. For multi-agent orchestration, this means agents are dispatched only when their inputs are ready, with no hardcoded sequencing logic required.