7 minute read

“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.

A printed circuit board trace layout photographed from above under inspection light

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.

  1. Planner: The LLM generates a DAG.
    • Task 1: Google “Apple stock”.
    • Task 2: Google “Microsoft stock”.
    • Task 3: Compare (Dep: 1, 2).
  2. Executor: A runtime (like Kahn’s Algorithm!) executes tasks.
  3. 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

  1. Hallucinated Cycles: The LLM plans Task A needs Task B, and Task B needs Task A. The executor deadlocks.
    • Fix: Validate the JSON dependency list for cycles using DFS before execution.
  2. 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

  1. Map-Reduce Pattern:
    • Map: “Generate 5 ideas.” (Run 5 LLM calls in parallel).
    • Reduce: “Select the best idea.” (Run 1 LLM call).
  2. 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


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

  1. Parallelism = Speed: Agents are slow. Parallelizing sub-tasks is the easiest performance win.
  2. Graph > Chain: Real world workflows are non-linear.
  3. 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.