Does Matryoshka Reranking Lose Relevant Docs? I Ran the Numbers

Looking for TL;DR? Check key takeaways

In my previous blog I reverse-engineered Exa's infrastructure costs. Their vector search pipeline looks roughly like this:

256d BQ IVF → top-1000 → 1024d BQ rerank → top-? → 2048d bf16 rerank → top-? → cross-encoder → top-10

But this iterative narrowing bothered me: does it silently lose relevant documents? A doc filtered out at the 256d stage can never be recovered by the 1024d or 2048d rerank. And if your evals only measure the precision of what you returned, you'd never know what you missed. So I ran the experiment.

Experiment Setup

Model: nomic-embed-text-v1.5 — 768d Matryoshka model, supports dimension truncation at any point.

Dataset: SciFact from BEIR — 5183 scientific paper abstracts, 300 test queries, ground-truth relevance labels. Picked this because queries are precise scientific claims ("X causes Y in Z") that require fine-grained semantic matching — exactly the kind of thing a coarse embedding might get wrong.

Pipeline under test (proportional to Exa's 256→1024→2048 dims at 768d scale):

64d → top-k1 → 256d → top-100 → 512d → top-25 → 768d → top-10

Oracle: direct cosine search at full 768d over all 5183 docs — what the model would return if there were no filters.

The sweep: instead of testing one k1, sweep k1 ∈ [20, 50, 100, 200, 500, 1000, 5183] to find where the recall cliff starts.

How aggressive is Exa's first-stage filter?

• Exa uses IVF Index with ~200k clusters of 100k docs each (~20B total)
  • At query time, they probe ~10 clusters → 1M candidates, then filter with 256d BQ to top-1000
  • That's 1000 / 1M probed = 0.1% of probed candidates, or 1000 / 20B = 0.000005% of total corpus
• Our most aggressive test: k1=20 from 5183 docs = 20 / 5183 = 0.39%
  • Ratio vs Exa: 0.39% / 0.000005% = 78,000x more generous — our "worst case" is Exa's easy case
• My experiment also uses 64d as the first-stage dim. Exa uses 256d BQ — 4x more bits, almost certainly better first-stage agreement (the ρ metric I introduce below)

So our results are a lower bound on Exa's recall performance — which makes the cliff even more striking.

The Recall Cliff

The cliff lives between 1–4% corpus retention — exactly where most aggressive production pipelines operate. Going from k1=200 (recall=0.906) to k1=50 (recall=0.694) is a 21-point drop for a 3x reduction in k1. At k1=20, 42% of queries lose more than half their oracle results.

Two other things worth noting:

• Even at k1=5183 recall tops out at 0.978, not 1.0 — the 256d/512d reranks add ~2% irreducible loss.
• Recall vs qrels degrades too, not just recall vs oracle: at k1=20, qrel recall drops from 0.797 to 0.668, a 16% real recall loss on labeled-relevant documents. These aren't near-duplicates; these are docs a user would actually want.

Where Exactly Does the Loss Happen?

Stage-by-stage breakdown at k1=100 over the full 5183-doc corpus:

Note how 100% of the recall loss happens at the first stage. Once a doc is dropped by the 64d filter, the subsequent 256d, 512d, and 768d reranking stages contribute zero additional loss — but they also can't recover anything.

Good news for the reranking design: the coarse→fine narrowing is faithful once the candidate pool is set — the problem is purely how many docs the first filter lets through, not the reranking structure itself.

One caveat this experiment can't capture: Exa uses IVF, not exhaustive search, so docs near a cluster boundary can be routed to the wrong centroid and missed entirely — a second source of first-stage loss stacked on top of the BQ recall gap.

Predicting Which Queries Will Fail

The best predictor of recall loss is Spearman ρ between 64d rankings and 768d rankings — how much does the coarse filter agree with what the full-dim model considers relevant?

Distribution across 300 test queries:

30% of queries have ρ < 0.35 — the coarse and full-dim rankings strongly disagree. Queries in this zone lose 60–70% of their oracle results even at our most generous-relative-to-Exa filter. And the min recall hits 0.10, meaning one query lost 9/10 oracle results.

Intuitively: low ρ means "the semantics this query needs are not well-captured by 64d." These tend to be queries that require fine-grained distinctions — a specific mechanism, a specific population, a specific treatment — where many docs look similar at coarse resolution but diverge at full resolution.

The "Never Caught" Problem

To be precise: offline evals with independently collected ground truth do catch this. recall@k = |retrieved ∩ relevant| / |relevant| — the denominator is the full relevant set, so a doc filtered at stage 1 shows up as a miss. I used SciFact's independent labels exactly this way and measured a real 3.5–16% qrel recall drop. The trouble is that production rarely looks like that: you can't run recall@10 on live traffic without annotated queries, and the signals you can measure — CTR, session length, thumbs-down — won't reliably surface a 10% recall drop on one narrow query type like "mechanism X in population Y".

Worse, offline labels are only as trustworthy as how they were collected. Labels annotated from your own pipeline's top results can never surface a doc that stage 1 already filtered out — they're blind to exactly the gap I'm measuring. (BEIR avoids this because it was labeled independently of any retrieval system.) The only reliable check is to periodically run full-corpus retrieval on a sample of queries and diff it against the pipeline — computing the oracle and comparing. At 20B docs that costs ~$200k per run by my embedding estimates, so it likely doesn't happen on every model update. Exa probably does some version of it via their offline evals — but whether their labels are pipeline-independent, and whether they cover the low-ρ 30% most at risk, is unclear.

Can a Rotation Before Truncation Save Recall?

At Exa's scale the first filter is far more aggressive than anything I tested, so first-stage recall is determined almost entirely by how much signal those 256d BQ vectors preserve. Can you make them preserve more? The obvious lever is to rotate the embedding space with PCA before truncating: instead of keeping nomic's first 64 (or 256) trained dimensions, fit PCA on the corpus and keep the top-k principal components. PCA packs maximum variance into the leading axes, so the truncated vector should preserve more of the full-768 ranking.

I re-ran the exact funnel above with three first-stage variants — MRL-prefix (the trained Matryoshka prefix, my baseline), PCA, and ITQ (a variance-balancing rotation — ITQ/OPQ) — in two regimes: plain float cosine, and binary-quantized (1-bit-per-dim), since binary quantization is what Exa runs at its 256d first stage.

Float first stage: PCA genuinely helps

At the blog's exact 64d float first stage, PCA shifts the entire cliff:

(recall vs oracle; my MRL-prefix column reproduces the original cliff within ~1 point, so the pipeline is faithful.)

The gain is largest exactly where the filter is most aggressive — +18 points at k1=20. In 64 real-valued numbers, PCA simply packs more of the full-768 variance than nomic's trained prefix does, so the coarse ranking agrees more with the oracle. At 256d float the edge shrinks to near-zero: the trained prefix already captures enough by then.

So for a float Matryoshka funnel, PCA-before-truncation is a real, free win. But Exa's first stage isn't float — it's 256d binary.

Binary first stage: PCA backfires, ITQ wins

Here's the catch that flips everything: a float dimension is worth its variance; a binary dimension is worth exactly one bit, whatever its variance. PCA packs variance into a few leading axes — ideal for float, where those axes dominate the cosine score as they should. Binarize it and every axis costs the same one bit: PCA's best axes are starved (one bit for the axis that mattered most) while its ~250 trailing axes turn into near-random sign flips. So once the first stage is binary-quantized (sign of each dim → 1 bit, ranked by Hamming distance — Exa's actual 256d BQ), the story inverts:

(recall vs oracle at 256d binary first stage)

Naive PCA barely helps, then actively hurts (−2 to −4 points at moderate k1): the ρ from earlier collapses from 0.62 (MRL) to 0.29 (PCA). PCA produces the most unequal variance split possible, and binary wants the opposite — it's the worst rotation you could feed a binary quantizer.

ITQ fixes exactly this. It adds an orthogonal rotation that flattens variance across the kept dimensions so every bit earns its keep — lifting recall +28 points at k1=20 and pushing ρ to 0.655, above even the trained MRL prefix. Same 256 bits, spent well. And it holds up on the independent labels too, not just oracle agreement: ITQ recovers +10 points of qrels recall (0.672→0.773 at k1=20).

So — would this help Exa?

• PCA specifically: no, and possibly worse. Exa's first stage is binary, where PCA concentrates variance into a handful of useful bits and wastes the rest — degrading first-stage recall.
• A learned rotation before binarization (ITQ/OPQ): very likely yes. It attacks the exact stage where 100% of the loss happens, recovered ~25–28 points at the most aggressive filter, and raised the ρ that predicts which queries fail — for the price of one matmul.

The caveat: ITQ must be fit on the deployment corpus and refit on large distribution shift, and our SciFact scale (5183 docs) is nowhere near Exa's 20B — so treat the magnitudes as directional, not as a promise of the gain at web scale. But the mechanism is robust and well-established: if Exa is feeding MRL-truncated (or worse, PCA-truncated) vectors straight into binary quantization without a variance-balancing rotation, adding one is probably the single highest-leverage fix to their first-stage recall.

Key Takeaways

• The recall cliff is real. At 1.93% corpus retention (k1=100), 74% of queries already lose at least one oracle result and 3% lose more than half.
• 100% of the loss is at the first stage. The iterative 256d→512d→768d reranking contributes zero additional recall loss once the candidate pool is set. The multi-stage reranking structure is not the problem — the first-stage filter aggressiveness is.
• ρ(coarse, full-dim) is the leading indicator. ~30% of queries have low rank correlation between 64d and 768d, making them most vulnerable. These are the queries that need fine-grained semantic distinctions the coarse filter can't see.
• Exa's operating point is beyond what I can test. Their 256d BQ model is better than our 64d, but their filter is 78,000x more aggressive. Net impact unknown — but the cliff I found at 1–4% corpus retention suggests it matters.
• Silent recall loss is easy to miss in practice. Offline evals with independent labels catch it, but production monitoring without labels doesn't. And if eval labels were collected by annotating pipeline results, they're biased — you'll never see the docs stage 1 already filtered out.
• A rotation before truncation helps — but PCA is the wrong one for binary. PCA helps a float funnel (+18 pts at the most aggressive filter) yet hurts under binary quantization; a variance-balancing rotation (ITQ/OPQ) recovered ~25–28 points at 256d BQ, Exa's actual setting. If you binary-quantize a truncated embedding, rotate it first.

Acknowledgements

Thanks to the discussion on my previous blog that prompted this experiment. Feel free to DM me on X or LinkedIn if you spot wrong assumptions or have better data on what Exa's actual first-stage recall looks like.

• https://huggingface.co/nomic-ai/nomic-embed-text-v1.5
• https://huggingface.co/datasets/BeIR/scifact
• https://huggingface.co/blog/matryoshka
• https://exa.ai/blog/building-web-scale-vector-db
• https://exa.ai/blog/evals-at-exa
• https://github.com/beir-cellar/beir