Which Examples to Annotate for In-Context Learning? Towards Effective and Efficient Selection

Q4: Does the uncertain with respect to one example equal that the LLM can learn it accurately?

We optimize the MaxCover problem, which assumes that if we annotate an example that the model is uncertain about, it will provide new information to the LLM which can improve its predictions on its neighboring examples (hard examples included in its region).

Q5: The paper argues that previous work assumes a high-resource setting, where a large set of ICL examples is already annotated. Could the paper provide some detailed examples for better understanding?

In this work, we focus on the “cold-start” problem, similar to Votek, where we are given an unlabeled set to select examples from. Most of the related works in AL for ICL assume they are given an annotated validation set, which needs to be statistically large and is not practical for real world few-shot applications [2]. The validation set is leveraged for measuring the informativeness of each individual example as well as for hyperparameter tuning. For example, [3] employs reinforcement learning, which requires one set of labeled examples for policy training and another set of labeled examples for reward estimation.

[2] Ethan Perez, Douwe Kiela, and Kyunghyun Cho. “True few-shot learning with language models”. NeurIPS, 2021. (link)
[3] Zhang, Yiming, Shi Feng, and Chenhao Tan. "Active example selection for in-context learning." EMNLP, (2022). (link)

Q6: For Section 4.1, could the paper provide more details about how to obtain the probability with respect to the label or demonstrations?

We follow previous works (MetaICL, Votek), but we would like to make our writing more clear: We feed the model by concatenating the kNN retrieved demonstrations $[ (x_1, y_1), … (x_k, y_k), x_{k+1} ]$ to compute the negative log-probability for each label $y \in \mathcal{Y}$ for $x_{k+1}$. We keep the prediction with the highest negative log-probability (model’s predicted label with highest confidence) and use its negative log-probability as the uncertainty score. We select the examples with the highest uncertainty scores for the set $U_h$.

Q7: Compared with previous work such as Vote-k, the method proposed by this work is more complex. It introduces a series of hyper-parameters. How to balance them in practice? Also, is there a time advantage of the proposed method over baselines?

Great questions, we have proposed a heuristic-based rule (Appendix A.3) for determining these hyper-parameters in practice. Moreover, AdaICL-base does not have many hyper-parameters (apart from the number of clusters $K$ and the uncertainty threshold $\theta$), but outperforms Votek in many tasks (Tables 6 and 7).

Q8: What is the definition of "egonet" in this paper?

The egonet is the set of nodes that connect to a central node within N-hops. In our work, the hard region $S_i$ centered around node $i$ includes either hard nodes within 1-hop or within 2-hops. We will omit the wording “egonet” in the new version to avoid any confusion.

Q9: For Figure 5, could the paper supplement the comparison between all methods not just the best baseline?

Yes, thank you for the suggestion. We are working on collecting the experimental results and will update the manuscript accordingly before the rebuttal deadline.

We thank the Reviewer for their appreciation of the presentation and the motivation and also acknowledging the strong experimental results across multiple datasets and tasks over contemporaneous baselines. We proceed here below in replying to the comments in specific.

W1: The contributions are somewhat overclaimed.

A1. We study active learning for ICL in the practical low-resource scenario, and highlight the importance of diversity-based uncertainty sampling. All AdaICL variants (AdaICL-base, AdaICL, AdaICL) are shown to be effective for ICL, while our optimization formulation (Section 4.2 and 4.3) provides a new framework for combining uncertainty and diversity sampling.

W2: Technical contributions are not sufficient.

A2. AdaICL performs subset selection based on the hard examples for the LLM, and solves a submodular maximization (MaxCover) problem that captures interactions of different hard examples and their effect during retrieval-based ICL. We believe these are important technical contributions, with connections to previous AL works for kNN classifiers [1].

[1] Wei, Kai, Rishabh Iyer, and Jeff Bilmes. "Submodularity in data subset selection and active learning." ICML, 2015. (link)

W3: The writing also should be polished. For the current form, there are a series of unclear justifications.

A3. We hope that our response addresses the Reviewer's comment and provides more clarifications. We will update the manuscript accordingly.

Q1: It is possible to meet outliers if the method overemphasizes the selection of diverse data. However, in the current form, it is not clear how to address the issue.

As we mention in Section 4.1, AdaICL-base uses kmeans clustering that may be affected by outliers. We then propose AdaICL (Section 4.2) that mitigates the effect of outliers by preferring representative examples of dense regions. Finally, AdaICL+ (Section 4.3) aims at avoiding some failing cases of AdaICL, e.g., the case in Figure 9 (Appendix).

Q2: Does the k-NN retriever equal the similar retriever in the Vote-k paper?

Exactly, all the methods (Random, Votek, AdaICL variants) use the exact same retriever during inference (e.g., retrieval based on SBERT embeddings). Tables 2 and 8 show that AdaICL is robust with respect to the retriever employed. Please also refer to “General Response: Pipeline of the compared methods”.

Q3: This paper claims that "However, these approaches do not consider which examples help the LLM learn new information and may waste resources for annotating examples whose answers are already within the model’s knowledge." I am somewhat confused about this claim. The method Vote-k also uses the feedback of LLMs. Could the paper give more details about this?

Votek does not perform uncertainty sampling, but uses the LLM’s feedback to partition the examples into $B$ bins (budget equals to $B$) and selects one example from each bin. This might select easy examples for the model, which lead to poor calibration (as it is shown in Section 6.3) or waste annotation resources (Table 1). In contrast, AdaICL solves a MaxCover problem iteratively, which is adapted to the LLM’s feedback, and does not assume any predefined data partition, e.g., to $B$ bins.

We thank the Reviewer for their appreciation of the strong experimental results across multiple datasets and tasks over contemporaneous baselines as well as the robustness of AdaICL. We proceed here below in replying to the comments in specific.

W1: Why is the semantic similiarity space determined by a 3rd party embedding model such as SBERT? Shouldn't this be from the LLM itself, such as from an embedding layer?

A1. Thank you for raising this point. We use 3rd party embeddings due to their applicability in practice. First, small-scale LMs, such as SBERT, are much faster at computing embeddings, compared to the LLMs with billions of parameters. Second, for many black-box LLMs, we do not have access to their intermediate layers (or parameters) but only to their outputs (predictions and token logprobabilities). Finally, we have performed experiments with different embedding models (Table 2 and 8), which show that AdaICL is robust to the embedding model selection.

W2: How does overall performance depend on m in $\mathcal{G}_m$?

A2. We have performed extensive AdaICL ablation studies in Appendix D. Table 11 shows the overall performance with respect to different m values in G_m. In addition, Table 12 compares alternative ways of constructing $\mathcal{G}$.

W3: My understanding is that AdaICL queries a LLM many times to get confidence scores before feeding the final prompt in to get $y_{test}$ . How do the various baselines and AdaICL compare when limited to the same LLM query budget? For example, random selection requires 0 queries, which could be far cheaper than running AdaICL.

A3. This is an important point. All model-based selection methods (“Hardest”, Votek, AdaICL variants) query the LLM on all candidate examples to get their confidence scores. We have performed a time analysis in Appendix C5 for the example selection process (Random selection has zero cost). With the downsampled version of data, AdaICL outperforms Random without involving many LLM queries. During inference, all methods (Random, Votek, AdaICL) have the same cost. Please also refer to “General Response: Pipeline of the compared methods”.

Q1: How are you performing k-mean clustering for AdaICL-Base?

During the selection process, we select which examples to annotate (set $\mathcal{L}$) by (i) identifying hard examples for the model (default is 50% most uncertain) , (ii) cluster them into $K$ clusters with $K=B$ ($B$ is the budget), and (iii) selecting the examples closest to each cluster centroid to be added to $\mathcal{L}$. The algorithm is summarized in Appendix A.1.

During inference, set $\mathcal{L}$ is used for retrieval-based ICL. To compare AdaICL-base with random selection, Random creates the set $\mathcal{L}$ drawing $B$ examples at random. Inference is the same for both AdaICL-base and Random ($k$-shot retrieval), but they differ during the selection process.

Q2: What embedder are you using for choosing top-k examples?

The default embedder is SBERT, and is the same for all competing methods during retrieval-based ICL. Tables 2 and 8 provide additional ablations on the embedder used, verifying AdaICL’s robustness.

Q3: Have you compared to any similarity based baselines?

We are not sure which similarity based baselines the Reviewer refers to. We include diversity-based selection (such as fast-votek). During inference, all methods (Random, Votek, AdaICL) will retrieve the $k$ most similar examples from the annotated set $\mathcal{L}$ as demonstrations for a test query $x_{test}$ .

Q4: Have you compared to any retriever-based baselines?

Yes, all compared methods use retrieval during ICL inference (including Random, Votek, AdaICL), which has been shown to be the most effective for ICL [1]. We would like to clarify on the pipeline of the compared methods: All methods have a “Selection Phase”, which selects which examples to annotate, and an “Inference Phase”, which is the $k$-shot retrieval-based ICL and is the same for all. We summarize the key differences between methods below:

Please also refer to “General Response: Pipeline of the compared methods”.

[1] Katerina Margatina, Timo Schick, Nikolaos Aletras, and Jane Dwivedi-Yu. "Active learning principles for in-context learning with large language models", 2023. (link)

Q5: Question about the practical setting. If we need to annotate the selected examples on demand based on the query, then why not annotate directly the query?

As we note above, the selection phase (which examples we choose to annotate) and the inference phase (downstream ICL) are two distinct phases. There is no annotation involved during inference.

Q6: Why are you choosing top-$N_{\theta}$ examples based on probability scores? Would uncertain examples mean bottom-$N_{\theta}$ examples?

Thank you for raising this. Similar to previous works (MetaICL, Votek), we transform probabilities to negative log-probabilites $u_i$. Higher $u_i$ means higher uncertainty, that is why we choose top-$N_{\theta}$. We will add this important clarification to the paper.

Q7: RQ4. is provided but not addressed in the main paper nor referred to Appendix?

Thank you for raising this, there is a typo in the title of Section 6.3, it should be “RQ4: …”. In this section, we investigate how well the model understands the task through the lens of its calibration, i.e., whether higher confidence correlates with higher accuracy. Experimental analysis in Section 6.3 and Appendix C.4, show that AdaICL improves the model’s calibration.

We thank the Reviewer for their appreciation of the well structured presentation of the paper and for acknowledging the strong experimental results. We proceed here below in replying to the comments in specific.

W1: The construction of the graph is highly dependent on other off-the-shelf encoders, which might not be representative of the target model.

A1. AdaICL’s graph construction depends on embedding space, which is also true for other methods that use semantic diversity (kmeans, Votek, AdaICL-base). Tables 2 and 8 show that AdaICL is robust to the selection of the embedding model. Moreover, as raised by reviewer 6M3N, we use 3rd party embeddings due to their applicability in practice. First, small-scale LMs, such as SBERT, are much faster at computing embeddings, compared to the LLMs with billions of parameters. Second, for many black-box LLMs, we do not have access to their intermediate layers (or parameters) but only to their outputs (predictions and token logprobabilities).

W2: The method requires multiple prompts to get LLM feedbacks (probability scores) for each example, which is expensive.

A2. This is an important point. All model-based selection methods (“Hardest”, Votek, AdaICL variants) query the LLM on all candidate examples for annotation to get their confidence scores. We have performed a time analysis in Appendix C5 for the example selection process (Random selection has zero cost). With the downsampled version of data, AdaICL outperforms Random without involving many LLM queries. During inference, all methods (Random, Votek, AdaICL) have the same cost.
Please also refer to “General Response: Pipeline of the compared methods”.

W3: Quite outdated models used (even given the ICLR submission date), so it is hard to verify if the method is applicable to more up-to-date LLMs.

A3. Our experiments (Figs. 4 and 6) show that our AdaICL selection strategy generalizes across different LLMs with varying sizes, which --we believe-- make AdaICL’s contributions clear.

W3: Baseline methods for active learning in ICL

A3. In this work, we focus on the “cold-start” problem, similar to Votek, where we are given an unlabeled set to select examples from. Most of the related works in AL for ICL assume they are given an annotated validation set, which needs to be statistically large and is not practical for real world few-shot applications [1]. The validation set is leveraged for measuring the informativeness of each individual example as well as for hyperparameter tuning. For example, [2] employs reinforcement learning, which requires one set of labeled examples for policy training and another set of labeled examples for reward estimation. Moreover, as suggested, we compare AdaICL with Patron, showcasing the benefits that AdaICL offers for ICL.

GPT-4 or GPT-3.5-turbo are not open-sourced and we currently do not have access to. However, we agree that comparing (i) smaller LLMs combined with AL against (ii) larger LLMs with zero-shot is an important direction.

[1] Ethan Perez, Douwe Kiela, and Kyunghyun Cho. “True few-shot learning with language models”. NeurIPS, 2021. (link)
[2] Zhang, Yiming, Shi Feng, and Chenhao Tan. "Active example selection for in-context learning." EMNLP, (2022). (link)

W4: Obtaining model uncertainty for LLMs

A4. We can obtain uncertainty for large black-box LLMs through their APIs. For example, ChatGPT provides the logprobs outputs, while other LLMs have other ways. AdaICL can be applied to any LLM from which we can access its output logits/probabilities (we discuss this in Appendix F).

W2: Related work combining diversity and uncertainty sampling

A2. We thank the reviewer for bringing forward these important related works. We will make sure to include them in our Related Work section of the updated manuscript.

We note that [2] is specifically designed for object detection and cannot be trivially adapted for NLP, while [3] aims at selecting the best pseudo-labels (where budget B=0), which is not optimal for retrieval-based ICL as our experiments show (Table 2 “Pseudo-labeling”). We highlight the key differences between our work (AdaICL) and Patron [1], which also targets for selective annotation at the cold-start problem:

Optimization. Patron computes an uncertainty score (based on model’s feedback) and a diversity score (based on kmeans clustering) for each example (Eq.(8)/(10) in [1]). Then, it selects the examples with the highest aggregate score from each cluster (similar to our AdaICL-base). In our AdaICL method, we solve MaxCover (a submodular function maximization) over the data subset with hard examples. The MaxCovar avoids selecting examples that will have similar effect during retrieval-based ICL, which leads to a dynamic (NP-hard) optimization. This optimization does not depend on pre-defined clusters, but focuses on examples that can convey new information to the model during inference, even if they would belong to the same cluster.

Multi-step adaptation. At each step (AL round), AdaICL estimates the model’s uncertainty and solves MaxCover over the new subset with hard examples. As the sets of hard examples may be completely different during successive steps, AdaICL can capture broad interactions of the examples and their effect during ICL. Patron combines uncertainty and diversity in a linear manner, which may lead to preferring examples with specific properties (e.g., ones that are close to the cluster centers).

To empirically verify our hypothesis, we adapt Patron to our tasks, and compare AdaICL with Patron in the multi-step setting (Figure 5):

We believe these to be good results and that they positively address the Reviewer’s request. Moreover, our results show that Patron is not suitable for tasks where semantic diversity is less important, i.e., RTE, MRPC, and MNLI:

[1] Yu, Yue, et al. "Cold-start data selection for few-shot language model fine-tuning: A prompt-based uncertainty propagation approach." ACL, 2023. (link)
[2] Wu, Jiaxi, Jiaxin Chen, and Di Huang. "Entropy-based active learning for object detection with progressive diversity constraint." CVPR. 2022. (link)
[3] Yu, Yue, et al. "AcTune: Uncertainty-based active self-training for active fine-tuning of pretrained language models." NAACL. 2022. (link)

We thank the Reviewer for their appreciation of our paper's presentation and the progression of our methodological variants. We proceed here below in replying to the comments in specific.

W1: Challenges in active learning (AL) for ICL, compared to fine-tuning based NLP

A1: Recent theoretical works relate ICL with nonparametric kernel regression [1,2], which is similar to $k$NN classifiers. Designing AL for non-parametric classifiers has been recently highlighted to be challenging [3], as new information cannot be directly incorporated into the model’s parameters. The seminal work for AL for $k$NN classifiers [4] performs subset selection (set of hard examples) and maximizes a submodular function to capture the interactions of different examples and their effect on the non-parametric classifier. Our AdaICL method follows a similar framework, but employs a MaxCover optimization which can generalize to both classification and generation tasks, as it does not require a finite set of label classes.

Furthermore, although active learning for NLP is well-studied, most of the recent approaches fine-tune the model during different AL rounds. This allows the model to incorporate information from the newly labeled examples into its parameters, which can gradually improve its predictions. However, LLMs with billions of parameters are used for ICL. In this case, computing gradient updates is costly and requires additional fine-tuning for every new task. Finally, ICL with wisely-selected labeled samples is shown to be a better few-shot practice than supervised finetuning ([5], Section 4.1).

[1] Chi Han et al., "In-context learning of large language models explained as kernel regression", 2023. (link)
[2] Yu Bai et al., "Transformers as statisticians: Provable in-context learning with in-context algorithm selection", 2023. (link)
[3]: Rittler, Nicholas, and Kamalika Chaudhuri. "A two-stage active learning algorithm for k-nearest neighbors." ICML, 2023. (link)
[4]: Wei, Kai, Rishabh Iyer, and Jeff Bilmes. "Submodularity in data subset selection and active learning." ICML, 2015. (link)
[5] Su, Hongjin, et al. "Selective annotation makes language models better few-shot learners." ICLR, 2023. (link)