AI Engineering & LLMs (50 Qs)•Part 1: RAG Architecture, Chunking & Vector Search
Vector Database Indexing Internals: HNSW vs. IVF-PQ Trade-Offs
1. Approximate Nearest Neighbor (ANN) vs. Exact Search
Exact k-Nearest Neighbors ($k$-NN) computes distance against every vector in the database, yielding $O(N \cdot D)$ complexity. For millions of vectors, exact search introduces hundreds of milliseconds of latency. Production vector databases use Approximate Nearest Neighbor (ANN) indexing:
scss
┌───────────────────────────────────────────┐
│ ANN Indexing Architectural Trade │
└─────────────────────┬─────────────────────┘
│
┌────────────────────────┴────────────────────────┐
▼ ▼
┌─────────────────────────┐ ┌─────────────────────────┐
│ HNSW │ │ IVF-PQ │
│ Hierarchical Navigable │ │ Inverted File with │
│ Small World │ │ Product Quantization │
└────────────┬────────────┘ └────────────┬────────────┘
│ │
• Multi-layer graph skip-list • Voronoi cluster partitions
• Top-tier recall (95–99%) • 80–90% RAM reduction (compression)
• Heavy RAM memory usage • Lower recall, higher build time
2. Comprehensive Index Comparison
| Feature | Flat (Exact k-NN) | HNSW (Hierarchical Graph) | IVF-PQ (Quantized Inverted File) |
|---|---|---|---|
| Search Complexity | $O(N)$ | $O(\log N)$ | $O(\text{nprobe} \cdot \frac{N}{K})$ |
| Recall / Accuracy | 100% (Ground Truth) | 95% – 99% (State-of-the-art) | 80% – 92% |
| Query Latency | Very High (100–1000ms) | Ultra Low (< 5ms) | Low (< 15ms) |
| RAM Consumption | High (raw vectors) | Very High (raw vectors + graph edges) | Extremely Low (8x to 32x compressed) |
| Index Build Speed | Instant (no index) | Slow ($O(N \log N)$ graph construction) | Medium (K-Means training + centroid assignment) |
| Dynamic Updates | Instant | Supported (node insertions) | Expensive (requires periodic retraining of centroids) |
3. Production Recommendation Rule
- Choose HNSW for systems with < 10 million vectors where recall accuracy and sub-10ms query latency are paramount and RAM budget is flexible.
- Choose IVF-PQ for large-scale enterprise deployments (> 50 million vectors) where fitting the entire vector index into server RAM without exceeding cloud infrastructure budgets is the primary constraint.