Efficient Conformal Prediction via Cascaded Inference with Expanded Admission

Adam Fisch, Tal Schuster, Tommi S. Jaakkola, Regina BarzilayICLR 2021 · OpenReview

Providing rigorous "safety" guarantees for a machine learning model's predictions without making those predictions uselessly vague or computationally expensive is a persistent challenge. By combining two clever strategies—Expanded Admission and Cascaded Inference—researchers from MIT demonstrate how to make Conformal Prediction (CP) practical for complex, real-world tasks like drug discovery and open-domain question answering.

The Challenge of Standard Conformal Prediction

In high-stakes fields, practitioners often need a statistical guarantee rather than just a "best guess." Conformal Prediction (CP) is a framework designed for this: instead of outputting a single label, it outputs a set of labels guaranteed to contain the correct answer with a user-defined probability (e.g., 95%).

However, standard CP has two major flaws in large-scale applications:

  1. Predictive Inefficiency: In tasks like Information Retrieval (IR), there might be many "correct" snippets of text that answer a query. Standard CP is too rigid, often producing massive, unusable sets because it tries to account for a single, specific ground-truth label.
  2. Computational Cost: To maintain its guarantees, CP usually requires scoring every possible label in the search space. If you are searching through millions of Wikipedia snippets or chemical compounds, running a heavy transformer model on every single candidate is prohibitively slow.

Proposed Framework: Expanded Admission and Cascades

To make CP more efficient, the authors introduce a framework that reduces the size of predicted sets by up to 4.6x and significantly lowers computational costs while maintaining rigorous statistical guarantees. They achieve this through two main technical innovations:

1. Expanded Admission

The authors relax the strict "correctness" criterion of standard CP. Instead of requiring the prediction set to contain one specific ground-truth label, they define an "admission function" that identifies a group of acceptable answers (e.g., different text snippets that all prove the same fact). By calibrating the model to find at least one of these admissible answers, the resulting prediction sets become much smaller and more precise.

2. Conformalized Cascades

To save computational time, the authors employ a sequence of models. A fast, "cheap" model (like a keyword search) filters out the obvious wrong answers early on. Only the remaining plausible candidates are passed to the next, more "expensive" model (like a BERT-based reader).

Retriever Cascade Example

Crucially, they use Multiple Hypothesis Testing (MHT) corrections (such as Bonferroni or Simes) to ensure that this multi-step pruning doesn't break the mathematical guarantees of the final output. The paper proves that you can prune a search space using a cascade of models and still provide a distribution-free marginal coverage guarantee.

Key Insights and Results

The authors evaluated their approach on three diverse, large-scale tasks: Open-domain QA (Natural Questions), Fact Verification (FEVER), and Drug Discovery (ChEMBL).

  • "Hugging the Diagonal" for Tighter Sets: Standard CP is often "too safe," achieving higher accuracy than requested at the cost of huge prediction sets (over-coverage). By using "minimal nonconformity scores"—calibrating against the easiest admissible answer—the authors' method "hugs the diagonal." This means it hits the target accuracy exactly without overshooting, allowing the prediction sets to remain much smaller.
Accuracy vs Target Coverage (IR)
  • Smaller Sets and Faster Inference: On Question Answering tasks, the "min-calibrated" approach produced prediction sets that were significantly smaller (up to 4.6x better predictive efficiency AUC) than standard CP. Furthermore, the cascaded approach drastically reduced the number of required p-value computations, amortizing costs effectively across the cascade.
  • Robustness over Heuristics: The proposed methods consistently outperformed heuristic baselines (like "top-k" or simple thresholding) because those heuristics fail to provide reliable coverage guarantees across different levels of query difficulty.

Limitations and Future Work

The success of "Expanded Admission" relies heavily on having a good rule or model to define what counts as an "admissible" answer; if this function is poorly defined, efficiency gains may diminish. Additionally, while MHT corrections ensure validity, they can sometimes be overly conservative. Finding tighter MHT corrections for specific types of model dependencies remains a promising area for future research. Finally, while the paper measures "amortized cost" in terms of theoretical computations, actual wall-clock speedups will depend on specific hardware and implementation optimizations.

Summary updated

Abstract

In this paper, we present a novel approach for conformal prediction (CP), in which we aim to identify a set of promising prediction candidates---in place of a single prediction. This set is guaranteed to contain a correct answer with high probability, and is well-suited for many open-ended classification tasks. In the standard CP paradigm, the predicted set can often be unusably large and also costly to obtain. This is particularly pervasive in settings where the correct answer is not unique, and the number of total possible answers is high. We first expand the CP correctness criterion to allow for additional, inferred "admissible" answers, which can substantially reduce the size of the predicted set while still providing valid performance guarantees. Second, we amortize costs by conformalizing prediction cascades, in which we aggressively prune implausible labels early on by using progressively stronger classifiers---again, while still providing valid performance guarantees. We demonstrate the empirical effectiveness of our approach for multiple applications in natural language processing and computational chemistry for drug discovery.
BibTeX
@inproceedings{fisch2021efficient,
  author = {Adam Fisch and Tal Schuster and Tommi S. Jaakkola and Regina Barzilay},
  title = {{Efficient Conformal Prediction via Cascaded Inference with Expanded Admission}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=tnSo6VRLmT},
}
Figure