Approximate Nearest Neighbors (ANN)

The scale problem

# Exact search (brute force):
# - 1M embeddings: ~100ms
# - 10M embeddings: ~1s
# - 100M embeddings: ~10s ❌ Too slow

# Solution: Approximate Nearest Neighbors (ANN)
# Trade-off: Accuracy vs Speed
# - 99% accuracy, 100x speedup ✅

---

Main ANN algorithms

1. HNSW (Hierarchical Navigable Small World)

# Used by: Pinecone, Weaviate, Qdrant
# Accuracy: ~99%
# Speed: 100-1000x faster
# Memory: 1.5x original size

2. IVF (Inverted File Index)

# Used by: FAISS
# Divides the space into clusters
# Search only within relevant clusters
# Speed: 10-100x faster

3. LSH (Locality Sensitive Hashing)

# Hashes similar vectors into the same bucket
# Speed: 50-100x faster
# Accuracy: ~95%

---

FAISS Example (basic)

import faiss
import numpy as np

# Embeddings
embeddings = np.random.randn(10000, 1536).astype('float32')
query = np.random.randn(1, 1536).astype('float32')

# Index (IVF)
nlist = 100  # Number of clusters
quantizer = faiss.IndexFlatL2(1536)
index = faiss.IndexIVFFlat(quantizer, 1536, nlist)

# Train
index.train(embeddings)
index.add(embeddings)

# Search (top-5)
k = 5
distances, indices = index.search(query, k)

print(f"Top-5 indices: {indices[0]}")
print(f"Distances: {distances[0]}")

---

Accuracy vs Speed Trade-off

# Exact search:
# - Accuracy: 100%
# - Speed: 1x (baseline)

# HNSW:
# - Accuracy: 99%
# - Speed: 100x

# IVF (nlist=100):
# - Accuracy: 95%
# - Speed: 50x

# IVF (nlist=1000):
# - Accuracy: 98%
# - Speed: 20x

Optimal: HNSW for production (best accuracy/speed balance).

---

Summary

• ✅ ANN: 100x speedup with 99% accuracy
• ✅ HNSW: Best algorithm (used by Pinecone)
• ✅ FAISS: Open-source library
• ✅ Production: ANN is mandatory for >1M vectors

---

Module 5 - Capsule 06