2 — Directed Acyclic Graphs (DAGs)

Concept overview

A directed acyclic graph models tasks as nodes and dependencies as edges without allowing a path back to an earlier node. It fits workflows whose overall structure is known before execution, even when individual nodes use probabilistic models. The graph exposes the critical path and makes prerequisites visible to schedulers and reviewers.

A DAG is not a complete model for open-ended agent behavior. Replanning and repeated critique require a bounded subworkflow or an external state machine. Separate the graph definition from each execution instance so retries, artifact versions, and task status do not mutate the intended dependency structure.

Why it matters in production

Proof of concept

A prototype may implement dependencies as ordinary function calls. Draw the actual graph to expose accidental serialization and missing validation steps.

Production

Production persists node outcomes and schedules only ready nodes. Make artifact identity include relevant input versions so cached output cannot survive a material source change.

Enterprise scale

At scale, prioritize critical-path tasks, enforce pool limits, and partition large graphs. A wide fan-out can overwhelm a shared model endpoint even when the scheduler has abundant capacity.

Architecture components

Graph definition

Specifies typed node inputs, dependency edges, and terminal success conditions.

Scheduler

Finds ready nodes and allocates constrained worker capacity without violating dependencies.

Artifact store

Retains immutable outputs with input hashes and schema versions for reuse.

Execution ledger

Tracks node attempts, terminal outcomes, and graph-level completion separately.

Join policy

Defines whether downstream work requires all branches or a permitted subset.

The architecture, mapped

flowchart TD
 I["Tender package"] --> P["Parse specifications"]
 I --> C["Retrieve supplier credentials"]
 P --> T["Technical comparison"]
 P --> F["Commercial normalization"]
 C --> R["Supplier risk review"]
 T --> J["Validated evidence join"]
 F --> J
 R --> J
 J --> A["Procurement recommendation"]

Runtime flow

1. 1

   Compile graph

   Validate references, reject cycles, and identify disconnected nodes before accepting an execution.

2. 2

   Bind inputs

   Pin source document and configuration versions to produce reproducible execution identity.

3. 3

   Schedule roots

   Queue independent nodes with concurrency limits for their particular tools and model providers.

4. 4

   Validate outputs

   Check each result before marking its dependency satisfied; quarantine invalid artifacts.

5. 5

   Release successors

   Start downstream nodes only when their declared join policy is met.

6. 6

   Close execution

   Commit the final artifact or expose blocked nodes and their precise upstream causes.

Reviewing an industrial equipment tender

Procurement · Illustrative enterprise scenario, not a reported customer outcome.

Business situation

A manufacturer must compare bids with inconsistent price schedules, engineering specifications, and supplier documentation.

The problem

An ad hoc script repeats expensive parsing after any downstream failure and cannot explain which checks were omitted.

Agent requirement

The assistant must create a comparable evidence package with every mandatory review completed before recommendation.

Architecture

A versioned DAG separates extraction, specification matching, price normalization, credentials verification, and final scoring.

Runtime

• A new bid package creates immutable input artifacts; independent parsing and supplier checks start together.
• Validated extraction releases technical and commercial branches, then a mandatory join produces the reviewer package.

Failure scenario

If currency normalization fails, technical findings remain available, but commercial ranking is blocked until the affected node succeeds.

Operational impact

Track critical-path duration, reusable-node rate, queue delay, and incomplete mandatory branches. Procurement approval remains a separate controlled action.

Architecture tradeoffs

Failure scenarios & recovery

Common architecture mistakes

Embedding invisible dependencies inside prompts

Declare required artifacts as graph edges.

Treating skipped nodes as successful

Represent skipped, failed, and completed states independently.

Retrying the whole graph after one failure

Restart only failed nodes and invalidated descendants.

When to choose this pattern

Choose it when

• Work has stable prerequisites and explicit terminal artifacts.
• Expensive independent stages benefit from controlled parallel execution.
• Reviewers require evidence that every mandatory check ran.

Avoid it when

• The agent must repeatedly revise its overall task structure.
• A simple sequence provides adequate scheduling visibility.
• Inputs change continuously without meaningful snapshot boundaries.

Architecture checklist

• Reject cyclic and disconnected graph definitions.
• Version the graph and every artifact schema.
• Specify all-branch versus partial join policies.
• Measure the actual critical path in traces.
• Test node restart without duplicate external writes.
• Bound concurrency for each shared dependency.

Related concepts

• 3 — Agentic State Machines
• 6 — Asynchronous Agent Execution
• 8 — Plan-and-Execute Pattern
• 12 — State Persistence
• 58 — Partial Success Management

Primary references

• LangGraph: workflows and agents