C over ICL : Selective Annotation for In-Context Learning via Active Graph Coverage (2024)

Abstract: In-context learning (ICL) adapts Large Language Models (LLMs) to new tasks, without requiring any parameter updates, but few annotated examples as input. In this work, we investigate selective annotation for ICL, where there is a limited budget for annotating examples, similar to low-budget active learning (AL). Although uncertainty-based selection is unreliable with few annotated data, we present CoverICL, an adaptive graph-based selection algorithm, that effectively incorporates uncertainty sampling into selective annotation for ICL. First, CoverICL builds a nearest-neighbor graph based on the semantic similarity between candidate ICL examples. Then, CoverICL employs uncertainty estimation by the LLM to identify hard examples for the task. Selective annotation is performed over the active graph of the hard examples, adapting the process to the particular LLM used and the task tackled. CoverICL selects the most representative examples by solving a Maximum Coverage problem, approximating diversity-based sampling. Extensive experiments on ten datasets and seven LLMs show that, by incorporating uncertainty via coverage on the active graph, CoverICL (1) outperforms existing AL methods for ICL by 2–4.6% accuracy points, (2) is up to 2x more budget-efficient than SOTA methods for low-budget AL, and (3) generalizes better across tasks compared to non-graph alternatives.

## introduction large language models (llms) have shown remarkable performance in various natural language tasks. one of the llms' advantages is their ability to perform few-shot learning @xcite , where they can adapt to new tasks, e.g., topic classification or sentiment prediction, via in-context gpt-j gpt-neo 55 60 65 70 75 69.8 65.9 66.6 61.5 64.2 60.4 65.9 icl is efficient as it does not require any parameter updates or fine-tuning, wherein users can leverage icl to generate task-adaptive responses from black-box llms. however, icl is sensitive to the input prompt @xcite as careful prompt engineering and ground-truth labeling are crucial for good icl performance @xcite . groundtruth labeling requires expert annotators and can be costly, especially for tasks in which the annotators need to provide elaborate responses @xcite . apart from lowering the labeling cost, carefully reducing the number of the icl examples can benefit inference costs and the llm's input context length requirements. consequently, we study the following active learning (al) problem: given a budget b, which examples do we select to annotate and include in the prompt of icl? selecting examples via semantic diversity @xcite offers better generalization while uncertainty sampling @xcite captures how well the llm understands the task. however, in icl, the llm is not fine-tuned and the annotated data are used as few-shot input examples. having few labeled examples at inference (as in few-shot icl) results in a low-budget al setting. it has been shown @xcite @xcite ) that semantic diversity is is crucial in the low-budget al as uncertainty estimation with few annotated data is unreliable. as a result, current selective annotation methods for icl rely on semantic diversity @xcite @xcite . to effectively utilize uncertainty sampling for icl, we propose an adaptive graph-based algorithm, termed covericl (section 4). motivated by recent theoretical works @xcite that relate icl with nearest-neighbor classifiers, covericl builds a nearest-neighbor graph that captures the semantic similarities between candidate examples. then, covericl identifies the examples that the llm is uncertain about (hard examples) and creates the active subgraph, which consists of the hard examples of interest. the active graph is task and model-aware, as uncertainty estimation depends on the llm used and how well it understands the task. having the active graph, covericl performs diversity-based sampling by formulating the well-studied maximum coverage problem (maxcover) over the graph. maxcover selects the examples that best represent the task's difficulty, captures interactions between hard examples, and can be approximately solved via greedy algorithms. furthermore, (i) we extend covericl to an iterative approach that gradually selects harder examples, (ii) we prove that covericl approximates diversity sampling, and (iii) we propose a heuristic rule to initialize covericl's hyperparameters. we conduct experiments on ten datasets across five nlp tasks (topic classification, sentiment analysis, natural language inference, summarization, and math reasoning) with seven llms of varying sizes (1.3b to 65b parameters). as shown in figure 1 , covericl boosts icl performance, improving performance by up to 4.4% accuracy points over diversity and uncertainty sampling. our key contributions are the following: ## problem statement & background we illustrate the overall problem setting in figure 2. given an unlabeled set @xmath0, the goal is to select a subset that contains b selected examples. the b selected examples {x i } b template π denotes a natural language verbalization for each demonstration (x, y) and it also expresses how the labels y map to the target tokens. we elaborate on selective annotation in practice: ## covericl: improving selective annotation for icl using the llm's feedback, e.g., via uncertainty sampling, adapts the selective annotation process to the underlying model and task. however, uncertainty estimation with few annotated examples, as in the low-budget al setting, is unreliable. to effectively utilize uncertainty sampling for icl, we propose an adaptive graph-based algorithm, termed covericl. the overall framework is presented in figure 3 . motivated by recent works that relate icl with nearest-neighbor classifiers (section 3.1), covericl builds a nearestneighbor graph that captures the semantic similar-"amazing movie!" : positive "awful acting": negative "terrible plot": negative -5.73 positive 1.15 "amazing movie!" : positive "awful acting": negative "special acting": ## experimental setting with our experimental analysis, we address the following research questions (rqs): rq1. how does covericl compare with other icl selective annotation methods across diverse tasks? rq2. how effective is covericl's active graph coverage for low-budget al? rq3. how sensitive is covericl to the graph construction? datasets. we perform empirical evaluation with nine nlp datasets that cover well-studied tasks, such as topic classification @xcite , sentiment analysis @xcite , natural language inference @xcite @xcite ), text summarization @xcite , math reasoning @xcite , and college exam questions @xcite . we provide additional details of these datasets in appendix c. ## time cost & visualization in ## conclusions in this work, we investigate selective annotation for icl and we introduce covericl that combines diversity and uncertainty-based selection. our key contributions are highlighted as follows: (1) covericl incorporates the llm's uncertainty by constructing the active graph of hard examples. the most representative and diverse examples are selected via maxcover to be annotated for icl. (2) covericl is extended to an iterative approach that gradually selects harder examples (covericl+). moreover, covericl has theoretical guarantees that it approximates diversity sampling, while covericl's hyperparameters can be determined via a heuristic rule. (3) covericl outperforms competing icl methods for selective annotation by up to 4.4% points. incorporating uncertainty via covericl's active graph is shown to is up to 2× more budget-efficient than sota methods for low-budget al.