The index Qdrant actually uses, explained by building it up from one idea — link every vector to a few neighbours and walk downhill. Layers, m, ef_construct and ef, what each one costs, and why the search is allowed to be wrong.
Part 1 established the problem: exact search reads every vector, so its cost grows with your corpus and there is no way around that while you insist on the exact answer. Part 2 built a collection and left the index alone.
This part opens it up. Qdrant’s index is HNSW — a Hierarchical Navigable Small World graph — and by the end you should be able to predict what happens when you change any of its three numbers, and say why.
We’ll build the idea up rather than define it. Everything here is Qdrant 1.19.1, and the defaults quoted are the ones a fresh collection actually reports.
Try this first
You have a million vectors. You are allowed to look at only 200 of them, chosen one at a time, and after each one you learn its distance to the query. You may use what you learn to choose the next one.
Can you find something close to the query?
Write down your answer, and the reason. The reason matters more than the answer, because it is the whole algorithm.
One idea: remember who your neighbours are
Suppose that when you inserted each vector, you wrote down a handful of the vectors nearest to it at the time. Not all of them. Say sixteen.
Now you have a graph: every vector is a node, and every node has a short list of nearby nodes.
To search, start anywhere. Look at your current node’s neighbours, compute the distance from the query to each, and move to whichever is closest to the query. Repeat. Stop when none of the neighbours is closer than where you already are.
That’s it. That’s the whole search, and it’s called greedy descent. You never look at the million; you look at sixteen, then another sixteen, and so on, following the slope downhill towards the query.
Two things about it are worth being precise about.
It terminates at a local minimum, not necessarily the global one. When no neighbour is closer, you stop — even if a genuinely nearer vector exists somewhere you never looked. This is the exact moment vector search stops being exact, and every parameter below is about making that outcome less likely.
It only works if the graph is navigable. If your links all point to things very close by, you shuffle around a tiny neighbourhood forever. If they all point far away, you never settle. A navigable small world graph has both: mostly short links, a few long ones. The long links let you cross the space quickly; the short ones let you land precisely.
The problem with one layer, and the fix
A single graph like that has an awkward failure. If you start somewhere random and the query is far away, you spend most of your hops just travelling — taking small steps across a huge space, because most of your links are short.
HNSW’s answer is to build several graphs stacked on top of each other.
The bottom layer contains every vector. The layer above it contains a random sample — roughly one in every few. The layer above that, a sample of those. Each layer up is sparser, so its links span further.
The search starts at the top, where there are very few nodes and each hop covers enormous ground. It descends greedily until it can’t improve, then drops to the next layer down and continues from where it landed. By the time it reaches the bottom layer — the one with everything in it — it is already in the right region, and the dense short links there do the precise work.
Schematic, not measured: the layout and the path are drawn to show the mechanism, which is the same at twenty nodes and at a million. The search stops where no neighbour is closer — a local minimum — which is why HNSW is approximate and why ef exists. Switch scenario to see the same query without the hierarchy.
This is why the structure is worth the trouble. Coarse, fast movement first; fine, careful movement last. It’s the same reason you find a street by zooming out to the city and then in to the block, rather than crawling the map at full zoom the whole way.
The layers are a zoom control. The search takes big steps while it is far away and small steps when it is close, and the hierarchy is how it knows which it is doing.
The three numbers
Everything you can tune is these. A fresh Qdrant collection reports them as:
{
"m": 16,
"ef_construct": 100,
"full_scan_threshold": 10000,
"on_disk": false,
"payload_m": null
}m — how many neighbours each node keeps
The size of the short list. Bigger m means a better-connected graph, so greedy descent has
more routes and is less likely to dead-end in a local minimum. That raises recall.
It costs memory, and the cost is arithmetic you can do now: each link is a 4-byte node id,
each node has up to m of them on the upper layers and up to 2m on the bottom layer. So
the graph’s own size is roughly
links ≈ points × m × 2 (bottom layer gets 2m, upper layers add a little)
bytes ≈ links × 4At a million points and m = 16 that is about 128 MB of graph on top of your vectors. Raise
m to 64 and it is about 512 MB. Compare that to the vectors themselves — a million 384-dim
float32 vectors are about 1.4 GiB — and you can see that m is a real but secondary cost at
typical settings, and a dominant one if you push it high.
Bigger m also makes construction slower, because every insert has more candidate links to
consider and prune.
ef_construct — how hard it looks while building
When a vector is inserted, HNSW searches the graph to find its neighbours. ef_construct is
how large a candidate list that search keeps.
A bigger value means the new node’s links are chosen from a better-explored set, so the graph is closer to the one you’d build if you could afford to check everything. It is paid once, at build time, and costs nothing at query time.
This is the parameter people under-spend on. Build time is a one-off; a badly connected graph is forever. If a build takes an hour instead of forty minutes and every subsequent query is more accurate, that is almost always the right trade.
ef — how hard it looks while searching
The only one of the three that is set per query, not on the collection.
Greedy descent as described above keeps one current node. Real HNSW keeps a candidate list of
the ef best nodes found so far, and explores from all of them. A bigger list means more of
the graph is examined, which means the local-minimum trap is likelier to be escaped — higher
recall, more time.
from qdrant_client import models
client.query_points(
"notes",
query=vector,
limit=10,
search_params=models.SearchParams(hnsw_ef=128),
)ef must be at least your limit, and in practice wants to be comfortably larger — you
cannot return the best 10 from a candidate list of 10 without having got all 10 right by luck.
The direction of every trade here is the same: more work, more recall. What that costs on your data, at your corpus size, is not something anyone can tell you from a blog post. Part 4 is how you measure it.
The fourth number nobody mentions
full_scan_threshold, default 10000.
Below this many vectors in a segment, Qdrant does not use the graph at all — it scans. The reason is honest: at small sizes a scan is genuinely faster than walking an index, exactly as Part 1’s table showed for a thousand vectors sitting in CPU cache. Building and traversing a graph to search 3,000 vectors is pure overhead.
This has a consequence that confuses people benchmarking small collections: your ef is
being ignored, and your recall is 1.0, because no approximation is happening. Then they
load real data and both change.
The same is true of indexing_threshold on the optimiser, also 10000 by default: a
segment smaller than that doesn’t get an HNSW graph built for it in the first place. A
collection is normally a mix of indexed and unindexed segments, which is why
indexed_vectors_count and points_count routinely disagree.
Explain it like I’m ten
Imagine finding one house in a huge city, and you’re only allowed to ask people for directions — no map.
The slow way is to knock on every door. Guaranteed to work. Takes forever.
The HNSW way: everyone in the city knows a few of their neighbours. But some people also know someone across town, and a very small number know someone in every district.
So you start by asking one of the well-connected people. They send you to roughly the right district. Someone there sends you to roughly the right street. Someone on that street points at the house. Six or seven questions instead of a million doors.
You might end up next door to the house you wanted, because nobody you asked happened to know
about it. If that matters, you ask more people at each step — that’s ef. If you want
everyone to know more neighbours in the first place, that’s m, and it means everyone has a
longer list to remember.
Where the analogy breaks: a city is flat and has streets, so “across town” is a direction you can point in. In 384 dimensions there are no streets and no directions — “near” is only ever a number you compute between two specific points. The graph isn’t a map of the space; it is the only structure there is.
The precise version
HNSW builds a layered proximity graph. On insertion, a node’s maximum layer ℓ is drawn from a geometric distribution, so layer occupancy decays exponentially and layer 0 holds every node.
Search from the top layer runs greedy best-first with a candidate list of size 1 in the upper
layers, descending one layer at each local minimum, then runs the same search at layer 0 with
a candidate list of size ef, returning the best k.
Link selection is not simply “the m nearest”. Malkov and Yashunin use a heuristic that
prefers a diverse neighbourhood: a candidate is kept only if it is closer to the new node
than to any already-selected neighbour. That is what preserves long-range links and keeps the
graph navigable, instead of collapsing it into tight clusters with no bridges between them.
The paper reports search complexity scaling logarithmically with the number of elements under its assumptions. Treat that as the shape of the thing rather than a promise about your data — it depends on the intrinsic dimensionality of what you actually store, which is a property of your embeddings and not of the library.
Trade-offs
m against memory. Raising m raises recall and raises the graph’s size roughly in
proportion. At a million points, going from 16 to 64 moves the graph from roughly 128 MB to
roughly 512 MB. If you are memory-bound, m is the first thing to look at, and
Part 5 is the second.
ef_construct against build time only. It costs nothing at query time. Under-spending
here is the most common way to end up with an index that is permanently worse than it needed
to be.
ef against latency, per query. The one you can change without rebuilding anything — and
therefore the one to tune last, once you know what your recall actually is. Raising ef on a
system whose latency is dominated by round trips buys recall almost for free; on a
compute-bound one it does not.
The graph against no graph at all. Below full_scan_threshold a scan wins. Under a few
thousand vectors, an index is not the answer to anything.
Approximate against exact. You can always pass exact=True for a query that must be
right, and pay the full scan for that one query. Mixed workloads are allowed.
Common mistakes
Benchmarking under full_scan_threshold. 5,000 vectors means no graph, ef ignored,
recall 1.0. Every conclusion drawn there is about brute force.
Reading points_count as the indexed count. Segments below indexing_threshold have no
graph. Check indexed_vectors_count before believing any latency number.
Setting ef below limit. Asking for 10 results from a candidate list of 10 is asking
for a top-10 that was never ranked against anything.
Tuning m when ef_construct is the problem. They both affect graph quality. Only one of
them is free at query time.
Expecting a rebuild from an ef change. There isn’t one — ef is per-query. Changing m
or ef_construct does rebuild the graph, and on a large collection that is not instant.
Assuming recall is a property of the settings. It is a property of the settings and your data. Part 1 measured the same index at recall 0.52 on structureless vectors and 1.0 on clustered ones. Your corpus decides which end you are near.
Interview questions
1. Explain HNSW to someone who knows what a nearest-neighbour search is.
Answer
Every vector is a node linked to a few of its near neighbours, forming a graph. A search walks that graph greedily towards the query — look at the current node’s neighbours, step to the closest one, repeat until nothing is closer. The hierarchy makes that efficient. Layers above the bottom hold exponentially fewer nodes, so their links span further. The search starts at the sparse top and takes large steps, drops a layer at each local minimum, and arrives at the dense bottom layer already in the right region. A strong answer names the consequence: the result is a local minimum of the walk, so the search is approximate by construction, not by accident. **Follow-up:** what makes it *navigable*? A mix of short and long links. The link-selection heuristic deliberately keeps diverse neighbours rather than simply the nearest ones, which is what preserves the long-range edges.2. What is the difference between ef_construct and ef?
Answer
`ef_construct` is used while building: it is the candidate-list size for the search that finds a new node’s neighbours. It affects the quality of the graph and is paid once. `ef` is used while searching, per query, and is the candidate-list size for the actual lookup. It trades latency for recall on every request. The practical point is that `ef_construct` is free at query time, so it should be generous; `ef` is not, so it should be measured. **Follow-up:** which requires a rebuild to change? `ef_construct` (and `m`). `ef` is a search parameter and changes nothing stored.3. Your recall is too low. What do you change, and in what order?
Answer
Raise `ef` first: it is per-query, needs no rebuild, and is reversible in a second. Measure recall against exact search as you go. If `ef` alone can’t get there at acceptable latency, the graph itself is the limit — raise `m` (better connectivity, more memory) and `ef_construct` (better link choices, slower build), and rebuild. Before any of that, check the measurement: is the collection actually indexed, are the queries drawn from the same distribution as the data, and is the ground truth exact. **Follow-up:** when is low recall not fixable by parameters? When the data has little structure to exploit — nearly-equidistant vectors give the greedy walk no gradient. Then the answer is a different representation, not a different `ef`.4. Why is there a full_scan_threshold?
Answer
Because below a few thousand vectors a linear scan is genuinely faster than traversing a graph. The scan is sequential over contiguous memory, which hardware likes; the graph is pointer-chasing, which it does not. Qdrant defaults it to 10,000 per segment. It matters for benchmarking: under that threshold you are measuring brute force, `ef` does nothing, and recall is 1.0 by definition. **Follow-up:** is that the same as `indexing_threshold`? No, though both default to 10,000. `indexing_threshold` decides whether a segment gets a graph built at all; `full_scan_threshold` decides whether an existing graph is used for a given search.5. How much memory does the graph itself cost?
Answer
Roughly `points × m × 2` links, at 4 bytes per link — the bottom layer allows up to `2m` neighbours and the upper layers add a little on top. At a million points with the default `m = 16` that is on the order of 128 MB. Put it next to the vectors: a million 384-dimension float32 vectors are about 1.4 GiB. So at default settings the graph is a minority of the bill, and at `m = 64` it stops being one. **Follow-up:** how would you reduce total memory? Quantize the vectors, which attacks the larger term — Part 5. Reducing `m` attacks the smaller term and costs recall.6. Is HNSW’s logarithmic search complexity something you can rely on?
Answer
As a shape, yes; as a guarantee about your workload, no. The scaling result comes with assumptions about the data’s structure, and what governs real behaviour is the intrinsic dimensionality of your embeddings rather than the count of vectors. The practical version: doubling your corpus does not double query time the way a scan does, which is the whole reason to use it. Exactly what it does do is something you measure. **Follow-up:** what would make it behave badly? Data with no cluster structure, or a filter so restrictive that almost every neighbour in the graph is ineligible — that second one is Part 7.7. Can you change a collection’s m after it has data?
Answer
Yes — `m` and `ef_construct` are updatable through `update_collection`, and changing them causes the graph to be rebuilt for affected segments. It is not free and it is not instant on a large collection. Contrast with the vector dimension and the distance metric, which cannot be changed at all (Part 2). Those need a new collection, and the alias swap in Part 11. **Follow-up:** how would you roll out an `m` change safely on a live system? Build a second collection with the new setting, verify recall and latency against the old one, then move an alias.8. Why does a search return a local minimum rather than the true nearest neighbour?
Answer
Because it stops when no neighbour of the current node is closer to the query. The true nearest neighbour may not be a neighbour of anything the walk visited, so nothing ever points at it. The hierarchy and the candidate list of size `ef` both reduce how often that happens — a larger `ef` keeps several frontiers alive instead of one, so a single dead end doesn’t end the search — but neither eliminates it. That residual is precisely what recall measures. **Follow-up:** so how do you ever know the true answer? You compute it by exact search on a sample, once, offline. That is the ground truth, and building it is Part 4.Sources
- Malkov, Y. A. and Yashunin, D. A., Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (arXiv:1603.09320). The algorithm Qdrant implements: the layer hierarchy, the search procedure and the diverse-neighbour link selection heuristic described above.
- Qdrant documentation, https://qdrant.tech/documentation/concepts/indexing/ and
https://qdrant.tech/documentation/concepts/search/ —
m,ef_construct,hnsw_ef,full_scan_thresholdandindexing_threshold. - The default values quoted here were read back from a freshly created collection on Qdrant 1.19.1, not from documentation, so they are what this version actually does.
What to remember
HNSW is one idea — link each vector to a few near neighbours and walk downhill — with a hierarchy bolted on so the early steps can be enormous and the late steps can be small.
Three numbers control it. m is how many neighbours each node keeps, and it costs memory.
ef_construct is how hard the builder looks for those neighbours, and it costs build time
only. ef is how hard each query looks, and it is the one you set per request.
And a fourth decides whether any of it is used at all: below full_scan_threshold there is
no graph, no approximation, and nothing to tune.
Every parameter in HNSW buys the same thing with a different currency: a lower chance that the walk stops somewhere that only looked like the answer.