How HNSW and IVF actually work
Comparing a query to every single stored vector does not scale. HNSW and IVF trade a small amount of accuracy for a large amount of speed by being clever about which vectors get checked at all.
- 10 min read
- 3 reading levels
- Published
Read these first
On this page 5
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
Approximate nearest neighbour search finds vectors that are probably closest to your query. It never checks every single vector to be certain.
Picture a massive fair ground, packed with tens of thousands of people. You are looking for one friend. Checking every single face would work, eventually, but it would take hours. Instead, you ask someone at the entrance which section your friend was headed toward. You walk to that section and check faces only there. You might occasionally miss, if your friend wandered off somewhere else. But you find them in minutes instead of hours, almost every time.
Approximate nearest neighbour search (ANN) does this with vectors instead of people. Comparing your query's embedding against every single stored vector is called brute-force, or exact search. It always finds the true best matches, but gets painfully slow once you have millions of vectors. ANN structures like HNSW and IVF organise the vectors in advance instead. A search only ever has to check a small, promising slice of them.
Why it exists
Semantic search at real scale means comparing a query against millions, sometimes billions, of stored vectors. Brute-force comparison is simple and exact. Its cost grows directly with how many vectors you have — double the catalogue, double the search time, every single search. That does not scale to a real product.
ANN structures accept a small, controllable chance of missing the true best answer. In exchange, search times barely grow as the collection grows. In practice, that trade is almost always worth it. The difference between the 3rd-best match and the true best match rarely matters to a user. The difference between a 40-millisecond search and a 4-second one always does.
How it works
BRUTE FORCE IVF ("inverted file")
compare query against split all vectors into zones ("cells")
EVERY vector, one by one in advance, using k-means-like clustering
-> always exact at search time: check only the
-> gets slower as the few zones closest to the query
collection grows -> fast, misses a little at the edges
HNSW ("graph-based")
build a graph where each vector points to its nearby neighbours,
in layers -- coarse "highways" on top, fine local links below
at search time: start at the top layer, hop toward the query,
drop down a layer, repeat -- lands near the true answer in a
handful of hops instead of comparing against everythingBoth HNSW and IVF do their expensive organising work once, when vectors are added to the index. Every search afterward benefits from that one-time investment.
A real example you have seen
Reverse image search can return visually similar photos from a billion-image collection in under a second. It is not comparing your photo against a billion others, one at a time. An ANN index, built once over that whole collection, lets it check only a tiny, well-chosen slice.
Remember this
- Brute-force search is exact but slows down as the collection grows. ANN structures like HNSW and IVF stay fast at any scale, at the cost of occasionally missing the true best match.
- Both build an index once, ahead of time, so every search afterward is fast.
- The speed-versus-accuracy trade-off is tunable — you decide how much accuracy to trade for how much speed.
What to learn next
- FAISS — putting IVF and HNSW to work through the library that implements them.
- The curse of dimensionality — why high-dimensional distance behaves so differently from the 2D and 3D intuition most people start with.
- Vector databases — the systems built around exactly this kind of index.
Developer — Code and libraries.
Setup
pip install faiss-cpu numpyOutputs verified with faiss-cpu 1.14.3 and numpy 1.26.4 on CPU.
Brute force vs HNSW on 50,000 vectors
This uses random vectors at a scale small enough to run in seconds, but large enough to make brute force's cost visible.
import time
import numpy as np
import faiss
rng = np.random.default_rng(0)
n_vectors, dim, n_queries = 50_000, 384, 200
vectors = rng.standard_normal((n_vectors, dim)).astype("float32")
queries = rng.standard_normal((n_queries, dim)).astype("float32")
# --- brute force: compare every query against every vector ---
flat_index = faiss.IndexFlatL2(dim)
flat_index.add(vectors)
t0 = time.perf_counter()
_, exact_ids = flat_index.search(queries, 10)
brute_force_search_time = time.perf_counter() - t0
# --- HNSW: build a graph once, then search it ---
t0 = time.perf_counter()
hnsw_index = faiss.IndexHNSWFlat(dim, 32)
hnsw_index.hnsw.efConstruction = 100
hnsw_index.add(vectors)
hnsw_build_time = time.perf_counter() - t0
hnsw_index.hnsw.efSearch = 128
t0 = time.perf_counter()
_, hnsw_ids = hnsw_index.search(queries, 10)
hnsw_search_time = time.perf_counter() - t0
overlaps = [len(set(exact_ids[i]) & set(hnsw_ids[i])) for i in range(n_queries)]
recall_at_10 = sum(overlaps) / (n_queries * 10)
print(f"{n_vectors:,} vectors x {dim} dimensions, {n_queries} queries, top 10 each")
print(f"HNSW one-time build cost: {hnsw_build_time:.2f} s")
print(f"brute force search, {n_queries} queries: {brute_force_search_time*1000:.1f} ms total")
print(f"HNSW search, {n_queries} queries: {hnsw_search_time*1000:.1f} ms total")
print(f"average recall@10 vs the exact answer: {recall_at_10:.2%}")50,000 vectors x 384 dimensions, 200 queries, top 10 each HNSW one-time build cost: 1.44 s brute force search, 200 queries: 69.5 ms total HNSW search, 200 queries: 14.4 ms total average recall@10 vs the exact answer: 77.75%
Timings here are entirely dependent on the machine this ran on — treat the 1.44 s build time and the millisecond figures as illustrative, not universal numbers. What generalises is the shape of the result: roughly a 5x search speed-up, in exchange for finding about 78% of the true top-10 matches, plus one extra one-time cost to build the graph before any searching happens at all.
The walkthrough
Recall@10 of 77.75%, not 100%, is the honest headline here — and it is a harder case than most real embeddings. Random Gaussian vectors have no genuine cluster structure at all; every vector is, in a real sense, equally close to every other. That is closer to a worst case for ANN methods than real sentence or document embeddings, which usually sit on a far more structured, lower-dimensional manifold and are noticeably easier for HNSW to navigate accurately. Expect higher recall on real embeddings than shown here.
efConstruction and efSearch are the two knobs that trade speed for accuracy. efConstruction controls how thoroughly the graph is built (higher = slower build, better graph). efSearch controls how many candidates are explored per query at search time (higher = slower search, higher recall). Both were raised well above their defaults here specifically to make the recall respectable on this hard, structureless data.
Build time is a one-time cost, search time is paid on every query. 1.44 seconds to build the HNSW graph sounds expensive next to a 70-millisecond brute-force search — until you remember that cost is paid exactly once, while the per-query search savings compound over every future search against that same index.
Common mistakes
Judging ANN quality from one query. Recall varies from query to query. Always average over a representative batch, as done here, not a single lucky or unlucky example.
Leaving efSearch at a library's low default and concluding ANN "doesn't work." As the researcher block's numbers confirm, recall is highly sensitive to this parameter — a default tuned for speed on easy data can look disappointing on harder data until it is raised.
Forgetting the build cost when comparing timings. A fair comparison needs to account for the one-time index-build cost somewhere — usually amortised, since it happens once and every subsequent search benefits.
Try it yourself
Drop efSearch from 128 down to 16 and re-run. Expect a noticeably faster search, at a real cost to recall — a concrete look at the knob production systems tune constantly to hit their own speed and accuracy targets.
What to learn next
- FAISS — putting IVF and HNSW to work through the library that implements them.
- The curse of dimensionality — why high-dimensional distance behaves so differently from the 2D and 3D intuition most people start with.
- Vector databases — the systems built around exactly this kind of index.
Researcher — Mathematics and papers.
HNSW: Hierarchical Navigable Small World graphs
Malkov & Yashunin (2016, 2018) build a multi-layer proximity graph. Layer 0 contains every point; each higher layer contains a randomly-selected, exponentially shrinking subset, with the number of layers a point participates in drawn from an exponentially-decaying distribution controlling how "prominent" that point is in the graph's hierarchy.
Search proceeds greedily: starting from an entry point in the top (sparsest) layer, repeatedly move to the neighbour closest to the query until no neighbour improves the distance, then descend one layer and repeat, using the previous layer's result as the new starting point. This coarse-to-fine traversal is what gives HNSW its logarithmic-ish query complexity: the top layers act as long-range "highways" across the space, and lower layers refine the answer locally — directly mirroring the beginner block's "ask at the entrance, then search locally" analogy.
Construction cost is approximately O(n log n); query cost is approximately O(log n) per search, both empirically, under reasonable assumptions about the data's intrinsic dimensionality. M (the 32 in IndexHNSWFlat(dim, 32)) sets how many neighbours each node keeps per layer, directly trading index memory and build time against graph connectivity and recall.
IVF: Inverted File Index
IVF (Sivic & Zisserman, 2003, applied to nearest-neighbour search; refined for large-scale use by Jégou, Douze & Schmid, 2011) partitions the vector space into nlist Voronoi cells via k-means clustering, run once at index build time. Each vector is assigned to its nearest cell centroid. A query first identifies the nprobe closest cell centroids to itself, then performs exact (or further-approximated) search only within the vectors assigned to those cells.
This gives a direct, explicit accuracy-speed knob: nprobe=1 searches a single cell (fast, high risk of missing true neighbours near a cell boundary); nprobe=nlist degenerates to brute force (searching every cell, exhaustively). The FAISS lesson demonstrates this trade-off in the library's actual API, alongside quantifying the exact speed-recall curve on the same synthetic data used here.
Why random vectors are a harder case than real embeddings
The curse of dimensionality, covered directly in The curse of dimensionality, shows that in high-dimensional space with no intrinsic low-dimensional structure, the ratio between nearest and farthest neighbour distances tends toward 1 — every point becomes almost equally close to every other. Real embeddings from a trained encoder are not distributed this way: they concentrate on a much lower-dimensional manifold reflecting genuine semantic structure, which both HNSW's graph and IVF's clustering can exploit far more effectively than they can on structureless random data. Published ANN benchmarks on real embedding datasets (see ann-benchmarks.com) consistently report recall well above 95% at comparable or better speedups than shown in the developer block above.
Key references
- Malkov, Y. & Yashunin, D. (2016, revised 2018). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. arXiv:1603.09320
- Jégou, H., Douze, M. & Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE TPAMI 33(1).
- Aumüller, M., Bernhardsson, E. & Faithfull, A. (2020). ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. Information Systems 87.
Current state
HNSW is the dominant choice in most current vector databases for its strong recall-per-millisecond on real embedding data, at the cost of relatively high memory use (the full graph must typically stay resident). IVF, especially combined with product quantization for compressed storage, remains preferred at very large scale where memory, not query latency, is the binding constraint. Most production vector search libraries, FAISS included, support both and hybrids of the two directly.
What to learn next
- FAISS — putting IVF and HNSW to work through the library that implements them.
- The curse of dimensionality — why high-dimensional distance behaves so differently from the 2D and 3D intuition most people start with.
- Vector databases — the systems built around exactly this kind of index.