Module 4 — Similarity Search (Exact Nearest Neighbors)

Now we use the metrics from Module 3 to actually find things. We start with the simple, exact way — then see why it can’t keep up, which sets up the clever indexes in Module 5.

The core task: k-Nearest Neighbors (kNN)

The job is stated in one line:

Given a query vector q and a collection of N stored vectors, return the k stored vectors most similar to q.

“Top-k” means “the best k results.” k is usually small — 5, 10, 50 — because a human or an LLM only consumes a handful of results. “Nearest neighbors” = the closest points by your chosen metric.

The simplest possible method: brute force (flat / exact search)

Compare the query to every stored vector, sort by similarity, take the top k.

import numpy as np

def brute_force_search(query, vectors, k=5):
    # vectors: shape (N, dim), assume L2-normalized so dot = cosine
    scores = vectors @ query          # one dot product per stored vector
    top_k = np.argsort(-scores)[:k]   # indices of highest scores
    return top_k, scores[top_k]

This is also called flat or exact search. It has a wonderful property and a fatal one:

✅ 100% accurate. It literally checks everything, so it always returns the true nearest neighbors.
❌ It scales linearly. Doubling your data doubles the work. Every single query touches every single vector.

The cost, made concrete

One comparison is dim multiply-adds. So one query costs roughly N × dim operations.

Vectors (N)	Dim	Ops per query	Feel
10,000	768	~7.7 million	Instant. Don’t overthink it.
1,000,000	768	~770 million	~Hundreds of ms on CPU. Getting slow.
100,000,000	768	~77 billion	Way too slow per query.
1,000,000,000	768	~770 billion	Hopeless one-at-a-time.

Now multiply by thousands of queries per second in production. Brute force collapses. Memory is also brutal: 1 billion × 768 floats × 4 bytes ≈ 3 terabytes of RAM just to hold the vectors. (Module 6 shrinks that.)

So when is brute force the right answer?

More often than beginners expect:

Small datasets (up to ~100k–1M vectors, depending on dim and latency budget). Exact search is simpler, perfectly accurate, and fast enough.
You need guaranteed exact results (e.g., a benchmark to measure how good your approximate index is — see “recall,” below).
Re-ranking a shortlist. A common pattern: use a fast approximate index to get the top 200 candidates, then brute-force-rank just those 200 precisely. Best of both worlds.

GPUs make brute force viable at surprisingly large scale too (FAISS on GPU can flat-search tens of millions quickly). Don’t reach for complex indexes before you need them.

The key trade-off you’ll manage forever: speed vs. accuracy vs. memory

Exact search gives perfect accuracy but poor speed at scale. The entire field of vector search is about giving up a tiny, controllable amount of accuracy to gain enormous speed and memory savings. Approximate methods might return 9 or 10 of the true top-10 — and do it 100–1000× faster. For search and RAG, missing one borderline result out of ten is almost always an acceptable trade. This is the central bargain of Module 5.

Recall: how we measure “how approximate?”

Since approximate search can miss true neighbors, we measure quality with recall@k:

recall@k = (number of true top-k neighbors the index actually returned) / k

Example: the true top-10 nearest neighbors are a known set. Your approximate index returns 10 results, and 9 of them are in that true set. Recall@10 = 0.9 (90%). Production systems often target 0.95–0.99 recall, tuning the index until speed and recall both meet requirements (Module 5 and 11).

To compute recall you need ground truth — which you get from brute force on a sample. That’s another reason exact search stays in your toolkit forever: it’s the ruler you measure approximations against.

Filtered search: the real-world wrinkle

Pure “find the 10 closest vectors” is rare. In practice you want “find the 10 closest vectors that also belong to this user / are newer than 2024 / have tag = ‘finance’.” Combining similarity with metadata filters is filtered (or hybrid) search, and doing it efficiently is genuinely hard:

Pre-filter (filter first, then search the survivors): exact, but if the filter is very selective the index can’t help much and you drift toward brute force on the survivors.
Post-filter (search first, then drop non-matching results): fast, but you might filter away most of your top-k and end up with too few results.

Mature databases blend these strategies. We dedicate Module 9 to it. For now, just know that filters complicate the clean “nearest neighbor” picture.

Hands-on: feel the scaling wall

import numpy as np, time

def make(n, d=768):
    v = np.random.randn(n, d).astype("float32")
    return v / np.linalg.norm(v, axis=1, keepdims=True)

q = make(1, 768)[0]
for n in [10_000, 100_000, 1_000_000]:
    vecs = make(n)
    t = time.time()
    scores = vecs @ q
    top = np.argsort(-scores)[:10]
    print(f"N={n:>9}: {1000*(time.time()-t):.1f} ms")

Watch the time grow roughly 10× each step. That linear wall is the reason the rest of this course exists.

Gotchas

Premature optimization. People build complex ANN indexes for 50k vectors. Don’t. Brute force or pgvector is simpler and exact. Add complexity only when measurements demand it.
Ignoring memory. Vectors are big. Estimate N × dim × 4 bytes early; it decides everything about your architecture.
No ground truth. If you never measure recall against exact search, you won’t know your approximate index is silently dropping good results.
Forgetting filters in your design. Teams build a beautiful pure-vector pipeline, then discover every real query needs “only this customer’s data.” Design filtering in from day one.

Check yourself

What does brute-force search guarantee, and what’s its fatal weakness?
Define recall@10 in your own words.
Why does brute force remain useful even after you adopt approximate indexes?
What’s the difference between pre-filtering and post-filtering?

Answers: (1) It guarantees 100% exact nearest neighbors, but its cost grows linearly with dataset size, so it’s too slow at large scale. (2) Of the 10 truly closest items, the fraction your search actually returned. (3) It provides the ground truth to measure recall, and it’s used to precisely re-rank a small candidate shortlist; it’s also fine for small datasets. (4) Pre-filter restricts the candidate set by metadata before the similarity search (exact but can be slow); post-filter searches first and drops non-matches after (fast but may return too few).

➡️ Next: 05-ann-indexes.md — the famous algorithms (HNSW, IVF, PQ, LSH) that beat the scaling wall.