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.

Choosing an index

IndexRecallQuery speedMemoryTypical use
Flat (exact)100%Slow, HighUnder 1M vectors, and ground truth for testing other indexes
IVFHigh (tunable)FastHighLarge collections that are rebuilt in batches
IVF-PQMedium to highVery fastVery lowBillions of vectors or tight memory
HNSWVery highVery fastHigh (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 xq

Notes:

  • faiss needs float32 arrays
  • recall@10 of another index is the fraction of the ids in true_nn that it also returns
  • IndexFlatL2 uses Euclidean distance, and for unit vectors this gives the same ranking as cosine similarity