Storing and finding vectors efficiently

Finding the nearest vectors to a query is simple if you have a thousand vectors: compare with all of them.

With ten million vectors at 768 dimensions that becomes 7.7 billion multiplications per query. It works, but not a hundred times a second.

Approximate indexes trade exactness for speed. They usually find the right neighbours, sometimes not, and do it a thousand times faster.

The index	The idea	Good at
Flat	compare with all	exact, small collections
IVF	split into clusters, search the nearest	large collections, adjustable
HNSW	a navigable graph of neighbours	low latency, high recall
PQ	compress the vectors	a memory limit

The measure that counts is called recall@k: of the $k$ true nearest neighbours, how many did the index find? 0.95 means that one in twenty is missed — which in a RAG system is usually entirely acceptable, since several documents are fetched anyway.

HNSW (hierarchical navigable small world) builds a layered neighbourhood network. The top layer has few nodes with long hops; the bottom has all the nodes with short hops. The search starts at the top, walks greedily towards the query, and goes down one layer at a time.

It is the same idea as a skip list: long hops first, then fine adjustment.

The parameter	Means	The effect
M	neighbours per node	higher → better recall, more memory
efConstruction	the search width when building	higher → a better index, a longer build time
efSearch	the search width at query time	adjusted in operation: higher → better recall, higher latency

The last is the most important in practice: it lets you move along the recall/latency curve without rebuilding the index.

IVF clusters the vectors (k-means) and searches only the nprobe nearest clusters. Simple, memory-thrifty and easy to understand — but the recall falls at cluster boundaries, since a neighbour can lie just on the other side.

Product quantisation (PQ) splits the vector into parts and replaces every part with the nearest codebook entry. A 768-dimensional float32 vector of 3 072 bytes becomes 96 bytes — 32× smaller. The cost is precision, and PQ is therefore nearly always combined with a rerank: fetch 10× more candidates with PQ, compute the exact distances on them.

The distance measure has to match the embedding model:

The measure	Used when
Cosine	text embeddings (nearly always)
The inner product	when the vectors are normalised — the same as cosine
Euclidean	image and audio embeddings sometimes

Using the Euclidean distance on unnormalised text embeddings is a common and hard-to-detect error: it works «almost», and the recall is lower without anything breaking.

Always measure recall against an exact search on a selection of queries before you trust an index. It is half an hour's work and the only way of knowing where on the curve you are.

import numpy as np, time

rng = np.random.default_rng(0)
N, D = 200_000, 128
X = rng.normal(size=(N, D)).astype("float32")
X /= np.linalg.norm(X, axis=1, keepdims=True)      # normalise → the inner product = cosine
queries = X[:100] + 0.1 * rng.normal(size=(100, D)).astype("float32")
queries /= np.linalg.norm(queries, axis=1, keepdims=True)

def exact(q, k=10):
    return np.argsort(-(X @ q))[:k]

t = time.perf_counter()
key = [exact(q) for q in queries]
print(f"exact: {(time.perf_counter() - t) / len(queries) * 1000:.1f} ms/query")

# IVF by hand: cluster, search only the nprobe nearest clusters
from collections import defaultdict

K = 256
centroids = X[rng.choice(N, K, replace=False)]
for _ in range(8):                                  # simple k-means
    belongs = np.argmax(X @ centroids.T, axis=1)
    for c in range(K):
        m = belongs == c
        if m.any():
            centroids[c] = X[m].mean(0)
    centroids /= np.linalg.norm(centroids, axis=1, keepdims=True)

lists = defaultdict(list)
for i, c in enumerate(np.argmax(X @ centroids.T, axis=1)):
    lists[int(c)].append(i)

def ivf_search(q, k=10, nprobe=8):
    nearest = np.argsort(-(centroids @ q))[:nprobe]
    candidates = np.array([i for c in nearest for i in lists[int(c)]])
    if len(candidates) == 0:
        return np.array([], dtype=int)
    scores = X[candidates] @ q
    return candidates[np.argsort(-scores)[:k]]

def recall(nprobe):
    hits = 0
    t0 = time.perf_counter()
    for q, f in zip(queries, key):
        hits += len(set(ivf_search(q, 10, nprobe)) & set(f))
    ms = (time.perf_counter() - t0) / len(queries) * 1000
    return round(hits / (10 * len(queries)), 3), round(ms, 2)

for nprobe in (1, 4, 16, 64, 256):
    r, ms = recall(nprobe)
    print(f"  nprobe={nprobe:>3}: recall@10 {r:.3f}  {ms:>6.2f} ms/query")
#  ↑ the curve between recall and latency — choose a point to suit the requirements, always measure yourself

The loop at the bottom is the most important thing in the whole node: recall and latency are a curve, not a value. Choosing nprobe or efSearch without having drawn that curve for your own data is guessing.