Vector Search and ANN Indexes
Vector search for RAG: brute-force vs ANN (HNSW, IVF), the recall/latency trade-off and typical AI interview questions.
Intuition
Once texts are turned into embeddings, “find similar by meaning” = “find the nearest points in a high-dimensional space”. Closeness is measured three ways: cosine similarity (the angle between vectors), the dot product and Euclidean distance. They sound like three different worlds, but if the vectors are normalized to unit length, all three metrics order neighbors almost the same way — so the “cosine or Euclidean” debate on normalized embeddings is nearly moot.
Exact search — compare the query with each of N vectors of dimension d:
For 10 thousand vectors — instant. For 100 million at d = 1024 — already hundreds of billions of operations per query. Does not scale.
How it works: ANN
ANN (Approximate Nearest Neighbors) is a deliberate trade: we search not for guaranteed nearest neighbors, but for “almost certainly nearest” ones, orders of magnitude faster. Index quality is measured by recall@k — what fraction of the true top-k neighbors was found. Recall 0.95 means: on average 19 of 20 true neighbors are present.
- HNSW (Hierarchical Navigable Small World) — a multilayer graph. Intuition: upper layers are sparse “highways” for long jumps across the space; lower ones are dense “streets” for fine tuning. Search greedily descends from top to bottom: we quickly land in the right neighborhood, then carefully find the house. Fast and accurate, but the graph eats a lot of memory.
- IVF (Inverted File index) — the base is pre-split into cells around centroids (clustering, hello k-means). At query time we search only in the nprobe nearest cells. More probes — higher recall, but more points scanned.
- PQ (Product Quantization) — vector compression: a long vector is cut into parts, each encoded by the index of the nearest prototype from a small codebook. Memory drops by tens of times, accuracy suffers a little; often combined with IVF (IVF-PQ).
A separate pain is metadata filters (“search only among department X documents”). Naively: find top-k, then filter — but the filter can knock out almost everyone, leaving two results out of k. So mature engines support filtering inside the index walk (filter-aware search).
What to choose in practice
Choosing an engine is a question of scale and stack, not fashion:
- Up to ~1M vectors and you already have Postgres — pgvector: one database, transactions, familiar backups. A separate vector DB is not required.
- An in-process library — FAISS / hnswlib: maximum control and speed, but persistence, replication and filters are your problem.
- A dedicated service — Qdrant, Milvus, Weaviate and the like: when you need scale, filter-aware search and live updates.
A typical design mistake is dragging a dedicated vector DB into a 50-thousand-document project “for growth”: the operational complexity is real today, and the scale may never arrive.
- “Cosine or Euclidean?” — on normalized vectors the ranking nearly coincides; what matters more is which metric the embedding model was trained with and the index was built with.
- “Explain HNSW in plain words” — a multilayer graph: “highways” on top for long jumps, “streets” below for fine tuning; greedy descent through the layers.
- “What do you tweak in IVF if recall is low?” — raise nprobe (slower, more complete) or the number/quality of centroids; check queries near cell borders.
- “How does ANN coexist with metadata filters?” — post-filtering can leave fewer than k results; you need an engine with filtering inside the index walk.
All interview questions in this section: RAG: Retrieval + Generation — interview questions