Choosing a Vector Search Algorithm for Production AI Systems

Vector search finds the closest embeddings to a query vector in a large collection, and the indexing strategy you pick trades off recall, latency, and memory in ways that shape your entire retrieval architecture.

Overview

Brute-force k-NN is exact but costs O(n-d) per query, which becomes impractical once corpora exceed roughly 100,000-500,000 vectors.
Approximate nearest neighbor (ANN) methods accept a small, measurable recall loss (tracked as recall@k against brute-force ground truth) in exchange for orders-of-magnitude speedups.
The two dominant ANN families work differently: HNSW reduces search cost via graph traversal, while IVF/PQ reduce it via space partitioning and vector compression.
No single index is universally correct - production systems typically compose multiple techniques (coarse filter -> ANN -> hybrid fusion -> exact rerank) into a tiered pipeline rather than relying on one index type.
Recall, latency, and memory must be measured against your own data and query patterns, not assumed from library defaults.

Key Concepts

Exact k-NN (Brute-Force Search)

Computes distance from the query to every vector; returns true top-k with 100% recall and no tuning knobs.
Cost is O(n-d), but is embarrassingly parallel and vectorizes well on CPU (SIMD) and GPU - FAISS exposes it as IndexFlatL2/IndexFlatIP.
Still the right choice under ~100K-500K vectors, for perfect-recall requirements (compliance, dedup), and as a reranking stage: retrieve broadly with ANN, then exact-score just the shortlist.

scores = corpus @ query  # cosine sim via dot product on normalized vectors
top_k_idx = np.argpartition(-scores, k)[:k]  # avoid full O(n log n) sort

Graph-Based ANN: HNSW

Builds a multi-layer graph (sparse long-range edges on top, dense local edges at the bottom); queries greedily descend layers, refining toward the nearest neighbor - conceptually a skip list over vector space.
Achieves near-logarithmic search scaling in practice (no tight worst-case bound), and is the default index in FAISS, hnswlib, Milvus, Qdrant, Weaviate, Elasticsearch, and pgvector.
Three tuning knobs: M (max connections/node, 16-64, trades memory for recall), efConstruction (build-time thoroughness), efSearch (query-time recall/latency trade-off, tunable without rebuilding the index).
Weakness: higher RAM per vector than partition-based methods, graph generally must stay in memory for low latency, and deletions require periodic rebuilds rather than clean removal.

Partition-Based ANN: IVF, Product Quantization, IVF-PQ

IVF: k-means splits the space into nlist Voronoi cells; a query only searches the nprobe nearest cells instead of the whole corpus.
Product Quantization (PQ): splits each vector into m sub-vectors, quantizes each independently (e.g., 256 centroids/sub-vector = 1 byte/code), enabling ~32x compression (768-dim float32 -> ~96 bytes) with approximate distance via precomputed lookup tables (asymmetric distance computation).
IVF-PQ combines both - FAISS's default for billion-scale search, same family as Google's ScaNN. Two error sources stack: IVF's cell-coverage error and PQ's quantization error - increasing nprobe does not fix quantization error and vice versa.
Related graph-traversal variant: Microsoft's DiskANN (Vamana graph) keeps the graph on SSD instead of RAM, trading latency for the ability to index corpora larger than memory.

Clustering + Exact Search

A simpler middle ground: cluster the corpus (IVF-style routing) but run exact distance computation within the selected clusters instead of PQ-compressed codes (IndexIVFFlat in FAISS).
Avoids quantization error entirely, at the cost of PQ's memory savings; well suited to data with natural partitions (multi-tenant systems, category taxonomies).
Failure mode: skewed cluster sizes make oversized clusters behave like de facto brute-force scans, spiking worst-case latency for queries routed there.

Hybrid Lexical + Vector Search

Combines BM25 lexical search (strong on exact terms, SKUs, acronyms) with vector search (strong on semantic/paraphrase matches) since each has blind spots the other covers.
Reciprocal Rank Fusion (RRF) merges result lists using only rank position (score(d) = Σ 1/(k + rank_i(d)), k≈60), sidestepping the problem that BM25 and cosine scores live on incomparable scales. It's the default fusion method in Elasticsearch, OpenSearch, and Vespa.
Common production pattern: lexical + vector retrieval -> RRF fusion -> cross-encoder reranking on the top 50-200 candidates.

const contribution = 1 / (k + rank);
scores.set(id, (scores.get(id) ?? 0) + contribution);

Learned Indexes

Replace hand-engineered structures (B-trees, IVF partitioning) with a model trained to predict item location, based on Kraska et al.'s "The Case for Learned Index Structures" (originally for scalar/structured data).
Applying this to high-dimensional vector search (e.g., learned cluster assignment instead of static k-means) is active research, not production-ready - FAISS, Milvus, Qdrant, and Weaviate still ship HNSW/IVF as defaults, not learned variants.

Binary and Quantized Embeddings

Sign-quantizes each dimension to a single bit (32x smaller than float32); distance uses Hamming distance via XOR + popcount, which is both smaller and faster per-comparison than float32 distance.
Accuracy loss is significant if used alone, so production use follows a retrieve-and-rescore pattern: cheap binary Hamming search over the full corpus -> rescore the shortlist with float32/int8 embeddings.
Pairs well with Matryoshka Representation Learning (MRL) models, whose leading dimensions carry more signal, reducing truncation penalty before quantization.

Trade-offs / Caveats

ANN recall is not free - it must be measured with a recall@k harness against brute-force ground truth; library defaults are tuned for general workloads, not your data distribution.
Switching embedding models invalidates the entire index (old and new embeddings aren't comparable), so reindexing cost/cadence must be planned for, not discovered mid-migration.
Post-retrieval metadata filtering can starve results when filters are highly selective; filter-aware or pre-filtering indexes are usually needed once filtered queries are common.
"Improving" RRF with weighted raw-score combinations is risky since BM25/cosine scales shift with query length and model choice - deviations need validation across a representative query set, not a handful of examples.

Example in Practice

A tiered retrieval pipeline for a large-scale RAG backend: binary embeddings provide a cheap first-pass filter over the full corpus (Hamming distance, fits in RAM/cache) -> an HNSW or IVF-PQ index performs the primary ANN retrieval on the narrowed set -> results are fused with BM25 lexical hits via RRF to catch exact-match terms -> a cross-encoder reranks the final top-N shortlist before anything reaches the LLM's context window. Each stage's recall is instrumented independently, since an early cheap stage can silently discard relevant results before expensive downstream stages ever see them.