**M is the per node neighbor count in the HNSW graph.** When you build an HNSW index, each vector becomes a node and gets M outgoing edges to other nodes. Typical M values are 16, 32, or 48 depending on the workload.
**Four things move when M increases:**
1. **Recall climbs.** A denser graph (more edges per node) gives the greedy search more paths to follow toward the true nearest neighbors. The graph is harder to get stuck in a local minimum. Recall@K rises monotonically with M, with diminishing returns past ~64.
2. **Memory climbs.** Each node stores M neighbor pointers (4 bytes each, or 8 on 64-bit systems). For 100M nodes at M=32, that is 100M * 32 * 4 = 12.8GB just for the graph edges, on top of the raw vectors. Memory cost is roughly linear in M.
3. **Build time slows.** Every insertion has to find its M nearest neighbors in the existing graph (using the same search algorithm but in 'construction mode'), then add edges. More edges per node means more search work per insertion. Build time scales roughly with M * log(N) per insert.
4. **Query latency rises modestly.** At each hop in the greedy walk, the algorithm evaluates all M neighbors of the current node. More edges per node means more per hop work. The effect is smaller than on memory or build time because the number of hops doesn't grow with M.
**Why the correct answer is option A.** All four directions are monotonic in M: recall up, memory up, build time up, query latency modestly up. Options B inverts every relationship; C ignores that M affects every layer of the hierarchy, not just the top; D confuses M with ef_search (a query time parameter, not a build time one).
**Production typical values.** M = 16 for memory constrained, M = 32 for general purpose, M = 48-64 for high-recall RAG. Going above M = 64 rarely pays off; the recall gains plateau and memory grows linearly.
**M is the maximum number of bidirectional edges per node in the HNSW graph.** It is set at index-build time, baked into the graph structure, and cannot be changed without a full rebuild.
**The four monotonic relationships.**
*Recall climbs with M.* A denser graph means the greedy walk has more outgoing edges to evaluate at each node, which reduces the chance of getting stuck in a region without good edges toward the true nearest neighbor. The recall versus M curve looks like an S: steep gains from M=4 to M=24, plateauing past M=48. The asymptotic recall ceiling for any HNSW index is set primarily by M; ef_search reaches toward that ceiling but cannot exceed it.
*Memory climbs with M, linearly.* Each node stores M neighbor pointers, 4 bytes each (or 8 on systems using 64-bit IDs). For 100M vectors at M=32, that is 100M * 32 * 4 = 12.8GB for the graph edges alone. The HNSW hierarchy adds a small additional cost (higher layers have fewer nodes, ~M/2 edges average each). The graph overhead is typically 5-15% of the total memory cost; the rest is the raw vectors. But M is the lever for that overhead.
*Build time slows with M.* HNSW construction is N independent insertions, each of which runs a search in the existing graph to find the M best neighbors for the new node, then creates the edges (sometimes pruning neighbor edges to maintain the M-bound). Per-insertion cost is roughly O(M * log(N)) where the log(N) factor comes from the hierarchy traversal. Doubling M roughly doubles build time.
*Query latency rises with M, modestly.* At each hop in the search, the algorithm evaluates all M neighbors of the current node (compute distance to query, update the candidate heap). More edges per node means more per hop work. However, the number of hops in a query does not grow with M (it grows roughly as log(N) regardless), so the total latency effect is closer to additive overhead per hop than the build time multiplicative effect.
**Why the other options are wrong.**
-
Quick reference
TL;DR
Larger M means: recall climbs (denser graph reaches more true neighbors), memory climbs (M pointers per node), build time slows (each insert does more neighbor lookups), and query latency rises modestly (more
Think of the HNSW graph like a social network where every person keeps a contact list of close friends, and M is the size of that list. **More friends per person** means it's easier to walk across the network to find any particular face (better recall), but each person's contact list takes more storage (more memory), and adding new people takes longer because you have to figure out who their best friends should be (slow build). Searching takes a tiny bit longer too because at each step you have to glance at more friends. **Fewer friends per person** is the opposite: smaller, faster to build, but you might get stuck because there's no good path to the person you want.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Memory is tightly constrained and the recall ceiling is acceptable Lower M (8-16) saves memory; the recall hit is manageable for many workloads.
Build time is the bottleneck and the corpus is large Higher M slows builds proportionally; for write heavy workloads, lower M plus higher ef_search at query time may be a better tradeoff.
The corpus is past 1B vectors and HNSW itself is no longer the right choice At billion scale, IVF-PQ or DiskANN may dominate HNSW regardless of M. M tuning is moot.
Quick scan · 2–4 min
Everything important, quickly.
3 min: name the four monotonic relationships + reject the distractors + cite typical production M range + connect to recall ceiling concept.
Side-by-side
M value
Memory overhead (per 100M nodes)
Build time (100M, well parallelized)
Typical recall@10 (well tuned ef_search)
Use case
8
~6 GB
~20 min
~0.88
Memory-constrained tiny corpora
16
~13 GB
~40 min
~0.92
General-purpose default
32
~26 GB
~80 min
~0.95-0.97
Production RAG
48
~38 GB
~2 hr
~0.97-0.98
High-stakes retrieval
64
~51 GB
~3 hr
~0.98-0.99
Extreme recall, diminishing returns
Real-world examples
Real products, models, and research that use this idea.
2Weaviate defaults M=64, positioning itself as a RAG first DB where recall is the primary metric.
3ANN-Benchmarks publishes recall-vs-build time curves sweeping M; the S-curve shape is universal across HNSW implementations.
4Production tuning guides at Pinecone, Weaviate, and Qdrant all recommend M=16-48 with the higher end reserved for high-recall RAG workloads.
Interviewer follow-ups
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy does the canonical HNSW implementation use 2*M edges at the base layer?
Sign in or go Pro to see the approach for this follow-up.
QHow does M interact with the dimensionality of the embedding?
Sign in or go Pro to see the approach for this follow-up.
QWhat is the right way to A/B test a change in M in production?
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
Confusing M (build time, per node graph degree) with ef_search (query time, candidate-list size). They both affect recall and latency but live on opposite sides of the build/query line and respond very differently to changes.