Dense retrieval needs the passage vectors that are closest to the question vector. Approximate nearest-neighbour (ANN) search finds them in milliseconds by accepting an occasional miss.
Why exact search is too slow
Exact search compares the question with every passage vector, so the cost is for vectors of numbers.
- with passages and , one query needs about multiply-adds
- the vectors need bytes, which is about 30.7 GB of memory
Introduction
ANN search returns vectors that are very probably the closest, for 100 to 1000 times less work. Its quality is measured by recall: the fraction of the true nearest neighbours that were found (which is the amount of true nearest neighbours we got right).
Remembering tip
Think of a library. Cluster means only walking to the shelves on the right topic, compress means keeping a short catalogue card instead of the whole book, and navigate means following signposts from hall to section to shelf.
| Idea | Method |
|---|---|
| Cluster | Inverted File Index (IVF) |
| Compress | Product Quantisation (PQ) |
| Navigate | Hierarchical Navigable Small World (HNSW) |
Choosing an index
| Index | Recall | Query speed | Memory | Typical use |
|---|---|---|---|---|
| Flat (exact) | 100% | Slow, | High | Under 1M vectors, and ground truth for testing other indexes |
| IVF | High (tunable) | Fast | High | Large collections that are rebuilt in batches |
| IVF-PQ | Medium to high | Very fast | Very low | Billions of vectors or tight memory |
| HNSW | Very high | Very fast | High (graph links) | Low-latency serving with frequent inserts |
Rule of thumb:
- start with HNSW for low-latency serving
- move to IVF-PQ when memory is the constraint
- always measure recall on your own data before committing
Code
The exact index is the ground truth that the other indexes are compared against:
import faiss
d = 64
flat = faiss.IndexFlatL2(d) # exact search, compares with every vector
flat.add(xb) # xb is a float32 array of shape (N, d)
distances, true_nn = flat.search(xq, 10) # the 10 nearest neighbours of each query in xqNotes:
faissneedsfloat32arrays- recall@10 of another index is the fraction of the ids in
true_nnthat it also returns IndexFlatL2uses Euclidean distance, and for unit vectors this gives the same ranking as cosine similarity