The recall cliff appears when eligible documents are rarer than the search budget

Pushing a predicate into the engine fixes the previous chapter's failure completely, and it does not fix filtered search. An index that can see the predicate still has to find eligible documents by walking a structure that was built without knowing the predicate existed, and it walks that structure for a bounded amount of time. That bound is the subject here. When eligible documents are plentiful the bound is irrelevant. When they are scarce the bound becomes the only thing that matters, and the point where one turns into the other is the recall cliff.

Two terms need pinning down before the measurements mean anything. Recall@k is the fraction of the true k nearest eligible documents that the search actually returned, so a recall@10 of 0.5 means the index found five of the ten documents an exhaustive comparison would have picked. The search budget is the engine's cap on how much of the index a single query is allowed to touch: on a graph index it is a count of candidate nodes held in play, and on a cell-based index it is a count of clusters probed. Both are set at query time, both are what makes approximate search fast, and neither has any relationship to how many documents the query's predicate matches.

Building a collection where selectivity is a dial#

The reason to reproduce this deliberately, rather than wait for a customer to find it, is that the failure is a smooth function of one variable you can control. Selectivity is a knob, and if you turn it slowly the results do not degrade slowly. They hold steady, then fall off over about one order of magnitude, and by the far end of the sweep the index is returning two results out of ten with no error at any layer of the stack.

The setup is a synthetic attribute added at ingest time to every document in a copy of the production index. Give each document a uniformly random integer bucket in [0, 10000), index that attribute alongside the real ones, and any selectivity between 0.01% and 100% becomes a range predicate. The construction is worth a moment, because it is what makes the sweep an instrument rather than an anecdote. A predicate bucket < c matches every document whose draw came out below the cutoff c, and since the draws are uniform over ten thousand values, the fraction matching is c divided by ten thousand. Setting the cutoff sets the selectivity directly, with no counting required.

Uniform assignment matters for a second reason. It decorrelates eligibility from position in embedding space, which isolates the mechanism from the clustering effects that made the previous chapter's failure look intermittent. A real predicate and this synthetic one differ in exactly that respect, and the synthetic one is the harder case, which is the right way round for a measurement.

import random, statistics

random.seed(7)
for batch in read_corpus():           # 10.2M chunks
    index.upsert([
        {"id": d.id, "values": d.vec,
         "metadata": {**d.metadata, "bucket": random.randrange(10000)}}
        for d in batch
    ])

# ground truth: exhaustive scan of the eligible set, per query
def exact_top_k(q_vec, cutoff, k=10):
    eligible = ((i, v) for i, v, b in corpus_iter() if b < cutoff)
    return [i for i, _ in sorted(
        eligible, key=lambda p: -cosine(q_vec, p[1]))[:k]]

SWEEP = [1000, 300, 100, 30, 10, 3, 1]   # bucket cutoffs
for cutoff in SWEEP:
    returned, recalls, latencies = [], [], []
    for q in QUERY_SET:                    # 500 held-out real queries
        t0 = time.perf_counter()
        hits = index.query(vector=q.vec, top_k=10,
                           filter={"bucket": {"$lt": cutoff}})
        latencies.append((time.perf_counter() - t0) * 1000)
        truth = set(exact_top_k(q.vec, cutoff))
        returned.append(len(hits))
        recalls.append(len(truth & {h.id for h in hits}) / len(truth))
    print(cutoff / 10000, statistics.mean(returned),
          statistics.mean(recalls), statistics.median(latencies))

Run the cutoffs in SWEEP through the division above and they land on the seven selectivities the sweep reports: a thousand out of ten thousand is 10%, three hundred is 3%, and so on down to one in ten thousand, which is 0.01%. The list is a geometric ladder rather than an even one — each step is roughly a third of the one before — because the phenomenon is logarithmic in selectivity and an evenly spaced sweep would put six of its seven points on the flat part of the curve.

The ground truth here is the expensive part and the part people skip. Computing recall requires knowing what the true k nearest eligible documents are, which means an exhaustive comparison against every eligible vector. Recall measured against the index's own unfiltered answer is not recall; it is agreement between two approximations, and two approximations that share a build and a traversal agree with each other far more readily than either agrees with the truth. The exact scan over the eligible set is what defines the correct answer, and on 10.2M vectors of dimension 768 a single exact scan takes roughly 4-8 seconds on one core, so 500 queries across 7 selectivity levels is a few hours of batch work — cheap next to the customer conversations it replaces.

Running that sweep against an HNSW index built with M = 16, meaning each node keeps sixteen outgoing edges to nearby nodes, and queried at ef_search = 128 produces a shape that shows up, with different constants, on every graph index:

Check the second column before trusting any of the others. Each entry is the selectivity applied to the 10.2 million stored chunks: a tenth of 10.2 million is 1,020,000, a hundredth is 102,000, and a ten-thousandth is 1,020. Every row reproduces exactly, with nothing left over. That closure is not decoration — it is the evidence that the bucket attribute behaves as advertised and that the engine's predicate evaluation agrees with the arithmetic. A row where the eligible count missed its selectivity would mean the dial was not connected to the thing it claims to turn, and every other column in the table would be measuring an unknown.

Reading the sweep as three failures on different schedules#

The three measured columns are doing different jobs, and the useful way to read them is by the size of the step between rows rather than by the level in any one row.

Recall falls first. Between the top two rows it gives up two hundredths, between the next two about five hundredths, and then the steps widen sharply: seventeen hundredths, twenty-five, twenty-two. The steepest part of the descent is between 0.3% and 0.1% selectivity, and by 1% — three rows from the top — recall has already lost the better part of a tenth of its value. Nobody notices, because ten results still come back and they are still plausible. They are simply not the right ten.

The result count moves a full order of magnitude later. It sits pinned at 10.0 for the first three rows, gives up two tenths of a document at 0.3%, and only then collapses: nearly two documents at the next step, three and a half at the one after. The first row where a human could see something wrong is 0.3%, and by then recall has already fallen by a quarter of its starting value.

That offset is the trap in this table, and it names the stumble. A reader who watches result counts will conclude that a full page means a healthy query, because a full page is what a healthy query returns. But the count is 10.0 at 0.98 recall and 10.0 at 0.91 recall and 10.0 at 0.96 recall — it does not move while recall moves by seven hundredths. A quantity that stays fixed while the dangerous property varies cannot rank queries by that property, so the result count is not a weak proxy for recall. It is not a proxy for recall at all across the entire band where the damage starts.

Latency tells the third story, and it is the one that explains the mechanism. The steps up are three, five, twelve, seventeen, fourteen and nine milliseconds: the rise accelerates through the middle of the sweep and then decelerates near the bottom. A cost that flattens out is a cost that has hit a ceiling. By the last two rows the walk is no longer searching harder — it is spending its full allowance and stopping, which is exactly what a fixed budget predicts and exactly what the collapsing result count implies. Two columns measured independently agree that something is capped, and neither would be persuasive alone. And 71 ms sits comfortably inside a 200 ms budget, so nothing here will ever page anyone.

The pattern is not specific to a synthetic attribute. Yudhiesh Ravindranath's write-up The Achilles Heel of Vector Search: Filters runs a similar sweep on real data and lands on the same shape, which is worth reading if you want a second set of measurements from a different engine before you trust these.

Once the sweep exists it is worth keeping, because it is the only artefact that tells you where your own cliff sits, and the position moves whenever anything upstream changes. Doubling the collection at fixed absolute filter cardinality pushes every predicate to the right along the selectivity axis and drags the whole curve down. Rebuilding with M = 32 instead of 16 gives each node twice as many edges, which improves subgraph connectivity and shifts the cliff maybe half a decade later, at roughly double the index memory. Changing embedding models redistributes the documents in space and changes how eligible ones cluster. A number measured once against last quarter's index is a historical fact, not a property of the system, so the sweep belongs in a scheduled job rather than in a document.

Why the walk runs out#

A graph search maintains a bounded candidate list — ef_search entries — and repeatedly expands the nearest unvisited candidate, scoring its neighbours and keeping the best ones. With a filter applied during traversal, ineligible neighbours are scored for navigation but rejected from the result list, so each expansion contributes to the work budget and, when eligible documents are rare, contributes nothing to the answer.

The arithmetic is the same product as the previous chapter's, with a different count in it. There the count was k, the page size, and the question was how many of the index's answers survive the predicate. Here the count is the candidate budget, and the question is how many of the nodes the walk touches are eligible in the first place. Explore 128 candidates in a collection where 1 in 10,000 documents is eligible and the expected number of eligible documents encountered is 128 multiplied by one ten-thousandth, which is 0.0128 per query — about one eligible document for every eighty queries, if the walk moved at random.

It does better than random, because it moves toward the query vector and eligible documents near the query are what you are looking for. The sweep says how much better. At that selectivity the walk returns a mean of 1.9 results, against a random tour's expectation of 0.0128, so navigation is buying roughly a factor of a hundred and fifty. That is a large constant and it is still a constant. Drop the selectivity by another decade and the random expectation drops by a decade too, while the navigational bonus does not grow to compensate: it is a fixed multiplier applied to a quantity that is falling geometrically.

Budget exhaustion is only half of it. The more stubborn half is that the eligible documents, viewed as a subgraph, are usually not connected. Follow the causal chain, because each link is checkable on its own. HNSW builds each node's neighbour list from every document in the index, so a node's 16 out-edges point at its 16 nearest neighbours regardless of metadata. Metadata therefore had no influence on which edges exist. Delete every ineligible node from the picture and each surviving node keeps only those of its 16 edges that happened to land on another survivor. At one eligible document in ten thousand, that is a low expectation per node. So most survivors have zero surviving out-edges, and whole pockets of eligible documents have no path to them from the entry point:

The two eligible nodes on the right are three ineligible hops from the entry point. Count them by walking the path: the search must step onto B, then onto F, then onto G, and only from G do H and I come into view. Three of those landings are on nodes that can never be returned. The eligible node on the left costs one such landing, on A, which is why it is found. An implementation that skips ineligible nodes outright never reaches the right-hand pair at all; an implementation that traverses through ineligible nodes can reach them, but only by spending budget on the intermediate hops, which is why traversing-through engines are slower and more accurate than skipping engines at the same ef_search. Neither implementation can conjure a short path that the graph does not contain.

Cell-based indexes reach the same place by a different route, and the same product predicts it. An inverted-file index partitions the documents into clusters and probes nprobe of them, so the work budget is expressed in cells rather than candidates. With 4,096 cells over 10.2M vectors, each cell holds about 2,500 vectors — 10.2 million divided by 4,096 — so probing 32 of them touches 80,000 vectors, and at 0.01% selectivity a ten-thousandth of 80,000 is roughly 8 eligible documents. That is better than the graph's 1.9 because a cell scan is exhaustive within the cells it touches, where a graph walk visits only what its edges offer. But the eligible documents are spread across all 4,096 cells rather than concentrated in the 32 nearest to the query, so the ones in unprobed cells are as unreachable as the disconnected pockets in the graph. Raising nprobe to 512 fixes recall and costs a scan of 1.28M vectors, which is more work than scanning the 1,020 eligible ones by a factor of 1,250.

This also explains why the obvious knob only buys so much. Raising ef_search from 128 to 512 at 0.03% selectivity moves the mean result count from 4.6 to 8.2 and recall from 0.27 to 0.55, at a p50 of 210 ms. Set the two ratios beside each other: the budget went up fourfold and recall went up about twofold, so four times the work bought roughly twice the recall, and the query is now slower than a plan that ignores the index entirely. The relationship between budget and filtered recall is sublinear in a way it is not for unfiltered search, and the subgraph argument says why. Extra budget buys extra hops. Extra hops only help if there are edges to follow, and the useful edges were never built.

One symptom, two causes, and only one of them has a fix#

Budget exhaustion looks identical from the outside to the post-filter starvation of the previous chapter — a short result list, a 200 response, nobody paged — and the two get merged into a single folk diagnosis of "filters break search". Keeping them apart matters because the fixes are different and one of them is a trap.

Post-filter starvation is a plan bug. The predicate was invisible to the search, and pushing it into the engine fixes it completely, at every selectivity. The recall cliff is a property of the index structure interacting with the predicate, and it survives pushing the predicate down, survives raising top_k, and survives raising ef_search in the sense that it moves rather than disappears. If you diagnose the second as the first, you will ship the pre-filter change, watch the metric improve for the loose filters that dominate your traffic, and conclude the problem is solved while the tight filters keep failing.

The cliff is also not evidence that the index is misconfigured or the vendor is at fault. Every approximate index trades recall for speed, and the trade is calibrated during construction against every document that was present. A filter changes which documents the query is really running against, after the calibration happened, and no amount of build-time tuning anticipates a predicate that a user will invent tomorrow in a sidebar.

Filtered ANN is an active research area rather than a settled one, which is worth knowing when you read benchmark numbers. The classic ANN-Benchmarks suite measures unfiltered recall, so a leaderboard position tells you little about behaviour under a selective predicate; the NeurIPS 2023 Big-ANN competition added a filtered track precisely because the unfiltered numbers were not predicting production behaviour. Recent work on filter-aware graph construction — building extra edges so that the subgraph induced by common predicates stays connected — improves the picture at the cost of larger indexes and predicates that must be known at build time. That last condition is the binding one: it is a design decision to declare your predicates up front, and it is available only where the predicates are known, which excludes every filter a user composes in a sidebar. None of it removes the cliff for an arbitrary ad-hoc filter.

Look at the bottom row of the sweep table again with an engineer's eye rather than a benchmarker's. At 0.01% selectivity there are 1,020 eligible vectors. Scoring 1,020 vectors of dimension 768 against a query means one multiply-add per component per vector, which is 1,020 multiplied by 768, or 783,360 multiply-adds — a figure a single core gets through in well under a millisecond. The answer is exact by construction: recall 1.0, ten results every time, no tuning. The index spent 71 ms to return two results out of ten while a loop over an array would have returned all ten in a fraction of that time.

That comparison is where the pre-versus-post question stops being a binary. The cliff is not a defect to be tuned away but a region of the selectivity axis where approximation has stopped being worth its price, and the plan that wins there is the one nobody proposes because it looks unsophisticated. Recognising the region turns the design problem into an estimation problem: something has to know, before the query runs, roughly how many documents the predicate matches.