Explain exactly what the ef_search knob on an HNSW index controls at query time.

Flashcard·Easy·4.0 · 0·~30s·Asked atPinecone

Attempt it

ef_search is the size of the dynamic candidate list maintained during the greedy graph descent at the base layer. At each step the search pops the closest unvisited node from the candidate list, expands its neighbors, evaluates their distances to the query, and re-trims the list back to ef_search entries.

Larger ef_search explores more of the graph before terminating, raising recall but increasing per query work roughly linearly. Smaller ef_search returns faster but may miss true nearest neighbors that the greedy walk did not happen to reach.

Unlike M (a build time graph degree parameter), ef_search is set at query time, so you can tune the recall latency tradeoff per request. Typical production range is 40-500; start at 40 and raise until the recall SLO is met. Some setups use low ef_search for cheap browsing queries and high ef_search for high-recall retrievals like RAG.

Your answer

**HNSW** (Hierarchical Navigable Small World) is the dominant ANN index type. Its three knobs are M, ef_construction, and ef_search. The first two are set at index-build time and baked into the index; ef_search is the only one set per query. **What ef_search does mechanically.** HNSW searches via greedy graph traversal at the base layer. Starting from an entry point, the search maintains a sorted list of candidate nodes ranked by distance to the query. At each step: 1. Pop the closest unvisited candidate from the list. 2. Look at its M graph neighbors. 3. Compute the distance from the query to each neighbor. 4. Add new neighbors to the candidate list. 5. Trim the list back to the top ef_search candidates. 6. Repeat until the closest unvisited candidate is farther than the K-th closest visited candidate (search has converged). ef_search is the maximum size of that candidate list. Bigger ef_search means the search considers more candidates before terminating, which raises recall (more chances to find true nearest neighbors) and per query work (more distance computations). **Typical values.** Defaults are usually 40-100. Production tuning lands between 40 and 500 depending on the recall SLO. To meet recall@10 = 0.95 on a well-tuned HNSW, ef_search around 80-200 is typical. **Per-request tuning.** Because ef_search is set at query time, you can change it without rebuilding the index. Common patterns: low ef_search for cheap autocomplete or browse queries, high ef_search for high recall RAG retrievals.

**ef_search is the maximum size of the dynamic candidate list maintained during HNSW's greedy graph descent at the base layer.** It is set at query time and is the primary lever for trading recall against per query latency in any HNSW deployment. **The search algorithm.** HNSW's search proceeds in two phases. First, traverse the upper layers (which contain progressively fewer nodes) greedily to find a near-query entry point at the base layer. Second, perform the bounded best first search at the base layer. The base-layer phase maintains two structures: a min-heap of unvisited candidates (sorted ascending by distance to query) and a set of the top-K results seen so far. ef_search bounds the candidate heap. At each step the algorithm: 1. Pops the closest unvisited candidate from the heap. 2. If it is farther than the K-th nearest result, terminate (the search has converged). 3. Otherwise, examine all M graph neighbors of the popped node. 4. For each unvisited neighbor, compute its distance to the query. Add to the heap and to the top-K results if it qualifies. 5. If the heap exceeds ef_search in size, drop the worst entries. **Why ef_search matters.** A larger ef_search keeps more 'second-best' candidates in the search frontier, which gives the algorithm more paths to explore and reduces the chance of getting stuck in a local minimum. For a randomly-built HNSW, recall@K typically follows an S-curve as ef_search increases: rapid gains from ef_search = 10 to 50, diminishing returns past 200, and asymptote near 1.0 around 500-1000. **Latency cost.** Per-query latency scales roughly linearly with ef_search because each search step does work proportional to the candidate-list size (distance computations to all newly-discovered neighbors). Doubling ef_search roughly doubles latency. **Typical values.** Defaults vary by vendor: Faiss defaults to 16, pgvector defaults to 40, Pinecone/Weaviate/Qdrant default to 100.

Quick reference

TL;DR

ef_search bounds the dynamic candidate list maintained during the HNSW greedy walk at the base layer. Larger = wider exploration = higher recall + more work per query. Set per query at runtime; typical range 40-500.

Memory aid

Easy to grasp

Imagine HNSW like a hiker hopping between viewpoints, always heading to whichever nearby viewpoint looks best. When HNSW searches for the closest vectors, it walks a graph by always jumping to the most promising node it can see. **ef_search is the size of its 'shortlist' of promising candidates to keep around.** A bigger shortlist means it considers more possibilities before settling, finding better answers but doing more work. A smaller shortlist is fast but sometimes commits to a so-so answer too early. You can change this number for every query: tiny number for cheap browsing, big number for important retrievals.

Key concepts

HNSW

Detailed answer & concept explanation

~4 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.

Quick scan · 2–4 min

Everything important, quickly.

2 min: name the dynamic-candidate-list mechanism + recall/latency tradeoff + distinguish from M and ef_construction + typical production range + Flat-ground-truth tuning.

Side-by-side

Knob	Phase	Tunable per query	Affects recall	Affects build cost	Affects per query latency
M	Build	No (rebuild required)	Yes (ceiling)	Yes (significant)	Modest
ef_construction	Build	No (rebuild required)	Yes (ceiling)	Yes (significant)	No
ef_search	Query	Yes	Yes (within ceiling)	No	Yes (linear)

Real-world examples

Real products, models, and research that use this idea.

pgvector exposes ef_search via SET hnsw.ef_search = N per session; production RAG deployments commonly use 40-160.
Qdrant lets ef_search be overridden per query, supporting tier based adaptive retrieval.
Faiss HNSW indexes set index.hnsw.efSearch before each batch of queries.
Production RAG at Notion, Glean, and similar B2B products tunes ef_search per workload tier (cheap autocomplete vs. high stakes retrieval).
ANN-Benchmarks publishes recall-vs-latency curves swept over ef_search; the S-curve shape is visible across all HNSW implementations.

Interviewer follow-ups

What an interviewer would ask next. Try answering before peeking at the approach.

QWhat is the right ratio between ef_search and ef_construction?

QHow does ef_search interact with a selective metadata filter on HNSW?

QWhy does the recall-vs-ef_search curve look like an S?

Don't say this

Red flags and common mistakes that signal junior thinking. Click to expand.

Most common mistake

Conflating ef_search with M or ef_construction. M and ef_construction are build time, baked into the index. ef_search is runtime tunable per query; changing it does not require a rebuild.

60-second cheat sheet

The night-before-the-interview bullets. Scan these on the way to the call.

References

Primary sources. Skim if you want the original framing.