Promises and Pitfalls of Threshold-based Auto-labeling

Harit Vishwakarma, Heguang Lin, Frederic Sala, Ramya Korlakai Vinayak

TL;DR

Threshold-based Auto-labeling (TBAL) is a popular way to slash data annotation costs by letting models label high-confidence data points, but it has been a theoretical "black box." This paper provides the first rigorous analysis of TBAL, revealing a surprising "promise"—even mediocre models can accurately label large chunks of data—and a significant "pitfall"—guaranteeing that accuracy requires a potentially massive amount of human-labeled validation data.

What Problem Does This Paper Address?

Supervised machine learning is hungry for high-quality labeled data, but human annotation is a massive bottleneck. To scale up, many practitioners turn to auto-labeling, where a model predicts labels for unlabeled data. A common commercial approach is Threshold-based Auto-labeling (TBAL): you use a small set of human-labeled validation data to find a confidence threshold. If the model is more confident than this threshold on a new point, it labels it automatically; otherwise, the point is sent to a human.

Despite its widespread use in tools like Amazon SageMaker Ground Truth, we haven't had a solid theoretical understanding of TBAL. How much validation data do we actually need to trust these machine-generated labels? Can a "bad" model still be a "good" auto-labeler? This paper bridges the gap between practice and theory by deriving sample complexity bounds and exploring the trade-offs between human effort and dataset quality.

Methods

The authors analyze a standard iterative TBAL workflow, which is visualized in the high-level workflow below:

Figure 1: High-level workflow threshold-based auto-labeling (TBAL). Box (B) shows the key component estimating the auto-labeling region using validation data and auto-labeling points in it.

The process works in rounds:

  1. Train: A model is trained on a small "seed" of human-labeled data.
  2. Threshold Estimation: Using a separate validation set, the system finds a confidence threshold $t$ such that the estimated error on points above $t$ is below a target tolerance $\epsilon_a$.
  3. Auto-label: Points in the unlabeled pool exceeding this threshold are machine-labeled and added to the final dataset.
  4. Active Querying: Informative points below the threshold are sent to a human labeler to improve the model for the next round.

The researchers used Rademacher complexity and VC-dimension to derive the first theoretical bounds on the auto-labeling error and coverage. They specifically looked at how the size of the validation set ($N_v$) impacts the reliability of the estimated threshold.

Datasets

The authors validated their theory across a mix of synthetic and real-world benchmarks:

  • Synthetic: Circles (two concentric circles, non-linearly separable), XOR (four clusters in a grid), and Unit-Ball (uniformly sampled points in $d$-dimensions).
  • Real-world: MNIST (handwritten digits), CIFAR-10 (images), Tiny-ImageNet (200-class image classification), and IMDB Reviews (sentiment analysis).

For the real-world datasets, they often used pre-computed embeddings (like CLIP for images or BGE for text) to represent the data before applying TBAL.

Key Insights and Ideas

  • The "Seemingly Bad Model" Promise: One of the most striking findings is that a model with poor overall accuracy can still be an excellent auto-labeler. For example, a linear classifier trying to separate concentric circles (a non-linear task) will have a high overall error. However, TBAL can identify specific high-confidence regions where that linear model is almost always right. As shown in Figure 2, TBAL achieves near 100% coverage with <1% error on the Circles dataset, whereas standard Active Learning (AL) fails because the model class is misspecified.
Figure 2: Comparison of TBAL, active learning (AL) followed by selective classification (AL+SC) and passive learning (PL) followed b selective classification (PL+SC) on the Circles dataset (Sec. 2.3) using linear classifiers and confidence functions. (a) Samples auto-labeled, queried, and left unlabeled. (b) The auto-labeling error and coverage achieved by the algorithms. (50 trials.)
  • The Validation Pitfall: Reliability isn't free. To guarantee that the auto-labeled data meets a specific quality bar, you need a lot of validation data. The sample complexity scales with $1/\epsilon_a^2$. If you want very low error, the amount of human-labeled validation data required might become prohibitively expensive, potentially negating the cost savings of auto-labeling.
  • The Necessity of UCB: The authors show that simply using the empirical error on validation data is risky. To meet error guarantees, one must use an Upper Confidence Bound (UCB) approach, adding a "safety margin" based on the standard deviation of the error estimate. Without this, the system often underestimates its own error, leading to low-quality datasets.

Key Results

  • Theoretical Tightness: The authors proved that their derived bounds are optimal up to logarithmic factors. Experimental results on the Unit-Ball dataset (Figure 3) show that the observed worst-case error follows the same rate as their theoretical upper bound.
  • Coverage vs. Error: In experiments on IMDB and Tiny-ImageNet, TBAL consistently stayed within the user-defined error budget (e.g., 5% or 10%) while maximizing coverage. For instance, on IMDB with 1000 validation points, TBAL achieved ~92% coverage while keeping error around 4.6% (below the 5% threshold).
  • Comparison to Baselines: TBAL generally outperformed "Active Learning + Selective Classification" (AL+SC). While AL+SC is good at finding a good model, it often struggles to label as much data as TBAL when the model class doesn't perfectly fit the data.

Limitations and Future Work

  • Confidence Function Quality: TBAL relies heavily on having a "good" confidence function (e.g., softmax scores or energy scores). If the model's confidence is poorly calibrated (i.e., it's "confident but wrong"), TBAL will fail to find accurate labeling regions. The authors noted this was a major challenge on CIFAR-10.
  • Validation Efficiency: Because validation data is the primary cost driver, the authors suggest that future work should explore Active Testing—techniques to validate model performance more efficiently than simple random sampling.
  • Human Oracle Assumptions: The study assumes a "noiseless oracle" (humans never make mistakes). In real-world crowdsourcing, human error is a factor that would add another layer of complexity to the bounds.

Summary updated

Abstract

Creating large-scale high-quality labeled datasets is a major bottleneck in supervised machine learning workflows. Threshold-based auto-labeling (TBAL), where validation data obtained from humans is used to find a confidence threshold above which the data is machine-labeled, reduces reliance on manual annotation. TBAL is emerging as a widely-used solution in practice. Given the long shelf-life and diverse usage of the resulting datasets, understanding when the data obtained by such auto-labeling systems can be relied on is crucial. This is the first work to analyze TBAL systems and derive sample complexity bounds on the amount of human-labeled validation data required for guaranteeing the quality of machine-labeled data. Our results provide two crucial insights. First, reasonable chunks of unlabeled data can be automatically and accurately labeled by seemingly bad models. Second, a hidden downside of TBAL systems is potentially prohibitive validation data usage. Together, these insights describe the promise and pitfalls of using such systems. We validate our theoretical guarantees with extensive experiments on synthetic and real datasets.
BibTeX
@inproceedings{vishwakarma2023promises,
  author = {Harit Vishwakarma and Heguang Lin and Frederic Sala and Ramya Korlakai Vinayak},
  title = {{Promises and Pitfalls of Threshold-based Auto-labeling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=RUCFAKNDb2},
}
Figure