You can schedule another thread, if you have SMT. You can execute out-of-order to try avoiding the stall.

But in general you are right in that once a stall happens, you aren't going anywhere.

>You can execute out-of-order to try avoiding the stall.

Exactly. By running multiple interleaved branch-free binary searches at once you offer independent work to the out of order engine.