You can still do the sneaky thing to query the build graph and only get changes in the transitive dependencies. This is almost always far smaller than the entire range between good and bad. For fast tests, the cost of doing the dependency lookup can be not worth it, but if your bisection will take more than 10 minutes, it's probably worth the effort.

It's still a little more complicated because then you have to bisect over a list of changes and not a raw range, but still.