"How does vector search work, and why is it fast at scale?"
Vector search sits underneath every RAG system, every semantic search, every recommendation pipeline. Interviewers use this question to check you understand ANN algorithms — most candidates say "cosine similarity" and stop there, which isn't an architecture.
Start with embeddings: a text (or image, audio) is mapped by a model to a fixed-dimensional vector, typically 384 to 3072 dimensions. Similar content gets similar vectors, measured by cosine similarity or dot product.
Naive search is O(N×D): compute similarity between the query vector and every stored vector. For millions of vectors this is too slow for interactive queries.
ANN (Approximate Nearest Neighbor) is the scaling answer. Trade a tiny amount of recall for massive speedup — instead of exact top-k, return top-k that are "almost certainly correct".
HNSW (Hierarchical Navigable Small World): builds a multi-layer graph where each node connects to nearby neighbors. Search starts at the top sparse layer, greedily walks toward the query, drops to denser layers. Log-ish query time, memory-heavy. Default in most modern vector DBs.
IVF (Inverted File): clusters vectors into K cells using k-means. Query probes only the nprobe nearest cells. Less memory, slightly lower recall, common in FAISS. Often combined with PQ (Product Quantization) to compress vectors 8-32x for billions-scale indexes.
Vector search is how semantic retrieval scales past a few thousand items. An embedding model maps text (or images, audio) into a fixed-dimensional vector — typically 384 for a small model like MiniLM, 1024 for bge-large, up to 3072 for OpenAI text-embedding-3-large. Similar inputs produce vectors close in this space, and "closeness" is usually cosine similarity (angular distance) or dot product. A naive search computes similarity between the query vector and every stored vector — O(N×D). With a million vectors at 768 dimensions that's a billion multiplications per query; too slow for interactive RAG. Approximate Nearest Neighbor algorithms are the practical answer — they give up a small amount of recall (maybe 99% vs. exact 100%) for orders of magnitude speedup. Two dominant algorithms. HNSW builds a hierarchical graph: each node connects to its nearest neighbors, and upper layers are sparser shortcuts. A search starts at an entry point in the top layer, greedily walks toward nodes more similar to the query, drops to the next layer, repeats. Query is roughly logarithmic and achieves high recall, at the cost of significant memory per vector (several edges stored per node). HNSW is the default in Qdrant, Milvus, Weaviate, and pgvector 0.5+. IVF clusters the dataset into K partitions via k-means. At query time, you compute which nprobe cells are nearest the query and only search within those cells. IVF uses less memory than HNSW but has lower recall unless you probe many cells (which slows it down). FAISS's default for very large indexes. IVF is often combined with Product Quantization — vectors are chopped into sub-vectors and each sub-vector is replaced by the nearest centroid from a learned codebook, compressing a 768-dim float32 vector from 3KB to around 96 bytes at ~95% recall. That's what makes billion-scale indexes feasible in RAM. Practical choice: for up to tens of millions of vectors, HNSW is usually the best speed-recall-memory point. For hundreds of millions to billions, IVF + PQ is where you end up. Every real vector DB exposes parameters — ef_construction, ef_search, M for HNSW; nlist, nprobe for IVF — tuning these is the difference between good and great search quality.
Saying "HNSW" and "IVF" by name is the fastest way to signal real experience.
Mentioning Product Quantization for billion-scale shows you understand the memory / recall tradeoff at enterprise scale.
Know which algorithm your vector DB uses by default — Qdrant/Milvus/pgvector all default to HNSW.
If you blank on algorithm names during the interview, HireMe AI can surface HNSW, IVF, PQ immediately.
For normalized embeddings (unit length), cosine and dot product are equivalent. Most embedding models output near-unit vectors, so dot product is fastest and commonly used. Euclidean is rarely used for text embeddings.
Memory — it stores many edges per vector, so RAM footprint can be 4-8x the raw vector size. For extremely large corpora, IVF+PQ is more memory-efficient.
HNSW supports efficient inserts but not great for heavy delete workloads (tombstones accumulate and quality degrades). Periodic reindexing is common.
HireMe AI listens to your interview in real-time, detects questions, and generates instant answer suggestions — so you never freeze up again.
Try HireMe AI Free