Dependency Graphs Guide AI Agent Tool Execution

I treat an AI agent’s tool plan as a proposal - not permission to run. Before each call, I check its inputs, permissions and prerequisites. In the four-call order example, two lookups can run together, but reservation waits for both, and confirmation waits for reservation.

My approach covers four checks:

• Build the graph: map outputs to inputs, then reject missing references, type errors and cycles.
• Control execution: run ready calls within resource limits and save valid results before releasing dependent work.
• Handle failures: set retry limits, prevent duplicate writes, and plan for cancellation and corrective actions.
• Test and measure: check crash recovery, latency and cost per completed workflow in £.

The rule I follow: a valid dependency graph does not grant approval. I check permission for the exact action and arguments, and send uncertain outcomes for human review rather than retrying blindly.

::: @figure {AI Agent Tool Execution: Dependency Graph and Safety Checks} :::

System design: a durable DAG runner for AI agents (build your own)

1. Map Tool Inputs and Outputs

Once the graph is defined, map each edge to exact input and output fields before scheduling any call.

In this workflow, customer_email, sku, quantity, order_id and currency are initial inputs. customer_id, warehouse_id and reservation details are tool-produced outputs.

Link Output Fields to Required Inputs

Run the two lookups concurrently. Reservation must wait for both results, and confirmation must wait until reservation succeeds. Keep their namespaces separate: use initial.field for supplied values and node_id.field for tool outputs.

Keep data dependencies, exclusive resources and business-order constraints separate. Label them with requires_value, exclusive_resource and must_precede metadata. Two reservation attempts for the same order need resource exclusion, even if neither passes outputs to the other.

A stock lookup doesn't guarantee stock: the reservation call must check availability when it runs. Leave unused outputs, such as delivery_address, out of downstream payloads. There's no need to pass customer data that the next call won't use.

With the field mappings in place, validate every reference and reject cycles before execution.

Reject Missing References and Cycles

Check references before analysing the graph. Reject unknown nodes, missing inputs, malformed paths, missing output fields, type mismatches, unsupported transformations, self-dependencies and duplicate field-level edges.

Check semantic types, not just the schema: a customer ID isn't a warehouse ID. Return specific errors, such as UNKNOWN_NODE: stock_check and MISSING_OUTPUT: customer_lookup.account_status. For cycle checks, treat multiple field mappings between the same two calls as a single edge.

Run depth-first search with unvisited, visiting and visited states. An edge back to a visiting node identifies a cycle; use the active stack to recover its path. Include business-order edges in this check.

For example, add an invalid edge reserve_order.customer_id → customer_lookup.customer_id while retaining the valid edge customer_lookup.customer_id → reserve_order.customer_id. DFS then reports customer_lookup → reserve_order → customer_lookup. If those declarations are absent, report a schema error first.

Reject the graph before execution. Don't infer or invent missing values to break a cycle.

2. Schedule Calls as Prerequisites Arrive

Dispatch independent nodes as soon as their prerequisites clear. Don’t wait for a global batch barrier.[12][13] The scheduler uses these dependencies to set release conditions for each node.

Track Ready Calls and Unresolved Dependencies

Initialise unresolved-dependency counts from distinct prerequisite nodes: 0 for each lookup, 2 for reservation and 1 for confirmation. Queue a call only when its count reaches zero and all required inputs are valid.[8][9]

Before dispatch, recheck authorisation, input freshness, deadlines, worker capacity, rate limits and resource locks. On completion, validate and persist the result, then advance dependants as one atomic operation. Use an event or attempt ID to apply each completion exactly once, including after retries.[10][11]

Use a live state record to decide what can run next. Each row shows a node’s dependency count and execution state. Timestamps use UK dates and a labelled time zone.

Define Failure Policies

Choose a policy that tells the scheduler when to release, block or compensate dependent nodes.

Use five states: succeeded, failed, timed out, cancelled and skipped. Only valid required outputs release dependants, unless their contracts explicitly allow partial inputs or fallbacks. Retry transient errors with bounded back-off, but don’t repeatedly retry permanent validation or authorisation errors.

Apply the chosen policy before execution begins. It determines how blocked and downstream work behaves.

With dispatch and retries defined, the next control point is side effects and cancellation.

Control Side Effects and Cancellation

Give every retryable write a stable idempotency key derived from the workflow ID, graph version, node ID and logical operation - not the attempt number. If a response is lost, check the remote operation’s status before assuming nothing happened.

Define release_reservation(reservation_id) for confirmed reservations that cannot proceed. Track whether release was requested, accepted, completed or needs manual intervention.

A stopped node must not release descendants for execution. Persist cancellation before stopping new dispatches, then propagate it to descendants that no longer have a valid business purpose. Cancelling in-flight calls is best effort: remote writes may still finish.

Authenticate late results and check their graph version and attempt ID. Don’t let cancelled or superseded attempts advance the graph. Route side effects to reconciliation or compensation.

Keep a compact audit record of graph versions, approvals, validation results, retries, deadlines, lock and rate-limit decisions, completion events and compensation outcomes.

3. Build and Test the Scheduler

Start with the order workflow: validate inputs, reserve stock and calculate delivery options in parallel, then charge payment, create shipment and send confirmation only after the required results arrive.

Define typed contracts for inputs, outputs, permissions, timeouts, retry policy, side-effect classification and resource requirements. Keep graph validation, scheduling and tool adapters separate. This lets you test the scheduler without live tool calls.

Write Scheduler Logic and Save Execution State

Extend persisted state to store each node’s status, unresolved prerequisite count, resolved inputs, output reference, attempt ID, error details, retry count, timestamps and transition history. Persist every transition before emitting events. Use a transaction or compare-and-set operation to claim work for dispatch.

The pseudocode below brings validation, claiming, completion and dependant release into one scheduler loop.

build(graph):
    validate_unique_ids(graph)
    validate_referenced_nodes_and_fields(graph)
    if topological_sort(graph).does_not_visit_every_node():
        raise CycleError

    persist_nodes_as_pending(graph)
    for node in graph.nodes:
        node.unresolved_prerequisite_count = count(distinct node.prerequisites)
        if node.unresolved_prerequisite_count == 0:
            mark_ready(node)

dispatch(node):
    transaction:
        require node.status == READY
        require prerequisites_resolved(node)
        require authorisation_valid(node)
        require within_deadline(node)
        require resource_capacity_available(node)
        require not_cancelled(node)
        compare_and_set(node, READY, CLAIMED)
        save_attempt_and_outbox_record(node)
    mark_running_before_call(node)

complete(event):
    transaction:
        if already_recorded(event.workflow_id, event.node_id, event.attempt_id):
            return

        validate_output_schema(event.output, event.node)
        persist_result_and_completion_event(event)

        for dependent in distinct_dependants(event.node_id):
            record_prerequisite_completion(dependent, event.node_id)
            if all_required_fields_present(dependent, event.output):
                decrement_unresolved_prerequisite_count_once(dependent, event.node_id)
            if unresolved_prerequisite_count(dependent) == 0 and dependent.status == PENDING:
                mark_ready_and_enqueue_after_commit(dependent)

The loop turns graph rules into durable state transitions, claims and releases.

Deduplication prevents duplicate state changes - not duplicate external side effects. A worker might finish a write, then crash before saving the result. Keep the same logical execution ID across attempts. During recovery, reconcile uncertain outcomes before retrying with the same external idempotency key. Recover expired claims and resource reservations so they don’t stay occupied indefinitely.[7][14]

Test Dependencies, Retries and Resource Limits

Once state transitions are durable, test race conditions, retries and restart recovery. Use deterministic fixtures for chains, independent branches, fan-in and fan-out. Add regression tests to prove that invalid graphs, including cycles, never reach READY.

Replay completion events and make workers compete for the same work. Prerequisite counts must change only once, completion processing must happen exactly once, and only one claim may succeed.

Inject crashes before and after dispatch, result persistence and dependant release. Test timeouts, bounded retries, cancellation, partial failures and restart recovery. Check that every start meets its prerequisites, current authorisation and resource limits. When capacity runs out, work must stay queued - not start running.

Measure Reliability, Latency and Cost

After proving correctness, measure how efficiently the scheduler runs. Track queue depth and age, blocked nodes, critical-path duration, achieved parallelism, prerequisite-wait time, tool latency, retries, failure propagation and recovery time. Compare workflow duration with the critical path to spot avoidable waiting.

Report median and p95 latency alongside cost per completed workflow in £. Separate model/token costs, tool charges, infrastructure and retry overhead. Include spending on failed runs so it doesn’t disappear from the calculation.

Conclusion: Validate Dependencies Before Running Tools

Treat the graph as an execution contract: check inputs, prerequisites, schemas and cycles before dispatching tools. Then validate results before passing them downstream.

A valid graph does not establish intent or authorisation. Add controls around the actions it permits, and bind approval to the current graph state and the exact actor, tool and node arguments - not a generic confirmation flag.[15] Send uncertain outcomes for human review rather than retrying blindly.

Before rolling out further, pilot one bounded workflow. Agree retry limits, timeouts, cancellation rules and human-review conditions before launch. Set acceptance thresholds for completion rate, p95 latency, cost per completed workflow and side effects. Expand only when tests consistently meet those thresholds, and revalidate the graph whenever tools or dependencies change.

FAQs