Possible solution: binary search to find the number of hops (buffering intermediate responses so that you don't have to re-send them), and send all missing TTLs in parallel once you've determined the number of hops to use.

You could do a linear scan in parallel with the binary search so that the user-facing behavior looks more or less the same as now.

(It could be that some utilities---including this one!!!---already do that. The linked article doesn't go into that level of detail and I haven't read the code.)

Knowing little about other use-cases, i would guess sending 1,2,4,8, ~12 is well within bandwidth budget for all people running traceroute.

Some bastardized version of binary search sounds reasonable for most internet targets.

Shouldn't there be some way to match up an ICMP packet received to a particular probe(s) e.g. by UDP port or something else?