Careeroza
ANN and HNSW Intuition
Why Not Compare with Everything?
Brute force (exact) search compares the query with every vector. With 10 million product vectors of 1024 dimensions that is 10 billion multiplications per query: too slow. Approximate nearest neighbour (ANN) indexes look at only a small part of the data and return almost the same results, much faster.
| Index | Idea | Used by |
|---|---|---|
| HNSW | A multi-layer graph: each vector links to its near neighbours. Search starts at the top (few long links) and walks greedily towards the query, layer by layer. | pgvector, Qdrant, Chroma, Weaviate, Pinecone |
| IVF | Group vectors into clusters; search only the few clusters closest to the query. | FAISS, pgvector (ivfflat), Milvus |
| PQ (product quantization) | Compress vectors to save memory, compare compressed codes. | FAISS, Milvus |
IVF-style Search vs Brute Force
Example
Cluster 2,000 random vectors into 20 buckets around "centroids", then search only the 3 closest buckets. We count comparisons and check how many of the true top-5 we still find (recall):
import math, random
rng = random.Random(42)
DIM, N = 8, 2000
def norm(v):
n = math.sqrt(sum(x * x for x in v)); return [x / n for x in v]
def dot(a, b): return sum(x * y for x, y in zip(a, b))
vectors = [norm([rng.gauss(0, 1) for _ in range(DIM)]) for _ in range(N)]
centroids = [vectors[i] for i in range(0, N, N // 20)] # 20 simple centroids
buckets = {c: [] for c in range(len(centroids))}
for i, v in enumerate(vectors):
buckets[max(range(len(centroids)), key=lambda c: dot(v, centroids[c]))].append(i)
query = norm([rng.gauss(0, 1) for _ in range(DIM)])
exact = sorted(range(N), key=lambda i: -dot(query, vectors[i]))[:5]
probe = sorted(range(len(centroids)), key=lambda c: -dot(query, centroids[c]))[:3]
candidates = [i for c in probe for i in buckets[c]]
approx = sorted(candidates, key=lambda i: -dot(query, vectors[i]))[:5]
print("brute force comparisons:", N)
print("IVF comparisons: ", len(centroids) + len(candidates))
print("recall@5: ", len(set(exact) & set(approx)) / 5)Output
brute force comparisons: 2000 IVF comparisons: 282 recall@5: 1.0
Tip: ANN indexes have knobs that trade speed for recall: ef_search / m for HNSW, nprobe / lists for IVF. Under ~100k vectors, exact search is often fast enough.