Measuring and Tuning Recall (ef_search)

Recall is a setting, not a given

At query time hnsw.ef_search (default 40) is the size of the candidate list searched: higher means better recall and more work. To measure it: choose a sample of real query vectors, compute the exact top-k for each with the index disabled (SET enable_indexscan = off), then compute the top-k with the index at several ef_search values and report the average overlap, recall@k. Note that ef_search should be at least k. Pick the lowest setting that meets your recall target (many applications target 0.95 to 0.99), and re-measure after data growth or parameter changes. HNSW construction is not perfectly deterministic, so exact recall numbers vary slightly between builds; in three builds here, ef_search=10 gave about 0.96 to 0.97, 40 about 0.985 and 200 about 0.998.

Recall against exact search, in SQL, run

I ran this SQL on PostgreSQL 16 with the pgvector extension, version 0.8.6, in a Docker container. 100 query vectors; the exact answers come from a forced sequential scan, then a small function measures overlap with the HNSW results at three ef_search values. Because HNSW builds vary slightly, the output shows threshold checks (all true) rather than exact fractions.

SET client_min_messages = warning;
CREATE TEMP TABLE queries AS SELECT id AS qid, embedding AS qv FROM big WHERE id % 200 = 0;      -- 100 query vectors

SET enable_indexscan = off;                                   -- force the exact (sequential) plan for ground truth
CREATE TEMP TABLE truth AS
  SELECT q.qid, array_agg(t.id) AS ids FROM queries q
  CROSS JOIN LATERAL (SELECT id FROM big b ORDER BY b.embedding <-> q.qv LIMIT 10) t GROUP BY q.qid;
RESET enable_indexscan;                                       -- now the HNSW index can be used again

DROP FUNCTION IF EXISTS recall_at(int);
CREATE FUNCTION recall_at(ef int) RETURNS numeric LANGUAGE plpgsql AS $$
DECLARE q record; found int[]; hit int := 0; total int := 0;
BEGIN
  EXECUTE format('SET LOCAL hnsw.ef_search = %s', ef);
  FOR q IN SELECT qid, qv FROM queries LOOP
    SELECT array_agg(id) INTO found FROM (SELECT id FROM big ORDER BY embedding <-> q.qv LIMIT 10) x;
    hit := hit + cardinality(ARRAY(SELECT unnest(found) INTERSECT SELECT unnest(ids) FROM truth WHERE truth.qid = q.qid));
    total := total + 10;
  END LOOP;
  RETURN round(hit::numeric / total, 3);
END $$;

SELECT recall_at(10)  >= 0.95  AS "ef_search=10 recall >= 0.95",
       recall_at(40)  >= 0.98  AS "ef_search=40 recall >= 0.98",
       recall_at(200) >= 0.995 AS "ef_search=200 recall >= 0.995";

Output:

 ef_search=10 recall >= 0.95 | ef_search=40 recall >= 0.98 | ef_search=200 recall >= 0.995 
-----------------------------+-----------------------------+-------------------------------
 t                           | t                           | t
(1 row)

Set ef_search at least as large as LIMIT

If ef_search is smaller than the number of rows you ask for, the index cannot return that many candidates.

Quick check: How do you measure the recall of an HNSW index?

• It cannot be measured
• Count its rows
• Read the table name
• Compare its results with exact search on a sample of queries