This sounds like the "Closest pair of points problem", which should have fast solutions - O(n log(n)) comparisons instead of O(n^2), which makes a huge differen

This sounds like the "Closest pair of points problem", which should have fast solutions - O(n log(n)) comparisons instead of O(n^2), which makes a huge difference when you have 10 million vectors. You might not find an off-the-shelf solution, but there are some good explanations of the approach at least.