Why Not Just Brute-Force Search? (ANN Intro)
Introduction
In Building a Semantic Search Engine from Scratch you built brute-force search — compare the query to every vector — and I left you with a warning: it won't scale. This lesson is the why, and the fix that powers every vector database: Approximate Nearest Neighbor (ANN) search.
Here's the deal ANN offers, and it sounds almost too good: give up a tiny sliver of accuracy, get a massive speedup. Searching 1 million vectors goes from ~750 ms (brute-force, too slow to ship) to ~10 ms (ANN) — while still finding 95–99% of the true matches. The mental shift this whole section turns on is realizing that approximate isn't a compromise — it's the smart choice.
In this lesson you'll learn:
- Why brute-force hits a wall (and exactly when)
- Why you don't need the exact answer for semantic search
- What ANN does — and the two big index families (preview)
- The recall ⇄ speed ⇄ memory tradeoff, and when brute-force is still fine
The Brute-Force Wall
Brute-force search (also called flat or exact search) is dead simple and 100% accurate: compute the distance from the query to every stored vector, sort, return the top-k. The problem isn't the math — it's doing it n times. Brute-force is O(n): cost grows linearly with your corpus.
Put real numbers on it. At 1 million 1536-dimension vectors, a single brute-force query takes roughly 750 ms on a modern CPU. That's already past a typical ~100 ms production latency budget — and it only gets worse:
| Corpus | Brute-force / query |
|---|---|
| 10K | ~8 ms (fine) |
| 1M | ~750 ms (too slow) |
| 10M | ~7.5 s (unusable) |
| 100M | ~75 s (hopeless) |
Every document you add makes every query slower, forever. You can't brute-force your way to a million-document knowledge base.
The Insight: You Don't Need the EXACT Answer
Before reaching for a fancier algorithm, sit with the key reframe — because it's why ANN is acceptable, not a hack:
In semantic search, the vectors are already approximations of meaning. The embedding is a lossy summary; cosine scores are fuzzy (recall anisotropy — unrelated things score 0.8); and in RAG you feed the top-k to an LLM that doesn't care whether it got the exact 10 best chunks or the 9 best + 1 near-best.
So paying O(n) for mathematically-exact nearest neighbors buys you precision you can't even perceive in the final answer. Returning almost all the true neighbors is, for retrieval, just as good — and vastly cheaper. That trade — a little recall for enormous speed — is the entire idea of ANN.
Approximate Nearest Neighbor (ANN)
ANN is the class of algorithms that find almost all of the true nearest neighbors without comparing against every vector. Instead of a flat scan, you build an index — a smart data structure, computed once — that lets each query skip most of the corpus and check only a small, promising fraction. The result is sub-linear (often near-logarithmic) search: 1M vectors → 5–20 ms at 95–99% recall, and it stays fast as you scale.
There are two dominant families (we go deep on both next lesson):
- Graph-based (HNSW) — build a graph linking each vector to its neighbors; a query navigates the graph, hopping closer and closer to the target, visiting only a tiny path of nodes. The most popular default.
- Partition-based (IVF) — divide the space into cells (clusters); a query only searches the few cells nearest to it, ignoring the rest.
Both share the same trick: don't look everywhere — look only where the answer probably is.
The Recall–Speed–Memory Triangle
ANN isn't one fixed thing — it's a tunable tradeoff between three quantities, and you set the dial:
- Recall — the fraction of the true nearest neighbors the index actually returns (your accuracy).
recall@10 = 0.95means it found 9.5 of the true top-10 on average. - Speed — query latency.
- Memory — the index itself takes RAM (on top of the vectors).
The primary knobs are ef_search (HNSW) and nprobe (IVF): turn them up and the query explores more of the index → higher recall, slower. Turn them down → faster, lower recall. Build-time knobs (M/ef_construction, nlist) trade memory and index-build time for quality.
Where to sit: the sweet spot for most RAG is ~90–95% recall — pushing from 95% to 99% can triple your latency for a quality gain you'll never notice. And remember the previous section: ANN + quantization combine — a compressed index uses far less of that precious RAM.
When Brute-Force Is Actually Fine
Don't reach for ANN reflexively — it adds an index to build, tune, and keep updated. For small corpora, brute-force is simpler, exact, and fast enough:
- Under ~10K–100K vectors, a flat scan (numpy, or FAISS
IndexFlat) returns in single-digit milliseconds with 100% recall — no tuning, no approximation. - Many real apps (a single product's docs, a personal knowledge base, a prototype) never outgrow this.
Reach for ANN when scale (millions of vectors) or latency (high QPS) forces it — which is exactly when a vector database (next lessons) earns its place. Rule of thumb: start flat; add an ANN index when the numbers demand it, not before.
See the Difference (Code)
FAISS makes the contrast concrete — the same search, exact vs ANN, with a one-line index swap:
import faiss, numpy as np, time
d, n = 768, 500_000
X = np.random.randn(n, d).astype('float32')
faiss.normalize_L2(X)
q = X[:1] # use an existing vector as the query
# --- EXACT (brute-force / flat) ---
flat = faiss.IndexFlatIP(d); flat.add(X) # inner product = cosine (normalized)
t = time.time(); flat.search(q, 10); print(f'flat: {(time.time()-t)*1000:.0f} ms') # ~slow, 100% recall
# --- APPROXIMATE (HNSW) ---
hnsw = faiss.IndexHNSWFlat(d, 32); hnsw.add(X) # build the ANN graph once
hnsw.hnsw.efSearch = 64 # the recall/speed knob
t = time.time(); hnsw.search(q, 10); print(f'hnsw: {(time.time()-t)*1000:.0f} ms') # ~10-100x fasterSame query, same results almost always — the HNSW index just skips the 99.99% of vectors that were never going to be the answer.
🧪 Try It Yourself
Drag the corpus size in the widget below and watch the two curves diverge:
- Brute-force climbs linearly — 750 ms at 1M, 7.5 s at 10M. It's a straight line to unusable.
- ANN stays flat in the milliseconds no matter how big the corpus gets.
That gap is the entire reason vector databases exist. Then a quick decision: you're building (a) a search over 5,000 internal docs, and (b) a search over 20 million product listings. Which needs ANN? → (b) — at 5K, brute-force is instant and exact, so keep it simple; at 20M, brute-force is ~15 s/query, so you need an ANN index. Match the tool to the scale.
Mental-Model Corrections
- "Approximate means inaccurate/worse." No — ANN hits 95–99% recall, and since embeddings already approximate meaning, the missing sliver is imperceptible in RAG. Approximate is the smart trade.
- "Brute-force is always too slow." Only at scale — under ~10K–100K vectors it's exact and fast. Don't add ANN before you need it.
- "ANN recall is fixed." It's tunable (
ef_search/nprobe) — dial recall against speed and memory. Sweet spot ~90–95%. - "The index is free." It costs RAM and build time — that's the third corner of the triangle (mitigated by quantization).
- "More recall is always better." Past ~95% you pay a lot of latency for almost no quality — a classic over-optimization.
Key Takeaways
- Brute-force (flat/exact) search is O(n) — 100% recall but linear: ~750 ms at 1M vectors, unusable beyond. Every doc you add slows every query.
- You don't need exact neighbors for semantic search — embeddings already approximate meaning, so approximate is smart, not a compromise.
- ANN builds an index to check only a promising fraction → sub-linear search (5–20 ms at 1M, 95–99% recall). Two families: graph (HNSW) and partition (IVF) (next lesson).
- It's a tunable triangle — recall ⇄ speed ⇄ memory (
ef_search/nprobe); sweet spot ~90–95% recall. ANN + quantization combine. - Start brute-force for small corpora (< ~10K–100K); add ANN (a vector database) when scale or latency demands it.