Why might increasing m significantly improve recall on one dataset but barely help - or even hurt latency - on another?

The reason m helps one dataset and not another comes down to three things: how much connectivity the dataset actually needs, how the data is distributed, and whether the graph still fits in cache. Recall vs m is a concave curve, and where it plateaus depends on the intrinsic dimensionality of the data and the clustering structure. On a dataset with clear cluster structure and moderate intrinsic dimensionality, a small m already gives the graph enough long-range links to jump between clusters, so recall saturates early - going from 16 to 64 buys almost nothing. On a dataset with high intrinsic dimensionality or with many near-duplicate points, the graph needs more edges to remain navigable, so the curve keeps rising longer. The key insight is that m is not adding information; it is adding redundant paths. Once every region of the space is reachable in a small number of hops, extra edges do not make the search find better answers, they just make the graph bigger.

The latency effect is even more interesting. In theory, more edges means fewer hops, which should mean lower latency. In practice, once the graph exceeds the size of the CPU cache (or the memory bandwidth budget), each extra edge is another potential cache miss during traversal. At that point, increasing m can increase latency even though it decreases hop count, because each hop is more expensive. This is the classic memory wall effect: a graph that fits entirely in L2 or L3 is dominated by computation, while a graph that spills to DRAM is dominated by memory access. On large collections, raising m past the point where the graph fits in cache is a net latency loss. The other dataset-dependent factor is hub nodes: high-dimensional datasets often develop hub nodes that are close to many points, and adding more edges to hubs makes them even more dominant, which can distort the graph and actually reduce recall for some queries. This is why HNSW's diversity heuristic exists - it deliberately prunes edges to hubs - but the heuristic can be overwhelmed if m is set very high.

The practical takeaway is that m is not a universal recall knob and you cannot pick it from a table. You measure the recall-vs-m curve on your own data at a fixed ef, find the knee, and stop there. If recall is still unacceptable at the knee, the problem is more likely the embedding model, the distance metric, or the intrinsic dimensionality of the data than m. The common mistake is treating m as the first thing to raise when recall is bad; in practice ef is cheaper to experiment with because it requires no rebuild, and the embedding model is usually the higher-leverage fix. The alternative to raising m is to reduce the intrinsic dimensionality of the data (e.g. via a supervised projection or by using a better embedding model), which often raises the recall ceiling more than any index parameter. Version note: Qdrant's on-disk HNSW changes this calculus because the graph no longer has to fit in RAM at all, so the cache-locality argument becomes about disk I/O patterns rather than DRAM, and inline storage of quantized vectors mitigates some of it.

Version-dependent: the on-disk HNSW and inline quantized-vector storage options were added in relatively recent Qdrant releases. If you are benchmarking m on an old version, your latency numbers will not transfer to a current version where the graph can live on disk and vectors are stored inline in nodes. Always re-run the sweep after a major upgrade if latency or recall is on your SLO.