SCOI : Syntax-augmented Coverage-based In-context Example Selection for Machine Translation (2024)

Abstract: In-context learning (ICL) greatly improves the performance of large language models (LLMs) on various down-stream tasks, where the improvement highly depends on the quality of demonstrations. In this work, we introduce syntactic knowledge to select better in-context examples for machine translation (MT). We propose a new strategy, namely S yntax-augmented CO verage-based I n-context example selection (SCOI), leveraging the deep syntactic structure beyond conventional word matching. Specifically, we measure the set-level syntactic coverage by computing the coverage of polynomial terms with the help of a simplified tree-to-polynomial algorithm, and lexical coverage using word overlap. Furthermore, we devise an alternate selection approach to combine both coverage measures, taking advantage of syntactic and lexical information. We conduct experiments with two multi-lingual LLMs on six translation directions. Empirical results show that our proposed SCOI obtains the highest average COMET score among all learning-free methods, indicating that combining syntactic and lexical coverage successfully helps to select better in-context examples for MT. Our code is available at https://github.com/JamyDon/SCOI.

## introduction in-context learning (icl) has become a popular prompting strategy to elicit the power of large language models (llms) across a wide range of natural language processing (nlp) tasks @xcite @xcite . in icl, several demonstrations including both task input and ground truth output are presented in the input context, to make llms understand the specific down-stream task and produce better results. the performance of icl highly depends on the quality of in-context examples, and it is thus of * corresponding author. in previous studies, for both statistical mt and neural mt, syntax plays a crucial role in improving model performance @xcite . however, in case of icl, most existing works focus on superficial features but pay little attention to the syntactic structure of sentences. to achieve a high translation quality, it requires not only an accurate word translation but also a proper syntactic structure of the generated target sentence. hence, syntactic information should also play a big part in mt even in the era of llms. compared with independent selection, it has been proved that selecting in-context examples as an entire set based on the set-level coverage leads to a better diversity while reducing redundancy and avoiding sub-optimal results @xcite . as a typical nlp task, mt would also benefit from in-context examples with a high set-level coverage. therefore, beyond the conventional lexical coverage, high syntactic coverage is also necessary to select informative in-context examples for mt. in this work, we propose syntax-augmented coverage-based in-context example selection, scoi foot_0 , to boost llms' performance on mt. specifically, to measure syntactic coverage, we first simplify a tree-to-polynomial algorithm @xcite , which is originally costly but has been reduced to no more than quadratic time complexity after simplification. using this new algorithm, we convert syntax trees into polynomials and then compute the set-level syntactic coverage based on vector representations of polynomial terms. meanwhile, we compute the proportion of word overlap to measure set-level lexical coverage. after that, we design an alternate approach to combine both coverage measures, so that word-level and syntaxlevel features would complement each other. we evaluate scoi on 6 translation directions (german, french, russian into and out of english) based on two open-source multi-lingual llms, xglm 7.5b @xcite and alpaca @xcite . among all learning-free methods, scoi obtains the highest comet scores on 4 out of 6 translation directions and the highest average comet score. especially, on russian-to-english and english-to-russian translations, scoi even outperforms the learning-based ctq scorer @xcite when using alpaca. our contributions can be summarized as follows: ## related work prompting llms for better performance has been one of the mainstream trends of nlp research. there have been a large number of studies on prompting strategies for mt in recent years @xcite . @xcite decompose the translation process into a sequence of word chunk translations to improve llms' performance on translation between linguistically related languages. @xcite propose to present llms with a set of possible translations for a subset of the input words from bilingual dictionaries to improve llms' performance on low-resource and out-of-domain mt. @xcite prompt llms with selected knowledge including keyword pairs, topics and sentence pairs to emulate human-like translation. @xcite manage to teach llms an unseen language on the fly with the help of a small parallel corpus and a dictionary. @xcite first create a textbook including vocabulary list, language examples with syntax patterns and translate instructions using llms and then prompt llms with the textbook just created to better translate low-resource languages. @xcite prompt llms with both sentence-level and word-level demonstrations, the former selected with a margin-based score and the latter being word pairs most related to the test input appeared in the former. among various prompting strategies, icl plays a key role. @xcite suggest that the performance of icl strongly depends on the selected in-context examples. thus it is of great significance to select better examples using various strategies. @xcite propose to train a unified demonstration retriever for icl across a wide range of tasks. ye et al. (2023 test input example 1 example 2 example 3 example 4 llm inference c 1 s 1 c n c 2 s 2 set-level syntactic coverage (3 rd ) e 1 e 2 c 1 s 1 c n c 2 s 2 … s n … e 1 𝑤𝑤 6 𝑤𝑤 7 𝒘𝒘 𝟐𝟐 𝒘𝒘 𝟑𝟑 𝑤𝑤 8 … t 𝑤𝑤 1 𝑤𝑤 2 𝑤𝑤 3 𝑤𝑤 4 𝑤𝑤 5 … 𝒘𝒘 𝟏𝟏 𝑤𝑤 9 𝒘𝒘 𝟒𝟒 𝒘𝒘 𝟓𝟓 𝑤𝑤 10 … 𝒘𝒘 𝟏𝟏 𝑤𝑤 6 𝑤𝑤 7 𝑤𝑤 11 𝑤𝑤 12 … 2/5 3/5 1/5 word coverage … … set-level word coverage (2 nd ) c 1 s 1 c n c 2 s 2 … s n … e 1 𝒘𝒘 𝟏𝟏 𝑤𝑤 9 𝒘𝒘 𝟒𝟒 𝒘𝒘 𝟓𝟓 𝑤𝑤 10 𝒘𝒘 𝟐𝟐 … t 𝑤𝑤 1 𝑤𝑤 2 𝑤𝑤 3 𝑤𝑤 4 𝑤𝑤 5 … 𝒘𝒘 𝟏𝟏 𝑤𝑤 9 𝒘𝒘 𝟒𝟒 𝒘𝒘 𝟓𝟓 𝑤𝑤 10 𝑤𝑤 7 … 𝒘𝒘 𝟏𝟏 𝑤𝑤 9 𝒘𝒘 𝟒𝟒 𝒘𝒘 𝟓𝟓 𝑤𝑤 10 𝑤𝑤 8 … 4/5 3/5 3/5 word coverage … … set-level word coverage (4 th ) e 2 e 3 figure 1: overview of scoi. each example is selected based on how well the test input is covered by the current candidate plus the existing examples selected in previous steps at syntax level and word level alternately. in each step, t , e i , ⊕, c i , s i denote the test input, the i-th selected example, concatenation of selected examples and one candidate, the i-th candidate from the example database, the to-be-scored set including the selected examples plus the i-th candidate, respectively. ous work has made use of syntactic information in in-context example selection for mt. ## method we propose to select in-context examples based on both syntactic and lexical coverage to better apply llms for mt. specifically, to measure the set-level syntactic coverage, we first simplify a tree-to-polynomial algorithm, making it practical to run on large mt datasets, and then compute the coverage of vector representations of polynomial terms. to measure the set-level lexical coverage, we simply consider the proportion of word overlap. after that, we design an alternate strategy to take advatage of both lexical and syntactic knowledge. an overview of our proposed method, scoi, is presented in figure 1 . @xcite convert dependency trees into polynomials recursively and compute the distance between polynomials to measure the syntactic similarity between sentences from different languages. specifically, given the number of dependency labels d, dependency trees will be transformed into polynomials based on two variable sets: @xmath0, x 2 ...x d } and @xmath1, y 2 , ...y d }. considering a leaf node with label l as n l , its corresponding polynomial is p (n l , x, y ) = x l . for a non-leaf node m l with label l, its polynomial is: ## experimental setup we follow @xcite to set up our experiments. test set we perform our evaluation on the devtest set of flores-101 @xcite , which has 1012 sentences with translations in 101 languages. ## conclusion in this work, we introduce syntactic information to in-context example selection for mt. first, we measure set-level syntactic coverage with coverage of polynomial terms based on a simplified algorithm that converts syntax trees into polynomials. then, we propose to select in-context examples for mt based on syntactic and lexical coverage alternately to combine information of syntax and word. our proposed method obtains the highest average comet score among all learning-free methods, indicating that combining syntactic and lexical coverage during in-context example selection is helpful for mt. we call on the nlp community to pay more attention to syntactic knowledge for syntaxrich tasks like mt. for low-resource languages. meanwhile, dependency parsing could be costly when dealing with large datasets, which makes scoi more timeconsuming in such situations.