Finding the K-Nearest Neighbors (KNN) of a query point is a fundamental operation in machine learning, recommendation systems, and AI-powered search. Given a query vector and a database of N vectors, exact KNN computes the distance from the query to every single vector and returns the k closest ones. This works flawlessly — but it’s O(N × D) where D is the vector dimensionality, making it prohibitively slow for the million- and billion-vector collections common in production AI systems.
Approximate K-Nearest Neighbors (AKNN) algorithms solve this by accepting a small accuracy tradeoff: instead of guaranteeing the true k closest vectors, they return vectors that are very likely the closest, typically achieving 95–99% recall while reducing query latency from seconds to sub-millisecond. This tradeoff is the cornerstone of every modern vector database.
The dominant AKNN algorithm families are graph-based (HNSW), partition-based (IVF), tree-based (Annoy), and hash-based (LSH). Each makes different tradeoffs between index build time, memory usage, query speed, and recall. Understanding these algorithms is essential for tuning vector search performance in RAG pipelines, semantic search engines, and recommendation systems.
Exact KNN (also called brute-force or flat search) computes the distance between the query vector and every vector in the database, then returns the k with the smallest distance. For a dataset of 10 million 1536-dimensional vectors, this requires ~15 billion floating-point operations per query. Even with SIMD-optimized distance functions, this takes hundreds of milliseconds — unacceptable for real-time applications.
Recall@K is the primary metric for evaluating AKNN quality. It measures the fraction of the true K nearest neighbors that the approximate algorithm actually returns. A recall@10 of 0.95 means that 9.5 out of the 10 true nearest neighbors appear in the approximate result set. Higher recall means better accuracy, but typically costs more computation time.
HNSW is the current state-of-the-art AKNN algorithm, used by default in Pinecone, Weaviate, Qdrant, Milvus, Elasticsearch, and pgvector. It builds a multi-layer graph where each node represents a vector and edges connect nearby vectors.
When a new vector is inserted, the algorithm assigns it a maximum layer using an exponentially decaying probability distribution. Most vectors exist only in Layer 0 (the base layer); fewer appear in Layer 1; even fewer in Layer 2, and so on. This creates a natural hierarchy:
At each layer, the new vector is connected to its M nearest neighbors (typically M = 16). The parameter efConstruction (typically 128–512) controls how many candidates are evaluated during construction — higher values build a better-connected graph but take longer.
efSearch (typically 64–500), exploring multiple paths simultaneously.M (max connections per node): Higher M improves recall but increases memory and build time. Typical: 16–64.
efConstruction (build-time beam width): Higher values build better graphs. Typical: 128–512.
efSearch (query-time beam width): Higher values improve recall at the cost of latency. Typical: 64–500.
Search complexity is O(log N) with constant factors determined by M and efSearch.
# HNSW search pseudocode
def hnsw_search(query, entry_point, layers, ef_search, k):
current_nearest = entry_point
# Phase 1: Greedy descent through upper layers
for layer in reversed(layers[1:]):
while True:
neighbors = layer.get_neighbors(current_nearest)
closest = min(neighbors, key=lambda n: distance(query, n))
if distance(query, closest) >= distance(query, current_nearest):
break # local minimum reached
current_nearest = closest
# Phase 2: Beam search at Layer 0
candidates = MinHeap([current_nearest])
visited = set([current_nearest])
result = MaxHeap(k) # keeps k closest
while candidates:
c = candidates.pop()
if result.full() and distance(query, c) > result.top():
break # no point exploring further
for neighbor in layers[0].get_neighbors(c):
if neighbor not in visited:
visited.add(neighbor)
candidates.push(neighbor)
result.push(neighbor)
return result.items()IVF takes a partition-based approach. During index construction, the vector space is divided into nlist clusters (typically 256–16384) using k-means clustering. Each vector is assigned to its nearest cluster centroid.
At query time, the algorithm computes the distance from the query to all centroids, selects the nprobe nearest clusters (typically 8–64), and then performs exact search only within those clusters. This reduces the search space by a factor of nlist / nprobe.
Product quantization is a compression technique often combined with IVF to create IVF-PQ indexes. It splits each D-dimensional vector into m sub-vectors of D/m dimensions each, then independently quantizes each sub-vector into one of 256 centroids (1 byte). A 1536-dimensional float32 vector (6144 bytes) can be compressed to just 48 bytes (m=48) — a 128× reduction.
Distance calculations use precomputed lookup tables, making them extremely fast but introducing quantization error that reduces recall. IVF-PQ is the go-to algorithm for billion-scale datasets where memory is the primary constraint.
LSH uses hash functions designed so that similar vectors hash to the same bucket with high probability. Multiple hash tables with different hash functions increase recall. LSH offers sub-linear query time with theoretical guarantees, but in practice HNSW and IVF outperform it on most benchmarks. LSH remains relevant for streaming data and extremely high-dimensional spaces.
Developed by Spotify, Annoy builds a forest of random projection trees. Each tree recursively splits the vector space with random hyperplanes. At query time, it traverses all trees and collects candidate vectors from the leaf nodes matching the query. Annoy excels at low-memory, read-heavy workloads but doesn’t support incremental updates — the index must be rebuilt to add new vectors.
The ann-benchmarks project provides standardized comparisons across AKNN algorithms and implementations. Key findings from recent benchmarks on the SIFT-1M dataset (1 million 128-dimensional vectors):
For the GloVe-200 dataset (1.2M vectors, 200 dimensions), HNSW consistently dominates the recall-vs-QPS Pareto frontier.
In a RAG system, the consequence of a missed relevant chunk is that the LLM generates an answer without key context — potentially hallucinating. This makes recall more important than raw speed. Typical production settings:
M=32, efConstruction=256, efSearch=128 for collections under 50M vectors.nlist=4096, nprobe=64, m=48 for collections above 100M vectors where memory is constrained.Spotify uses Annoy to serve recommendations from ~4 billion track embeddings across 600+ million users. Pinecone’s managed service handles collections of 1B+ vectors using sharded HNSW indexes with p99 query latencies under 50ms. Facebook’s FAISS library (powering their internal similarity search) uses IVF-PQ to index multi-billion-vector datasets on GPU clusters.
Every AKNN algorithm exposes parameters that let you slide along the recall-latency curve. For HNSW, increasing efSearch from 100 to 500 might improve recall from 95% to 99.5% while increasing latency from 1ms to 5ms. The right setting depends on your application: a chatbot can tolerate 50ms latency for better context retrieval; an autocomplete feature needs sub-5ms responses and can accept lower recall.
O(N × D) and too slow for production-scale vector collections; AKNN algorithms provide sub-millisecond search by accepting small recall losses.O(log N) search complexity.efSearch, nprobe, M) that let you trade latency for recall based on application requirements.