Build a vector similarity search engine from scratch.

What you need to know

Brute-force (exact) search compares the query with every stored vector. It is always correct, and with NumPy it is fast up to roughly a million vectors. Know the memory number cold:

memory = n × d × 4 bytes   (float32)1,000,000 × 768 × 4 = 3.07 GB

Top-k without a full sort. np.argpartition(-scores, k - 1) rearranges indices so the k largest scores are in the first k slots, in no particular order. That is O(n). Sorting those k afterwards is O(k log k).

Approximate nearest neighbour (ANN) indexes skip most of the vectors:

• IVF (inverted file): cluster the vectors with k-means into, say, 1,000 cells. At query time, search only the few cells whose centres are nearest the query.
• HNSW (hierarchical navigable small world): a layered graph where each vector links to its close neighbours. A search greedily walks the graph, taking roughly O(log n) hops.

Both give up a little recall (sometimes a true top-k vector is missed) for speed. FAISS, Qdrant, Milvus and pgvector all implement one or both.

1import numpy as np23class VectorIndex:4    """Exact cosine search over unit-normalised float32 vectors."""56    def __init__(self, dim: int) -> None:7        self.dim = dim8        self.vectors = np.zeros((0, dim), dtype=np.float32)9        self.ids: list[str] = []1011    def add(self, ids: list[str], vecs) -> None:12        v = np.atleast_2d(np.asarray(vecs, dtype=np.float32))13        if v.ndim != 2 or v.shape[1] != self.dim:14            raise ValueError(f"expected vectors of dim {self.dim}, got shape {v.shape}")15        if len(ids) != v.shape[0]:16            raise ValueError("ids and vectors must be the same length")17        v = v / (np.linalg.norm(v, axis=1, keepdims=True) + 1e-10)18        self.vectors = np.vstack([self.vectors, v])19        self.ids.extend(ids)2021    def search(self, query, k: int = 5) -> list[tuple[str, float]]:22        if not self.ids or k <= 0:23            return []24        q = np.asarray(query, dtype=np.float32).ravel()25        if q.shape[0] != self.dim:26            raise ValueError("query has the wrong dimension")27        scores = self.vectors @ (q / (np.linalg.norm(q) + 1e-10))28        k = min(k, len(self.ids))29        top = np.argpartition(-scores, k - 1)[:k]           # O(n): k best, unordered30        top = top[np.argsort(-scores[top], kind="stable")]  # O(k log k): order them31        return [(self.ids[i], float(scores[i])) for i in top]3233    def delete(self, doc_id: str) -> None:34        i = self.ids.index(doc_id)                          # ValueError if absent35        self.vectors = np.delete(self.vectors, i, axis=0)36        self.ids.pop(i)

The tricky parts:

• Check the shape explicitly. The tempting reshape(-1, dim) silently turns one 4-dimension vector into two 2-dimension vectors; with two ids passed in, the length check even passes. Checking v.shape[1] == self.dim catches it.
• k - 1 in argpartition is the position of the k-th largest element (0-based). Clamping k to n first avoids an out-of-range error.
• np.vstack on every add copies the whole matrix, O(n) per insert. Fine for a demo; a real engine preallocates and doubles capacity, or batches inserts.

Complexity: add is O(n·d) because of the copy; search is O(n·d) + O(n) + O(k log k); delete is O(n·d). Memory is O(n·d).

A real-life example

1index = VectorIndex(dim=2)2index.add(["cricket", "football", "recipe"], [[0.9, 0.1], [0.8, 0.3], [0.0, 1.0]])3print(index.search([1.0, 0.0], k=2))4# [('cricket', 0.9938837289810181), ('football', 0.936329185962677)]5index.delete("cricket")6print(index.search([1.0, 0.0], k=5))7# [('football', 0.936329185962677), ('recipe', 0.0)]

Step by step for the first search:

argpartition with k = 2 puts the indices of 0.994 and 0.936 in the first two slots (in either order); the small argsort orders them. After the delete, asking for k = 5 is clamped to the 2 vectors left.

A sports app's "more like this article" feature is exactly this: one vector per article, top 5 by cosine.

Follow-up questions to expect

• "How do you make delete cheap?" — Mark a tombstone (a boolean mask) instead of copying the matrix, skip masked rows at search time, and compact in the background. HNSW indexes do the same.
• "How would you verify an ANN index?" — Run the exact index as a reference on a sample of queries and measure recall@10 of the ANN results against it. Tune the ANN parameters (ef_search, nprobe) until recall is acceptable.
• "How do you cut memory?" — Store float16 (half the memory), or use product quantisation, which compresses each vector to a few dozen bytes at some accuracy cost.