Reading the issue and the benchmarks, it seems like the right call here might be to make the "throws error" version the one that defers the failure check, and to use a similar algorithm for update (which must search to the leaf in any case). So (!) uses the new algorithm, as do alterF and family. lookup, member, and findWithDefault retain the old algorithm.
That does leave an opening for an expected-to-hit lookup that can still miss. I'd suggest having an alternative only to lookup, rather than repeating the whole suite of lookup-, member-, and find-like things.
It looks like the benchmarks are manipulating quite large IntMaps? I wonder how things look for smaller, shallower maps where fail-late tends to dominate. I use maps-with-miss all the time, but seldom with (say) millions of elements.
-Jan-Willem Maessen