What does concurrent HNSW construction and querying actually require?

Concurrent HNSW construction and querying require very different levels of care, because serving read-only searches against a graph that isn’t currently being modified is close to embarrassingly parallel, while inserting new vectors means multiple threads reading and writing the same shared structure at once — and getting that coordination wrong doesn’t just slow things down, it can silently corrupt the graph in ways that only show up later as unexplained recall problems.

Why is serving queries concurrently the easy half of this problem?

A search that isn’t inserting anything only reads the graph — it walks neighbor lists, computes distances, and returns results, without changing a single connection anywhere in the structure. Multiple threads can perform this kind of read-only traversal simultaneously without any risk of interfering with each other, since none of them is modifying data another thread might be reading at the same moment. This is why serving a high volume of concurrent queries against a stable, already-built graph is generally the straightforward part of building a production-quality implementation — the real complexity shows up only once insertions enter the picture.

What makes concurrent insertion so much harder than concurrent search?

Inserting a new vector both reads the existing graph, to find good candidate neighbors, and writes to it, by adding new connections and potentially pruning an existing node’s neighbor list. If two insertions happen at the same time and both end up touching the same node’s neighbor list, one thread‘s changes can be lost or corrupted by the other’s, depending on exactly how the two operations happen to interleave — a problem that doesn’t show up reliably in testing, since it depends on timing that varies from run to run. The graph’s global entry point adds a further wrinkle: an insertion that lands in a higher layer than any previous vector needs to update that shared piece of state, and if two such insertions happen concurrently, they need some mechanism to agree on the correct final entry point rather than one silently overwriting the other’s update.

How fine-grained should locking actually be?

The general answer is to lock as narrowly as possible around only the specific parts of the graph actually being modified, typically the neighbor lists of the small number of nodes directly involved in a given insertion, rather than locking the entire graph for the duration of every single insert. A single global lock covering the whole structure is simple to reason about and guarantees correctness, but it also means every insertion has to wait for every other insertion to finish completely before starting, eliminating essentially all of the benefit multiple threads were supposed to provide. Per-node locking allows insertions in unrelated parts of the graph to proceed simultaneously, at the cost of needing careful, consistent rules about the order in which multiple locks are acquired whenever a single insertion needs to touch more than one node at once — inconsistent lock ordering across different code paths is one of the most common sources of deadlock in exactly this kind of fine-grained locking scheme.

Does running construction on multiple threads change the resulting graph?

It generally does, and this is worth expecting rather than being surprised by. Because the order in which concurrent insertions actually complete isn’t fully determined in advance, two separate multithreaded builds of the same dataset, even with identical parameters, can produce graphs that differ in their exact connections, simply because the vectors weren’t necessarily processed and connected in the same order both times. This doesn’t make the resulting graphs incorrect — search itself remains fully deterministic on a completed, fixed graph — but it does mean that reproducibility work, benchmarking, and debugging all need to account for insertion order and thread scheduling as real variables, not treat construction as if it always produces one single canonical graph for a given dataset.

With construction, search, memory layout, and concurrency all covered, the last piece of building a usable implementation is making sure a graph that took real time and effort to build doesn’t have to be reconstructed from scratch every time a process restarts — which is exactly what the next page on persistence and recovery addresses. Readers specifically weighing per-node locking against a single coarse lock for their own implementation will find the underlying primitives — mutexes, atomics, and reader-writer locks — covered individually in this site’s systems-and-hardware glossary section.