Approximate Nearest Neighbor (ANN)

You need to find the 10 closest vectors to your query among 500 million stored vectors, each with 1,536 dimensions. Exact KNN means 500 million distance calculations, roughly 770 billion floating-point operations. Even on modern hardware, that's seconds per query.

Your users expect results in under 50 milliseconds.

Approximate Nearest Neighbor (ANN) algorithms solve this by cleverly organizing vectors so that searching requires examining only a tiny fraction of the dataset. The trade-off: results might miss a few true nearest neighbors (95-99% recall), but the speed improvement is 1,000x or more.

This isn't a theoretical compromise. In practice, the vectors ANN misses are the borderline cases, items that are almost equally distant as the true nearest neighbors. For recommendation engines, semantic search, and RAG, this difference is imperceptible to users.

The three most important ANN algorithms in production today are HNSW, IVF, and LSH. Each makes fundamentally different trade-offs, and understanding them lets you choose the right one for your scale and latency requirements.

Hierarchical Navigable Small World is the most popular ANN algorithm in production today. Used by Pinecone, Weaviate, Qdrant, pgvector, and Elasticsearch.

The idea: Build a multi-layer graph where each vector is a node. Nearby vectors are connected by edges. The top layer has few nodes with long-range connections (express lanes). Lower layers have more nodes with shorter connections. The bottom layer has all nodes.

Building the graph:

1. Insert each vector as a node
2. Randomly assign it a maximum layer (higher layers = less likely, like skip lists)
3. At each assigned layer, connect it to its M nearest neighbors

Searching:

1. Start at the top layer at an arbitrary entry point
2. Greedily move to the neighbor closest to the query vector
3. When no closer neighbor exists at this layer, drop to the next layer
4. Repeat until the bottom layer
5. At the bottom layer, do a more thorough local search among nearby nodes

Think of it as navigating a city. Start on the highway (top layer, big jumps), take the exit to a main road (middle layers), then navigate side streets (bottom layer) to reach your destination.

Key parameters:

• M (connections per node): Higher = better recall, more memory. Typical: 16-64
• ef_construction (search width during build): Higher = better graph, slower build. Typical: 200
• ef_search (search width during query): Higher = better recall, slower search. Typical: 50-200

Weakness: Memory. The graph itself can be as large as the vector data. For 1 billion vectors, you might need 200+ GB just for the graph structure on top of the vector storage.