The data structure that makes billion-scale vector search feasible is called HNSW — Hierarchical Navigable Small World. Understanding it takes away the magic from your vector database and gives you the levers to tune it correctly.
A Small-World graph is a network where most nodes can be reached from any other node in a small number of hops — like six degrees of separation in social networks. HNSW builds such a graph over your vectors, then uses it to “navigate” towards the nearest neighbor at search time.
The “Hierarchical” part means the graph is built in multiple layers. The top layer is sparse — it allows the algorithm to make large jumps across the vector space. Lower layers are denser and allow fine-grained local search. At query time, the algorithm starts at the top layer, drops down, and progressively zooms in to find the nearest neighbors.
| Property | Flat (Exact) | HNSW (ANN) |
|---|---|---|
| Recall | 100% | ~95–99% |
| Query latency (1M vecs) | ~1–10s | ~1–10ms |
| Build time | O(n) | O(n log n) |
| Memory overhead | Low | Medium (graph structure) |
| Supports updates | ✅ | ✅ (slower) |
| Best for | <50K vectors | >50K vectors |
M — Number of bi-directional links per node (default: 16)
Controls graph connectivity. Higher M = better recall, higher memory, slower index build. Typical range: 8–64.
ef_construction — Search width during index build (default: 200)
Higher values = better index quality, slower build time. Does not affect query speed. Typical range: 100–500.
ef_search (or ef) — Search width at query time
Higher values = better recall, slower queries. This is the query-time knob for tuning the speed/recall trade-off without rebuilding the index.
Select your deployment size to see the right index configuration:
Production app. Tune HNSW for your recall/speed target.
import chromadb
client = chromadb.PersistentClient(path="./db")
collection = client.get_or_create_collection(
name="high_recall_docs",
metadata={
"hnsw:space": "cosine",
"hnsw:M": 32, # More connections → better recall (default: 16)
"hnsw:construction_ef": 400, # Thorough index build (default: 200)
"hnsw:search_ef": 100, # Query-time recall tuning (default: 10)
},
)
# M=32 + ef_construction=400: ~97% recall, 2× memory vs default
# Tune ef_search at query time without rebuilding the indexHNSW is the dominant algorithm for general use, but others are optimized for specific workloads:
Partitions vectors into clusters (cells). At query time, only searches the k nearest cells. Much lower memory than HNSW, but less accurate without tuning. Used heavily in Faiss.
Use when: Very large collections (>100M) where memory is the constraint
Compresses vectors by encoding them as products of smaller codebooks — achieves 8–64× memory reduction at the cost of recall. The key algorithm behind billion-scale search.
Use when: Web-scale retrieval where you need to fit 1B vectors in RAM
State-of-the-art recall-performance balance. Uses asymmetric hashing and anisotropic quantization. Powers Google Search and Vertex AI Vector Search.
Use when: When you need the best performance and are on GCP
| Database | Best For | Key Trait |
|---|---|---|
| ChromaDB | Prototypes, <1M vectors | Zero-config, in-process |
| pgvector | Already using Postgres, <10M | No new infrastructure |
| Pinecone | Production SaaS, any scale | Managed, serverless |
| Weaviate | Multi-modal, graph queries | Hybrid search built-in |
| Qdrant | High performance, self-hosted | Best OSS throughput |
| Milvus | >100M vectors, enterprise | Horizontal scaling |
< 100K vectors → ChromaDB (in-process) < 5M vectors → pgvector (if already on Postgres) < 100M vectors → Pinecone or Qdrant (managed / self-hosted) > 100M vectors → Milvus or Weaviate (distributed)
In Lesson 7, we wire everything together — embedding model + ChromaDB + a retrieval function — into a complete semantic search pipeline ready to power any RAG system.