Task Graph

A task graph is the directed acyclic graph a build tool computes over the tasks it has been asked to run, with one node per task and one edge per dependency between tasks. That graph fixes three things about the run: the order tasks execute in, which tasks are allowed to run at the same time, and which tasks can be answered from a stored result instead of being executed.

Every build tool that manages more than one package keeps a structure of this shape. Some call the nodes tasks, some call them targets, and some call them actions. The vocabulary moves between tools; the three decisions the graph drives stay the same.

Definition

A node is one unit of work bound to one package or target, written in most tools as a pair such as api#build or web#test. An edge is a "must finish first" relation pointing from the dependency to the dependent, so an edge from utils#build to api#build means the second cannot start until the first has a result.

Edges come from two places. Task-to-task rules inside a package produce the local edges, such as a test task that requires its own build task. The package dependency graph, read from the manifests, produces the cross package edges: if web imports utils, then the build task of web depends on the build task of utils.

The graph must be acyclic. A cycle describes a set of tasks that each wait on another, so no valid order exists, and build tools reject the configuration with a cycle error rather than picking one arbitrarily.

What the graph decides

Order comes from a topological sort. The tool repeatedly takes the nodes with no unsatisfied dependencies, runs them, and moves on, which guarantees no task sees a half built dependency.

Parallelism comes from the width of each wave. Two nodes with no path between them are independent and may run at once, bounded by the concurrency the tool was given. The critical path is the part width cannot help with: a chain of four nodes takes at least four task durations on any machine.

Reuse comes from hashing. Before executing a node the tool computes a hash over that node's inputs, including the hashes of its dependencies, and looks for a stored result. A hit replays the recorded outputs and logs. This is why an edge is more than an ordering constraint: it carries the upstream hash into the downstream one, so a changed package invalidates everything downstream of it and nothing else.

The task graph and the workflow job graph

GitHub Actions maintains its own graph at the job level. Jobs with no needs key start together, and a job that lists needs waits for every job it names to finish first (GitHub workflow syntax, checked on 2026-08-13). A matrix expands one job definition into many, up to 256 jobs per workflow run, and max-parallel caps how many of those run at once (GitHub Actions limits, checked on 2026-08-13).

The two graphs sit at different altitudes and answer to different owners.

Example

Take a repository with four packages. web imports ui and utils, api imports utils, and every package defines a build task and a test task. A monorepo task runner config states the two edge rules once, and the tool applies them across every package:

{
  "tasks": {
    "build": {
      "dependsOn": ["^build"],
      "outputs": ["dist/**"]
    },
    "test": {
      "dependsOn": ["build"],
      "inputs": ["src/**", "test/**"]
    }
  }
}

^build means the build task of every package this package depends on. build without the caret means the build task of this same package. Those two lines expand into eight nodes and their edges.

The workflow runs the whole graph inside one job, and checks out full history so the tool can compare the branch against the merge base:

name: build
on:
  pull_request:

jobs:
  build-and-test:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v4
        with:
          fetch-depth: 0
      - uses: actions/setup-node@v4
        with:
          node-version: 22
      - run: npm ci
      - run: npx turbo run build test --filter=...[origin/main]

Now trace one pull request that edits a single file in utils. The tool hashes every node, finds that only the utils subtree moved, and treats the rest of the graph as answered.

Two behaviors show up in that table. Wave 2 holds four independent nodes, so a runner with enough cores executes them in one pass, while a two core machine runs them in two passes and the run takes longer for reasons that have nothing to do with the code. And the ui branch is downstream of nothing that changed, so both of its nodes replay from stored results and never compile anything, which is the whole payoff of computing the graph before running it.

The critical path here is utils#build to web#build to web#test. That chain of three sets the floor on how fast this pull request can be verified, and the way to shorten it is to remove an edge from the graph rather than to add machines.

Where the graph meets a GitHub Actions run is a sizing decision. One job on one large runner keeps the whole graph in a single process, so waves fill the cores of that machine and the tool's local cache is already warm. Splitting the graph across matrix jobs adds machines and adds startup, checkout, and cache restore to each shard. Monorepo pipelines on GitHub Actions covers that tradeoff with worked numbers. When a tool dispatches nodes to a pool of worker machines rather than running them locally, the mode is remote execution, and the graph is what tells the coordinator which nodes are ready to dispatch.

Related Terms

• Monorepo pipelines on GitHub Actions: how a task graph is split across jobs and matrix shards, and what each split costs in startup and cache restore time.
• Remote execution and worker pools: the mode where a build tool sends ready graph nodes to worker machines and fetches back only the outputs it needs.
• Running only the tests a change affects: selecting the affected subgraph on a pull request and the failure modes of getting the base commit wrong.
• WarpBuild caching documentation: cache action inputs and key examples for holding a tool's local cache between runs.
• WarpBuild pricing: per minute rates by runner type.