I believe it’s because when the metadata is missing, you need to download each version of an entire massive package and try installing it to check compatibility. Repeated for every possible version, backwards until one works.

I think you’re right; that definitely seems to be poetry’s behaviour. So that’s clearly IO-bound. On the other hand, Anaconda got massive speedups by switching to a better dependency solver. Dependency resolution is basically SAT, after all.