# Approximate Search: IVF and HNSW — Embeddings & Vector Search

Source: https://www.geekswithgeeks.com/en/embeddings/s-ann

> Understand the two most common index families and their recall knobs.

## Skip most of the data on purpose

For millions of vectors, scanning everything is too slow, so **approximate nearest neighbour (ANN)** indexes avoid looking at most of the data. **IVF (inverted file)** clusters the vectors into `nlist` cells with k-means; a query looks only in the `nprobe` closest cells. **HNSW (hierarchical navigable small world)** builds a layered graph in which each vector links to near neighbours; a query walks the graph greedily toward the target, and `efSearch` controls how many candidates it keeps while walking. Both give **recall below 100%**: the true nearest neighbour is sometimes missed. Increasing `nprobe` or `efSearch` raises recall and latency together, so you **tune on your data** to the recall you need. IVF needs a **training** step and uses less memory; HNSW has no training, is very fast and accurate, but uses more memory and supports updates less cheaply.

## Recall versus search effort, run

I ran this in a Python virtual environment with numpy 2.5.3, scikit-learn 1.9.1 and faiss-cpu 1.15.1, with fixed random seeds so the numbers repeat. On 20,000 clustered 64-dimension vectors, IVF with 100 cells reaches 0.743 recall@10 when probing 1 cell, 0.998 with 4 and 1.000 with 16. HNSW goes from 0.643 at efSearch=4 to 0.932 at 16 and 1.000 at 64. Recall is measured against the exact flat-index answers. Latency is not shown because timings vary by machine.

```python
import numpy as np, faiss
rng = np.random.default_rng(0)
d, n, nq = 64, 20000, 200
centers = rng.normal(size=(50, d)) * 3
xb = (centers[rng.integers(0, 50, n)] + rng.normal(size=(n, d))).astype("float32")
xq = (centers[rng.integers(0, 50, nq)] + rng.normal(size=(nq, d))).astype("float32")

flat = faiss.IndexFlatL2(d); flat.add(xb)
_, truth = flat.search(xq, 10)                                   # exact answers

def recall(found): return float(np.mean([len(set(f) & set(t)) / 10 for f, t in zip(found, truth)]))

ivf = faiss.IndexIVFFlat(faiss.IndexFlatL2(d), d, 100); ivf.train(xb); ivf.add(xb)
for nprobe in (1, 4, 16):
    ivf.nprobe = nprobe
    print(f"IVF  nprobe={nprobe:2d} recall@10 = {recall(ivf.search(xq, 10)[1]):.3f}")

hnsw = faiss.IndexHNSWFlat(d, 16); hnsw.hnsw.efConstruction = 100; hnsw.add(xb)
for ef in (4, 16, 64):
    hnsw.hnsw.efSearch = ef
    print(f"HNSW efSearch={ef:2d} recall@10 = {recall(hnsw.search(xq, 10)[1]):.3f}")

```

Output:

```
IVF  nprobe= 1 recall@10 = 0.743
IVF  nprobe= 4 recall@10 = 0.998
IVF  nprobe=16 recall@10 = 1.000
HNSW efSearch= 4 recall@10 = 0.643
HNSW efSearch=16 recall@10 = 0.932
HNSW efSearch=64 recall@10 = 1.000
```

## Tune against exact answers

Compute recall@k of your ANN index against a flat index on a sample of real queries. Pick the cheapest setting that meets your target.

**Quiz:** What does raising nprobe (IVF) or efSearch (HNSW) do?

- [x] Raises recall and also latency
- [ ] Lowers both recall and latency
- [ ] Changes the embedding model
- [ ] Deletes vectors

*Answer:* Raises recall and also latency. More search effort finds more true neighbours but takes longer.