Chemical similarity searches: when is complexity justified?

Chemical similarity is a very popular method for virtual screening. Similarity methods have been under development for decades and there is a tendency for the newer methods to be more complex (and more computationally expensive). One stated justification for adding complexity is that the methods are better able to 'lead-hop'. However, is this really true? I argue that only some types of complexity are useful in this regard.