Vector Indexing & Similarity Search: HNSW vs IVF
Somewhere between 100,000 and 5 million vectors, a search feature that used to feel instant starts feeling off. Not broken, exactly. Latency's fine, error rate is zero, nothing's on fire. The results are just a bit worse, and nobody can point to why.
Here's why: your index is doing exactly what it was configured to do, return approximate answers. Somebody decided how approximate, whether they meant to or not. Usually it was whoever left the defaults alone.
This is about what happens inside a vector index, mainly HNSW, and what the speed-versus-accuracy trade costs in real numbers instead of vague adjectives like "a bit slower." Assuming you already have embeddings sitting in a vector store, this covers what happens between a query arriving and the top-k coming back.
Why exact search falls apart at scale
Brute-force k-NN (exact or flat search) compares your query against every stored vector and returns the k closest. Perfectly accurate. Also linear in the number of vectors, and it never gets faster no matter how clever your code is.
Let's do the arithmetic nobody bothers with. A million vectors at 768 dimensions in float32 (a common output size for embedding models) is 1,000,000 x 768 x 4 bytes, about 3.07 GB. Every query has to touch all of it.
Here's the part people miss: exact search is bottlenecked by memory bandwidth, not compute. Dot products are cheap, reading 3 gigabytes off memory is not. At a realistic ~50 GB/s of sustained bandwidth, the floor for one query is roughly 3.07 / 50 ≈ 61 milliseconds, before any actual math happens. That's set by physics, not your code, so no amount of optimizing gets you under it.
It scales the way you'd fear:
| Vectors (768-dim) | Data read per query | Latency floor @ 50 GB/s |
|---|---|---|
| 10,000 | 30.7 MB | ~0.6 ms |
| 100,000 | 307 MB | ~6 ms |
| 1,000,000 | 3.07 GB | ~61 ms |
| 10,000,000 | 30.7 GB | ~614 ms |
| 100,000,000 | 307 GB | won't fit in RAM on most machines |
At 61 ms a query, one core handles about 16 queries per second. Hitting 500 QPS needs roughly 31 cores doing nothing but distance math. A well-tuned HNSW index answers the same query in 1 to 2 ms, so one core pushes 500 to 1,000 QPS. Not a "nice speed bump", a 30x difference in how many servers you're renting.
(Numbers assume 768-dim float32 vectors and ~50 GB/s bandwidth on a single socket. Your hardware will vary, this is illustrative, not a benchmark.)
Quick honesty check: below roughly 10,000 vectors, don't bother with an index. A flat scan is sub-millisecond, perfectly accurate, needs no build step, and handles inserts and deletes without drama. Building an HNSW graph over 5,000 vectors solves a problem you don't have.
What an index does, and what "approximate" means
A vector index is a data structure that lets you find approximate nearest neighbors without touching every stored vector. It pre-computes some structure, a graph, a clustering, a compressed encoding, so a query only has to look at a small slice of the data.
Quick clarification: the index is the data structure, the database is the product wrapped around it (storage, filtering, an API, persistence). One database can offer several index types. FAISS is just a library of indexes with no database attached.
Every ANN index does the same basic trick, it refuses to look at most of your data. Graphs skip vectors by walking toward the answer, clustering skips whole regions, quantization skips precision instead of vectors. The differences are in what gets skipped and what it costs.
Recall@k is the number this whole article hinges on. It's the fraction of the true k nearest neighbors your index returned. True top-10 is IDs 1 through 10, your index gives you 9 of them plus one impostor, that's recall@10 = 0.9.
Important nuance: recall is a property of your configuration on your data. HNSW doesn't "have" 95% recall, HNSW at M=16, efSearch=64, on this specific corpus, has some measured recall. Different corpus, different number.
What does losing 5% actually mean for a user? Usually, not much. The swapped-out item is almost never a random document, it's typically the 11th or 12th nearest neighbor, a rounding error away from the 10th. To a human or an LLM reading retrieved context, that's often invisible.
Where it does matter: dedup and near-duplicate detection, legal or medical retrieval where a missed document is a real failure, small k (one miss is the whole result), and eval harnesses comparing against a fixed gold set.
One tip: if you retrieve 50 and rerank down to 10, it's recall@50 that matters, and hitting 0.99 there is a lot easier than at recall@10. Plenty of teams tune the wrong number.
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreThe six index families, side by side
Everything you'll meet in production is one of these six, or a variant.
| Index | How it works | Query speed | Memory (1M x 768-dim) | Recall | Updates? |
|---|---|---|---|---|---|
| Flat (exact) | Compares against everything | Slowest (~61 ms @ 1M) | 3.07 GB | 1.0, by definition | Trivial |
| IVF | k-means cells, scan only the nearest few | Fast, tunable | ~3.1 GB | ~0.55-0.99 | Poorly, needs retraining |
| IVF-PQ | IVF cells + compressed codes | Very fast | ~100-300 MB | ~0.70-0.90 raw | Same as IVF |
| HNSW | Multi-layer navigable graph | Fastest in-memory (~1-2 ms @ 1M) | ~3.2 GB | Highest, ~0.99+ | Yes, native |
| ScaNN | Ranking-aware quantization | Very fast, top QPS | Comparable to IVF-PQ | Very high for its size | Weakly |
| DiskANN | Graph on SSD, codes in RAM | Moderate (~2-10 ms) | ~1 GB RAM + SSD | High, >0.95 at scale | Yes, streaming variants |
Read it this way: HNSW buys speed by spending memory. IVF buys memory by spending recall stability. PQ buys memory by spending precision, then buys some of it back with reranking. DiskANN buys memory by spending latency. Nothing here is free, that's the whole subject of this article.
HNSW: Hierarchical Navigable Small World
That's the full name, and it's worth knowing because it's what half the search traffic around this topic is actually looking for.
HNSW is an ANN algorithm built around a multi-layer graph. Each vector is a node, connected to its nearest neighbors. A search starts at a sparse top layer that covers long distances in a few hops, then descends into progressively denser layers to refine the answer.
Quick answer to something people mix up: ANN (approximate nearest neighbor) is the problem, HNSW is one algorithm that solves it. IVF and ScaNN are others, not rivals in the way it sounds, just different answers to the same question.
The algorithm comes from Malkov and Yashunin's 2016 paper, readable as far as these things go.
The layered graph, walked step by step
Think of a skip list, express lanes cover long distances fast, then you drop into the local lane for precision. HNSW does this in high-dimensional space: the top layer has very few nodes with long edges, each layer down gets denser with shorter edges, and layer 0 holds every vector.
1. Enter at a fixed point in the top layer.
2. Greedily move to whichever neighbor is closer, repeat till nothing improves.
3. Drop a layer, starting from wherever you stopped.
4. Repeat on shorter edges in a denser graph.
5. At layer 0, keep a candidate list (size efSearch) instead of one best node, so the search explores sideways.
6. Return the best k from that list.
Here's the honest part: greedy walks sometimes land in a local minimum, ending up somewhere decent but not optimal, and the true nearest neighbor never gets visited. That's the entire source of HNSW's recall loss. Every parameter below is insurance against this happening.
Fun fact: which layer a node lands on is picked randomly, with exponentially decaying odds. Most vectors only exist at layer 0, a handful get lucky and reach the top. No balancing step involved, it just works.
M, efConstruction, efSearch (the three knobs)
M is the max edges per node per layer (layer 0 allows up to 2M). Common range 8 to 64, 16 is the usual default. Higher M means fewer local minima and a higher recall ceiling, but costs memory permanently, roughly N x 2M x 4 bytes for layer 0's edges.
| M | Graph memory @ 1M | Build time | Recall@10 (efSearch=64) |
|---|---|---|---|
| 8 | ~64 MB | 1.0x | ~0.90 |
| 16 (default) | ~128 MB | ~1.6x | ~0.96 |
| 32 | ~256 MB | ~2.8x | ~0.98 |
| 64 | ~512 MB | ~5x | ~0.99 |
Rule of thumb: M is the one parameter you can't change without a full rebuild, so pick it deliberately. Start at 16, only go higher if raising efSearch alone can't hit your target. Jumping straight to 64 is almost always a bad trade, 4x the memory for the last percentage point.
efConstruction controls how hard the index works while being built, the candidate list size during construction. Typical 100-500, default around 200. Raising it makes every future query a bit better, and costs build time only, no extra latency, no extra memory.
Pay-once framing: if your build fits in the maintenance window, just raise efConstruction. Spend 20 extra minutes building, get a permanently better recall curve. Most teams skip this and then wonder why efSearch alone isn't cutting it.
efSearch is the one you actually get to play with at runtime, per query, with no rebuild required. Recall rises with it, roughly monotonically. Latency rises too, roughly linearly.
Setup: 1M vectors, 768-dim, cosine, M=16, efConstruction=200, k=10, single thread.
| efSearch | Recall@10 | Latency (ms) | QPS (single thread) |
|---|---|---|---|
| 10 | ~0.72 | ~0.35 | ~2,900 |
| 32 | ~0.91 | ~0.70 | ~1,400 |
| 64 | ~0.96 | ~1.1 | ~900 |
| 128 | ~0.985 | ~1.9 | ~530 |
| 256 | ~0.995 | ~3.4 | ~290 |
| Flat (exact) | 1.000 | ~61 | ~16 |
Two things worth remembering: getting from recall 0.91 to 0.995 costs roughly 5x the latency, the last half-percent costs more than the first 91% did. And going from exact search to recall 0.96 costs you about 4% of your true neighbors and buys a 55x speedup. That's the actual exchange rate, and it's why approximate search won.
(Illustrative numbers, verify on your own hardware. The shape of the curve, steep rise then a long flat tail, holds pretty universally, the exact numbers won't. Check ann-benchmarks for published comparisons.)
Different tools name these knobs slightly differently, which trips people up:
| Concept | FAISS / hnswlib | pgvector | Qdrant |
|---|---|---|---|
| Connections per node | M | m | m |
| Build-time breadth | efConstruction | ef_construction | ef_construct |
| Query-time breadth | efSearch | hnsw.ef_search | hnsw_ef |
Small thing worth knowing: in pgvector, hnsw.ef_search is a session-level setting, so you can run a high-recall path for one endpoint and a fast path for another against the exact same index. Barely anyone uses this.
IVF: the inverted file index
Quick note: don't search "IVF" alone on Google, it means in-vitro fertilization to basically the entire internet. We'll say "inverted file index" here, for everyone's sanity.
It partitions your vector space into cells using k-means. Every vector gets assigned to its nearest centroid. A query is compared against the centroids first, then searched exhaustively within just the closest few cells, skipping the rest entirely.
Unlike HNSW, it needs a training step first, running k-means over a sample to produce nlist centroids. FAISS's own guidance puts nlist between 4x√N and 16x√N. For a million vectors that's 4,000 to 16,000, commonly rounded to 4,096 or 16,384. Too few cells and you gain nothing; too many and each cell can't cluster meaningfully.
nprobe is the runtime dial, how many nearest cells to actually search. With N=1,000,000 and nlist=4,096, each cell averages ~244 vectors. At nprobe=16, that's 4,096 centroid comparisons plus 16 x 244 ≈ 3,900 vector comparisons, about 8,000 total instead of a million. A 125x reduction.
| nprobe | Vectors compared | Recall@10 | Latency (ms) |
|---|---|---|---|
| 1 | ~244 | ~0.55 | ~0.3 |
| 16 | ~3,900 | ~0.92 | ~1.3 |
| 64 | ~15,600 | ~0.98 | ~4.5 |
| 4,096 (= nlist) | 1,000,000 | 1.000 | ~61 (= exact) |
Neat property nobody points out enough: set nprobe equal to nlist and you've turned the inverted file index into exact search. It's a continuous dial from fast-and-approximate to slow-and-perfect.
Recall loss here comes from cell boundaries, arbitrary lines k-means drew. Your query can land near an edge, and the true nearest neighbor sits just across it, in a cell you never probed. No cleverness inside the probed cells fixes that.
On updates: inserts look cheap (assign to nearest centroid, append), but centroids were trained on old data. New vectors pile unevenly into a few cells as the data shifts, and recall quietly degrades. Fixing it means retraining k-means and reassigning everything, basically a rebuild.
HNSW inserts using the same algorithm it built with, so quality doesn't drift. Its weak spot is deletes, tombstoned and needing periodic compaction. Rough rule: high write volume, go HNSW; large static corpora, the inverted file index is fine.
Product quantization: fitting billions of vectors in RAM
HNSW and IVF both cut how many vectors you compare. Neither shrinks the vectors themselves. At 100 million vectors x 768 dims x 4 bytes, that's 307 GB, you run out of RAM before you run out of speed. Quantization attacks that other axis.
The mechanism, from Jégou, Douze and Schmid's 2011 paper:
7. Split each vector into m subvectors (d=768, m=96 gives 8-dim chunks).
8. Run k-means independently per subspace, 256 centroids each (256 = 2^8, one byte per ID).
9. Replace each subvector with its nearest centroid ID. A 768-dim vector becomes 96 bytes.
10. At query time, build a lookup table of distances from the query to each subspace's centroids, then score candidates with table lookups instead of floating-point math. Query stays full-precision, only stored vectors get compressed, preserving far more accuracy than compressing both sides.
Compression ratio is 32d / (m x nbits). At d=768, m=96, nbits=8, that's 32x compression.
| Configuration | Bytes/vector | Size @ 1M | Recall (raw) | Recall (rerank top-100) |
|---|---|---|---|---|
| Flat float32 | 3,072 | 3.07 GB | 1.000 | - |
| SQ8 (int8) | 768 | 768 MB | ~0.97 | ~0.995 |
| PQ96 | 96 | 96 MB | ~0.72 | ~0.95 |
| PQ48 | 48 | 48 MB | ~0.55 | ~0.88 |
100 million vectors going from 307 GB (needs a cluster) to under 10 GB (fits on a laptop) is why billion-scale vector search exists as a product category.
Most teams don't need full PQ, though. Scalar quantization (SQ8, float32 to int8) gets a straightforward 4x reduction at a recall cost within noise, no codebooks, no tuning. Try that first, reach for PQ when 4x isn't enough.
The single most underused trick here is reranking: retrieve a generous candidate set (top 100 instead of 10) using the compressed index, fetch full-precision vectors for just those 100, rescore exactly, return the true top 10. You're paying for 100 exact comparisons, not a million, and it drags PQ96 from ~0.72 recall up to ~0.95. FAISS calls this refinement, Qdrant calls it rescoring.
One warning: this only works if you kept the original full-precision vectors. Quantize and delete them and you can't rerank, ever, without re-embedding the whole corpus. Keep the originals.
ScaNN and DiskANN, briefly
Two bets on which primitive to lean on hardest.
ScaNN (Google Research) uses anisotropic quantization, meaning it weights compression error by how much it actually affects the ranking, rather than treating every direction of error equally. Result: better recall per byte than plain PQ, top-tier QPS, CPU-only. Trade-off: more build-oriented, narrower ecosystem than FAISS or HNSW.
DiskANN (Microsoft Research) keeps full vectors on SSD and compressed codes in RAM, using a graph with deliberately long-range edges (the Vamana graph) to keep hop counts low. Published claim: a billion points on one node with ~64 GB RAM, over 95% recall, single-digit millisecond latency. Trade: latency rises from ~1 ms to ~2-10 ms, RAM per vector drops by roughly 10x. Given how much cheaper SSD is than RAM, that's usually a good deal.
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreCosine, dot product, Euclidean: does it matter which one you pick?
Sometimes, yes. Often, no. Here's the identity almost nobody states plainly: for unit-length vectors, L2(a,b)^2 = 2 - 2*cos(a,b), and dot(a,b) = cos(a,b). For normalized vectors, all three produce the same ranking. Scores differ, order doesn't. Dot product is cheapest to compute since there's no norm to calculate.
It matters when vectors aren't normalized, and plenty aren't (check the model card, don't assume). Run dot product on unnormalized vectors and longer documents, which tend to have bigger norms, will systematically outrank shorter, more relevant ones. Looks exactly like a relevance bug. Is actually a magnitude bug.
The rule that overrides everything: use whatever metric the embedding model was trained and evaluated on. Mismatch it and you'll lose more result quality than any parameter in this article could fix.
How to actually choose an index
Honest default: start with HNSW at M=16, efConstruction=200, efSearch=64. Measure. Only change things when a measurement tells you to, premature tuning is far more common than the opposite problem.
By size. Under 10k vectors, flat. 10k-1M, HNSW. 1M-10M, HNSW with SQ8 if RAM's tight. 10M-100M, IVF-PQ or DiskANN. Past 100M, DiskANN or sharded IVF-PQ.
By update pattern. Constant writes, HNSW. Batch updates, anything works. Static corpus, ScaNN or IVF-PQ. Heavy deletes on HNSW, schedule compaction.
By memory. RAM roughly equals N x (bytes per vector + graph or centroid overhead). At 10M vectors: HNSW float32 is ~32 GB, HNSW + SQ8 is ~9 GB, IVF-PQ96 is ~1-2 GB, DiskANN is ~1 GB RAM plus ~30 GB SSD. Memory is what actually drives your cloud bill, swinging 30x across options while latency swings less than 10x. Optimize memory first.
By recall need. Need 0.99+? HNSW at high efSearch, or flat, or quantization with reranking. Fine with ~0.95 (most RAG)? HNSW at defaults, stop tuning. Fine with ~0.90 (recommendations)? Crank the speed, save the money.
Measuring recall on your own data
Every recall number in this article, and every one in every vendor's blog post, was measured on somebody else's data. Yours will be different. Good news: measuring it takes about an hour.
Step 1, ground truth. Sample ~1,000 real queries from production logs (or write 200 by hand). Embed them with your production model, run brute-force search over the full corpus at the k you care about or bigger, store the true neighbor IDs.
Common mistake: sample the queries, never the corpus. Ground-truth against 10% of your vectors and you've computed neighbors for a different dataset. Your recall number will look great and mean nothing.
Step 2. Compute recall@k with a five-line function:
def recall_at_k(truth, pred, k):
hits = sum(len(set(t[
return hits / (len(truth) * k)
Order inside the top-k doesn't matter, only membership.
Step 3, sweep and find the knee. Run the same queries at efSearch (or nprobe) values of 10, 16, 32, 64, 128, 256, 512. Record recall and p95 latency, not the mean, which hides the tail behavior that actually ruins the experience. Plot recall against QPS, find where latency spikes but recall barely moves, pick a setting just past that knee.
Re-measure whenever the embedding model changes, the corpus roughly doubles, or the query mix shifts. Recall drifts downward as a corpus grows at fixed parameters, same efSearch exploring a proportionally smaller slice of a bigger graph. This is the silent failure from the intro, and this is where you catch it before your users do.
One distinction people constantly blur: index recall asks "did my ANN index find what exact search would have found." RAG retrieval quality asks "did the retrieved chunks actually answer the question." Different things, different ground truth. An index at recall 0.99 can still power a lousy RAG system if the chunking is off. If your RAG answers are bad, check chunking and embeddings before touching the index.
Mistakes people make, repeatedly
● Never measuring recall, so nothing alerts you to silent degradation.
● Building an index for 5,000 vectors when flat would've been simpler.
● Leaving efConstruction at default and fighting efSearch instead.
● Not budgeting for build time, so a re-index blocks a release nobody planned for.
● Quantizing and deleting the originals, killing reranking permanently.
● Running dot product on unnormalized embeddings, then debugging a "relevance issue" that's a magnitude bias.
Turn Learning into Career Growth
FAQs
What is HNSW?
Hierarchical Navigable Small World, an ANN algorithm storing vectors in a multi-layer graph, searching from a sparse top layer down to a dense bottom layer holding every vector.
ANN vs HNSW?
ANN is the problem (find near-neighbors without checking everything). HNSW is one algorithm that solves it, alongside IVF, PQ, ScaNN, and DiskANN.
IVF vs HNSW?
The inverted file index clusters vectors and searches nearby cells. HNSW builds a graph and walks toward the answer. HNSW handles live inserts better and hits higher recall; the inverted file index uses less memory but needs retraining as data shifts.
What is recall@k?
The fraction of true k nearest neighbors your index actually returned. A property of your configuration on your data, not the algorithm itself.
What is product quantization?
Splitting each vector into subvectors, replacing each with a one-byte codebook ID. Shrinks a 768-dim float32 vector from 3,072 bytes to about 96, roughly 32x.
Cosine, dot product, or Euclidean?
Whatever your embedding model was trained on. Normalized vectors rank identically across all three, so pick dot product for the lower compute cost.
