Enhancing Cost Efficiency in Active Learning with Candidate Set Query
Authors: Yeho Gwon
Sehyun Hwang
Hoyoung Kim
Jungseul Ok
Suha Kwak
Venue: Accepted by TMLR ()

Abstract: This paper introduces a cost-efficient active learning (AL) framework for classification, featuring a novel query design called candidate set query. Unlike traditional AL queries requiring the oracle to examine all possible classes, our method narrows down the set of candidate classes likely to include the ground-truth class, significantly reducing the search space and labeling cost. Moreover, we leverage conformal prediction to dynamically generate small yet reliable candidate sets, adapting to model enhancement over successive AL rounds. To this end, we introduce an acquisition function designed to prioritize data points that offer high information gain at lower cost. Empirical evaluations on CIFAR-10, CIFAR-100, and ImageNet64x64 demonstrate the effectiveness and scalability of our framework. Notably, it reduces labeling cost by 48% on ImageNet64x64. The project page can be found at https://yehogwon.github.io/csq-al.

Published in Transactions on Machine Learning Research (08/2025)
Enhancing Cost Efficiency in Active Learning with Candidate Set Query
Yeho Gwon"
yeho.guon&@pstechh.cc
Deportment of Computer Science and Engineering
POSTECH
Schyun Hwang"
cchyan09@postechh.
Department Computer Science and Engineering POSTECH
Hoyoung Kim
cskhy16@postech.coo oc.kr
Graduate School of Artificial Intelligence
POSTECH
Jungseul Ok
jungseal@ppsseec..com
Graduate School of Artificial Intelligence
POSTECH
Suha Kwak
kuha. Opwsttehhhcccoccm oc.kr
Graduate School of Artificial Intelligence
POSTECH
Reviewed OpenReview:
net/ forum? id= LhHal
Abstract
This paper introduces a cost-efficient active learning (AL) framework for classífication, fea- turing a novel query design called condidate set query. Unlike traditional AL queries requir- ing the oracle examine all possible classes, our method narrows down the of candidate classes likely include the ground-truth class, significantly reducing the search space and labeling cost. Morcover, yet reliable candidate sets, adapting to model enhancement over successive AL rounds. To this end, we introduce an acquisition function designed to prioritize data points that offer high information gain at lower cost. Empirical evaluations on CIFAR-10, CIFAR-100, and ImageNet64x64 demonstrate the effectiveness and scalability of our framework. Notably, reduces labeling cost. by 48% on ImageNet64x64. The project page can be found at httpss:/yebogron.gittbbb.oo iocq--l
leverage conformal prediction to dynamically generate small
1
Introduction
Deep neural networks owe much of their success large-scale annotated datasets (Deng 2009 Kirillov
et al. 2023 OpenAl 2023 Radford et al.] 2021). Scaling datasets is crucial for improving both of their performance (Hestness el. al. 2017 Zhai et al. 2022) and robustness (Fang et. al. 2022 However, the resources demanded for manual annotation pose significant bottleneck, particularly in fields requiring expert input like medical data. In response to these challenges, cost-efficient methods for dataset collection,
such as semi-automatic labeling (Kim et al. 2024 Qu et al., 2024 Wang et al. 2024), synthetic data
generation (Liu et al.] 2019a, Tran et al. 2019 and active learning (AL.) (Ash al. 2020 Kirsch et al. 2019 Sener & Savaresc
2018 Scttles 2009 Sinha al. 2019
Wang Ye 2015) have been studied.
"equal contribution.

---

Published in Transactions on Machine Learning Research (08/2025)
Comparison on query for classification
Labeling cost based on candidate set size
Conventional query
Apple
Dolphin
8.3
Time per query (s)
Theoretica costs
Bed
sec
Bed
Car
Wolf
(Image)
(32 candidates)
(Annotation click) (Label)
Candidate set query
Apple
Bed
3.5 sec
Bed
User study
O Chair
Theory
Wolf
16 Size of candidate set
32
(Image)
(Model)
(4 candidates)
(Annotation click)
(Label)
Conventional query versus candidate set query. (left) While the conventional query presents all possible options to annotators, CSQ leverages the knowledge of the model to offer narrowed options that are likely to include the ground-truth label, thereby reducing the annotation time. (right) By conducting a user study on 40 participants, we demonstrate that the labeling cost increases logarithmically to the candidate set size, which closely aligns with the informatiion-heeoellii cost suggested by HHu el. al. (2020) with correlation coefficient of 0.97. Note that as the labeling cost increases per sample, the overall labeling cost increases significantly when multiplied by the total number of labeled samples. Further details of the user study are provided in Sec. 4.2 and Appendix A
Figure 1:
This paper investigates AL for classification, where training algorithm selects informative samples from the data pool and queries annotators for their class labels within a limited budget. We focus improving the design of annotation queries, emphasizing their critical role. To be specific, consider image classification of L classes. In the conventional query design, an annotator is asked to choose a class from a list of L classes. Here, the effort needed to review the entire class list and identify the correct class increases as the list size I, increases; according to an information--hcoreti analysis {u et al.] 2020). the cost of choosing among options is log, L. To address this issue of growing annotation cost, recent studies (Hu et al. 2020) Kim al.) 2024) employ a 1-bit query design asking annotators to check if the top-1 model prediction is correct. While this simplifies and speeds up annotation, it produces weak supervision incompatible with standard classification loss functions, necossitating specialized losses and algorithms like contrastive loss and semi-supervised learning techniques.
We propose candidate set query (CSQ), novel AL query design that remains cost-efficient with increasing classes and integrates scamlessly with cxisting loss functions. CSQ presents the annotator with an image and a narrowed set of candidate classes, which likely to include the ground-truth class. The annotator first searches this small candidate for the ground-truth class and proceeds to the remaining classes only if the ground-truth class is not found during the first scarch. This query approach can reduce labeling cost by reducing the search space required for annotation, which is particularly effective in scenarios with wide range of classes where the search space for the annotator could be extensive. Figure left) compares CSQ with the conventional query in AL for classification to show its efficiency.
In the CSQ framework, the design of the candidate set is crucial for its effectiveness. On one hand, too many candidates unnecessarily increase the labeling costs. On the other hand, too few candidates are likely to omit the ground-truth class, requiring an additional query to identify the ground-truth class among the remaining classes, which is more expensive than the conventional query. To enhance the effectiveness of the CSQ framework, propose to construct candidate sets guided by prediction uncertainty from trained model using conformal prediction (Shafer & Vovk 2008 Angelopoulos et al. 2023). Conformal prediction aims at constructing a set. of predictions including the true class, where each set is properly sized based on the certainty of the model about the input. This strategy enables flexible adjustment of the candidate set for each sample, expanding for an uncertain sample include the truc label and shrinking it for a more certain one reduce the labeling cost. Furthermore, we optimize the level of certainty in conformal prediction to minimize the labeling cost for each round. Therefore, this candidate set construction adapts
2

---

Published in Transactions on Machine Learning Research (08/2025)
to the increasing accuracy of the model over successive AL rounds, refining the candidate set as the model improves.
Last but not least, we propose a new acquisition function designed to maximize the cost efficiency of CSQ. Conventional acquisition functions in AL are designed to favor samples with high estimated information gain, assuming uniform annotation costs across all samples. On the other hand, in CSQ, the labeling cost for each sample varies according to the size of its candidate set. Thus, we propose an acquisition function that evaluates samples based on the ratio of estimated information gain to labeling cost. Specifically, we combine the conventional acquisition function score, which indicates the estimated information gain, with the estimated cost derived from the candidate set, favoring samples that maximize information gain per unit cost. This cost-efficient. acquisition function can incorporate with any sample-wise acquisition score, ensuring the selection of both informative and cost-efficient samples.
The proposed method achieves stato-of-tho-art performance on CIFAR-10 Krizhevsky et al., 2009), CIFAR- 100 (Krizhevsky al., 2009), and ImageNeu64x64 (Chrabaszcz al., 2017). We verily the ellectiveness and generalizability of CSQ through extensive experiments with varying datasets, acquisition functions, and budgets. Notably, CSQ achieves the same performance as the conventional query on ImageNet644664 at only 48% of the cost, showing its scalability. Our ablation studies demonstrate that both our candidate set construction and sampling strategy contribute to the performance. Furthermore, the necessity of CSQ is demonstrated by a user study involving 40 participants. In short, the main contribution of this paper is four-fold:
We propose a novel query design for active learning, where the annotator is presented with an image and narrowed set of candidate classes that is likely to include the ground-truth class. This approach, termed CSQ, reduces labeling cost by minimizing the scarch space the annotator needs to explore.
To maximize the advantage of CSQ, we propose to utilize conformal prediction to dynamically generate small yet reliable candidate sets optimized to reduce labeling costs, adapting to the evolving model throughout successive AI. rounds.
We propose a new acquisition function that prioritizes data point expected to have high information gain relative to its labeling cost, enhancing cost efficiency.
The proposed framework achieved state-of-the-art performance on diverse image classification datasets, CIFAR-10, CIFAR-100, and ImageNet64x64, showing its effectiveness and generalizability.
2
Related Work
Acquisition functions in AL. The key to AL to select and annotale the most informat ive samples (Sel-
tles
2009 Dasgupta. 2011
Hanneke et al. 2014). To assess informativeness, various acquisition functions
have been proposed, considering either the uncertainty of model predictions (Asghar et al.) 2017 He ct al.
2019 Ostapuk et al.
2019
Fuchsgruber et al. 2024 Kim et al. 2024 Cho et al. 2024
Kim et al. 2023
Wang et al. ), diversity in feature space (Sener & Savarese 2018 Sinha et al.
2019
Yehuda et al. 2022
or both (Ash et al.
2020 Hwang et al. 2022) Wang & Ye, 20155) Wang et al.] 2019
Hacohen et al. 2022
Hacohen & Weinshall (023). Disagreement- based AL and its variants are supported by rigorous theoretical
learning guarantees (Hanneke et al.] 2014 Krishnamurthy et al. (019). However, these methods assume uniform sample costs and select based solely on the amount of information. We emphasize that the labeling cost required for each sample varies and prioritize samples offering the best information--o-costt ratio.
Efficient query design. Designing efficient annotation queries reduces the annotation costs of craft- ing datascts. In AL, diverse types of queries have been investigated, including conventional classification
queries (Huang et al. 2015 Kang et al. 2020 Yu et al. 2020 Xie & Huang] 2021 Cour el al. 2011), oie-bit queries (Hu et al.) 2020; Joshi et al.) 2010) asking for yes or no answers, multi-class queries (Hwang et al,,
2023) identifying all classes within a set of multiple instances, relative queries (Qian et al., 2013)) asking for similarity of triplets, and correction queries (Kim et al., (2024) utilizing pseudo labels from the model. While these query methods require tailored loss functions, our candidate set query (CSQ) is cost-efficient
3

---

Published in Transactions on Machine Learning Research (08/2025)
and provides complete supervision, integrating scamlessly with existing loss functions. The approach closely related to CSQ is the n-ary query (Bhattacharya & Chakraborty, 2019), which reduces the search space by asking for the correct class among top-n predictions of the model. However, the n-ary query uses a fixed number of top-n predictions for all data without considering individual sample difficulty. On the other hand, CSQ adjusts the candidate set size based on sample difficulty and model performance using conformal pre- diction. Through rigorous comparisons, we demonstrate that CSQ achieves a superior model performance at the same cost compared to the previous query designs.
Realistic cost model for AL. We consider annotation cost, rather than the mumber of labeled samples, as the primary objective of active learning. While we follow Hu et al. (2020) in modeling annotation cost based on the size of the labeling options using an information-theorellic perspective, other works have ex- plored additional factors influencing real-world annotation cost, such as annotator behavior and interaction complexity (Settles et al. 2008 Arora et al., 2009; Wallace et al., 2011: Herde et al., 2021). For exam- ple, SSttles et al. (2008) and Arora et al. (2009) show that instance, task, and user features jointly affect annotation time, while Wallace et al. (2011) propose a cost-saving strategy where less experienced annotators can pass uncertain cases to more experienced ones. Herde et al. (2021) provide taxonomy of cost-aware active learning approaches under more realistic assumptions. These studies highlight that annotation cost depends on multiple factors and varies across settings. While our size- azzeb proxy is effective and supported by user study, richer cost. models may better capture real-world annotation behavior and further improve performance.
Conformal prediction (CP). CP enables us to quantify uncertainty in predictions with an associated confidence level (Shafer & Vovk 2008). Recent advances in CP empower classifiers to generate predictive sets that include the ground-truth label with a probability chosen by the user (Angelopoulos et al.) 2020; 2023). In the field of AL, nonconformity measurements from CP are employed in the acquisition function to select informative samples (Matiz & Barner 2020). In contrast, we utilize CP not only to develop a cost-efficient acquisition function but also to design an efficient candidate set query, reducing the labeling cost.
3 Proposed Method
We consider general classification tasks such that for input x and a categorical variable y E y= a model parameterized by 0 predicts the class of the input as arg max Po x). We study an active learning (AL) scenario conducted over rounds. In each round r, a budget of B samples with high acquisition function values is actively selected from the unlabeled data pool X. This actively selected set A, is then labeled by annotator to form the labeled dataset D, with labeling cost Cr, and is used to update the model. Let 0, denote the model trained on the accumulated labeled data up to round r, Ui=o Our goal is to maximize the performance of O,, while minimizing the accumulated cost Ui_o C.. The key aspect of the proposed method is candidate set query (CSQ), which reduces C, by narrowing the set of candidate classes presented to annotators. For simplicity, we omit the round index r from 0, in the remainder of this section.
In the following, we first introduce CSQ and discuss its efficiency in labeling cost (Sec. 3.1. Then, we present method to construct a candidate set based on the prediction uncertainty of trained model for given sample (Sec. b.2h. Lastly, introduce acquisition function designed to consider cost efficiency as well as information gain (Sec. 3.3). The overall pipeline of the CSQ framework combined with our cost-cfficient sampling is summarized in Algorithun 1
3.1 Candidate set query
CSQ for an instance x is associated with (non-empty) candidate set Y(x) S ) such that 1 < [Y() < L. CSQ first asks the annotator to choose the ground-truth class in Yx) if it exists, or to verify the absence of the ground-truth label in (x), i.e., the annotator is first asked to pick an option out of (k: + 1) choices, where k = (x) Only if the absence of the ground-truth class in the candidate set is verified, the annotator is further asked to select the ground-truth class from the remaining ones y \ Y(x). In short, CSQ asks the following query with an image to the oracle.
4

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm Cost-efficient active learning with candidate set query
Require: The number of AL rounds R, per-round budget B, unlabeled data pool N, initial labeled dataset Do-
1: Train the initial model 0o on Do.
2: for 1, ,,, R do
3: Estimate sample-wise wise labeling cost
4: Select B samples A, C X considering both their estimated labeling cost and informativeness.
> Sec. 3.3
Construct candidate set (xx) for each X.
Sec. 3.2
6: Query annolator for label y of x E Ar using candidate set (x) to form Dr.
Get model 0, trained Ui_o D..
8: end for
9: Return Final model OR.
Select the ground-truth class from the condidate set, or choose "None of the above." (only if "None of the above" is chosen): Select the ground-truth from the remaining classes.
Following the thooreie cost model of (Hu al. 2020) and the user-study results in Table we model the cost of selecting one label from & candidates as loge k. Then, the labeling cost I(Y (x))x)) of CSQ for input x, ground-truth label y, and candidate set ((x) S y can be obtained as:
(x).)) = logg(k + +1) 1ogg(k 1) + logz (T. - k)
y E (x))
(1)
otherwise
The conventional query in AL is a special case of CSQ where Y(x) - V, and it is inefficient since the annotator must search through the entire set of size with a cost of log, L. The following theorem reveals the condition under which the expected cost of CSQ offers an improvement over that of the conventional query.
Theorem 3.1. Assume the information-lheoree
cost model (Hu el al,, 2020) of selecting one oul of L possible options to be log, L. Let L 2 2 be the number of classes, == 1Y (x),, and a be the probability that the candidate set Yx)) does not include the ground-trui truth class of instance x. Denote by Ceon and Cesq the expected costs of the conventional query and the condidate set query, respectively. If
logg 11
a
(2)
logg L
then the candidate set query is strictly cheaper, i.c., Creg (L, x, a) < Coon (L,x).
Proof. Recalling the definition of a, we have Cesq X, from Eq. ①1 As < L, the cost ratio of Casq L, x, a) to Ceon (L, x) for instance x is induced as:
x, a) = (1-a) log, (o
loga (L- k}}
Cesq (L,x, Ceon (L,x)
loga + 1) + algg (L k)
log L logz (k +
a.
(3)
loga L
Although we adopt the cost model from Hu et al. (0200) Theorem 3.1 holds for any cost model that increases monotonically with the number of options.
Remark 3.2. If we construin all condidale set sizes k to be fiaed, then - corresponds to the lop-k accuracy Ps of the model. Therefore, when pk 2 log, (k + 1), CSQ consistently offers an improvement over the conventional query the expected labeling cost. For ezample,
datasets such as CIFAR (I. 10), CIFAR- 100 (L- 100), and ImageNet (L 1000), if the model has a top-1 accuracy (i.c., & 1) of at least 30.1 1 17,,, 15.1 %, and 10.0% respectively, then CSQ always provides improvemend.
5

---

Published in Transactions on Machine Learning Research (08/2025)
The above proof and remark demonstrate that under moderate conditions, CSQ is more efficient than the conventional query. As described in Eq. [3. the cost of CSQ decreases as both and k become smaller. However, since & and are inversely related, balancing the trade-off between a and k is essential to fully leverage CSQ. Also, fixing candidate set sizes as in Remark 3.2 is suboptimal because it does not consider the difficultyy of individual samples. In the following section, we introduce our candidate set construction method, which both reflects the uncertainty of each sample and automatically balances the trade-off between a and k.
3.2 Construction of cost-efficient candidate set
As shown in Eq. 1 and Theorem 3.1 a candidate set needs to be both small and accurate in covering the ground-truth class. To do so, we propose using conformal prediction (Romano al. 2020 to get. a reliable and cost-optimized candidate set using the trained model 0 of the previous round.
Calibration set collection. Conformal prediction requires a labeled set for calibration that has not been used during the model training phase; this set must follow the same distribution as the target dataset for prediction (Vovk et al. 1999 Angelopoulos et al. 2023 To achieve this, we randomly select neat samples from the actively selected data Ar and annotate them within the given budget to form Deat = {(x,,,)) )=) Maal
The calibration set Deal is used for conformal prediction and candidate set optimization, which will be explained in the following sections. Note that Deal also contributes to model training after the candidate set construction.
Conformal prediction. Using the model 0 from the previous round and calibration set Deal C A, of size Real, we define a collection of conformal scores s := (s:)?en, where 8; == 1 Pe(y x.) for (x;, Bi) E Deal- Then, obtain the (1 - a) empirical quantile (aa) of s, indicating that at least 100 a)% of the scores in are smaller than (a). This empirical quantile (a)) is given as,
(a) == min sEs
5:
1
Σ s'Es
[1[s's
< 2 ()))) 11)21-a.
(4)
Peaal
where E 10. is an error rate hyperparameter, and 1[+] is an indicator function. Then, we define the candidate set (o(x, a) for unlabeled data x using conformal prediction as follows:
8o(x,a) = (v Polulx) 2 ((a), y y
(5)
2023) proved that the candidate set includes the true Previous study (Vovk et al. 1999 Angelopoulos et al.
label with the probability not less than 1 a, which is,
P(y E Po(x, 2 1 - a
(6)
This ensures the inclusion of the ground-truth classes even under model overconfidence, while adaptively reflecting uncertaintics throughout the AL. process. Without loss of genorality, we consider Yo 0) = y, where y corresponds to the conventional query. More detailed procedure of conformal prediction is in Appendix C
Cost-optimized error rate selection. The proposed candidate set construction method (Eq. (5) adapts the size of the candidate set for each sample based on its predicted uncertainly. While this allows the candidate set to be both compact and reliable, it requires manually adjusting the hyperparameter eliminate the need for manual tuning, we introduce an automatic selection scheme that optimizes a at each AL round by minimizing the expected labeling cost on the calibration set, which serves as a pscudo-validation set. To be specific, a optimized by
To
a' = arg min aE(011)
Σ r(fo(x,)).),
(7)
(x.)))
where I[: y) is the labeling cost in Eq. predefined options of a. The optimization is computationally efficient, requiring only negligible computation
We implement this optimization using grid search over
6

---

Published in Transactions on Machine Learning Research (08/2025)
shown in Figure This approach not only eliminates the reliance hand-tuned hyperparameters but also helps construct candidate sets in more cost-efficient manner, the selected a" is tailored to minimize the labeling cost under the proposed cost model for each round. Since the optimization in Eq. 7 naturally considers the conventional query as a special case of CSQ at a = 0, CSQ is at least as efficient as, and in general more efficient than, the conventional query.
Note that to construct the candidate set query, the calibration set Deal is required calculate (1-a*) quantile in Eq. 4 Thus, when getting annotations of Deal in the calibration set collection step, the candidate set query of the current round cannot be applied. To avoid this circular dependency, the quantile from the previous round is used when labeling Deal-
3.3 Cost-efficient acquisition function
Since the labeling cost of each sample varies in CSQ, we propose to consider the cost for annotation in the acquisition function. We implement acquisition function that evaluates samples based on the ratio of the estimated information gain to the estimated labeling cost. The information gain is quantified using an ostablished acquisition score, entropy, BADGE (Ash et al. 2020). ProbCover (Yehuda et al. 2022 b or SAAL (Kim et al. 2023), though our approach compatible with other acquisition scores as well, not just these. Given conventional acquisition score Jscore the proposed cost-effcient acquisition function Jeost
is given by,
(1 Iscore (x)))e(x)) (x))
gcost := logy(k + 1) + a logz(L- - k)
(8)
where d is hyperparameter adjusting the inftuence of Iscoro and a' is the optimized error rate hy- perparameter obtained by Eq. 77. The denominator is an expected cost derived from cost model (Eq. (1, considering two cases: the correct label is included or excluded from the candidate set, which is (1 - log + +) + a" (log2 + 1) + (L - (- This expected cost assumes the candidate set to include the ground-trute wooudd-ruuh class with a probability of a", which is supported by the coverage guarantee in Eq. (
4 Experiments
4.1 Experimental setup
Datasets. We use three image classification dalasets: CIFAR-10 Krizhevsky et al. 2009). CIFAR-100
(Krizhevsky et al. 2009), and ImageNet64x64 (Chrabaszez et al. 2017p. CIFAR-10 comprises 50K training and 10K validation images across 10 classes. CIFAR-100 contains the same number of images as CIFAR-10 10,
but is associated with 100 classes. ImageNet64x64 is a downsampled version of ImageNet. (Deng el al. 2009 with a resolution of 64 x 64, which consists of 1.2M training and 50K validation images with 1000 classes. Following previous studies, we evaluate a model using the validation split of each dataset.
Implementation details. For CIFAR-10 and CIFAR-100, we adopt ResNet18 (He et al. 2016 classification model. We train it for 200 epochs using AdamW (Loshchilov & Hutter 2019) optimizer with an initial learning rate of le-3, decreasing by factor of 0.2 at epochs 60, 120, and 160. We apply a weight decay of 5c-4 and a data augmentation consisting random crop, random horizontal flip, and random rotation. For ImageNet64x64, we adopt WRN-36-5 (Zagoruyko 2016), and train it for 30 epochs using AdamW optimizer with an initial lcarning rate of 8c-3. We apply a learning rate warm-up for 10 epochs from 2e-3. After the warm-up, we decay the learning rate by factor of 0.2 every 10 epochs. We adopt random horizontal flip and random translation use Mix-up (Zhang et al.) 2018), where a mixing ratio is sampled from Beta(1, We set the size of the calibration dataset Teaal to 500 for CIFAR-10 and CIFAR-100, and 5K for ImageNet64x64. For all datasets and acquisition functions, hyperparameter d in Eq. S is set to 0.3.
data augmentation. For all the datasets, we
Active learning protocol. For CIFAR-10, we conduct 10 AL rounds of consccutive data sampling and model updates, while for CIF,R-100, we perform 9 AL rounds. In both cases, the per-round budget is 6K images. For ImageNee664x64, we conduct 16 AL rounds with per-round budget of 60K images. The detailed
7

---

Published in Transactions on Machine Learning Research (08/2025)
CQ Rand
CQ I Ent
CQ BADGE
CQ | ProbCover
CQ SSALL CSQ+ Cozt(SAAL)
CSQ+ Rand
Cos+Cos((En)
CSQ+ Cost(BADGE)
CSQ+ Coost(robbCover)
70
65
90
Accuracy (%)
Accuracy (%)
60
50
Accuracy
55
85
45
50
45
40
40
20 40
100
40
80
Relative labeling cost (%)
Relative labeling cost (%)
Relative labeling cost (%)
(a) CIFAR-10
(b) CIFAR-100
(c) ImageNer64x64
Figure Accuracy (%) versus relative labeling cost (%) for conventional query (CQ) and the proposed candidate set query (CSQ) with different acquisition functions. CSQ approaches (blue lines) consistently oulperform the CQ baselines (red lines) by significant. margin across various cost budgels, acquisition functions, and dataset
budget configuration for the three datasets is shown in Table 5 In the initial round, we randomly sample 1K images for CIFAR-10, 5K images for CIFAR- 100, and 60K images for ImageNet64x64. In each round, the model is evaluated based on two factors: its accuracy (%) on the validation set, and the accumulated annotation cost required to train it. The annotation cost is defined as a relative labeling cost (%) compared to the cost of labeling the entire training set using the conventional query, given by N Vogg I., where is the size of the entire training set, and L is the number of classes. We conduct all experiments with three independent trials with different random seeds and report the mean and standard deviation to ensure reproducibility.
Baseline methods. We compare our candidate set query (CSQ) with the conventional query (CQ) in combination with various sampling strategies. To be specific, we employ random (Rand), entropy (Ent), BADGE (Ash et al.) 2020), ProbCover (Yehuda et al. 2022), and SAAL (Kim et al. 2023) as the sampling strategics. Cost(.) indicates the proposed cost-cfficient sampling (Eq. (8)) using conventional acquisition scores; e-g., Cost(SAAL) is the one combined with SAAL. We denote the combination of the query and
sampling method with '+', e.g., Rand is candidate set query combined with random sampling.
4.2 Experimental results
Candidate set query vs. Conventional query. In Figure 2 we compare the performance of the candidate set query (CSQ) with the conventional query (CQ) CIFAR-10, CIFAR-100, and Tmagexee664664 with different acquisition functions. CSQ approaches consistently outperform the CQ approaches across various acquisition functions and datasets, demonstrating the general effectiveness of our method. Notably, CSQ reduces the labeling cost by 43%, 54%, and 48% on CIFAR-10, CIFAR-100, and ImageNet64x664, compared to CQ, respectively. This is promising as it shows that the same volume of labeled data can be obtained at roughly half the cost, without introducing any label noise or sample bias. Notably, the performance gain of CSQ increases as the model improves, as it is tailored to the improved model. In the appendix, we also present experiments on text classification task (Figure [4] showing the generalization ability of the proposed method to the natural language domain. Additionally, we provide the zoomed version of Figure 2 in Figure 19 and Figure 20
Unfortunately, ImageNet64x644, exclude the BADGE and ProbCover acquisition baselines due their computational intractability.
8

---

Published in Transactions on Machine Learning Research (08/2025)
Avg. size of candidate set
Avg. size of candidate set
Ávg. size of candidate 1000
10
70
55
90
Soocuut syg (%)
50
120
6
60
45
80
40
80
40
73
20
40
35
30
70
40
0
2 4
6 8
10
2
2 4 6 10121416
Round
Round
Round
(a) CIFAR-10
(b) CTFAR-100
(c) ImageNet664x64
Figure 3: Average size of the candidate set and accuracy (%) of method with cost-cfficient entropy sampling in varying rounds on CIPAR-10, CIFAR-100, and includes all classes at the imitial round, but our candidate set design effectively reduces its size over successive active learning rounds, adapting dynamically as the model accuracy improves.
Note that the candidate set
Table 1: User-study results on a fixed image set with different numbers of class options presented to the annotator. A smaller option set yields both faster annotation and higher accuracy. The empirical trends also align closely with the theoretical cost curves Figure [ right). all experiments, we treat annotation cost as proportional annotation time, which we consider a more practical measure than simply counting labeled examples.
Class options (#)
4
8
16
32
Annotation Time (s)
69.4
91.5427.3
116.9429.6
166.9
Accuracy (%)
100.040.0
98.543.2
99.5
95.5
Progressive reduction in candidate set size. The effectiveness CSQ stems from its ability to reduce labeling costs through smaller candidate sets. To demonstrate this, Figure 3 shows the average size of the candidate sets and accuracy (%) of our method with varying AL rounds on CIFAR-10, CIFAR-100, and ImageNet64x64. After the first round, CSQ achieves sufficiently small candidate set size and continues to reduce it accuracy improves, thereby enhancing labeling efficiency.
Empirical validation for our cost model. We conduct user study with 40 annotators who label samples using candidate sets of various sizes; see Appendix A for more details. The results in Table I suggest that shrinking candidate sets improves both labeling efficiency and accuracy. They also align closely with the theoretical cost (Hu et al. 2020 as shown Figure right).
4.3 Ablation studies
Contribution of each component. Figure demonstrates the contribution of each component in method across varying AL rounds: candidate set query (Fq. (5)) cost reduction from a" (Eq- (7).. and the proposed acquisition function (Eq. ( The results show consistent performance improvements from each component in every round. The performance gap between CQ+Ent and CSQ(a= 0.1)+Emm Ent verifies the efficacy of proposed CSQ framework, which provides the largest improvement. The gap between (01(a=0.1)+EE)) and CSQ+Ent Ent shows the impact of a optimization, offering modest but steady gains across rounds. Finally, the gap between Ent+Ent and CSQ+Cost(Ent) shows the effectiveness of our acquisition function, particularly from round to 6.
we evaluate the relative labeling cost (%) at the fifth round with varying calibration set sizes Real in Eq. 14 to assess its impact on the performance on CIFAR-100. As shown in Figure 4b our method shows consistent performance, varying by less than 2%p as the calibration set size changes from 0.1K to 2K, and significantly outperforms the baseline.
Impact of calibration set size. In Figure 4b
Detailed ablation study on candidate set design. Figure illustrates the effectiveness of using con- formal prediction (Conformal (a=0.1)) for candidate set construction CIFAR-100, compared to baselines:

---

Published in Transactions on Machine Learning Research (08/2025)
CQ+ (50 0.1)+Emt
CSQ+Ent (SQ+Coou(Ent)
0Q+Ext (3Q-Com((En)
70
Relative labeling cost. (%)
100
Relative labeling cust, (%)
60
Accuracy (%)
80
55
60
50
60
45
30
40
40
40
20
100 Relative labeling cost (%)
20 40
60
80
3
5
7
0.1 0.5
Round
Size of calibration set Reaa (K)
(a) Contribution of each component
(b) Impact of calibration set size
Figure 4: (a) Contribution of each component of our method, measured by accuracy (%) versus relative
labeling cost (%) (left), and relative labeling cost (%) versus AL rounds (right) on CIFAR-100 The results compare the full method (CSQ+ (oo@++Etss()))) the method without acquisition function in Eq. (8) without a optimization in Eq. 7 where a is fixed to 0.1 (CSQ(a=0.1) +.n)) and without CSQ (CQ+Ent). All components of our method lead to steady performance improvement over varying rounds. (b) Relative labeling cost (%) the fifth round with varying calibration set sizes Real in Eq. 4 on REFAR-100. The dashed line indicates the relative labcling cost (%) of CQ+ Ent. Our method shows consistent performance with varying calibration set sizes.
Conventional
Tapl
Top10 (Bbatiacharya & Chaiaaborit, 2019)
Conformal (a=00.1
Oracke
100
100
Relative labeling cost (%)
70
GT inclusion rate (%)
900
80
Accuracy (%)
65
60
60
55
40
40
50
20
20
100 Relative labeling (%)
6
8
Round
Round
(a) Accuracy
(b) Relative labeling cost
(c) GT inclusion rate
Figure 5: Impact of the candidate set design evaluated on CIFAR-100 using the conventional query with all classes (Conventional), top-1 prediction from model (Top1), top-10 predictions from model (Top10), our method with conformal prediction with fixed =.1 (Conformal( and the smallest top-k prediction sets always including the ground-truth class (Oracle). Note that Top10 is a variant of the n-ary query (Bhattacharya & Chakraborty 2019) baseline. For comparison, the same entropy sampling is used to keep the accuracy at each round constant, focusing solely on the labeling cost and isolating the effect of the candidate set design. (a) Our method constantly outperforms the baselines both in accuracy (%) and relative to labeling cost (%). (b) Our design achieves greater reduction in labeling cost compared to the basclines.
(c) Our candidato set effectively includes the ground-truth class in over 90% of cases (=1 a), even when model accuracy is low.
Conventional (using all classes), Topl (top-1 prediction), Top10 (top-10 predictions), and Oracle (smallest top-k set always containing the ground truth). Note that Oracle represents unattainable upper bound requiring knowledge of the ground truth. Top10 is variant of the n-ary query (Bhattacharya & Chakraborty 2019) baseline. For consistency, we fixed = 0.1 in Eq. 5 Figures 5a and 5b show that conformal prediction consistently reduces labeling cost compared to the baselines. While Top10 effective in the early rounds and Topl becomes more efficient as the model improves, our method adapts and outperforms all basclines in every round. Figure 5c demonstrates that with a 0.1, our method includes the ground-truth class in over 90% of cases, aligning with Eq. ( while the top-k baselines show lower inclusion rates, especially in
10

---

Published in Transactions on Machine Learning Research (08/2025)
Table 2: Effectiveness of the proposed cost-efficient sampling (Cost(-)) on C1FAR-100, reported as accuracy per cost. All methods employ the same candidate set query (CSQ) framework, and we simply replace the acquisition function baselines with their Cost(-) variants. Our sampling consistently improves the performance across various acquisition functions and AL rounds. The best results are highlightod in bold.
Acquisition
2nd round
3rd
round
4th round
3th
round
6th round
7th round
8th round 9th round
Ent
2.36
1.74
1.55
1.43
1.36
1.30
1.26
1.24
Cost(Ent)
2.36
2.09
1.89
1.68
1.56
1.48
1.37
1.30
BADGE
2.51
1.94
1.69
1.51
1.40
1.34
1.29
1.27
Cost(BADGE)
2.64
2.17
1.92
1.75
1.58
1.49
1.37
1.32
ProbCover
2.43
1.72
1.60
1.55
1.47
1.39
1.33
1.30
Cost(ProbCover)
2.43
2.10
1.98
1.79
1.66
1.52
1.39
1.32
SAAL
2.37
1.83
1.55
1.43
1.37
1.32
1.28
1.25
Cost(SAAL)
2.36
2.12
1.94
1.74
1.64
1.50
1.38
1.31
Relative labeling cost (%)
65
Relative cost per round (%)
100
55
Convertional
Round 5
50
0.2
40
0.3
Selected at
True optineal
45
5
0.2
0.4
0.6
0.8
Round
(a) Impact of cost-oplimized error rale
(b) Quality selected error rale
Figure 6: Impact of cost-optimized error rate selection as in Eq. 7 evaluated on CIFAR-100 with entropy sampling. (a) Relative labeling cost (%) versus AL rounds with different error rate a compared with the a" selected by the proposed method (Eq. 77). This shows our method removes manual tuning by automatically choosing an adaptive error rate at each round. (b) Relative labeling cost per round (%) versus a across various AL rounds. The cost curves reveal that selecting the right error rate greatly lowers labeling cost, with the benefit growing in later rounds. Pink triangles mark the true optimal a, blue squares mark a" from our method. The selected a" remains consistently close the true optimum, enabling each round to sharply reduce labeling cost.
early and middle rounds. This demonstrates that conformal prediction effectively adjusts candidate set sizes based sample uncertainty, ensuring ground-truth inclusion and improving labeling efficiency.
we investigate the impact of the proposed cost-efficient sampling (Sec. (3.3) on CIFAR-100, where performance is measured by accuracy per cost (i.e., accuracy divided by relative labeling cost). This metric reflects how efficiently a method achieves high accuracy under a fixed annotation budget-higher higher values indicate better cost-elfeectiveness. The proposed cost-cfficient sampling strategy consistently improves performance across different acquisition functions, with gains observed throughout various AL rounds. A more detailed accuracy versus labeling cost graph is illustrated in Figure 10
Detailed ablation study on cost-efficient. acquisition function. In Table 2
Ablation study on cost-optimized error rate sclection. In Figure 6a we present the impact of cost- optimized error rate selection as in Eq. ( evaluated on CIFAR-100 using entropy sampling, in terms of relative labeling cost (%). Compared to the baselines using hand-picked enror rate values, the cost-optimized error rate a* from the proposed method consistently reduces labeling cost across all AL rounds. This demonstrates that the proposed method reduces the need for manual tuning of the error-rate hyperparameter rate optimized for each AL round.
and instead automatically selects
11

---

Published in Transactions on Machine Learning Research (08/2025)
4.4 In-depth analysis
Quality of the optimized error rate a". In Figure 6b we compare the optimized error rate (a", blue squares) selected by our method with the true optimal error rate (pink triangles), showing their relative labeling costs (%) across different AL rounds. As indicated by the labeling cost curves for each error rate, choosing an effective error rate significantly impacts cost reduction, and this impact becomes more prominent at later rounds. Our proposed method adaptively selects an optimized error rate (a*) close to the true optimal error rate at each AL round, substantially reducing labeling costs.
Analysis on computational complexity. Figure i plots the wall-clock time measured in minutes of each strategy as the size of unlabeled pool from ImageNct6-4x64 grows from 10K to 0.7M images. The dashed curve isolates the cost of the candidate set query (CSQ) itself and reveals a flat line: constructing candidate sets is constant time, independent of the unlabeled pool size. All autropy-based samplings, including our proposed CSQ+ Cost(Ent), exhibit the expected linear slope. This confirms that both the candidate set query and cost-efficient sampling add negligible overhead, preserving the linear complexity of standard entropy sampling. By contrast, CQ+BADGE rises steeply owing to the k-means++ seeding inside BADGF with an accelerated implementatior""
even
Table 3: Detailed comparison of wall-clock time mea- sured in minutes (mean + standard deviation across three different random seeds) with an unlabeled data pool of size 1.21 million from ImageNet64x64. The ta- ble decomposcs the total runtime into Query (for con- structing candidate sets) and Sampling (for selecting informative samples). While conventional querying strategies (CQ+Ent and CQ+BADGE) incur no query- time cost by presenting all classes to the oracle, the proposed CSQ framework introduces a marginal over- head (<0.05 minutes), thereby maintaining practical elficiency. Also, our cost-efficient sampling Cost(Ent) maintains the linear time complexity of standard en- tropy sampling, while adding only marginal addi- tional cost. Together, these results show that the full pipeline CSQ+ (SQ+CCst(Ent) achieves competitive compu- tational efficiency without sacrificing scalability.
3
CQI Ent CSQ+Ent
CSO=Coe((m)) CQ-RADGE C5Q
2.5
Wall-clock Lime (minutes)
1.5
0.5
0
0M
0.1M
0.2M 0.3M 0.4M 0.5M 0.6M 0.7M
Size unlabeled set
Query
Sampling
Total
Figure 7: Wall-clock time versus unlabeled pool size on ImageNet64x664. CSQ (dashed) runs in con- stant time, independent of pool size. Our sampling (Cost(Ent)) adds a negligible overhead, keeping the same linear complexity as plain entropy sampling.
CQ+Ent CQ+ CQ+BADGE
0.00+0.00
2.2940.01
2.29
0.00+0.00
17.6440.31
17.6440.31
CSQ+Ent
0.04
2.27
2.31
CSQ+ Cost(Ent)
0.04
2.26
2.31 10.02
Table 3 gives an absolute breakdown at the largest pool size (1.21 M images). Although conventional queries (CQ+Ent, CQ+BADGE) have zero query cost- cost-they they simply show all classes to the oracle our CSQ adds only <0.05 minutes, a negligible overhead that confirms the constant-time trend in the Figure 7 Likewise, replacing plain entropy sampling with its cost-efficient variant (Cost(Ent)) increases sampling time by less than 0.01 min, preserving the same linear complexity. Both components of our pipeline are light CSQ for querying and Cost(-) for sampling so the full method (CSQ + Cost(Ent)) remains scalable even on million-scale pools.
Foor computational feasibility we therefore cap its hudget 5000 images and its calibration size 500.
We adopt the accelerated code from Zhang et al. 22024).
12

---

Published in Transactions on Machine Learning Research (08/2025)
Baseball
Water buffalo
ball
Bison
Vase
Warthog
Rugby ball
Warthog
Soccer ball
Water buffalo
Elephant
M Beaver
Scale
Wallaby
D Car wheel
Porcupine
K Magnetic
Komodo dragon
O Washer
Compass
Beaver
M Lens cap
/ Armadillo
+ Coil
Easy samples = Small candidates
Hard samples Large candidates
Figure 8: Examples of input images and their corresponding candidate sets constructed using our method at the fifth AL round on ImageNet644x64. For each image, the v indicates the ground-truth class. Our method adjusts the size of each candidate set on the fly: it shrinks the set for confident cases (left) to reduce annotation cost, and enlarges it for uncertain ones (right) to include the ground-truth class.
Examples of constructed candidate sets. In Figure we present input images and their corresponding candidate sets on ImageNet66464. Thanks to the conformal prediction, the proposed method allows flexible adjustments of the candidate set for each sample.
5 Conclusion
We have introduced candidate set query, active learning framework that reduces the labeling cost effec- tively and efficiently by narrowing down the candidate set likely to include the ground-truth class. We have also proposed novel acquisition function that balances model performance and labeling cost by taking ex- pected candidate set sizes into account. Empirical evaluations on CIFAR-10, CIFAR-100, and ImageNet64x64 confirm the effectiveness our framework.
Limitations and future work. One limitation is that the proposed acquisition function lacks theoretical guarantec for label complexity (Dasgupta) 2011 Hanneke et al. 2014) at this point. Establishing thcoretical understanding to quantify the cost required to achieve target performance remains an interesting direction for future work.
Acknowledgemenn. This work was supported by the ITTP grants (RS-2021-I111206 25%, RS-2024- 00457882-255 DS-2002-11120926-4000 RSS20119-1111106-1100 funded by Ministry Science and ICT, Korea.
References
Anastasios N Angelopoulos, Stephen Bates, et al. Conformal prediction: A gentle introduction. Foundations and Trends0 in Machine Learning, 16(4):494 591, 2023.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In Proc. International Conference on Machine Learning (ICML), 2020.
Shilpa Arora, Eric Nyberg, and Carolyn Rose. Estimating annotation cost for active learning in multi- annotator environment. Proceedings of the NAACL HLT 2009 Workshop on Active Learning for Natural Language Processing, pp. 18 26, 2009.
Nabiha Asghar, Pascal Poupart, Xin Jiang, and Hang Li. Deep active learning for dialogue generation. Proceedings of the 6th Joint Conference on Levical and Computational Semantics (*SEM), 2017.
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alckh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds, In Proc. International Conference on Learning Representations (ICLR), 2020.
13

---

Published in Transactions on Machine Learning Research (08/2025)
Yalong Bai, Yuxiang Chen, Wei Yu, Linfang Wang, and Wei Zhang. Products-10k: A large-scale product recognition dataset. Xiv preprint arXiv:2088. 10545, 2020.
Aditya Bhattacharya and Shayok Chakraborty. Active learning with n-ary queries for image recognition. In Proc. IEEE/CVF Winter Conference Applications of Computer Vision (WACV), 2019.
Seong Jin Cho, Gwangsu Kim, Junghyun Lee, Jinwoo Shin, and Chang D. Yoo. Querying easily flip-Oopped samples for deep active learning. In The Twelfth International Conference on Learning Representations, 2024. URL httta://openrrviiet wttpaarrevieieneeffeeeeeeee mee/Foormmiid-THUTTEEA???
Patryk Chrabaszez, Nya Loshchilov, and Frank Hutter. downsampled variant of imagenct as an alternative to the cifar datasets. arXiv preprinl (eXix:1077.053 2017.
Corinna Cortes. Support-vector networks. Machine Learning, 1995.
Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. In Journal of Machine Learning Research (JMLR), 2011.
Yin Cui, Menglin Jia, Tsung-Y Yi Lin, Yang Song, and Serge Belongic. Class-balanced loss basod on effective number of samples. In Proceedings of the IEEE/CVE conference on compuler vision and pattern recogrition (CVPR), pp. 9268 9277, 2019.
Sanjoy Dasgupta. Two faces of active learning. Theorelical compuler science, 412(119:1767-177 1781,, 2011.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: large-scale hicrarchical image database. In Proc. IEEE/CVE Conference on Computer Vision and Pallern Recognition (CVPR), 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In Inter- national Conference on Learning Representations (ICLR), 2021. URL https::/openreviiee net/forum? id=YicbFaNTTy/
Pan Du, Suyun Zhao, Hui Chen, Shuwen Chai, Hong Chen, and Cuiping Li. Contrastive coding for active lcarning under class distribution mismatch. In Proc. IEEE/CVE /CVF International Conference on Computer Vision (ICCV), pp. 8927 8936, 2021.
Alex Fang, Gabriel Ilharco, Mitchell Wortsman, Yuhao Wan, Vaishaal Shankar, Achal Dave, and Ludwig Schmidt. Data determines distributional robustness in contrastive language image pre-training (clip). In Proc. International Conference on Machine Learning (ICML), pp. 6216 6234. PMLR, 2022.
Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: a survey. IEEE transactions on neural networks and learming systems, 25(5):845 869, 2013.
Dominík Fuchsgruber, Tom Wollschläger, Bertrand Charpentier, Antonio Oroz, and Stephan Günnemann. Uncertainty for active learning graphs In Forty-first International Conference on Machine Learning (ICML), 2024.
Guy Hacohen and Daphna Weinshall. How select which active learning strategy is best suited for your specific problem and budget. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems (NewrIPS), volume 36, pp. ran Associates, Inc., 2023.
Cur-
Guy Hacohen, Avihu Dekel, and Daphna Weinshall. Active learning on budget: Opposite strategies suit high and low budgets. In International Conference on Machine Learning (ICML), pp. 8175-8195. PMLR, 2022.
Steve Hanneke et al. Theory of disagroement- based active learning. Foundations and Trends8 in Machine Learning, 7(2-3):131 -30099, 2014.
14

---

Published in Transactions on Machine Learning Research (08/2025)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. IEEE/CV /VF Conference on Compuler Vision and Poltern Recognition. (CVPR), 2016.
Tao He, Xiaoming Jin, Guiguang Ding, Lan Yi, and Chenggang Yan. Towards better uncertainty sam- pling: Active learning with multiple views for deep convolutional neural network. In IEEF International Conference Multimedia and Expo (ICME), 2019.
Marek Herde; Denis Huseljic, Bernhard Sick, and Adrian Calma. A survey on cost types, interaction schemes, and amnotator performance models in selection algorithms for active learning in classification. IEEE Access, 9:166970-166988 2021.
Joel Hestnees, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint Xr:::171220000 00409, 2017.
Hengtong Hu, Lingxi Xie, Zewei Du, Richang Hong, and Qi Tian. One- bit supervision for image classification. Proc. Neural Information Processing Systems (NeurIPS), 33:501-511, 2020.
Jie Hu, Li Shen, and Gang Sun. Squeeze-and--exiiaatio networks. In Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
Sheng-Jun Huang, Songean Chen, and Zhi-Hua Zhou. Multi-label active learning: query type matters. In Proc. International Joint Conference on Artificial Intelligence (IJCAI), volume 15, pp. 946-952, 2015.
Sehyun Hwang, Sohyun Lee, Sungyeon Kim, Jungseul Ok, and Suha Kwak. Combating label distribution shift for active domain adaptation. In Proc. European Conference Computer Vision (ECCV), pp. 549-566. Springer, 2022.
Sehyun Hwang, Sohyun Lee, Hoyoung Kim, Minhyeon Oh, Jungseul Ok, and Suha Kwak. Active learning for semantic segmentation with multi-class label query. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
Ajay Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Breaking the interactive bottleneck in multi- class classification with active selection and binary feedback. In Proc. IEEE/CVI Conference on Computer Vision and Pattern Recognition (CVPR), 2010.
Xin Kang, Xuefeng Shi, Yunong Wu, and Fuji Ren. Active learning with complementary sampling for instructing class- biased multi-label text emotion classification, IEEE Transactions on Affective Computing, 14(1):523 536, 2020.
Hoyoung Kim, Sehyun Hwang, Suha Kwak, and Jungseul Ok. Active label correction for semantic segmen- tation with foundation models. In Proc. International Conference on Machine Learning (ICML), 2024.
Yoon- Kim, Youngjae Cho, JoonHo Jang, Byeonghu Na, Yeongmin Kim, Kyungwoo Song, Wanmo Kang, and II-Chul Moon. Saal: sharpness-aware active learning. In Proc. International Conference on Machine Learning (ICML), 2023.
Youngdong Kim, Junho Yim, Juseung Yun, and Junmo Kim. Niul: Negative learning for noisy labels. In Proceedings of the IEEE/CVE international conference on computer vision (CVPR), pp. 101-110, 2019.
Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan- Yen Lo, et al. Segment anything. In Proc. IEEE International Conference on Computer Vision (ICCV), pp. 4015-4026, 2023.
Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. Proc. Newral Information Processing Systems (NeurIPS), 32, 2019.
Suraj Kothawade, Nathan Beck, Krishnateja Killamsetty, and Rishabh Iyer. Similar: Submodular informa- tion measures based active learning in realistic scenarios. Proc. Neural Information Processing Systems 2021.
(NeurIPS),
15

---

Published in Transactions on Machine Learning Research (08/2025)
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. Journal of Machine Learning Research, (JMLR), 20(65))1-500 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
David D. Lewis. Reuters-21578 text categorization test collection, 1997. URL http://www.davidddeest
Yezheng Liu, Zhe Li, Chong Zhou, Yuanchun Jiang, Jianshan Sun, Meng Wang, and Xiangnan He. Generative adversarial active learning for unsupervised outlier detection. IEEE Transactions on Knowledge and Data Engineering, 32(8):1517-1522 2019a.
Yinhan Liu, Myle Out Naman Goyal, Jinglei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint Xrt::1107. 1199, 2019b.
Ily Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proc. International Conference on Learning Represenlations (ICLR), 2019.
Christopher D Manning. An introduction information retrieval. 2009.
Sergio Matiz and Kenneth E. Barner. Conformal prediction based active learning by linear regression opti- mization. Nearocomputing, 388:157- 169117776661111111 2020.
Kun-Peng Ning, Xun Zhao, Yu Li, and Sheng-Jun Huang. Active learning for open-set annotation. In Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 41-49, 2022.
OpenAL. Gpt-4 technical report. arXiv preprint orXiv:2303.0877. 2023.
Natalia Ostapuk, Jie Yang, and Philippe Cudré- Activelink: deep active learning for link prediction in knowledge graphs. In The World Wide Web Conference (WWW), 2019.
Dongmin Park, Yooju Shin, Jihwan Bang, Youngjun Lee, Hwanjun Song, and Jae-Gil Lee. Meta-query-net: Resolving innitt-informativennss dilemmaa in open-set active learning. Proc. Newral Information Processing Systems (NewrIPS), 35:31416 31429, 2022.
Buyue Qian, Xiang Wang, Fei Wang, Hongfei Li, Jieping Ye, and Ian Davidson. Active learning from relative queries. In Proc. International Joint Conference on Artificial Intelligence (IJCAI), 2013.
Chongyu Qu, Tiezheng Zhang, Hualin Qiao, Yucheng Tang, Alan L Yuille, Zongwei Zhou, et al. Abdomonatlas-Sl:: Annotating 8,000 et volumes for milti-organ segmentation in three weeks. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkinn Jack Clark, et al. Learning transferable visual models from natural language supervision. In Proc. International Conference on Machine Learning (ICML), pp. 8748- 8763. PMLR, 2021.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Proc. Neural Information Processing Systems (NewrIPS), 33:3581-3555 -5911, 2020.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. Tn Proc. International Conference Learning Representations (ICLR), 2018.
Burr Settles. Active learning literature survey. Computer Sciences Technical Report 1648, University of Wisconsin-Maadison 2009.
Burr Settles, Mark Craven, and Lewis Friedland. Active learning with real annotation costs. In Proceedings of the NIPS workshop on cost-sensilive learning, volume 1, 2008
16

---

Published in Transactions on Machine Learning Research (08/2025)
Glenn Shafer and Vladimir Vovk. A tutorial conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. In Proc. IEEE/CVP International Conference Computer Vision (TCCV), 2019.
Mingxing Tan and Quoe Te. Ffficientnet: Rethinking model scaling for convolutional neural networks. Tn Proc. International Conference on Machine Learning (ICML), pp. 6105 6114. PMLR, 2019.
Toan Tran, Thanh- Toan Do, Ian Reid, and Gustavo Carneiro. Bayesian generative active deep learning. In International conference on machine learning, pp. 6295-6304. PMLR, 2019.
Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-learningg applications of algorithmic randomness. In Proc. International Conference on Machine Learning (ICML), ICML '99, pp. 444-453, San Francisco, CA, USA, 1999. Morgan Kaulmann Publishers Inc. ISBN 1558606122.
Byron Wallace, Kevin Small, Carla Brodley, and Thomas A Trikalinos. Who should label what? instance allocation in multiple expert active learning. In Proceedings of the 2011 SIAM international conference on data mining, pp. 176-187. SIAM, 2011.
Di Wang, Jing Zhang, Bo Du, Minqiang Xu, Lin Liu, Dacheng Tao, and Liangpei Zhang. Samrs: Scaling-up remote sensing segmentation dataset with segment anything model. Proc. Neural Information Processing Systems (NeurIPS), 36, 2024.
Jing Wang, Jie Shen, Xiaofei Ma, and Andrew Arnold. Uncertainty-based active learning for reading com- prehension. Transactions on Machine Learning Research (TMLR), 2022. ISSN 2835-8856.
Zengmao Wang, Bo Du, Weiping Tu, Lefei Zhang, and Dacheng Tao. Incorporating distribution matching into uncertainty for multiple kernel active learning. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2019.
Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. ACM Transactions on Knowledge Discovery from Data (TKDD), 2015.
Ming-Kun Xie and Sheng-Jun Huang. Multi-label learning with pairwise relovance ordering. Proc. Neural Information Processing Systems (NeurIPS), 34:23545 23556, 2021.
Yang Yang, Yuxuan Zhang, Xin Song, and Yi Xu. Not all -uttof-distributtin data are harmful to open-set active learning. Proc. Neural Information Processing Systems (NeurIPS), 36, 2024.
Ofer Yehuda, Avihu Dekel, Guy Hacohen, and Daphna Weinshall. Active learning through covering lens. Proc. Neural Information Processing Systems (NeurIPS), 00222344-22666 2022.
Guoxian Yu, Xia Chen, Carlotta Domeniconi, Jun Wang, Zhao Li, Zili Zhang, and Xiangliang Zhang. Cmal: Cost-cffective multi-label active lcarning by querying subexamples. JEEE Transactions on Knowledge and Dala Engineering (TKDE), 34(5):2091 2105, 2020.
Sergey Zagoruyko. Wide residual networks. arXiv preprint arXiv:1605.07144, 2016.
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer Scaling vision transformers. In Proc. IEEE Conference Compuler Vision and Pallern Recognation (CVPR), pp. 12104 12113, 2022.
Hongyi Zhang, Moustapha Cissc, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In Proc. International Conference on Learning Representations (ICLR), 2018.
Jifan Zhang, Yifang Chen, Gregory Canal, Arnav Mohanty Das, Ganlavya Bhatt, Stephen Mussmann, Yinglun Zhu, Jeff Bilmes, Simon Shaolei Du, Kevin Jamieson, and Robert D Nowak. Labelbench: A comprehensive framework for benchmarking adaptive label-officient learning. Journal of Data-centric Ma- Reproducibility
chine Learning Research, 2024. URL http:///ppppmoooooreeee//o/ro/oo Certification.
17

---

Published in Transactions on Machine Learning Research (08/2025)
Yuhang Zhang, Xiaopeng Zhang, Lingxi Xie, Jie Li, Robert C Qiu, Hengtong Hu, and Qi Tian. Oie-bit active query with contrastive pairs. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9697 9705, 2022.
18

---

Published in Transactions on Machine Learning Research (08/2025)
Appendix
A Details of User Study
Q, Select the class that corresponds to the image.
plain
poppy
rabbit
rose
(a) Questionnaire with four candidates (k = 4)
(b) Example queries in CIFAR-100
Figure Questionnaire and examples used in the user study. (a) Each question contains an instruction, image, and set of candidates. In this case, the candidate set size is 4. (b) We utilize 20 images from CIFAR-100, each with resolution of 128 128 pixels.
We conduct user study to examine how the size of a candidate set, k in Sec. 3.1 affects the annotation time in practice. Figure g presents examples of the questionnaire and all images used in facilitate casy comparison with the thcoretical costs (Hu et al. 2018), we set the candidate set sizes to 4, 8, 16, and 32. To be specific about Figure g we use CIFAR 100 images resized to 128 x 128 using super resolution to enhance visibility for annotators. We first randomly select 20 classes in CIFAR-100 and choose one image per class to organize the questionnaires. For small-sized candidate sets, we ensure the inclusion of the ground truth by randomly trimming around it when generating the candidate sets.
study. To
We divide 44 annotators into four groups of 11 for each candidate set size to perform labeling tasks. To account for potential outliers, exclude the results of the annotators whose time taken deviates the most from the average lime in each group. Table 4 shows that as the candidate set size increases, the time per query increases and the accuracy decreases. In addition, on the right side of Table 4 the comparison between the experimental costs and theoretical costs reveals a significant correlation of 0.97.
Table User study for different sizes of candidate set query.
k
Total time (s)
Time per query (s)
Accuracy (%)
Experimental
Theoretical
69.4
3.47 +0.09
100.0+t.0
2.0
2
8
91.54277.
5.20
98.5 98.543.2
2.6
3
116.9429.6
6.94+1.48
99.5+1.5
3.4
32
166.9430.8
8.35
95.545.2
4.8
5
Shttps://wwe http:////ww./...aa.////////////a veserreiieeeiliaaaaiiseeeeeeeeee
19

---

Published in Transactions on Machine Learning Research (08/2025)
B Implementation Details and Configuration
Table presents the configuration of our main experiments for each dataset. In all experiments, we fixed the per-round budget, which limits the number of annotated instances per active learning (AL) round. Given this budget constraint, we compute the labeling cost for each AL round to assess labeling efficiency. The batch size for CIFAR-10, CIFAR-100, and ImageNet64x644 was determined image ensure the stability of the training. We trained our classification model on CIFAR-10 and CIFAR- 100 using NVIDIA RTX 3090 and on Image using 4 NVIDIA A100 GPUs in parallel. The training requires about 5 GPU hours for CIEAR-10 10 and CIFAR-100, and about 1.5 GPU days for ImageNet64x64.
be 128. We normalized the input
Table 5: Detailed dataset and budget configuration for the proposed scenario.
Dataset
L
logg L
Size
Cost of full label
# of rounds
Per-round budget
CIFAR-10
10
3.322
50K
166. 1K
10
6K
CIFAR-100
100
6.644
50K
332.2K
6K
ImageNet661x61
1000
9.966
1.2M
12.7M
16
60K
C Additional Clarification on Candidate Set Construction
The detailed procedure of computing (()) in Eq. (4) We begin with computing the collection of conformal scores for the calibration dataset Deal- For each data point (x,,)) M)) Deal, the conformal score is defined as:
= 1 - (o x,), for =1==1 1,2, ... Meal
(9)
where neal (Deall Using these scores, we define the empirical distribution function (s),), which measures the proportion of scores less than equal to given value Formally, Fs(() is expressed as:
neal
(s)
Σ [ss
(10)
neal
where 1[-] is an indicator function. The (1 - a) empirical quantile is then defined as the smallest score such that the proportion of scores satisfying < 8 is at least (1 a). Mathernttcally, this is given as minge(naa (s,(s,) 2 1 - -a,, where [Meil] = 21, .. Real).
((a): = min
(11)
Note that Eq.
is equivalent to Eq.
D Impact of Cost-efficient Sampling across Sampling Strategies
compare different sampling strategies when combined with their cost-efficient variants on CIFAR-100 Notably, the performance of cost-efficient sampling consistently improves when combined with range of acquisition functions. These results show that our cost-efficient acquisition method (Eq.. (8) performs consistently well when paired with four diverse acquisition strategies: entropy sampling, BADGE (Ash et al. 2020), ProbCover (Yehuda et al., 2022) and SAAL (Kim et al. 2023). This suggests that it can readily combined with a broad range of acquisition functions beyond those evaluated in our experiments.
In Figure 10
E Discussion on Handling Outliers and Anomalous Data Points
Dealing with out-of-distribution (OOD) data points showing high uncertainty scores has been chronic issue in active learning and may affect the efficiency of candidate set query (CSQ). Recent open-set active
20

---

Published in Transactions on Machine Learning Research (08/2025)
70
70
65
65
Accuracy (56
60
Accuracy (%6
60
55
55
50
45
45
40
40
20
40
60
80
100
20
40
60
80
100
Relative labeling cost (%)
Relative labeling cust (%)
70
70
65
Accuracy (%)
60
Accuracy (%)
60
55
55
50
50
45
Ci--PicCCowr Cont(ProCowwr)
CD+SAAL
CSQ CoHISAAL)
40
40
20
40
60
80
100
20
40
60
80
100
Relative labeling cost (%)
Relative labeling cost (%)
Figure 10: Comparison of different sampling methods and their cost-sampling variants CIFAR-100. Each
subplot shows triple of corresponding methods.
learning approaches (Du et al. 2021 Kothawade et al., 2021 Ning al. 2022 Park et al. 2022 Yang et al.
2024) tackle this by filtering out OOD samples during active sampling using an OOD classifier. Our CSQ Iramework integrates seamlessly with these methods, focusing labeling in-distribution (ID) samples prevent cost inefficiency.
However, as OOD classifiers are not flawless, some OOD samples may still be selected. One advantage of our method is its ability to leverage the calibration set to capture information about such mixed OOD samples. This enables adjustments such as increasing the OOD classifier threshold to exclude more OOD-like data or incorporating the OOD ratio into the alpha optimization process Eq. 7 Optimizing the combination of OOD and ID classifier scores within the calibration set or designing better OOD-aware queries presents promising future research directions.
21

---

Published in Transactions on Machine Learning Research (08/2025)
0-05
d=
d-12
2-0
55
70
93
50
Accuracy (%)
91
Accuracy (%)
65
Accuracy (%)
45
89
10
87
55
50
30
25
Relative labeling cost (%)
Relative labeling cost (%)
Relative labeling cost (%)
(a) CIFAR-10
(b) CIFAR-I00
(c) ImageNet6dx61
Figure 11: Accuracy (%) versus relative labeling cost (%) with varying hyperparameter in Eq. across AL rounds, evaluated on CIFAR-10, CIFAR-100 and ImageNeu64x64 with CostEnn)(E We set 0.3 for all datasets in our main experiments.
1.11
70
70
Accuracy (%)
Aocuracy (%)
60
20
30
40 50
60
20
30
10
50
Relative labeling cost (%)
Relative labeling cost (%)
(a) CSQ Cost(Ent)
(b) CSQ+ Cost-BADG)
Figure 12: Accuracy (%) versus relative labeling cost (%) with varying hyperparameter d in Eq. across AL rounds on C00AR-100. (a) cost-efficient sampling combined with entropy sampling (CSQ+ (r55++ost(Ent).. (b)
cost-efficient sampling combined with BADGE (CSQ=Cos(BAADGE).
F Impact of Informativeness-- Cost Balancing Hyperparameter d
The hyperparameter in our acquisition function (Eq. 8 balances the trade-off between labeling cost and the informativeness of sample. We provide comprehensive analysis showing the trend of performance in accuracy with varying d values over AL rounds across datascts (Figure 11 and sampling stratogics (Figure 12 , and additionally demonstrate the results in the language domain (Figure 13
For CIFAR-10 (Figure Ila), both accuracy and labeling cost remain robust to the change of d, varying only 0.5%p in accuracy. For CIFAR-100 and ImageNet64x64 (Figure 11b and Figure [1c] combined with entropy-based sampling, the overall performance improves as d decreases. On the other hand, as shown in Figure 12 and Figure [3 the accuracy and labeling cost exhibit no clear correlation with Nevertheless, the performance and cost-efficiency remain insensitive across different datasets, domains, and sampling strategics. This suggests that be easily selected without extensive tuning. We fix d 0.3 in all main experiments to demonstrate the robustness of method without dataset-specific adjustment.
22

---

Published in Transactions on Machine Learning Research (08/2025)
d 0.4
2.0
94
70
Accuracy (96)
Macru-Pi (%)
92
50
90
15
20
25
30
35
15
20
25
30
35
Relative labeling cost (%)
Relative labeling cost (%)
(a) Accuracy
(b) Macro-F1
Figure 13: (a) Accuracy (%) and (b) Macro-F1 (%) versus relative labeling cost (%) with varying hyperpa- rameter d in Eq. (8) across AL rounds on R52 with CSQ Cost(Ent).
RRnd
CSQ Rond
CSQ Coot(Ent)
94
(96
(%6
90
90
88
88
86
20
40
60
80
100
20
40
60
80
100
Relative labeling cost (%)
Relative labeling cost (%)
(a) TF-IDF
(b) RoBERTa-Large
Figure 14: Comparison between conventional query (CQ) and candidate set query (CSQ) with random sam pling (Rand), entropy sampling (Ent), and cost-efficient entropy sampling (Cost(Ent)) text classification task with R52 dataset. We adopt (a) TF-IDF (Manning, 2009) and (b) RoBERTa-Large (Lin et al.] 2019b)
as feature extractors. We report the results as Accuracy (%) versus relative labeling cost (%). CSQ ap- proaches (blue lines) consistently outperform the CQ baselines (red lines) by a significant margin across various budgets and acquisition functions.
G Experiments in Language Domain
Datasct. The R52 datasct [Lewis] 1997) is subset of the Routcrs-21578 Lewis 1997p news collection, specifically curated for text classification tasks. It comprises documents categorized into 52 distinct classes, with total of 9,130 documents. The dataset is divided into 6,560 training documents and 2,570 testing documents. Each document is labeled with single category, and the categorics are selected to ensure that each has at least one document in both the training and testing sets. This structure makes the R52 dataset particularly suitable for evaluating text classification models.
Implementation details. We adopt an SVM classifier (Cortes 1995 with a sigmoid kernel, evaluating with feature extractors: TF-IDF (Manning 2009) and RoBERTa-Lare (Liu et al.) 2019b). We conduct 11 AL rounds of consecutive data sampling and model updates, where the per-round budget is 600. The
23

---

Published in Transactions on Machine Learning Research (08/2025)
CQ+5m (5Q+Coe(Fan)
70
65
65
Accuracy (%)
Accuracy (96)
60
53
55
50
50
45
100
Relative labeling cust (%)
Relative labeling cost (%)
0.05
(b) 0.1
Figure 15: Comparison between conventional query (CQ) and candidate set query (CSQ) with entropy sam-
pling (Ent) and the proposed acquisition function with entropy measure (Cost(Ent) on CIFAR-100 with label noise across AL rounds with varying noise level: (a) Noise rate of 0.05. (b) Noise rate of 0.1. The proposed
CSQ+ Cost(Ent) consistently outperforms CSQ+ Ent across various AL rounds and noise rates.
hyperparameter d for our acquisition function is set to 1.2. In the initial round, randomly sample 300 samples. In each round, the model is evaluated based on two factors: accuracy (%) and relative labeling cost. (%).
Figure 14 presents a comparison of candidate set query (CSQ) and conventional query (CQ) on the text classification dataset (R52) with random sampling (Rand), entropy sampling (Ent), and our acquisition func- tion with entropy measure (Cost(Ent), Eq. (8) across AL rounds, CSQ approaches consistently outperform the CQ basclines by significant margin across various budgets and acquisition functions. Especially round 10 with the TF-IDF feature extractor, RSQ+ reduces labeling cost. by 65.6%p compared to its conventional query baseline. The result demonstrates that the proposed CSQ framework generalizes to the text classification domain.
H Experiments on Real-World Datasets
Experiment on datasets containing label noise. evaluate the candidate set query (CSQ) framework on CIFAR-100 with noisy labels, simulating a scenario where human annotators misclassify images into random classes with a noise rate This is modeled using uniform label noise (Frénay & Verleysen 2013) with set to 0.05 and 0.1. Note that this scenario is unfavorable for CSQ, reject the actual true label even if the candidate set includes it. Figure 15 compares CSQ and conventional query (CQ) on CIFAR-100 with noisy labels using entropy sampling (Ent) and our acquisition function with entropy measure (Cost(Ent)) across 2, 6, and 9 rounds.
misclassifying annotator would
Despite the disadvantageous scenario, our method (CSQ+Cost(Ent)) reduces labeling cost compared to the bascline (CQ+ + Ent) across varying AL rounds and noise rates. At round 9, CSQ+ Cost(Ent) achieves cost reductions of 33.4%p and 27.4%p noise rates of 0.05 and 0.1, respectively. It also consistently oulperforms the baseline in terms of accuracy per labeling cost, demonstrating the robustness of CSQ, Additionally, CSQ has the potential to reduce label noise, narrowing the candidate set can lead to more precise annotations. Our user study (Table D shows that reducing candidate set size improves annotation accuracy, suggesting that CSQ can further enhance performance by reducing label noise.
Experiment on datascts containing class imbalances. Figure 16 compares candidate set query (CSQ) and conventional query (CQ) on CIFAR-100-LT (Cui et al., 2019 a class-imbalanced version of CIFAR- 100, using entropy sampling (Ent), and our acquisition function with entropy measure (Cost(Ent)) across AT
24

---

Published in Transactions on Machine Learning Research (08/2025)
CQ+Em
CSQ+Con(Eat)
55
65
50
60
Accuracy (%)
Accuracy (%)
Accuracy
55
45
50
40
20
30
40
50
60
20
25
30
35
40 45
15
20
25
30
35
40
Relative labeling cost (%6
Relative labeling cost (%)
Relative labeling cost (%)
(a) p
(b) p p=
(c) p =
Figure 16: Comparison between conventional query (CQ) and candidate set query (CSQ) with entropy sam-
pling (Ent) and the proposed acquisition function with entropy mcasure (Cost(Ent) on CIFAR-100-LT, a variant of CIFAR-100 with class imbalance, across AL rounds with varying imbalance level: (a) Imbalance ratio of 3. (b) Imbalance ratio of 6. (c) Imbalance ratio of 10. The proposed approach (CSQ+Cos((En)) consistently outperforms the bascline (CSQ+Ent) across various AL rounds and noise rates. Note that the maximum AL rounds vary with the imbalance ratio due to dalaset size, with maximum of rounds for ratios of 3 and 6, and 6 rounds for ratio of 10.
rounds. The experiments use imbalance ratios (i.e., ratios between the largest and smallest class sizes) of 3, 6, and 10. Note that the maximum AL rounds vary with the imbalance ratio due to dataset size, with a maximum of 4 rounds for ratios of 3 and 6, and 6 rounds for a ratio of 10.
The result shows that our method (CSQ + Cost(Ent)) reduces labeling cost compared to the baselines (CQ+Ent by significant margins across varying AL rounds and imbalance ratios. Specifically, at round 4, CSQ+ Cost(En)) achieves cost reductions of 31.1%p and 29. 29.2%p at inbalance ratios of 6 and 10, respectively. In terms of ac- curacy per labeling cost, CSQ+ Cost(Ent) consistently outperforms the baseline, demonstrating the robustness of the CSQ framework in class-imballe imbalanced scenarios.
Experiments on Products-100 10K
To evaluate the scalability of CSQ with respect to the number of classes, conduct experiments the Products-10K (Bai et al. 2020) dataset, which contains 10K classes. We perform 6 AT rounds of consecutive data sampling and model updates. For the first round, 30K images are used to construct the initial training dataset, and the per-round budget is set to 22K. The calibration dataset is built by randomly selecting 5K images at each round.
We compare CSQ combined with cost-cfficient entropy sampling (CSQ Cost(Entt) and the conventional query baseline (CQ-Ent) evaluated using three model architectures: EfficientNet-B33 (Tan & Le 2019). ResNet50 (He et al. 2016), and VIT-S/16 (Dosovitskiy pretrained on ImageNet- (Deng et al. 2009) to further assess the compatibility of CSQ with advanced pre-trained models, while Efficient B3 is trained from scratch.
al. 2021). ResNet50 and VIT-S/16 are DINO-
As shown in Figure [7] CSQ consistently achieves higher performance per unit cost compared to the CQ bascline across model architectures and training strategics. In particular, for EfficientNet-BB. CSQ roduces labeling cost by 27%p without any performance degradation, demonstrating that the proposed method scales effectively to scenarios with huge number of classes.
25

---

Published in Transactions on Machine Learning Research (08/2025)
CQ+ Coe
50
40
Accuracy (%)
40
Accuracy
30
Accuracy
20
30
10
20
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
Relative labeling cost (%)
Relative labeling cost (%)
Relative labeling cost (%)
(a) EfficientNet-B3**
(b) ResNet50t
(c) VIT-S/16t
Figure 17: Comparison between conventional query combined with entropy sampling (CQ+Ent) and candi- date set query combined with cost-efficient entropy sampling (CSQ + Cost(Ent)) on Products-10K (Bai et al. 2020). We use (a) EfficientNet-BB B3 (Tan & Le 2019). (b) ResNet50 (He et al. 2016) model, and (c) ViT- S/16 Dosovviskky et al. 2021 as backbones. * and indicate the models are trained from scratch and respectively. Fine-tuned models are evaluated on
DINO-pretrainees on ImageNet-11K (Dng et al, 2009 Products-10ks via linear probing.
(Zhang
Amaraey (%)
10
20
30
40
50
60
70
80
90
100
Relative labeling cost (%)
Figure 18: Comparison of conventional query (CQ), top-1 query (Top1) Zhang et al. 2022). and candidate set query (CSQ) combined with entropy sampling on CTFAR-100. Topl asks the oracle whether the top-1 prediction is the ground-truth class, potentially yielding partial labels. For fair comparison, we employ negative learning loss {Kim al.] 2019) to utilize samples with partial labels. Also, samples with partial labels are sampled with replacement until they get full labels.
J Comparison with Weakly Supervised Baseline
As described in Sec. 3.1 the oracle is prompted with a follow-up query only when the ground-truth label is absent from the candidate set. To assess the elfectiveness of CSQ's two-query design, we compare three types of query strategies: the conventional query (CQ), a weakly supervised baseline (Zhang et al. 2022) that constructs candidate sets solely from top-1 predictions (i.e., pscudo labels) (Top1), and our candidate set query (CSQ). Unlike CSQ, Topl does not issue second query, leaving incorrectly pscudo-labeled samples partial labels, requiring specialized negative learning loss for training.
26

---

Published in Transactions on Machine Learning Research (08/2025)
CSQ+Ent achieves the highest performance among all methods. Despite leveraging partial label learning (Kim et al., 2019), Topl+Ent fails to match CSQ's accuracy, negative learning loss introduces noisy signals in early rounds. Since CSQ produces no partial labels, CsQ+Ent matches the performance of Eq+Ent while improving cost-efficiency. Morcover, since CSQ does not require a specialized loss function, can be seamlessly integrated into a conventional classífication framework.
As shown in Figure 18
CQ+RRad
CQ-Eat
CQ+ProhCowe CSQ+ BoSEB
CQ-RADGE
CSQ+Rard
CSQ+ Cost([nt)
CSQ CostiProsCover)
CSQ Cos(SAAA)
91
92
Accuracy (56)
90
30
40
30
60
80
100
Relative labeling cost (%)
Figure 19: Accuracy (%) versus relative labeling cost (%) CIFAR-10.
CQ Rand RaQd
CQ Ent CSQ++Cuv((En)
CQ BADGE SSQ+Cove(BADCE
CO ProbCover
CQ SAAL
CSQ Pre--Goo//PsSCCmer
CSQACOu((AAAL)
Accuracy (96)
50
45
20
30
40
50
60
70
80
90
100
Relative labeling cost (%)
Figure 20: Accuracy (%) versus relative labeling cost (%) on CIFAR-100.
27


Reviews:
[{"review_id": "DswrheucrX", "reviewer": "Reviewer_FogS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Below, I list the strengths and weaknesses according to their importance, starting with the most important one and ending with the least important one. Thereby, the strengths are rather concisely formulated, serving primarily as confirmation and, unlike the weaknesses, requiring no further discussion. Of course, I will reconsider my perspective of my comments, if I have misunderstood or overlooked any aspect. Looking forward to a constructive discussion!\n\n**Strengths:**\n- The paper addresses a well-known practical problem [1, 2] of designing more efficient queries for active learning.\n- Leveraging conformal predictions for creating candidate subsets of classes is a neat idea to balance the trade-off between small subsets and the high probability of keeping the ground truth class as candidate.\n- The proposed cost model is supported by theoretical insights and a case study with humans as labelers.\n- The experimental evaluation is well designed, very extensive and shows in combination with a detailed ablation study the benefits of the cost-sensitive active learning framework's components.\n- The authors provide code including detailed descriptions improving the reproducibility.\n- The writing and presentation of the paper is very clear.\n\n**Weaknesses:**\n- Although ResNets remain popular, they’re now fairly dated. At the same time, active learning studies are increasingly built on features from pretrained (often self‐supervised) models [3, 4]. ProbCover even adopts this approach, as noted in your code as part of the supplementary material. That raises a natural question: why not use these modern pretrained networks as backbones, either in combination with fine-tuning or linear probing for evaluation? The same logic applies to case study with the text dataset where you used an SVM. Here, large language models could serve as powerful feature extractors. In fact, incorporating such state-of-the-art models typically means you can work with much smaller per-round budgets, since they need far fewer labeled examples to reach convergence.\n- The case study with real participants is a valuable contribution. However, the case study’s protocol in the appendix (see quote) of always including the ground-truth label in each candidate set leaves the investigation open whether omitting the correct label from the sets of candidate classes could irritate them or even bias their decisions.\n> \"For small-sized candidate sets, we ensure the inclusion of the ground truth by randomly trimming around it when generating the candidate sets.\"\n- Your hyperparameter $d$ controlling the influence of the acquisition function is set to $d=0.3$ for all experiments with image data. At the same time this is the smallest and seems to be the best value according to your ablation study in Figure 11. Therefore, it would be interesting to see what happens for an even smaller value. Moreover, I am confused why and how did you choose $d=1.2$ for the experiments with the text dataset?\n- Your cost model relies only on the subset's size for the class candidates. Your case study confirms that this is a good proxy. Moreover, your conformal predictions automatically penalize too uncertain samples because they will have larger subsets. However, I think a brief discussion (e.g., as part of the related work) regarding the existing literature on more complex cost models for the annotation time would be more transparent regarding potential limitations. For example, there are several resources [2, 5, 6, 7] demonstrating/overviewing the non-negligible effects of sample-wise labeling difficulties and the labeler's behavior.\n\n**References:**\n- [1] B. Settles, ‘‘From theories to queries: Active learning in practice,’’ in Proc. Workshop Active Learn. Exp. Design, Sardinia, Italy, 2011, pp. 1–18\n- [2] Herde, M., Huseljic, D., Sick, B., & Calma, A. (2021). A Survey on Cost Types, Interaction Schemes, and Annotator Performance Models in selection algorithms for active learning in classification. IEEE Access, 9, 166970-166989.\n- [3] Hacohen, G., Dekel, A., & Weinshall, D. (2022, June). Active Learning on a Budget: Opposite Strategies Suit High and Low Budgets. In International Conference on Machine Learning (pp. 8175-8195). PMLR.\n- [4] Gupte, S. R., Aklilu, J., Nirschl, J. J., & Yeung-Levy, S. (2024) Revisiting Active Learning in the Era of Vision Foundation Models. Transactions on Machine Learning Research.\n- [5] B. Settles, M. Craven, and L. Friedland, ‘‘Active learning with real annotation costs,’’ in Proc. NIPS Workshop Cost-Sensitive Learn., Vancouver, CA, Canada, 2008, pp. 1–10.\n- [6] B. C. Wallace, K. Small, C. E. Brodley, and T. A. Trikalinos, ‘‘Who should label what? Instance allocation in multiple expert active learning,’’ in Proc. SIAM Int. Conf. Data Mining, Apr. 2011, pp. 176–187.\n- [7] Arora, S., Nyberg, E., & Rose, C. (2009). Estimating annotation cost for active learning in a multi-annotator environment. In Proceedings of the NAACL HLT 2009 Workshop on Active Learning for Natural Language Processing (pp. 18-26).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper deals with **pool-based active learning**, where the objective is to maximize the performance of a machine learning model, while minimizing the labeling costs for collecting the associated training dataset. Therefore, existing active learning strategies aim to select unlabeled samples whose labeling and inclusion into the labeled training set result in the largest performance gains for the machine learning model. Typically, these strategies assume that a selected sample is presented to a labeler whose task is to decide on the ground truth class from the list of candidate classes. This decision often gets more time-intensive (and therefore costly), when there are many candidate classes. The main **contributions** of the paper to resolve this issue are the following ones:\n\n- Candidate set query as an alternative query type is proposed, which leverages conformal predictions of the machine learning model to propose only small subsets of candidate classes per sample. \n- A well-motivated labeling cost model accounts for the size of each subset of candidate classes and lays the foundation for a new cost-sensitive active learning framework, which can be combined with existing active learning strategies providing sample-wise scores.\n- Extensive experimental results across varying settings, e.g., standard image and text classification, imbalanced classification, and classification with uniform label noise, demonstrate the benefit of this framework for cost-sensitive active learning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would appreciate it if the authors could address the abovementioned weaknesses and resolve the following minor remarks.\n\n**Minor Remarks:** \n- Resolve Inconsistent capitalization of \"Initial\" in \"Require: ...\" of Algorithm 1.\n- Update arXiv references of LabelBench to its formal publication at DMLR.\n- Check consistent venue referencing, e.g., inconsistent usage of \"(NeurIPS)\".", "broader_impact_concerns": "Humans were involved in a case study for labeling. However, the number of images to be labeled seemed small and their content probably unproblematic.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "S3baRC03lK", "reviewer": "Reviewer_jH6f", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strengths:\nThe active learning problem is important. The authors proposed to use cost as a new way to evaluate the importance of samples that would be annotated. It is novel. The motivation of candidate set is to improve the performance of annotator. \n\nWeakness:\nMy primary concern lies in the relationship between the estimated cost and the actual number of labeled samples. After all, the goal of active learning is to minimize the number of labeled samples needed to achieve a model with the desired performance.\n\nAlso, it remains unclear how the performance of the trained model is guaranteed. The 1-\\alpha^* probability only ensures that the annotator is provided with a candidate set containing the ground-truth class.\n\nHere is also a related paper about active learning which authors may consider including in the related works. Uncertainty-Based Active Learning for Reading Comprehension. Wang, Jing and Shen, Jie and Ma, Xiaofei and Arnold, Andrew. TMLR, 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors proposed a cost-efficient active learning framework. The algorithm begins by estimating the labeling cost for each unlabeled sample, and then computes an acquisition score. This score is determined by the ratio of the estimated information gain to the estimated labeling cost. The information gain is quantified using established methods, such as entropy, BADGE, or SAAL. The expected cost calculation depends on whether the correct label is included in the candidate set or not. Specifically, the annotator is presented with a label candidate set, where the ground-truth class is included with probability 1-\\alpha^*. This candidate set is constructed based on conformal prediction [Romano et al., 2020]. The experiments in Figure 1 shows that with proposed framework, existing methods achieve high accuracy with much less cost.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The discussion between the cost and the actual number of labeled data is required. To validate the effectiveness of cost evaluation criteria and the candidate set, the convincing discussion or experiments are required.", "broader_impact_concerns": "no", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kovaShRp7C", "reviewer": "Reviewer_opMR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1.\tThe CSQ framework introduces a practical method to reduce annotator workload by narrowing down the class options.\n2.\tUtilizing conformal prediction allows the system to adaptively generate candidate sets that balance reliability and size, enhancing the efficiency of the annotation process.\n\n# Weaknesses\n1.\tThe paper does not extensively discuss how annotation errors within the candidate sets might impact the model's performance or how the system handles such errors. For example, in the case when the Oracle model still has a chance to give the wrong candidates, how would the proposed method perform?\n2.\tThe framework assumes the availability of an oracle to validate the candidate sets, which may not always be feasible in real-world scenarios, especially where expert annotators are scarce.\n3.\tWhile the method is tested on datasets like ImageNet64x64, the scalability, and effectiveness of CSQ in scenarios with an even larger number of classes remain unaddressed.\n4.\tThe paper could benefit from a more comprehensive comparison with other active learning strategies, particularly those that also aim to reduce labeling costs or utilize weak supervision.\n5.\tThe absence of publicly available code or detailed implementation details may hinder reproducibility and adoption by the broader research community.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work presents CSQ, which seeks to minimize labeling costs by presenting annotators with a subset of likely classes rather than the full set. By leveraging conformal prediction, the model dynamically generates small, reliable candidate sets that adapt over successive AL rounds. An acquisition function is introduced to prioritize data points that offer high information gain at lower costs. Empirical evaluations on datasets such as CIFAR-10, CIFAR-100, and ImageNet64x64 demonstrate the effectiveness and scalability of the framework.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)