Vector Databases and Approximate Nearest Neighbour Search

Semantic search, RAG, recommendation, deduplication and image search all reduce to one operation: given a query vector, find the most similar vectors among millions or billions. Doing this exactly is slow at scale. Approximate nearest neighbour (ANN) algorithms and vector databases make it fast, trading a small amount of accuracy for orders-of-magnitude speed. Understanding how they work helps you tune them and choose among many products.

Similarity measures#

• Cosine similarity — direction only; standard for text embeddings.
• Inner (dot) product — equals cosine for normalised vectors; used for many retrieval models.
• Euclidean (L2) distance — for normalised vectors, ranking by L2 equals ranking by cosine.

Always use the metric the embedding model was trained for, and normalise when appropriate.

Exact (brute-force) search#

Compute the similarity to every vector: $O(Nd)$ per query. With $N = 10^6$ and $d = 768$, that is about 770 million multiply–adds per query — feasible on a GPU or for small collections, and it gives exact results. For many applications with up to a few hundred thousand vectors, brute force (e.g. a NumPy matrix product or FAISS IndexFlatIP) is perfectly adequate and simplest.

Graph-based ANN: HNSW#

Hierarchical Navigable Small World graphs (Malkov & Yashunin, 2016) are the most popular ANN method:

• Each vector is a node connected to some of its near neighbours.
• Nodes are assigned to layers probabilistically; upper layers are sparse "express highways", the bottom layer contains all nodes.
• Search starts at the top layer, greedily moves to the neighbour closest to the query, drops down a layer, and repeats, finishing with a more thorough local search at the bottom.

Key parameters:

• M — neighbours per node (graph density; memory and recall).
• ef_construction — search breadth when building (build time vs quality).
• ef_search — search breadth at query time (latency vs recall — tune this).

HNSW gives excellent recall at low latency but uses considerable memory and is slower to build.

Clustering-based ANN: IVF#

Inverted File indexes cluster vectors with k-means into nlist cells. At query time, only the nprobe nearest cells are searched. Increasing nprobe raises recall and latency. IVF builds quickly and scales well, and combines naturally with compression.

Compression: product quantisation (PQ)#

Product quantisation (Jégou et al., 2011) splits each vector into $m$ sub-vectors and replaces each sub-vector with the index of its nearest centroid in a small codebook (e.g. 256 centroids → 1 byte). A 768-dimensional float32 vector (3,072 bytes) can be compressed to, say, 96 bytes. Distances are approximated with precomputed lookup tables. IVF-PQ combines both ideas to search billions of vectors in limited memory. Scalar and binary quantisation are simpler alternatives.

# pip install faiss-cpu
import numpy as np, faiss, time

rng = np.random.default_rng(0)
d, N = 384, 200_000
X = rng.normal(size=(N, d)).astype("float32"); faiss.normalize_L2(X)
Q = rng.normal(size=(100, d)).astype("float32"); faiss.normalize_L2(Q)

flat = faiss.IndexFlatIP(d); flat.add(X)
_, gt = flat.search(Q, 10)                                     # exact ground truth

hnsw = faiss.IndexHNSWFlat(d, 32, faiss.METRIC_INNER_PRODUCT)
hnsw.hnsw.efConstruction = 100; hnsw.add(X)
for ef in [16, 64, 256]:
    hnsw.hnsw.efSearch = ef
    t = time.time(); _, I = hnsw.search(Q, 10); ms = (time.time() - t) * 1000 / len(Q)
    recall = np.mean([len(set(I[i]) & set(gt[i])) / 10 for i in range(len(Q))])
    print(f"HNSW efSearch={ef:>3}: recall@10={recall:.3f}, {ms:.2f} ms/query")

(Random vectors are a hard case for ANN; real embeddings, which have structure, usually achieve high recall more easily.)

What a vector database adds#

A plain index library (FAISS, hnswlib, ScaNN) searches vectors. A vector database adds operational features:

• CRUD operations — insert, update and delete vectors as documents change;
• metadata filtering ("only documents in Bangla, published after 2024, that this user may access");
• hybrid (keyword + vector) search;
• persistence, replication, backups, sharding for scale;
• access control and multi-tenancy.

Options include dedicated systems (e.g. Milvus, Qdrant, Weaviate, Pinecone), search engines with vector support (Elasticsearch, OpenSearch) and extensions to general databases (pgvector for PostgreSQL). For many projects, adding vectors to a database you already operate is the simplest and most maintainable choice.

Filtering pitfalls#

Combining ANN with filters is tricky: post-filtering (search then filter) can return too few results if the filter is selective; pre-filtering (filter then search) can break graph navigation. Good systems integrate filtering into the search; test recall with your real filters.

Choosing and operating#

Operational tips:

• Measure recall@k against exact search on a sample of real queries; tune ef_search/nprobe to your latency budget.
• Re-embed everything when you change embedding models — vectors from different models are incompatible. Store the model name and version with each vector.
• Monitor index size, latency percentiles and recall drift as data grows.