What are the various methods proposed to retrieve demonstrations for in-context learning?
In this section, we introduce previous demonstration retrievers for in-context learning, and explain the difference between UDR and them. In general, there are two kinds of demonstration retrievers for ICL. One is to leverage off-the-shelf retrievers. For example, Liu et al. (2022) propose to use a fine-tuned BERT to encode examples and use a
KNN-based method to retrieve semantically similar demonstrations to improve ICL. Agrawal et al. (2022) use BM25 to retrieve demonstrations for machine translation. Compared with them, UDR incorporates various tasks’ supervision by unified LM’s feedback and thus can better retrieve informative demonstrations. Another approach is to train a task-specific retriever by a designed task-specific signal. Das et al. (2021) explore demonstration
retrieval for knowledge-based question answering and define the F1 score of logic forms as soft-label to train the retriever. Poesia et al. (2022) train a demonstration retriever for code generation, based on the edit distance of abstract syntax trees. Hu et al. (2022) define the similarity between dialogue states, and use it to train a demonstration retriever for dialogue state tracking. Rubin et al. (2022) propose Efficient Prompt Retriever (EPR) for semantic
parsing, which is to use the language model to score examples, assign positive and negative labels for them and use DPR (Karpukhin et al., 2020) to train a demonstration retriever. Shi et al. (2022) explore demonstration retrieval for cross-lingual semantic parsing using a similar example scoring method with EPR. These task-specific methods serve for each task separately and are hard to transfer and scale on various tasks. For other tasks, it requires
to redesign the similarity function or training signal. Compared with them, we introduce a unified training framework based on list-wise ranking and propose a single multi-task retriever UDR to serve for a wide range of tasks. Compared with EPR, besides UDR’s versatility on various tasks, UDR can incorporate LM’s feedback by ranking-based training in a more fine-grained way and receive more crucial candidates’ signals by the iterative mining
strategy.
Unified Demonstration Retriever for In-Context Learning
In-context learning is a new learning paradigm where a language model conditions on a few input-output pairs (demonstrations) and a test input, and directly outputs the prediction. It has been shown sensitive to the provided demonstrations and thus promotes the research of demonstration retrieval: given a test input, relevant examples are retrieved from the training set to serve as informative demonstrations for in-context learning. While previous works train task-specific retrievers for several tasks separately, these methods are hard to transfer and scale on various tasks, and separately trained retrievers will cause a lot of parameter storage and deployment cost. In this paper, we propose Unified Demonstration Retriever (UDR), a single model to retrieve demonstrations for a wide range of tasks. To train UDR, we cast various tasks’ training signals into a unified list-wise ranking formulation by language model’s feedback. Then we propose a multi-task list-wise ranking training framework with an iterative mining strategy to find high-quality candidates, which can help UDR fully incorporate various tasks’ signals. Experiments on 30+ tasks across 13 task families and multiple data domains show that UDR significantly outperforms baselines. Further analyses show the effectiveness of each proposed component and UDR’s strong ability in various scenarios including different LMs (1.3B 175B), unseen datasets, varying demonstration quantities, etc. We will release the code and model checkpoint after review.
[{"first":"Xiaonan","last":"Li","middle":[]},{"first":"Kai","last":"Lv","middle":[]},{"first":"Hang","last":"Yan","middle":[]},{"first":"Tianyang","last":"Lin","middle":[]},{"first":"Wei","last":"Zhu","middle":[]},{"first":"Yuan","last":"Ni","middle":[]},{"first":"Guotong","last":"Xie","middle":[]},{"first":"Xiaoling","last":"Wang","middle":[]},{"first":"Xipeng","last":"Qiu","middle":[]}]
Learning To Retrieve Prompts for In-Context Learning
In-context learning is a recent paradigm in natural language understanding, where a large pre-trained language model (LM) observes a test instance and a few training examples as its input, and directly decodes the output without any update to its parameters. However, performance has been shown to strongly depend on the selected training examples (termed prompts). In this work, we propose an efficient method for retrieving prompts for in-context learning using annotated data and an LM. Given an input-output pair, we estimate the probability of the output given the input and a candidate training example as the prompt, and label training examples as positive or negative based on this probability. We then train an efficient dense retriever from this data, which is used to retrieve training examples as prompts at test time. We evaluate our approach on three sequence-to-sequence tasks where language utterances are mapped to meaning representations, and find that it substantially outperforms prior work and multiple baselines across the board.
[{"first":"Ohad","last":"Rubin","middle":[]},{"first":"Jonathan","last":"Herzig","middle":[]},{"first":"Jonathan","last":"Berant","middle":[]}]
Case-based Reasoning for Natural Language Queries over Knowledge Bases
It is often challenging to solve a complex problem from scratch, but much easier if we can access other similar problems with their solutions — a paradigm known as case-based reasoning (CBR). We propose a neuro-symbolic CBR approach (CBR-KBQA) for question answering over large knowledge bases. CBR-KBQA consists of a nonparametric memory that stores cases (question and logical forms) and a parametric model that can generate a logical form for a new question by retrieving cases that are relevant to it. On several KBQA datasets that contain complex questions, CBR-KBQA achieves competitive performance. For example, on the CWQ dataset, CBR-KBQA outperforms the current state of the art by 11% on accuracy. Furthermore, we show that CBR-KBQA is capable of using new cases without any further training: by incorporating a few human-labeled examples in the case memory, CBR-KBQA is able to successfully generate logical forms containing unseen KB entities as well as relations.
[{"first":"Rajarshi","last":"Das","middle":[]},{"first":"Manzil","last":"Zaheer","middle":[]},{"first":"Dung","last":"Thai","middle":[]},{"first":"Ameya","last":"Godbole","middle":[]},{"first":"Ethan","last":"Perez","middle":[]},{"first":"Jay Yoon","last":"Lee","middle":[]},{"first":"Lizhen","last":"Tan","middle":[]},{"first":"Lazaros","last":"Polymenakos","middle":[]},{"first":"Andrew","last":"McCallum","middle":[]}]
In-Context Learning for Few-Shot Dialogue State Tracking
Collecting and annotating task-oriented dialogues is time-consuming and costly; thus, zero and few shot learning could greatly benefit dialogue state tracking (DST). In this work, we propose an in-context learning (ICL) framework for zero-shot and few-shot learning DST, where a large pre-trained language model (LM) takes a test instance and a few exemplars as input, and directly decodes the dialogue state without any parameter updates. To better leverage a tabular domain description in the LM prompt, we reformulate DST into a text-to-SQL problem. We also propose a novel approach to retrieve annotated dialogues as exemplars. Empirical results on MultiWOZ show that our method IC-DST substantially outperforms previous fine-tuned state-of-the-art models in few-shot settings. In addition, we test IC-DST in zero-shot settings, in which the model only takes a fixed task instruction as input, finding that it outperforms previous zero-shot methods by a large margin.
[{"first":"Yushi","last":"Hu","middle":[]},{"first":"Chia-Hsuan","last":"Lee","middle":[]},{"first":"Tianbao","last":"Xie","middle":[]},{"first":"Tao","last":"Yu","middle":[]},{"first":"Noah","last":"Smith","middle":["A."]},{"first":"Mari","last":"Ostendorf","middle":[]}]
What Makes Good In-Context Examples for GPT-3?
GPT-3 has attracted lots of attention due to its superior performance across a wide range of NLP tasks, especially with its in-context learning abilities. Despite its success, we found that the empirical results of GPT-3 depend heavily on the choice of in-context examples. In this work, we investigate whether there are more effective strategies for judiciously selecting in-context examples (relative to random sampling) that better leverage GPT-3’s in-context learning capabilities.Inspired by the recent success of leveraging a retrieval module to augment neural networks, we propose to retrieve examples that are semantically-similar to a test query sample to formulate its corresponding prompt. Intuitively, the examples selected with such a strategy may serve as more informative inputs to unleash GPT-3’s power of text generation. We evaluate the proposed approach on several natural language understanding and generation benchmarks, where the retrieval-based prompt selection approach consistently outperforms the random selection baseline. Moreover, it is observed that the sentence encoders fine-tuned on task-related datasets yield even more helpful retrieval results. Notably, significant gains are observed on tasks such as table-to-text generation (44.3% on the ToTTo dataset) and open-domain question answering (45.5% on the NQ dataset).
[{"first":"Jiachang","last":"Liu","middle":[]},{"first":"Dinghan","last":"Shen","middle":[]},{"first":"Yizhe","last":"Zhang","middle":[]},{"first":"Bill","last":"Dolan","middle":[]},{"first":"Lawrence","last":"Carin","middle":[]},{"first":"Weizhu","last":"Chen","middle":[]}]
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
In-context learning using large language models has recently shown surprising results for semantic parsing tasks such as Text-to-SQL translation. Prompting GPT-3 or Codex using several examples of question-SQL pairs can produce excellent results, comparable to state-of-the-art finetuning-based models. However, existing work primarily focuses on English datasets, and it is unknown whether large language models can serve as competitive semantic parsers for other languages. To bridge this gap, our work focuses on cross-lingual Text-to-SQL semantic parsing for translating non-English utterances into SQL queries based on an English schema. We consider a zero-shot transfer learning setting with the assumption that we do not have any labeled examples in the target language (but have annotated examples in English). This work introduces the XRICL framework, which learns to retrieve relevant English exemplars for a given query to construct prompts. We also include global translation exemplars for a target language to facilitate the translation process for large language models. To systematically evaluate our model, we construct two new benchmark datasets, XSpider and XKaggle-dbqa, which include questions in Chinese, Vietnamese, Farsi, and Hindi. Our experiments show that XRICL effectively leverages large pre-trained language models to outperform existing baselines. Data and code are publicly available at https://github.com/Impavidity/XRICL.
[{"first":"Peng","last":"Shi","middle":[]},{"first":"Rui","last":"Zhang","middle":[]},{"first":"He","last":"Bai","middle":[]},{"first":"Jimmy","last":"Lin","middle":[]}]
Synchromesh: Reliable code generation from pre-trained language models
Large pre-trained language models have been used to generate code,providing a flexible interface for synthesizing programs from natural language specifications. However, they often violate syntactic and semantic rules of their output language, limiting their practical usability. In this paper, we propose Synchromesh: a framework for substantially improving the reliability of pre-trained models for code generation. Synchromesh comprises two components. First, it retrieves few-shot examples from a training bank using Target Similarity Tuning (TST), a novel method for semantic example selection. TST learns to recognize utterances that describe similar target programs despite differences in surface natural language features. Then, Synchromesh feeds the examples to a pre-trained language model and samples programs using Constrained Semantic Decoding (CSD): a general framework for constraining the output to a set of valid programs in the target language. CSD leverages constraints on partial outputs to sample complete correct programs, and needs neither re-training nor fine-tuning of the language model. We evaluate our methods by synthesizing code from natural language descriptions using GPT-3 and Codex in three real-world languages: SQL queries, Vega-Lite visualizations and SMCalFlow programs. These domains showcase rich constraints that CSD is able to enforce, including syntax, scope, typing rules, and contextual logic. We observe substantial complementary gains from CSD and TST in prediction accuracy and in effectively preventing run-time errors.
[{"first":"Gabriel","last":"Poesia","middle":[]},{"first":"Oleksandr","last":"Polozov","middle":[]},{"first":"Vu","last":"Le","middle":[]},{"first":"Ashish","last":"Tiwari","middle":[]},{"first":"Gustavo","last":"Soares","middle":[]},{"first":"Christopher","last":"Meek","middle":[]},{"first":"Sumit","last":"Gulwani","middle":[]}]
In-context Examples Selection for Machine Translation
Large-scale generative models show an impressive ability to perform a wide range of Natural Language Processing (NLP) tasks using in-context learning, where a few examples are used to describe a task to the model. For Machine Translation (MT), these examples are typically randomly sampled from the development dataset with a similar distribution as the evaluation set. However, it is unclear how the choice of these in-context examples and their ordering impacts the output translation quality. In this work, we aim to understand the properties of good in-context examples for MT in both in-domain and out-of-domain settings. We show that the translation quality and the domain of the in-context examples matter and that 1-shot noisy unrelated example can have a catastrophic impact on output quality. While concatenating multiple random examples reduces the effect of noise, a single good prompt optimized to maximize translation quality on the development dataset can elicit learned information from the pre-trained language model. Adding similar examples based on an n-gram overlap with the test source significantly and consistently improves the translation quality of the outputs, outperforming a strong kNN-MT baseline in 2 out of 4 out-of-domain datasets.
[{"first":"Sweta","last":"Agrawal","middle":[]},{"first":"Chunting","last":"Zhou","middle":[]},{"first":"Mike","last":"Lewis","middle":[]},{"first":"Luke","last":"Zettlemoyer","middle":[]},{"first":"Marjan","last":"Ghazvininejad","middle":[]}]
Unified Demonstration Retriever for In-Context Learning
Large language models have shown an impressive in-context learning ability for various Natural Language Processing (NLP) tasks (Brown et al., 2020;Dong et al., 2022). In-context learning (ICL) is a recent learning paradigm where a language model (LM) learns a task by observing a few inputoutput pairs (demonstrations) and directly output the prediction of the given test input. Thus ICL can unify a wide range of NLP tasks through one language model's inference without parameter updates, which makes it a promising alternative to supervised fine-tuning (Devlin et al., 2019).
Unified Demonstration Retriever for In-Context Learning
However, it has been shown that ICL's performance highly depends on the provided demonstrations (Liu et al., 2022;Li and Qiu, 2023a). This promotes the research of demonstration retrieval for in-context learning (Liu et al., 2022;Rubin et al., 2022;: As shown in Figure 1, given a test input, relevant examples are retrieved from an annotated training set, to serve as informative demonstrations for ICL.
Unified Demonstration Retriever for In-Context Learning
There are about two lines of methods to retrieve demonstrations. One is to leverage off-the-shelf retrievers, e.g., BM25 (Robertson and Zaragoza, 2009) or Sentence-BERT (Reimers and Gurevych, 2019a). They can retrieve demonstrations that are textually or semantically similar to the test input and achieve empirical improvements. Thanks to their versatility, they can serve for extensive NLP tasks, but they are heuristic and sub-optimal since they are not guided by task supervision. Another line is to train a task-specific retriever by a specially designed task signal. Das et al. (2021) train the retriever for knowledge-based question answering, based on the logic form's surface similarity. Hu et al. (2022) explore ICL on dialogue state tracking and design the similarity between dialogue's states as the retriever's training signal. Rubin et al. (2022) and  leverage the LM's feedback to train demonstration retrievers for semantic parsing in English and cross-lingual scenarios, respectively. These task-specialized retrievers show better performance than the former, but they still face two challenges: 1. these explorations are limited to a small range of tasks and demonstrated separately on each task, e.g., semantic parsing or dialogue state tracking, which restricts systematic and compatible research on demonstration retrieval for ICL while ICL is a unified framework for extensive tasks. 2. it is costly for these methods to transfer and scale on various tasks and the reason is twofold: (i) they need to design a specialized training signal for each task. (ii) the number of retrievers will scale up with increasing tasks, which results in massive parameter storage and deployment costs.
Unified Demonstration Retriever for In-Context Learning
To address these limitations, we explore learning various tasks' demonstration retrieval in a unified formulation and propose Unified Demonstration Retriever (UDR), a single multi-task model for demonstration retrieval of a wide range of tasks. To train UDR, we cast various tasks' training signals into a unified list-wise ranking formulation. For a training example from task T , we select a list of candidate examples from T 's training set and rank them by LM's feedback. Then we propose a multitask list-wise ranking training framework, with an iterative mining strategy to find high-quality candidates. Specifically, we iteratively train the retriever to rank candidates and use itself to find high-quality positive candidates and hard negatives. Compared with the representative method for demonstration retrieval, EPR(Rubin et al., 2022), which trains the retriever by the binary label from LM's feedback and selects candidates in a manually limited range, our training framework can explore the entire dataset to get high-quality candidates and help UDR fully incorporate the LM's feedback through list-wise ranking training.
Unified Demonstration Retriever for In-Context Learning
Experiments on 30+ tasks across 13 task families and multiple data domains show that UDR significantly outperforms baselines and further analyses show the effectiveness of each proposed component and UDR's strong ability under various scenarios including different LMs (1.3B ∼ 175B), unseen datasets, varying demonstrations quantities, etc. We release the code and model checkpoint at https://github.com/KaiLv69/UDR.
Unified Demonstration Retriever for In-Context Learning
Provided a language model G, a training set D train and a test case x test , demonstration retrieval aims to retrieve x test 's relevant demonstrations from D train to help LM G decode the target output. Previous works (Das et al., 2021;Rubin et al., 2022; propose task-specialized methods for several tasks separately, but they are hard to transfer and scale on various tasks. In this work, we focus on learning various tasks' demonstration retrieval in a unified formulation and propose UDR , a single model for demonstration retrieval of a wide range of tasks, as shown in Figure 2. We introduce its architecture, training, and inference as follows.
Unified Demonstration Retriever for In-Context Learning
UDR is based on the prevailing bi-encoder architecture, dense passage retriever (DPR) (Karpukhin et al., 2020), which encodes the query example and candidate examples separately and then calculates their similarity. To distinguish examples from different tasks, UDR encodes the example together with its task instruction, which is a short piece of text related to the task objective. Taking CNN/-DailyMail (Hermann et al., 2015) as an example, its task instruction can be "Summarize the text". Given an example query x and a candidate demonstration z = {x ′ , y ′ } from task T i , UDR uses the query encoder E q and demonstration encoder E d to encode them respectively and calculates their similarity as:
Unified Demonstration Retriever for In-Context Learning
where I i is T i 's task instruction and ⊕ is the concatenation operator. E q and E d are two multilayer Transformer (Vaswani et al., 2017) encoders with "CLS" pooling and can be initialized with pre-trained models (Devlin et al., 2019).
Unified Demonstration Retriever for In-Context Learning
Thus, we can not only get task-specific features by specifying the task instruction, but also retain the uniformity and parameter efficiency of ICL.
Unified Demonstration Retriever for In-Context Learning
To train the demonstration retriever, previous works (Das et al., 2021;Rubin et al., 2022;Hu et al., 2022)  a unified list-wise ranking formulation. Then we introduce a multi-task list-wise ranking training framework, where we iteratively let the retriever itself to mine high-quality candidates and learn to rank them in turn, across various tasks, shown in Algorithm 1. We introduce the list-wise ranking training and iterative mining strategy as follows.
Unified Demonstration Retriever for In-Context Learning
Given a training example (x, y) and its candidates Z = {z i } l i=1 , we first rank these candidates as:
Unified Demonstration Retriever for In-Context Learning
where s(z j ) = s gen (z j ) for generation tasks and s(z j ) = s cls (z j ) for classification and multi-choice tasks. p G (·|·) is the LM G's conditional likelihood. Y is the label space or choices of the classification or multi-choice task, respectively. For simplicity, we omit special tokens and classification tasks' verbalizers in the equations above. First we use G to score each candidate (Rubin et al., 2022) and calculate s(z j ) as the ground truth y's likelihood conditioned on the candidates z j and the query input x. s(z j ) indicates the importance of z j for G to encode x and generate the ground truth y. Then we rank Z according to {s(z i )} l i=1 . The more important z j is for x, the higher z j 's rank will be. Thus we unify various tasks' training signals into the same list-wise ranking formulation using LM's feedback, instead of designing task-specific objectives (Das et al., 2021;Hu et al., 2022).
Unified Demonstration Retriever for In-Context Learning
With these candidates' ranks from G's feedback, we propose to use the following loss function to in-ject the ranking signal into the retriever E, inspired by LambdaRank (Burges, 2010):
Unified Demonstration Retriever for In-Context Learning
. For those z i and z j where r(z i ) < r(z j ), L rank will draw sim(x, z i ) up and optimize the retriever towards sim(x, z i ) > sim(x, z j ). Additionally, w adjusts the weight for each pair of demonstrations and inject list-wise ranking information into L rank . When z i has a much higher rank than z j , e.g, r(z i ) = 1 and r(z j ) = 10, w will be a high weight and strongly draw sim(x, z i ) up from sim(x, z j ). Since we optimize the retriever on demonstration pairs under different w, L rank can help UDR fully incorporate candidates' listwise ranking signals from G's feedback for various tasks and learn to retrieve those helpful demonstrations.
Unified Demonstration Retriever for In-Context Learning
To fully leverage the computation of the same batch, we also use the in-batch negative loss as:
Unified Demonstration Retriever for In-Context Learning
where z * is the rank-1 candidate of x and Z is all candidates (x's or not x's) in the batch. Each batch is sampled from the same task, and to alleviate the bias towards high-resource tasks, we sample each task according to the multinomial distribution with probabilities {p(T i )} T i=1 as:
Unified Demonstration Retriever for In-Context Learning
where D T i is the ith task's dataset. α is a predefined hyper-parameter and we follow Conneau and Lample (2019) to set α as 0.5.
Unified Demonstration Retriever for In-Context Learning
The overall loss function of UDR is the integration of these two losses as follows,
Unified Demonstration Retriever for In-Context Learning
where λ is a pre-defined hyper-parameter.
Unified Demonstration Retriever for In-Context Learning
The selection of candidates can be a key factor for retriever's training (Karpukhin et al., 2020;Xiong et al., 2021). It is desirable for UDR to take the entire training set as candidates to provide abundant ranking signals. However, it is infeasible since scoring all pairs of training examples is quadratic in |D| and costly. Previous work (Rubin et al., 2022) selects those examples which have textually similar targets with x's as candidates. However, it may bias the retriever to learn among candidates with highly similar targets. Meanwhile, it can probably miss important demonstrations. For instance, if an example z contains relevant logic with the query x but has a dissimilar target with x's, the valuable z will not be selected as candidate to provide signal for the retriever. So, we propose an iterative mining strategy to select candidates by the retriever itself. Specifically, we iteratively train the retriever and use it to select candidates in turn. At each iteration, we update each training example's candidates as:
Unified Demonstration Retriever for In-Context Learning
where D is the task's entire training set. Then we will use LM G to score and rank Z * . The new candidates in Z * can be divided into two categories. If a new candidate z has a low score, it means that we find a hard-negative candidate that can provide crucial negative signal for the retriever. If the score of z is high and even higher than all old candidates, it means that we find a valuable positive candidate that can help the retriever learn to find informative demonstrations. Thus, with iterative mining, we can explore the entire dataset, find high-quality candidates and improve training progressively. Before the first iteration, the retriever is untrained, so we initialize candidates based on surface similarity, inspired by Rubin et al. (2022).
Unified Demonstration Retriever for In-Context Learning
For computational efficiency, we first update candidates and score Z * at each iteration, and then randomly sample l of Z * and rank them at each training step. In summary, Algorithm 1 shows the UDR's overall training procedure. Score new candidates by G. 12: end for
Unified Demonstration Retriever for In-Context Learning
After training, we encode each task T i 's training set using E d (p i ⊕ ·). At the test stage, given a task T i 's input, x test , we use E q (p i ⊕ ·) to compute its encoding and then use FAISS (Johnson et al., 2021) to search over T i 's training set to find the most relevant demonstrations, ascendingly sorted by sim(x test , ·), D = (z 1 , z 2 , · · · , z L ). For generation tasks, the number of final demonstrations, L, is determined by the LM G's maximal input length C.
Unified Demonstration Retriever for In-Context Learning
where |y| is the pre-defined maximal length of the generated target. For classification and multi-choice tasks, we observe that increasing L brings negligible performance improvement and thus we set L to a small value, 8. We conduct further analysis of the number of demonstrations in section 3.3.5. Finally, we use greedy decoding to get the result of G([z 1 ; z 2 ; · · · ; z L ; x test ]). Notice that here D is ascendingly sorted by sim(x test , ·) unless otherwise specified. Our analysis in section 3.3.4 shows that different orderings lead to similar performance. Thus we use the same ordering strategy with EPR (Rubin et al., 2022) for fair comparison.
Unified Demonstration Retriever for In-Context Learning
Dataset We train UDR on a wide range of NLP tasks, consisting of about 40 tasks across 13 task families and multiple data domains, including: Sentiment Classification: SST-2, SST-5 (Socher et al., 2013), Amazon (McAuley and Leskovec, 2013), Yelp (Zhang et al., 2015), MR (Pang and Lee, 2005) and CR (Amplayo et al., 2022); Topic Classification: AGNews, Yahoo (Zhang et al., 2015), TREC (Voorhees and Tice, 2000) and DBPeida (Lehmann et al., 2015); Implementation Details We follow EPR (Rubin et al., 2022) to use GPT-Neo-2. 7B (Black et al., 2021) as the scoring LM and the inference LM for most experiments in the paper unless otherwise specified. We also explore UDR's transferability across different inference LMs in section 3.3.2. Following EPR(Rubin et al., 2022), we initialize E q and E d as two separate "BERT-base-uncased" encoders (Devlin et al., 2019). We list the overall hyper-parameters and implementation details in Appendix B. On each task, we use one specific template for scoring and inference (see Appendix A). We evaluate UDR's performance when inference templates are different with the scoring template in Appendix C, and the results show that UDR has stable performance across varying inference templates, which reflects UDR's generality.  (Su et al., 2022): Instructor is a recently proposed competitive text embedding model trained on 330 tasks with instructions. By providing the specialized instruction, it can serve for demonstration retrieval. For fair comparison, we conduct experiments on its released base-size model. 5. DR-Target: This baseline is inspired by previous works on generation tasks like dialogue state tracking, question answering and code generation (Hu et al., 2022;Das et al., 2021;Poesia et al., 2022), which design the task-specific target's similarity and use examples with similar targets to train the retriever.
Unified Demonstration Retriever for In-Context Learning
Here we use BM25 as the similarity function for each task's target output. Specifically, we use BM25 to find positive pairs with similar targets and use DPR (Karpukhin et al., 2020) for training. 6. EPR (Rubin et al., 2022): EPR is a recently proposed representative method for training demonstration retriever. It uses the language model to assign candidate examples with positive and negative labels and thus trains a task-specific demonstration retriever by DPR. For fair comparison, we train EPR on each task using the same hyper-parameters of UDR. Specially, we discuss EPR's candidate quantity in Appendix B.
Unified Demonstration Retriever for In-Context Learning
Except that the performance of Random, BM25, SBERT and EPR on semantic parsing is from the previous paper (Rubin et al., 2022), other results are from our implementation since they are not explored previously.
Unified Demonstration Retriever for In-Context Learning
We show the performance comparison of classification tasks and generation tasks in Table 1 and  Table 2, respectively. We can see that UDR outperforms baselines significantly on most tasks, which shows UDR's best overall demonstration retrieval ability on a wide range of NLP tasks. Specially, compared with DR-Target and EPR, UDR has better overall performance and this shows the effectiveness of our unification of various tasks' training signals. Meanwhile, compared with Instructor (Su et al., 2022), the text embedding model trained on 330 tasks' text pairs, UDR has an improvement  of 10 and 6.7 points for classification and generation tasks respectively with less training data. This straightly demonstrates that our proposed training framework can help UDR incorporate LM's feedback through a unified ranking formulation and better retrieve informative demonstrations.
Unified Demonstration Retriever for In-Context Learning
Additionally, we find the random baseline shows the worst performance on most tasks and this reflects the necessity to retrieve high-quality relevant demonstrations. Meanwhile, EPR and UDR have better performance than other methods, which reflects the importance of LM's feedback. Among these datasets, we notice a different trend on text summarization datasets like CNN/DailyMail and Reddit, on which these methods have similar performance. We conjecture that the LM can already have the knowledge of summarization since there are a lot of "[Article, TL;DR, Abstract]" texts in its pre-training corpus (Radford et al., 2018), thus random demonstrations can well activate LM's summarization ability without example-specific information.
Unified Demonstration Retriever for In-Context Learning
To evaluate the effect of UDR's each component, we conduct ablation study on SMCalFlow, SST-2 and Java code summarization, shown in Table 3. When removing list-wise ranking training, we use EPR's training strategy (Rubin et al., 2022). We can see that removing task instructions cause slight performance degradation, which indicates that they can help UDR distinguish examples from various tasks and thus get better task-specific features. Meanwhile, we can see that UDR has a slightly better performance than the single-task counterpart on SST-2 and Java. We suppose that is because   there are several relevant tasks in UDR's training tasks and our multi-task ranking unification can help UDR fully share these tasks' knowledge. The performance of single-task UDR still outperforms EPR significantly and this straightly reflects that our training components, i.e., list-wise ranking formulation and iterative candidate mining strategy, can 1. help UDR better incorporate LM's feedback than EPR 2. serve as a competitive universal training method for a task-specific retriever. Removing list-wise ranking training and iterative candidate mining both cause performance degradation, which straightly indicates their effectiveness.
Unified Demonstration Retriever for In-Context Learning
In  future where more competitive large-scale LM is built. When we demonstrate the example-specific demonstration transferability across different inference LMs in this paper, Li and Qiu (2023a) show that task-level demonstrations also exhibit such transferability. We leave the analysis of the transferablity of ICL's demonstrations across different LMs as future work.
Unified Demonstration Retriever for In-Context Learning
In this section we explore UDR's zero-shot transferability and evaluate it on unseen datasets including: 1. Twitter sentiment classification (Naji, 2012) 2. question-answering NLI (QNLI) (Wang et al., 2019a) 3. Ruby and JavaScript code summarization (Lu et al., 2021). These domains or programming languages (Twitter, NLI on QA, Ruby and Javascript) are never seen during UDR's training and thus can straightly reflect UDR's zero-shot transferability. We compare UDR with two powerful universal retrievers, BM25 and SBERT, and show the result in Table 5. We can see UDR significantly outperforms BM25 and SBERT on these unseen datasets by about 10 points on average, which shows that the learned ranking knowledge inside UDR can be well transferred and generalized to unseen datasets.
Unified Demonstration Retriever for In-Context Learning
Previous work (Lu et al., 2022) has revealed that ICL is sensitive to demonstrations' order when using random examples. Specifically, the same randomly sampled demonstrations with different orders can lead to the performance between random guess and near state-of-the-art. Here we explore the effect of ordering on example-specific demonstrations retrieved by UDR. We compare 3 demonstrations' orders: 1. random, for this setting, we run experiments with 10 different random seeds and report the best and worst performance. 2. descending sorted by UDR's score, i.e, the demonstration which has the highest similarity with x test is put at the beginning of LM's input. 3. ascending sorted by UDR's score, opposite to "2". The result is shown in Table 6. We  observe a different phenomenon from that in previous work (Lu et al., 2022). In general, The performance of UDR's demonstrations with different orders is more stable than previously investigated random examples. Across these tasks, different orders' performance gap is within 1 point, and it is far less than the performance fluctuation of up to tens points when using random examples (Lu et al., 2022). This indicates that high-quality demonstrations are less sensitive to the ordering and stabilize in-context learning, which is consistent with the analysis in previous work (Chen et al., 2022; Li and Qiu, 2023a).
Unified Demonstration Retriever for In-Context Learning
We compare UDR with BM25 and EPR under different amounts of demonstrations on two classification tasks: Yelp and RTE, and two generation tasks: WikiAuto and Java code summarization. We show results in Figure 3. We can see that UDR outperforms baselines consistently across varying amounts of demonstrations. Meanwhile, we can draw two conclusions from the results: 1. The number of demonstrations has a greater impact on generation tasks than classification tasks. Specifically, as the number of demonstrations increases, generation tasks' performance gets significant improvements while classification tasks' has slight or no improvements. 2. The quality of demonstrations can be more important than their quantity. In detail, UDR with the quota of 2 demonstrations still outperforms BM25 and EPR with 8 demonstrations. This also reflects the strong demonstration retrieval ability of UDR. Li and Qiu (2023b) observe the similar trends in the CoT-retrieval scenario, indicating that the relevance of the used reasoning paths is more important than their quantity.
Unified Demonstration Retriever for In-Context Learning
In this paper, we propose UDR, a single multi-task model for a wide range of tasks' demonstration retrieval. To train UDR, we cast various tasks' training into a unified list-wise ranking formulation by language model's feedback, and propose a multitask list-wise ranking training framework, with an iterative mining strategy to find high-quality candidates. Experiments on 30+ tasks show that UDR significantly outperforms baselines. Further analyses show the effectiveness of each proposed component and UDR's strong ability in various scenarios including different LMs (1.3B ∼ 175B), unseen datasets, varying demonstration quantities, etc.
Unified Demonstration Retriever for In-Context Learning
We illustrate this paper's limitations from the following three aspects: 1) Limited by the computational resources, we only train UDR from the initialization of "BERT base uncased" following EPR (Rubin et al., 2022). We regard explorations based on other competitive pre-trained models like RoBERTa (Liu et al., 2019) and DeBERTa (He et al., 2021) as future work.
Unified Demonstration Retriever for In-Context Learning
2) Most of current dense demonstration retriev-ers, including UDR, are black-box models. Although they lead to significantly better performance than BM25, how they find informative demonstrations is still unknown. Therefore, a better understanding of the principle of informative demonstration's retrieval or an interpretable and transparent demonstration retriever may be the next stage of improving demonstration retrieval. Xu et al. (2023) propose a more explainable method, beyond-context learning, which first uses the language model to get training data's next word probability distribution, then assigns test instances with labels of their nearest neighbors with similar next word's probability distribution. We leave demonstration retrieval with better explainability as future work.
Unified Demonstration Retriever for In-Context Learning
3) In the training stage we use LM to score candidates separately but in the inference stage LM is provided with a sequence of demonstrations. Although experimental results demonstrate UDR's effectiveness, we think it is a promising direction to model the dependence between different demonstrations and leave it to future work.  
Unified Demonstration Retriever for In-Context Learning
We show each task's 1. input/output domain 2. statistics and evaluation metric 3. instruction, inference template and example cases in Table 9, 10 and 11, respectively. For the dataset which has publicly available test data, we use the test data for evaluation, like SST-2, SST-5, MTOP, etc. For the others like BREAK and SMCalFlow, we follow previous work (Rubin et al., 2022) and use the dev data for evaluation. For training efficiency, we manually limit the training examples of UDR. Specifically, for the classification task whose training set size is > 30000, we randomly sample a 30000 subset for UDR's training. For the generation task whose training set size is > 100000, we randomly sample a 100000 subset for UDR's training. In the pilot experiment, we find such a strategy will not cause significant performance degradation. At the inference stage, we use the full training set as demonstrations' pool. Restricted by computational resources, we randomly sample a test set of 3000 samples for evaluation on these tasks: Amazon, Yelp, AGNews DBPedia and Yahoo.
Unified Demonstration Retriever for In-Context Learning
We follow Rubin et al. (2022)   initialize E q and E d as two separate "BERT base uncased" encoders (Devlin et al., 2019). Thus the total number of parameters of UDR is about 220M. We use 8 NVIDIA A100s-80GB to train UDR for up to 30 epochs before iteratively mining candidates. And then we train UDR for 10 epochs at each iteration. The whole training pipeline including scoring candidates takes about 8 days. In the pilot experiment, we select the number of training epochs through the average performance on validation set on single-task SST-2, TREC, MTOP, Java code summarization, WikiAuto and DART. We set the number of iterations as 3. We follow EPR (Rubin et al., 2022) to set learning rate and batch size as 1e-4 and 128 and we use AdamW (Loshchilov and Hutter, 2019) as the optimizer. We list the overall hyper-parameters in Table 8. On each task, we use one specific template for scoring and inference (see Table 11). For fair comparison, we train DR-Target, EPR and UDR under the same hyperparameter and report their average performance under three random seeds.
Unified Demonstration Retriever for In-Context Learning
The initialization of UDR's candidates For classification and multi-choice tasks, we initialize candidates as those examples that have similar input with x by BM25. For generation tasks, similarly, we initialize candidates as those of similar targets with x's, inspired by previous work (Rubin et al., 2022).
Unified Demonstration Retriever for In-Context Learning
The Quantity of EPR's Candidates Since UDR's training needs to score iteratively mined candidates and thus has to score more candidates than EPR, we also run experiments on EPR with the same candidate quantities of UDR. But we find increasing the candidates of EPR instead slightly hurts its overall performance, which is consistent with its original paper (Rubin et al., 2022). Thus for EPR, we use the same number of candidates as its original paper.
Unified Demonstration Retriever for In-Context Learning
For UDR, we use one specific template when scoring candidates and here we evaluate UDR's transferability across different inference templates on MR, Yahoo and Subj. The results are shown in Table 7. We can see that the performance gap across various inference templates is smaller than 1 point and this reflects UDR's stability and transferability across different inference templates.  Generate a sentence using these concepts: counter, pizza, restaurant Generated sentence: Two men standing at counters assembling pizzas in a restaurant. Generate a sentence using these concepts: counter, restaurant, stand Generated sentence: A man stands behind the counter of a restaurant. · · · Generate a sentence using these concepts: field, look, stand Generated sentence: Output:
Unified Demonstration Retriever for In-Context Learning
The player stood in the field looking at the batter.
Unified Demonstration Retriever for In-Context Learning
Task: Roc Story Task Instruction: Beginning of the story: Inference Template: Input:
Unified Demonstration Retriever for In-Context Learning
Beginning of the story: Taylor had been up all night memorizing lines for the play.
Unified Demonstration Retriever for In-Context Learning
Rest of the story: She knew that most of the girls in her class would be auditioning too. She watched the other girls stumble over their lines. She took a deep breath before going up on stage with a smile. All her lines were delivered perfectly and she got the part. Beginning of the story: Gabby was proud to be given the lead role in the school play.
Unified Demonstration Retriever for In-Context Learning
Rest of the story: She had worked hard on her audition piece. She worked hard to memorize her lines for the play. When the show opened, she stood on the stage and took it all in. She loved the feeling of performing. · · · Beginning of the story: Natalie had auditioned for the lead in the school play.
Unified Demonstration Retriever for In-Context Learning
Rest of the story: Output: She won the part and was super excited. She rehearsed for weeks and weeks. On opening night, she acted her little heart out. The play was a huge success! Simplify the text: Stanton went on to write some of the most influential books , documents , and speeches of the women 's rights movement . Simplified text: Together they wrote speeches , articles , and books . Simplify the text: When she was eighteen and without a university education , she began writing for the newspaper " Exce lsior " , doing interviews and society columns . Simplified text: She began writing for the newspaper " Exce lsior " , doing interviews and society columns . · · · Simplify the text: Together with James, she compiled crosswords for several newspapers and magazines, including People, and it was in 1978 that they launched their own publishing company. Simplified text: Output: Together with James, she compiled crosswords. It was for several newspapers and magazines, including People. They launched their own publishing company. It was in 1978.  
Learning To Retrieve Prompts for In-Context Learning
The striking language skills and world knowledge embedded in large pre-trained language models (LMs) (Devlin et al., 2019;Petroni et al., 2019;Raffel et al., 2020;Brown et al., 2020) have recently led to in-context learning, a new paradigm in natural language understanding. Under this paradigm, a language model is given a prompt, which typically contains a few training examples, as well as a test instance as input, and generates the output for the test instance directly, without any update to its parameters. This approach was first introduced in GPT-3 (Brown et al., 2020), but has quickly spread to other LMs (Lieber et al., 2021;Du et al., 2021;Rae et al., 2021).
Learning To Retrieve Prompts for In-Context Learning
An attractive property of in-context learning is that it provides a single model for multiple language understanding tasks. However, Liu et al.
Learning To Retrieve Prompts for In-Context Learning
What is the longest river in the smallest state in the usa? 1) states 2) size of #1 3) #1 where #2 is the lowest 4) rivers of #3 5) how long are #4 6) #4 where #5 is the highest Which states border the shortest river in the usa? 1) the usa 2) rivers of #1 3) how long are #2 4) #2 where #3 is the lowest 5) border states of #4 Which states border the longest river in the usa? 1) the usa 2) rivers of #1 3) how long are #2 4) #2 where #3 is the highest 5) border states of #4 (2021a) showed that downstream performance can vary widely depending on the choice of in-context examples. This has sparked interest in prompt retrieval (see Fig. 1), where given a test instance, training examples are chosen for the prompt based on some similarity metric. Recent work has either used off-the-shelf unsupervised similarity metrics, or trained a prompt retriever to select examples based on surface similarity (Das et al., 2021).
Learning To Retrieve Prompts for In-Context Learning
In this work, we suggest to use language models themselves to label examples that can serve as good prompts, and train a prompt retriever from this signal. To train the retriever (see Fig. 2), we assume access to a training set of input-output pairs and to a scoring LM, i.e., a language model that will be used to score prompts. For each training example (x, y), we go over other candidate training examples, and estimate the probability, according to the scoring LM, of y conditioned on x and the candidate prompt. We label training examples that lead to high probability as positive and low probability as negative and train a prompt retriever D Figure 2: An overview of our approach for training EPR. Given a training example, we use an unsupervised retriever R u to obtain a set of candidates. We then pass the candidates to a scoring LM and label the top-k and the bottom-k as positive and negative examples, respectively. Last, we use this training data to train a dense retriever. from this data using contrastive learning. We argue that using an LM for labeling examples is a better proxy for training a retriever compared to previously-proposed surface similarity heuristics. Importantly, when creating the training data, we have access to the gold label y, which can be used to obtain a high-quality set of candidate prompts. This leads to good positive examples and hard negative examples, which are beneficial for training with a contrastive objective.
Learning To Retrieve Prompts for In-Context Learning
Using a scoring LM to train an efficient retriever for a potentially different test time inference LM is beneficial in two scenarios. First, when the scoring LM is smaller than the inference LM and serves as a proxy for it. This results in cheap and efficient data generation for the retriever, accessible to a wide range of researchers. Second, our approach can be used even when the scoring and inference LMs are identical (e.g., both are GPT-3). This is beneficial when we do not have access to model parameters and can only use it as a service, an increasingly popular paradigm. In this case, we use the LM to train a light-weight retriever that is only tasked with learning a similarity function. More generally, given that the scale of LMs is likely to keep increasing in the foreseeable future, one can view our approach for Efficient Prompt Retrieval, or EPR, as a method for interfacing and learning to interact with large LMs.
Learning To Retrieve Prompts for In-Context Learning
We empirically test EPR on three structured sequence-to-sequence tasks, where input natural language utterances are mapped to a meaning representation: MTOP  and SM-CALFLOW (Andreas et al., 2020), which focus on task-oriented dialogue, and BREAK (Wolfson et al., 2020), a benchmark for mapping questions to a language-based meaning representation. We observe that EPR substantially improves performance compared to prior work on prompt retrieval. When the scoring LM and inference LM are identical (using GPT-NEO ), performance compared to the best baseline improves from 26% to 31.9% on BREAK, from 57% to 64.2% on MTOP, and from 51.4% to 54.3% on SMCALFLOW. When using GPT-NEO as a proxy for larger LMs (GPT-J, GPT-3, and CODEX), we observe similar gains, where performance improves substantially in all cases.
Learning To Retrieve Prompts for In-Context Learning
To conclude, we propose an approach for retrieving training examples for in-context learning in large language models, and show it substantially outperforms prior methods. Given recent developments in scaling LMs, designing efficient methods for interacting with LMs is an important direction for future research.
Learning To Retrieve Prompts for In-Context Learning
2 Background: Prompt Retrieval Problem setup Given a training set D = {(x i , y i )} n i=1 of input-output sequences, and a test example x test , our goal is to train a retriever, R(x test , D), that will retrieve a subset of training examples P = {(x j , y j )} m j=1 ⊂ D, where m ≪ n. We succinctly refer to P as the prompt. 1 Given an inference LM, g, a good prompt should lead to the target output sequence when the test example x test is concatenated to the prompt P and passed as a prefix to g. Specifically, decoding from the LM g([P; x test ]) should yield y test . In this work, we focus on structured tasks, such as semantic parsing, where x is a natural language utterance and y is a meaning representation for that utterance.
Learning To Retrieve Prompts for In-Context Learning
Prior work Liu et al. (2021a) investigated the effect of different prompts on the performance of GPT-3 and demonstrated that the choice of incontext examples strongly affects downstream performance. They used an unsupervised sentence encoder to encode training examples, and retrieved for every test instance its nearest neighbors. Das et al. (2021) trained a supervised prompt retriever for knowledge-base question answering. The retriever was trained with supervision that is tailored for knowledge-base queries, and relies on surface similarity between formal queries. Conversely, our approach takes advantage of the generative LM itself and is thus more general. Shin et al. (2021) used GPT-3 to select examples for the prompt for few-shot semantic parsing. However, rather than training a retriever, they randomly sample a large set of utterance-program pairs from the training set, and choose those that are similar to the target instance question according to GPT-3. This results in an expensive inference procedure, where GPT-3 is run hundreds of times for each test instance, unlike our approach, which is based on a light-weight sub-linear retriever.
Learning To Retrieve Prompts for In-Context Learning
We now describe our method for training EPR, an efficient prompt retriever for in-context learning. We first describe how to generate labeled data ( §3.1), and then how to use the training data for training and inference ( §3.2). Fig. 2 provides an overview of the training procedure.
Learning To Retrieve Prompts for In-Context Learning
Our approach relies on finding which training examples can serve as good prompts for other training examples. Scoring all pairs of training examples is quadratic in |D|, and thus prohibitive. Hence, we present a method for choosing a set of candidate ex-amplesĒ ⊂ D, from which we will choose positive and negative examples for training. Importantly, since we are not at test time and are only generating data for training, we can use the target sequence y to retrieve a good set of candidates. This can be approached using a simple retrieval method, given that our goal is to retrieve examples that are similar to the input in terms of their output sequence, y.
Learning To Retrieve Prompts for In-Context Learning
To obtain a high-quality candidate set of training examples, we take advantage of an unsupervised retriever,Ē = R u ((x, y), D). For the choice of the unsupervised retriever, we experiment with BM25 (Robertson and Zaragoza, 2009), a sparse retriever that relies on surface text similarity, and SBERT (Reimers and Gurevych, 2019), which is based on dense sentence encoding. For both, we experimented with passing the retriever the training pair (x, y) or the target sequence y only, and found that using y leads to slightly higher performance.
Learning To Retrieve Prompts for In-Context Learning
Scoring the candidate set Once we retrieve the set of candidatesĒ = {ē 1 , · · · ,ē L } for a training example (x, y), 2 we score each candidateē l ∈Ē independently with a scoring LM,ĝ, which serves as a proxy for the inference LM, g. Specifically, the score for a candidate prompt is s(ē l ) = Probĝ(y |ē l , x), which is the probability under the LM,ĝ, of the output sequence conditioned on the candidate prompt and input sequence. This indicates how helpful this candidate is for decoding the target (independent of all other candidates). We argue this score is a better proxy for the utility of a training example at inference time compared to prior approaches.
Learning To Retrieve Prompts for In-Context Learning
We apply this scoring function to all training examples, and define for each training example a set of positive examples E pos , which includes the top-k candidates inĒ according to s(ē l ), and a set of negative examples E neg , which includes the bottom-k candidates inĒ according to s(ē l ). This should lead to relevant positive examples, assuming that the set of candidates,Ē includes good prompt candidates and hard negatives, since all candidates have high similarity with (x, y) according to R u (y, D). With positive and negative examples at our disposal, we can now apply contrastive learning, which we describe next.
Learning To Retrieve Prompts for In-Context Learning
Training Our training procedure proceeds exactly like the contrastive learning procedure from DPR . This procedure results in an input encoder E X (·), which receives the sequence of input tokens, x, and a prompt encoder E P (·), which receives a candidate prompt, namely, a concatenation of the tokens in an input-output pair. Both encoders are initialized with BERT-base (Devlin et al., 2019), and the output vector representation is given by the CLS token, as usual. The goal of training is to learn a similarity metric such that given a test example x test , it will be similar to training examples that lead to decoding of y test .
Learning To Retrieve Prompts for In-Context Learning
Our training instances are of the form
Learning To Retrieve Prompts for In-Context Learning
Where the positive example e + i is sampled from the set E We define the similarity score between an input and an input-output pair to be the inner product sim(x, e) = E X (x) ⊤ E P (e). We can now define the typical contrastive learning objective and minimize for each example the negative log likelihood of the positive example:
Learning To Retrieve Prompts for In-Context Learning
.
Learning To Retrieve Prompts for In-Context Learning
An advantage of this approach is that for batch size B the effective batch size is of order B 2 , with the in-batch negatives trick (Henderson et al., 2017).
Learning To Retrieve Prompts for In-Context Learning
Inference After training the input encoder and prompt encoder, we encode the entire set of training examples with E P (·) in a pre-processing step using FAISS (Johnson et al., 2017). At test time, given an input sequence, x test , we compute its encoding E X (x test ), and then use maximum innerproduct search over the training data to find the L most similar training examples, sorted by their inner product (from high to low): P = (e 1 , . . . , e L ). The final prompt P ′ is determined by C, the maximal context size supported by the inference LM,
Learning To Retrieve Prompts for In-Context Learning
where |y ′ | is the desired maximal length of the generated output. Finally, we return the output of greedy decoding on g([e L ′ ; e L ′ −1 ; . . . ; e 1 ; x test ]).
Learning To Retrieve Prompts for In-Context Learning
We note that while at training time we score each training example independently, at test time the language model observes a prompt, i.e., a sequence of examples. We leave modeling the dependence between different training examples to future work.
Learning To Retrieve Prompts for In-Context Learning
We now compare EPR to a wide range of unsupervised and supervised baselines, both when the scoring LM,ĝ, is smaller than the inference LM, g, and when they are identical.
Learning To Retrieve Prompts for In-Context Learning
We focus on tasks that map utterances to meaning representations, where in-context examples can be used to learn the mapping from inputs to outputs. Examples from each dataset and the number of examples are in Table 1 
Learning To Retrieve Prompts for In-Context Learning
We consider the following unsupervised baselines, which are applied at test time only.
Learning To Retrieve Prompts for In-Context Learning
• RANDOM: we randomly sample examples from the training set D.  (Thursday))))))) Next, we describe baselines that use the training set, D, to train a prompt retriever. All supervised methods share the following template. First, a candidate setĒ of L = 50 examples is retrieved with the unsupervised retriever R u (y, D). We use BM25 as an unsupervised retriever, since it outperformed SBERT (see §4.4). We then score each candidate promptē l ∈Ē with some scoring function, and label the top-k prompts as positive examples and the bottom-k as negative examples (k = 5). Different supervised methods only differ in the scoring function itself. 4 • DR-BM25: Here, we use the original BM25 scores for labeling positive and negative examples and training a dense retriever.
Learning To Retrieve Prompts for In-Context Learning
• CASE-BASED REASONING (CBR): We adapt the scoring function from Das et al. (2021), which focused on knowledge-base question answering. They define the weight for a pair of logical forms to be the F 1 score between the two sets of relations appearing in those logical forms, and use this weight to softly label their data. Since in our setting we do not assume logical forms, we define the score between two output sequence y i and y j to be the F 1 between the two sets of tokens in y i and y j , omitting stop words. 
Learning To Retrieve Prompts for In-Context Learning
Language models In this work, we only train a dense retriever, but use scoring and inference LMs. For our scoring LM,ĝ, we use GPT-NEO , a 2.7B-parameter LM trained on The Pile , an 825 GB English text corpus, constructed from a wide range of highquality resources.
Learning To Retrieve Prompts for In-Context Learning
In addition, we consider the following inference LMs: (a) GPT-J (Wang and Komatsuzaki, 2021): a 6B-parameter LM, also trained on The Pile. The advantage in this setup, is that GPT-J was trained on the same corpus as GPT-NEO. (b) GPT-3 (Brown et al., 2020)   For all LMs, we use a maximum context size of C =2,048 tokens.
Learning To Retrieve Prompts for In-Context Learning
Evaluation On BREAK, we evaluate performance on the development set with LF-EM (Hasson and Berant, 2021), which is a better metric compared to Normalized Exact Match (NEM), the official metric, as it measures whether two meaning representations are semantically equivalent. On the test set, we use NEM. On MTOP and SM-CALFLOW, we evaluate with Exact Match (EM), i.e., whether the string output by the inference LM is identical to the reference string.
Learning To Retrieve Prompts for In-Context Learning
We evaluate EPR in two settings: (a) LM-as-aservice, and (b) LM-as-a-proxy. In the first setting, we use GPT-NEO as both the scoring LM and inference LM. In this setting, we evaluate on the full development sets of BREAK, MTOP, and SMCALFLOW. In the latter setting, as we access GPT-3 and CODEX through a paid API, we sample a random subset of 1,000 development examples from each dataset and evaluate each model once on this subset.
Learning To Retrieve Prompts for In-Context Learning
One-shot Full-context  
Learning To Retrieve Prompts for In-Context Learning
LM-as-a-service Interestingly, EPR outperforms BM25-ORACLE on MTOP and SMCALFLOW and is comparable on BREAK. This is surprising since BM25-ORACLE has access to the output sequence y test at test time, illustrating that the signal provided by the scoring LM for training goes beyond surface text similarity. The performance of LM-ORACLE is substantially higher than EPR, showing that the supervision provided by the scoring LM is strong, and training a better retriever from this signal can substantially enhance performance.
Learning To Retrieve Prompts for In-Context Learning
We further evaluate our models in the one-shot setup, i.e., when the prompt given to the inference LM includes the highest scoring example only. In this setup, the inference LM is applied in the same setting as when we generate labeled data, where we go over each prompt candidate independently.   Since train and test time are now closer, we can expect the advantage of EPR to be more pronounced. Table 4 shows the results. Indeed, EPR outperforms the best baseline by 8.5%, and BM25-ORACLE by 5%. In addition, we examine ANYCORRECT-ORACLE, which tests whether any of the candidates returned by BM25 leads to the correct output. ANYCORRECT-ORACLE reaches 53.6%, 20 points above LM-ORACLE. This shows the high quality of candidates provided by BM25 (applied on the y), as one can reach more than 50% LF-EM with just a single prompt. Moreover, it hints that a better scoring function can potentially further improve performance. Table 5 shows results when the scoring LM is GPT-NEO and the inference LM is a larger LM. First, the trends are similar to the LM-as-a-service setup, i.e., EPR substantially outperforms prior baselines, including our best unsupervised baseline, BM25, and the best supervised baseline, CBR, by 2-8 points on all datasets and all pretrained models. Thus, GPT-NEO serves as a good proxy for choosing training examples.
Learning To Retrieve Prompts for In-Context Learning
To further validate this finding, we evaluate the performance of GPT-J on BREAK with GPT-NEO as the scoring LM compared to using GPT-J itself as the scoring LM. We find performance improves slightly from 31.5 to 33.6. Analogously, when using CODEX as the scoring LM and inference LM performance remains roughly the same: 29.5→29.3. Thus, using a smaller LM (GPT-NEO) is an effective strategy for training a retriever that will be applied on other LMs. Zooming in on different inference LMs, GPT-J performs slightly better than GPT-NEO across the board, since it was trained on the same data and using the same procedure as GPT-NEO. CODEX outperforms GPT-3, which can be explained by the fact that it was trained on code, and our datasets involve mapping to programs or meaning representations. Surprisingly, GPT-J outperforms CODEX (except on MTOP) and GPT-3 despite being 30x smaller. This can perhaps be explained by the fact that GPT-J was trained on a different dataset (The Pile   Table 7: Accuracy comparison between the decoded instances that contained patterns from the prompt and novel instances those that don't. Results shown are on the LM-as-a-service setup using GPT-NEO.
Learning To Retrieve Prompts for In-Context Learning
Analysis Table 6 shows an example from BREAK where EPR decodes the correct output, while CBR does not. All training examples retrieved by EPR perform an argmax (argmin in the original utterance), and return in the final step "a code", while the third example retrieved by CBR does not perform an argmax or argmin, and do not involve "a code". We provide additional examples in App. A. Figure 3 shows a t-SNE (Hinton and Roweis, 2002) projection of the embeddings learned by EPR for the training examples of BREAK, with a link to an interactive version, where we applied the OPTICS (Ankerst et al., 1999;Schubert and Gertz, 2018) Figure 4: On the subset of copied patterns we plot the distribution of the distance from the test instance to the example containing the pattern. Shown on the BREAK validation set using EPR in the LM-as-a-service setup using GPT-NEO. Note that the y-axis is in log-scale.
Learning To Retrieve Prompts for In-Context Learning
shows that EPR captures both lexical and structure similarity. Examples for clusters are also available in App. A.
Learning To Retrieve Prompts for In-Context Learning
Prompt copying We analyze how the LM utilizes in-context prompts. Specifically, is the target output copied from one of the prompts or is it a composition of different prompt fragments, which result in generalization to new structures.
Learning To Retrieve Prompts for In-Context Learning
To achieve this, we define two types of copying. (a) Exact copying measures if the generated output exactly matches one of the examples in the prompt, and (b) Abstract copying, that quantifies if the structure of the decoded output matches any of the structures seen in the prompt. Specifically, we eliminate the effect of non-structural elements such as entities and function arguments. We replace every sequence of words in the logical form that appears in the input utterance with the string [MASKED] for both the target utterance and incontext examples. If the masked logical form that the LM decoded appears in the set of masked examples defined by the prompt, we say that the LM copied that abstract pattern. Table 7 presents the results on the validation set for each of our three datasets, as well as the accuracy on each subset. We observe that the rate of copying is much higher in MTOP and SM-CALFLOW compared to BREAK, where in MTOP and SMCALFLOW abstract copying reaches more than 80%. Moreover, accuracy on examples where copying occurred is much higher compared to accuracy where no copying happened. For example, on MTOP, 84.5% of the examples were abstractly copied, and on that subset of examples, EPR achieves 71.6% EM, compared to 64.2% on the entire validation set. Nevertheless, even though accuracy is much lower in cases where no copying occurred, accuracy is not negligible, which shows that some form of generalization to new structures is taking place.
Learning To Retrieve Prompts for In-Context Learning
Another follow-up question is whether the model copies patterns from prompts uniformly or does it attend mostly to the ones with high retrieval score.
Learning To Retrieve Prompts for In-Context Learning
To answer this, we look at the subset of examples where copying occurred. We then identify for each example the highest-ranking prompt that was copied from, and define the distance of that prompt by dividing the rank by the number of prompts that fit in that example. Figure 4 shows the distribution over distances for the BREAK dataset. We observe that copying happens mostly from highly-ranked prompts.
Learning To Retrieve Prompts for In-Context Learning
Large pre-trained LMs are becoming an inseparable part of the natural language understanding ecosystem. However, accessing their weights or updating them can be prohibitive for many researchers. In this work, we propose EPR, a method for learning to retrieve good prompts for in-context learning, by using language models themselves as the scoring function. This allows us to train a light-weight retriever and substantially improve performance on three challenging tasks.
Learning To Retrieve Prompts for In-Context Learning
More broadly, given that large LMs models are likely to play a prominent role in developing language understanding models, it is important to develop approaches for interacting with such models effectively. EPR can be viewed as a step in this direction.
Learning To Retrieve Prompts for In-Context Learning
Council (ERC) under the European Union Horizons 2020 research and innovation programme (grant ERC DELPHI 802800). This work was completed in partial fulfillment for the Ph.D degree of Ohad Rubin. Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2022 Effect of hyperparameters We test the effect of k, the number of prompts labeled as positive or negative, and L, the number of prompts retrieved by the unsupervised retriever.  Risk assessment Large language models have been shown to exhibit various kinds of bias (Bender et al., 2021), since EPR is trained on the signal obtained from such large LMs, it might also exhibit these biases.
Learning To Retrieve Prompts for In-Context Learning
Additional examples Tables 9, 10, and 11 provide more examples for cases where EPR is correct while CBR is incorrect along with the top-3 prompts for each method.     2669 Utterance
Learning To Retrieve Prompts for In-Context Learning
List the total scores of body builders in ascending order. 1#) return body builders 2#) return scores of #1 3#) return sum of #2 for each #1 4#) return #3 sorted by ascending order What are the names of body builders in descending order of total scores? 1#) return body builders 2#) return names of #1 3#) return scores of #1 4#) return sum of #3 for each #1 5#) return #2 sorted by #4 in descending order List the total points of gymnasts in descending order.
Learning To Retrieve Prompts for In-Context Learning
1#) return gymnasts 2#) return points of #1 3#) return sum of #2 for each #1 4#) return #3 sorted by descending order What are the total points for all gymnasts, ordered by total points descending?
Learning To Retrieve Prompts for In-Context Learning
1#) return gymnasts 2#) return total points for all #1 3#) return #2 ordered by total points descending List the total points of gymnasts in descending order of floor exercise points.
Learning To Retrieve Prompts for In-Context Learning
1#) return gymnasts 2#) return points of #1 3#) return sum of #2 for each #1 4#) return floor exercise points of #1 5#) return #3 sorted by #4 in descending order Table 13: Example of a cluster from the t-SNE projection of EPR on BREAK.
Learning To Retrieve Prompts for In-Context Learning
Show the locations that have both performances with more than 2000 attendees and performances with less than 1000 attendees.
Learning To Retrieve Prompts for In-Context Learning
1#) return performances 2#) return attendees of #1 3#) return the number of #2 for each #1 4#) return #1 where #3 is more than 2000 5#) return #1 where #3 is less than 1000 6#) return the locations of #4 7#) return the locations of #5 8#) return the locations in both #6 and #7 Show the theme for exhibitions with both records of an attendance below 100 and above 500.
Learning To Retrieve Prompts for In-Context Learning
1#) return exhibitions 2#) return attendances of #1 3#) return number of #2 for each #1 4#) return #1 where #3 is below 100 5#) return #1 where #3 is above 500 6#) return #1 of both #4 and #5 7#) return themes for #6 Which themes have had corresponding exhibitions that have had attendance both below 100 and above 500?
Learning To Retrieve Prompts for In-Context Learning
1#) return themes 2#) return exhibitions with #1 3#) return attendances of #2 4#) return #1 where #3 is lower than 100 5#) return #1 where #3 is higher than 500 6#) return #1 of both #4 and #5 Show the publishers that have publications with price higher than 10000000 and publications with price lower than 5000000.
Learning To Retrieve Prompts for In-Context Learning
1#) return publishers 2#) return publications of #1 3#) return prices of #2 4#) return #1 where #3 is higher than 10000000 5#) return #1 where #3 is lower than 5000000 6#) return #1 of both #4 and #5 Show the famous titles of the artists with both volumes that lasted more than 2 weeks on top and volumes that lasted less than 2 weeks on top.
Learning To Retrieve Prompts for In-Context Learning
1#) return artists 2#) return volumes of #1 3#) return weeks on top that #2 lasted 4#) return number of #3 for each #2 5#) return #1 where #4 is more than 2 6#) return #1 where #4 is less than 2 7#) return #1 in both #5 and #6 8#) return famous titles of #7 
Learning To Retrieve Prompts for In-Context Learning
What is the metal thing next to the small cylinder?
Learning To Retrieve Prompts for In-Context Learning
1#) return the small cylinder 2#) return things 3#) return #2 that are metal 4#) return #3 that are next to #1 What is the purple thing next to the brown thing?
Learning To Retrieve Prompts for In-Context Learning
1#) return the brown thing 2#) return things 3#) return #2 that are purple 4#) return #3 that are next to #1 What is the gray thing next to the block?
Learning To Retrieve Prompts for In-Context Learning
1#) return gray thing 2#) return the block 3#) return #1 next to #2 What is the shiny thing next to the cylinder?
Learning To Retrieve Prompts for In-Context Learning
1#) return shiny thing 2#) return cylinder 3#) return #1 next to #2 What is the thing in front of the red square?
Learning To Retrieve Prompts for In-Context Learning
1#) return things 2#) return squares 3#) return #2 that is red 4#) return #1 that is in front of #3 Is the purple thing behind the big red thing? 1#) return purple thing 2#) return big red thing 3#) return Is #1 behind #2 is the purple sphere in front of the blue cube?
Learning To Retrieve Prompts for In-Context Learning
1#) return the purple sphere 2#) return the blue cube 3#) return if #1 is in front of #2 is the gray sphere behind the green cylinder?
Learning To Retrieve Prompts for In-Context Learning
1#) return the green cylinder 2#) return the gray sphere 3#) return if #2 is behind #1 is the red cube in front of the yellow ball?
Learning To Retrieve Prompts for In-Context Learning
1#) return the red cube 2#) return the yellow ball 3#) return if #1 is in front of #2 Is the blue ball in front of the silver cube?
Learning To Retrieve Prompts for In-Context Learning
1#) return blue ball 2#) return silver cube 3#) return is #1 in front of #2 
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Humans often solve a new problem by recollecting and adapting the solution to multiple related problems that they have encountered in the past (Ross, 1984;Lancaster and Kolodner, 1987;Schmidt et al., 1990). In classical artificial intelligence (AI), case-based reasoning (CBR) pioneered by Schank (1982), tries to incorporate such model of reasoning in AI systems (Kolodner, 1983;Rissland, 1983;Leake, 1996). A sketch of a CBR system (Aamodt and Plaza, 1994) comprises of -(i) a retrieval module, in which 'cases' that are similar to the given problem are retrieved, (ii) a reuse module, where the solutions of the retrieved cases are reused to synthesize a new solution. Often, the new solution does not work and needs more revision, which is handled by a (iii) revise module.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
In its early days, the components of CBR were implemented with symbolic systems, which had their limitations. For example, finding similar cases and synthesizing new solutions from them is a challenging task for a CBR system implemented with symbolic components. However, with the recent advancements in representation learning (LeCun et al., 2015), the performance of ML systems have improved substantially on a range of practical tasks.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Given a query, CBR-KBQA uses a neural retriever to retrieve other similar queries (and their logical forms) from a case memory (e.g. training set). Next, CBR-KBQA generates a logical form for the given query by learning to reuse various components of the logical forms of the retrieved cases. However, often the generated logical form does not produce the right answer when executed against a knowledge base (KB). This can happen because one or more KB relations needed are never present in the retrieved cases or because KBs are woefully incomplete (Min et al., 2013) (Figure 1). To alleviate such cases, CBR-KBQA has an additional revise step that aligns the generated relations in the logical form to the query entities' local neighborhood in the KB. To achieve this, we take advantage of pre-trained relation embeddings from KB completion techniques (e.g. Trans-E (Bordes et al., 2013)) that learn the structure of the KB.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
It has been shown that neural seq2seq models do not generalize well to novel combinations of previously seen input (Lake and Baroni, 2018;Loula et al., 2018). However, CBR-KBQA has the ability to reuse relations from multiple retrieved cases, even if each case contains only partial logic to answer the query. We show that CBR-KBQA is effec-tive for questions that need novel combination of KB relations, achieving competitive results on multiple KBQA benchmarks such as WebQuestionsSP (Yih et al., 2016), ComplexWebQuestions (CWQ) (Talmor and Berant, 2018) and CompositionalFree-baseQuestions (CFQ) (Keysers et al., 2020). For example, on the hidden test-set of the challenging CWQ dataset, CBR-KBQA outperforms the best system by over 11% points.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
We further demonstrate that CBR-KBQA, without the need of any further fine-tuning, also generalizes to queries that need relations which were never seen in the training set. This is possible due to CBR-KBQA's nonparametric approach which allows one to inject relevant simple cases during inference, allowing it to reuse new relations from those cases. In a controlled human-in-the-loop experiment, we show that CBR-KBQA can correctly answer such questions when an expert (e.g. database administrator) injects a few simple cases to the case memory. CBR-KBQA is able to retrieve those examples from the memory and use the unseen relations to compose new logical forms for the given query.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Generalization to unseen KB relations, without any re-training, is out of scope for current neural models. Currently, the popular approach to handle such cases is to re-train or fine-tune the model on new examples. This process is not only time-consuming and laborious but models also suffer from catastrophic forgetting (Hinton and Plaut, 1987;Kirkpatrick et al., 2017), making wrong predictions on examples which it previously predicted correctly. We believe that the controllable properties of CBR-KBQA are essential for QA models to be deployed in real-world settings and hope that our work will inspire further research in this direction.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Recent works such as REALM (Guu et al., 2020) and RAG (Lewis et al., 2020b) retrieve relevant paragraphs from a nonparametric memory for answering questions. CBR-KBQA, in contrast, retrieves similar queries w.r.t the input query and uses the relational similarity between their logical forms to derive a logical form for the new query. CBR-KBQA is also similar to the recent retrieve and edit framework (Hashimoto et al., 2018) for generating structured output. However, unlike us they condition on only a single retrieved example and hence is unlikely to be able to handle complex questions that need reuse of partial logic from multiple questions. Moreover, unlike CBR-KBQA, retrieve and edit does not have a component that can explicitly revise an initially generated output.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
The contributions of our paper are as follows -(a) We present a neural CBR approach for KBQA capable of generating complex logical forms conditioned on similar retrieved questions and their logical forms. (b) Since CBR-KBQA explicitly learns to reuse cases, we show it is able to generalize to unseen relations at test time, when relevant cases are provided. (c) We also show the efficacy of our revise step of CBR-KBQA which allows to correct generated output by aligning it to local neighborhood of the query entity. (d) Lastly, we show that CBR-KBQA significantly outperforms other competitive models on several KBQA benchmarks.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
This section describes the implementation of various modules of CBR-KBQA. In CBR, a case is defined as an abstract representation of a problem along with its solution. In our KBQA setting, a case is a natural language query paired with an executable logical form. The practical importance of KBQA has led to the creation of an array of recent datasets (Zelle and Mooney, 1996;Bordes et al., 2015;Su et al., 2016;Yih et al., 2016;Zhong et al., 2017a;Ngomo, 2018;Yu et al., 2018;Talmor and Berant, 2018, inter-alia). In these datasets, a question is paired with an executable logical form such as SPARQL, SQL, S-expression or graph query. All of these forms have equal representational capacity and are interchangeable (Su et al., 2016). Figure 2 shows an example of two equivalent logical forms. For our experiments, we consider SPARQL programs as our logical form. Formal definition of task: let q be a natural language query and let K be a symbolic KB that needs to be queried to retrieve an answer list A containing the answer(s) for q. We also assume access to a training set D = {(q 1 , 1 ), (q 2 , 2 ), . . . (q N , N )} of queries and their corresponding logical forms where q i , i represents query and its corresponding logical form, respectively. A logical form is an executable query containing entities, relations and free variables ( Figure 2). CBR-KBQA first retrieves K similar cases D q from D ( § 2.1). It then generates a intermediate logical form inter by learning to reuse components of the logical forms of the retrieved cases ( § 2.2). Next, the logical form inter is revised to output the final logical form by aligning to the relations present in the neighborhood subgraph of the query entity to recover from any spurious relations generated in the reuse step ( § 2.3). Finally, is executed against K and the list of answer entities are returned. We evaluate our KBQA system by calculating the accuracy of the retrieved answer list w.r.t a held-out set of queries.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
The retrieval module computes dense representation of the given query and uses it to retrieve other similar query representation from a training set. Inspired by the recent advances in neural dense passage retrieval (Das et al., 2019;Karpukhin et al., 2020), we use a ROBERTA-base encoder to encode each question independently. Also, we want to retrieve questions that have high relational similarity instead of questions which share the same entities (e.g. we prefer to score the query pair (Who is Justin Bieber's brother?, Who is Rihanna's brother?), higher than (Who is Justin Bieber's brother?, Who is Justin Bieber's father?)). To minimize the effect of entities during retrieval, we use a named entity tagger 1 to detect spans of entities and mask them with [BLANK] symbol with a probability p mask , during training. The entity masking strategy has previously been successfully used in learning entity-independent relational representations (Soares et al., 2019). The similarity score between two queries is given by the inner product between their normalized vector representations (cosine similarity), where each representation, following standard practice (Guu et al., 2020), is obtained from the encoding of the initial [CLS] token of the query.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Fine-tuning question retriever: In passage retrieval, training data is gathered via distant supervision in which passages containing the answer is marked as a positive example for training. Since in our setup, we need to retrieve similar questions, we use the available logical forms as a source of distant supervision. Specifically, a question pair is weighed by the amount of overlap (w.r.t KB relations) it has in their corresponding logical queries. Following DPR (Karpukhin et al., 2020), we ensure there is at least one positive example for each query during training and use a weighted negative log-likelihood loss where the weights are computed by the F 1 score between the set of relations present in the corresponding logical forms. Concretely, let (q 1 , q 2 , . . . , q B ) denote all questions in a minibatch. The loss function is:
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Here, q i ∈ R d denotes the vector representation of query q i and sim(q i , q j ) = q i q j . w i,j is computed as the F 1 overlap between relations in the logical pairs of q i and q j . We pre-compute and cache the query representations of the training set D. For query q, we return the top-k similar queries in D w.r.t q and pass it to the reuse module.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
The reuse step generates an intermediate logical form from the k cases that are fed to it as input from the retriever module. Pre-trained encoderdecoder transformer models such as BART (Lewis et al., 2020a)   . We take a similar approach in generating an intermediate logical form conditioned on the retrieved cases. However, one of the core limitation of transformer-based models is its quadratic dependency (in terms of memory), because of full-attention, which severely limits the sequence length it can operate on. For example, BART and T5 only supports sequence length of 512 tokens in its encoder. Recall that for us, a case is a query from the train set and an executable SPARQL program, which can be arbitrarily long.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
To increase the number of input cases, we leverage a recently proposed sparse-attention transformer architecture -BIGBIRD (Zaheer et al., 2020). Instead of having each token attend to all input tokens as in a standard transformer, each token attends to only nearby tokens. Additionally, a small set of global tokens attend to all tokens in the input. This reduces the transformer's memory complexity from quadratic to linear, and empirically, BIGBIRD enables us to use many more cases.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Description of input: The input query q and cases D q = {(q 1 , 1 ), (q 2 , 2 ), . . . (q k , k )} are concatenated on the encoder side.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Specifically,
Case-based Reasoning for Natural Language Queries over Knowledge Bases
where [SEP] denotes the standard separator token. Each logical form also contain the KB entity id of each entities in the question (e.g. m.03_r3 for Jamaica in Figure 2). We append the entity id after the surface form of the entity mention in the question string. For example, the query in Figure 2 becomes "What do Jamaican m.03_r3 people speak?".
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Training is done using a standard seq2seq crossentropy objective. Large deep neural networks usually benefit from "good" initialization points (Frankle and Carbin, 2019) and being able to utilize pre-trained weights is critical for seq2seq models. We find it helpful to have a regularization term that minimizes the Kullback-Leibler divergence (KLD) between output softmax layers of (1) when only the query q is presented (i.e not using cases), and (2) when query and cases (D q ) are available (Yu et al., 2013). Formally, let f be the seq2seq model, let σ = sof tmax(f (q, D q )) and σ = sof tmax(f (q)) be the decoder's prediction distribution with and without cases, respectively. The following KLD term is added to the seq2seq cross-entropy loss
Case-based Reasoning for Natural Language Queries over Knowledge Bases
where λ T ∈ [0, 1] is a hyper-parameter. Intuitively, this term regularizes the prediction of f (q, D q ) not to deviate too far away from that of the f (q) and we found this to work better than initializing with a model not using cases.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
In the previous step, the model explicitly reuses the relations present in D q , nonetheless, there is no guarantee that the query relations in D q will contain the relations required to answer the original query q. This can happen when the domain of q and domain of cases in D q are different even when the relations are semantically similar. For example, in Figure 1 although the retrieved relations in NN queries are semantically similar, there is a domain mismatch (person v/s fictional characters). Similarly, large KBs are very incomplete (Min et al., 2013), so querying with a valid relation might require an edge that is missing in the KB leading to intermediate logical forms which do not execute.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
To alleviate this problem and to make the queries executable, we explicitly align the generated relations with relations (edges) present in the local neighborhood of the query entity in the KG. We propose the following alignment models:
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Using pre-trained KB embeddings: KB completion is an extensively studied research field (Nickel et al., 2011;Bordes et al., 2013;Socher et al., 2013;Velickovic et al., 2018;Sun et al., 2019b) and several methods have been developed that learn low dimensional representation of relations such that similar relations are closer to each other in the embedding space. We take advantage of the pre-trained relations obtained from TransE (Bordes et al., 2013), a widely used model for KB completion. For each predicted relation, we find the most similar (outgoing or incoming) relation edge (in terms of cosine similarity) that exists in the KB for that entity and align with it. If the predicted edge exists in the KB, it trivially aligns with itself. There can be multiple missing edges that needs alignment ( Figure 1) and we find it more effective to do beam-search instead of greedy-matching the most similar edge at each step.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Using similarity in surface forms: Similar relations (even across domains) have overlap in their surface forms (e.g. 'siblings' is common term in both 'person.siblings' and 'fic-tional_character.siblings'). Therefore, word embeddings obtained by encoding these words should be similar. This observation has been successfully utilized in previous works (Toutanova and Chen, 2015;Hwang et al., 2019). We similarly encode the predicted relation and all the outgoing or incoming edges with ROBERTA-base model. Following standard practices, relation strings are prepended with a [CLS] token and the word pieces are encoded with the ROBERTA-base model and the output embedding of the [CLS] token is considered as the relation representation. Similarity between two relation representations is computed by cosine similarity.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Our alignment is simple and requires no learning. By aligning only to individual edges in the KB, we make sure that we do not change the structure of the generated LF. We leave the exploration of learning to align single edges in the program to sequence of edges (paths) in the KB as future work.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Data: For all our experiments, the underlying KB is full Freebase containing over 45 million entities (nodes) and 3 billion facts (edges) (Bollacker et al., 2008). We test CBR-KBQA on three datasets -We-  Hyperparameters: All hyperparameters are set by tuning on the valdation set for each dataset. We initialize our retriever with the pre-trained ROBERTAbase weights. We set p mask = 0.2 for CWQ and 0.5 for the remaining datasets. We use a BIGBIRD generator network with 6 encoding and 6 decoding sparse-attention layers, which we initialize with pre-trained BART-base weights. We use k=20 cases and decode with a beam size of 5. Initial learning rate is set to 5 × 10 −5 and is decayed linearly through training. Further details for the EMNLP reproducibility checklist is given in §A.2.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
The first step required to generate an executable LF for a NL query is to identify and link the entities present in the query. For our experiments, we use a combination of an off-the-shelf entity linker and a large mapping of mentions to surface forms. For the off-the-shelf linker, we use a recently proposed high precision entity linker ELQ . To further improve recall of our system, we first identify mention spans of entities in the question by tagging it with a NER 2 system. Next, we link entities not linked by ELQ by exact matching with surface form annotated in FACC1 project (Gabrilovich et al., 2013). Our entity linking results are shown in Table 2.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
This section reports the performance of CBR-KBQA on various benchmarks. We report the strict exact match accuracy where we compare the list of predicted answers by executing the generated SPARQL program to the list of gold answers 3 . A question is answered correctly if the two list match exactly. We also report the precision, recall and the F1 score to be comparable to the baselines. Models such as GraftNet (Sun et al., 2018)   2019a) rank answer entities and return the top entity as answer (Hits@1 in table 1). This is undesirable for questions that have multiple entities as answers (e.g. "Name the countries bordering the U.S.?").
Case-based Reasoning for Natural Language Queries over Knowledge Bases
We also report performance of models that only depend on the query and answer pair during training and do not depend on LF supervision (weaklysupervised setting). Unsurprisingly, models trained with explicit LF supervision perform better than weakly supervised models. Our main baseline is a massive pre-trained seq2seq model with orders of magnitude more number of parameters -T5-11B (Raffel et al., 2020). T5 has recently been shown to be effective for compositional KBQA (Furrer et al., 2020). For each dataset, we fine-tune the T5 model on the query and the LF pairs. Table 1 reports results of various models on We-bQSP. All reported model except CBR-KBQA and T5-11B directly operate on the KB (e.g. traverse KB paths starting from the query entity) to generate the LF or the answer. As a result, models such as STAGG tend to enjoy much higher recall. On the other hand, much of our logical query is generated by reusing components of similar cases. We also report the results of 'aligning' the LF produced by T5 using our revise step. As shown in Table 1, CBR-KBQA outperforms all other models significantly and improves on the strict exact-match accuracy by more than 6 points w.r.t. the best model. Revise step also improves on the performance of T5 suggesting that it is generally applicable. Table 3 reports performance on the hidden test set of CWQ 4 , which was built by extending WebQSP 4 The result of our model in the official leaderboard (https://www.tau-nlp.org/ compwebq-leaderboard) is higher (70.4 vs 67.1). This is because the official evaluation script assigns full score if any of the correct answer entities are returned even if there are multiple correct answers for a question. In the paper we report strict exact-match accuracy.  questions with the goal of making a more complex multi-hop questions. It is encouraging to see that CBR-KBQA outperforms all other baselines on this challenging dataset by a significant margin. Finally, we report results on CFQ in Table 4. On error analysis, we found that on several questions which are yes/no type, our model was predicting the list of correct entities instead of predicting a yes or no. We created a rule-based binary classifier that predicts the type of question (yes/no or other). If the question was predicted as a yes/no, we would output a yes if the length of the predicted answer list was greater than zero and no otherwise. (If the model was already predicting a yes/no, we keep the original answer unchanged). We report results on all the three MCD splits of the dataset and compare with the T5-11B model of Furrer et al.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
(2020) and we find that our model outperforms T5-11B on this dataset as well. It is encouraging to see that CBR-KBQA, even though containing order-of-magnitudes less parameters than T5-11B, outperforms it on all benchmarks showing that it is possible for smaller models with less carbon footprint and added reasoning capabilities to outperform massive pre-trained LMs. Table 5 show that the revise step is useful for CBR-KBQA on multiple datasets. We also show that the T5 model also benefits from the alignment in revise step with more than 3 points improvement in F1 score on the CWQ dataset. We find that TransE alignment outperforms ROBERTA based alignment, suggesting that graph structure information is more useful than surface form similarity for aligning relations. Moreover, relation names are usually short strings, so they do not provide enough context for LMs to form good representations. Next we demonstrate the advantage of the nonparametric property of CBR-KBQA-ability to fix an initial wrong prediction by allowing new cases to be injected to the case-memory. This allows CBR-KBQA to generalize to queries which needs relation never seen during training. Due to space constraints, we report other results (e.g. retriever performance), ablations and other analysis in §B.  
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Modern QA systems built on top of large LMs do not provide us the opportunity to debug an erroneous prediction. The current approach is to finetune the model on new data. However, this process is time-consuming and impractical for production settings. Moreover, it has been shown (and as we will empirically demonstrate) that this approach leads to catastrophic forgetting where the model forgets what it had learned before. (McCloskey and Cohen, 1989;Kirkpatrick et al., 2017). On the other hand, CBR-KBQA adopts a nonparametric approach and allows inspection of the retrieved nearest neighbors for a query. Moreover, one could inject a new relevant case into the case-memory (KNN-index), which could be picked up by the retriever and used by the reuse module to fix an erroneous prediction.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
We consider the case when the model generates a wrong LF for a given query. We create a controlled setup by removing all queries from the training set of WebQSP which contain the (people.person.education) relation. This led to a removal of 136 queries from the train set and ensured that the model failed to correctly answer the 86 queries (held-out) in the test set which contained the removed relation in its LF. We compare to a baseline transformer model (which do not use cases) as our baseline. As shown in Table 6, both baseline and CBR-KBQA do not perform well without any relevant cases since a required KB relation was missing during training. Next, we add the 136 training instances back to the training set and recompute the KNN index. This process involves encoding the newly added NL queries and recomputing the KNN index, a process which is computationally much cheaper than re-training the model again. Row 5 in Table 6 What colors do the school where Donald Stanley Marshall is grad student use? shows the new result. On addition of the new cases, CBR-KBQA can seamlessly use them and copy the unseen relation to predict the correct LF, reaching 70.6% accuracy on the 86 held-out queries.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
In contrast, the baseline transformer must be fine-tuned on the new cases to handle the new relation, which is computationally more expensive than adding the cases to our index. Moreover, just finetuning on the new instances leads to catastrophic forgetting as seen in row 2 of Table 6 where the baseline model's performance on the initial set decreases drastically. We find it necessary to carefully fine-tune the model on new examples alongside original training examples (in a 1:2 proportion). However, it still converges to a performance which is lower than its original performance and much lower than the performance of CBR-KBQA.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
During error analysis, we realized that there are queries in the test set of WebQSP that contain KB relations in their LFs which were never seen during training 5 . That means models will never be able to predict the correct LF for the query because of the unseen relation. We conduct a human-inthe-loop experiment (Figure 3)     NL query paired with a program which only contain one KB relation.  Table 14 in Appendix D shows various statistics of the missing relations and the number of cases added by humans and from SimpleQuestions. The cases are added to the original KNN-index. By adding a few cases, the performance increases from 0 to 36 F1 (Table 7) without requiring any training. Note unlike the previous controlled experiment in §3.4.1, we add around 3.87 cases for each unseen relation 6 . Importance of this result: We believe that flexibility of models to fix predictions (without training) is an important desideratum for QA systems deployed in production settings and we hope our results will inspire future research in this direction.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
We analyze questions in the evaluation set which require novel combinations of relations never seen in 6 In §3.4.1, we added 136 cases (v/s 3.87) for one relation. This is why the accuracy in Table 6 is higher w.r.t Table 7   the training set. This means, in order for our model to answer these questions correctly, it would have to retrieve relevant nearest neighbor (NN) questions from the training set and copy the required relations from the logical form of multiple NN queries. Table 8 shows that our model outperforms the competitive T5 baseline. Also as we saw in the last section, our model is able to quickly adapt to relations never seen in the training set altogether by picking them up from newly added cases. We also compare with a model with the same reuse component of CBR-KBQA but is trained and tested without retrieving any cases from the casememory (Table 9). Even though the baseline model is competitive, having similar cases is beneficial, especially for the WebQSP dataset. We also report the results when we only use cross-entropy loss for training the BIGBIRD model and not the KLdivergence term. Table 10 reports the performance of CBR-KBQA using different number of retrieved cases. It is encouraging to see the the performance improves with increasing number of cases.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
To the best of our knowledge, we are the first to propose a neuralized CBR approach for KBQA. We showed that our model is effective in handling complex questions over KBs, but our work also has several limitations. First, our model relies on the availability of supervised logical forms such as SPARQL queries, which can be expensive to annotate at scale. In the future, we plan to explore ways to directly learn from question-answer pairs (Berant et al., 2013;Liang et al., 2016). Even though, CBR-KBQA is modular and has several advantages, the retrieve and reuse components of our model are trained separately. In future, we plan to explore avenues for end to end learning for CBR.  
Case-based Reasoning for Natural Language Queries over Knowledge Bases
The WebQSP dataset does not contain a validation split, so we choose 300 training instances to form the validation set. We use grid-search (unless explicitly mentioned) to set the hyperparameters listed below. Case Retriever: We initialize our retriever with the pre-trained ROBERTA-base weights. We set the initial learning rate to 5 × 10 −5 and decay it linearly throughout training. We evaluate the retriever based on the percentage of gold LF relations in the LFs of the top-k retrieved cases (recall@k). We train for 10 epochs and use the best checkpoint based on recall@20 on the validation set. We set train and validation batch sizes to 32. For p mask , we try values from [0, 0.2, 0.4, 0.5, 0.7, 0.9, 1]. When training the retriever, we found p mask = 0.2 works best for COMPLEXWEBQUES-TIONS and p mask = 0.5 for the remaining datasets.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Seq2Seq Generator: We use a BIGBIRD generator network with 6 encoding and 6 decoding sparse-attention layers, which we initialize with
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Validation Acc WebQSP 71.5 CWQ 82.8 CFQ 69.9 Table 12: Validation set accuracy of models corresponding to the results reported in the paper pre-trained BART-base weights. We set the initial learning rate to 5 × 10 −5 and decay it linearly throughout training. Accuracy after the execution of generated programs on the validation set is used to select the optimal setting and model checkpoint.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
For λ T , we perform random search in range [0, 1]. We finally use λ T =1.0 for all datasets. For k (number of cases), we search over the values [1,3,5,7,10,20]. For all datasets, we use k=20 cases and decode with a beam size of 5 for decoding. The WebQSP model was trained for 15K gradient steps and all other models were trained for 40K gradient steps.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Computing infrastructure: We perform our experiments on a GPU cluster managed by SLURM. The case retriever was trained and evaluated on NVIDIA GeForce RTX 2080 Ti GPU. The models for the Reuse step were trained and evaluated on NVIDIA GeForce RTX 8000 GPUs. Revise runs on NVIDIA GeForce RTX 2080 Ti GPU when using ROBERTA for alignment and runs only on CPU when using TRANSE. We report validation set scores in Table 12.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
We compare the performance of our trained retriever with a ROBERTA-base model. We found that ROBERTA model even without any fine-tuning performs well at retrieval. However, fine-tuning ROBERTA with our distant supervision objective improved the overall recall, e.g., from 86.6% to 90.4% on WEBQUESTIONSSP and from 94.8% to 98.4% on CFQ.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
In Table 7 we showed CBR-KBQA is effective for unseen relations. But what about unseen entities in the test set?. On analysis we found that in WebQSP, CBR-KBQA can copy unseen entities correctly 86.8% (539/621) from the question. This is +1.9% improvement from baseline trans-former model which is able to copy correctly 84.9% (527/621) of the time. Note that unseen entities can be copied from the input NL query and we do not need additional cases to be injected to KNN index.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
In the revise step, we attempt to fix programs predicted by our reuse step that did not execute on the knowledge base. The predicted program can be syntactically incorrect or enforce conditions that lead to an unsatisfiable query. In our work, we focus on predicted programs that can be fixed by aligning clauses to relations in the local neighborhood of query entities. We give examples of successful alignments Table 16 as well as failed attempts at alignment Table 17.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
In this section, we include more details about our held-out experiment described in section 3.4.1. The goal of this experiment is to show that our approach can generalize to unseen relations without requiring any further training of the model. This is a relevant setting to explore, because real-world knowledge bases are often updated with new kinds of relations, and we would like KBQA systems that adapt to handle new information with minimal effort.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
We explicitly hold-out all questions containing a particular relation from the datasets. Table 13 shows the relation type and the number of questions that are removed as a result of removing the relation.  
Case-based Reasoning for Natural Language Queries over Knowledge Bases
While conducting analysis, we also noticed that WebQSP has queries in the test set for which the required relations are never present in the training set. This gives us an opportunity to conduct real human-in-the-loop experiments to demonstrate the advantage of our model. To add more cases, we resort to a mix of automated data collection and human-in-the-loop strategy. For each of the missing relation, we first try to find NL queries present  . Sim-pleQuestions (SQ) is a large dataset containing more than 100K NL questions that are 'simple' in nature -i.e. each NL query maps to a single relation (fact) in the Freebase KB. For each missing relation type, we try to find questions in the SQ dataset that can be mapped to the missing relation. However, even SQ has missing coverage in which case, we manually generate a question and its corresponding SPARQL query by reading the description of the relation. Table 14 shows the number of questions in the evaluation set which at least has a relation never seen during training and also the number of cases that has been added. For example, we 7 were able to collect 292 questions from SQ and we manually created 72 questions for WebQSP. Overall, we add 3.87 new cases per query relation for WebQSP. Table 15 shows some example of cases added manually or from SQ. We look up entity ids for entities from the FACC1 alias table ( §3.1). Also note, that since we only add questions which are simple in nature, the corresponding SPARQL query can be easily constructed from the missing relation type and the entity id.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Importance of this result: Through this experiment, we demonstrate two important properties of our model -interpretability and controllability. Database schemas keep changing and new tables keep getting added to a corporate database. When our QA system gets a query wrong, by looking at the retrieved K-nearest neighbors, users can deter-    (2020) recently proposed a meta-learning approach which utilizes cases retrieved w.r.t. the similarity of the input. However, their main goal is to learn a better parametric model (retriever and generator) from neighboring cases rather than composing and fixing cases to generate answers at test time.
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Question Decomposition One strategy to answer a complex question is to first break it down into simpler subquestions, each of which can be viewed as a natural language program describing how to answer the question. This approach has been shown to be effective as far back as IBM Watson (Ferrucci et al., 2010) to more recent systems for answering questions about text (Das et al., 2019;Min et al., 2019;Perez et al., 2020;Wolfson et al., 2020) or knowledge bases (Talmor and Berant, 2018). These prior studies do not leverage case-based reasoning when generating decompositions and thus may also benefit from similar techniques as proposed in our work.
In-Context Learning for Few-Shot Dialogue State Tracking
Dialogue state tracking (DST) is an important module in many task-oriented dialogue systems. The goal of this module is to extract users' intentions at each turn in the dialogue as represented in the slot values of a predefined schema. Collecting and annotating turn-level dialogue states is notoriously hard and expensive (Budzianowski et al., 2018). Also, in commercial applications, it is common to extend the schema and incorporate new domains. Thus, it is important to develop DST learning strategies that are flexible and scalable, in addition to requiring less data.
In-Context Learning for Few-Shot Dialogue State Tracking
Previous studies have explored zero/few-shot DST, but with some limitations. Most few-shot methods are based on finetuning pretrained language models (Wu et al., 2020;Su 1 Our code : https://github.com/Yushi-Hu/IC-DST  Figure 1: Illustration of DST task and IC-DST approach. The task is to track the slot values associated with a user request up to the current turn (dialogue state). In few-shot settings, given a test turn (1), IC-DST first retrieves a few most similar turns from the labeled dialogues as examples (2). The task schema (not shown in the figure), examples, and the test dialogue turn are concatenated in the prompt to a LM (e.g. GPT3) (3) to produce the current turn dialogue state changes as a SQL query (4). Lin et al., 2021b;Xie et al., 2022). Such systems are less flexible, since they need to be retrained when new slots or domains are added, and finetuning large LMs is computationally expensive. Most zero-shot methods have involved domain-transfer approaches (Hosseini-Asl et al., 2020;Lin et al., 2021b,a), which have not yielded good performance.
In-Context Learning for Few-Shot Dialogue State Tracking
To address the above challenges, we propose the IC-DST model to solve the DST problem with the in-context learning (ICL) paradigm (Brown et al., 2020), in which a large language model makes predictions based on the task instruction and/or examples in the prompt. In few-shot settings, the prompt contains exemplars that are retrieved from a small set of labeled training data. A motivation behind this framework is that it requires no fine-tuning (i.e., no parameter updates), which makes systems flexible in that they can handle queries in a new domain via the exemplar retrieval process without re-training. This enables developers to quickly prototype systems in new domains and rapidly leverage new collected data. ICL has been used successfully in semantic parsing (Rajkumar et al., 2022;Rubin et al., 2022), especially in few-shot scenarios. However, these studies focus on sentence-level tasks. ICL has been explored for DST (Madotto et al., 2021;Xie et al., 2022), but the performance fell short of pretraining and domain-transfer approaches to few/zero-shot learning. DST involves long, two-party dialogue histories with grounding in a structured ontology. We believe these challenges cause the poor ICL performance on DST tasks in previous work.
In-Context Learning for Few-Shot Dialogue State Tracking
To address these challenges, we explore incontext learning with three novel contributions. First, we reformulate DST as a text-to-SQL task, including a tabular description of the ontology in the prompt. This is a better match to the knowledgegrounded scenario, and it takes advantage of large language models pretrained with code: Codex (Chen et al., 2021), GPT-Neo (Black et al., 2021), andCodeGen (Nijkamp et al., 2022). Second, we use the dialogue state in representing context, rather than the full conversation history, which is more efficient and better suited to domain changes. Lastly, in the few-shot scenario, we propose a new approach to learning a similarity score for selecting in-context examples that is trained to match similarity based on dialogue state changes. The IC-DST approach, which incorporates these advances, achieves a new state of the art on MultiWOZ fewshot settings, i.e. when using 1-10% training data. We also substantially improve the zero-shot state of the art by 10-30% absolute accuracy on each domain. A further contribution is an extensive analysis demonstrating impact from each innovation.
In-Context Learning for Few-Shot Dialogue State Tracking
In summary, our work makes the following contributions:
In-Context Learning for Few-Shot Dialogue State Tracking
• To our knowledge, we are the first to successfully apply in-context learning for DST, building on a text-to-SQL approach.
In-Context Learning for Few-Shot Dialogue State Tracking
• To extend in-context learning to dialogues, we introduce an efficient representation for the dialogue history and a new objective for dialogue retriever design.
In-Context Learning for Few-Shot Dialogue State Tracking
• Our system achieves a new state of the art on MultiWOZ in zero/few-shot settings.
In-Context Learning for Few-Shot Dialogue State Tracking
• We provide insights into how in-context learning works for dialogue, including the importance of good in-context examples and the LM's ability to generalize beyond examples.
In-Context Learning for Few-Shot Dialogue State Tracking
Notation A task-oriented dialogue consists of a sequence of utterances alternating between the user and the system, A 1 , U 1 , ..., A T , U T , where A and U represent the system and user utterances, respectively. The task of DST is to predict the dialogue state y t at each turn t, 2 given the dialogue context
In-Context Learning for Few-Shot Dialogue State Tracking
where y t is a set of slot-value pairs:
In-Context Learning for Few-Shot Dialogue State Tracking
The set of possible slots s i is given in a pre-defined schema. The schema can contain multiple domains, where a "domain" corresponds to a backend capability such as hotel or restaurant booking. Each domain is associated with a set of slots; for example, the 'hotel' domain has slots 'hotel-name', 'hotel-price_range,' 'hotel-area', etc. Each observed slot is associated with a value, which may have predefined categories (e.g., 'hotel-price_range' may be 'cheap, ' 'moderate,' or 'expensive') or open (e.g. 'hotel-name'). We focus on a multi-domain scenario in this work, in which dialogue states may contain slots from multiple domains. One popular way to generate the dialogue states for the current turn is finetuning auto-regressive language models (Hosseini-Asl et al., 2020;Peng et al., 2021). For each turn, the model takes the dialogue context C t as input, and generates a sequence of slot-value pairs (s i , v i ) sequentially. Equivalently, one can generate a sequence of slot-value pair dialogue state changes.
In-Context Learning for Few-Shot Dialogue State Tracking
Dialogue states vs. state changes Dialogues can be lengthy and complex, resulting in dialogue states that can include several slots and values, which means that coverage of the possible states is sparse for few-shot learning. However, the dialogue state change from one turn to the next typically involves a small number of slots. For that reason, we use state changes at each turn as a label for prediction. Figure 2: Illustration of the dialogue context representation: the full dialogue context C t−1 before the current turn is replaced by the associated dialogue state y t−1 .
In-Context Learning for Few-Shot Dialogue State Tracking
The concept of state changes is illustrated in Figure 1. Possible state changes include slot addition, slot deletion, and slot value change. For example, in the current test turn of Figure 1, the user asks for Catalan food in turn t − 1, and changes it to French food in turn t. The state change updates the dialogue state by replacing 'Catalan' with 'French'. Specifically, given the previous turn dialogue state y t−1 and the predicted current turn state changes c t , we update the dialogue state by first copying y t−1 to y t , and then executing add, delete and change operations according to each slot-value pair (s i , v i ) in c t . Our analysis in Section 5 shows that using state changes leads to substantial improvements.
In-Context Learning for Few-Shot Dialogue State Tracking
DST as Text-to-SQL Here we propose a new representation for dialogue states: SQL. This is inspired by the fact that dialogue states are used to determine how to query backend databases for the information users need. Our representation follows three rules: (1) each domain is defined as a table and each slot is defined as a column; (2) all the slots and values are in the WHERE clause; and (3) for turns with multiple domains, we rename each domain to d 1 , ..., d m . Using the SQL state representation with a generative LM, DST becomes a Text-to-SQL problem. This approach is facilitated by language models pretrained with code (Codex and GPT-Neo) as SQL is closer to the code used for pre-training.
In-Context Learning for Few-Shot Dialogue State Tracking
Dialogue context representation Previous work generally represents dialogue context by concatenating all the system and user utterances A 1 , U 1 , · · · , A t , U t (Lee et al., 2021;Lin et al., 2021b;Peng et al., 2021). However, real world dialogues can be lengthy, and there is a length CREATE  limit for current large language models (2048 tokens for GPT-3, 4096 tokens for Codex). It is not practical to represent full dialogue context for multiple exemplars in the prompt. A simple solution is to just include the N recent turns in the dialogue history (Lei et al., 2018;Budzianowski and Vulić, 2019;Wu et al., 2021). We adopt a new approach that takes advantage of the fact that the dialogue state is a summary of the dialogue history, as shown in Figure 2. Specifically, we represent dialogue context by [y t−1 , A t , U t ], in which y t−1 is the accumulated dialogue state after user turn t − 1.
In-Context Learning for Few-Shot Dialogue State Tracking
In-context learning is an alternative to finetuning that keeps pretrained language model parameters fixed (Brown et al., 2020). The language model takes a prompt P that contains task descriptions, in-context examples, and the test instance as input, and predicts the label by capturing the patterns in the context. ICL has two advantages over finetuning. First, it avoids the need for repeated finetuning when the schema is updated or new examples are added. This is particularly important for large models like GPT-3, since finetuning at this scale is extremely expensive. Second, by simply adding/removing training examples, in-context learning enables us to quickly manipulate the model's predictions and correct mistakes without re-training.
In-Context Learning for Few-Shot Dialogue State Tracking
An overview of our IC-DST system is shown in Figure 1 for the few-shot setting. The details of our We follow the table prompt from Rajkumar et al. (2022). prompt are shown in Figure 3. The task description is the schema associated with the task ontology, and a retriever is used to select labeled example turns from the training data. In the zero-shot setting, there is no retriever.
In-Context Learning for Few-Shot Dialogue State Tracking
Schema prompting We use an SQL table for each domain to represent the dialogue schema in the prompt. Each table includes a row of slot names followed by three rows of example values associated with each slot, as illustrated in Figure 4. Slots like "restaurant-name" or "restaurant-book time" typically have many possible values. Thus, for these slots, we only list a few example values. In our experiments, we create SQL tables for all domains and concatenate them to be part of our input.
In-Context Learning for Few-Shot Dialogue State Tracking
In the few-shot scenario, a retriever takes the dialogue context as input (either
In-Context Learning for Few-Shot Dialogue State Tracking
and retrieves similar example contexts from the labeled training set. Advantages of using the dialogue state y t−1 rather than the full history C t−1 are that it is shorter (allowing for more examples) and it leads to a more effective retrieval similarity score. In the zero-shot scenario, following previous work on zero-shot learning , the incontext example is a formatting example turn. We call this setting "zero shot" because the prompt is fixed by the system developer and does not use any labeled data. Prompt examples for the few-shot and zero-shot settings are given in Appendices A.1 and A.2, respectively.
In-Context Learning for Few-Shot Dialogue State Tracking
In few-shot settings, successful prediction of incontext learning relies on the quality of the context examples. Usually this is accomplished by semantic retrieval using the testing input as the query. Previous studies have explored methods for building sentence-level retrievers (Poesia et al., 2022;Rubin et al., 2022). Our work goes beyond sen-tences to retrieving dialogue histories (contexts).
In-Context Learning for Few-Shot Dialogue State Tracking
We want to retrieve example dialogue contexts that are relevant for the predicted state change of a test sample. Formally, suppose X = {(e i , c i )} is a dataset of dialogue context e i and corresponding state change c i pairs. Each labeled turn in a dialogue is a candidate. Given a test dialogue context x, our goal is to retrieve k examples {(e 1 , c 1 ), (e 2 , c 2 ), · · · , (e k , c k )} such that c 1 , c 2 , · · · , c k should be similar to the state changes associated with x.
In-Context Learning for Few-Shot Dialogue State Tracking
Unsupervised retriever One approach is to use a pretrained embedding model with a cosine similarity score as the retriever. This approach does not need any DST data. Let M be an embedding model. For each test example x, we retrieve the k training examples such that e i , e 2 , · · · , e k are the nearest neighbors of x * , given by a similarity score,
In-Context Learning for Few-Shot Dialogue State Tracking
We experiment with RoBERTa (Liu et al., 2019) and SBERT (Reimers and Gurevych, 2019) as embedding models. We also try BM25 (Robertson and Zaragoza, 2009), a retriever based on surface text similarity. We find SBERT leads to the best result; therefore, all IC-DST results reported here use SBERT as the retriever.
In-Context Learning for Few-Shot Dialogue State Tracking
Retriever finetuning We also finetune SBERT on the few-shot examples to get a retriever that is better matched to the objective of predicting state changes. We first define the similarity between state changes. Suppose there are two sets of state changes,
In-Context Learning for Few-Shot Dialogue State Tracking
Let F (set 1 , set 2 ) be the average of two F 1 scores calculated by using set 1 vs. set 2 as the target. Here we use the standard definition F 1 = 2P R P +R , in which P is precision, and R is recall. We define the slot similarity as
In-Context Learning for Few-Shot Dialogue State Tracking
and the slot-value pair similarity as
In-Context Learning for Few-Shot Dialogue State Tracking
Then the similarity between c a and c b is
In-Context Learning for Few-Shot Dialogue State Tracking
The positive and negative examples for training sample x i = (e i , c i ) are identified by computing s(c i , c j ) for each sample x j = (e j , c j ), sorting, and taking the k highest and lowest scoring samples, respectively. We finetune the embedding model M with a contrastive loss so that the similarity between a positive example pair is high and the similarity between a negative example pair is low. 
In-Context Learning for Few-Shot Dialogue State Tracking
TRADE (Wu et al., 2019) An encoder-decoder framework is applied to the DST problem, enabling generalization to unseen values and domains. This was the first work to explore cross-domain transfer in DST. Different from IC-DST, TRADE has to make a prediction for each domain and slot pair in separate passes.
In-Context Learning for Few-Shot Dialogue State Tracking
In SGP-DST, schema information is used as a prompt to query a sequence-to-sequence language model (e.g., T5). It achieves SOTA on MultiWOZ 2.2. Similar to TRADE, the value for each domain and slot pair is predicted in a separate pass.
In-Context Learning for Few-Shot Dialogue State Tracking
TransferQA (Lin et al., 2021a) TransferQA reformulated DST as QA problem. It is the stateof-the-art model for zero-shot DST. The model is pretrained with a large amount of QA data. At inference time, the model predicts slot values by taking synthesized extractive questions as input.
In-Context Learning for Few-Shot Dialogue State Tracking
DS2  In DS2, DST is reformulated as a dialogue summarization problem. Sequence-to-sequence language models are trained with synthetic summary templates. The dialogue states can be recovered by reversing the template generation rules. This is by far the strongest fewshot model in the literature, outperforming recent few-shot models like T5-DST (Lin et al., 2021b). However, different from us, this model still requires finetuning on DST labels.
In-Context Learning for Few-Shot Dialogue State Tracking
Few-shot setting We follow the multi-domain scenario from Wu et al. (2020), where 1%, 5%, and 10% of training data are sampled as the selection pool. The retriever is fine-tuned on the selection pool and does not see any other DST data.
In-Context Learning for Few-Shot Dialogue State Tracking
Zero-shot setting There are no labeled examples to retrieve, but a single formatting example turn is included, following previous zero-shot learning work .
In-Context Learning for Few-Shot Dialogue State Tracking
Language models GPT3 (Brown et al., 2020) is a language model with 175B parameters pretrained on a large web corpus. It demonstrates strong zeroshot results on language modeling benchmarks. Its successor, Codex (Chen et al., 2021), is pretrained using open-source code from Github. 4 This enables interesting applications such as code completion. In our initial studies, as in (Shin and Van Durme, 2022), Codex substantially outperforms GPT3; therefore, we use Codex for the following experiments. In this paper, we use Codex-Davinci. 5 In addition, we report results using GPT-Neo (2.7B) (Black et al., 2021) and CodeGen (2.7B) (Nijkamp et al., 2022). They are both pretrained on Pile (Gao et al., 2020a) and open-source code.
In-Context Learning for Few-Shot Dialogue State Tracking
Evaluation The standard joint goal accuracy (JGA) is used as the evaluation metric. It treats a prediction as correct only if for every domain all slots exactly match the ground-truth values. To be consistent with prior work (Wu et al., 2019), we report all-domain JGA on few-shot settings and per-domain JGA on zero-shot settings. We also report the F 1 on slot-value pairs for analysis.
In-Context Learning for Few-Shot Dialogue State Tracking
The retriever is initialized with SBERT all-mpnet-v2 (220M). We use AdamW optimizer (Loshchilov and Hutter, 2018) and set 2 × 10 −5 as learning rate, 1000 as warmup steps. During retriever finetuning, for each training sample, we first compute similarity based on target 
In-Context Learning for Few-Shot Dialogue State Tracking
Few-shot DST on MultiWOZ Table 1 shows the result on few-shot settings and full-shot settings of our IC-DST compared with several recent baselines on MultiWOZ 2.1 and 2.4. As discussed in Section 3.1, MultiWOZ 2.4 is a clean version of MultiWOZ 2.1 and therefore the performance is better. Our system achieves state-of-the-art performance for 1%, 5%, and 10% few-shot learning settings using Codex, outperforming previous works that require model finetuning. When given more data as retrieval candidates, our systems improve. GPT-Neo and Codegen have a similar trend but are generally worse than Codex and other baselines. This suggests that the size of language model matters when deploying ICL. The prior ICL DST systems did not report on the standard few-shot configurations, so were not included as baselines. However, our system represents a significant advance over these systems as well, substantially outperforming both Unified-SKG (Xie et al., 2022) Table 2 shows the zero-shot DST results on MultiWOZ 2.1 and 2.4. Our IC-DST outperforms previous results by a large margin. In addition, IC-DST has the advantage over these approaches that no training is required. The multi-domain JGA of our IC-DST is 35.3% on MultiWOZ 2.4, which can be compared to 48.35% for the system using few-shot learning with 1% training (roughly 80 labeled dialogues). SimpleTOD++ (Hosseini-Asl et al., 2020) and T5DST (Lin et al., 2021b) are trained on four domains on MultiWOZ and tested on the unseen domain. In addition, T5DST uses human-written slot descriptions to boost zero-shot performance. TransferQA (Lin et al., 2021a) does not need any training on DST data. However, each slot has to be reformatted into a question, and the model is trained on a large amount of QA data. Our results show the flexibility of IC-DST. For each new domain or slot added, by updating the SQL tables and adding a demonstration example, the model attains good performance on the new ontology without any training.
In-Context Learning for Few-Shot Dialogue State Tracking
To better understand the effectiveness of our proposed methods, we provide detailed analysis in this section. All ablation experiments are conducted on 100 random MultiWOZ 2.4 development set dialogues in the 5% few-shot setting. Table 3 compares approaches to representing dialogue context in the examples in the prompt, with different retriever fine-tuning objectives. For each setting, we train a retriever with the given dialogue context representation and retrieval objective for a fair comparison. We experiment with representing the   dialogue history by: (1) concatenating the whole dialogue history, (2) only the latest turn (one system utterance and one user utterance), and (3) the previous dialogue states and the latest turn. For both of the retrieval objectives, representing the dialogue context by the previous dialogue state and the current turn gives the best performance. There are multiple possible explanations. First, the previous state is more relevant than the full context for predicting the next-turn dialogue state, especially after a topic shift. Second, full dialogue contexts are too long. To fit in the length limit of Codex, we sometimes need to truncate examples when using full context, which lowers the system performance, as evidenced by the fact that a single turn outperforms the full context but not the state-based representation.
In-Context Learning for Few-Shot Dialogue State Tracking
Dialogue states vs. state changes We also explore the benefit of using state change vs. full dialogue state labels (c t vs. y t ). Note that example labels also act as the basis for the similarity objective in training the retriever. Table 3 shows that using state changes gives substantial improvement. A likely reason is that state changes contain fewer slots compared with dialogue states, making for an easier prediction task for the LM. Also, there are many more example turns with the same state changes, compared with examples with the same  Table 3 row 5 (our IC-DST setting). The red line is the JGA of dialogue states produced by accumulating predicted state changes. The yellow line is the JGA of dialogue states predicted by the system on Table 3 row 2. dialogue states, making it easier for the retriever to fetch good examples in few-shot scenario. We further compare these two kinds of example labels by investigating the JGA on each turn, illustrated in Figure 5. Because states have increasing numbers of slots with more turns, JGA (red and yellow lines) of the full state decreases for later turns. However, all turns have a relatively small number of state changes, so the state change JGA (blue line) remains high throughout the dialogue. As a result, the JGA of the full state benefits from using predicted state change updates (red line, Table 3 row 5) as compared to predicting the full state (yellow line, Table 3 row 2).
In-Context Learning for Few-Shot Dialogue State Tracking
Performance dependence on the retriever Table 4 compares Codex's performance when using different retrievers. F 1 is computed over the predicted and gold full dialogue states. The "copy" baseline makes a prediction by copying the label of the nearest example retrieved by the corresponding retriever in the selection pool. This baseline gives a direct measure of the quality of the retrieved examples. First, the result shows that Codex's performance is highly dependent on the quality of the  Table 4: Comparison of different retrievers using 5% of the training data and Codex. The "copy" baseline copies the label of retrieved nearest example as prediction. The oracle retriever assumes prior knowledge of the gold test instance dialogue state.
In-Context Learning for Few-Shot Dialogue State Tracking
retrievers and their retrieved examples. We can also see that F 1 of "copy" baseline correlates with the end task performance (JGA), which supports the use of state-change F 1 as a learning objective for our similarity measure. Our finetuned SBERT retriever obtains substantial improvements over the unsupervised one. The oracle retriever fetches the examples that have the highest state change F 1 , assuming prior knowledge of test instance gold dialogue states. It shows the upper bound of the retriever performance in this few-shot setting. Note that the state-of-the-art full-shot performance on MultiWOZ 2.4 is 73.62% (Ye et al., 2021b). The oracle experiment shows that the few-shot ICL may match or outperform the state-of-the-art full-shot model with further retriever improvements. Table 4 also shows that the LM is not simply copying the example labels. For both evaluation metrics and all the retrievers, the "copy" baseline performance is much lower than IC-DST, indicating that the inference language model is generalizing over the examples, rather than copying the closest example labels.  Effect of DST as Text-to-SQL Table 5 shows the performance of our ICL framework given different input-output formats. We follow Simple-TOD (Hosseini-Asl et al., 2020) as the traditional format to formulate the input-output. More specifically, the exemplar labels and the generation target are slot-value pairs. Also, we rewrite the dialogue schema in the same format in the prompt to replace the SQL tables. The prompt in the setting is shown in Appendix A.3. By reformulating DST as a text-to-SQL task, and leveraging large language models pretrained with code, ICL can make better use of the structured knowledge associated with the task schema. As shown in Table 5, GPT-Neo, CodeGEN, and Codex all perform better with text-to-SQL format. Note that the performance of GPT-Neo with the traditional format is much worse than with the text-to-SQL format, possibly due to its much smaller model size compared to Codex. It is easier for GPT-Neo to work with SQL, rather than learning a slot value pair format.
In-Context Learning for Few-Shot Dialogue State Tracking
Error analysis In examining a subset of IC-DST errors, we identified three common types, as shown in Table 6. The first type of error is caused by a noisy training example, such as a missing slot. ICL is sensitive to noisy training data because the inference LM only sees a few examples in the prompt during prediction. The second type of error is retrieval limitations. In this case, the retrieved samples are not good exemplars, because they lack some slots that should be predicted in the test instance. This could be due to sparse annotated data (which impacts all few-shot learning methods) or a retriever error. The third type of error is failure to generalize from examples, which happens when the model fails to learn from examples.
In-Context Learning for Few-Shot Dialogue State Tracking
We successfully apply in-context learning for dialogue state tracking by introducing a new approach to representing dialogue context, a novel objective for retriever training, and by reformulating DST into a text-to-SQL task. On MultiWOZ, our system achieves a new state of the art in both few-shot and zero-shot settings. Our analyses show that each innovation benefits performance. We also study in detail the contribution of each design decision. Future work may apply this in-context learning framework to a wider range of dialogue tasks.
In-Context Learning for Few-Shot Dialogue State Tracking
This research was supported in part by funding from Allstate. We thank OpenAI for free access to Codex and Amazon for AWS credits.
In-Context Learning for Few-Shot Dialogue State Tracking
The performance of our framework is highly dependent on the inference language model, which may limit the framework's usage. For example, our framework may not work as well on speech recognition transcripts or other languages because of the lack of such data during language model pretraining. Future work may explore the robustness and generalization ability of in-context learning, for which our IC-DST can serve as a test bed. Also, there is a tradeoff between avoiding the cost of fine tuning with a large language model vs. the cost of inference. Fortunately, thanks to the recent efforts in open-source large models like OPT (Zhang et al., 2022) and BLOOM (BigScience), and model compression techniques like LLM.int8() (Dettmers et al., 2022), the cost of running large language models has been drastically reduced, and we are optimistic that this trend will continue in the future. Further, it is possible to leverage zero/few-shot methods as a teacher model to generate "pseudolabels" for training a system that has a lower inference cost, as in Ye et al. (2022). Future work may investigate more on low-cost approaches to applying in-context learning and large language models. 
In-Context Learning for Few-Shot Dialogue State Tracking
This section provides a more detailed description of errors described in Table 6.
In-Context Learning for Few-Shot Dialogue State Tracking
The first type of error is caused by a noisy training example. In this example, there is a missing slot 'attraction-type' in the example label.
In-Context Learning for Few-Shot Dialogue State Tracking
The second type of error is unable to retrieve good examples. In this example, the inference LM is mimicing the example, only predicting slot 'attraction-name' and missing the slot 'hotelpricerange'.
In-Context Learning for Few-Shot Dialogue State Tracking
The third type of error is fail to generalize from examples. In this example, the in-context example contains the notion of slot value 'don't care'. However, the LM fails to generalize this notion and misses the slot value pair 'hotel-area: don't care'.
In-Context Learning for Few-Shot Dialogue State Tracking
For zero-shot inference and few-shot in-context learning, we do not need any training. We use one NVIDIA A10G graphics card for GPT-Neo and CodeGen models. Inference of one turn takes about 2 seconds for both models. For Codex, we use the OpenAI API. On average each turn takes about 4 seconds for inference.
In-Context Learning for Few-Shot Dialogue State Tracking
For retriever finetuning, we train all our retrievers on one single NVIDIA A10G graphics card. For 5% few-shot scenario, each epoch of training takes 10 minutes on average with our given hyperparameters, and we train for 10 epochs. For 100% full-shot scenario, we train for 2 epochs, which takes 6 hours. The training time is linear to the data size.
In-Context Learning for Few-Shot Dialogue State Tracking
Only retriever finetuning requires hyperparameter tuning. Hyperparameters are given in our code, and the best configuration is provided in the experiment section. They are chosen by manual tuning. The development evaluation metrics is the average F 1 score of retrieved examples, which has been described in the paper. For learning rates, we experimented over 1 × 10 −5 and 2 × 10 −5 . For contrastive learning, we scale the number of positive/negative examples for each data point linearly with the selection pool size. When using 1% of labeled data, the number of positive/negative examples is 2. For 5% of data, the number is 10. We also experimented with doubling the number of positive/negative examples. All few-shot test numbers are the average of three evaluation runs, and all retrievers are trained just once with each hyperparameter configuration. MultiWOZ (Budzianowski et al., 2018) is an English multi-domain task-oriented dialogue dataset. It contains 7 different domains. Following the previous work (Wu et al., 2019), we use 5 domains: hotel, taxi, attraction, restaurant, and train. There are 8438 dialogues in the training set, and 1000 dialogues in the dev and test set. On average, there are 13.46 turns per dialogue and 13.13 tokens per turn. For preprocessing, we use the scripts of Ye et al. (2021a). This script mainly fixes typos and standardizes the formatting. All data are downloadable from Ye et al. (2021a).  
What Makes Good In-Context Examples for GPT-3?
1 Introduction GPT-3 (Brown et al., 2020) is a new breakthrough in NLP research. Previously, NLP models are firstly pre-trained and then fine-tuned on a specific task. What sets GPT-3 apart from other models is its impressive "in-context" learning ability. Provided with a few in-context examples, GPT-3 can generalize to unseen cases without further finetuning. This opens up many new technological possibilities that are previously considered unique * Work was done when Jiachang (intern) and Yizhe were at Microsoft. to human. Future NLP systems can be developed to expand emails, extract entities from text, generate code based on natural language instructions with a few demonstration examples.
What Makes Good In-Context Examples for GPT-3?
Despite its powerful and versatile in-context learning ability, GPT-3 has some practical challenges. The original paper utilizes task-relevant examples that are randomly sampled from the training set. However, we observe that the performance of GPT-3 tends to fluctuate with different choices of in-context examples. As shown in Table 1, the variance with distinct in-context examples can be significant. Our work aims to carefully examine this issue to gain a deeper understanding on how to better select in-context examples to improve GPT-3's performance without fine-tuning. Note that our approach requires a training set to select examples. With such a training dataset, it is possible to fine-tune GPT-3 to take full advantage of the model's strength. However, currently GPT-3 has not been released to public for fine-tuning. Even if it is available, fine-tuning GPT-3 requires hundreds of GPUs to load the 175B model, which is prohibitively expensive and time-consuming for ordinary research labs. Another issue is that storing large fine-tuned model checkpoints require huge storage space. Consequently, we resort to prompt/example engineering strategy. Nevertheless, the fine-tuning results using T5 are provided for reference.
What Makes Good In-Context Examples for GPT-3?
A brute-force approach for selecting the optimal in-context instances would be to perform combinatorial search over the entire dataset. Unfortunately, this strategy is computationally impractical. To this end, we empirically investigate the influences of employing different in-context examples. Interestingly, we find that the in-context examples that are closer to the test sample in the embedding space consistently give rise to stronger performance (relative to the farther ones). Inspired by this observation and the recent success of retrieval-augmented models , we propose to utilize nearest neighbors of a given test sample (among all the training instances available) as the in-context examples.
What Makes Good In-Context Examples for GPT-3?
To verify the effectiveness of the proposed method, we evaluate it on several natural language understanding and generation tasks, including sentiment analysis, table-to-text generation and opendomain question answering. It is observed that the retrieval-based in-context examples unleash the in-context learning capabilities of GPT-3 much more effectively than the random sampling baseline, even when the number of examples is small. Moreover, we find that the specific sentence encoders employed for the retrieval procedure play a critical role. Thus, an extensive exploration is conducted and shows that encoders fine-tuned on natural language matching tasks serve as more effective in-context examples selector on the QA task. In summary, our contributions are as follows:
What Makes Good In-Context Examples for GPT-3?
i) to the best of our knowledge, we take a first step towards understanding the sensitivity of GPT-3's in-context learning ability with respect to the choice of in-context examples;
What Makes Good In-Context Examples for GPT-3?
ii) to alleviate the sensitivity issue, an additional retrieval module is introduced to find semanticallysimilar in-context examples of a test instance, which greatly outperforms the baseline based on randomly sampled in-context examples;
What Makes Good In-Context Examples for GPT-3?
iii) empirically, the better selected examples lead GPT-3 to achieve comparable performance to a fine-tuned T5 model on the table-to-text task and outperforms the T5 model on the QA tasks; iv) fine-tuning the retrieval model on task-related dataset(s) leads to stronger empirical results; v) the performance of GPT-3 improves as the number of examples for retrieval increases.
What Makes Good In-Context Examples for GPT-3?
The in-context learning scenario of GPT-3 can be regarded as a conditional text generation problem. Concretely, the probability of generating a target y is conditioned on the context C, which includes k examples, and the source x. Therefore, the probability can be expressed as:
What Makes Good In-Context Examples for GPT-3?
where LM denotes the parameters of the language model, and C = {x 1 , y 1 , x 2 , y 2 , ..., x k , y k } is a context string concatenating k training instances with the special character "\n". A concrete illustration can be found in the Appendix. For GPT-3, this generation process is implemented through a giant transformer-based architecture (Vaswani et al., 2017). Due to the computational burden of fine-tuning, GPT-3 is leveraged in an in-context learning manner as described above. Unfortunately, as shown in Table 1, the results of GPT-3 tend to fluctuate significantly with different in-context examples. We aim to alleviate this issue via judicious in-context example selection.
What Makes Good In-Context Examples for GPT-3?
We start the investigation by looking at the role of in-context examples from an empirical perspective. Previous retrieve-and-edit literature usually retrieve prototypes that are close to the test source x in some embedding space. These examples and the test source x often share semantic or lexical similarities. This hints on how we may select incontext examples for GPT-3.
What Makes Good In-Context Examples for GPT-3?
To this end, we examine the impact of the distance between the in-context example and the test sample on GPT-3's performance. Concretely, a comparison is made on the the Natural Questions (NQ) dataset between two selection strategies. Given a test example, the first method utilizes the 10 farthest training instances as the in-context examples, while the second employs the 10 closest neighbors. We use the CLS embeddings of a pre-trained RoBERTa-large model as sentence representations to measure the proximity of two sentences (using the Euclidean distance).
What Makes Good In-Context Examples for GPT-3?
For evaluation, 100 test questions are randomly sampled and the average Exact Match (EM) scores with the two distinct strategies are reported in Table 2. It can be observed that the nearest neighbors, used as the in-context examples, give rise to much better results relative to the farthest ones. Moreover, the pre-trained RoBERTa model serves as effective sentence embeddings for the retrieval procedure.
What Makes Good In-Context Examples for GPT-3?
Based on the findings above, we propose KATE 1 , a strategy to select good examples for in-context learning. The process is visualized in Figure 1. Specifically, we first use a sentence encoder to convert sources in both the training set and test set to vector representations. For online prediction, we can convert the training set first and encode each test source on the fly. Then, for each test source x, we retrieve its nearest k neighbors x 1 , x 2 , ..., x k from the training set (according to the distances in the embedding space). Given some pre-defined similarity measure s such as the negative Euclidean distance or the cosine similarity, the neighbors are ordered so that s(x i , x) ≥ s(x j , x) when i < j.
What Makes Good In-Context Examples for GPT-3?
The k sources are concatenated with their targets to form the context C = {x 1 , y 1 , x 2 , y 2 , ..., x k , y k }, which is sent to GPT-3 along with the test input. The algorithm is presented in Algorithm 1. Note that different 1 KATE: Knn-Augmented in-conText Example selection
What Makes Good In-Context Examples for GPT-3?
Closest Farthest Accuracy 46.0 31.0 
What Makes Good In-Context Examples for GPT-3?
, sentence encoder µ θ (·), and number of in-context examples k (hyperparameter).
What Makes Good In-Context Examples for GPT-3?
numbers of examples can be employed, and we conduct study on its impact in a later section.
What Makes Good In-Context Examples for GPT-3?
Choices of Retrieval Module A core step for our context selection approach is mapping sentences into a latent semantic space, leaving a question as what sentence encoders we should choose. We compared among existing pre-trained text encoders and found them sufficient to retrieve semantically similar sentences. The sentence encoders can be divided into two categories.
What Makes Good In-Context Examples for GPT-3?
The first category includes generally pre-trained sentence encoders such as the BERT, RoBERTa, and XLNet models. These models have been trained on large quantities of unsupervised tasks and achieved good performance on many natural language tasks. The corresponding embeddings contain rich semantic information from the original sentences.
What Makes Good In-Context Examples for GPT-3?
The second category includes sentence encoders fine-tuned on specific tasks or datasets. For example, a sentence encoder trained on the STS dataset should be able to assess similarities among different questions better than a generally pre-trained sentence encoder. Sentence-BERT (Wolf et al., 2019;Gurevych, 2019, 2020) shows that these fine-tuned encoders have achieved great performance on tasks such as sentence clustering, paraphrase mining, and information retrieval.
What Makes Good In-Context Examples for GPT-3?
We apply our proposed method to the following three tasks: sentiment analysis, table-to-text generation, and question answering. Dataset split setups and prompt templates are shown in Table 9 and 11 in the Appendix. For the hyper-parameters in the GPT-3 API, we set the temperature to 0.
What Makes Good In-Context Examples for GPT-3?
To retrieve semantically-similar training instances, we consider two types of sentence embeddings.
What Makes Good In-Context Examples for GPT-3?
• The original RoBERTa-large model , which is abbreviated as KATE roberta ;
What Makes Good In-Context Examples for GPT-3?
• The RoBERTa-large models which are: i) finetuned on the SNLI and MultiNLI datasets (KATE nli ) (Bowman et al., 2015;Williams et al., 2017); ii) first fine-tuned on the SNLI and MultiNLI dataset and then on the STS-B datasets (KATE nli+sts-b ) (Cer et al., 2017).
What Makes Good In-Context Examples for GPT-3?
All sentence encoders share the same architecture. The only differences are the specific datasets used for fine-tuning. The negative Euclidean distance is used for KATE roberta , while the cosine similarity is employed for KATE nli and KATE nli+sts-b .
What Makes Good In-Context Examples for GPT-3?
For this task, we conduct experiments under the dataset-transfer setting. Incontext examples are selected from one dataset, and the evaluation is made on another dataset. This setting is designed to simulate a real-world scenario where we want to leverage an existing labeled dataset for a unlabeled one (of a similar task). Specifically, we select examples from the SST-2 training set (Socher et al., 2013; and ask GPT-3 to predict on the IMDB test set (Maas et al., 2011). To explore whether a sentence encoder fine-tuned on a similar task would benefit KATE, we also employ a pre-trained RoBERTa-large model fine-tuned on the SST-2 training set (dubbed as KATE sst-2 ). The number of examples is chosen to be 3 since adding more examples does not further improve the performance. Table-to-Text Generation Given a Wikipedia table and a set of highlighted cells, this task focuses on producing human-readable texts as descriptions. ToTTo (Parikh et al., 2020) 2 is utilized for evaluation due to its popularity. We use BLEU (Papineni et al., 2002) and PARENT  metrics for evaluation. Because the token length limit of GPT-3 is 2048, we add a preprocessing step by deleting the closing angle brackets such as </cell> and </table> to save space. The number of in-context examples is set as 2 so that the input length is within the token limit.
What Makes Good In-Context Examples for GPT-3?
Question Answering We conduct experiments on three QA benchmarks: Natural Questions (NQ) (Kwiatkowski et al., 2019), Web Questions (WQ) (Berant et al., 2013), and TriviaQA (Joshi et al., 2017). For evaluation, we use the Exact Match (EM) score, which is defined as the proportion of the number of predicted answers being exactly one of the ground-truth answers. The matching is performed after string normalization, which includes article and punctuation removal. The number of examples is set to be 64 for NQ and WQ and 10 for TriviaQA (The retrieved 64 examples exceed the token limit). We evaluate on the test sets of NQ and WQ and the dev set of TriviaQA.
What Makes Good In-Context Examples for GPT-3?
Random Sampling For each test sentence, we randomly select in-context examples from the training set. We refer to this method as Random in the experimental results. On the test set, the random baseline is repeated for five times to obtain the average score and corresponding standard deviation.
What Makes Good In-Context Examples for GPT-3?
k-Nearest Neighbor Additionally, to investigate whether the retrieval module is complementary to GPT-3's in-context learning ability, we further consider a k-nearest neighbor baseline. Specifically, the target y 1 associated with the first retrieved example is considered as the predicted target for the test sample. For the sentiment analysis and QA tasks, the top k retrieved examples {y 1 , ..., y k } are utilized, where the final prediction is determined by majority voting among the k examples' targets. If there is a tie case, we use the target of the example most similar to the test sentence. To ensure fair comparison, we compare the baseline kNN and KATE under the same embedding space of a pre-trained RoBERTa-large model. This baseline is abbreviated as kNN roberta .
What Makes Good In-Context Examples for GPT-3?
Fine-tuned T5 Although this work aims at improving the in-context learning abilities of GPT-3, we include a fine-tuned T5 (3B) model as a baseline. This comparison informs us where GPT-3 performs comparably or surpasses a fine-tuned model.  4 Experimental Results
What Makes Good In-Context Examples for GPT-3?
We first evaluate KATE on the sentiment analysis task. The results are in Table 3. KATE consistently produces better performance relative to the random selection baseline. Notably, there is no variance with the obtained results since the fixed retrieved in-context examples are employed. For KATE, when the pre-trained sentence encoder is fine-tuned on NLI or NLI+STS-B datasets, the performance slightly decreases. Since the objectives of the IMDB and the NLI+STS-B datasets are different, this shows that fine-tuning on a dissimilar task hurts KATE's performance. In contrast, KATE sst-2 obtains the best accuracy, showing that fine-tuning on a similar task improves KATE's performance.
What Makes Good In-Context Examples for GPT-3?
To verify that the gains are not merely from the retrieval step, we further compare KATE roberta with the kNN roberta . It turns out that the performance of kNN roberta is close to random guessing. This observation is consistent when one neighbor or three neighbors are retrieved. Notably, with the sentence encoder fine-tuned on the SST-2 dataset, the accuracy of kNN sst-2 is 92.46, which is lower than that of KATE sst-2 . These results suggest that GPT-3 is critical to the final results, and the retrieval module is complementary to GPT-3. The fine-tuned T5 model works better since its parameters has been adapted to this specific task. However, fine-tuning requires access to model parameters, lots of memory storage, and time. The fine-tuning result here is just for reference. Through KATE, the performance of GPT-3 has increased significantly without fine-tuning.
What Makes Good In-Context Examples for GPT-3?
We next evaluate KATE on the ToTTo dataset and present results in Table 4. KATE gives rise to considerable gains over the random baseline, according to both the BLEU and PARENT scores. Notably, KATE enables GPT-3 to achieve performance comparable to a fine-tuned T5 model. On a finer scale, the evaluation can be done on the overlap subset and the nonoverlap subset. The overlap dev subset shares a significant number of header names with the training set, while the nonoverlap one does not. KATE improves results on both subsets, meaning that the retrieval module is helpful even when the dev set is out of distribution of the training set. Similar to sentiment analysis, there is a slight drop in performance from KATE roberta to KATE nli and KATE nli+sts-b . This is due to the difference between the objectives of the ToTTo dataset and NLI+STS-B datasets. The drop from KATE nli to KATE nli+sts-b further validates the idea that fine-tuning on a dissimilar task can hurt KATE's performance. For the kNN baseline, it performs much worse than the random selection method and KATE, suggesting that the retrieval process and GPT-3 work collaboratively to achieve better results.
What Makes Good In-Context Examples for GPT-3?
To understand how the retrieval mechanism helps GPT-3, we conduct a case study on the retrieved examples (see Table 5). By retrieving relevant examples from the training set, KATE provides useful detailed information within the table, e.g., the number of points, rebounds, and assists, to GPT-3 for more accurate description. On the other hand, the random selection method has the issue of hallucination, where the generated sequences contain information (i.e., "senior year" and "University of Texas") not present in the table.
What Makes Good In-Context Examples for GPT-3?
Lastly, we evaluate KATE on the open-domain QA tasks, as shown in Table 6. We compare with some state-of-the-art fine-tuned methods such as RAG (Lewis et al., 2020) and T5 (Raffel et al., 2019). The T5 results were reported in (Brown et al., 2020) using the 11B model, which needs specialized TPUs to do fine-tuning. KATE again improves GPT-3's performance substantially across various benchmarks. Moreover, KATE helps GPT-3 to even outperform the fine-tuned T5 model. It is worth noting that this time both KATE nli and KATE nli+sts-b improve upon KATE roberta because fine-tuning on NLI or STS-B datasets is helpful for retrieving semantically similar questions from the QA datasets. Moreover, on the NQ and TriviaQA datasets, further fine-tuning on the STS-B dataset improves KATE's results. We evaluate the baseline kNN roberta by using the top-1 nearest neighbor. The kNN baseline results again suggest that  Table 4: Table-to-text generation results on the ToTTo dev dataset.
What Makes Good In-Context Examples for GPT-3?
Test Table  Table: <page_title >Trey Johnson <section_title >College <table ><cell >32 <col_header > GP <cell >4.8 <col_header >RPG <cell >2.3 <col_header >APG <cell >23.5 <col_header >PPG   the retrieval module and GPT-3 work together to achieve better performance. We also explore using 64 nearest neighbors (10 for TriviaQA) to determine the answer (by majority voting explained in Section 3.2). The EM score are similar to retrieving the top-1 nearest neighbor.
What Makes Good In-Context Examples for GPT-3?
To investigate why the retrieved examples are helpful, we present a case study. Concretely, the retrieval examples from the NQ dataset are shown in Table 7. For the first and second cases, the random baseline provides wrong answers because GPT-3 is unable to recall the exact detail. However, the in-context examples selected by KATE contain the correct details, which facilitate GPT-3 to answer questions. For the third case, the random baseline leads GPT-3 to misinterpret the question as asking for a specific location. In contrast, KATE selects similar types of questions asking for the origins of objects. Using these in-context examples, GPT-3 is able to interpret and answer the question correctly.
What Makes Good In-Context Examples for GPT-3?
We first investigate the impact of the number of examples on KATE's performance. Concretely, on the NQ dataset, we choose the number of examples to be 5, 10, 20, 35, and 64, and KATE nli+sts-b is compared with the random baseline and KATE roberta across different settings. As shown in the left plot of Figure 2, both KATE and the random baseline benefit from utilizing more examples. However, KATE consistently outperforms the random selection method, even when the number of in-context examples is as few as 5. This result is interesting because in practice, employing less examples leads to more efficient inference with GPT-3.
What Makes Good In-Context Examples for GPT-3?
We further examine how the size of the training set may influence the KATE method. On the NQ dataset, we create new subsets from the original training set, with sizes of 1k, 2k, 5k, 10k, 30k, and   70k, respectively. In-context examples are retrieved from these subsets instead of the original training set. The number of nearest neighbors is set to 64. We compare KATE nli+sts-b with the random selection method and KATE roberta , and the results are shown in the right plot of Figure 2. For KATE roberta and KATE nli+sts-b , as the size of the training set increases, the EM scores also increase. In contrast, the result of the random sampling baseline does not change much. Intuitively, as the training size gets larger, it is more likely for KATE to retrieve relevant in-context examples to help GPT-3 answer a question correctly. As we have shown previously in Table 7, the retrieved in-context examples could provide critical detailed information to GPT-3, thus helping GPT-3 to better answer the questions.  
What Makes Good In-Context Examples for GPT-3?
The results are presented in Table 8. On this particular NQ dataset, the reverse order performs the best. However, we also did the experiments on the WQ and TriviaQA and find that the default order performs slightly better than the reverse order. Hence, the choice of orders is data-dependent. Additionally, it can be observed that the variation among the NQ results tends to be quite small (compared with the difference between the random baseline and KATE), indicating that the example order does not have a significant impact on KATE's performance.
What Makes Good In-Context Examples for GPT-3?
There is a long history of applying information retrieval to text generation (Sumita and Hitoshi, 1991). It is very related to the exemplar-based learning (Jäkel et al., 2008;Ziyadi et al., 2020). Some representative applications in the field of deep learning include machine translation (Gu et al., 2018), sentiment transfer , QA (Karpukhin et al., 2020;Mao et al., 2020), dialogue generation Cai et al., 2018;Pandey et al., 2018;We-ston et al., 2018;, text summarization (Cao et al., 2017;Peng et al., 2019), datato-text generation (Peng et al., 2019), and text-tocode generation . All these retrieve-and-edit frameworks require their editors to be trained or fine-tuned on specific tasks. In contrast, our work uniquely examines how to better use GPT-3 as a universal editor without fine-tuning. We find that the more semantically similar context we provide to GPT-3, the better results the model can generate.
What Makes Good In-Context Examples for GPT-3?
Improve NLP Systems with kNN Some recent works try to incorporate non-parametric methods to improve a given model's performance. For example, the newly introduced kNN-LM (Khandelwal et al., 2019), kNN-MT (Khandelwal et al., 2020), and BERT-kNN (Kassner and Schütze, 2020) generate the next token by retrieving the nearest k neighbors from the datastore. Another related work kNN classification model (Rajani et al., 2020) uses kNN as backoff when the confidence is low from the classification model. There are two key differences between our work and other approaches. First, we retrieve the nearest k neighbors to modify the conditional context instead of the prediction. Second, we do not have access to the parameters of GPT-3. Instead, we rely on some independently pre-trained models to get the sentence embeddings to retrieve the nearest k neighbors.
What Makes Good In-Context Examples for GPT-3?
This work presented a first step towards investigating the sensitivity of GPT-3 to in-context examples.
What Makes Good In-Context Examples for GPT-3?
To this end, we proposed KATE, a non-parametric selection approach that retrieves in-context examples according to their semantic similarity to the test samples. On several natural language understanding and generation tasks, the proposed method improves GPT-3's performance, over the random sampling baseline, by a significant margin. Particularly, KATE enables GPT-3 to achieve performance comparable to a fine-tuned T5 model on the tableto-text generation task and outperforms T5 on the QA task. Moreover, we found that fine-tuning the sentence embeddings for retrieval on task-related datasets gave rise to further empirical gains. Detailed analysis was conducted to explore the robustness of KATE to different hyperprameters, such as the number of in-context examples, examples' order, etc. One limitation we notice is that despite the improved performance on sentiment analysis, GPT-3 still lags behind the fine-tuned T5 model by a small margin. This suggests that our proposed method is more suitable and effective on long text generation tasks. We hope this work could provide insights for better understanding the behaviors of GPT-3 and represents a helpful step towards further improving its in-context learning capabilities.
What Makes Good In-Context Examples for GPT-3?
Risk Our proposed KATE method significantly improves the in-context learning ability of GPT-3 and makes long-text generation more easily without fine-tuning the pre-trained model. However, one risk implication is that our proposed method will benefit the research groups which are financially capable of using such huge models. For individual or small-group researchers, they cannot apply our proposed method to their specific applications since they don't have access to the model. Our work has suggested researchers should focus more on investigating the in-context learning of pretrained models. One potential future direction is for researchers to scale-down the sizes of pre-trained models to find a balance between model performance and model size. Once a smaller model is obtained with comparable performance (enhanced by KATE), our proposed method can become more widely accessible to individual researchers. During the experiment on table-to-text generation, we have pointed out that large pre-trained language models could be susceptible to hallucination (case study in Table 5). This problem is more pronounced when we use randomly sampled examples. This happens because the language model is biased toward the training dataset. As shown in Table 5, when random examples are used, the sentence generated by GPT-3 is grammatically correct, but some details never exist in the given table. In contrast, our proposed method, KATE, can significantly alleviate this problem by guiding GPT-3 to look for and generate the correct information. For similar reasons, large pretrained models could be potentially susceptible to gender and racial bias. Since our KATE method shows that in-context examples are crucial for highquality long-text generations, one way to alleviate the racial and gender bias is to incorporate an additional module to filter out offensive in-context examples. Since racial and gender bias are not our main research focus, a full investigation goes beyond the scope of our work. However, we believe this is an exciting opportunity for future work.
What Makes Good In-Context Examples for GPT-3?
Implementations of the proposed KATE method discussed in this paper are available at https: //github.com/jiachangliu/KATEGPT3.
What Makes Good In-Context Examples for GPT-3?
As shown in the illustration of Figure 3, GPT-3 is asked to translate "mountain" to its German version based on the three examples given as part of the input.    
What Makes Good In-Context Examples for GPT-3?
Due to the length limit of the main paper, we present in the appendix the full ToTTo case study comparing the random sampling baseline and our proposed KATE method. We present the case study in Table 10.
What Makes Good In-Context Examples for GPT-3?
As we have discussed in the main paper, the in-context examples retrieved by KATE facilitates GPT-3 to effectively extract key information from the given table. Detailed numbers such as the number of points, rebounds, and assists have all been included in the sentence.
What Makes Good In-Context Examples for GPT-3?
In contrast, the sentence generated by GPT-3 using randomly sampled in-context examples only extract partial information from the table. Only the number of points is included while the numbers of rebounds and assists are ignored. Moreover, the random sampling baseline could lead to the issue of hallucination. Both "senior year" and "University of Texas" are not present in the given table. One may wonder whether these wrong phrases were present in the randomly sampled in-context examples, which might have caused this issue. However, if we look at the randomly sampled in-context examples in the second block of the table, such information do not exist. This suggests such hallucinated phrases are generated by the language model itself.
What Makes Good In-Context Examples for GPT-3?
This comparison provides some key insights on why KATE works better than the random sampling baseline. By retrieving semantically/syntactically similar in-context examples, KATE provides GPT-3 with a much more accurate template/structure to do text generation. Without such structure, GPT-3 can generate sentences that are fluent but do not meet the goal of a particular task.
What Makes Good In-Context Examples for GPT-3?
Fine-tuning
What Makes Good In-Context Examples for GPT-3?
As we mentioned in the main paper, given a training dataset, we could take the full advantage of the GPT-3's model strength through fine-tuning. However, there are several advantages of prompt engineering over fine-tuning. First, fine-tuning requires access to the model parameters and gradients. It is impossible to access this information via the current GPT-3's API. Second, fine-tuning large models are time-consuming and costly. Ordinary research labs and individual developers do not have resources to accomplish such tasks. Third, storing large fine-tuned model checkpoints requires large storage space. Even if GPT-3 is fine-tuned and stored for many specific tasks/datasets, many finetuned checkpoints may not be frequently called. This is not energy efficient. Our proposed KATE method does not require costly fine-tuning and improves the random baseline on both text classification and generation tasks, sometimes by a significant margin. This makes it more practical to deploy the same GPT-3 model across all tasks.
What Makes Good In-Context Examples for GPT-3?
Although our primary goal is to improve GPT-3's in-context learning ability, we also include the finetuned T5 results as a reference (3B T5 on SST-2 and Test Table   Table:   year" and "University of Texas" also do not exist in the randomly sampled in-context examples. This suggests that the wrong information was generated by the language model itself. Although the sentence by the random sampling baseline is fluent, it does meet the goal of the table-to-text task.
What Makes Good In-Context Examples for GPT-3?
ToTTo datasets, and 11B T5 on the QA datasets). The reason for reporting the 3B T5 results on the SST-2 and ToTTo datasets is that this is the largest T5 model we can use. For the 3B T5 model, Google Colab 3 provides a free V2-8 TPU to fine-tune the 3B model. We used the Colab tutorial notebook to fine-tune the 3B T5 model on the SST-2 and ToTTo training sets. We couldn't fine-tune the 11B T5 model because the model size is too large. Finetuning such a large model requires a V3-8 TPU, which is not free of charge. Fortunately, the original GPT-3 paper (Brown et al., 2020) has already reported the finet-tuned 11B T5 results on the three QA datasets, so we reuse these results in our main paper for the QA task. Our proposed KATE method significantly improves GPT-3, performing comparably to the fine-tuned T5 model on the table-to-text task and outperforming the fine-tuned T5 model on the QA task.
What Makes Good In-Context Examples for GPT-3?
As we mention in the main paper, we use the pretrained RoBERTa-large model  as the first retrieval module, which has 355M parameters and is pre-trained with the MLM (masked language modeling) objective. The result given by this module is denoted as KATE roberta . We directly download this model from the HuggingFace Model Zoo (MIT license) 4 . All other retrieval modules share the same architecture as the RoBERTa-large module but are fine-tuned on specific datasets. For the fine-tuned retrieval modules, the first we use is the RoBERTa-large model fine-tuned on the SNLI and MultiNLI datasets (KATE nli ) (Bowman et al., 2015;Williams et al., 2017); the next we use is the RoBERTa-large model fine-tuned on the SNLI and MultiNLI dataset and then on the STS-B datasets (KATE nli+sts-b ) (Cer et al., 2017). These fine-tuned models have already been accomplished and included by the Sentence-BERT family and are publicly available, so we directly download from the Sentence-BERT Model Zoo 5 .
What Makes Good In-Context Examples for GPT-3?
Lastly, specifically for the sentiment analysis task, we include a RoBERTa-large model finetuned on the SST-2 dataset (KATE sst-2 ) (Socher et al., 2013;. At the time of our  Table: <page_title>Dedric Lawson <section_title>College <table><cell>9.9 <col_header>RPG <cell>3.3 <col_header>APG <cell>19.2 <col_header>PPG Sentence: Dedric Lawson averaged 19.2 points, 9.9 rebounds and 3.3 assists per game.  Table 11: The prompt templates used for all tasks discussed in the paper. We show only one in-context example per task for illustration purposes.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Semantic parsing is the task of translating natural language questions into meaning representations such as Lambda CDS (Liang, 2013), Python code (Yin et al., 2018), and SQL . More recently, Text-to-SQL semantic parsing has attracted attention from academia and industry due to its challenging setup and practical applications.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Cross-lingual Text-to-SQL semantic parsing (Sherborne and Lapata, 2022b;Min et al., 2019;Sherborne et al., 2020) aims to translate non-English utterances into SQL queries based on an English schema (assuming we have an internationalized database), enabling users to query databases in non-English languages. For example, such a system could help people from around the world access the US government's open data 1 with natural language questions in different languages.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
State-of-the-art approaches for Text-to-SQL semantic parsing have been greatly improved by finetuning pre-trained language models as a sequenceto-sequence problem (Scholak et al., 2021;Yin et al., 2020;Herzig et al., 2020;Yu et al., 2021a,b;Shi et al., 2021a). More recently, in-context learning with large language models (LLMs), such as GPT-3 (Brown et al., 2020) and Codex (Chen et al., 2021), has emerged as a new learning paradigm. This paradigm enables effective few-shot learning without model finetuning, showing its practical and scientific value (Beltagy et al., 2022). Recent papers also have shown promising results applying in-context learning to the Text-to-SQL task. Rajkumar et al. (2022) studied if LLMs are already competitive Text-to-SQL semantic parsers without further finetuning on task-specific training data. Additionally, Poesia et al. (2022) and Rubin et al. (2022) investigated the exemplar retrieval problem for the semantic parsing task.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
However, previous work mostly focused on English utterances, leaving other languages behind. It is unclear if LLMs are competitive for crosslingual Text-to-SQL with English exemplars using in-context learning. Even in the mono-lingual setting (where the exemplars and the query are in the same language), many approaches are not practical beyond English due to the paucity of target language query-SQL exemplars.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
To bridge this gap, we propose XRICL, a novel framework based on LLMs with in-context learning for cross-lingual Text-to-SQL semantic parsing. Specifically, the task is to generate SQL queries for non-English queries based on an English schema and an English query-SQL candidate pool. Our framework first constructs the context prompt by retrieving the most relevant English query-SQL exemplars for each target language query. Since we do not have any training data in the target language, we cannot train a retriever for target queries directly. Our solution is to train an English exemplar retriever with mT5 (Xue et al., 2021) and adopt a model-based cross-lingual transfer method for cross-lingual retrieval. The English exemplar retriever is trained with feedback from the LLM itself by distilling soft labels (likelihood).
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Our framework introduces an additional exemplar into the LLM's input context, to instruct the model to translate the target query into English and then to translate the English query into SQL; this approach is inspired by recent work on chainof-thought prompting (Wei et al., 2022;. However, in our framework, this additional exemplar is identical for all test queries, which means that we only need a single pair of translations for any English-target language pair, requiring minimal translation effort.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
During the inference process, the language model is expected to generate the English translation first and then the SQL query. In our exper-iments, we find that our proposed retriever and reranker can improve the LLMs' cross-lingual fewshot in-context learning performance by a large margin, and further improvements can be observed by adding an additional translation exemplar.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
We further construct two benchmarks, XSPI-DER and XKAGGLE-DBQA, to systematically evaluate the proposed framework in many languages. For XSPIDER, besides adopting existing work, including CSPIDER (Min et al., 2019) and VSPI-DER (Tuan Nguyen et al., 2020), we further translate the SPIDER dataset into Farsi and Hindi for evaluation. For XKAGGLE-DBQA, we translate the English KAGGLE-DBQA dataset into Chinese, Farsi, and Hindi. Experimental results show that our proposed framework improves effectiveness compared to baseline systems.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Our contributions are summarized as follows:
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
(1) We propose a novel retrieve-rerank framework to improve the exemplar selection process for incontext learning for cross-lingual Text-to-SQL semantic parsing. To the best of our knowledge, we are the first to explore the effectiveness of large pre-trained language models for cross-lingual Textto-SQL semantic parsing. (2) We propose to use translation as a chain-of-thought prompt in the inference process, bridging the cross-lingual gap for large language models. (3) Last, we construct two new benchmarks, XSPIDER and XKAGGLE-DBQA, to facilitate evaluation of cross-lingual Text-to-SQL semantic parsing.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Given a database where the schema s is in English (denoted as the source language), our task is to translate a non-English (denoted the target language) example x (x includes utterance u and schema s) into a SQL query a. In this work, we explore large pre-trained language models such as Codex for this Text-to-SQL task with in-context learning. To support in-context learning, labeled candidates of (utterance, schema, SQL) triples are required. Since more annotated resources are available in English, we assume that the labeled candidate set D is in English. Overall, in-context learning is an efficient method to leverage large pre-trained language models without expensive parameter fine-tuning. Furthermore, the candidate pool can be easily expanded for better generalization to new domains.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Our XRICL framework is shown in Figure 1, consisting of four steps:
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
(1) Cross-lingual Exemplar Retrieval: Retrieve a list of N English exemplars that are relevant to the input non-English example x.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
(2) Exemplar Reranking: Rerank the retrieved N exemplars and use the top K exemplars to construct prompts.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
(3) Prompt Construction with Translation as Chain of Thought: Construct a prompt consisting of the translation exemplar as a chain of thought, the selected K exemplars, and the input example.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
(4) Inference: Feed the prompt into a pre-trained language model to generate SQL.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Given a non-English question, the goal of the crosslingual exemplar retriever is to find relevant exemplars from the English candidate pool efficiently that can improve the predictions of the generators. Considering that we use labeled examples in English (a high-resource language) as candidates, we formulate this step as a cross-lingual retrieval problem, where the test question is in a non-English language. In this case, traditional term matching methods such as BM25 (Robertson and Zaragoza, 2009) or BM25 + RM3 query expansion (Lin, 2018) cannot be applied due to token mismatch. Instead, we propose to use a bi-encoder for cross-lingual semantic retrieval with model-based zero-shot transfer. We further improve the retriever with distillationbased training.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Model. Here, we leverage the popular bi-encoder architecture known as dense passage retriever (DPR) (Karpukhin et al., 2020), where the query and candidates are mapped into representation vectors independently. The retriever uses a dense encoder E u (·) that converts an utterance into a ddimensional vector and builds an index over the candidate pool that is used for retrieval.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
For a test instance x, we use the same dense encoder to map the utterance into a d-dimensional vector (denoted the query vector). Based on the query vector, the closest top N exemplars are retrieved from the pre-built index based on the predefined distance function. Following Karpukhin et al. (2020), we define the distance function as
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
where Z is the set of candidate exemplars and z ∈ Z. We use a transformer as the dense encoder, and the average of the contextual embeddings of the utterance tokens is taken as the representation of the encoded text.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Model-based Cross-lingual Transfer. Considering that we do not have training data in target languages, we adopt a model-based crosslingual transfer method, where we leverage the zero-shot cross-lingual transfer ability of multilingual pre-trained transformers such as mBERT (Devlin et al., 2019), XLM-Roberta (Conneau et al., 2020), mBART , and mT5 (Xue et al., 2021). Specifically, we train the dense retriever in the source language, where both the query utterance and candidate utterances are in English (in our case), and apply inference directly on query utterances in the target language and retrieve English exemplars in a cross-lingual manner.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Distillation-based Training. One common practice for bi-encoder training is contrastive learning.  Hu et al. (2022), hard labels are used. Another way to train the bi-encoder is to use a regression-based loss function. Poesia et al. (2022) proposed to retrieve exemplars that have relevant program structures (tree edit distance of SQL abstract syntax trees is used as the relevance metric) for the test utterances and the model is optimized with mean-squared error loss for predicting the similarity score.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
As an alternative to these above approaches, we train our retriever by distilling the LLM's scoring function. This scoring function calculates the ground-truth SQL query's likelihood given an English exemplar z k and the input utterance x, which estimates the importance of this exemplar for parsing the given input utterance. Hence, we score the retrieved English exemplars with an LLM and optimize the KL divergence between the LLM's ranking scores and the retriever's ranking scores to update the retriever, as shown in Figure 2. This retriever is denoted DE-Retriever (Distillation-based Exemplar Retriever). Intuitively, with the KL divergence loss function, the model tries to match the probability of retrieving an exemplar z k with the contribution of that exemplar to the generated SQL query a.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
We first obtain N exemplars with the highest scores based on Equation (1), denoted as Z top−N . Our loss function is defined as:
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
where SG denotes the stop gradient operation, G denotes the generator, and E denotes the retriever en-coder. We further compute p(z n | x, a, Z top−N ; G) as follows:
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
We approximate the posterior under the assumption that we have a uniform prior over the set of retrieved exemplars, so p(z n | x, Z top−N ) is approximated as 1 N . We further compute p(a | x, z n , Z top−N ; G) as:
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
More specifically, we use example z j as the prompt and concatenate it with test instance u and target SQL a. Then we feed it to the generator to compute the log probability of each token log(p(a i )) in the target SQL query a; p(a | x, z j ) can be computed as exp( log(p(a i ))).
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
For tasks such as information retrieval and opendomain question answering, reranking is widely adopted to further improve retrieval results by incorporating a reranker. Such a two-stage procedure is also useful in a variety of natural language processing tasks. In this work, following the retrieveand-rerank idea, we propose to incorporate an exemplar reranker in our framework. This reranker can leverage token-level interactions between the utterances to better rank the exemplars.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
More specifically, the query utterance u and the candidate utterance u z are concatenated together with special tokens:
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
The tokenized input is fed into a transformer model. An MLP with sigmoid activation is applied on top of the contextual embedding of the [CLS] token to obtain the relevance score of the candidate example . Sigmoid cross-entropy loss is used and the model is optimized to produce a relevance score as p(a|x, z n , Z top−N ; G). This reranker is denoted DE-Reranker (Distillationbased Exemplar Reranker).
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
From the input instance x and the list of retrievedand-reranked exemplars Z, we construct the augmented query by concatenating exemplars with the input instance following previous work (Hu et al., 2022;Rubin et al., 2022;Poesia et al., 2022;Liu et al., 2022;Brown et al., 2020;Pasupat et al., 2021). For the exemplar, we linearize the table schema, the question, and the SQL query. The exemplars are sorted by relevance score in descending order. For the test instance, only the table schema and the question are linearized. We denote this prompting approach Vanilla-P.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Translation as Chain of Thought: Recent work on chain-of-thought prompting is designed to solve the multi-step reasoning problem by providing intermediate reasoning steps before the final answer in the prompt (Wei et al., 2022). Inspired by this, we use the translation pair (from non-English to English in our case) as an intermediate step for cross-lingual semantic parsing inference. Specifically, a translation-based exemplar is inserted in front of Z. For example, in the right part of Figure 1, the grey box contains the Chinese version of the translation as a chain-of-thought prompt. The question in the prompt is in the target language, followed by an instruction Translate into English and the English translation of the question. Note that this translation-based exemplar is shared among all the test instances in that language, as shown in the left part of Figure 1. The translation-based examples are indexed by the language code, such as zh and vi. In this way, it only requires minimal translation effort to build the global translation-based exemplar. We denote this prompting approach Translation-P.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
For inference, we feed the constructed prompt to a large pre-trained language model to generate the target SQL query with greedy decoding. In this work, we consider Codex (Codex-Davinci-001) (Chen et al., 2021) because it has shown superior performance for the English Text-to-SQL task (Poesia et al., 2022).
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
In this section, we describe the datasets, implementation details, and baselines for our experiments.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
We create two benchmarks, XSPIDER and XKAGGLE-DBQA, by translating existing English Text-to-SQL datasets into other languages and evaluate our methods on these two benchmarks.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
XSPIDER: CSPIDER (Min et al., 2019) and VSPI-DER (Tuan Nguyen et al., 2020) are Chinese (zh) and Vietnamese (vi) cross-domain Text-to-SQL datasets translated from SPIDER . More specifically, we use the English SPIDER training set as the candidate pool and training data for retriever-reranker models. We use the development sets of CSPIDER and VSPIDER for cross-lingual evaluation. We further translate the SPIDER development set into Farsi (fa) and Hindi (hi) for a more comprehensive evaluation.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
XKAGGLE-DBQA: This is a recently constructed dataset for more realistic and challenging Textto-SQL evaluation. The dataset is based on 8 databases from Kaggle. We translate the questions into Chinese (zh), Farsi (fa), and Hindi (hi) for cross-lingual evaluation. We use the English SPI-DER training set as the candidate pool.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
For the exemplar retriever, we use 24-layer transformers initialized with the parameters of the mT5 encoder that is then fine-tuned on the English SPI-DER dataset for the Text-to-SQL task. For the exemplar reranker, we use InfoXLM (Chi et al., 2021) as the starting point. We train the retriever and reranker on the English SPIDER dataset and then apply both models to cross-lingual retrieval and reranking in a zero-shot fashion. For the Codex configuration, we use greedy decoding by setting the temperature to zero. We use N = 16 and K = 8 for all experiments, which means that the DE-Retriever first retrieves 16 exemplars from the candidate pool and the DE-Reranker produces the top 8 exemplars for prompt construction.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
In terms of evaluation metrics, we use Exact Match (EM) accuracy for both the XSPIDER benchmark and the XKAGGLE-DBQA benchmark. Following Zhong et al. (2020), we report the Testsuite (TS) accuracy. Only the datasets that are aligned with the SPIDER dev set can be evaluated with TS accuracy, so the XKAGGLE-DBQA benchmark is not applicable. Because the CSPIDER dev set is only partially aligned to the SPIDER dev set, the full CSPIDER (zh-full) dev set can be only evaluated with EM accuracy. We collect a subset of the CSPIDER dev set (zh) whose queries are aligned with the English SPIDER dev set, and further evaluate these using TS accuracy.  Table 1: Results on the XSPIDER dev set. "zh-full" and "zh" are two different splits from CSPIDER (Min et al., 2019). EM and TS are exact match accuracy and test suite accuracy, respectively. Entry (5) is based on the DE-Retriever with Vanilla-P. Entry (6) is based on the DE-Retriever and DE-Reranker (denoted as DE-R 2 ) with Vanilla-P. Entry (7) is based on DE-R 2 with Translation-P.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
mT5 zero-shot transfer is a baseline model that is trained with the English SPIDER training set. The model is based on the pre-trained sequenceto-sequence multilingual language model mT5large (Xue et al., 2021). This model has zero-shot cross-lingual transfer ability, with which the model can directly handle non-English utterances.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
mUSE and mSBERT are baselines that use unsupervised retrievers to obtain exemplars: multilingual Universal Sentence Encoder (Yang et al., 2020) and multilingual Sentence-BERT (Reimers and Gurevych, 2019). Prompts are then constructed for in-context learning with Codex.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Results on XSPIDER are shown in Table 1. We report the EM and TS accuracy. For the full CSPI-DER dataset (zh-full), since TS Accuracy is not supported, we only report EM accuracy. We report both TS and EM accuracy on the subset of CSPI-DER. Entry (1) reports the zero-shot performance of the mT5 model that is trained on the English SPI-DER dataset. On zh-full, vi, fa, and hi, the mT5 zero-shot method obtains on average 41.1 EM accuracy and 39.8 TS accuracy (average TS accuracy is computed without zh-full because the metric cannot be computed on the full CSPIDER). From entry (2) to entry (7), the methods are based on in-context few-shot learning. For entries (2-6), the prompting method is Vanilla-P. For entry (7), prompting with Translation-P is applied.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
With unsupervised exemplar retrievers such as mUSE and mSBERT, shown in entries (2) and (3), Codex performs worse than mT5 zero-shot transfer, especially for Farsi (39.5→31.1/31.8 on TS accuracy) and Hindi (39.7→23.7/22.3 on TS accuracy). By switching the unsupervised exemplar retriever to the mT5-encoder, which is the encoder component of the fine-tuned mT5 model, the effectiveness of Codex improves by a large margin. For example, on the CSPIDER subset, TS accuracy improves to 51.4 from 47.1, outperforming mT5 zero-shot performance by 3 points. This indicates that the exemplar retrieval component is essential to take advantage of the competitive performance of LLMs such as Codex. For languages such as Vietnamese and Farsi, Codex is comparable to mT5 zero-shot transfer, while for Hindi, there is still a large gap (39.7 vs. 27.0 on TS accuracy).
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
By applying our proposed distillation based retriever-reranker pipeline (denoted as DE-R 2 ) for retrieving exemplars, impressive improvements can be observed in all four languages by comparing entry (6) with entry (4). Our end-to-end results are shown in entry (7), where we see that our proposed framework achieves the best results for most of the languages (except Vietnamese EM accuracy) in the in-context learning setting.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Comparing the best results of in-context learning with mT5 zero-shot results, we can see that Codex can achieve better performance in Chinese, Vietnamese, and Farsi. For example, XRICL outperforms mT5 zero-shot by 7.7 EM accuracy on the full dev set of CSPIDER. One exception is Hindi, where the best in-context learning performance cannot match mT5 zero-shot transfer. One possible explanation is that Codex has weaker modeling ability in Hindi because less Hindi data were accessible during the training. (1) mT5 zero-shot 9.7 8.1 7.6 (2) mUSE 20.7 12.4 16.2 (3) mSBERT 14.7 13.0 11.9
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
(4) mT5-Encoder 22.2 16.8 16.2 (5) DE-Retriever 26.5 18.4 16.8 (6) DE-R 2 27.0 18.4 17.8 (7) + Translation-P 28.1 20.0 19.5 Table 2: Results on the XKAGGLE-DBQA test set. We report exact match (EM) accuracy.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
There is agreement by researchers today that XKAGGLE-DBQA is a more realistic evaluation for the Text-to-SQL parsing task. The databases are real-world databases with abbreviated column names. We use the training set of English SPIDER as the candidate pool. In this case, both the model's generalization ability and its cross-lingual transfer capability can be tested.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
The XKAGGLE-DBQA results are shown in Table 2. Entry (1) shows the zero-shot cross-lingual cross-domain transfer performance of the mT5 model trained on the English SPIDER dataset. For example, on Chinese KAGGLE-DBQA, mT5 only obtains 9.7 EM accuracy. For comparison, mT5 reach 20.0 EM accuracy on the English test set in a zero-shot fashion, outperforming the previous state of the art obtained by RAT-SQL (Wang et al., 2020) with 18.4 EM accuracy  using column descriptions and model adaptation. This indicates that the mT5 model is more robust than RAT-SQL on domain transfer. However, the effectiveness degrades drastically when mT5 is applied to non-English languages. The mT5 zero-shot method on average obtains only 8.5 EM accuracy in the three languages.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
For the Codex-based in-context learning methods, the results are shown in entries (2-7). With unsupervised retrieval methods such as mUSE, Codex can reach 20.7 EM accuracy in Chinese, improving over the zero-shot mT5 baseline. Comparing entries (2) and (3), there is no clear winner for these two unsupervised retrieval methods. Our end-toend results are shown in entry (7), which achieves state-of-the-art performance on the XKAGGLE-DBQA benchmark, with 22.5 EM accuracy on average, which is better than the mT5 zero-shot method. For example, on Chinese KAGGLE-DBQA, our framework obtains an 18.4 point improvement over mT5 zero-shot transfer.  We show that our model is comparable to other in-context learning methods for English semantic parsing. Through this comparison, we show that our framework is built on a competitive backbone for Text-to-SQL. We use the DE-Retriever as the backbone model in the ablation study and compare with three recent methods, described as follows: Rubin et al. (2022) used hard labels obtained from the generator to train the retriever. Poesia et al. (2022) used the tree edit distance of SQL queries as a similarity function: a smaller distance means better exemplar quality for the specific test instance. The ranking model is optimized to predict the target SQL pair tree edit distance based on the utterance pair. Rajkumar et al. (2022) designed an efficient prompt that leverages table contents for zero-shot Text-to-SQL. We refer the reader to the original papers for more details. Table 3 shows the results on the SPIDER development set. Our backbone system (DE-Retriever + Codex Generator) obtains 53.5 EM accuracy and 60.3 EX accuracy, which is comparable to the 60.0 EX accuracy reported by Poesia et al. (2022). Comparing to Rajkumar et al. (2022), our system obtains comparable TS accuracy (56.3 vs. 55.1).
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
We analyze the effectiveness of DE-R 2 on the XSPIDER benchmark and the XKAGGLE-DBQA benchmark. By comparing entries (5) and (4) in Table 1 and Table 2, we can observe that the DE-Retriever can improve over the mT5-encoder baseline in most of the languages (except EM accuracy in Farsi). Comparing entries (6) and (5), we find that the reranker can further improve the EM accuracy and the TS accuracy. This indicates that our XRICL framework is effective in selecting good  exemplars as prompts.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
By comparing entries (7) and (6) in Table 1 and Table 2, we find that Translation-P can further improve the semantic parsing ability of Codex on top of DE-R 2 , except EM accuracy for Vietnamese.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
It is interesting to investigate the upper bound of Codex on cross-lingual Text-to-SQL semantic parsing. We design two pipelines to experiment with the capabilities of Codex when an oracle is available (i.e., the target SQL query is accessible to help the retrieval and reranking). We experiment with two different oracles:
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Template Oracle: We retrieve exemplars using the gold parse. The template is extracted from the target SQL query and only exemplars with the same SQL template are retrieved. This is based on the assumption that utterances with the same SQL templates share the same query intent and the generator can benefit from these exemplars.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Template Oracle + Codex LM oracle: Here we introduce an oracle from the generator (Codex) into the pipeline. More specifically, we replicate the training process in the testing phase. The exemplars with the same SQL templates are first retrieved. For each retrieved exemplar, we use Codex to compute its contribution to the test instance as the reranking score. We then use the top-k as the exemplars.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
The experimental results are shown in Table 4. Comparing entries (1) and (2) 
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
In this work, we proposed the XRICL framework that improves in-context learning for crosslingual Text-to-SQL semantic parsing. The retrieveand-rerank models that we propose can learn signals from large pre-trained models (Codex) to improve the quality of selected exemplars, which can further benefit the generator. By integrating prompts inspired by chain of thought, our proposed Translation-P method can bridge the crosslingual gap for the generator. Extensive experiments on XSPIDER and XKAGGLE-DBQA demonstrate the effectiveness of our framework, which obtains state-of-the-art performance on few-shot in-context learning in most of the datasets, thus unlocking the potential of Codex.
XRICL: Cross-lingual Retrieval-Augmented In-Context Learning for Cross-lingual Text-to-SQL Semantic Parsing
Our work is based on the large language model Codex, which is not open-sourced. To replicate our experiments, an application to OpenAI for Codex API access is required. Due to annotation costs, we were unable to evaluate on more languages than those described in this paper. In the future, we plan to collect more data to investigate Codex performance on different language families.
Synchromesh: Reliable code generation from pre-trained language models
Large language models (LLMs) trained on massive corpora of unsupervised data have been shown to perform a wide range of tasks, including natural language generation, semantic parsing and sentiment analysis (Brown et al., 2020;Devlin et al., 2019;Raffel et al., 2020). This can be achieved without task-specific training, but rather by adapting the model to each task at test-time using textual prompts, which can contain examples and natural language descriptions. In many cases, this methodology was shown to provide good performance, reducing the need to annotate large datasets for each task of interest (Brown et al., 2020;Shin et al., 2021).
Synchromesh: Reliable code generation from pre-trained language models
An important application of LLMs is in synthesizing programs from natural language descriptions (Austin et al., 2021;Chen et al., 2021). But this task is still challenging for LLMs. First, they can commit conceptual errors, generating code that misses the intent behind the given description. For example, when asked to reverse an array, the model might generate code that simply swaps the first and last elements. Indeed, users of current natural language-to-code systems report that models often produce code that is unrelated to their query (Xu et al., 2021). Figure 1: Overview of the SYNCHROMESH framework. Given the user's query, high-relevance examples are first retrieved with Target Similarity Tuning (TST). Then, a program is incrementally sampled via Constrained Semantic Decoding (CSD), which queries a completion engine (CE) to enforce constraints during code generation without re-training or fine-tuning the language model. Even when they capture the right intent, LLMs can still make implementation errors: the generated code can fail to execute. For reversing an array, a model might generate a loop with the correct structure but with an off-by-one error, causing a runtime exception. These errors are common even with very large models. For example, Austin et al. (2021) tested models with up to 137B parameters on generating short Python programs from natural language. Still, 47% of the failures were due to syntax, typing or run-time errors (as opposed to running but producing incorrect output). This is in line with theoretical results in Merrill et al. (2021) showing that programming language semantics cannot be fully inferred from ungrounded data. Together, both observations suggest that simply scaling up LLMs might be ineffective to obtain reliable performance, especially for longer programs.
Synchromesh: Reliable code generation from pre-trained language models
In this paper, we address both conceptual and implementation errors with SYNCHROMESH, a framework for reliable code generation from pre-trained models. Since LLMs are highly sensitive to which few-shot examples are given in their prompt, we propose Target Similarity Tuning (TST): a method for dynamically selecting semantically relevant examples for a given description. TST mitigates conceptual errors by learning to select examples with similar intent, even when their natural language descriptions seem unrelated in form. Given relevant examples, we then generate programs with Constrained Semantic Decoding (CSD), a novel method for enforcing rich syntactic and semantic constraints during code generation on top of a frozen language model. Rich language-specific constraints, ranging from syntax validity to scoping and type-checking, can be implemented under the simple abstraction of completion engines (CE). CSD aligns these constraints with the language model's token vocabulary by leveraging Brzozowski language derivatives (Brzozowski, 1964). This guarantees that all sampled programs satisfies the implemented constraints, preventing whole classes of implementation errors by construction. The pipeline is illustrated in Figure 1.
Synchromesh: Reliable code generation from pre-trained language models
We demonstrate the generality of SYNCHROMESH in three real-world languages: SQL (database queries), Vega-Lite (data visualization) and SMCalFlow (calendar applications). In experiments with GPT-3 and Codex, we observe that SYNCHROMESH can eliminate whole classes of errors that make outputs from unconstrained models either fail to execute or produce trivial results (e.g., empty charts). Furthermore, eliminating invalid programs consistently improves prediction accuracy. In summary, we make the following contributions:
Synchromesh: Reliable code generation from pre-trained language models
• We propose Target Similarity Tuning for selecting few-shot examples based on the similarity of the programs they describe, improving relevance and downstream performance.
Synchromesh: Reliable code generation from pre-trained language models
• We introduce completion engines as an abstraction that can implement rich classes of semantic program constraints, as we demonstrate in SQL, Vega-Lite and SMCalFlow.
Synchromesh: Reliable code generation from pre-trained language models
• We introduce a general, constraint-observing decoding algorithm, which aligns programming language constraints with the language model's token vocabulary.
Synchromesh: Reliable code generation from pre-trained language models
• We evaluate our method in three natural language-to-code tasks. CSD and TST both show strong complementary gains in output validity and prediction accuracy across domains. Figure 2: Example of Target Similarity Tuning improving example selection for synthesizing a SQL query. In (a), the prompt example missed the key query structure (grouping and counting). With this example, GPT-3 generates an invalid query (b). With TST, we retrieve a relevant example which GPT-3 successfully adapts to answer the user's question (c).
Synchromesh: Reliable code generation from pre-trained language models
In this section, we first overview the challenge posed by conceptual errors in programs synthesized by LLMs. We then introduce TST, which improves performance through more relevant example selection. Throughout, we will use a real example of synthesizing a SQL database query to answer a question posed in natural language.
Synchromesh: Reliable code generation from pre-trained language models
Suppose a data analyst has a relational database of airports and wants to answer the following question: "Which city has the highest number of airports?" One procedure for turning this description into a SQL query is to use an LLM such as GPT-3 (Brown et al., 2020) or Codex (Chen et al., 2021). To prompt the model for the task at hand, we would feed it with a natural language description of the task and a selection of input-output examples.
Synchromesh: Reliable code generation from pre-trained language models
Given the analyst's question, how do we select the most relevant examples from a training pool? Liu et al. (2021a) proposed to retrieve examples with similar natural language descriptions using a pre-trained paraphrase detection model. Figure 2a shows the most similar example from the Spider natural language-to-SQL dataset (Yu et al., 2018) according to Sentence-BERT (Reimers & Gurevych, 2019). The query "Which city has the highest elevation?" is similar on a surface level: it also asks "Which city has the highest ?". This training query asks about "elevation", a property that is readily available as a column in the Airports table. Figure 2b shows GPT-3's output when given this and a few other examples. The model attempts to mimic the top example, referring to a nonexistent column "NumberOfAirports". The issue is that we picked the example in the prompt based on description similarity and not SQL query similarity. In fact, the SQL query in the chosen example had a simplistic structure that was significantly different from the structure of the desired SQL query, and this contributed to the failure at Point (b) in Figure 2.
Synchromesh: Reliable code generation from pre-trained language models
We want to retrieve examples that have relevant program structures for the test query. We do so using our fine-tuning scheme called Target Similarity Tuning (TST). Formally, suppose D is a dataset of programs and associated utterances, with D i = (p i , u i ). Let S(p a , p b ) ∈ [0, 1] denote a normalized similarity metric between programs. If f θ is a pre-trained similarity model for natural language sentences, TST consists in fine-tuning f to predict the similarity between target programs given by S from their descriptions. Precisely, we minimize the mean-squared error loss:
Synchromesh: Reliable code generation from pre-trained language models
We define S using the classical tree edit distance algorithm from Zhang & Shasha (1989) to compare Abstract Syntax Trees (ASTs). Figure 2c shows GPT-3's output when given examples selected with TST. Now, the output query is correct: it performs a "group by" on the "City" column, and sorts by the count of records in each group. This structure was already present in the top example selected by TST, corresponding to "Return the team with the most technicians". Even if the analyst's question and this utterance are drastically different in natural language, they share similarity in the SQL query that they describe. The TST objective is able to properly capture this fact. As our experiments show in Section 4, TST significantly boosts the performance of both GPT-3 and Codex. 
Synchromesh: Reliable code generation from pre-trained language models
We now present Constrained Semantic Decoding (CSD) as an approach to eliminate implementation errors from code generated by LLMs. We first illustrate CSD with an example, and then formalize it using the abstraction of CEs.
Synchromesh: Reliable code generation from pre-trained language models
The example in Figure 2 showed that TST can help LLMs generate the correct program. In general, however, TST only helps LLMs by guiding toward the correct structure, but the model still needs to fill all the specific implementation details correctly. Figure 3 shows a case where the model cannot simply adapt one example from the prompt. Here, the user's query is "Which city has the highest number of departing flights?" This query is similar to the previous one -in fact, TST retrieves the same top-1 example as before. But now the correct SQL query needs to join the "Airports" and "Flights" tables. GPT-3 generates the join condition Flights.AirportCode = Airports.SourceAirport, but this condition has a subtle error: the column names of the two tables are swapped. Thus, this query fails to execute. In general, unconstrained language models often make such implementation errors: using undeclared variables, losing track of nesting levels when producing complex expressions, or calling functions using arguments of the wrong type. Even the smallest of such errors prevents generated code from executing.
Synchromesh: Reliable code generation from pre-trained language models
CSD prevents implementation errors by construction (as opposed to repairing after-the-fact). Imagine we have access to an oracle, which we call a CE, that can take a partial program and return all tokens that can extend that partial program toward a complete correct program. When the LLM is generating the program token by token, CSD ensures that the next token is sampled from the set returned by the CE.
Synchromesh: Reliable code generation from pre-trained language models
In Figure 3, after generating "T1." inside the "on" clause, our SQL CE resolves the alias and constrains the model to output one of the columns from the "Flights" table. This fixes the error seen previously during generation and produces the correct SQL query.
Synchromesh: Reliable code generation from pre-trained language models
We now formally define CEs. Let Σ be a base alphabet, and Σ L ⊆ Σ * be the (potentially infinite) set of tokens of the target language. Our goal is to sample programs from a language L ⊆ Σ * Lthe set of valid programs. A CE C L is a partial function from Σ * L to a set of tokens. We use a regular expression over Σ to represent a set of tokens. The strings in the domain of C L are called completion points, and a CE satisfies the following axioms: (A1) The empty string and every p ∈ L must be completion points. For every p ∈ L, C L (p) = r $ , where r $ is the regular expression that matches the stop token. (A2) If s ∈ Σ * L is a completion point and t fully matches C L (s), then their concatenation st must also be a completion point. (A3) The CE is exhaustive; that is, if s is a completion point and s = tt 0 , where t 0 is a token, then t should be a completion point and C L (t) should match t 0 . Furthermore, we assume that CEs are only called after maximal matches. For example, if a partial program ends in an identifier, the CE can assume that the identifier is complete. {"x": {"field": "Category", "type": ∧ "nominal" "temporal" × Do not facet on field with too many distinct values (breaks rendering).
Synchromesh: Reliable code generation from pre-trained language models
{"column":{"field": ∧ "Category" "ZipCode" ×  Table 1: Examples of constraints implemented in our CEs for SQL, Vega-Lite and SMCalFlow. Given a partial program, CEs return a regular expression that matches the valid tokens that can follow. Here, we show positive and negative token examples for each such regular expression. This abstraction allows domain experts to encode a wide range of expressive code generation constraints.
Synchromesh: Reliable code generation from pre-trained language models
Our CEs are implemented in two layers: a context-free layer, which enforces syntactic validity, and a context-sensitive layer, which encodes semantic constraints that depend on language semantics and the user's context (e.g., the database). Below, we describe an automatic method for constructing context-free CEs directly from the target language's grammar. The context-sensitive layer of an engine is specific to the target language. Table 1 provides an overview of several constraints implemented by our CEs for SQL, Vega-Lite and SMCalFlow, three rich languages with different syntactic and semantic structures. A detailed description of the three CEs can be found in Appendix C.
Synchromesh: Reliable code generation from pre-trained language models
Deriving completions from grammars Computer language parsers are often automatically generated from a grammar. The grammar contains enough information to derive the context-free layer of CEs. To facilitate this process, we created a library that extends any parser generated by ANTLR (Parr & Fisher, 2011), a popular LL( * ) top-down parser generator, to provide token-level completions. Namely, we (i) let the ANTLR-generated parser process the given program prefix p, (ii) retrieve its state in the Augmented Transition Network (ATN) at the last program token, (iii) traverse the ATN from that state to enumerate all possible next token productions. This process yields (a) a list of productions and token types {τ j } K j=1 that are allowed to follow p and (b) a partial AST T p . Each CE takes {τ j } and T p as input to generate semantic context-sensitive constraints.
Synchromesh: Reliable code generation from pre-trained language models
We use CEs to guide sampling from an LLM. A key component of our algorithm for constrained sampling is a decision procedure for membership in prefix-closure of the set L of all valid programs. The prefix-closure L c of a language L contains all programs in L as well as all of their prefixes. Intuitively, L c contains all partial programs that can be completed to a valid program. Given a CE C L , our first goal is to build a decision procedure for L c : given a string s, does it belong to L c ?
Synchromesh: Reliable code generation from pre-trained language models
We answer if s ∈ L c by repeatedly calling C L on certain prefixes p of s and matching the regular expression C L (p) with suffixes of s. We start with p being the empty string. We find the maximal prefix of s that matches the regular expression C L (p) and remove it from s and add it to p, and repeat until the match fails. There are two cases: either s is empty now, which means the input string was a completion point and hence it is in L c , or s now is the remainder left after removing the largest prefix that was a completion point. For the second case, we must check: does there exist a completion string c such that sc fully matches the regular expression C L (p)?
Synchromesh: Reliable code generation from pre-trained language models
This question can be efficiently answered by Brzozowski derivatives (Brzozowski, 1964). Formally, the derivative of a formal language S with respect to a string u is another formal language u −1 S = {v : uv ∈ S}. In other words, it is precisely the set of strings that can complete u to some string in S. If u −1 S = ∅, then no string in S starts with u. Brzozowski derivatives are efficient to compute for our regular languages (or regular expressions defining them) -we describe a simple linear-time algorithm in the Appendix. Given the derivative of C L (p), answering whether s can be completed to belong to C L (p) reduces to performing a simple regular expression match. This operation answers the case when the remainder is non-empty and completes our decision procedure for L c .
Synchromesh: Reliable code generation from pre-trained language models
Using the decision procedure for L c , we can now describe the Constrained Semantic Decoding algorithm. Suppose s ∈ L c is the language model's output so far (we start with ). If Σ M is the model's vocabulary, we can compute the set of valid next tokens V M (s) = {t ∈ Σ M : st ∈ L c } by using our decision procedure for each token in the vocabulary Σ M . In other words, we maintain the invariant that the model's current partial output s is in L c , and make progress by using the model to sample from V M (s), instead of the unconstrained Σ M . Once we have a complete program, we are guaranteed that it will satisfy all constraints enforced by the CE.
Synchromesh: Reliable code generation from pre-trained language models
One subtlety to note is that language models and programming languages have drastically different tokenizations; i.e., C L and LLM work with different tokens. For instance, a long string literal is a single SQL token, but might span multiple tokens for the language model. Similarly, a single token from the language model's vocabulary might close multiple parentheses at once. In general, token boundaries between the two can be arbitrarily misaligned. Each decision of whether st belongs to L c can potentially cross multiple completion points, or might not even finish a maximal match to the previous completion point (see the Appendix for an example prediction in Vega-Lite where this happens multiple times). Nevertheless, our CSD algorithm described here naturally handles this alignment problem. Hence, in SYNCHROMESH, CEs do not need to be aware of this issue -they can be fully implemented in terms of the target language's tokens. 1
Synchromesh: Reliable code generation from pre-trained language models
Our implementation applies substantial optimizations that leverage the structure of Byte-Pair Encoding vocabularies (namely, that many tokens are prefixes of longer tokens) and reuse computation. We detail these optimizations in Appendix E. In our experiments with GPT-3, CSD adds an average of 8% overhead to the sampling procedure -a relatively small impact to trade for output correctness.
Synchromesh: Reliable code generation from pre-trained language models
We evaluate SYNCHROMESH in three tasks of synthesizing code from natural language descriptions. For SQL, we use the Spider dataset (Yu et al., 2018). For Vega-Lite, we use the NLV Corpus (Srinivasan et al., 2021). For SMCalFlow, we use the dataset that introduced the language (Andreas et al., 2020). In NLV, which has visualizations over 3 different datasets, we alternate using each dataset as a test-set by only using training examples from the other two datasets. In Spider and SMCalFlow, we use the training/validation set split given in each dataset.
Synchromesh: Reliable code generation from pre-trained language models
To select examples, we use Sentence-BERT (Reimers & Gurevych, 2019) to fetch the 5 closest examples by cosine similarity. When using TST, we fine-tuned the model with the TST objective in both the Spider and SMCalFlow training sets. The NLV corpus is smaller and does not provide a clear train-test split to fairly evaluate TST. Holding out one dataset and fine-tuning on the remaining two yields SYNCHROMESH accuracies of over 90%. However, we attribute that performance to the fact that NLV has only 10 distinct visualizations and the same participants labeled all three datasets. For that reason, we omit Vega-Lite from the TST experiments. Exec. Valid Dist. Acc. Valid Dist. Acc. Valid Dist. Language models We used the two largest models from the GPT-3 family (Brown et al., 2020, with 13B and 175B parameters), as well as the largest Codex model (Chen et al., 2021). Codex shares the same architecture with 175B GPT-3, but its training set contained a larger portion of source code in a variety of languages. Our only access to the models was through the public OpenAI HTTP API, which allowed us to apply constraints by adding a bias to logits. We describe the necessary adaptations of CSD to this setting in Appendix F.
Synchromesh: Reliable code generation from pre-trained language models
Metrics For Vega-Lite and SMCalFlow, we report the exact-match accuracy between predictions and ground-truth (field order is disregarded in Vega-Lite). In SQL, we instead measure execution accuracy, comparing query results instead. For a more fine-grained signal, we additionally measure the edit distance between the predicted and ground-truth ASTs using the normalized tree edit distance (Zhang & Shasha, 1989).
Synchromesh: Reliable code generation from pre-trained language models
Table 2 and Figure 4 summarize the results of evaluating SYNCHROMESH versus various baselines.
Synchromesh: Reliable code generation from pre-trained language models
The key observations are as follows:
Synchromesh: Reliable code generation from pre-trained language models
SYNCHROMESH improves reliability on top of all pre-trained LLMs. First, it improves top-1 accuracy (exact or execution-measured) over any pre-trained LLM in all domains. SMCalFlow benefits the most, likely because this domain-specific language is absent in the LLM pre-training corpus. For SQL and SMCalFlow, the absolute gain is almost the same for equally-sized GPT-3 and Codex.
Synchromesh: Reliable code generation from pre-trained language models
Second, SYNCHROMESH dramatically improves validity. In SQL, it eliminates execution errors from 29% of the queries generated by GPT-3 13B (as validity improves from 43% to 72%). Even Codex benefits, with 12% more queries executing successfully after SYNCHROMESH augmentation. In Vega-Lite and SMCalFlow, SYNCHROMESH improves reliability even more substantially. GPT-3 13B only produces valid charts for 55% of the queries in NLV; all errors are eliminated with SYNCHROMESH. This is nearly paralleled in SMCalFlow, in which all models produce well-typed programs 97% of the time or more with SYNCHROMESH. SYNCHROMESH brings the output closer to ground truth. While error prevention alone is trivial (e.g., with a constant error-free prediction), that would improve neither accuracy nor the average edit distance to the ground-truth, unlike SYNCHROMESH results. Again, we observe improvements in all domains and the most in SMCalFlow. For GPT-3 175B, SYNCHROMESH reduced the average edit distance from 0.41 to 0.18.
Synchromesh: Reliable code generation from pre-trained language models
TST and CSD bring complementary benefits. Our ablation studies reported in Table 2 show that their combination performs better than either one separately. TST helps LLMs generate programs in the "vicinity" of the correct one, and CSD helps by "guiding" the models toward the correct one.
Synchromesh: Reliable code generation from pre-trained language models
SYNCHROMESH adds more value for longer programs. Program synthesis is hardest when the target program is complex. Does SYNCHROMESH improve synthesis of longer programs, or are its benefits coming from fixes to small programs? Figure 4(a) shows accuracies and (b) validity for SMCalFlow broken down by the length of the ground truth program (we show results for SQL in the Appendix).
Synchromesh: Reliable code generation from pre-trained language models
Here, program lengths are shown as their percentile. With SYNCHROMESH, we see that accuracy decays at a slower pace, and validity remains high throughout, when compared to Codex alone. This indicates that SYNCHROMESH improves the ability of base models to generate longer programs.
Synchromesh: Reliable code generation from pre-trained language models
LLMs augmented with SYNCHROMESH approach but underperform supervised models. For context, we include state-of-the-art results at the time of writing for each task in Table 2. We note that these methods fine-tune or train the underlying language-to-code model on each task, thus are not directly comparable to LLMs with SYNCHROMESH. That said, we observe that base LLMs-even Codexsubstantially underperform supervised models (19% worse for SQL; 27% worse for SMCalFlow), and SYNCHROMESH helps narrow that gap (now 11% worse for SQL; 9% worse for SMCalFlow).
Synchromesh: Reliable code generation from pre-trained language models
SYNCHROMESH outperforms "generate-then-test". CSD enforces program constraints during generation. Instead, prior work has leveraged a "generate-then-test" approach: take multiple samples and filter out those that produce errors or violate constraints (Chen et al., 2021). Figure 4(b) evaluates this approach with Codex, the highest performing base LLM. We sample from Codex with a temperature τ = 0.7 to obtain diverse but high-quality samples. We then compute the "Valid@K" metric by using the "Pass@K" estimator from Chen et al. (2021) to calculate the probability of at least one valid sample among K, with K ≤ 5. In SQL, Codex needs 3 samples to match SYNCHROMESH (Valid@K = 85%). In SMCalFlow and Vega-Lite, SYNCHROMESH is able to virtually eliminate errors with 1 sample, while "Valid@5" for Codex is still below 93%. This provides evidence that even the best LLMs benefit from incremental validation, especially in less popular languages.
Synchromesh: Reliable code generation from pre-trained language models
In our experiments, SYNCHROMESH was able to improve accuracies and program validity across all languages due to better examples to use as a reference (TST) and preventing errors during generation (CSD). Yet, this approach has an important limitation. While TST can reduce conceptual errors, and CSD can guarantee that certain implementation errors never occur (e.g., type errors in SMCalFlow, Figure 5: Illustration of implementation and conceptual errors in Vega-Lite. CSD can avoid generating the invalid Vega-Lite mark type "scatterplot", though conceptual errors can still remain.
Synchromesh: Reliable code generation from pre-trained language models
or undefined column references in Vega-Lite or SQL), TST cannot guarantee elimination of conceptual errors. When those occur, CSD is usually insufficient to correct the prediction. Figure 5 shows an example in Vega-Lite from the "Cars" dataset in NLV. Here, the user asks for one scatter plot for each origin, indicating faceting (multiple charts). GPT-3 alone produces an invalid Vega-Lite chart type, "scatterplot". CSD can eliminate this error, guiding GPT-3 to generate "point" instead. However, a conceptual error remains: instead of faceting, the model colors points by their origin. Codex produces the correct Vega-Lite mark type, but still makes the same conceptual mistake.
Synchromesh: Reliable code generation from pre-trained language models
Nonetheless, we argue that improving validity is especially important for user-facing applications. Users of language-to-code systems might need to rephrase their request or to edit the system's output. But outputs that fail to even execute undermine user experience: fixing an automatically generated program can be more cumbersome than writing it in the first place. In LLM-driven systems like Github Copilot, implementation errors can remain unnoticed and introduce bugs or vulnerabilities.
Synchromesh: Reliable code generation from pre-trained language models
Program synthesis is a long-standing AI challenge with the goal of generating computer programs from higher-level specification (Gulwani et al., 2017). In particular, synthesis from natural language descriptions has gained recent attention (Liu et al., 2016;Yaghmazadeh et al., 2017), thanks to advances in natural language processing models such as Transformers (Vaswani et al., 2017). Typically, LLMs such as GPT-3 (Brown et al., 2020) and Codex (Chen et al., 2021) output an unconstrained sequence of tokens, and still often make conceptual or implementation errors in generated programs (Austin et al., 2021). Specialized training, e.g. to output an AST (Wang et al., 2020;Yin & Neubig, 2017), can mitigate syntactic errors, but still does not guarantee accuracy or conformance to domain-specific semantic constraints. Moreover, it requires a specialized architecture and a decoding procedure for each target language. Instead, SYNCHROMESH applies such constraints at inference, neither using specialized architectures nor fine-tuning the LLM.
Synchromesh: Reliable code generation from pre-trained language models
The general idea of constraining LLMs when generating programs has been explored in recent work. Shin et al. (2021) applied syntactic constraints for semantic parsing. However, their method requires enumerating all valid programs for determining valid next tokens for the LLM, and does not enforce semantic constraints. In concurrent work, Scholak et al. (2021) applied similar semantic constraints to synthesizing SQL queries. The authors substantially improve the performance of an already finetuned model by leveraging an incremental parser. We see CSD as a generalization of these efforts, as our completion engines can apply context-sensitive constraints by dynamically constructing regular expressions. Aligning these constraints with the underlying model vocabulary does not require finetuning: SYNCHROMESH only trains the much smaller target similarity model (Section 2).
Synchromesh: Reliable code generation from pre-trained language models
Since the emergence of LLMs, researchers have developed numerous techniques to adapt them to new domains (Liu et al., 2021b). Many focus on prompting, i.e. generating a domain-and instancespecific input to an LLM to increase the likelihood of correctness. In few-shot prompt augmentation, Gao et al. (2020) use pre-trained sentence embeddings to select the closest prompt examples to the given input instance. Liu et al. (2021a) further fine-tune sentence embeddings on the available training set of input utterances. TST in SYNCHROMESH takes this approach a step further, and finetunes the embedding models based on output similarity. It optimizes the amount of relevant output bits in the prompt, thereby reinforcing the necessary hints for the LLM.
Synchromesh: Reliable code generation from pre-trained language models
SYNCHROMESH augments program synthesis with pre-trained LLMs to prevent both conceptual and implementation errors in their generated programs. We designed SYNCHROMESH to be easily usable for any domain with minimal NLP or LLM knowledge expected from a domain expert. As such, it (a) automatically generates the completion engine API from the language grammar, (b) does not require fine-tuning the underlying LLM, drastically reducing the data/compute budget, and (c) integrates into the decoding loop or inference API with minimum computational overhead. Our method significantly improves performance of both GPT-3 and Codex in three real-world programming languages, both by boosting prediction accuracy and consistently improving output validity.
Synchromesh: Reliable code generation from pre-trained language models
While real-world and well-established, the domains we study are still not Turing-complete. We envision extending SYNCHROMESH to a Turing-complete language like Python can vastly increase reliability of LLM-based systems like Github Copilot. This requires further extension of CSD to integrate with the parser/interpreter of the target language, and to study applicable classes of constraints. The TST technique, however, can be used in any LLM-based language-to-code system. A CONSTRAINED SEMANTIC DECODING ALGORITHM In Section 3.3, we described the Constrained Semantic Decoding algorithm in the text. We provide the same algorithm in pseudo-code in Algorithms 1 and 2 in Figure 6 below. ValidPrefix is our decision procedure for L c , while CSD samples a complete program from the model M by making calls to ValidPrefix. We use s · t to denote concatenation of s and t, and s −1 · t to denote the Input : A LLM-based token generator, M Input : Its token set ΣM Output: String generated by M , constrained by CL s ← next token ← ""; while next token = "$" do valid tokens ← {t ∈ ΣM | ValidPrefix(st)}; next token ← Sample(M (s), valid tokens); s ← s · next token; end return s;
Synchromesh: Reliable code generation from pre-trained language models
Input : A string s Output: True iff s ∈ L c p ← next prefix ← ""; while next prefix = ⊥ do p ← p · next prefix ; s ← next prefix −1 · s; regex ← CL(p); next prefix ← startswith(s, regex ); end return (s −1 · regex = {}); string obtained by removing the prefix s from t. The utility function startswith(s, r) returns the maximal prefix of s that matches the regular expression r, and returns ⊥ if there is no such match. The function Sample(Dist, S) returns a token from the set S of tokens sampled from the distribution Dist restricted to S. The CSD procedure uses the model M on the partial program to generate a distribution on the next token, but constrains it to belong to the set of valid tokens determined by the completion engine C L .
Synchromesh: Reliable code generation from pre-trained language models
Regular expression derivatives can be expensive to compute in general. The main challenge is that Klenee stars fork the decision procedure: the algorithm must decide to repeat or skip the pattern inside a star. However, in this work, all our regular expressions come from grammars of programming languages. These languages have one important feature in common: tokens are defined by greedy matching rules. This means that Klenee stars consume as many characters as possible, and do not backtrack if a tokenization error occurs (the error simply propagates). Under the assumption that Klenee stars have greedy semantics, derivatives can be computed in linear time. The algorithm for computing derivatives of a regular expression can be worked out by looking at all constructors of regular expressions.  
Synchromesh: Reliable code generation from pre-trained language models
Here, we describe our completion engines for SQL, Vega-Lite and SMCalFlow in more detail.
Synchromesh: Reliable code generation from pre-trained language models
C.1 SQL SQL database queries are executed in the context of a particular database containing a set of tables. Each table has a schema, which specifies named columns, their data types and constraints such as foreign keys. We refer to Yu et al. (2018) for a more detailed description of the SQL language.
Synchromesh: Reliable code generation from pre-trained language models
Our CE for SQL enforces that only columns that exist in the tables in the database are used. The main challenge is that queries often specify aliases. Thus, during parsing, we construct a symbol table mapping aliases to the tables they refer to. We enforce that tables that already have an alias should only be referred to by their alias, not in their unqualified form. Since aliases can be referred to in the SELECT clause before being defined in the FROM clause, we also keep track of undefined aliases to enforce that they will be assigned a table later. Moreover, a condition in the WHERE clause might involve a nested query, which in its turn might redefine or create new aliases. As a result, our symbol table keeps a stack of scopes to properly resolve aliases in nested contexts.
Synchromesh: Reliable code generation from pre-trained language models
We constrain numeric literals to either come from a set of common numbers (including 0 and 1) or from the user's natural language question. This prevents the model from copying arbitrary numbers from the few-shot examples in the prompt. Finally, since SQL is case-insensitive, our CE returns case-insensitive regular expressions for keywords, table and column names.
Synchromesh: Reliable code generation from pre-trained language models
Vega-Lite is a declarative language for specifying data visualizations given a data frame -a table where rows represent data points and columns represent attributes of various data types. Its syntax is a subset of JSON. Therefore, our Vega-Lite grammar accepts JSON objects that follow a subset of the Vega-Lite schema.
Synchromesh: Reliable code generation from pre-trained language models
As in SQL, we use the user's data frame to constrain valid field names. Additionally, in Vega-Lite, one must also specify a Vega-Lite type that is used to interpret the field values. We inspect the runtime values in the data frame to determine compatible Vega-Lite types. For example, a string column is typically used as a categorical value (nominal, in Vega-Lite). However, if its entries have ISOformatted timestamps, it can be used as temporal, or quantitative if its values can be parsed as numbers. Since JSON objects are unordered, it must handle two valid output orders: the model might output the field name first (we thus later constrain the type) or the data type first (we then constrain the field name to compatible columns). Because Vega-Lite's behavior is to silently ignore invalid data points, associating a column with an incompatible type simply produces an empty chart. Our constraint completely prevents this class of errors.
Synchromesh: Reliable code generation from pre-trained language models
We forbid repeated fields and limit the length of free-form string literals to 30 characters, which prevents the common failure mode of language models to enter repetition loops. Similarly, we only allow an aggregation in one of the X-Y axes, but not both, since that collapses the chart to a single data point and is another common failure case. Finally, we prevent the model from faceting (i.e., splitting into multiple charts) based on a column with too many (> 50) distinct values: that typically crashes the Vega-Lite rendering engine since it allocates an overly large output image. In summary, our constraints guarantee conformance to the Vega-Lite specification and additionally avoid common mistakes that cause crashes or degenerate outputs.
Synchromesh: Reliable code generation from pre-trained language models
SMCalFlow programs express responses to user queries about calendar events, weather, places, and people (Andreas et al., 2020). It is a rich language with scoped variable declarations, generic types, polymorphic operators and a large API of over 400 functions, which can be composed to express complex actions like "cancel any meetings on the same day of my next doctor's appointment", or answer queries such as "will it be raining during my next walking meeting with Frank?" Our CE enforces that programs type-check 2 by construction. An example 3 is given in Figure 1. At the current point in inference, the model is producing an argument to size. Since this function takes a list, its argument must be the return value of a function with return type List<T>. Among all functions and methods in the SMCalFlow API, only 14 return lists, which severely limits the valid options for the callee. Similarly, we keep track of declared variables inside let expressions, together with their types (inferred from their initialization expression), and use that data structure to limit options whenever a token of type identifier is syntactically allowed to follow.
Synchromesh: Reliable code generation from pre-trained language models
Finally, we implemented heuristics based on user utterance patterns that avoid common failure cases we observed in GPT-3. These tend to happen when the model blindly copies portions of the examples in the prompt without adaptation. For instance, whenever the utterance contains exactly one of "a.m." or "p.m", this is usually represented in SMCalFlow by a call to a corresponding SMCalFlow function that constructs a Time object (e.g., NumberAM (5)). However, if the examples retrieved for the prompt tend to only have times in the opposite half of the day, GPT-3 might call the wrong function, and translate the time sub-expression in "Schedule it for 5pm" into NumberAM (5). To avoid this, if we detect exactly one of "a.m." or "p.m." in the utterance, we remove the time construction functions associated with the opposite pattern from the candidates. We do the same filtering with days of the week and months, which are also constructed by specific functions.
Synchromesh: Reliable code generation from pre-trained language models
In all domains, the CE abstraction allows us to easily encode domain knowledge in a modular fashion. Besides constraints coming from the language's semantics, it further allows domain experts to analyze failure modes of the language model and to implement fixes them in a modular and predictable manner.
Synchromesh: Reliable code generation from pre-trained language models
The main challenge of CSD is in aligning constraints expressed in terms of programming language tokens with the model's output, which happens in another token vocabulary (typically constructed with Byte-Pair Encoding). Figure 7 shows an illustration of this challenge in Vega-Lite. Arbitrary mismatches can occur: the first BPE token includes the first Vega-Lite token and the first character of the second. In the middle of the example, the "encoding" token in Vega-Lite spans 4 BPE tokens, with misaligned boundaries at the beginning and end. Nonetheless, this issue is seamlessly handled by the CSD algorithm.
Synchromesh: Reliable code generation from pre-trained language models
The algorithm described in Section 3.3 tests each token from the language model's vocabulary individually. However, many BPE tokens are prefixes of oen another, which lets us apply a significant optimization. If t 1 is a prefix of t 2 and t 1 is inadmissible after a partial program p, then t 2 is also inadmissible. Thus, we test tokens by order of length, and keep rejected tokens in a Trie structure. Before we test a token against the completion engine, we check whether one of its prefixes was already rejected. If so, we can safely skip that token. Another optimization consists in memoizing the enumerated completion points. When testing a new partial program p, instead of starting from the empty string, we can start from the longest known completion point that is a prefix of p. This, again, can be efficiently done by keeping completion points in a Trie.
Synchromesh: Reliable code generation from pre-trained language models
We used the public OpenAI API to access GPT-3 and Codex. Therefore, we did not have direct access to the underlying language models. Even so, CSD can still be applied provided we can pass a bias to be added to the logits, which is available in the OpenAI API.
Synchromesh: Reliable code generation from pre-trained language models
However, making one request at each token is too slow. Instead, we apply a "rejection"-based sampling, as follows. First, we request a complete program from the model. Then, we iterate tokenby-token, validating it with the CSD algorithm against the completion engine. If we find a violation, we (a) use CSD to determine all valid next tokens, (b) make a request asking from just a single token, applying a logit bias to constrain it to the valid tokens, and then (c) continue generation after appending the new token. Most (90%+) trajectories end after at most 3 corrections to the model. In degenerate cases, we might need to correct the model after almost every token. In our experiments, we capped CSD to apply at most 15 corrections, to control the time a request with CSD takes. This only happened in less than .5% of the cases, and could be completely avoided if we had direct access to the model (in which case CSD is efficient enough to be applied at every token). Figure 8 shows the equivalent of Figure 4 for the SQL domain. We notice that the largest gaps in validity happen for the longest queries, and the benefits in accuracy are highest for queries around the 60% length percentile.
Synchromesh: Reliable code generation from pre-trained language models
In Section 2, we described TST, which fine-tunes a sentence embedding model to attempt to capture program similarity. Here, we give more details on our training procedure.
Synchromesh: Reliable code generation from pre-trained language models
First, for both SQL and SMCalFlow, we selected a random set of 2000 examples, and computed the normalized tree edit distance between all pairs of examples. We then fine-tuned S-BERT for one epoch using the cosine similarity loss. We used the AdamW optimizer with a learning rate of 2 × 10 − 5 -the default parameters in the S-BERT library 4 . We did not perform any hyperparameter tuning. Training took around 3 hours on a single GPU. Figure 9: Benefit of CSD: The left plot is generated by Codex without CSD, but it has an overflowing legend and it also raises a warning about missing values. Using CSD, we generate the plot on right that generates no runtime warning or error.
In-context Examples Selection for Machine Translation
In-context learning (Brown et al., 2020) has recently received a lot of attention from the NLP research community due to its remarkable ability to utilize only a few input-output examples to perform many NLP tasks (Liu et al., 2021). For example, Lin et al. (2021) demonstrate that a 7.5B multilingual generative model, XGLM, outperforms a supervised sequence-to-sequence baseline in 45 translation directions on the FLORES-101 machine translation benchmark (Goyal et al., 2022) using * Work done during internship at Meta AI Research. just 32 randomly sampled translation examples as demonstrations. While these results are compelling, recent work has also shown that the performance and capability of a pre-trained language model (PLM) can be highly sensitive to many factors, such as the choice of in-context examples (Liu et al., 2022b), their ordering  and the template (Jiang et al., 2020).
In-context Examples Selection for Machine Translation
Typically, in-context learning for MT uses examples that are randomly sampled from a small development set that resembles the domain of the test dataset. The effect of the aforementioned factors (such as the choice of the examples) on the translation quality of the PLM hence remains unclear and unexplored. Yet another crucial gap in using in-context learning for MT in the current literature is the effect of the domain of in-context examples on translation quality since out-of-domain generalization is a known and important challenge in MT (Koehn and Knowles, 2017).
In-context Examples Selection for Machine Translation
In this work, we systematically analyze how factors such as the choice and the number of few-shot in-context examples and their ordering impact MT output quality. We show that while noisy unrelated 1-shot example can have a significantly adverse effect on translation quality, a single prompt optimized to maximize the translation quality on a development set can sufficiently elicit task-based information from the PLM. Our analysis thus demonstrates the importance of selecting good examples for MT and raises the question: What are the properties of good in-context examples for MT? In that direction, our findings suggest that a well-formed meaning-equivalent translation example results in higher quality translation than randomly selected in-context examples.
In-context Examples Selection for Machine Translation
Furthermore, motivated by the use of Translation Memory in Computer-Aided Translation (Yamada, 2011) and its usage in computational approaches to Machine Translation (Somers, 1999;Koehn and Senellart, 2010;Khandelwal et al., 2020, arXiv:2212.02437v1 [cs.CL] 5 Dec 2022 inter alia), we retrieve similar examples to the test source from a datastore that includes pairs of source text and their corresponding translations via BM25, an unsupervised efficient retriever to provide additional context to the model. As the context window of the PLM is usually limited (∼ 3096 tokens, 16 − 20 examples), we propose a novel in-contextexample selection and reranking strategy that maximizes the coverage of the source n-grams in the selected examples. Experiments on WMT'19 English↔German and English↔Russian datasets show that our proposed re-ranking strategy can consistently improve the translation quality over the outputs generated using BM25 retrieved examples.
In-context Examples Selection for Machine Translation
Combining optimized 1-shot task-level with example-specific in-context examples using a simple concatenation strategy further improves translation quality, outperforming state-of-the-art inference-adapted nearest-neighbor MT models (kNN-MT) on two out-of-domain datasets (Medical and IT) while being memory and compute efficient as our approach does not require constructing and querying a dense token-level datastore.
In-context Examples Selection for Machine Translation
Generating translations from large-scale multilingual language models like mGPT (Shliazhko et al., 2022), XGLM (Lin et al., 2021) or AlexaTM 20B (Soltan et al., 2022) requires conditioning the decoder-only language model with in-context parallel examples. These examples serve two purposes: a) providing the model with the format and knowledge of the task (task-level) and b) guiding the output generation via providing useful information about the unseen source sentence (example-specific). This is different from the standard sequence-to-sequence models, where the task is always known, and the model learns generalizable patterns from the input-output examples to perform the task (in this case, translation) for the unseen source text.
In-context Examples Selection for Machine Translation
Formally, given k in-context examples {x i , y i } k 1 the prefix input or the prompt, x p j , is generated by concatenating the demonstration examples {(x i , y i )} k 1 to the test input, x s j according to a template, P (see Table 1). The output,ŷ, is then generated via the PLM with parameters θ via greedy decoding as follows: y j,t = arg max y j,t P PLM (y j,t |x p j ,ŷ j,<t ; θ) (1)  
In-context Examples Selection for Machine Translation
Ideally, good in-context examples can trigger the pre-trained language model to generate the desired output and also elicit the information learned during pre-training (Jiang et al., 2020). Min et al. (2022) show that, for classification tasks, the incontext examples provide information about the task (the distribution of the input text, the label space, and the format of the task) and that the model does not rely on these examples to generate the final output. However, their analysis is limited to a) classification tasks and 2) randomly sampled in-context examples. Prior work has also shown that the order of these in-context examples can also lead to high variance in downstream performance . However, less is understood about how these factors impact text generation tasks like MT. Do we need multiple incontext examples? What makes good in-context examples for MT? How sensitive is the model to the order of the prompts?
In-context Examples Selection for Machine Translation
In this work, we aim to better understand the impact of prompt selection on the translation quality of the outputs. Given a training dataset consist-
In-context Examples Selection for Machine Translation
, and a test source x j , we select a subset of m informative samples to form a prompt which either provides task-level and/or example-specific information as discussed below.
In-context Examples Selection for Machine Translation
A good task-level in-context example should be able to elicit information learned during pretraining from the PLM. One way to measure the efficacy of an example as a prompt is via computing the translation quality of the outputs generated when prompting the PLM given an example. Hence, we select the task-level prompt as follow: For a given example sampled from the training dataset, (x i , y i ) ∈ D S , we create a prompt, x p i by concatenating the example {(x i , y i )} to each source in the development set. The system outputs are then generated using equation 1. We then rank examples from D S as task-level prompts based on the BLEU of the generated outputs against the references on this held-out development set, D dev = {X, Y }:
In-context Examples Selection for Machine Translation
Prior work on retrieving good in-context examplespecific prompts for tasks other than MT (like question answering or knowledge retrieval) either trains a dense-retriever (Rubin et al., 2021) or utilizes samples that are closer to the test source in the embedding space of a PLM like BERT (Devlin et al., 2019), RoBERTa (Liu et al., 2019), or XLNET models (Liu et al., 2022b). While contextual models can generate a global sentence representation, they overlook rare lexicons which can be important for generating translations in unseen domains like medical or IT (Wrzalik and Krechel, 2021). However, for MT, overlapping n-grams between the source and the retrieved sentences ensures informativeness as the target associated with the retrieved sentence is likely to include partial translations of the source. We can thus use BM25 as an efficient unsupervised retrieval method to retrieve similar examples. However, as the examples are scored independently and BM25 favors rare word matches (Robertson et al., 2009), the top retrieved candidates might not cover all the terms in the source text ( Figure 1). Given that the context window of the PLM is usually limited (∼ 3096 tokens, 16 − 20 examples), maximizing the coverage of all the terms found in the test input might be favorable. Hence, we propose to re-rank the top 100 candidates retrieved from BM25 using our algorithm outlined in 1.
In-context Examples Selection for Machine Translation
We extract all the word n-grams, and their counts from the test source, x s j and source of the BM25 retrieved examples, {P j (x i } k 1 (lines 2-4). Let S and Q denote the set of the source n-grams and the n-grams from a BM25 retrieved example, respectively. We compute a recall-based (R) n-gram overlap score (line 7) using the following equation:
In-context Examples Selection for Machine Translation
The example with the maximum score is then added to the set of selected prompts, and the found n-grams from the test source are then downweighted by a factor, λ for the next iteration of selection (line 14). For example, setting λ = 0 will select the example that covers the n-grams from the test source in the subsequent iteration that has not already been encountered. This process is then re-Algorithm 1: An N-gram Recall-based Strategy to Re-rank In-context Examples
In-context Examples Selection for Machine Translation
peated over the retrieved pool until a set threshold of the score is reached. Figure 1 shows the top-100 candidates retrieved via BM25 for the input: "Welche Risiken sind mit Poulvac FluFend H5N3 RG verbunden?". The top few candidates provide the same information to the PLM, i.e., translation of the phrase "Poulvac FluFend H5N3 RG". The examples including the other terms ("Welche Risiken sind mit verbunden ?") from the input text, are ranked lower. On the other hand, our proposed re-ranking strategy can cover all the terms from the input text, in this case, with just the top-2 examples.
In-context Examples Selection for Machine Translation
We perform our in-domain evaluation on the WMT-19 German (de) ⇔ English (en) and WMT-19 Russian (ru) ⇔ English (en) datasets (Barrault et al., 2019). For the out-of-domain evaluation, we use the multi-domain dataset from Aharoni and Goldberg (2020) for the following domains: Medical, Law, IT, and Koran. The dataset statistics are included in the Appendix (Table 11). We normalize punctuation using the Moses toolkit (Koehn et al., 2007) and remove sentences longer than 250 tokens as well as sentence pairs with a source/target length ratio exceeding 1.5 from the in-domain datasets.
In-context Examples Selection for Machine Translation
We evaluate the detokenized length truncated outputs generated by the model using sacreBLEU (Post, 2018). 1 The generated outputs from the PLM are truncated to twice the source length, as preliminary analysis suggested degeneration in a few (∼10-20) examples.
In-context Examples Selection for Machine Translation
Language Model We use the publicly available checkpoint of the XGLM 7.5B , a decoder-only causal language multilingual model (Lin et al., 2021) for all our experiments, which has 32 layers and a hidden dimension of 4096.
In-context Examples Selection for Machine Translation
We consider the following comparisons:
In-context Examples Selection for Machine Translation
• Random: p random few-shot examples sampled from the training dataset (number of trials=3).
In-context Examples Selection for Machine Translation
• Task-level: top-p examples that achieve the highest BLEU on the development set ( § 3.1).
In-context Examples Selection for Machine Translation
• Retrieved In-context (BM25): q max examples retrieved via BM25, since unlike task-level examples, there is no guarantee that exactly q similar examples will be found in the training dataset for each input.   Table 2: Results on WMT'19 test sets: Concatenating task-level prompt to R-BM25 consistently achieves the best BLEU scores across the board. p and q max are the number of task-level and example-specific prompts respectively.
In-context Examples Selection for Machine Translation
• Retrieved Re-ranked In-context (R-BM25): q max re-ranked examples using our proposed approach as detailed in § 3.2.
In-context Examples Selection for Machine Translation
We additionally compare our results with kNN-MT (Khandelwal et al., 2020) for out-of-domain evaluation. We use λ = 0.1, threshold=1.  Table 2 and 3 summarizes our main results for the in-domain evaluation when translating between English <-> German and English <-> Russian and the four German-English out-of-domain datasets, respectively.
In-context Examples Selection for Machine Translation
A single task-level prompt is competitive with 16 random few-shot examples. Our experiment suggests that it is possible to elicit the task-level knowledge from the large-scale language model using a single prompt as opposed to using 16 random few-shot examples when translating into English (Table 2). Using a single task-level prompt (optimized on the development set) improves BLEU over using 16 random few-shot examples for 2 out of 4 translation directions (De-En, Ru-En). We hypothesize that when translating out of English, the model still benefits from getting exposed to multiple and diverse random few-shot examples as the target language model is relatively weaker.
In-context Examples Selection for Machine Translation
Multiple example-specific prompts are required to improve translation quality over a single task-level prompt. Using a single task-level (p = 1) prompt attains higher BLEU over using a single example-specific prompt (q = 1; BM25, R-BM25) across the board. By contrast, using upto 16 BM25 prompts (q max = 16) significantly improves output quality over using task-level prompts, with an average gain of 1.41 in BLEU. Both task-level and R-BM25 examples provide complementary advantages, as combining them using a simple concatenation strategy improve output quality over task-level or R-BM25 examples. We leave the exploration of optimizing the number and the joint order of task-level and example-specific prompts to future work.
In-context Examples Selection for Machine Translation
As XGLM is trained on monolingual Common Crawl snapshots, translation in any domain and language could be considered an out-of-domain task from the model's perspective. However, we hypothesize that translation in specific domains like medical, law, or IT could still be challenging for the PLM as the model is less likely to have observed even sufficient monolingual datasets for these specialized domains, in contrast to the news text found in WMT. Examples from these domains might require translating rare terminologies  and carry domain-specific idiosyncrasies, which is known to pose a challenge even for a well-trained supervised neural MT model (Koehn and Knowles, 2017). Hence, we also evaluate PLM under these specialized out-of-domain scenarios.
In-context Examples Selection for Machine Translation
Task-level in-context examples drawn from the domain of evaluation, i.e., domain-specific, obtain on an average higher BLEU scores across the board than using examples from a distant WMT corpus as expected (Table 3) in both 1-shot (p = 1: +1.4) and 16-shot (p = 16: +2.7) settings.
In-context Examples Selection for Machine Translation
Example-specific prompts significantly improve translation quality over task-level prompts. Unlike the in-domain evaluation, retrieved and re-ranked example-specific prompts (R-BM25) improve the translation quality significantly across the board with up to 23 BLEU gain in the Law domain using just a single example as a prompt over a task-level prompt. This can be attributed to the high lexical overlap in the examples retrieved from the training data for these domains (Table 8).
In-context Examples Selection for Machine Translation
Task-level and R-BM25 prompts are complementary. Both task-level and R-BM25 provide supporting information for a given test source sentence as concatenating these set of prompts improves output quality over using these methods independently, outperforming a strong kNN-MT baseline on 2 out of 4 domains (Medical and IT) without requiring access to a strong base MT model or token-level retrieval during inference. Our manual analysis suggests that the higher gain obtained in the IT domain (+0.86) when using both task-  Figure 2. Across all four language pairs, there is a large variation in BLEU scores (up to 20 BLEU), where noisy or unrelated prompts can lead to significantly worse output quality. Given that most existing parallel corpora are web-crawled and the quality of bitext can vary significantly across different language pairs (Kreutzer et al., 2022), randomly sampled examples can under-estimate the translation quality attainable by prompting these PLM.
In-context Examples Selection for Machine Translation
Impact of Pool Size on Task-level Prompt Selection We select the best task-level prompt based on the translation quality on the development set from a random sample of 100 examples (pool) as detailed in Section 3.1. However, one concern regarding the selection of the best task-level prompt in this fashion could be that we might still be underestimating the PLM (s) performance, as a larger pool size could result in better output quality. We study the impact of using a larger pool size in Table 5 where increasing the number of examples from 100 to 1000 only leads to a gain of 0.5 points in the maximum BLEU. From the same table, we    can also observe that for any subset of random 100 few-shot examples, we can extract a task-level prompt (BLEU: 36) with a small standard deviation in overall outpust quality (0.18). Figure 3 shows the correlation between output quality in forward (x → y) and reverse (y → x) translation directions when using 1-shot prompts -there is a moderate to high correlation in output quality for both language pairs suggesting that the best and worst 1-shot prompts in one direction exhibit similar behavior in the opposite translation direction.
In-context Examples Selection for Machine Translation
Our manual analysis on the best task-level prompts suggests that any well-formed and meaning-equivalent translation (Vyas et al., 2018;Briakou and Carpuat, 2020) could make a good task-level prompt (see examples in Appendix Table 14). To quantify the meaning equivalence of the 1-best task-level prompt against random 1-shot examples, we report the percentage of aligned words between the source and reference translation ("% Aligned words") using fastAlign (Dyer et al., 2013) and the probability of generating the reference translation condi- tioned on the source using a pre-trained multilingual NMT model, Prism-src (Thompson and Post, 2020;Agrawal et al., 2021) in Table 4. 2 Across all language pairs and both metrics, task-level examples achieve higher semantic similarity scores than random   Table 6 shows the impact on translation quality when using an unrelated translation example against a meaning-equivalent or wellformed source-translation pair as a prompt: a noisy unrelated in-context example leads to extremely low BLEU score of 1. While using both a good task-level and a noisy prompt via concatenation (best-then-worst and worst-then-best) reduces the effect of noise, the best output quality achieved when using both prompts (31.43) is still lower than using just the best task-level prompt (32.14), highlighting the importance of both prompts selection and their ordering on translation quality.
In-context Examples Selection for Machine Translation
To further explore the sensitivity to the order of few-shot prompts on MT quality, we use all possible order permutations of four randomly sampled examples and the top four task-level examples as prompts (4!) and report the translation quality as measured by BLEU in Table 7: Task-level prompts are less sensitive to prompt order, as suggested by the lower standard deviation achieved in all settings, and result in higher translation quality than randomly selected examples.  Table 7: BLEU over all 24 permutations of 3 seeds of 4 randomly selected and top 4 task-level prompts.
In-context Examples Selection for Machine Translation
To understand the benefit of retrieved examples in the out-of-domain evaluation, we measure the lexical overlap between the test input (x, y) and the prompts (I x , I y ) using BLEU (Avg. BLEU (I x , x), Avg. BLEU (I y , y)), where I x and I y are the sources and target translations of the retrieved incontext examples. We also report the correlation against the translation quality BLEU(ŷ, y). Table 8 shows that the source lexical overlap is a good indicator of the informativeness of a prompt for 3 out of 4 domains, with Koran as an exception. For Koran, while the retrieved sentences have a high overlap with the source (36.03), the target associated with the prompts (I y ) does not get high BLEU with the reference (10.36) compared to other domains. We hypothesize that this might be due to a bias in the reference translations towards a particular output style. We provide an analysis of Dataset Avg. BLEU (I x , x) Corr(BLEU (ŷ, y),BLEU (I x , x)) Avg. BLEU (I y , y) Corr(BLEU (ŷ, y), BLEU (I y , y))  Table 8: Correlation between the degree of overlap as measured by BLEU and the translation quality of the outputs, BLEU(ŷ, y), across different domains when using the top-1 prompt retrieved using BM25. I x and I y are the sources and the reference translations in the BM25 examples respectively.
In-context Examples Selection for Machine Translation
the impact of this phenomenon on MT quality in Section 7.
In-context Examples Selection for Machine Translation
We report two interesting findings when prompting PLM with task-level and example-specific prompts:
In-context Examples Selection for Machine Translation
Stylistic Outputs One advantage of using a single task-level in-context example to prompt the PLM is that it allows us to systematically study how the choice of prompt influences the style of the generated translation. Table 9 illustrates one such example: we can observe that as the prompt includes a contraction ("we are" vs. "we're"), the outputs generated by the PLM also include contractions and can be incorrectly penalized by BLEU while being meaning equivalent.
In-context Examples Selection for Machine Translation
Prompt: Wegen des heißen Sommers fangen wir erst spät an. = Because of the hot summer, we're late getting started. Source: Ja, ich bin sehr zufrieden mit dem Auftritt.
In-context Examples Selection for Machine Translation
Reference: Yes, I am very happy with the performance. PLM Output: Yes, I'm very satisfied with the performance.
In-context Examples Selection for Machine Translation
Source: Es ist eine andere Unternehmenskultur. Reference: It is a different corporate culture. PLM Output: It's a different corporate culture.  7.1 Size of the Datastore Figure 4 shows BLEU when varying the size of the datastore used to retrieve similar in-context examples using BM25 on the Medical dataset. As the size of the datastore increases, the likelihood of retrieving a more similar example increases. However, similar output quality in BLEU can be achieved by using multiple in-context examples when a smaller in-domain datastore is available as multiple examples can provide better coverage of the source terms -BLEU @q=16 with a datastore size of 100k is equivalent to BLEU @q=1 with twice as many examples (200k). In-context Learning for MT Garcia and Firat (2022)  Domain Adaptation for MT Prior work on domain adaptation for machine translation uses outof-domain bilingual or monolingual datasets to improve the translation quality of a pre-trained neural sequence-to-sequence MT model either during training (Luong and Manning, 2015;Freitag and Al-Onaizan, 2016;Wang et al., 2017) or inference (Zheng et al., 2021;Khandelwal et al., 2020). Similar to past work, our work utilizes out-of-domain datasets during inference to adapt a pre-trained generative language model to improve the translation quality on unseen domains. However, our approach does not rely on creating a domain-specific tokenlevel datastore, but directly uses similar examples to provide additional context, hence is more compute and memory efficient.
In-context Examples Selection for Machine Translation
Prompt Selection The importance of selecting good in-context examples and their impact on downstream NLP task performance has been studied in prior work (Liu et al., 2022b;Jiang et al., 2020;Min et al., 2022;Zemlyanskiy et al., 2022;Rubin et al., 2021;Liu et al., 2022a). However, how these examples and their properties impact MT quality remains unexplored, which we investigate in our work.
In-context Examples Selection for Machine Translation
We investigate the choice of in-context examples selection for MT in both in-domain and out-ofdomain settings. We propose a novel recall-based re-ranking approach to utilize similar training examples as prompts and show their efficacy across multiple datasets and domains. Our findings show that task-level prompts can provide a complementary advantage to example-specific prompts, outperforming a strong kNN-MT baseline in 2 out of 4 out-of-domain datasets while being memory and compute efficient. Our manual analysis of the generated outputs reveals that the PLM can mimic the style of the in-context examples provided and can be used for template-based translation synthesis. These results open space for future research to evaluate the potential of generating diverse and style-specific outputs for MT.  
In-context Examples Selection for Machine Translation
We report translation quality using Comet (Rei et al., 2020) in Tables 15 and 16. We use the eamt22-cometinho-da model (Rei et al., 2022) to generate the scores as it was shown to achieve higher correlations with human judgments than lexical overlap metrics while being computationally efficient. Our re-ranking strategy (with q max = 16) consistently performs the best across the board except for Koran, outperforming strong kNN-MT baselines on the multi-domain test set in 3 out of 4 settings. Adding a task-level prompt to 16 R-BM25 prompts via concatenation further improves quality in 5 out of 8 settings.   
In-context Examples Selection for Machine Translation
Table 14 shows the best task-level in-context example selected by our method described in § 3.1 and the respective BLEU scores on the development set for the German-English and Russian-English tasks.
In-context Examples Selection for Machine Translation
German: Beispielsweise der Änderungsantrag zu Artikel 5 in der Stellungnahme des Ausschusses für Landwirtschaft und ländliche Entwicklung weist klar und deutlich darauf hin, dass die Verschlechterung der Qualität des Bodens lokale oder regionale Ursachen und Wirkungen hat und daher unbedingt nationale statt europäischer Maßnahmen ergriffen werden müssen.
In-context Examples Selection for Machine Translation
English: For example, the amendment to Article 5 in the opinion of the Committee on Agriculture and Rural Development clearly indicates that the degradation of the soil has local or regional causes and effects and it is therefore essential to adopt national as opposed to European measures.
In-context Examples Selection for Machine Translation
Development BLEU: 35.82
In-context Examples Selection for Machine Translation
Russian: Если ваш браузер возвращает ранее сохраненный "cookie", то управляющий им поставщик имеет возможность соединить актуальное посещение пользователя с предыдущими посещениями, но только в отношении своего содержания.
In-context Examples Selection for Machine Translation
English: If the browser sends back an earlier saved cookie, then the service managing these can connect to the userś earlier visit, but only in respect of their own content.
In-context Examples Selection for Machine Translation
Development BLEU: 25.63   