HNSW Tuning: Find the Recall, Latency, and Cost Operating Point

[Definition] HNSW tuning is the process of selecting graph connectivity and search breadth so approximate nearest-neighbour retrieval meets a required Recall@k and tail-latency target at an acceptable memory and indexing cost.

The system-design triangle

Vector retrieval has three competing outcomes:

             Recall
               ▲
              / \
             /   \
            /     \
        Cost ───── Latency

Higher recall usually means exploring more graph candidates, building denser connections, or storing higher-precision vectors. Each can increase latency, memory, build time, or all three. There is no universal best configuration—only a defensible operating point for a workload.

The three HNSW parameters that matter

M: graph connectivity

M is the maximum number of neighbour links a node retains. A common starting point is 16. Consider 32 when high recall matters more than memory.

memory per vector ≈ vector bytes + (M × link bytes)

Increasing M can help difficult, high-dimensional or clustered data, but it is an index rebuild decision. Do not change it first if query-time recall is slightly low.

ef_construction: build-time quality

During insertion, HNSW considers ef_construction candidates before choosing neighbours. A practical baseline is often 100–256. More candidates usually produce a navigable graph, but indexing takes longer and the benefit eventually plateaus.

ef_search: the first query-time lever

ef_search controls how many candidates are explored for a query. It is normally the safest first tuning knob because it changes query quality without rebuilding the index.

The actual numbers depend on data, dimensions, filters, model, and hardware. Measure them; do not copy them as a service-level objective.

Tune with exact ground truth

Approximate recall cannot be measured from approximate results alone. Build a held-out query set, run exact kNN for its ground truth, then compare HNSW output:

Recall@10 = |top10_HNSW ∩ top10_exact| / 10

For graded relevance, also report NDCG@10. Exact kNN can be too expensive for every production request, but it is essential for an offline benchmark sample.

A repeatable tuning loop

1. ▸Freeze the variables. Pin the embedding model, normalization rule, document corpus, chunking scheme, metadata filters, and top-k.
2. ▸Create a representative query set. Include head queries, rare terminology, multi-document questions, and important business slices.
3. ▸Build the baseline. Start with M=16, ef_construction=200–256, and ef_search=100 unless the engine has stronger defaults.
4. ▸Sweep ef_search. Test values such as 50, 100, 150, 200, and 300; record Recall@k, NDCG, P50/P95/P99, and QPS.
5. ▸Pick the lowest value that reaches the quality target. If recall plateaus below target, rebuild with higher M or ef_construction.
6. ▸Re-test filters and load. Metadata filters, concurrency, cache state, segment count, and tail load can invalidate a quiet benchmark.
7. ▸Version the result. Record index parameters, corpus version, embedding model, benchmark set, and acceptance thresholds.

Read the curve, not one score

Recall@10
1.00 |                         ●
0.98 |                    ●
0.96 |               ●
0.94 |          ●
0.92 |     ●
     +-----+-----+-----+-----+---- ef_search
      50   100   150   200   300

If recall rises sharply from 50 to 100 but barely changes after 150, the extra query work above 150 is likely not useful. This plateau is more informative than a generic recommendation such as “set ef_search to 500.”

Filters, segments, and the hidden latency costs

HNSW settings are not the only levers.

Pre-filter versus post-filter

Highly selective metadata filters can reduce the candidate set before vector traversal. Post-filtering may return too few eligible neighbours even when the underlying vector result is good. Test filter-heavy query slices separately.

Segment management

After a bulk load, merged/optimized segments can improve search latency substantially. Many small segments multiply graph traversal overhead. Treat index lifecycle operations as part of the benchmark, not an unrelated operations task.

Request caching

Caching repeated semantic queries improves latency and cost but says nothing about raw HNSW quality. Report cached and uncached performance separately.

Memory and storage choices

Before increasing infrastructure, check whether vector representation is the real cost driver.

Quantization changes the retrieval problem. Re-run the same ground-truth suite after every representation change.

Workload decisions

Free concepts, Pro tuning workflow

The article and its benchmark method are public. The Pro search path turns the method into a guided practice: build the ground-truth set, sweep parameters, inspect recall/latency curves, choose a storage tier, and document the resulting service-level objective. A Live Cohort capstone adds review of the index design and production runbook.

Next steps

1. ▸Read kNN and HNSW for graph mechanics.
2. ▸Read Measuring Search Quality for NDCG and benchmark design.
3. ▸Read Quantization before changing vector precision.
4. ▸Use the learning roadmap to see where index tuning fits the Pro production-search path.