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 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 database vectors and a query , find the indices with the smallest squared Euclidean distance
Scanning all vectors for every query (brute force) costs 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:
nlist clusters. Each cluster has a centroid and an
inverted list holding the vectors closest to that
centroid.nprobe
nearest centroids, then compute the distance only to the vectors in
those nprobe lists, and keep the
best.With nlist = 1024 and nprobe = 16, a query
would scan
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 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 dimensions (default , , 10,000 queries, similar in size to the standard SIFT1M benchmark).
The code is C++17, uses only the standard library, and is serial:
ivf.h: the API (data generation, k-means, index build,
search, recall), with commentsivf.cc: the implementation of the algorithmmain.cc: command-line options, timing and outputrun.sh: builds and runs the program on MiyabiAll vectors are stored in flat float arrays (vector
i is X[i*d .. i*d+d)).
nblob random centers
in
;
each vector is a random center plus Gaussian noise with standard
deviation sigma (default 0.25) in every dimension. Queries
are generated the same way. A larger sigma makes the
clusters overlap, so the search gets harder.train_kmeans): Lloyd’s
algorithm on a training sample of ntrain vectors, for
iters iterations:
nlist centroids and pick the nearest;build_lists):
every one of the
vectors is assigned to its nearest centroid. The vectors are then copied
so that each list is stored contiguously (a CSR-like layout: list
c is offsets[c] .. offsets[c+1]).search), for each query:
nlist centroids and keep
the nprobe smallest;TopK).brute_force): the exact
top-
for the first ngt queries, used to compute recall@k.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
One Grace (Neoverse-V2) core, clang++ -O3, default
parameters
(,
,
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 vectors) | 55.6 s |
| search (10,000 queries) | 28.3 s (353 queries/s) |
| main computation in total | 111.4 s |
What may limit the speedup: