Exact nearest-neighbor search asks a simple question: given a query vector q, return the k stored vectors with the smallest distance to it. For a dataset X,

kNN(q) = arg top-k over x in X of -distance(q, x)

A flat scan computes distance(q, x) for every vector. Its cost grows linearly with the number of stored vectors, although optimized kernels, quantization, and parallelism can make that baseline surprisingly competitive at modest scale.

HNSW—Hierarchical Navigable Small World—does less work by accepting a possibility of error. It stores vectors as nodes in a multilayer proximity graph and follows edges toward the query. The practical promise is not “constant-time vector search.” It is a controllable exchange: fewer distance calculations and lower latency in return for index memory, construction work, and recall below one.

Understanding that exchange is more useful than memorizing default parameters.

Begin with the graph, not the hierarchy

Imagine each vector connected to several nearby vectors. To search, start at some node, measure the query’s distance to its neighbors, move to a closer neighbor, and repeat. This greedy routing can cross a local neighborhood quickly.

It can also get trapped. A graph containing only short local edges may have no route from the current cluster to a better cluster. Adding longer edges improves global navigation, but examining every long and short edge at every hop increases work.

HNSW separates those distance scales into layers:

  • layer 0 contains every node and the densest local graph;
  • higher layers contain progressively smaller random subsets of nodes;
  • edges in sparse upper layers tend to span longer distances;
  • one node in the highest non-empty layer acts as the entry point.

The structure resembles a probabilistic skip list, with proximity graphs replacing sorted linked lists. Search starts on the sparsest layer, greedily approaches the query, then uses that local minimum as the entry point for the next layer. The base layer performs a wider search to recover from imperfect routing.

For a newly inserted point, the original paper samples its maximum layer as

level = floor(-ln(U) × mL), where U is uniform on (0, 1)

so membership falls exponentially with layer number. The paper proposes mL = 1 / ln(M) as a simple choice. Most managed engines do not expose mL; they derive the hierarchy internally.

This random promotion has two consequences. The expected number of layers grows logarithmically with the dataset size, and insertion order is not the only source of graph structure. HNSW is still not fully deterministic in practice: random seeds, insertion order, concurrent construction, and implementation details can change the graph and its measured recall.

The same layer-search primitive is used during indexing and querying. It keeps:

  • candidates, a min-priority queue ordered by distance to the query;
  • best, a bounded max-priority queue whose root is the worst retained result;
  • visited, so a node is not evaluated repeatedly.

A simplified version of the paper’s SEARCH-LAYER algorithm is:

search_layer(query q, entry_points, ef, layer):
    visited    = set(entry_points)
    candidates = min_heap(entry_points, by distance to q)
    best       = max_heap(entry_points, by distance to q)

    while candidates is not empty:
        current = candidates.pop_nearest()
        worst   = best.peek_farthest()

        if distance(current, q) > distance(worst, q):
            break

        for neighbor in neighbors(current, layer):
            if neighbor in visited:
                continue
            visited.add(neighbor)

            if len(best) < ef or distance(neighbor, q) < distance(best.peek_farthest(), q):
                candidates.push(neighbor)
                best.push(neighbor)

                if len(best) > ef:
                    best.pop_farthest()

    return best

ef is a search width, not a fixed count of distance computations. It caps the retained working set, while graph degree and the path discovered determine how many nodes are actually visited. The stopping condition says: stop once the nearest unexplored candidate is worse than the worst element already retained. No remaining expansion is expected to improve the bounded result set.

For a query, HNSW uses a narrow greedy search through the upper layers and a wider search at layer 0:

ep = graph.entry_point

for layer from graph.max_layer down to 1:
    ep = nearest(search_layer(q, {ep}, ef=1, layer))

candidates = search_layer(q, {ep}, ef=efSearch, layer=0)
return nearest_k(candidates)

The final candidate width must be at least k in the original algorithm. Libraries may enforce that relationship, clamp a value, or expose a differently named candidate parameter. For example, Elasticsearch exposes num_candidates per shard, while OpenSearch behavior depends on the selected engine.

What the logarithmic complexity claim does—and does not—mean

The original paper derives expected O(log N) search scaling under a useful but idealized model: each layer is an exact Delaunay graph, spatial position is independent of layer promotion, and average node degree remains bounded. Under those assumptions, the expected work per layer is constant and the number of layers is logarithmic in vector count.

A production HNSW graph is only an approximation of that model. Its degree is capped, its edges are selected from approximate construction candidates, and base-layer search backtracks to recover from local minima. The paper presents empirical evidence that the extra ef work can remain bounded as low-dimensional datasets grow, but it also notes that further analysis is needed for high-dimensional spaces.

Therefore, O(log N) is a description of the intended scaling mechanism, not a latency guarantee. Real cost depends on graph quality, intrinsic dimensionality, target recall, filtering, cache misses, vector representation, and implementation. Capacity tests should include multiple corpus sizes; benchmarking only one N cannot establish a scaling curve.

Construction is search plus selective linking

HNSW is built incrementally. To insert a vector x:

  1. sample its maximum layer level;
  2. descend greedily from the current top layer to just above level;
  3. at each layer from min(level, max_layer) down to 0, run search_layer with efConstruction;
  4. choose up to M neighbors from the returned candidates;
  5. add bidirectional links;
  6. prune an existing node’s adjacency list if it exceeds the implementation’s layer limit;
  7. replace the global entry point if x created a new highest layer.

The important detail is step four. Selecting the M closest candidates sounds obvious, but it can create redundant edges aimed into the same dense cluster. The paper’s heuristic considers candidates in increasing distance from x and rejects a candidate when an already-selected neighbor is closer to that candidate than x is. In simplified form:

selected = []

for candidate in candidates ordered by distance(candidate, x):
    if every neighbor in selected satisfies
       distance(candidate, neighbor) > distance(candidate, x):
        selected.append(candidate)

    if len(selected) == M:
        break

The test favors links in different directions rather than merely the shortest links. That diversity preserves routes between clusters and improves the chance that greedy traversal can escape a local basin. This is why HNSW index quality depends on construction search and neighbor selection, not only on the number of edges.

The original algorithm distinguishes the number of connections created for a new node, the maximum connections on upper layers, and the maximum on layer 0. Product APIs often compress those details into a single M. Treat an engine’s documentation and index format as authoritative; do not assume that M=16 produces the same graph across implementations.

The three knobs control different stages

M: graph connectivity and standing memory

M controls the target or maximum number of bidirectional links per node, subject to implementation-specific layer rules. Raising it generally:

  • gives traversal more possible routes;
  • can improve recall for high-intrinsic-dimensional or clustered data;
  • increases distance evaluations per expanded node;
  • increases graph memory approximately linearly;
  • slows construction because more candidates and adjacency updates are involved.

The original paper reports that smaller values worked better for lower-dimensional data or lower recall targets, while larger values helped at high recall or high dimension. That observation is not a universal preset. Embedding dimensionality is not the same as intrinsic dimensionality, and two 768-dimensional embedding distributions can require different graphs.

Memory has two major terms:

resident bytes ≈
    N × dimensions × bytes_per_component
  + N × graph_cost(M)
  + engine overhead

where N is vector count. The graph term is O(N × M), but its constant is engine-specific. Elastic’s documentation estimates graph bytes as N × 4 × M, separate from vector storage. OpenSearch documents an estimate of 1.1 × (4 × dimensions + 8 × M) bytes per vector. Those formulas are capacity-planning starting points for those engines, not definitions of HNSW.

efConstruction: index quality paid at write time

efConstruction is the candidate-list width used while finding neighbors for an inserted node. Raising it explores more of the existing graph before selecting links. That usually improves graph quality, especially when a low value would miss bridges, but increases:

  • initial build time;
  • CPU per insert;
  • temporary construction memory;
  • replication or ingestion lag when index maintenance is synchronous.

It does not normally add a per-query data structure after the index is built. Its lasting effect is the quality of the chosen edges.

A weak graph cannot always be rescued by an enormous query-time search. Increasing efSearch may eventually approach the desired recall, but it can require enough exploration to erase the latency advantage. Tune construction against the recall-latency frontier, not build time alone.

efSearch: recall paid on every query

efSearch is the base-layer working-set width during query traversal. Raising it keeps more competing paths alive, which typically raises recall and latency. It also increases per-request scratch memory.

This is the most convenient online control because it can often vary per query. A low-latency interactive path and an offline deduplication job can use the same graph with different search widths. However, the mapping is implementation-specific:

  • pgvector exposes hnsw.ef_search;
  • OpenSearch accepts ef_search for HNSW, with behavior depending on the engine;
  • Elasticsearch exposes num_candidates per shard rather than a setting named efSearch.

Do not compare the numeric value 100 across these APIs as though it represented identical work.

Tune the frontier, not one metric

HNSW tuning is a multi-objective problem:

maximize Recall@k
subject to p99 ≤ latency_budget
           RAM ≤ memory_budget
           build_time ≤ build_budget

There is no single “best” tuple (M, efConstruction, efSearch). A useful tuning sequence is:

  1. establish an exact-search ground truth;
  2. choose two or three plausible M values within the engine’s supported range;
  3. for each M, build indexes at increasing efConstruction;
  4. sweep efSearch or its engine equivalent for every built index;
  5. plot recall against p50, p95, and p99 latency;
  6. reject configurations that violate memory, build-time, or ingestion constraints;
  7. keep Pareto-efficient configurations—those for which no alternative is both faster and more accurate.

If raising efConstruction produces no meaningful improvement anywhere on the query-time curve, stop paying the extra build cost. If a larger M improves recall only at search widths that already miss the latency target, its extra memory is not justified.

Also measure throughput under the intended concurrency. A configuration with excellent single-query latency may saturate memory bandwidth sooner because each search touches more graph nodes and vector values. Tail latency under load is the production result; an isolated microbenchmark is only a component measurement.

Filtering changes the search problem

A metadata predicate such as tenant_id = 42, language = 'ur', or created_at > ... is not a minor addition to ANN search. The system must find nearest neighbors inside a subset:

filtered_kNN(q) =
    arg top-k over x in X where filter(x) is true
    of -distance(q, x)

There are several execution strategies:

  • pre-filter then exact search: materialize a small eligible set and scan it exactly;
  • filter during graph traversal: allow the predicate to influence candidate acceptance while preserving enough traversable nodes;
  • ANN then post-filter: retrieve approximate candidates globally, then discard ineligible rows;
  • partitioned or partial indexes: build separate graphs for stable, high-value filter boundaries;
  • iterative search: continue graph exploration when the first candidate batch does not contain k eligible results.

Post-filtering is the easiest failure to miss. Suppose a predicate matches a fraction s of the corpus and membership is independent of vector position. A candidate set of size c then has an expected s × c eligible results. To expect k survivors, the crude estimate is:

candidate_count ≳ k / filter_selectivity

This is not a guarantee. Filter values are often correlated with embedding neighborhoods, and the variance becomes severe for selective predicates. The query may return fewer than k rows even though the corpus contains enough matches.

Engine semantics matter here. pgvector documents that filtering is applied after the approximate index scan; it supports iterative scans and recommends exact indexes, partial HNSW indexes, or partitioning depending on selectivity. Elasticsearch’s knn query filter parameter is a pre-filter applied during approximate search, while filters elsewhere in the query tree can be post-filters. OpenSearch support varies by engine and filter mode.

Benchmark every filter path you intend to ship. At minimum, stratify queries by selectivity, filter cardinality, and correlation with vector clusters. Confirm both recall and result count. Authorization filters deserve special attention: retrieval must never broaden the eligible set to improve vector recall.

A benchmark protocol that can be reproduced

An ANN benchmark needs an exact oracle and a controlled workload. Record enough context that a later run can explain a changed result.

1. Freeze the data contract

Record:

  • corpus, query set, and relevance split;
  • embedding model and exact version;
  • vector dimension, storage type, normalization, and distance function;
  • duplicate handling and invalid-vector policy;
  • metadata distribution and filter definitions;
  • index engine, version, commit or build, and all parameters.

Use production-shaped vectors when possible. Uniform random vectors are useful for mechanical tests but do not reproduce clusters, hubs, duplicates, or anisotropy found in embedding spaces.

2. Compute exact ground truth

For each query, run an exact scan under the same distance function and the same filter. Store the top k identifiers and distances. Then calculate:

Recall@k =
    (1 / number_of_queries)
    × sum over q of |ANN_top_k(q) ∩ exact_top_k(q)| / k

Report the distribution as well as the mean: median and low-percentile per-query recall can reveal a class of consistently bad queries hidden by an average.

If the product cares only whether one relevant item appears, also report hit rate, but do not label it Recall@k. If business relevance differs from vector distance, maintain a separate judged relevance evaluation. HNSW recall measures approximation of the chosen vector metric, not usefulness of the embedding.

3. Control machine and cache state

Record CPU, RAM, storage, operating system, shard and replica layout, thread counts, and concurrency. Separate:

  • cold-start behavior after restart or cache eviction;
  • warmed steady state;
  • single-query latency;
  • closed-loop and open-loop load at realistic concurrency.

Report p50, p95, p99, throughput, error count, and returned-result count. Averages conceal queueing and filter underfill. Elastic explicitly notes that HNSW graph and vector data depend on filesystem cache; a benchmark whose index fit changes between runs is measuring memory pressure as well as algorithm parameters.

4. Measure the index lifecycle

For every build, retain:

  • wall-clock build time and CPU time;
  • peak resident memory during construction;
  • final index bytes and estimated resident working set;
  • insert/update/delete throughput after the initial build;
  • merge, compaction, or vacuum state;
  • index age and number of segments or shards.

Elasticsearch builds a separate HNSW graph per segment, so segment count can affect search cost. pgvector notes that builds slow significantly when the graph no longer fits in maintenance_work_mem. These operational conditions belong in the benchmark record.

5. Sweep one axis systematically

Use the same query order and warm-up policy for every configuration. Repeat runs, publish variation, and retain random seeds and insertion order. A defensible matrix might vary:

M               = [engine-appropriate low, baseline, high]
efConstruction  = [baseline, 2× baseline, 4× baseline]
efSearch        = [k, 2k, 4k, 8k, ... up to latency failure]
filter bucket   = [unfiltered, broad, medium, selective]
concurrency     = [1, expected, overload boundary]

The values are deliberately relative. Fixed folklore such as “always use M=16” ignores the data distribution, engine, hardware, target k, filtering, and service-level objective.

Production decisions after the benchmark

Once a configuration passes the initial frontier test, validate behavior over time:

  • rebuild after an embedding-model change; old and new vector spaces are not comparable;
  • monitor recall on a stable canary query set, not latency alone;
  • track index size, cache residency, segment count, and ingestion lag;
  • version index parameters with the embedding and distance configuration;
  • test selective filters for underfilled result sets;
  • rerun ground truth after corpus growth or material distribution drift;
  • test update and deletion churn, because engine maintenance semantics differ;
  • keep an exact path for small filtered subsets and for evaluation.

HNSW is effective because it turns nearest-neighbor search into navigable graph traversal with a query-time escape hatch. Its hierarchy provides coarse-to-fine routing; its construction search and neighbor heuristic determine whether useful routes exist; M, efConstruction, and efSearch decide where memory, write cost, and read cost are paid.

The production task is therefore not to maximize recall in isolation. It is to build the smallest graph and perform the narrowest search that meet recall and result-completeness requirements under the real workload—including its filters, concurrency, cache state, and index lifecycle.

References