When I wrote embedded C code in the 2000s we latched onto something Raymond Chen, wrote in passing
My O(n) algorithm can run circles around your O(log n) algorithm; why much of what you learned in school simply doesn’t matter
True of a sorting algorithm. True of vector search.
People think they need a vector database. But often the number of vectors to search turns out to be low. And numpy can brute-force an array of float32s very fast:
| Index Size | Client Threads | QPS | Avg Latency |
|---|---|---|---|
| 1000000 | 1 | 79.7 | 0.012s |
| 1000000 | 10 | 170.5 | 0.058s |
| 8841823 | 1 | 9.34 | 0.106s |
| 8841823 | 10 | 18.34 | 0.106s |
This is literally 3 lines of Python code, on 384 dim embeddings, running on my MBP.
scores = self.doc_vectors @ query_vector.astype(np.float32, copy=False)
ranked_indexes = np.argpartition(scores, -top_k)[-top_k:]
scores = scores[ranked_indexes]
ranked_indexes = ranked_indexes[np.argsort(-scores, kind="stable")]
scores = scores[np.argsort(-scores, kind="stable")]
I work with a lot of teams that don’t need the complexity of a vector database. They have ~1m documents to search. They have low query traffic, and write their embeddings all up front. They don’t need to buy a multi-million dollar vector database, or spend 6 months learning to operate it.
For low enough n, just brute force the embeddings until you can’t bear to. As fellow search traveler Jo Kristian Bergum says “an exhaustive search may be all you need”.
As a footnote, this is just naive numpy operations, it could probably be faster. As Andreas Erickson says, throughput can be improved here by giving threads more than one query during the scan). And we could be doing a lot more during the search to collect into a top-n heap than what numpy does.
Upcoming course: Build your own vector database
Want to understand what makes embedding retrieval fast, relevant, and useful in real AI systems? Join Build your own vector database and build the core pieces yourself, from embeddings and indexing to search and retrieval.