Planner/Executor & Agentic Workflows

Start with a concrete problem

When no remaining task is ready, is that successful completion or a deadlock?

You are building the task graph module for HeatStack’s planner, which must turn complex requests into recoverable task dependency structures.

The current tests require TaskGraph to reject missing dependencies and cycles at construction, and topological_order() to return a dependency-respecting tuple.

A common mistake is returning a partial result when pending is non-empty but ready is empty, causing a cyclic graph to be treated as successful completion.

You must distinguish between ‘all tasks completed’ and ‘remaining tasks cannot execute’; the latter must raise a ValueError.

Make a prediction

In topological_order(), if pending is non-empty but ready is empty, what should happen?

• Return the current completed order because it is a partial topological sort
• Raise a ValueError indicating a cycle in the graph
• Skip those tasks and continue processing others
• Return an empty tuple to indicate no executable tasks

Reasoning guide: The correct option is to raise a ValueError. Because pending non-empty means tasks remain, and ready empty means all remaining tasks depend on unfinished tasks, which necessarily forms a cycle; otherwise at least one task would be ready.

What it is

Structural validation of task graphs

TaskGraph is a container for a directed acyclic graph (DAG) that stores tasks and their dependencies and provides topological ordering.

Topological ordering is a linear sequence where each task appears after all its dependencies, which is the basis for planning execution order.

The constructor immediately calls topological_order() to validate the graph, rejecting cycles and missing dependencies at creation time.

What it is not

Task graph is not an execution engine

TaskGraph does not execute any tasks, nor does it manage task state or budgets; it only handles structural validation and ordering.

It does not handle retry or recovery after task failure; those are capabilities of later stages.

It does not prioritize tasks by importance or cost; it only cares about dependency relationships.

How it relates to neighboring concepts

Relationship to the agent loop

The agent loop can choose the next action directly or execute plan nodes, and TaskGraph provides the dependency order for plan nodes.

The output of topological_order() can serve as a reference for execution order, but actual execution is still controlled by the external runtime.

Verification decides whether a node is complete, while TaskGraph only guarantees structural validity and does not participate in verification.

Boundary decision for this stage: When pending is non-empty but ready is empty, you must raise a ValueError because this is a deadlock, not completion; returning a partial result would mask the cycle and make subsequent execution impossible.

Start with a concrete problem

The Deliverable Must Be a Terminal Node

In the software delivery scenario, you are responsible for implementing the create_plan function, which must bind a user goal, a task graph, and a final deliverable into a Plan object.

The test test_plan_binds_goal_to_a_terminal_deliverable requires that when the deliverable is a terminal node (such as verify), the returned plan.deliverable_task_id equals that node ID and the topological order is correct.

Another test, test_nonterminal_deliverable_is_rejected, requires that when the deliverable is an intermediate node (such as code, which is depended on by verify), a ValueError is raised with a message containing terminal.

A third test, test_unknown_deliverable_is_rejected, requires that when the deliverable ID is not in the graph, a ValueError is raised with a message containing missing.

Your task is to create forge/workflow/planner.py, implementing the Plan dataclass and the create_plan function to satisfy these three tests.

Make a prediction

When implementing create_plan, do you think checking that the deliverable exists in the graph is sufficient? Choose the option that best matches your expectation.

• Yes, as long as the deliverable ID is in the graph, the plan is valid.
• No, you also need to check whether the deliverable is depended on by other tasks, i.e., whether it is a terminal node.
• No, you also need to check whether the deliverable is the first node in the topological order.
• No, you also need to check whether the deliverable matches the goal string.

Reasoning guide: The correct option is the second one. Checking only existence would allow an intermediate node as the deliverable, causing the plan to report completion before verification tasks run, violating test_nonterminal_deliverable_is_rejected.

What it is

Terminal Nodes and Deliverables

A terminal node is a task that no other task depends on, meaning it does not appear in any task’s depends_on list.

The deliverable must be a terminal node because it represents the completion of the entire plan; if it has downstream tasks, the plan is not truly complete when the deliverable finishes.

create_plan builds a TaskGraph to validate the graph structure, then checks that the deliverable ID exists in the graph, and finally checks that it is not in the depended_on set.

What it is not

Not Just an Existence Check

Merely checking that the deliverable ID exists in the graph is insufficient because intermediate nodes also exist but are not the plan’s endpoint.

The deliverable is not the first node in the topological order but the last, as it is the end of all dependency chains.

The deliverable is not required to match the goal string; the goal is descriptive text, while the deliverable is a concrete task ID.

How it relates to neighboring concepts

Relationship with TaskGraph and Dependencies

TaskGraph validates cycles and missing dependencies at construction, and create_plan uses it to obtain the task set and topological order.

The depended_on set is derived from all tasks’ depends_on lists, representing which tasks are depended on by others.

The deliverable must not be in depended_on, ensuring it is a terminal node, which guarantees that all prerequisite tasks have executed when the plan completes.

Boundary decision for this stage: create_plan only validates and binds; it does not execute any tasks, nor does it check whether the goal matches task content or whether tasks are executable, as those are responsibilities of the execution phase.

Start with a concrete problem

Why is a dependency having a result record not the same as a dependency having succeeded?

In the software delivery scenario, you have a task graph: inspect checks code, code modifies code, and test runs tests. code depends on inspect, and test depends on code. If inspect fails, code should not run.

Currently, the file forge/workflow/executor.py does not exist, so tests cannot import Executor and TaskResult. You need to create this file and implement an executor that schedules only tasks whose dependencies all have status succeeded.

The key decision is: when checking if a dependency is satisfied, do you only check whether the results dictionary has a record for that task, or must you check that the record’s status is succeeded? If you only check for record existence, a failed dependency would be treated as satisfied, causing dependent tasks to run incorrectly.

Make a prediction

In the Executor.ready method, which approach is correct for determining if a dependency is satisfied?

• As long as dep in self.results, the dependency is satisfied because a result has been recorded.
• You must check self.results.get(dep).status == 'succeeded'; only success satisfies the dependency.
• A dependency task is satisfied as soon as it has been scheduled, regardless of its result.
• Whether a dependency is satisfied is determined by the task graph, so the executor does not need to check.

Reasoning guide: The correct answer is the second option. A dependency having a result record only means it has executed, but it may have failed. Only a status of succeeded indicates that the dependency is truly satisfied and that dependent tasks can safely execute.

What it is

What a dependency-aware executor is

Executor is a scheduler that decides which tasks can run immediately based on the task graph’s dependencies and the recorded task results.

The ready method returns a sorted list of task IDs that have not yet been executed and whose dependencies all have status succeeded.

The run_ready method calls ready to get the ready tasks, executes their handlers in order, catches exceptions, and records the outcome as a TaskResult.

What it is not

What a dependency-aware executor is not

It is not the task graph itself; the task graph only defines tasks and dependencies and does not handle scheduling.

It does not validate whether the task output content is correct; it only cares whether the task completed successfully (i.e., did not raise an exception).

It does not manage budgets or retry policies; it simply executes the tasks that are currently ready.

How it relates to neighboring concepts

Relationships with other components

Executor uses TaskGraph to obtain task and dependency information but does not modify the graph structure.

TaskResult is a dataclass used by the executor to record each task’s result, including task ID, status, output, and error information.

run_ready depends on ready to determine which tasks can execute, and ready depends on the task statuses recorded in self.results.

Boundary decision for this stage: The executor only schedules tasks according to dependency-readiness rules and captures handler exceptions; it does not validate output content or manage budgets.

Start with a concrete problem

Task handler returns normally, but the result may be invalid

In the software delivery scenario, the executor calls a task handler and receives a TaskResult, but the absence of an exception does not guarantee that the output meets business requirements.

For example, a build task might return {'tests': 'failed'}; if only exceptions are checked, this failure would be incorrectly marked as success.

This stage introduces the validate_output function, which uses a ResultContract to declare required keys and assertion checks, ensuring that only outputs passing validation are considered successful.

Make a prediction

If a task handler returns {'tests': 'failed'} without raising an exception, how should the executor handle it?

• Mark it as successful because the handler returned normally
• Check that the output contains required keys but ignore the values
• Use assertion checks from the contract to validate the output; if a check fails, mark it invalid
• Ignore the output content and only log it

Reasoning guide: The correct answer is to use assertion checks from the contract. A normal return only indicates no exception, but business rules may require tests to be 'passed'. The contract’s checks tuple contains callables that return booleans; the result is valid only if all checks pass and required keys are present.

What it is

Result validation is an external contract check

validate_output takes an arbitrary output object and a ResultContract, returning a ValidationResult with a valid boolean and an errors tuple.

It first checks whether the output is a dict; if not, it immediately returns invalid with the error 'output must be an object'.

Then it checks for all required keys, generating errors for missing ones, and finally iterates over all check functions, adding a 'check N failed' error for any that return False.

What it is not

Result validation does not execute tasks or modify state

validate_output is a pure function: it only reads the output and contract, never calls any task handler, and never changes global state or databases.

It does not handle retries or recovery; if validation fails, the caller must decide the next action based on the error information.

It does not replace type checking or runtime monitoring; it only focuses on the structure and assertions declared in the contract.

How it relates to neighboring concepts

Collaboration between validation and executor

The executor calls validate_output after the task handler returns, using ValidationResult.valid to decide whether to mark the task as successful.

ResultContract is constructed by the planner or caller, containing required_keys and checks, which together define the acceptance criteria for task output.

When validation fails, the errors tuple provides specific reasons, aiding logging, debugging, and supporting later local retries.

Boundary decision for this stage: Validation only checks whether the output conforms to the contract, not how the task was executed; if the output is not a dict, it immediately returns invalid because subsequent key checks and assertions assume the output is a dictionary.

Start with a concrete problem

How to reset only the affected subgraph after a failure?

In the software delivery scenario, the task graph contains five tasks: inspect, code, test, publish, and docs. The code task depends on inspect, test depends on code, publish depends on test, and docs also depends on inspect.

When the code task fails, the directly dependent test task must be reset, but the transitive descendant publish must also be reset because publish depends on the result of test.

If only direct dependents of the failed task are reset, transitive descendants will be missed, causing later execution to use stale results.

Therefore, we need to implement a replan function that takes the task graph, current results dictionary, and failed task ID, and returns the set of tasks to reset and the set of tasks that can be preserved.

Make a prediction

In the following task graph, if code fails, which tasks should be reset?

• Only reset code
• Reset code and test
• Reset code, test, and publish
• Reset code, test, publish, and docs

Reasoning guide: The correct answer is to reset code, test, and publish. Because test directly depends on code, and publish depends on test, publish must also be reset. Although docs depends on inspect, inspect has not failed, so docs can be preserved.

What it is

What local replanning is

Local replanning identifies all tasks affected by a failed task in the task graph, including direct and transitive dependencies, and marks them for reset.

It starts from the failed task and repeatedly finds tasks whose dependency set intersects the already affected set, until no new tasks are added.

It returns two sorted tuples: reset_task_ids contains all task IDs to reset, and preserved_task_ids contains task IDs with status ‘succeeded’ that are not in the reset set.

What it is not

What local replanning is not

It does not execute tasks or modify the results dictionary; it only computes which tasks to reset and which to preserve.

It does not reset only direct dependents of the failed task; it must include all transitive descendants.

It does not perform a global reset of the entire task graph; it only processes the affected subgraph locally.

How it relates to neighboring concepts

Relationships with other components

The replan function depends on TaskGraph and Task to obtain task dependencies, and on TaskResult to obtain task status.

It returns a ReplanDecision object containing reset_task_ids and preserved_task_ids, which the executor uses during retry.

The affected_subgraph function is the core of replan, computing the affected task set through iteration.

Boundary decision for this stage: replan only computes the affected subgraph and classifies reset and preserved sets; it does not execute tasks or modify the results dict.

Start with a concrete problem

Why is checking only steps and cost insufficient?

In a software delivery scenario, a workflow may contain multiple tasks, each consuming steps, tokens, and cost. If the budget only checks steps and cost but ignores tokens, a task consuming a large number of tokens could be incorrectly allowed to execute, exceeding the token budget.

For example, suppose the budget is max_steps=3, max_tokens=100, max_cost=1.0. First, a task consumes (1, 40, 0.25), so used tokens are 40. If the next task consumes (1, 70, 0.25), total tokens would be 110, exceeding 100, but if only steps and cost are checked, the task would be allowed, violating the budget constraint.

Therefore, all three dimensions must be checked simultaneously to ensure that any dimension exceeding the budget causes rejection and no usage counters are modified.

Make a prediction

If WorkflowBudget’s can_reserve method only checks steps and cost, ignoring tokens, what happens when used tokens are 40 and you try to consume 70 tokens?

• Raises RuntimeError because tokens exceed the limit
• Does not raise an exception because steps and cost are within limits
• Raises ValueError because tokens are negative
• Modifies usage counters but logs a warning

Reasoning guide: The correct answer is ‘Does not raise an exception because steps and cost are within limits’. Since can_reserve only checks steps and cost, the token dimension is ignored, so even if tokens exceed the limit, no RuntimeError is triggered. This causes the budget guard to fail.

What it is

What WorkflowBudget is

WorkflowBudget is a dataclass that tracks cumulative usage across three resource dimensions during workflow execution: steps, tokens, and cost.

It provides a can_reserve method to determine whether a specified amount of resources can be reserved, and a consume method to actually consume resources.

The consume method updates usage counters only after a successful reservation, ensuring atomicity: either all counters are updated or none are.

What it is not

What WorkflowBudget is not

WorkflowBudget does not decide replanning strategy or execute any tasks. It only tracks and checks resource usage.

It is not a general-purpose resource manager; it is specifically designed for the three dimensions of workflow budgets.

It does not provide a rollback mechanism; once resources are consumed, they cannot be undone, so strict checks must be performed before consumption.

How it relates to neighboring concepts

Relationships with other components

WorkflowBudget works with the Executor and replan modules. The Executor calls budget.consume before executing a task to reserve resources; if an exception is raised, replan is triggered for re-planning.

Budget checking is a line of defense in the execution flow, ensuring that preset resource limits are not exceeded.

The can_reserve method uses <= comparison, meaning that when usage exactly equals the maximum, reservation is still allowed, permitting the last task to execute when the budget is exactly exhausted.

Boundary decision for this stage: Budget checks must be completed before any resource consumption, and any dimension exceeding the limit should block consumption. Using <= instead of < allows the last task to execute when the budget is exactly exhausted, but negative usage must be rejected because it represents invalid consumption.

Start with a concrete problem

When a task handler returns normally but validation fails, should the workflow continue to subsequent tasks or immediately return recoverable state?

In the software delivery scenario, run_workflow must execute tasks in topological order and validate each task’s output against its contract.

If the code task handler returns {'ok': False} but the validation contract requires value['ok'] is True, then validate_output returns valid=False.

The workflow cannot continue to the dependent verify task because its input may be based on invalid code output, leading to error propagation.

The correct behavior is to immediately call replan and return status='needs_replan' with the tuple of task IDs to reset, enabling upper layers to perform local retry.

Make a prediction

In run_workflow, when validate_output returns valid=False, which behavior best fits a recoverable workflow design?

• Continue executing subsequent tasks because the handler did not raise an exception, so the task itself succeeded.
• Stop execution immediately, call replan, and return needs_replan status to prevent invalid output from affecting dependent tasks.
• Ignore the validation result, mark the task as successful, and continue, handling failures at the end.
• Raise an exception to terminate the entire workflow and let the caller decide how to handle it.

Reasoning guide: The correct option is the second one. A handler returning normally only means no exception occurred; it does not mean the output satisfies the contract. Validation failure indicates the task result is untrustworthy, and continuing to dependent tasks wastes budget and may cause cascading errors. Immediately returning needs_replan with the reset task list allows upper layers to retry only the failed part, following the principle of local recovery.

What it is

Core mechanism of a recoverable workflow

run_workflow is a composer that schedules tasks in topological order, executes, validates, consumes budget for each task, and returns recoverable state on failure.

It relies on Executor to run tasks, validate_output to check output contracts, replan to generate reset decisions, and WorkflowBudget to control resource consumption.

When validation fails, the workflow stops immediately and returns WorkflowRun(status='needs_replan', completed=..., reset=...), where reset contains the task IDs that need to be re-executed.

What it is not

Boundaries of a recoverable workflow

It is not a simple sequential executor that ignores validation results and continues running subsequent tasks.

It does not implement topological sorting or replanning algorithms itself; instead, it calls the existing public APIs Executor.ready and replan.

It does not treat handler exceptions and validation failures identically: handler exceptions are detected via result.status == 'failed', while validation failures are detected via validation.valid == False. Both trigger replan and return needs_replan, but the completed tuple excludes the current task only on validation failure.

How it relates to neighboring concepts

Relationships with other modules

run_workflow uses Executor to get ready tasks and execute them, validate_output to check results, replan to generate reset decisions, and WorkflowBudget to consume budget before each execution.

Budget consumption must occur before run_ready to ensure that even if task execution or validation fails, the budget is correctly deducted, preventing infinite retries from exhausting resources.

The completed tuple only contains tasks with status succeeded and passing validation; a task that fails validation, even if its handler succeeded, must not appear in completed.

Boundary decision for this stage: When validate_output returns valid=False, you must immediately call replan and return needs_replan, without executing any dependent tasks; also, the current failed task must be excluded from completed, while previously successful tasks are retained.