Cost-aware LLM-based Online Dataset Annotation

Dear Reviewer,

Thank you for the comments. Our responses to the reviewer's questions are below.

Q1: Lemma 2.1 can be extended to remove the conditional-independence assumption using Bahadur’s model (R.R. Bahadur, “On classification based on responses to n dichotomous items,” 1961) characterizes the joint distribution of $n$ binary variables using their marginal probabilities $p_i$, second-order dependence terms known as Bahadur parameters, and higher-order interaction terms. This framework allows the computation of majority vote confidence by summing the probabilities of all outcomes where the majority label is correct. However, the lack of a closed-form solution and the rapid growth in computational complexity with increasing $n$ limit its practical applicability. We will include a note on this in the discussion of Lemma 2.1 in the final version of the paper.

Due to this computational intractability, we implemented a practical Monte Carlo simulation approach to evaluate majority vote confidence given LLM accuracies and their correlations. Using a Gaussian copula, we generate $m$ binary outcomes (correct/incorrect) for each LLM that capture both the marginal accuracies and correlations. From these simulated outcomes, we compute $m$ majority vote results weighted by the LLM weights. Average accuracy over these instances provides an empirical confidence estimate for the majority voting scheme.

Applying this method on the MMLU dataset with CaMVo ($\delta=0.96$, $k_{\min}=1$) yields an accuracy of 86.96% at a cost of 3.07, exceeding the target accuracy of 84.65%. For comparison, the original CaMVo results are 87.98% accuracy at 4.74 cost ($\delta=0.96$), and 86.82% accuracy at 2.76 cost ($\delta=0.95$). On the IMDB dataset, the simulation with $\delta=0.99$ and $k_{\min}=1$ produces 95.09% accuracy at a cost of 0.83, surpassing the target accuracy of 94.66%. The original CaMVo results are 95.10% accuracy at 1.09 cost ($\delta=0.99$), and 94.69% accuracy at 0.34 cost ($\delta=0.985$).

These results indicate that incorporating the copula-based simulation does not significantly improve performance on MMLU and yields a modest cost improvement on IMDB, where LLM outputs exhibit higher correlation. We attribute this to two factors: (1) LinUCB’s use of input embedding vectors to predict LLM confidences already implicitly captures correlations among LLM outputs conditioned on the input context, and (2) estimation errors in the correlation matrix reduce the potential gains from explicitly modeling correlations.

We plan to extend this study across all tested $\delta$ and $k_{\min}$ values in our simulations and include these results in the final version of the paper.

Q2: Our method can be naturally extended beyond classification tasks in several ways. For regression, LLM outputs can be aggregated via a weighted average or median, with weights updated based on how closely each LLM’s output aligns with the aggregate. For ranking tasks, each LLM can assign scores to items, and a weighted combination of these scores would produce a final ranking; weights can then be adjusted according to agreement of the LLM's ranking generated from its scores with the aggregated ranking. These extensions involve only minor modifications to the aggregation and weight update steps, making them straightforward to integrate into our existing framework. We will highlight these as directions for future work in the final version of the paper.

Dear Reviewer,

Thank you for the comments. Our responses to the reviewer's comments are below.

Responses to Questions:

Q1: In selecting the individual models, we prioritized those commonly used in related work while also aiming to ensure diversity in both model architecture and per-token cost. Since our primary objective is cost optimization, it is important to span a wide range of cost levels to enable meaningful trade-offs.

Additionally, we included different versions of similar LLMs with varying parameter sizes (e.g., llama-3.1 and llama-3.3) to allow CaMVo to learn cost-aware selection strategies. The intent is to allow CaMVo to favor cheaper, smaller models on simpler tasks, and to choose the larger, more expensive models when the input task is more complex.

Q2: On the MMLU dataset, more than 20% of the LLM responses were incorrectly formatted. For example, when the expected output was the answer choice ‘A’, common variations included responses like “A) 5”, “5”, “The answer is A”, or full explanations preceding the answer. Similarly, on the IMDB dataset, LLMs frequently generated summaries of user comments before stating their classification decision.

To handle these inconsistencies, we post-processed the outputs using keyword matching and other simple heuristics to extract the intended answer. In fewer than 2% of cases, the LLMs failed to produce a usable response (i.e. by answering a question in the movie review in the IMDB dataset or providing an answer that is not in the answer choices). In such cases, we were able to obtain valid responses by requerying the LLM.

Q3: In practice, the confidence threshold can be set to reflect a desired target accuracy. If no specific accuracy requirement is given, the threshold can instead be adapted dynamically to meet a target cost budget or tuned over time as feedback on the output labels becomes available. This flexibility allows the method to operate under varying application constraints, whether accuracy-driven, cost-driven, or feedback-guided.

Q4: Yes, there is a growing body of work showing that LLMs can approximate, and in some cases even surpass human annotators across a wide range of tasks, including the classification tasks considered in our work. For example, Gilardi et al. (“ChatGPT Outperforms Crowd-Workers for Text-Annotation Tasks”) demonstrate that LLMs can not only match but often exceed the performance of crowd-sourced human annotations.

Q5: Since CaMVo is designed for online use, low-latency embedding generation is crucial. We selected SBERT over BERT because SBERT is significantly faster for producing sentence embeddings. To inform our choice in choosing an SBERT model, we referred to the accuracy and speed trade-off comparisons provided on the official Sentence Transformers (SBERT) library website. We chose the all-MiniLM-L6-v2 model as it offers a strong balance between efficiency and performance, making it well-suited for our setting.

Q6: In the current implementation of CaMVo, we query all LLMs when no subset achieves confidence above the threshold $\delta$. For example, with $\delta=0.96$ and $k_{\min}=1$ on the MMLU dataset, this occurs an average of 597 times across 14,042 data instances. To extend this mechanism, an additional threshold $\delta_{\text{human}} < \delta$ can be introduced: if the highest subset confidence falls between $\delta_{\text{human}}$ and $\delta$, we query all LLMs; if it falls below $\delta_{\text{human}}$, the instance can be deferred to a human annotator. This extension provides a principled way to incorporate human in the loop annotations for low-confidence labels.

Responses to Weaknesses:

W1: Please see our response to the limitations section.

W2: We will further extend our simulation results to an additional dataset and include the results in the final version of the paper, and we have conducted the following synthetic experiment to analyze the sensitivity of our method to correlated LLM outputs, and will also include its results in the final version of the paper. Using the true accuracies of the LLMs, we apply the Gaussian copula approach to generate synthetic labels that preserve the individual accuracies while introducing controlled correlations via a specified correlation matrix. The diagonal entries are set to 1, and off-diagonal entries are set to a shared correlation coefficient $C_i$, which we vary across experiments. The results from these experiments show that while CaMVo’s performance declines with increasing correlation, the performance of majority voting also degrades. Importantly, CaMVo maintains its target accuracy except under very high correlation levels. See our response W5 to Reviewer fBz7 for additional details.

W3: We will include additional evaluation metrics such as precision, recall, and F1 score in the final version of the paper to provide a more comprehensive assessment of performance.

W4: Please refer to our response Q3.

Responses to Limitations

L1: To overcome the assumption of independence, we have implemented a practical Monte Carlo simulation approach to evaluate majority vote confidence given LLM accuracies and their correlations. Using a Gaussian copula, we generate $m$ binary outcomes (correct/incorrect) for each LLM that capture both the marginal accuracies and correlations. From these simulated outcomes, we compute $m$ majority vote results weighted by the LLM weights. Average accuracy over these instances provides an empirical confidence estimate for the majority voting scheme.

Applying this method on the MMLU dataset with CaMVo ($\delta=0.96$, $k_{\min}=1$) yields an accuracy of 86.96% at a cost of 3.07, exceeding the target accuracy of 84.65%. For comparison, the original CaMVo results are 87.98% accuracy at 4.74 cost ($\delta=0.96$), and 86.82% accuracy at 2.76 cost ($\delta=0.95$). On the IMDB dataset, the simulation with $\delta=0.99$ and $k_{\min}=1$ produces 95.09% accuracy at a cost of 0.83, surpassing the target accuracy of 94.66%. The original CaMVo results are 95.10% accuracy at 1.09 cost ($\delta=0.99$), and 94.69% accuracy at 0.34 cost ($\delta=0.985$).

These results indicate that incorporating the copula-based simulation does not significantly improve performance on MMLU and yields a modest cost improvement on IMDB, where LLM outputs exhibit higher correlation. We attribute this to two factors: (1) LinUCB’s use of input embedding vectors to predict LLM confidences already implicitly captures correlations among LLM outputs conditioned on the input context, and (2) estimation errors in the correlation matrix reduce the potential gains from explicitly modeling correlations.

We plan to extend this study across all tested $\delta$ and $k_{\min}$ values in our simulations and include these results in the final version of the paper.

Additionally, Lemma 2.1 can be extended to remove the conditional-independence assumption using Bahadur’s model (R.R. Bahadur, “On classification based on responses to n dichotomous items,” 1961) characterizes the joint distribution of $n$ binary variables using their marginal probabilities $p_i$, second-order dependence terms known as Bahadur parameters, and higher-order interaction terms. This framework allows the computation of majority vote confidence by summing the probabilities of all outcomes where the majority label is correct. However, the lack of a closed-form solution and the rapid growth in computational complexity with increasing $n$ limit its practical applicability. We will include a note on this in the discussion of Lemma 2.1 in the final version of the paper.

Dear Reviewer,

Thank you for the comments. Our responses to the reviewer's comments are below.

Responses to Questions:

Q1: We propose the following implementation strategy to integrate task-specific fine-tuning. Initially, we will start with zero-shot LLMs to label data. As more data is labeled, we can fine-tune the LLMs using the accumulated labels. However, blindly fine-tuning on all generated labels risks incorporating incorrect annotations, which can degrade model performance and lead to error propagation. To mitigate this, we introduce a threshold $\delta_u$ and update the LLMs only with labels whose confidence exceeds $\delta_u$.

Since CaMVo already selects subsets with confidence above a threshold $\delta$, it will not necessarily choose subsets with confidence above $\delta_u$. To enable this, we can use $\delta_u$ as the update threshold for a user-defined fraction of the data. Additionally, as more data is collected, we can recalculate label confidences and include them for fine-tuning once they surpass $\delta_u$. To control cost, fine-tuning can be performed in batches once a sufficient number of high-confidence labels is accumulated.

To account for changes in model behavior due to fine-tuning when estimating model parameters such as empirical accuracy, we can use discounted updates on model parameters, assigning higher weight to recent observations.

Finally, since fine-tuning may increase correlation among LLMs, it may be beneficial to keep the original zero-shot LLMs available for selection in the subset. In such cases, we can introduce a constraint to avoid simultaneously selecting both the fine-tuned and zero-shot versions of the same model, as they are likely to be highly correlated.

Q2: Yes, since the Beta estimator does not model correlations between LLMs, its performance will degrade in regimes with correlated LLM outputs. To overcome this degradation in performance, and also to remove the assumption of independence, we have implemented a practical Monte Carlo simulation approach to evaluate majority vote confidence given LLM accuracies and their correlations. Using a Gaussian copula, we generate $m$ binary outcomes (correct/incorrect) for each LLM that capture both the marginal accuracies and correlations. From these simulated outcomes, we compute $m$ majority vote results weighted by the LLM weights. Average accuracy over these instances provides an empirical confidence estimate for the majority voting scheme.

Applying this method on the MMLU dataset with CaMVo ($\delta=0.96$, $k_{\min}=1$) yields an accuracy of 86.96% at a cost of 3.07, exceeding the target accuracy of 84.65%. For comparison, the original CaMVo results are 87.98% accuracy at 4.74 cost ($\delta=0.96$), and 86.82% accuracy at 2.76 cost ($\delta=0.95$). On the IMDB dataset, the simulation with $\delta=0.99$ and $k_{\min}=1$ produces 95.09% accuracy at a cost of 0.83, surpassing the target accuracy of 94.66%. The original CaMVo results are 95.10% accuracy at 1.09 cost ($\delta=0.99$), and 94.69% accuracy at 0.34 cost ($\delta=0.985$).

These results indicate that incorporating the copula-based simulation does not significantly improve performance on MMLU and yields a modest cost improvement on IMDB, where LLM outputs exhibit higher correlation. We attribute this to two factors: (1) LinUCB’s use of input embedding vectors to predict LLM confidences already implicitly captures correlations among LLM outputs conditioned on the input context, and (2) estimation errors in the correlation matrix reduce the potential gains from explicitly modeling correlations.

We plan to extend this study across all tested $\delta$ and $k_{\min}$ values in our simulations and include these results in the final version of the paper.

Additionally, Lemma 2.1 can be extended to remove the conditional-independence assumption using Bahadur’s model (R.R. Bahadur, “On classification based on responses to n dichotomous items,” 1961) characterizes the joint distribution of $n$ binary variables using their marginal probabilities $p_i$, second-order dependence terms known as Bahadur parameters, and higher-order interaction terms. This framework allows the computation of majority vote confidence by summing the probabilities of all outcomes where the majority label is correct. However, the lack of a closed-form solution and the rapid growth in computational complexity with increasing $n$ limit its practical applicability. We will include a note on this in the discussion of Lemma 2.1 in the final version of the paper.

Responses to Weaknesses:

W1: The NP-hard nature of subset selection is well known in the combinatorial bandits literature (e.g., CUCB, Combinatorial Thompson Sampling), and many algorithms assume access to an oracle (either exact or approximate) that solves the offline combinatorial optimization step.

An exact oracle, which evaluates all possible subsets, has a time complexity of $O(2^K)$ per round. However, for small $K$ (i.e., $K \leq 10$), the number of subsets remains tractable. In our simulations, $K=7$, and we did not observe any meaningful impact on runtime.

For larger $K$, an approximate oracle can be employed to reduce computation at the cost of approximation. In our setting, one such approach is to use Monte Carlo simulations to generate $m$ realizations for each LLM. Given these samples, the confidence of a subset of size $K$ can be estimated in $O(mK)$ time. As we discussed in our response to Q2, this approach can also incorporate LLM correlations using a given correlation matrix, however time complexity will increase to $O(mK^2 + K^3)$. To efficiently search a low-cost subset that satisfies the confidence threshold, a greedy approximation can be used. Starting with all LLMs in the subset, at each step we can remove the highest cost LLM that does not reduce the confidence of the subset below the threshold. This will continue until no more LLMs can be removed. In this method, each iteration will have $O(K)$ comparisons, and in total there will be $O(K)$ iterations. As confidence estimation for one subset is $O(mK)$, in total the runtime will be $O(mK^3)$ for this method. We will add this discussion to the final version of the paper.

W2: Please refer to our response Q2.

Responses to Limitations:

L1: Please refer to our response Q2.

Dear Reviewer,

Thank you for the comments. Our responses to the reviewer's comments are below.

Responses to Weaknesses:

W1: In our paper, we consider a problem setting where a user wished to label a dataset. Without our method, the default approach would be majority voting. Our primary motivation is to reduce the labeling cost by allowing a trade-off with accuracy. Accordingly, the accuracy we define is relative to the accuracy of majority voting, which serves as the baseline for comparison. We acknowledge that this distinction could be more clearly articulated. In the final version, we will revise the terminology to avoid ambiguity. For instance, we will "accuracy" to "relative accuracy" and "target accuracy" to "target relative accuracy". Note that the accuracy values reported in our simulation results correspond to comparisons between the generated labels and the true labels, so the use of "Accuracy" in those contexts remains appropriate.

Regarding the LLM accuracies, the individual model accuracies (used as weights in majority voting) on the MMLU dataset are [0.680,0.848,0.817,0.835,0.856,0.859,0.640], and the final weights learned by the baseline method are [0.728,0.905,0.875,0.893,0.901,0.911,0.689]. As expected, these weights are higher than the original accuracies, since under the baseline method, any LLM that agrees with the majority vote is treated as having produced a correct label—even in cases where all LLMs are jointly incorrect. This inflates the estimated accuracy. Nonetheless, the baseline performs comparably to majority voting because for the majority voting output to be correct, the weights of the correct labels need to exceed the weights of incorrect labels. Even though the weights are not exactly correct, the baseline method learns the correct ordering of the weights (if LLMs are sorted by weight both set of weights produce the same result). With this, the weights of the correct labels can still exceed the weights of incorrect labels, and this helps the baseline method achieve similar results as majority voting. This explains why the baseline method achieves results close to majority voting.

W2: Using a Beta distribution is a standard Bayesian approach for modeling binary outcomes, as it is the conjugate prior to the Bernoulli likelihood. This allows for efficient incremental posterior updates as new binary observations (correct/incorrect labels) are collected. While maximum likelihood estimation (MLE) is the formal method for updating the shape parameters of the Beta distribution based on observed data, it has no closed-form solution. In practice, the method of moments is commonly used as a computationally efficient alternative to approximate the parameter updates.

W3: Since no labeled data is available at the start, early accuracy estimates of the LLMs can be noisy and prone to overfitting. Because subset selection is based on these estimated confidences, early estimation errors can bias the selection process and lead to compounding errors over time. To mitigate this, we use regularization to stabilize the accuracy estimates. We choose Laplace smoothing as the regularizer as Laplace smoothing corresponds to using a uniform prior on the Beta estimator, and hence combines well with the Beta estimator. We use a log(t) term with the Laplace smoothing as compared to a constant term, as the log(t) term does not decay as quickly as the constant term and prevents overfitting in the long run.

We will include the reasoning behind our design choices in the final version of the paper.

W4: While we use the true labels to compute accuracy in our simulations, these labels are not available to the user in the actual problem setting. As a result, the user does not know a priori which LLM performs best, or whether any individual model outperforms majority voting. Crucially, if only a single LLM is queried in each round, its output will be treated as the true label. Since it will always agree with itself, this prevents any meaningful estimation of the true accuracy of the LLM. Hence, to reliably estimate individual LLM accuracies over time, it is necessary to query a subset of LLMs in each round, which incurs a cost. This is a fundamental aspect of the exploration-exploitation trade-off in our framework.

Regarding the cost-accuracy trade-off plots, although individual models are already included in the plots, we agree that their presentation can be improved. In the final version, we will use a distinct color to clearly differentiate individual LLMs for better visual clarity.

W5: We have conducted the following sensitivity study to evaluate the impact of correlated LLM outputs. Using the true accuracies of the LLMs, we generate synthetic labels via a Gaussian copula approach. This method preserves the original accuracies while introducing correlations among the LLMs as specified by a correlation matrix. In this matrix, the diagonal entries representing self-correlation are set to 1, and all off-diagonal entries are set to a parameter $C_i$ that represents the pairwise correlation. We run experiments using these synthetic labels, sweeping $C_i$ across a range of values to analyze how varying correlation strengths affect performance.

The results of this experiment for the MMLU dataset are given below .

As can be seen from the results, although the performance of CaMVo declines as the correlation among LLMs increases, the performance of majority voting also deteriorates similarly. Importantly, CaMVo is able to maintain the target accuracy across all tested correlation levels except at the very high correlation coefficient of $C_i=0.8$, verifying the utility of CaMVo even in correlated regimes.

Currently, we have used a single uniform value for all off-diagonal entries in the cross-correlation matrix. In the final version of the paper, we plan to extend this sensitivity study by exploring varying cross-correlation values across different matrix elements. Additionally, we will extend the experiments to the IMDB dataset and conduct experiments with a broader range of $\delta$ values to provide a more comprehensive analysis.

Responses to Questions:

We have addressed the reviewer’s questions as part of our responses to the weaknesses.