# On Subjective Uncertainty Quantification and Calibration
in Natural Language Generation

Ziyu Wang
University of Oxford
<EMAIL_ADDRESS>Chris Holmes
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

Applications of large language models often involve the generation of free-
form responses, in which case uncertainty quantification becomes challenging.
This is due to the need to identify task-specific uncertainties (e.g., about
the semantics) which appears difficult to define in general cases. This work
addresses these challenges from a perspective of Bayesian decision theory,
starting from the assumption that our utility is characterized by a similarity
measure that compares a generated response with a hypothetical true response.
We discuss how this assumption enables principled quantification of the
model’s subjective uncertainty and its calibration. We further derive a
measure for epistemic uncertainty, based on a missing data perspective and its
characterization as an excess risk. The proposed measures can be applied to
black-box language models. We demonstrate the proposed methods on question
answering and machine translation tasks, where they extract broadly meaningful
uncertainty estimates from GPT and Gemini models and quantify their
calibration.

##  1 Introduction

We are interested in uncertainty quantification for language models (LMs) in
_free-form_ natural language generation (NLG): given instruction $I$, the
model generates a response $y^{\prime}$ based on its predictive distribution
$p_{M}(y\mid I)$, where $y^{\prime}$ could be _any_ natural language passage
that fits the instruction. An example of this is question answering (QA):
given a question from the user, the model may provide a brief answer, but it
may also follow with supporting facts and explanations, which can vary in form
and detail. The user can be satisfied by a wide variety of responses,
irrespective of their style or (to some extent) the choice of supporting facts
included.

Free-form NLG poses significant challenges to uncertainty quantification: some
aspects of generation are irrelevant to the task’s purpose and best excluded
from uncertainty quantification, but it often appears that we are unable to
characterize them precisely. If left unaddressed, however, the model’s
variation in the irrelevant aspects may dominate in standard uncertainty
measures such as token-level entropy (Kuhn et al.,, 2023), making them
uninformative about the model’s actual performance on the task.

Starting from Kuhn et al., (2023), a recent line of work (Kuhn et al.,, 2023;
Lin et al.,, 2024; Zhang et al.,, 2023; Aichberger et al.,, 2024) studied this
issue and proposed measuring the “semantic uncertainty” of generation;
“semantics” is defined as the equivalence class of textual responses that
logically entail one another. Empirical improvements in downstream tasks
evidenced their contributions and highlighted the importance of _task-
specific_ uncertainty quantification, but important conceptual and practical
issues remain. From a practical perspective, semantic equivalence is estimated
using machine learning models, resulting in imprecise estimates that do not
necessarily define an equivalence relation. The imprecision necessitates the
introduction of _heuristics_ to post-process the estimates or to aggregate
them through other means. Conceptually, the notion of _semantic equivalence
does not always provide a valid or complete characterization_ of relevance for
certain tasks. Style transfer (Jin et al.,, 2022) tasks provide an example of
the first kind. For the second scenario, consider a QA task where the model is
fully certain about the answer to a question, as well as a large set of
supporting facts, each of which provides complete and independent
justification for the answer; yet there is still the “uncertainty”, or
variation across generations, about which facts are included in a response.
Then very few of the model generations may logically entail one another, and
there is a very high level of “semantic uncertainty” just as if there was
complete uncertainty about the correct answer.

This paper is about the observation that the above challenges can be resolved
in a more general setup from a perspective of _Bayesian decision theory_
(Savage,, 1954). We first assume that we can compute a similarity-type measure
$S(y^{\prime},y;I)$ that characterizes our _utility function_ when the model
generates $y^{\prime}$ in respond to $I$ and $y$ is a (true or hypothetical)
correct response. This generalizes previous works based on semantic
equivalence, which corresponds to defining $S$ using entailment. It can also
be applied to traditional structured prediction tasks where a choice of $S$ is
readily available (e.g., the chrF score for machine translation, Popović,,
2015), as well as tasks where evaluation can be adequately implemented using
frontier language models that computes $S$ based on few-shot demonstrations or
detailed instructions.

To quantify the subjective uncertainty defined by the LM, we assume the
generation $y$ is always chosen to maximize the expected utility under the
LM’s predictive distribution $p_{M}$ (§2.1). This is a common assumption in
NLG (Bickel and Doksum,, 1997; Bertsch et al.,, 2023). It can be supported by
a common belief that high-capacity LMs may approximate Bayesian inference
(e.g., Xie et al.,, 2021; Akyürek et al.,, 2022; Hahn and Goyal,, 2023; Ye et
al.,, 2024), and is also more broadly applicable whenever we view $p_{M}$ as
our best available model for $y\mid I$. Subjective uncertainty is then
naturally characterized by the Bayes risk, or equivalently the maximum
achievable expected utility, where the action space is defined by the
candidate generations available. This simple observation allows us to
understand that previous methods for “semantic uncertainty” can be adapted to
a broader range of scenarios, regardless of whether semantic equivalence is
relevant. It also provides a unique, principled approach for aggregating
similarity measures among generations (§2.2).

For subjective uncertainty measures to be useful, it will be ideal if the LM
is calibrated. It has been unclear in previous works how calibration can be
evaluated in free-form NLG tasks, given the distinction between relevant and
irrelevant differences for a specific task and our apparent inability to
formally characterise it. The decision-theoretic view provides a natural
answer to this question: an LM is deemed as to possess a calibrated notion of
uncertainty if the expected subjective utility of its actions matches the
expectation of the actually incurred utility, defined w.r.t. responses from
the true data distribution (§2.3). This observation allows us to quantify the
calibration of LMs through reliability diagrams (Murphy and Winkler,, 1977)
and a generalized version of expected calibration error (Naeini et al.,,
2015). In the discussion we also note a generally applicable definition for
“task-specific semantics”: the equivalence class defined by the action-utility
map, known as _Savage acts_.

Bayesian modelling allows for the decomposition of predictive uncertainty into
_epistemic uncertainty_ and _aleatoric uncertainty_ (Der Kiureghian and
Ditlevsen,, 2009). The decomposition allows us to better understand and
diagnose the model’s uncertainty (e.g., only the epistemic uncertainty should
decrease as the training set grows); it can also guide data acquisition
(Kendall and Gal,, 2017). The quantification of epistemic uncertainty in
general NLG applications appears challenging, due to the black-box nature of
LMs and the free-form generations involved. §2.4 demonstrates that the
decision-theoretic view enables us to quantify epistemic uncertainty for in-
context learning (ICL, Brown et al.,, 2020) applications; key additional
ingredients include a missing data perspective to Bayesian modelling (Fong et
al.,, 2024) and a connection between epistemic uncertainty and a notion of
excess risk (Xu and Raginsky,, 2022). The resulted measure is connected to and
generalizes various previous works on epistemic uncertainty quantification for
black-box models, which provides independent justification for its use.

The rest of this paper is structured as follows: §2 presents the proposed
methodology and discusses connections to previous work; §3 provides
experimental illustrations; and §4 provides concluding remarks.

##  2 Quantifying Subjective Uncertainty and Calibration

###  2.1 A Utilitarian Setup

The basic setup of this paper is as follows:

  * •

we have a NLG task: given prompt $I\in\mathcal{I}$, generate a response
$y^{\prime}\in\mathcal{Y}$ where $\mathcal{Y}$ denotes the space of natural
language responses;

  * •

our utility can be measured through the similarity measure
$S(y^{\prime},y;I)\in\mathbb{R}$, which can be cheaply evaluated;

  * •

we have access to an LM $p_{M}$, and, in the absence of further evidence,
consider $p_{M}$ sufficiently trustworthy so that the ideal generation (i.e.,
action) $y^{\prime}$ given $I$ should maximize the expected utility,

$y^{\prime}:=\operatorname*{arg\,max}_{y^{\prime}\in\mathcal{Y}^{\prime}_{I}}\mathbb{E}_{y\sim
p_{M}(\cdot\mid I)}S(y^{\prime},y;I),$ (1)

where $\mathcal{Y}^{\prime}_{I}\subset\mathcal{Y}$ denotes the space of
candidate generations.

In the above, $p_{M}$ represents a subjective belief about the true data
distribution. $\mathcal{Y}_{I}^{\prime}\subset\mathcal{Y}$ can be determined
based on computational constraints, e.g., as a separate set of samples from
$p_{M}(\cdot\mid I)$.111 When $\mathcal{Y}_{I}^{\prime}$ is stochastic,
expected utility/risk quantities such as (1) should also be averaged over the
randomness in $\mathcal{Y}_{I}^{\prime}$. For brevity, we omit such (outmost)
expectations throughout the paper.  The utility $S$ determines a _risk_
function $r(y^{\prime},y;I)=-S(y^{\prime},y;I)$, which can be scaled and
shifted as desired.

As discussed in §1, this setup is very general. This decision-theoretic
perspective is taken in the framework of minimum Bayes risk (MBR) decoding
(Bickel and Doksum,, 1997), which advocates for generating $y$ based precisely
on (1). MBR recovers many modern methods for natural language generation
(Bertsch et al.,, 2023), and these methods can be viewed as having adopted the
same view implicitly. Note that adopting the decision-theoretic setup does not
compel us to assume that $p_{M}$ is a strictly Bayesian model (e.g., in the
sense of Xie et al.,, 2021): although that will provide a good justification,
it is also possible that a non-Bayesian LM may better approximate our belief
than any available Bayesian model does.

###  2.2 Task-Specific Measure of Subjective Uncertainty

It is well known that Bayesian uncertainty measures are connected to minimum
achievable risks of the form

$R_{B}(I;p_{M},\mathcal{Y}^{\prime}_{I}):=\min_{y^{\prime}\in\mathcal{Y}^{\prime}_{I}}\mathbb{E}_{y\sim
p_{M}(\cdot\mid I)}r(y^{\prime},y;I).$ (2)

For example, if $\mathcal{Y}=\mathcal{Y}^{\prime}_{I}\subset\mathbb{R}$ and
$r(y,y^{\prime};I)=(y-y^{\prime})^{2}$,
$R_{B}(I;p_{M},\mathcal{Y}^{\prime}_{I})$ will be equivalent to the variance
of the predictive distribution; if with an abuse of notation we redefine
$y^{\prime}$ as a probability density function and
$r(y^{\prime},y;I)\leftarrow\log y^{\prime}(y)$,
$R_{B,\mathcal{Y}^{\prime}_{I}}(I)=H[p_{M}(\cdot\mid I)]$ will be the entropy.
When the action space $\mathcal{Y}^{\prime}_{I}\subsetneq\mathcal{Y}$ is a
strict subset, (2) will be connected to measures of _usable_ information as
discussed in Xu et al., (2019).

It is thus natural to also adopt (2) as a measure of subjective uncertainty
for NLG tasks. To implement (2), we adopt Monte Carlo approximation for the
expectation.

A common generation strategy is to follow the Gibbs predictor, which
corresponds to (1) with $\mathcal{Y}^{\prime}_{I}:=\\{y_{I}\\}$ and $y_{I}\sim
p_{M}(\cdot\mid I)$ being a single sample. In such cases, the expected
uncertainty
$\mathbb{E}_{\mathcal{Y}^{\prime}_{I}}R_{B}(I;p_{M},\mathcal{Y}^{\prime}_{I})$
is connected to the degree statistic in Lin et al., (2024, Eq. 8); the
difference is that we use a similarity measure that is assumed to define our
utility. While Lin et al., (2024) explored 9 different uncertainty measures
for the Gibbs predictor, the decision-theoretic perspective leads to one
unique method without any underspecified design choices, justifies its use
beyond the scope of semantic equivalence, and highlights that different
choices of predictors ($\mathcal{Y}_{I}^{\prime}$) should be matched with
different uncertainty measures. However, being a measure of subjective
uncertainty, it is not guaranteed to always improve on downstream tasks
compared with heuristic alternatives, especially if the LM is less calibrated.

###  2.3 Evaluation of Task-Specific Calibration

Subjective uncertainty measures are most useful when the LM is calibrated. As
discussed in Huang et al., (2024), many previous works studying uncertainty on
NLG tasks did not distinguish between calibration and predictive performance
in their evaluation, which leads to a relative lack of understanding about the
calibration of LMs in such scenarios.

A typical definition of calibration is as follows (see e.g., Johnson et al.,,
2024): suppose the spaces $\mathcal{Y},\mathcal{I}$ are discrete, and denote
the true data distribution as $p_{0}$; a model $p_{M}$ is considered
calibrated w.r.t. some grouping function $G(I):\mathcal{I}\to\mathcal{G}$ if
we have

$\mathbb{E}_{p_{0}}(p_{M}(y=y^{\prime}\mid I)\mid
G(I)=g)=\mathbb{E}_{p_{0}}(p_{0}(y=y^{\prime}\mid I)\mid G(I)=g)~{}~{}\forall
g\in\mathcal{G},y^{\prime}\in\mathcal{Y}.$ (3)

The grouping function $G$ may be defined based on the model’s prediction, or
it may incorporate additional information such as input demographics. In the
NLG setting, however, the criterion (3) can be trivially violated if, e.g.,
the LM always generates a longer response compared with $p_{0}$.

In light of the assumptions in §2.1, it is natural to relax (3) as follows:

$\displaystyle\mathbb{E}(p_{M}(\\{y:S(y^{\prime},y;\mathcal{I})=s\\}\mid
I)\mid G(I)=g)$
$\displaystyle=\mathbb{E}(p_{0}(\\{y:S(y^{\prime},y;\mathcal{I})=s\\}\mid
I)\mid G(I)=g)$ $\displaystyle\hskip 130.0002pt~{}~{}\forall
g\in\mathcal{G},y^{\prime}\in\mathcal{Y}^{\prime}_{I},s\in\mathbb{R}.$ (3’)

(3’) is equivalent to (3) if $\mathcal{Y}^{\prime}_{I}=\mathcal{Y}$ and
$S(y^{\prime},y;\mathcal{I})=\mathbf{1}\\{y=y^{\prime}\\}$, or more generally
if for all $I\in\mathcal{I}$ the map from $y$ to the function

$s_{y,I}:\mathcal{Y}_{I}^{\prime}\to\mathbb{R},~{}y^{\prime}\mapsto
S(y^{\prime},y;I)$ (4)

is injective (e.g., if $S$ is defined by a metric on $\mathcal{Y}$). (3’)
becomes weaker if $S(y^{\prime},y;\mathcal{I})$ only depends on $y$ and
$y^{\prime}$ through a non-invertible function, e.g., a map from a natural
language passage to its semantics; in such cases, it is clear that (3’)
remains a sufficiently strong criterion for task-specific calibration. More
generally, we can always view the function $s_{y,I}(y^{\prime})$ as a
representation of “task-specific semantics”.222 For the goals of providing the
best generation from $\mathcal{Y}^{\prime}_{I}$ and quantifying its risk, it
suffices to define the function $s_{y,I}$ on $\mathcal{Y}^{\prime}_{I}$. For
purposes beyond the scope of the generation task, it may be helpful to extend
its domain to a larger subset of $\mathcal{Y}$.  In fact, the replacement of
$y^{\prime}\in\mathcal{Y}^{\prime}_{I}$ with the more compact
$s_{y^{\prime},I}(\cdot)$ has been advocated by Savage, (1954), and $s_{y,I}$
is referred to as a _Savage act_ (see e.g., Marinacci,, 2015, §2.4).

A main reason we are interested in criteria such as (3) or (3’) is that they
guarantee the calibration of uncertainty measures. It follows from (3’) that
$\mathbb{E}_{p_{0}(I\mid G(I)=g)p_{M}(y\mid
I)}r(y^{\prime},y;I)=\mathbb{E}_{p_{0}(I\mid G(I)=g)p_{0}(y\mid
I)}r(y^{\prime},y;I)$ for all $y^{\prime}$, and thus

$\displaystyle\mathbb{E}_{p_{0}(I\mid
G(I)=g)}R_{B}(I;p_{M},\mathcal{Y}^{\prime}_{I})=\mathbb{E}_{p_{0}(I\mid
G(I)=g)p_{M}(y\mid I)}r(\hat{y}_{I},y;I)=\mathbb{E}_{p_{0}(I\mid
G(I)=g)p_{0}(y\mid I)}r(\hat{y}_{I},y;I),$ (5)

where $\hat{y}_{I}$ denotes the MBR generation (1). Plugging in
$G(I)=R_{B}(I;p_{M},\mathcal{Y}^{\prime}_{I})$, we find that LMs are
calibrated in the sense of (3’) only if

$\text{gECE}(p_{M}):=\mathbb{E}_{s}|f_{M}(s)-s|=0,~{}~{}~{}\text{where
}f_{M}(s):=\mathbb{E}_{I,y,\hat{y}_{I}}(r(\hat{y}_{I},y;I)\mid
R_{B}(I;p_{M},\mathcal{Y}^{\prime}_{I})=s)~{}\forall s\in\mathbb{R}.$ (6)

(6) provides a natural generalization of the _expected calibration error_
(ECE, Naeini et al.,, 2015) in classification, which it recovers with
$r(y^{\prime},y;I)\leftarrow\mathbf{1}\\{y^{\prime}\neq y\\}$. Similar to the
classification case, (6) can be estimated through histogram binning. The plot
for the function $f_{M}$ is called a _reliability diagram_ (Murphy and
Winkler,, 1977) and provides information on overconfidence ($f_{M}(s)<s$) or
underconfidence. Importantly, these methods remain applicable in NLG as we
have shown. Moreover, they will automatically focus on the task-specific
aspects of uncertainty, since the function $f_{M}$ only depends on model
generations through the utility $S$.

######  Remark 2.1.

We discussed the evaluation of LM calibration based on the uncertainty measure
(2). To our knowledge, only Huang et al., (2024) studied a similar problem in
the general NLG setting, namely the _rank-calibration_ of general uncertainty
measures. As discussed in Huang et al., (2024, §4.2), rank-calibration is
still a different property; in particular, (2) will be rank-calibrated
whenever $f_{M}$ is monotone, even though it can be arbitrarily overconfident
or underconfident and thus miscalibrated.

###  2.4 Representing and Eliciting Epistemic Uncertainty

We now turn to the problem of epistemic uncertainty quantification in in-
context learning, where the prompt $I=\langle
x_{1},y_{1},\ldots,x_{n},y_{n},x_{*}\rangle$ is formed by $n$ demonstrations
$(x_{i},y_{i})$ followed by a test input $x_{*}$. We assume that
$r(y,y^{\prime};I)=r(y,y^{\prime};x_{*})$ only depends on $I$ through $x_{*}$,
which is commonly satisfied in applications. We propose the following measure
of epistemic uncertainty inspired by Fong et al., (2024); Xu and Raginsky,
(2022):

$\displaystyle\inf_{y^{\prime}\in\mathcal{Y}^{\prime}_{I}}\mathbb{E}_{p_{x}(x_{n+1:N})}\mathbb{E}_{p_{M}(y_{n+1:N}\mid
y_{1:n},x_{1:N})}\mathbb{E}_{p_{M}(y_{*}\mid
y_{1:N},x_{1:N},x_{*})}r(y^{\prime},y_{*};x_{*})$ $\displaystyle\hskip
40.00006pt-\mathbb{E}_{p_{x}(x_{n+1:N})}\mathbb{E}_{p_{M}(y_{n+1:N}\mid
y_{1:n},x_{1:N})}\inf_{y^{\prime}\in\mathcal{Y}^{\prime}_{I}}\mathbb{E}_{p_{M}(y_{*}\mid
y_{1:N},x_{1:N},x_{*})}r(y^{\prime},y_{*};x_{*}).$ (7)

In the above, $p_{x}$ denotes a user-specified distribution of additional ICL
inputs, $y_{n+1:N}$ are model generations, $N>n$ is a hyperparameter, and we
assume the LM has good performance for ICL up to a sample size of $N$. Eq. (7)
can be estimated through autoregressive sampling. As long as we use the same
set of samples for its both terms, the resulted estimate will always be non-
negative, due to the convexity of the functional
$\rho\mapsto\inf_{y^{\prime}\in\mathcal{Y}^{\prime}_{I}}\mathbb{E}_{\rho(y_{*})}r(y^{\prime},y_{*};x_{*})$.

To understand (7), first consider a simplified scenario as follows: suppose
the LM $p_{M}$ is equivalent to a Bayesian model that assumes
$\\{(x_{i},y_{i})\\}$ are i.i.d. conditional on a latent variable $\theta$,
$p_{x}$ defines i.i.d. $x_{n+1:N}$, and $\\{x_{n+i},y_{n+i}\\}$ are
sufficiently informative so that the likelihood function $p(y=\cdot\mid
x=x_{*},\theta)$ determined by $\theta\mid x_{1:N},y_{1:N}$ is identifiable
given infinite samples. Then under mild technical conditions, as $N\to\infty$
(7) will become equivalent to

$\displaystyle\min_{y^{\prime}\in\mathcal{Y}^{\prime}_{I}}\mathbb{E}_{p_{M}(\theta\mid
x_{1:n},y_{1:n})}\mathbb{E}_{p(y\mid\theta,x=x_{*})}r(y^{\prime},y;x_{*})-\mathbb{E}_{p_{M}(\theta\mid
x_{1:n},y_{1:n})}\min_{y^{\prime}\in\mathcal{Y}^{\prime}_{I}}\mathbb{E}_{p(y\mid\theta,x=x_{*})}r(y^{\prime},y;x_{*}).$
(7’)

The equivalence is a consequence of Doob, (1949)’s theorem and can be proved
with the same idea as Fong et al., (2024). For completeness, we provide a
proof in Appendix A. (7’) is a subjective notion of _excess risk_. In other
words, it is the amount of _reducible_ risk should we have full knowledge
about the distribution of $y\mid x=x_{*}$, which can be determined given
either the latent $\theta$, or an infinite amount of missing data
$\\{x_{>n},y_{>n}\\}$. As noted in Xu and Raginsky, (2022), this is precisely
the intuition behind Bayesian epistemic uncertainty, and we recover standard
epistemic uncertainty measures (e.g., posterior variance for a regression
mean, or mutual information) if we return to simple scenarios where $r$ is the
square or log loss.

Within the Bayesian framework, (7) with a finite choice of $N$ will provide a
lower bound for (7’): by convexity the second term may become larger. The
intuition is that knowledge of the samples $\\{x_{n+1:N},y_{n+1:N}\\}$ does
not always allow for the full reduction of risk. It is possible to view the
lower bound as an indication of the “true epistemic uncertainty” (7’), and it
can be tightened if we choose $\\{x_{n+i}\\}$ to be more similar to $x_{*}$.
The bound will also be tight regardless of the choice of $N$ if the
uncertainty is “fully aleatoric” or “fully epistemic”, i.e., if the risk for
$y\mid x=x_{*}$ cannot be reduced by any number of additional observations
$(x_{n+1:N},y_{n+1:N})$ or can be fully reduced using a single
$(x_{n+1},y_{n+1})$. Alternatively, we can observe that we do not always need
the tightest bound for (7’): if all we can do is to collect $N-n$ real
samples, the remaining proportion of the risk will be _effectively
irreducible_.

As discussed in §1, the Bayesian view above may be justified through a common
belief that high-capacity LMs may approximate Bayesian inference. It is also
supported by the results of Wen et al., (2022, §2.6, §4), which imply that in
a multi-task setting, any $p_{M}$ with a strong average-case performance for
prediction will yield a similar value for (7) as the true Bayesian model.
Falck et al., (2024) investigated this belief empirically on synthetic low-
dimensional datasets, and found it to be valid for smaller choices of $N$,
although it breaks down as $N\to\infty$ becomes larger.333 Falck et al.,
(2024) also studied epistemic uncertainty quantification for ICL but
restricted to datasets where the method of Fong et al., (2024) is applicable.
Their method assumes $\\{x_{n+1:N},$ $y_{n+1:N}\\}$ can be modelled by a low-
dimensional statistical model, so that a posterior for the model parameter can
be constructed and visualized. This is unrealistic for free-form natural
language data.  Taken together, these results suggest that the Bayesian
perspective could be relevant when we restrict $N$ to a scope where ICL is
sample efficient.

Independent to the Bayesian perspective, Eq. (7) can also be understood
through its connection to recent works. Collier et al., (2022) studied a
broadly similar problem where a proportion of the combined uncertainty can be
reduced by conditioning on privilege information; this leads to a similar
measure for reducible uncertainty as (7), if we view $(x_{n+1:N},y_{n+1:N})$
as the latent “privilege information”. Johnson et al., (2024); Ahdritz et al.,
(2024) proposed methods that measure the correlation between consecutive
predictions $(y_{n+1},y_{*})$ given the same input $x_{n+1}=x_{*}$; as argued
in Johnson et al., (2024), _any_ learning system $p_{M}$ with complete
confidence for the true data distribution should lead to conditionally i.i.d.
$(y_{*},y_{n+1})$ given $I$, and any $p_{M}$ with a “fully epistemic”
uncertainty should produce $y_{*}=y_{n+1}$. It is clear that (7) matches these
behaviours at the extremes: it equals 0 in the former case, and correctly
indicate a full reduction of risk in the latter case (i.e., it equals
$R_{B}(I;p_{M},\mathcal{Y}^{\prime}_{I})$ assuming $r(y,y;I)\equiv 0$).The
Bayesian perspective provides additional insights to the works of Johnson et
al., (2024); Ahdritz et al., (2024). Eq. (7) generalizes their methodology by
allowing for a wider range of choices for $\\{x_{n+1:N}\\}$, and the above
discussion provides guidance on their choices.

Finally, we note that while (7) is generally applicable to MBR decoding, with
a trivial choice of $\mathcal{Y}_{I}^{\prime}$ it may take a trivial value: if
we use the Gibbs predictor which always samples from $p_{M}(\cdot\mid
x_{1:n},y_{1:n})$, we will find (7) to be zero; this is to be expected as the
predictor does not make any attempt to utilize the additional information. In
our experiments we choose $\mathcal{Y}_{I}^{\prime}$ to contain multiple
samples, one from each sample path for $y_{n+1:N}$. As we will see, this is
sufficient to provide meaningful estimates of epistemic uncertainty.

##  3 Experiments

###  3.1 Free-Form Question Answering

We first illustrate the proposed method on two QA tasks chosen by Lin et al.,
(2024): CoQA (Reddy et al.,, 2019) and NQOpen (Lee et al.,, 2019). CoQA
contains reading comprehension questions where the answer can generally be
deduced from the prompt, whereas NQOpen is an open-domain task and requires
information not present in the prompt. Kalai and Vempala, (2024) proved in
simplified scenarios that instruction-tuned LMs may have to be uncalibrated on
the latter type of task; we investigate their theoretical predictions
empirically.

Figure 1: Reliability diagrams for GPT-3.5 on QA tasks. Error bar denotes 95%
confidence interval for the average observed utility.

We follow the setup in Lin et al., (2024) and adopt the GPT-3.5 model
(OepnAI,, 2024), both for generation and to define the automated evaluation
criterion; the latter determines our utility function and in turn the
uncertainty measure (2).444 In this aspect our method differs from Lin et al.,
(2024), where uncertainty measures are defined with estimated entailment
relations or lexical metrics.  The evaluation criterion is defined using ICL,
by instructing the LM to rate the consistency between two responses based on
few-shot demonstrations (Lin et al.,, 2024, App. B.3). We reuse the model
samples released by Lin et al., (2024), which contains 20 sampled responses
for each query. Following their work we focus on the Gibbs predictor.

The results are shown in Fig. 1. As we can see, the LM’s subjective
uncertainty generally correlates well with the average observed utility. It is
slightly overconfident on the reading comprehension task, but much more so on
the open-domain task. Such a difference appears consistent with the
theoretical analysis of Kalai and Vempala, (2024).

###  3.2 In-Context Machine Translation

We now consider machine translation with ICL, where utility is defined through
the widely adopted chrF score (Popović,, 2015). chrF measures both semantic
and syntactic differences; the latter can be relevant in translation due to
the need to detect unnatural or invalid syntactic structures. The inherent
syntactic differences in the possible generations for $y\mid x$ constitute a
source of irreducible uncertainty, making machine translation a non-trivial
scenario to illustrate our uncertainty decomposition method.

We follow the setup of Agarwal et al., (2024) who demonstrated that ICL can
lead to steady improvements for machine translation. We adopt the FLORES+
dataset (NLLB Team et al.,, 2022), in particular the translation tasks from
English to the following languages: French, Tamil, Yue Chinese (Cantonese),
and Tigrinya. We use the following LMs: GPT-3.5, Gemini-1.5-Flash, and
Gemini-1.5-Pro (Gemini Team,, 2024), and vary the number of ICL shots
$n\in\\{4,16\\}$. For each task, we subsample 128 queries $(x_{*},y_{*})$ from
the datasets. For each query, we draw 35 samples from the LM to approximate
its predictive distribution, and another 5 samples to define the action space
$\mathcal{Y}^{\prime}_{I}$. For the quantification of epistemic uncertainty,
we set $N=n+8$, and sample $x_{n+1:N}$ by instructing an LM to rewrite the
test query $x_{*}$; see Appendix B for details.

$n$ | gemini-1.5-flash | gemini-1.5-pro | gpt-3.5
---|---|---|---
$4$ | 0.276 / 0.356 | 0.332 / 0.431 | 0.185 / 0.329
$16$ | 0.246 / 0.371 | 0.304 / 0.426 | 0.168 / 0.351
Table 1: Machine translation (English $\to$ Yue Chinese): gECE (Eq. (6),
$\downarrow$) and chrF ($\uparrow$) for varying choices of $n$.

We first evaluate the calibration of the combined subjective uncertainty on
the Yue Chinese task. As shown in Table 1, the LMs are generally poorly
calibrated, although calibration improves as the sample size $n$ increases.
Calibration plots are presented in Figure 3 in Appendix, which shows that all
LMs are overconfident. It is interesting to note an anticorrelation between
the task performance and calibration among the three LMs evaluated. We note
that Yue Chinese may constitute a _low-resource_ translation task (Haddow et
al.,, 2022) for which the LMs’ pretraining corpus is likely less informative.
As is also shown in Figure 3, calibration is better on the French task for
which more corpus is available.

Figure 2: Machine translation (English $\to$ Yue Chinese): reduction of
epistemic uncertainty (EU) vs total uncertainty (TU) as the ICL sample size
increases from $4$ to $16$.

We now investigate whether the LMs possess a coherent notion of epistemic and
aleatoric uncertainty, in particular whether epistemic uncertainty is the only
reducible component as sample size increases. For this purpose we plot the
reduction of total uncertainty (TU, (2)) against that of epistemic uncertainty
(EU, (7)) on each data point. Figure 2 shows that the two quantities have a
good match. Deviation from perfect equivalence is expected here, due to the
variance in the Monte-Carlo estimation for EU and TU.

Language | French | Tamil | Yue | Tigrinya
---|---|---|---|---
Avg. EU | 0.016 | 0.059 | 0.078 | 0.091
chrF | 0.737 | 0.392 | 0.329 | 0.084
# speakers (M) | 312 | 87 | 87 | 10
Table 2: Machine translation: average epistemic uncertainty on different
languages, obtained from gpt-3.5 using $n=4$ ICL shots. We also provide the
chrF score and the number of speakers (from Ethnologue,, 2024, in million) of
each language as an indication of its linguistic resource available.

Finally, we evaluate if the epistemic uncertainty measure (7) is meaningful,
by comparing its average value across different translation tasks: we expect
sensible notions of epistemic uncertainty to be higher on tasks for low-
resource languages, as they are likely less represented in the pretraining
corpus. Table 2 confirms this intuition: the LM demonstrates higher epistemic
uncertainty on lower-resource languages.

##  4 Conclusion

This work studies uncertainty quantification in free-form natural language
generation. Through a Bayesian decision-theoretic perspective, we derived
principled methods to quantify the model’s task-specific subjective
uncertainty and to evaluate its calibration. The proposed methods are also
connected to previous work, which provides additional justification for their
adoption. While the discussions (in particular those in §2.2 and §2.3) are not
necessarily novel outside the context of language modelling, within this
domain the decision-theoretic perspective appears new and addresses important
conceptual challenges in uncertainty quantification. Experiments demonstrate
that the methods extract meaningful uncertainty estimates from black-box LMs
and quantify their calibration.

Our discussion concerns the quantification of subjective uncertainty. In
applications where i.i.d. calibration samples are available, it would be
beneficial to recalibrate (Marx et al.,, 2022) the uncertainty measures, which
can be achieved through (6), or to incorporate the uncertainty measures in
conformal prediction (Quach et al.,, 2023). As the capabilities of LMs
continue to evolve, it is also conceivable that future-generation models may
find use in “one-of-its-kind” applications where post-calibration and
conformal approaches are inapplicable. In such scenarios, it would be crucial
to have principled measures for subjective uncertainty, as well as the tools
to dissect and understand the sources of this uncertainty, e.g., through the
proposed decomposition into epistemic and aleatoric uncertainty. It would also
be interesting for future work to investigate the consistency between the LM’s
verbalized uncertainty (Kadavath et al.,, 2022) and the subjective uncertainty
defined by its predictive distributions.

## References

  * Agarwal et al., (2024) Agarwal, R., Singh, A., Zhang, L. M., Bohnet, B., Chan, S., Anand, A., Abbas, Z., Nova, A., Co-Reyes, J. D., Chu, E., Behbahani, F., Faust, A., and Larochelle, H. (2024).  Many-Shot In-Context Learning.  arXiv:2404.11018 [cs].
  * Ahdritz et al., (2024) Ahdritz, G., Qin, T., Vyas, N., Barak, B., and Edelman, B. L. (2024).  Distinguishing the Knowable from the Unknowable with Language Models.  arXiv:2402.03563 [cs].
  * Aichberger et al., (2024) Aichberger, L., Schweighofer, K., Ielanskyi, M., and Hochreiter, S. (2024).  How many Opinions does your LLM have? Improving Uncertainty Estimation in NLG.
  * Akyürek et al., (2022) Akyürek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D. (2022).  What learning algorithm is in-context learning? investigations with linear models.  arXiv preprint arXiv:2211.15661.
  * Bertsch et al., (2023) Bertsch, A., Xie, A., Neubig, G., and Gormley, M. R. (2023).  It’s MBR All the Way Down: Modern Generation Techniques Through the Lens of Minimum Bayes Risk.  arXiv:2310.01387 [cs].
  * Bickel and Doksum, (1997) Bickel, P. J. and Doksum, K. A. (1997).  Mathematical statistics: basic ideas and selected topics.  Holden-Day Inc.
  * Brown et al., (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020).  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901.
  * Collier et al., (2022) Collier, M., Jenatton, R., Kokiopoulou, E., and Berent, J. (2022).  Transfer and marginalize: Explaining away label noise with privileged information.  In International Conference on Machine Learning, pages 4219–4237. PMLR.
  * Der Kiureghian and Ditlevsen, (2009) Der Kiureghian, A. and Ditlevsen, O. (2009).  Aleatory or Epistemic? Does it Matter?  Structural safety, 31(2):105–112.
  * Doob, (1949) Doob, J. L. (1949).  Application of the Theory of martingales.  Le calcul des probabilites et ses applications, pages 23–27.
  * Ethnologue, (2024) Ethnologue (2024).  Ethnologue.  https://www.ethnologue.com.
  * Falck et al., (2024) Falck, F., Wang, Z., and Holmes, C. C. (2024).  Are large language models bayesian? a martingale perspective on in-context learning.  In ICLR 2024 Workshop on Secure and Trustworthy Large Language Models.
  * Fong et al., (2024) Fong, E., Holmes, C., and Walker, S. G. (2024).  Martingale posterior distributions.  Journal of the Royal Statistical Society Series B: Statistical Methodology, 85(5):1357–1391.
  * Gemini Team, (2024) Gemini Team (2024).  Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context.
  * Haddow et al., (2022) Haddow, B., Bawden, R., Barone, A. V. M., Helcl, J., and Birch, A. (2022).  Survey of low-resource machine translation.  Computational Linguistics, 48(3):673–732.
  * Hahn and Goyal, (2023) Hahn, M. and Goyal, N. (2023).  A theory of emergent in-context learning as implicit structure induction.  arXiv preprint arXiv:2303.07971.
  * Huang et al., (2024) Huang, X., Li, S., Yu, M., Sesia, M., Hassani, H., Lee, I., Bastani, O., and Dobriban, E. (2024).  Uncertainty in Language Models: Assessment through Rank-Calibration.  arXiv:2404.03163 [cs, stat].
  * Jin et al., (2022) Jin, D., Jin, Z., Hu, Z., Vechtomova, O., and Mihalcea, R. (2022).  Deep learning for text style transfer: A survey.  Computational Linguistics, 48(1):155–205.
  * Johnson et al., (2024) Johnson, D. D., Tarlow, D., Duvenaud, D., and Maddison, C. J. (2024).  Experts Don’t Cheat: Learning What You Don’t Know By Predicting Pairs.  arXiv:2402.08733 [cs].
  * Kadavath et al., (2022) Kadavath, S., Conerly, T., Askell, A., Henighan, T., Drain, D., Perez, E., Schiefer, N., Hatfield-Dodds, Z., DasSarma, N., Tran-Johnson, E., Johnston, S., El-Showk, S., Jones, A., Elhage, N., Hume, T., Chen, A., Bai, Y., Bowman, S., Fort, S., Ganguli, D., Hernandez, D., Jacobson, J., Kernion, J., Kravec, S., Lovitt, L., Ndousse, K., Olsson, C., Ringer, S., Amodei, D., Brown, T., Clark, J., Joseph, N., Mann, B., McCandlish, S., Olah, C., and Kaplan, J. (2022).  Language Models (Mostly) Know What They Know.  arXiv:2207.05221 [cs].
  * Kalai and Vempala, (2024) Kalai, A. T. and Vempala, S. S. (2024).  Calibrated Language Models Must Hallucinate.  In Proceedings of the 56th Annual ACM Symposium on Theory of Computing.
  * Kendall and Gal, (2017) Kendall, A. and Gal, Y. (2017).  What Uncertainties do we Need in Bayesian deep learning for computer vision?  Advances in Neural Information Processing Systems, 30.
  * Kuhn et al., (2023) Kuhn, L., Gal, Y., and Farquhar, S. (2023).  Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation.  arXiv:2302.09664 [cs].
  * Lee et al., (2019) Lee, K., Chang, M.-W., and Toutanova, K. (2019).  Latent retrieval for weakly supervised open domain question answering.  In Korhonen, A., Traum, D., and Màrquez, L., editors, Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 6086–6096, Florence, Italy. Association for Computational Linguistics.
  * Lin et al., (2024) Lin, Z., Trivedi, S., and Sun, J. (2024).  Generating with confidence: Uncertainty quantification for black-box large language models.  Transactions on Machine Learning Research.
  * Marinacci, (2015) Marinacci, M. (2015).  Model uncertainty.  Journal of the European Economic Association, 13(6):1022–1100.
  * Marx et al., (2022) Marx, C., Zhao, S., Neiswanger, W., and Ermon, S. (2022).  Modular Conformal Calibration.  arXiv:2206.11468 [cs, stat].
  * Murphy and Winkler, (1977) Murphy, A. H. and Winkler, R. L. (1977).  Reliability of subjective probability forecasts of precipitation and temperature.  Journal of the Royal Statistical Society Series C: Applied Statistics, 26(1):41–47.
  * Naeini et al., (2015) Naeini, M. P., Cooper, G., and Hauskrecht, M. (2015).  Obtaining well calibrated probabilities using bayesian binning.  In Proceedings of the AAAI conference on artificial intelligence, volume 29.
  * NLLB Team et al., (2022) NLLB Team, Costa-jussà, M. R., Cross, J., Çelebi, O., Elbayad, M., Heafield, K., Heffernan, K., Kalbassi, E., Lam, J., Licht, D., Maillard, J., Sun, A., Wang, S., Wenzek, G., Youngblood, A., Akula, B., Barrault, L., Mejia-Gonzalez, G., Hansanti, P., Hoffman, J., Jarrett, S., Sadagopan, K. R., Rowe, D., Spruit, S., Tran, C., Andrews, P., Ayan, N. F., Bhosale, S., Edunov, S., Fan, A., Gao, C., Goswami, V., Guzmán, F., Koehn, P., Mourachko, A., Ropers, C., Saleem, S., Schwenk, H., and Wang, J. (2022).  No language left behind: Scaling human-centered machine translation.
  * OepnAI, (2024) OepnAI (2024).  Models - OpenAI API.  https://platform.openai.com/docs/models/gpt-3-5-turbo.
  * Popović, (2015) Popović, M. (2015).  chrf: character n-gram f-score for automatic mt evaluation.  In Proceedings of the tenth workshop on statistical machine translation, pages 392–395.
  * Quach et al., (2023) Quach, V., Fisch, A., Schuster, T., Yala, A., Sohn, J. H., Jaakkola, T. S., and Barzilay, R. (2023).  Conformal Language Modeling.  arXiv:2306.10193 [cs].
  * Reddy et al., (2019) Reddy, S., Chen, D., and Manning, C. D. (2019).  Coqa: A conversational question answering challenge.  Transactions of the Association for Computational Linguistics, 7:249–266.
  * Savage, (1954) Savage, L. J. (1954).  The Foundations of Statistics.  Wiley.
  * Wen et al., (2022) Wen, Z., Osband, I., Qin, C., Lu, X., Ibrahimi, M., Dwaracherla, V., Asghari, M., and Van Roy, B. (2022).  From Predictions to Decisions: The Importance of Joint Predictive Distributions.  arXiv:2107.09224 [cs, stat].
  * Xie et al., (2021) Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. (2021).  An explanation of in-context learning as implicit Bayesian inference.  arXiv preprint arXiv:2111.02080.
  * Xu and Raginsky, (2022) Xu, A. and Raginsky, M. (2022).  Minimum Excess Risk in Bayesian learning.  IEEE Transactions on Information Theory, 68(12):7935–7955.
  * Xu et al., (2019) Xu, Y., Zhao, S., Song, J., Stewart, R., and Ermon, S. (2019).  A theory of usable information under computational constraints.  In International Conference on Learning Representations.
  * Ye et al., (2024) Ye, N., Yang, H., Siah, A., and Namkoong, H. (2024).  Pre-training and in-context learning IS bayesian inference a la de finetti.  In ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models.
  * Zhang et al., (2023) Zhang, J., Li, Z., Das, K., Malin, B. A., and Kumar, S. (2023).  SAC3: Reliable Hallucination Detection in Black-Box Language Models via Semantic-aware Cross-check Consistency.  arXiv.  arXiv:2311.01740 [cs].

##  Appendix A Proof for the Equivalence between (7) and (7’)

######  Claim A.1.

Suppose $\mathcal{X},\mathcal{Y}$ are finite sets, and
$\sup_{y^{\prime},y,x}|r(y^{\prime},y;x)|<\infty$. Suppose there exists a
Bayesian model with prior $\pi$ over a discrete parameter $\theta\in\Theta$
and a (conditional) likelihood function $p(y\mid x,\theta)$, s.t. for all
$(n,x_{1:n},y_{1:n},x_{*})$ we have

$p_{M}(y_{n+1}=\cdot\mid x_{n+1}=x_{*},x_{1:n},y_{1:n})=\int\pi(d\theta\mid
x_{1:n},y_{1:n})p(y=\cdot\mid x=x_{*},\theta)$

where $\pi(d\theta\mid
x_{1:n},y_{1:n})\propto\pi(d\theta)\prod_{i=1}^{n}p(y=y_{i}\mid
x=x_{i},\theta)$ denotes the parameter posterior. Suppose (7) is defined using
$x_{n+1:N}\overset{i.i.d.}{\sim}p_{x,1}$, and that for all
$x_{*}\in\mathcal{X}$ and $\pi$-a.e. $\theta$ we have

$\lim_{n\to\infty}\mathbb{E}_{x_{1:n}\sim p_{x,1},y_{i}\sim p(y=\cdot\mid
x=x_{i},\theta)}\|p_{M}(y_{n+1}=\cdot\mid
x_{n+1}=x_{*},x_{1:n},y_{1:n})-p(y=\cdot\mid
x=x_{*},\theta)\|_{\ell_{2}(\mathcal{Y})}^{2}=0,$ (8)

where $\|f\|_{\ell_{2}(\mathcal{Y})}:=\sqrt{\sum_{y\in\mathcal{Y}}f(y)^{2}}$
denotes the $\ell_{2}$ norm. Then for $p_{x,1}$-a.e. $(x_{1:n},x_{*})$ and
$p_{M}$-a.e. $y_{1:n}$, the $n\to\infty$ limit of (7) is equivalent to (7’).

In the above, (8) is the assumed identifiability condition for the likelihood
function. We expect the numerous technical restrictions to be relaxable, but
refrain from a more general proof for brevity. The main conditions that enable
the equivalence are that _(i)_ $p_{M}$ can be augmented to define an
exchangeable (or c.i.d.) model for $(x,y)$, and _(ii)_ the likelihood function
is identifiable.

###### Proof.

We will show that each of the two terms in (7) and (7’) are equivalent.

Let us introduce the following notations: define
$\mathcal{Z}:=\mathcal{X}\times\mathcal{Y}$ and, for any $x_{i},y_{i}$,
$z_{i}:=(x_{i},y_{i})\in\mathcal{Z}$. For all $n\geq 0$, define
$\bar{p}_{M}(z_{n+1}=(x,y)\mid z_{1:n})=p_{x,1}(x)p_{M}(y_{n+1}=y\mid
x_{n+1}=x,x_{1:n},y_{1:n}),\bar{p}(z=(x,y)\mid\theta)=p_{x,1}(x)p(y\mid\theta,x)$.
Clearly, $\bar{p}_{M}$ is equivalent to a Bayesian model with prior $\pi$ and
the factorized likelihood $\bar{p}$. Thus,
$z_{n+1:N+1}\sim\bar{p}_{M}(\cdot\mid z_{1:n})$ are exchangeable, and we have,
for all $n,z_{1:n},N>n,y^{\prime}\in\mathcal{Y}$ and $p_{x,1}$-almost every
$x_{*}$,

$\mathbb{E}_{\bar{p}_{M}}(r(y^{\prime},y_{N+1};x_{*})\mid
z_{1:n},x_{N+1}=x_{*})=\mathbb{E}_{\bar{p}_{M}}(r(y^{\prime},y_{n+1};x_{*})\mid
z_{1:n},x_{n+1}=x_{*}).$

By definitions, the terms above equal the first term in (7) and (7’),
respectively, with their outmost infimum removed. Retaking infimum proves the
equivalence of the first terms.

For the second term, observe that by the boundedness of $r$ and the
discreteness of $\mathcal{Y}$, for all $x_{*}\in\mathcal{X}$ the function
$R_{x_{*}}(\rho):=\inf_{y^{\prime}\in\mathcal{Y}^{\prime}_{I}}\mathbb{E}_{y\sim\rho}r(y^{\prime},y;x_{*})$
is Lipschitz continuous w.r.t. the $\ell_{2}(\mathcal{Y})$ norm.555Note that
any distribution $\rho$ over $\mathcal{Y}$ can be identified with a
probability mass function in $\ell_{2}(\mathcal{Y})$ since $\mathcal{Y}$ is
discrete. Thus, for $\pi$-a.e. $\theta$ we have

$\lim_{N\to\infty}\mathbb{E}_{z_{1:N-n}\overset{i.i.d.}{\sim}\bar{p}(z\mid\theta)}|R_{x_{*}}(p_{M}(y=\cdot\mid
x=x_{*},z_{1:N-n}))-R_{x_{*}}(p(y=\cdot\mid x=x_{*},\theta))|=0$

following (8). It follows by the boundedness of $R_{x_{*}}(\cdot)$ and the
dominated convergence theorem that

$\displaystyle\phantom{=}\lim_{N\to\infty}\mathbb{E}_{\theta\sim\pi,z_{1:N-n}\sim\bar{p}(z\mid\theta)}R_{x_{*}}(p_{M}(y=\cdot\mid
x=x_{*},z_{1:N-n}))=\mathbb{E}_{\theta\sim\pi}R_{x_{*}}(p(y=\cdot\mid
x=x_{*},\theta)).$ (9)

The RHS above equals the expectation of the second term in (7’) over
$z_{1:n}\sim\bar{p}_{M}$. Denote the second term in (7) as $u_{N}(z_{1:n})$.
By definition of $\bar{p}_{M}$ and its exchangeability, as well as the
convexity of $R_{x_{*}}(\cdot)$, we have

$\displaystyle\mathbb{E}_{\bar{p}_{M}(z_{1:n})}u_{N}(z_{1:n})$
$\displaystyle=\mathbb{E}_{\bar{p}_{M}(z_{1:n})}\mathbb{E}_{\bar{p}_{M}(z_{n+1:N}\mid
z_{1:n})}R_{x_{*}}(\bar{p}_{M}(y_{N+1}=\cdot\mid x_{N+1}=x_{*},z_{1:N}))$
$\displaystyle\leq\mathbb{E}_{\bar{p}_{M}(z_{n+1:N})}R_{x_{*}}(\mathbb{E}_{\bar{p}_{M}(z_{1:n}\mid
z_{n+1:N})}\bar{p}_{M}(y_{N+1}=\cdot\mid x_{N+1}=x_{*},z_{1:N}))$
$\displaystyle=\mathbb{E}_{\bar{p}_{M}(z_{1:N-n})}R_{x_{*}}(\bar{p}_{M}(y_{N-n+1}=\cdot\mid
x_{N-n+1}=x_{*},z_{1:N-n}))$
$\displaystyle=\mathbb{E}_{\theta\sim\pi,z_{1:N-n}\sim\bar{p}(z\mid\theta)}R_{x_{*}}(p_{M}(y=\cdot\mid
x=x_{*},z_{1:N-n})).$

Combining with (9) and applying the dominated convergence theorem yield

$\displaystyle\mathbb{E}_{\bar{p}_{M}(z_{1:n})}\lim_{N\to\infty}u_{N}(z_{1:n})=\lim_{N\to\infty}\mathbb{E}_{\bar{p}_{M}(z_{1:n})}u_{N}(z_{1:n})\leq\mathbb{E}_{\bar{p}_{M}(z_{1:n})}\mathbb{E}_{\pi(\theta\mid
z_{1:n})}R_{x_{*}}(p(y=\cdot\mid x=x_{*},\theta)).$ (10)

On the other hand, we have

$\displaystyle u_{N}(z_{1:n})$
$\displaystyle=\mathbb{E}_{\bar{p}_{M}(z_{n+1:N}\mid
z_{1:n})}R_{x_{*}}(\bar{p}_{M}(y=\cdot\mid x=x_{*},z_{1:N}))$
$\displaystyle=\mathbb{E}_{\bar{p}_{M}(z_{n+1:N}\mid
z_{1:n})}R_{x_{*}}(\mathbb{E}_{\pi(\theta\mid z_{1:N})}p(y=\cdot\mid
x=x_{*},\theta))$ $\displaystyle\geq\mathbb{E}_{\bar{p}_{M}(z_{n+1:N}\mid
z_{1:n})}\mathbb{E}_{\pi(\theta\mid z_{1:N})}R_{x_{*}}(p(y=\cdot\mid
x=x_{*},\theta))$ $\displaystyle=\mathbb{E}_{\pi(\theta\mid
z_{1:n})}R_{x_{*}}(p(y=\cdot\mid x=x_{*},\theta)),$

so the same holds for $\lim_{N\to\infty}u_{N}(z_{1:n})$. Comparing with (10)
we find that equality must hold for $\bar{p}_{M}$-a.e. $z_{1:n}$. This proves
the equivalence for the second terms in (7) and (7’), and consequently the
original claim. ∎

##  Appendix B Additional Experimental Details

In both experiments we use the following versions of LM APIs:
gpt-3.5-turbo-0125, gemini-1.5-flash-001, gemini-1.5-pro-001.

The machine translation experiment is implemented as follows: for each test
query $x_{*}$, we sample the ICL demonstrations $(x_{1:n},y_{1:n})$, a single
set of $x_{n+1:N}$, and $5$ sets of $y_{n+1:N}\sim p_{M}(x_{1:N},y_{1:n})$;
then for each path sample $y_{n+1:N}$ we draw $8$ samples from
$p_{M}(y_{*}\mid x_{1:N},y_{1:N},x_{*})$. The action space is defined using
$5\times 1$ samples from each path sample, and the expectations in (2) and (7)
using the remaining $5\times 7$ samples. For each $x_{*}$, we reuse the same
set of samples for $(x_{n+1:N},x_{1:n},y_{1:n})\mid x_{*}$ across all
experiments. The completion inputs $x_{n+1:N}$ are generated using
Gemini-1.5-Flash with the following prompt:

⬇

Please generate {K} sentences that convey a broadly similar meaning as the one
provided, ensuring they are of similar length and use varied wording. Place a
blank line after each sentence. Avoid adding any extra explanations.

{x_*}

In the above, $x_{*}$ denotes the test query. For simplicity, we report the
chrF scores evaluated using the final samples $y_{*}\mid
x_{1:N},y_{1:N},x_{*}$, which is similar to the reinforced ICL method (Agarwal
et al.,, 2024).

Figure 3: Machine translation: reliability diagrams for a subset of
experiments. Error bar indicates 95% confidence interval for the expected
observed utility.


# Analytical Expression and Deconstruction of the Volume of the
Controllability Ellipsoid ††thanks: Work supported by the National Natural
Science Foundation of China (Grant No. 61273005)

Mingwang Zhao  Information Science and Engineering School, Wuhan University of
Science and Technology, Wuhan, Hubei, 430081, China
Tel.: +86-27-68863897
Work supported by the National Natural Science Foundation of China (Grant No.
61273005)

###### Abstract

In this article, we present three theorems and develop an effective analytical
method to compute analytically the volume of the controllability ellipsoid for
the linear discrete-time (LDT) systems with $n$ different eigenvalues.
Furthermore, by deconstructing the analytical expression of the volume, some
factors on the shape of the ellipsoid, the side length of its circumscribed
rhomboid, the evenness of the eigenvalue distribution of the LDT system are
constructed. Based on the analytical expression of the volume and these
factors, the control ability can be defined, computing, analyzed, and
optimized for the LDT systems.

###### keywords:

volume computation , controllability ellipsoid , controllability Grammian
matrix , discrete-time systems , state controllability

††journal: Journal Name

##  1 Introduction

In control theory, linear discrete-time (LDT) systems can be formulated as
follows:

$x_{k+1}=Ax_{k}+Bu_{k},\quad x_{k}\in R^{n},u_{k}\in R^{r},$ (1)

where $x_{k}$ and $u_{k}$ are the state variable and input variable,
respectively, and matrices $A\in R^{n\times n}$ and $B\in R^{n\times r}$ are
the state matrix and input matrix in the system models, respectively, [6] [2].
To investigate the controllability of the LDT systems (1), the controllability
Grammian matrix can be defined as follows

$G_{N}=\sum_{i=0}^{N-1}A^{i}B\left(A^{i}B\right)^{T},\;N\geq n$ (2)

That the rank of the Grammian matrix $G_{N}$ is $n$, the dimension of the
state space of the LDT systems (1), is the well-known criterion on the state
controllability. By the controllability Grammian matrix, the controllability
ellipsoid that can describe the maximum controllable region under the total-
energy constraint $\left(\sum_{k=0}^{N-1}\|u_{N}\|^{2}_{2}\leq 1\right)$ can
be defined as follows [3] [7] [10] [8] [1]

$E_{N}=\left\\{x\left|x=G_{N}^{1/2}z_{N},\forall z_{N}\in
R^{n}:\|z_{N}\|_{2}\leq 1\right.\right\\}$ (3)

In papers [11], [4], [9], and [5], the determinant value
$\det\left(G_{N}\right)$ and the minimum eigenvalue
$\lambda_{\textnormal{min}}\left(G_{N}\right)$ of the controllability Grammian
matrix $G_{N}$, correspondingly the volume
$\textnormal{vol}\left(E_{N}\right)$ and the minimum radius
$r_{\textnormal{min}}\left(E_{N}\right)$ of the controllability ellipsoid
$E_{N}$, can be used to quantify the control ability of the input variables to
the state space, and then be chosen as the objective functions for optimizing
and promoting the control ability of the dynamical systems. Due to lack of the
analytical computing of the determinant $\det\left(G_{N}\right)$ and
eigenvalue $\lambda_{\textnormal{min}}\left(G_{N}\right)$, correspondingly the
volume $\textnormal{vol}\left(E_{N}\right)$ and the radius
$r_{\textnormal{min}}\left(E_{N}\right)$, these optimizing problems for the
control ability are solved very difficulty, and few achievements about that
have been made.

In this paper, the analytical volume-computation of the controllability
ellipsoid $E_{N}$, when the system (1) is a sigle input system, is studied and
an analytical expression on that $N\rightarrow\infty$ will be proven. By
deconstructing the analytical volume expression, some factors for the
ellipsoid $E_{N}$, such as, the shape factor, the minimum circumscribed
rhomboid, etc, can be got. Therefore, the analytical volume and the shape
factor of the ellipsoid, the minimum side length of the rhomboid can be used
to describe the control ability and can be chosen as the objective functions
and the constraint conditions for optimizing and promoting the control
ability. Because of the analytical expression of these objective functions and
constraint conditions, the optimizing problems will be solved with very
effective optimizing computation.

##  2 The analytical volume-computing of the controllability ellipsoid for the
matrix $A$ with $n$ different eigenvalues

Based on the linear system theory [6], [2], the LDT system (1) can be
transformed as the Jordan canonical form, and especially the LDT system (1)
with $n$ different eigenvalues can be transformed as the diagonal canonical
form. Obviously, if the Jordan canonical form is $\Sigma(P^{-1}AP,P^{-1}B)$
with the Jordan transformation matrix $P$, the corresponding controllability
Grammian matrix can be expressed respectively as

$\displaystyle\overline{G}_{N}=P^{-1}G_{N}P^{-T}$ (4)

And then, the determinant $\det\left(\overline{G}_{N}\right)$ is $\left(\det
P\right)^{-2}\det\left(G_{N}\right)$ and the volume of the controllability
ellipsoid is $|\det P|^{-1}\textnormal{vol}\left(E_{N}\right)$. In this paper,
the determinant and ellipsoid volume for the diagonal canonical form,
respectively, are computed analytically and related results can be generalized
to the general systems $\Sigma(A,B)$.

When the system $\Sigma(A,B)$ is a sigle-input diagonal canonical form as

$\displaystyle
A=\textnormal{diag}\\{\lambda_{1},\lambda_{2},\dots,\lambda_{n}\\},\;B=[b_{1},b_{2},\dots,b_{n}]^{T}$
(5)

the controllability Grammian matrix can be rewritten as

$\displaystyle G_{N}$
$\displaystyle=\sum_{i=0}^{N-1}A^{i}B\left(A^{i}B\right)^{T}$
$\displaystyle=\sum_{i=0}^{N-1}\left[\begin{array}[]{cccc}b_{1}^{2}\lambda_{1}^{2i}&b_{1}b_{2}\lambda_{1}^{i}\lambda_{2}^{i}&\cdots&b_{1}b_{n}\lambda_{1}^{i}\lambda_{n}^{i}\\\
b_{1}b_{2}\lambda_{1}^{i}\lambda_{2}^{i}&b_{2}^{2}\lambda_{2}^{2i}&\cdots&b_{2}b_{n}\lambda_{2}^{i}\lambda_{n}^{i}\\\
\vdots&\vdots&\ddots&\vdots\\\
b_{1}b_{n}\lambda_{1}^{i}\lambda_{n}^{i}&b_{2}b_{n}\lambda_{2}^{i}\lambda_{n}^{i}&\cdots&b_{n}^{2}\lambda_{n}^{2i}\end{array}\right]$
(10)
$\displaystyle=\left[\begin{array}[]{cccc}b_{1}^{2}\frac{1-\lambda_{1}^{2N}}{1-\lambda_{1}^{2}}&b_{1}b_{2}\frac{1-\lambda_{1}^{N}\lambda_{2}^{N}}{1-\lambda_{1}\lambda_{2}}&\cdots&b_{1}b_{n}\frac{1-\lambda_{1}^{N}\lambda_{n}^{N}}{1-\lambda_{1}\lambda_{n}}\\\
b_{1}b_{2}\frac{1-\lambda_{1}^{N}\lambda_{2}^{N}}{1-\lambda_{1}\lambda_{2}}&b_{2}^{2}\frac{1-\lambda_{2}^{2N}}{1-\lambda_{2}^{2}}&\cdots&b_{2}b_{n}\frac{1-\lambda_{2}^{N}\lambda_{n}^{N}}{1-\lambda_{2}\lambda_{n}}\\\
\vdots&\vdots&\ddots&\vdots\\\
b_{1}b_{n}\frac{1-\lambda_{1}^{N}\lambda_{n}^{N}}{1-\lambda_{1}\lambda_{n}}&b_{2}b_{n}\frac{1-\lambda_{2}^{N}\lambda_{n}^{N}}{1-\lambda_{2}\lambda_{n}}&\cdots&b_{n}^{2}\frac{1-\lambda_{n}^{2N}}{1-\lambda_{n}^{2}}\end{array}\right]$
(15)

When all eigenvalues $\lambda_{i}\in(-1,1),i=\overline{1,n}$, and
$N\rightarrow\infty$, we have

$\displaystyle
G_{\infty}=\left[\begin{array}[]{cccc}\frac{b_{1}^{2}}{1-\lambda_{1}^{2}}&\frac{b_{1}b_{2}}{1-\lambda_{1}\lambda_{2}}&\cdots&\frac{b_{1}b_{n}}{1-\lambda_{1}\lambda_{n}}\\\
\frac{b_{1}b_{2}}{1-\lambda_{1}\lambda_{2}}&\frac{b_{2}^{2}}{1-\lambda_{2}^{2}}&\cdots&\frac{b_{2}b_{n}}{1-\lambda_{2}\lambda_{n}}\\\
\vdots&\vdots&\ddots&\vdots\\\
\frac{b_{1}b_{n}}{1-\lambda_{1}\lambda_{n}}&\frac{b_{2}b_{n}}{1-\lambda_{2}\lambda_{n}}&\cdots&\frac{b_{n}^{2}}{1-\lambda_{n}^{2}}\end{array}\right]$
(20)

Before discussing the analytical volume computing of the infinite-time
controllability ellipsoid $E_{\infty}$ for the diagonal canonical form, a
theorem about the determinant of the matrix $G_{\infty}$ is put forward and
proven as follows.

###### Theorem 1

For all eigenvalues $\lambda_{i}\in(-1,1),i=\overline{1,n}$, we have

$\displaystyle F^{\lambda_{1},\lambda_{2},\dots,\lambda_{n}}_{\infty}$
$\displaystyle=\det\left[\begin{array}[]{cccc}\frac{1}{1-\lambda_{1}^{2}}&\frac{1}{1-\lambda_{1}\lambda_{2}}&\cdots&\frac{1}{1-\lambda_{1}\lambda_{n}}\\\
\frac{1}{1-\lambda_{1}\lambda_{2}}&\frac{1}{1-\lambda_{2}^{2}}&\cdots&\frac{1}{1-\lambda_{2}\lambda_{n}}\\\
\vdots&\vdots&\ddots&\vdots\\\
\frac{1}{1-\lambda_{1}\lambda_{n}}&\frac{1}{1-\lambda_{2}\lambda_{n}}&\cdots&\frac{1}{1-\lambda_{n}^{2}}\end{array}\right]$
(25) $\displaystyle=\left[\prod_{1\leq i<j\leq
n}\left(\frac{\lambda_{j}-\lambda_{i}}{1-\lambda_{i}\lambda_{j}}\right)^{2}\right]\times\left(\prod_{i=1}^{n}\frac{1}{1-\lambda_{i}^{2}}\right)$
(26)

Proof. The theorem can be proven by induction method as follows.

(1) When $n=1$ and $2$, we have

$\displaystyle F^{\lambda_{1}}_{\infty}$
$\displaystyle=\det\left[\frac{1}{1-\lambda_{1}^{2}}\right]=\frac{1}{1-\lambda_{1}^{2}}$
(27) $\displaystyle F^{\lambda_{1},\lambda_{2}}_{\infty}$
$\displaystyle=\det\left[\begin{array}[]{cc}\frac{1}{1-\lambda_{1}^{2}}&\frac{1}{1-\lambda_{1}\lambda_{2}}\\\
\frac{1}{1-\lambda_{1}\lambda_{2}}&\frac{1}{1-\lambda_{2}^{2}}\end{array}\right]=\frac{\left(\lambda_{{}_{2}}-\lambda_{1}\right)^{2}}{\left(1-\lambda_{1}\lambda_{2}\right)^{2}\left(1-\lambda_{1}^{2}\right)\left(1-\lambda_{2}^{2}\right)}$
(30)

And then, for $n=1$ and $2$, Eq. (26) holds.

(2) It is assumed that for a given $k$, Eq. (26) holds for $n=k-1$, that is,
we have,

$\displaystyle
F^{\lambda_{1},\lambda_{2},\dots,\lambda_{k}-1}_{\infty}=\left[\prod_{1\leq
i<j\leq
k-1}\left(\frac{\lambda_{j}-\lambda_{i}}{1-\lambda_{i}\lambda_{j}}\right)^{2}\right]\times\left(\prod_{i=1}^{k-1}\frac{1}{1-\lambda_{i}^{2}}\right)$
(31)

(3) For $n=k$, we have

$\displaystyle F_{\infty}^{\lambda_{1},\lambda_{2},\dots,\lambda_{k}}$
$\displaystyle=\det\left[\begin{array}[]{cccc}\frac{1}{1-\lambda_{1}^{2}}&\frac{1}{1-\lambda_{1}\lambda_{2}}&\cdots&\frac{1}{1-\lambda_{1}\lambda_{k}}\\\
\frac{1}{1-\lambda_{1}\lambda_{2}}&\frac{1}{1-\lambda_{2}^{2}}&\cdots&\frac{1}{1-\lambda_{2}\lambda_{k}}\\\
\vdots&\vdots&\ddots&\vdots\\\
\frac{1}{1-\lambda_{1}\lambda_{k}}&\frac{1}{1-\lambda_{2}\lambda_{k}}&\cdots&\frac{1}{1-\lambda_{k}^{2}}\end{array}\right]$
(36)
$\displaystyle=\det\left[\begin{array}[]{cccc}\frac{1}{1-\lambda_{1}^{2}}&0&\cdots&0\\\
0&q_{22}&\cdots&q_{2k}\\\ \vdots&\vdots&\ddots&\vdots\\\
0&q_{2k}&\cdots&q_{kk}\end{array}\right]$ (41)

where

$\displaystyle q_{22}$
$\displaystyle=\frac{1}{1-\lambda_{2}^{2}}-\frac{1}{1-\lambda_{1}\lambda_{2}}\times\frac{1-\lambda_{1}^{2}}{1-\lambda_{1}\lambda_{2}}$
$\displaystyle=\frac{1-2\lambda_{1}\lambda_{2}-\lambda_{1}^{2}\lambda_{2}^{2}-\left(1-\lambda_{1}^{2}-\lambda_{2}^{2}+\lambda_{1}^{2}\lambda_{2}^{2}\right)}{\left(1-\lambda_{2}^{2}\right)\left(1-\lambda_{1}\lambda_{2}\right)^{2}}$
$\displaystyle=\frac{\left(\lambda_{2}-\lambda_{1}\right)^{2}}{\left(1-\lambda_{2}^{2}\right)\left(1-\lambda_{1}\lambda_{2}\right)^{2}}$
(42) $\displaystyle q_{2k}$
$\displaystyle=\frac{1}{1-\lambda_{2}\lambda_{k}}-\frac{1}{1-\lambda_{1}\lambda_{k}}\times\frac{1-\lambda_{1}^{2}}{1-\lambda_{1}\lambda_{2}}$
$\displaystyle=\frac{\left(1-\lambda_{1}\lambda_{2}\right)\left(1-\lambda_{1}\lambda_{k}\right)-\left(1-\lambda_{2}\lambda_{k}\right)\left(1-\lambda_{1}^{2}\right)}{\left(1-\lambda_{1}\lambda_{2}\right)\left(1-\lambda_{1}\lambda_{k}\right)\left(1-\lambda_{2}\lambda_{k}\right)}$
$\displaystyle=\frac{1-\lambda_{1}\lambda_{2}-\lambda_{1}\lambda_{k}+\lambda_{1}^{2}\lambda_{2}\lambda_{k}-\left(1-\lambda_{2}\lambda_{k}-\lambda_{1}^{2}+\lambda_{1}^{2}\lambda_{2}\lambda_{k}\right)}{\left(1-\lambda_{1}\lambda_{2}\right)\left(1-\lambda_{1}\lambda_{k}\right)\left(1-\lambda_{2}\lambda_{k}\right)}$
$\displaystyle=\frac{-\lambda_{1}\lambda_{2}-\lambda_{1}\lambda_{k}-\left(-\lambda_{2}\lambda_{k}-\lambda_{1}^{2}\right)}{\left(1-\lambda_{1}\lambda_{2}\right)\left(1-\lambda_{1}\lambda_{k}\right)\left(1-\lambda_{2}\lambda_{k}\right)}$
$\displaystyle=\frac{\left(\lambda_{2}-\lambda_{1}\right)\left(\lambda_{k}-\lambda_{1}\right)}{\left(1-\lambda_{1}\lambda_{2}\right)\left(1-\lambda_{1}\lambda_{k}\right)\left(1-\lambda_{2}\lambda_{k}\right)}$
(43) $\displaystyle\dots$

And then, we have

$\displaystyle F_{\infty}^{\lambda_{1},\lambda_{2},\dots,\lambda_{k}}$
$\displaystyle=\frac{1}{1-\lambda_{1}^{2}}\det\left[\begin{array}[]{ccc}\frac{\left(\lambda_{2}-\lambda_{1}\right)^{2}}{\left(1-\lambda_{2}^{2}\right)\left(1-\lambda_{1}\lambda_{2}\right)^{2}}&\cdots&\frac{\left(\lambda_{2}-\lambda_{1}\right)\left(\lambda_{k}-\lambda_{1}\right)}{\left(1-\lambda_{1}\lambda_{2}\right)\left(1-\lambda_{1}\lambda_{k}\right)\left(1-\lambda_{2}\lambda_{k}\right)}\\\
\vdots&\ddots&\vdots\\\
\frac{\left(\lambda_{2}-\lambda_{1}\right)\left(\lambda_{k}-\lambda_{1}\right)}{\left(1-\lambda_{1}\lambda_{2}\right)\left(1-\lambda_{1}\lambda_{k}\right)\left(1-\lambda_{2}\lambda_{k}\right)}&\cdots&\frac{\left(\lambda_{k}-\lambda_{1}\right)^{2}}{\left(1-\lambda_{k}^{2}\right)\left(1-\lambda_{1}\lambda_{k}\right)^{2}}\end{array}\right]$
(47)
$\displaystyle=\frac{1}{1-\lambda_{1}^{2}}\prod_{i=2}^{k}\left(\frac{\lambda_{i}-\lambda_{1}}{1-\lambda_{i}\lambda_{1}}\right)^{2}\det\left[\begin{array}[]{ccc}\frac{1}{1-\lambda_{2}^{2}}&\cdots&\frac{1}{1-\lambda_{2}\lambda_{k}}\\\
\vdots&\ddots&\vdots\\\
\frac{1}{1-\lambda_{2}\lambda_{k}}&\cdots&\frac{1}{1-\lambda_{k}^{2}}\end{array}\right]$
(51)
$\displaystyle=\frac{1}{1-\lambda_{1}^{2}}\prod_{i=2}^{k}\left(\frac{\lambda_{i}-\lambda_{1}}{1-\lambda_{i}\lambda_{1}}\right)^{2}\times
F_{\infty}^{\lambda_{2},\lambda_{3},\dots,\lambda_{k}}$ (52)

Therefore, by Eq. (31) and Eq. (52), we have, Eq. (26) holds for $n=k$.

In summary, the theorem is proven by the inductive method.

Based on Theorem 1, the determinant of the controllability Grammian matrix and
the volume of the controllability ellipsoid for the diagonal canonical form
are as follows

$\displaystyle\det\left(G_{\infty}\right)$
$\displaystyle=F_{N}^{\lambda_{1},\lambda_{2},\dots,\lambda_{n}}\prod_{i=1}^{n}b_{i}^{2}$
(53) $\displaystyle\textnormal{vol}\left(E_{\infty}\right)$
$\displaystyle=H_{n}\sqrt{\det\left(G_{\infty}\right)}=H_{n}\sqrt{F_{N}^{\lambda_{1},\lambda_{2},\dots,\lambda_{n}}\prod_{i=1}^{n}b_{i}^{2}}$
$\displaystyle=H_{n}\left|\prod_{1\leq i<j\leq
n}\frac{\lambda_{j}-\lambda_{i}}{1-\lambda_{i}\lambda_{j}}\right|\times\left|\prod_{i=1}^{n}\frac{b_{i}}{\left(1-\lambda_{i}^{2}\right)^{1/2}}\right|$
(54)

where the hypersphere volume-coefficient $H_{n}$ and the Gamma function
$\varGamma(s)$ can be defined as

$\displaystyle H_{n}$
$\displaystyle=\frac{\pi^{n/2}}{\varGamma\left(\frac{n}{2}+1\right)}$ (55)
$\displaystyle\varGamma(s)$
$\displaystyle=\left\\{\begin{array}[]{ll}(s-1)\varGamma(s-1)&s>1\\\
\sqrt{\pi}&s=1/2\end{array}\right.$ (58)

According to the above computation for the diagonal canonical form, a theorem
on the the determinant of the controllability Grammian matrix and the volume
of the controllability ellipsoid for the general systems $\Sigma(A,B)$ is can
be established as follows.

###### Theorem 2

For the LDT systems $\Sigma(A,B)$ with $n$ different eigenvalues
$\lambda_{i}\in(-1,1),i=\overline{1,n}$, the determinant of the
controllability Grammian matrix and the volume the controllability ellipsoid
for the systems can be computed analytically as follows

$\displaystyle\det\left(G_{\infty}\right)$
$\displaystyle=F_{N}^{\lambda_{1},\lambda_{2},\dots,\lambda_{n}}\left(\det(P)\prod_{i=1}^{n}q_{i}B\right)^{2}$
(59) $\displaystyle\textnormal{vol}\left(E_{\infty}\right)$
$\displaystyle=H_{n}\left|\det(P)\prod_{1\leq i<j\leq
n}\frac{\lambda_{j}-\lambda_{i}}{1-\lambda_{i}\lambda_{j}}\right|\times\left|\prod_{i=1}^{n}\frac{q_{i}B}{\left(1-\lambda_{i}^{2}\right)^{1/2}}\right|$
(60)

where $q_{i}$ is the $i$-th unit left eigenvector of the matrix $A$, and the
matrix $P$ is the diagonalization transformation matrix constructed by all
unit right eigenvectors of matrix $A$.

In papers [11], [4], [9], and [5], the determinant value
$\det\left(G_{N}\right)$ of the controllability Grammian matrix $G_{N}$ and
the volume $\textnormal{vol}\left(E_{N}\right)$ the controllability ellipsoid
$E_{N}$ are chosen as the objective functions for optimizing the control
ability. Because lack of the analytical computing methods for
$\det\left(G_{N}\right)$ and $\textnormal{vol}\left(E_{N}\right)$, these
optimizing problems for the control ability are solved very difficulty, and
few achievements about that have been made. Based on the above analytical
computing of $\det\left(G_{\infty}\right)$ and
$\textnormal{vol}\left(E_{\infty}\right)$, these optimizing problems for
promoting the control ability can be solved conviently and the controlled
plants with the better control abilty and dynamical performance can be
designed.

##  3 Decoding the Controllability Ellipsoid

According to the computing equation (60), two factors are deconstructed as
follows.

$\displaystyle F_{1}$ $\displaystyle=\left|\prod_{1\leq i<j\leq
n}\frac{\lambda_{j}-\lambda_{i}}{1-\lambda_{i}\lambda_{j}}\right|$ (61)
$\displaystyle F_{2,i}$
$\displaystyle=\frac{\left|q_{i}B\right|}{\left(1-\lambda_{i}^{2}\right)^{1/2}}$
(62)

In fact, the above two factors can be used to describe the shape and size of
the controllability ellipsoid $E_{N}$ and the eigenvalue evenness of the LDT
system.

###  3.1 The ellipsoid shape factor

The controllability ellipsoid $E_{N}$ in the original space and the invariant
eigen-space can be represented respectively as the following equation

$\displaystyle x^{T}\left(G_{N}\right)^{-1/2}x\leq 1$ (63) $\displaystyle
x^{T}\left(\overline{G}_{N}\right)^{-1/2}x\leq 1$ (64)

The $n$ radii of the ellipsoid $\overline{E}_{N}$ in the invariant eigen-space
are indeed the $n$ eigenvalues of the Garmmian matrix $\overline{G}_{N}$, and
then the shape of the ellipsoid $\overline{E}_{N}$ can be characterized by the
sizes of all $n$ radii of the ellipsoid. So is the ellipsoid $G_{N}$.

By Eq. (61), we can see, when some two eigenvalues of the system matrix $A$
are approximately equal, the minimum radius of the ellipsoid
$\overline{E}_{N}$ will be approximately zero, and the ellipsoid
$\overline{E}_{N}$ will be flattened. Therefore, if the distributions of all
eigenvalues of the matrix $A$ are even, the ratio between the minimum and
maximum radii can be avoided as a small value and then the ellipsoid
$\overline{E}_{N}$ will be avoided flattened.

The factor $F_{1}$ deconstructed from the volume computing equation (60) can
be used to describe the evenness of the eigenvalue distribution of the
Grammian matrix $G_{N}$ and then the uniformity of the $n$ radii of the
ellipsoid $\overline{E}_{N}$. The bigger the value of the factor $F_{1}$, the
more evenness of the eigenvalue distribution of the matrix $G_{N}$ in $(-1,1)$
is, the smaller the ratio between the minimum and maximum radii of the
ellipsoid $\overline{E}_{N}$ is, and then the greater the volume of the
ellipsoid is.

To some extent, the minimum eigenvalue
$\lambda_{\textnormal{min}}\left(G_{N}\right)$ of the Grammian matrix $G_{N}$
and the minimum radius $r_{\textnormal{min}}\left(E_{N}\right)$ of the
ellipsoid $E_{N}$ can be used to quantify the control ability of the input
variables to the state space, and then be chosen as the objective functions
for optimizing the control ability of the dynamical systems in papers [11],
[4], [9], and [5]. Due to lack of the analytical computing methods for
$\lambda_{\textnormal{min}}\left(G_{N}\right)$ and
$r_{\textnormal{min}}\left(E_{N}\right)$, these optimizing problems for the
control ability are solved very difficulty. In fact, the minimum radius
$r_{\textnormal{min}}\left(E_{N}\right)$, that is, the minimum distance
between the original and the boundary of the ellipsoid, is proportional to the
above shape factor $F_{1}$. The bigger the factor $F_{1}$ is, and the bigger
the minimum radius $r_{\textnormal{min}}\left(E_{N}\right)$ is. Therefore,
optimizing the factor $F_{1}$ is equal to optimizing
$\lambda_{\textnormal{min}}\left(G_{N}\right)$ and
$r_{\textnormal{min}}\left(E_{N}\right)$, and then based on the above
analytical expression of the fact $F_{1}$, optimizing control ability of the
LDT systems can be carried out conveniently and effectively.

Fig. 1 shows the 2-dimensional ellipsoids $E_{30}$, i.e., the sampling number
$N=30$, generated by the 3 matrix pairs $(A,b)$ that the matrix $A$ is with
the different eigenvalues and matrix $b$ is a same vector, and Fig. 2 shows
the 2-dimensional ellipsoids generated by the diagonal matrix pairs of these 3
matrix pairs $(A,b)$, that is, the ellipsoids in Fig. 2 are in the invariant
eigen-space. These figures show us that the smaller the difference of two
eigenvalues of the systems matrix $A$ is, the more flat the controllability
ellipsoid is.

(a) (0.85,0.9,0.2128))

(b) (0.6,0.9,0.6522)

(c) (0.4,0.9,0.7813)

Figure 1: The 2-dimensional ellipsoid with $(\lambda_{1},\lambda_{2},F_{1})$

(a) (0.85,0.9,0.2128))

(b) (0.6,0.9,0.6522)

(c) (0.4,0.9,0.7813)

Figure 2: The 2-dimensional ellipsoid with $(\lambda_{1},\lambda_{2},F_{1})$
in the eigen-space

###  3.2 The shape factors in 2-dimensional section of the ellipsoid

In fact, the shape of the ellipsoid can be observed by the shape of the each
2-dimensional section of the ellipsoid in the eigen-space. For example, for
any two eigenvalues $\lambda_{i}$ and $\lambda_{j}$, the shape factor of the
2-dimensional section $x_{i}-x_{j}$ of the ellipsoid in the eigen-space can be
deconstructed from the shape factor $F_{1}$ as follows

$\displaystyle
F_{1,i,j}=\left|\frac{\lambda_{j}-\lambda_{i}}{1-\lambda_{i}\lambda_{j}}\right|$
(65)

Therefore, all factor $F_{1,i,j}$ can describe the shape of the each section
of the ellipsoid and then can construct the shape factor $F_{1}$ of the
ellipsoid.

###  3.3 The eigenvalue evenness factor of the LDT system

Beyond for describing the shape of the ellipsoid, the factor $F_{1}$ can be
used to describe the evenness of the eigenvalue distribution of the LDT system
$\Sigma(A,B)$. The bigger the value of the factor $F_{1}$ is, the more even
the distribution of the $n$ eigenvalues of the matrix $A$ is, and then the
bigger the controllable region of the system is, and the stronger the control
ability of the systems is.

As we know, many computing and designing methods for control laws are based on
the pole assignment method with a set of given expecting closed-loop poles.
How to determine the expecting closed-loop poles to obtain the greater control
ability and dynamical performance for the closed-loop systems? There has been
no good answer to this question. By the above analysis, we can see, optimizing
the evenness factor $F_{1}$ of the given expecting closed-loop poles, we can
get a clsode-loop system with the greater control ability and dynamical
performance by the pole assignment control method.

###  3.4 The circumscribed hypercube and circumscribed rhomboid

The factor $F_{2,i}$ is indeed the biggest distance of the boundary of the
ellipsoid $\overline{E}_{N}$ in the $i$-dimensional space. In fact, the $n$
side lengths of the circumscribed hypercube of the ellipsoid
$\overline{E}_{N}$, shown in Fig. 2, are $2F_{2,i},i=\overline{1,n}$, and then
the volume of circumscribed hypercube is the production
$2^{n}\prod_{i=1}^{n}F_{2,i}$ among the all factor $F_{2,i}$. By the volume
equation (60), the volume of the ellipsoid can be represented as the volume of
the circumscribed hypercube, the shape factor $F_{1}$, and some constant
coefficient.

Therefore, we have the following discussions:

(1) When the circumscribed hypercubes of two controllability ellipsoids are
approximated, the bigger the shape factor $F_{1}$ is , the bigger the volume
of the ellipsoid is. Furthermore, the almost all 2-dimensional shape factors
$F_{1,i,j}$ for some ellipsoid are bigger than the another, the whole
ellipsoid can be said to be bigger than the another.

(2) When the shape factors $F_{1}$ of two controllability ellipsoids are
approximated, the bigger the circumscribed hypercubes is, the bigger the
volume of the ellipsoid is. Furthermore, the almost all 2-dimensional shape
factors $F_{1,i,j}$ for the two ellipsoids are approximated, the whole
ellipsoid with the bigger circumscribed hypercubes can be said to be bigger
than the another.

##  4 Analytic Volume-Computation for the systems with the complex eigenvalues

Theorem 2 for the LDT systems with the real eigenvalues can be generalized to
the LDT systems with the complex eigenvalues, and the corresponding the
theorem can be stated as follows.

###### Theorem 3

When all $n$ different complex eigenvalues
$\lambda_{i}\left(i=\overline{1,n}\right)$ of the LDT systems $\Sigma(A,B)$
satisfy that $|\lambda_{i}|\in[0,1)$, the determinant of the controllability
Grammian matrix and the volume the controllability ellipsoid for the systems
can be computed analytically as follows

$\displaystyle\det\left(G_{\infty}\right)$
$\displaystyle=\left[\det(P)\prod_{1\leq i<j\leq
n}\frac{\lambda_{j}-\lambda_{i}}{1-\lambda_{i}\lambda_{j}}\right]^{2}\left[\prod_{i=1}^{n}\frac{\left(q_{i}B\right)^{2}}{1-\left|\lambda_{i}\right|^{2}}\right]$
(66) $\displaystyle\textnormal{vol}\left(E_{\infty}\right)$
$\displaystyle=H_{n}\left|\det(P)\prod_{1\leq i<j\leq
n}\frac{\lambda_{j}-\lambda_{i}}{1-\lambda_{i}\lambda_{j}}\right|\times\left|\prod_{i=1}^{n}\frac{q_{i}B}{\left(1-\left|\lambda_{i}\right|^{2}\right)^{1/2}}\right|$
(67)

where the complex vector $q_{i}$ is the $i$-th unit left eigenvector of the
matrix $A$, and the complex matrix $P$ is the diagonalization transformation
matrix constructed by all unit right eigenvector of the matrix $A$.

Similar to Section 3, based on these analytical expression, the shape factors
of the controllability ellipsoid and the evenness factor of the eigenvalue
distribution for LDT systems with complex eigenvalues can be got.

According to the computing equation (67), some factors described the shape and
size of the controllability ellipsoid are deconstructed as follows.

$\displaystyle F_{1}$ $\displaystyle=\left|\prod_{1\leq i<j\leq
n}\frac{\lambda_{j}-\lambda_{i}}{1-\lambda_{i}\lambda_{j}}\right|$ (68)
$\displaystyle F_{2,i}$
$\displaystyle=\frac{\left|q_{i}B\right|}{\left(1-\left|\lambda_{i}\right|^{2}\right)^{1/2}}$
(69)

Similar to the factors for the matrix $A$ with the real eigenvalues in Eqs.
(61) and (62), the above factors can be describe the shape and size of the
controllability ellipsoid $E_{N}$ and the eigenvalue evenness factor of the
LDT systems.

For the conjugate complex eigenvalue pair
$\left(\lambda_{i},\lambda_{i+1}\right)=\left(\lambda_{i},\lambda_{i}^{*}\right)$,
the shape factor of the 2-dimensional section of the ellipsoid in the eigen-
space is

$\displaystyle
F_{1,i,i+1}=\left|\frac{\lambda_{i}^{*}-\lambda_{i}}{1-\lambda_{i}\lambda_{i}^{*}}\right|=\frac{2\textnormal{Im}\lambda_{i}}{1-\left|\lambda_{i}\right|^{2}}$
(70)

Fig. 3 shows the 2-dimensional ellipsoids $E_{N}(30)$ generated by the
following matrix pairs $(A,b)$ with the complex eigenvalues

$\displaystyle A=\left[\begin{array}[]{cc}0.8&-a\\\
a&0.8\end{array}\right],\;\;b=\left[\begin{array}[]{c}1\\\
1\end{array}\right]$ (75)

where $a=0.1,0.2,0.3$, the corresponding the eirenvalues are $0.8\pm
0.1i,0.8\pm 0.2i,0.8\pm 0.3i$, and the factors $F_{1}=1.032,2.282,4.121$. By
Fig. 3, we can see, the bigger the image part of the conjugate complex
eigenvalue pair is, the greater the volume of the ellipsoid.

Figure 3: The 2-dimensional ellipsoid with the complex eigenvalues

##  5 Numerical Experiments

###### Example 1

Computing the volume, shape factor, and the side lengths of the circumscribe
hypercube of the controllability ellipsoid generated by the following matrix
pair

$\displaystyle(A,b)=\left(\left[\begin{array}[]{ccc}0&1&0\\\ 0&0&1\\\
0.432&-1.74&2.3\end{array}\right],\left[\begin{array}[]{c}0\\\ 0\\\
1\end{array}\right]\right)$ (82)

By the diagonal matrix transformation, the diagonal matrix pair is as follows

$\displaystyle\left(\hat{A},\hat{b}\right)=\left(\textnormal{diag}\\{0.6,0.8,0.9\\},[2.034,7.158,5.235]^{T}\right)$
(83)

and then, the analytical computing results about the volume and these factors
are as Table 1

Table 1: Computing results of the volume and shape factors for the systems $\Sigma(A,B)$ factors | values
---|---
volume: | 298.8566
shape factor $F_{1}$: | 0.0896
2-D shape factors $F_{1,1,2},F_{1,1,3},F_{1,2,3}$: | 0.3846, 0.6522, 0.3571
the side length $F_{2,1},F_{2,2},F_{2,3}$: | 2.5425, 11.9300, 12.0099

Fig. 4 shows the 3-dimensional ellipsoids $E_{N}(60)$ generated by the above
matrix pairs $\left(\hat{A},\hat{b}\right)$ in the eigen-space, from three
visual angle, and these 3 figures show us the 3 sections of the ellipsoid.

Figure 4: The 3-dimensional ellipsoid in the eifen-sapce

##  6 Conclusions

In this article, we present three theorems and develop an effective analytical
method to compute the volume of the controllability ellipsoid for the LDT
systems with $n$ different eigenvalues. Furthermore, by deconstructing the
analytical expression of the volume, some factors on the shape of the
ellipsoid, the side length of its circumscribed rhomboid, the evenness of the
eigenvalue distribution of the LDT system are constructed. Based on the
analytical expression of the volume and these factors, the control ability can
be defined, computing, analyzed, and optimized.

## References

  * Canfield and Nkhumise [2017] S.L. Canfield, R. Nkhumise, Controllability ellipse to evaluate performance of mobile manipulators for manufacturing tasks, Journal of Mechanisms and Robotics 9 (2017).
  * Chen [1998] C.T. Chen, Linear system theory and design, Oxford University Press, Inc. New York, NY, USA, 3rd edition, 1998.
  * Dullerud and Paganini [2000] G.E. Dullerud, F. Paganini, A Course in Robust Control Theory: A Convex Approach, Sringer, 2000.
  * Georges [1995] D. Georges, The use of observability and controllability gramians or functions for optimal sensor and actuator location in finite-dimensional systems, in: Proc. of IEEE Conf. on Decision and Control, New Orleans, LA, USA, p. 3319–3324.
  * Ilkturk [2015] U. Ilkturk, Observability Methods in Sensor Scheduling, Ph.D. thesis, ARIZONA STATE UNIVERSITY, 2015.
  * Kailath [1980] T. Kailath, Linear systems, Prentice-Hall, Englewood Cliffs, NJ, 1980\.
  * Kurzhanskiy and Varaiya [2007] A. Kurzhanskiy, P. Varaiya, Ellipsoidal techniques for reachability analysis of discrete-time linear systems, IEEE Trans. on Automatic Control 52 (2007) 26–38.
  * Nkhumise [2016] R.M. Nkhumise, Controllability Ellipse – a Method to Eavluate Performance of Mobile Manipulators Applied to Welding, Master’s thesis, Tennessee Technological University, 2016.
  * Pasqualetti et al. [2014] F. Pasqualetti, S. Zampieri, F. Bullo, Controllability metrics, limitations and algorithms for complex networks, IEEE Trans. on Control of Network Systems 1 (2014) 40–52.
  * Polyak et al. [2008] B. Polyak, S. Nazin, M. Khlebnikov, The invariant ellipsoid technique for analysis and design of linear control systems, in: Advances in Mechanics: Dynamics and Control: Proceedings of the 14th International Workshop on Dynamics and Control, ed. F.L. Chernousko, G.V. Kostin, V.V. Saurin, Moscow: Nauka,, pp. 239–246.
  * VanderVelde and Carignan [1982] W. VanderVelde, C. Carignan, A dynamic measure of controllability and observability for the placement of actuators and sensors on large space structures, Technical Report, NASA-CR-168520, SSL-2-82, 1982\.