Build Your Own Vector DB — From Brute Force to HNSW

Assemble a vector search engine step by step, starting from a 20-line brute-force scan. The curse of dimensionality, IVF partitioning, HNSW graph traversal and quantization, all viewed through one lens: the trade between recall and speed.

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

Check Every Shelf, or Give Up Cleverly

You are in a library of a million books, and someone hands you one and asks for five that are similar. There is exactly one way to be certain: walk every aisle, pick up every book, judge it. The answer is guaranteed correct, and a single question takes hours.

Real libraries do something else. You go to the right genre, narrow to a shelf, and look at a handful of books. It is fast — and it can miss the single most similar book in the building, because that book happened to sit on the other side of a genre boundary.

A vector database does the second thing. It gives up on "guaranteed correct" and buys orders of magnitude in speed. The name for that bargain is approximate nearest neighbor search (ANN).

This article stops treating that machinery as a black box. We start with a twenty-line brute-force scan, watch it break, and then build the two escape routes — IVF and HNSW — by hand. The wider picture lives in RAG Fundamentals and Design Patterns; here we drill into retrieval alone.

What Does "Close" Mean?

One premise. An embedding model turns text or images into arrays of a few hundred to a few thousand numbers (vectors), trained so that similar meanings point in similar directions — see Embeddings from Scratch.

So how do we measure "close"? Three metrics cover almost all practice.

Equation (1), left to right: multiply matching components and add them up (inner product); divide that by the lengths so only direction matters (cosine); the straight-line distance between two points (L2). Note the sign flip — bigger is closer for the first two, smaller is closer for L2.

Said in words, all three are the same notion of closeness read off different rulers. $q$ is the query vector, $x$ a document vector, $q_i$ and $x_i$ their $i$-th components, and $\|\cdot\|$ the length of a vector. The inner product folds "do these point the same way?" and "how long are they?" into one score; cosine throws the lengths away and scores direction alone; L2 is what you get by laying a ruler between the two points.

There is a property here that matters enormously in code. If you normalize every vector to length 1, all three produce the same ranking. With unit length the denominator becomes 1, so cosine is the inner product, and furthermore

Equation (2) says that once vectors are normalized, squared L2 distance is just the inner product turned upside down. Larger inner product means smaller L2, so the ordering is identical.

Put in words: with every vector at length 1, "this one is nearby" and "this one has a big inner product" are two phrasings of a single fact. The $2$ left on the right-hand side is the same constant for every vector and so cannot move anything up or down the ranking — the entire ordering is decided by $q \cdot x$ and nothing else.

Spend that one line up front and you can change your index's distance setting later without the results flipping on you. Skip it, and searching by inner product simply promotes long vectors. Documents win for being large, not for being relevant.

Start With a Brute-Force Scan

You do not need to write HNSW first. The starting point of a vector database is twenty lines of numpy.

import numpy as np

class FlatIndex:
    def __init__(self, dim):
        self.vecs = np.empty((0, dim), dtype=np.float32)
        self.ids  = []

    def add(self, vecs, ids):
        v = np.asarray(vecs, dtype=np.float32)
        v /= np.linalg.norm(v, axis=1, keepdims=True)   # normalize to unit length
        self.vecs = np.vstack([self.vecs, v])
        self.ids += list(ids)

    def search(self, q, k=5):
        q = np.asarray(q, dtype=np.float32)
        q /= np.linalg.norm(q)
        scores = self.vecs @ q                          # every dot product at once
        top = np.argpartition(-scores, k)[:k]           # partial select of top-k
        top = top[np.argsort(-scores[top])]             # sort only those k
        return [(self.ids[i], float(scores[i])) for i in top]

The small trick is argpartition. Sorting everything costs $O(N \log N)$, but merely splitting into "top k" and "the rest" costs $O(N)$.

More importantly, whatever FlatIndex returns is correct. It is not an approximation. Every ANN structure we build from here gets graded against these results.

When Brute Force Falls Over

A back-of-the-envelope estimate. Embed a million documents in 768 dimensions and a single query costs $10^6 \times 768 \approx 7.7 \times 10^8$ multiply-adds, with $10^6 \times 768 \times 4$ bytes ≈ 3 GB of float32 to hold. One query lands in the hundreds of milliseconds; a hundred queries per second falls apart. At ten million documents the memory reaches 30 GB and no longer fits on one machine.

The nasty part is that this growth is linear. It is not dramatic like an exponential, so you keep adding data thinking you still have headroom, and then one day you blow through your latency budget.

The Bargain — Recall as the Yardstick

So we give up on "always correct." But unless we can measure how much we gave up, we just have broken search. The yardstick is recall@k.

In equation (3), $G_k$ is the true top-k from the brute-force scan, $R_k$ is the k results the approximate method returned, and $|\cdot|$ counts set members. In words: of the true top-k, what fraction did we manage not to lose? A recall@10 of 0.9 means nine of the correct ten came back.

Read as a sentence, the formula is a grading sheet — one which says how much of the right answer survived. $R_k \cap G_k$ is the set of items that appear in both the approximate answer and the true answer, its size is your score, and $k$ is full marks. It is the same arithmetic as marking a ten-question quiz: nine right out of ten is 0.9.

Here is the point beginners miss: ANN performance is not a single number. Turn one knob and you get slower but more accurate; turn it the other way and you get faster but lossier. The only honest comparison is a point on a curve — "at recall@10 = 0.95, how many queries per second?" A claim of "fast" alone is hiding one of the two axes.