Making a Mini Vector Database (IVF Index) from Scratch

Problem

A vector database stores a large number of vectors (e.g., embeddings of text, images or audio produced by a neural network) and answers nearest-neighbor queries: given a query vector, return the kk stored vectors closest to it. This is the core of semantic search and of retrieval-augmented generation (RAG) for LLMs; systems such as FAISS and Milvus are built around it.

Formally, given NN database vectors x1,…,xN∈ℝdx_1, \dots, x_N \in \mathbb{R}^d and a query q∈ℝdq \in \mathbb{R}^d, find the kk indices ii with the smallest squared Euclidean distance

∥q−xi∥2=∑j=1d(qj−xij)2. \|q - x_i\|^2 = \sum_{j=1}^{d} (q_j - x_{ij})^2 .

Scanning all NN vectors for every query (brute force) costs O(Nd)O(Nd) per query, which is too slow for millions of vectors and many queries. Real systems therefore build an index and do approximate search: they look at only a small part of the data, and accept missing a few true neighbors.

This program implements the classic IVF (inverted file) index:

  1. Build: cluster the vectors with k-means into nlist clusters. Each cluster has a centroid and an inverted list holding the vectors closest to that centroid.
  2. Search: for a query, find the nprobe nearest centroids, then compute the distance only to the vectors in those nprobe lists, and keep the kk best.

With nlist = 1024 and nprobe = 16, a query would scan 16/1024≈1.6%16/1024 \approx 1.6\% of the data if all lists had the same length; in our runs it scans about 5% (see the results below), because the lists are uneven and queries tend to fall into the large ones. nprobe trades speed against accuracy.

How good is the answer? We measure recall@k: for some queries, we also compute the exact answer by brute force, and count what fraction of the true kk nearest neighbors the index returned (1.0 = perfect).

The input is synthetic, generated inside the program from a fixed seed: vectors are drawn from a mixture of Gaussian “blobs” in dd dimensions (default N=106N = 10^6, d=128d = 128, 10,000 queries, similar in size to the standard SIFT1M benchmark).

How the algorithm/baseline code works

The code is C++17, uses only the standard library, and is serial:

All vectors are stored in flat float arrays (vector i is X[i*d .. i*d+d)).

The main computation (k-means + list building + search) is timed with std::chrono. The program also reports queries/s and GFLOP/s.

The inner loop of every step is the same distance kernel:

float sum = 0;
for (j = 0; j < d; j++) { float diff = a[j] - b[j]; sum += diff * diff; }

Command line options: -n N -d D -q Q -l NLIST -p NPROBE -k K -t NTRAIN -i ITERS -g NGT -b NBLOB -r SIGMA -s SEED (-r is the noise around each blob: larger values make the clusters overlap and the search harder).

Example: ./ivf -n 1000000 -d 128 -q 10000 -l 1024 -p 16

Results of the baseline on Miyabi

One Grace (Neoverse-V2) core, clang++ -O3, default parameters (N=106N = 10^6, d=128d = 128, 10,000 queries, nlist = 1024, nprobe = 16, sigma = 0.25):

step time
k-means training (50,000 vectors, 10 iterations) 27.5 s
building the lists (assigning all 10610^6 vectors) 55.6 s
search (10,000 queries) 28.3 s (353 queries/s)
main computation in total 111.4 s

Where is parallelism

What may limit the speedup: