Concept illustration of vector neighbors found across graph layers with long- and short-range links

Vector search looks for data close to a query. With a large dataset, comparing the query to every item can be costly, so a system may use an approximate nearest-neighbor (ANN) index. HNSW builds proximity graphs at several levels, moving broadly before refining candidates. The distinction from exact search matters: results can differ from the true top K depending on data and settings.

Layers separate different link scales

Malkov and Yashunin describe items as nodes connected to nearby items. Every node appears in the bottom layer, while some nodes are selected to appear in higher layers as well. The paper selects a node’s maximum level using an exponentially decreasing probability, so upper levels contain fewer nodes. Longer-range links are available at higher levels; lower layers contain denser local connections.

A highway-and-street analogy can help: upper layers move the search toward a relevant region, and lower layers inspect nearby candidates. It is only an analogy, not a guarantee of a shortest route or exact neighbor. The paper’s complexity and performance statements refer to the proposed algorithm and its evaluations. They do not guarantee the same result for every dimension, distribution, distance measure, or machine.

A query descends while narrowing candidates

Search starts at an upper-layer entry point and follows neighbors closer to the query. When that layer no longer offers a better candidate, the search descends, using promising nodes from the prior layer as new entry points. At the bottom layer it examines a broader set of candidates to select the final K. A useful graph can locate a nearby region without comparing the query against every stored vector.

Approximation comes from limiting work and candidates. Needed neighbors can be missed when links are sparse, data are strongly clustered, or the distance measure does not fit the task. The embedding model, normalization, distance function, and filters also affect interpretation. HNSW is a search index; it does not validate whether an embedding captures the right meaning or whether a result is useful for a particular decision.

M and ef are implementation-specific controls

The paper describes variables that control graph connections and candidate breadth during construction and search. The widely used hnswlib library exposes M, ef_construction, and query-time ef. Its documentation says M strongly affects memory and can also affect accuracy and runtime. ef_construction adjusts construction-search characteristics; increasing query ef generally explores more candidates and can improve accuracy or recall, at the cost of slower search.

These descriptions belong to hnswlib’s implementation, not a promise that every library uses identical defaults or semantics. Implementations may differ in storage layout, connection limits, parallel construction, and filters. The hnswlib README says ef should be greater than K in its API; that is not a universal HNSW standard. Test settings against exact results using representative data and queries.

Measure speed and quality together

Do not evaluate an index only by query time. Compare recall with exact nearest-neighbor results and record latency distribution, memory use, build time, updates, and filtering behavior. Strong average recall can hide misses for rare query types or smaller data groups. If the embedding model or data distribution changes, remeasure rather than assuming an earlier configuration still performs the same way.

Treat M and candidate breadth as resource trade-offs, not automatic quality switches; the paper’s logarithmic complexity is not a deployed-service latency guarantee. For a reproducible comparison, define relevance and use an exact-neighbor sample that represents real query traffic. Keep embeddings and distance definitions fixed, and record data, distance measure, hardware, concurrency, index version, recall, memory, build time, latency distribution, and the share of slow responses. Report filtered queries with few eligible candidates as a separate cohort. This makes it easier to see whether a setting changes recall or tail latency for a particular request group instead of hiding that cost in an average.

Sources