# Large Language Models Struggle to Learn Long-Tail Knowledge

Nikhil Kandpal  Haikang Deng  Adam Roberts  Eric Wallace  Colin Raffel

###### Abstract

The Internet contains a wealth of knowledge—from the birthdays of historical
figures to tutorials on how to code—all of which may be learned by language
models. However, while certain pieces of information are ubiquitous on the
web, others appear extremely rarely. In this paper, we study the relationship
between the knowledge memorized by large language models and the information
in pre-training datasets scraped from the web. In particular, we show that a
language model’s ability to answer a fact-based question relates to how many
documents associated with that question were seen during pre-training. We
identify these relevant documents by entity linking pre-training datasets and
counting documents that contain the same entities as a given question-answer
pair. Our results demonstrate strong correlational and causal relationships
between accuracy and relevant document count for numerous question answering
datasets (e.g., TriviaQA), pre-training corpora (e.g., ROOTS), and model sizes
(e.g., 176B parameters). Moreover, while larger models are better at learning
long-tail knowledge, we estimate that today’s models must be scaled by many
orders of magnitude to reach competitive QA performance on questions with
little support in the pre-training data. Finally, we show that retrieval-
augmentation can reduce the dependence on relevant pre-training information,
presenting a promising approach for capturing the long-tail.

Language Models, NLP, Stealing, Security

##  1 Introduction

Figure 1: Language models struggle to capture the long-tail of information on
the web. Above, we plot accuracy for the BLOOM model family on TriviaQA as a
function of how many documents in the model’s pre-training data are relevant
to each question.

Large language models (LLMs) trained on text from the Internet capture many
facts about the world, ranging from well-known factoids to esoteric domain-
specific information. These models implicitly store knowledge in their
parameters (Petroni et al., 2019; Roberts et al., 2020), and given the scale
of today’s pre-training datasets and LLMs, one would hope that they can learn
a huge amount of information from web-sourced text. However, not all of the
knowledge on the Internet appears equally often—there is a long-tail of
information that appears rarely or only once.

Figure 2: In our document counting pipeline, we first run entity linking on
large pre-training datasets (top left) and store the set of the document
indices in which each entity appears (top right). We then entity link
downstream QA pairs and extract the salient question and answer entities
(bottom). Finally, for each question we count the number of documents in which
the question and answer entities co-occur.

In this work, we explore the relationship between the knowledge learned by an
LLM and the information in its pre-training dataset. Specifically, we study
how an LLM’s ability to answer a question relates to how many documents
associated with that question were seen during pre-training. We focus on
factoid QA datasets (Joshi et al., 2017; Kwiatkowski et al., 2019), which lets
us ground question-answer pairs into concrete subject-object co-occurrences.
As an example, for the QA pair (In what city was the poet Dante born?,
Florence), we consider documents where the entities Dante and Florence co-
occur as highly relevant. To identify these entity co-occurrences we apply a
highly-parallelized entity linking pipeline to trillions of tokens from
datasets such as C4 (Raffel et al., 2020), The Pile (Gao et al., 2020), ROOTS
(Laurençon et al., 2022), OpenWebText (Gokaslan & Cohen, 2019), and Wikipedia.

We observe a strong correlation between an LM’s ability to answer a question
and the number of pre-training documents relevant to that question for
numerous QA datasets, pre-training datasets, and model sizes (e.g., Figure 1).
For example, the accuracy of BLOOM-176B (Scao et al., 2022) jumps from 25% to
above 55% when the number of relevant pre-training documents increases from
$10^{1}$ to $10^{4}$.

We also conduct a counterfactual re-training experiment, where we train a
4.8B-parameter LM with and without certain documents. Model accuracy drops
significantly on questions whose relevant documents were removed, which
validates our entity linking pipeline and shows that the observed
correlational trends are likely causal in nature.

Finally, we analyze ways to better capture knowledge that rarely appears in
the pre-training data: model scaling and retrieval-augmentation. For model
scaling, we find a strong log-linear relationship between parameter count and
QA accuracy. These trends show that while scaling up LMs improves knowledge
learning, models would need to be scaled dramatically (e.g., to one
quadrillion parameters) to achieve competitive QA accuracy on long-tail
questions. Retrieval-augmented systems are more promising—when a retriever
succeeds in finding a relevant document, it reduces an LLM’s need to have a
large amount of relevant pre-training text. Nevertheless, retrieval systems
themselves still exhibit a mild dependence on relevant document count.

Overall, our work is one of the first to study how LLM knowledge is influenced
by pre-training data. To enable future research, we release our code as well
as the entity data for ROOTS, The Pile, C4, OpenWebText, and Wikipedia at
https://github.com/nkandpa2/long_tail_knowledge.

##  2 Identifying Relevant Pre-training Data

#### Background and Research Question

Numerous NLP tasks are knowledge-intensive: they require recalling and
synthesizing facts from a knowledge source (e.g. Wikipedia or the web).
Results on knowledge-intensive tasks have been dramatically improved using
LLMs, as these models have been shown to leverage the vast amounts of
knowledge they learn from their pre-training corpora (Roberts et al., 2020;
Petroni et al., 2019; De Cao et al., 2021). However, it remains unclear as to
what kind of knowledge LMs actually capture—for example, do they simply learn
“easy” facts that frequently appear in their pre-training data?

We study this question using closed-book QA evaluations (Roberts et al., 2020)
of LLMs in the few-shot setting (Brown et al., 2020). Models are prompted with
in-context training examples (QA pairs) and a test question without any
relevant background text. The goal of our work is to investigate the
relationship between an LM’s ability to answer a question and the number of
times information relevant to that question appears in the pre-training data.

#### Our Approach

The key challenge is to efficiently identify all of the documents that are
relevant to a particular QA pair in pre-training datasets that are hundreds of
gigabytes in size. To tackle this, we begin by identifying the salient
entities that are contained in a question and its set of ground-truth answer
aliases. We then identify relevant pre-training documents by searching for
instances where the salient question entity and the answer entity co-occur.

For example, consider the question In what city was the poet Dante born? with
the valid answers Florence, City of Florence, and Italy (e.g., Figure 2). We
extract the salient question and answer entities, Dante_Alighieri and
Florence, and count the documents that contain both entities.

Our approach is motivated by Elsahar et al. (2018), who show that when only
the subject and object of a subject-object-relation triple co-occur in text,
the resulting triple is often also present. In addition, we conduct human
studies that show our document counting pipeline selects relevant documents a
majority of the time (Section 2.3). Moreover, we further validate our pipeline
by training an LM without certain relevant documents and showing that this
reduces accuracy on the associated questions (Section 3.2). Based on these
findings, we refer to documents that contain the salient question and answer
entities as relevant documents.

To apply the above method, we must entity link massive pre-training corpora,
as well as downstream QA datasets. We accomplish this by building a
parallelized pipeline for entity linking (Section 2.1), which we then
customize for downstream QA datasets (Section 2.2).

###  2.1 Entity Linking Pre-training Data

We perform entity linking at scale using a massively distributed run of the
DBpedia Spotlight Entity Linker (Mendes et al., 2011), which uses traditional
entity linking methods to link entities to DBpedia or Wikidata IDs. We entity
link the following pre-training datasets, which were chosen based on their use
in the LLMs we consider:

  * •

The Pile: an 825GB dataset that contains a mix of 22 different primarily
English-language sources (Gao et al., 2020).

  * •

ROOTS (En): the 490GB English subset of the ROOTS corpus (Laurençon et al.,
2022). Note that we do not study if models trained on the non-English subsets
of ROOTS are able to leverage cross-lingual factual knowledge.

  * •

C4: a 305GB English corpus that was collected by filtering CommonCrawl (Raffel
et al., 2020).

  * •

OpenWebText: a 39GB English corpus that contains the text of web pages that
were linked on the website Reddit (Gokaslan & Cohen, 2019).

  * •

Wikipedia: a text dump of December 2018 Wikipedia articles from Lee et al.
(2019), a standard corpus for evaluating open-domain QA systems (e.g.
Karpukhin et al. 2020; Lewis et al. 2020; Guu et al. 2020).

For each document in these pre-training datasets, we record the linked
entities in a data structure that enables quickly counting individual entity
occurrences and entity co-occurrences. This pipeline took approximately 3
weeks to entity link 2.1TB of data on a 128-CPU-core machine.

###  2.2 Finding Entity Pairs in QA Data

We next entity link two standard open-domain QA datasets: Natural Questions
(Kwiatkowski et al., 2019) and TriviaQA (Joshi et al., 2017). To expand our
sample sizes, we use both the training and validation data, except for a small
set of examples used for few-shot learning prompts.

We first run the DBPedia entity linker on each example. Because there can be
multiple annotated answers for a single example, we concatenate the question
and all valid answers, as this enabled more accurate entity linking. We use
the most common entity found in the set of ground truth answers as the salient
answer entity. We then iterate over all entities found in the question and
select the entity that co-occurs the most with the salient answer entity in
the pre-training data. In cases where no entity is found in the question,
answer, or both, we discard the example. If the resulting number of relevant
documents is zero, we discard the example, as this is likely due to an entity
linking error.

###  2.3 Human Evaluation of Document Counting Pipeline

Here, we conduct a human evaluation of our document identification pipeline.
Note that a document can vary in the extent to which it is “relevant” to a
particular QA pair. For instance, consider the QA pair (William Van Allan
designed which New York building—the tallest brick building in the world in
1930?, Chrysler Building). The documents that we identify as relevant may (1)
contain enough information to correctly answer the question, (2) contain
information relevant to the question but not enough to correctly answer it, or
(3) contain no relevant information. For example, a document that mentions
that the Chrysler building was designed by William Van Allan, but not that it
was the tallest brick building in 1930, would fall into the second category.

We randomly sample 300 QA pairs from TriviaQA and selected one of their
relevant documents at random. We then manually labeled the documents into one
of the three categories: 33% of documents contained enough information to
answer the question and an additional 27% of contained some relevant
information. Thus, our pipeline has $\sim$60% precision at identifying
relevant documents for TriviaQA.

Our pipeline is imperfect as (1) the entity linker sometimes mis-identifies
entities and (2) not all documents containing the salient question and answer
entity are relevant. However, when applied at the scale of large-scale pre-
training datasets, this pipeline is efficient and achieves enough precision
and recall to observe correlational (Section 3.1) and causal (Section 3.2)
relationships to QA performance.

##  3 LM Accuracy Depends on Relevant Document Count

Figure 3: We plot accuracy on TriviaQA versus relevant document count for GPT-
Neo. The trends match those seen for BLOOM (Figure 1). We also include a
histogram that shows how many QA examples fall into each bucket; TriviaQA
often asks about knowledge represented $10^{2}$ to $10^{5}$ times in the pre-
training data. Figure 4: We plot accuracy on Natural Questions versus relevant
document count for GPT-Neo. The trends match those in TriviaQA—model accuracy
is highly dependent on fact count.

In this section, we measure the relationship between an LLM’s ability to
answer a question and the number of relevant documents in the pre-training
corpus. We use popular Transformer decoder-only LMs (Vaswani et al., 2017)
that span three orders of magnitude in size:

  * •

GPT-Neo: The GPT-Neo, GPT-NeoX, and GPT-J LMs trained by EleutherAI on the
Pile (Gao et al., 2020) that range in size from 125M to 20B parameters (Black
et al., 2021; Wang & Komatsuzaki, 2021; Black et al., 2022). We refer to these
models collectively as GPT-Neo models.

  * •

BLOOM: Models trained by the BigScience initiative on the ROOTS dataset (Scao
et al., 2022). The BLOOM models are multi-lingual; we analyze their English
performance only. The models range in size from 560M to 176B parameters.

  * •

GPT-3: Models trained by OpenAI that range in size from $\approx$350M (Ada) to
$\approx$175B parameters (Davinci). Since the pre-training data for these
models is not public, we estimate relevant document counts by scaling up the
counts from OpenWebText to simulate if the dataset was the same size as
GPT-3’s pre-training data. We recognize that there is uncertainty around these
models’ pre-training data, their exact sizes, and whether they have been fine-
tuned. We therefore report these results in the Appendix for readers to
interpret with these sources of error in mind.

We use these LMs because (with the exception of GPT-3) they are the largest
open-source models for which the pre-training data is publicly available. We
focus on 4-shot evaluation, although we found that other amounts of in-context
training examples produced similar trends. We use simple prompts consisting of
templates of the form

Q: [In-Context Question 1] A: [In-Context Answer 1] $\displaystyle\hskip
55.00008pt\vdots$ Q: [In-Context Question $n$] A: [In-Context Answer $n$] Q:
[Test Question]

We generate answers by greedy decoding until the models generate a newline
character, and we evaluate answers using the standard Exatch Match (EM) metric
against the ground-truth answer set (Rajpurkar et al., 2016).

###  3.1 Correlational Analysis

We first evaluate the BLOOM and GPT-Neo model families on TriviaQA and plot
their QA accuracies versus the number of relevant documents in Figures 1 and
3. For improved readability, we average the accuracy for QA pairs using log-
spaced bins (e.g., the accuracy for all questions with 1 to 10 relevant
documents, 10 to 100 relevant documents, etc.). Below each plot, we also
include a histogram that shows how many QA examples fall into each bin. We
trim the plots when the bins contain fewer than 500 QA examples to avoid
reporting accuracies for small sample sizes.

There is a strong correlation between question answering accuracy and relevant
document count for all tested models. Correspondingly, when the number of
relevant documents is low, models are quite inaccurate, e.g., the accuracy of
BLOOM-176B jumps from 25% to above 55% when the number relevant documents
increases from $10^{1}$ to $10^{4}$. Model size is also a major factor in
knowledge learning: as the number of model parameters is increased, the QA
performance substantially improves. For example, BLOOM-176B has over 4$\times$
higher accuracy than BLOOM-560M on TriviaQA questions with more than $10^{5}$
relevant documents.

Figure 5: We run a counterfactual experiment, where we re-train an LM without
certain documents. We take TriviaQA questions with different document counts
and delete all of their relevant pre-training documents. The difference in
accuracy between the original model and the re-trained LM (counterfactual) is
high when the original number of relevant documents is large.

We repeat this experiment using the Natural Questions QA dataset and find
similar trends for all model families (see Figure 4 for GPT-Neo, and Figures
10 and 11 in the Appendix for BLOOM and GPT-3 results).

#### Simpler Methods for Identifying Relevant Documents Are Less Effective

In the experiments above, we identify relevant documents by searching for co-
occurrences of salient question and answer entities. To evaluate whether this
process is necessary, we compare against two baseline document identification
methods: counting documents that contain the salient question entity and
counting documents that contain the salient answer entity (as done in Petroni
et al. 2019).

We show in Figure 13 that all three document identification methods are
correlated with QA accuracy. However, when only considering QA examples where
the question and answer entities co-occur few ($<5$) times, the two baseline
methods no longer correlate with QA accuracy. This indicates that counting
documents with just the answer entity or question entity alone is insufficient
for explaining why LMs are able to answer certain questions. This validates
our definition of relevant documents as those that contain both the question
entity and answer entity.

#### Humans Show Different Trends Than LMs

An alternate explanation for our results is that questions with lower document
counts are simply “harder”, which causes the drop in model performance. We
show that this is not the case by measuring human accuracy on Natural
Questions. We use a leave-one-annotator-out metric, where we take questions
that are labeled by 5 different human raters (all of whom can see the
necessary background text), hold out one of the raters, and use the other four
as the ground-truth answer set. We plot the human accuracy versus relevant
document count in the top of Figure 7. Human accuracy is actually highest for
the questions with few relevant documents, the opposite trend of models. We
hypothesize that humans are better on questions with few relevant documents
because (1) questions about rarer facts are more likely to be simple factoids
compared to common entities, and (2) the Wikipedia documents are that are
provided to the annotators are shorter for rarer entities, which makes reading
comprehension easier and increases inner-annotator agreement.

###  3.2 Causal Analysis via Re-training

Our results thus far are correlational in nature: there may be unknown
confounds that explain them away, i.e., the rarer questions are more difficult
for LMs for other reasons. Here we establish a causal relationship by removing
certain documents in the training data and re-training the LM.

We first train a baseline 4.8 billion parameter LM on C4, following the setup
from Wang et al. (2022). We then measure the effect of deleting certain
documents from the training set. For each log-scaled bin of relevant document
count (e.g., $10^{0}$ to $10^{1}$ relevant documents, $10^{1}$ to $10^{2}$, …)
we sample 100 questions from Trivia QA and remove all relevant documents for
those questions in C4. In total, this removes about 30% of C4. Finally, we
train a “counterfactual” LM on this modified pre-training dataset and compare
its performance to the baseline model. For both the baseline model and the
counterfactual model, we train for a single epoch. Note that the
counterfactual model was trained for 30% fewer steps, which makes it slightly
worse in performance overall. To account for this, we only study the
performance on questions whose relevant documents were removed.

We show the difference in performance between the two LMs on questions whose
documents were removed in Figure 5. For questions with few relevant documents
in the original C4 dataset, performance is poor for both the baseline and the
counterfactual LM, i.e., their performance difference is small. However, for
questions with many relevant documents, performance is significantly worse for
the counterfactual LM. This suggests a causal link between the number of
relevant documents and QA performance.

Figure 6: _Scaling trends for fact learning_. We plot BLOOM accuracy on rare
instances from Natural Questions ($<100$ relevant docs) as a function of the
log of the model size. Extrapolating from the empirical line of best fit—which
approximates the trend well at $R^{2}=0.98$—implies that immensely large
models would be necessary to get high accuracy.

##  4 Methods to Improve Rare Fact Learning

Thus far, we showed that LLMs have a strong dependence on relevant document
count. Here, we investigate methods to mitigate this dependence: increasing
data scale, increasing model scale, and adding an auxiliary retrieval module.

###  4.1 Can We Scale Up Datasets?

Today’s largest LLMs are pre-trained on hundreds of billions of tokens. One
naïve approach for improving accuracy on questions about less-prevalent
knowledge is to collect larger quantities of data. Our results suggest that
this would not significantly improve accuracy as scaling datasets by moderate
factors (e.g., 5x) usually results in small accuracy gains. An alternative
idea would be to increase the diversity of the pre-training data. However, we
also believe this would provide minimal benefit because many data sources are
surprisingly correlated . Although each of the pre-training datasets
considered were collected independently, the amount of supporting information
they provide for different TriviaQA examples is highly consistent as seen by
the rank correlations between their relevant document counts in Table 1.

| ROOTS | Pile | C4 | OWT | Wiki
---|---|---|---|---|---
ROOTS | - | 0.97 | 0.97 | 0.94 | 0.87
Pile | - | - | 0.95 | 0.96 | 0.87
C4 | - | - | - | 0.96 | 0.90
OWT | - | - | - | - | 0.91
Wiki | - | - | - | - | -
Table 1: Spearman rank correlations of the relevant document counts for
TriviaQA examples in The Pile, ROOTS, C4, OpenWebText, and Wikipedia. Despite
having different collection methodologies, these pre-training datasets are
highly correlated in terms of how much information they contain related to
different QA pairs.

###  4.2 Can We Scale Up Models?

Using larger models consistently produces better QA performance. However, our
results suggest that one would need immensely large LMs to achieve high
accuracy on long-tail questions. In Figure 6 we plot a scaling trend line for
rare fact learning, where we show BLOOM accuracy on rare instances from
Natural Questions ($<100$ relevant docs) as a function of the log of the model
size. The empirical log-linear trend—which approximates the scaling extremely
well ($R^{2}=0.98$)—shows that in order to match a strong supervised baseline
(Izacard & Grave, 2021) or human performance, one would need a BLOOM model
with over $10^{18}$ (one quintillion) parameters.111For this experiment, the
supervised and human accuracies are computed over the validation set whereas
the scaling trend is computed using the train and validation sets. We see
similar trends for other models and datasets (see Figure 12 in the Appendix).

#### Modifying the Training Objective

Another option similar to scaling up models is to directly modify the training
objective to encourage memorization. One simple method to accomplish this is
to increase the number of training epochs. All of the LMs that we study do
limited epochs, as it is generally seen as preferable to use large enough pre-
training datasets so that the LM completes one epoch of training when the
compute budget is exhausted (Raffel et al., 2020). However, in the context of
QA, it may be preferable to increase epochs and reduce data size to ensure
models memorize as much as possible. Alternatively, one could consider
modifying the training loss to encourage the model to focus on salient facts
(Guu et al., 2020) or designing a curriculum to minimize forgetting (Jagielski
et al., 2023).

Figure 7: Models with access to the required background context do not
struggle on questions with low relevant document count. Concretely, we provide
questions and gold paragraphs to GPT-Neo models on Natural Questions, and
their accuracy trends roughly match the trends of humans.

Figure 8: Retrieval systems such as BM25 have a mild dependence on document
count. Above we plot the top-$k$ recall for BM25 on Natural Questions for
different values of $k$.

Figure 9: Retrieval-augmented LMs no longer exhibit low accuracy on rare
instances. We plot GPT-Neo accuracy on Natural Questions when augmented with
three paragraphs from BM25.

###  4.3 Can We Use Retrieval Augmentation?

Thus far, we use LMs as isolated systems that do not leverage external
information. However, for knowledge-intensive tasks, a natural alternative is
to make LMs _retrieval-augmented_ , i.e., combine them with a retrieval module
that returns relevant textual contexts (Lewis et al., 2020; Guu et al., 2020;
Karpukhin et al., 2020). Here, we study whether retrieval-augmented models can
mitigate the dependence on the amount of relevant knowledge in the pre-
training data.

#### Oracle Retrieval

We first study an oracle setting where we provide LMs with a gold paragraph
from Wikipedia that supports each answer in Natural Questions (Petroni et al.,
2020). We use the 300-word segment that surrounds the ground-truth answer from
the gold Wikipedia page and evaluate the 2-shot accuracy of GPT-Neo. Figure 7
shows that oracle retrieval-augmentation dramatically boosts accuracy over
closed-book models, especially on rarer instances. Similar to Liu et al.
(2022), we also find that QA accuracy actually goes _down_ as the number of
relevant documents increases—the opposite trend of closed-book LLMs. As
discussed in Section 3.1, humans exhibit the same trend, likely because rare
questions are easier on average when relevant context information.

#### BM25 Retrieval

We next follow a common retrieval-augmented baseline, where we use a BM25
retriever (Robertson & Zaragoza, 2009) to select paragraphs from Wikipedia. We
add the top-3 highest scoring paragraphs into the prompt for both the in-
context training examples and the test question. We verify that at least one
of the retrieved paragraphs contains the answer for each in-context training
example, to ensure that the LM learns to utilize on the documents.

We first evaluate the BM25 retriever’s top-$k$ recall on its knowledge corpus
(Wikipedia) as a function of relevant document count, and plot the results in
Figure 9. We find that BM25 attains reasonably high recall, especially for
larger values of $k$. However, the BM25 retriever still shows a mild
dependence on relevant document count. We next evaluate the accuracy of
BM25-augmented GPT-Neo models on Natural Questions and plot the results in
Figure 9. Overall, retrieval-augmented models outperform their closed-book
counterparts across all ranges of relevant document counts, and especially on
rare examples. These results suggest that retrieval augmentation provides a
promising path towards improving performance on questions with few relevant
documents in the pre-training dataset.

##  5 Related Work

#### Identifying The Origins of Few-shot Learning

Our work contributes to an emerging line of research that explains the success
of zero- and few-shot learning in language models by tracing their behavior
back to the pre-training data. For example, Razeghi et al. (2022) show
mathematical reasoning capabilities can be correlated with training data
frequency, and Shin et al. (2022) and Han & Tsvetkov (2022) show that training
corpus source can influence few-shot accuracies.

The most similar work to ours in this context is Elazar et al. (2022), who use
causal inference to measure the effect of pre-training data statistics on QA
performance. Their main focus is testing the extent to which LMs answer
questions using heuristics based on co-occurrences between subjects, objects,
and textual patterns in the pre-training data. Our main focus is to measure
the relationship between the knowledge learned by an LLM and the prevalence of
that knowledge in the pre-training data. Moreover, we also conduct re-training
experiments and study how model scaling and retrieval-augmentation affect
knowledge learning.

#### Memorization and Privacy

Past work studies training data memorization from the perspective of privacy,
i.e., how LMs inadvertently reveal private text (Carlini et al., 2019, 2021;
Lee et al., 2021). These works focus on how LMs memorize and repeat verbatim
text samples, and the effect of duplicating those texts in the training set
(Kandpal et al., 2022). Doing so has various limitations, as memorization can
be harmful or beneficial even in non-verbatim cases (Ippolito et al., 2022).
Our work takes studies non-verbatim memorization in the context of QA—our LMs
memorize facts in text form and then answers questions about those facts at
test time.

#### Memorization and Fact Learning

Existing work also analyzes the relationship between the pre-training data and
the factual knowledge of LLMs. Akyürek et al. (2022) look to automatically
identify which documents were most influential for a language model’s QA
predictions. Our work instead directly identifies and estimates the number of
relevant documents via entity linking large corpora. Other work notices a
correspondence between model accuracy and data frequency for different
knowledge-intensive tasks (Petroni et al., 2019; Kassner et al., 2020; De Cao
et al., 2021; Wei et al., 2021; Févry et al., 2020) and for domains outside of
NLP (Rao et al., 2021). Our paper reports similar findings, but scales this
analysis to massive LM pre-training datasets and model sizes.

In concurrent and independent work, Mallen et al. (2022) study how QA
performance correlates with frequency in the pre-training data. Unlike our
work, they do not use entity linking methods to count occurrences and instead
use proxies such as entity popularity on Wikipedia. They also find QA accuracy
is highly correlated with pre-training data frequency and show that retrieval
models can improve long-tail knowledge. Our work differs in that we conduct
causal re-training experiments and find that model scaling is highly
beneficial to long-tail QA performance.

##  6 Conclusion and Future Work

Large language models demonstrate impressive few-shot learning capabilities
that arise from simply training on large-scale internet text. With the open-
source release of LLMs—and their associated pre-training datasets—the research
community can now begin to understand the origins of these capabilities. Our
work is one of the first to relate an observed phenomenon in LLMs back to the
pre-training data itself. In our case, our results are negative: while LLMs
achieve moderate performance on open-domain QA benchmarks, they are mainly
successful on questions that probe knowledge that appears widely in their pre-
training datasets.

Our work raises numerous directions for further inquiry, namely, how to
improve retention of long-tail knowledge given that simply scaling up model
and dataset size will likely be insufficient. We are personally excited about
improving retrieval-augmented LMs, especially with regards to their efficiency
and retrieval accuracy. Moreover, our work focuses on knowledge learning as it
relates to factoid question answering, but we leave open the question as to
whether similar relationships exist for other types of tasks, be it knowledge-
intensive or otherwise. Relatedly, even though our work analyzes the impact of
memorization on question answering, our results may have implications for
other tasks that require using (or avoiding) memorized knowledge, e.g.,
analyzing private text, performing commonsense reasoning, or predicting source
code. Finally, we hope that future evaluations of few-shot learning can
continue to shed light into model behavior by tracing accuracy back to
properties of the pre-training data. In particular, our work shows that by
performing such an analysis, one can help elucidate the successes and failures
of existing models, as well as help to identify possible paths forward to
improve today’s systems.

## Acknowledgements

We thank Sewon Min, Sameer Singh, Katherine Lee, and the members of UNC NLP
for their valuable feedback. Eric Wallace is supported by the Apple Scholars
in AI/ML Fellowship. This work was supported by NSF-AI Engage Institute
DRL-2112635.

## References

  * Akyürek et al. (2022) Akyürek, E., Bolukbasi, T., Liu, F., Xiong, B., Tenney, I., Andreas, J., and Guu, K.  Tracing knowledge in language models back to the training data.  In _Findings of EMNLP_ , 2022.
  * Black et al. (2021) Black, S., Leo, G., Wang, P., Leahy, C., and Biderman, S.  GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh-Tensorflow, 2021.
  * Black et al. (2022) Black, S., Biderman, S., Hallahan, E., Anthony, Q., Gao, L., Golding, L., He, H., Leahy, C., McDonell, K., Phang, J., et al.  GPT-Neox-20B: An open-source autoregressive language model.  _arXiv preprint arXiv:2204.06745_ , 2022.
  * Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.  Language models are few-shot learners.  In _NeurIPS_ , 2020.
  * Carlini et al. (2019) Carlini, N., Liu, C., Erlingsson, Ú., Kos, J., and Song, D.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In _USENIX Security Symposium_ , 2019.
  * Carlini et al. (2021) Carlini, N., Tramer, F., Wallace, E., Jagielski, M., Herbert-Voss, A., Lee, K., Roberts, A., Brown, T., Song, D., Erlingsson, U., Oprea, A., and Raffel, C.  Extracting training data from large language models.  In _USENIX Security Symposium_ , 2021.
  * De Cao et al. (2021) De Cao, N., Izacard, G., Riedel, S., and Petroni, F.  Autoregressive entity retrieval.  In _ICLR_ , 2021.
  * Elazar et al. (2022) Elazar, Y., Kassner, N., Ravfogel, S., Feder, A., Ravichander, A., Mosbach, M., Belinkov, Y., Schütze, H., and Goldberg, Y.  Measuring causal effects of data statistics on language model’s factual predictions.  _arXiv preprint arXiv:2207.14251_ , 2022.
  * Elsahar et al. (2018) Elsahar, H., Vougiouklis, P., Remaci, A., Gravier, C., Hare, J., Laforest, F., and Simperl, E.  T-REx: A large scale alignment of natural language with knowledge base triples.  In _LREC_ , 2018.
  * Févry et al. (2020) Févry, T., Soares, L. B., FitzGerald, N., Choi, E., and Kwiatkowski, T.  Entities as experts: Sparse memory access with entity supervision.  In _EMNLP_ , 2020.
  * Gao et al. (2020) Gao, L., Biderman, S., Black, S., Golding, L., Hoppe, T., Foster, C., Phang, J., He, H., Thite, A., Nabeshima, N., et al.  The Pile: An 800GB dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_ , 2020.
  * Gokaslan & Cohen (2019) Gokaslan, A. and Cohen, V.  Openwebtext corpus, 2019.
  * Guu et al. (2020) Guu, K., Lee, K., Tung, Z., Pasupat, P., and Chang, M.  Retrieval augmented language model pre-training.  In _ICML_ , 2020.
  * Han & Tsvetkov (2022) Han, X. and Tsvetkov, Y.  ORCA: Interpreting prompted language models via locating supporting data evidence in the ocean of pretraining data.  _arXiv preprint arXiv:2205.12600_ , 2022.
  * Ippolito et al. (2022) Ippolito, D., Tramèr, F., Nasr, M., Zhang, C., Jagielski, M., Lee, K., Choquette-Choo, C. A., and Carlini, N.  Preventing verbatim memorization in language models gives a false sense of privacy.  _arXiv preprint arXiv:2210.17546_ , 2022.
  * Izacard & Grave (2021) Izacard, G. and Grave, E.  Distilling knowledge from reader to retriever for question answering.  In _ICLR_ , 2021.
  * Jagielski et al. (2023) Jagielski, M., Thakkar, O., Tramer, F., Ippolito, D., Lee, K., Carlini, N., Wallace, E., Song, S., Thakurta, A., Papernot, N., et al.  Measuring forgetting of memorized training examples.  In _ICLR_ , 2023.
  * Joshi et al. (2017) Joshi, M., Choi, E., Weld, D. S., and Zettlemoyer, L.  TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension.  In _ACL_ , 2017.
  * Kandpal et al. (2022) Kandpal, N., Wallace, E., and Raffel, C.  Deduplicating training data mitigates privacy risks in language models.  In _ICML_ , 2022.
  * Karpukhin et al. (2020) Karpukhin, V., Oğuz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t.  Dense passage retrieval for open-domain question answering.  In _EMNLP_ , 2020.
  * Kassner et al. (2020) Kassner, N., Krojer, B., and Schütze, H.  Are pretrained language models symbolic reasoners over knowledge?  In _CoNLL_ , 2020.
  * Kwiatkowski et al. (2019) Kwiatkowski, T., Palomaki, J., Rhinehart, O., Collins, M., Parikh, A., Alberti, C., Epstein, D., Polosukhin, I., Kelcey, M., Devlin, J., et al.  Natural Questions: A benchmark for question answering research.  In _TACL_ , 2019.
  * Laurençon et al. (2022) Laurençon, H., Saulnier, L., Wang, T., Akiki, C., del Moral, A. V., Scao, T. L., Werra, L. V., Mou, C., Ponferrada, E. G., Nguyen, H., Frohberg, J., Šaško, M., Lhoest, Q., McMillan-Major, A., et al.  The BigScience ROOTS corpus: A 1.6TB composite multilingual dataset.  In _NeurIPS_ , 2022.
  * Lee et al. (2019) Lee, K., Chang, M.-W., and Toutanova, K.  Latent retrieval for weakly supervised open domain question answering.  In _ACL_ , 2019.
  * Lee et al. (2021) Lee, K., Ippolito, D., Nystrom, A., Zhang, C., Eck, D., Callison-Burch, C., and Carlini, N.  Deduplicating training data makes language models better.  In _ACL_ , 2021.
  * 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., et al.  Retrieval-augmented generation for knowledge-intensive NLP tasks.  In _NeurIPS_ , 2020.
  * Liu et al. (2022) Liu, L., Lewis, P., Riedel, S., and Stenetorp, P.  Challenges in generalization in open domain question answering.  In _Findings of NAACL_ , 2022.
  * 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.
  * Mendes et al. (2011) Mendes, P. N., Jakob, M., García-Silva, A., and Bizer, C.  DBpedia Spotlight: Shedding light on the web of documents.  In _International Conference on Semantic Systems_ , 2011.
  * Petroni et al. (2019) Petroni, F., Rocktäschel, T., Lewis, P., Bakhtin, A., Wu, Y., Miller, A. H., and Riedel, S.  Language models as knowledge bases?  In _EMNLP_ , 2019.
  * Petroni et al. (2020) Petroni, F., Lewis, P. S. H., Piktus, A., Rocktäschel, T., Wu, Y., Miller, A. H., and Riedel, S.  How context affects language models’ factual predictions.  In _AKBC_ , 2020.
  * Raffel et al. (2020) Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., Liu, P. J., et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  In _JMLR_ , 2020.
  * Rajpurkar et al. (2016) Rajpurkar, P., Zhang, J., Lopyrev, K., and Liang, P.  SQuAD: 100,000+ questions for machine comprehension of text.  In _EMNLP_ , 2016.
  * Rao et al. (2021) Rao, R. M., Liu, J., Verkuil, R., Meier, J., Canny, J., Abbeel, P., Sercu, T., and Rives, A.  Msa transformer.  In _ICML_ , 2021.
  * Razeghi et al. (2022) Razeghi, Y., Logan IV, R. L., Gardner, M., and Singh, S.  Impact of pretraining term frequencies on few-shot reasoning.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , 2022.
  * Roberts et al. (2020) Roberts, A., Raffel, C., and Shazeer, N.  How much knowledge can you pack into the parameters of a language model?  In _EMNLP_ , 2020.
  * Robertson & Zaragoza (2009) Robertson, S. and Zaragoza, H.  The probabilistic relevance framework: BM25 and beyond.  _Foundations and Trends in IR_ , 2009.
  * Scao et al. (2022) Scao, T. L., Fan, A., Akiki, C., Pavlick, E.-J., Ili’c, S., Hesslow, D., Castagn’e, R., Luccioni, A. S., Yvon, F., Gallé, M., Tow, J., Rush, A. M., et al.  BLOOM: A 176b-parameter open-access multilingual language model.  _arXiv preprint arXiv:2211.05100_ , 2022.
  * Shin et al. (2022) Shin, S., Lee, S.-W., Ahn, H., Kim, S., Kim, H., Kim, B., Cho, K., Lee, G., Park, W., Ha, J.-W., et al.  On the effect of pretraining corpora on in-context learning by a large-scale language model.  In _NAACL_ , 2022.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I.  Attention is all you need.  In _NeurIPS_ , 2017.
  * Wang & Komatsuzaki (2021) Wang, B. and Komatsuzaki, A.  GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model.  https://github.com/kingoflolz/mesh-transformer-jax, 2021.
  * Wang et al. (2022) Wang, T., Roberts, A., Hesslow, D., Scao, T. L., Chung, H. W., Beltagy, I., Launay, J., and Raffel, C.  What language model architecture and pretraining objective work best for zero-shot generalization?  In _ICML_ , 2022.
  * Wei et al. (2021) Wei, J., Garrette, D., Linzen, T., and Pavlick, E.  Frequency effects on syntactic rule learning in transformers.  In _EMNLP_ , 2021.

##  Appendix A Additional Results: Relevant Document Scaling

Here we show how QA performance is related to the number of relevant pre-
training documents for the BLOOM on Natural Questions (Figure 10) and the
GPT-3 model family on TriviaQA and Natural Questions (Figure 11). Like the
results in the main text, models are significantly better at answering
questions about facts that are well supported in the pre-training data and
model scale improves knowledge acquisition.

Note that our estimates for the number of relevant pre-training documents for
the GPT-3 model family may be inaccurate since the training data for GPT-3 is
not public. Instead, we estimate these relevant document counts using the open
source dataset OpenWebText, which was collected with a similar process to the
reported collection methodology for the GPT-3 pre-training dataset.

Figure 10: We show results for Natural Questions for BLOOM. The trends match
those seen in TriviaQA, although the accuracy is lower overall for Natural
Questions.

Figure 11: We present the QA results for GPT-3, with Natural Questions shown
in 11 and TriviaQA shown in 11. The trends match those seen in BLOOM and GPT-
Neo. Note that our estimates for the number of relevant pre-training documents
may be inaccurate because the training data for GPT-3 is not public.

##  Appendix B Additional Results: Model Scaling

In this section we show additional results for how long-tail QA accuracy
scales with model size for the BLOOM model family on TriviaQA and the GPT-Neo
model family on Natural Questions and TriviaQA (Figure 12). The log-linear
trend matches the results shown in the main text.

Figure 12: We present additional scaling laws for BLOOM on TriviaQA 12, and
GPT-Neo on Natural Questions 12 and TriviaQA 12. All the trends are similar—we
will need to scale up models dramatically to reach high QA accuracy—but the
exact degree to how much we would need to scale models changes across the
different settings.

##  Appendix C Relevant Document Counting Heuristics

In this section, we analyze the difference between our relevant document
heuristic, which counts documents where the salient question and answer entity
co-occur, compared to two simple baselines: counting documents containing the
question entity and documents containing the answer entity. In Figure 13 we
show that all three document counting heuristics are correlated with QA
accuracy. However, as seen in Figure 13 the correlation of the two baseline
counting methods with QA accuracy disappears when only considering QA examples
where the question and answer entity co-occur few ($<5$) times in the pre-
training data. Thus, these baseline counting heuristics appear correlated with
QA accuracy simply because they are simply correlated with question and answer
entity co-occurrence (i.e., common entities tend to co-occur with other
entities more frequently) rather than causally related to QA performance.

Figure 13: In 13, we plot the relationship between model accuracy and the
count of the question entity alone, as well as the answer entity alone. QA
accuracy increases as both of these counts increase. In 13, we consider only f
QA pairs with few question and answer entity co-occurrences ($<5$ documents).
For this subpopulation of QA pairs, neither of the baseline heuristics are
correlated with QA accuracy.


# A pivoting Mechanically Controllable Break junction setup enabling
“partially wet phase” MCB-junctions.

C.J. Muller

This research has, in its entirety, been privately conducted and funded by the
author Correspondence: PO Box 60, 6580 AB Malden, The Netherlands

###### Abstract

A technique is presented, which creates MCB junctions that can be pivoted to
any desirable angle. The MCB junction equipped with a specific glass liquid
cell can be used to produce a MCB junction, of which the electrodes are
covered with a microscopic layer of fluid, thus producing a “partially wet
phase” MCB junction.

##  1 Introduction

The development of the point-contact-spectroscopy technique by gently pressing
a needle on a metallic bulk piece dates back to 1966 [1]. The so called “spear
anvil” technique has been very successful in studying the density of states
and the superconducting gap at the time. The contacts were usually created by
a sharp screw of a certain metal which was gently contacting the anvil by
turning the screw. At the microscopic scale the contacts were not well
defined, both tunnel junctions created by the native metal-oxide as well as
multiple micro metallic contacts could coexist in the same contact. Nowadays
the point contact technique has evolved to provide scientists with an expanded
toolset including STM versatility and MCB junctions.

The MCB technique muller1992source1a,*muller1992source1b,*muller1996source1c
has been used to obtain insights in a wide spectrum of physical science. For
example, molecules can be captured between the atomically sharp electrodes,
enabling a host of experiments on a single captured molecule. The electrodes
themselves can be made up from normal metals, superconductive metals or exotic
materials, for example heavy fermion superconductors. The adjustable contact
size of the constriction at the atomic scale, the possibility to move atoms in
and out of this constriction in a reproducible way, as well as the adjustable
vacuum gap in the non-contact mode ensures a flexible baseline setup.
Experiments can be performed in vacuum (from dilution fridge temperatures to
room temperature), or at ambient conditions, or submerged in a cryogenic
fluid. These possibilities have led to a wealth of discoveries made in this
interesting field, which basically studies matter at the atomic and/or
molecular scale.

Figure 1: Figure 1a shows a schematic of the central section of a notched MCB
junction. The small size of the electrode-bending beam loop,
electrode1-bendingbeam1-bendingbeam2-electrode2 (E1-B1-B2-E2) plays a key part
in the MCB operation. Figure 1b shows a MCB liquid cell with the junction
fully submerged in the liquid which has been used in molecular conductivity
experiments [2]

The novelty of the MCB junction in the early 90’s relied on the heart of the
device. The electrode-bending beam loop, E1-B1-B2-E2 as indicated in Figure
1a, is on the order of 100 to a few hundred micrometers for notched MCB
junctions. It is feasible to create a distance B1-B2 of 1 to 2 filament
diameters, down to 25 micrometer filaments. For lithographically defined MCB
junctions this loop can be as small as a micrometer to a few tens of
micrometers. The small dimensions of the electrode-bending beam loop ensure an
extreme rigidity of the system, not susceptible to all kinds of (building)
vibrations, present in most labs. A large attenuation factor, which is
inversely proportional to the electrode-bending beam loop, exists between the
extension of the actuator perpendicular to the bending beam, as compared to
the movement of the electrodes alongside the bending beam. Making the
electrode-bending beam loop larger, millimeters or centimeters, will
facilitate breaking of the electrode material. However this will come at the
cost of reduced rigidity and stability as well as a reduction of the
attenuation factor. This will thus in general not lead to the subatomic
adjustability and stability that has become the hallmark of MCB junctions.

One specific category of MCB experiments is submerged in a fluid at ambient
conditions. Some special precaution is required to ensure operability. For
example, one opening of a small glass capillary can be glued on the bending
beam with a flexible elastomeric sealant surrounding the junction area, see
Figure 1b. If the capillary is positioned vertically, a liquid can be injected
at the other end to ensure the MCB junction is submerged. This method has been
proven [2], i.e. the junction can be broken and remains mechanically
controllable whilst being submerged in a liquid. The flexible elastomeric
sealant ensures a tight seal; it caters as well for various degrees of flexing
of the MCB’s bending beam. A controllable junction submerged in a fluid opens
a new range of physical science to be studied. It is possible to measure the
effect of adhesion of a fluid to the electrode material, making it harder for
the electrodes to contact when brought together, as opposed to a situation in
vacuum. In addition specific molecules can be dissolved in the fluid. These
molecules may be tailored with anchor groups to have strong covalent bonds to
the electrodes either on one side, or on opposite sides and bridge the two
junction electrodes once a matching gap is adjusted. In this way the molecular
deposition is modifying the transport characteristics within the fluid
environment.

##  2 Pivoting MCB design

Here we will focus on a MCB design variant which is flexible to pivot an
adjusted MCB junction, leaving the adjusted junction intact during pivoting.
The pivoting MCB design operation is aimed at ambient conditions, where the
setup can either submerge the MCB junction in a fluid, or drain the fluid from
the junction area depending on a certain pivot angle. Its basic principle
relies on the pivoting of a liquid cell, which holds the liquid. The cell is
designed in such a manner that it can hold the liquid while being tilted at
various angles. At one position the MCB junction is submerged in the liquid
(see Figure 2a). At another position the MCB junction is drained, while the
cell still contains the fluid (see Figure 2b).

Figure 2: A MCB liquid cell as detailed in the text. When used in the pivoting
MCB setup, it enables both the completely wet phase (Figure 2a) as well as the
partially wet phase (Figure 2b). The partially wet phase depends on the time
after draining the junction area, until a microscopic layer of fluid resides
on the junction electrodes. Figure 3: A schematic view of the pivoting MCB
setup. The MCB pivot angle in figure 3a and 3b correspond to the two sample
positions indicated in figure 2a and 2b respectively.

This MCB setup encompasses three main parts bolted solidly together and
mounted on a spindle which can freely rotate in a base assembly stand. The
three main parts are: a classical central adjustment part, a top part and a
solid stainless-steel block, connecting the prior two parts, see Figure 3.

The MCB bending beam is flexed using a motor and gearbox 1:120, driving a
spindle which is coupled to a screw. Depending on the revolution direction of
the motor, this screw moves a piezo towards or away from the bending beam via
a lever. For fine tuning of the MCB junction, a hard-piezo material can be
used, extending 5µm at 1000V. The central adjustment part contains the screw,
the piezo, the lever as well as the bending beam assembly. The central
adjustment part is mounted to a stainless-steel block, which forms the right
leg of a rigid, solid “U-shaped” part (see Figure 3a). The top part forms the
left leg of this U-shape in Figure 3a.

Figure 4: Photos of the pivoting MCB setup from 2 different angles

The motor and gearbox are mounted to the top part. Eddy current metal
shielding boxes are mounted to the top part. Electrical connections, running
to the central adjustment part, enter these boxes via corresponding
feedthrough plugs/connectors. In this way the adjusted MCB junction is not
influenced by the connecting measurement cables. Instead these cables pull on
the top part, where they do not influence the junction fixture, see Figure 4.

The entire setup can be pivoted at the lower right corner of the “U”, around a
spindle in a base assembly stand. It can be manually locked/unlocked in any
desired position by a shaft collar with a clamping lever, see Figure 3, 4.

##  3 Modes of operation

A typical mode of operation would make use of the flexible pivot-angle design.
For example, consider a pivot angle in which the liquid cell is in a vertical
position (Figure 2a). In this case an adjusted and fine-tuned MCB junction is
submerged in fluid. By modifying the pivot-angle to arrive at a liquid cell in
a near-horizontal position (Figure 2b), the same adjusted and fine-tuned MCB
junction is now drained from liquid. This procedure can be repeated, as the
liquid is contained by the liquid cell at these pivoting angles.

With this design, repeatability can be studied of both submerged junctions as
well as drained junctions. In analogy to the physics of wetting [5], the
following definitions of possible phases for the MCB junction are proposed:

  * •

Completely wet phase: A MCB junction submerged in a liquid, or if a
macroscopic layer of liquid wets its electrodes.

  * •

Completely dry phase: A MCB junction free from the liquid used in the
experiment or drained from this liquid, and left long enough to dry, to be
sure no liquid layer is present on the junction’s electrodes

  * •

Partially wet phase: A MCB junction drained from its liquid, however, where
the junction electrodes still hold on to a microscopic layer of liquid. A
microscopic layer may consist of a thickness of one or several liquid
molecules, depending on the liquid surface affinity.

Partially wet phase MCB junctions are in general difficult to obtain. Once
drained, the junction electrodes areas will start with a macroscopic layer of
liquid adhered to it, and thus show behavior as in the “Completely wet phase”.
As time progresses, the junction electrodes hold less and less layers of fluid
due to evaporation, until the electrodes will be completely dry from this
fluid. So why try to measure on a system which is time dependent anyhow? The
answer is manifold.

First, at the atomic/molecular or mono-layer level, physics is different from
our everyday experiences. At ambient conditions, all solid surfaces are wetted
with some layer of fluid [5]. If we are able to control the type of fluid, the
resulting microscopic layer of fluid is sustainable over a relatively long
time period. This will provide ample time to perform measurements on a fixed,
unique and well defined system.

Second, within solid state physics we have come to appreciate the importance
of interfaces on electrical transport parameters. A few examples of these
phenomena are as follows:

  * •

A textbook example here is the PN junction interface. At and near the
interface, the excess of charge carriers in the P material (positive holes)
will need to rebalance with the excess of electrons in the N material. Over a
characteristic distance extending from the interface into the P and the N
region, called the depletion region, a build-in potential is generated by
positive carriers in the N region and negative carriers in the P region. Thus
establishing equilibrium between the generated electric field in the depletion
region and the diffusion process because of the concentration differences in
charge carriers.

  * •

The metal-semiconductor interface is another interesting one. Here negative
surface states at the metal surface and a positive charge distribution over a
finite region in the semiconductor make up for the well-known Shottky barrier
[6].

  * •

With proper bandgap engineering the GaAs AlGaAs hetero junction can be
manufactured such that at the GaAs/AlGaAs interface a “V-shaped” triangular
potential exists just below the Fermi level, enabling filling one or a few
levels within this potential trap with electrons. At low enough temperatures
this leads to a two-dimensional electron gas (2DEG) at the GaAs/AlGaAs
interface. 2DEG’s have played an instrumental role in the discovery of the
quantum Hall effect [7] as well as in the understanding of conductance in
mesoscopic structures (for a review see [8]).

  * •

Graphene is a more recent and extreme example. This material of a mono atomic
layer of carbon atoms is interfaced above and below plane with a high barrier,
disabling the layer to layer interaction which is present in graphite.
Graphene reveals the quantum Hall effect at room temperature [9], which is
absent in graphite, which consists of many weakly coupled graphene layers.

Third, however thin a microscopic layer of fluid may be, it can provide
structural support. The microscopic layer adheres strongly to the electrode
surface, thus it may provide structural support for a bridging molecule by
wrapping it in a microscopic 3-dimensional layer lattice.

Summarizing after a MCB junction is drained a macroscopic layer of liquid will
wet its electrodes. If left untouched to dry, at some point the “Partially wet
phase” will be entered. Here only a microscopic layer of fluid exists on the
junction electrodes. This layer will evaporate eventually and be replaced by a
layer of $\text{H}_{2}\text{O}$ at ambient conditions. Thus, although the
electrodes may be completely dry from the specific fluid used in the
experiments, a “Completely dry phase” will not be reached at ambient
conditions.

##  4 Conclusion

We have provided a design of a pivoting MCB setup which enables studies of the
partially wet phase MCB junction. Controlled “partially wet phase” MCB
junctions have been difficult to obtain until now. These junctions may show
interesting physics, as electrical properties as well as mechanical properties
at the molecular level can be profoundly influenced by the presence of a
microscopic layer of fluid.

## Acknowledgement

We would like to thank H.A.J. Peters for the construction of the pivoting MCB
setup.

## References

  * [1] HJ Levinstein and JE Kunzler.  Observation of energy gaps in $\beta$-tungstens and other superconductors using a simplified tunneling technique.  Physics Letters, 20(6):581–583, 1966.
  * [2] CJ Muller.  An experimental study on mechanically controllable break junctions.  PhD thesis, Universiteit Leiden, 1992.
  * [3] CJ Muller, JM Van Ruitenbeek, and LJ De Jongh.  Experimental observation of the transition from weak link to tunnel junction.  Physica C: Superconductivity, 191(3-4):485–504, 1992.
  * [4] CJ Muller, BJ Vleeming, MA Reed, JJS Lamba, R Hara, L Jones II, and JM Tour.  Atomic probes: a search for conduction through a single molecule.  Nanotechnology, 7(4):409, 1996.
  * [5] Daniel Bonn, Jens Eggers, Joseph Indekeu, Jacques Meunier, and Etienne Rolley.  Wetting and spreading.  Reviews of modern physics, 81(2):739, 2009.
  * [6] Walter Schottky.  Zur halbleitertheorie der sperrschicht-und spitzengleichrichter.  Zeitschrift für Physik, 113(5):367–414, 1939.
  * [7] K v Klitzing, Gerhard Dorda, and Michael Pepper.  New method for high-accuracy determination of the fine-structure constant based on quantized hall resistance.  Physical review letters, 45(6):494, 1980.
  * [8] Leo P Kouwenhoven, Gerd Schön, and Lydia L Sohn.  Introduction to mesoscopic electron transport.  In Mesoscopic Electron Transport, pages 1–44. Springer, 1997.
  * [9] Konstantin S Novoselov, Z Jiang, Y Zhang, SV Morozov, Horst L Stormer, U Zeitler, JC Maan, GS Boebinger, Philip Kim, and Andre K Geim.  Room-temperature quantum hall effect in graphene.  Science, 315(5817):1379–1379, 2007.


University of Warsaw Pierre Ohlmann [100]Replace ccsdesc macro with valid one

###### Acknowledgements.

I want to thank …John Q. Open and Joan R. Access 2 42nd Conference on Very
Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little
Whinging, United Kingdom 42 23

# Positionality of mean-payoff games on infinite graphs

Pierre Ohlmann

###### keywords:

Dummy keyword

###### category:

## Context

The mean-payoff objective was introduced by Ehrenfeucht and Mycielski [3] who
first proved its positionality over finite game graphs. By now, many
additional proofs of positionality are available, using the GKK algorithm [5],
the reduction to discounted games [8, 9], first-cycle games [2, 1], concavity
[6], or the 1-to-2 player lift of [4]. All these proofs have in common that
finiteness of the game graph is required. In fact, if defined without care,
mean-payoff games fail to be positional over infinite graphs (even with degree
2), as shown in Figure 1.

Figure 1: Two infinite games of finite degree witnessing failure of
positionality for different variants of the mean-payoff objective. Circles are
controlled by Eve, the minimizer, while squares are controlled by the
opponent. In the game displayed at the top, Eve requires non-positional
strategies to ensure a path whose weights $w_{0}w_{1}\dots$ satisfy
$\limsup_{n}\frac{1}{n}\sum_{i=0}^{n-1}w_{i}\leq 0$. In the game at the
bottom, Eve requires non-positional strategies to ensure a path whose weights
$w_{0}w_{1}\dots$ satisfy $\liminf_{n}\frac{1}{n}\sum_{i=0}^{n-1}w_{i}\leq 0$,
or that the same quantity is $<0$.

## Result

In this short note, we establish that, if the mean-payoff objective is defined
adequately, positionality (for Eve) is recovered over arbitrary game graphs.
To do so, we define a well-founded monotone graph which is universal for the
mean-payoff objective, and then rely on [7, Theorem 3.2]. For all definitions
and notations relative to graphs, games, positionality, universality and
monotonicity, we refer to [7].

## Mean-payoff

We define the mean-payoff function to be

$\begin{array}[]{lrcl}\text{mp}:&\mathbb{Z}^{\omega}&\to&\overline{\mathbb{R}}\\\
&w_{0}w_{1}\dots&\mapsto&\limsup_{n}\frac{1}{n}\sum_{i=0}^{n-1}w_{i}\end{array}$

and the (threshold) mean-payoff objective to be

$W=\\{w\in\mathbb{Z}^{\omega}\mid\text{mp}(w)<0\\}.$

Note that the three other variants (changing $\limsup$ for $\liminf$ and/or
$<0$ for $\leq 0$) are non-positional (see Figure 1), even over graphs of
degree 2.

## A well-founded monotone graph

Consider the graph $U$ over $V(U)=\mathbb{N}^{\geq 1}\times\mathbb{N}$,
ordered lexicographically (with the first coordinate as most important) and
given by

$(m,t)\xrightarrow{w}(m^{\prime},t^{\prime})\in E(U)\quad\iff\quad
m>m^{\prime}\text{ or }\big{[}m=m^{\prime}\text{ and }mw\leq
t-t^{\prime}-1\big{]}.$

Clearly, $U$ is a well-founded monotone graph.

######  Lemma 0.1.

The graph $U$ satisfies the objective $W$.

######  Proof 0.2.

Consider an infinite path
$(m_{0},t_{0})\xrightarrow{w_{0}}(m_{1},t_{1})\xrightarrow{w_{1}}\dots$ and
let $w=w_{0}w_{1}\dots$. By well-foundedness, there is $i_{0}$ such that
$(m_{i})_{i\geq i_{0}}$ is constant, say, equal to $m\geq 1$. Then by
definition of $U$, for all $i\geq i_{0}$, we have $mw_{i}\leq t_{i}-t_{i+1}-1$
which leads to

$\text{mp}(w)=\limsup_{n}\frac{1}{n}\Big{[}\sum_{i=0}^{i_{0}-1}w_{i}+\frac{t_{i_{0}}-t_{n}-(n-i_{0})}{m}\Big{]}\overset{(*)}{\leq}-\frac{1}{m}<0,$

where $\overset{(*)}{\leq}$ holds since for all $n$, $t_{n}\geq 0$.

## Proof of universality

We now prove that for any cardinal $\kappa$, $U$ is almost $\kappa$-universal
for $W$, which implies, by [7, Lemma 4.5], that $U\cdot\kappa$ is
$\kappa$-universal for $W$. Below, $G[v]$ denotes the restriction of a graph
$G$ to vertices reachable from $v$ in $G$.

######  Lemma 0.3.

Let $G$ be a graph satisfying $W$. There exists $v\in V(G)$ such that $G[v]\to
U$.

######  Proof 0.4.

Given a finite path $\pi$, we use $\operatorname{sum}(\pi)$ and
$\text{avg}(\pi)$ to denote respectively the sum or the average of the weights
appearing on $\pi$. The proof hinges on the following claim.

######  Claim 1.

There exists $v\in V(G)$, $m\geq 1$ and $t\in\mathbb{N}$ such that for all
finite paths $\pi$ of length $\ell$ from $v$ we have

$\operatorname{sum}(\pi)\leq\frac{-\ell+t}{m}.$

The statement of Claim 1 is illustrated in Figure 2.

Figure 2: Constraining all paths below some affine line with negative slope,
as in the statement of Claim 1.

We prove the claim by contradiction, so assume that for all $v\in V(G)$ and
all $m\geq 1$ and $t\in\mathbb{N}$, there is a finite path $\pi$ of length
$\ell$ from $v$ such that

$\operatorname{sum}(\pi)>\frac{-\ell+t}{m}.$

Pick $v_{0}\in V(G)$; we aim to construct a path from $v_{0}$ in $G$ with
mean-payoff $\geq 0$, which contradicts the fact that $G$ satisfies $W$. It
will be of the form

$v_{0}\overset{\pi_{0}}{\rightsquigarrow}v_{1}\overset{\pi_{1}}{\rightsquigarrow}\dots,$

where each $\pi_{i}$ is non-empty. For $n\in\mathbb{N}$, we let $\pi_{<n}$
denote the concatenation of $\pi_{0},\dots,\pi_{n-1}$ (which is the empty path
for $n=0$). The idea is to ensure that at the $n$-th step, the average of the
partial sum on our path exceeds $-1/(n+1)$:

$\text{avg}(\pi_{<n})\geq-\frac{1}{n+1}.$

This implies our claim: since averages of partial sums have a subsequence
lower bounded by one that goes to 0, the limsup is $\geq 0$.

Let $n\in\mathbb{N}$ and assume the path constructed up to $v_{n}$ (this is
trivially verified for $n=0$). Apply $(*)$ to obtain a finite path
$\pi_{n}:v_{n}\overset{}{\rightsquigarrow}v_{n+1}$ of length $\ell$ satisfying

$\operatorname{sum}(\pi_{n})\geq-\frac{\ell}{n+1}+\max\Big{(}-\operatorname{sum}(\pi_{<n})-\frac{\ell^{\prime}}{n+1},1\Big{)},$

where $\ell^{\prime}=|\pi_{<n}|$. Note that since the $\max$ is $>0$,
$\pi_{n}$ must be non-empty (this is the only purpose of the $\max$ above).
Then we get

$\text{avg}(\pi_{<n+1})=\frac{\operatorname{sum}(\pi_{<n})+\operatorname{sum}(\pi_{n})}{\ell^{\prime}+\ell}\geq\frac{-\frac{\ell^{\prime}}{n+1}-\frac{\ell}{n+1}}{\ell^{\prime}+\ell}\geq-\frac{1}{n+1},$

as required. This concludes the proof of the claim.

Thus we take $v\in V(G),m\geq 1$ and $t\in\mathbb{N}$ as given by the above
claim.

######  Claim 2.

For any $v^{\prime}$ reachable from $v$ in $G$, there exists $t^{\prime}$ such
that for all finite paths $\pi^{\prime}$ of length $\ell^{\prime}$ from
$v^{\prime}$ we have

$\operatorname{sum}(\pi^{\prime})\leq\frac{-\ell^{\prime}+t^{\prime}}{m}.$

Fix a path $v\overset{\pi}{\rightsquigarrow}v^{\prime}$ of length $\ell$ and
let $t^{\prime}=\lceil t-\ell-m\operatorname{sum}(\pi)\rceil$. Then we get

$\operatorname{sum}(\pi^{\prime})\leq\operatorname{sum}(\pi\pi^{\prime})-\operatorname{sum}(\pi)\leq\frac{-(\ell+\ell^{\prime})+t-m\operatorname{sum}(\pi)}{m}\leq\frac{-\ell^{\prime}+t^{\prime}}{m},$

as required.

Now, for each $v^{\prime}$ reachable from $v$ (including $v$ itself), we
define $t_{v^{\prime}}$ to be the minimal $t^{\prime}$ as in Claim 2, and
define a map $\phi:V(G[v])\to V(U)$ by setting
$\phi(v^{\prime})=(m,t_{v^{\prime}})$.

######  Claim 3.

The map $\phi$ defines a morphism $G[v]\to U$.

Let $u\xrightarrow{w}u^{\prime}$ be an edge in $G[v]$, we must prove that
$(m,t_{u})\xrightarrow{w}(m,t_{u^{\prime}})$ is an edge in $U$, which rewrites
as

$mw\leq t_{u}-t_{u^{\prime}}-1.$

By minimality of $t_{u^{\prime}}$, there exists a finite path $\pi^{\prime}$
of length $\ell^{\prime}$ from $u^{\prime}$ satisfying

$\operatorname{sum}(\pi^{\prime})>\frac{-\ell^{\prime}+t_{u^{\prime}}-1}{m}.$

But then $(u\xrightarrow{w}u^{\prime})\pi^{\prime}$ defines a path of length
$\ell^{\prime}+1$ from $u$, and weight $w+\operatorname{sum}(\pi^{\prime})$
therefore by definition of $t_{u}$ we get

$w+\operatorname{sum}(\pi^{\prime})\leq\frac{-(\ell^{\prime}+1)+t_{u}}{m}.$

Subtracting $(1)$ from $(2)$ yields

$w<\frac{-(\ell^{\prime}+1)+t_{u}+\ell^{\prime}-t_{u^{\prime}}+1}{m}=\frac{t_{u}-t_{u^{\prime}}}{m}.$

Since $mw<t_{u}-t_{u^{\prime}}$ and these are integers, we get $mw\leq
t_{u}-t_{u^{\prime}}-1$, as required. This concludes our proof.

######  Remark 0.5.

The reader may wonder what happens when real weights are allowed, instead of
just integers. We claim that the exact same construction remains universal,
which proves positionality. The proof of universality becomes slightly more
subtle, the idea is to take $v,m,t$ as in Claim 1, then continue the proof
with $2m$ instead of $m$, and by rounding up the weights within
$\frac{\mathbb{Z}}{2m}$. The move from $m$ to $2m$ gives some extra slack that
compensates for the loss from the rounding. To keep the note short, we do not
include a detailed proof.

## References

  * [1] Benjamin Aminof and Sasha Rubin.  First-cycle games.  Inf. Comput., 254:195–216, 2017.  doi:10.1016/j.ic.2016.10.008.
  * [2] Henrik Björklund, Sven Sandberg, and Sergei G. Vorobyov.  Memoryless determinacy of parity and mean payoff games: a simple proof.  Theor. Comput. Sci., 310(1-3):365–378, 2004.  doi:10.1016/S0304-3975(03)00427-4.
  * [3] A. Ehrenfeucht and J. Mycielski.  Positional strategies for mean payoff games.  Int. J. Game Theory, 8(2):109–113, jun 1979.  doi:10.1007/BF01768705.
  * [4] Hugo Gimbert and Wieslaw Zielonka.  Games where you can play optimally without any memory.  In CONCUR, volume 3653 of Lecture Notes in Computer Science, pages 428–442. Springer, 2005.  doi:10.1007/11539452\\_33.
  * [5] V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan.  Cyclic games and an algorithm to find minimax cycle means in directed graphs.  USSR Computational Mathematics and Mathematical Physics, 28:85–91, 1988.
  * [6] Eryk Kopczyński.  Half-positional determinacy of infinite games.  In ICALP, pages 336–347, 2006.
  * [7] Pierre Ohlmann.  Characterizing Positionality in Games of Infinite Duration over Infinite Graphs.  TheoretiCS, Volume 2, January 2023.  URL: https://theoretics.episciences.org/10878, doi:10.46298/theoretics.23.3.
  * [8] Anuj Puri.  Theory of Hybrid Systems and Discrete Event Systems.  PhD thesis, EECS Department, University of California, Berkeley, dec 1995\.  URL: http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2950.html.
  * [9] Uri Zwick and Mike Paterson.  The complexity of mean payoff games on graphs.  Theoretical Computer Science, 158(1-2):343–359, 1996.  doi:10.1016/0304-3975(95)00188-3.