# An Empirical Analysis of In-context Learning Abilities of LLMs for MT

Pranjal A. Chitale1,2 Jay Gala1∗ Varun Gumma3 Mitesh M. Khapra1,2 Raj Dabre4
1Nilekani Centre at AI4Bharat 2IIT Madras 3Microsoft Corporation
4National Institute of Information and Communications Technology, Kyoto, Japan
Equal contribution

###### Abstract

In-context learning (ICL) has consistently demonstrated superior performance
over zero-shot performance in large language models (LLMs). However, the
understanding of the dynamics of ICL and the aspects that influence downstream
performance remains limited, especially for natural language generation (NLG)
tasks. This work aims to address this gap by investigating the ICL
capabilities of LLMs and studying the impact of different aspects of the in-
context demonstrations for the task of machine translation (MT). Our
preliminary investigations aim to discern whether in-context learning (ICL) is
predominantly influenced by demonstrations or instructions by applying diverse
perturbations to in-context demonstrations while preserving the task
instruction. We observe varying behavior to perturbed examples across
different model families, notably with BLOOM-7B derivatives being severely
influenced by noise, whereas Llama 2 derivatives not only exhibit robustness
but also tend to show enhancements over the clean baseline when subject to
perturbed demonstrations. This suggests that the robustness of ICL may be
governed by several factors, including the type of noise, perturbation
direction (source or target), the extent of pretraining of the specific model,
and fine-tuning for downstream tasks if applicable. Further investigation is
warranted to develop a comprehensive understanding of these factors in future
research.

##  1 Introduction

Large Language Models can be used as a single effective solution for a diverse
range of downstream tasks via in-context learning (Brown et al., 2020; Dong et
al., 2023; Liu et al., 2023; OpenAI et al., 2023; Chowdhery et al., 2022).
This is an inference-only procedure that involves conditioning on a few
handcrafted task-specific demonstrations consisting of input-output pairs as a
part of the prompt before the actual test example. Although several works use
in-context learning as an effective way of gaining good performance on tasks,
there is limited understanding of how it works and which aspects of the
demonstrations contribute to end task performance, whether all examples
contribute equally or not, and whether the end generation can be controlled by
in-context examples, whether in-context exemplars can be an effective way to
control pre-training biases observed in models. While numerous studies employ
in-context learning as an effective method for achieving proficient task
performance, there remains a limited understanding of its underlying
mechanisms.

Min et al. (2022) showed that the correctness of the output labels in the
demonstrations has limited impact on the downstream performance for Language
Understanding (NLU) tasks. However, Yoo et al. (2022); Kossen et al. (2023)
demonstrate that the model’s predictions are dependent on in-context labels.
Wei et al. (2023) also shows that In-Context Learning (ICL) can override
semantic priors for larger models even in the case of semantically unrelated
input-label mappings. However, these studies are restricted to NLU tasks which
are discriminative and the label space is limited. For NLG tasks where
controlling the generation is harder, there is limited exploration of these
dynamics rendering the open question of whether ICL is a mere
contextualization tool that elicits the appropriate set of memorized knowledge
or whether ICL can be used as an effective means to control the generations.
There exists a lack of clarity or consensus regarding the distinct
contributions of various aspects of demonstrations to end task performance,
the individual impact of each demonstration on performance, and the potential
for regulating end generation through contextual examples. Additionally,
exploring the effectiveness of in-context exemplars as a means to regulate
pre-training biases in models warrants further investigation.

Our work aims to bridge the gap by considering the task of machine translation
and providing a comprehensive analysis of the robustness of in-context
learning, specifically delving into its impact on NLG tasks, taking Machine
Translation as a use case. Although Raunak et al. (2023) conducted limited
exploration across the machine translation task, it was on a limited set of
attacks and language pairs, and the aforementioned work did not focus on
understanding to what extent ICL be used to control the generations
(translations). In this work, we not only expand the scope of the above work
by focusing on conducting a meticulous examination of LLMs across different
scales to elucidate the sensitivity of LLMs towards the in-context
demonstrations (using a diverse set of attacks focusing on lexical, syntactic,
and semantic properties) but also aim to understand and quantify the degree to
which the generations of the LLMs can be improved or controlled via in-context
learning.

##  2 Related Works

This work lies at the intersection of in-context learning, model robustness,
and machine translation.

In-context Learning: Large Language Models have demonstrated strong
performance in various downstream tasks through supervised fine-tuning on
task-specific data (Devlin et al., 2019; Raffel et al., 2020; Lewis et al.,
2020; Radford et al., 2019). Recently, instruction-tuning (Ouyang et al.,
2022) has emerged as a special variant of supervised fine-tuning, where models
are fine-tuned on instruction data to enhance task-level performance and
enforce alignment with human preferences. However, collecting and generating
training data at optimal scales for every task may be infeasible.
Additionally, due to computational constraints, fine-tuning these LLMs, even
via PEFT-based approaches (Houlsby et al., 2019; Pfeiffer et al., 2021; Hu et
al., 2022), may not be feasible. In contrast, in-context learning (Brown et
al., 2020; Dong et al., 2023; Liu et al., 2023; OpenAI et al., 2023; Chowdhery
et al., 2022) is a training-free method that has emerged as a more cost-
effective approach, especially given the increasing size of LLMs ($\geq$ 7B
parameters). ICL aims to implicitly learn the task-solving abilities through a
few hand-crafted demonstrations. These emergent capabilities (Wei et al.,
2022; Lu et al., 2023) are driven by the distribution of the pretraining data
(Chan et al., 2022). Intuitively, ICL can be considered analogous to
performing a gradient descent implicitly during the inference (Akyürek et al.,
2023; Li et al., 2023; Zhang et al., 2023b). Vilar et al. (2023) explored few-
shot prompting strategies for MT task on PaLM (Chowdhery et al., 2022)
suggesting that the downstream MT performance is largely correlated with the
quality of in-context examples. Subsequently, several recent works have
explored ICL capabilities of LLMs for the MT task Robinson et al. (2023);
Zhang et al. (2023a); Zhu et al. (2023). Recently, Lin et al. (2023) have
recently shown that the alignment of instruction-tuned (or SFT) models is
superficial, and it is possible to elicit similar behavior in base models just
by a few static stylistic examples and system prompts by leveraging ICL
capabilities.

Factors impacting in-context learning: Several aspects of the demonstrations
in an in-context setup such as input distribution, output distribution, or
input-output alignment can play a significant role in the ICL performance of
LLMs. Min et al. (2022) demonstrated that label correctness (output
distribution) in the demonstrations has limited significance for
classification tasks. However, Yoo et al. (2022) countered this viewpoint,
asserting that ICL sensitivity to input-label mapping can introduce variance
in downstream performance, and the findings of Min et al. (2022) may lack
generalizability across tasks. Furthermore, Wei et al. (2023) showed that ICL
can override semantic priors, being influenced even by semantically unrelated
input-label mappings, especially in the case of larger models. While prior
works (Min et al., 2022; Wei et al., 2023; Kossen et al., 2023) have explored
various aspects of in-context learning for NLU tasks, it remains crucial to
investigate the generalizability of these findings for NLG tasks. Raunak et
al. (2023), in one of the initial explorations into NLG tasks such as MT,
explored the impact of syntactic perturbations (e.g. jumbling alignment,
shuffling order, etc.) on demonstrations across three Indo-European language
pairs. Their findings suggest that the distribution of target text
significantly impacts GPT-3 results in comparison to the source text
distribution. Our work builds upon the above by incorporating a diverse array
of perturbations, including lexical, syntactic, and semantic variations. The
objective of the perturbations we introduce is to closely mirror real-world
scenarios wherein the in-context demonstrations are obtained from a noisy web
data store, particularly relevant for low-resource languages where there are
little to no hand-crafted demonstrations for every task. Furthermore, our
study considers a broader range of language families, including Dravidian,
Indo-Aryan, and Indo-European, contributing to a more comprehensive
understanding of ICL dynamics across different linguistic contexts. Chen et
al. (2023b) observed an inverse relationship between the sensitivity and
accuracy of Language Models (LLMs) when perturbing either the instructions
within demonstrations or the order of demonstrations. Our work differs from
the above by applying perturbations to the demonstrations while keeping the
instruction as it is.

Perturbation and Robustness: Text perturbation attacks (Xu et al., 2021;
Moradi and Samwald, 2021; Zhang et al., 2022; Niu et al., 2020; Salinas and
Morstatter, 2024) are frequently employed to assess the resilience of models
to alterations in the input text. Given the inherent noise in real-world text,
there is a need to gauge the robustness and sensitivity of models to perturbed
texts. It is essential to differentiate perturbations from adversarial attacks
(Michel et al., 2019; Garg and Ramakrishnan, 2020; Zhang et al., 2021), as the
latter are designed to deliberately deceive or compel the model into
manifesting unintended behaviors, whereas perturbations entail minor
modifications to inputs intended to simulate the presence of noise in a real-
world setting. Typically, to assess the robustness of NMT models, various
perturbation attacks are applied either at the word-level (Zhao et al., 2018;
Cheng et al., 2020) or the character-level (Belinkov and Bisk, 2018; Ebrahimi
et al., 2018; Formento et al., 2023). These perturbations may exhibit non-
linguistic characteristics, such as random injections, or be linguistically
aware, incorporating strategies like the introduction of frequently confused
or conflated characters. Additionally, perturbations may involve random
removal or addition of punctuations (Formento et al., 2023). Closest to our
work is the work by Moradi and Samwald (2021), however, they applied word and
character-based attacks to the inputs of LMs to study their robustness. In
contrast, our work differs by applying these perturbations to demonstrations,
leaving the test examples unperturbed.

##  3 Methodology

Perturbation Method | Lexical | Syntactic | Semantic | Example
---|---|---|---|---
Clean |  |  |  | Wow! That place is so wonderful, and I would
|  |  | love to go there again.
Span Noise | $\checkmark$ | $\checkmark$ | $\times$ | Wow! That place is po wonde9l, a I uld
love to go thyre again.
OCR | $\checkmark$ | $\times$ | $\times$ | Wow!That place isso wonderful, and I would
lo ve to go there again .
Word Ordering | $\times$ | $\checkmark$ | $\checkmark$ | Wow! and place is so to would I That wonderful,
love go there again.
Word Duplication | $\checkmark$ | $\times$ | $\checkmark$ | Wow! That place is is so so wonderful, and I I would
love to go there again. again.
Punctuationadd | $\checkmark$ | $\checkmark$ | $\checkmark$ | Wow! That% place is so wonderful, and I would"
love. to go there again.
Punctuationdrop | $\checkmark$ | $\checkmark$ | $\checkmark$ | Wow That place is so wonderful, and I would
love to go there again
Table 1: Categorization of different perturbation methods for the different
attributes.

In this section, we describe the various perturbation methods we used to
introduce noise into the in-context demonstrations to understand the
robustness of different LLMs for the task of MT. Our perturbation methods
influence the lexical (alterations to individual words), syntactic
(alterations to structure or ordering of words), and semantic (alterations to
meaning) attributes of the in-context demonstrations.

### Span Noise:

This perturbation involves modification of random contiguous segments of the
original text to introduce noise by string operations such as deletion,
insertion, or replacement of characters within the selected spans similar to
Maurya et al. (2023) and Joshi et al. (2020). Based on the noise percentage
chosen, we consider the number of characters to be perturbed until the budget
is exhausted. We uniformly select 1 to 3-gram character spans and the selected
span is then either deleted or replaced by a single uniformly sampled
character from the character set of the corresponding language with equal
probability and the number of characters removed or altered is then subtracted
from the noise budget.

### OCR:

This perturbation involves randomly selecting words from the original text and
performing operations such as fusion or split to simulate noise which might
commonly be introduced in the pipelines involving OCR systems. The noise
percentage controls the extent of the perturbation, determining the number of
words subjected to manipulation. This perturbation involves a random choice of
either a fusion operation, which concatenates a selected word with the next
one, or a split operation, which breaks a selected word into two parts at a
uniformly chosen split point in the selected word.

### Word Ordering:

This perturbation introduces controlled permutations to disrupt the original
word order of some portions of the original text similar to Raunak et al.
(2023). Based on the noise budget, a set of words from the original text is
uniformly sampled for reordering by generating a new order for these words. It
is important to note that this perturbation can have different implications
across different languages as few languages have free-form word order while
other languages are more rigid in terms of word order.

### Word Duplication:

This perturbation introduces some redundancy into the original text without
altering its semantics by introducing repetition to certain words. Based on
the noise percentage, a specified number of words are uniformly chosen for
duplication, followed by identifying the occurrences of these chosen words and
duplicating them at random positions within the original text.

### Punctuation:

This perturbation introduces noise by altering the syntactic cues and rhythm
of the original text, by either inserting or deleting existing punctuations
present in the original text. In the case of the addition of punctuation, we
uniformly append punctuation to the words that do not contain any punctuation
based on the noise budget. Similarly, in the case of deletion of punctuation,
we uniformly drop the punctuation characters from the original text based on
the noise budget.

Table 1 provides a categorization of various perturbation methods considered
as a part of this study with regards to the attributes it impacts.

##  4 Experimental setup

This section describes the different pre-trained models, evaluation
benchmarks, in-context prompts, and decoding hyperparameters used for our
current study.

### Models:

We conduct our experimentation on off-the-shelf open-source pre-trained LLMs
like Llama 2 (Touvron et al., 2023), BLOOM (Fan et al., 2022) and their
corresponding instruction-tuned variants such as BLOOMZ Muennighoff et al.
(2023) and ALMA (Xu et al., 2023). First, models like Llama 2 Touvron et al.
(2023) are prominently pre-trained with English or European languages and its
tokenizer has poor fertility rates on Indic languages. Further, Ahuja et al.
(2023) showed that Llama 2 70B (Touvron et al., 2023) exhibit poor in-context
MT performance on Indian languages. As a result, we evaluate Llama 2 (Touvron
et al., 2023) and ALMA (Xu et al., 2023) on 3 European languages like German,
Czech, and Russian which share the same script as the pre-training data.
Furthermore, we evaluate BLOOM (Fan et al., 2022) and BLOOMZ Muennighoff et
al. (2023) on 3 Indian languages like Bengali, Hindi, and Tamil. Due to
computational constraints, we restrict our experimentation to 7B models for a
fair comparison across the base and instruction-tuned variants. We adopt a
greedy decoding strategy without sampling to generate a maximum of 256 tokens
with early stopping to ensure reproducibility in our results.

### Benchmarks:

FLORES-200 (Goyal et al., 2022; Costa-jussà et al., 2022) is a N-way parallel
benchmark that covers 200 languages, including various low-resource languages.
However, it is important to note that data from FLORES-200 (Goyal et al.,
2022; Costa-jussà et al., 2022) has been consumed in the multitask fine-tuning
xP3 mixture of BLOOMZ (Muennighoff et al., 2023), suggesting data
contamination. Therefore, we do not consider FLORES-200 for the evaluation of
Indian languages and instead, we use the newly released IN22-Gen (Gala et al.,
2023). IN22-Gen is a 22-way parallel benchmark for Indian languages that
focuses on demography-specific content and serves as an unbiased evaluation
set for both BLOOM and BLOOMZ models.

### Prompt Details:

Vilar et al. (2023) have demonstrated that the models are typically unaffected
by the few-shot prompt template for the task of MT. However, to maintain
consistency in terms of evaluation, we follow the same prompt that was used
for fine-tuning ALMA (Xu et al., 2023) across all different models considered
in this work (see Figure 1). However, we find Llama 2 Chat models do not
perform well with the above standard prompt in the monolithic format, which is
similar to Sclar et al. (2023). Therefore, we resort to passing each
demonstration as a user-assistant turn and task description in the system
prompt in the chat format. We use uniformly sampled high-quality translation
pairs from the FLORES-200 dev set to compose the in-context demonstrations
with $k=\\{1,4,8\\}$ across various noise scales with
$\delta=\\{0,0.1,0.25,0.5,0.75\\}$ for evaluating LLMs.

Translate this from {src_lang} into {tgt_lang}:

{src_lang}: {src_text
{tgt_lang}: {tgt_text}

$\cdots$
$\cdots$

{src_lang}: {src_text}
{tgt_lang}:

Figure 1: Prompt for translation

### Evaluation:

We use the ChrF++ metric (Popović, 2017) as the primary evaluation metric for
our analysis. Sai B et al. (2023) showed that it demonstrates a strong
correlation with human judgments over the other string-based MT evaluation
metrics. We use the SacreBLEU (Post, 2018) library to ensure standardization
in terms of tokenization by using the built-in mteval-v13a tokenizer to ensure
a fair comparison. In the future, we plan to include model-based metrics for
further analysis.

##  5 Results and Analysis

Figure 2: Mean percent change in ChrF++ score for each attack relative to the
0 noise baseline, for each model across both translation directions (En-XX and
XX-En) and both perturbation directions. Scores are averaged across shots and
noise percentages ($\delta$). “Span" denotes span noise, “order" represents
word order attack, “dup" signifies word duplication attack, “add" indicates
punctuation addition attack, and "drop" signifies punctuation removal attack.
Note: In certain cases, scores are bounded within minimum and maximum values
for clarity in depicting overarching trends.

Figure 2 shows the impact of various perturbation attacks described in Section
3 across two different model families: multilingual BLOOM and prominently
English Llama 2.

### Findings about BLOOM family:

In both the En-XX and XX-En directions, and across both perturbation
categories, our observations indicate that the task-specific fine-tuned
BLOOM-7B-FT model exhibits superior robustness. It is followed by the BLOOM-7B
model, while the multitask fine-tuned BLOOMZ-7B model displays high
vulnerability to various perturbation attacks. A comparative analysis of
source and target-side perturbations suggests that target-side perturbations
are generally more detrimental than source-side perturbations for all BLOOM
model variants in both directions. Specifically, the span-noise attack proves
to be the most detrimental, causing significant performance drops in the BLOOM
and BLOOM-Z models, with a comparatively lower drop observed in the case of
the BLOOM-7B-FT model.

BLOOM-7B model exhibits robustness to various perturbations when applied on
the source side, except span noise. Conversely, the BLOOMZ-7B model is highly
sensitive to source-side perturbations, particularly impacted by span noise.
The BLOOM-7B and BLOOM-7B-FT models demonstrate comparable robustness, with
span and OCR attacks proving most detrimental. We observe varying trends
across translation directions in case of target-side perturbation. In the En-
XX translation direction, both the BLOOM-7B and BLOOMZ-7B models exhibit
susceptibility to various perturbations, except for punctuation drop.
Conversely, in the XX-En direction, the BLOOM-7B model is vulnerable to almost
all perturbation attacks, while the BLOOMZ-7B model demonstrates notable
robustness to all attacks apart from span noise. On the other hand, the
BLOOM-7B-FT model exhibits robustness across all evaluated attacks.
Furthermore, considering the free-form word order in Indian languages, the
anticipation that word order attacks on the Indic side would minimally impact
performance is contradicted by our observation of sensitivity to this attack
on the target side perturbation in the En-XX direction. Notably, we observe a
high susceptibility to word duplication attacks in BLOOM-7B models, despite
the expected benign nature of this attack as it introduces redundancy without
content deletions. Figures 3, 4 and 5 in Appendix A provide fine-grained
results across shots and perturbation attack variants.

### Findings about Llama 2 family:

Across various perturbation categories, in both the En-XX and XX-En
directions, we find that all models demonstrate strong robustness to various
attacks, except for susceptibility to the span noise attack on the target
side. This contrasts with the BLOOM family, where the task-specific fine-tuned
model BLOOM-7B-FT proved to be the most robust. We posit that the robustness
observed in Llama 2 7B model and its derivatives may be attributed to the
extensive pre-training they underwent and subsequent instruction tuning if
applicable. A comparative analysis of source and target-side perturbations
generally highlights that target-side perturbations have a higher impact.
Specifically, the span-noise attack significantly impacts the performance of
the ALMA and Llama 2 7B-Chat models, while OCR attacks exhibit minimal impact
across both translation and perturbation directions. A surprising observation
in this setup is that the Llama 2 7B model when subjected to various attacks
demonstrates strong improvements in performance over the clean baseline across
both translation and perturbation directions. Punctuation add and drop attacks
have variable impact with substantial improvements observed in the case of
Llama and Llama-Chat with punctuation add attacks and minimal improvement in
ALMA. Analyzing source side perturbations in the XX-En translation direction,
all models demonstrate robustness to word order, word duplication, punctuation
add, and punctuation drop attacks, with Llama and Llama-Chat displaying
marginal improvements in these scenarios. Under target side perturbation in
the XX-En translation direction, ALMA exhibits severe susceptibility to span
noise, while Llama-Chat is moderately affected, and Llama 2 shows slight
improvement. Figures 6, 7 and 8 in Appendix A provide fine-grained results
across shots and perturbation attack variants.

Our findings from BLOOM models align with the assertions of Raunak et al.
(2023), emphasizing that these models are more sensitive to target-side
perturbations. Notably, our study offers a more comprehensive evaluation,
encompassing diverse translation directions and perturbation types. While we
observe that in general target-side perturbations are more detrimental, our
findings reveal instances where source-side attacks, particularly span noise,
exert substantial impact. Upon comparing our observations from BLOOM and Llama
2 models with the findings of Raunak et al. (2023), it becomes apparent that
the sensitivity of models to perturbation direction varies among different
model families. This discrepancy may be attributed to factors such as pre-
training data, training steps, architecture depth and width, and the mixture
of SFT data (wherever applicable). Further investigation is imperative to
comprehensively understand the role of these factors in determining model
robustness, underscoring the necessity for a nuanced and model-specific
approach to robustness evaluation and limited generalizability of findings
from one model to another.

##  6 Conclusion

ICL dynamics in LLMs are influenced by the interplay between context
demonstrations and semantic priors from parametric memory, and the degree of
interplay varies depending on the task. Prior studies (Min et al., 2022; Yoo
et al., 2022; Wei et al., 2023; Kossen et al., 2023) primarily focus on
understanding these dynamics for NLU tasks, with limited applicability to NLG
tasks. In this study, we investigated the sensitivity of LLMs to the quality
of in-context examples in the context of MT across two model families: BLOOM
and Llama 2. We examine whether ICL is primarily driven by demonstrations or
if the clean instructions and pre-trained knowledge can be leveraged by the
model to mitigate the impact of noisy in-context examples. Our findings
indicate that the shifts in the output distribution of demonstrations
significantly affect the downstream MT performance, however, the shifts in the
input distribution cannot also be disregarded which is contrary to Raunak et
al. (2023). Notably, generalizing the robustness of ICL across various models
proves challenging as there are several aspects at play beyond in-context
examples which needs to be further investigated. We advocate for conducting
specific robustness tests for the specific model of interest, recognizing that
findings from other model families may not always universally hold true.

##  7 Limitations and Future Work

### Heterogeneous perturbations:

Our current experiments only focused on homogenous perturbations, where all
in-context examples are equally considered and applied uniform perturbation
levels. However, the assumption of models treating all examples equivalently
is questionable as reflected by findings of Yang et al. (2023) which suggest
that in-context examples might have varying relevance. Thus, it becomes
imperative to assess the models’ sensitivity to perturbation attacks that are
more heterogeneous and specifically target the most pertinent support samples.

### Directionality of in-context examples:

The emphasis on target language distribution over source language for in-
context MT was highlighted by Raunak et al. (2023) and is further reinforced
by our findings. Therefore, this warrants further exploration of whether the
directionality of the in-context examples influences the downstream MT
performance and whether target-original in-context examples can elicit more
fluent generations.

### Non-linguistic perturbations:

The current experiments were focused on only 5 non-linguistic perturbations
which conducted random textual attacks which were mostly uniform and language-
independent. However, it would be more interesting to explore more
linguistically aware attack types like causality alternation, entity, and
number replacements similar to Chen et al. (2023a).

### Extending this study across different model scales:

Our current investigation is limited only to the 7B model scale due to
computational constraints. However, exploring how the ICL capabilities of
different models vary with scales would provide a more comprehensive
understanding.

### Understanding whether ICL is example-driven or instruction-driven:

Our current experiments focus on maintaining a consistent high-quality
instruction while subjecting the in-context examples to various attacks. An
additional intriguing aspect to explore is the model’s capability to
comprehend tasks through example-based learning when provided with random or
noisy instructions. This investigation aims to understand whether ICL is
instruction-driven or example-driven or both.

##  8 Ethical Considerations

Potential toxic and hateful outputs: While we have only focused on MT, it is
not unlikely that our attacks may lead to toxic and hateful content being
generated as a result of the model’s distributions being perturbed.

Safety Circumvention and Jailbreaking Adversarial perturbations might be able
to circumvent a model’s safety parameters and enable the generation of biased
and harmful outputs. We plan to release our perturbation scripts and resultant
perturbed data for research, and we do not intend it to be used to perform
adversarial attacks in practice intended to undo the security features, also
known as jailbreaking, of a model.

## References

  * Ahuja et al. (2023) Sanchit Ahuja, Divyanshu Aggarwal, Varun Gumma, Ishaan Watts, Ashutosh Sathe, Millicent Ochieng, Rishav Hada, Prachi Jain, Maxamed Axmed, Kalika Bali, and Sunayana Sitaram. 2023.  Megaverse: Benchmarking large language models across languages, modalities, models and tasks.
  * Akyürek et al. (2023) Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. 2023.  What learning algorithm is in-context learning? investigations with linear models.  In _The Eleventh International Conference on Learning Representations_.
  * Belinkov and Bisk (2018) Yonatan Belinkov and Yonatan Bisk. 2018.  Synthetic and natural noise both break neural machine translation.  In _International Conference on Learning Representations_.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Chan et al. (2022) Stephanie C. Y. Chan, Adam Santoro, Andrew K. Lampinen, Jane X. Wang, Aaditya Singh, Pierre H. Richemond, Jay McClelland, and Felix Hill. 2022.  Data distributional properties drive emergent in-context learning in transformers.
  * Chen et al. (2023a) Mingda Chen, Kevin Heffernan, Onur Çelebi, Alexandre Mourachko, and Holger Schwenk. 2023a.  xSIM++: An improved proxy to bitext mining performance for low-resource languages.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 101–109, Toronto, Canada. Association for Computational Linguistics.
  * Chen et al. (2023b) Yanda Chen, Chen Zhao, Zhou Yu, Kathleen McKeown, and He He. 2023b.  On the relation between sensitivity and accuracy in in-context learning.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 155–167, Singapore. Association for Computational Linguistics.
  * Cheng et al. (2020) Minhao Cheng, Jinfeng Yi, Pin-Yu Chen, Huan Zhang, and Cho-Jui Hsieh. 2020.  Seq2sick: Evaluating the robustness of sequence-to-sequence models with adversarial examples.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 3601–3608. AAAI Press.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2022.  Palm: Scaling language modeling with pathways.
  * Costa-jussà et al. (2022) Marta R. Costa-jussà, James Cross, Onur Çelebi, Maha Elbayad, Kenneth Heafield, Kevin Heffernan, Elahe Kalbassi, Janice Lam, Daniel Licht, Jean Maillard, Anna Sun, Skyler Wang, Guillaume Wenzek, Al Youngblood, Bapi Akula, Loic Barrault, Gabriel Mejia Gonzalez, Prangthip Hansanti, John Hoffman, Semarley Jarrett, Kaushik Ram Sadagopan, Dirk Rowe, Shannon Spruit, Chau Tran, Pierre Andrews, Necip Fazil Ayan, Shruti Bhosale, Sergey Edunov, Angela Fan, Cynthia Gao, Vedanuj Goswami, Francisco Guzmán, Philipp Koehn, Alexandre Mourachko, Christophe Ropers, Safiyyah Saleem, Holger Schwenk, and Jeff Wang. 2022.  No language left behind: Scaling human-centered machine translation.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dong et al. (2023) Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, Lei Li, and Zhifang Sui. 2023.  A survey on in-context learning.
  * Ebrahimi et al. (2018) Javid Ebrahimi, Daniel Lowd, and Dejing Dou. 2018.  On adversarial examples for character-level neural machine translation.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 653–663, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Fan et al. (2022) Angela Fan, Suzana Ilic, Thomas Wolf, and Matthias Gallé, editors. 2022.  _Proceedings of BigScience Episode #5 – Workshop on Challenges & Perspectives in Creating Large Language Models_. Association for Computational Linguistics, virtual+Dublin.
  * Formento et al. (2023) Brian Formento, Chuan Sheng Foo, Luu Anh Tuan, and See Kiong Ng. 2023.  Using punctuation as an adversarial attack on deep learning-based NLP systems: An empirical study.  In _Findings of the Association for Computational Linguistics: EACL 2023_ , pages 1–34, Dubrovnik, Croatia. Association for Computational Linguistics.
  * Gala et al. (2023) Jay Gala, Pranjal A Chitale, A K Raghavan, Varun Gumma, Sumanth Doddapaneni, Aswanth Kumar M, Janki Atul Nawale, Anupama Sujatha, Ratish Puduppully, Vivek Raghavan, Pratyush Kumar, Mitesh M Khapra, Raj Dabre, and Anoop Kunchukuttan. 2023.  Indictrans2: Towards high-quality and accessible machine translation models for all 22 scheduled indian languages.  _Transactions on Machine Learning Research_.
  * Garg and Ramakrishnan (2020) Siddhant Garg and Goutham Ramakrishnan. 2020.  Bae: Bert-based adversarial examples for text classification.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics.
  * Goyal et al. (2022) Naman Goyal, Cynthia Gao, Vishrav Chaudhary, Peng-Jen Chen, Guillaume Wenzek, Da Ju, Sanjana Krishnan, Marc’Aurelio Ranzato, Francisco Guzmán, and Angela Fan. 2022.  The Flores-101 evaluation benchmark for low-resource and multilingual machine translation.  _Transactions of the Association for Computational Linguistics_ , 10:522–538.
  * Houlsby et al. (2019) Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin de Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. 2019.  Parameter-efficient transfer learning for nlp.
  * Hu et al. (2022) Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2022.  LoRA: Low-rank adaptation of large language models.  In _International Conference on Learning Representations_.
  * Joshi et al. (2020) Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S. Weld, Luke Zettlemoyer, and Omer Levy. 2020.  Spanbert: Improving pre-training by representing and predicting spans.
  * Kossen et al. (2023) Jannik Kossen, Yarin Gal, and Tom Rainforth. 2023.  In-context learning learns label relationships but is not conventional learning.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Li et al. (2023) Yingcong Li, M. Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. 2023.  Transformers as algorithms: Generalization and stability in in-context learning.
  * Lin et al. (2023) Bill Yuchen Lin, Abhilasha Ravichander, Ximing Lu, Nouha Dziri, Melanie Sclar, Khyathi Chandu, Chandra Bhagavatula, and Yejin Choi. 2023.  The unlocking spell on base llms: Rethinking alignment via in-context learning.
  * Liu et al. (2023) Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. 2023.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.  _ACM Comput. Surv._ , 55(9).
  * Lu et al. (2023) Sheng Lu, Irina Bigoulaeva, Rachneet Sachdeva, Harish Tayyar Madabushi, and Iryna Gurevych. 2023.  Are emergent abilities in large language models just in-context learning?
  * Maurya et al. (2023) Kaushal Kumar Maurya, Rahul Kejriwal, Maunendra Sankar Desarkar, and Anoop Kunchukuttan. 2023.  Utilizing lexical similarity to enable zero-shot machine translation for extremely low-resource languages.
  * Michel et al. (2019) Paul Michel, Xian Li, Graham Neubig, and Juan Pino. 2019.  On evaluation of adversarial perturbations for sequence-to-sequence models.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 3103–3114, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Min et al. (2022) Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2022.  Rethinking the role of demonstrations: What makes in-context learning work? In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 11048–11064, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Moradi and Samwald (2021) Milad Moradi and Matthias Samwald. 2021.  Evaluating the robustness of neural language models to input perturbations.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 1558–1570, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Muennighoff et al. (2023) Niklas Muennighoff, Thomas Wang, Lintang Sutawika, Adam Roberts, Stella Biderman, Teven Le Scao, M Saiful Bari, Sheng Shen, Zheng Xin Yong, Hailey Schoelkopf, Xiangru Tang, Dragomir Radev, Alham Fikri Aji, Khalid Almubarak, Samuel Albanie, Zaid Alyafeai, Albert Webson, Edward Raff, and Colin Raffel. 2023.  Crosslingual generalization through multitask finetuning.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 15991–16111, Toronto, Canada. Association for Computational Linguistics.
  * Niu et al. (2020) Xing Niu, Prashant Mathur, Georgiana Dinu, and Yaser Al-Onaizan. 2020.  Evaluating robustness to input perturbations for neural machine translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8538–8544, Online. Association for Computational Linguistics.
  * OpenAI et al. (2023) OpenAI, :, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mo Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapiro, Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Łukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Łukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichiro Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O’Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. 2023.  Gpt-4 technical report.
  * Ouyang et al. (2022) Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. 2022.  Training language models to follow instructions with human feedback.
  * Pfeiffer et al. (2021) Jonas Pfeiffer, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych. 2021.  AdapterFusion: Non-destructive task composition for transfer learning.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 487–503, Online. Association for Computational Linguistics.
  * Popović (2017) Maja Popović. 2017.  chrF++: words helping character n-grams.  In _Proceedings of the Second Conference on Machine Translation_ , pages 612–618, Copenhagen, Denmark. Association for Computational Linguistics.
  * Post (2018) Matt Post. 2018.  A call for clarity in reporting BLEU scores.  In _Proceedings of the Third Conference on Machine Translation: Research Papers_ , pages 186–191, Brussels, Belgium. Association for Computational Linguistics.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Raunak et al. (2023) Vikas Raunak, Arul Menezes, and Hany Awadalla. 2023.  Dissecting in-context learning of translations in GPT-3.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 866–872, Singapore. Association for Computational Linguistics.
  * Robinson et al. (2023) Nathaniel Robinson, Perez Ogayo, David R. Mortensen, and Graham Neubig. 2023.  ChatGPT MT: Competitive for high- (but not low-) resource languages.  In _Proceedings of the Eighth Conference on Machine Translation_ , pages 392–418, Singapore. Association for Computational Linguistics.
  * Sai B et al. (2023) Ananya Sai B, Tanay Dixit, Vignesh Nagarajan, Anoop Kunchukuttan, Pratyush Kumar, Mitesh M. Khapra, and Raj Dabre. 2023.  IndicMT eval: A dataset to meta-evaluate machine translation metrics for Indian languages.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 14210–14228, Toronto, Canada. Association for Computational Linguistics.
  * Salinas and Morstatter (2024) Abel Salinas and Fred Morstatter. 2024.  The butterfly effect of altering prompts: How small changes and jailbreaks affect large language model performance.  _arXiv preprint arXiv: 2401.03729_.
  * Sclar et al. (2023) Melanie Sclar, Yejin Choi, Yulia Tsvetkov, and Alane Suhr. 2023.  Quantifying language models’ sensitivity to spurious features in prompt design or: How i learned to start worrying about prompt formatting.  _arXiv preprint arXiv: 2310.11324_.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023.  Llama 2: Open foundation and fine-tuned chat models.
  * Vilar et al. (2023) David Vilar, Markus Freitag, Colin Cherry, Jiaming Luo, Viresh Ratnakar, and George Foster. 2023.  Prompting PaLM for translation: Assessing strategies and performance.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 15406–15427, Toronto, Canada. Association for Computational Linguistics.
  * Wei et al. (2022) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, E. Chi, Tatsunori Hashimoto, O. Vinyals, P. Liang, J. Dean, and W. Fedus. 2022.  Emergent abilities of large language models.  _Trans. Mach. Learn. Res._
  * Wei et al. (2023) Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, and Tengyu Ma. 2023.  Larger language models do in-context learning differently.
  * Xu et al. (2023) Haoran Xu, Young Jin Kim, Amr Sharaf, and Hany Hassan Awadalla. 2023.  A paradigm shift in machine translation: Boosting translation performance of large language models.
  * Xu et al. (2021) Weiwen Xu, Ai Ti Aw, Yang Ding, Kui Wu, and Shafiq Joty. 2021.  Addressing the vulnerability of NMT in input perturbations.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Industry Papers_ , pages 80–88, Online. Association for Computational Linguistics.
  * Yang et al. (2023) Zhe Yang, Damai Dai, Peiyi Wang, and Zhifang Sui. 2023.  Not all demonstration examples are equally beneficial: Reweighting demonstration examples for in-context learning.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 13209–13221, Singapore. Association for Computational Linguistics.
  * Yoo et al. (2022) Kang Min Yoo, Junyeob Kim, Hyuhng Joon Kim, Hyunsoo Cho, Hwiyeol Jo, Sang-Woo Lee, Sang-goo Lee, and Taeuk Kim. 2022.  Ground-truth labels matter: A deeper look into input-label demonstrations.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 2422–2437, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Zhang et al. (2023a) Biao Zhang, Barry Haddow, and Alexandra Birch. 2023a.  Prompting large language model for machine translation: A case study.  In _Proceedings of the 40th International Conference on Machine Learning_ , ICML’23. JMLR.org.
  * Zhang et al. (2023b) Ruiqi Zhang, Spencer Frei, and Peter L. Bartlett. 2023b.  Trained transformers learn linear models in-context.
  * Zhang et al. (2021) Xinze Zhang, Junzhe Zhang, Zhenhua Chen, and Kun He. 2021.  Crafting adversarial examples for neural machine translation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1967–1977, Online. Association for Computational Linguistics.
  * Zhang et al. (2022) Yunxiang Zhang, Liangming Pan, Samson Tan, and Min-Yen Kan. 2022.  Interpreting the robustness of neural NLP models to textual perturbations.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 3993–4007, Dublin, Ireland. Association for Computational Linguistics.
  * Zhao et al. (2018) Zhengli Zhao, Dheeru Dua, and Sameer Singh. 2018.  Generating natural adversarial examples.  In _International Conference on Learning Representations (ICLR)_.
  * Zhu et al. (2023) Wenhao Zhu, Hongyi Liu, Qingxiu Dong, Jingjing Xu, Shujian Huang, Lingpeng Kong, Jiajun Chen, and Lei Li. 2023.  Multilingual machine translation with large language models: Empirical results and analysis.  _arXiv preprint arXiv: 2304.04675_.

##  Appendix A Additional Results

Figures 3, 4 and 5 depict the trends in terms of ChRF scores observed in BLOOM
derivatives while Figures 6, 7 and 8 depict the same for Llama2-derivatives
when subject to different perturbation attacks across both source and target
side attacks across both En-XX and XX-En directions.

(a) En-XX (Source) - 1 shot

(b) En-XX (Target) - 1 shot

(c) XX-En (Source) - 1 shot

(d) XX-En (Target) - 1 shot

Figure 3: Variation in ChrF++ scores across different attack types observed in
BLOOM-7B derivatives when prompted in a 1-shot manner.

(a) En-XX (Source) - 4 shot

(b) En-XX (Target) - 4 shot

(c) XX-En (Source) - 4 shot

(d) XX-En (Target) - 4 shot

Figure 4: Variation in ChrF++ scores across different attack types observed in
BLOOM-7B derivatives when prompted in a 4-shot manner.

(a) En-XX (Source) - 8 shot

(b) En-XX (Target) - 8 shot

(c) XX-En (Source) - 8 shot

(d) XX-En (Target) - 8 shot

Figure 5: Variation in ChrF++ scores across different attack types observed in
BLOOM-7B derivatives when prompted in a 8-shot manner.

(a) En-X - 1 shot - source

(b) En-X - 1 shot - target)

(c) X-En - 1 shot - Source

(d) X-En 1-shot Target

Figure 6: Variation in ChrF++ scores across different attack types observed in
Llama2-7B derivatives when prompted in a 1-shot manner.

(a) En-X - 4 shot - source

(b) En-X - 4 shot - target)

(c) X-En - 4 shot - Source

(d) X-En 4-shot Target

Figure 7: Variation in ChrF++ scores across different attack types observed in
Llama2-7B derivatives when prompted in a 4-shot manner.

(a) En-X - 8 shot - source

(b) En-X - 8 shot - target)

(c) X-En - 8 shot - Source

(d) X-En 8-shot Target

Figure 8: Variation in ChrF++ scores across different attack types observed in
Llama2-7B derivatives when prompted in a 8-shot manner.


# Approximations of the Domination Number of a Graph

Glenn G. Chappell
Department of Computer Science
University of Alaska
Fairbanks, AK 99775-6670
<EMAIL_ADDRESS>John Gimbel
Department of Mathematics and Statistics
University of Alaska
Fairbanks, AK 99775-6660
<EMAIL_ADDRESS>Chris Hartman
Department of Computer Science
University of Alaska
Fairbanks, AK 99775-6670
<EMAIL_ADDRESS>
(January 17, 2017)

###### Abstract

Given a graph $G$, the domination number $\gamma(G)$ of $G$ is the minimum
order of a set $S$ of vertices such that each vertex not in $S$ is adjacent to
some vertex in $S$. Equivalently, label the vertices from $\\{0,1\\}$ so that
the sum over each closed neighborhood is at least one; the minimum value of
the sum of all labels, with this restriction, is the domination number. The
fractional domination number $\gamma_{f}(G)$ is defined in the same way,
except that the vertex labels are chosen from $[0,1]$. Given an ordering of
the vertex set of $G$, let $\gamma_{g}(G)$ be the approximation of the
domination number by the standard greedy algorithm. Computing the domination
number is NP-complete; however, we can bound $\gamma$ by these two more easily
computed parameters:

$\gamma_{f}(G)\leq\gamma(G)\leq\gamma_{g}(G).$

How good are these approximations? Using techniques from the theory of
hypergraphs, one can show that, for every graph $G$ of order $n$,

$\frac{\gamma_{g}(G)}{\gamma_{f}(G)}=O(\log n).$

On the other hand, we provide examples of graphs for which
$\gamma/\gamma_{f}=\Theta(\log n)$ and graphs for which
$\gamma_{g}/\gamma=\Theta(\log n)$. Lastly, we use our examples to compare two
bounds on $\gamma_{g}$.

2010 Mathematics Subject Classification. 05C69 (primary), 05C80 (secondary).

Key words and phrases. domination, fractional domination, greedy domination,
random graphs.

Graphs will be finite, simple, and undirected. For a graph $G$, we denote by
$\delta(G)$ and $\Delta(G)$ the minimum and maximum degree of $G$,
respectively. We use $N[v]$ to denote the closed neighborhood of a vertex $v$.
The closed neighborhood of a sequence of vertices, e.g.,
$N[v_{1},v_{2},\ldots,v_{k}]$, is the union of the closed neighborhoods of the
vertices in the sequence. We say that vertex $v$ _dominates_ vertex $u$ if $u$
lies in the closed neighborhood of $v$. See Haynes, Hedetniemi, & Slater [8]
for definitions of graph-theoretic terms and an introduction to domination in
graphs.

If we assign weights to the vertices of a graph, then the _total weight_ of a
set of vertices is the sum of the weights of the vertices in the set. We may
consider a dominating set as a $0,1$-weighting of the vertex set so that the
total weight of each closed neighborhood is at least one. Relaxing the
requirement that the weights be integers, we obtain a fractional version of
the domination number. Suppose we assign weight $f(v)\in[0,1]$ to each vertex
$v$. The function $f\colon V(G)\to[0,1]$ is a _fractional domination_ if for
each vertex $v$,

$\sum_{u\in N[v]}f(u)\geq 1.$

The _fractional domination number_ $\gamma_{f}(G)$ of $G$ is the minimum total
weight of the vertex set, taken over all fractional dominations of $G$.

A useful bound is the following, which was discovered independently by
Grinstead & Slater [7, Theorem 1] and by Domke, Hedetniemi, & Laskar [5,
Observation 3] (Observation 3 in the latter paper is slightly misstated, with
the inequalities in the wrong direction, but the proof is correct).

######  Lemma 1.

For a graph $G$ of order $n$,

$\frac{n}{1+\Delta(G)}\leq\gamma_{f}(G)\leq\frac{n}{1+\delta(G)}.\hbox{}\nobreak\hbox{\quad$\square$}$

Throughout this paper, we will implicitly assume an ordering on the vertex set
of a graph. Given such an ordering, we can approximate the domination number
using a greedy algorithm, as follows. Iteratively select vertices
$x_{1},x_{2},\ldots,x_{m}$ so that, for each $k=1,2,\ldots,m$, vertex $x_{k}$
is chosen so that it dominates as many vertices of
$V(G)-N[x_{1},x_{2},...,x_{k-1}]$ (that is, not-yet-dominated vertices) as
possible. Resolve ties by choosing $x_{k}$ as early as possible in the
ordering on $V(G)$. Stop the iterative process when every vertex is dominated
by one of the $x_{k}$’s. We refer to $x_{1},x_{2},\ldots,x_{m}$ as the _greedy
dominating sequence_. The _greedy domination number_ $\gamma_{g}(G)=m$ is the
number of vertices in this sequence.

Determining the domination number of a general graph is known to be NP-
complete (see Garey & Johnson [6]); it is natural to seek more easily computed
approximations. The values of $\gamma_{f}$ and $\gamma_{g}$ can be determined
in polynomial time. Further, the fact that $\gamma$ lies in the interval
$[\gamma_{f},\gamma_{g}]$ follows easily from definitions.

######  Observation 2.

For every graph $G$,

$\gamma_{f}(G)\leq\gamma(G)\leq\gamma_{g}(G).\hbox{}\nobreak\hbox{\quad$\square$}$

We study the relationships of these three parameters further.

Techniques from the theory of hypergraphs can be used to show that the
ratio$\gamma_{g}(G)/\gamma_{f}(G)$ is $O(\log\Delta)$, and thus $O(\log n)$,
where $n$ is the order of $G$; see Theorem 4, below. Thus $\gamma(G)$ must lie
within a relatively small interval. We produce examples showing that,
asymptotically, we can do no better. We show that $\gamma(G)/\gamma_{f}(G)$
can be $\Theta(\log n)$, and then we show that $\gamma_{g}(G)/\gamma(G)$ can
be $\Theta(\log n)$.

Since $\gamma_{g}$ is a useful upper bound on $\gamma$, it is worthwhile to
consider upper bounds on $\gamma_{g}$. One such bound follows immediately from
the above discussion:

$\gamma_{g}(G)\leq c\gamma_{f}(G)\log n,$

for some constant $c$, where $n$ is the order of $G$. Another class of bounds
are those in which $\gamma_{g}$ is bounded above by a constant multiple of
$(n\log\delta)/\delta$. The first of these was found by Alon & Spencer [1]
(see their Theorem 2.2 and the remarks following it). A slightly improved
bound was given by Clark, Shekhtman, Suen, & Fisher [4, Theorem 2]; we state
this below.

######  Theorem 3 (Clark, Shekhtman, Suen, & Fisher [4]).

For every graph $G$ of order $n$,

$\gamma_{g}(G)\leq
n\left[1-\prod_{i=1}^{\delta+1}\frac{i\delta}{i\delta+1}\right],$

where $\delta=\delta(G)$. $\square$

We note that the right side of the above inequality is
$\Theta\bigl{(}[n\log\delta]/\delta\bigr{)}$. At the conclusion of this paper,
we will compare these two bounds on $\gamma_{g}$, using examples to show that
sometimes one is tighter, and sometimes the other is.

In the following result, we will use a concept dual to fractional domination.
A function $f\colon V(G)\to[0,1]$ is a _fractional packing_ if for each vertex
$v$,

$\sum_{u\in N[v]}f(u)\leq 1.$

Note that the maximum total weight of $V(G)$, taken over all fractional
packings, and the minimum total weight of $V(G)$, taken over all fractional
dominations, are described by dual linear programs (see Haynes, Hedetniemi, &
Slater [8, Chapter 4] or Domke, Hedetniemi, & Laskar [5, Section 3]). Thus, by
the principle of strong duality, given a fractional packing on a graph $G$,
the total weight of the vertex set is at most $\gamma_{f}(G)$.

We now prove an upper bound on $\gamma_{g}(G)/\gamma_{f}(G)$. This is a
special case of a more general result on vertex covers of hypergraphs and is
similar to a bound found by Johnson [9, Theorem 4] and by Lovász [10,
Corollary 2] (see also Schrijver [13, Theorem 77.2]).

######  Theorem 4.

For every graph $G$,

$\frac{\gamma_{g}(G)}{\gamma_{f}(G)}\leq 1+\ln\bigl{[}1+\Delta(G)\bigr{]}.$

###### Proof.

Set $m=\gamma_{g}(G)$. Let $x_{1},x_{2},\ldots,x_{m}$ be the greedy dominating
sequence. For each vertex $v$ of $G$, let $g(v)$ be the first vertex in the
greedy dominating sequence that dominates $v$. Let $F(v)$ be the set of all
vertices of $G$ that are first dominated by $g(v)$; that is,
$F(v)=N[x_{k}]-N[x_{1},x_{2},\ldots,x_{k-1}]$, where $x_{k}=g(v)$. Let
$w(v)=\frac{1}{\left|F(v)\right|}$. So $w(v)$ is the reciprocal of the number
of vertices that are dominated in the same step of the greedy algorithm as
$v$. Note that $\sum_{u\in F(v)}w(u)=1$, and thus $\sum_{v\in V(G)}w(v)=m$.

Our proof is based on that of Schrijver [13, Theorem 77.2], and proceeds as
follows. We assign weight $w(v)$ to each vertex $v$. We find upper bounds on
the weights of vertices lying in a closed neighborhood, and conclude that, if
each vertex $v$ is given weight
$w(v)/\left(1+\ln\bigl{[}1+\Delta(G)\bigr{]}\right)$, then the result is a
fractional packing. Applying linear programming duality, we then obtain a
lower bound on $\gamma_{f}(G)$, from which our result follows.

Let $v$ be a vertex of $G$. We list the elements of $N[v]$ in the order in
which they were dominated in the greedy algorithm. Letting $p=1+\deg(v)$, we
represent $N[v]$ as $\\{u_{1},u_{2},\ldots,u_{p}\\}$, where, if $g(u_{i})$
comes before $g(u_{j})$ in the greedy dominating sequence, then $i<j$.

We claim that $w(u_{i})\leq\frac{1}{p+1-i}$ for each $u_{i}$. Suppose for a
contradiction that $\left|F(u_{i})\right|<p+1-i$, for some $u_{i}$. Then
$\left|F(u_{i})\right|<\bigl{|}\\{u_{i},u_{i+1},\ldots,u_{p}\\}\bigr{|}$, and
so replacing $g(u_{i})$ by $v$ in the greedy dominating sequence would
increase the number of vertices dominated at this step in the greedy
algorithm. However, this contradicts the definition of greedy dominating
sequence, and so $\left|F(u_{i})\right|\geq p+1-i$. Thus,

$w(u_{i})=\frac{1}{\left|F(u_{i})\right|}\leq\frac{1}{p+1-i},$

as claimed.

Hence, for each vertex $v$ we have

$\sum_{u\in
N[v]}w(u)\leq\sum_{i=1}^{p}\frac{1}{p+1-i}=\sum_{i=1}^{p}\frac{1}{i}\leq 1+\ln
p\leq 1+\ln\bigl{[}1+\Delta(G)\bigr{]}.$

Dividing by $1+\ln\bigl{[}1+\Delta(G)\bigr{]}$, we obtain

$\sum_{u\in N[v]}\frac{w(u)}{1+\ln\bigl{[}1+\Delta(G)\bigr{]}}\leq 1,$

and so assigning weight $w(v)/\left(1+\ln\bigl{[}1+\Delta(G)\bigr{]}\right)$
to each vertex $v$, results in a fractional packing. Therefore, as noted
before the statement of the theorem, the sum of all vertex weights is bounded
above by $\gamma_{f}(G)$. That is,

$\sum_{v\in
V(G)}\frac{w(v)}{1+\ln\bigl{[}1+\Delta(G)\bigr{]}}\leq\gamma_{f}(G).$

Multiplying by $1+\ln\bigl{[}1+\Delta(G)\bigr{]}$, we obtain

$\gamma_{g}(G)=m=\sum_{v\in
V(G)}w(v)\leq\left(1+\ln\bigl{[}1+\Delta(G)\bigr{]}\right)\gamma_{f}(G).$

Dividing by $\gamma_{f}(G)$ yields our result. $\square$

Hence the following.

######  Corollary 5.

For any graph $G$ of order $n$ with maximum degree $\Delta\geq 2$

$\gamma(G)\leq c_{1}\ln(\Delta)\gamma_{f}(G)$

and

$\gamma(G)\leq c_{2}\ln(n)\gamma_{f}(G),$

where $c_{1}$ and $c_{2}$ are appropriately chosen constants. $\square$

The preceding theorem and corollary place restrictions on the value of
$\gamma$. We now show that these restrictions are asymptotically best possible
up to a constant factor. We begin with a construction of a family of graphs in
which $\gamma$ lies near the high end of the interval
$[\gamma_{f},\gamma_{g}]$. Later, we will obtain better results using random
graphs.

######  Example 6.

Given a positive integer $t$, we construct a graph $J_{t}$ of order
$n=(2t)^{2t-1}$ such that

$\gamma_{f}(J_{t})=e+o(1)=\Theta(1)$

and

$\gamma(J_{t})=2t=\Theta\left(\frac{\log n}{\log\log n}\right).$

Let $t$ be a positive integer. Set $d=2t-1$ and $n=(2t)^{d}$. Let $G$ be the
graph $K_{2t}-tK_{2}$, that is, $K_{2t}$ with a perfect matching removed. Let
$J_{t}$ be the graph whose vertices are $d$-tuples of the form
$(x_{1},x_{2},\ldots,x_{d})$ where each $x_{i}$ is a vertex in $G$. Let
vertices $(x_{1},x_{2},\ldots,x_{d})$ and $(y_{1},y_{2},\ldots,y_{d})$ be
adjacent in $J_{t}$ if for each $i$, the vertices $x_{i}$ and $y_{i}$ are
equal or adjacent in $G$. (The way in which $J_{t}$ is constructed from $G$ is
often called the “strong [direct] product”.) We note that $J_{t}$ has order
$n$.

We show that $J_{t}$ has the required properties. For each vertex $v$ of $G$,
denote by $\overline{v}$ the unique vertex in $G$ that is not adjacent to $v$.

Note that $J_{t}$ is regular of degree $(2t-1)^{d}-1$. By Lemma 1,

$\gamma_{f}(J_{t})=\frac{n}{(2t-1)^{d}}=\frac{(d+1)^{d}}{d^{d}}=e+o(1).$

Let $S$ be a set of $d$ vertices of $J_{t}$. We write
$S=\bigl{\\{}\,\left(x_{1}^{i},x_{2}^{i},\ldots,x_{d}^{i}\right)\mathrel{\big{|}}i=1,2,\ldots,d\,\bigr{\\}}$.
Let
$u=\left(\overline{x_{1}^{1}},\overline{x_{2}^{2}},\ldots,\overline{x_{d}^{d}}\right)$.
Then $u$ is not dominated by any vertex in $S$, so $S$ is not a dominating
set. Hence, the domination number of $J_{t}$ is at least $d+1$. Now let $A$ be
the set of all vertices in $J_{t}$ of the form $(v,v,v,\ldots,v)$ where $v$ is
a vertex in $G$. Since there are $d+1$ such vertices, but only $d$
coordinates, every vertex of $J_{t}$ must be dominated by at least one vertex
of $A$. Thus, $A$ is a dominating set of size $d+1$, and so
$\gamma(J)=d+1=2t$. $\square$

For the graph $J_{t}$ of Example 6, $\gamma/\gamma_{f}=\Theta(\log n/\log\log
n)$. Thus we have constructed an infinite family of graphs for which the ratio
$\gamma/\gamma_{f}$ is unbounded. However, the ratio is not as high as we
would like. Using random graphs, we can produce better examples, for which
$\gamma/\gamma_{f}$ is, with high probability, $\Theta(\log n)$.

For each natural number $n$, let $R_{n}$ be a random graph on $n$ labeled
vertices with edge probability $1/2$. Given a graphical property $P$ we say
that $R_{n}$ _almost surely_ (a.s.) has $P$ if the probability that $R_{n}$
has $P$ goes to one as $n$ approaches infinity. See Palmer [12] for an
introduction to random graphs.

It is known that the domination number of $R_{n}$ is almost surely
$\Theta(\log n)$ (see Nikoletseas & Spirakis [11, Lemmas 1 & 2]). In fact,
much stronger results are known. Weber [14, Theorem 2] showed that
$\gamma(R_{n})$ is a.s. equal to one of two values given by explicit formulae.
For our purposes, it suffices that $\gamma(R_{n})$ is a.s. $\Theta(\log n)$.
On the other hand, $\gamma_{f}(R_{n})$ is a.s. $\Theta(1)$. We give a short
proof of these facts below.

######  Theorem 7.

Almost surely,

$\gamma_{f}(R_{n})=2+o(1)$

and

$\gamma(R_{n})=\Theta(\log n).$

###### Proof.

It is known that the degrees of all vertices in $R_{n}$ tend to concentrate
tightly around $n/2$. In particular, a.s.

$\bigl{[}1-o(1)\bigr{]}\frac{n}{2}\leq\delta(R_{n})\leq\Delta(R_{n})\leq\bigl{[}1+o(1)\bigr{]}\frac{n}{2}.$

This follows from a Chernoff bound [3, Theorem 1]; for a proof, see Palmer
[12, Theorem 5.1.4]. Applying Lemma 1, we conclude that a.s.
$\gamma_{f}(R_{n})=2+o(1)$.

Since $\gamma_{f}(R_{n})$ is a.s. $\Theta(1)$, by Corollary 5 we see that
$\gamma(R_{n})$ is a.s. $O(\log n)$. It remains to show that $\gamma(R_{n})$
is a.s. $\Omega(\log n)$. Fix $\varepsilon$ with $0<\varepsilon<1$. Set
$p=\bigl{\lfloor}(1-\varepsilon)\log_{2}n\bigr{\rfloor}$. We show that a.s.
$\gamma(R_{n})>p$, which will complete our proof.

Our argument is similar to that given by Nikoletseas & Spirakis [11, Lemma 1].
Let $S$ be a subset of $V(G)$ with order $p$. If $v$ is a vertex not in $S$
then the probability that $S$ dominates $v$ is
$1-\left(\frac{1}{2}\right)^{p}$. Hence, the probability that $S$ dominates
$R_{n}$ is $\left[1-\left(\frac{1}{2}\right)^{p}\right]^{n-p}$. Let $E$ be the
expected number of $p$-sets that dominate $R_{n}$. Then,

$\displaystyle
E=\binom{n}{p}\left[1-\left(\frac{1}{2}\right)^{p}\right]^{n-p}$
$\displaystyle\leq n^{p}\left[e^{-\left(1/2\right)^{p}}\right]^{n-p}$
$\displaystyle\leq
n^{p}e^{-\left(1/n^{1-\varepsilon}\right)(n-p)}\qquad\text{since $2^{p}\leq
n^{1-\varepsilon}$}$
$\displaystyle=e^{p\ln(n)-\left(n/n^{1-\varepsilon}\right)}e^{p/n^{1-\varepsilon}}$
$\displaystyle\leq ce^{p\ln(n)-n^{\varepsilon}},$

for some constant $c$. But the last expression goes to zero as $n$ approaches
infinity. Hence, $R_{n}$ a.s. has no dominating $p$-set. This leads to the
desired result. $\square$

When the random graph $R_{n}$ almost surely has some property, we may conclude
that, for each sufficiently large $n$, there exists a graph of order $n$
having the property. Hence, we obtain the following.

######  Corollary 8.

There exist graphs $G_{n}$, for infinitely many integers $n$, so that each
$G_{n}$ has order $n$, and

$\frac{\gamma(G_{n})}{\gamma_{f}(G_{n})}=\Theta(\log
n).\hbox{}\nobreak\hbox{\quad$\square$}$

Thus, the bounds in Corollary 5 are asymptotically best possible. We have
proven this using probabilistic methods. The best explicit construction we
have been able to find is that of the graphs $J_{t}$ from Example 6, for which
the ratio $\gamma/\gamma_{f}$ is smaller: $\Theta(\log n/\log\log n)$. We ask
whether an explicit construction can be found for the larger ratio.

######  Problem 9.

Find an explicit construction of graphs $G_{n}$, for infinitely many integers
$n$, so that each $G_{n}$ has order $n$, and

$\frac{\gamma(G_{n})}{\gamma_{f}(G_{n})}=\Theta\left(\log
n\right).\hbox{}\nobreak\hbox{\quad$\square$}$

We have seen that $\gamma_{g}/\gamma_{f}$ is $O(\log n)$, and that the ratio
$\gamma/\gamma_{f}$ may be $\Theta(\log n)$. In our next example the ratio
$\gamma_{g}/\gamma$ is $\Theta(\log n)$. Thus, $\gamma$ is near the low end of
the interval $[\gamma_{f},\gamma_{g}]$, and the greedy algorithm approximates
the domination number relatively poorly.

######  Example 10.

Given an integer $t\geq 4$, we construct a graph $H_{t}$ of order $n=2^{t+2}$
such that

$\gamma_{f}(H_{t})=\gamma(H_{t})=4$

and

$\gamma_{g}(H_{t})=t=\Theta(\log n).$

Let $t\geq 4$ be a natural number. Let $u_{1}$, $u_{2}$, $u_{3}$, $u_{4}$ be
vertices and set $S=\\{u_{1},u_{2},u_{3},u_{4}\\}$. To construct $H_{t}$,
begin with the union of $S$ and $t$ disjoint cliques:

$S\cup\bigl{[}K_{4}\cup K_{8}\cup K_{16}\cup\cdots\cup K_{2\cdot
2^{t}}\bigr{]}.$

Add additional edges so that each vertex of $S$ is adjacent to one quarter of
the vertices in each clique, and no two vertices of $S$ have any common
neighbors. Let $H_{t}$ be the resulting graph. We note that the order of
$H_{t}$ is

$4+4\bigl{[}1+2+4+\cdots+2^{t-1}\bigr{]}=2^{t+2}.$

Given a fractional domination of $H_{t}$, the total weight of the vertices in
each $N[u_{i}]$ is at least 1. Since the sets $N[u_{1}]$, $N[u_{2}]$,
$N[u_{3}]$, $N[u_{4}]$ are pairwise disjoint, we have $\gamma_{f}(H_{t})\geq
4$. On the other hand, $S$ dominates $H_{t}$, so $\gamma(H_{t})\leq 4$. Thus,

$4\leq\gamma_{f}(H_{t})\leq\gamma(H_{t})\leq 4,$

and we have $\gamma_{f}(H_{t})=\gamma(H_{t})=4$.

If we approximate $\gamma(H_{t})$ with the greedy algorithm, then we will
never choose any vertex in $S$. The greedy dominating sequence will contain
one vertex from each of the cliques used to construct $H_{t}$. Since $t\geq 4$
the first four such vertices chosen will dominate the four vertices in $S$,
and so $\gamma_{g}(H_{t})=t$. $\square$

Letting $n=2^{t+2}$, and letting $G_{n}$ be $H_{t}$ from the above example, we
obtain the following.

######  Corollary 11.

There exist graphs $G_{n}$, for infinitely many integers $n$, so that each
$G_{n}$ has order $n$, and

$\frac{\gamma_{g}(G_{n})}{\gamma(G_{n})}=\Theta(\log
n).\hbox{}\nobreak\hbox{\quad$\square$}$

We now consider upper bounds on $\gamma_{g}$. By Theorem 4 we have, for a
graph $G$ of order $n$,

$\gamma_{g}(G)\leq c_{1}\gamma_{f}(G)\log n,$ (1)

for some constant $c_{1}$. And by Theorem 3, we have

$\gamma_{g}(G)\leq c_{2}\frac{n\log\delta(G)}{\delta(G)},$ (2)

for some constant $c_{2}$.

Consider these bounds for the graph $H_{t}$ from Example 10. We have
$\gamma_{f}(H_{t})=4$, and clearly $\delta(H_{t})=4$. Thus, letting $n$ be the
order of $H_{t}$, the right-hand side of (1) is $\Theta(\log n)$, while the
right-hand side of (2) is $\Theta(n)$, making (1) by far the tighter bound.

On the other hand, let $t$ be a positive integer, and let $G$ be a $t$-clique
with a pendant vertex joined to each clique vertex (a “hairy clique”). Letting
$n$ be the order of $G$, we have $\gamma_{f}(G)=t=n/2$, and $\delta(G)=1$.
Thus, the right-hand side of (1) is $\Theta(n\log n)$, while the right-hand
side of (2) is $\Theta(n)$, making (2) the tighter bound.

## References

  * [1] N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, New York, 1992.
  * [2] B. Bollobás and P. Erdős, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1976), no. 3, 419–427.
  * [3] H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), no. 4, 493–507.
  * [4] W.E. Clark, B. Shekhtman, S. Suen, and D.C. Fisher, Upper bounds for the domination number of a graph, in Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1998), Congr. Numer. 132 (1998), 99–123.
  * [5] G.S. Domke, S.T. Hedetniemi, and R.C. Laskar, Fractional packings, coverings, and irredundance in graphs, in Proceedings of the Nineteenth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1988), Congr. Numer. 66 (1988), 227–238.
  * [6] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
  * [7] D.L. Grinstead and P.J. Slater, Fractional domination and fractional packing in graphs, in Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congr. Numer. 71 (1990), 153–172.
  * [8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
  * [9] D.S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. System Sci. 9 (1974), 256–278.
  * [10] L. Lovász, On the ratio of optimal integral and fractional covers, Discrete Math. 13 (1975), no. 4, 383–390.
  * [11] S.E. Nikoletseas and P.G. Spirakis, Near-optimal dominating sets in dense random graphs in polynomial expected time, in Graph-Theoretic Concepts in Computer Science, J. van Leeuwen, ed., Lecture Notes in Computer Science 790, Springer, Berlin, 1994, 1–10.
  * [12] E.M. Palmer, Graphical Evolution: An Introduction to the Theory of Random Graphs, Wiley, Chichester, 1985.
  * [13] A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Vol. C: Disjoint Paths, Hypergraphs, Springer-Verlag, Berlin, 2003.
  * [14] K. Weber, Domination number for almost every graph, Rostock. Math. Kolloq. 16 (1981), 31–43.