Approximate Nearest Neighbor (ANN) Search and HNSW Intuition

The similarity metrics from the previous subtopic tell you HOW to compare two vectors, but they don't address a scaling problem: if you have 50 million stored document vectors and a new query comes in, comparing the query against every single one of those 50 million vectors (called exact or 'brute-force' search) is enormously slow — the work grows linearly with the collection size, so doubling your document count doubles every single search's cost. Fine for a few thousand vectors; unworkable at real production scale. This is exactly the scaling problem approximate nearest neighbor (ANN) search solves.

The core idea behind ANN is a trade: give up the GUARANTEE of finding the mathematically absolute closest vector, in exchange for finding a vector that's ALMOST certainly among the closest ones, dramatically faster. In practice, for real embedding data, ANN algorithms find the true nearest neighbor (or something essentially as good) the vast majority of the time, while running orders of magnitude faster than brute-force — a trade nearly every production system happily accepts. This course's RAG-workflow section mentions this directly: once the approximate nearest neighbors have been retrieved, the system gathers the corresponding stored context — 'approximate' is baked into how production vector search actually works, not an edge case.

HNSW (Hierarchical Navigable Small World) is the most widely used ANN algorithm today, and the intuition behind it is genuinely visual. Imagine multiple LAYERS of a graph connecting your vectors, like a multi-level highway system: the TOP layer has very few nodes with long-range connections (like interstate highways — jump across huge distances quickly, but only a few 'exits'), and each layer below has progressively MORE nodes with shorter, more local connections (down to city streets — precise, but only useful once you're already close). A search starts at the sparse top layer, quickly navigates via the long 'highway' connections to roughly the right neighborhood, then drops down a layer and refines locally, drops down again, and repeats — narrowing in on the true nearest neighbors far faster than searching every point directly, similar to how you'd take a highway to get near your destination city before switching to local streets for the last mile.

You'll rarely implement HNSW yourself — vector databases and libraries (covered in the next subtopic) implement it internally and expose simple 'add vector' / 'search' APIs. What matters practically is knowing the KNOBS: most ANN implementations let you trade search speed against accuracy (e.g. HNSW's ef_search parameter — search more candidates per query for higher accuracy at the cost of latency), and understanding that a slightly-not-perfectly-optimal top result is the accepted cost of vector search actually being usable at scale.

# Simulating the CORE tradeoff ANN makes: brute-force checks every
# vector (exact, slow); a simplified 'layered' search checks far
# fewer vectors by first narrowing to a rough neighborhood.
import random
import math

random.seed(0)

def euclidean(a, b):
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))

def brute_force_search(query, vectors: dict) -> tuple[str, int]:
    """Exact search: checks EVERY vector. Guaranteed correct, doesn't scale."""
    best_id, best_dist, checked = None, float("inf"), 0
    for vid, v in vectors.items():
        d = euclidean(query, v)
        checked += 1
        if d < best_dist:
            best_id, best_dist = vid, d
    return best_id, checked

def toy_layered_search(query, vectors: dict, top_layer_sample: int = 20) -> tuple[str, int]:
    """Simplified HNSW-style idea: first narrow to a rough neighborhood
    using a small SAMPLE (the sparse 'top layer'), then only refine
    among that neighborhood's closest few real vectors."""
    all_ids = list(vectors.keys())
    sample_ids = random.sample(all_ids, min(top_layer_sample, len(all_ids)))
    # "top layer": find the roughly-nearest sampled point
    coarse_best = min(sample_ids, key=lambda vid: euclidean(query, vectors[vid]))
    # "lower layer": only refine among points near that coarse match
    neighborhood = sorted(all_ids, key=lambda vid: euclidean(vectors[coarse_best], vectors[vid]))[:15]
    best_id = min(neighborhood, key=lambda vid: euclidean(query, vectors[vid]))
    return best_id, top_layer_sample + len(neighborhood)

vectors = {f"doc_{i}": [random.gauss(0, 1) for _ in range(8)] for i in range(5000)}
query = [random.gauss(0, 1) for _ in range(8)]

exact_id, exact_checked = brute_force_search(query, vectors)
approx_id, approx_checked = toy_layered_search(query, vectors)
print(f"brute-force:  checked {exact_checked} vectors -> {exact_id}")
print(f"toy ANN-like: checked {approx_checked} vectors -> {approx_id}")
print(f"speedup: ~{exact_checked / approx_checked:.0f}x fewer comparisons")