Vector Search Internals: HNSW, IVF, and Product Quantization

HNSW: Hierarchical Navigable Small Worlds

Performing an exact nearest-neighbor search across millions of high-dimensional vectors is too slow for real-time applications. Hierarchical Navigable Small Worlds (HNSW) is a graph-based Approximate Nearest Neighbor (ANN) algorithm that achieves an excellent balance between search speed, recall, and memory usage. It builds on the principles of Navigable Small Worlds (NSW) and adds a critical enhancement: a hierarchical, multi-layer graph structure.

The Multi-Layer Architecture

HNSW builds multiple layers of graphs. The bottom layer (Layer 0) contains every data point in the index. Each layer above it holds a progressively smaller subset. The topmost layer has only a handful of nodes, serving as the global entry point.

Higher layers act as long-range expressways — they let the search jump quickly across the vector space. Lower layers provide fine-grained local navigation. The search always starts at the top and descends, zooming in on the target region layer by layer.

Each node exists in its assigned layer and all layers below it. A node assigned to Layer 2 is also present in Layers 1 and 0. Connections exist only within each layer. The search transitions downward by reusing the closest node found in layer l as the entry point for layer l - 1.

Graph Construction Algorithm

Building an HNSW index is an incremental process. Each new vector p is inserted one at a time. The steps below walk through what happens when you insert a single point.

Search Algorithm

Searching for the k nearest neighbors of a query vector q mirrors insertion — but the graph is read-only. No connections are modified.

1. Start at the top. Use the global entry point of the topmost layer.
2. Greedy descent. In each layer, navigate greedily toward q. Track only the single closest node found (for layers above Layer 0).
3. Refine at Layer 0. Use the closest node from Layer 1 as the entry point. Run a more exhaustive search controlled by efSearch — a candidate queue that tracks the best nodes seen so far.
4. Return top k. Once the queue cannot be improved further, return the k closest vectors from the final candidate list.

efSearch directly controls the speed-recall tradeoff at query time. Adjust it below to see the effect on latency and recall:

recall = min(99.8, 60 + 32 × log(efSearch / 10) / log(512 / 10))

latency_ms = 0.4 + efSearch × 0.028

nodes_evaluated ≈ efSearch × 6.2

Core Parameters and Tuning

HNSW exposes four key parameters. Each controls a distinct dimension of the index quality. Flip the cards below to review each parameter's role and typical values.

Advantages and Disadvantages

Inverted File Index (IVF) Variations

IVF takes a different approach from graph-based methods. It partitions the vector space into distinct regions using clustering, then restricts each search to only the most relevant regions. This dramatically reduces the number of distance calculations needed per query.

How IVF Works

During index construction, IVF runs k-means clustering on the dataset to produce k centroids. Each data vector is then assigned to its nearest centroid, forming k inverted lists (also called buckets or cells). At query time:

1. The query vector q is compared against all k centroids.
2. The nprobe nearest centroids are selected.
3. Only the vectors in those nprobe lists are searched with full distance calculations.
4. The closest results from those lists are returned.

Tune nprobe below to explore how it affects recall and search cost:

recall = min(99.5, 55 + 38 × log(nprobe) / log(256))

coverage_% = (nprobe / 256) × 100

latency_ms = 0.3 + nprobe × 0.31

IVFPQ: Combining IVF with Product Quantization

IVFFlat stores full float32 vectors inside each inverted list. For large datasets, this is memory-prohibitive. IVFPQ addresses this by compressing the vectors inside each list using Product Quantization (PQ). Only compact PQ codes are stored, not original vectors.

At query time, the search inside each probed list uses Asymmetric Distance Computation (ADC): the query vector stays full-precision, while distances to database vectors are approximated via precomputed lookup tables over the PQ codes. ADC is significantly faster than full-vector distance calculation.

Choosing Between IVFFlat and IVFPQ

Product Quantization (PQ) Mechanics

A 768-dimensional float32 vector requires 3,072 bytes. Storing 100 million such vectors takes nearly 300 GB of RAM. Product Quantization (PQ) compresses these vectors to a few bytes each while preserving enough information for fast approximate distance calculations.

Vector Decomposition

PQ splits a D-dimensional vector x into M non-overlapping sub-vectors, each of dimension D/M. For example, a 768-dim vector with M=48 produces 48 sub-vectors of dimension 16 each.

# D=768, M=48, k*=256 (1 byte per code)
import numpy as np
from sklearn.cluster import MiniBatchKMeans

D, M, K_STAR = 768, 48, 256
sub_dim = D // M  # 16

# Train M independent codebooks on training data
codebooks = []
for m in range(M):
    sub_vectors = train_data[:, m * sub_dim : (m+1) * sub_dim]
    kmeans = MiniBatchKMeans(n_clusters=K_STAR, random_state=42)
    kmeans.fit(sub_vectors)
    codebooks.append(kmeans)

# Encode a single vector x -> M bytes
def pq_encode(x):
    code = np.empty(M, dtype=np.uint8)
    for m in range(M):
        sub = x[m * sub_dim : (m+1) * sub_dim]
        code[m] = codebooks[m].predict([sub])[0]
    return code  # 48 bytes vs. 3072 bytes original → 64x compression

Subspace Quantization and Codebooks

For each of the M subspaces, PQ trains a separate codebook of k* centroids using k-means. Each sub-vector is then replaced by the index (0–255 when k*=256) of its nearest centroid in that subspace's codebook. The entire original vector reduces to M bytes — 48 bytes for the 768-dim example, versus the original 3,072 bytes. This is a 64x compression ratio.

Approximate Distance Calculation

The key performance gain of PQ is not just storage compression — it is fast distance approximation. For a query vector q, PQ precomputes a lookup table for each of the M subspaces: the distance from q's sub-vector to every one of the k* centroids in that subspace.

This creates M tables, each with k* entries. Approximating the distance to any database vector then costs exactly M table lookups and M-1 additions — no floating-point multiplication over D dimensions. For D=768 and M=48, this replaces 768 multiply-add operations with 48 integer lookups.

ADC vs SDC. Asymmetric Distance Computation (ADC) keeps the query full-precision. Symmetric Distance Computation (SDC) also quantizes the query, enabling all-centroid precomputation, but adds quantization error to the query side. SDC is faster but less accurate. ADC is the default in FAISS and most production systems.

Trade-offs

PQ introduces a tunable accuracy-compression tradeoff via two parameters:

• M (number of subspaces): More subspaces means shorter sub-vectors, finer quantization, and higher recall — but the code length grows (M bytes per vector) and codebook training time increases linearly.
• k* (centroids per codebook): More centroids means finer resolution within each subspace. k*=256 is the standard choice — it fits each code in one byte (8 bits), which is byte-aligned and SIMD-friendly. Going to k*=512 needs 9 bits and complicates packing.

Other Graph-Based ANN Methods

HNSW is not the only graph-based ANN algorithm. NSG and Vamana represent distinct design philosophies for building proximity graphs, each targeting different constraints.

NSG: Navigating Spreading-Out Graphs

NSG focuses on building a graph with strong directional coverage. Rather than connecting each node purely to its nearest neighbors, NSG selects neighbors that provide diverse angular coverage relative to the node — the "spreading-out" property. This prevents the graph from clustering too tightly around local neighborhoods, which would trap greedy search in local optima.

Construction starts from an initial approximate k-NN graph. A designated navigation node serves as the global entry point for all searches. For each node, NSG iteratively selects neighbors by checking whether a candidate improves reachability from the navigation node. After construction, a refinement pass ensures global connectivity.

NSG can achieve high recall with compact graphs — fewer edges than HNSW at equivalent recall targets in some benchmarks. The tradeoff: construction is more complex and the single navigation node can create hotspot congestion under high concurrency.

Vamana Algorithm

Vamana is the core index behind DiskANN, designed for datasets too large to fit in RAM. It explicitly optimizes the graph structure for greedy search performance, not just proximity.

Construction is iterative. Vamana starts with a random graph of fixed out-degree, then runs multiple refinement passes. In each pass, it simulates a greedy search for each node and uses a RobustPrune heuristic to update neighborhood sets. RobustPrune rejects a candidate neighbor p_c if an existing neighbor p_n is closer to the target than p_c is — preventing redundant short-range edges in favor of long-range navigational edges.

Because Vamana targets disk storage, it batches neighbor list reads to minimize random I/O. The resulting graph achieves state-of-the-art recall at billion-scale datasets that reside entirely on SSDs.

Choosing Between Graph Methods

Selecting the Right ANN Algorithm

No single algorithm wins across all dimensions. Your choice must be driven by your specific constraints: dataset size, memory budget, recall target, latency budget, and update frequency.

Core Trade-off Dimensions

• Recall: What fraction of true top-k neighbors do you need? 95%? 99%?
• Latency: Do you need sub-millisecond P99, or is 10ms acceptable?
• Memory: Can the entire index fit in RAM, or must it live on disk?
• Build time: Is index construction a one-time cost or a frequent event?
• Updateability: Do vectors change frequently? Are deletions common?

Algorithm Characteristics at a Glance

Making the Decision

1. Define your recall floor. If you need 99%+ recall, HNSW with high efSearch is your starting point. If 90% recall is acceptable, IVF variants open up.
2. Check your memory budget. If the index must fit under a fixed RAM ceiling, calculate index size first. For HNSW: roughly M * 8 bytes * N bytes in graph links alone, plus vector storage. IVFPQ compresses vectors to M_pq bytes each and has no graph overhead.
3. Check your dataset size. Below 1M vectors, HNSW in-memory is almost always correct. Above 100M vectors, consider IVFPQ or DiskANN.
4. Benchmark on your data. Theoretical comparisons guide the starting point. Only benchmarks on your actual query distribution and vectors reveal the true recall-latency curve.