AI Principles · Orchestration

Vector search

Under every RAG system is one hard problem: find the handful of vectors nearest a query, among millions or billions. Comparing them all is too slow — so approximate nearest-neighbor search trades a sliver of accuracy for enormous speed.

Read at your depth: 01 The answer · 02 Intuition · 03 Mechanics · 04 The math · 05 The code · 07 Sources

01The answer, then the intuition

Don't check everything — check the right neighborhood

An embedding turns every document into a point in high-dimensional space, where nearness means similar meaning. Retrieval is then just geometry: find the points closest to the query point. The naive way — measure the distance to every stored vector and sort — is exact but costs a full scan per query. At a billion vectors, that's hopeless.

The insight of approximate nearest-neighbor (ANN) search is that you don't need to check everything. Pre-build an index that lets you jump to the right neighborhood and examine only a few candidates. You give up a tiny chance of missing a true neighbor in exchange for searching orders of magnitude fewer points. Move the query below and watch exact scan versus approximate:

Nearest-neighbor search — exact vs approximate

Click or drag anywhere to move the query. The 3 nearest points light up; examined points are ringed.

—

points compared

—

correct top-3 found

02Mechanics

How you skip the full scan

The problem is scale. Exact search compares the query to all $N$ vectors, each of dimension $d$ — fine for thousands, ruinous for billions. Every RAG query would otherwise touch the entire store.
HNSW graphs. The dominant method builds a navigable "small-world" graph linking each vector to nearby ones, with a few long-range links layered on top. Search starts anywhere and greedily hops toward the query, reaching the neighborhood in roughly logarithmic steps — examining a few dozen points instead of billions.
IVF & quantization. Alternatives cluster the space into cells and search only the nearest cells (IVF), and product quantization compresses each vector into a few bytes so more fit in memory. These cut both time and storage, at some cost to precision.
The trade-off: recall. ANN can occasionally miss a true neighbor — measured as recall@k. Turning a knob (examine more candidates) raises recall toward 100% but costs speed. Vector databases — pgvector, FAISS, Qdrant, Pinecone, Weaviate — are largely engines for tuning this recall-speed-memory triangle.

So vector search is the unglamorous machinery that makes semantic retrieval possible at real scale — the reason "search by meaning over everything you own" is a product and not a research demo.

04The math

expand ▾

From linear to logarithmic

The $k$ nearest neighbors of a query $q$ minimize distance over the store:

$$ \text{kNN}(q) = \operatorname*{arg\,min}_{|S|=k}\; \sum_{d_i \in S} \lVert q - d_i \rVert $$

Exact search evaluates that distance for every vector — cost $O(N \cdot d)$, linear in the number of documents. An HNSW index changes the exponent: greedy graph traversal reaches the query's neighborhood in roughly

$$ O\big(d \cdot \log N\big) \quad\text{expected, per query} $$

The difference between $N$ and $\log N$ is the whole game: at a billion vectors, $\log_2 N \approx 30$, so ANN examines on the order of tens of candidates instead of a billion. The price is recall@k $= \frac{|\text{retrieved} \cap \text{true top-}k|}{k}$, which a good index keeps at 95–99% while searching a vanishing fraction of the data.

05The code

expand ▾

Exact search, and why it doesn't scale

Exact k-NN is a full scan. The comparison count is the whole reason ANN indexes exist.

knn.py

import numpy as np

q = np.array([5.0, 5.0])
store = {"A":[5.2,4.8], "B":[1.0,1.0], "C":[6.0,5.5], "D":[8.5,2.0],
         "E":[4.6,5.3], "F":[9.0,9.0], "G":[2.0,7.0], "H":[5.1,6.2]}

comparisons = 0
dists = {}
for name, p in store.items():
    comparisons += 1                       # exact = compare to EVERY vector
    dists[name] = np.linalg.norm(q - np.array(p))

top3 = sorted(dists, key=dists.get)[:3]
print(f"exact scan: {comparisons} comparisons")     # 8 (here) ... N at scale
print("3 nearest:", [(n, round(float(dists[n]), 2)) for n in top3])
# exact scan: 8 comparisons
# 3 nearest: [('A', 0.28), ('E', 0.5), ('C', 1.12)]
# an HNSW index would touch ~log(N) candidates and return the same 3

07Going deeper

expand ▾

The primary sources

Malkov & Yashunin (2016) — HNSW · the navigable small-world graph index.
Johnson et al. (2017) — Billion-scale similarity search (FAISS) · ANN at scale.
Jégou et al. (2011) — Product Quantization · compressing vectors for search.
ANN-Benchmarks · the recall-vs-speed trade-off, measured across libraries.

"First Principles — how AI actually works", chapter "Vector search", by The Catch. CC-BY 4.0. Hosted at TheCatch.AI / Tech Stack / AI Principles.

Originally from First Principles by The Catch · CC-BY 4.0 · Hosted at TheCatch.AI / Tech Stack / AI Principles