Directed Acyclic Graph (DAG)

Definition

A Directed Acyclic Graph (DAG) is a computational graph where nodes represent agent operations or processing steps, and directed edges define the execution dependencies between those steps. The "acyclic" property means there are no cycles in the graph—execution always progresses forward and eventually terminates. DAGs are the foundational data structure for modeling deterministic workflows where dependencies must be respected, parallel execution is possible for independent branches, and the overall execution order is unambiguous.

Engineering Context

DAGs are the structural backbone of deterministic agent workflows. By modeling agent execution as a DAG, teams get explicit, auditable control over execution order. LangGraph's StateGraph implements a DAG-based execution model. DAGs support parallel execution of independent branches, conditional routing based on state, and clear debugging when something goes wrong—because each node has a fixed set of predecessors and successors. When a workflow requires cycles (e.g., an agent loop that iterates until completion), LangGraph uses conditional edges that can route back to earlier nodes, technically making it a general graph rather than a strict DAG, but the DAG model applies to individual workflow passes.

Related Terms