Exact vs approximate search

Once you can embed text, the next problem is retrieval at scale: given a query vector, find the k closest vectors among millions or billions. Exact search works until it doesn't. Approximate indexes trade a little recall for orders-of-magnitude latency and cost wins.

Think of the vector database as a specialized index you query with coordinates instead of keywords. The embedding model chooses the coordinate system. The ANN index chooses how aggressively to approximate neighborhoods. Mixing those concerns — blaming "Pinecone" for a bad embedder, or retuning HNSW when chunks are garbage — wastes calendar time.

Exact search is still useful

Before reaching for HNSW, know when brute force wins. Flat (exact) search is:

• Trivial to implement correctly (a matrix multiply of normalized vectors).
• Perfect recall — essential for building the ground-truth neighbor sets you use to measure ANN recall.
• Often fast enough below ~100k–300k vectors at moderate QPS on a single machine, especially at 384 dims.

Many teams ship the first RAG demo with NumPy or FAISS IndexFlatIP, then add HNSW when latency or CPU graphs complain. Skipping that step means you never know whether quality bugs are from embeddings or from approximation.

Why ANN exists

Exact search over N vectors of dimension d costs O(N · d) distance computations per query.

N = 10,000,000 vectors
d = 1,024
ops ≈ 10M × 1,024 = 1.024e10 floating-point ops per query

Even at a generous 50 GFLOP/s effective on one core, that is ~200 ms of pure math,
before memory bandwidth. At hundreds of QPS you need a machine room — or an ANN index.

ANN targets high recall@k (fraction of true top-k neighbors returned) at low latency and bounded memory. Typical production goals: recall@10 ≥ 0.95, p95 latency under 20–50 ms, including filters.

def recall_at_k(exact_ids, ann_ids, k=10):
    """Fraction of the true top-k that ANN also returned."""
    truth = set(exact_ids[:k])
    hits = truth.intersection(ann_ids[:k])
    return len(hits) / k


print(recall_at_k([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 2, 3, 4, 5, 6, 7, 8, 99, 98]))

Output:

0.8

Eight of the ten true neighbors came back. That is recall@10 = 0.80 — below a 0.95 production bar. Raise the search budget or fix the index before you blame the LLM.

Common mistakes

• Jumping to ANN before you have an exact ground-truth set, so you cannot measure recall.
• Blaming the vector store when the embedder or the chunks are the real bug.
• Tuning on vibes instead of recall@k versus latency on held-out queries.

Check yourself

1. Why is 10M × 1,024 exact search about 200 ms on one generous core? 10M × 1,024 ≈ 1.024e10 ops. At 50 GFLOP/s that is about 200 ms of math, before memory.
2. You have no exact neighbor set. Can you say HNSW recall is 0.96? No. Recall is measured against exact top-k, so you need a flat-search ground truth first.

Key takeaways

• Exact kNN is O(N · d). It is the right default until about 100k–300k vectors.
• ANN buys latency with a recall trade-off you must measure.
• Build ground-truth neighbors with exact search, then tune ANN against them.
• Typical bar: recall@10 ≥ 0.95 at p95 under 20–50 ms.

Further learning

Embeddings and vector similarity. Next, the default ANN index: HNSW.