Vector Indexing & HNSW

Why Exact k-NN Breaks Down at Scale

Modern AI search, RAG pipelines, and recommendation engines represent text, images, and audio as dense embedding vectors v ∈ ℝ^d (typically d = 768 to 3,072 float32 numbers) where geometric closeness (Cosine similarity, Inner Product, or Euclidean L2 distance) reflects semantic similarity.

Finding the exact top-k nearest neighbors (Flat Index) is simple: compute dist(q, x) against every vector x in the dataset and keep a bounded heap of size k (O(N · d + N log k)).

At N = 50,000, brute force takes < 2 ms and gives 100% recall. At N = 50,000,000 with d = 1,536:

• Raw float32 vectors occupy 50M × 1,536 × 4 bytes ≈ 307 GB of RAM.
• Scanning all 50M vectors per user query requires 76.8 billion multiply-adds!

Why don’t classical k-d trees save us? Because of the curse of dimensionality: once d > ~20, hyper-rectangles intersect nearly every query hypersphere, forcing exact spatial trees to inspect almost 100% of leaves anyway. To go sub-linear, we embrace Approximate Nearest Neighbor (ANN) indexing.

Strategy 1: Partition Space with IVF (Inverted File Index)

IVF runs k-means during index build to partition the vector space into C Voronoi cells (often C ≈ √N), storing an inverted list of vectors assigned to each centroid:

1. Coarse step: Compare query q against the C centroids (O(C · d)).
2. Fine step: Scan vectors inside only the nprobe closest Voronoi cells!

• The Boundary Trap: If q lands right near the border between two Voronoi cells and nprobe = 1, the true nearest neighbor sitting across the border in the adjacent cell is missed. Increasing nprobe (1 → 4 → 16) raises Recall@k smoothly at a linear increase in latency.
• IVF + PQ (Product Quantization): When vectors don’t fit in RAM, PQ slices each d-dimensional vector into M sub-vectors (e.g. 96 chunks of 16 floats) and replaces each chunk with a 1-byte (0..255) centroid ID — shrinking memory 16× to 64× and estimating distances via fast lookup tables!

Strategy 2: Navigate Proximity Graphs with HNSW

HNSW (Hierarchical Navigable Small World) is the workhorse behind pgvector, Qdrant, Weaviate, Milvus, and Lucene when low-latency, high-recall in-memory search and live inserts matter.

Think of HNSW as Skip Lists meets Dijkstra / Best-First Search:

1. Upper Express Layers (L₂, L₁): Contain exponentially fewer nodes (assigned randomly with geometric decay, just like a Skip List) wired with long-range edges. Starting at a fixed entry point on the top layer, greedy search hops from neighbor to neighbor as long as dist(neighbor, q) < dist(current, q) until reaching a local minimum, then drops down to the next layer at that exact node.
2. Dense Base Layer (L₀): Contains every vector with up to 2 · M local short-range edges. Here, instead of stopping at the first local valley, HNSW runs a bounded priority-queue beam search of width efSearch (identical in spirit to Dijkstra’s min-heap!) so it can route around sparse gaps and return the best k candidates.

from heapq import heappop, heappush


def greedy_layer_descent(
    query: list[float],
    entry_id: int,
    adj: dict[int, list[int]],
    vectors: dict[int, list[float]],
    dist_fn,
) -> int:
    """Upper-layer HNSW zoom: greedily hop to closer neighbors until local minimum."""
    curr = entry_id
    curr_dist = dist_fn(query, vectors[curr])
    improved = True

    while improved:
        improved = False
        for nxt in adj[curr]:
            d = dist_fn(query, vectors[nxt])
            if d < curr_dist:
                curr, curr_dist = nxt, d
                improved = True
    return curr


def beam_search_base_layer(
    query: list[float],
    entry_id: int,
    ef_search: int,
    adj0: dict[int, list[int]],
    vectors: dict[int, list[float]],
    dist_fn,
) -> list[tuple[float, int]]:
    """Layer-0 HNSW search using a candidate min-heap + bounded max-heap of size ef_search."""
    d0 = dist_fn(query, vectors[entry_id])
    visited = {entry_id}
    candidates = [(d0, entry_id)]     # Min-heap: closest unexplored neighbor next
    best_results = [(-d0, entry_id)]  # Max-heap via negated distance: worst kept is -best_results[0][0]

    while candidates:
        cand_dist, node = heappop(candidates)
        worst_kept = -best_results[0][0]
        if cand_dist > worst_kept and len(best_results) >= ef_search:
            break

        for nxt in adj0[node]:
            if nxt in visited:
                continue
            visited.add(nxt)
            d = dist_fn(query, vectors[nxt])
            if len(best_results) < ef_search or d < -best_results[0][0]:
                heappush(candidates, (d, nxt))
                heappush(best_results, (-d, nxt))
                if len(best_results) > ef_search:
                    heappop(best_results)

    return sorted((-neg_d, idx) for neg_d, idx in best_results)

Choosing the Right Index in Production

• N < 50k: Stick with Exact Flat Scan — 100% recall, zero index build time, trivial metadata filtering.
• 50k – 10M (low latency + live updates): HNSW (M = 16..32, tune efSearch per query). Watch RAM overhead (~4 × M bytes of graph edges per vector on top of raw vectors).
• 10M – 1B+ (memory-constrained or disk-backed): IVF-PQ or hybrid disk graphs (DiskANN / Vamana) to keep compressed routing codes in RAM while fetching full-precision vectors from NVMe SSDs for final reranking.