Your Vector Search Got Faster and Recall Fell Off a Cliff

The latency graph looked like a win. Someone had tuned the vector index over the weekend, and p99 for semantic search dropped from around 200ms to 25ms. The dashboard was green, the change shipped, everyone moved on.

Two weeks later a different graph started climbing: support tickets. Search "felt dumb." The RAG assistant kept missing answers that were obviously in the knowledge base — type in almost the exact wording of a document and it still wouldn't surface. Nothing had errored. Nothing had paged. The index was returning ten results for every query, fast, every time. They were just increasingly the wrong ten.

Why approximate search fails quietly

Any production vector search runs on an approximate nearest neighbor (ANN) index, because exact nearest-neighbor over millions of high-dimensional embeddings means scanning every row. ANN indexes buy their speed by not looking at most of your data on each query — and every one of them exposes a knob that controls exactly how much they skip.

pgvector IVFFlat partitions vectors into lists clusters at build time; ivfflat.probes decides how many clusters a query actually scans.
pgvector HNSW walks a proximity graph; hnsw.ef_search sets how wide the candidate frontier is during the walk.
AlloyDB ScaNN builds a tree of num_leaves partitions over quantized vectors; scann.num_leaves_to_search decides how many of those partitions a query visits, and scann.pre_reordering_num_neighbors controls how many candidates get rescored with full-precision distances before the top k is returned.

These knobs all trade the same two things against each other: recall (did I actually find the true nearest neighbors?) versus latency (how fast did I answer?). Turn them down and the query touches fewer candidates, so it gets faster — and starts missing true matches. The pathological part is the failure mode. A too-aggressive setting doesn't throw. It doesn't return fewer rows. It returns k rows drawn from a smaller, wronger pool, and the API shape is identical to a perfect answer. Latency is loud and easy to graph; recall is silent and nobody instruments it. So recall is the thing that rots.

And the curve is not gentle. Recall against these knobs is steeply non-linear: over part of the range you can cut candidates hard and barely lose anything, and then you cross a threshold where recall collapses. Someone tuning purely by watching the latency number has no way to see which side of that cliff they landed on.

Measuring the thing that actually matters

Recall has a precise definition, and you can compute it directly. Ground truth is the exact nearest neighbors — the ones a brute-force scan would return. Recall@k is the fraction of those true top-k that your ANN index actually returned, averaged over a representative set of queries.

The trick is getting the exact answer out of the same database. In pgvector, force a sequential scan and the distance operator computes exact distances, bypassing the index entirely:

-- Exact top-10 (ground truth): disable index scan so it brute-forces.
SET LOCAL enable_indexscan = off;
SET LOCAL enable_bitmapscan = off;
SELECT id
FROM   docs
ORDER  BY embedding <=> :query_vec
LIMIT  10;

-- Approximate top-10 from the ANN index, at the tuning you want to test.
SET LOCAL enable_indexscan = on;
SET LOCAL hnsw.ef_search = 40;          -- the knob under test
SELECT id
FROM   docs
ORDER  BY embedding <=> :query_vec
LIMIT  10;

Recall@10 for that query is |exact ∩ approx| / 10. Do it over a fixed sample of real queries — a few hundred is plenty to see the shape — and average. Here's the whole harness, small enough to live next to your test suite:

import psycopg
import statistics

def topk(cur, qvec, k, exact):
    if exact:
        cur.execute("SET LOCAL enable_indexscan = off")
        cur.execute("SET LOCAL enable_bitmapscan = off")
    else:
        cur.execute("SET LOCAL enable_indexscan = on")
        cur.execute("SET LOCAL hnsw.ef_search = %s", (EF_SEARCH,))
    cur.execute(
        "SELECT id FROM docs ORDER BY embedding <=> %s LIMIT %s",
        (qvec, k),
    )
    return {row[0] for row in cur.fetchall()}

def recall_at_k(conn, queries, k=10):
    scores = []
    with conn.cursor() as cur:
        for qvec in queries:
            truth = topk(cur, qvec, k, exact=True)
            got   = topk(cur, qvec, k, exact=False)
            scores.append(len(truth & got) / k)
    return statistics.mean(scores)

# queries = a fixed, version-controlled sample of real query embeddings
print(f"recall@10 = {recall_at_k(conn, queries):.3f}")

Run that same sample through the AlloyDB ScaNN knobs and you get a table you can actually make decisions from. The following numbers are illustrative — the point is the shape, which is what you'll see when you run this on your own data:

num_leaves_to_search   p99 latency   recall@10
        5                 14 ms        0.61     <- shipped "for speed"
       20                 28 ms        0.86
       50                 52 ms        0.94
      100                 95 ms        0.98     <- floor you actually wanted

The weekend change in the opening was the top row: someone found the setting that made latency beautiful and stopped there, four points of the curve too far left.

Making recall a first-class signal

Once you can compute recall, the fixes are mostly about not letting it drift out of sight again.

Put recall in CI next to the latency benchmark. A performance test that only asserts on latency will happily green-light a change that halves recall. Assert on both, and fail the build if recall drops below an explicit floor:

def test_search_quality():
    r = recall_at_k(conn, GOLDEN_QUERIES, k=10)
    assert r >= 0.90, f"recall@10 regressed to {r:.3f} (floor 0.90)"

Tune to a recall target, not a latency target. Decide the recall floor first — for RAG feeding an LLM, retrieval misses are answers the model literally cannot get right, so this floor is a product decision, not a knob. Then find the cheapest setting that clears it. That's the opposite of tuning latency down until someone complains.

Right-size the build parameters, not just the query knobs. Query-time knobs can only recover recall the index structure allows. If lists (IVFFlat) or num_leaves (ScaNN) is far off — a common heuristic starting point is on the order of the square root of the row count — you'll be forced to scan a large fraction of partitions to hit your recall floor, which throws away the speed the index was for. And ANN recall drifts as data grows and the vector distribution shifts, so recompute it on a schedule, not once at launch.

Watch for the quantization tax. ScaNN and other quantized indexes compress vectors, so the initial ranking is done on approximate distances. That's what pre_reordering_num_neighbors is for: it pulls a wider candidate set, then rescores those with full-precision vectors before returning the top k. Set it too low and you get fast, cheap, subtly-wrong rankings — the same silent failure in a second location. It shows up in exactly the same recall measurement, which is the point: one number catches all of these.

Lesson

Approximate search is a deliberate trade of accuracy for speed, and a trade you don't measure is one you'll make badly. Latency instruments itself — it's on every dashboard — so it's the metric that gets optimized, and recall is the metric that silently pays for it. If your vector search feeds anything a user or a model relies on, recall@k belongs next to p99 in CI and in monitoring, with a floor you refuse to ship under. A speedup that quietly returns worse answers isn't a speedup; it's an outage that never fires an alert.

Hitting something like this in production? I help teams with performance engineering, SRE/observability, and AI-driven root cause analysis — work with me.

Search This Blog

Lets Architect the Performance Engineering