#  RePlug: Retrieval-Augmented Black-Box Language Models

Weijia Shi  Sewon Min  Michihiro Yasunaga  Minjoon Seo  Rich James  Mike Lewis
Luke Zettlemoyer  Wen-tau Yih

###### Abstract

We introduce RePlug, a retrieval-augmented language modeling framework that
treats the language model (LM) as a black box and augments it with a tuneable
retrieval model. Unlike prior retrieval-augmented LMs that train language
models with special cross attention mechanisms to encode the retrieved text,
RePlug simply prepends retrieved documents to the input for the frozen black-
box LM. This simple design can be easily applied to any existing retrieval and
language models. Furthermore, we show that the LM can be used to supervise the
retrieval model, which can then find documents that help the LM make better
predictions. Our experiments demonstrate that RePlug with the tuned retriever
significantly improves the performance of GPT-3 (175B) on language modeling by
6.3%, as well as the performance of Codex on five-shot MMLU by 5.1%.

##  1 Introduction

Large language models (LLMs) such as GPT-3 (Brown et al., 2020a) and Codex
(Chen et al., 2021a), have demonstrated impressive performance on a wide range
of language tasks. These models are typically trained on very large datasets
and store a substantial amount of world or domain knowledge implicitly in
their parameters. However, they are also prone to hallucination and cannot
represent the full long tail of knowledge from the training corpus. Retrieval-
augmented language models (Khandelwal et al., 2020; Borgeaud et al., 2022;
Izacard et al., 2022b; Yasunaga et al., 2022), in contrast, can retrieve
knowledge from an external datastore when needed, potentially reducing
hallucination and increasing coverage. Previous approaches of retrieval-
augmented language models require access to the internal LM representations
(e.g., to train the model (Borgeaud et al., 2022; Izacard et al., 2022b) or to
index the datastore (Khandelwal et al., 2020)), and are thus difficult to be
applied to very large LMs. In addition, many best-in-class LLMs can only be
accessed through APIs. Internal representations of such models are not exposed
and fine-tuning is not supported.

Figure 1:  Different from previous retrieval-augmented approaches (Borgeaud et
al., 2022) that enhance a language model with retrieval by updating the LM’s
parameters, RePlug treats the language model as a black box and augments it
with a frozen or tunable retriever. This black-box assumption makes RePlug
applicable to large LMs (i.e., >100B parameters), which are often served via
APIs.

In this work, we introduce RePlug (Retrieve and Plug), a new retrieval-
augmented LM framework where the language model is viewed as a black box and
the retrieval component is added as a tuneable plug-and-play module. Given an
input context, RePlug first retrieves relevant documents from an external
corpus using an off-the-shelf retrieval model. The retrieved documents are
prepended to the input context and fed into the black-box LM to make the final
prediction. Because the LM context length limits the number of documents that
can be prepended, we also introduce a new ensemble scheme that encodes the
retrieved documents in parallel with the same black-box LM, allowing us to
easily trade compute for accuracy. As shown in Figure 1, RePlug is extremely
flexible and can be used with any existing black-box LM and retrieval model.

We also introduce RePlug LSR (RePlug with LM-Supervised Retrieval), a training
scheme that can further improve the initial retrieval model in RePlug with
supervision signals from a black-box language model. The key idea is to adapt
the retriever to the LM, which is in contrast to prior work (Borgeaud et al.,
2022) that adapts language models to the retriever. We use a training
objective which prefers retrieving documents that improve language model
perplexity, while treating the LM as a frozen, black-box scoring function.

Our experiments show that RePlug can improve the performance of diverse black-
box LMs on both language modeling and downstream tasks, including MMLU
(Hendrycks et al., 2021) and open-domain QA (Kwiatkowski et al., 2019; Joshi
et al., 2017). For instance, RePlug can improve Codex (175B) performance on
MMLU by 4.5%, achieving comparable results to the 540B, instruction-finetuned
Flan-PaLM. Furthermore, tuning the retriever with our training scheme (i.e.,
RePlug LSR) leads to additional improvements, including up to 6.3% increase in
GPT-3 175B language modeling. To the best of our knowledge, our work is the
first to show the benefits of retrieval to large LMs (>100B model parameters),
for both reducing LM perplexity and and improving in-context learning
performance. We summarize our contributions as follows:

  * •

We introduce RePlug (§3), the first retrieval-augmented language modeling
framework for enhancing large black-box language models with retrieval.

  * •

We propose a training scheme (§4) to further adapt an off-the-shelf retrieval
model to the LM, using the language modeling scores as supervision signals,
resulting in improved retrieval quality.

  * •

Evaluations on language modeling (§6), open-domain QA and MMLU demonstrate
that RePlug can improve the performance of various language models such as
GPT, OPT and BLOOM, including very large models with up to 175B parameters.

##  2 Background and Related Work

Figure 2: RePlug at inference (§3). Given an input context, RePlug first
retrieves a small set of relevant documents from an external corpus using a
retriever (§3.1 Document Retrieval). Then it prepends each document separately
to the input context and ensembles output probabilities from different passes
(§3.2 Input Reformulation).

#### Black-box Language Models

Large language models (i.e., >100B), such as GPT-3 (Brown et al., 2020a),
Codex (Chen et al., 2021a), and Yuan 1.0 (Wu et al., 2021), are not open-
sourced due to commercial considerations and are only available as black-box
APIs, through which users can send queries and receive responses. On the other
hand, even open sourced language models such as OPT-175B (Zhang et al., 2022a)
and BLOOM-176B (Scao et al., 2022) require significant computational resources
to run and finetune locally. For example, finetuning BLOOM-176B requires 72
A100 GPUs (80GB memory, $15k each (Younes Belkda, 2022)), making them
inaccessible to researchers and developers with limited resources.
Traditionally, retrieval-augmented model frameworks (Khandelwal et al., 2020;
Borgeaud et al., 2022; Yu, 2022; Izacard et al., 2022b; Goyal et al., 2022)
have focused on the white-box setting, where language models are fine-tuned to
incorporate retrieved documents. However, the increasing scale and black-box
nature of large language models makes this approach infeasible. To address the
challenges posed by large language models, we investigate retrieval-
augmentation in the black-box setting, where users only have access to the
model predictions and cannot access or modify its parameters.

#### Retrieval-augmented Models

Augmenting language models with relevant information retrieved from various
knowledge stores has shown to be effective in improving performance on various
NLP tasks, including language modeling (Min et al., 2022; Borgeaud et al.,
2022; Khandelwal et al., 2020) and open-domain question answering (Lewis et
al., 2020; Izacard et al., 2022b; Hu et al., 2022). Specifically, using the
input as query, (1) a retriever first retrieves a set of documents (i.e.,
sequences of tokens) from a corpus and then (2) a language model incorporates
the retrieved documents as additional information to make a final prediction.
This style of retrieval can be added to both _encoder-decoder_ (Yu, 2022;
Izacard et al., 2022b) and decoder-only models (Khandelwal et al., 2020;
Borgeaud et al., 2022; Shi et al., 2022; Rubin et al., 2022). For example,
Atlas (Izacard et al., 2022b) finetunes an _encoder-decoder_ model jointly
with the retriever by modeling documents as latent variables, while RETRO
(Borgeaud et al., 2022) changes the decoder-only architecture to incorporate
retrieved texts and pretrains the language model from scratch. Both methods
require updating the model parameters through gradient descent, which cannot
be applied to black-box LMs. Another line of retrieval-augmented LMs such as
kNN-LM (Khandelwal et al., 2020; Zhong et al., 2022) retrieves a set of tokens
and interpolates between the LM’s next token distribution and kNN
distributions computed from the retrieved tokens at inference. Although kNN-LM
does not require additional training, it requires access to internal LM
representations to compute the kNN distribution, which are not always
available for large LMs such as GPT-3. In this work, we investigate ways to
improve large black-box language models with retrieval. While concurrent work
(Mallen et al., 2022; Si et al., 2023; Yu et al., 2023; Khattab et al., 2022)
has demonstrated that using a frozen retriever can improve GPT-3 performance
on open-domain question answering, we approach the problem in a more general
setting, including language modeling and understanding tasks. We also propose
an ensemble method to incorporate more documents and a training scheme to
further adapt the retriever to large LMs.

##  3 RePlug

We introduce RePlug (Retrieve and Plug), a new retrieval-augmented LM paradigm
where the language model is treated as black box and the retrieval component
is added as a potentially tuneable module.

As shown in Figure 2, given an input context, RePlug first retrieves a small
set of relevant documents from an external corpus using a retriever (§3.1).
Then we pass the concatenation of each retrieved document with the input
context through the LM in parallel, and ensemble the predicted probabilities
(§3.2).

###  3.1 Document Retrieval

Given an input context $x$, the retriever aims to retrieve a small set of
documents from a corpus $\mathcal{D}=\\{d_{1}...d_{m}\\}$ that are relevant to
$x$. Following prior work (Qu et al., 2021; Izacard & Grave, 2021b; Ni et al.,
2021), we use a dense retriever based on the dual encoder architecture, where
an encoder is used to encode both the input context $x$ and the document $d$.
Specifically, the encoder maps each document $d\in D$ to an embedding
$\textbf{E}(d)$ by taking the mean pooling of the last hidden representation
over the tokens in $d$. At query time, the same encoder is applied to the
input context $x$ to obtain a query embedding $\textbf{E}(x)$. The similarity
between the query embedding and the document embedding is computed by their
cosine similarity:

$\displaystyle s(d,x)=\cos(\textbf{E}(d),\textbf{E}(x))$ (1)

The top-$k$ documents that have the highest similarity scores when compared
with the input $x$ are retrieved in this step. For efficient retrieval, we
precompute the embedding of each document $d\in D$ and construct FAISS index
(Johnson et al., 2019) over these embeddings.

###  3.2 Input Reformulation

The retrieved top-$k$ documents provide rich information about the original
input context $x$ and can potentially help the LM to make a better prediction.
One simple way to incorporate the retrieved documents as part of the input to
the LM is to prepend $x$ with all $k$ documents. However, this simple scheme
is fundamentally restricted by the number of documents (i.e., $k$) we can
include, given the language model’s context window size. To address this
limitation, we adopt an ensemble strategy described as follows. Assume
$\mathcal{D}^{\prime}\subset\mathcal{D}$ consists of $k$ most relevant
documents to $x$, according to the scoring function in Eq. (1). We prepend
each document $d\in\mathcal{D}^{\prime}$ to $x$, pass this concatenation to
the LM separately, and then ensemble output probabilities from all $k$ passes.
Formally, given the input context $x$ and its top-$k$ relevant documents
$\mathcal{D}^{\prime}$, the output probability of the next token $y$ is
computed as a weighted average ensemble:

$\displaystyle p(y\mid
x,\mathcal{D}^{\prime})=\sum_{d\in\mathcal{D}^{\prime}}p(y\mid d\circ
x)\cdot\lambda(d,x),$

where $\circ$ denotes the concatenation of two sequences and the weight
$\lambda(d,x)$ is based on the similarity score between the document $d$ and
the input context $x$:

$\displaystyle\lambda(d,x)=\frac{e^{s(d,x)}}{\sum_{d\in\mathcal{D}^{\prime}}e^{s(d,x)}}$

Although our ensemble method requires running the LM $k$ times, the cross
attention is performed between each retrieved document and the input context.
Therefore, compared with the method of prepending all the retrieved documents,
our ensemble methods do not incur additional computational cost overhead.

Figure 3: RePlug LSR training process (§4). The retriever is trained using the
output of a frozen language model as supervision signals.

##  4 RePlug LSR: Training the Dense Retriever

Instead of relying only on existing neural dense retrieval models (Karpukhin
et al., 2020a; Izacard et al., 2022a; Su et al., 2022), we further propose
RePlug LSR (RePlug with LM-Supervised Retrieval), which _adapts_ the retriever
in RePlug by using the LM itself to provide supervision about which documents
should be retrieved.

Inspired by Sachan et al. (2022), our approach can be seen as adjusting the
probabilities of the retrieved documents to match the probabilities of the
output sequence perplexities of the language model. In other words, we would
like the retriever to find documents that result in lower perplexity scores.
As shown in Figure 3, our training algorithm consists of the four steps: (1)
retrieving documents and computing the retrieval likelihood (§4.1), (2)
scoring the retrieved documents by the language model (§4.2), (3) updating the
retrieval model parameters by minimizing the KL divergence between the
retrieval likelihood and the LM’s score distribution (§4.3), and (4)
asynchronous update of the datastore index (§4.4).

###  4.1 Computing Retrieval Likelihood

We retrieve $k$ documents $\mathcal{D}^{\prime}\subset\mathcal{D}$ with the
highest similarity scores from a corpus $\mathcal{D}$ given an input context
$x$, as described in §3.1. We then compute the retrieval likelihood of each
retrieved document $d$:

$\displaystyle P_{R}(d\mid
x)=\frac{e^{s(d,x)/\gamma}}{\sum_{d\in\mathcal{D}^{\prime}}e^{s(d,x)/\gamma}}$

where $\gamma$ is a hyperparameter that controls the temerature of the
softmax. Ideally, the retrieval likelihood is computed by marginalizing over
all the documents in the corpus $\mathcal{D}$, which is intractable in
practice. Therefore, we approximate the retrieval likelihood by only
marginalizing over the retrieved documents $\mathcal{D}^{\prime}$.

###  4.2 Computing LM likelihood

We use the LM as a scoring function to measure how much each document could
improve the LM perplexity. Specifically, we first compute $P_{LM}(y\mid d,x)$,
the LM probability of the ground truth output $y$ given the input context $x$
and a document $d$. The higher the probability, the better the document
$d_{i}$ is at improving the LM’s perplexity. We then compute the LM likelihood
of each document $d$ as follows:

$\displaystyle Q(d\mid x,y)=\frac{e^{P_{LM}(y\mid
d,x)/\beta}}{\sum_{d\in\mathcal{D}^{\prime}}e^{P_{LM}(y\mid d,x)/\beta}}$

where $\beta$ is another hyperparameter.

###  4.3 Loss Function

Given the input context $x$ and the corresponding ground truth continuation
$y$, we compute the retrieval likelihood and the language model likelihood.
The dense retriever is trained by minimizing the KL divergence between these
two distributions:

$\displaystyle\mathcal{L}=\frac{1}{|\mathcal{B}|}\sum_{x\in\mathcal{B}}{KL\Big{(}P_{R}(d\mid
x)\parallel Q_{\text{LM}}(d\mid x,y)\Big{)}},$

where $\mathcal{B}$ is a set of input contexts. When minimizing the loss, we
can only update the retrieval model parameters. The LM parameters are fixed
due to our black-box assumption.

###  4.4 Asynchronous Update of the Datastore Index

Because the parameters in the retriever are updated during the training
process, the previously computed document embeddings are no longer up to date.
Therefore, following Guu et al. (2020), we recompute the document embeddings
and rebuild the efficient search index using the new embeddings every $T$
training steps. Then we use the new document embeddings and index for
retrieval, and repeat the training procedure.

##  5 Training Setup

In this section, we describe the details of our training procedure. We first
describe the model setting in RePlug (§5.1) and then describe the procedure
for training the retriever in RePlug LSR (§5.2).

###  5.1 RePlug

In theory, any type of retriever, either dense (Karpukhin et al., 2020b; Ni et
al., 2021) or sparse (Robertson et al., 2009), could be used for RePlug.
Following prior work (Izacard et al., 2022b), we use the Contriever (Izacard
et al., 2022a) as the retrieval model for RePlug, as it has demonstrated
strong performance.

###  5.2 RePlug LSR

For RePlug LSR, we initialize the retriever with the Contriever model (Izacard
et al., 2022a). We use GPT-3 Curie (Brown et al., 2020b) as the supervision LM
to compute the LM likelihood.

#### Training data

We use 800K sequences of 256 tokens each, sampled from the Pile training data
(Gao et al., 2020), as our training queries. Each query is split into two
parts: the first 128 tokens are used as the input context $x$, and the last
128 tokens are used as the ground truth continuation $y$. For the external
corpus $D$, we sample 36M documents of 128 tokens from the Pile training data.
To avoid trivial retrieval, we ensure that the external corpus documents do
not overlap with the documents from which the training queries are sampled.

#### Training details

To make the training process more efficient, we pre-compute the document
embeddings of the external corpus $D$ and create a FAISS index (Johnson et
al., 2019) for fast similarity search. Given a query $x$, we retrieve the top
20 documents from the FAISS index and compute the retrieval likelihood and the
LM likelihood with a temperature of 0.1. We train the retriever using the Adam
optimizer (Kingma & Ba, 2015) with a learning rate of 2e-5, a batch size of
64, and a warmup ratio of 0.1. We re-compute the document embeddings every 3k
steps and fine-tune the retriever for a total of 25k steps.

Model |  | # Parameters | Original |  \+ RePlug | Gain % |  \+ RePlug LSR | Gain %
---|---|---|---|---|---|---|---
GPT-2 | Small | 117M | 1.33 | 1.26 | 5.3 | 1.21 | 9.0
| Medium | 345M | 1.20 | 1.14 | 5.0 | 1.11 | 7.5
| Large | 774M | 1.19 | 1.15 | 3.4 | 1.09 | 8.4
| XL | 1.5B | 1.16 | 1.09 | 6.0 | 1.07 | 7.8
GPT-3 | Ada | 350M | 1.05 | 0.98 | 6.7 | 0.96 | 8.6
(black-box) | Babbage | 1.3B | 0.95 | 0.90 | 5.3 | 0.88 | 7.4
| Curie | 6.7B | 0.88 | 0.85 | 3.4 | 0.82 | 6.8
| Davinci | 175B | 0.80 | 0.77 | 3.8 | 0.75 | 6.3
Table 1: Both RePlug and RePlug LSR consistently enhanced the performance of
different language models. Bits per byte (BPB) of the Pile using GPT-3 and
GPT-2 family models (Original) and their retrieval-augmented versions (+RePlug
and +RePlug LSR. The gain % shows the relative improvement of our models
compared to the original language model.

##  6 Experiments

We perform evaluations on both language modeling (§6.1) and downstream tasks
such as MMLU (§6.2) and open-domain QA (§6.3). In all settings, RePlug ĩmprove
the performance of various black-box language models, showing the
effectiveness and generality of our approach.

###  6.1 Language Modeling

#### Datasets

The Pile (Gao et al., 2020) is a language modeling benchmark that consists of
text sources from diverse domains such as web pages, code and academic papers.
Following prior work, we report bits per UTF-8 encoded byte (BPB) as the
metric on each subset domain.

#### Baselines

We consider GPT-3 and GPT-2 family language model as the baselines. The four
models from GPT-3 (Davinci, Curie, Baddage and Ada) are black-box models that
are only accessible through API

#### Our model

We add RePlug and RePlug LSR to the baselines. We randomly subsampled Pile
training data (367M documents of 128 tokens) and use them as the retrieval
corpus for all models. As the Pile dataset has made efforts to deduplicate
documents across train, validation and test splits (Gao et al., 2020), we did
not do additional filtering. For both RePlug and RePlug LSR, we use a length
of 128-token context to do retrieval and adopt the ensemble method (Section
3.2) to incorporate top 10 retrieved documents during inference.

#### Results

Table 1 reports the results of the original baselines, baselines augmented
with the RePlug, and baselines augmented with the RePlug LSR. We observe that
both RePlug and RePlug LSR significantly outperform the baselines. This
demonstrates that simply adding a retrieval module to a frozen language model
(i.e., the black-box setting) is effective at improving the performance of
different sized language models on language modeling tasks. Furthermore,
RePlug LSR consistently performs better than RePlug by a large margin.
Specifically, RePlug LSR results in 7.7% improvement over baselines compared
to 4.7% improvement of RePlug averaged over the 8 models. This indicates that
further adapting the retriever to the target LM is beneficial.

###  6.2 MMLU

Model | # Parameters | Humanities | Social. | STEM | Other | All
---|---|---|---|---|---|---
Codex | 175B | 74.2 | 76.9 | 57.8 | 70.1 | 68.3
PaLM | 540B | 77.0 | 81.0 | 55.6 | 69.6 | 69.3
Flan-PaLM | 540B | - | - | - | - | 72.2
Atlas | 11B | 46.1 | 54.6 | 38.8 | 52.8 | 47.9
Codex + RePlug | 175B | 76.0 | 79.7 | 58.8 | 72.1 | 71.4
Codex + RePlug LSR | 175B | 76.5 | 79.9 | 58.9 | 73.2 | 71.8
Table 2: RePlug and RePlug LSR improves Codex by 4.5% and 5.1% respectively.
Performance on MMLU broken down into 4 categories. The last column averages
the performance over these categories. All models are evaluated based on
5-shot in-context learning with direct prompting.

#### Datasets

Massive Multi-task Language Understanding (MMLU (Hendrycks et al., 2021)) is a
multiple choice QA dataset that covers exam questions from 57 tasks including
mathematics, computer science, law, US history and etc. The 57 tasks are
grouped into 4 categories: humanities, STEM, social sciences and other.
Following Chung et al. (2022a), we evaluate RePlug in the 5-shot in-context
learning setting.

#### Baselines

We consider two groups of strong previous models as baselines for comparisons.
The first group of baselines is the state-of-the-art LLMs including
Codex111Code-Davinci-002 (Chen et al., 2021b), PaLM (Chowdhery et al., 2022),
and Flan-PaLM (Chung et al., 2022b). According to Chung et al. (2022b), these
three models rank top-3 in the leaderboard of MMLU. The second group of
baselines consists of retrieval-augmented language models. We only include
Atlas (Izacard et al., 2022b) in this group, as no other retrieval-augmented
LMs have been evaluated on the MMLU dataset. Atlas trains both the retriever
and the language model, which we consider a white-box retrieval LM setting.

#### Our model

We add RePlug and RePlug LSR only to Codex because other models such as PaLM
and Flan-PaLM are not accessible to the public. We use the test question as
the query to retrieve 10 relevant documents from Wikipedia (2018, December)
and prepend each retrieved document to the test question, resulting in 10
separate inputs. These inputs are then separately fed into the language
models, and the output probabilities are ensemble together.

#### Results

Table 2 presents the results from the baselines, RePlug, and RePlug LSR on the
MMLU dataset. We observe that both the RePlug and RePlug LSR improve the
original Codex model by 4.5% and 5.1%, respectively. In addition, RePlug LSR
largely outperforms the previous retrieval-augmented language model, Atlas,
demonstrating the effectiveness of our black-box retrieval language model
setting. Although our models slightly underperform Flan-PaLM, this is still a
strong result because Flan-PaLM has three times more parameters. We would
expect that the RePlug LSR could further improve Flan-PaLM, if we had access
to the model.

Another interesting observation is that the RePlug LSR outperforms the
original model by 1.9% even in the STEM category. This suggests that retrieval
may improve a language model’s problem-solving abilities.

###  6.3 Open Domain QA

Lastly, we conduct evaluation on two open-domain QA datasets: Natural
Questions (NQ) (Kwiatkowski et al., 2019) and TriviaQA (Joshi et al., 2017).

| NQ | TQA
---|---|---
Model | Few-shot | Full | Few-shot | Full
Chinchilla | 35.5 | - | 64.6 | -
PaLM | 39.6 | - | - | -
Codex | 40.6 | - | 73.6 | -
RETRO† | - | 45.5 | - | -
R2-D2† | - | 55.9 | - | 69.9
Atlas† | 42.4 | 60.4 | 74.5 | 79.8
Codex + Contrievercc222Si et al. (2022) augment Codex with concatenation of 10 documents retrieved by contriever. | 44.2 | - | 76.0 | -
Codex + RePlug | 44.7 | - | 76.8 | -
Codex + RePlug LSR | 45.5 | - | 77.3 | -
Table 3: Performance on NQ and TQA. We report results for both few-shot (64
shots for Chinchilla, PaLM, and Atlas; 16 shots for Codex-based models) and
full training data settings. RePlug LSR improves Codex by 12.0% on NQ and 5.0%
on TQA, making it the best-performing model in the few-shot setting. Note that
models with † are finetuned using training examples, while other models use
in-context learning.

#### Datasets

NQ and TriviaQA are two open-domain QA datasets consisting of questions,
answers collected from Wikipedia and the Web. Following prior work (Izacard &
Grave, 2021a; Si et al., 2022), we report results for the filtered set of
TriviaQA. For evaluation, we consider the few-shot setting where the model is
only given a few training examples and full data where the model is given all
the training examples.

#### Baselines

We compare our model with several state-of-the-art baselines, both in a few-
shot setting and with full training data. The first group of models consists
of powerful large language models, including Chinchilla (Hoffmann et al.,
2022), PaLM (Chowdhery et al., 2022), and Codex. These models are all
evaluated using in-context learning under the few-shot setting, with
Chinchilla and PaLM evaluated using 64 shots, and Codex using 16 shots. The
second group of models for comparison includes retrieval-augmented language
models such as RETRO (Borgeaud et al., 2021), R2-D2 (Fajcik et al., 2021), and
Atlas (Izacard et al., 2022b). All of these retrieval-augmented models are
finetuned on the training data, either in a few-shot setting or with full
training data. Specifically, Atlas is finetuned on 64 examples in the few-shot
setting.

#### Our model

We add RePlug and RePlug LSR to Codex with Wikipedia (2018, December) as the
retrieval corpus to evaluate the model in a 16-shot in context learning.
Similar to the setting in language modeling and MMLU, we incorporate top-10
retrieved documents using our proposed ensemble method.

#### Results

As shown in Table 3, RePlug LSR significantly improves the performance of the
original Codex by 12.0% on NQ and 5.0% on TQA. It outperforms the previous
best model, Atlas, which was fine-tuned with 64 training examples, achieving a
new state-of-the-art in the few-shot setting. However, this result still lags
behind the performance of retrieval-augmented language models fine-tuned on
the full training data. This is likely due to the presence of near-duplicate
test questions in the training set (e.g., Lewis et al. (2021) found that 32.5%
of test questions overlap with the training sets in NQ).

##  7 Analysis

Figure 4:  Ensembling random documents does not result in improved
performance. BPB of Curie augmented with different methods (random, RePlug and
RePlug LSR) when varying the number of documents (i.e.; number of ensemble
times.)

###  7.1 RePlug performance gain does not simply come from the ensembling
effect

The core of our method design is the use of an ensemble method that combines
output probabilities of different passes, in which each retrieved document is
prepended separately to the input and fed into a language model. To study
whether the gains come solely from the ensemble method, we compare our method
to ensembling random documents. For this, we randomly sample several
documents, concatenated each random document with the input, and ensemble the
outputs of different runs (referred to as "random"). As shown in Figure 6, we
evaluated the performance of GPT-3 Curie on Pile when augmented with random
documents, documents retrieved by RePlug, and documents retrieved by RePlug
LSR. We observed that ensembling random documents leads to worse performance,
indicating that the performance gains of RePlug do not solely come from the
ensembling effect. Instead, ensembling the relevant documents is crucial for
the success of RePlug. Additionally, as more documents were ensembled, the
performance of RePlug and RePlug LSR improved monotonically. However, a small
number of documents (e.g., 10) was sufficient to achieve large performance
gains.

Figure 5:  GPT-2, BLOOM and OPT models of varying sizes consistently benefit
from RePlug. The x-axis indicates the size of the language model and the
y-axis is its perplexity on Wikitext-103.

###  7.2 RePlug is applicable to diverse language models

Here we further study whether RePlug could enhance diverse language model
families that have been pre-trained using different data and methods.
Specifically, we focus on three groups of language models with varying sizes:
GPT-2 (117M, 345M, 774M, 1.5B parameters) (Brown et al., 2020a), OPT (125M,
350M, 1.3B, 2.7B, 6.7B, 13B, 30B, 66B) (Zhang et al., 2022b) and BLOOM (560M,
1.1B, 1.7B, 3B and 7B) (Scao et al., 2022). We evaluate each model on
Wikitext-103 (Stephen et al., 2017) test data and report its perplexity. For
comparison, we augment each model with RePlug that adopts the ensemble method
to incorporate top 10 retrieved documents. Following prior work (Khandelwal et
al., 2020), we use Wikitext-103 training data as the retrieval corpus.

Figure 5 shows the performance of different-sized language models with and
without RePlug. We observe that the performance gain brought by RePlug stays
consistent with model size. For example, OPT with 125M parameters achieves
6.9% perplexity improvement, while OPT with 66B parameters achieves 5.6%
perplexity improvement. Additionally, RePlug improves the perplexity of all
the model families. This indicates that RePlug is applicable to diverse
language models with different sizes.

###  7.3 Qualitative Analysis: rare entities benefit from retrieval

To understand why the RePlug improves language modeling performance, we
conducted manual analysis of examples in which the RePlug results in a
decrease in perplexity. We find that RePlug is more helpful when texts contain
rare entities. Figure 6 shows a test context and its continuation from the
Wikitext-103 test set. For RePlug, we use the test context as a query to
retrieve a relevant document from Wikitext-103 training data. We then compute
the perplexity of the continuation using the original GPT-2 1.5B and its
RePlug enhanced version. After incorporating the retrieved document, the
perplexity of the continuation improves by 11%. Among all tokens in the
continuation, we found that RePlug is most helpful for the rare entity name
"Li Bai". This is likely because the original LM does not have sufficient
information about this rare entity name. However, by incorporating the
retrieved document, RePlug was able to match the name with the relevant
information in the retrieved document, resulting in better performance.

Figure 6: Rare entities benefit from retrieval. After incorporating the
retrieved document during inference, the entity "Li Bai" and the token
"greatest" in the continuation show the most improvement in perplexity (15%
for "Li Bai" and 5% for "greatest"). Other tokens’ perplexity changes are
within 5%.

##  8 Conclusion

We introduce RePlug, a retrieval-augmented language modeling paradigm that
treats the language model as a black box and augments it with a tuneable
retrieval model. Our evaluation shows that RePlug can be integrated with any
existing language model to improve their performance on language modeling or
downstream tasks. This work opens up new possibilities for integrating
retrieval into large-scale black-box language models and demonstrates even the
state-of-the-art large-scale LMs could benefit from retrieval. However, RePlug
lacks interpretability as it is unclear when the model relies on retrieved
knowledge or parametric knowledge. Future research could focus on developing
more interpretable retrieval-augmented language models.

## References

  * Borgeaud et al. (2021) Borgeaud, S., Mensch, A., Hoffmann, J., Cai, T., Rutherford, E., Millican, K., Driessche, G. v. d., Lespiau, J.-B., Damoc, B., Clark, A., et al.  Improving language models by retrieving from trillions of tokens.  _arXiv preprint arXiv:2112.04426_ , 2021.
  * Borgeaud et al. (2022) Borgeaud, S., Mensch, A., Hoffmann, J., Cai, T., Rutherford, E., Millican, K., Van Den Driessche, G. B., Lespiau, J.-B., Damoc, B., Clark, A., et al.  Improving language models by retrieving from trillions of tokens.  In _International Conference on Machine Learning_ , pp. 2206–2240. PMLR, 2022.
  * Brown et al. (2020a) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D.  Language models are few-shot learners.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 1877–1901. Curran Associates, Inc., 2020a.  URL https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf.
  * Brown et al. (2020b) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D.  Language models are few-shot learners.  In _Proc. of NeurIPS_ , 2020b.  URL https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf.
  * Chen et al. (2021a) Chen, M., Tworek, J., Jun, H., Yuan, Q., de Oliveira Pinto, H. P., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P., Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, L., Bavarian, M., Winter, C., Tillet, P., Such, F. P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E., Herbert-Voss, A., Guss, W. H., Nichol, A., Paino, A., Tezak, N., Tang, J., Babuschkin, I., Balaji, S., Jain, S., Saunders, W., Hesse, C., Carr, A. N., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M., Brundage, M., Murati, M., Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S., Sutskever, I., and Zaremba, W.  Evaluating large language models trained on code.  _CoRR_ , abs/2107.03374, 2021a.  URL https://arxiv.org/abs/2107.03374.
  * Chen et al. (2021b) Chen, M., Tworek, J., Jun, H., Yuan, Q., de Oliveira Pinto, H. P., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P., Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, L., Bavarian, M., Winter, C., Tillet, P., Such, F. P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E., Herbert-Voss, A., Guss, W. H., Nichol, A., Paino, A., Tezak, N., Tang, J., Babuschkin, I., Balaji, S., Jain, S., Saunders, W., Hesse, C., Carr, A. N., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M., Brundage, M., Murati, M., Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S., Sutskever, I., and Zaremba, W.  Evaluating large language models trained on code.  _CoRR_ , abs/2107.03374, 2021b.  URL https://arxiv.org/abs/2107.03374.
  * Chowdhery et al. (2022) Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_ , 2022.
  * Chung et al. (2022a) Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, E., Wang, X., Dehghani, M., Brahma, S., et al.  Scaling instruction-finetuned language models.  _arXiv preprint arXiv:2210.11416_ , 2022a.
  * Chung et al. (2022b) Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, E., Wang, X., Dehghani, M., Brahma, S., et al.  Scaling instruction-finetuned language models.  _arXiv preprint arXiv:2210.11416_ , 2022b.
  * Fajcik et al. (2021) Fajcik, M., Docekal, M., Ondrej, K., and Smrz, P.  R2-D2: A modular baseline for open-domain question answering.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pp. 854–870, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.findings-emnlp.73.  URL https://aclanthology.org/2021.findings-emnlp.73.
  * Gao et al. (2020) Gao, L., Biderman, S., Black, S., Golding, L., Hoppe, T., Foster, C., Phang, J., He, H., Thite, A., Nabeshima, N., Presser, S., and Leahy, C.  The Pile: An 800gb dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_ , 2020.
  * Goyal et al. (2022) Goyal, A., Friesen, A., Banino, A., Weber, T., Ke, N. R., Badia, A. P., Guez, A., Mirza, M., Humphreys, P. C., Konyushova, K., et al.  Retrieval-augmented reinforcement learning.  In _International Conference on Machine Learning_ , pp. 7740–7765. PMLR, 2022.
  * Guu et al. (2020) Guu, K., Lee, K., Tung, Z., Pasupat, P., and Chang, M.  Retrieval augmented language model pre-training.  In _International Conference on Machine Learning_ , pp. 3929–3938. PMLR, 2020.
  * Hendrycks et al. (2021) Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J.  Measuring massive multitask language understanding.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=d7KBjmI3GmQ.
  * Hoffmann et al. (2022) Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D. d. L., Hendricks, L. A., Welbl, J., Clark, A., et al.  Training compute-optimal large language models.  _arXiv preprint arXiv:2203.15556_ , 2022.
  * Hu et al. (2022) Hu, Y., Hua, H., Yang, Z., Shi, W., Smith, N. A., and Luo, J.  Promptcap: Prompt-guided task-aware image captioning.  _arXiv preprint arXiv:2211.09699_ , 2022.
  * Izacard & Grave (2021a) Izacard, G. and Grave, E.  Leveraging passage retrieval with generative models for open domain question answering.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pp. 874–880, Online, April 2021a. Association for Computational Linguistics.  doi: 10.18653/v1/2021.eacl-main.74.  URL https://aclanthology.org/2021.eacl-main.74.
  * Izacard & Grave (2021b) Izacard, G. and Grave, E.  Leveraging passage retrieval with generative models for open domain question answering.  In _Proc. of EACL_ , 2021b.  URL https://arxiv.org/abs/2007.01282.
  * Izacard et al. (2022a) Izacard, G., Caron, M., Hosseini, L., Riedel, S., Bojanowski, P., Joulin, A., and Grave, E.  Unsupervised dense information retrieval with contrastive learning.  _Transactions on Machine Learning Research_ , 2022a.  URL https://openreview.net/forum?id=jKN1pXi7b0.
  * Izacard et al. (2022b) Izacard, G., Lewis, P., Lomeli, M., Hosseini, L., Petroni, F., Schick, T., Dwivedi-Yu, J., Joulin, A., Riedel, S., and Grave, E.  Few-shot learning with retrieval augmented language models.  _arXiv preprint arXiv:2208.03299_ , 2022b.
  * Johnson et al. (2019) Johnson, J., Douze, M., and Jégou, H.  Billion-scale similarity search with gpus.  _IEEE Transactions on Big Data_ , 7(3):535–547, 2019.
  * Joshi et al. (2017) Joshi, M., Choi, E., Weld, D., and Zettlemoyer, L.  TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1601–1611, Vancouver, Canada, July 2017. Association for Computational Linguistics.  doi: 10.18653/v1/P17-1147.  URL https://aclanthology.org/P17-1147.
  * Karpukhin et al. (2020a) Karpukhin, V., Oguz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t.  Dense passage retrieval for open-domain question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 6769–6781, Online, November 2020a. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-main.550.  URL https://aclanthology.org/2020.emnlp-main.550.
  * Karpukhin et al. (2020b) Karpukhin, V., Oguz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t.  Dense passage retrieval for open-domain question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 6769–6781, 2020b.
  * Khandelwal et al. (2020) Khandelwal, U., Levy, O., Jurafsky, D., Zettlemoyer, L., and Lewis, M.  Generalization through memorization: Nearest neighbor language models.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=HklBjCEKvH.
  * Khattab et al. (2022) Khattab, O., Santhanam, K., Li, X. L., Hall, D., Liang, P., Potts, C., and Zaharia, M.  Demonstrate-search-predict: Composing retrieval and language models for knowledge-intensive nlp.  _arXiv preprint arXiv:2212.14024_ , 2022.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  In _ICLR (Poster)_ , 2015.
  * Kwiatkowski et al. (2019) Kwiatkowski, T., Palomaki, J., Redfield, O., Collins, M., Parikh, A., Alberti, C., Epstein, D., Polosukhin, I., Devlin, J., Lee, K., Toutanova, K., Jones, L., Kelcey, M., Chang, M.-W., Dai, A. M., Uszkoreit, J., Le, Q., and Petrov, S.  Natural questions: A benchmark for question answering research.  _Transactions of the Association for Computational Linguistics_ , 7:452–466, 2019.  doi: 10.1162/tacl_a_00276.  URL https://aclanthology.org/Q19-1026.
  * Lewis et al. (2020) Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W.-t., Rocktäschel, T., Riedel, S., and Kiela, D.  Retrieval-augmented generation for knowledge-intensive nlp tasks, 2020\.  URL https://arxiv.org/abs/2005.11401.
  * Lewis et al. (2021) Lewis, P., Stenetorp, P., and Riedel, S.  Question and answer test-train overlap in open-domain question answering datasets.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pp. 1000–1008, 2021.
  * Mallen et al. (2022) Mallen, A., Asai, A., Zhong, V., Das, R., Hajishirzi, H., and Khashabi, D.  When not to trust language models: Investigating effectiveness and limitations of parametric and non-parametric memories.  _arXiv preprint arXiv:2212.10511_ , 2022.
  * Min et al. (2022) Min, S., Shi, W., Lewis, M., Chen, X., Yih, W.-t., Hajishirzi, H., and Zettlemoyer, L.  Nonparametric masked language modeling.  _arXiv preprint arXiv:2212.01349_ , 2022.
  * Ni et al. (2021) Ni, J., Qu, C., Lu, J., Dai, Z., Ábrego, G. H., Ma, J., Zhao, V. Y., Luan, Y., Hall, K. B., Chang, M., and Yang, Y.  Large dual encoders are generalizable retrievers, 2021.  URL https://arxiv.org/abs/2112.07899.
  * Qu et al. (2021) Qu, Y., Ding, Y., Liu, J., Liu, K., Ren, R., Zhao, W. X., Dong, D., Wu, H., and Wang, H.  RocketQA: An optimized training approach to dense passage retrieval for open-domain question answering.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 5835–5847, Online, June 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.naacl-main.466.  URL https://aclanthology.org/2021.naacl-main.466.
  * Robertson et al. (2009) Robertson, S., Zaragoza, H., et al.  The probabilistic relevance framework: Bm25 and beyond.  _Foundations and Trends® in Information Retrieval_ , 3(4):333–389, 2009.
  * Rubin et al. (2022) Rubin, O., Herzig, J., and Berant, J.  Learning to retrieve prompts for in-context learning.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 2655–2671, 2022.
  * Sachan et al. (2022) Sachan, D. S., Lewis, M., Yogatama, D., Zettlemoyer, L., Pineau, J., and Zaheer, M.  Questions are all you need to train a dense passage retriever.  _arXiv preprint arXiv:2206.10658_ , 2022.
  * Scao et al. (2022) Scao, T. L., Fan, A., Akiki, C., Pavlick, E., Ilić, S., Hesslow, D., Castagné, R., Luccioni, A. S., Yvon, F., Gallé, M., et al.  Bloom: A 176b-parameter open-access multilingual language model.  _arXiv preprint arXiv:2211.05100_ , 2022.
  * Shi et al. (2022) Shi, W., Michael, J., Gururangan, S., and Zettlemoyer, L.  Nearest neighbor zero-shot inference.  2022\.
  * Si et al. (2022) Si, C., Gan, Z., Yang, Z., Wang, S., Wang, J., Boyd-Graber, J., and Wang, L.  Prompting gpt-3 to be reliable.  _arXiv preprint arXiv:2210.09150_ , 2022.
  * Si et al. (2023) Si, C., Gan, Z., Yang, Z., Wang, S., Wang, J., Boyd-Graber, J., and Wang, L.  Prompting gpt-3 to be reliable.  In _Proc. of ICLR_ , 2023.  URL https://openreview.net/forum?id=98p5x51L5af.
  * Stephen et al. (2017) Stephen, M., Caiming, X., James, B., and Socher, R.  Pointer sentinel mixture models.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_ , 2017\.
  * Su et al. (2022) Su, H., Kasai, J., Wang, Y., Hu, Y., Ostendorf, M., Yih, W.-t., Smith, N. A., Zettlemoyer, L., Yu, T., et al.  One embedder, any task: Instruction-finetuned text embeddings.  _arXiv preprint arXiv:2212.09741_ , 2022.
  * Wu et al. (2021) Wu, S., Zhao, X., Yu, T., Zhang, R., Shen, C., Liu, H., Li, F., Zhu, H., Luo, J., Xu, L., et al.  Yuan 1.0: Large-scale pre-trained language model in zero-shot and few-shot learning.  _arXiv preprint arXiv:2110.04725_ , 2021.
  * Yasunaga et al. (2022) Yasunaga, M., Aghajanyan, A., Shi, W., James, R., Leskovec, J., Liang, P., Lewis, M., Zettlemoyer, L., and Yih, W.-t.  Retrieval-augmented multimodal language modeling.  _arXiv preprint arXiv:2211.12561_ , 2022.
  * Younes Belkda (2022) Younes Belkda, T. D.  A gentle introduction to 8-bit matrix multiplication, 2022.  URL https://huggingface.co/blog/hf-bitsandbytes-integration.
  * Yu (2022) Yu, W.  Retrieval-augmented generation across heterogeneous knowledge.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Student Research Workshop_ , pp. 52–58, Hybrid: Seattle, Washington + Online, July 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.naacl-srw.7.  URL https://aclanthology.org/2022.naacl-srw.7.
  * Yu et al. (2023) Yu, W., Iter, D., Wang, S., Xu, Y., Ju, M., Sanyal, S., Zhu, C., Zeng, M., and Jiang, M.  Generate rather than retrieve: Large language models are strong context generators.  2023\.
  * Zhang et al. (2022a) Zhang, S., Diab, M., and Zettlemoyer, L.  Democratizing access to large-scale language models with opt-175b.  _Meta AI_ , 2022a.
  * Zhang et al. (2022b) Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., et al.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_ , 2022b.
  * Zhong et al. (2022) Zhong, Z., Lei, T., and Chen, D.  Training language models with memory augmentation.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , 2022\.

Knowledge: Arctic Ocean. Although over half of Europe’s original forests
disappeared through the centuries of deforestation, Europe still has over one
quarter of its land area as forest, such as the broadleaf and mixed forests,
taiga of Scandinavia and Russia, mixed rainforests of the Caucasus and the
Cork oak forests in the western Mediterranean. During recent times,
deforestation has been slowed and many trees have been planted. However, in
many cases monoculture plantations of conifers have replaced the original
mixed natural forest, because these grow quicker. The plantations now cover
vast areas of land, but offer poorer habitats for many European
---
Question: As of 2015, since 1990 forests have  in Europe and have  in Africa
and the Americas.
A. "increased, increased" B. "increased, decreased" C. "decreased, increased"
D. "decreased, decreased"
Answer: B
Knowledge: Over the past decades, the political outlook of Americans has
become more progressive, with those below the age of thirty being considerably
more liberal than the overall population. According to recent polls, 56% of
those age 18 to 29 favor gay marriage, 68% state environmental protection to
be as important as job creation, 52% "think immigrants śtrengthen the country
with their hard work and talents,"́ 62% favor a "tax financed, government-
administrated universal health care" program and 74% "say ṕeopleś willśhould
have more influence on U.S. laws than the Bible, compared to 37%, 49%, 38%,
47% and 58% among the
Question: As of 2019, about what percentage of Americans agree that the state
is run for the benefit of all the people?
A. 31% B. 46% C. 61% D. 76%
Answer: B
…
Knowledge: last week at a United Nations climate meeting in Germany, China and
India should easily exceed the targets they set for themselves in the 2015
Paris Agreement… India is now expected to obtain 40 percent of its electricity
from non-fossil fuel sources by 2022, eight years ahead of schedule." Solar
power in Japan has been expanding since the late 1990s. By the end of 2017,
cumulative installed PV capacity reached over 50 GW with nearly 8 GW installed
in the year 2017. The country is a leading manufacturer of solar panels and is
in the top 4 ranking for countries
Question: Which of the following countries generated the most total energy
from solar sources in 2019?
A. China B. United States C. Germany D. Japan
Table 4: Prompt for MMLU Knowledge: received 122,000 buys (excluding WWE
Network views), down from the previous yearś 199,000 buys. The event is named
after the Money In The Bank ladder match, in which multiple wrestlers use
ladders to retrieve a briefcase hanging above the ring. The winner is
guaranteed a match for the WWE World Heavyweight Championship at a time of
their choosing within the next year. On the June 2 episode of "Raw", Alberto
Del Rio qualified for the match by defeating Dolph Ziggler. The following
week, following Daniel Bryan being stripped of his WWE World Championship due
to injury, Stephanie McMahon changed the
---
Question: Who won the mens money in the bank match?
Answer: Braun Strowman
Knowledge: in 3D on March 17, 2017. The first official presentation of the
film took place at Disneyś three-day D23 Expo in August 2015. The world
premiere of "Beauty and the Beast" took place at Spencer House in London,
England on February 23, 2017; and the film later premiered at the El Capitan
Theatre in Hollywood, California, on March 2, 2017. The stream was broadcast
onto YouTube. A sing along version of the film released in over 1,200 US
theaters nationwide on April 7, 2017. The United Kingdom received the same
version on April 21, 2017. The film was re-released in
Question: When does beaty and the beast take place
Answer: Rococo-era
…
Knowledge: Love Yourself "Love Yourself" is a song recorded by Canadian singer
Justin Bieber for his fourth studio album "Purpose" (2015). The song was
released first as a promotional single on November 8, 2015, and later was
released as the albumś third single. It was written by Ed Sheeran, Benny
Blanco and Bieber, and produced by Blanco. An acoustic pop song, "Love
Yourself" features an electric guitar and a brief flurry of trumpets as its
main instrumentation. During the song, Bieber uses a husky tone in the lower
registers. Lyrically, the song is a kiss-off to a narcissistic ex-lover who
did
Question: love yourself by justin bieber is about who
Table 5: Prompt for open-domain QA


Contemplating some invariants of the Jaco Graph, $J_{n}(1),n\in\mathbb{N}$

(Johan Kok, Susanth C)111Affiliation of author(s):
Johan Kok (Tshwane Metropolitan Police Department), City of Tshwane, Republic
of South Africa
e-mail<EMAIL_ADDRESS>

Susanth C (Department of Mathematics, Vidya Academy of Science and
Technology), Thalakkottukara, Thrissur-680501, Republic of India
e-mail<EMAIL_ADDRESS>
###### Abstract

Kok et.al. $[7]$ introduced Jaco Graphs (_order 1_). In this essay we present
a recursive formula to determine the _independence number_
$\alpha(J_{n}(1))=|\mathbb{I}|$ with,
$\mathbb{I}=\\{v_{i,j}|v_{1}=v_{1,1}\in\mathbb{I}$ and
$v_{i}=v_{i,j}=v_{(d^{+}(v_{m,(j-1)})+m+1)}\\}.$ We also prove that for the
Jaco Graph, $J_{n}(1),n\in\mathbb{N}$ with the prime Jaconian vertex $v_{i}$
the chromatic number, $\chi(J_{n}(1))$ is given by:

$\chi(J_{n}(1))\begin{cases}=(n-i)+1,&\text{if and only if the edge
$v_{i}v_{n}$ exists,}\\\ \\\ =n-i,&\text{otherwise.}\end{cases}$

We further our exploration in respect of _domination numbers, bondage numbers_
and declare the concept of the _murtage number_ 222In honour of U.S.R. Murty,
co-author of [2]. of a simple connected graph $G$, denoted $m(G).$ We conclude
by proving that for any Jaco Graph $J_{n}(1),n\in\mathbb{N}$ we have that
$0\leq m(J_{n}(1))\leq 3.$

Keywords: Jaco graph, Hope graph, Independence number, Covering number,
Chromatic number, Domination number, Bondage number, Murtage number,
$d_{om}$-sequence, Compact $\gamma$-set, Murtage partition.

AMS Classification Numbers: 05C07, 05C20, 05C38, 05C75, 05C85

##  1 Introduction

Let $\mu(G)$ be an arbitrary invariant of the simple connected graph $G$. The
_$\mu$ -stability number_ of $G$ is conventionally, the minimum number of
vertices whose removal changes $\mu(G).$ If the removal of the minimum
vertices results in a decrease of the invariant the result is conventionally
denoted, $\mu^{-}(G)$ and if the change is to the contrary the change is
denoted $\mu^{+}(G).$ We note that the _domination number_ ,
$\gamma(G^{\prime}),$ of a subgraph $G^{\prime}$ of $G$ can be larger or
smaller than $\gamma(G).$ Note that a subgraph may result from the removal of
vertices and/or edges from $G$. Furthermore, we note that the removal of edges
only from the graph $G$ to obtain $G^{\prime}$ can only result in
$\gamma(G^{\prime})\geq\gamma(G).$ The minimum number of edges whose removal
from $G$ results in a graph $G^{\prime}$ with $\gamma(G^{\prime})>\gamma(G),$
is called the _bondage number_ $b(G)$, of $G$.

##  2 Some invariants of a Jaco Graph, $J_{n}(1),n\in\mathbb{N}$

The infinite directed Jaco graph (_order 1_) was introduced in $[7],$ and
defined by $V(J_{\infty}(1))=\\{v_{i}|i\in\mathbb{N}\\}$,
$E(J_{\infty}(1))\subseteq\\{(v_{i},v_{j})|i,j\in\mathbb{N},i<j\\}$ and
$(v_{i},v_{j})\in E(J_{\infty}(1))$ if and only if $2i-d^{-}(v_{i})\geq j.$
The graph has four fundamental properties which are;
$V(J_{\infty}(1))=\\{v_{i}|i\in\mathbb{N}\\}$ and, if $v_{j}$ is the head of
an edge (arc) then the tail is always a vertex $v_{i},i<j$ and, if $v_{k},$
for smallest $k\in\mathbb{N}$ is a tail vertex then all vertices
$v_{\ell},k<\ell<j$ are tails of arcs to $v_{j}$ and finally, the degree of
vertex $k$ is $d(v_{k})=k.$ The family of finite directed graphs are those
limited to $n\in\mathbb{N}$ vertices by lobbing off all vertices (and edges
arcing to vertices) $v_{t},t>n.$ Hence, trivially we have $d(v_{i})\leq i$ for
$i\in\mathbb{N}.$

###  2.1 Independence number of a Jaco Graph, $J_{n}(1),n\in\mathbb{N}$

Consider the underlying graph of the finite directed Jaco Graph,
$J_{n}(1),n\in\mathbb{N}.$ Obviously the graph has vertices
$v_{1},v_{2},v_{3},...,v_{n}.$ Because the independence number is defined to
be the number of vertices in a maximum independent set $[1]$, it is optimal to
choose non-adjacent vertices recursively, each of minimum indice. This
observation leads to the next theorem. Observe that $v_{i,j}=v_{i}$ as
calculated on the _j-th step_ of a recursive formula applied to the vertices
of a simple connected graph.

######  Theorem 2.1.

The cardinality of the set $\mathbb{I}=\\{v_{i,j}|v_{1}=v_{1,1}\in\mathbb{I}$
and $v_{i}=v_{i,j}=v_{(d^{+}(v_{m,(j-1)})+m+1)}\\},$ derived from the
underlying graph of the Jaco Graph $J_{n}(1),n\in\mathbb{N}$ is equal to the
independence number, $\alpha(J_{n}(1)).$

###### Proof.

Clearly for $J_{1}(1)$ the cardinality of $\mathbb{I}=\\{v_{1}\\}$ equals 1
and it is indeed the maximum independent set. It is equally easy to see that
the set $\mathbb{I}=\\{v_{1}\\}$ is indeed a maximum independent set of
$J_{2}(1)$ as well. Considering $J_{3}(1)$ the derived maximum independent set
is, $\mathbb{I}=\\{v_{1},v_{3}\\}.$ It easily follows that
$v_{3}=v_{3,2}=v_{(d^{+}(v_{1})+1+1)}=v_{(d^{+}(v_{1,(2-1)})+1+1)}.$ It
follows that this maximum independent set (not unique) remains valid for
$J_{3}(1),J_{4}(1),J_{5}(1).$ Hence, $\alpha(J_{i}(1)=2,$ for $3\leq i\leq 5.$

Assume on the _$\ell$ -th step_ we have the maximum independent set
$\\{v_{1},v_{3},v_{6},...,v_{(d^{+}(v_{m,(\ell-1)})+m+1)}\\}$ in respect of
the Jaco Graphs $J_{i}(1)$ for $k=(d^{+}(v_{m,(\ell-1)})+m+1)\leq i\leq
k+d^{+}(v_{k}).$

Considering the Jaco Graph $J_{(k+d^{+}(v_{k})+1)}(1)$ will yield a maximum
independent set, $\\{v_{1},v_{3},v_{6},...,\\\
v_{(d^{+}(v_{m,(\ell-1)})+m+1)},v_{(k+d^{+}(v_{k})+1)}\\}.$ So the result
holds for the _( $\ell$ \+ 1)-th step_. Through mathematical induction the
result holds in general. ∎

######  Corollary 2.2.

It follows that the _covering number,_ $\beta(J_{n}(1))=n-\alpha(J_{n}(1)).$

###  2.2 Chromatic number of a Jaco Graph, $J_{n}(1),n\in\mathbb{J}$

From the definitions provided in $[7]$ the Hope Graph of the Jaco Graph,
$J_{n}(1)$ is the complete graph on the vertices $v_{i+1},v_{i+2},...,v_{n}$
if and only if $v_{i}$ is the prime Jaconian vertex of $J_{n}(1).$ Hence,
$\mathbb{H}_{n}(1)\simeq K_{n-i}.$ The reader is reminded that a _t-colouring_
of a graph $G$ is a map $\lambda:V(G)\rightarrow[c]:=\\{1,2,3,...,c,c\geq
0\\}$ such that $\lambda(u)\neq\lambda(v)$ whenever $u,v\in V(G)$ are adjacent
in $G$. The _chromatic number_ of $G$ denoted $\chi(G)$ is the minimum $c$
such that $G$ is _c-colourable_. Now the following theorem can be settled.

######  Theorem 2.3.

For the Jaco Graph, $J_{n}(1),n\in\mathbb{N}$ with the prime Jaconian vertex
$v_{i}$ we have that the chromatic number, $\chi(J_{n}(1))$ is given by:

$\chi(J_{n}(1))\begin{cases}=(n-i)+1,&\text{if and only if the edge
$v_{i}v_{n}$ exists,}\\\ \\\ =n-i,&\text{otherwise.}\end{cases}$

###### Proof.

(a(i)) If the edge $v_{i}v_{n}$ exists the largest complete subgraph of
$J_{n}(1)$ is given by $\mathbb{H}_{n}(1)+v_{i}\simeq K_{(n-i)+1}.$ Since it
is known that $\chi(K_{(n-i)+1})=(n-i)+1,$ it follows that
$\chi(J_{n}(1))\geq(n-i)+1.$ For $J_{1}(1)$ we have that the prime Jaconian
vertex is $v_{1}$ and inherently connected to itself. One may imagine the
imaginary edge $"v_{1}v_{1}"$ to find $\chi(J_{1}(1))=(1-1)+1=1$ to be true.
For $J_{2}(1)$ the prime Jaconian vertex is $v_{1}$ and the Hope Graph,
$\mathbb{H}_{2}(1)\simeq K_{1}.$ Also, the edge $v_{1}v_{2}$, exists. Thus,
$\chi(J_{2}(1))=(2-1)+1=2,$ which is true.

Now assume the result holds for any $J_{n}(1),n>2$ for which the edge
$v_{i}v_{n}$ exists and $v_{i}$ is the prime Jaconian vertex. Label the
$(n-i)+1$ colours used to colour the vertices
$v_{i},v_{i+1},v_{i+2},,,,v_{n},$ consecutively,
$c_{i},c_{i+1},c_{i+2},...,c_{n}.$ From definitions 1.3 and 1.4 and Lemma 1.1
$[7]$ it follows that if the prime Jaconian vertex $v_{i}$ is unique, the Jaco
Graph $J_{n+1}(1)$ will be the _smallest_ Jaco Graph _larger_ than $J_{n}(1)$
with prime Jaconian vertex $v_{i+1}$ for which the edge $v_{i+1}v_{n+1}$,
exists. It also implies that $\mathbb{H}_{n+1}(1)\simeq\mathbb{H}_{n}(1).$
Since the edge $v_{i}v_{n+1}$ does not exists, the colouring of $v_{n+1}$ with
$c_{1}$ suffices, whilst the colouring of the rest of the graph $J_{n+1}(1)$
remains the same as that of $J_{n}(1).$ So clearly the result
$\chi(J_{n+1}(1))=((n+1)-(i+1))+1=(n-i)+1=\chi(J_{n}(1))$ holds.

From definitions 1.3 and 1.4 and Lemma 1.1 $[7]$ it follows that if the prime
Jaconian vertex $v_{i}$ of $J_{n}(1)$ is not unique, the Jaco Graph
$J_{n+2}(1)$ will be the _smallest_ Jaco Graph _larger_ than $J_{n}(1)$ with
prime Jaconian vertex $v_{i+1}$ for which both the edge $v_{i+1}v_{n+1}$ and
$v_{i+1}v_{n+2}$, exist (also see the Fisher Table for illustration). Since
the edge $v_{i}v_{n+1}$ does not exist, colour vertices $v_{n+1},v_{n+2}$
respectively $c_{1}$ and $c_{n+1}.$ Since $\mathbb{H}_{n+2}(1)$ has $(n-i)+1$
vertices we must consider the colouring of $K_{(n-i)+2}.$ We however, have
that
$\chi(K_{(n-i)+2})=(n-i)+2=((n-i)+1)+1=((n+1)-i)+1=((n+2)-(i+1))+1=\chi(J_{n+2}(1)).$

Assume that for some Jaco Graph $J_{n}(1)$ with the edge $v_{i}v_{n}$ existing
we have that $\chi(J_{n}(1))>(n-i)+1.$ Clearly this contradicts the definition
on minimality of the colouring set so we safely conclude that
$\chi(J_{n}(1))\ngtr(n-i)+1.$

Since all cases have been considered the necessary condition follows through
mathematical induction.

(a(ii)) Consider the converse statement namely, if $\chi(J_{n}(1))=(n-i)+1$
then the edge $v_{i}v_{n}$ exists and assume it is not true for some Jaco
Graph $J_{n}(1)$ by assuming that the edge $v_{i}v_{n}$ does not exists. The
Hope Graph $\mathbb{H}_{n}(1)\simeq K_{n-i}$ requires $n-i$ colours. Since,
the edge $v_{i}v_{n}$ does not exists, colouring $v_{i}$ the same as $v_{n}$
will suffice. It implies that using $(n-i)+1$ colours contradicts the
definition on minimality of the colouring set. Hence, the sufficient condition
follows thus, the result.

(b)333Reader can formalise the proof as an exercise. The result follows
directly from the proof of result (a) and the definition on minimality of the
colouring set. ∎

###  2.3 Introduction to the murtage number $m(G)$ of a simple connected graph
$G$

Note that if vertices $u$ and $v$ are not adjacent in $G$, then
$\gamma(G+uv)\leq\gamma(G).$ The significance of this concept becomes apparent
in the application of domination theory. In a situation where a $\gamma$-set
of a graph is to represent costly facilities in a network $N$, it may be
preferable to establish additional links (edges) between vertices of $N$
rather than constructing facilities at all vertices of a $\gamma$-set.

In order to calculate the murtage number of a graph we introduce the concept
of a $d_{om}$-_sequence_ of a $\gamma$-set, $X_{i}$ of a graph. Label the
vertices of $X_{i}$ such that $V(G)$ can be partitioned into sets
$D_{1,i},D_{2,i},...,D_{\gamma(G),i}$ such that $D_{j,i}$ contains the vertex
$v_{j}\in X_{i}$ and vertices in $V(G)-X_{i}$ which are adjacent to $v_{j}$
and such that, $|D_{1,i}|\leq|D_{2,i}|\leq...,\leq|D_{\gamma(G),i}|$ and
$|D_{1,i}|$ is a minimum. We define a $d_{om}$-_sequence_ of the $\gamma$-set
$X_{i}$ as $(|D_{1,i}|,|D_{2,i}|,...,|D_{\gamma(G),i}|).$ Clearly a
$\gamma$-set can have more than one $d_{om}$-_sequence_. Assume $G$ has $k$
$\gamma$-sets namely $X_{1},X_{2},...,X_{k}$. Let
$\theta=\emph{absolute}(min|D_{1,j}|)$ for some $X_{j}$. All $\gamma$-sets,
$X_{\ell}$ for which firstly, $|D_{1,\ell}|=\theta$ (_primary condition_) and
secondly, $d(v_{1},v_{i})$ is minimum for all $v_{i}\in X_{\ell}$ (_secondary
condition_) is said to be _compact_ $\gamma$-sets. The partitioning described
above in respect of a compact $\gamma$-set is called a _murtage partition_ of
$V(G).$

As example let us consider the path $P_{4}$ with vertices labelled from _left
to right_ $v_{1},v_{2},v_{3}$ and $v_{4}$. Clearly the $\gamma$-set
$\\{v_{2},v_{3}\\}$ is a $\gamma$-set with the $d_{om}$-sequence = (2,2) and
$d(v_{2},v_{3})=1.$ The aforesaid set is however not a _compact_ $\gamma$-set
because the set $\\{v_{1},v_{3}\\}$ has $d_{om}$-sequence = (1, 3) meaning
_absolute_ $(min|D_{1,i}|)=1<2$ which is primary in the definition. The fact
that $d(v_{1},v_{3})=2>1=d(v_{2},v_{3})$ is secondary in the definition. The
corresponding murtage partition of $V(P_{4}))$ is
$\\{\\{v_{1}\\},\\{v_{2},v_{3},v_{4}\\}\\}.$

Another example will be considering the path $P_{5}$ with the vertices
labelled _left to right_ $v_{1},v_{2},v_{3},v_{4}$ and $v_{5}$. Clearly the
sets $\\{v_{1},v_{4}\\},\\{v_{2},v_{4}\\}$ are $\gamma$-sets. Both have
$d_{om}$-sequence $(2,3)$ with set $\\{v_{2},v_{4}\\}$ providing
$d(v_{2},v_{4})=2$ hence compact, whilst the set $\\{v_{1},v_{4}\\}$ provides
$d(v_{1},v_{4})=3$ hence, non-compact. The murtage partion associated with the
compact $\gamma$-set $\\{v_{2},v_{4}\\}$ is
$\\{\\{v_{1},v_{2}\\},\\{v_{3},v_{4},v_{5}\\}\\}.$

######  Definition 2.1.

We define the murtage number, $m(G)$, of a simple connected graph $G$ to be
the minimum number of edges that has to be added to $G$ such that the
resulting graph $G^{\prime}$ has $\gamma(G^{\prime})<\gamma(G).$

It follows from the definition that $m(G)=0$ if and only if $\gamma(G)=1.$

######  Theorem 2.4.

Let $|D_{1,i}|=\theta$ for some compact $\gamma$-set $X_{i}$ of G, then:

$m(G)\begin{cases}=\theta,&\text{if and only if $v_{1}$ is not adjacent to any
$v_{j}\in X_{i},$}\\\ \\\ =\theta-1,&\text{if and only if $v_{1}$ is adjacent
to some $v_{j}\in X_{i}$.}\end{cases}$

###### Proof.

(a) Assume $v_{1}$ is not adjacent to any $v_{j}\in X_{i}.$ Since we are
considering a $d_{om}$-sequence of a compact $\gamma$-set of $G$, it is clear
that the vertices in $D_{1,i}$ are uniquely dominated by $v_{1}$ hence, we
must join all vertices in $D_{1,i}$ to vertices in $X_{i}-\\{v_{1}\\}$ in
order to eliminate $v_{1}$ from $X_{i}$. Since, $|D_{1,i}|=\theta$ is an
absolute minimum over all minimum number of edges to be added to have a
resulting graph $G^{\prime}$ such that
$\gamma(G^{\prime})=\gamma(G)-1<\gamma(G),$ it follows from the definition
that $m(G)=\theta.$

Conversely we assume that $m(G)=\theta$ and that $v_{1}$ is adjacent to some
$v_{j}\in X_{i}.$ Since we are considering a $d_{om}$-sequence of a compact
$\gamma$-set of $G$, it is clear that the vertices in $D_{1,i}$ are uniquely
dominated by $v_{1}$ hence, we must join all vertices in $D_{1,i}-\\{v_{1}\\}$
to vertices in $X_{i}-\\{v_{1}\\}$ in order to eliminate $v_{1}$ from $X_{i}$.
However, it required only $\theta-1$ edges to be added hence, $m(G)=\theta-1.$
The latter is a contradiction, implying $v_{1}$ is not adjacent to any vertex
$v_{j}\in X_{i}.$

(b) The proof follows in a similar way as part (a). ∎

######  Proposition 2.5.

For any graph $G$ for which $m(G)\geq 1$ we have that $m(G)=\gamma^{-}(G).$

###### Proof.

Since $m(G)\geq 1$ it follows that $\gamma(G)\geq 2.$ Consider any compact
$\gamma$-set $X_{i}$ of $G$. From the definition it follows that
$m(G)=|D_{1,i}|=\theta.$ If $\gamma^{-}(G)=k<\theta$, let $Y\subseteq V(G)$ be
a $\gamma^{-}$-set of $G$ with $|Y|=k.$ Since $\gamma(G-Y)<\gamma(G)$ there
exists at least one vertex $v_{j}\in X_{i}$ such that every vertex of
$G-(Y\cup X_{i})\cup\\{v_{j}\\}$ is joined to a vertex in $X_{i}-\\{v_{j}\\}.$
Join every vertex in $Y$ to a vertex $v_{t}\in X_{i},v_{t}\neq v_{j}$ to
obtain $G^{\prime}$. Clearly $\gamma(G^{\prime})<\gamma(G)$ and it follows
that $m(G)\leq k<\theta$, which is a contradiction.

If $\theta<|Y|=\gamma^{-}(G)$ we consider the graph $G-D_{1,i}$ which has
$\gamma$-set, $X_{i}-\\{v_{1}\\}.$ Since $\gamma(G-D_{1,i})<\gamma(G)$ we have
that $\gamma^{-}(G)\leq\theta<|Y|$ which renders a contradiction.

Hence $m(G)=\gamma^{-}(G).$ ∎

Although the two invariants differ conceptually, the result is very useful. We
only have to investigate one of the invariants and all the results will hold
for the other.

######  Theorem 2.6.

Any simple connected graph $G$ has a spanning subtree $T$ such that:
$\Delta(T)=\Delta(G),\gamma(T)=\gamma(G)$ and $m(T)=m(G).$

###### Proof.

Consider a compact $\gamma$-set,
$X_{i}=\\{v_{1},v_{2},v_{3},...,v_{\gamma(G)}\\}$ of $G$ and an associated
_murtage partitioning_ of $V(G).$ Consider the forest $\cup\langle
D_{j,i}\rangle_{\forall j}$ with $\langle D_{j,i}\rangle$ the star with edges
$\\{v_{j}v_{k}|v_{k}\in D_{j,i}\\}.$

If in $\langle D_{\gamma(G),i}\rangle$ we have $d(v_{\gamma(G)})=\Delta(G)$,
then join all $\langle D_{j,i}\rangle,j=1,2,...,(\gamma(G)-1)$ to $\langle
D_{\gamma(G),i}\rangle$ with one edge $uv$ if and only if $u\in
D_{\gamma(G),i},v\in D_{j,i}$ and $uv\in E(G).$ Label the tree $T^{*}$. If any
of the stars $\langle D_{j,i}\rangle$ has not been joined to $\langle
D_{\gamma(G),i}\rangle$ we join them to $T^{*}$ with one edge $uv$ if and only
if $u\in V(T^{*}),v\in D_{j,i}$ and $uv\in E(G).$ Label this successor tree
$T^{*}.$ Since $G$ is connected it is evident that recursively all stars will
eventually be connected. Clearly $\Delta(T)=\Delta(G).$

If in $\langle D_{\gamma(G),i}\rangle$ we have $d(v_{\gamma(G)})<\Delta(G),$
join all $\langle D_{j,i}\rangle,j=1,2,...,(\gamma(G)-1)$ to $\langle
D_{\gamma(G),i}\rangle$ with one edge $uv_{\gamma(G)}$ if and only if $u\in
D_{j,i}$ and $uv_{\gamma(G)}\in E(G).$ Label the tree $T^{*}$. Note that
$\Delta(T^{*})=\Delta(G).$ All other stars $\langle D_{j,i}\rangle$ which have
not been joined at this first iteration can recursively be joined as described
above. Hence, in all cases a spanning subtree $T$ can be constructed with
$\Delta(T)=\Delta(G).$

To complete the proof we note that $\gamma(G)\leq\gamma(T)$ and the set
$X_{i}$ is a $\gamma$-set of $T$, hence $\gamma(T)=\gamma(G).$ It is also
clear that $X_{i}$ is a compact $\gamma$-set of $T$ hence, $m(T)=m(G).$ ∎

Furthermore, let $\mathbb{G}=\\{G_{1},G_{2},G_{3},...,G_{\ell}\\}$ with each
$G_{i},$ a simple connected graph. It follows easily that
$\gamma(\cup_{\forall i}G_{i})=\sum_{\forall i}\gamma(G_{i})$ and similarly,
$m(\cup_{\forall i}G_{i})=\sum_{\forall i}m(G_{i}).$ Also if
$\gamma(G_{i})\leq\gamma(H_{i}),i=1,2,3,...,n$ then $\gamma(\cup_{\forall
i}G_{i})=\sum_{\forall i}\gamma(G_{i})\leq\sum_{\forall
i}\gamma(H_{i})=\gamma(\cup_{\forall i}H_{i}).$

###  2.4 Murtage number of a Jaco Graph, $J_{n}(1),n\in\mathbb{N}$

In this subsection, reference to a Jaco Graph will mean we consider the
undirected underlying graph of the Jaco Graph. Hence we _peel off_ the
orientation of the Jaco Graph. From the definition of a Jaco Graph it follows
that all Jaco Graphs on $n\geq 2$ has at least one leaf (vertex with degree =
1). Hence, the _bondage number_ is $b(J_{n}(1))_{n\geq 2}=1.$

The fact that $m(J_{n}(1))_{n\in\mathbb{N}}\geq 0$ follows from the
definition.

From the definition of a Jaco Graph it follows easily that vertex $v_{1}$
dominates $J_{1}(1)$ and $J_{2}(1)$ and vertex $v_{2}$ dominates $J_{3}(1)$
hence, $m(J_{1}(1))=m(J_{2}(1))=m(J_{3}(1))=0.$

For $J_{4}(1)$ and $J_{5}(1)$ it follows that the set $\\{v_{1},v_{3}\\}$ is a
compact $\gamma$-set with the $d_{om}$-_sequences_ , $(1,2)$ and $(1,3)$
hence, $m(J_{4}(1))=m(J_{5}(1))=1.$

For the Jaco Graphs $J_{6}(1)$ and $J_{7}(1)$ we have sets
$\\{v_{1},v_{4}\\},\\{v_{1},v_{5}\\},\\{v_{2},v_{4}\\},\\{v_{2},v_{5}\\},\\{v_{2},v_{6}\\},\\\
\\{v_{2},v_{7}\\}$ being $\gamma$-sets with only $\\{v_{2},v_{4}\\}$ and
$\\{v_{2},v_{5}\\}$ the compact $\gamma$-sets. The corresponding
$d_{om}$-_sequences_ are $(2,4)$ and $(2,5)$ hence,
$m(J_{6}(1))=m(J_{7}(1))=2.$ For $J_{8}(1)$ we have that the sets
$\\{v_{2},v_{5}\\},\\{v_{2},v_{6}\\},\\{v_{2},v_{7}\\}$ are $\gamma$-sets with
$\\{v_{2},v_{5}\\}$ the unique compact $\gamma$-set. The unique corresponding
$d_{om}$-_sequence_ is (2, 6) so, $m(J_{8}(1))=2.$

In respect of $J_{9}(1)$ and $J_{10}(1)$ we make the interesting observation
that exactly two $\gamma$-sets, both being compact $\gamma$-sets namely,
$\\{v_{2},v_{6}\\}$ and $\\{v_{2},v_{7}\\}$, exist. The corresponding
$d_{om}$-_sequences_ are (3, 6) and (3, 7) respectively, meaning,
$m(J_{9}(1))=m(J_{10}(1))=3$.

In the case of $J_{11}(1)$ an unique compact $\gamma$-set =
$\\{v_{2},v_{7}\\}$ exists with the $d_{om}$-sequence (3, 8). So also here we
have $m(J_{11}(1))=3.$

For $J_{12}(1)$ and $J_{13}(1)$ we note that the sets
$\\{v_{1},v_{3},v_{8}\\},\\{v_{1},v_{3},v_{9}\\}$ and
$\\{v_{1},v_{3},v_{10}\\}$ are the $\gamma$-sets with
$\\{v_{1},v_{3},v_{8}\\}$ the unique compact $\gamma$-set. The corresponding
$d_{om}$-sequences are (1, 3, 8) and (1, 3, 9). Hence,
$m(J_{12}(1))=m(J_{13}(1))=1.$ Further exploratory analysis leads to the next
theorem.

######  Theorem 2.7.

For any Jaco Graph $J_{n}(1),n\in\mathbb{N}$ we have $0\leq m(J_{n}(1))\leq
3.$ The bounds are obviously sharp as well.

###### Proof.

Following from the definition of a finite Jaco Graph
$J_{n}(1),n\in\mathbb{N}$, it follows easily that the _murtage number_ can
always be found be linking the minimum number of minimum (_smallest_) indiced
vertices labelled $v_{i},i\in\\{1,2,3,.....,k\\}_{k<n}$ to some $v_{j}\in$
compact $\gamma$-set of $J_{n}(1).$

Assume $m(J_{n}(1))\geq 4.$ It implies that at least the vertices
$v_{1},v_{2},v_{3},v_{4}$ have to be linked to some vertex
$v_{j}\in\gamma$-set, in order to reduce the value of $m(J_{n}(1))$ with at
least 1. It also implies that $v_{1},v_{2},v_{3},v_{4}\notin$ compact
$\gamma$-set else $m(J_{n}(1))\leq 3.$ Furthermore, the lowest indiced vertex
$v_{\ell}\in$ compact $\gamma$-set is $4<\ell=8.$ However, the lowest indiced
vertex dominated by $v_{8}$ is $v_{5}$ implying that vertices
$v_{1},v_{2},v_{3},v_{4}$ were not dominated, hence not adjacent to any vertex
in the compact $\gamma$-set under consideration. The latter is a contradiction
in terms of the definition of a $\gamma$-set (therefore, compact
$\gamma$-set). So the result follows. ∎

######  Corollary 2.8.

For any finite Jaco Graph $J_{n}(1),n\in\mathbb{N}$ we have that:
$\gamma(J_{n}(1))=\gamma(J_{(n-d^{-}(v_{n})-d^{-}(v_{(n-d^{-}(v_{n})})-1)}(1))+1.$

###### Proof.

Consider the Jaco Graph $J_{n}(1)$ and let vertex $v_{\ell}$ be the minimum
indiced vertex with the edge $v_{\ell}v_{n}\in E(J_{n}(1)).$ Clearly all
vertices $v_{k\neq\ell}\in\\{v_{\ell-d^{-}(v_{\ell})},...,v_{n}\\}$ are
adjacent to $v_{\ell}$. Reducing by one more vertex we consider the Jaco Graph
$J_{(n-d^{-}(v_{n})-d^{-}(v_{(n-d^{-}(v_{n})})-1)}(1).$ Hence if $X_{i}$ is a
compact $\gamma$-set of
$J_{(n-d^{-}(v_{n})-d^{-}(v_{(n-d^{-}(v_{n})})-1)}(1),$ a compact $\gamma$-set
of $J_{n}(1)$ is given by $X_{i}\cup\\{v_{\ell}\\}.$

It concludes the result that
$\gamma(J_{n}(1))=\gamma(J_{(n-d^{-}(v_{n})-d^{-}(v_{(n-d^{-}(v_{n})})-1)}(1))+1.$
∎

_Open access: 444To be submitted to the _Pioneer Journal of Mathematics and
Mathematical Sciences.__ This paper is distributed under the terms of the
Creative Commons Attribution License which permits any use, distribution and
reproduction in any medium, provided the original author(s) and the source are
credited.

References (Limited)

$[1]$ Bauer, D., Harary, F., Nieminen, J., Suffel, C., _Domination alteration
sets in graphs_ , Discrete Mathematics, Vol 47 (1983), pp 153-161.
$[2]$ Bondy, J.A., Murty, U.S.R., _Graph Theory with Applications,_ Macmillan
Press, London, (1976).
$[3]$ Dutton, R.D., Brigham, R.C., _An extremal problem for edge domination
insensitive graphs_ , Discrete Applied Mathematics, Vol 20 (1988), no.2, pp
113-125.
$[4]$ Haynes, T.W., Henning, M.A., _Changing and unchanging domination: a
classification_ , Discrete Mathematics, Vol 272 (2003), pp 65-79.
$[5]$ Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., _Domination and
independence subdivision numbers of graphs_ , Discussioness Mathematicae Graph
Theory, Vol 20 (2001), pp 271-280.
$[6]$ Kalayathankal, S.J., Susanth, C., _The Sum and Product of Chromatic
Numbers of Graphs and their Line Graphs_ , arXiv: 1404.1698v1 [math.CO], 7
April 2014.
$[7]$ Kok, J., Fisher, P., Wilkens, B., Mabula, M., Mukungunugwa, V.,
_Characteristics of Finite Jaco Graphs, $J_{n}(1),n\in\mathbb{N}$_, arXiv:
1404.0484v1 [math.CO], 2 April 2014.
$[8]$ Kok, J., Fisher, P., Wilkens, B., Mabula, M., Mukungunugwa, V.,
_Characteristics of Jaco Graphs, $J_{\infty}(a),a\in\mathbb{N}$_, arXiv:
1404.1714v1 [math.CO], 7 April 2014.
$[9]$ Teschner, U., _The bondage number of a graph_ , Discrete Mathematics,
Vol 171 (1997), pp 249-259.