Vector search and ANN indexes

HNSW stands for Hierarchical Navigable Small World. It builds a multi-layer proximity graph where upper layers contain sparse long-range connections enabling coarse navigation, and the bottom layer holds dense short-range edges for fine-grained refinement. Greedy traversal from top to bottom achieves O(log n) average-case search complexity. This hierarchical structure mirrors a skip list but in graph form.

Cosine similarity normalizes by each vector's magnitude, measuring only the angle between vectors, so it is magnitude-invariant. Dot product is magnitude-sensitive: a longer vector can dominate similarity rankings regardless of direction. They are equivalent only when all vectors are unit-normalized. In RAG retrieval pipelines, cosine is preferred when embeddings are not guaranteed to be unit-norm to avoid magnitude bias.

M controls the maximum number of bidirectional links each node maintains per graph layer (layer 0 uses up to 2*M links). A larger M increases graph connectivity, improving recall, but linearly increases memory consumption and index build time. Typical values range from 8 to 64; beyond 64 marginal recall gains rarely justify the doubled memory. The graph overhead is approximately M × 8 bytes per node per layer.

ef_construction is the size of the dynamic candidate list used during index build to select neighbors at insertion time; a higher value produces a better-quality graph at the cost of longer build time. ef (ef_search) controls the beam width of the greedy search at query time and can be adjusted at runtime without any rebuild, directly trading recall for latency. ef_construction should be at least M to avoid degenerate sparse graphs.

PQ splits each d-dimensional vector into m sub-vectors of d/m dimensions and independently quantizes each sub-vector to one of k* centroids (typically 256), storing m centroid indices per vector. ADC builds a lookup table of m × k* sub-space distances between the query and every centroid once per query in O(d × k*); approximate distance to any DB vector is then just m table lookups summed in O(m)—no DB vector decoding required. This enables billions of approximate distance computations per second.

import faiss, numpy as np
d, m, bits = 128, 8, 8      # 128-dim, 8 sub-spaces, 8-bit codes
index = faiss.IndexPQ(d, m, bits, faiss.METRIC_L2)
index.train(xb)             # xb: (N, d) float32
index.add(xb)
D, I = index.search(xq, k)  # xq: (nq, d) float32

In an IVF index the database is partitioned into nlist Voronoi cells. At query time, the query is compared to all cell centroids and the nprobe closest cells are searched exhaustively. Increasing nprobe improves recall (reaching brute-force at nprobe=nlist) but latency scales linearly since more candidates are scanned. A practical rule of thumb is nprobe ≈ √nlist for a balanced recall-latency operating point.

Recall@10 = 0.95 means the ANN index returns, on average, 9.5 of the true 10 nearest neighbors (from brute-force ground truth) in its top-10 results. For ANN evaluation the ground-truth set size equals k, so precision and recall are numerically identical—using Recall@k is simply the convention. Values below 0.9 indicate significant approximation loss that may harm downstream task quality.

HNSW achieves O(log n) average-case search complexity. Upper layers act like skip-list express lanes: long-range edges allow O(log n) hops to approach the target region quickly, and the bottom layer performs local neighborhood refinement. The expected number of nodes visited per layer is O(log(1/p)) where p is the layer assignment probability, giving O(log n) total hops. The constant factor grows with M and ef, unlike brute-force O(n · d).

IndexIVFPQ stores only m bytes per vector (vs. ~4d bytes for HNSW), making it the right choice when the dataset does not fit in RAM or memory-per-vector is the primary constraint. For a 768-dim dataset with m=16 PQ sub-spaces, IVF-PQ uses 16 bytes/vector vs. ~3-6 KB for HNSW. HNSW achieves better recall at equivalent latency but its graph overhead makes billion-scale in-RAM storage impractical on commodity hardware.

import faiss
d, nlist, m, bits = 128, 1024, 8, 8
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, bits)
index.train(xb)
index.add(xb)
index.nprobe = 32
D, I = index.search(xq, 10)

DiskANN stores PQ-compressed codes for the entire dataset in RAM (a few GB for 1B vectors) and uses them to identify beam search candidates cheaply. Full-precision vectors and graph edges live on SSD; only the shortlisted candidates' data is fetched in 3-5 I/O rounds per query. The key algorithmic innovation is the Vamana graph with robust-prune neighbor selection that produces a navigable graph requiring fewer I/O rounds than a naive greedy search.

Post-filtering runs ANN to retrieve a shortlist and then discards non-matching vectors; when a filter is highly selective (e.g., matches only 0.1% of the database), true neighbors may not appear in the ANN shortlist, causing severe recall degradation regardless of any re-ranking. Mitigation strategies include over-retrieval (fetching k×α candidates), pre-filtering via auxiliary inverted indexes on metadata fields (as in Qdrant's HNSW + payload index), or partition-based approaches where each metadata value has its own sub-index.

Binary quantization maps each embedding dimension to a single bit (typically sign of the value), reducing a float32 embedding of d dimensions from 4d bytes to d/8 bytes—a 32× compression. Distance is computed via Hamming distance using CPU POPCNT instructions, giving roughly 100× throughput over float32 L2. Models fine-tuned for BQ (e.g., Cohere Embed v3, Matryoshka-trained OpenAI embeddings) recover ~95% Recall@10 with BQ retrieval followed by float32 re-scoring of the shortlist.

LSH for cosine similarity uses random hyperplane hashing: each hash function picks a random unit vector r and assigns hash bit = sign(x · r). The collision probability is P[h(x)=h(y)] = 1 − θ(x,y)/π, where θ is the angle between x and y, so similar vectors are more likely to share a bucket. Multiple hash tables with concatenated bits amplify separation, and candidates sharing any table's bucket are retrieved and re-ranked exactly. LSH is often outperformed by HNSW on the recall-latency curve but provides theoretical guarantees.

MRL trains embedding models with a nested loss that simultaneously optimizes representations at multiple truncated dimensions (e.g., 64, 128, 256, 512, 1536), so the first d' coordinates of the full embedding form a useful d'-dimensional embedding. This enables a two-stage retrieval: cheap coarse ANN over small-dimension embeddings generates a candidate set, then exact re-ranking uses the full-dimension embeddings. OpenAI's text-embedding-3 models use MRL, enabling 75%+ dimension reduction with under 5% Recall@10 loss, cutting ANN index memory and latency proportionally.

Hybrid search retrieves candidates from both a dense ANN index (semantic similarity) and a sparse inverted index (keyword matching via BM25 or SPLADE) independently, then merges the ranked lists. Reciprocal Rank Fusion (RRF) is the recommended strategy: score = Σ 1/(k + rank_i) with k ≈ 60, which is rank-based and therefore immune to the incompatible score scales of BM25 and cosine similarity. Score interpolation (α × dense_score + (1−α) × sparse_score) requires careful calibration and is dataset-sensitive.

HNSW with M=16 stores roughly (4 × 768 + 16 × 2 × 8) ≈ 3.3 KB/vector, totaling ~33 GB for 10M vectors, but achieves top-tier recall-latency (e.g., Recall@10=0.99 at 1-3 ms). IVF-PQ with m=16 sub-spaces uses only 16 bytes/vector (~160 MB for 10M vectors), dramatically more memory-efficient, but at equivalent recall requires more latency due to nprobe scanning overhead. The choice hinges on whether RAM budget or latency budget is the primary constraint.

HNSW indexes are memory-mapped from disk; after a process restart the underlying pages are cold and the first queries incur OS page faults causing multi-hundred-ms latency spikes. Warm-up involves pre-loading the index data into RAM or page cache before routing live traffic—either by a sequential mmap read, issuing representative warm-up queries, or using explicit 'load collection' APIs (Milvus, Qdrant). Rolling restarts should keep at least one warm replica in service during deployment.

ann-benchmarks benchmarks ANN libraries on standardized datasets (SIFT-1M, GloVe-100, etc.) by sweeping index parameters and plotting Recall@10 vs. queries-per-second (QPS). The Pareto frontier contains only those configurations where no alternative achieves both higher recall AND higher QPS—these are the non-dominated operating points. A practitioner picks a target recall (e.g., ≥0.95) and reads off the maximum QPS achievable; HNSW (hnswlib) consistently dominates this frontier for in-memory single-machine deployments.

ScaNN uses anisotropic vector quantization (AVQ): it minimizes a quantization loss that penalizes error in the query-parallel direction (which directly affects distance ranking) far more than error in the perpendicular direction (which does not). Standard PQ minimizes isotropic L2 reconstruction error regardless of direction, leading to suboptimal distance approximations. AVQ combined with tree-AH candidate selection and batched SIMD scoring gives ScaNN 2-10× higher QPS than FAISS IVF-PQ at equivalent recall on Google-scale datasets.

Tombstoning (soft delete) marks a node as deleted without rewiring its neighbors' edges, because true hard deletes in HNSW require expensive graph repair. The node stays in the graph until a background compaction (vacuum) removes it. Accumulated tombstones degrade recall because beam search at query time wastes candidate slots visiting dead nodes, effectively reducing the number of live nodes explored relative to ef, especially when the tombstone ratio exceeds ~10-20%.

Annoy (Spotify) builds a forest of random projection trees where each tree recursively splits the space with a random hyperplane until leaves are small enough, storing the entire structure as a memory-mapped flat file. Multiple processes can attach to the same mmap file without serialization overhead—ideal for frequently-restarted read-only services. Unlike HNSW, Annoy does not support incremental inserts; the index must be rebuilt from scratch on any data change, and it achieves lower recall at the same latency than HNSW.

ColBERT represents each document as a matrix of per-token embeddings and scores query-document relevance as MaxSim: the sum over each query token of its maximum cosine similarity to any document token. Standard ANN indexes handle one query vector vs. one database vector; ColBERT requires searching all document token embeddings (hundreds per document) simultaneously. PLAID (ColBERT's production system) addresses this by clustering all document token embeddings and running centroid-ANN first, then re-scoring shortlisted documents with full MaxSim—an approach fundamentally different from single-vector retrieval.

QAT fine-tunes the embedding model while simulating quantization noise (e.g., binary sign or int8 rounding) in the forward pass, so gradients teach the model to concentrate discriminative signal into quantization-stable dimensions. Without QAT, post-hoc binary quantization of a float32 model typically loses 10-15% Recall@10; with QAT, models like Cohere Embed v3 and Nomic-embed-v1.5 achieve under 3% recall loss at 32× memory compression. The key insight is that the model learns which information survives the quantization bottleneck.

NSG uses a monotonic path diversification rule (MRNG): when selecting neighbors for node u, a candidate p is pruned if any already-selected neighbor w satisfies dist(w, p) < dist(u, p), ensuring selected neighbors are spread across different directions rather than clustering in one region. This produces more globally navigable graphs with well-diversified edge sets. NSG achieves competitive or superior recall-latency over HNSW at the cost of higher build time, since NSG requires a k-NN graph (KNNG) as initialization whereas HNSW builds the graph incrementally via sequential insertion.

GPU ANN search exploits massive parallelism via two operations: (1) cuBLAS GEMM for all-pairs distance computation—an (nq × n × d) matrix multiplication executed across thousands of GPU cores—and (2) parallel top-k reduction using GPU-native algorithms. In practice, GPU brute-force and IVF-based ANN achieve 10–100× higher QPS than a multi-core CPU for the same dataset, with the exact ratio depending on dataset size, dimensionality, and query batch size. The fundamental constraint is that the entire index (or at least the active partition) must fit in GPU VRAM (24-80 GB), limiting dataset scale; billion-scale datasets require multi-GPU sharding or CPU-GPU hybrid approaches.

The quantization gap is the recall lost at the ANN first stage: if the true k nearest neighbors are absent from the ANN's retrieved candidate set (e.g., top-100), no subsequent re-ranker can recover them. It is addressed by over-retrieval (fetching k×α candidates with α=5-10) and cascaded retrieval: BQ ANN → float32 ANN → cross-encoder re-ranking. Each stage reduces the gap while keeping end-to-end latency manageable. Monitoring Recall@k of the first-stage ANN against exact ground truth is essential for catching silent degradation in production.

Index sharding partitions the vector dataset across multiple nodes, each holding a local ANN index. At query time the query is broadcast to all shards (fan-out); each returns its local top-k results, and a coordinator merges and re-ranks the global top-k. Recall@k is unaffected by sharding as long as each shard returns at least k results, because the true global top-k must reside in at least one shard. Latency is bounded by the slowest shard (straggler), so consistent shard sizes and hedged requests are critical.

BM25 is a non-learned retrieval function using term frequency and inverse document frequency with no trainable parameters. SPLADE is a learned sparse encoder that uses a transformer with log-sum-exp vocabulary pooling to produce sparse vectors in the full vocabulary space (~30,000 dims for BERT-vocab), where non-zero entries correspond to semantically expanded terms. Both SPLADE and BM25 vectors can be indexed identically in standard inverted indexes, but SPLADE's learned sparsity captures synonyms and paraphrases BM25 misses. SPLADE-v3 outperforms dense retrievers on out-of-domain BEIR benchmarks.

As dimension d grows, the ratio of maximum to minimum pairwise distances among random vectors converges to 1 (concentration of measure), making nearest-neighbor queries ill-conditioned because all candidates appear equally distant. Practically, HNSW and IVF-PQ show degraded recall-latency curves for d > 1000-2000 because greedy traversal heuristics fail more often. Common mitigations include PQ compression (sub-space factorization), PCA to ~256 dimensions, or using cosine similarity over normalized vectors, which is somewhat less affected than L2 distance in high dimensions.

IndexHNSWSQ uses scalar quantization (int8 or fp16) to compress neighbor vectors stored at graph nodes, reducing memory ~4× (SQ8) and improving distance computation throughput via integer SIMD without any index rebuild. Since HNSW uses distances only for relative comparisons during traversal (not for final output scores), SQ8 introduces only ~0.5% Recall@10 loss in practice. Use SQ8 when d ≥ 256 and memory or throughput is constrained; use IndexHNSWFlat when maximizing recall is the sole objective regardless of memory.

import faiss
d = 768
# Flat: exact float32 distances in graph traversal
index_flat = faiss.IndexHNSWFlat(d, 32)
# SQ8: int8-quantized distances, ~4x less memory, ~0.5% recall loss
index_sq = faiss.IndexHNSWSQ(d, faiss.ScalarQuantizer.QT_8bit, 32)

A two-tower model encodes queries and documents through separate (or weight-shared) encoder networks into a shared embedding space where similarity is measured by dot product or cosine. Because query and document encodings are computed independently, all document embeddings can be precomputed offline and indexed in an ANN index once. At serving time only the query tower runs (one forward pass), then ANN search retrieves the top-k documents in milliseconds—decoupling document indexing cost from query latency. This offline/online split is fundamental to scalable dense retrieval.

HNSW prunes a candidate p if any already-selected neighbor w is closer to p than the query node u (effectively α=1). Vamana's robust prune uses α ≥ 1: p is pruned only if dist(w, p) ≤ α × dist(u, p), meaning even if w is close to p, p is retained if it is sufficiently far from w in the direction of u. With α > 1 (e.g., 1.2), Vamana retains longer-range edges that improve global navigability, enabling search to reach distant regions in fewer hops—critical for disk-based search where each hop may incur an SSD I/O.

RRF computes a fused score as Σ 1/(k + rank_i) across retrieval systems, where k ≈ 60 is a stabilizing constant. It is rank-based and thus completely agnostic to score scale and distribution—BM25 scores (typically 0-20) and cosine similarities (0-1) cannot be directly interpolated without calibration that is query- and dataset-specific. Score normalization (min-max, softmax) is sensitive to score range outliers and shifts as the corpus changes. RRF was empirically shown optimal by Cormack et al. 2009 and consistently outperforms score interpolation in BEIR evaluations.

def rrf(rankings: list[list[int]], k: int = 60) -> dict[int, float]:
    scores: dict[int, float] = {}
    for ranks in rankings:
        for rank, doc_id in enumerate(ranks, start=1):
            scores[doc_id] = scores.get(doc_id, 0.0) + 1.0 / (k + rank)
    return dict(sorted(scores.items(), key=lambda x: -x[1]))

A graph is navigable if greedy search—always moving to the neighbor closest to the query—monotonically converges to the true nearest neighbor without getting trapped in local minima. Formally, for every query q and every non-target node u, there must exist a neighbor v of u with dist(v, q) < dist(u, q). HNSW ensures navigability via its hierarchical structure with long-range edges in upper layers; Vamana's robust prune with α > 1 explicitly retains long-range edges that provide escape routes from local optima. Navigability is measured empirically by 1-recall@1 and average distance computations per query.