Ruby's bundler had these exact same issues 5 or so years ago. I remember attending a talk by on Bundler run by it's core devs and asking about how they make dep resolution faster. Turns out that it was never really a solved problem there either, Bundler just uses a bunch of heuristics to avoid cases like the 18 minute `Pipefile.lock` described above.