Pruning CI Build Graphs in Large Monorepos

At 30,000 build targets, a monorepo CI pipeline that rebuilds and re-tests everything on every commit stops being an inconvenience and becomes an existential threat to delivery velocity. We measured a full-graph rebuild at 47 minutes on a mid-sized Bazel monorepo with roughly 1,800 engineers committing daily. The fix is not more compute — it is dependency graph pruning: computing the minimal affected subgraph for a given commit and executing only that. This article covers the theory, the traversal algorithms, and the production configuration required to implement dependency graph pruning correctly, without introducing false negatives that let broken code merge silently.

#The Problem Statement: Linear Cost Growth in Monolithic Build Graphs

Monorepos centralise source control but do not, by default, centralise build efficiency. As target count grows, naive CI configurations that invoke bazel test //... or npm run test at the repository root scale linearly (or worse, given shared test fixtures) with the total number of targets, regardless of how small the actual diff is. A one-line change to a leaf-level utility library can trigger a rebuild of every downstream service, every integration test, and every container image in the repository.

The core inefficiency is that CI treats the commit as a black box rather than as a delta against a known graph state. Without dependency graph pruning, the build system has no way to distinguish "this change touches an isolated documentation file" from "this change touches a core authentication module consumed by forty services." Both trigger identical, maximal build behaviour. This is the bottleneck that must be architected away.

#Architectural Breakdown: The Graph, the Hash, and the Diff

Correct dependency graph pruning requires three cooperating subsystems, each with distinct correctness guarantees:

• The static dependency graph — a directed acyclic graph (DAG) where nodes represent build targets (libraries, binaries, test suites) and edges represent declared dependencies. Bazel, Nx, Pants, and Turborepo all maintain this internally, derived from BUILD files, package.json workspace references, or equivalent manifests.
• The content-addressable hash layer — each node is assigned a Merkle-style hash computed from its own source files plus the hashes of its transitive dependencies. This is what allows a target to be skipped even if it sits inside the "affected" region of the graph but its actual inputs are byte-identical to the last successful build.
• The changed-file diff — the set of files modified between the base commit and the head commit, typically produced by git diff --name-only against a merge-base reference.

Dependency graph pruning is the operation that maps the changed-file diff onto the static graph via an ownership index (which target owns which file), then performs a reverse traversal — walking from the changed nodes outward along incoming edges — to compute the full set of transitively affected targets. This reverse traversal is the computationally interesting part; everything downstream of it (scheduling, parallel execution, caching) depends on the traversal being complete and correct.

#Why Forward Traversal Is the Wrong Direction

Engineers new to this problem frequently attempt forward traversal — starting from a changed target and walking its own dependencies. This is backwards. A change to library A does not affect what A depends on; it potentially affects everything that depends on A. Correct dependency graph pruning always operates on the reverse dependency graph (sometimes called the "rdeps" graph), constructed by inverting every edge in the static DAG.

#Implementation Logic: Step-by-Step Execution

1. Checkout the merge-base commit shared between the feature branch and the target branch.
2. Compute the changed-file set via git diff against that merge-base, not against HEAD~1, to correctly handle squash-merges and rebased history.
3. Resolve each changed file to its owning build target(s) using the build system’s ownership query (e.g. bazel query with --output=package, or an Nx project.json file-to-project map).
4. Load the cached static dependency graph (do not recompute it from scratch on every run — persist it as a build artefact and incrementally patch it).
5. Invert the graph edges to obtain the reverse adjacency list.
6. Run a breadth-first traversal from every changed target across the reverse adjacency list, collecting all reachable nodes. This set is the affected subgraph.
7. Cross-reference each node in the affected subgraph against the content-addressable cache. Nodes whose computed hash matches a previously successful build are pruned from the execution set even though they remain in the affected set for reporting purposes.
8. Topologically sort the remaining execution set to determine safe parallel execution order, respecting the original (non-inverted) edge direction.

#Reference Query with Bazel

Bazel exposes this natively through its query language. The rdeps function performs exactly the reverse traversal described above, scoped to a universe expression for performance:

1# Get merge-base and changed files
2MERGE_BASE=$(git merge-base origin/main HEAD)
3CHANGED_FILES=$(git diff --name-only "$MERGE_BASE" HEAD)
4
5# Resolve changed files to Bazel labels
6CHANGED_TARGETS=$(bazel query 
7  --input=/dev/null)
8
9echo "$affected" > affected_targets.txt

For further detail on the query grammar, refer to the official Bazel Query Language reference, specifically the semantics of rdeps and universe scoping, which materially affect traversal performance on graphs exceeding 50,000 nodes.

#Graph Traversal in Custom Tooling

Teams without Bazel (e.g. polyglot monorepos with a hand-rolled dependency manifest) must implement the reverse BFS themselves. The following illustrates the core algorithm operating on a serialised adjacency map:

1from collections import deque, defaultdict
2import json
3
4def invert_graph(forward_edges: dict[str, list[str]]) -> dict[str, list[str]]:
5    reverse = defaultdict(list)
6    for node, deps in forward_edges.items():
7        for dep in deps:
8            reverse[dep].append(node)
9    return reverse
10
11def affected_subgraph(reverse_edges: dict, changed_nodes: set[str]) -> set[str]:
12    visited = set(changed_nodes)
13    queue = deque(changed_nodes)
14    while queue:
15        node = queue.popleft()
16        for parent in reverse_edges.get(node, []):
17            if parent not in visited:
18                visited.add(parent)
19                queue.append(parent)
20    return visited
21
22with open('graph.json') as f:
23    forward = json.load(f)
24
25reverse = invert_graph(forward)
26changed = {'lib/auth', 'lib/logging'}
27affected = affected_subgraph(reverse, changed)
28print(f"Dependency graph pruning yielded {len(affected)} affected targets")

#Wiring Pruned Targets into CI

Once the affected set is materialised as a flat file, it becomes a matrix input for the CI orchestrator rather than a static job list. This is where dependency graph pruning delivers its measurable throughput gain — the executor only schedules work for nodes present in affected_targets.txt:

1jobs:
2  compute-affected:
3    runs-on: ubuntu-latest
4    outputs:
5      targets: ${{ steps.diff.outputs.targets }}
6    steps:
7      - uses: actions/checkout@v4
8        with:
9          fetch-depth: 0
10      - id: diff
11        run: |
12          ./scripts/compute_affected.sh > affected.json
13          echo "targets=$(cat affected.json)" >> "$GITHUB_OUTPUT"
14
15  build-affected:
16    needs: compute-affected
17    strategy:
18      matrix:
19        target: ${{ fromJson(needs.compute-affected.outputs.targets) }}
20    runs-on: ubuntu-latest
21    steps:
22      - run: bazel build ${{ matrix.target }}
23      - run: bazel test ${{ matrix.target }}_test

This pattern keeps the pruning decision as a first-class pipeline artefact, auditable independently of the build itself — which matters considerably when a pruning bug is suspected as the cause of a missed regression.

#Failure Modes and Edge Cases

Dependency graph pruning is only as trustworthy as the completeness of the declared graph. The most damaging failure mode is the undeclared dependency: a target that consumes another target’s output at runtime (via a shared config file, an environment variable, or a dynamically loaded plugin) without declaring it in the build manifest. In this scenario, the reverse traversal never discovers the consumer, the affected subgraph is incomplete, and a broken change ships with a fully green CI run. This is a false negative, and it is strictly more dangerous than the cost the pruning was meant to save.

Related edge cases worth architecting against explicitly:

• Cycle contamination — a genuine cycle in the declared graph (often from circular test fixtures) breaks topological sort and must be rejected at graph-load time, not silently tolerated with an arbitrary tie-break.
• Generated file drift — code generation steps (protobuf, GraphQL schema stitching) that run outside the tracked build graph create files the ownership index cannot map, effectively invisible to the diff resolver.
• Merge-base miscalculation — computing the diff against HEAD~1 instead of a true merge-base after a rebase produces an inflated or deflated changed-file set, corrupting the entire downstream traversal.
• Global configuration files — a change to a root-level lockfile or compiler flag file should, by design, invalidate the entire graph. Pruning logic must special-case these paths rather than resolve them through the ownership index, or it will incorrectly scope a global change to a narrow subgraph.
• Cache poisoning across branches — if the content-addressable cache is shared across untrusted forks or external contributors, a malicious actor can craft inputs that hash-collide with a trusted artefact, bypassing execution entirely. This overlaps with the broader architectural patterns used in supply-chain security for build systems.

#Scaling and Security Trade-offs

Dependency graph pruning is not a free optimisation; it trades absolute correctness guarantees (full rebuild, every time) for throughput, and that trade must be actively managed rather than assumed safe.

• Full-graph builds: highest confidence, zero false-negative risk, but cost grows linearly (or superlinearly with shared fixtures) with repository size — unsustainable past roughly 5,000–10,000 targets on standard CI runner fleets.
• Pruned builds via dependency graph pruning: typically reduce median CI wall-clock time by 70–90% on large monorepos, but introduce a dependency on the completeness of the declared manifest — a governance problem, not just a tooling problem.
• Periodic full-graph reconciliation: running an unpruned build on a schedule (e.g. nightly, or on merge to the trunk branch) acts as a safety net that catches undeclared-dependency drift before it compounds across many pruned merges.
• Remote cache trust boundary: pruning efficiency is amplified by remote caching, but every cache hit is an unverified trust decision. Signing cache entries with a content hash tied to a verified builder identity mitigates poisoning, at the cost of additional round-trip latency on cache lookups.
• Ownership index staleness: the file-to-target mapping must be regenerated on every graph change, not cached indefinitely; stale ownership data silently degrades traversal accuracy over weeks without triggering any visible CI failure.

Teams operating monorepos beyond the low tens of thousands of targets should treat dependency graph pruning as a core piece of build infrastructure with its own test suite, ownership, and on-call rotation — not as a CI script maintained informally by whichever engineer wrote it first. The traversal correctness of the reverse graph is now load-bearing for release safety, and it should be reviewed with the same rigour as the production services it gates.