Dependency Graphs for Agents
“An Agent without a Plan is just a stochastic parrot reacting to noise.”
TL;DR
Sequential ReAct agents waste time executing independent subtasks one after another. Dependency graphs model agent plans as DAGs where independent tasks run in parallel and synchronize at join points, turning a 30-second sequential workflow into a 10-second parallel one. The Plan-and-Solve pattern separates reasoning (LLM generates the DAG) from execution (runtime processes it via topological sort). LangGraph makes this practical with typed state objects and checkpoint persistence. Watch out for hallucinated cycles in LLM-generated plans and context overflow when merging too many parallel results. For the fundamentals of planning architectures, see Planning and Decomposition, and for where LangGraph sits among agent frameworks, see Agent Frameworks Landscape.

1. Introduction
The simpler agents (ReAct) operate in a loop: Thought -> Action -> Observation. This is sequential.
But complex tasks require parallel planning.
Task: “Research 3 companies (A, B, C) and write a comparison report.”
- Sequential Agent: Research A (wait), Research B (wait), Research C (wait), Write. Total: 30s.
- DAG Agent: Research A, B, C in parallel. Join results. Write. Total: 10s.
We need to treat Agent Actions not as a “Loop” but as a Dependency Graph.
2. Core Concepts: The Plan-and-Solve Pattern
This pattern separates Reasoning from Execution.
- Planner: The LLM generates a DAG.
Task 1: Google “Apple stock”.Task 2: Google “Microsoft stock”.Task 3: Compare (Dep: 1, 2).
- Executor: A runtime (like Kahn’s Algorithm!) executes tasks.
- Replanner: If Task 1 fails, the Planner updates the graph.
3. Architecture Patterns: Graphs vs. Chains
- Chain: Linear.
A -> B -> C. (LangChain Classic). - DAG: Directed, No Cycles.
A -> B, A -> C, D(B, C). (Parallel Execution). - Cyclic Graph:
A -> B -> A. (Iterative Refinement).
LangGraph is a library designed specifically to define these state machines as graphs.
graph TD
Start --> Planner
Planner --> |Review| Critic
Critic -- "Bad" --> Planner
Critic -- "Good" --> Executor
Executor --> End
4. Implementation Approaches
4.1 Static Graph
The developer defines the graph.
- “Always research, then summarize.”
- Reliable, rigid.
4.2 Dynamic Graph (AI-Driven)
The LLM writes the graph.
- Prompt: “Break this down into subtasks with dependencies.”
- Output: JSON List of Edges.
- Flexible, fragile.
5. Code Examples: The Task Graph Executor
A simplified implementation of a DAG runner for agents in Python.
import concurrent.futures
class Task:
def __init__(self, id, prompt, deps=None):
self.id = id
self.prompt = prompt
self.deps = deps or []
self.result = None
def execute_dag(tasks, llm_function, max_workers=4):
"""
Executes tasks in dependency order, running independent tasks in parallel.
"""
by_id = {t.id: t for t in tasks}
completed = set()
running = {} # future -> task
with concurrent.futures.ThreadPoolExecutor(max_workers=max_workers) as executor:
while len(completed) < len(tasks):
# 1. Submit every task whose dependencies are all complete
for t in tasks:
if t.id in completed or t in running.values():
continue
if all(d in completed for d in t.deps):
# Inject dependency results into the prompt
context = "\n".join(by_id[d].result for d in t.deps)
full_prompt = f"Context: {context}\nTask: {t.prompt}"
running[executor.submit(llm_function, full_prompt)] = t
if not running:
raise ValueError("Unrunnable tasks: dependency cycle or unknown dependency")
# 2. Wait for at least one task to finish, then record its result
done, _ = concurrent.futures.wait(running, return_when=concurrent.futures.FIRST_COMPLETED)
for future in done:
task = running.pop(future)
task.result = future.result()
completed.add(task.id)
return by_id
This is Kahn’s algorithm for topological sorting, applied to LLM calls. The ValueError branch doubles as a runtime cycle check: if nothing can run and nothing is running, the plan cannot finish.
6. Production Considerations
6.1 State Management
In a DAG, “State” is shared.
If Task A and Task B run in parallel, and both try to update memory.txt, you have a race condition.
LangGraph handles this with a typed State Object (TypedDict) and per-key reducers: parallel branches return partial updates, and a reducer (for example, list append) merges them. Two branches writing the same key without a reducer raise an error instead of silently overwriting each other. A checkpointer (for example, Postgres) persists the state after each step.
6.2 Human-in-the-Loop
You might want a human to verify Task 1 before Task 2 starts.
The Graph Executor must support Pause/Resume. This requires serializing the graph state (Agents!) to a DB.
7. Common Pitfalls
- Hallucinated Cycles: The LLM plans
Task AneedsTask B, andTask BneedsTask A. The executor deadlocks.- Fix: Validate the JSON dependency list for cycles using DFS before execution.
- Context Overflow: Merging results from 10 parallel tasks into the prompt for Task 11 blows up the context window.
- Fix: Summarize intermediate results (Map-Reduce).
8. Best Practices
- Map-Reduce Pattern:
- Map: “Generate 5 ideas.” (Run 5 LLM calls in parallel).
- Reduce: “Select the best idea.” (Run 1 LLM call).
- Visual Debugging: Use tools like LangSmith to visualize the graph execution. Debugging a 50-step async agent via print logs is impossible.
9. Connections to Other Topics
- Planning and Decomposition: how the planner produces the subtasks in the first place.
- Hierarchical Planning: DAGs inside a coarse-to-fine plan, with budgets and verification gates.
- Scaling Multi-Agent Systems: DAG execution across many agents, with queues and idempotent tasks.
10. Real-World Examples
- GPT-Researcher: A popular open-source agent.
- Generates a set of research questions.
- Scrapes sources for them in parallel.
- Aggregates the results into one report.
- Deep research products (OpenAI, Google, Perplexity): run many search-and-read steps over several minutes before writing a cited report. Their internal plan structures are not published, but the visible behavior is fan-out search followed by a synthesis step.
11. Future Directions
- Multi-Agent Graphs:
- Node A is “Coder Agent”.
- Node B is “Reviewer Agent”.
- The graph defines the “Company Org Chart”.
- Self-Modifying Graphs: The Agent realizes the plan is bad halfway through and re-writes the remaining graph nodes (Runtime Graph Modification).
12. Key Takeaways
- Parallelism = Speed: Agents are slow. Parallelizing sub-tasks is the easiest performance win.
- Graph > Chain: Real world workflows are non-linear.
- State is King: The edges of the graph transport State. Managing that schema is the hard part of Agent engineering.
Next: Building Domain-Specific Agents covers how to trade breadth for depth in vertical AI.
FAQ
What is a dependency graph in AI agent planning?
A dependency graph models agent tasks as a Directed Acyclic Graph (DAG) where nodes are subtasks and edges represent prerequisites. Independent tasks with no dependencies between them can execute in parallel, while dependent tasks wait for their prerequisites to complete. This is fundamentally Kahn’s Algorithm applied to LLM calls.
How does LangGraph handle agent state management?
LangGraph passes a typed State Object (TypedDict) through the edges of the graph. Parallel branches return partial updates that per-key reducers merge, so concurrent writes are combined explicitly instead of overwriting each other. A checkpointer (e.g., Postgres) persists the state after each step, which supports pause/resume for human-in-the-loop workflows.
What is the Plan-and-Solve pattern for AI agents?
Plan-and-Solve separates reasoning from execution. A Planner LLM generates a DAG of subtasks with dependencies. An Executor runs them in topological order using parallel workers. A Replanner updates the graph if any task fails. This gives agents structured, parallelizable plans instead of reactive step-by-step loops.
How do you prevent hallucinated cycles in agent dependency graphs?
LLMs sometimes plan circular dependencies (Task A needs B, Task B needs A), which causes executor deadlocks. Fix this by validating the JSON dependency list for cycles using DFS before execution. If a cycle is detected, send the plan back to the LLM for correction.