HNSW ef_search: Why Your Vector Search Misses the Right Chunk

The chunk was in the index. I checked three times.

A support bot kept answering "that isn't covered in the documentation" for a question that was covered, in one paragraph, in a doc we had ingested two weeks earlier. I pulled the row out of Postgres by ID. It was there. Embedding present, 1536 dimensions, right tenant, not soft-deleted. I ran BM25 over the same corpus and the passage came back at rank 2.

Vector search, top 20: not present. Not at rank 21 either. Just gone.

I spent a day blaming the embedding model. The actual culprit was a Postgres GUC with a default of 40: HNSW ef_search. Your vector index is not a database lookup. It is a graph walk that gives up early, on purpose, and nobody tells you when it gave up too early.

TL;DR

• HNSW is an approximate nearest-neighbor index. A vector being in the index does not mean the index will ever return it. Recall@k is a number you own, not a guarantee your vector DB provides.
• ef_search (pgvector hnsw.ef_search, Qdrant hnsw_ef, Weaviate ef) is the size of the candidate list the graph walk keeps in flight. pgvector's default is 40. If your LIMIT is anywhere near that, recall falls off a cliff.
• Metadata filters make it far worse: post-filtering throws away most of those 40 candidates after the walk, so a tenant filter can turn top-20 into top-2.
• Measure recall by running the same queries with an exact scan (SET LOCAL enable_indexscan = off) and comparing ID sets. Sweep ef_search, watch the recall curve flatten and the latency curve keep climbing. Stop where they cross.
• Under a few hundred thousand vectors, brute force is milliseconds. You may not need the graph at all.

Why does my vector search miss a chunk that's definitely in the index?

Because HNSW does not search your vectors. It walks a graph built over your vectors, and the walk is greedy.

Picture the index as a subway map with express layers stacked on local ones. The query enters at the top layer, where there are only a handful of nodes and the hops are long. It greedily moves to whichever neighbor is closer to the query vector, drops a layer when it can't improve, and repeats. At the bottom layer it does a proper best-first search over a candidate list.

That candidate list has a fixed size. That size is ef_search.

So a document gets skipped when the greedy walk never enters its neighborhood, or enters it but evicts it from a candidate list that was already full of nearer-looking-but-wrong neighbors. Both get more likely as your corpus grows, as your embeddings cluster (hello, boilerplate legal footers), and as ef_search shrinks toward k.

The nasty part: the failure is silent and query-dependent. Ninety-five queries look perfect. Five look like the document was never ingested. You go read the ingestion pipeline. The ingestion pipeline is fine.

What does HNSW ef_search actually do?

ef_search is the beam width at query time. Bigger beam, more of the bottom-layer graph gets explored, more chances to stumble into the right cluster.

Here's the whole knob surface in pgvector:

-- build time
CREATE INDEX ON chunks USING hnsw (embedding vector_cosine_ops)
  WITH (m = 16, ef_construction = 64);   -- these are the defaults

-- query time
SET hnsw.ef_search = 100;                -- default is 40
SELECT id FROM chunks ORDER BY embedding <=> $1 LIMIT 20;

Three things fall out of that:

ef_search bounds how many neighbors you can get. You cannot return more results than you kept candidates for. A LIMIT 40 against ef_search = 40 is asking the walk to be perfect on the first try. Keep k well under ef_search, not near it.

m and ef_construction are baked in at build time. m is how many neighbors each node keeps. Low m on a high-dimensional, clustered corpus produces poorly connected regions the walk struggles to reach, and no amount of query-time ef_search fully rescues a badly built graph. If your recall plateaus below what you need at ef_search = 500, the fix is rebuilding with higher m and ef_construction, not more beam.

Defaults differ per engine and they are not comparable. Weaviate ships ef: -1, meaning it derives the beam from your query limit at runtime. Qdrant exposes hnsw_ef per search request. Migrating from one to another and seeing "worse embeddings" is very often just a different default beam width.

Deletes matter too. Most HNSW implementations tombstone rather than surgically repair the graph, so a table that has churned hard for months walks through dead nodes and wastes beam on them. Periodic reindexing is a recall operation, not just a disk-space one.

How do I measure vector search recall@k?

Run the same queries twice: once through the index, once exact. Compare ID sets. That's it. In Postgres you can force the exact path by turning off index scans, which makes the planner sequential-scan and sort:

K = 20
def ann(cur, q):
    cur.execute("SET LOCAL hnsw.ef_search = %s", (EF,))
    cur.execute(
        "SELECT id FROM chunks ORDER BY embedding <=> %s LIMIT %s", (q, K))
    return {r[0] for r in cur.fetchall()}

def exact(cur, q):
    cur.execute("SET LOCAL enable_indexscan = off")
    cur.execute("SET LOCAL enable_bitmapscan = off")
    cur.execute(
        "SELECT id FROM chunks ORDER BY embedding <=> %s LIMIT %s", (q, K))
    return {r[0] for r in cur.fetchall()}

recall = mean(len(ann(cur, q) & truth[q]) / K for q in queries)

Use real production queries, not synthetic ones. Recall on random queries is flattering; recall on the weird, short, jargon-heavy queries your users actually type is where the graph walk falls apart.

Then sweep. Run ef_search at 40, 80, 160, 320, 640 and plot two lines: recall@k and p95 latency. The shape is always the same. Recall climbs steeply, then flattens hard. Latency keeps climbing, roughly linearly in ef_search, forever. You want the elbow, and you want to find your own elbow, because it moves with corpus size, embedding model, and how clustered your text is. Anyone who tells you "just use 100" is quoting a number from someone else's corpus.

Why do metadata filters destroy HNSW recall?

Because naive filtering happens after the graph walk, and the walk had no idea your filter existed.

Ask for 20 chunks WHERE tenant_id = 42 with ef_search = 40. The walk finds 40 globally nearest candidates across every tenant. Then the filter runs. If tenant 42 is 2% of your corpus, you keep roughly one. You asked for 20 and got 1, and nothing in the response says "I threw away 39."

This is why filtered vector search feels randomly broken. Recall is fine for your biggest tenant and catastrophic for your smallest, and both use identical code.

Ways out, roughly in order of how much I like them:

1. Partition the index by the filter. Separate index per tenant or per collection means the filter stops being a filter. Best recall, most operational work.
2. Turn on iterative scanning. pgvector 0.8 added hnsw.iterative_scan = relaxed_order (plus hnsw.max_scan_tuples), which keeps walking until it has enough rows that survive the filter instead of stopping at the first ef_search candidates.
3. Use filter-aware search. Qdrant, for instance, indexes payload fields and adapts its strategy for restrictive filters rather than blindly post-filtering.
4. Crank ef_search proportional to filter selectivity. Crude, works, gets expensive fast. If the filter keeps 1 in 50, you need roughly 50x the beam to see the same number of survivors.

What should I set ef_search to?

Start at 4x to 10x your k, measure, then tune to your recall target instead of your comfort level. Concretely: pick recall@k ≥ 0.95 as a product requirement, sweep, take the smallest ef_search that hits it on your production query log, and re-measure quarterly because the elbow drifts as the corpus grows.

Two more moves that beat tuning:

Over-fetch and rerank. Pull 100 candidates with a healthy ef_search, then run a cross-encoder reranker over them and keep 10. The graph only has to get the right chunk into the candidate set. The reranker handles ordering, which it does far better than cosine distance anyway.

Hybrid it. BM25 found my missing paragraph at rank 2 while the vector index couldn't see it at rank 20. Lexical search has no approximation step, so exact term matches never silently vanish. Fusing BM25 and vector results covers the exact failure mode HNSW creates.

And the unglamorous one: if you have 200k vectors, benchmark a flat exact scan before you build any graph. Modern SIMD brute force over a few hundred thousand embeddings is often single-digit milliseconds. An approximate index that you never tuned is strictly worse than an exact scan that can't be wrong.

The short answer

Your vector search skips the right chunk because HNSW is an approximate index whose query-time beam width, ef_search, defaults to a small number (40 in pgvector) that was chosen for latency, not for your recall. The graph walk keeps only that many candidates in flight, so any chunk the greedy descent doesn't reach, or that gets evicted from a full candidate list, is invisible no matter how good your embeddings are. Metadata filters compound it by discarding most of those candidates after the walk. Fix it by measuring recall@k against an exact scan on real queries, raising ef_search to the elbow of your own recall-versus-latency curve, partitioning or using iterative scan for filtered queries, and over-fetching into a reranker so the graph only has to be approximately right.

---

Written by the developer behind Preterview, an interview prep platform.

Comments

[Dean Lee]

pgvector ships ef_search at 40 because that keeps the graph walk cheap. A tenant filter then throws most of those 40 candidates away after the walk, so a LIMIT of 20 can return two survivors. The missing paragraph never raises an error. I would pay the extra milliseconds of a higher ef_search, or skip HNSW under a few hundred thousand rows, before I let a support bot invent a documentation gap that was sitting in Postgres.

[Dylan Couzon]

Great article!