1 Introduction↩︎

Deep neural networks (DNNs) are increasingly deployed in domains where reliability is critical, including autonomous vehicles [1], medical diagnosis [2], and financial systems [3]. Ensuring reliability requires systematic testing to identify test inputs on which the model makes incorrect predictions—commonly referred to as faults. In many settings, however, verifying predictions requires ground-truth labels obtained through costly human annotation by domain experts [4].

This creates a fundamental and practical challenge: when should we stop labeling test inputs? Stopping too early risks missing faults that could lead to system failures; stopping too late wastes labeling resources on inputs that are unlikely to reveal new faults.

Existing test selection methods primarily focus on the selection problem—determining which inputs to label first—while the complementary stopping problem has received comparatively little attention. We identify three key limitations:

1. Lack of principled stopping criterion. Methods like DeepGini [5], TestRank [6], ATS [7], and DeepSample [8] typically evaluate performance under predetermined labeling budgets without providing guidance on when testing should terminate.

2. Arbitrary budget selection. In the absence of stopping criteria, practitioners must choose labeling budgets heuristically. However, appropriate budgets depend on factors such as model quality and dataset characteristics, which are often unknown beforehand.

3. Unaddressed cost–benefit trade-off. Labeling each input incurs cost, while discovering a fault provides value. Existing approaches focus on optimizing the order of test selection, such as prioritizing inputs that are more likely to reveal model errors, but do not explicitly consider this cost–benefit trade-off [5].

Although stopping criteria exist in related domains, such as the SAFE procedure [9] for document screening and convergence-based stopping [10] for active learning, these methods have not been adapted to DNN test selection, where the goal is efficient fault discovery.

A key empirical observation motivates our approach: test selection often exhibits diminishing returns. Inputs with higher uncertainty, which are typically selected first, tend to reveal faults at higher rates. As testing progresses, the remaining inputs yield progressively fewer faults per labeled instance.

This behavior suggests that the value of additional labeling decreases over time, creating a natural point at which further testing becomes inefficient. Based on this observation, we propose AdaStop, a cost-aware framework that terminates testing when the marginal fault discovery rate \(p(t)\) falls below a cost-adjusted threshold \(\tau = c/v\), where \(c\) denotes the labeling cost and \(v\) represents the value of discovering a fault.

The AdaStop framework consists of three components: (1) an uncertainty-based selection strategy (DeepGini) to prioritize inputs likely to reveal faults, (2) a sliding-window estimator of the marginal fault discovery rate, and (3) a cost-aware stopping rule that terminates labeling once the estimated rate falls below \(\tau\).

Contributions. (1) We frame DNN test selection as a sequential cost-benefit optimization, deriving the optimal stopping condition \(\tau = c/v\). (2) We propose a cost-aware threshold-based stopping rule and compare it against practical alternatives, including patience, consecutive non-faults, confidence-based, and cumulative-rate stopping. (3) We conduct a comprehensive evaluation across 3 datasets, 4 architectures, 3 quality levels, and 8 strategies, achieving 65–84% recall with 70–91% budget savings. (4) We provide an open-source implementation for community adoption.

2 Problem Formulation↩︎

2.1 Setting and Objective↩︎

Consider a DNN classifier \(M: \mathcal{X} \rightarrow \mathcal{Y}\) and an unlabeled test pool \(\mathcal{U} = \{x_1, \ldots, x_n\}\). A fault is an input where \(M(x) \neq y^*\) (the ground-truth label). Labeling costs \(c > 0\) per query; each fault discovered has value \(v > 0\).

Test selection proceeds sequentially: at step \(t\), select input \(x_t\) from the remaining pool via strategy \(s\), query the oracle for label \(y_t\), record outcome \(r_t = \mathbf{1}[M(x_t) \neq y_t]\), and decide whether to continue. The net value at stopping time \(T\) is: \[V(T) = v \cdot F(T) - c \cdot T\] where \(F(T) = \sum_{t=1}^{T} r_t\) is the number of faults found.

2.2 Optimal Stopping Threshold↩︎

At step \(t\), the marginal cost of labeling one more input is \(c\), and the marginal benefit is \(v \cdot p(t)\), where \(p(t) = \mathbb{E}[r_t]\) is the probability of discovering a fault. The marginal net value of the next label is: \[\Delta V(t) = v \cdot p(t) - c\]

The optimal decision rule follows directly: continue if \(v \cdot p(t) > c\) (positive marginal value); stop if \(v \cdot p(t) \leq c\). Rearranging the stopping condition gives: \[\boxed{\tau = \frac{c}{v}}\]

Proposition 1 (Optimal Stopping). Under diminishing returns (fault rate \(p(t)\) is non-increasing), the optimal policy stops at the first \(T\) where \(p(T) \leq \tau = c/v\). Once \(p(t)\) drops below \(\tau\), it remains below for all subsequent steps, so stopping immediately is optimal. \(\square\)

The threshold \(\tau\) is the break-even fault rate. For example, if labeling costs \(c = \$1\) and each fault is worth \(v = \$20\), then \(\tau = 0.05\): we stop when fewer than 5% of labels are expected to reveal faults. At this point, the expected value of the next label exactly equals its cost. The threshold automatically adapts—safety-critical scenarios (low \(c/v\)) continue longer; expensive-labeling scenarios (high \(c/v\)) stop earlier.

2.3 Fault Rate Estimation↩︎

Since \(p(t)\) is not directly observable, we estimate it from recent history using a sliding window: \[\hat{p}(t) = \frac{1}{W} \sum_{i=t-W+1}^{t} r_i\] where \(W\) is the window size. This estimator addresses three challenges: (1) non-stationarity—the fault rate decreases as testing progresses, so we use only recent samples rather than the full history; (2) noise—individual outcomes are binary, so averaging over \(W\) samples provides smoothing; (3) responsiveness—the window adapts to rate changes faster than a cumulative average. The choice of \(W\) involves a bias-variance trade-off: small \(W\) is responsive but noisy (risking premature stopping); large \(W\) is stable but slow to detect rate drops. We analyze this empirically in Section 6.

2.4 The Diminishing Returns Property↩︎

The optimal stopping condition relies on a key empirical observation: test selection exhibits diminishing returns. When using uncertainty-based selection (e.g., DeepGini), high-uncertainty inputs are selected first. Since high uncertainty correlates with higher fault probability, the fault rate \(p(t)\) decreases as \(t\) increases. This ensures a natural stopping point where \(p(t)\) crosses below \(\tau\). Without this property, the stopping problem would be ill-defined—the rate could fluctuate unpredictably. We validate this assumption formally with Mann-Kendall monotonicity tests in Section 6.

3 Related Work↩︎

3.1 Test Selection for DNNs↩︎

Uncertainty-based methods prioritize inputs where the model is least confident. DeepGini [5] uses Gini impurity of softmax outputs; FAST [11] addresses over-confidence through guided feature selection; CertPri [12] uses movement cost with formal robustness guarantees. Coverage and diversity-based methods aim for diverse test inputs: NLC [13] captures neuron output distributions; DeepGD [14] combines Gini score with geometric diversity via NSGA-II. Learning-based methods include TestRank [6] (GNN-based ranking) and ATS [7] (RL-based adaptive selection). Sampling-based methods include DeepSample [8] and DeepReduce [15]. All these methods use fixed budgets without principled stopping criteria.

3.2 Stopping Criteria in Other Domains↩︎

Active learning uses convergence-based criteria [10], [16], [17]—stopping when the model stops improving. These are fundamentally different from our setting: we are not training a model, but discovering faults in a fixed model. Document screening uses discovery-based criteria: SAFE [9] monitors discovery rates; Chao’s estimator [18] predicts total relevant documents. Mittal et al. [19] formulate model evaluation as an MDP but minimize estimation error, not fault discovery efficiency. We adapt the discovery-based stopping concept, adding a cost-benefit formulation specific to DNN testing.

3.3 Research Gap↩︎

Existing methods typically assume a fixed labeling budget and do not provide principled guidance on when additional testing is no longer worthwhile. Table 1 summarizes the comparison.

4 Proposed Approach↩︎

4.1 Framework Overview↩︎

Figure 1 illustrates the AdaStop framework. The system iteratively selects inputs via uncertainty-based ranking, obtains labels from an oracle, estimates the current fault rate, and stops when the rate falls below the cost-justified threshold.

4.2 Selection Strategy↩︎

AdaStop uses DeepGini [5] as its default selection strategy, prioritizing inputs by Gini impurity of softmax outputs: \[\text{Gini}(x) = 1 - \sum_{i=1}^{C} p_i(x)^2\] where \(p_i(x)\) is the predicted probability for class \(i\) and \(C\) is the number of classes. At each step, we select the input with the highest Gini score from the remaining pool, as uncertain predictions are more likely to be incorrect. We choose DeepGini for its simplicity (requires only softmax outputs), effectiveness (4–5\(\times\) over random), and wide adoption. AdaStop’s stopping framework is strategy-agnostic and is compatible with any strategy that produces a ranked ordering (Section 6.6).

4.3 Stopping Criteria↩︎

We discuss four practical stopping criteria for different scenarios:

Threshold-based (default). Stop when \(\hat{p}(t) < \tau\), with a minimum sample constraint \(N_{\min}\) to ensure reliable estimates. Directly implements the cost-benefit optimality condition. The threshold \(\tau = c/v\) should reflect the testing scenario’s cost-benefit ratio.

Patience-based. When \(\hat{p}(t)\) first drops below \(\tau\), continue for an additional patience window of \(k\) labels and stop unless the estimated rate rises above \(\tau\) again. This criterion adds a small safety margin against transient fluctuations at the stopping boundary.

Consecutive non-faults. Stop after observing \(k\) consecutive labels with no faults. This criterion is simple to implement and does not require setting an explicit cost-benefit threshold, but it is less directly tied to the optimality condition.

Confidence-based. For risk-averse scenarios, stop when the upper bound of a Wilson confidence interval [20] falls below \(\tau\): \(\text{CI}_{\text{upper}}(\hat{p}) < \tau\). This reduces premature stopping at the cost of more budget.

4.4 Complete Algorithm↩︎

Algorithm 2 presents the complete AdaStop procedure.

5 Experimental Setup↩︎

5.1 Research Questions↩︎

• RQ1: Can AdaStop realize high recall with a small budget fraction?

• RQ2: What is the impact of \(\tau\) on recall-budget balance?

• RQ3: What are the differences between various stopping criteria?

• RQ4: How sensitive is AdaStop to window size \(W\)?

• RQ5: Does AdaStop have good generalization properties with respect to datasets and architectures?

• RQ6: Is AdaStop strategy-agnostic?

• RQ7: How sensitive is AdaStop to model quality?

5.2 Datasets, Model Architectures, and Configuration↩︎

We evaluate across three datasets: CIFAR-10 [21] (10K test images), SVHN [22] (26K test images), and FashionMNIST [23] (10K test images); four architectures: ResNet-20 [24], VGG-16 [25], DenseNet-121 [26], and ShuffleNetV2 [27]; and three model quality levels for ResNet-20 on CIFAR-10: low (\(\sim\)​70%, 2,961 faults), mid (\(\sim\)​79%, 2,117 faults), and high (\(\sim\)​88%, 1,196 faults). Table 2 summarizes the configurations.

Default parameters: \(\tau{=}0.05\), \(W{=}20\), \(N_{\min}{=}50\). We compare against DeepGini at fixed budgets (\(k \in \{1,2,5,10,20,50,100\}\%\)), an oracle (perfect fault-first ordering), and five alternative stopping criteria: patience-5, consecutive non-faults (\(k{=}50,100\)), confidence-90%, and cumulative rate. For RQ6, we test eight selection strategies: DeepGini, entropy, margin, boundary distance, random, TestRank [6], ATS [7], and DeepGD [14].

Metrics: (1) Budget used (%): fraction of the test pool labeled before stopping. (2) Fault recall (%): fraction of total faults discovered. (3) Efficiency: ratio of faults found to labels used. (4) Net value: \(v \times \text{faults} - c \times \text{budget}\) with \(v{=}20\), \(c{=}1\).

5.3 Experimental Procedure↩︎

For each configuration, we compute model predictions and Gini scores, sort inputs by score, iterate through the ranked list while updating the sliding-window estimate, and apply the stopping rule once \(N_{\min}\) samples have been collected. For baseline comparisons, we run DeepGini at each fixed budget and record the same metrics.

6 Experimental Results↩︎

6.1 RQ1: Effectiveness↩︎

Table 3 compares AdaStop against exhaustive testing on CIFAR-10/ResNet-20.

Figure 3 shows the budget-recall trade-off. AdaStop automatically finds an effective operating point on the budget-recall curve without manual budget tuning.

Figure 4 compares net value across methods. The oracle achieves peak net value at exactly 11.96% budget (the error rate), where all faults are found with zero waste. DeepGini peaks at 50% and then decreases as costs outpace discovery. AdaStop achieves 90% of DeepGini’s peak value while using 27 percentage points less budget. Notably, exhaustive testing yields lower net value (13,920) than AdaStop (16,552), demonstrating that more testing is not always better.

RQ1: AdaStop achieves 79.0% fault recall using only 23.5% of the budget, with a 3.35\(\times\) efficiency improvement and 18.9% higher net value than exhaustive testing.

6.2 RQ2: Threshold Selection↩︎

Table 4 shows threshold sensitivity.

RQ2: Thresholds \(\tau{=}0.01\)–\(0.05\) converge to the same stopping point (23.5% budget, 79.0% recall), while \(\tau{=}0.10\)–\(0.20\) converge to an earlier point (13.2% budget, 54.7% recall). This stepped behavior indicates the fault rate exhibits sharp drops rather than smooth decline, creating natural stopping plateaus where multiple threshold values trigger at similar points.

6.3 RQ3: Stopping Criteria Comparison↩︎

Table 5 compares stopping criteria, all using DeepGini for selection.

The criteria form a clear aggressive-to-conservative spectrum. Threshold is most efficient; patience-5 adds a small safety margin; consecutive-50 achieves the best net value; and consecutive-100 and confidence-90 are conservative, achieving \(\geq\)​98.8% recall at higher cost. The cumulative rate criterion never triggers because the cumulative average is too slow to reflect marginal rate decline.

RQ3: For maximum efficiency, use threshold-based stopping. For best net value, consecutive-50 is optimal. For near-complete recall, confidence-90 provides 99.0% recall with 40% savings.

6.4 RQ4: Sensitivity to Window Size↩︎

Small windows (\(W{=}10\)) cause premature stopping; \(W{=}20\) and \(W{=}50\) converge to the same point, showing robustness for moderate sizes. The minimum-samples parameter \(N_{\min}\) is also robust: values of 20, 50, and 100 all produce identical results because the natural stopping point (2,348 samples) far exceeds \(N_{\min}\).

6.5 RQ5: Generalization↩︎

6.5.1 Cross-Dataset↩︎

AdaStop consistently achieves substantial budget savings (77–91%) across all datasets while maintaining 65–79% recall.

6.5.2 Cross-Architecture↩︎

Across architectures, the 18–30% budget range and the 67–84% recall range confirm that the stopping criterion adapts to varying error rates without parameter changes.

RQ5: AdaStop generalizes well: 65–84% recall with 70–91% savings across 3 datasets and 4 architectures.

6.6 RQ6: Strategy-Agnostic Property↩︎

Six of the eight strategies produce remarkably consistent stopping behavior: 23–24% budget, 79–81% recall, and 0.39–0.40 efficiency. This consistency occurs because all six strategies exploit model uncertainty to order inputs, producing similar diminishing-returns curves that cross \(\tau\) at nearly the same point.

RQ6: AdaStop is strategy-agnostic—all uncertainty-based strategies produce consistent stopping points. DeepGD stops earlier (12%) due to a steeper initial rate decline from its diversity component; random stops almost immediately because its unprioritized fault rate fluctuates enough to cross \(\tau\) soon after the initial window.

6.7 RQ7: Effect of Model Quality↩︎

As model quality improves (fewer faults), AdaStop uses less budget and achieves higher savings. For the low-quality model (30% error rate), the fault rate remains above \(\tau\) for longer, while for the high-quality model (12% error rate), it drops below \(\tau\) at 23.5%. The stopping point therefore varies naturally with fault density.

RQ7: AdaStop adapts to model quality: more budget for worse models (64.7%) and less for better ones (23.5%), with consistent efficiency (\(\sim\)​0.40–0.44).

6.8 Diminishing Returns Validation↩︎

The diminishing returns property is validated via APFD scores and Mann-Kendall monotonicity tests (Table 11).

All guided strategies show strong decreasing trends (MK \(\tau\) from \(-0.51\) to \(-0.74\), all \(p < 10^{-4}\)), confirming the diminishing returns assumption. Random selection shows near-zero trend (\(|\tau| < 0.04\)), confirming no meaningful trend as expected—without prioritization, the fault rate remains roughly constant at the base error rate.

6.9 Summary of Key Findings↩︎

1. Cost-aware stopping improves labeling efficiency: AdaStop with \(\tau{=}0.05\) achieves 79.0% recall using 23.5% of the budget—a 3.35\(\times\) efficiency gain with 18.9% higher net value than exhaustive testing.

2. Threshold exhibits stepped behavior: \(\tau{=}0.01\)–\(0.05\) converge to 23.5% budget; \(\tau{=}0.10\)–\(0.20\) converge to 13.2%, reflecting sharp fault rate drops.

3. Multiple criteria suit different needs: threshold for efficiency, consecutive-50 for best net value, confidence-90 for near-complete recall.

4. Window size matters: \(W \geq 20\) is required for stable estimates; \(W{=}10\) causes premature stopping (30% recall vs.%).

5. Generalizes broadly: consistent 65–84% recall with 70–91% savings across 3 datasets, 4 architectures, and 8 strategies.

6. Adapts to model quality: uses 23–65% budget depending on error rate, without parameter changes.

6.10 Limitations↩︎

Our evaluation focuses on image classification across three vision datasets; generalization to NLP, tabular, or multi-modal domains remains to be validated. AdaStop assumes labels are obtained one at a time; batch labeling scenarios (where multiple inputs are sent for annotation simultaneously) would require extending the framework. The threshold \(\tau = c/v\) requires practitioners to estimate the labeling cost and fault value; in practice these may be uncertain, though the relative and consecutive stopping criteria partially address this by not requiring explicit cost-benefit ratios. Finally, while the diminishing returns assumption is validated empirically via Mann-Kendall tests across three datasets, it may not hold for models with multi-modal failure clusters or adversarial inputs where faults appear in unexpected regions of the uncertainty space.

7 Conclusion↩︎

We presented AdaStop, a cost-aware framework for determining when to stop labeling in DNN test selection. By formalizing the stopping problem as a cost-benefit optimization, we derived the optimal stopping threshold \(\tau = c/v\) and implemented it through a sliding window fault rate estimator. Our comprehensive evaluation across 3 datasets (CIFAR-10, SVHN, FashionMNIST), 4 architectures (ResNet-20, VGG-16, DenseNet-121, ShuffleNetV2), 3 model quality levels, and 8 selection strategies demonstrates that AdaStop consistently achieves 65–84% fault recall with 70–91% budget savings. The framework is strategy-agnostic, producing consistent stopping behavior regardless of the underlying selection method. Among the stopping criteria evaluated, consecutive non-faults (\(k{=}50\)) achieves the best net value, while threshold-based stopping offers the highest efficiency. The diminishing returns assumption underlying our approach is formally validated via Mann-Kendall tests across all configurations. Future work will extend AdaStop to non-vision domains (NLP, tabular data), batch labeling scenarios.

References↩︎

---

1. \(^{1}\)Independent Researcher {shenbonan2, william.wj.huang, iamxinliu, gjz140103, ntgd1102}gmail.com?↩︎