F ast GAS : Fast Graph-based Annotation Selection for In-Context Learning (2024)

Abstract: In-context learning (ICL) empowers large language models (LLMs) to tackle new tasks by using a series of training instances as prompts. Since generating the prompts needs to sample from a vast pool of instances and annotate them (e.g., add labels in classification task), existing methods have proposed to select a subset of unlabeled examples for annotation, thus enhancing the quality of prompts and concurrently mitigating annotation costs. However, these methods often require a long time to select instances due to their complexity, hindering their practical viability. To address this limitation, we propose a graph-based selection method, FastGAS, designed to efficiently identify high-quality instances while minimizing computational overhead. Initially, we construct a data similarity graph based on instance similarities. Subsequently, employing a graph partitioning algorithm, we partition the graph into pieces. Within each piece (i.e., subgraph), we adopt a greedy approach to pick the most representative nodes. By aggregating nodes from diverse pieces and annotating the corresponding instances, we identify a set of diverse and representative instances for ICL. Compared to prior approaches, our method not only exhibits superior performance on different tasks but also significantly reduces selection time. In addition, we demonstrate the efficacy of our approach in LLMs of larger sizes.

## introduction recent advances in natural language processing heavily leverage large language models, exemplified by models such as gpt-3 @xcite . among them, in-context learning (icl) emerges as a promising direction in this field. icl adapts specific tasks with just a few instances as prompts, offering a viable alternative to traditional supervised fine-tuning @xcite . the performance of icl is intricately tied to the effectiveness of the prompt surface, encompassing factors such as in-stance selection and the sequence of demonstration instances @xcite @xcite . in this study, we focus on instance selection and explore novel solutions to reduce manual annotation costs while maintaining high in-context learning performance. previous research underscores the importance of retrieving prompts from a vast set of annotated instances to achieve optimal performance @xcite . in particular, performance is shown to improve significantly when choosing in-context examples similar to each test input @xcite . however, addressing the unique requirements of different test instances requires a large set of annotated examples, incurring significant human and financial resources. to mitigate annotation costs, previous efforts have sought to identify a small number of unlabeled instances for annotation @xcite . the objective is to select diverse and representative instances, where representativeness aids in finding similar demonstrations for different test instances, while diversity broadens the overall coverage. despite their superiority over random selection, these methods have specific drawbacks. for example, vote-k @xcite emphasizes diversity but adds inference costs due to predictions on unlabeled data. ideal @xcite employs influence-driven selective annotations, drawing inspiration from influence maximization in social graphs. however, both methods struggle to balance diversity and representativeness, leading to suboptimal performance. furthermore, a notable shortcoming of existing methods is their computational inefficiency. the precise calculation process (e.g., iteratively searching the entire dataset) results in high computational costs, making them less practical for real-world applications. figure 1 illustrates the time required by our method and two baseline methods, vote-k and ideal, under the same hardware conditions 053& 667 '%shgld 6hohfwlrq7lphv )dvw*$6 figure 1: comparison of our method and two baselines on three classification tasks (mprc, sst-5, and dbpedia) with respect to time consumption during subset selection. the annotation budget is 18. the y-axis represents the time consumption with a log scale. notably, our method significantly reduces the time cost in comparison to both baseline methods. and annotation budgets. it is observed that both baselines necessitate at least 500 seconds to select a subset for dbpedia and sst-5 tasks. remarkably, for the dbpedia task, vote-k exceeds 30, 000 seconds (over eight hours) to select just 18 instances. as the annotation budget grows, the time needed by these methods to perform the selection process can increase exponentially (see section 4.4), further constraining their applicability in real-world settings. in our pursuit of an efficient and effective selective annotation method, we pose the fundamental question: can we identify a set of diverse and representative instances with high efficiency? answering this question, we propose fastgas, a fast graph-based annotation selection method that works in an unsupervised manner. we first build a data similarity graph based on the similarity among unlabeled data. we then select instances for annotation based on the data similarity graph. in particular, our method focuses on the following three properties of selected instances: compared with state-of-the-art baseline methods, our method improves the overall performance on seven datasets in three types of tasks. besides, for all tasks, our method only needs a few seconds to complete the instance selection process. in addition, we also provide a theoretical guarantee for the effectiveness of the greedy selection algorithm. ## related work in-context learning in-context learning (icl) integrates a small number of training examples as prompts before the test input @xcite , demonstrating a remarkable ability to enhance the performance of large language models (llms) in a wide range of downstream tasks, such as machine translation @xcite , data generation @xcite , and others @xcite @xcite . furthermore, the advent of advanced strategies such as chain-of-thought prompting @xcite has significantly refined the efficacy of icl, offering deeper insights and more nuanced understanding within this innovative paradigm @xcite @xcite . despite its successes, icl's efficacy is often hampered by the sensitivity to the choice of in-context examples, leading to research on optimized selection strategies @xcite @xcite . techniques have evolved from selecting examples close to the test input in embedding spaces @xcite @xcite . the focus has also shifted towards annotation efficiency, exploring how to find a set of examples once for all queries on the same task @xcite @xcite . following existing works @xcite , we also use a graph to represent unlabeled instances and employ graph-based methods to select instances for annotation. however, our methodology distinguishes itself from existing works by focusing on efficiency in the selection of instances. as discussed in section 1, we aim to select diverse and representative instances while reducing the computation cost. active learning given a limited budget for labeling, active learning empowers machine learning models to achieve comparable or superior performance using a carefully selected set of labeled training instances @xcite @xcite . our work on selective annotation aligns with the goal of active learning applied to graphs, specifically focusing on the selection of nodes for labeling to inform predictions @xcite @xcite . traditional graph-based active learning methods employ criteria such as uncertainty @xcite and representativeness @xcite for selection. since the icl tasks we focus on do not involve model training or finetuning, we compare our method with basic graph active learning methods that are not incorporated with model training, like those based on node degree @xcite and pagerank @xcite . our experiments indicate that while simple graph active learning methods work well in icl, our approach still achieves better overall performance. ## methods in this section, we will explain how to integrate a graph partition algorithm and a greedy algorithm in a selective annotation in in-context learning to reduce the annotation cost. ## experiment in this section, we evaluate the effectiveness of our method in various datasets encompassing diverse task categories. we begin by presenting the details of our experiment setups. subsequently, the reported results demonstrate the superior performance of the proposed method in identifying an optimal selective annotation subset efficiently, outperforming established baselines. furthermore, we conduct ablation studies to investigate the impact of crucial hyperparameters in our method. ## conclusion recent advancements have showcased the capability of large language models (llms) to adapt to new tasks with just a few demonstration instances. while existing approaches aim to enhance model performance by selecting a limited number of instances to annotate for prompts, they are hindered by significant computational demands and lengthy processing times. to address these challenges, we introduce a graph-based selection algorithm, fast-gas, accompanied by a theoretical analysis of its effectiveness. our empirical evaluations reveal that this method outperforms others in seven distinct tasks, demonstrating exceptional efficacy. unlike conventional methods that require high computation costs, our method greatly improves the efficiency of selecting instances, substantially enhancing its applicability to practical scenarios. addition-ally, we demonstrate fastgas's versatility across llms of various sizes. we hope that these insights will help researchers in devising effective icl strategies to optimize llm performance.