What a Full Dep Graph Actually Unlocks

Yesterday’s post was about getting the graph. Manual stubs, tags = ["manual"], 26% to ~100% coverage, the whole trick. The PR landed. CI is green. Now what?

Now the interesting part. A complete dependency graph is infrastructure. It doesn’t do anything by itself. It enables things that were previously impossible, impractical, or held together with 1,600 lines of custom Python.

This post is about what those things are.

The incumbent: find_changed

Before we talk about what the graph enables, we need to talk about what we already have. Because we already have a CI test selector. It works. It’s been running for months. Every PR goes through it.

find_changed is ~1,600 lines of Python that answers: “given these changed files, which test packages should run?” It builds two parallel graphs:

• Package-level from uv.lock — workspace packages and external deps, including version tracking
• File-level from ruff analyze graph + AST scanning — individual Python files and their imports

Then it DFS-walks the reverse dependencies. Changed foo.py → trace upward → affected packages → test matrix for GitHub Actions.

It also handles things Python imports can’t see: Dockerfiles, C++ sources via package_extra_dependencies.yml, conftest.py propagation, inline TOML annotations for runtime file deps, external version bumps in the lockfile. These are real dependencies that matter for correctness, and the tool catches them.

Here’s the thing: find_changed is package-granularity. Change one file in mai_layers, and every test in mai_layers runs. Every test in every package that depends on mai_layers runs. That’s the smallest unit it can reason about — the package.

The new option: Bazel rdeps

Bazel reasons about targets. A target is a py_library, a py_test, a specific thing with specific deps. When you ask Bazel “what depends on this?”, you get back individual targets, not whole packages.

# "What is affected by a change to mai_config?"
$ bazel query 'rdeps(//..., //mai_config/...)' | wc -l
65

# "What TEST targets are affected?"
$ bazel query 'kind(py_test, rdeps(//..., //mai_config/...))' | wc -l
# Only the test targets — not libraries, not binaries

That second query is the key. You’re not asking “which packages.” You’re asking “which specific test targets have a transitive dependency on this change.” If a package has 20 tests and only 3 of them transitively depend on the thing you changed, you run 3.

The show_affected.sh script that does this in CI is 20 lines of bash. find_changed is 1,600 lines of Python. That’s not a flex — find_changed does more things. But for the core question of “what depends on what,” the graph already has the answer.

Head-to-head: test selection

Let’s compare what happens when you change a leaf package — say fortknox, which nothing critical depends on.

For a core library like mai_nano:

The precision gap compounds. A package with 50 tests where 5 are affected: find_changed runs 50, Bazel runs 5. Multiply by the number of affected packages, and you’re looking at potentially 3-10x fewer test invocations for the same correctness guarantee.

Head-to-head: pyright

This one’s less obvious but possibly higher-impact for developer experience.

The current state

Pyright runs on every PR. It type-checks the entire repo: 106 execution environments, all 104 packages. Every time. No caching between runs, no incremental mode. Takes about 5 minutes.

Five minutes doesn’t sound bad until you do the math:

Four hundred hours a year of engineers watching a progress bar. For a type checker that re-checks 103 packages that didn’t change.

What scoped pyright looks like

Yipu’s PR #22032 already adds pyright_targets — a tool that does BFS on the dep graph to scope pyright to affected packages. The full Bazel dep graph makes this trivial:

# "Which packages need pyright after changing fortknox?"
$ bazel query 'rdeps(//..., //lib/fortknox/...)' \
    --output package | sort -u
# → ~6 packages instead of 104

Change a leaf package → pyright runs on that package → 15-30 seconds instead of 5 minutes. Change a core lib → pyright runs on the affected subgraph → maybe 2 minutes. Still better than 5.

The endgame: per-package pyright in Bazel

The real endgame is pyright_test targets in BUILD files. aspect_rules_lint is already in our MODULE.bazel (we use it for Starlark formatting). Extending it to Python linting means:

• Per-package pyright_test targets
• Cache hits on unchanged packages → 0 seconds
• Only invalidated when deps change (Bazel tracks this natively)
• Estimated improvement: 80-95% faster for typical PRs

The “no Python changes” row is the silent killer. Someone edits a markdown file. Pyright runs for 5 minutes. With the dep graph, the query returns zero affected Python targets, and pyright doesn’t run at all.

GPU test targeting

GPU runners are expensive. Like, “we have a finite budget and every minute counts” expensive. Right now, whether a change needs GPU tests is determined by a hardcoded list in the workflow file:

# run_gpu_tests.yml (simplified)
GPU_TEST_PKGS: "rocket mai_layers mai_distributed ..."
# ~13 manually maintained entries

Change anything in those packages → spin up a GPU runner. Change anything else → don’t. The list is maintained by humans who sometimes forget to add new GPU-dependent packages and sometimes forget to remove ones that no longer need GPU.

With the dep graph, you don’t need a list. You need a query:

# "Does this change affect any torch-tagged test targets?"
$ bazel query 'attr(tags, "torch", rdeps(//..., //changed/package/...))'

If the result is empty, no GPU runner. If it’s not empty, spin one up — and you know exactly which tests need it, not “run everything in these 13 packages.”

Beyond CI: things we couldn’t do before

Test selection, pyright scoping, GPU targeting — those are the immediate CI wins. But a complete dep graph is a data structure, and data structures have more than three use cases.

Impact analysis in PRs

Already shipping. The CI annotation step shows affected targets in the PR summary:

This change affects 60/986 targets (~94% skip rate)

Before you merge, you know the blast radius. Before a reviewer opens the diff, they know if this is a leaf change or a core lib change. Context before code.

Migration planning

The graph knows which packages are fully migrated (real BUILD files) and which are stubs (tags = ["manual"]). It also knows which stub packages have all their deps already migrated. That’s your migration queue — automatically, no spreadsheet.

# "Which manual-tagged packages have all deps already migrated?"
# → These are ready for full migration with minimal effort

Hub detection

mai_nano has 319 reverse dependencies. That’s a hub. Hubs need:

• More test coverage (a bug here breaks 319 things)
• More review rigor (a bad API change here propagates everywhere)
• More careful deprecation planning (you can’t just delete a hub)

The graph gives you fan-in counts for free. Sort by fan-in, and you have a prioritized list of “packages that deserve the most engineering attention.”

Leaf detection

The inverse. Packages with zero or near-zero reverse dependencies are safe to:

• Extract into separate repos
• Deprecate without cascade analysis
• Experiment with aggressively (low blast radius)

Decoupling analysis

Connected components. Minimum cuts. “If we split the monorepo along this boundary, how many cross-boundary edges would we sever?” These are graph theory 101 questions that you literally cannot ask without a complete graph.

Critical path analysis

The longest dependency chain in the graph is the minimum parallel build time. Shortening the critical path is the highest-leverage optimization for build speed. The graph tells you exactly where to look.

BUILD file drift detection

This is the maintenance story. When someone adds a dependency to pyproject.toml, the generated BUILD file is stale. Run the generator, diff the output, fail CI if they diverge. The graph stays accurate because CI enforces accuracy.

The two-graph story, resolved

A previous post explored how find_changed and Bazel see different dependency graphs. They read the same files. They arrive at different conclusions. Both are correct — they’re answering different questions.

The full dep graph changes this. Bazel now sees every package, every edge. The two graphs still disagree on details — find_changed knows about Dockerfiles and runtime file deps that Bazel doesn’t — but the structural disagreement is gone. Bazel is no longer blind to 74% of the monorepo.

The path forward is clear: migrate find_changed’s extra-dependency knowledge into Bazel (non-Python deps as filegroups, runtime deps as data attributes), and you converge the two graphs into one. Not today. But the architecture makes it possible, and it wasn’t possible a week ago.

What this doesn’t solve

Intellectual honesty moment. The dep graph is not magic.

find_changed’s non-Python deps. Bazel’s dep graph is Python-level. Dockerfiles, C++ sources, cmake configs — find_changed tracks these via package_extra_dependencies.yml. Bazel doesn’t know about them yet. Until those relationships are expressed as Bazel deps, find_changed catches things Bazel misses.

Version bump detection. find_changed diffs the lockfile. If numpy goes from 1.24 to 1.25, every package using numpy gets retested. Bazel doesn’t do this — @pypi//numpy is @pypi//numpy regardless of version. This matters for correctness.

The lib/bus problem. C++/Cython packages can’t be fully represented as py_library stubs. The Python-level dep edges are there, but the native build deps aren’t. lib/bus affects ~28 downstream packages, and the graph captures the Python side but not the C++ side.

Migration is still required. The stubs give you the graph. They don’t give you sandboxed builds, hermetic tests, or cache-aware execution. Those require real BUILD files — the full migration. The graph tells you what to migrate and in what order. It doesn’t do the migration for you.

These are real gaps. They’re also scoped gaps — we know exactly what’s missing, and we know how to fill each one. That’s progress.

The roadmap

Here’s what becomes possible, roughly in order of effort:

The first three are weeks of work, not months. The graph is the hard part, and the graph is done.

The punchline

Yesterday’s post ended with “stop counting packages on Bazel, start counting edges in the graph.” Today’s answer to “why?” is concrete:

• Test selection drops from package-level to target-level precision
• Pyright drops from 5 minutes to 15 seconds for leaf changes
• GPU targeting drops from a manual list to a query
• 1,600 lines of custom Python become 20 lines of bash — eventually

A dependency graph that covers 26% of your monorepo is a curiosity. A dependency graph that covers 100% of your monorepo is infrastructure. Infrastructure you build everything else on.

The graph is done. Now we build on it.

This is a follow-up to The Dep Graph Is the Product, which covered how we got to 100% graph coverage. Previous posts in the series: Your Monorepo Has Two Dependency Graphs (and They Disagree), When Homegrown Tools Hit the Ceiling.