Deferred Pruning: End-to-End Risk Control for Multi-Stage Distance Cascades

Many search problems need an expensive distance. Examples are Word Mover's Distance between documents, graph edit distance between molecules, and learned translation metrics. Systems make these tractable with a cascade of cheaper filters. A cheap score throws out most candidates, a better score throws out more, and only a handful reach the exact computation. This creates a familiar weakness of hierarchical systems: once an early stage drops the true answer, nothing downstream can recover it. Existing cascades take one of two stances. Some prune only with provable lower bounds, which makes them exact but gives modest speedups. Others prune with heuristics, which is fast but carries no guarantee.

We propose a cascade that never permanently discards a candidate. It defers them. Every candidate keeps the cheap scores already computed for it. Exact verification proceeds in a fixed priority order. At each step the system checks two things. First, it asks which deferred candidates are now provably ruled out, because their lower bound exceeds the current k-th best exact distance. Second, it asks whether the estimated risk carried by the candidates not yet ruled out is low enough to stop. A single stopping knob is calibrated with conformal risk control, which turns a held-out set of queries into a finite-sample guarantee on the expected loss. The guarantee bounds the probability that the returned top-k differs from the exact top-k, end to end, for any number of stages.

Because the stopping rule is evaluated per query, hard queries automatically get more exact verification. Easy queries stop early. In the language of the error-propagation literature, this is a recovery mechanism: an early mistaken ordering costs extra compute, not correctness.

Core Claim

In distance cascades, errors come from only one source: declining to verify a candidate that has not been certified out. Admissible lower bounds introduce no error. Making the rest of the pipeline safe therefore needs three things:

  • Spend the statistical error budget only on that one decision.
  • Make the decision revocable until the query finishes.
  • Calibrate it once, end to end, rather than stage by stage.

We claim this gives substantially fewer exact evaluations than exact bound-based cascades at a small certified miss rate. We also claim it gives fewer evaluations than per-stage calibrated pruning at the same miss rate.

Relation to Prior Work

Two strands supply the method. The first is exact bound-based filtering.

We reuse their bounds unchanged as certificates. We drop their rule that a candidate not certified out must be verified.

The second strand is risk calibration.

  • Conformal Risk Control controls any bounded loss that is monotone in a scalar parameter. Its rate is $O(1/n)$. It has been demonstrated on single-step outputs.

We construct a cascade policy whose loss is provably monotone in one scalar, so that result applies directly to a K-stage pipeline.

The closest prior work is Certified Error Control of Candidate Set Pruning for Two-Stage Relevance Ranking. It calibrates a first-stage score threshold so that ranking degradation stays within a user tolerance. It cuts MS MARCO candidates from 1,000 to 27 on average, a 37x reranking speedup. It is strictly two-stage, its authors name multi-stage cascades as future work, and its pruning is a one-shot, irrevocable cut. We differ on three points:

  • We handle any number of stages.
  • We combine provable certificates with calibrated stopping.
  • Our stopping depends on the query's own running state rather than on a fixed score threshold.

Several works motivate the proposal by documenting the failure mode. Within distance filtering, the heuristic coarse-to-fine MBR of Sampling-Based Approximations to Minimum Bayes Risk Decoding gains up to 22x speedup with no guarantee on what the top-T cut loses. The multiresolution tangent-distance cascade of Efficient Computation of Complex Distance Metrics Using Hierarchical Filtering hand-tunes its per-stage cutoffs on validation data. Outside distance filtering, the hierarchical-systems literature documents that coarse errors do not heal downstream:

Recovery-oriented designs such as beam retention in BeamAggR and stacked correction in Stacked Hierarchical Labeling inspire the deferral idea. Neither provides a guarantee.

Decomposition-Based Modular Conformal Prediction for Two-Stage Modeling constrains the design. It shows that monolithic split conformal coverage falls to 69% against an 80% target under upstream shift. That warns us that an end-to-end calibration is only as good as exchangeability. We answer this in two ways. Certificates, unlike calibration, remain valid under any shift. We also add an abstention fallback in the spirit of that paper.

Method

Fix a query $q$, candidates $x_1,\dots,x_N$, the exact distance $D$, and a target of k nearest neighbors. Each stage $s$ yields a cheap score for each candidate. Where available, it also yields an admissible lower bound $L_s(q,x) \le D(q,x)$.

Verification order. A priority score orders candidates once, before any exact computation. The priority score is a small model trained on a separate split; its inputs are all the cheap scores. Candidates are exactly verified in that order. Let $D_k^*$ be the current k-th best exact distance. Any unverified candidate with $\max_s L_s(q,x) > D_k^*$ is certified out, and we compute later-stage bounds lazily only for survivors.

Residual risk. For the uncertified, unverified remainder $U_t$ after $t$ verifications, we form a residual-risk score $$r_t = \sum_{x \in U_t} \hat p(x),$$ where $\hat p(x)$ is a learned estimate of the probability that $D(q,x) < D_k^*$, given $x$'s bounds and the current $D_k^*$.

Stopping rule and guarantee. Verification stops at the first $t$ with $r_t \le \lambda$. Lowering $\lambda$ can only lengthen the verified prefix. Exact top-k over a longer prefix is never worse. The miss loss is therefore monotone, so conformal risk control yields a $\hat\lambda$ with expected miss rate at most $\alpha$. The estimator $\hat p$ need not itself be calibrated; it only has to rank remaining risk well.

Fallback. If $|U_t|$ at stopping exceeds a calibrated high quantile, we treat the query as out of distribution and verify everything.

Diagnostics. Each miss is logged with the stage whose bounds the missed candidate passed. This gives the stage-level error attribution that modular conformal prediction provides for regression.

Research Program

We will build the policy on three testbeds.

  1. WMD k-nearest-neighbor classification. Stages are word-centroid distance, then the relaxed WMD bound, then exact WMD, all from Kusner et al. These run on BBCSPORT, TWITTER, RECIPE, OHSUMED, CLASSIC, REUTERS, AMAZON and 20NEWS.
  2. Graph similarity search with exact GED. Stages are BRANCH, then the BranchUB/BranchRUB upper bounds, then exact GED. These run on QM9 and the TUDataset graphs (MUTAG, PTC_FM, Fingerprint, Letter, Cuneiform).
  3. Three-stage passage ranking on MS MARCO Passage v1. Stages are BM25, then a dense bi-encoder, then a MonoBERT-style cross-encoder. This testbed has no admissible bounds, so it isolates the calibrated-deferral component. It also allows a direct comparison with Li et al.

We will vary $\alpha$ over 0.01, 0.05 and 0.1. Each configuration is repeated over 100 random calibration/test splits of queries.

Baselines

Exhaustive exact computation. This is the do-nothing reference. It defines ground-truth top-k and the zero-error compute cost. It is run where feasible: the WMD datasets, TUDataset, and a QM9 query subsample.

Exact bound-based cascade. This is Kusner's prefetch-and-prune for WMD and Bause's metric-index pipeline for GED, run with their published bounds. It is the strongest competitor because it already achieves zero error. The reported figure is a 2x to 5x speedup over exhaustive WMD (Kusner et al.). For GED, Bause et al. report "several orders of magnitude" lower filtering time. We found no reported per-dataset number on Lacuna for QM9 exact-GED verification counts, so we will measure their pipeline ourselves.

To beat these, we must cut exact evaluations and wall-clock time by at least a further factor of two at $\alpha = 0.01$. We must also keep k-NN classification error within run-to-run noise of exact.

Certified Error Control. On MS MARCO, the strongest calibrated competitor is Certified Error Control. It reports 27 retained candidates on average and a 37x reranking speedup at its risk target. We will run it in two ways:

  • Native mode: calibration of the BM25-to-reranker cut only.
  • Multi-stage extension: per-stage calibration with the error budget split as $\alpha/2$ per stage by a union bound.

Both use our exact calibration queries and the same models, with the same compute and tuning budget given to the priority and risk estimators as to its threshold search. We must match its risk while retaining fewer candidates on average.

Fixed top-K per stage. This is the common practice, tuned on validation. We report how often it violates the target.

Ablations. Two ablations isolate the key ingredients:

  • No certificates. Deferral without lower-bound certificates, which tests whether provable bounds add value beyond calibration.
  • No adaptivity. A fixed per-query verification count calibrated with conformal risk control, which tests whether stopping on the query's running state is what saves compute.

Why not just…?

Why not just split the error budget across stages and apply Certified Error Control at each one? This is valid by a union bound and easy to implement. It is the real threat on MS MARCO. Its weakness is twofold. It charges budget at every stage, including stages where admissible bounds make pruning free. Its cuts are also irrevocable: a candidate dropped at stage one cannot be reconsidered after stage two reveals the query is hard. If the per-stage misses are nearly disjoint and cheap scores are well separated, Bonferroni may be nearly as efficient as our method. The head-to-head at matched $\alpha$ settles this. If our method retains no fewer candidates, deferral adds nothing on ranking pipelines, and the contribution narrows to the certificate-bearing testbeds.

Why not just use the exact bound-based cascade and accept its speed? Its error is zero, which is the cleanest property available. Its speed, however, is limited by how loose the bounds are. Kusner et al. note that bounds degrade on specialized vocabularies such as OHSUMED, exactly where the expensive tail grows. Our method contains this cascade as the $\lambda \to 0$ limit. The question is purely how many exact calls a 1% miss budget buys. If the answer is under 2x, we will say the guarantee is not worth the machinery.

Why not just calibrate the whole cascade as a black box with one conformal threshold? Monolithic calibration is what our method uses for its single knob. The difference is what the knob controls. A black-box threshold on a fixed score ignores each query's running $D_k^*$ and its certificates. The no-adaptivity ablation measures exactly this. The shift result in modular conformal prediction also suggests black-box calibration is brittle under shift. We test that brittleness directly below.

Decisive Checks

The first check is validity. Across splits, the mean end-to-end miss rate must sit at or below $\alpha$ on every testbed. The comparison point is how closely conformal risk control hit its targets on ImageNet: 0.0499 at $\alpha = 0.05$.

The second check is efficiency. We plot exact evaluations against realized miss rate for our method, the exact cascade, Bonferroni-split certified error control, and the two ablations.

The third check is shift. We calibrate WMD on the non-medical corpora and test on OHSUMED, then measure three quantities:

  • how far the miss rate drifts;
  • how often the fallback fires;
  • what fraction of pruning decisions were certificate-backed, and therefore shift-proof.

The idea succeeds if the method wins efficiency on WMD and GED at $\alpha = 0.01$ without violating risk. It fails if a union-bounded per-stage calibration matches it everywhere.