# A Latent Space Theory for Emergent Abilities in Large Language Models

Hui Jiang
Department of Electrical Engineering and Computer Science
York University, Toronto, Ontario, M3J 1P3, Canada
<EMAIL_ADDRESS>http://wiki.cse.yorku.ca/user/hj/

###### Abstract

Languages are not created randomly but rather to communicate information.
There is a strong association between languages and their underlying meanings,
resulting in a sparse joint distribution that is heavily peaked according to
their correlations. Moreover, these peak values happen to match with the
marginal distribution of languages due to the sparsity. With the advent of
LLMs trained on big data and large models, we can now precisely assess the
marginal distribution of languages, providing a convenient means of exploring
the sparse structures in the joint distribution for effective inferences. In
this paper, we categorize languages as either unambiguous or
$\varepsilon$-ambiguous and present quantitative results to demonstrate that
the emergent abilities of LLMs, such as language understanding, in-context
learning, chain-of-thought prompting, and effective instruction fine-tuning,
can all be attributed to Bayesian inference on the sparse joint distribution
of languages.

##  1 Introduction

Over the past few years, large language models (LLMs) have emerged as the
predominant method for most natural language processing (NLP) tasks [18, 19,
3, 5]. With the increase in model size and training data, LLMs have
demonstrated remarkable capabilities in solving various NLP tasks, including
semantic understanding, few-shot in-context learning, chain-of-thought
prompting, and effective instruction fine-tuning for alignment. These
abilities are often referred to as emergent capabilities as they have been
observed to emerge as the model size and training data increase [27]. Machine
learning researchers are perplexed by how LLMs develop these skills to perform
well on unseen tasks, especially since LLMs are primarily trained in an
unsupervised manner to predict the next tokens in text. Some empirical studies
have suggested that the emergent abilities of LLMs may be linked to the label
space and input data distributional properties [14, 4], multitask prompted
learning [22], and pre-training term frequencies [20]. Moreover, Xie et al.
[28], Wang et al. [24] have proposed theories that explain in-context learning
of LLMs as Bayesian inferences that use prompts to recover latent concepts.
More recently, Hahn and Goyal [7] claimed that the emergent abilities arise
through recombination of compositional structures in natural languages.

Motivated by Xie et al. [28], our study proposes a novel latent space theory
to explain the emergent abilities of LLMs. While Xie et al. [28] considered a
specific type of data distribution generated by Hidden Markov Models (HMMs),
we examine general data distributions by exploring the sparsity property that
is universally present in the joint distributions of languages. LLMs, which
serve as a universal density approximator to the marginal distribution, offer
a convenient means of exploring these sparse structures for effective
inferences. We categorize languages as either unambiguous or
$\varepsilon$-ambiguous and present quantitative results demonstrating that
the emergent abilities of LLMs can be attributed to Bayesian inference on the
sparse joint distribution of languages. Furthermore, we provide simulation
results on synthetic languages that validate our theoretical findings.

##  2 A Latent Space Model for Language Generation

Languages are not created randomly, but with a specific purpose in mind, which
is to convey information. Languages are composed of distinct, relatively
independent units, such as sentences in natural languages or statements in
programming languages. These separate pieces of language are referred to as
"messages" in this paper. Each message, represented as $\mathbf{x}$, is in
turn composed of a sequence of symbols from an alphabet with varying lengths.
A message is created with the aim of expressing a single and definite
intention, denoted as $\theta$. The set of all possible intentions constitutes
another space, denoted as $\mathbf{\Theta}$. We assume that the intention
space $\mathbf{\Theta}$ is a countable set of many distinct intentions. Each
$\theta$ may represent a simple intention, which is an element from a finite
set, or a composite intention that is made up of several simpler concepts or
components through concatenation or recursion. Here we only require that the
intention space $\mathbf{\Theta}$ is discrete and complete, and each element
in $\mathbf{\Theta}$ is unique.

In this study, we investigate a popular stochastic process for language
generation:

Step one: To generate a message, we first select an intention
$\mathbf{\theta}$ we wish to convey from a prior distribution
$q(\mathbf{\theta})$: $\mathbf{\theta}\sim q(\mathbf{\theta})$. Since the
underlying intention $\mathbf{\theta}$ is not explicitly specified, it is
considered a latent variable, and therefore the intention space
$\mathbf{\Theta}$ is a latent space.

Step two: After sampling an intention, say $\theta_{0}$, from the prior
distribution in the previous step, we generate a message $\mathbf{x}$ to
convey the intention using a conditional distribution $q(\mathbf{x}|\theta)$
by conditioning on $\theta_{0}$, i.e., $\mathbf{x}\sim
q(\mathbf{x}|\theta_{0})$. To ensure that the generated message is meaningful,
we require that the conditional distribution $q(\mathbf{x}|\theta)$ is
appropriately formulated such that the generated messages satisfy one of the
following conditions:

  1. 1.

Unambiguous condition:

$\Pr(\theta_{0}|\mathbf{x})=1.$ (1)

This condition implies that we can precisely infer the underlying intention
from the message with certainty. If this condition holds for all messages
generated in a language, it is called an unambiguous language.

  2. 2.

Dominant condition with $\varepsilon$-ambiguity:

$\Pr(\theta_{0}|\mathbf{x})\geq
1-\varepsilon(\mathbf{x})\;\;\;\;(\mbox{with}\;\;0\leq\varepsilon(\mathbf{x})<1).$
(2)

In this scenario, we cannot definitively deduce the underlying intention from
the observed message, but we can do so with a reasonable level of confidence.
If every message generated in a language satisfy this condition with an
$\varepsilon\in[0,1)$, it is called an $\varepsilon$-ambiguous language. Each
generated message has an $\varepsilon$ value that measures its degree of
ambiguity. The smaller the $\varepsilon$ value of a message, the more precise
and explicit it is. For any given intention $\theta_{0}$, it is possible to
revise the message $\mathbf{x}$ in order to reduce its $\varepsilon$ value.
This can be achieved by adding more details or choosing a better expression
that makes the message less ambiguous.

From the perspective of communication, it makes sense that any practically-
useful languages have been designed or evolved to satisfy either the condition
of being unambiguous or the condition of being dominant. Otherwise, a message
$\mathbf{x}$ becomes gibberish so that it does not serve the purpose of
communication. It is important to note that neither of these conditions limits
the possibility of expressing a single intention through multiple messages.
The key constraint is whether or not we can confidently infer the intended
meaning from each given message. For example, computer languages are designed
to satisfy the unambiguous condition. For any computation task (viewed as an
intention $\theta_{0}$), we can always write many different programs to
achieve the same purpose. However, once we are given a piece of computer
programs, it will perform one particular computation without any ambiguity.
Even if the program has errors or bugs, it still carries out a specific action
in a definitive manner. On the other hand, natural languages are well known to
be notoriously ambiguous. Almost every message written in a natural language
can be misinterpreted one way or another. However, we argue that every
meaningful message in natural languages must satisfy the dominant condition so
that the probability of misunderstanding is bounded by a sufficiently small
number. If the probability of miscommunication is kept low, the message can
still be valuable in conveying some information. In such cases, generating
additional messages that are aligned with the same intention can enhance the
likelihood of effectively communicating the intended meaning to a level that
is considered adequate.

The joint distribution of languages, whether they are unambiguous or
$\varepsilon$-ambiguous, shows an intriguing property of sparsity (see
Appendix A). For any unambiguous language, we have

$\Pr(\theta_{0}|\mathbf{x})=1\implies
q(\theta,\mathbf{x})=\left\\{\begin{array}[]{cc}q(\mathbf{x})&\theta=\theta_{0}\\\
0&\theta\neq\theta_{0}\end{array}\right.$ (3)

For an $\varepsilon$-ambiguous language, we have

$\Pr(\theta_{0}|\mathbf{x})\geq
1-\varepsilon(\mathbf{x})\implies\frac{q(\theta_{0},\mathbf{x})}{q(\Theta\backslash\theta_{0},\mathbf{x})}\geq\frac{1}{\varepsilon(\mathbf{x})}$
(4)

where $\Theta\backslash\theta_{0}$ denotes a complement set containing all
elements in $\Theta$ except $\theta_{0}$, and
$q(\Theta\backslash\theta_{0},\mathbf{x})$ is defined as the total residue
after the contribution of the intention $\theta_{0}$ is taken out:
$q(\Theta\backslash\theta_{0},\mathbf{x})\overset{\Delta}{=}\sum_{\theta\in\mathbf{\Theta},\theta\neq\theta_{0}}\;q(\theta,\mathbf{x})=q(\mathbf{x})-q(\theta_{0},\mathbf{x})$.

The above latent space model can be extended to generate a composite segment
of languages that is composed of multiple messages, i.e.,
$\mathbf{X}=\\{\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{m}\\}$. The
marginal distribution of $\mathbf{X}$ can be computed based on the latent
space model as:

$q(\mathbf{X})=q(\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{m})=\sum_{\theta_{1},\cdots,\theta_{m}}\;\;q(\theta_{1},\theta_{2},\cdots,\theta_{m})\prod_{i=1}^{m}q(\mathbf{x}_{i}|\theta_{i})$

where $\theta_{i}$ ($\forall i=1,2,\cdots,m)$ denotes the latent variable
under which each message $\mathbf{x}_{i}$ is generated. If these intentions
are coherent, their joint probability
$q(\theta_{1},\theta_{2},\cdots,\theta_{m})$ is high, otherwise it is low.
Obviously, for unambiguous or $\varepsilon$-ambiguous languages, the term
corresponding to the actual intentions of all messages will dominate the above
summation over other possible intentions.

The above latent space model for language generation has been known for a long
time [16, 13, 2, 25]. However, when we apply this model to any practical
language-related task, we face two insurmountable challenges:
i) The latent space $\mathbf{\Theta}$ is unknown. We can only be certain that
$\mathbf{\Theta}$ is a complete set encompassing all possible distinct
intentions that are relevant to the underlying task. We lack understanding of
what the individual components of $\theta$ may be and how to effectively
construct them in order to achieve a complete $\mathbf{\Theta}$ for any
practical application. For a considerable period of time, many AI researchers
have maintained the belief that we cannot achieve artificial general
intelligence without possessing the full knowledge and ability to explicitly
specify and model the underlying latent space $\mathbf{\Theta}$.
ii) All true probability distributions, i.e. $q(\theta)$,
$q(\mathbf{x}|\theta)$, $q(\mathbf{x})$, are not available. In the past, a
variety of statistical models have been proposed to approximate these unknown
distributions. However, due to the constraints in computing resources, it
tended to use simple or small models for this purpose, which could only
provide rough estimates for these true distributions and were never able to
assess them with precision.

This paper aims to elucidate why and how the existing practices of utilizing
LLMs have inadvertently addressed the two aforementioned issues, leading to a
significant enhancement in the inference performance without requiring
explicit knowledge of $\mathbf{\Theta}$. This sudden improvement is often
viewed as the emergent abilities from these extensive language models.

##  3 LLMs are a universal density approximator of marginal distribution
$q(\mathbf{x})$

For any message $\mathbf{x}$ in a language consisting of $T$ symbols,
$\mathbf{x}=\\{x_{1},x_{2},\cdots,x_{T}\\}$, according to the general product
rule of probability, we have

$q(\mathbf{x})=q(x_{1},x_{2},\cdots,x_{T})=q(x_{1})q(x_{2}|x_{1})\cdots
q(x_{T}|x_{1},x_{2},\cdots,x_{T-1}).$

If we can construct a statistical model to accurately compute these
conditional probabilities conditioned on any history string (no more than
$T-1$ symbols), we will be able to compute the true marginal distribution
$q(\mathbf{x})$ for any message of no more than $T$ symbols. Let’s denote this
statistical model as $p_{\mathbf{\Lambda}}(x|\mathbf{h})$, where
$\mathbf{\Lambda}$ stands for all parameters of this model, we may use this
model to compute a distribution for any $\mathbf{x}$ (no more than $T$
symbols) as follows:

$p_{\mathbf{\Lambda}}(\mathbf{x})=p_{\mathbf{\Lambda}}(x_{1},x_{2},\cdots,x_{T})=p_{\mathbf{\Lambda}}(x_{1})p_{\mathbf{\Lambda}}(x_{2}|x_{1})\cdots
p_{\mathbf{\Lambda}}(x_{T}|x_{1},x_{2},\cdots,x_{T-1})$

Generally speaking, $p_{\mathbf{\Lambda}}(\mathbf{x})\neq q(\mathbf{x})$
because the statistical model can only be viewed as a rough approximation of
the true marginal distribution $q(\mathbf{x})$ at best. In the following, we
will discuss a special case where a sufficiently large statistical model is
constructed so that $p_{\mathbf{\Lambda}}(\mathbf{x})$ can approach
$q(\mathbf{x})$ asymptotically.

###### Definition 1

A parametric statistical model $p_{\mathbf{\Lambda}}(\mathbf{x})$ is called a
universal density approximator if there exists a set of parameters
$\mathbf{\Lambda}$ for any given probability distribution $q(\mathbf{x})$ so
that $p_{\mathbf{\Lambda}}(\mathbf{x})$ can approximate $q(\mathbf{x})$ up to
any precision:

$\forall\,q(\mathbf{x}),\forall\epsilon>0,\exists\mathbf{\Lambda}:\;\;\;\;\Big{|}\,q(\mathbf{x})-p_{\mathbf{\Lambda}}(\mathbf{x})\,\Big{|}\leq\epsilon\;\;(\forall\mathbf{x}).$

###### Lemma 1

A composition of some universal function approximators and the softmax
function leads to a universal density approximator to the above conditional
distribution $q(x|\mathbf{h})$.

Lemma 1 is obvious. For any history $\mathbf{h}$, $q(x|\mathbf{h})$ is a
multinomial distribution (of all unique symbols in alphabet), we can take
logarithm to obtain the required input for the softmax function to derive this
multinomial distribution. A set of universal function approximators can be
constructed to map any $\mathbf{h}$ to its required input so that the given
conditional distribution is modelled precisely [1, 10].

###### Lemma 2

A sufficiently large transformer model is a universal function approximator.

Yun et al. [29] have proved that transformer models [23] can universally
approximate arbitrary continuous sequence-to-sequence functions. An immediate
corollary is that transformers can precisely map each input sequence
$\mathbf{h}$ to any output values.

###### Theorem 1

If a statistical model $p_{\mathbf{\Lambda}}(\mathbf{x})$ is a universal
density approximator, the model parameters $\mathbf{\Lambda}_{n}$ is the
maximum likelihood estimation from a training set consisting of $n$ i.i.d.
samples randomly drawn from any distribution $q(\mathbf{x})$, then we have

$\lim_{n\to\infty}\;\;p_{\mathbf{\Lambda}_{n}}(\mathbf{x})=q(\mathbf{x})$

for all $\mathbf{x}$.

Theorem 1 can be viewed as a corollary from the consistency property of
maximum likelihood estimation [11, 8]. See Appendix B for a proof.

As in today’s large language models (LLMs), if we construct a universal
density approximator $p_{\mathbf{\Lambda}}(x|\mathbf{h})$ for any history
$\mathbf{h}$ (no more than $T-1$ symbols) using the so-called GPT structures
[17, 18], and furthermore if we use maximum likelihood estimation to derive
its parameters, denoted as $\mathbf{\Lambda}_{*}$, from an infinite number of
text messages that are presumed to be generated from the above latent space
model (as in [3]), according to Lemmas 1 and 2, and Theorem 1, we have

$p_{\mathbf{\Lambda}_{*}}(\mathbf{x})=q(\mathbf{x})$ (5)

for all $\mathbf{x}$ (no more than $T$ symbols) generated from the same latent
space model. In other words, today’s LLM techniques allow us to accurately
assess the margin distribution of languages, which was not possible in the
past.

##  4 Language Understanding with LLMs

Large Language models (LLMs) have surprised many NLP researchers with their
ability to comprehend any given text prompt and generate highly relevant
fluent responses. What is remarkable is that LLMs are trained through a
predict-next-token approach, which seems to have nothing to do with the
semantic meanings of languages. However, it is easy to tell that this predict-
next-token approach is essentially the maximum likelihood estimation of the
marginal distribution $q(\mathbf{x})$. Assume an LLM $\mathbf{\Lambda}_{*}$ is
well trained from an infinite number of text messages so that this model
converges to the true marginal distribution of languages as shown in eq.(5).
Despite this seemingly limited training approach, LLMs demonstrate a
remarkable capacity to understand the content of any text prompt and generate
coherent and appropriate responses. Here, we will explain how this happens in
LLMs.

Assume the prompt $\mathbf{x}$ is a message generated from the above latent-
space-based language generation process, where $\mathbf{x}$ is generated based
on a hidden intention $\theta_{\mathbf{x}}$. We do not know exactly what
$\theta_{\mathbf{x}}$ is but we are sure it belongs to the latent space
$\mathbf{\Theta}$. For simplicity, we first assume the language generation
process is unambiguous. When we sample the LLM $\mathbf{\Lambda}_{*}$ to
generate a reply $\mathbf{y}$ conditioned on the prompt $\mathbf{x}$, we can
easily compute the distribution of all possible replies $\mathbf{y}$ as
follows:

$p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})=\frac{p_{\mathbf{\Lambda}_{*}}(\mathbf{x},\mathbf{y})}{p_{\mathbf{\Lambda}_{*}}(\mathbf{x})}=\frac{q(\mathbf{x},\mathbf{y})}{q(\mathbf{x})}$

Let’s use $\theta$ to indicate the latent variable in the above language
generation process, we further derive the numerator as follows:

$q(\mathbf{x},\mathbf{y})=\sum_{\theta\in\mathbf{\Theta}}q(\mathbf{x},\theta,\mathbf{y})=\sum_{\theta\in\mathbf{\Theta}}q(\mathbf{x},\theta)\;q(\mathbf{y}|\mathbf{x},\theta)=q(\mathbf{x})\;q(\mathbf{y}|\mathbf{x},\theta_{\mathbf{x}})$

The last step in the above relies on the sparsity property of unambiguous
languages in (3). Substituting it to the above equation, we further have

$p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})=q(\mathbf{y}|\mathbf{x},\theta_{\mathbf{x}})$

In other words, when we sample the LLMs to generate a reply based on the
prompt $\mathbf{x}$, it essentially uses the exactly same language generation
process conditioned on both the prompt and its true unknown intention
$\theta_{\mathbf{x}}$. Even though we do not know what $\theta_{\mathbf{x}}$
is, the magic of the LLMs lies at that this unknown intention can be
implicitly explored by the LLMs in such a way that the reply $\mathbf{y}$ is
generated under this intention to continue the prompt $\mathbf{x}$. This is
the fundamental reason why the LLMs can perfectly understand the meaning of
any text prompt and accordingly generate a highly relevant and fluent reply
because the conditional sampling on LLMs is essentially identical to the same
language generation process that yields a text message under the intention
$\theta_{\mathbf{x}}$ in the first place.

Next, let’s extend the above result to $\varepsilon$-ambiguous languages.

###### Proposition 1

For $\varepsilon$-ambiguous languages, the conditional distribution of LLMs
and the true conditional distribution in the language generation process are
bounded as:

$\Big{|}p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})-q(\mathbf{y}|\mathbf{x},\theta_{\mathbf{x}})\Big{|}\leq\varepsilon(\mathbf{x})$
(6)

where $\varepsilon(\mathbf{x})$ denotes the ambiguity of the prompt.

See Appendix C for a detailed proof. Proposition 1 suggests that the ambiguity
in language generation deviates the distribution of all possible replies from
the ideal distribution in the language generation. However, their difference
is bounded by the ambiguity of the prompt, i.e. $\varepsilon(\mathbf{x})$.
This explains why choosing a well-crafted prompt can minimize the margin of
error and result in more proficient responses [12, 21].

##  5 In-Context Learning in LLMs

One impressive capability of large language models (LLMs) is their ability to
perform few-shot in-context learning. Even when presented with tasks that were
not included in their initial training, LLMs can quickly learn these tasks by
observing just a few examples without any need to modify their model
parameters. After observing a few such examples, the LLM can immediately apply
the newly acquired skill to any new cases following the examples.

Let’s first explain the typical setting for few-shot in-context learning in
LLMs. Assume we want to teach an pre-trained LLM $\mathbf{\Lambda_{*}}$ to
conduct a new task by providing an instruction text $\mathbf{x}$, along with a
few independent examples of input-output pairs associated with this new task,
i.e.
$(\mathbf{i}_{1},\mathbf{o}_{1}),(\mathbf{i}_{2},\mathbf{o}_{2}),\cdots,(\mathbf{i}_{m},\mathbf{o}_{m})$.
We further assume that the underlying unknown intention associated with this
task is denoted as $\theta_{*}$. In other words, both the instruction
$\mathbf{x}$ and all provided examples are generated independently under the
same intention $\theta_{*}$ of this task [28]. Moreover, since these examples
correctly reflect how this task is performed, we have
$q(\mathbf{o}_{k}\,|\,\mathbf{i}_{k},\theta_{*})\approx 1$ ($\forall
k=1,2,\cdots,m$).

We have the following in-context learning results for unambiguous languages
and $\varepsilon$-ambiguous languages, respectively.

###### Proposition 2

Under the above setting, for unambiguous languages, the conditional
probability distribution of the LLM $\mathbf{\Lambda}_{*}$ given the
instruction prompt and all examples and a new case is equal to the true
conditional distribution used in language process under the common intention
$\theta_{*}$:

$p_{\Lambda_{*}}(\mathbf{y}|\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1})=q(\mathbf{y}|\mathbf{i}_{m+1},\theta_{*})$
(7)

See a detailed proof in Appendix D. Proposition 2 suggests that, if we sample
the conditional distribution of the LLM, it is equivalent to sampling the
ideal conditional distribution in language generation under the shared true
intention $\theta_{*}$ and the new input $\mathbf{i}_{i+1}$. As this
conditional distribution peaks at the correct output $\mathbf{o}_{m+1}$, i.e.
$q(\mathbf{o}_{m+1}\,|\,\mathbf{i}_{m+1},\theta_{*})\approx 1$, we will get
$\mathbf{o}_{m+1}$ at a high probability. Moreover, as we have seen at above,
for unambiguous languages, it does not help much by providing more examples
for in-context learning. Next, let’s see what may happen if we perform in-
context learning on $\varepsilon$-ambiguous languages.

###### Proposition 3

Under the same setting, for $\varepsilon$-ambiguous languages, we have

$\Big{|}p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1})-q(\mathbf{y}|\mathbf{i}_{m+1},\theta_{*})\Big{|}\leq\varepsilon(\mathbf{x})\varepsilon(\mathbf{i}_{m+1})\prod_{k=1}^{m}\varepsilon(\mathbf{i}_{k},\mathbf{o}_{k})\leq\varepsilon_{0}^{m+2}$
(8)

where $\varepsilon(\mathbf{x})$ is the ambiguity of the prompt,
$\varepsilon(\mathbf{i}_{k},\mathbf{o}_{k})$ the ambiguity of $k$-th example,
and $\varepsilon(\mathbf{i}_{m+1})$ for $\mathbf{i}_{m+1}$. Here
$\varepsilon_{0}$ stands for the maximum ambiguity among the prompt and all
examples.

See a detailed proof in Appendix E. Proposition 3 shows that LLMs deviate from
the ideal generation process due to the language ambiguity but the error bound
exponentially decreases with respect to the number of provided examples. As a
result, for ambiguous languages, we tend to have better performance if more
relevant examples are provided for few-shot in-context learning. This is
consistent with what has been observed in many in-context learning experiments
on LLMs [3].

##  6 Chain-of-Thought Prompting and Fine-tuning in LLMs

If we are given a composite argument $\mathbf{X}$, consisting of a sequence of
multiple messages as
$\mathbf{X}=\\{\mathbf{x}_{0},\mathbf{x}_{1},\cdots,\mathbf{x}_{m}\\}$, where
these messages are generated under their own intentions, i.e.,
$\\{\theta_{0},\theta_{1},\cdots,\theta_{m}\\}$. If these messages in the
argument are coherent as a sequence of reasoning steps, it represents a higher
level chain of thought, characterised by the sequence of these underlying
intentions:
$\theta_{0}\rightarrow\theta_{1}\rightarrow\cdots\rightarrow\theta_{m}$.
Empirical results have shown that it will significantly improve the chance for
LLMs to correctly arrive at the final conclusion if these intermediate
reasoning steps are explicitly specified in prompts, which is often called
chain-of-thought prompting. Here let’s use the latent space model to explain
how the chain-of-thought prompting may help LLMs to correctly infer the final
conclusion in multi-step reasoning tasks.

Similarly, we start with a simple case for unambiguous languages. Taking the
above composite argument $\mathbf{X}$ as example, assume $\mathbf{x}_{0}$ is
the question, and $\mathbf{x}_{1},\cdots,\mathbf{x}_{m-1}$ denotes all
intermediate reasoning steps, and $\mathbf{x}_{m}$ the final conclusion. If we
only prompt the question without using chain-of-thought, the probability for
an LLM to arrive at the correct conclusion is computed as:

$\displaystyle
p_{\mathbf{\Lambda}_{*}}(\mathbf{x}_{m}|\mathbf{x}_{0})=\frac{q(\mathbf{x}_{0},\mathbf{x}_{m})}{q(\mathbf{x}_{0})}=\frac{q(\theta_{0},\theta_{m})q(\mathbf{x}_{0}|\theta_{0})q(\mathbf{x}_{m}|\theta_{m})}{q(\theta_{0})q(\mathbf{x}_{0}|\theta_{0})}=q(\theta_{m}|\theta_{0})q(\mathbf{x}_{m}|\theta_{m})$
(9)

If the argument from $\mathbf{x}_{0}$ to $\mathbf{x}_{m}$ requires many
reasoning steps, the direct transition from the intention $\theta_{0}$ to
$\theta_{m}$ may be rare and under-represented in the training corpus so that
$q(\theta_{m}|\theta_{0})$ is extremely small. If we directly prompt the LLMs
as above, the chance to arrive at the correct conclusion is slim. On the other
hand, if we use the chain-of-thought prompting, the conditional probability is
computed as:

$p_{\mathbf{\Lambda}_{*}}(\mathbf{x}_{m}|\mathbf{x}_{0},\mathbf{x}_{1},\cdots,\mathbf{x}_{m-1})=\frac{q(\mathbf{x}_{0},\mathbf{x}_{1},\cdots,\mathbf{x}_{m-1},\mathbf{x}_{m})}{q(\mathbf{x}_{0},\mathbf{x}_{1},\cdots,\mathbf{x}_{m-1})}=q(\theta_{m}|\theta_{0},\cdots,\theta_{m-1})q(\mathbf{x}_{m}|\theta_{m})$

As $\theta_{m}$ is an immediate reasoning step after
$\theta_{0}\rightarrow\theta_{1}\cdots\rightarrow\theta_{m-1}$, the transition
to $\theta_{m}$ occurs more often in the training corpus, as there are many
other training examples that may follow the same reasoning chain. As a result,
the transition probabilities
$q(\theta_{m}|\theta_{0},\theta_{1},\cdots,\theta_{m-1})$ are higher since
more information is conditioned. This makes it more likely for the LLM to
arrive at $\mathbf{x}_{m}$ by going through
$\theta_{0}\rightarrow\theta_{1}\cdots\rightarrow\theta_{m-1}$ than by
transitioning directly from $\theta_{0}$ to $\theta_{m}$.

We can easily extend the above results to $\varepsilon$-ambiguous languages.

###### Proposition 4

For $\varepsilon$-ambiguous languages, the conditional probability at the
chain-of-thought prompting is bounded as follows:

$\Big{|}p_{\mathbf{\Lambda}_{*}}(\mathbf{x}_{m}|\mathbf{x}_{0},\mathbf{x}_{1},\cdots,\mathbf{x}_{m-1})-q(\theta_{m}|\theta_{0},\cdots,\theta_{m-1})q(\mathbf{x}_{m}|\theta_{m})\Big{|}\leq\varepsilon_{m}\leq\varepsilon^{m}_{0}$
(10)

where $\varepsilon_{m}=\prod_{i=0}^{m-1}\varepsilon(\mathbf{x}_{i})$ and
$\varepsilon_{0}=\max_{i=0}^{m-1}\varepsilon(\mathbf{x}_{i})$.

The proof is left out as it is similar to that of Proposition 3 in Appendix E.

Obviously, a chain of thought is applicable to not only X but also many other
seemingly different arguments as long as their messages are similarly
generated under the same sequence of intentions as
$\theta_{1}\rightarrow\theta_{2}\cdots\rightarrow\theta_{m}$. For example,
assume we have another argument that is generated along the same chain of
thought, i.e.,
$\mathbf{Y}=\\{\mathbf{y}_{1},\mathbf{x}_{2},\cdots,\mathbf{y}_{m}\\}$, based
on the latent space model, the probabilities of generating these two different
arguments can be computed as:

$\Pr(\mathbf{X})=q(\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{m})=q(\theta_{1},\theta_{2},\cdots,\theta_{m})\prod_{i=1}^{m}q(\mathbf{x}_{i}|\theta_{i})$
$\Pr(\mathbf{Y})=q(\mathbf{y}_{1},\mathbf{y}_{2},\cdots,\mathbf{y}_{m})=q(\theta_{1},\theta_{2},\cdots,\theta_{m})\prod_{i=1}^{m}q(\mathbf{y}_{i}|\theta_{i})$

Because both $\mathbf{X}$ and $\mathbf{Y}$ are two instances derived from the
same chain of thought, we can see at above that their probabilities share a
common term $q(\theta_{1},\theta_{2},\cdots,\theta_{m})$, which represents how
likely this particular chain-of-thought occurs in the language. When we add
$\mathbf{X}$ to the training set of LLMs, it increases the probability
$\Pr(\mathbf{X})$, which in turn boosts the common term
$q(\theta_{1},\theta_{2},\cdots,\theta_{m})$ more or less [22]. As long as
$q(\theta_{1},\theta_{2},\cdots,\theta_{m})$ is increased, the probabilities
of all documents generated along the same chain of thought, including
$\Pr(\mathbf{Y})$, are also boosted, even if they appear very different at the
surface level. This is why LLMs have better generalization and abstraction
capabilities than smaller machine learning models [26], and LLMs have a higher
likelihood of generalizing to unseen contexts, as long as they follow the same
chain of thought.

##  7 Aligning LLMs to Follow Instruction

Assume that an LLM $\mathbf{\Lambda}_{*}$ is prompted with an instruction
$\mathbf{x}$, which is a message generated under an unknown intention
$\theta_{\mathbf{x}}$. Let’s consider the conditional distribution of all
possible responses $\mathbf{y}$ that may be generated by the LLM under this
instruction. For unambiguous languages, we have

$p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})=\frac{q(\mathbf{x},\mathbf{y})}{q(\mathbf{x})}=\frac{\sum_{\theta^{\prime}}\sum_{\theta}q(\mathbf{x},\theta^{\prime},\mathbf{y},\theta)}{\sum_{\theta^{\prime}}q(\mathbf{x},\theta^{\prime})}=\sum_{\theta\in\mathbf{\Theta}}\;q(\theta|\theta_{\mathbf{x}})q(\mathbf{y}|\theta)$
(11)

where $\theta^{\prime}$ and $\theta$ denote the latent variables to generate
the instruction and its response.

Similarly, for $\varepsilon$-ambiguous languages, we have

$\bigg{|}p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})-\sum_{\theta\in\mathbf{\Theta}}\;q(\theta|\theta_{\mathbf{x}})q(\mathbf{y}|\theta)\bigg{|}\leq\varepsilon(\mathbf{x})$
(12)

where $\varepsilon(\mathbf{x})$ denotes the ambiguity of the instruction.

The results presented above demonstrate that when an LLM receives an
instruction $\mathbf{x}$, all possible responses follow a mixture
distribution. Each specific response is generated by first selecting an
intention $\theta$ based on the transition probability from the prompt
intention, i.e. $q(\theta|\theta_{\mathbf{x}})$. Then, a response $\mathbf{y}$
is generated by sampling the conditional distribution, i.e.
$q(\mathbf{y}|\theta)$, to reflect the selected intention. Therefore, the
underlying intention of any generated response largely depends on the
transition probability from the prompt intention, i.e.
$q(\theta|\theta_{\mathbf{x}})$. If the LLM’s training set is sufficiently
large, these transition probabilities tend to take higher values for those
intentions strongly related to the prompt intention $\theta_{\mathbf{x}}$,
whether through causation or mere association. However, some of these
intentions may be harmful or offensive, so LLMs need to be fine-tuned to avoid
generating hurtful responses [15].

To fine-tune an LLM, a number of responses to common prompts are manually
labeled as good or bad by human annotators. These labeled responses are then
used to train the LLM via reinforcement learning so that the probabilities of
generating bad responses are significantly reduced. By adjusting a single
transition probability $q(\theta|\theta_{\mathbf{x}})$, it is possible to
improve not only one particular instruction $\mathbf{x}$ but also many other
instructions generated under the same intention. This is why instruction fine-
tuning for LLMs is often very effective [15, 6].

The results in eqs. (11) and (12) suggest that the best instruction fine-
tuning strategy should focus on adjusting only the transition probabilities
$q(\theta|\theta_{\mathbf{x}})$ to inhibit bad intentions, while keeping all
conditional distributions $q(\mathbf{y}|\theta)$ intact to ensure that fluent
and high-quality responses are generated from the same distributions as the
original language generation. However, in practice, since all intentions are
unknown, it is currently unclear how to fine-tune LLMs to adjust only the
transition probabilities between intentions without affecting the intention-
conditioned distributions for language generation. This presents an
interesting research direction for future investigation.

##  8 Simulation Experiments

In order to verify the theoretical results on $\varepsilon$-ambiguous
languages, we need to create synthetic languages with explicitly known
distributions, and a simple mechanism to control the level of ambiguity. In
this paper, we propose using a doubly-embedded Markov chain model to generate
both unambiguous and $\varepsilon$-ambiguous languages. To generate the
synthetic languages, we begin by sampling an intention from a circular Markov
chain of six states that moves in one direction:
$\theta_{0}\to\theta_{1}\to\theta_{2}\to\theta_{3}\to\theta_{4}\to\theta_{5}\to\theta_{0}$.
Each state corresponds to a distinct intention, and has a 50% chance of
staying and a 50% chance of jumping to the next state. After sampling an
intention, we use another intention-specific Markov chain to generate a
message for that intention. These intention-dependent Markov chains consists
of 18 states, corresponding to 18 alphabetic letters (from a to r). To
generate unambiguous languages, we use only three distinct letters to
construct a message for each intention, such as using only $\\{a,b,c\\}$ for
$\theta_{0}$, $\\{d,e,f\\}$ for $\theta_{1}$, and so on. In this case, each
intention-dependent Markov chain has only $3\times 3$ nonzero probabilities
(corresponding to the three selected letters) in its $18\times 18$ transition
matrix. On the other hand, to generate $\varepsilon$-ambiguous languages, we
inject small amounts of noise into these sparse transition matrices so that
each letter has a small probability of jumping to other letters rather than
those dedicated to the same intention. By varying the amount of noise added to
the transition matrices, we can simulate different levels of
$\varepsilon$-ambiguity. After generating a message for a given intention
using an intention-dependent Markov chain, a newline character is appended to
signify the message’s end. After that, the next intention is selected using
the circular Markov chain, and another message is generated for that intention
in the same way. This process can be repeated as many times as desired to
generate multiple messages. The true distributions of these generated
languages can be precisely calculated from all transition matrices of the
doubly-embedded Markov chain model. Therefore, these synthetic languages can
be used in simulation experiments to verify the theoretical results on
$\varepsilon$-ambiguous languages.

###  8.1 Convergence of LLMs

For our experiments, we train a character-level GPT-like model [17] on the
synthetic languages we generated. The GPT model has three layers and about 21
million parameters. We vary the amount of training data and the block size
used by transformers in each layer. The convergence of transformer-based GPT
models is depicted in Figure 1, as a function of the amount of training data.
The models exhibit a rapid convergence on the simple synthetic language. The
left panel of the figure shows the learning curves of three transformers of
different block sizes, using the regular cross-entropy objective function
(equivalent to the negative log-likelihood function). In the right panel, the
average difference between the model distribution
$p_{\Lambda_{*}}(\mathbf{x})$ and the true distribution $q(\mathbf{x})$ is
shown when evaluated on an independent validation set. The results clearly
indicate that the gap between these two probability distributions reduces
quickly as the transformer models observe more training data. Interestingly,
transformers model the true distribution slightly better with a larger block
size, even though this does not increase the number of model parameters.

Figure 1: Illustration of the convergence of the transformer-based LLMs as
more and more training data is added. Left: the cross-entropy objective
functions. Right: The average difference between the probability distributions
$p_{\Lambda_{*}}(\mathbf{x})$ and $q(\mathbf{x})$ on an unseen validation set.

Figure 2: Illustration of language understanding (left) and in-context
learning (right) of LLMs on synthetic languages with various levels of
ambiguity.

###  8.2 Language Understanding with LLMs

To validate Proposition 1, we first use the trained language model to generate
a partial message $\mathbf{x}$ based on an intention
$\mathbf{\theta}_{\mathbf{x}}$. We then prompt the LLM with the partial
message $\mathbf{x}$ and calculate the KL divergence between the model’s
conditional distribution $p_{\Lambda_{*}}(\mathbf{y}|\mathbf{x})$ and the true
conditional distribution on the underlying intention
$q(\mathbf{y}|\mathbf{x},\mathbf{\theta}_{\mathbf{x}})$. In the left of Figure
2, the average KL divergence of three languages with varying levels of
ambiguity is displayed, demonstrating that the gap is small for unambiguous
languages and slightly increases as the languages become more ambiguous.

###  8.3 In-Context Learning in LLMs

To verify the results presented in Propositions 2 and 3 regarding in-context
learning, we follow a two-step process. Firstly, we generate multiple messages
based on the same intention using the trained model. Then, we concatenate
these messages to create a single prompt for the LLM. We then compare the KL
divergence between the model’s conditional distribution and the true
distribution under the correct intention as a function of the number of
independent messages in the prompt. The results, as shown in the right panel
of Figure 2, demonstrate that the average KL divergence remains small and
constant for unambiguous languages, but increases for $\varepsilon$-ambiguous
languages. However, the gap for $\varepsilon$-ambiguous languages can be
reduced by adding more messages to the prompt.

##  9 Final Remarks

In this paper, we have presented a novel latent space theory that explains the
remarkable capabilities of LLMs. Our theory categorizes languages as either
unambiguous or $\varepsilon$-ambiguous, and establishes quantitative results
that attribute the LLMs’ emergent abilities to their unique approach for
exploring sparse structures in joint distributions through being a universal
approximator of the marginal distribution. Simulation experiments on synthetic
data have confirmed our findings related to language ambiguity. Moreover, our
theory can explain many other observations in LLMs beyond what we have
discussed in this paper. For instance, unlike autoregressive language models,
emergent abilities do not occur in masked language models or bi-directional
language models because they do not precisely model the marginal distribution
of text data.

## References

  * Asadi and Jiang [2020] Behnam Asadi and Hui Jiang.  On approximation capabilities of relu activation and softmax output layer in neural networks.  In _preprint arXiv:2002.04060_ , 2020.  URL https://arxiv.org/abs/2002.04060.
  * Blei et al. [2003] David M. Blei, Andrew Y. Ng, and Michael I. Jordan.  Latent dirichlet allocation.  _Journal of Machine Learning Research_ , 3:993–1022, March 2003.  ISSN 1532-4435.  URL https://www.jmlr.org/papers/volume3/blei03a/blei03a.pdf.
  * Brown et al. [2020] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In _preprint arXiv:2005.14165_ , 2020.  URL https://arxiv.org/abs/2005.14165.
  * Chan et al. [2022] Stephanie C. Y. Chan, Adam Santoro, Andrew K. Lampinen, Jane X. Wang, Aaditya Singh, Pierre H. Richemond, Jay McClelland, and Felix Hill.  Data distributional properties drive emergent in-context learning in transformers.  In _preprint arXiv:2205.05055_ , 2022.  URL https://arxiv.org/abs/2205.05055.
  * Chowdhery et al. [2022] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel.  Palm: Scaling language modeling with pathways.  In _preprint arXiv:2204.02311_ , 2022.  URL https://arxiv.org/abs/2204.02311.
  * Chung et al. [2022] Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Alex Castro-Ros, Marie Pellat, Kevin Robinson, Dasha Valter, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei.  Scaling instruction-finetuned language models.  In _preprint arXiv:2210.11416_ , 2022.  URL https://arxiv.org/abs/2210.11416.
  * Hahn and Goyal [2023] Michael Hahn and Navin Goyal.  A theory of emergent in-context learning as implicit structure induction.  In _preprint arXiv:2303.07971_ , 2023.  URL https://arxiv.org/abs/2303.07971.
  * Hogg et al. [2019] Robert Hogg, Joseph W. McKean, and Allen T. Craig.  _Introduction to Mathematical Statistics_.  Pearson., 2019.  ISBN 9781292264769.  URL https://books.google.ca/books?id=wz0QyQEACAAJ.
  * Jiang [2019] Hui Jiang.  Why learning of large-scale neural networks behaves like convex optimization.  In _preprint arXiv:1903.02140_ , 2019.  URL https://arxiv.org/abs/1903.02140.
  * Jiang [2021] Hui Jiang.  _Machine Learning Fundamentals_.  Cambridge University Press, 2021.  URL https://books.google.ca/books?id=jSFGEAAAQBAJ.
  * Lehmann and Casella [1998] Erich L. Lehmann and George Casella.  _Theory of Point Estimation_.  Springer-Verlag, New York, NY, USA, second edition, 1998.  URL https://books.google.ca/books?id=4f24CgAAQBAJ.
  * Liu et al. [2021] Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen.  What makes good in-context examples for GPT-$3$?  In _preprint arXiv:2101.06804_ , 2021.  URL https://arxiv.org/abs/2101.06804.
  * Miller et al. [1994] Scott Miller, Robert Bobrow, Robert Ingria, and Richard Schwartz.  Hidden understanding models of natural language.  ACL ’94, page 25–32, USA, 1994. Association for Computational Linguistics.  doi: 10.3115/981732.981736.  URL https://doi.org/10.3115/981732.981736.
  * Min et al. [2022] Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer.  Rethinking the role of demonstrations: What makes in-context learning work?  In _preprint arXiv:2202.12837_ , 2022.  URL https://arxiv.org/abs/2202.12837.
  * Ouyang et al. [2022] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe.  Training language models to follow instructions with human feedback.  In _preprint arXiv:2203.02155_ , 2022.  URL https://arxiv.org/abs/2203.02155.
  * Pieraccini and Levin [1992] Roberto Pieraccini and Esther Levin.  Stochastic representation of semantic structure for speech understanding.  _Speech Communication_ , 11(2):283–288, 1992\.  ISSN 0167-6393.  doi: https://doi.org/10.1016/0167-6393(92)90022-Y.  URL https://www.sciencedirect.com/science/article/pii/016763939290022Y.  Eurospeech ’91.
  * Radford et al. [2018a] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving language understanding by generative pre-training.  2018a.
  * Radford et al. [2018b] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners.  2018b.
  * Raffel et al. [2020] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  In _preprint arXiv:1910.10683_ , 2020.  URL https://arxiv.org/abs/1910.10683.
  * Razeghi et al. [2022] Yasaman Razeghi, Robert L. Logan IV au2, Matt Gardner, and Sameer Singh.  Impact of pretraining term frequencies on few-shot reasoning.  In _preprint arXiv:2202.07206_ , 2022.  URL https://arxiv.org/abs/2202.07206.
  * Rubin et al. [2022] Ohad Rubin, Jonathan Herzig, and Jonathan Berant.  Learning to retrieve prompts for in-context learning.  In _preprint arXiv:2112.08633_ , 2022.  URL https://arxiv.org/abs/2112.08633.
  * Sanh et al. [2022] Victor Sanh, Albert Webson, Colin Raffel, Stephen H. Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, Manan Dey, M Saiful Bari, Canwen Xu, Urmish Thakker, Shanya Sharma Sharma, Eliza Szczechla, Taewoon Kim, Gunjan Chhablani, Nihal Nayak, Debajyoti Datta, Jonathan Chang, Mike Tian-Jian Jiang, Han Wang, Matteo Manica, Sheng Shen, Zheng Xin Yong, Harshit Pandey, Rachel Bawden, Thomas Wang, Trishala Neeraj, Jos Rozen, Abheesht Sharma, Andrea Santilli, Thibault Fevry, Jason Alan Fries, Ryan Teehan, Tali Bers, Stella Biderman, Leo Gao, Thomas Wolf, and Alexander M. Rush.  Multitask prompted training enables zero-shot task generalization.  In _preprint arXiv:2110.08207_ , 2022.  URL https://arxiv.org/abs/2110.08207.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://arxiv.org/abs/1706.03762.
  * Wang et al. [2023] Xinyi Wang, Wanrong Zhu, and William Yang Wang.  Large language models are implicitly topic models: Explaining and finding good demonstrations for in-context learning.  In _preprint arXiv:2301.11916_ , 2023.  URL https://arxiv.org/abs/2301.11916.
  * Wei et al. [2022a] Colin Wei, Sang Michael Xie, and Tengyu Ma.  Why do pretrained language models help in downstream tasks? an analysis of head and prompt tuning.  In _preprint arXiv:2106.09226_ , 2022a.  URL https://arxiv.org/abs/2106.09226.
  * Wei et al. [2022b] Jason Wei, Maarten Bosma, Vincent Y. Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M. Dai, and Quoc V. Le.  Finetuned language models are zero-shot learners.  In _preprint arXiv:2109.01652_ , 2022b.  URL https://arxiv.org/abs/2109.01652.
  * Wei et al. [2022c] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus.  Emergent abilities of large language models.  In _preprint arXiv:2206.07682_ , 2022c.  URL https://arxiv.org/abs/2206.07682.
  * Xie et al. [2022] Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma.  An explanation of in-context learning as implicit bayesian inference.  In _preprint arXiv:2111.02080_ , 2022.  URL https://arxiv.org/abs/2111.02080.
  * Yun et al. [2020] Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar.  Are transformers universal approximators of sequence-to-sequence functions?  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=ByxRM0Ntvr.

Appendix

##  Appendix A The sparsity property of the joint distribution of languages

For any unambiguous language, we have

$\displaystyle\Pr(\theta_{0}|\mathbf{x})=1\;\;$ $\displaystyle\Longrightarrow$
$\displaystyle\;\;\Pr(\theta_{0}|\mathbf{x})=\frac{q(\theta_{0},\mathbf{x})}{q(\mathbf{x})}=1$
(15) $\displaystyle\implies$ $\displaystyle
q(\mathbf{x})=q(\theta_{0},\mathbf{x})$ $\displaystyle\implies$ $\displaystyle
q(\theta,\mathbf{x})=\left\\{\begin{array}[]{cc}q(\mathbf{x})&\theta=\theta_{0}\\\
0&\theta\neq\theta_{0}\end{array}\right.$

For an $\varepsilon$-ambiguous language, we have

$\displaystyle\Pr(\theta_{0}|\mathbf{x})\geq 1-\varepsilon(\mathbf{x})$
$\displaystyle\Longrightarrow$
$\displaystyle\;\Pr(\theta_{0}|\mathbf{x})=\frac{q(\theta_{0},\mathbf{x})}{q(\mathbf{x})}\geq
1-\varepsilon(\mathbf{x})$ $\displaystyle\Longrightarrow$
$\displaystyle\;q(\theta_{0},\mathbf{x})\geq\big{(}1-\varepsilon(\mathbf{x})\big{)}q(\mathbf{x})$
$\displaystyle\Longrightarrow$ $\displaystyle
q(\theta_{0},\mathbf{x})\geq\big{(}1-\varepsilon(\mathbf{x})\big{)}\Big{(}q(\theta_{0},\mathbf{x})+q(\Theta\backslash\theta_{0},\mathbf{x})\Big{)}$
$\displaystyle\Longrightarrow$
$\displaystyle\frac{q(\theta_{0},\mathbf{x})}{q(\Theta\backslash\theta_{0},\mathbf{x})}\geq\frac{1-\varepsilon(\mathbf{x})}{\varepsilon(\mathbf{x})}\approx\frac{1}{\varepsilon(\mathbf{x})}$

where $\Theta\backslash\theta_{0}$ denotes a complement set containing all
elements in $\Theta$ except $\theta_{0}$, and
$q(\Theta\backslash\theta_{0},\mathbf{x})$ is defined as the total residue
after the contribution of the intention $\theta_{0}$ is taken out:

$q(\Theta\backslash\theta_{0},\mathbf{x})\overset{\Delta}{=}\sum_{\theta\in\mathbf{\Theta},\theta\neq\theta_{0}}\;q(\theta,\mathbf{x})=q(\mathbf{x})-q(\theta_{0},\mathbf{x})$

##  Appendix B Proof of Theorem 1

As the consistency is a well-accepted property of maximum likelihood
estimation (MLE), the result in Theorem 1 should not be too surprised.

Firstly, due to that the model $p_{\mathbf{\Lambda}}(\mathbf{x})$ is a
universal density approximator, for any given distribution $q(\mathbf{x})$,
there exists a set of model parameters, denoted as $\Lambda_{*}$, to make
$p_{\Lambda_{*}}(\mathbf{x})=q(\mathbf{x})$ hold for all $\mathbf{x}$.

Secondly, we define an expected log-likelihood function as follows:

$l(\Lambda)=\int_{\mathbf{x}}q(\mathbf{x})\ln
p_{\Lambda}(\mathbf{x})d\mathbf{x}=\int_{\mathbf{x}}p_{\Lambda_{*}}(\mathbf{x})\ln
p_{\Lambda}(\mathbf{x})d\mathbf{x}$

Based on Jensen’s inequality, for any $\Lambda\neq\Lambda_{*}$, we have
$l(\Lambda)\leq l(\Lambda_{*})$ because of

$\int_{\mathbf{x}}p_{\Lambda_{*}}(\mathbf{x})\ln
p_{\Lambda}(\mathbf{x})d\mathbf{x}-\int_{\mathbf{x}}p_{\Lambda_{*}}(\mathbf{x})\ln
p_{\Lambda_{*}}(\mathbf{x})d\mathbf{x}\leq 0$

Therefore, $\Lambda_{*}$ is the maximum point of the above function
$l(\Lambda)$, i.e. $l(\Lambda_{*})=\max_{\Lambda}l(\Lambda)$.

Thirdly, the maximum likelihood estimation $\Lambda_{n}$ is the maximum point
of the following empirical log-likelihood function:

$l_{n}(\Lambda)=\frac{1}{n}\sum_{i=1}^{n}\ln p_{\Lambda}(\mathbf{x}_{i})$

where $\\{\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{n}\\}$ are $n$
i.i.d. samples randomly drawn from the distribution
$p_{\mathbf{\Lambda_{*}}}(\mathbf{x})$. According to the law of large numbers,
we have

$\lim_{n\to\infty}l_{n}(\Lambda)=l(\Lambda)$

As a result, the maximum value of $l_{n}(\Lambda)$ converges to the maximum
value of $l(\Lambda)$. That is

$\lim_{n\to\infty}\max_{\Lambda}\;l_{n}(\Lambda)=\max_{\Lambda}l(\Lambda)=l(\Lambda_{*})$

At last, because neural networks, including transformer models, usually do not
satisfy the identification requirement, we can not immediately conclude
$\Lambda_{n}\to\Lambda_{*}$ as $n\to\infty$. Following the technique in [9],
under the condition of over-parameterization, the model can be mapped to a
canonical model space where the identification requirement holds. By doing
that, we conclude that if the model is sufficiently large, some simple
optimization methods, such as stochastic gradient descent, will ensure that
$\Lambda_{n}$ converges to a point that achieves the same objective function
values as $l(\Lambda_{*})$. In other words, it converges to a model that is at
least as good as $\Lambda_{*}$.

##  Appendix C Proof of Proposition 1

We first start with the conditional distribution of the LLM
$\mathbf{\Lambda}_{*}$ as:

$\displaystyle p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})$
$\displaystyle=$
$\displaystyle\frac{p_{\mathbf{\Lambda}_{*}}(\mathbf{x},\mathbf{y})}{p_{\mathbf{\Lambda}_{*}}(\mathbf{x})}=\frac{q(\mathbf{x},\mathbf{y})}{q(\mathbf{x})}$
$\displaystyle=$
$\displaystyle\frac{q(\mathbf{x},\theta_{\mathbf{x}},\mathbf{y})+\sum_{\theta\neq\theta_{\mathbf{x}}}q(\mathbf{x},\theta,\mathbf{y})}{q(\mathbf{x},\theta_{\mathbf{x}})+\sum_{\theta\neq\theta_{\mathbf{x}}}q(\mathbf{x},\theta)}$
$\displaystyle=$
$\displaystyle\frac{q(\mathbf{x},\theta_{\mathbf{x}},\mathbf{y})+\sum_{\theta\neq\theta_{\mathbf{x}}}q(\mathbf{x},\theta)q(\mathbf{y}|\mathbf{x},\theta)}{q(\mathbf{x},\theta_{\mathbf{x}})+\sum_{\theta\neq\theta_{\mathbf{x}}}q(\mathbf{x},\theta)}$

Due to $0\leq q(\mathbf{y}|\mathbf{x},\theta))\leq 1$, we have

$\frac{q(\mathbf{x},\theta_{\mathbf{x}},\mathbf{y})}{q(\mathbf{x},\theta_{\mathbf{x}})+\sum_{\theta\neq\theta_{\mathbf{x}}}q(\mathbf{x},\theta)}\leq
p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})\leq\frac{q(\mathbf{x},\theta_{\mathbf{x}},\mathbf{y})+\sum_{\theta\neq\theta_{\mathbf{x}}}q(\mathbf{x},\theta)}{q(\mathbf{x},\theta_{\mathbf{x}})+\sum_{\theta\neq\theta_{\mathbf{x}}}q(\mathbf{x},\theta)}$

If we denote
$\delta=\frac{\sum_{\theta\neq\theta_{\mathbf{x}}}q(\mathbf{x},\theta)}{q(\mathbf{x},\theta_{\mathbf{x}})}$,
then we have

$\frac{q(\mathbf{y}|\mathbf{x},\theta_{\mathbf{x}})}{1+\delta}\leq
p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})\leq\frac{q(\mathbf{y}|\mathbf{x},\theta_{\mathbf{x}})+\delta}{1+\delta}$

According to the sparsity property of $\varepsilon$-ambiguous languages, we
have $0\leq\delta\leq\varepsilon(\mathbf{x})$. As a result, we have

$\frac{q(\mathbf{y}|\mathbf{x},\theta_{\mathbf{x}})}{1+\varepsilon(\mathbf{x})}\leq
p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})\leq
q(\mathbf{y}|\mathbf{x},\theta_{\mathbf{x}})+\varepsilon(\mathbf{x})$

Due to $\frac{1}{1+\varepsilon}>1-\varepsilon$, we have

$\Big{|}p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x})-q(\mathbf{y}|\mathbf{x},\theta_{\mathbf{x}})\Big{|}\leq\varepsilon(\mathbf{x})$

##  Appendix D Proof of Proposition 2

Here we assume the language generation is unambiguous. Let’s consider how the
LLMs will compute the following conditional probability given the prompt
$\mathbf{x}$, all examples
$\\{\mathbf{i}_{k},\mathbf{o}_{k}\,|\,k=1,2,\cdots,m\\}$, and an new input
$\mathbf{i}_{m+1}$ for the same task. Note that all these conditions are
generated under the same intention but they are independent as they are not
generated by conditioning each other. However, the reply $\mathbf{y}$ is not
independent from these conditions because $\mathbf{y}$ is generated
conditioning on all of them.

$\displaystyle
p_{\Lambda_{*}}(\mathbf{y}|\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1})$
$\displaystyle=\frac{p_{\Lambda_{*}}\big{(}\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1},\mathbf{y}\big{)}}{p_{\Lambda_{*}}\big{(}\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1}\big{)}}$
$\displaystyle=\frac{q\big{(}\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1},\mathbf{y}\big{)}}{q\big{(}\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1}\big{)}}$
$\displaystyle=\frac{\sum_{\theta_{0},\theta_{1},\cdots,\theta_{m}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\theta_{m},\mathbf{i}_{m+1},\mathbf{y}\big{)}}{\sum_{\theta_{0},\theta_{1},\cdots,\theta_{m}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\theta_{m},\mathbf{i}_{m+1}\big{)}}$
$\displaystyle=\frac{\sum_{\theta_{0},\theta_{1},\cdots,\theta_{m}}q(\mathbf{x},\theta_{0})\prod_{k=1}^{m}q(\mathbf{i}_{k},\mathbf{o}_{k},\theta_{k})q(\mathbf{i}_{m+1},\mathbf{y}|\theta_{0},\cdots,\theta_{m})}{\sum_{\theta_{0},\theta_{1},\cdots,\theta_{m}}q(\mathbf{x},\theta_{0})\prod_{k=1}^{m}q(\mathbf{i}_{k},\mathbf{o}_{k},\theta_{k})q(\mathbf{i}_{m+1}|\theta_{0},\cdots,\theta_{m})}$
$\displaystyle=\frac{q(\mathbf{x},\theta_{*})\prod_{k=1}^{m}q(\mathbf{i}_{k},\mathbf{o}_{k},\theta_{*})q(\mathbf{i}_{m+1},\mathbf{y}|\theta_{*})}{q(\mathbf{x},\theta_{*})\prod_{k=1}^{m}q(\mathbf{i}_{k},\mathbf{o}_{k},\theta_{*})q(\mathbf{i}_{m+1}|\theta_{*})}=\frac{p(\mathbf{i}_{m+1},\mathbf{y}|\theta_{*})}{q(\mathbf{i}_{m+1}|\theta_{*})}$
$\displaystyle=q(\mathbf{y}|\mathbf{i}_{m+1},\theta_{*})$

At the above, we have applied the sparsity property of unambiguous languages
in eq.(3) because the prompt and all examples are generated under the same
intention $\theta_{*}$. For all other intentions $\theta\neq\theta_{*}$, we
have $q(\mathbf{x},\theta)=0$, and
$q(\mathbf{i}_{k},\mathbf{o}_{k},\theta)=0$, and
$q(\mathbf{i}_{k+1},\theta)=0$.

##  Appendix E Proof of Proposition 3

For $\varepsilon$-ambiguous languages, as in Appendix D, we still can derive:

$\displaystyle
p_{\Lambda_{*}}(\mathbf{y}|\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1})$
$\displaystyle=\frac{\sum_{\theta_{0},\theta_{1},\cdots,\theta_{m+1}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\theta_{m},\mathbf{i}_{m+1},\theta_{m+1},\mathbf{y}\big{)}}{\sum_{\theta_{0},\theta_{1},\cdots,\theta_{m+1}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\theta_{m},\mathbf{i}_{m+1},\theta_{m+1}\big{)}}$
$\displaystyle=\frac{q\big{(}\mathbf{x},\theta_{*},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{*},\cdots,\mathbf{i}_{m+1},\theta_{*},\mathbf{y}\big{)}+\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m+1},\theta_{m+1},\mathbf{y}\big{)}}{q\big{(}\mathbf{x},\theta_{*},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{*},\cdots,\mathbf{i}_{m+1},\theta_{*}\big{)}+\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m+1},\theta_{m+1}\big{)}}$
(16)
$\displaystyle\leq\frac{q\big{(}\mathbf{x},\theta_{*},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{*},\cdots,\mathbf{i}_{m+1},\theta_{*},\mathbf{y}\big{)}+\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m+1},\theta_{m+1}\big{)}}{q\big{(}\mathbf{x},\theta_{*},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{*},\cdots,\mathbf{i}_{m+1},\theta_{*}\big{)}+\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m+1},\theta_{m+1}\big{)}}$
$\displaystyle=\frac{q(\mathbf{y}|\mathbf{i}_{m+1},\theta_{*})+\overbrace{\frac{\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\theta_{m},\mathbf{i}_{m+1}\big{)}}{q\big{(}\mathbf{x},\theta_{*},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{*},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\theta_{*},\mathbf{i}_{m+1}\big{)}}}^{=\eta}}{1+\underbrace{\frac{\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\theta_{m},\mathbf{i}_{m+1}\big{)}}{q\big{(}\mathbf{x},\theta_{*},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{*},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\theta_{*},\mathbf{i}_{m+1}\big{)}}}_{=\eta}}$

At above, we have applied the following inequality:

$\displaystyle\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m+1},\theta_{m+1},\mathbf{y}\big{)}$
$\displaystyle=\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m+1},\theta_{m+1}\big{)}q(\mathbf{y}|\theta_{0},\cdots,\theta_{m+1})$
$\displaystyle\leq\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m+1},\theta_{m+1}\big{)}\;\;\;\;\;\;[\mbox{
due to }q(\mathbf{y}|\theta_{0},\cdots,\theta_{m+1})\leq 1]$

We further consider $\eta$:

$\displaystyle 0\leq\eta$ $\displaystyle=$
$\displaystyle\frac{\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m+1},\theta_{m+1}\big{)}}{q\big{(}\mathbf{x},\theta_{*},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{*},\cdots,\mathbf{i}_{m+1},\theta_{m+1}\big{)}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q(\mathbf{x},\theta_{0})\prod_{k=1}^{m}q(\mathbf{i}_{k},\mathbf{o}_{k},\theta_{k})q(\mathbf{i}_{m+1},\theta_{m+1})}{q(\mathbf{x},\theta_{*})\prod_{k}^{m}q(\mathbf{i}_{k},\mathbf{o}_{k},\theta_{*})q(\mathbf{i}_{m+1},\theta_{*})}$
$\displaystyle=$
$\displaystyle\frac{\sum_{\theta_{0}\neq\theta_{*}}q(\mathbf{x},\theta_{0})}{q(\mathbf{x},\theta_{*})}\prod_{k=1}^{m}\frac{\sum_{\theta_{k}\neq\theta_{*}}q(\mathbf{i}_{k},\mathbf{o}_{k},\theta_{k})}{q(\mathbf{i}_{k},\mathbf{o}_{k},\theta_{*})}\frac{\sum_{\theta_{m+1}\neq\theta_{*}}q(\mathbf{i}_{m+1},\theta_{m+1})}{q(\mathbf{i}_{m+1},\theta_{*})}$
$\displaystyle\leq$
$\displaystyle\varepsilon(\mathbf{x})\varepsilon(\mathbf{i}_{m+1})\prod_{k=1}^{m}\varepsilon(\mathbf{i}_{k},\mathbf{o}_{k})\leq\varepsilon_{0}^{m+2}$

where $\varepsilon_{0}$ denotes the maximum ambiguity among the prompt and all
examples.

On the other hand, due to

$\sum_{\theta_{0}\neq\theta_{*},\cdots,\theta_{m+1}\neq\theta_{*}}q\big{(}\mathbf{x},\theta_{0},\mathbf{i}_{1},\mathbf{o}_{1},\theta_{1},\cdots,\mathbf{i}_{m+1},\theta_{m+1},\mathbf{y}\big{)}\geq
0$

we can derive the lower bound of eq.(16) as follows:

$p_{\Lambda_{*}}(\mathbf{y}|\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1})\geq\frac{q(\mathbf{y}|\mathbf{i}_{m+1},\theta_{*})}{1+\eta}$

Similar to the last step in Appendix C, for $\varepsilon$-ambiguous languages,
we finally have

$\Big{|}p_{\mathbf{\Lambda}_{*}}(\mathbf{y}|\mathbf{x},\mathbf{i}_{1},\mathbf{o}_{1},\cdots,\mathbf{i}_{m},\mathbf{o}_{m},\mathbf{i}_{m+1})-q(\mathbf{y}|\mathbf{i}_{m+1},\theta_{*})\Big{|}\leq\varepsilon(\mathbf{x})\varepsilon(\mathbf{i}_{m+1})\prod_{k=1}^{m}\varepsilon(\mathbf{i}_{k},\mathbf{o}_{k})\leq\varepsilon_{0}^{m+2}$

##  Appendix F More Details on Experimental Settings

###  F.1 Data Generation

We use a 6-state circular Markov chain, as shown in Figure 3, to model the
prior distribution of intentions, i.e. $q(\theta)$, in the step one of the
latent space model for language generation. Each state corresponds to a
distinct intention. As a result, the latent space $\mathbf{\Theta}$ consists
of only 6 elements.

Figure 3: A 6-state circular Markov chain model is used to simulate the prior
intention distribution $q(\theta)$ in the latent space model for language
generation.

Given each intention, we use another intention-specific Markov chain to
generate a message for it. These intention-dependent Markov chains consists of
18 states, corresponding to 18 alphabetic letters (from a to r). To generate
unambiguous languages, we use only three distinct letters to construct a
message for each intention, i.e. only using $\\{a,b,c\\}$ for $\theta_{0}$,
$\\{d,e,f\\}$ for $\theta_{1}$, $\\{g,h,i\\}$ for $\theta_{2}$, $\\{j,k,l\\}$
for $\theta_{3}$, $\\{m,n,o\\}$ for $\theta_{4}$, and $\\{p,q,r\\}$ for
$\theta_{5}$. In this case, each intention-dependent Markov chain has only
$3\times 3$ nonzero probabilities (corresponding to the three selected
letters) in its $18\times 18$ transition matrix. On the other hand, to
generate $\varepsilon$-ambiguous languages, we inject small amounts of noise
into these sparse transition matrices so that each letter has a small
probability of jumping to other letters rather than those dedicated to the
same intention. By varying the amount of noise added to the transition
matrices, we can simulate different levels of ambiguity. After generating a
message for a given intention using an intention-dependent Markov chain, a
newline character is appended to signify the message’s end. For the sake of
simplicity, we generate all messages under the assumption that every message
has a consistent length, comprised of 20 letters and one newline character.
After each message is generated, using the circular Markov chain, the next
intention will be selected, and another message will be generated for that
intention in the same way. This process can be repeated as many times as
desired to generate any number of messages.

Some unambiguous messages generated in this way are shown below as an example:

    ...
    qqpqrqrqqqqrrqprqqqqq
    abccbacbaabbbbcaaacba
    effeffeeffffffffeffff
    fefffffeddddfeeffffff
    deeedfedeffeedfffffff
    hgiiiiiiigihgihgiihih
    jjjklkjjkjkjkjkllkkkk
    kjkkkllkjkjjjkllljkkk
    omnoononmnononommonom
    nonoonomnnoonomnononm
    rrqprrrqpqrqqprqrrrqp
    baaabaaacacaabaaaaaac
    baacaacbaaaaabaabbaca
    caaacbabbacaaccaaabca
    cabacbcabbaaccccacaaa
    ...

Some generated ambiguous messages ($\varepsilon=0.06$) are shown below as an
example:

    ...
    qqqqqqafdrqqqppribmmf
    aagaaaraaojogikfdjone
    aaahdnbabcadnkdggkkep
    cmjjfdiqhaacmbcnpaajr
    deeffedelokhhhdffemef
    iiiiihhghcoqqcpbliiig
    ghigkabkecemgjkeefbii
    iihqbrghghhhghghkmnpn
    kfgoaqdgholkljkhondjc
    oblohjfnnmnanhjbhonom
    nfkpjgqoomaibpragedak
    qrqrrprqhehdloajilopq
    rlljmprrqqrrhgrrqqqpr
    rqhijkpjmkcmlfeicopnr
    ...

Finally, some more ambiguous messages ($\varepsilon=0.11$) are shown below as
an example:

    ...
    diporcqddofiffeffdqnc
    fafnakjcdmcdbfeoqaeff
    dedfepnddedenpaghceer
    ededlapbnpipnirkpqqan
    eialkcpfefopqojpmrffe
    ffeddefcaaffipkbcohak
    dffederonkqldeemkaclp
    djhfpbrbjpkpcgnjhamke
    efjnhlhdeddeffeeeffoi
    ebchiqcjfbrihlqipdedd
    gholgghgilchgjrobmrrk
    lkqdhfdriqjklkkjlfbmm
    lcjkjkllljlllkkjlkihn
    lklnkepaojjjpqaarbrpa
    lnrhmpbpmchhhdampekjj
    llklkkjkrcpbliqhaaqgh
    jbbklkjjllcbijkkkerge
    ...

###  F.2 Model Training

In our experiments, we train a character-level GPT-like model [17], similar to
the nanoGPT model111nanoGPT: https://github.com/karpathy/nanoGPT, on the
generated synthetic languages using the ADAM algorithm on a GTX1080 Ti GPU
with 12GB memory. During the training process, the learning rates are
automatically decayed according to a preset annealing schedule. All training
hyper-parameters for the GPT model structure and the optimizer settings are
given in Table 1.

All codes used in this work are available at
https://github.com/iNCML/LLM_Simulation.

model structure
---
number of layers | 3
number of head | 12
head size | 64
block size | 32, 64, or 128
number of model parameters | 21.25 million
optimizer
initial learning rate | $6.0\times 10^{-4}$
minibatch size | 12
$\beta_{1}$ | $0.9$
$\beta_{2}$ | $0.95$
maximum iterations | 5000
Table 1: All hyperparameters used in the training process for a GPT-like
language model.


# Strongly generating elements
in finite and profinite groups

Eloisa Detomi  Dipartimento di Ingegneria dell’Informazione - DEI, Università
di Padova, Via G. Gradenigo 6/B, 35121 Padova, Italy<EMAIL_ADDRESS>and  Andrea Lucchini  Dipartimento di Matematica “Tullio Levi Civita”,
Università di Padova, Via Trieste 63, 35121 Padova, Italy
<EMAIL_ADDRESS>
###### Abstract.

Given a finite group $G$ and an element $g\in G$, we may compare the expected
number $e(G)$ of elements needed to generate $G$ and the expected number
$e(G,g)$ of elements of $G$ needed to generate $G$ together with $g.$ We
address the following question: how large can the difference $e(G)-e(G,g)$ be?

###### Key words and phrases:

groups generation; waiting time; profinite groups

###### 1991 Mathematics Subject Classification:

20P05

##  1\. introduction

Let $G$ be a nontrivial finite group and let $x=(x_{n})_{n\in\mathbb{N}}$ be a
sequence of independent, uniformly distributed $G$-valued random variables.
Let $Y$ be a subset of $G.$ We may define a random variable $\tau_{G,Y}$ (a
waiting time) by

$\tau_{G,Y}=\min\\{n\geq 1\mid\langle
Y,x_{1},\dots,x_{n}\rangle=G\\}\in[0,+\infty].$

Since $\tau_{G,Y}>n$ if and only if $\langle Y,x_{1},\dots,x_{n}\rangle\neq
G$, $P(\tau_{G,Y}>n)=1-P_{G,Y}(n),$ denoting by

$P_{G,Y}(n)=\frac{|\\{(g_{1},\dots,g_{n})\in G^{n}\mid\langle
g_{1},\dots,g_{n},Y\rangle=G\\}|}{|G|^{n}}$

the probability that $n$ randomly chosen elements of $G$ generate $G$ together
with the elements of $Y.$ We denote by $e(G,Y)$ the expectation
$\operatorname{E}(\tau_{G,Y})$ of this random variable. In other word $e(G,Y)$
is the expected number of elements of $G$ which have to be drawn at random,
with replacement, before a set is found with the property that its union with
$Y$ generates $G.$ When $Y=\varnothing,$ we just write $e(G)$ and $P_{G}(n)$
instead of $e(G,Y)$ and $P_{G,Y}(n).$

It follows from [10, Theorem 11] that $e(G,Y)$ can be directly determined
using the Möbius function defined on the subgroup lattice of $G$ by setting
$\mu_{G}(G)=1$ and $\mu_{G}(H)=-\sum_{H<K}\mu_{G}(K)$ for any $H<G$. Indeed
the following formula holds:

$e(G,Y)=-\sum_{Y\leq H<G}\frac{\mu_{G}(H)|G|}{|G|-|H|}.$

Consider the particular case when $Y=\\{g\\}$ is a singleton. In this case we
just write $e(G,g)$. Clearly $e(G,g)\leq e(G)$ (with equality if and only if
$g$ belongs to the Frattini subgroup of $G$). The question that we want to
address in this paper is whether there are elements $g$ with the property that
$e(G,g)$ is “much smaller” of $e(G)$. We call these element “strongly
generating elements”.

To discuss this problem, it is useful to highlight the relation between
$e(G,Y)$ and another invariant related with the enumeration of the maximal
subgroups of $G.$ For $n\in\mathbb{N},$ denote by $m_{n}(G,Y)$ the number of
maximal subgroups of $G$ with index $n$ and containing $Y$. Let

$\mathcal{M}(G,Y)=\sup_{n\geq 2}\frac{\log(m_{n}(G,Y))}{\log(n)}.$

Actually ${\mathcal{M}}(G)={\mathcal{M}}(G,\varnothing)$ is the “polynomial
degree” of the rate of growth of $m_{n}(G,\varnothing)$. This rate has been
studied for finite and profinite groups by several authors, including Mann,
Shalev, Borovik, Jaikin-Zapirain and Pyber (see [2], [8], [12], [13]).

In [11, Theorem 1], improving an argument used by Lubotzky [9], it is proved
that $\lceil\mathcal{M}(G)\rceil-4\leq e(G)\leq\lceil\mathcal{M}(G)\rceil+3$
for any finite group $G$. With precisely the same argument the following more
general statement can be proved:

######  Theorem 1.

Let $G$ be a finite group and $Y$ a subset of $G$. Then

$\lceil\mathcal{M}(G,Y)\rceil-4\leq e(G,Y)\leq\lceil\mathcal{M}(G,Y)\rceil+3.$

If follows immediately:

######  Corollary 2.

Let $G$ be a finite group. If $g\in G,$ then

$e(G)-e(G,g)\leq\mathcal{M}(G)-\mathcal{M}(G,g)+8.$

Our first application of Corollary 2 is to show that the difference
$e(G)-e(G,g)$ can be arbitrarily large. More precisely we prove:

######  Theorem 3.

For any positive integer $n,$ there exists a finite 2-generated group $G$ such
that

  1. (1)

$e(G)\geq n.$

  2. (2)

$e(G,g)\leq 5$ for some $g\in G.$

The definition of $e(G,Y)$ can be extended to the case of a (topologically)
finitely generated profinite group $G.$ If we denote with $\mu$ the normalized
Haar measure on $G$, so that $\mu(G)=1$, the probability that $k$ random
elements generate (topologically) $G$ together with the elements of a given
subset $Y$ of $G$ is defined as

$P_{G,Y}(k)=\mu(\\{(x_{1},\ldots,x_{k})\in G^{k}\mid\langle
x_{1},\ldots,x_{k},Y\rangle=G\\}),$

where $\mu$ denotes also the product measure on $G^{k}$. As it is proved for
example in [10, Section 6], $e(G)=\sup_{N\in\mathcal{N}}e(G/N),$ where
$\mathcal{N}$ is the set of the open normal subgroups of $G$. In the same way
it can be easily proved that

$e(G,Y)=\sup_{N\in\mathcal{N}}e(G/N,YN/N).$

This implies that the inequalities in Theorem 1 still hold if $G$ is a
finitely generated profinite group. Recall that a profinite group $G$ is said
to be positively finitely generated, PFG for short, if $P_{G}(k)$ is positive
for some natural number $k$ and that $G$ is said to have polynomial maximal
subgroup growth if $m_{n}(G)\leq\alpha n^{\sigma}$ for all $n$ (and for some
constants $\alpha$ and $\sigma$). A celebrated result of Mann and Shalev [13]
says that a profinite group is PFG if and only if it has polynomial maximal
subgroup growth. Moreover, by Theorem 1, $G$ is PFG if and only if
$e(G)<\infty.$ A strongly generating element in a profinite group $G$ which is
not PFG can be defined as an element $g$ with the property that $e(G,g)$ is
finite. As an immediate corollary of Theorem 3 and its proof we will deduce
the following result.

######  Corollary 4.

There exists a 2-generated profinite group $G$ such that $e(G)=\infty,$ but
$e(G,g)\leq 5$ for some $g\in G.$

An analogous of Theorem 3 cannot hold if we only consider finite soluble
groups. Indeed denote by $d(G)$ the smallest cardinality of a generating set
of $G.$ By [10, Corollary 14], there exists an absolute constant $\alpha$ such
that, for any finite soluble group $G$, $e(G)\leq\left\lceil\gamma
d(G)\right\rceil+\alpha,$ where $\gamma\backsimeq 3.243$ is the Pàlfy-Wolf
constant. Clearly, for any $g\in G,$ we have $e(G,g)\geq d(G)-1,$ so
$e(G)\leq\gamma(e(G,g))+\gamma+\alpha+1$ and

$e(G)-e(G,g)\leq\left\lceil\gamma
d(G)\right\rceil+\alpha-(d(G)-1)\leq(\gamma-1)d(G)+\alpha+2.$

In particular, if $e(G,g)$ is bounded, then $e(G)$ cannot be arbitrarily
large. This does not exclude that a finite soluble group can contain strongly
generating elements. Indeed the difference $e(G)-e(G,g)$ could increase in
function of $d(G).$ It can be immediately seen that this cannot be the case if
we consider finite nilpotent groups. Indeed if $G$ is a finite nilpotent
group, then $e(G)\leq d(G)+2.1185$ (see for example [16, Corollary 2]), and
therefore $e(G)-e(G,g)\leq 3.1185.$ The same argument cannot be applied in the
class of finite metabelian groups. Indeed it follows from [10, Corollary 15]
that for any $d\geq 2$ it is possible to construct a $d$-generated metabelian
group $G$ with $e(G)\sim 2d.$ Nevertheless, a more careful computation shows
that even in the class of finite metabelian group, we cannot have strongly
generating elements. More precisely we prove the following more general
statement.

######  Theorem 5.

If the derived subgroup of a finite group $G$ is nilpotent, then

$e(G)-e(G,g)\leq 11$

for every $g\in G.$

The previous theorem could cast doubt on the existence of strongly generating
elements in finite soluble groups, but in the last section of the paper we
prove that they can occur. Indeed we prove:

######  Theorem 6.

For every positive integer $d\geq 2,$ there exists a finite soluble group $G$
with $d(G)=d$ and containing an element $g$ such that $e(G)-e(G,g)\sim
0.262\cdot d-8.$

##  2\. Proofs of Theorem 3 and Corollary 4

Let $\mathcal{P}$ be the set of the primes $p\geq 7$ with the property that
$p\notin\\{11,23\\}$ and there is no prime power $q$ and positive integer $d$
with $p=(q^{d}-1)/(q-1).$ It is a formidable open problem in Number Theory
whether there are infinitely many primes $p$ which do not belong to
$\mathcal{P}.$ However it can be easily seen that the set of these primes have
density 0. This implies in particular that $\mathcal{P}$ is infinite.

Let $S=\operatorname{Alt}(p),$ with $p\in\mathcal{P},$ and $G_{p}=S^{(p-1)!}$.
If follows from the results presented in [14] that $S^{t}$ is 2-generated if
and only if $t\leq P_{S}(2)|S|^{2}/|\operatorname{Aut}S|.$ In particular if
$S=\operatorname{Alt}(p),$ then $P_{S}(2)\geq
P_{\operatorname{Alt}(7)}(2)=\frac{229}{315},$ so
$(p-1)!\leq\frac{229}{315}\frac{p!}{4}$ and therefore $S^{(p-1)!}$ is
2-generated. Notice that $G_{p}$ contains $(p-1)!$ normal subgroups
$S_{1},\dots,S_{(p-1)!}$ with $S_{i}\cong S.$ For each $1\leq t\leq(p-1)!$
there is an epimorphism $\pi_{t}:G_{p}\to S$ with $\ker(\pi_{t})=R_{t},$ being
$R_{t}=\prod_{j\neq t}S_{j}.$ Since $S$ contains $p$ maximal subgroups
$M_{1},\dots,M_{p}$ of index $p,$ $G_{p}$ contains $p\cdot(p-1)!$ maximal
subgroups of index $p$ (namely $\pi_{t}^{-1}(M_{u})$ for $1\leq t\leq(p-1)!$
and $1\leq u\leq p$) so

$e(G_{p})\geq\mathcal{M}(G_{p})-4\geq\frac{\log m_{p}(G_{p})}{\log
p}-4=\frac{\log\left(p\cdot(p-1)!\right)}{\log p}-4\geq p\left(1-\frac{\log
e}{\log p}\right)-4.$

Now we set $g_{p}=(\sigma,\dots,\sigma),$ where
$\sigma=(1,2,\dots,p)\in\operatorname{Alt}(p)$, and we want to estimate
$e(G_{p},g_{p}).$ First recall that a maximal subgroup $M$ of $G$ can be of
two possible kinds:

  1. (1)

There exists a maximal subgroup $H$ of $S$ and $1\leq t\leq(p-1)!$ such that
$M=\pi_{t}^{-1}(H).$

  2. (2)

There exist $1\leq r<s\leq(p-1)!$ and $\alpha\in\operatorname{Aut}(S)$ such
that $M=\\{x\in G_{p}\mid x^{\pi_{s}}=(x^{\pi_{r}})^{\alpha}\\}.$

If $p\in\mathcal{P},$ then
$N_{S}(\langle\sigma\rangle)\cong\operatorname{Aff}(1,p)$ is the unique
maximal subgroup of $S_{p}$ containing $\sigma$ (see for example [15,
Corollary 3]), so there are precisely $(p-1)!$ maximal subgroups $M$ of type
(1) containing $g_{p}$, and $|G_{p}:M|=|S:\operatorname{Aff}(1,p)|=(p-2)!$ for
each of them. A maximal subgroup of the second type which contains $g_{p}$ is
of the form $\\{x\in G_{p}\mid x^{\pi_{s}}=(x^{\pi_{r}})^{\alpha}\\}$ where
$\sigma=g_{p}^{\pi_{s}}=(g_{p}^{\pi_{r}})^{\alpha}=\sigma^{\alpha}$ and has
index $|S|.$ We have $\binom{(p-1)!}{2}$ choices for the pair $(r,s)$ and
$|C_{S}(\sigma)|=p$ choices for $\alpha.$ Summarizing $m_{n}(G_{p},g_{p})=0$
if $n\notin\\{(p-2)!,p!/2\\}$ and

$\displaystyle\frac{\log\left(m_{(p-2)!}(G_{p},g_{p})\right)}{\log\left((p-2)!\right)}$
$\displaystyle=\frac{\log\left((p-1)!\right)}{\log\left((p-2)!\right)}\leq 2$
$\displaystyle\frac{\log\left(m_{p!/2}(G_{p},g_{p})\right)}{\log\left(\frac{p!}{2}\right)}$
$\displaystyle=\frac{\log\left(\frac{p\cdot(p-1)!\cdot\left((p-1)!-1\right)}{2}\right)}{\log\left(\frac{p!}{2}\right)}\leq
2.$

In particular

$e(G_{p},g_{p})\leq\lceil\mathcal{M}(G_{p},g_{p})\rceil+3\leq 5$

and this concludes the proof of Theorem 1.

Now, let $G_{p}$ and $g_{p}$ as defined above and let
$G=\prod_{p\in\mathcal{P}}G_{p}$ and $g=(g_{p})_{p\in\mathcal{P}}.$ For any
$p\in\mathcal{P},$ let $\pi_{p}:G\to G_{p}$ be the corresponding projection.
We have $e(G)=\sup_{p\in\mathcal{P}}e(G_{p})=\infty.$ Let $M$ be a maximal
subgroup of $G$ containing $g.$ By the Goursat’s Lemma (see for example [17,
4.3.1]), there exists $p\in\mathcal{P}$ and a maximal subgroup $L$ of $G_{p}$
containing $g_{p}$, such that $M=L\times\prod_{q\neq p}G_{q}.$ In particular
$|G:M|=|G_{p}:L|\in\\{(p-2)!,p!/2\\}.$ Notice that if $p_{1}\neq p_{2}$ then
$\\{(p_{1}-2)!,p_{1}!/2\\}\cap\\{(p_{2}-2)!,p_{2}!/2\\}=\varnothing.$ If
follows $\mathcal{M}(G,g)=\sup_{p\in\mathcal{P}}\mathcal{M}(G_{p},g_{p})\leq
2,$ so $e(G,g)\leq 5.$ This proves Corollary 4.

##  3\. Soluble groups

Let $G$ be a finite soluble group and $M$ a maximal subgroup of $G$. Denote by
$Y_{M}=\bigcap_{g\in G}M^{g}$ the normal core of $M$ in $G$ and by
$X_{M}/Y_{M}$ the socle of the primitive permutation group $G/Y_{M}$: clearly
$X_{M}/Y_{M}$ is a chief factor of $G$ and $M/Y_{M}$ is a complement of
$X_{M}/Y_{M}$ in $G/Y_{M}.$ Let $\text{Max}(G)$ be the set of maximal
subgroups of $G,$ let $\mathcal{V}(G)$ be a set of representatives of the
irreducible $G$-modules that are $G$-isomorphic to some complemented chief
factor of $G$ and, for every $V\in\mathcal{V}(G),$ let $\text{Max}(G,V)$ be
the set of maximal subgroups $M$ of $G$ with $X_{M}/Y_{M}\cong_{G}V.$

Recall some results by Gaschütz [7]. Given $V\in\mathcal{V}(G)$, let

$R_{G}(V)=\bigcap_{M\in\text{Max}(G,V)}M.$

It turns out that $R_{G}(V)$ is the smallest normal subgroup contained in
$C_{G}(V)$ with the property that $C_{G}(V)/R_{G}(V)$ is $G$-isomorphic to a
direct product of copies of $V$ and that it has a complement in $G/R_{G}(V)$.
The factor group $C_{G}(V)/R_{G}(V)$ is called the $V$-crown of $G$. The non-
negative integer $\delta_{G}(V)$ defined by $C_{G}(V)/R_{G}(V)$
$\cong_{G}V^{\delta_{G}(V)}$ is called the $V$-rank of $G$ and it coincides
with the number of complemented factors in any chief series of $G$ that are
$G$-isomorphic to $V$ (see for example [1, Section 1.3]). In particular
$G/R_{G}(V)\cong V^{\delta_{G}(V)}\rtimes H,$ with $H\cong G/C_{G}(V).$ Let
$\mathbb{F}_{V}=\operatorname{End}_{G}(V)$, $q_{G}(V)=|\mathbb{F}_{V}|$ and
$r_{G}(V)=\dim_{\mathbb{F}_{V}}V.$ The maximal subgroups in $\text{Max}(G,V)$
are in bijective correspondence with the maximal supplements of
$V^{\delta_{G}(V)}$ in $V^{\delta_{G}(V)}\rtimes H,$ i.e. with the subgroups
of $V^{\delta_{G}(V)}\rtimes H$ of the form $WH^{w}$ with $W$ a maximal
$H$-submodule of $V^{\delta_{G}(V)}$ and $w\in V^{\delta_{G}(V)}$. The number
of choices for $W$ are $(q_{G}(V)^{\delta_{G}(V)}-1)/(q_{G}(V)-1)$ (see for
example [4, Lemma 2.5]) so

(3.1)
$|\text{Max}(G,V)|=\left(\frac{q_{G}(V)^{\delta_{G}(V)}-1}{q_{G}(V)-1}\right)|V|^{\theta_{G}(V)},$

with $\theta_{G}(V)=0$ if $G$ centralizes $V,$ $\theta_{G}(V)=1$ otherwise.
Now we want to count the number of maximal subgroups $M\in\text{Max}(G,V)$
containing a given element $g.$ Let us denote by $\text{Max}(G,g,V)$ this set.
This task corresponds to count the number of maximal supplements of
$V^{\delta_{G}(V)}$ in $V^{\delta_{G}(V)}\rtimes H,$ containing a given
element $x.$ Suppose $x=wh,$ with $w\in V^{\delta_{G}(V)}$ and $h\in H.$ Then
a maximal subgroup of $V^{\delta_{G}(V)}\rtimes H$ containing $x$ is of the
form $WH^{v}$ with $v\in V^{\delta_{G}(V)},$ $W$ a maximal $H$-submodule of
$V^{\delta_{G}(V)}$ and $w+[h^{-1},v]\in W.$ The multiplicity of $V$ in
$\mathbb{F}_{V}H/J(\mathbb{F}_{V}H)$ (where $\mathbb{F}_{V}H$ denote the group
algebra and $J(\mathbb{F}_{V}H)$ its Jacobson radical) is $r_{G}(V)$ so it
follows from [3, Lemma 1] that the $H$-submodule of $V^{\delta_{G}(V)}$
generated by one of its elements is isomorphic to $V^{k}$ with $k\leq
r_{G}(A).$ So, if $\delta_{G}(V)>r_{G}(V),$ then for any choice of $v,$ we
have at least $(q_{G}(V)^{\delta_{G}(V)-r_{G}(V)}-1)(q_{G}(V)-1)$ maximal
$H$-submodules $W$ containing $w+[h^{-1},v],$ and therefore

(3.2)
$|\text{Max}(G,g,V)|\geq\left(\frac{q_{G}(V)^{\delta_{G}(V)-r_{G}(V)}-1}{q_{G}(V)-1}\right)|V|^{\theta_{G}(V)}.$

Combining (3.1) and (3.2), it follows that if $\delta_{G}(V)>r_{G}(A),$ then

(3.3) $|\text{Max}(G,V)|\leq|\text{Max}(G,g,V)|\cdot
q_{G}(V)^{2r_{G}(V)}=|\text{Max}(G,g,V)|\cdot n^{2}.$

Let $\mathcal{V}_{n}(G):=\\{V\in\mathcal{V}(G)\mid|V|=n\\}$ and
$\mathcal{V}_{n}^{\circ}(G)=\\{V\in\mathcal{V}_{n}(G)\mid\delta_{G}(V)\leq
r_{G}(V)\\}.$ Moreover define

$\mu^{+}_{n}(G)=\sum_{V\in\mathcal{V}_{n}(G)\setminus\mathcal{V}_{n}^{\circ}(G)}|\text{Max}(G,V)|,\quad\mu_{n}^{\circ}(G)=\sum_{V\in\mathcal{V}_{n}^{\circ}(G)}|\text{Max}(G,V)|.$

Notice that, by (3.3), we have:

(3.4) $\mu^{+}_{n}(G)\leq m_{n}(G,g)n^{2}.$

######  Lemma 7.

If $\mu^{+}_{n}(G)\geq\mu_{n}^{\circ}(G)$, then, for every $g\in G,$

$\frac{\log m_{n}(G,g)}{\log n}\geq\frac{\log m_{n}(G)}{\log n}-3.$

###### Proof.

Assuming $\mu^{+}_{n}(G)\geq\mu_{n}^{\circ}(G)$, and using (3.4), we get

$\displaystyle\frac{\log m_{n}(G)}{\log n}$
$\displaystyle=\frac{\log\left(\sum_{V\in\mathcal{V}_{n}(G)}|\text{Max}(G,V)|\right)}{\log
n}=\frac{\log\left(\mu^{+}_{n}(G)+\mu_{n}^{\circ}(G)\right)}{\log n}$
$\displaystyle\leq\frac{\log\left(2\mu^{+}_{n}(G)\right)}{\log n}\leq
1+\frac{\log\left(\mu^{+}_{n}(G)\right)}{\log n}\leq
1+\frac{\log\left(m_{n}(G,g)\cdot n^{2}\right)}{\log n}$ $\displaystyle\leq
3+\frac{\log\left(m_{n}(G,g)\right)}{\log n}.\qed$

We say that $n$ is a $G$-dominant integer if
$\mathcal{M}(G)=\lceil\log(m_{n}(G))/\log n\rceil.$ Combining Corollary 2 and
Lemma 7, we deduce:

######  Corollary 8.

Let $G$ be a finite soluble group. If $\mu^{+}_{n}(G)\geq\mu_{n}^{\circ}(G)$
for some $G$-dominant integer $n,$ then $e(G)-e(G,g)\leq 11$ for every $g\in
G.$

Now we are ready to prove Theorem 5.

###### Proof of Theorem 5.

Suppose that the derived subgroup of $G$ is nilpotent. Without loss of
generality we can assume that $\operatorname{Frat}(G)=1$. In this case the
Fitting subgroup $\operatorname{Fit}(G)$ of $G$ is a direct product of minimal
normal subgroups of $G$, it is abelian and complemented. Let $K$ be a
complement of $\operatorname{Fit}(G)$ in $G$. Since $G^{\prime}$ is nilpotent,
$G^{\prime}\leq\operatorname{Fit}(G).$ In particular
$K^{\prime}\leq\operatorname{Fit}(G)\cap K=1,$ and therefore $K$ is abelian.
Let $F$ be a complement of $Z(G)$ in $\operatorname{Fit}(G)$ and let
$H=Z(G)\times K.$ We have $G=F\rtimes H$ and we can write $F$ in the form

$F=V_{1}^{\delta_{G}(V_{1})}\times\cdots\times V_{r}^{\delta_{G}(V_{r})}$

where $V_{1},\ldots,V_{r}$ are irreducible nontrivial $H$-modules, pairwise
not $H$-isomorphic. Let $\mathbb{F}_{i}=\operatorname{End}_{H}(V_{i}).$ Since
$H$ is abelian, $r_{G}(V_{i})=\dim_{\mathbb{F}_{i}}V_{i}=1$ and
$H/C_{H}(V_{i})$ is isomorphic to a subgroup of $\mathbb{F}_{i}^{*}.$ Suppose
that $n$ is a $G$-dominant integer. By Corollary 8, we may assume
$\mu^{+}_{n}(G)<\mu_{n}^{\circ}(G).$ Since $r_{G}(V)=1$ for every
$V\in\mathcal{V}(G),$ $\delta_{G}(V)=1$ for every
$V\in\mathcal{V}_{n}^{\circ}(G).$ Moreover, if $V\in\mathcal{V}_{n}(G),$ then
either $V=V_{i}$ for some $1\leq i\leq r$ or $V$ is a trivial-$G$-module (this
occurs only if $n$ is a prime and it divides $|H|$). So

$\mu_{n}^{\circ}(G)\leq 1+\tau,$

where $\tau$ is the cardinality of the set
$\mathcal{T}=\left\\{i\in\\{1,\dots,r\\}\mid|V_{i}|=n\right\\}.$ In
particular, to any $i\in\mathcal{T},$ there corresponds a different nontrivial
homomorphism from $H$ to $\mathbb{F}_{i}^{*}\cong C_{n-1}$. It follows

$\tau\leq(n-1)^{d(H)}-1.$

But then

$\mu_{n}^{\circ}(G)\leq(n-1)^{d(H)}\leq(n-1)^{d(G)}.$

By Theorem 1

$e(G)\leq\mathcal{M}(G)+4\leq\frac{\log(2\mu_{n}^{\circ}(G))}{\log
n}+4\leq\frac{\log\mu_{n}^{\circ}(G)}{\log n}+5\leq d(G)+5.$

Since $e(G,g)\geq d(G)-1,$ we conclude that $e(G)-e(G,g)\leq 6.$ ∎

##  4\. Proof of Theorem 6

Le $X$ be the Sylow 2-subgroup of $\operatorname{GL}(2,3).$ Recall that $X$ is
the semidihedral group of order 16, it is 2-generated and
$|\operatorname{Aut}(X)|=16.$ Now let $F$ be the free group of rank $d\geq 2$
and denote by $\Sigma$ the set of the epimorphisms $\sigma:F\to X.$ We have

$|\Sigma|=|X|^{d}P_{X}(d)\geq 16^{d}P_{X}(2)=\frac{3\cdot 16^{d}}{8}.$

Now let

$N:=\bigcap_{\sigma\in\Sigma}\ker\sigma\quad\text{ and }\quad H:=F/N.$

Then $H$ is a $d$-generated 2-group and it contains
$\rho:=|\Sigma|/|\operatorname{Aut}(X)|$ different normal subgroups
$N_{1},\dots,N_{\rho}$ with $H/N_{i}\cong X.$ If follows from [16] that

$e(H)=e(C_{2}^{d})=d+\sum_{1\leq i\leq d}\frac{1}{2^{i}-1}\leq d+\sum_{0\leq
j\leq d-1}\frac{1}{2^{j}}\leq d+2.$

We consider the semidirect product

$G_{d}:=\prod_{1\leq i\leq\rho}V_{i}\rtimes H,$

where $V_{i}\cong C_{3}\times C_{3}$ and $N_{i}$ is the kernel of the action
of $H$ on $V_{i}$. Notice that by the main result in [6], $d(G_{d})=d(H)=d.$
It follows that

$\mathcal{M}(G_{d})=\frac{\log(m_{9}(G_{d}))}{\log(9)}\geq\frac{\log\left(\frac{3\cdot
16^{d-1}}{8}\right)}{\log(9)}=\frac{(d-1)\log(16)+\log(3)-\log(8)}{\log(9)}.$

In particular

$e(G_{d})\geq\frac{d\log(16)}{\log(9)}-c,\text{ with
}c=4+\frac{\log(16)+\log(8)-\log(3)}{\log(9)}\leq 6.$

Now consider $g=(v_{1},\dots,v_{\rho})\in\prod_{1\leq
i\leq\rho}(V_{i}\setminus\\{0\\}).$ Then $m_{9}(G_{d},g)=0,$ so
$e(G_{d},g)\leq e(H)\leq d+2.$ We conclude that

$e(G_{d})-e(G_{d},g)\geq\frac{d\log(16)}{\log(9)}-6-(d+2)=d\left(\frac{\log(16)-\log(9)}{\log(9)}\right)-8\sim
0.262\cdot d-8.$

Remark. Notice that the previous argument can be repeated taking an arbitrary
pair $(H,V),$ where $H$ is a nilpotent irreducible subgroup of
$\operatorname{GL}(V)$ with $|H|>|V|.$ There exists a positive constant $c$,
depending only on $H$, such that if $\tilde{H}_{d}$ is the largest
$d$-generated subdirect product of copies of $H,$ and $\rho$ is the number of
different kernels of epimorphisms from $\tilde{H}_{d}\to H,$ then the
semidirect product $G_{d}=\prod_{1\leq i\leq\rho}V_{i}\rtimes\tilde{H}_{d}$
contains an element $g$ with the property that

$e(G_{d})-e(G_{d},g)\geq d\left(\frac{\log|H|}{\log|V|}-1\right)-c.$

In the proof of [18, Proposition 1.7] a sequence
$(H_{n},V_{n})_{n\in\mathbb{N}}$ is constructed, where $H_{n}$ is a nilpotent
irreducible subgroup of $\operatorname{GL}(V_{n}),$ such that

$\lim_{n\to\infty}\frac{\log|H_{n}|}{\log|V_{n}|}=\frac{2^{n}\log(16)+(1+2+\dots+2^{n-1})\log(2)}{2^{n}\log(9)}=\frac{\log(32)}{\log(9)}\sim
1.577,$

hence, for $d$ large enough, it can be constructed a $d$-generated soluble
group $G_{d}$ containing an element $g$ with $e(G_{d})-e(G_{d},g)\sim
0.577\cdot d.$ By [18, Theorem 1.6], this is the largest gap that can be
obtained with these kind of examples.

##  5\. Other considerations about profinite groups

As mentioned in the introduction, if $G$ is a $d$-generated prosoluble group,
then $G$ is PFG and the gap $e(G)-e(G,g)$ is bounded, for every $g\in G,$ by
$e(\widehat{F}_{\text{sol},d}),$ where $\widehat{F}_{\text{sol},d}$ is the
free-prosoluble group of rank $d$ (i.e the prosoluble completion of the free
group of rank $d$). In the case where $G$ is precisely the free-prosoluble
group, the arguments introduced in Section 3 allow us to show that this gap
can be actually bounded by a constant that does not depend on $d(G)$.

######  Proposition 9.

There exists an absolute constant $\kappa$ such that

$e(\widehat{F}_{\text{sol},d})-e(\widehat{F}_{\text{sol},d},g)\leq\kappa$

for every positive integer $d$ and for every $g\in\widehat{F}_{\text{sol},d}.$

###### Proof.

A prosoluble group is PFG [12, Theorem 10], hence
$e(\widehat{F}_{\text{sol},d})<\infty$. More precisely there exists a constant
$\alpha$ such that, for each $d\geq 2,$ we have
$e(\widehat{F}_{\text{sol},d})\leq\lceil\gamma d\rceil+\alpha$, where
$\gamma\sim 3.243$ is the Pàlfy-Wolf constant. Clearly it is not restrictive
to assume $d>2.$ Let $G=\widehat{F}_{\text{sol},d}$ and let $K_{n}$ be the
intersection of the maximal open subgroups of $G$ with index $n.$ Since $G$ is
finitely generated, $K_{n}$ is an open normal subgroup of $G$,
$m_{n}(G)=m_{n}(G/K_{n})$ and $m_{n}(G,g)=m_{n}(G/K_{n},gK_{n})$ for every
$g\in G.$ Let $V\in\mathcal{V}_{n}(G/K_{n})$ and set
$H=(G/K_{n})/C_{G/K_{n}}(V)\cong G/C_{G}(V).$ It follows from the main result
in [6] that the semidirect product $V^{t}\rtimes H$ is $d$-generated if and
only if $t\leq r_{H}(V)(d-\theta_{H}(V)).$ Since $G$ is the free-prosoluble
group of rank $d,$ every $d$-generated finite soluble group is an epimorphic
image of $G$. It follows that $V^{r_{H}(V)(d-\theta_{H}(V))}\rtimes H$ is an
epimorphic image of $G/K_{n}$ and consequently
$\delta_{G/K_{n}}(V)=r_{H}(V)(d-\theta_{H}(V)).$ Since we are assuming $d>2,$
$\delta_{G/K_{n}}(V)>r_{H}(V)=r_{G/K_{n}}(V),$ i.e.
$\mathcal{V}^{\circ}_{n}(G/K_{n})=\varnothing.$ By (3.4)
$m_{n}(G)=m_{n}(G/K_{n})\leq m_{n}(G/K_{n},gK_{n})n^{2}=m_{n}(G,g)n^{2}$ for
every $g\in G$, and consequently, by Corollary 2, $e(G)-e(G,g)\leq 10.$ ∎

We conclude with some considerations on strongly generating elements in the
finitely generated profinite groups that are not PFG. Recall that when $G$ is
a finitely generated group which is not PFG, then we say that $g\in G$ is a
strongly generating element if $e(G,g)$ is finite. Denote by $\mathcal{S}(G)$
the set of these elements. Notice that $g\in\mathcal{S}(G)$ if and only if
there exists a positive integer $k$ with the property that
$P_{G,\\{g\\}}(k)<\infty.$ The set $\mathcal{F}(G)$ of the elements of $G$
which do not satisfy this property is studied in [5]. In particular, by [5,
Proposition 2.6], $\mu(\mathcal{S}(G))=1-\mu(\mathcal{F}(G))=0,$ in other
words a non-PFG group $G$ can contain strongly generating elements, but the
probability that a randomly chosen element of $G$ is a strongly generating
element is zero. Nevertheless, $\mathcal{S}(G)$ can be dense in $G$ (see [5,
Proposition 3.5]). On the other hand, there are examples of non-PFG groups
without strongly generating elements. In particular,
$\mathcal{S}(\hat{F}_{d})=\varnothing$ for every $d\geq 2$, denoting by
$\hat{F}_{d}$ the free profinite group of rank $d$ [5, Theorem 3.3].

## References

  * [1] A. Ballester-Bolinches and L. M. Ezquerro, Classes of finite groups, Mathematics and Its Applications (Springer), vol. 584, Springer, Dordrecht, 2006.
  * [2] A.V. Borovik, L. Pyber and A. Shalev, Maximal subgroups in finite and profinite groups, Trans. Amer. Math. Soc. 348 (1996), 3745–3761.
  * [3] J. Cossey, K. Gruenberg and L. G Kovács, The presentation rank of a direct product of finite groups, J. Algebra 28 (1974), 597–603.
  * [4] F. Dalla Volta and A. Lucchini, Finite groups that need more generators than any proper quotient, J. Austral. Math. Soc. Ser. A 64 (1998), no. 1, 82–91.
  * [5] E. Detomi and A. Lucchini, Probabilistic non-generators in profinite groups, Ischia group theory 2004, 149–158, Contemp. Math., 402, Israel Math. Conf. Proc., Amer. Math. Soc., Providence, RI, 2006
  * [6] W. Gaschütz, Die Eulersche Funktion endlicher auflösbarer Gruppen, Illinois J. Math. 3 (1959), 469–476.
  * [7] W. Gaschütz, Praefrattinigruppen, Arch. Math. 13 (1962), 418–426.
  * [8] A. Jaikin-Zapirain and L. Pyber, Random generation of finite and profinite groups and group enumeration, Ann. of Math. (2) 173 (2011), no. 2, 769–814.
  * [9] A. Lubotzky, The expected number of random elements to generate a finite group, J. Algebra 257 (2002), no. 2, 452–459.
  * [10] A. Lucchini, The expected number of random elements to generate a finite group, Monatsh. Math. 181 (2016), no. 1, 123–142.
  * [11] A. Lucchini and M. Moscatiello, Generation of finite groups and maximal subgroup growth, Adv. Group Theory Appl. 9 (2020), 39–49.
  * [12] A. Mann, Positively finitely generated groups, Forum Math. 8 (1996) 429–459.
  * [13] A. Mann and A. Shalev, Simple groups, maximal subgroups and probabilistic aspects of profinite groups, Israel J. Math. 96 (1996) 449–468.
  * [14] N. Menezes, M. Quick, C. Roney-Dougal, The probability of generating a finite simple group, Israel J. Math. 198 (2013), no. 1, 371–392.
  * [15] P. P. Pálfy, On Feit’s examples of intervals in subgroup lattices, J. Algebra 116 (1988), no. 2, 471–479.
  * [16] C. Pomerance, The expected number of random elements to generate a finite abelian group, Period. Math. Hung. 43 (2001) 191–198.
  * [17] W. R. Scott, Group theory. Second edition. Dover Publications, Inc., New York, 1987.
  * [18] T. R. Wolf, Solvable and nilpotent subgroups of $GL(n,q^{m}),$ Canadian J. Math. 34 (1982), no. 5, 1097–1111.