Planning and Scheduling Harnesses: Task Graphs, Dependencies, ReWOO, and LLMCompiler

A plan that reads like a clean numbered list can still deadlock at runtime, because the list never told the scheduler which steps actually depend on which outputs.

The first time I watched a plan stall, the trace looked absurd. Step 4 was waiting on a value that step 2 had already produced. Step 3 had run in parallel because nothing in the plan said it couldn't. The model had written a perfectly reasonable sequence of English sentences, and the harness had treated those sentences as if they were a program. They were not. They were a wish list with punctuation.

That failure is not a model failure. It is a representation failure. The plan was never executable, because it never encoded the one thing the scheduler needs: which task produces which value, and which task consumes it. Once you fix the representation, most of the "the model is bad at planning" complaints turn into ordinary scheduling bugs you can actually debug.

Why a Step List Is Not a Plan

Planning and scheduling are two different jobs, and collapsing them into a single ordered list is where most planner bugs are born. Planning decides what tasks exist and how they relate. Scheduling decides when each task is allowed to run. A numbered list hides the first decision inside the second, and the hidden structure is exactly the part that determines whether the run is correct.

This distinction is old. In classical automated planning, scheduling assumes the tasks are already decided and focuses on ordering and resource assignment. Agent harnesses need both halves, and the seam between them is where the design mistakes live. If your planner emits a list and your executor walks the list, you have quietly decided that every task depends on every prior task. That is a valid schedule. It is also the slowest one, and it will produce wrong results the moment a later task needs a value the list never bound.

The executable unit is not a step. It is a task node: a tool reference, an argument map, and a dependency set. Nothing else is required for a scheduler to do its job. Everything else — status, result, timing, retry count — is bookkeeping the scheduler attaches to the node as it runs.

Invariant: a task is runnable only when every dependency has produced a result that satisfies the task's argument contract. If you cannot express that binding, you do not have a graph. You have a wish.

The observable consequence of missing dependencies is binary and ugly. Without explicit edges, the harness either serializes everything, which is slow, or parallelizes blindly, which is wrong. Both look identical from the outside: "the model is bad." Neither is a model problem.

The Task Graph Contract: Nodes, Edges, and Variable Binding

Before comparing planner architectures, fix the data structure they all have to produce. Keep it flat and serializable, because this same object becomes your checkpoint, your trace, and your debugging surface.

{
  "id": "3",
  "tool": "search",
  "args": { "query": "${1}" },
  "deps": ["1"],
  "status": "pending",
  "result": null
}

That is the whole contract. The deps field is the edge set. The ${1} reference is the mechanism that makes a graph more than a fan-out: an argument can point at a prior task's output, which is what lets the planner express data flow instead of mere ordering.

Edges are data dependencies, not control dependencies. Ask "does this task need that value?" not "should this run after that?" The second question is a scheduling opinion. The first is a fact about the computation, and only facts belong in the graph.

Cycle handling is where naive implementations die. A DAG is the tractable case. If the planner emits a cycle, the scheduler must detect it and fail loudly rather than deadlock waiting for a dependency that can never complete. Run cycle detection at graph admission time, before you dispatch anything.

Outcome States, Not Just "Done"

The single most common scheduler bug is treating "the task finished" as "the task succeeded." Those are different facts, and conflating them releases dependents that should never have run. Model the outcome explicitly:

The readiness rule now reads: a task is runnable only when every dependency is in succeeded and its output satisfies the consuming argument's contract. A dependency in failed, cancelled, or skipped does not release the dependent — it either blocks it, marks it skipped, or hands the whole subgraph to a replanning seam. Which of those you choose is a policy decision, but the state model has to exist before the policy can be expressed.

Here is the minimal scheduler, in pseudocode:

def run(graph):
    while any_pending(graph):
        ready = [n for n in graph
                 if n.status == "pending"
                 and all(graph[d].status == "succeeded" for d in n.deps)]
        if not ready and not any_running(graph):
            raise Deadlock("cycle or unresolvable dependency")
        for node in ready:
            node.args = bind(node.args, graph)   # resolve ${id} references
            node.status = "running"
            dispatch(node)
        for node in completed_since_last_scan():
            node.status = "succeeded" if node.error is None else "failed"
            if node.status == "failed":
                propagate_failure(graph, node)   # skip or block dependents

The naive scan is O(n²) in the number of nodes. For a plan with a dozen tasks, that is free. For hundreds, replace it with a ready-queue driven by in-degree counters: when a node succeeds, decrement the in-degree of each dependent and enqueue the ones that hit zero. Do not build the queue until the scan actually shows up in your profile.

Dry Run: Three Nodes, One Shared Dependency

Dry-run a three-node graph by hand. Node 1 has no dependencies. Node 2 depends on 1. Node 3 has no dependencies. At t=0, nodes 1 and 3 are ready and node 2 is not. That is the entire value of the graph: it tells you that 1 and 3 can run concurrently and that 2 cannot start until 1 lands. A step list cannot tell you that, and a scheduler cannot guess it.

Here is what the trace looks like when node 1 succeeds:

t=0.00  node1  running   args={query:"gdp of NY"}
t=0.00  node3  running   args={expr:"2+2"}
t=0.42  node1  succeeded result="New York GDP is $2.1T"
t=0.43  node2  running   args={query:"${1}"} -> {query:"New York GDP is $2.1T"}
t=0.44  node3  succeeded result="4"
t=0.91  node2  succeeded result="..."

And here is the same graph when node 1 fails:

t=0.00  node1  running   args={query:"gdp of NY"}
t=0.00  node3  running   args={expr:"2+2"}
t=0.42  node1  failed    error="search timeout"
t=0.42  node2  skipped   reason="dependency node1 failed"
t=0.44  node3  succeeded result="4"

Node 3 completes regardless. Node 2 never fires. That is the failure-propagation behavior the state model buys you, and it is invisible in a step list.

Planner Design Axes: Four Dimensions, Not Three Architectures

The comparison that matters is not "which planner is smarter." It is a point in a four-dimensional design space. Naming the axes first prevents the common mistake of treating ReWOO and LLMCompiler as mutually exclusive categories when they are really different coordinates on the same map.

Axis 1 — Graph materialization. When does the graph become fixed? Fully up front, incrementally as a stream, or one step at a time as the model reasons.

Axis 2 — Dependency binding. How do tasks consume prior outputs? Positional ordering, explicit variable references, or implicit context accumulation.

Axis 3 — Execution concurrency. Serial, embarrassingly parallel fan-out, or dependency-aware eager scheduling.

Axis 4 — Replanning trigger. Never, on failure, on a joiner decision, or continuously per step.

ReWOO sits at: full graph up front, explicit variable binding, serial-or-parallel execution depending on graph width, no native replanning. LLMCompiler sits at: streamed graph, explicit variable binding, eager dependency-aware scheduling, joiner-triggered replanning. Interleaved reason-act sits at: emergent graph, implicit binding, serial execution, continuous replanning. They are not three flavors of the same thing. They are three points in a space, and you can move along any axis independently.

ReWOO: Plan Once, Bind Variables, Execute Without Re-Prompting

ReWOO — Reasoning WithOut Observations — attacks the per-step reasoning call directly. The planner emits the full plan with variable assignments, so each task can consume a prior task's output without an intervening model call. The plan is a dependency structure, not a list; the variable references are what encode the edges.

What this buys is concrete. Fewer LLM calls, lower token cost, and a plan you can inspect before spending any execution budget. The plan is a reviewable artifact, which means you can validate tool availability and argument shapes before the first tool fires.

What it costs is equally concrete: the plan is frozen. If task 2 returns something that invalidates task 5's premise, ReWOO has no built-in recovery path. You must add a replanning layer yourself. That is not a flaw in the mechanism; it is the boundary of the mechanism.

The failure mode to plan for is silent propagation. A variable reference that resolves to an empty or malformed value flows straight into downstream arguments, and the run fails somewhere far from the cause. Validate bindings at dispatch, not at the end. When ${1} resolves to an empty string, fail the node that consumes it, not the node that produced it.

I would not reach for ReWOO when later steps genuinely depend on the content of earlier results in ways the planner cannot anticipate at plan time. That is exactly the case the frozen plan cannot handle, and no amount of prompt engineering fixes a structural mismatch.

LLMCompiler: Streaming the Graph and Executing Eagerly

LLMCompiler pushes the same idea further by removing the wait for the full plan. It has three components: a planner that streams a DAG of tasks, a task fetching unit that schedules each task the moment its dependencies are satisfied, and a joiner that decides whether to answer or trigger another planning round.

The latency win comes from two mechanisms stacked. Streaming means the scheduler does not wait for the whole plan before starting the first task. Dependency-aware scheduling means independent branches run concurrently. Variable arguments are what make eager execution safe: a task cannot be dispatched until its referenced outputs actually exist, so the scheduler never fires a task with an unresolved binding.

The joiner is the replanning seam, and it is the more interesting component. It sees the entire graph history, including task results, which is a stronger signal than a single step's observation. That is what lets LLMCompiler recover from a plan that reality contradicted, without paying for a model call between every action.

The speedups reported for LLMCompiler are real but conditional. They depend on how much genuine parallelism the task graph contains. A fully serial plan gains nothing from eager scheduling, because there is nothing to overlap. If your tasks form a chain, streaming buys you a small head start and nothing more.

Implementation trap: streaming parsers must tolerate partial and malformed task objects. A parse failure mid-stream should fail the affected task, not kill the whole run. Design the parser to yield what it can and report what it could not.

Comparing Planners on Latency, Replanning, and Observability

With the four axes named, the comparison table becomes a coordinate lookup rather than a category fight.

Latency decomposes into two numbers worth tracking separately: planning latency, the time to first executable task, and execution latency, the wall-clock to completion. Streaming planners win on the first. Dependency-aware scheduling wins on the second only when the graph has real width.

Replanning is the axis that decides most real deployments. ReWOO has no native replanning. LLMCompiler's joiner provides a seam. Interleaved reason-act replans continuously at the cost of per-step model calls. Pick based on how often reality invalidates the plan, not on which architecture sounds more advanced.

Observability follows directly from when the graph materializes. A materialized graph is inspectable before execution, which means you can validate tool availability, argument shapes, and dependency cycles cheaply. An emergent plan can only be observed after the fact, which turns every failure into archaeology.

Cost is best counted per plan, not per task. The plan-and-execute family's main economic argument is removing the per-step reasoning call, and that argument holds as long as the plan survives contact with execution.

My decision rule: if the task decomposes into mostly independent subtasks with predictable data flow, stream a graph and schedule eagerly. If later steps genuinely depend on the semantics of earlier results, keep a replanning seam and accept the extra calls. And when the whole thing is overkill — short tasks, single-tool tasks, or tasks where a deterministic workflow already encodes the dependency structure — do not build a planner to rediscover a graph you already know.

Making the Graph Survivable: Validation, Recovery, and Traces

A planner demo becomes a harness component when it survives partial failure and can explain itself afterward.

Admission validation before dispatch is the cheapest insurance you can buy. Check for cycles, verify every tool exists, validate argument schemas, and confirm every variable reference resolves to a task that appears earlier in the graph. These checks are cheap relative to a failed tool call, and they prevent the expensive failures.

Partial failure policy is a decision, not a default. For each node, decide whether a failed task fails its dependents, triggers a replan, or falls back to a degraded result. The scheduler should not guess. Make the policy explicit per node type, because a failed search and a failed payment have nothing in common.

Idempotency matters more in a graph than in a chain, because retries and replans can re-dispatch a node whose side effects already landed. If a node writes to an external system, it needs an idempotency key or it needs to be marked non-retryable.

The trace shape is what lets you answer "why did task 7 run before task 6" after the fact. Record node id, tool, resolved arguments, dependency set, start and end time, outcome state, and a result digest. That is the minimum for reconstructing a run.

Checkpoint the graph state, not just the conversation. A resumable run needs node statuses and results, which is a different artifact from the message history. If your checkpoint only stores messages, you cannot resume mid-graph without re-running completed work.

Finally, concurrency limits and rate limits are scheduler concerns. An eager scheduler with no backpressure will happily open more parallel tool calls than your provider or downstream system allows. The scheduler that dispatches eagerly is also the scheduler that must throttle.

Verifying the Scheduler Before You Trust It

You can build the scheduler and still not know whether it is correct. A compact verification protocol catches the failure classes that matter, and it runs against the three-node graph you already have.

Test these cases explicitly:

• Cycle rejection. Feed a graph where node 2 depends on node 3 and node 3 depends on node 2. The scheduler must raise, not hang.
• Missing-reference rejection. A node references ${9} when no node 9 exists. Admission validation must reject it before dispatch.
• Dependency-order correctness. Node 2 must never start before node 1 reaches succeeded. Assert on the trace timestamps.
• Failure propagation. When node 1 fails, node 2 must be skipped or blocked, and node 3 must still complete.
• Independent-branch concurrency. Nodes 1 and 3 must overlap in the trace. If they serialize, your readiness scan is wrong.

Then measure five numbers per run: time-to-first-task, critical-path wall time, total model and tool calls, replan count, and trace completeness. Time-to-first-task isolates planning latency. Critical-path wall time isolates scheduling quality. The gap between critical-path time and total wall time tells you how much parallelism you actually captured versus how much the graph offered.

The distinction that matters most here is between a structurally valid graph and a semantically correct one. A graph can pass every admission check — no cycles, all references resolve, all tools exist — and still encode the wrong dependencies. Structural validation catches representation bugs. Only execution traces and outcome assertions catch semantic ones. Build both.

Where to Start

Pick your planner by asking one question: when is the graph fixed, and what happens when execution contradicts it? Everything else — ReWOO, LLMCompiler, interleaved reasoning — is a specific answer to that question, and each answer has a boundary where it stops being correct.

The next action is small and concrete. Implement the node schema, the outcome-state model, and the ready-queue scheduler from the contract section. Run it against a three-node graph with one shared dependency and one independent branch. Add the five verification tests before you add any planner sophistication, so you can see which nodes were ready at each tick and why. Once that runs, the interesting question becomes how the scheduler interacts with state persistence and checkpointing when a run has to survive a restart — which is where the graph stops being a data structure and starts being a durable system.