[hinkley]

I think for pairs you can still do a logarithmic search, it’s just not base 2.

A trinary or quaternary search should be able to find two bugs at once (and intuition tells me a quad search should be able to handle three).

Say you have 16 optimizations and 7 and 12 don’t work together. Eliminate the first half, the second half, the odd or the even opts and the build is still green. But if you remove the first third or quarter the tests still fail.

So in a trinary search you might see 1-16 -> 6-16 -> 6-13 -> 6-8,12-13 -> 6,7,8,12 -> 6,7,12 -> 7,12. Including the first and last sanity checks you’re in for about 8-14 test passes for 16 tests, which is a lot better than 2^16.

But there’s still a binary search you can do, and that’s a bisect of the commit history. Before some commit this bug didn’t happen. And that’s going to contain one half of the bug. Now you run a second binary search to find its complement.