Which search and graph optimizations improve HNSW without changing its architecture?

Several optimizations improve HNSW’s real-world speed without touching M, efConstruction, efSearch, or the graph’s actual connections at all — they change how efficiently the existing search procedure runs on real hardware, which candidate is examined next, and how many queries get served together, rather than changing what the algorithm is fundamentally doing.

What can be improved about the bookkeeping a search does along the way?

Every search needs to track which nodes it has already visited, and the data structure used for that bookkeeping has a real performance cost of its own, separate from the graph traversal itself. A general-purpose hash set works correctly but carries overhead that a more specialized structure can avoid — a bitmap indexed directly by a node’s internal ID, for instance, or a reusable array paired with a generation counter that avoids having to clear the whole structure between searches by simply incrementing a counter instead. The priority queues used to track candidates and results benefit from similar specialization: a heap implementation tuned for the specific access pattern a search actually uses, rather than a generic off-the-shelf priority queue, can meaningfully reduce the overhead paid on every single insertion and extraction during a search that might perform hundreds of these operations.

Does reordering or prefetching a node’s own neighbor list help?

Both can, and for related reasons. Storing a node’s neighbors in an order that reflects how they’re actually likely to be accessed together — grouping neighbors that tend to get visited in the same search near each other — improves how well that data reuses the CPU’s cache once it’s loaded, building on the same locality principle covered in this site’s page on memory layout. Prefetching takes this further by explicitly requesting the next piece of data the search is about to need before it’s actually needed, giving memory enough time to deliver it before the CPU sits idle waiting. Because a graph traversal’s next few steps are somewhat predictable — the algorithm already knows which neighbors it’s about to examine — issuing a prefetch request for that data slightly ahead of when it’s used can hide a meaningful amount of memory latency that would otherwise show up as wasted CPU time.

Can starting from more than one point speed up a search?

Beginning a base-layer search from several different entry points rather than a single one, and merging the resulting candidates, can sometimes recover accuracy that a single unlucky entry point might have missed, at the cost of the extra work involved in exploring from multiple starting positions. Early and range-aware termination work in the opposite direction, looking for ways to safely stop a search sooner than a completely exhaustive stopping rule would require — for instance, when the task at hand only cares whether any point exists within a certain distance of the query rather than finding the single closest point, a search can often stop as soon as one qualifying candidate is found, without needing to fully rank every candidate the way a standard top-k search would.

Why does running queries in batches often beat running them one at a time?

Serving one query at a time means paying certain fixed overheads — setting up data structures, warming relevant memory, coordinating with whatever system is issuing the request — separately for every single query, even when a system has many queries available to process together. Submitting a batch of queries together instead lets that overhead be amortized across the whole batch rather than paid individually, and it often improves how efficiently the CPU’s memory and computation resources get used overall, since multiple queries touching related parts of the graph in overlapping time windows create more opportunities for cache reuse than the same queries handled strictly one after another. This makes batching a meaningful throughput optimization for any workload where queries can be reasonably grouped rather than each needing an immediate individual response.

None of the optimizations covered here change how much memory a graph consumes, which is where the next page picks up — how compressing the vectors themselves, separately from the graph structure sitting on top of them, trades some accuracy for a real reduction in memory footprint. Readers interested in query-adaptive exploration as a further, more research-oriented optimization on top of everything covered here should revisit this site’s page on why recall and query difficulty vary from query to query.