# An Optimal Transport Approach to
the Computation of the LM Rate ††thanks: The first two authors contributed
equally to this work. ††thanks: ${\dagger}$ Corresponding authors.

Wenhao Ye  Department of Mathematical Sciences, Tsinghua University, Beijing
100084, China  Huihui Wu  Theory Lab, Central Research Institute, 2012 Labs,
Huawei Tech. Co. Ltd., Hong Kong SAR, China  Shitong Wu  Department of
Mathematical Sciences, Tsinghua University, Beijing 100084, China  Yizhu Wang
Theory Lab, Central Research Institute, 2012 Labs, Huawei Tech. Co. Ltd., Hong
Kong SAR, China  Wenyi Zhang  Hao Wu  Bo Bai  Theory Lab, Central Research
Institute, 2012 Labs, Huawei Tech. Co. Ltd., Hong Kong SAR, China

###### Abstract

Mismatch capacity characterizes the highest information rate for a channel
under a prescribed decoding metric, and is thus a highly relevant fundamental
performance metric when dealing with many practically important communication
scenarios. Compared with the frequently used generalized mutual information
(GMI), the LM rate has been known as a tighter lower bound of the mismatch
capacity. The computation of the LM rate,111To our best knowledge, the name LM
rate first appeared in the reference [1]. The capital letter LM seems to be
the abbreviation of Lower bound on the Mismatch capacity. however, has been a
difficult task, due to the fact that the LM rate involves a maximization over
a function of the channel input, which becomes challenging as the input
alphabet size grows, and direct numerical methods (e.g., interior point
methods) suffer from intensive memory and computational resource requirements.
Noting that the computation of the LM rate can also be formulated as an
entropy-based optimization problem with constraints, in this work, we
transform the task into an optimal transport (OT) problem with an extra
constraint. This allows us to efficiently and accurately accomplish our task
by using the well-known Sinkhorn algorithm. Indeed, only a few iterations are
required for convergence, due to the fact that the formulated problem does not
contain additional regularization terms. Moreover, we convert the extra
constraint into a root-finding procedure for a one-dimensional monotonic
function. Numerical experiments demonstrate the feasibility and efficiency of
our OT approach to the computation of the LM rate.

###### Index Terms:

Entropy optimization, LM rate, mismatch capacity, optimal transport, Sinkhorn
algorithm.

††publicationid: pubid:  978-1-6654-3540-6/22 © 2022 IEEE

##  I Introduction

The Shannon capacity of a channel characterizes the ultimate transmission
efficiency limit of reliable communication over a channel [2]. It has played a
fundamental role in the research of communication theory and directed the
development of communication systems for decades.

In many scenarios of practical interest, however, the perfect knowledge about
a channel may not be available or may not be fully utilized for implementing
the transceivers. Important examples include channels with uncertainty (like
fading in wireless communication systems) [3], with non-ideal transceiver
hardware [4], or with constrained receiver structure [5]. A commonly adopted
practice of the receiver under such circumstances is to use a prescribed
decoding metric, which may not be matched to the actual channel transition
probability, and the mismatch capacity has been introduced to characterize the
highest information rate under a prescribed decoding metric; see, e.g., [6]
[7] and references therein.

Unfortunately, the mismatch capacity is still an open problem to date [8]. So
instead of it, researchers have been focusing on deriving its achievable lower
bounds. The generalized mutual information (GMI) is a relatively simple lower
bound [9], which has found extensive applications in various setups; see,
e.g., [3] [4] [10]. However, the LM rate [1] is a tighter lower bound, by
replacing the independent and identically distributed (i.i.d.) codebook
ensemble for the GMI by constant-composition codebook ensemble.222The LM rate
is still not the tightest lower bound of the mismatch capacity. There are
several ways of improving the GMI and the LM rate by considering more
structured codebook ensembles [7]. These are beyond the scope of this paper.

From the perspective of optimization, the primal forms of the GMI and the LM
rate are highly similar, except that for the LM rate there is an additional
constraint on the marginal distribution of the sought-for maximizing joint
probability distribution over the input and output alphabets; see, e.g., [11,
Thm. 1]. Consequently, the dual form of the GMI is easy to compute, since it
can be written as a maximization over a real number [11, Eqn. (12)], which is
readily solved by a one-dimensional line search. On the other hand, the dual
form of the LM rate further involves a maximization over a function of the
channel input [11, Eqn. (11)]. Consequently the computation of the LM rate is
much more challenging, and there is rare work on the numerical computation of
the LM rate. Interior point methods (e.g., [12, 13]) can be applied for
computing the LM rate, but it is typically memory intensive and
computationally expensive. It is therefore desirable to develop effective
computation models and efficient numerical algorithms for the LM rate.

In this paper, we formulate the LM rate computation as an optimal transport
(OT) problem with an extra constraint, motivated by the similarity between
these two optimization problems. Our contribution consists of three parts.
First, we propose an OT model with an extra constraint for the LM rate.
Second, we show that this model can be solved directly using the well-known
Sinkhorn algorithm [14]. Since our OT model is strongly convex, no additional
regularization is required. This guarantees that we only need several hundred
of Sinkhorn iterations to converge rather than tens of thousands of iterations
for classical OT problems. Last, we show that the extra constraint in the OT
problem formulation can be efficiently handled by finding the root of a one-
dimensional monotone function, and the feasibility of the extra constraint is
guaranteed at each iteration. Numerical experiments show that for the case of
QPSK and 16-QAM, our proposed algorithm is efficient and accurate. We also
point out that our method is highly scalable and can be easily generalized to
large-scale cases, such as 256-QAM.

The remaining part of this paper is organized as follows. In Section II, after
briefly reviewing the basic definition of the LM rate, we write it in the form
of OT model with an extra constraint. Next, we present the numerical methods
for this problem, including the Sinkhorn algorithm and the treatment of the
extra constraint in Section III. In Section IV, the simulation results
demonstrate the advantages of our approach. We finally conclude the paper in
Section V.

##  II Problem Formulation

###  II-A The LM Rate

We consider a discrete memoryless communication channel model with transition
law $W(y|x)$ over the (finite, discrete) channel input alphabet
$\mathcal{X}=\\{x_{1},\cdots,x_{M}\\}\subset\mathbb{R}^{2}$ and the channel
output alphabet $\mathcal{Y}\subset\mathbb{R}^{2}$. Thus, given a probability
measure $P_{X}$ on $\mathcal{X}$, we are able to define the joint probability
distribution $P_{XY}$ on $\mathcal{X}\times\mathcal{Y}$ and the output
distribution $P_{Y}$ on $\mathcal{Y}$ by the following:

$\displaystyle P_{XY}(x_{i},B)=W(B|x_{i})P_{X}(x_{i}),~{}\forall
B\subset\mathcal{Y},$ $\displaystyle
P_{Y}(B)=\sum_{i=1}^{M}W(B|x_{i})P_{X}(x_{i}),~{}\forall B\subset\mathcal{Y}.$

This discrete memoryless channel is in fact a mapping from the input alphabet
$\mathcal{X}$ to the output alphabet $\mathcal{Y}$ with the channel transition
law $W(y|x)$.

For transmission of rate $R$, a block length-$n$ codebook $\mathcal{C}$
consists of $2^{nR}$ vectors
$\mathbf{x}(m)=(x^{(1)}(m),\cdots,x^{(n)}(m))\in\mathcal{X}^{n}$. The encoder
maps the message $m$ uniformly randomly selected from the set
$\mathcal{M}=\\{1,\cdots,2^{nR}\\}$ to the corresponding codeword
$\mathbf{x}(m)$. After receiving the output sequence
$\mathbf{y}=(y^{(1)},\cdots,y^{(n)})$, the decoder forms the estimation on the
message $m$ following the decoding rule

$\hat{m}=\operatorname*{\arg\min}_{j\in\mathcal{M}}\sum_{k=1}^{n}d(x^{(k)}(j),y^{(k)}),$

where $d:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ is a non-negative function
called the decoding metric.

With the notations defined above, the LM rate, as one of the achievable lower
bound of the mismatch capacity, is defined as:

$\displaystyle I_{LM}(P_{X})$
$\displaystyle:=\min_{{\color[rgb]{0,0,0}\gamma\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})}}D(\gamma\|P_{X}P_{Y})$
(1a)
$\displaystyle\textrm{s.t.}\quad\int_{y\in\mathcal{Y}}\gamma(x_{i},y)\mathrm{d}y$
$\displaystyle=P_{X}(x_{i}),\ \forall x_{i}\in\mathcal{X},$ (1b)
$\displaystyle\sum_{x_{i}\in\mathcal{X}}\gamma(x_{i},y)$
$\displaystyle=P_{Y}(y),\ \forall y\in\mathcal{Y},$ (1c)
$\displaystyle\int_{y\in\mathcal{Y}}\sum_{x_{i}\in\mathcal{X}}\gamma
d(x_{i},y)\mathrm{d}y$
$\displaystyle\leq\int_{y\in\mathcal{Y}}\sum_{x_{i}\in\mathcal{X}}P_{XY}d(x_{i},y)\mathrm{d}y.$
(1d)

Here $D(\cdot\|\cdot)$ denotes the relative entropy function and
$\mathcal{P}(\mathcal{X}\times\mathcal{Y})$ denotes the set of all joint
probability distributions on $\mathcal{X}\times\mathcal{Y}$.

###  II-B The OT Problem

In (1), we can see that the LM rate is similar to the OT problem [15] in terms
of optimization objective and constraints. Naturally, we would like to derive
an equivalent OT-type problem to (1), which creates a prerequisite for
computing the LM rate by using the Sinkhorn algorithm [14].

Consider a discrete probability distribution $\mu_{i}=P_{X}(x_{i})$ on
$\mathcal{X}$. It satisfies the following normalization and average power
constraints:

$\sum_{i=1}^{M}\mu_{i}=1,\quad\sum_{i=1}^{M}\mu_{i}\|x_{i}\|_{2}^{2}=1.$ (2)

For given channel transition law $W(y|x)$ and decoding metric $d(x,y)$, the
right-hand side of (1d) is a constant:

$\displaystyle T$
$\displaystyle=\int_{\mathcal{Y}}\sum_{i=1}^{M}P_{XY}(x_{i},y)d(x_{i},y)\mathrm{d}y$
(3)
$\displaystyle=\int_{\mathcal{Y}}\sum_{i=1}^{M}\mu_{i}W(y|x_{i})d(x_{i},y)\mathrm{d}y.$

Moreover, it is easy to show that

$\displaystyle
D(\gamma\|P_{X}P_{Y})=\int_{\mathcal{Y}}\sum_{i=1}^{M}\gamma(x_{i},y)\log\gamma(x_{i},y)\mathrm{d}y-C,$
$\displaystyle C=\sum_{i=1}^{M}P_{X}(x_{i})\log
P_{X}(x_{i})+\int_{\mathcal{Y}}P_{Y}(y)\log P_{Y}(y)\mathrm{d}y.$

By neglecting the constant $C$, minimizing the objective function
$D(\gamma\|P_{X}P_{Y})$ is equivalent to maximizing the entropy

$-\int_{\mathcal{Y}}\sum_{i=1}^{M}\gamma(x_{i},y)\log\gamma(x_{i},y)\mathrm{d}y.$

Thus, we have obtained the following optimal transport problem (4a)-(4c) with
an extra constraint (4d):

$\displaystyle\min_{{\color[rgb]{0,0,0}\gamma\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})}}$
$\displaystyle\int_{\mathcal{Y}}\sum_{i=1}^{M}\gamma(x_{i},y)\log\gamma(x_{i},y)\mathrm{d}y$
(4a) s.t.
$\displaystyle\int_{\mathcal{Y}}\gamma(x_{i},y)\mathrm{d}y=\mu_{i},\quad
i=1,\cdots,M,$ (4b)
$\displaystyle\sum_{i=1}^{M}\gamma(x_{i},y)=P_{Y}(y),\quad\forall
y\in\mathcal{Y},$ (4c)
$\displaystyle\int_{\mathcal{Y}}\sum_{i=1}^{M}\gamma(x_{i},y)d(x_{i},y)\mathrm{d}y\leq
T.$ (4d)

###### Remark 1

In the classical OT theory, the cost function is only related to distance and
should be independent of variables. Thus, (4a)-(4d) is not a standard OT form,
since the “cost function” $\log\gamma(x_{i},y)$ in (4a) is related to the
variables $\gamma(x_{i},y)$. However, the optimization objective function (4a)
is obtained by complicated and lengthy inequality scaling of the original
problem (2.29) in [7], which is in standard OT form. For detailed derivation,
the interested readers are referred to Chapter 2 in [16]. On the other hand,
from the numerical point of view, the optimization problem (4a)-(4d) can be
efficiently solved by the Sinkhorn algorithm, which is well-known for its high
efficiency in solving OT problems. In these senses, we might as well call
(4a)-(4d) an OT problem.

##  III THE Sinkhorn ALGORITHM

In this section, we turn to the Sinkhorn algorithm for the equivalent OT
problem to the LM rate. First, we need to discretize the integral in (4). We
might as well consider a set of uniform grid points $\\{y_{j}\\}_{j=1}^{N}$ in
$\mathcal{Y}$, and the corresponding rectangular discretization of the
integral. This leads to the discrete form of (4):

$\displaystyle\min_{{\color[rgb]{0,0,0}\gamma_{ij}}}\quad$
$\displaystyle\sum_{i=1}^{M}\sum_{j=1}^{N}\gamma_{ij}\log\gamma_{ij}$ (5a)
s.t. $\displaystyle\sum_{j=1}^{N}\gamma_{ij}=\mu_{i},\quad i=1,\cdots,M,$ (5b)
$\displaystyle\sum_{i=1}^{M}\gamma_{ij}=\nu_{j},\quad j=1,\cdots,N,$ (5c)
$\displaystyle\sum_{i=1}^{M}\sum_{j=1}^{N}d_{ij}\gamma_{ij}\leq T.$ (5d)

Here $\gamma_{ij}=\gamma(x_{i},y_{j}),\;\nu_{j}=P_{Y}(y_{j})$ and
$d_{ij}=d(x_{i},y_{j})$.

###### Remark 2

In this work, we illustrate our key idea through the rectangular formula with
only first-order accuracy for numerical integration. The idea can be easily
generalized to a higher-order numerical discretization, e.g., the trapezoid
formula. Not only that, the Sinkhorn algorithm, which we will discuss later in
this section, only requires minor modifications to be suitable for higher-
order discretization.

Introducing the dual variables
$\bm{\alpha}\in\mathbb{R}^{M},\bm{\beta}\in\mathbb{R}^{N}$ and
$\lambda\in\mathbb{R}^{+}$, the Lagrangian of (5) can be written as:

$\displaystyle\mathcal{L}(\gamma;\bm{\alpha},\bm{\beta},\lambda)=\sum_{i=1}^{M}\sum_{j=1}^{N}\gamma_{ij}\log\gamma_{ij}+\sum_{i=1}^{M}\alpha_{i}(\sum_{j=1}^{N}\gamma_{ij}-\mu_{i})$
(6)
$\displaystyle+\sum_{j=1}^{N}\beta_{j}(\sum_{i=1}^{M}\gamma_{ij}-\nu_{j})+\lambda(\sum_{i=1}^{M}\sum_{j=1}^{N}d_{ij}\gamma_{ij}-T).$

Taking the derivative of $\mathcal{L}(\gamma;\bm{\alpha},\bm{\beta},\lambda)$
with respect to $\gamma_{ij}$ leads to

$\gamma_{ij}=\phi_{i}\Lambda_{ij}\psi_{j},$

in which

$\phi_{i}=\mathrm{e}^{-\alpha_{i}-1/2},\;\psi_{j}=\mathrm{e}^{-\beta_{j}-1/2},\;\Lambda_{ij}=\mathrm{e}^{-\lambda
d_{ij}}.$

Substituting the above formula into (5b) and (5c) yields

$\displaystyle\phi_{i}\sum_{j=1}^{N}\Lambda_{ij}\psi_{j}=\mu_{i},\quad
i=1,\cdots,M,$
$\displaystyle\psi_{j}\sum_{i=1}^{M}\Lambda_{ij}\phi_{i}=\nu_{j},\quad
j=1,\cdots,N.$

Since $\Lambda_{ij}>0$, we can alternatively update $\phi_{i}$ and $\psi_{j}$
as follows:

$\displaystyle\phi_{i}^{(\ell+1)}=\mu_{i}/\sum_{j=1}^{N}\Lambda_{ij}^{(\ell)}\psi_{j}^{(\ell)},\quad
i=1,\cdots,M,$ (7a)
$\displaystyle\psi_{j}^{(\ell+1)}=\nu_{j}/\sum_{i=1}^{M}\Lambda_{ij}^{(\ell)}\phi_{i}^{(\ell+1)},\quad
j=1,\cdots,N.$ (7b)

This iterative formula is the well-known Sinkhorn algorithm [17]. Different
from the classical OT problem, we need to deal with the extra constraint (5d).
By taking the derivative of
$\mathcal{L}(\gamma;\bm{\alpha},\bm{\beta},\lambda)$ with respect to
$\lambda$, we have

$G(\lambda)\triangleq\sum_{i=1}^{M}\sum_{j=1}^{N}\phi_{i}\psi_{j}d_{ij}\mathrm{e}^{-\lambda
d_{ij}}-T=0.$ (8)

Thus, we can update $\lambda$ by finding the roots of

$G(\lambda^{(\ell+1)})\triangleq\sum_{i=1}^{M}\sum_{j=1}^{N}\phi_{i}^{(\ell+1)}\psi_{j}^{(\ell+1)}d_{ij}\mathrm{e}^{-\lambda^{(\ell+1)}d_{ij}}-T.$

Noticing that

$G^{\prime}(\lambda)=-\sum_{i=1}^{M}\sum_{j=1}^{N}\phi_{i}\psi_{j}d_{ij}^{2}\mathrm{e}^{-\lambda
d_{ij}}<0,$

the function $G(\lambda)$ is monotonic. Thus, The problem of finding the root
of $G(\lambda)$ can be easily solved by the Newton’s method. The pseudo-code
of the proposed algorithm is present in Algorithm 1.

Algorithm 1 The Sinkhorn Algorithm

0: Decoding metric $d_{ij}$; Marginal distributions $\mu_{i},\nu_{j}$;
Iteration number $K$.

0: Minimal value of $\sum_{i=1}^{M}\sum_{j=1}^{N}\gamma_{ij}\log\gamma_{ij}$.

1: Initialization:
$\bm{\phi}=\mathbf{1}_{M},\bm{\psi}=\mathbf{1}_{N},\lambda=1$;

2: for $\ell=1:K$ do

3: $\Lambda_{ij}\leftarrow\mathrm{e}^{-\lambda d_{ij}}$, $i=1,\cdots,M,\
j=1,\cdots,N$

4: for $i=1:M$ do

5: $\phi_{i}\leftarrow\mu_{i}/\sum_{j=1}^{N}\Lambda_{ij}\psi_{j}$

6: for $j=1:N$ do

7: $\psi_{j}\leftarrow\nu_{j}/\sum_{i=1}^{M}\Lambda_{ij}\phi_{i}$

8: Solve $G(\lambda)=0$ for $\lambda$ with Newton’s method

9: return
$\sum_{i=1}^{M}\sum_{j=1}^{N}\phi_{i}\psi_{j}\Lambda_{ij}\log\left(\phi_{i}\psi_{j}\Lambda_{ij}\right)$

Finally, we need to discuss the feasibility of the Sinkhorn iteration,
especially under the extra constraint (5d). Depending on the value of $G(0)$,
there are two cases:

  * •

$G(0)>0$: In this case, $G(\lambda)=0$ has a unique solution on $(0,+\infty)$
since $G^{\prime}(\lambda)<0$. Thus the extra constraint (5d) is obviously
satisfied.

  * •

$G(0)\leq 0$: In this case, the extra constraint (5d) is already satisfied. We
only need to set $\lambda=0$ instead of solving $G(\lambda)=0$ at line 8 of
Algorithm 1.

##  IV NUMERICAL SIMULATIONS

In this section, we use the model and algorithm developed in previous sections
to compute the LM rate for different modulation schemes over the additive
white Gaussian noise (AWGN) channels subject to rotation and scaling with the
following transition law

$Y=HX+Z,\ \text{with }Z\sim\mathcal{N}(0,\sigma_{Z}^{2}).$ (9)

The matrix $H\in\mathbb{R}^{2\times 2}$ is a combination of rotation and
scaling transformations as

$H=\begin{pmatrix}\eta_{1}&0\\\
0&\eta_{2}\end{pmatrix}\begin{pmatrix}\cos\theta&\sin\theta\\\
-\sin\theta&\cos\theta\end{pmatrix}.$

Here the parameters $\eta_{1},\;\eta_{2}$ indicate the scaling of the signal,
and the parameter $\theta$ indicates the degree of rotation on the signal. In
this work, we consider the case of $\eta_{1}=1$ and $\eta_{2}=\eta$. Note
that, the specific values of $\eta$ and $\theta$ can not be priorly known.

The decoding metric is $d(x,y):=\|y-\hat{H}x\|_{2}^{2}$, where $\hat{H}$ is an
approximation that is based on part of the information we know about $H$. We
consider the scenario in which the decoder is unaware of the mismatch effect.
Thus, in the decoding rule, we have $\hat{H}=I$.

In the following simulations, we consider two classical modulation schemes:
QPSK and 16-QAM. Under the power constraint (2), their constellation points
(also known as the alphabet) are illustrated in Fig 1. For both cases, all the
constellation points in $\mathcal{X}$ are restricted in the region
$[-1,1]\times[-1,1]$.

Figure 1: Constellation points under the power constraint. Left: The QPSK
modulation scheme. Right: The 16-QAM modulation scheme.

Meanwhile, according to the channel law (9), the channel output alphabet
$\mathcal{Y}$ is $\mathbb{R}^{2}$ itself. Under some reasonable assumptions,
e.g. $\eta\leq 1,\sigma_{z}^{2}\leq\frac{1}{2}$, we are able to truncate the
alphabet $\mathcal{Y}$ with a sufficiently large region, e.g.
$[-8,8]\times[-8,8]$. Correspondingly, we can discretize the region by a set
of uniform grid points $\\{y_{j}\\}_{j=1}^{N}$:

$\displaystyle y_{r\sqrt{N}+s}$ $\displaystyle=(-8+r\Delta y,-8+(s-1)\Delta
y),\Delta y=\frac{16}{\sqrt{N}-1},$ $\displaystyle r$
$\displaystyle=0,1,\cdots,\sqrt{N}-1,s=1,2,\cdots,\sqrt{N},$

In Algorithm 1, the termination condition of the Newton iteration is that the
update step size of $\lambda$ is less than $10^{-14}$. Moreover, the
$\text{SNR}\triangleq 1/(2\sigma_{Z}^{2})$ is used in the sequel.

All the experiments are conducted on a platform with 128G RAM, and one
Intel(R) Xeon(R) Gold 5117 CPU @2.00GHz with 14 cores.

###  IV-A Algorithm Verfication

We first study the convergence of our Sinkhorn algorithm by considering the
residual errors of (7) and (8):

$\displaystyle r_{\phi}$
$\displaystyle=\sum_{i=1}^{M}|\phi_{i}\sum_{j=1}^{N}\Lambda_{ij}\psi_{j}-\mu_{i}|,$
$\displaystyle r_{\psi}$
$\displaystyle=\sum_{j=1}^{N}|\psi_{j}\sum_{i=1}^{M}\Lambda_{ij}\phi_{i}-\nu_{j}|,$
$\displaystyle r_{\lambda}$ $\displaystyle=|G(\lambda)|.$

The parameters are set to

$(\eta,\theta)=(0.9,\pi/18),\;N=250,000,\;\text{SNR}=0\textrm{dB}.$ (10)

Figure 2: The convergent trajectories of the residual error for $r_{\phi}$ (Orange), $r_{\psi}$ (Blue) and $r_{\lambda}$ (Purple). Left: The QPSK modulation scheme. Right: The 16-QAM modulation scheme. TABLE I: Comparison between the Sinkhorn algorithm and CVX. Columns 3-5 are the averaged computational time and the speed-up ratio of the Sinkhorn algorithm. Column 6 is the averaged difference of the LM rate computed by two methods. |  $N$ |  Computational time (s) |  Speed-up ratio |  Average difference
---|---|---|---|---
Sinkhorn |  CVX
QPSK |  $100$ |  $0.37\times 10^{0}$ |  $2.61\times 10^{1}$ |  $7.05\times 10^{1}$ |  $1.99\times 10^{-7}$
$225$ |  $0.64\times 10^{0}$ |  $8.66\times 10^{1}$ |  $1.35\times 10^{2}$ |  $6.45\times 10^{-7}$
$400$ |  $1.28\times 10^{0}$ |  - |  - |  -
16-QAM |  $100$ |  $0.96\times 10^{0}$ |  $1.49\times 10^{2}$ |  $1.55\times 10^{2}$ |  $4.13\times 10^{-7}$
$225$ |  $1.96\times 10^{0}$ |  $9.27\times 10^{2}$ |  $4.73\times 10^{2}$ |  $1.37\times 10^{-6}$
$400$ |  $3.81\times 10^{0}$ |  - |  - |  -
256-QAM |  $100$ |  $1.49\times 10^{1}$ |  - |  - |  -
$1600$ |  $2.24\times 10^{2}$ |  - |  - |  -

In Fig. 2, we output the convergent trajectories of the residual errors with
respect to iteration steps. We can see that the three curves all decrease
rapidly and reach the machine accuracy near $250$ iterations. It is worth
mentioning that classical OT problems usually require tens of thousands of
Sinkhorn iterations to converge. This significantly illustrates the dramatic
efficiency advantage of our OT model and Sinkhorn algorithm.

To further illustrate the accuracy and efficiency of the Sinkhorn algorithm
for the OT problem (5). We use CVX [13] as the baseline. The averaged
computational time and the averaged difference of the optimal values between
the two methods are listed in Table I. To reduce the influence of noise, we
repeat each experiment for $100$ times. Except for $N$, other parameters are
the same as (10). Since it is difficult for CVX to handle large-scale
problems, we restrict $N$ to small scales, e.g. $100,\;225,\;400$ and $1600$.
From the table, we can see the optimal values obtained by the two methods are
almost the same. But our Sinkhorn algorithm has a significant advantage (one
or two orders of magnitude) in computational speed. Moreover, for slightly
larger scale problems, CVX has failed to output convergent results.

###  IV-B Results and Discussions

Below, we present the computational results of the LM rate under different
modulation schemes, different parameters $(\eta,\theta)$, and different SNRs.
For comparison, we also present the computational results of GMI [4] under the
same setup. As we know, GMI is generally lower than the LM rate [7]. These
results not only help us quantitatively understand the relationship between
the two rates, but also help verify the correctness of our model and
algorithm. In the numerical experiments, we consider four sets of parameters
$(\eta,\theta)$, namely,

$(0.9,\frac{\pi}{18}),\quad(0.9,\frac{\pi}{12}),\quad(0.8,\frac{\pi}{18}),\quad(0.8,\frac{\pi}{12}).$

We set $N=250,000$ to ensure the discretization accuracy. And we use $500$
iterations for each experiment to ensure the algorithm convergence. We also
repeat each experiment for $100$ times to reduce the influence of noise.

Figure 3: LM rate (solid) and GMI (dashed) versus SNR for the QPSK modulation
scheme under different mismatched cases, including
$(\eta,\theta)=(0.9,\pi/18)$ (Purple), $(\eta,\theta)=(0.8,\pi/18)$ (Blue),
$(\eta,\theta)=(0.9,\pi/12)$ (Red), and $(\eta,\theta)=(0.8,\pi/12)$ (Orange).

Figure 4: LM rate (solid) and GMI (dashed) versus SNR for the 16-QAM
modulation scheme under different mismatched cases, including
$(\eta,\theta)=(0.9,\pi/18)$ (Purple), $(\eta,\theta)=(0.8,\pi/18)$ (Blue),
$(\eta,\theta)=(0.9,\pi/12)$ (Red), and $(\eta,\theta)=(0.8,\pi/12)$ (Orange).

In Fig. 3, we can see the comparison of the LM rate and GMI verse SNR for the
QPSK modulation scheme. We observe that the LM rate is higher than GMI with
the same parameters. Especially when $\text{SNR}>8$dB, there is about $2\%$
gain in the LM rate. In addition, as $\eta$ decreases (from $0.9$ to $0.8$) or
$\theta$ increases (from $\pi/18$ to $\pi/12$), both LM rate and GMI decrease
accordingly. These results agree with intuition. In Fig. 4, we display the
comparison for the 16-QAM modulation scheme. From this, we can draw the same
conclusions as those for Fig. 3.

##  V CONCLUSION

In this paper, we studied the computation problem of the LM rate, which is a
lower bound for mismatch capacity. Our contributions are twofold. First, we
showed that the computation of the LM rate can be reformulated into the
Optimal Transport problem with an extra constraint. Second, we proposed a
Sinkhorn-type algorithm to solve the above problem. For the extra constraint,
we show that it is equivalent to seeking the root of a one-dimensional
monotonic function. Numerical experiments show that our approach to computing
the LM rate is efficient and accurate. Moreover, we can observe a noticeable
gain in the LM rate compared to GMI.

## References

  * [1] N. Merhav, G. Kaplan, A. Lapidoth, and S. Shamai (Shitz), “On Information Rates for Mismatched Decoders,” _IEEE Transactions on Information Theory_ , vol. 40, no. 6, pp. 1953–1967, Nov. 1994.
  * [2] C. Shannon, “A Mathematical Theory of Communication,” _The Bell System Technical Journal_ , vol. 27, no. 3, pp. 379–423,623–656, Jul.-Oct. 1948.
  * [3] A. Lapidoth and S. Shamai (Shitz), “Fading Channels: How Perfect Need ‘Perfect Side Information’ Be?” _IEEE Transactions on Information Theory_ , vol. 48, no. 5, pp. 1118–1134, May 2002.
  * [4] W. Zhang, “A General Framework for Transmission with Transceiver Distortion and Some Applications,” _IEEE Transactions on Communications_ , vol. 60, no. 2, pp. 384–399, Feb. 2012.
  * [5] J. Salz and E. Zehavi, “Decoding under Integer Metrics Constraints,” _IEEE Transactions on Communications_ , vol. 43, no. 2/3/4, pp. 307–317, Feb./Mar./Apr. 1995.
  * [6] A. Lapidoth and P. Narayan, “Reliable Communication under Channel Uncertainty,” _IEEE Transactions on Information Theory_ , vol. 44, no. 6, pp. 2148–2177, Oct. 1998.
  * [7] J. Scarlett, A. Guillèn i Fábregas, A. Somekh-Baruch, and A. Martinez, “Information-Theoretic Foundations of Mismatched Decoding,” _Foundations and Trends® in Communications and Information Theory_ , vol. 17, no. 2-3, pp. 149–400, 2020.
  * [8] I. Csiszar and P. Narayan, “Channel Capacity for a Given Decoding Metric,” _IEEE Transactions on Information Theory_ , vol. 41, no. 1, pp. 35–43, Jan. 1995.
  * [9] G. Kaplan and S. Shamai (Shitz), “Information Rates and Error Exponents of Compound Channels with Application to Antipodal Signaling in a Fading Environment,” _AEU-International Journal of Electronics and Communications_ , vol. 47, no. 4, pp. 228–239, Jul. 1993.
  * [10] A. Asyhari and A. Guillèn i Fábregas, “Nearest Neighbor Decoding in MIMO Block-Fading Channels with Imperfect CSIR,” _IEEE Transactions on Information Theory_ , vol. 58, no. 3, pp. 1483–1517, Mar. 2012.
  * [11] A. Ganti, A. Lapidoth, and I. E. Telatar, “Mismatched Decoding Revisited: General Alphabets, Channels with Memory, and the Wide-Band Limit,” _IEEE Transactions on Information Theory_ , vol. 46, no. 7, pp. 2315–2328, Nov. 2000.
  * [12] R. H. Tütüncü, K. C. Toh, and M. J. Todd, “Solving Semidefinite-Quadratic-Linear Programs Using SDPT3,” _Mathematical Programming, Series B_ , vol. 95, no. 2, pp. 189–217, 2003.
  * [13] M. Grant and S. Boyd, “CVX Users’ Guide for CVX Version 1.21,” Jan. 2011.
  * [14] M. Cuturi, “Sinkhorn Distances: Lightspeed Computation of Optimal Transport,” in _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 26, Lake Tahoe, Nevada, US, Dec. 2013, pp. 2292–2300.
  * [15] G. Peyré and M. Cuturi, “Computational Optimal Transport: With Applications to Data Science,” _Foundations and Trends® in Machine Learning_ , vol. 11, no. 5-6, pp. 355–607, Feb. 2019.
  * [16] I. Csiszár and J. Körner, _Information Theory: Coding Theorems for Discrete Memoryless Systems_. Cambridge, UK: Cambridge University Press, 2011.
  * [17] R. Sinkhorn, “Diagonal Equivalence to Matrices with Prescribed Row and Column Sums,” _The American Mathematical Monthly_ , vol. 74, no. 4, pp. 402–405, Apr. 1967.


# Note on the Existence of Minimizers for Variational Geometric Active
Contours

El Hadji S. Diop Department of Mathematics, University of Thies, Thies BP 967,
Senegal. Email<EMAIL_ADDRESS>Valérie Burdin Image and Information
Department, Institut Mines Telecom - Telecom Bretagne, Technopole Brest-Iroise
CS 83818, 29238 Brest Cedex 3, France. Email<EMAIL_ADDRESS>V. B. Surya Prasath Division of Biomedical Informatics, Cincinnati Children’s
Hospital Medical Center, Cincinnati, OH 45229 USA. Also with the Departments
of Biomedical Informatics, Pediatrics, Electrical Engineering and Computer
Science, University of Cincinnati, OH, USA. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We propose here a proof of existence of a minimizer of a segmentation
functional based on a priori information on target shapes, and formulated with
level sets. The existence of a minimizer is very important, because it
guarantees the convergence of any numerical methods (either gradient descents
techniques and variants, or PDE resolutions) used to solve the segmentation
model. This work can also be used in many other segmentation models to prove
the existence of a minimizer.

Keywords: Image Segmentation, Energy Minimization, Bounded Variation,
Variational Model, Level sets, Shape priors.

##  1 Introduction

Image segmentation is still subjects of intensive researches due to emerging
acquisition techniques and capacity of image processing and computer vision
models in modeling and solving real life problems. In many applications, e.g.
medical imaging, it is essential by just a first step towards the true
application (e.g. results analysis, therapeutic evaluation, $\dots$). Accuracy
is then very important, and due to that fact, we developed a segmentation
model [10] for $X$-$rays$ medical images that suffer from a poor contrast
between objects of interests (femur or tibia for instance) and other
structures (soft tissues, pelvis, hip, fibula, tarsus, metatarsus, $\dots$),
problems of edge salience, occlusions phenomena in bones joints, $\dots$.
Prior shapes were incorporated in a level set-based variational formulation of
the segmentation problem, and then, as common, associated Euler-Lagrange
equations were derived constituting our segmentation model. A proof of
existence of a minimizer of a segmentation energy is not always provided, the
segmentation model is solved numerically (gradient descent, partial
differential equation numerical resolutions, $\dots$), rather. The main reason
is the complexity of the designed segmentation functionals, and then, many
criteria (e.g. convexity) are not usually satisfied in order to apply
classical optimization results. Many techniques have been developed e.g.
convex relaxation techniques [21, 6], which are weak formulation of the
original problem. Although the existence of a minimizer was not proven, the
efficiency and robustness of the segmentation model [10] were showed on
various image types; namely, on synthetic images, digitally reconstructed
images, and real radiographic images. Also, quantitative evaluations of
obtained segmentation results were provided. Here, we propose a proof of
existence of a minimizer for the variational segmentation functional [10].
Different works [8, 5, 9, 16] and more recently [17, 24, 22, 19, 20] pursued
the same goal, even if the proposed segmentation functionals were different.

The article is organized as follows. The segmentation functional is presented
in Section 2. The proof of the existence of a minimizer is proposed in Section
3. We conclude with some perspectives in Section 4.

##  2 Variational Image Segmentation Model

Let $I:\Omega\rightarrow\mathds{R},I=\\{I(x),x\in\Omega\\}$ be a continuous
image, $\Omega\subset\mathds{R}^{2}$ its domain assumed to be open, bounded
and with a Lipschitz boundary denoted by $\partial\Omega$.

###  2.1 Prior Shapes Design

We consider a set $\\{C_{n}\\}_{1\leq n\leq N}$ of $N$ aligned contours
embedded as signed distance functions denoted by $\phi_{n}$, $\forall~{}n\geq
0$. Let $\\{\phi_{n}\\}_{1\leq n\leq N}$ be the training dataset, and denote
$\bar{\phi}=\displaystyle\frac{1}{N}\sum_{n=1}^{N}\phi_{n}$ its mean. In order
to learn the local deformations of the dataset, we follow [15] and perform a
$PCA$ on $\\{\phi_{n}\\}_{1\leq n\leq N}$. Advantages in doing that on
$(\phi_{n})_{n}$ instead of on $(C_{n})_{n}$ were already discussed [10]. So,
this means looking for the best orthonormal basis $\\{u_{k}\\}_{1\leq k\leq
K}$ s.t. the projection of $\phi_{n}$ on $(u_{k})_{k}$ has a minimal distance
in $L^{2}$ sense. Let $U$ be composed with $p$ first columns of $V$ holding
the orthogonal modes of variations, new shapes can be built then by:
$\phi=\bar{\phi}+U\lambda$, where $U=[u_{i}]_{1\leq i\leq p}$ is the
eigenvectors matrix and $\lambda=[\lambda_{i}]^{\text{t}}_{1\leq i\leq p}$ the
shape parameters vector.

###  2.2 Segmentation Functional and Variational Formulation

The segmentation functional is defined as follows [10]:

$F(\varphi,\lambda,V,I_{in},I_{out})=\dfrac{\alpha}{2}F_{1}(\varphi)+F_{2}(\varphi,\lambda,V)+\beta
F_{3}(\varphi)+\nu F_{4}(\lambda,V,I_{in},I_{out}),$ (1)

where $\alpha,\beta,\nu>0$ for counterbalancing different energy terms defined
as follows:

$\displaystyle
F_{1}(\varphi)=\int_{\Omega}\left(\lvert\nabla\varphi\rvert-1\right)^{2}\mathrm{d}x,$
(2) $\displaystyle F_{2}(\varphi,\lambda,V)=\int_{\Omega}[\xi
g+\dfrac{\gamma}{2}\phi^{2}(\lambda,h(x))]\delta(\varphi)\lvert\nabla\varphi\rvert\mathrm{d}x,$
(3) $\displaystyle
F_{3}(\varphi)=\int_{\Omega}g\,H(-\varphi)\mathrm{d}x,\text{ and }$ (4)
$\displaystyle F_{4}(\lambda,V,I_{in},I_{out})=\int_{\Omega}\lvert
I-I_{in}\rvert^{2}+\mu\lvert\nabla
I_{in}\rvert^{2}H(\phi(\lambda,h(x)))\,\mathrm{d}x$
$\displaystyle+\int_{\Omega}\lvert I-I_{out}\rvert^{2}+\mu\lvert\nabla
I_{out}\rvert^{2}(1-H(\phi(\lambda,h(x))))\,\mathrm{d}x+\zeta\int_{\Omega}d\mathcal{H}^{1}(C(\lambda,h(x)));$
(5)

with $\varphi$ being the level set function; $\xi$ and $\gamma$ are positive
parameters; $\delta(\cdotp)$ is the unidimensional Dirac distribution; $g$ is
a positive and strictly non increasing function, typically:
$g=\dfrac{1}{1+\eta\lvert\nabla G_{\sigma}\star I\rvert^{2}}$, $\star$
standing for the convolution operator, $\eta>0$, $G_{\sigma}$ is a Gaussian
kernel with a variance $\sigma$. $I_{in}$ and $I_{out}$ designate the Mumford-
Shah functional terms; $\nu$ is a positive parameter. $H(\cdotp)$ is the
Heaviside function, i.e. $H:\mathds{R}\longrightarrow\\{0,1\\}$, s.t. $H=1$ in
$\mathds{R}^{+}$, $H=0$ in $\mathds{R}_{\star}^{-}$, and $\delta=H^{\prime}$
in the sense of distributions. $\phi$ is the prior shape; $\lambda$ is the
shape parameters vector; $h:\Omega\longrightarrow\Omega$; $x\longmapsto
h(x)=\tau R_{\theta}x+T$ accounts the spatial rigid transformations achieved
through a vector $V$ holding the scale parameter factor $\tau$, the rotation
matrix $R_{\theta}$ of angle $\theta$ and the translation vector
$T=[T_{x},\,T_{y}]$; $C(\lambda,h(x))=\\{x\in\Omega$ s.t.
$\phi(\lambda,h(x))=0\\}$; $\mathcal{H}^{1}$ is the one dimensional Hausdorff
measure.

  * $\bullet$

$F_{1}$ (2) guarantees the signed distance function property, and avoids the
re-initialization process. In fact, when keeping $\lvert\nabla\varphi\rvert$
bounded, one ensures the correct computations of $\varphi$ derivatives. The
most common way is to apply the re-initialization procedure by periodically
solving the PDE [23, 25, 7]:

$\left\\{\begin{array}[]{c}\dfrac{\partial\varphi}{\partial
t}=\text{sign}(\varphi_{0})(1-\lvert\nabla\varphi\rvert)\\\
\varphi(x,0)=\varphi_{0}(x),\end{array}\right.$ (6)

where $\varphi_{0}$ refers to the level set to be re-initialized.

  * $\bullet$

$F_{2}$ (3) makes the active contour evolve towards high gradients areas, and
also towards similar regions of the prior shape. Minimizing $F_{2}$ increases
the similarity between the active contour and the shape prior.

  * $\bullet$

$F_{3}$ (4) could be interpreted as a weighted area term of the target object
of interests. Notice that if $g$ equal to $1$, then $F_{3}$ is the area of the
region of the object of interests; i.e. $\\{x\in\Omega,\text{ s.t.
}\varphi(x)<0\\}$. Minimizing it provides another force pushing the active
contour quickly towards the edges.

  * $\bullet$

$F_{4}$ (5) is a modified version of the complete Mumford-Shah functional
energy [18], which was the most suitable model for the bi-planar $X$-ray
images we dealt with, since anatomic regions of interests have almost
homogeneous gray level image intensities.

The level set formulation of the variational problem is thus given by:

$\displaystyle\varphi,\lambda,V,I_{in},I_{out}$
$\displaystyle=\operatorname*{arg\,min}_{\varphi,\lambda,V,I_{in},I_{out}}F(\varphi,\lambda,V,I_{in},I_{out})$
$\displaystyle=\operatorname*{arg\,min}_{\varphi,\lambda,V,I_{in},I_{out}}\dfrac{\alpha}{2}F_{1}(\varphi)+F_{2}(\varphi,\lambda,V)$
$\displaystyle+\beta F_{3}(\varphi)+\nu F_{4}(\lambda,V,I_{in},I_{out}).$ (7)

By the means of calculus of variations [11, 4], we solve the Euler-Lagrange
equations associated to the variational formulation (2.2) to finally obtain
the evolution equations that constituted the segmentation model [10].

##  3 Minimum Existence of the Segmentation Functional

Let us recall first definitions and most important properties related to the
space of Bounded Variation ($BV$) [12, 13, 2, 1]:

###### Definition 3.1

Let $u\in L^{1}(\Omega)$, and denote

$\int_{\Omega}|Du|=\sup\left\\{\int_{\Omega}u~{}\text{div}(\varphi)\mathrm{d}x;~{}\varphi=(\varphi_{1},\varphi_{2})\in
C_{0}^{1}(\Omega,\mathds{R}^{2})\text{ and }\lVert\varphi\rVert\leq
1\right\\},$

where $C_{0}^{1}(\Omega)$ is the space of continuously differential functions
with compact support in $\Omega$,
$\text{div}(\varphi)=\dfrac{\partial\varphi_{1}}{\partial
x_{1}}+\dfrac{\partial\varphi_{2}}{\partial x_{2}}$ where derivatives are
taken in a distributional sense, and
$\lVert\varphi\rVert=\lVert(\varphi_{1}^{2}+\varphi_{2}^{2})^{1/2}\rVert_{L^{\infty}(\Omega)}$.
The space of functions of bounded variation on $\Omega$, denoted BV($\Omega$),
is the set of functions defined by

$BV(\Omega)=\left\\{u\in L^{1}(\Omega);s.t.\int_{\Omega}|Du|<\infty\right\\}.$

###### Remark 3.1

BV($\Omega$) is a Banach space when endowed with the norm $\lVert
u\rVert_{\text{BV}(\Omega)}=\lVert u\rVert_{L^{1}(\Omega)}+\int_{\Omega}|Du|$.

######  Proposition 3.1 (Lower semi continuity)

Let $(u_{n})_{n}$ be a sequence of functions $\in\text{BV}(\Omega)$ s.t.
$u_{n}\underset{n}{\longrightarrow}u$ in $L^{1}_{loc}(\Omega)$. Then, one has:

$\int_{\Omega}|Du|\leq\underset{n}{\lim\inf}\int_{\Omega}|Du_{n}|.$

######  Proposition 3.2 (Approximations)

Let $u\in\text{BV}(\Omega)$. Then, there exists a sequence $(u_{n})_{n}$ of
functions belonging to $\text{BV}(\Omega)\cap C^{\infty}(\Omega)$ s.t. :

$u_{n}\underset{n}{\longrightarrow}u\text{ in }L^{1}(\Omega)\text{ and
}\int_{\Omega}|Du_{n}|\underset{n}{\longrightarrow}\int_{\Omega}|Du|.$

######  Proposition 3.3 (Compactness)

Let $(u_{n})_{n}$ be a uniformly bounded sequence of functions
$\in\text{BV}(\Omega)$. Then, there exists a subsequence $(u_{\rho(n)})_{n}$
of $(u_{n})_{n}$ and a function $u\in\text{BV}(\Omega)$ s.t.:
$u_{n}\underset{n}{\longrightarrow}u\text{ in }L^{1}_{\text{loc}}(\Omega)$.

Thanks to preceding results on BV spaces, we state and prove the main result
of the paper:

###### Theorem 3.1

There exists $(\varphi,\lambda,V,I_{in},I_{out})$ as a minimizer of the
segmentation functional $F$ (1).

###### Proof 3.1

The proof is based on the direct method of the calculus of variations [14],
compactness theorems and standard techniques of the calculus of variations on
BV spaces and its variants.
Let $\Omega=[0;~{}255]^{2}$,
$\lambda=(\lambda_{i})_{i=1}^{p}\in\Omega_{\lambda}=\underset{1\leq i\leq
p}{\prod}[-3x_{i};3x_{i}]$; $x_{i},i\in[[1;~{}p]]$, being the resulted
eigenvalues from the $PCA$,
$V=[\tau,~{}\theta,~{}T]\in\Omega_{V}=[0;~{}255]\times[-\pi;~{}\pi]\times[0;~{}255]^{2}$,
and let $J=I_{in}$ and $\bar{J}=I_{out}$.

Let now $(\varphi_{n})_{n},(\lambda_{n})_{n},(V_{n})_{n},(J_{n})_{n}$ and
$(\bar{J}_{n})_{n}$ be minimizing sequences of $F$ (1); i.e.

$\underset{n}{\lim}~{}F(\varphi_{n},\lambda_{n},V_{n},J_{n},\bar{J}_{n})=\inf
F.$ (8)

Step 1: Let us consider $G$ defined as

$G(\varphi)=\dfrac{\alpha}{2}\int_{\Omega}(|\nabla\varphi|-1)^{2}+\beta\int_{\Omega}gH(-\varphi)\text{
and }\Psi(\varphi)=(|\nabla\varphi|-1)^{2}.$ (9)

Then, $\forall~{}n\in\mathds{N}$, one has:

$G(\varphi_{n})=\dfrac{\alpha}{2}\int_{\Omega}\Psi(\varphi_{n})+gH(-\varphi_{n}).$
(10)

$\bullet$ $(\varphi_{n})_{n}$ is a family of level set functions; one can
assume then $\varphi_{n}$ belong to $C^{1}(\Omega)$, $\forall~{}n$. For all
$n$, let $\Psi_{n}=\Psi(\varphi_{n})$. In addition, since $\Omega$ is compact,
then, $\varphi_{n}$ are bounded on $\Omega$, $\forall~{}n\geq 0$; thus,
$\Psi_{n}\in\text{BV}(\Omega)$. The compactness result (Proposition 3.3)
guarantees the existence of a subsequence $(\Psi_{\rho(n)})_{n}$ extracted
from $(\Psi_{n})$ s.t.:

$\Psi_{\rho(n)}\underset{n}{\longrightarrow}\Psi\text{ in }L^{1}(\Omega)\text{
sense, and
}\int_{\Omega}|D\Psi|\leq\underset{n}{\lim\inf}\int_{\Omega}|D\Psi_{\rho(n)}|.$
(11)

Since $(\Psi_{n})_{n}$ is positive, then, $\Psi\geq 0$; therefore, one has:

$\int_{\Omega}\Psi_{n}\underset{n}{\longrightarrow}\int_{\Omega}\Psi.$ (12)

$\bullet$ Let $D_{n}=\\{x\in\Omega;~{}\varphi_{n}\leq 0\\}$, $n\in\mathds{N}$.
Then, $\forall~{}n\geq 0$, $H(-\varphi_{n})=\chi_{D_{n}}$.
Since $g$ is bounded ($-1\leq g\leq 1$) in $\Omega$ and
$(\chi_{D_{n}})_{n}\subset\text{BV}(\Omega)$, there exists then a function
$k\in\text{BV}(\Omega)$ and a subsequence $(\chi_{D_{\rho(n)}})_{n}$ (without
loss of generality, we take the same extractor function $\rho$ since the
composition of extractors is also an extractor) s.t.
$g\chi_{D_{\rho(n)}}\underset{n}{\longrightarrow}g\,k$ in $L^{1}(\Omega)$
sense. As in the previous case, the positivity of
$(g\cdotp\chi_{D_{\rho(n)}})_{n}$ and $k$ yields then:

$\int_{\Omega}g\chi_{D_{\rho(n)}}\underset{n}{\longrightarrow}~{}\int_{\Omega}g\,k.$
(13)

(12) and (13) prove the existence of a minimizer for $G$.

Step 2: Let us consider $K$ in the following

$K(\lambda,V,J,\bar{J})=\int_{\Omega}\lvert I-J\rvert^{2}+\mu\lvert\nabla
J\rvert^{2}H(\phi(\lambda,h(\cdotp)))+\int_{\Omega}\lvert
I-\bar{J}\rvert^{2}\\\
+\mu\lvert\nabla\bar{J}\rvert^{2}(1-H(\phi(\lambda,h(\cdotp)))).$ (14)

Previously defined minimizing sequences also satisfy then:
$\underset{n}{\lim}~{}K(\varphi_{n},\lambda_{n},V_{n},J_{n},\bar{J}_{n})=\inf
K$. $H$ can be written as an indicator function by considering the set
$\Theta=\\{x\in\Omega;~{}\phi(\lambda,h(x))\geq 0\\}$; thus, one has:
$H(\phi(\lambda,h(x)))=\chi_{\Theta}$. It is clear that $\chi_{\Theta}$
depends continuously on $\lambda$ and $V$ parameters; since that is the case
for $\Theta$. Let us introduce the function

$\varsigma(\cdotp)=|I-\cdotp|^{2}+|\nabla\cdotp|^{2}.$ (15)

Then, one has:

$K(\lambda,V,J,\bar{J})=\int_{\Omega}\varsigma(J)\chi_{\Theta}+\varsigma(\bar{J})(1-\chi_{\Theta}).$
(16)

Let then introduce sequences $(\chi_{\Theta_{n}})_{n}$ and
$(\varrho_{n})_{n}$, defined $\forall~{}n\in\mathds{N}$, by:

$\chi_{\Theta_{n}}=\chi_{\Theta}(\lambda_{n},V_{n})\text{ and
}\varrho_{n}=\varsigma(J_{n})\chi_{\Theta_{n}}+\varsigma(\bar{J}_{n})(1-\chi_{\Theta_{n}}).$
(17)

Then, thanks to the compactness-lower semi continuity result in $GSBV(\Omega)$
[3], there exists $\varrho\in~{}GSBV(\Omega)$ and a subsequence
$\varrho_{\rho(n)}$ s.t.
$\varrho_{\rho(n)}\underset{n}{\longrightarrow}\varrho$ in $L^{p}$ sense;
$1\leq p<2$; moreover, one has:

$\int_{\Omega}\varsigma(J)\chi_{\Theta}\leq\underset{n}{\lim\inf}\int_{\Omega}\varsigma(J_{n})\chi_{\Theta_{\rho(n)}}$
(18)

and

$\int_{\Omega}\varsigma(\bar{J})(1-\chi_{\Theta})\leq\underset{n}{\lim\inf}\int_{\Omega}\varsigma(\bar{J}_{n})(1-\chi_{\Theta_{\rho(n)}}).$
(19)

Thus, the existence of a minimizer of $K$.

Step 3: Let
$L(\varphi,\lambda,V)=\int_{\Omega}[\xi
g+\dfrac{\gamma}{2}\phi^{2}(\lambda,h(x))]\delta(\varphi)\lvert\nabla\varphi\rvert\,\mathrm{d}x+\zeta\int_{\Omega}d\mathcal{H}^{1}(C(\lambda,h(x)))$.

$\bullet$ One has [12]:

$\int_{\Omega}d\mathcal{H}^{1}(C(\lambda,h(x)))=\int_{\Omega}\delta(\phi(\lambda,h(x)))|\nabla\phi(\lambda,h(x))|\mathrm{d}x.$
(20)

$\Omega$ is a compact set, and since $(\phi_{i})_{i}$ is a family of signed
distance functions, then, $\phi$ is smooth enough. Let us assume $\phi\in
C^{1}(\Omega)$ and consider again the set
$\Theta=\\{x\in\Omega;~{}\phi(\lambda,h(x))\geq 0\\}$ and the subsequence
$(\chi_{\Theta_{n}})_{n}$ defined $\forall~{}n\in\mathds{N}$ by
$\chi_{\Theta_{n}}=\chi_{\Theta}(\lambda_{n},V_{n})$. Then, one also has [12,
1]:

$\int_{\Omega}d\mathcal{H}^{1}(C(\lambda,h(x)))=\int_{\Omega}|D\chi_{\Theta}|.$
(21)

Because $\phi\in\text{BV}(\Omega)$, then, $\forall~{}n,~{}\Theta_{n}$ has
finite perimeter; i.e. $\chi_{\Theta_{n}}\in\text{BV}(\Omega),~{}\forall~{}n$.
Consequently, there exists $k\in\text{BV}(\Omega)$ and a subsequence
$\chi_{\Theta_{\rho(n)}}$ s.t.
$\chi_{\Theta_{\rho(n)}}\underset{n}{\longrightarrow}k$ in $L^{1}(\Omega)$
sense. Since $\chi_{\Theta_{\rho(n)}}$ are characteristic functions, $k$ is
also a characteristic function; let then $k=\chi_{\Theta}$.
Let now $\varphi\in C_{0}^{1}(\Omega,\mathds{R}^{2})$ s.t.
$\lVert\varphi\rVert\leq 1$. Because
$\chi_{\Theta_{\rho(n)}}\underset{n}{\longrightarrow}\chi_{\Theta}$ in
$L^{1}(\Omega)$ sense, then, one has:

$\int_{\Omega}\chi_{\Theta}\text{div}(\varphi)=\underset{n}{\lim}\int_{\Omega}\chi_{\Theta_{\rho(n)}}\text{div}(\varphi)\leq\underset{n}{\lim}\int_{\Omega}|D\chi_{\Theta_{\rho(n)}}|.$
(22)

Thus, by taking the supremum over all $\varphi$, one has:

$\int_{\Omega}d\mathcal{H}^{1}(C(\lambda,h(x)))=\int_{\Omega}|D\chi_{\Theta}|\leq\underset{n}{\lim\inf}\int_{\Omega}|D\chi_{\Theta_{\rho(n)}}|.$
(23)

$\bullet$ Let $W=\\{x\in\Omega;~{}\varphi(x)\geq 0\\}$ and
$f(\cdotp,\lambda,V)=\xi
g(\cdotp)+\dfrac{\gamma}{2}\phi^{2}(\lambda,h(\cdotp))$ defined on $\Omega$.
Following [12, 7], then one has:

$F_{2}(\chi_{W},\lambda,V)=\int f(\cdotp,\lambda,V)|D\chi_{W}|.$ (24)

Let us consider now the sequence $(f_{n})_{n}$ defined for all
$n\in\mathds{N}$ by $f_{n}(\cdotp)=f(\cdotp,\lambda_{n},V_{n})$ in $\Omega$,
where $(\lambda_{n})_{n}$ and $(V_{n})_{n}$ are previously defined sequences.
It is clear that $(f_{n})_{n}$ is a positive sequence, since $f\geq 0$. In
addition, $g,\phi^{2}\in C^{\infty}(\Omega)$ and $\Omega$ is compact; then,
$(f_{n})_{n}\subset\text{BV}(\Omega)$. Therefore, there exists subsequences
$(\lambda_{\rho(n)})_{n}$ and $(V_{\rho(n)})_{n}$ s.t.:
$f_{\rho(n)}(\cdotp)=f(\cdotp,\lambda_{\rho(n)},V_{\rho(n)})\underset{n}{\longrightarrow}~{}f(\cdotp)$
in $L^{1}(\Omega)$ sense, and

$\int_{\Omega}f(\cdotp,\lambda,V)\leq\underset{n}{\lim\inf}\int_{\Omega}f(\cdotp,\lambda_{\rho(n)},V_{\rho(n)}).$
(25)

Tychonoff’s theorem ensures that $\Omega,\Omega_{V}$ and $\Omega_{\lambda}$
are compact sets; then, there exists subsequences $(\lambda_{\rho(n)})_{n}$
and $(V_{\rho(n)})_{n}$ s.t:
$\lambda_{\rho(n)}\underset{n}{\longrightarrow}\lambda$ and
$V_{\rho(n)}\underset{n}{\longrightarrow}V$. Since $f$ is continuous, then,
one has
$f(\cdotp,\lambda_{\rho(n)},V_{\rho(n)})\underset{n}{\longrightarrow}f(\cdotp,\lambda,V)$.

Following [8], let $\varepsilon>0$. There exists then $N\in\mathds{N}$ s.t.
$\forall~{}n\geq N$, one has $|f_{\rho(n)}(\cdotp)-f(\cdotp)|\leq\varepsilon$.
Let us define $\Psi=\\{\psi\in
C_{0}^{1}(\Omega,\mathds{R});~{}\lVert\psi\rVert\leq 1\text{ in }\Omega\\}$
and $\Psi_{\omega}=\\{\psi\in
C_{0}^{1}(\Omega,\mathds{R});~{}\lVert\psi\rVert\leq\omega\text{ in
}\Omega\\}$, for any positive and continuous function
$\omega:\Omega\longrightarrow\mathds{R}$.

Now, let $n\in\mathds{N}$ s.t. $n\geq N$ and let
$\varphi\in\Psi_{f-\varepsilon}$. Then, $\varphi\in\Psi_{f}$. We previously
show that $\forall~{}n\in\mathds{N},~{}\varphi_{n}\in\text{BV}(\Omega)$
implying $W_{n}=\\{x\in\Omega;~{}\varphi_{n}(x)\geq 0\\}$ has a finite
perimeter; i.e.
$\chi_{W_{n}}\in\text{BV}(\Omega),~{}\forall~{}n\in\mathds{N}$. As in the
previous case, there exists then a subsequence $\chi_{W_{\rho(n)}}$ s.t.
$\chi_{W_{\rho(n)}}\underset{n}{\longrightarrow}\chi_{W}$ in $L^{1}(\Omega)$
sense. Then, one has:

$\int_{\Omega}\chi_{W}\text{div}(\varphi)=\underset{n}{\lim}\int_{\Omega}\chi_{W_{\rho(n)}}\text{div}(\varphi).$
(26)

Since $\Psi_{f-\varepsilon}\subseteq\Psi_{f}$, then:

$\int_{\Omega}\chi_{W}\text{div}(\varphi)\leq\underset{n}{\lim}\int_{\Omega}f_{\rho(n)}|D\chi_{W_{\rho(n)}}|.$
(27)

Due to the fact that $n\geq N$, $\varphi\in\Psi_{f-\varepsilon}$ and
$\varepsilon>0$ are arbitrary chosen; then:

$\underset{\varphi\in\Psi_{f-\varepsilon}}{\sup}\int_{\Omega}\chi_{W}\text{div}(\varphi)\leq\underset{n}{\lim}\int_{\Omega}f_{\rho(n)}|D\chi_{W_{\rho(n)}}|.$
(28)

Thus, by letting $\varepsilon\rightarrow 0$, one has:

$\int_{\Omega}f|D\chi_{W}|=\underset{\varphi\in\Psi_{f}}{\sup}\int_{\Omega}\chi_{W}\text{div}(\varphi)\leq\underset{n}{\lim}\int_{\Omega}f_{\rho(n)}|D\chi_{W_{\rho(n)}}|.$
(29)

(23) and (29) prove the existence of a minimizer of $L$.

##  4 Conclusion

A proof of existence of a minimizer of a non-convex variational segmentation
functional is provide here. That is important, since it guarantees the good
evolution of the segmentation model towards the desired objects, and it can be
seen as a completion of a previous work where both the efficiency and
robustness of the segmentation model were already demonstrated without that
proof. However, since the functional is not convex, the existence of a minimum
does not guarantee the uniqueness. We plan to investigate that for a future
work.

## References

  * [1] Luigi Ambrosio, Vicent Caselles, Simon Masnou, and Jean-Michel Morel.  Connected components of sets of finite perimeter and applications to image processing.  Journal of the European Mathematical Society, 3:39–92, 2001.
  * [2] Luigi Ambrosio, Nicola Fusco, and Diego Pallara.  Functions of Bounded Variation and Free Discontinuity Problems.  Oxford Mathematical Monographs, 2000.
  * [3] Luigi Ambrosio and Francesco Ghiraldin.  Compactness of Special Functions of Bounded Higher Variation.  Analysis and Geometry in Metric Spaces, pages 1–30, 2013.
  * [4] Gilles Aubert and Pierre Kornprobst.  Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, volume 147 of Applied Mathematical Sciences.  Springer-Verlag, New York, Inc., New York, 2002.
  * [5] Xavier Bresson, Pierre Vandergheynst, and Jean-Philippe Thiran.  A Variational Model for Object Segmentation Using Boundary Information and Shape Prior Driven by the Mumford-Shah Functional.  International Journal of Computer Vision, 68(2):145–162, 2006.
  * [6] Ethan S. Brown, Tony F. Chan, and Xavier Bresson.  Completely Convex Formulation of the Chan-Vese Image Segmentation Model.  International Journal of Computer Vision, 98:103–121, 2012.
  * [7] Tony F. Chan and Luminata A. Vese.  Active Contours Without Edges.  IEEE Transactions on Image Processing, 10(2):266–277, February 2001\.
  * [8] Yunmei Chen, Hemant D. Tagare, Sheshadri Thiruvenkadam, Feng Huang, David Wilson, Kaundinya S. Gopinath, Richard W. Briggs, and Edward A. Geiser.  Using Prior Shapes in Geometric Active Contours in a Variational Framework.  International Journal of Computer Vision, 50(3):315–328, 2002.
  * [9] G. Chung and L.A. Vese.  Image segmentation using a multilayer level-set approach.  Computing and Visualization in Science, 12:267–285, August 2009\.
  * [10] El Hadji S. Diop and Valérie Burdin.  Bi-planar image segmentation based on variational geometrical active contours with shape priors.  Medical Image Analysis, 17:165–181, 2013.
  * [11] Lawrence C. Evans.  Partial Differential Equations, volume 19 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, Rhode Island, June 1998.
  * [12] Lawrence C. Evans and Ronald F. Gariepy.  Measure Theory and Fine Properties of Functions.  Studies in advanced mathematics. CRC Press, Boca Raton, FL, 1992.
  * [13] Enrico Giusti.  Minimal Surfaces and Functions of Bounded Variation.  Birkhuser, 1994.
  * [14] Enrico Giusti.  Direct Methods in the Calculus of Variations.  World Scientific, 2005.
  * [15] Michael E. Leventon, W. Eric L. Grimson, and Olivier Faugeras.  Statistical Shape Influence in Geodesic Active Contours.  In CVPR, pages 316–323, South Carolina, USA, June 2000.
  * [16] Fang Li, Michael K. Ng, Tie Yong Zeng, and Chunli Shen.  A Multiphase Image Segmentation Method Based on Fuzzy Region Competition.  SIAM Journal on Imaging Sciences, 3:277–299, 2010.
  * [17] Juan C. Moreno, V. B. Surya Prasath, Hugo Proença, and K. Palaniappan.  Fast and globally convex multiphase active contours for brain MRI segmentation.  Computer Vision and Image Understanding, 125:237–250, August 2014\.
  * [18] David Mumford and Jayant Shah.  Optimal Approximations by Piecewise Smooth Functions and Associated Variational Problems.  Communications on Pure and Applied Mathematics, 42:577–685, 1989\.
  * [19] Solène Ozeré, Christian Gout, and Carole Le Guyader.  Joint Segmentation/Registration Model by Shape Alignment via Weighted Total Variation Minimization and Nonlinear Elasticity.  SIAM Journal on Imaging Sciences, 8(3):1981–2020, 2015.
  * [20] Rengarajan Pelapur, VB Surya Prasath, Juan C Moreno, and Michael M Heck.  3d workflow for segmentation and interactive visualization in brain mr images using multiphase active contours.  In IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 921–926. IEEE, 2017.
  * [21] Thomas Pock, Antonin Chambolle, Daniel Cremers, and Horst Bischof.  A convex relaxation approach for computing minimal partitions.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 810–817. IEEE, 2009.
  * [22] VB Surya Prasath, Kiichi Fukuma, Bruce J Aronow, and Hiroharu Kawanaka.  Cell nuclei segmentation in glioma histopathology images with color decomposition based active contours.  In IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 1734–1736. IEEE, 2015.
  * [23] Mark Sussman, Peter Smereka, and Stanley Osher.  A Level Set Approach for Computing Solutions to Incompressible Two-Phase Flow.  Journal of Computational Physics, 114(1994):146–159, 1994.
  * [24] Yongfei Wu and Chuanjiang He.  A convex variational level set model for image segmentation.  Signal Processing, 106:123–133, 2015.
  * [25] Hong-Kai Zhao, Tony Chan, Barry Merriman, and Stanley Osher.  A variational level set approach to multiphase motion.  Journal of Computational Physics, 127(1):179–195, 1996.


# The Price of Prompting: Profiling Energy Use in Large Language Models
Inference

Erik Johannes Husom,
SINTEF,
<EMAIL_ADDRESS>
& Arda Goknil,
SINTEF,
<EMAIL_ADDRESS>
& Lwin Khin Shar,
Singapore Management University,
<EMAIL_ADDRESS>
& Sagar Sen,
SINTEF,
<EMAIL_ADDRESS>

(July 4th, 2024)

###### Abstract

In the rapidly evolving realm of artificial intelligence, deploying large
language models (LLMs) poses increasingly pressing computational and
environmental challenges. This paper introduces MELODI – Monitoring Energy
Levels and Optimization for Data-driven Inference – a multifaceted framework
crafted to monitor and analyze the energy consumed during LLM inference
processes. MELODI enables detailed observations of power consumption dynamics
and facilitates the creation of a comprehensive dataset reflective of energy
efficiency across varied deployment scenarios. The dataset, generated using
MELODI, encompasses a broad spectrum of LLM deployment frameworks, multiple
language models, and extensive prompt datasets, enabling a comparative
analysis of energy use. Using the dataset, we investigate how prompt
attributes, including length and complexity, correlate with energy
expenditure. Our findings indicate substantial disparities in energy
efficiency, suggesting ample scope for optimization and adoption of
sustainable measures in LLM deployment. Our contribution lies not only in the
MELODI framework but also in the novel dataset, a resource that can be
expanded by other researchers. Thus, MELODI is a foundational tool and dataset
for advancing research into energy-conscious LLM deployment, steering the
field toward a more sustainable future. The released code and dataset are
available at https://github.com/ejhusom/MELODI.

##  1 Introduction

The swift progression of artificial intelligence (AI) has precipitated the
emergence of advanced natural language processing (NLP) systems. Large
language models (LLMs) have ascended to prominence among these systems,
proving indispensable across a vast spectrum of applications. Their utility
ranges from simple text predictions to managing complex dialogues.
Concurrently, as these models grow in computational complexity, their energy
demands escalate correspondingly [25, 32, 31]. In an epoch that prioritizes
sustainable computing, the energy expenditure of LLMs is a consideration of
mounting importance and one that commands focused attention [5, 17].

In the current literature, several endeavors aim to quantify and mitigate the
environmental impact of AI. Prior studies have predominantly concentrated on
the training phase of traditional machine learning (ML) models, with the
inference phase often relegated to a secondary focus despite its cumulative
energy footprint over the lifespan of a model [28]. Tools such as Green
Algorithms [16] provide estimations of carbon emissions for computational
tasks and yet lack real-time monitoring capabilities. Furthermore, while
initiatives like CodeCarbon [6] and its integration to ML pipelines [13] offer
a more automated tracking of emissions, they do not cater specifically to the
nuanced demands of LLMs nor provide granular data concerning inference-related
energy consumption.

This paper introduces the MELODI framework designed to monitor and analyze
energy usage during LLM inference. The urgent need for such a framework stems
from the growing environmental and economic costs associated with the
operation of LLMs. MELODI leverages two specialized power usage monitoring
tools (i.e., Scaphandre [27] and Nvidia-smi [22]). Scaphandre tracks the CPU’s
power consumption for the LLM process, while nvidia-smi measures the GPU’s
total power usage. For accurate measurements, the GPU must be exclusively used
for the LLM inference, with no concurrent processes. MELODI records the energy
consumption for each inference process, in addition to the prompt and the
LLM’s response. Furthermore, it facilitates the collection of metadata
associated with LLM inference tasks, enabling a deeper analysis of the
relationship between task complexity and energy utilization.

An important part of our research involved creating a robust dataset essential
for evaluating MELODI’s capabilities. This included gathering a diverse set of
prompts to monitor the energy consumption of various LLMs across different
types of instructions. We deployed these models on different hardware to
ensure a thorough analysis. The data collection includes not only energy
consumption measurements but also related metadata, such as the size and
complexity of prompts, the responses, and the time metrics for each inference
process. This rich dataset helps us explore the relationships between prompt
complexity and the energy expenditure they incur.

Contributions. In summary, we make three main contributions. Firstly, we have
developed a framework integrating open-source tools to monitor power and
energy consumption during the inference phase of LLMs. Secondly, we have
undertaken an extensive data collection initiative involving a variety of
language model deployment frameworks, multiple LLMs, and diverse prompt
datasets to facilitate a comprehensive comparison of energy consumption across
these dimensions. Thirdly, we offer a generalized analysis that elucidates the
relationships between prompt characteristics, such as length and features, and
the energy consumption patterns observed within the collected data.

##  2 Background

###  2.1 Large Language Models (LLMs)

LLMs represent a significant advancement in natural language processing (NLP)
and deep learning (DL). These models, such as OpenAI’s GPT-3.5 architecture,
are based on transformer neural networks, which have revolutionized NLP tasks
by capturing long-range dependencies in text [29]. LLMs, trained on vast text
datasets, learn intricate language patterns and relationships through
unsupervised learning, predicting subsequent text from context. The
integration of LLMs into digital ecosystems is underpinned by advanced APIs
and deployment frameworks. These APIs are essential tools that allow
developers to use LLM features for prompt submission and response generation,
making it possible to add LLM capabilities to various applications. Among the
plethora of tools, several APIs and frameworks, such as Ollama [23], OpenAI’s
GPT API [24], Huggingface’s Transformers [33], Llama.cpp [18], GPT4All [2],
and vLLM [15], have emerged as pivotal to the LLM deployment landscape.

###  2.2 Monitoring Tools and Technologies

Advanced monitoring tools and technologies are essential for tracking and
optimizing energy consumption, thereby mitigating the environmental impact of
AI operations. In this context, MELODI employs the following two tools for
their complementary features:

Scaphandre [27] is one of the few tools that provide detailed insights into
the energy usage of computing systems at the process level. Its ability to
deliver real-time power metrics makes it invaluable for assessing the energy
efficiency of LLM deployments.

NVIDIA System Management Interface (nvidia-smi) [22] is a command-line utility
providing the real-time monitoring of GPU, including power consumption, for
systems equipped with NVIDIA GPUs. It can be used to evaluate the energy
efficiency of LLMs leveraging GPU acceleration.

##  3 Dataset Collection: MELODI Framework for Monitoring Energy Usage

Figure 1: Overview of the MELODI framework.

To understand the energy consumption patterns of LLMs, we created the MELODI
framework, a tool designed to monitor energy usage during the inference
processes of LLMs. Figure 1 provides an architecture of this framework. The
core of MELODI’s approach involves systematically sampling prompts from a
curated collection, submitting these prompts to an LLM, and recording the
prompts, their responses, metadata, and the energy metrics during inference.
This data is cataloged to allow for a detailed analysis of energy consumption
trends during the operational phase of LLMs.

  * •

Input Data (Prompt Dataset): MELODI extracts prompts from a pre-existing
dataset (prompt dataset in Figure 1) and uses them to query a deployed LLM
through an API client.

  * •

Power Usage Monitoring and Data Collection: MELODI integrates two power
monitoring tools, Scaphandre [27] and nvidia-smi [22], to track the power
consumption of the deployed LLM, such as the Ollama model depicted in Figure
1. These tools provide complementary functionalities: Scaphandre measures the
CPU’s power usage specific to the LLM process, while nvidia-smi assesses the
total power usage of the GPU. It is crucial that no other processes operate on
the GPU during LLM inference to ensure the accuracy of nvidia-smi’s
measurements. MELODI then calculates the energy consumption for each prompt,
compiling data samples that encompass the prompt, the LLM’s response, and the
associated energy metrics, thus providing a granular view of energy
utilization.

  * •

Dataset Generation: MELODI iterates through all prompts from the dataset,
capturing the prompt, its response, and energy metrics. These data samples are
aggregated into a comprehensive dataset, encapsulating the energy consumption
of the LLM during inference.

The MELODI framework is contingent upon LLM services that can be queried for
responses. While MELODI is designed to be compatible with any service offering
an API endpoint for response generation, our current implementation
specifically caters to services that conform to either the Ollama- or OpenAI
API specifications, encapsulating the majority of prevalent LLM deployment
services. These API endpoints furnish not only the LLM’s natural language
responses but also critical metadata, including timestamps and token lengths
for both prompts and responses. The landscape of LLM deployment tools is
diverse, featuring platforms such as Llama.cpp [18], GPT4All [2], vLLM [15],
Llamafile [19], and Ollama [23]. For the scope of our experiments, we chose to
utilize Ollama [23] as our model deployment mechanism, attributing this choice
to its straightforward installation process, dual compatibility with CPU and
GPU architectures, and the expansive repository of open-source LLMs it
supports for facile download and deployment.

Scaphandre [27] operates with process-level granularity, monitoring and
recording the power usage of active processes on a computing device. We apply
a regular expression to the process names to isolate the specific process
associated with the LLM service. The frequency at which Scaphandre samples
power metrics is configurable with granularity fine enough to reach the
nanosecond scale. Although a higher sampling frequency increases the
resolution and accuracy of the data, it also requires more storage for data
retention and increases the energy consumption of Scaphandre itself.
Therefore, we also monitor the energy consumption of Scaphandre, enabling an
assessment of the energy overhead incurred by the measurement process. In
contrast, nvidia-smi [22] tracks the power usage of the entire GPU and lacks
the capability to distinguish among multiple processes concurrently utilizing
the GPU. To guarantee precise measurements, we limit the GPU to solely
operating the LLM inference process. Our monitoring tools measure the power
consumption $P$ of a process in microwatts ($\mu$W). We then compute the
energy consumption $E$ by integrating the power consumption over the duration
$t$, applying the trapezoidal rule. With $t$ expressed in seconds, we convert
$E$ into kilowatt-hours (kWh) by dividing by $3.6\times 10^{12}$, facilitating
a standardized energy usage assessment.

##  4 Dataset Composition

Table 1: Prompt datasets. | Prompt
---
dataset
| Avg. energy
---
cons. (kWh)
| Avg. response
---
token length
Alpaca | 4.09e-04 | 229.34
Code-feedback | 6.93e-04 | 372.51

This section outlines the energy consumption dataset collected with MELODI,
using diverse computing systems (from high-end servers to laptops) and
multiple prompt datasets for several LLMs. Table 1 lists the prompt datasets
in dataset collection, i.e., Alpaca [1] and Code-Feedback [12], and their
average energy consumption and response token length. The Alpaca dataset,
produced using OpenAI’s text-davinci-003 engine, contains 52,000 prompts
designed to enhance instruction-following capabilities in language models. The
dataset primarily includes text generation tasks and is tailored to train pre-
trained language models to follow complex instructions more effectively. The
Code-Feedback dataset supports the OpenCodeInterpreter model [35] designed to
refine code by integrating code execution and human feedback. This dataset
features 68,000 multi-turn interactions, combining user instructions with
compiler responses to enhance model training in coding scenarios.

Table 2: LLMs used in data collection. Model name/size |  | Avg. energy
---
cons. (kWh)
| Avg. response
---
token length
codellama-7b | 2.05e-04 | 451.52
codellama-70b | 4.40e-03 | 330.04
gemma-2b | 8.30e-05 | 279.32
gemma-7b | 1.46e-04 | 249.41
llama3-8b | 1.34e-04 | 255.20
llama3-70b | 2.26e-03 | 251.46

Table 2 summarizes the LLMs with their average energy consumption and response
token lengths. The models range from codelama-7b to llama3-70b, with energy
consumption varying from as low as $8.30\times 10^{-5}$ kWh for gemma-2b to
$2.26\times 10^{-3}$ kWh for llama3-70b. The average response token lengths
also vary, with codelama-7b generating the longest responses at 451.52 tokens,
while gemma-7b records shorter lengths at 249.41 tokens.

Table 3 details the hardware used in our data collection. The diversity of the
hardware used during data collection covers a wide range of processing power,
memory capacities, and graphics capabilities, crucial for a comprehensive
analysis of energy consumption across different computing environments.

Table 3: Hardware used in the data collection. Machine | CPU | Memory | GPU | GPU memory
---|---|---|---|---
Server | AMD EPYC 7643 48-Core Processor | 528GB | NVIDIA RTX A5000 | 24GB
Workstation | Intel Xeon W-2223 8-core @ 3.6GHz | 128GB | NVIDIA RTX A2000 | 12GB
Laptop 1 | Intel i5 11th Gen 12-core @ 2.4GHz | 16GB | None | None
Laptop 2 | Intel i7 10th Gen 12-core @ 2.7GHz | 32GB | NVIDIA Quadro RTX 4000 | 8GB

Table 4 provides a detailed summary of the energy consumption dataset obtained
using MELODI, capturing data from different hardware setups and LLMs under
varying operational conditions. The dataset encompasses an array of data
points per sample. These include the prompt and response; token lengths for
both prompt and response; the timestamp of the API query; time series data on
the power usage of the LLM service during inference and of Scaphandre during
the monitoring period; and the aggregated energy consumption of the LLM
service during inference.

Table 4: Overview of the energy consumption dataset. ID | Prompt dataset | Model | Model size | Hardware | No. of prompts |  | Avg energy cons.
---
per response (kWh)
| Avg response
---
token length
1 | codefeedback | codellama | 7b | workstation | 3084 | 1.83e-04 | 431.13
2 | codefeedback | codellama | 7b | laptop1 | 5295 | 1.85e-04 | 403.63
3 | codefeedback | codellama | 7b | laptop2 | 3555 | 2.47e-04 | 520.32
4 | codefeedback | codellama | 70b | workstation | 161 | 4.40e-03 | 330.04
5 | alpaca | gemma | 2b | laptop1 | 5295 | 1.85e-04 | 403.63
6 | alpaca | gemma | 2b | workstation | 11828 | 3.65e-05 | 187.91
7 | codefeedback | gemma | 2b | workstation | 9897 | 7.30e-05 | 318.22
8 | codefeedback | gemma | 2b | laptop2 | 4972 | 7.36e-05 | 305.29
9 | alpaca | gemma | 2b | laptop2 | 5101 | 4.70e-05 | 181.52
10 | alpaca | gemma | 7b | laptop2 | 5099 | 9.81e-05 | 160.60
11 | codefeedback | gemma | 7b | workstation | 5885 | 1.81e-04 | 338.23
12 | alpaca | gemma | 7b | workstation | 8735 | 1.05e-04 | 165.09
13 | codefeedback | gemma | 7b | laptop2 | 3387 | 2.01e-04 | 333.73
14 | alpaca | llama3 | 8b | laptop2 | 5101 | 1.34e-04 | 255.20
15 | alpaca | llama3 | 70b | server | 1026 | 2.26e-03 | 251.46

##  5 Dataset Analysis

We analyze the energy consumption dataset to address three Research Questions
(RQ)s:

  * •

RQ1. How does the energy consumption of LLM inference vary across different
hardware, models, and prompt datasets?

  * •

RQ2. What is the relationship between prompt complexity, response
characteristics, and the energy consumption of LLMs during the inference
process?

  * •

RQ3. Can we develop a predictive model that accurately forecasts the energy
consumption of LLMs based on prompt features and response characteristics?

###  5.1 Analysis Setup

_Data Preparation._ Our raw data consists of power usage over time, which we
aggregate to calculate the energy consumption for each inference process as
outlined in Section 3. These aggregated values are then compiled into distinct
energy consumption datasets, categorized by the specific hardware, model, and
prompt dataset utilized during the inference.

_Statistical Analysis._ Our analysis of the energy consumption datasets
focuses on two metrics: energy per token and energy per response. Energy
consumption per token is crucial as it evaluates resource use across different
inference setups regardless of text volume. Meanwhile, energy per response is
beneficial for estimating resource usage relative to the input prompt. We
conduct statistical analyses on these metrics to compare across model types,
sizes, hardware setups, and the specific prompt datasets used during
inference, providing a comprehensive view of energy dynamics.

_Visualization._ We employ box plots to visualize the distribution of energy
consumption for each model and hardware configuration (see Figure 2). The box
plots depict the median energy consumption as a red line, the interquartile
range with the main box, and extend to 1.5 times the interquartile range with
whiskers, providing a clear summary of variability and central tendency.

_Interpretation._ We interpret results through a comparative analysis of
energy consumption across different scenarios. The relationship between prompt
complexity and energy consumption is assessed using the Pearson correlation
coefficient, which ranges from 0 to 1 to indicate variable correlation.
Additionally, predictive models for energy consumption are evaluated using the
$R^{2}$ score.

###  5.2 Results

####  5.2.1 RQ1 (energy consumption of LLM inference across different setups)

To address RQ1, we performed a comparative analysis of energy consumption
across various LLMs operating on different hardware. The box plots in Figure 2
graphically represent this analysis, showing the energy usage of LLMs during
inference on diverse hardware setups.

_Model Size._ Figure 2(a) categorizes energy consumption per token by the
model utilized for inference. Notably, the largest models (codellama-70b with
Code-Feedback and llama3-70b with Alpaca) exhibit energy usage approximately
100 times greater than their smallest counterparts (codellama-7b with Code-
Feedback and llama3-8b with Alpaca). Additionally, the larger models (gemma-7b
with both Alpaca and Code-Feedback) show an energy consumption that is roughly
ten times higher than their smaller versions (gemma-2b with Alpaca and Code-
Feedback).

_Hardware._ Figure 2(b) organizes results by the hardware used for model
execution. Energy consumption is noticeably higher when LLM tasks are run on
the laptops than on the workstation. Specifically, Laptop1 (CPU-only) shows
similar energy usage levels when operating different models (codellama-7b with
Code-Feedback and gemma-2b with Alpaca), suggesting inefficiencies in CPU-
based processing for LLM tasks since we would expect a significant difference
when running a 2b model vs a 7b model. This observation could also reflect the
limitations of the CPU-monitoring tool Scaphandre, as the power metrics are
only estimates [14]. Comparisons between Laptop2 and the workstation, despite
the latter’s more robust GPU (12GB vs. 8GB), reveal roughly equivalent energy
usage, underscoring potential disparities in hardware efficiency.

_Model._ In energy assessments of different models of the same size
(codellama-7b with Code-Feedback vs. gemma-7b with Code-Feedback) run on both
a workstation and Laptop2, gemma-7b consistently displayed higher energy
consumption than codellama-7b. This observation suggests that codellama-7b is
a slightly more energy-efficient model than gemma-7b.

_Prompt Datasets._ To evaluate the energy consumption per token across two
prompt datasets, we analyzed the box plots for gemma-2b and gemma-7b in Figure
2(a), the only models tested with both prompt datasets. The analysis reveals
that, except in one instance, the Alpaca dataset consistently led to higher
energy consumption per token. Additionally, the interquartile range,
representing variability in energy consumption, is notably wider in all cases,
suggesting greater fluctuation in energy use when using the Alpaca dataset.

Table 4 facilitates a comparison of energy consumption per prompt, revealing
that the median consumption for the Code-Feedback prompt dataset exceeds that
of the Alpaca dataset during inference. This discrepancy likely arises from
the longer average response length associated with the Code-Feedback prompts,
which at 373 words surpasses the 229 words of the Alpaca prompts.

##### RQ1 Conclusion.

Our analysis indicates marked disparities in energy consumption among
different LLMs and hardware configurations. Larger models like codellama-70b
and llama3-70b use roughly 100 times more energy per token than smaller ones.
Energy demands are higher for LLMs running on laptops than workstations,
particularly due to inefficiencies in CPU processing. Models of the same size
exhibit varying energy efficiencies. Notably, the Code-Feedback dataset leads
to greater energy use per token than the Alpaca dataset, likely due to longer
response lengths.

(a) Comparison of energy consumption per token across models.

(b) Comparison of energy consumption per token across hardware setups
(Codellama-70b is excluded for the workstation to not skew the plot).

Figure 2: Comparative energy consumption per token across inference setups.

####  5.2.2 RQ2 (the relationship between prompt complexity, response
characteristics and the energy consumption)

To address RQ2, we used Python frameworks—Spacy [11], nltk [4], textblob [20],
and textstat [30]—to derive 57 text-based features. We integrated these
features with our energy consumption dataset and calculated the Pearson
correlation coefficient between energy consumption per prompt and each
feature. Table 5 presents the top 20 features from this analysis.

Table 5: Correlations between features and energy consumption per response, calculated across all samples of our datasets. All features are derived from the input prompt, except those marked with a star (*), which are obtained from the response. Feature | Correlation | Feature | Correlation
---|---|---|---
*response_token_length | 0.846 | reading_time | 0.080
response_duration | 0.625 | lexicon_count | 0.078
total_duration | 0.618 | prompt_token_length | 0.075
adjectives | 0.113 | adverbs | 0.073
adj_count | 0.113 | adverb_count | 0.073
polysyllabcount | 0.095 | stop_word_count | 0.072
long_word_count | 0.090 | noun_count | 0.070
syllable_count | 0.083 | monosyllabcount | 0.068
letter_count | 0.082 | word_count | 0.068
char_count | 0.080 | verb_count | 0.067

Our analysis revealed that significant correlations with energy consumption
per prompt are primarily linked to response characteristics rather than the
complexity of the prompt. Key factors such as response token length, response
duration, and total inference duration show strong positive correlations with
energy consumption, with coefficients of 0.846, 0.625, and 0.618,
respectively. This observation suggests that energy consumption escalates with
an increase in response tokens due to more extensive processing within the
model, highlighting that longer and more time-intensive responses
significantly drive higher energy usage.

Upon analyzing correlations with prompt complexity features, we observe only
low positive correlations. Attributes like adjective count, syllable count,
and long word count demonstrate modest correlations with energy consumption,
with coefficients of 0.113, 0.083, and 0.090, respectively. These results
indicate that prompt complexity (given our set of features) has a minimal
impact on energy consumption. Instead, the length and duration of responses
are more significant factors. This insight suggests that optimizing the
response generation process could be more effective in reducing energy
consumption than merely simplifying the input prompts.

##### RQ2 Conclusion.

The results show that response characteristics such as token length and
duration are strongly correlated with energy usage, indicating higher
consumption with longer responses. Conversely, prompt complexity features like
adjective and syllable counts exhibit low correlations, suggesting minimal
impact on energy use. These findings emphasize that managing response
generation may offer more significant energy savings than simplifying prompts.

####  5.2.3 RQ3 (predictive model for the energy consumption of LLMs)

Figure 3: $R^{2}$ scores of RF models using only response length for
forecasting energy consumption per response.

To address RQ3, we developed ML models using the energy consumption dataset,
focusing on either prompt or response characteristics as input features. Our
exploratory analysis identified Random Forest (RF) as the optimal model for
effectively handling both types of input features. This choice was based on
their performance and suitability for the data structure encountered in our
dataset. Hence, we developed RF models (using either response token length or
prompt characteristics) across hardware setups, models, and prompt datasets
(one RF model for one LLM utilizing one prompt dataset on one hardware setup).

Table 5 shows that energy consumption highly correlates with response
characteristics such as token length and duration. Figure 3 presents the
$R^{2}$ scores of RF models using only response token length, demonstrating
high predictive performance in most cases, with the majority achieving $R^{2}$
greater than 0.97 and an average $R^{2}$ score of 0.94. However, the RF models
for laptop1 with only a CPU show a lower $R^{2}$ of 0.74, suggesting potential
inaccuracies in CPU-based energy consumption estimates. The findings reveal
that constraining the length of responses—by explicitly specifying the maximum
text length in the prompts—could significantly reduce energy consumption
during model operations.

Predictive models relying solely on prompt characteristics exhibit limited
performance, as depicted in Figure 4. Analysis of the $R^{2}$ scores across
different models reveals variability in predictive accuracy. For example, the
RF models for LLMs like gemma-7b, utilized with the Code-Feedback dataset on
both a workstation and Laptop2, as well as gemma-2b using the Code-Feedback
dataset on the workstation, show relatively higher $R^{2}$ scores, ranging
between 0.549 and 0.580. This demonstrates some levels of predictive
effectiveness, particularly under specific hardware and dataset conditions.

Figure 4: R2 scores of RF models using prompt characteristics for forecasting
energy consumption per response.

Figure 4 illustrates that RF models for some LLMs, such as codellama-7b using
Code-Feedback on laptop1 and laptop2, demonstrate notably poor predictive
performance, with negative $R^{2}$ scores signaling ineffective model fitting
and potential discrepancies in model predictions. Specifically, the RF model
for codellama-7b utilizing Code-Feedback on laptop2 shows an $R^{2}$ score of
-205.897, indicating a significant divergence between predicted and actual
energy consumption. Generally, the RF models for gemma models show more
predictable energy consumption patterns than llama models. Nonetheless, the
small dataset size limits the robustness of these conclusions.

##### RQ3 Conclusion.

Random Forest models showed strong predictive abilities, especially when using
response characteristics, with most achieving an $R^{2}$ score over 0.97.
However, models for CPU-only laptops performed poorly, indicating potential
inaccuracies in CPU-based energy estimates. Overall, models trained on
response features were more effective than those using prompt characteristics,
highlighting areas for energy optimization in LLM operations.

###  5.3 Threats to validity

_Threats to internal validity._ The primary concern regarding the internal
validity of our data collection and analysis is the accuracy of the power
usage monitoring tools. The precision of the nvidia-smi tool, as noted in the
documentation of NVIDIA [7], has a stated accuracy within $\pm 5$ Watts.
However, a study by Yang et al. [34] suggests the error margin might reach up
to $\pm 5\%$. Accurate GPU power usage readings also necessitate that no other
processes utilize the GPU concurrently. While we ensured this in most
experiments, some base processes remained active on the GPU of the
workstation, though their impact on baseline energy consumption was minimal.
Scaphandre only provides an estimate of the power usage based on the RAPL
interface of Intel processors [27] without quantifying accuracy, potentially
affecting the reliability of our energy consumption data. Additionally, power
efficiency variations in identical hardware models could introduce more
variability to our results. Future research should utilize more precise power
measurement tools and standardized tests across different hardware to better
understand and quantify these discrepancies.

_Threats to external validity._ The generalizability of our results is
constrained by the limited range of inference scenarios analyzed, particularly
in terms of hardware setups and LLMs utilized. The small sample size makes it
challenging to draw robust conclusions, and the extent to which our findings
can be generalized depends on the representativeness of the selected hardware
and model configurations relative to the broader array of LLM deployments.

##  6 Discussion and Future Work

Our study provides insights into the energy consumption of LLM inference while
identifying areas needing further research. One limitation identified is the
accuracy of CPU-based power monitoring, which may compromise our results.
Despite using the Scaphandre tool for measuring CPU power, we observed similar
energy consumption across models of significantly different sizes, suggesting
possible measurement imprecision. This was particularly evident in the reduced
predictive performance of energy consumption on CPU-only setups, as opposed to
configurations equipped with GPUs.

Our results reveal that response token length is a reliable indicator of
energy consumption, suggesting that managing response lengths could
effectively control energy use. However, the connection between prompt
complexity and energy consumption is less definitive. While models based on
prompt characteristics show potential, their performance varies. Future
research could explore the potential of using LLMs or other NLP models to
analyze prompts for energy consumption prediction, balancing the benefits
against the potential energy costs of such analyses.

Our current analysis does not address the quality of responses generated. Our
dataset, however, provides a rich foundation for future research to explore
the relationship between response quality and energy consumption.
Understanding whether higher-quality responses inherently require more energy
could inform the development of more efficient models and prompt designs.

To enhance our study’s generalizability, we plan to test a wider array of
hardware configurations and model types, allowing us to better understand
energy consumption variations. Comparing the energy efficiency of task-
specific models against general-purpose models in different applications would
also be valuable. This analysis could reveal if specialized models yield
significant energy savings for specific tasks, ensuring that comparisons
maintain a consistent base model for accuracy.

Future research could explore patterns in energy consumption across models,
focusing beyond mere size to include architectural differences. This could
reveal how specific design choices impact energy demands and help optimize
models for better energy efficiency without sacrificing performance.

##  7 Related Work

The merging of NLP and sustainable computing, emphasized in studies like the
investigation of Strubell et al. [28] into the energy use and carbon footprint
of NLP model training, is a pivotal aspect of AI. These studies stress the
need for energy-efficient practices across AI model lifecycles and have
spurred extensive research into sustainable AI. Meanwhile, initiatives by
Henderson et al. [10] advocate for transparent reporting of energy
consumption, enhancing accountability, especially during the training phase.
Tools like Green Algorithms [16], CodeCarbon [6], and CarbonTracker [3] have
been developed to estimate computational carbon emissions, yet they often
provide general rather than detailed analyses necessary for large-scale LLM
deployment.

Luccioni et al. [21] and Desislavov et al. [8] found that general-purpose ML
models are more energy-intensive than task-specific ones and that efficiency
gains in NLP and computer vision do not necessarily correlate with increased
energy consumption. In contrast, MELODI, focusing on the inference stage,
delivers real-time energy assessments of LLMs by utilizing Scaphandre and
nvidia-smi to directly measure power usage. This method provides detailed
energy metrics at the API level, offering a more nuanced evaluation of energy
use than broader estimates and enhancing MELODI’s role in sustainable AI.

Recent studies, including those by Liang et al. [17] and Samsi et al. [26],
focus on sustainable AI by analyzing the LLMs’ energy usage and carbon
footprint. These studies highlight energy demands across various LLM
configurations. However, MELODI enhances these efforts by providing a
comprehensive framework that measures LLM energy consumption by leveraging
Scaphandre and nvidia-smi for real-time energy tracking of both CPUs and GPUs.
This capability enables a more dynamic energy efficiency optimization in LLM
deployment, distinguishing MELODI with its predictive and monitoring
strengths.

Everman et al. [9] analyzed the carbon footprint of open-source LLMs during
inference, using the Software Carbon Intensity (SCI) to gauge environmental
impact. Their findings debunked the notion that higher carbon footprints
correlate with better model quality and highlighted GPUs’ role in reducing
emissions. In contrast, MELODI supports real-time power monitoring during
inference, generating data that serves as a benchmark and facilitates the
development of ML models for predicting energy consumption. Thus, while
Everman et al. focus on comparative carbon impact analysis, MELODI enables
continuous monitoring and predictive energy management.

##  8 Conclusion

In conclusion, MELODI represents a noteworthy leap forward in advancing
energy-aware practices within the domain of LLMs. By formulating a precise
methodology and unveiling an open-source instrument tailored for real-time
monitoring of energy consumption throughout the LLM inference process, MELODI
effectively bridges a vital chasm in sustainable computing. Our data
collection, encompassing various LLM architectures, hardware setups, and
prompt datasets, provides a robust platform for rigorous comparison and
nuanced analysis. This endeavor facilitates a deeper understanding of the
energy dynamics associated with LLM deployment scenarios, offering critical
insights that contribute to the optimization and sustainability of LLM
applications.

## Acknowledgments and Disclosure of Funding

The work has been conducted as part of the ENFIELD project (101120657) funded
by the European Commission within the HEU Programme.

## References

  * [1] Alpaca.  https://huggingface.co/datasets/tatsu-lab/alpaca, Visited in 2024.
  * [2] Yuvanesh Anand, Zach Nussbaum, Adam Treat, Aaron Miller, Richard Guo, Ben Schmidt, GPT4All Community, Brandon Duderstadt, and Andriy Mulyar.  Gpt4all: An ecosystem of open source compressed language models.  arXiv preprint arXiv:2311.04931, 2023.
  * [3] Lasse F Wolff Anthony, Benjamin Kanding, and Raghavendra Selvan.  Carbontracker: Tracking and predicting the carbon footprint of training deep learning models.  arXiv preprint arXiv:2007.03051, 2020.
  * [4] Steven Bird, Ewan Klein, and Edward Loper.  Natural language processing with Python: analyzing text with the natural language toolkit.  " O’Reilly Media, Inc.", 2009.
  * [5] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al.  On the opportunities and risks of foundation models.  arXiv preprint arXiv:2108.07258, 2021.
  * [6] CodeCarbon.  https://codecarbon.io/, Visited in 2024.
  * [7] NVIDIA Corporation.  Nvidia system management interface, 2023.  2024-05-03.
  * [8] Radosvet Desislavov, Fernando Martínez-Plumed, and José Hernández-Orallo.  Trends in ai inference energy consumption: Beyond the performance-vs-parameter laws of deep learning.  Sustainable Computing: Informatics and Systems, 38:100857, 2023.
  * [9] Brad Everman, Trevor Villwock, Dayuan Chen, Noe Soto, Oliver Zhang, and Ziliang Zong.  Evaluating the carbon impact of large language models at the inference stage.  In IEEE international performance, computing, and communications conference (IPCCC), pages 150–157. IEEE, 2023.
  * [10] Peter Henderson, Jieru Hu, Joshua Romoff, Emma Brunskill, Dan Jurafsky, and Joelle Pineau.  Towards the systematic reporting of the energy and carbon footprints of machine learning.  Journal of Machine Learning Research, 21(248):1–43, 2020.
  * [11] Matthew Honnibal and Ines Montani.  spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing.  To appear, 2017.
  * [12] https://huggingface.co/datasets/m-a-p/Code-Feedback.  https://huggingface.co/datasets/tatsu-lab/alpaca, Visited in 2024.
  * [13] Erik Johannes Husom, Sagar Sen, and Arda Goknil.  Engineering carbon emission-aware machine learning pipelines.  In IEEE/ACM 3th International Conference on AI Engineering–Software Engineering for AI (CAIN), 2024.
  * [14] Mathilde Jay, Vladimir Ostapenco, Laurent Lefèvre, Denis Trystram, Anne-Cécile Orgerie, and Benjamin Fichel.  An experimental comparison of software-based power meters: focus on cpu and gpu.  In 2023 IEEE/ACM 23rd International Symposium on Cluster, Cloud and Internet Computing (CCGrid), pages 106–118. IEEE, 2023.
  * [15] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica.  Efficient memory management for large language model serving with pagedattention.  In Proceedings of the 29th Symposium on Operating Systems Principles, pages 611–626, 2023.
  * [16] Loïc Lannelongue, Jason Grealey, and Michael Inouye.  Green algorithms: quantifying the carbon footprint of computation.  Advanced science, 8(12):2100707, 2021.
  * [17] Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al.  Holistic evaluation of language models.  arXiv preprint arXiv:2211.09110, 2022.
  * [18] Llama.cpp.  https://github.com/ggerganov/llama.cpp, Visited in 2024.
  * [19] Llamafile.  https://github.com/Mozilla-Ocho/llamafile, Visited in 2024.
  * [20] Steven Loria.  textblob documentation.  Release 0.15, 2, 2018.
  * [21] Alexandra Sasha Luccioni, Yacine Jernite, and Emma Strubell.  Power hungry processing: Watts driving the cost of ai deployment?  arXiv preprint arXiv:2311.16863, 2023.
  * [22] NVIDIA.  https://developer.nvidia.com/nvidia-system-management-interface, Visited in 2024.
  * [23] Ollama.  https://github.com/ollama/ollama, Visited in 2024.
  * [24] OpenAI.  https://platform.openai.com/, Visited in 2024.
  * [25] Matthias C Rillig, Marlene Ågerstrand, Mohan Bi, Kenneth A Gould, and Uli Sauerland.  Risks and benefits of large language models for the environment.  Environmental Science & Technology, 57(9):3464–3466, 2023.
  * [26] Siddharth Samsi, Dan Zhao, Joseph McDonald, Baolin Li, Adam Michaleas, Michael Jones, William Bergeron, Jeremy Kepner, Devesh Tiwari, and Vijay Gadepally.  From words to watts: Benchmarking the energy costs of large language model inference.  In IEEE High Performance Extreme Computing Conference (HPEC), pages 1–9. IEEE, 2023.
  * [27] Scaphandre.  https://github.com/hubblo-org/scaphandre, Visited in 2024.
  * [28] Emma Strubell, Ananya Ganesh, and Andrew McCallum.  Energy and policy considerations for deep learning in nlp.  arXiv preprint arXiv:1906.02243, 2019.
  * [29] Ilya Sutskever, Oriol Vinyals, and Quoc V Le.  Sequence to sequence learning with neural networks.  Advances in neural information processing systems, 27, 2014.
  * [30] textstat.  https://github.com/textstat/textstat, Visited in 2024.
  * [31] Laura Weidinger, John Mellor, Maribeth Rauh, Conor Griffin, Jonathan Uesato, Po-Sen Huang, Myra Cheng, Mia Glaese, Borja Balle, Atoosa Kasirzadeh, et al.  Ethical and social risks of harm from language models.  arXiv preprint arXiv:2112.04359, 2021.
  * [32] Laura Weidinger, Jonathan Uesato, Maribeth Rauh, Conor Griffin, Po-Sen Huang, John Mellor, Amelia Glaese, Myra Cheng, Borja Balle, Atoosa Kasirzadeh, et al.  Taxonomy of risks posed by language models.  In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 214–229, 2022.
  * [33] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al.  Huggingface’s transformers: State-of-the-art natural language processing.  arXiv preprint arXiv:1910.03771, 2019.
  * [34] Zeyu Yang, Karel Adamek, and Wesley Armour.  Part-time power measurements: nvidia-smi’s lack of attention, 2024.
  * [35] Tianyu Zheng, Ge Zhang, Tianhao Shen, Xueling Liu, Bill Yuchen Lin, Jie Fu, Wenhu Chen, and Xiang Yue.  Opencodeinterpreter: Integrating code generation with execution and refinement.  https://arxiv.org/abs/2402.14658, 2024.