3 ms·
I've built a few vector search engines too, so this was an immediate red flag: "Brute force takes 12 seconds / query on 1 million vectors of 768 dim". No, a sa
by Radim 5y ago
I've built a few vector search engines too, so this was an immediate red flag: "Brute force takes 12 seconds / query on 1 million vectors of 768 dim".
No, a sane brute-force search (via BLAS) that size should be a ~200ms / query. I.e. SIXTY TIMES faster!
If they (Faiss?) got this wrong, what else did they get wrong?
I understand researchers want to showcase their "best and fastest" approach, so they fudge the baselines. Approximate search can be genuinely useful – orders of magnitude faster than (even non-fudged) brute force, and using less RAM too.
But as a user, tech stack complexity is also a consideration. Because the trade-off is not only "speed vs accuracy". Brute force is a trivial algorithm, easy to implement and maintain with no corner cases. It has completely predictable data access patterns (linear, sequential, fixed response time, 100% accuracy). It supports operations (update, range, dynamic k-NN) that complex indexes struggle with.
So if your dataset is tiny – and anything under 1 million counts as tiny – do you really need to maintain an external dependency of fancy data structures and approximate algorithms?
- jhj 5y ago1 vector against 1 million vectors in 768 dims at k = 10 takes 259 ms for me using Faiss CPU IndexFlatL2 with Intel MKL: https://gist.github.com/wickedfoo/165b69075cfcceba872aec1c46aa3ce6 https://gist.github.com/wickedfoo/165b69075cfcceba872aec1c46...
- Radim 5y agoSounds about right. I like how you tested "query multiple vectors at once". Super useful when documents can be batched, for increased throughput. If I'm reading your benchmark correctly, Faiss brute-force can do a batch query of 10,000 vectors in ~19 seconds => 1.9 ms per vector. That's pretty cool – and more than 130x faster than querying those 10,000 vectors individually, one by one.