Verdict
The decision is mechanical once you name your control-flow requirements. A DAG cannot express what agents fundamentally do - loop until done: Apache Airflow's own docs define the DAG as acyclic and the tutorial states Airflow raises an error if it detects a cycle, so retry-until-quality-passes and agent-tool loops must be faked with retries or dynamic task mapping. A state graph makes cycles first-class but inherits their failure mode - LangGraph bounds every run with a recursion_limit and raises GraphRecursionError when a loop doesn't converge (the default was 25 supersteps for years; langgraph 1.0.6 raised it to 1000, per the official graph-API docs - which changes how late a runaway loop gets caught, not whether termination is your problem). An explicit finite state machine gives you enumerable, auditable states but suffers combinatorial state explosion the moment error handling and conversation branches multiply. So: graphs beat chains only when you need branching, joins, retries mid-flow, human-in-the-loop pauses, or persistent checkpointed state; DAGs win for batch fan-out/fan-in with no cycles; FSMs win when a regulator or reviewer must be able to enumerate every reachable state. And per Anthropic's own 'Building Effective Agents' guidance, if none of those hold, a plain chain of composed LLM calls - no orchestration framework at all - is the correct default, not a naive one.
Each model maps to a different guarantee. Acyclicity is a real constraint, not a framework quirk: Airflow's core-concepts docs (airflow.apache.org) define DAGs as directed acyclic graphs and error on cycles, which is exactly why data-engineering teams that try to run agent loops on their existing orchestrator end up encoding 'loop' as schedule-level re-runs or bounded dynamic task mapping. State graphs (LangGraph and its imitators) exist precisely to legalize cycles over a shared state object - with the cost that termination is now your problem, bounded by an explicit recursion limit (GraphRecursionError on breach; the default jumped from 25 supersteps to 1000 in langgraph 1.0.6 - a tacit admission that real agent workloads kept hitting the old ceiling, per LangGraph's graph-API docs). FSMs/statecharts (the XState lineage) trade expressiveness for verifiability - every state and transition is enumerable - but practitioners consistently document the state-explosion wall for open-ended conversational flows, which is why statecharts are recommended for bounded workflows rather than exploratory agent behavior. The research current runs toward determinism: the GraphBit paper (arXiv 2605.13848) argues prompted orchestration suffers hallucinated routing, infinite loops, and non-reproducible execution, and demonstrates an engine-orchestrated deterministic DAG with typed-function agents and a Rust routing engine reporting 67.6% accuracy on GAIA with zero framework-induced hallucinations - evidence that pushing control flow out of the prompt and into an explicit structure is what makes agent systems debuggable. Anthropic's 'Building Effective Agents' essay draws the same boundary from the other side: workflows are LLMs on predefined code paths, agents are model-directed control flow, and teams should start with the simplest composable pattern that works instead of reaching for a graph framework on day one.
Decision Table
| Criterion | Edge | Explanation |
|---|---|---|
| Cycles and loop-until-done semantics | State graph (cyclic graph with shared state - LangGraph-style) Best edge | This is the load-bearing difference. Agent behavior is a loop - call tool, evaluate, decide, repeat - and a DAG cannot represent it: Airflow's docs define the graph as acyclic and the framework errors on detected cycles (airflow.apache.org core-concepts and tutorial). DAG users fake iteration with task retries (runtime behavior, not a graph edge), dynamic task mapping (fan-out, still acyclic), or scheduling the whole DAG repeatedly. A state graph makes the loop an explicit edge back to a prior node, guarded by a condition on shared state. FSMs also support cycles natively (transitions can return to prior states), so if you don't need shared rich state, an FSM handles loops too - the graph wins overall because it carries a typed state object through the cycle. |
| Guaranteed termination and runaway protection | DAG pipeline (directed acyclic graph - Airflow-style) Best edge | Acyclicity buys you a proof: a DAG run always terminates - every execution visits finitely many tasks. State graphs must bolt termination on: LangGraph kills a run with GraphRecursionError when its recursion_limit is exceeded - and the default moved from 25 supersteps to 1000 in langgraph 1.0.6 (official docs), meaning a runaway loop on defaults now burns 40x more model calls before dying. That incident class simply cannot exist in a DAG. FSMs sit between: cycles are possible, but because states are enumerable you can statically detect which cycles exist and guard them. If your workload is genuinely acyclic - ETL for a RAG index, batch document processing - taking the DAG's free termination guarantee is strictly better than carrying a recursion limit you never intend to hit. |
| Human-in-the-loop pauses and resumable checkpoints | State graph (cyclic graph with shared state - LangGraph-style) Best edge | State graphs with checkpointing pause mid-run - persist state at a node boundary, wait hours for an approval, resume on the same state object. That mechanism is the basis of our human-in-the-loop approval flow pattern. Batch DAG orchestrators model waiting as sensors or deferrable operators: workable for data pipelines, awkward for conversational approval flows where the resume carries updated human input back into shared state. FSMs handle pause/resume respectably too (persist current state + context, resume on event) - the graph's advantage is that the checkpoint captures the full working state, not just the state label. |
| Auditability and enumerable behavior | Tie | A third model wins this row: the explicit FSM. When compliance, safety review, or an on-call engineer needs the complete answer to 'what states can this system be in and what triggers each transition,' only a finite state machine makes that enumeration a build artifact rather than an archaeology project. Statechart tooling (the XState lineage) can render the whole behavior space as a diagram and reject undefined transitions at compile time. State graphs are inspectable but their behavior depends on runtime state contents; DAG runs are auditable per-execution but the interesting logic often hides inside task code. The FSM's documented cost is state explosion - enumerate error handling × conversation branches × retry status and the machine becomes unmaintainable - which is why statecharts fit bounded, regulated workflows rather than open-ended agents. |
| Parallel fan-out, joins, and batch throughput | DAG pipeline (directed acyclic graph - Airflow-style) Best edge | For 'process 10,000 documents through embed → enrich → index with a join at the end,' the DAG orchestrator is the mature tool: dynamic task mapping generates per-item task instances at runtime, the scheduler owns retries/backfill/SLAs, and a decade of Airflow operations knowledge applies. State graphs can fan out (LangGraph send/branch primitives) but you inherit scheduling, concurrency limits, and observability yourself. FSMs are the wrong shape entirely for data-parallel work - a machine models one entity's lifecycle, not a batch. |
| Determinism and reproducible routing | Tie | Tie between DAG and FSM, and the research receipts favor explicit structure generally: the GraphBit paper (arXiv 2605.13848) identifies hallucinated routing, infinite loops, and non-reproducible execution as failure modes of prompt-driven orchestration, and its fix is an engine-orchestrated deterministic DAG - typed-function agents, a Rust engine owning routing and state transitions - reporting 67.6% on GAIA with zero framework-induced hallucinations. The lesson transfers: whichever model you pick, keep routing decisions in code evaluating structured state, not in a prompt asking the model where to go next. A state graph with LLM-decided edges is the least deterministic of all four options; the same graph with predicate-based conditional edges is nearly as reproducible as an FSM. |
| Simple linear tasks (the case nobody defends in a comparison post) | Tie | For prompt → tool call → synthesis with no branching, a plain chain - sequential function calls in ordinary code - beats all three structures. This is Anthropic's published position in 'Building Effective Agents': workflows with predefined code paths cover most use cases, frameworks add failure modes and debugging distance, and you should reach for more structure only when the task demonstrably needs it. A graph with no cycles used, a DAG with a single path, or a two-state FSM are all a chain wearing an orchestration costume - plus a dependency, an abstraction layer, and a recursion limit you now have to explain in code review. |
Choose State graph (cyclic graph with shared state - LangGraph-style) if...
- Agent loops that iterate until a quality gate passes, with a typed shared state object carried through every cycle.
- Human-in-the-loop approval flows: checkpoint at the decision node, wait indefinitely, resume with the human's input merged into state.
- Multi-step assistants needing conditional routing where the next node depends on accumulated state, not just the previous step's output.
- Long-running resumable work where a crash should resume from the last checkpoint instead of restarting the run.
Choose DAG pipeline (directed acyclic graph - Airflow-style) if...
- Batch and scheduled pipelines: RAG index refreshes, embedding backfills, nightly eval runs - acyclic by nature, throughput-bound, retry-tolerant.
- Teams already operating Airflow/Dagster/Prefect who need LLM steps inside data workflows without adopting a second orchestrator.
- Workloads where guaranteed termination matters more than expressive control flow - no recursion limits to tune because no cycles exist.
- Wide fan-out with joins: per-item task mapping across thousands of inputs with scheduler-owned concurrency and backfill.
Decision rules
- 01Need loops (retry-until-quality, agent tool loops), human pauses with resumable state, or checkpointed long-running runs → state graph. Set recursion_limit deliberately - LangGraph's default is no longer a tight guardrail (25 supersteps historically, 1000 since langgraph 1.0.6), so on defaults a non-converging loop now burns hundreds of model calls before GraphRecursionError fires; a deliberate low limit is your cheap runaway protection, and hitting it in production means your convergence condition is wrong.
- 02Batch data flow with fan-out/fan-in and no cycles (RAG index builds, document pipelines, eval harnesses) → DAG orchestrator. You get guaranteed termination, mature scheduling, and retries for free; Airflow errors on cycles by design, so don't fight it to encode agent loops.
- 03A reviewer, regulator, or safety case must enumerate every reachable state and transition → explicit FSM/statechart, and keep it bounded - state explosion is the documented failure mode once error-handling branches multiply.
- 04Linear flow, no branching, no pauses → plain chain in ordinary code. Anthropic's Building Effective Agents guidance is explicit: start with the simplest composable pattern; add graph structure only when the task needs branching, joins, retries, HITL pauses, or persistent state.
- 05Wherever you land, keep routing deterministic: conditional edges evaluating structured state, not prompt-decided next steps - the GraphBit results (67.6% GAIA, zero framework-induced hallucinations from engine-owned routing) quantify why.
- 06Mixed workloads compose: a DAG for offline batch stages that invokes a state graph for the interactive agent step is a normal architecture, not a smell - pick per-subsystem, not per-company.
Migration Notes
- Chain → state graph is the common graduation path: keep node functions pure (state in, partial state out) from day one in the chain, and the rewrite is re-wiring, not re-writing.
- DAG → state graph: the forcing signal is faked loops - schedule-level re-runs or retry hacks standing in for iterate-until-done. Move the loop into a state graph and keep the surrounding batch stages in the DAG; orchestrators compose.
- State graph → FSM: usually driven by audit or compliance pressure. Derive the machine from observed graph traces (states = node × relevant-state-flags), then check the transition count honestly against the state-explosion wall before committing.
- Any → any: routing logic embedded in prompts migrates worst. Extract every 'decide what to do next' decision into code that reads structured state first - after that, all three structures can host it.