Vector databases — HNSW, IVF, ScaNN
The similarity-search index behind every RAG system in 2025.
You have a billion documents, each embedded as a 1536-dimensional vector. A user query arrives; you must find the top-10 most similar vectors in under 100ms. A brute-force scan takes minutes. The answer is an approximate nearest neighbor (ANN) index — the algorithm every vector database is built around.
Interactive latency calculator
How brute-force works
Compute cosine similarity (or L2 distance) between the query vector and every stored vector. Return top-K. Trivially parallelizable on GPU with matrix multiplication.
- Query complexity: O(N × D) — linear in corpus size.
- Recall: 100% — this is the ground truth.
- Use case: corpora up to ~100K vectors, or GPU-backed at 1M-10M, or as evaluation baseline for ANN algorithms.
- Reference impl:
FAISS IndexFlatIPornumpy @ operator.
The 2025 vector DB landscape
| Database | Primary algo | Best for | Notes |
|---|---|---|---|
| Pinecone | Proprietary (HNSW-based) | Managed cloud | Serverless, per-query pricing, easiest to start |
| Qdrant | HNSW | Self-host + filtering | Excellent metadata filtering, Rust core |
| Weaviate | HNSW | Hybrid retrieval | Built-in BM25 + reranking |
| Milvus | HNSW / IVF / DiskANN | Large scale (100M+) | GPU support, tunable per collection |
| pgvector | IVFFlat / HNSW | Postgres integration | You already have Postgres? Start here. |
| FAISS | All above + more | Research + on-prem | Library only, not a service. Backs many others. |
| Vespa | HNSW + ANN | Multi-stage retrieval | Yahoo internal → open source, full search stack |
| Chroma | HNSW | Prototyping | Simplest API, small corpora |
The senior insight — recall vs latency is a knob, not a fixed number
Every ANN algorithm has a tuning parameter (nprobe for IVF, ef for HNSW). Higher value = more candidates checked = higher recall = more latency. In production you tune this per QUERY class — high-value queries get higher recall, cheap queries get lower. This is why RAG systems often surface a “quality mode” toggle.
Applied in these systems
References
- Malkov, Yu. A. and Yashunin, D. A. (2018) — “Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.” The HNSW paper.
- Jégou, H. et al. (2011) — “Product quantization for nearest neighbor search.” Foundational IVF paper.
- Guo, R. et al. (2020) — “Accelerating large-scale inference with anisotropic vector quantization.” ScaNN paper from Google.
- ANN Benchmarks: ann-benchmarks.com — reproducible latency/recall comparison of every algorithm on standard datasets.
Practice what you just read
Every foundation concept has a companion quiz to close the loop.