Recall-Aware Selection for Noisy Candidate Generation

Search engines, question-answering systems, and recommenders usually work in two stages. A cheap first-stage model scans millions of items and keeps a short list of a few hundred. An expensive second-stage model, the reranker, then orders that list. Anything the first stage drops is lost for good. The first stage's scores are noisy estimates of what the reranker would say, and the noise is uneven: some query–document pairs are scored reliably, others are not. Economics and fairness research on selection under uneven noise has identified two opposite mistakes. Ranking by raw noisy scores over-selects high-noise items, because they produce lucky outliers. Ranking by noise-corrected averages under-selects them, because their scores are pulled toward the mean.

Our claim is that for a short list both mistakes come from optimizing the wrong objective, and the correct rule follows directly from the right one. The first stage's job is to maximize the expected number of the reranker's eventual top-$k$ items that make it into a pool of size $K$. That objective has an exact solution: keep the $K$ items with the highest probability of truly belonging to the top $k$. For Gaussian noise, the boundary of this pool is a noise penalty whose coefficient is not a constant. It is computed per query from the budget ratio $K/k$, and it changes sign, penalizing noise when the pool is tight and rewarding it when the pool is generous. We propose to derive this rule, estimate per-candidate noise in real retrieval pipelines, and test whether it moves the recall-versus-cost curve of standard two-stage systems at a fixed reranking budget.

Core Claim

Let $x_i$ be the score the reranker would give candidate $i$ for a query, and let the first stage yield a calibrated estimate $x_i \sim \mathcal{N}(\mu_i, \sigma_i^2)$. Here $\mu_i$ is the predicted reranker score and $\sigma_i$ its per-candidate uncertainty. Let $T_k$ be the set of items the reranker would place in its top $k$ over the whole corpus. By linearity of expectation, the expected recall of a pool $C$ is

$$\mathbb{E}\big[\,|C \cap T_k|\,\big] = \sum_{i \in C} \pi_i, \qquad \pi_i = \Pr(i \in T_k).$$

This holds whether or not the errors are correlated. The recall-optimal pool of size $K$ is therefore simply the top $K$ items by $\pi_i$. We approximate $\pi_i \approx \Phi\big((\mu_i - t)/\sigma_i\big)$, where $\Phi$ is the standard normal distribution function. The threshold $t$ is the per-query value solving $\sum_i \Phi((\mu_i - t)/\sigma_i) = k$, a one-dimensional root-find over a shortlist.

The rule keeps items with $(\mu_i - t)/\sigma_i \ge z^*$, where $z^*$ is the value at the $K$-th item. Rearranged, this is the linear rule $\mu_i - z^* \sigma_i \ge t$. So the recall-optimal pool is a linear noise penalty whose coefficient $z^*$ depends on the query and the budget.

This reconciles the two strands of prior work. Reward Selection with Noisy Observations proves that a linear penalty $y_i - c\sigma_i$ with any fixed $c$ can be $\Omega(\log n)$ worse than optimal for picking a single item, and recommends discarding high-noise items altogether (their IgnoreLarge rule). Our rule does not contradict that result, because both the objective and the coefficient differ. When $K \approx k$, $z^*$ is positive and the rule is conservative, close in spirit to IgnoreLarge. When $K \gg k$, $z^*$ is negative and the rule deliberately admits high-noise items whose averages fall below the cutoff. Discarding those items is exactly what the recall bottleneck punishes.

On Fair Selection in the Presence of Implicit and Differential Variance shows two failure modes: the "star illusion," where raw-score ranking over-picks the noisy group, and the "shrinkage trap," where posterior-mean ranking ($c=0$) under-picks it. Both appear as fixed-$c$ special cases in our analysis. The prediction we will test is that the gain of the per-query rule over posterior-mean ranking grows with $K/k$ and with how uneven $\sigma_i$ is across candidates.

Relation to Prior Work

The motivating evidence comes from the recall-bottleneck literature. Typos cut dense-retriever MRR@10 on MS MARCO from 0.296 to 0.141 and cap BERT rerankers (Dealing with Typos for BERT-based Passage Retrieval and Ranking). GPT-4 reranking cannot repair a weak candidate pool (University of Tsukuba Team at the TREC 2023 Deep Learning Track). Together these show that uneven first-stage error, not reranker capacity, sets the ceiling.

Three bridge papers are the closest work, and each leaves a gap we address:

Two further papers are related in narrower ways. Beating the Winner's Curse via Inference-Aware Policy Optimization counters the winner's curse with stochastic policies in tabular treatment decisions, relying on known logging propensities that retrieval indexes lack. Beyond Hamming: Query-Aware Decoding of Binary Cosine Sketches is a method supplier. It shows that the noise of binary sketch similarity estimates peaks for near-orthogonal vectors and fixes the estimator, but it still selects by point estimate. Its analysis gives us a setting where $\sigma_i$ is known in closed form.

Research Program

The work has three layers, ordered by how much of the noise model is known.

Synthetic Gaussian settings. We use the box environments of the reward-selection paper, where $x_i$ and $\sigma_i$ are known exactly. The goal is to confirm the predicted sign flip of $z^*$ as $K/k$ grows. We will also map when fixed-$c$ rules, IgnoreLarge, and posterior-mean ranking lose recall relative to exceedance ranking.

Binary sketch retrieval. Here we use 1-bit sign projections of dense embeddings. The sketch's angle estimate is a binomial proportion, so $\sigma_i$ follows analytically from the estimated angle and the number of bits. This isolates the selection rule from any errors in estimating noise.

Dense bi-encoder retrieval. Here $\sigma_i$ must be learned. On held-out calibration queries we fit a heteroskedastic regression predicting the cross-encoder's score from four inputs:

  • the bi-encoder score;
  • document length;
  • query term rarity;
  • a cheap sensitivity signal, namely how much the bi-encoder score moves when the query is re-encoded under a few character-level or paraphrase perturbations. Document embeddings stay fixed, so this adds only a handful of query encodings.

We then check whether the implied $\pi_i$ are calibrated before using them for selection. The threshold $t$ is solved per query over a shortlist of the top few thousand items by $\mu_i + 3\sigma_i$, so the added latency is one root-find plus the query perturbations.

Baselines

Raw-score top-$K$. The naive reference point is the standard pipeline: take the top $K$ by raw first-stage score and rerank. It is the operating default in every cascade in the research file. It is run at the same $K$, the same index, and the same reranker.

Posterior-mean top-$K$. This ranks by $\mu_i$, the calibrated prediction of the reranker's score. It is the "Bayesian correction" a careful practitioner would apply, and it isolates the value of calibration alone from the value of using $\sigma_i$. It uses the same calibration data as our method.

Linear penalty with one tuned coefficient. This ranks by $\mu_i - c\sigma_i$ with a single $c$ tuned on a development split for each $K$. It is the most important ablation. Because our pool boundary is itself linear, this baseline differs from our method only in replacing the per-query, per-budget $z^*$ with one global constant. It gets the same tuning budget as our only free choice. If it matches our method within confidence intervals, the per-query derivation is unnecessary, and we will report that.

IgnoreLarge. The rule from Reward Selection with Noisy Observations drops candidates whose $\sigma_i$ exceeds a tuned threshold and then fills the pool by $\mu_i$. It is the theoretically recommended rule from the selection literature, and we predict it will lose recall at large $K/k$.

QA-COS in the sketch setting. The decoder from Beyond Hamming is the strongest existing method there. It reports Hit@100 on ArguAna improving from 0.000 to 0.454 over standard SimHash, and 45–50% smaller candidate sets at an 80% recall target. We apply exceedance ranking on top of both the Hamming and the QA-COS estimators. Beating it means matching its recall with a smaller pool, or reaching higher recall at the same pool size.

Certified Error Control on MS MARCO. CEC is the strongest adaptive-size method. It reports reducing the average candidate set from 1,000 to 27 while meeting a requested 90% coverage. We run CEC with raw scores and with $\pi_i$ as the pruning score under the same risk tolerance and calibration split. Beating it means certified coverage at a smaller average pool size.

For the dense setting, the research file contains no reported result on Lacuna for recall of the reranker's top-$k$ within the pool at matched $K$. All numbers there will come from our own reruns of the baselines.

Why not just…?

Why not just enlarge the pool? A larger $K$ trades latency for recall. CEC's 37x reranking speedup from shrinking pools shows how costly reranking each extra candidate is. Our claim is about the shape of the recall-versus-$K$ curve, so we report full curves. The method wins only if it reaches a target recall at a smaller $K$. That threatens to fail when noise is nearly uniform across candidates, so we measure the spread of $\sigma_i$ in each setting and report gains as a function of it.

Why not just tune a noise penalty once? This is the real threat, because our rule is a linear penalty. The difference is that its coefficient $z^*$ varies with the query and the budget, and can be positive or negative. The globally tuned $\mu_i - c\sigma_i$ baseline tests this directly. We also report the per-query distribution of $z^*$. If $z^*$ barely varies across queries in real retrieval, the tuned constant will match us, and the contribution reduces to explaining why the optimal constant changes sign with $K/k$.

Why not just correct scores with a Bayesian average? That is the $c=0$ case. The fair-selection work predicts it under-admits high-noise candidates, and our analysis says it does so increasingly as $K/k$ grows. The posterior-mean baseline measures exactly this gap.

Why not use reranker-guided graph search instead? Reranker-Guided Search avoids a static pool, raising BRIGHT NDCG@10 from 25.3 to 28.8 with a budget of 100 reranked documents. It does this with sequential reranker calls, and it still ranks its search frontier by point estimates. Our rule is a drop-in replacement for static-pool selection, so the two can be combined. As a secondary experiment on BRIGHT, we will order the frontier by $\pi_i$.

Proposed Experiments

Synthetic settings. In the Gaussian and monotone-hazard box environments, we sweep $K/k$ and the spread of $\sigma_i$. We report expected recall for every baseline, along with the sign and size of the optimal $z^*$.

Sketch setting. On the BEIR datasets used by Beyond Hamming (ArguAna, FiQA-2018, NFCorpus, SciFact), we compare exceedance ranking on SimHash and QA-COS estimates against point-estimate selection. Metrics are Hit@100 and the pool size needed for 80% recall.

Dense setting. On MS MARCO passage with a bi-encoder first stage and a MonoBERT-style cross-encoder, we evaluate on original queries and on the typo-perturbed queries of Zhuang and Zuccon, where noise should be most uneven. We add Quora out of domain to test calibration shift, the regime where Li et al. found heuristic pruning met accuracy constraints only about half the time.

Metrics. The primary metric is recall of the reranker's top-10, computed with the reranker run over the top 1,000 as reference, at matched $K \in \{20, 50, 100, 200\}$. Secondary metrics are final MRR@10 or NDCG@10 against human relevance labels, plus added latency.

Decisive checks. Four results will settle whether the idea works:

  • Sign flip. The empirically best fixed $c$ should move from penalizing noise to rewarding it as $K$ grows. This confirms the mechanism.
  • Per-query coefficient. The per-query $z^*$ should beat the tuned global $c$ at matched $K$. This justifies the method over its simplest rival.
  • Calibration. Reliability plots of $\pi_i$ against realized top-$k$ membership should be close to diagonal. Otherwise any gains cannot be attributed to the stated mechanism.
  • Correlated errors. Gains should persist when the first-stage errors are correlated, which we test by using a reranker that shares its backbone with the bi-encoder. The expected-recall identity survives correlation, but the root-find for $t$ assumes independence.

If gains vanish whenever $\sigma_i$ must be learned rather than known, the conclusion is that noise estimation, not selection, is the bottleneck. That is still a useful negative result for the field.