Approximate Nearest Neighbor Indexes

One million ticket embeddings at 768 dimensions in float32: 1,000,000 × 768 × 4 = 3.07 GB. Exact nearest-neighbor means reading all 3.07 GB for one query. On a node pulling roughly 9 GB/s from memory that is a 340 ms query before a single multiply-accumulate finishes — three queries per second for every core you dedicate, at a latency no type-ahead box accepts.

   exact search                      approximate search

 read 3.07 GB                       read ~4,000 candidate vectors
 768-dim distance × 1,000,000       768-dim distance × 4,000
 rank, keep top 10                  rank, keep top 10
        |                                   |
        v                                   v
  recall = 1.000, 310 ms            recall ≈ 0.95, 6 ms

Two escapes exist. Shrink what is stored — product quantization turns a 3 KB vector into 32 bytes — and the error becomes systematic: every query pays it, and nobody can tell you which neighbors it displaced. Or accept that the index may skip a true neighbor. That is approximate nearest neighbor, and every ANN structure makes the same bargain: examine a subset of the corpus per query, then measure how much was missed with recall@k.

recall@10 = average over queries of  |ANN top 10 ∩ exact top 10| / 10

Everything else in this topic is a mechanism for moving along one curve — recall against latency — plus the arithmetic to know what you bought. The knobs each engine exposes are in Vector Search with pgvector and Managed Vectors with Pinecone; the measurement protocol that ties them together closes this topic.

IVF (inverted file) starts with a question that costs nothing to answer: which region of the space is the query in? Before it looks at vectors, it looks at centroids.

Training runs k-means over the corpus and splits it into lists clusters — 1024 for a million rows, roughly rows divided by 1000. Each vector records its centroid. At query time the search finds the nearest centroids, examines only those clusters, and ranks what they hold. probe is how many clusters it examines.

1M × 768-dim float32 vectors, 1000 held-out queries, one 8-core node. Your absolute numbers will move with hardware; the shape of the curve will not.

Read the last row: probe enough clusters and IVF converges on exact search, paying exact search's cost. That convergence is the honest part of the design — IVF never claims free recall, it lets you buy it in units of latency without rebuilding anything.

Three failure modes are structural rather than accidental:

• Default probe is 1. The shipped configuration examines one cluster, which is the fastest and least accurate point on the curve. If nobody tuned it, recall is exactly what the first row says.
• Skewed data defeats uniform lists. Dense regions of the corpus get many small clusters, the long tail gets a few large ones; a probe of 8 serves common tenants well and rare tenants badly. Measure recall per slice, not only in aggregate.
• Centroids trained on stale rows. The clusters describe the distribution at build time. After the corpus drifts, recall decays while latency looks healthy — the symptom that only a re-measurement against exact search will surface.

IVF asks which region; HNSW asks which neighbor to walk to next. It builds a proximity graph — each vector linked to its nearest m neighbors — and stacks it in layers where each level up keeps roughly one node in three:

layer 2      A --------------------------- F        (few nodes, long edges)
layer 1      A ----------- C ------- E --- F
layer 0      A - B - C - D - E - F - G - H - I ...  (every node)
             ^
      entry point: descend greedily while distance improves,
      then beam-search layer 0 carrying ef_search candidates

The descent through sparse layers costs almost nothing and lands near the query. Layer 0 then runs a beam search with a candidate heap of ef_search entries: larger heap, more of the neighborhood explored, better recall, more distance computations.

Same corpus, same node as the IVF table. Put the two side by side: at equal recall around 0.96–0.97, HNSW answers in ~9 ms where IVF needs ~16 ms. HNSW paid for that at build time — minutes of link construction against IVF's 25-second k-means pass — and it holds more memory.

The memory figure is worth computing instead of accepting. At m = 16, layer 0 stores up to 2m = 32 neighbor ids per node at 4 bytes each: about 128 bytes of graph per vector, plus a few percent for upper layers.

The graph is cheap against wide text embeddings and expensive against narrow ones. And steady-state size understates the real constraint: construction wants the vectors and the growing graph resident together, which is why builds OOM hosts that serve the table fine.

Inserts behave differently from IVF: the graph accepts new nodes by linking them during descent, so incremental writes need no rebuild. IVF is the one that must be retrained when the distribution moves.

Published recall figures are measured on vectors you do not have, for queries you will never run. The protocol to produce your own number is short enough to run after every index change:

rng = np.random.default_rng(0)
q_idx = rng.choice(len(emb), 1000, replace=False)   # held-out queries
queries = emb[q_idx]

exact = [set(np.argpartition(row, -10)[-10:])       # brute-force ground truth
         for row in queries @ emb.T]                # 1000 × 1M cosine scores

hits = 0
for q, truth in zip(queries, exact):
    res = index.query(vector=q.tolist(), top_k=10, namespace="tickets")
    hits += len(truth & {m["id"] for m in res["matches"]})
print(f"recall@10 = {hits / (1000 * 10):.3f}")

One number per configuration, and the trade table builds itself:

Where to aim depends on what runs after retrieval. A pipeline that re-ranks the top-30 with a cross-encoder (Reranking Models) recovers neighbors the index missed, provided they survived into the 30 — recall near 0.90 at the vector stage is often enough. Retrieval that answers directly, or hybrid setups that blend lexical matches (Hybrid Search), wants 0.95 or better because nothing downstream repairs a missing neighbor.

Record four things with every configuration: structure, parameter values, measured recall, measured p95. Without them, the next engineer who raises ef_search to quiet a complaint has no way to name the latency they spent or the recall they gained — and the alternative to that record is a benchmark on synthetic vectors that predicts nothing about your filters.