Tuning HNSW Parameters Against a Recall Target You Can Measure

The harness needs two query paths against the same data: exact and approximate. In PostgreSQL with pgvector, exact search means forcing a sequential scan, and approximate search uses the index. The pattern below computes both and stores the recall per query.

-- Ground truth: force a sequential scan, keep the ids
SET LOCAL enable_indexscan = off;
CREATE TEMP TABLE golden AS
SELECT q.id AS query_id, n.doc_id, n.rank
FROM queries q
CROSS JOIN LATERAL (
  SELECT doc_id, row_number() OVER (ORDER BY embedding <-> q.embedding) AS rank
  FROM docs
  ORDER BY embedding <-> q.embedding
  LIMIT 10
) n;

Then measure the approximate side at a given ef_search:

SET hnsw.ef_search = 64;
WITH approx AS (
  SELECT q.id AS query_id, n.doc_id
  FROM queries q
  CROSS JOIN LATERAL (
    SELECT doc_id FROM docs ORDER BY embedding <-> q.embedding LIMIT 10
  ) n
)
SELECT count(*) FILTER (WHERE g.doc_id IS NOT NULL)::float
       / (count(DISTINCT g.query_id) * 10) AS recall_at_10
FROM golden g
LEFT JOIN approx a ON a.query_id = g.query_id AND a.doc_id = g.doc_id;

Two practical notes. First, verify the approximate query actually uses the index with EXPLAIN; pgvector guidance is explicit that some query shapes fall back to a scan, and a silent fallback makes recall look perfect while latency is missing Crunchy Data. Second, run the harness inside a transaction with SET LOCAL so a forgotten enable_indexscan = off does not poison later measurements.

If you use a dedicated vector database, the same logic applies. Qdrant exposes an exact mode via search_params=models.SearchParams(exact=True), and the tutorial includes a ready-made Python helper that returns average recall@k for a list of query vectors Qdrant.

HNSW builds a layered proximity graph. Each vector is a node, and each node keeps a bounded list of neighbors per layer. m is that bound. ef_construction is the size of the candidate list maintained while inserting a node, so it controls how carefully the builder looks for good neighbors before committing edges.

The consequences are asymmetric:

m is the only parameter that costs memory, so it is the one to economize on. ef_construction is a pure build-time cost, and ef_search is a pure query-time cost. That asymmetry is the whole tuning strategy: spend on ef_construction once during a nightly build, spend on ef_search only as far as your latency budget allows, and keep m as small as the recall ceiling permits.

There is a blunt caution from practice. Build parameters "will slow the speed of index build drastically, while not improving performance" in the sense of speed, though they may raise answer accuracy, per Crunchy Data's write-up Crunchy Data. Treat every increment as something to justify with a measurement.

Build time is not a minor concern at scale. A pgvector user indexing partitions of roughly 40 million rows with m = 16, ef_construction = 200 saw the build stall after the graph outgrew maintenance_work_mem, and the maintainer's remedies included dropping back to the default ef_construction of 64 to build faster pgvector issue 822. Parallel builds help: pgvector's parallel index build was reported to improve HNSW build time by a factor of 30 in tests on a 10 million row, 1,536-dimension dataset Neon.

pgvector's documented index size estimate is (4 * m + 8 * (m + 1)) bytes per vector for the graph, before the vector data and identifiers. Worked example with 768-dimensional float32 embeddings, 1 million rows:

• Vector data: 768 × 4 bytes = 3,072 bytes per vector, or about 3.07 GB for 1 million rows.
• Graph at m = 16: 4 × 16 + 8 × 17 = 64 + 136 = 200 bytes per vector, about 0.20 GB.
• Graph at m = 32: 128 + 264 = 392 bytes per vector, about 0.39 GB.
• Graph at m = 64: 256 + 520 = 776 bytes per vector, about 0.78 GB.

So moving from m = 16 to m = 64 adds roughly 0.58 GB on a graph that already sits under 1 GB, but the vector data dominates at 3 GB. The lesson: on unquantized float32 embeddings, m is a rounding error next to the vectors themselves. Choose a reasonable m and stop optimizing it. Where m starts to matter is after you shrink the vectors.

That is why the pgvector maintainer's advice for large datasets is to use halfvec or binary quantization with re-ranking to reduce index size pgvector issue 822. Halving the vector bytes does more for your memory budget than any m reduction. OpenSearch documents the same arithmetic from the other direction: a compression_level of 32x takes a 768-dimensional float32 vector from 3,072 bytes to 96 bytes OpenSearch. Compression is the big lever; m is the fine one.

For an order-of-magnitude sanity check on the algorithm family: HNSW is generally reported to reach 95 percent or higher recall out of the box while using two to five times more memory than IVFFlat BigData Boutique. If your sweep cannot approach 0.95 at any setting, suspicion should fall on embedding quality or chunking before it falls on the index.

Keep one variable fixed to make the grid readable: set ef_construction to four times m. This is a heuristic, not a law, but it couples graph quality to graph degree so cells are comparable.

Procedure:

1. Build the index at the first m. Record build wall time and pg_relation_size for the index.
2. For each ef_search, run the harness and record recall@k and p50/p95 query latency.
3. Rebuild at the next m and repeat. Rebuilds are the expensive part; do them overnight.
4. Plot recall against p95 latency. The frontier is the lower-right staircase of points; configurations below it are dominated.
5. Pick the leftmost point whose recall clears the threshold by a comfortable margin, not exactly at it. A margin of a couple of points absorbs drift from new data.

Recall should rise with ef_search and then flatten. The flattening point is the ceiling that m and ef_construction set. If raising ef_search from 256 to 512 buys nothing, you are at the ceiling and must raise m to move it. Qdrant's documentation says the same thing: if hnsw_ef alone does not reach the target, m and ef_construct set the ceiling and changing them requires a rebuild Qdrant.

A worked decision. Suppose your threshold is recall@10 of 0.95 and your p95 budget is 40 ms. The sweep returns 0.93 at m = 16, ef_search = 128 with 18 ms, and 0.96 at m = 16, ef_search = 256 with 31 ms. The second cell wins: it clears the target with margin and leaves headroom in the latency budget. Now suppose the next cells show 0.96 at m = 32, ef_search = 256 with 44 ms. It is over budget and buys no recall, so it is dominated and discarded. The decision rule is always the same: among cells that clear the recall threshold, take the one with the lowest p95 that still leaves margin, and prefer the smaller m when latency ties.

One caveat about what recall@k measures. A paper on ANN evaluation argues that Recall@k counts identifier matches and overstates the cost of approximation, and that distance-based measures such as the inverse approximation ratio track downstream quality more faithfully, remaining stable even when Recall@k drops substantially arXiv. Practical reading: use recall@k as your tuning target because it is cheap and unambiguous, but if two configurations differ by half a point, break the tie with a downstream evaluation rather than with more recall math. Additional metric definitions are covered in this evaluation metrics overview.

An approximate index does not fail loudly. It returns k plausible neighbors, silently omitting some true ones, with no error and no log entry, which is why tooling like pg_recall_guard exists to compare a live index against approved ground truth and report drift. You can build the same loop with the harness above: run it on a schedule, store the recall figure, and alert when it drops below the margin you chose.

Two things cause drift in practice. Deletes leave dead entries that the graph still traverses, and growth shifts the neighbor structure. pgvector's HNSW does support update and delete, and the algorithm is designed for incremental addition rather than requiring a fully populated table before the build Jonathan Katz. That is a comfort, not a guarantee: schedule a recall check after bulk changes as well as on a calendar.

Wire the check into continuous integration. Fail the build when recall falls below the threshold, which catches regressions from an embedding model swap or an index configuration change before they reach users, exactly the pattern Qdrant recommends Qdrant. If you run hybrid retrieval with BM25 and reciprocal rank fusion alongside dense search, keep the ANN recall check separate from relevance scoring: rank fusion can mask a degraded vector index because the lexical arm keeps returning good results.

Finally, revisit m when the data changes character, not on a schedule. New document types, a different embedding model, or a shift in query length can move the recall ceiling. Re-run the sweep on the same golden set and compare.

When the tuning is done and you would rather spend the engineering time on retrieval quality than on running five embedding models behind five different APIs, Quanta Inference puts text, image, video, audio and embedding models behind one OpenAI-compatible key at https://quantaintelligence.ai/inference.