Resolve a ReWOO Plan into Execution Waves

mediumFREEAgent Loop Control & PlanningAI AgentsAI Agents 1

Problem Statement

ReWOO's whole trick is that the planner writes the entire plan up front, before a single tool has run, by referring to results it has not seen yet through variables like #E1. The worker then has to figure out what can run now, what must wait, and what can never run at all because the planner hallucinated a reference to a step it never wrote.

Background

A plan step looks like:

{"id": "E2", "tool": "LLM", "args": ["What is the population of #E1?"]}

Every occurrence of #E<n> inside any argument string is a dependency on step E<n>. A step is ready when all of its dependencies have completed in an earlier wave, so:

Steps with no references at all form wave 0.
Each subsequent wave holds every step whose references are now all satisfied.

Two things can make a step unrunnable, and the worker must report them rather than crash:

an unresolved reference to an id that is not in the plan at all;
a cycle (including a step that references itself), or a chain of steps hanging off an unresolved reference.

Either way that step is blocked: it never appears in a wave.

Your Task

Implement:

def resolve_plan(plan):

plan: list of {"id": str, "tool": str, "args": list}. Ids have the form E followed by digits.

Return:

waves: list of lists of ids. Ids within a wave are sorted by their numeric index (E2 before E10).
unresolved: sorted list of strings "<step_id>:#<missing_id>", deduplicated.
blocked: ids never scheduled, sorted by numeric index.

Input/Output Format

Returns the three-key dict. Note ids sort numerically, not lexicographically - a plain sorted() would put E10 before E2.

Sample

plan = [
    {"id": "E1", "tool": "Search", "args": ["capital of France"]},
    {"id": "E2", "tool": "Search", "args": ["landmarks in Paris"]},
    {"id": "E3", "tool": "LLM", "args": ["Summarise #E1 and #E2"]},
]
print(resolve_plan(plan)["waves"])
# [['E1', 'E2'], ['E3']]

E1 and E2 reference nothing, so ReWOO fires them in parallel; E3 waits for both.

Example

Input

plan = [{'id':'E1','tool':'Search','args':['capital of France']},{'id':'E2','tool':'Search','args':['landmarks in Paris']},{'id':'E3','tool':'LLM','args':['Summarise #E1 and #E2']}]
print(resolve_plan(plan)['waves'])

Output

[['E1', 'E2'], ['E3']]

Reasoning

E1 and E2 contain no #E references, so both are ready immediately and share wave 0 - this is the parallelism ReWOO buys by planning up front. E3 references both, so it can only run once wave 0 has completed, landing in wave 1.

Constraints

0 <= len(plan) <= 200; ids are unique and match E<digits>
References are found with the pattern #E<digits> anywhere inside any argument, stringified with str()
A step referencing itself is a cycle and is therefore blocked
Steps depending (directly or transitively) on a blocked or unresolved step are themselves blocked
Wave contents and blocked sort by numeric id index; unresolved sorts lexicographically
Duplicate references from one step to the same id collapse to one dependency

Learn this in

The Agent Loop & ReAct FoundationsAgent Engineering Study Plan Planning Patterns: Plan-and-Execute, ReWOO, HTNAgent Engineering Study Plan Workflow Patterns & LangGraph Stateful GraphsAgent Engineering Study Plan LLM Agents & ToolsLLM Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primer

1. Background Knowledge

This problem models static dependency resolution in a Directed Acyclic Graph (DAG). In AI agent planning, specifically the ReWOO (Reasoning Without Observation) framework, the planner generates a full execution plan before any tools are invoked. This requires the system to parse implicit dependencies—references like #E1—and determine a valid topological ordering of steps. The core concept is wave-based execution, where independent tasks are grouped into parallel "waves" to maximize concurrency.

The underlying data structure is a dependency graph where nodes are plan steps and directed edges represent data dependencies (e.g., E3 depends on E1). If the graph contains cycles or references to non-existent nodes, it violates the DAG property, making those nodes unexecutable. This is a classic application of Kahn’s Algorithm for topological sorting, which processes nodes with zero in-degree (no unresolved dependencies) iteratively.

Key technical terms include:

In-degree: The number of dependencies a step has.
Wave: A set of steps that can execute in parallel because all their dependencies were resolved in previous waves.
Unresolved Reference: A dependency pointing to an ID not present in the plan.
Cycle: A circular dependency chain (e.g., E1 needs E2, E2 needs E1).

2. Algorithm Approach

The optimal approach is a modified Breadth-First Search (BFS) using Kahn’s Algorithm. Standard topological sort produces a single linear order, but here we need to group nodes by their "level" or "wave."

Graph Construction: Parse each step's arguments to extract #E<n> references. Build an adjacency list or, more efficiently for this problem, an in-degree map and a reverse adjacency list (dependents).
Validation: Identify steps with references to IDs not in the plan. These are unresolved.
Wave Generation:

Initialize a queue with all steps having an in-degree of 0 (no dependencies).
Process the queue level-by-level. Each level corresponds to one wave.
When a step is processed, decrement the in-degree of its dependents. If a dependent's in-degree hits 0, it becomes ready for the next wave.

Cycle Detection: After the BFS completes, any step that was never added to a wave is either part of a cycle or blocked by an unresolved reference. These form the blocked list.

3. Step-by-Step Strategy

Parse and Index:

Create a set of all valid IDs from the plan for O(1) lookup.
Use a regex or string search to find all #E\d+ patterns in each step's args.
Build a dependencies map: step_id -> list of required_ids.

Identify Unresolved References:

Iterate through all steps. For each dependency #E<n>, check if E<n> exists in the valid ID set.
If not, add "<step_id>:#<missing_id>" to the unresolved list.
Crucially, treat steps with unresolved references as having a "phantom" dependency that can never be satisfied. They will never reach in-degree 0.

Compute In-Degrees:

Initialize in_degree for each step to 0.
For every valid dependency A depends on B, increment in_degree[A].
Note: Do not increment in-degree for unresolved references, as those steps are already doomed to be blocked.

Execute Wave BFS:

Initialize queue with all steps where in_degree == 0.
While queue is not empty:
Create a new wave list.
Process all nodes currently in the queue (this defines the parallel batch).
For each node, find its dependents (steps that reference it) and decrement their in_degree.
If a dependent's in_degree becomes 0, add it to the next_queue.
Sort the current wave numerically by ID (e.g., E2 before E10) and append to waves.
Set queue = next_queue.

Identify Blocked Steps:

Any step ID not present in any wave is blocked.
Collect these IDs, sort them numerically, and return.

4. Common Pitfalls

Lexicographic vs. Numeric Sorting: The problem explicitly states IDs must be sorted numerically (E2 < E10). Using standard sorted() on strings will fail because '10' < '2' is true in lexicographical order. You must extract the integer part for sorting.
Self-References: A step referencing itself (E1 depends on E1) creates a cycle of length 1. Ensure your in-degree logic handles this; the in-degree will never drop to 0, so it correctly ends up in blocked.
Unresolved vs. Cycle: Both result in blocked steps, but unresolved requires specific reporting. Ensure you distinguish between "missing ID" (unresolved) and "present ID but circular dependency" (cycle).
Argument Parsing: Ensure you correctly extract all #E<n> references. Missing a reference leads to incorrect in-degrees and wrong wave assignments.
Empty Plan: Handle edge cases where the plan is empty or contains only blocked steps.

5. Time & Space Complexity

Time Complexity: $O(N \cdot L)$ , where $N$ is the number of steps and $L$ is the average length of the argument strings (for parsing). Building the graph takes $O(N \cdot L)$ . The BFS visits each node and edge once, taking $O(N + E)$ , where $E$ is the number of dependencies. Since $E$ is bounded by $N \cdot L$ , the total time is dominated by parsing and graph traversal.
Space Complexity: $O(N + E)$ to store the graph (adjacency list/in-degree map) and the output lists. The queue and wave lists also consume $O(N)$ space.

# Example of numeric sorting key
def sort_key(id_str):
 return int(id_str[1:]) # Extract number after 'E'

solution.py

Python 3.13

Test results