Self-Adaptive In-Context Learning: An Information Compression Perspective for In-Context Example Selection and Ordering (2023)

Abstract: Despite the surprising few-shot performance of in-context learning (ICL), it is still a common practice to randomly sample examples to serve as context. This paper advocates a new principle for ICL: self-adaptive in-context learning. The self-adaption mechanism is introduced to help each sample find an in-context example organization (i.e., selection and permutation) that can derive the correct prediction, thus maximizing performance. To validate the effectiveness of self-adaptive ICL, we propose a general select-then-rank framework and instantiate it with new selection and ranking algorithms. Upon extensive evaluation on eight different NLP datasets, our self-adaptive ICL method achieves a 40% relative improvement over the common practice setting. Further analysis reveals the enormous potential of self-adaptive ICL that it might be able to close the gap between ICL and finetuning given more advanced algorithms. Our code will be released to facilitate future research.

## introduction the increasing scale of pre-trained language models (plms) has brought emergent abilities @xcite via in-context learning (icl), where the plms learn to do downstream tasks simply by conditioning on a prompt containing a few examples of their kinds @xcite . due to its impressive performance, icl has now emerged as a popular and efficient way of using plms. however, icl is inherently unstable: given different prompts, the performance of icl on downstream tasks can vary from almost random to comparable with state-of-the-art systems @xcite @xcite , depending on the quality of the prompts. the instability of icl motivates researchers to explore methods that search for high-performing prompts. note that a prompt within the context of icl contains two ingredients: some input-output pairs (i.e., in-context examples) and a template that wraps these examples into a natural language instruction. extensive research has been carried out on searching for a better template @xcite @xcite . in contrast, very few efforts have been spent on searching for the best in-context example organization. 1 recent work, however, has pointed out that the organization of in-context examples can have a significant influence on icl's performance @xcite @xcite . this paper fills this gap by proposing a framework for in-context example searching and ranking. while one can also trivially extend template searching methods to conduct in-context example searching, these methods operate at the corpuslevel. they first construct a small candidate template set using plms @xcite , data mining algorithms @xcite , or by hands @xcite . after that, each candidate will be applied to the whole validation set for inference. according to validation performance, the best template will be adapted for testing. however, existing solutions have the following problems: (i) their performance relies heavily on the availability of a large-scale high-quality validation set; (ii) corpus-level methods can be sub-optimal (see figure 1 ) because finding a universal template that suits all testing samples perfectly is unlikely. such majority bias @xcite will significantly hurt user experience in practice and make corpus-level methods less robust. to tackle these issues, we seek to construct a good-performing in-context example organization for each testing sample individually, without access to a validation dataset. this problem, namely self-adaptive in-context learning, is essentially an np-hard combinatorial optimization problem that cannot be solved within polynomial time. we thus formulate it as a search problem and propose a general two-stage framework to cope with the issue of massive search space. in the first stage, we apply heuristic rules (e.g., nearest neighbors based on semantic similarity) to filter candidate examples. given a much smaller candidate set, we then apply algorithms to rank different organizations and look for the best-performing one. our ranking algorithms are theoretically supported by the minimal description length (mdl) principle and can shed light on why certain permutations are better than others. our contributions are summarized as follows: ## related work despite the surprising zero-shot performance of plms, recent works show that icl can bring the performance to the next level. augmenting plms with icl achieves sota results on a wide range of nlp tasks, ranging from question answering @xcite , information retrieval @xcite , math word problem @xcite , commonsense reasoning @xcite , and fact checking @xcite etc. the instability of icl, however, has encouraged researchers to explore methods that search for robust and high-performing prompts. these methods can be categorized as follows based on the target of searching/optimization: template search focuses on searching for the template that can guide plm's behavior and steer its best performance. great advances have been made in template searching using various methods: plms @xcite ), heuristic rules @xcite @xcite , reinforcement learning @xcite , genetic algorithms @xcite , or by hands @xcite . nonetheless, all these methods require a high-quality validation set to do prompt selection or optimization. unlike them, our framework does not require a validation set. when the validation set is not available, researchers propose to search prompts using entropy @xcite or mutual information @xcite . it's worth mentioning that these two works and all aforementioned methods search at the corpus-level: they pick the bestperforming template with or without a validation set and then equally apply this template to all test examples during inference. however, corpus-level methods might be sub-optimal. if we consider the no free lunch theorem, finding one single template that works well for all testing examples is nearly impossible. in-context example search, unlike template search, is rarely explored in the literature despite that they also have a huge impact on icl performance @xcite . @xcite first propose a learning-free corpuslevel method for in-context example search. however, they only consider an impractical setting with only 4 examples and their 24 permutations ( 4 p 4 = 4! = 24). @xcite find examples that are semantically similar to a test sample can serve as a good choice for its in-context examples. however, the reason why such a simple heuristic works is unclear. @xcite extend this nearest neighbor search and further take the diversity of examples into consideration. inspired by these methods, recent studies propose to learn to retrieve in-context examples @xcite . ## problem formulation given a test sample (x, y), the probability of generating the target y using a casual plm p can be formulated as follows: ## method in this section, we propose a two-stage framework to tackle the problem of self-adaptive icl. ## analysis the observed benefits of our method raise the natural question of why and how it helps and whether the same performance improvements can be transferred to other plms or prompts. in this section, we conduct comprehensive experiments and analy-ses to understand the strength and weaknesses of our method. ## conclusion this paper proposes a new paradigm for icl: selfadaptive icl. unlike existing efforts that universally use one single example organization on all testing samples, we propose a general two-stage select-then-rank framework to search in-context ex-amples at the instance-level. we instantiate this framework with an information-theory-driven ranking algorithm. empirical results suggest that selfadaptive in-context learning can significantly outperform the common practice in icl by a large margin. we reveal the great potential of self-adaptive in-context learning and point out several interesting research problems in method analysis.