Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 36 ยท Indexing and ANN Search

Exact Search, ANN and the Recall Tradeoff

Learn brute-force vector search, why it stops scaling, what approximate nearest neighbor (ANN) search trades away, and how to measure recall against exact results.

Searching vectors sounds simple: compare the query to every stored vector and keep the best few. That is exact nearest-neighbor search, also called brute force or a flat index. It is perfectly accurate and, for small collections, it is also the best choice. The trouble is cost: every query touches every vector, so doubling your data doubles your latency.

Approximate nearest neighbor (ANN) search gives up a little accuracy to answer in a tiny fraction of the time. This chapter covers the index families that make it work (graphs, clusters, hashing, compression). This first lesson sets the vocabulary and the one metric you will use throughout: recall.

Exact search with NumPy

For unit-length vectors, scoring every document against a query is one matrix multiplication. Taking the top k is a partial sort.

Python A flat (brute force) index

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

That is about 6.4 million multiply-adds per query. Modern CPUs and GPUs do this in milliseconds, so a flat index is fine up to a few hundred thousand vectors. Beyond that, the linear growth hurts:

Vectors Multiply-adds per query (768 dims)
100 thousand 77 million
10 million 7.7 billion
1 billion 770 billion

A system serving many queries per second cannot do this for every query on a big collection. We need to look at only a small part of the data, and that means accepting that sometimes the true nearest neighbor is not inspected.

What "approximate" means

An ANN index returns the k results it believes are nearest. Usually they are exactly right, occasionally one is missing and replaced by the 11th best. We measure that with recall@k:

recall@k = (number of the true top-k found by the ANN search) / k

If the exact top 10 are A to J and the index returns A to I plus Z, recall@10 is 0.9. You average over many queries to get the recall of the index.

flowchart LR
    Q["Query"] --> E["Exact search (flat): slow, recall 1.0"]
    Q --> A["ANN index: fast, recall 0.95-0.99"]
    E --> T["True top-k"]
    A --> R["Returned top-k"]
    T --> C["recall@k = overlap / k"]
    R --> C

Recall compares the ANN result against the exact one on the same queries.

Two things to remember:

  • Recall is only about the index. It says nothing about whether the true nearest neighbor was the right answer to the user's question. That is a retrieval metric measured against labelled questions. First make sure the embeddings are good, then make sure the index does not lose much on top of them.
  • In RAG, a recall of 0.95 to 0.99 against exact search is usually invisible in the final answer quality, because top-k contains slack and rerankers fix ordering. Spending 10 times more compute for the last 1% is rarely worth it.

A toy ANN: scan only part of the data

The simplest possible approximate search looks at a random fraction of the vectors. It is fast and wrong in a very clear way, so it shows the speed-versus-recall tradeoff cleanly.

Python Recall of a scan-a-fraction toy index

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Recall grows roughly in proportion to the fraction scanned, which is a terrible deal: you lose accuracy exactly as fast as you save time. Real ANN indexes get the best of both by choosing which 1% to look at: the part of the space where the query lives. They differ in how they decide.

The families of ANN indexes

Family Idea Examples
Graph Connect each vector to near neighbors, then walk the graph toward the query HNSW, DiskANN, Vamana
Partition (clusters) Split space into regions; search only the closest regions IVF, k-d trees (low dimensions)
Hashing Similar vectors collide in the same bucket LSH
Compression Store small codes and compare approximate distances PQ, scalar and binary quantisation

They combine: a very common production index is IVF + PQ (clusters plus compression), and HNSW is often combined with quantised vectors.

Trees and the dimension problem

Classic spatial trees (k-d trees) work wonderfully in 2 to 10 dimensions and degrade in high dimensions, because of the distance concentration you saw earlier: nearly every branch could contain a near neighbor, so the tree cannot prune. SciPy's k-d tree has an eps setting that makes the search approximate: any returned neighbor is within (1 + eps) times the true nearest distance. Look at what that buys on clustered 16-dimensional data.

Python Approximate search with a k-d tree (eps)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On this data recall stays at 1.0 up to eps 0.5, then falls to 0.76 at eps 3. Increasing eps lets the tree skip branches that might hold a slightly closer point, which makes searches faster and recall lower. Every ANN index exposes a similar dial, with a different name: ef_search in HNSW, nprobe in IVF. Turning it trades speed for recall, and finding the right setting is the subject of index tuning.

The three-way tradeoff

Every index sits somewhere among three costs:

  • Recall: how much of the true top-k it returns.
  • Latency / throughput: how fast it answers.
  • Memory and build time: how big the index is and how long it takes to build or update.

You cannot maximise all three. Graph indexes give excellent recall and speed but use plenty of RAM; compression shrinks memory but lowers recall; clustering builds quickly and updates easily. The right choice depends on your data size, hardware and how often data changes.

When to skip ANN entirely

  • Under roughly 100,000 vectors, a flat index is often fast enough and has perfect recall with zero tuning.
  • If you filter heavily by metadata so that only a few thousand vectors remain per query, a flat scan over the filtered set can beat an ANN index.
  • During development and for building ground truth in evaluation, always use exact search as the reference.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is recall@k for an ANN index?

    Recall@k compares the ANN top-k with the exact top-k: overlap divided by k.
  2. 2. Why does brute-force search stop scaling?

    A flat scan touches all n vectors per query, so 100 times more data means 100 times more work.
  3. 3. Which is a reasonable choice for 50,000 vectors and a tolerance for simplicity?

    At this size an exact scan takes milliseconds, has perfect recall and needs no tuning.
  4. 4. What does raising the eps value of an approximate k-d tree query typically do?

    A larger eps lets the search prune more aggressively, accepting slightly farther neighbors.
  5. 5. A recall@10 of 0.97 against exact search means:

    Recall measures index fidelity to exact search, not answer quality.

Summary

  • Exact (flat) search is simple and perfectly accurate, but its cost grows linearly with the data.
  • ANN search inspects a small, well-chosen part of the data and accepts occasional misses.
  • Recall@k against exact search is the standard way to measure what an index loses.
  • Index families: graph, partition, hashing and compression, often combined.
  • Every index has a speed-versus-recall dial; small collections often need no ANN at all.

Next: HNSW: Navigating a Graph of Neighbors