Adaptive Stratified Sampling for Precision-Recall Estimation

Ashish Sabharwal, Yexiang XueUAI 2018

Abstract

Evaluating the quality of large-scale generative models often requires estimating Precision-Recall (PR) curves, a process typically bottlenecked by expensive human annotations. We present ADASTRAT (Adaptive Stratified Sampling), a data-aware algorithm that leverages weak monotonicity and an adaptive geometric envelope to minimize queries. ADASTRAT achieves significant efficiency gains, requiring as few as 18 queries for a 3.5-million-item dataset—a 13x improvement over prior state-of-the-art methods—while maintaining high estimation accuracy.

Introduction

Generative AI models can produce millions of outputs—such as poems, paraphrases, or code snippets—in seconds. To deploy these models safely and effectively, we must quantify their performance using metrics like the Precision-Recall (PR) curve. This curve illustrates how the "correctness" of model outputs diminishes as the model's internal confidence threshold decreases.

However, determining "correctness" usually necessitates human judgment, creating a significant bottleneck. For a dataset of size $N$, exhaustive annotation is infeasible. Standard random sampling requires $\Theta(\sqrt{N \log N})$ annotations, which remains prohibitively expensive for modern "Big Data" scales. While previous "logarithmic" methods like LOGSTRAT improved upon this, they were data-oblivious, querying precision at fixed points regardless of the actual shape of the precision curve.

The ADASTRAT Algorithm

ADASTRAT (Adaptive Stratified Sampling) treats PR estimation as an active search problem. Unlike its predecessors, it is "data-aware," adjusting its sampling strategy based on observed data points. The algorithm is built on four core pillars:

  1. Weak Monotonicity: It assumes that while precision may fluctuate locally, it generally follows a downward trend as one moves down a ranked list of model outputs.
  2. The Geometric Envelope: ADASTRAT defines a mathematical "envelope" consisting of upper and lower bounds. Any valid PR curve must reside within this envelope based on previously queried points.
The geometric envelope used by ADASTRAT to bound the precision curve based on observed points.
  1. Adaptive Bisection: Rather than querying at fixed intervals, ADASTRAT identifies regions where the gap between the upper and lower bounds of the envelope is largest. It then queries the geometric midpoint of these regions. If the envelope is already thin (indicating a flat curve), the algorithm stops early.
  2. Adaptive Stratified Sampling: To maximize efficiency, the algorithm reuses human annotations across different query points. Since precision at a lower rank $r_2$ includes items from a higher rank $r_1$, ADASTRAT only samples the specific "new" items required to update its confidence intervals.

Experimental Evaluation

The researchers evaluated ADASTRAT using the Paraphrase Database (PPDB), specifically the PPDB-36K subset containing approximately 35,000 human-judged paraphrase pairs. To test scalability, they generated synthetic variants (PPDB-10x, 100x, and 1000x) by statistically mirroring the original distribution, allowing for simulations on datasets containing up to 35 million items with known ground truth.

Key Results and Efficiency

ADASTRAT demonstrates a significant reduction in human labor requirements compared to existing methods. On the 3.5-million-item PPDB-100x dataset, ADASTRAT required only 18 precision queries to generate an accurate curve. In contrast, the previous state-of-the-art method, LOGSTRAT, required 234 queries, while conventional random sampling would have necessitated nearly one million annotations.

Comparison of query complexity between ADASTRAT and previous methods across varying dataset sizes.

Theoretical analysis shows that ADASTRAT's query complexity scales with $\log \log N$ in many practical scenarios, rather than the $\log N$ scaling of previous methods. For a dataset of one billion items, this reduces the query count from approximately 30 to fewer than 5. Furthermore, the algorithm maintains high accuracy; the curves generated by ADASTRAT were found to be remarkably close to the true precision functions, supported by a proven "regret bound" that aligns its efficiency with an optimal oracle.

Discussion and Limitations

While highly effective, ADASTRAT relies on the assumption of "weak monotonicity." If a model's ranking is entirely uncorrelated with quality (e.g., its most confident outputs are its worst), the envelope bounds may be less tight, though the algorithm is designed for robustness against minor fluctuations. Additionally, users must tune the approximation factor ($\epsilon$) and confidence level ($\delta$), which represent a direct trade-off between annotation cost and precision.

Future work may extend this adaptive envelope approach to other ranking metrics, such as Average Precision (AP) or Discounted Cumulative Gain (DCG), potentially revolutionizing how we evaluate large-scale AI systems across diverse domains.

Summary updated

BibTeX
@inproceedings{sabharwal2018adaptive,
  author = {Ashish Sabharwal and Yexiang Xue},
  title = {{Adaptive Stratified Sampling for Precision-Recall Estimation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
}
Figure