myexamplef[Example][List of Examples]

# Tokenization and the Noiseless Channel

Vilém Zouhar${}^{\text{ {{\color[rgb]{0.0,0.0,0.0}{E}}}}}$ Clara
Meister${}^{\text{ {{\color[rgb]{0.0,0.0,0.0}{E}}}}}$ Juan Luis
Gastaldi${}^{\text{ {{\color[rgb]{0.0,0.0,0.0}{E}}}}}$ Li Du${}^{\text{
{\color[rgb]{0,0.1,0.4}{J}}}}$
Mrinmaya Sachan${}^{\text{ {{\color[rgb]{0.0,0.0,0.0}{E}}}}}$ Ryan
Cotterell${}^{\text{ {{\color[rgb]{0.0,0.0,0.0}{E}}}}}$

ETH Zürich${}^{\text{ {{\color[rgb]{0.0,0.0,0.0}{E}}}}}$ Johns Hopkins
University${}^{\text{ {\color[rgb]{0,0.1,0.4}{J}}}}$
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Subword tokenization is a key part of many NLP pipelines. However, little is
known about why some tokenizer and hyperparameter combinations lead to better
downstream model performance than others. We propose that good tokenizers lead
to _efficient_ channel usage, where the channel is the means by which some
input is conveyed to the model and efficiency can be quantified in
information-theoretic terms as the ratio of the Shannon entropy to the maximum
possible entropy of the token distribution. Yet, an optimal encoding according
to Shannon entropy assigns extremely long codes to low-frequency tokens and
very short codes to high-frequency tokens. Defining efficiency in terms of
Rényi entropy, on the other hand, penalizes distributions with either very
high or very low-frequency tokens. In machine translation, we find that across
multiple tokenizers, the Rényi entropy with $\alpha=2.5$ has a very strong
correlation with Bleu: $0.78$ in comparison to just $-0.32$ for compressed
length.

†† We release the tokenization-scorer package (App. B).

##  1 Introduction

Tokenization, the practice of breaking up text into words or subword pieces,
or more generally, tokens,111To avoid ambiguity, we eschew the common
expressions word and subword and, instead, adopt the term token to mean an
element of the vocabulary _after_ tokenization. We formally define token in §
2. is often the first step in an NLP pipeline. A wide variety of tokenization
functions have been proposed in the NLP literature Mermer (2010); Sennrich et
al. (2016); Kudo (2018). And, indeed, research on developing a good
tokenization function continues because _how_ one tokenizes may have a large
impact on model performance in the downstream task. For instance, Gowda and
May (2020) note Bleu ranges from 28 to 37 just by changing the size of the
vocabulary in their machine translation (MT) pipeline. A direct _extrinsic_
evaluation of a tokenization function, however, is computationally intensive:
One first has to retokenize the corpora (generally quick), but then retrain
the NLP model (often computationally intensive) to evaluate the effect. For
this reason, characterizing the _intrinsic_ properties of a good tokenization
function has practical benefits (Gallé, 2019; Gowda and May, 2020).

Our paper takes an information-theoretic approach to characterizing a good
tokenization function. Following Gallé (2019), we contend that tokenization
may be fruitfully viewed as determining a good dictionary code for a language.
Fortunately, dictionary codes are equipped with a natural intrinsic metric of
utility (expected code length) whereas there are many ways to extrinsically
measure the tokenization quality. For simplicity and in line with previous
research, we choose a specific downstream task metric: Bleu (Papineni et al.,
2002) in the domain of MT.222In Tab. 2 (Appendix) we replicate the findings
with ChrF (Popović, 2015), BLEURT (Sellam et al., 2020) and COMET (Rei et al.,
2020).

We hypothesize that, ceteris paribus, downstream task metrics should correlate
with the expected code length of the unigram token distribution. While not
immediately intuitive, the motivation is that there is a theoretical
connection between the expected code length (under an optimal encoder) of a
token distribution and that distribution’s Shannon entropy: The latter gives
us a lower bound on the former. And given a fixed vocabulary size, higher
entropy token distributions are more desirable because they are more balanced,
i.e., there are fewer tokens that occur too rarely or too frequently. This
characteristic should in turn balance a model’s ability to learn
representations for the entire vocabulary, which requires exposure to enough
instances of each token while also penalizing the use of very frequent
character sequences as tokens, which is often inefficient due to their lack of
distinct meaning.

Yet when using Shannon entropy as our metric of a distribution’s balance, the
optimal token distribution may still include a large number of infrequent
tokens. This behavior may be undesirable for a number of reasons that we
subsequently discuss. Accordingly, we formulate the compression principle,
which states that downstream task metrics, e.g., Bleu, should correlate with
the expected code length subject to a penalty for long codewords (which
correspond to infrequent tokens). Consequently, we introduce a more nuanced
formulation of efficiency that employs Rényi entropy (Rényi, 1961),333Campbell
(1965) shows that Rényi gives a lower-bound on the expected length of an
optimal code subject to a length penalty, i.e., overly long or short codewords
are penalized. whose hyperparameter $\alpha$ allows us to penalize the use of
long codes to varying degrees.

In the experimental portion of our paper, we predict the performance of MT
models. We find that the channel efficiency with Rényi entropy with
$\alpha=2.5$ yields a Pearson correlation of $0.78$ with Bleu on German
$\rightarrow$ English MT (1M parallel sentences from CommonCrawl). This stands
in contrast to Shannon entropy or expected sequence length, which yield
Pearson correlations of only $0.22$ and $-0.30$, respectively.

We also provide an easy-to-use package to score tokenizations. See App. B for
usage instructions.

##  2 Tokenization

Tokenization is generally defined informally as the breaking up of text into a
sequence of tokens which are then encoded into a machine-interpretable format.
However, to proceed with our analysis, we require a more formal treatment.
First, we assume that there exists an alphabet, a finite, non-empty set of
characters $\Sigma$. We call a string of characters
$\bm{\sigma}=\langle\sigma_{1}\sigma_{2}\cdots\sigma_{N}\rangle\in\Sigma^{*}$
a text. In this formulation, we assume that the alphabet $\Sigma$ includes all
characters, including punctuation and a distinguished white space character.
Finally, an unordered multiset of texts
$\\{\bm{\sigma}_{1},\ldots,\bm{\sigma}_{M}\\}\subset\Sigma^{*}$ is termed a
corpus of size $M$. We denote the true distribution over all texts as
$p_{\scaleto{\Sigma^{*}}{4pt}}$. Every $p_{\scaleto{\Sigma^{*}}{4pt}}$ induces
a marginal distribution over $\Sigma$, which we call the $\Sigma$-unigram
distribution:

$p_{\scaleto{\Sigma}{4pt}}(\sigma)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sum_{\bm{\sigma}\in\Sigma^{*}}p_{\scaleto{\Sigma^{*}}{4pt}}(\bm{\sigma})\,\frac{\mathrm{count}(\sigma,\bm{\sigma})}{|\bm{\sigma}|}$
(1)

where $\mathrm{count}(\sigma,\bm{\sigma})$ returns the number of times the
character $\sigma$ appears in text $\bm{\sigma}$. In general, we do not have
access to $p_{\scaleto{\Sigma^{*}}{4pt}}$ but rather only to samples from
$p_{\scaleto{\Sigma^{*}}{4pt}}$ with which we can represent an empirical
distribution $\widehat{p_{\scaleto{\Sigma^{*}}{4pt}}}$. Our formal analysis,
however, will consider $p_{\scaleto{\Sigma^{*}}{4pt}}$.

Let $\Delta$ be a second alphabet, which we call the tokenization alphabet. We
define a tokenization function $t:\Sigma^{*}\rightarrow D\subseteq\Delta^{*}$
as a function mapping texts in alphabet $\Sigma$ to sequences of tokens in
$D=t(\Sigma^{*})$, One popular choice in NLP is to have $\Sigma$ be a set of
Unicode characters and $\Delta$ be a set of _strings_ of Unicode characters.
In this case, the tokenization function $t$ segments the text $\bm{\sigma}$
into tokens corresponding to smaller chunks of text. There are many approaches
for devising different $t$’s; a brief overview of some of them is offered in
App. E.

Furthermore, for our purposes, it is useful to restrict tokenization functions
to those that are invertible (bijections), i.e., rules where we can undo the
tokenization. This way, the original text can be reconstructed and no
information is lost during tokenization.

######  Example 2.1.

Any injective tokenization function, i.e., mapping different inputs
$\bm{\delta}^{\prime},\bm{\delta}^{\prime\prime}$ to different outputs
$\bm{\sigma}^{\prime},\bm{\sigma}^{\prime\prime}$, satisfies our requirements.
As a counter example, consider a tokenization function $t_{1}$ for which
$t_{1}(\texttt{two{$\rule{5.0pt}{1.5pt}{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\\_}$}cows})=\langle\texttt{two},$
_$,\texttt{[UNK]}\rangle$ and
$t_{1}(\texttt{two{$\rule{5.0pt}{1.5pt}{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\\_}$}birds})=\langle\texttt{two},$
_$,\texttt{[UNK]}\rangle$. The $t_{1}$’s lack of injectivity prevents us from
recovering the original text from the token sequence $\langle\texttt{two},$
_$,\texttt{[UNK]}\rangle$.

Because of our restriction to invertible tokenization functions, with a change
of variable we can convert the distribution over texts in $\Sigma^{*}$ into
one over token sequences $\bm{\delta}$ in $D$ in a straightforward manner:
$p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})=p_{\scaleto{\Sigma^{*}}{4pt}}(t^{-1}(\bm{\delta}))$.
Note that the pushforward $p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})$ induces
a distribution over $\Delta^{*}$ but with support limited to $D$.

In applied NLP, there is currently no widely accepted notion of the intrinsic
quality of a tokenization function. Rather, practitioners are generally
interested in its _extrinsic_ performance, i.e., the performance of a model
trained on a corpus tokenized using a certain tokenization function. Under
such an evaluation, given two tokenization functions, the one that enables
better performance on the downstream task is taken to be better. However,
gauging the quality of a tokenizer function in this manner is computationally
expensive. Thus, we develop an information-theoretic intrinsic evaluation.

##  3 Communication in a Noiseless Channel

Our analysis of tokenization schemes relies on the following framing: Our
ultimate goal when tokenizing a text $\bm{\sigma}\sim
p_{\scaleto{\Sigma^{*}}{4pt}}$ is the transmission of this text across a
hypothetical channel. To perform this feat, we first tokenize $\bm{\sigma}$
into a sequence in $D\subseteq\Delta^{*}$. We then encode each token in
$\Delta$ as a sequence of symbols from the set $\\{1,\ldots,b\\}$, where $b$
is determined by the channel. Our goal is to analyze the properties of
tokenization schemes that lead to models with good downstream performance.

In the case of a noisy channel, we seek an encoding scheme that will help
ensure that $\bm{\sigma}$ is resilient to noise in addition to efficiently
encoding $\bm{\sigma}$. However, in the noiseless case, we _only_ care about
efficiency. We can assume that we are working with a noiseless channel
because, in the process of encoding data, no information is ever altered by a
stochastic process. In this case, one can equivalently think of noiseless
channel encoding as compression. Thus, our analysis proceeds by considering
the efficiency of different tokenization functions as if our goal is to use
them to communicate over a noiseless channel. To this end, we first discuss
the conditions for building such an encoding and then discuss the concept of
efficient channel usage.

######  Definition 3.1.

A token-level encoder ${\textsf{enc}_{\scaleto{\Delta}{4pt}}}$ is a function
${\textsf{enc}_{\scaleto{\Delta}{4pt}}}:\Delta\rightarrow\\{1,\ldots,b\\}^{*}$
that maps every token $\delta\in\Delta$ to a string of symbols in base $b$,
which we call a codeword. We can naturally lift the token-level encoder to a
sequence-level encoder using concatenation as
${\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\bm{\delta})=\bigoplus_{n=1}^{|\bm{\delta}|}{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta_{n})$.444Whitespace
information is not lost here because it is included in the tokens (see Example
2.1).

In order to be able to uniquely decode a string $\bm{\delta}$, we further
require that ${\textsf{enc}_{\scaleto{\Delta}{4pt}}}$ produces prefix-
free555Prefix-free means that no codeword is a prefix of any other codeword.
codes for all tokens in $\Delta$. As an example, Huffman encoding provides a
fast and nearly optimal (in a sense to be discussed in the subsequent section)
method to construct prefix-free codes (Huffman, 1952).

######  Example 3.2 (One-hot encoding).

Consider a tokenization alphabet $\Delta$. In NLP, when $b=2$, the most
straightforward way of encoding the $n^{\text{th}}$ element of $\Delta$ is a
vector of zeroes with length $|\Delta|$ with $1$ on position $n$.

######  Example 3.3 (Transmission).

We consider an arbitrary encoder ${\textsf{enc}_{\scaleto{{\Delta}}{4pt}}}$
over a given alphabet $\Delta$ and a channel with $b=2$. Now given a text and
some tokenization function
$t(\texttt{two{$\rule{5.0pt}{1.5pt}{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\\_}$}cows})$
$=\langle\texttt{two$\rule{5.0pt}{1.5pt}{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\\_}$},\texttt{cow},\texttt{s}\rangle$
we apply the encoder:
${\textsf{enc}_{\scaleto{{\Delta}}{4pt}}}(\texttt{two$\rule{5.0pt}{1.5pt}{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\\_}$})={\color[rgb]{.33,.545,.33}\definecolor[named]{pgfstrokecolor}{rgb}{.33,.545,.33}\texttt{1010101}}$
${\textsf{enc}_{\scaleto{{\Delta}}{4pt}}}(\texttt{cow})$
$={\color[rgb]{.21,.392,.545}\definecolor[named]{pgfstrokecolor}{rgb}{.21,.392,.545}\texttt{101111101}}$
and ${\textsf{enc}_{\scaleto{{\Delta}}{4pt}}}(\texttt{s})$
$={\color[rgb]{.545,.04,.312}\definecolor[named]{pgfstrokecolor}{rgb}{.545,.04,.312}\texttt{01010}}$
and for the whole sequence
${\textsf{enc}_{\scaleto{{\Delta}}{4pt}}}(t(\texttt{two{$\rule{5.0pt}{1.5pt}{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\\_}$}cows}))$
$={\color[rgb]{.33,.545,.33}\definecolor[named]{pgfstrokecolor}{rgb}{.33,.545,.33}\texttt{1010101}}{\color[rgb]{.21,.392,.545}\definecolor[named]{pgfstrokecolor}{rgb}{.21,.392,.545}\texttt{101111101}}{\color[rgb]{.545,.04,.312}\definecolor[named]{pgfstrokecolor}{rgb}{.545,.04,.312}\texttt{01010}}$.

For the remainder of the paper, we will not be interested in any specific
${\textsf{enc}_{\scaleto{\Delta}{4pt}}}$, but rather in an _optimal_ token-
level encoder that we can achieve, as measured by expected code length
measures.

######  Definition 3.4.

The expected code length $\mathcal{L}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}$
of a token-level encoder ${\textsf{enc}_{\scaleto{\Delta}{4pt}}}$ is defined
as

$\displaystyle\mathcal{L}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})=\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|$
(2)

A well-known result from information theory tells us that Eq. 2 is bounded by
the Shannon entropy of $\mathrm{W}_{\scaleto{\Delta}{4pt}}$, a $\Delta$-valued
random variable with law $p_{\scaleto{\Delta}{4pt}}$. To introduce the
theorem, we first define Shannon entropy.

######  Definition 3.5.

The Shannon entropy of $\mathrm{W}_{\scaleto{\Delta}{4pt}}$ is defined as

$\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}-\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)\log
p_{\scaleto{\Delta}{4pt}}(\delta)$ (3)

For channels using $b$ symbols for transmission, the logarithm is of base $b$.
Traditionally in information theory, ones takes $b=2$.

######  Theorem 3.6 (Shannon’s Source Coding Theorem).

Let $\mathrm{W}_{\scaleto{\Delta}{4pt}}$ be a $\Delta$-valued random variable
with law $p_{\scaleto{\Delta}{4pt}}$ and let
${\textsf{enc}_{\scaleto{\Delta}{4pt}}}$ be an encoder. Then,

$\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\leq\mathcal{L}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})$
(4)

with the optimal token-level encoder
${\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}$ satisfying

$\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta}{4pt}})\leq\left\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\right\rceil$
(5)

This theorem tells us that if we wish to communicate tokens from the alphabet
$\Delta$ through a noiseless channel, their minimum expected length for any
possible encoding is bounded by the Shannon entropy of the distribution
$p_{\scaleto{\Delta}{4pt}}$. An optimal token-level encoder will produce codes
with the expected length within those exact bounds. We can prove a very
similar result to Shannon’s source coding theorem (Shannon, 1948) that tells
us how well we can optimally encode a $\Delta^{*}$-valued source using only
the token-level encoder.

To this end, we first introduce the notions of expected sequence length and
average per-token encoding length, and then offer a lower-bound on the
compression achievable using only a token-level encoder. We additionally
define three random variables that will prove useful in our analysis; all of
them are pushforwards of $p_{\scaleto{\Delta^{*}}{4pt}}$.

Let $L$ be a random variable whose values range over strings’ lengths, i.e.,
$L(\bm{\delta})=|\bm{\delta}|$. The expected token sequence length
$\mathbb{E}[L]$ for sequences sampled according to
$p_{\scaleto{\Delta^{*}}{4pt}}$ is then

$\displaystyle\mathbb{E}[L]=\sum_{\bm{\delta}\in\Delta^{*}}p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})|\bm{\delta}|$
(6)

where for notational simplicity, we leave the dependence of this expectation
on $p_{\scaleto{\Delta^{*}}{4pt}}$ implicit as it will always be clear from
context. Let
$X_{\delta}(\bm{\delta})=\frac{\mathrm{count}(\delta,\bm{\delta})}{|\bm{\delta}|}$
be the unigram random variable, i.e., a function that returns the proportion
of $\bm{\delta}$ that consists of a particular $\delta$. Finally, define the
random variable
$\overline{L}_{{\textsf{enc}_{\scaleto{\Delta}{4pt}}}}(\bm{\delta})=\sum_{\delta\in\Delta}X_{\delta}(\bm{\delta})|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|$.

We now turn to our first major theorem.

######  Theorem 3.7.

Let $p_{\scaleto{\Delta^{*}}{4pt}}$ be a distribution over $\Delta^{*}$, and
let $p_{\scaleto{\Delta}{4pt}}$ be the unigram distribution induced by
$p_{\scaleto{\Delta^{*}}{4pt}}$ (Eq. 1). Then, for an optimal token-level
encoder
${\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}:\Delta\rightarrow\\{1,\ldots,b\\}^{*}$
lifted to the sequence level, the following lower and upper bounds hold:666Be
careful not to confuse ${\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}$, an
optimal token-level encoder (here lifted to the sequence level), with
${\textsf{enc}_{\scaleto{\Delta^{*}}{4pt}}}$, an arbitrary sequence-level
encoder, which we usually denote enc when clear from context.

$\displaystyle\begin{aligned}
\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})&\leq\frac{\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})-\mathrm{Cov}(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L)}{\mathbb{E}[L]}\\\
&\leq\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil\end{aligned}$
(7)

###### Proof.

The proof is given in App. C. ∎

In the special case of Shannon entropy, we additionally arrive at the
following stronger inequality:

$\mathcal{L}_{{\textsf{enc}}^{\star}}(p_{\scaleto{\Delta^{*}}{4pt}})\leq\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})$
(8)

This holds because ${\textsf{enc}}^{\star}$ is _not_ constrained to token-
level codes and the unconstrained minimum over all codes is naturally lower
than the constrained version. As a concrete example, even if two
$\delta^{\prime},\delta^{\prime\prime}\in\Delta$ _always_ appear together in
practice, ${\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}$ must assign both
$\delta^{\prime}$ and $\delta^{\prime\prime}$ their own unique code. Such a
constraint does not apply to ${\textsf{enc}}^{\star}$. We foreshadow that this
inequality does _not_ generalize to Rényi entropy, as discussed in § 4.

Theorem 3.7 tells us that the expected code length of a sequence-level
encoder, based on a token-level encoder, is proportional to the expected code
length of the unigram distribution up to an additive covariance factor. This
allows us to determine both a lower-bound for the expected code length of such
an encoder and an upper-bound for the expected code length of a sequence-level
encoder based on an optimal token-level encoder.

We are now in the position to return to the main objective of this paper:
Assessing the quality of different tokenizers. One natural way of comparing
tokenizers would be to compare properties of the distributions over tokens
that they each induce. At first glance, Shannon entropy looks like the most
obvious candidate for such a property. However, for distributions over
$\Delta$ of different sizes, it is not directly comparable. The efficiency of
a tokenization function addresses this issue.

######  Definition 3.8.

Let $p_{\scaleto{\Sigma^{*}}{4pt}}$ be a distribution over $\Sigma^{*}$, let
$t:\Sigma^{*}\rightarrow\Delta^{*}$ be a tokenization function, and let
$p_{\scaleto{\Delta^{*}}{4pt}}$ be the distribution over $\Delta^{*}$ induced
by $t$. The efficiency of $t$ is defined as

${\textsf{eff}}(p_{\scaleto{\Sigma^{*}}{4pt}},t)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\frac{\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$
(9)

where ${\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}$ is an optimal token-
level encoder and ${\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}$
a uniform encoder that assigns all tokens in $\Delta$ codes of equal length:
$\lceil\log|\Delta|\rceil$.

######  Theorem 3.9.

The efficiency of $t$ is upper-bounded by

$\frac{\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\frac{\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathbb{E}[L]}}{\log|\Delta|}\geq{\textsf{eff}}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$
(10)

and lower-bounded by

$\frac{\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})+\frac{\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathbb{E}[L]}}{\lceil\log|\Delta|\rceil}\leq{\textsf{eff}}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$
(11)

where $\mathrm{W}_{\scaleto{\Delta}{4pt}}$ is a $\Delta$-valued random
variable with law $p_{\scaleto{\Delta}{4pt}}$, the unigram distribution
induced by $t$.

###### Proof.

The proof is given in App. C. ∎

Note that the upper bound given in Eq. 10 tells us how efficient the _best_
code could be, which is the more interesting bound for our purposes.
Additionally, we note that, by introducing a normalization factor, efficiency
provides a better solution than directly comparing distributions’ entropies.
We illustrate this in the following example.

######  Example 3.10.

Consider a tokenization function $t_{1}$ with tokenization alphabet
$\Delta_{1}$ where $|\Delta_{1}|=6$. We then introduce a second tokenization
function $t_{2}$ with a tokenization alphabet $\Delta_{2}$ defined to be
$\Delta_{1}$ plus an additional $6$ tokens that occur very infrequently. The
difference between these two distributions is illustrated in Fig. 1. If, for
example, we relied solely on the Shannon entropy, which is higher for more
uniformly spread-out distributions, we would judge the second distribution to
be better ($2.50<3.08$). However, the efficiency tells the opposite story
($0.97\%>0.86\%$).

As Example 3.10 suggests, the measure provided by efficiency is in line with
the idea of a more balanced distribution over $\Delta^{*}$. Informally, we do
not want a tokenizer that induces a distribution with very low entropy, as
this is indicative of an unbalanced distribution. The efficiency eff provides
us with a notion of this imbalance. To relate efficiency back to our metaphor
of the noiseless channel, we note that the quantity
$1-{\textsf{eff}}(p_{\scaleto{\Delta^{*}}{4pt}},t)$ is known as relative
redundancy and corresponds to the maximum data compression ratio (in
percentage of how much can data size be reduced) that can be achieved.

##  4 Rényi Efficiency

Definition 3.8, the standard definition of efficiency, is based on Shannon
entropy. Upon closer inspection, we see it linearly penalizes the use of long
codes. To see why, consider a case where the distribution changes such that
the entropy increases by one. Then, the upper-bound for the expected code
length provided by an optimal encoder also increases by one. However, in some
cases, we may wish to assign a non-linear cost to code length, e.g., there may
be a non-linearly higher cost for decoding longer codes. In the context of
choosing the vocabulary for a model, this corresponds to our desire to avoid
inducing tokens that occur very infrequently because there may not be enough
examples of them in the training data for the model to learn. To add an
additional degree of freedom to accommodate such preferences Campbell (1965)
generalizes the measure of expected code length to discounted expected code
length for a hyperparameter $s$ as follows:777Our notation differs slightly
from Campbell (1965).

$\mathcal{L}^{(s)}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\lim_{s^{\prime}\rightarrow
s}\frac{\log\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s^{\prime}|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|}\right)}{s^{\prime}}$
(12)

By L’Hôpital’s rule, we can show that

$\mathcal{L}^{(0)}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})=\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|$
(13)

and, additionally, that

$\mathcal{L}^{(\infty)}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})=\max_{\delta\in\Delta}|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|$
(14)

Beyond the limiting cases, for $s\in(-1,\infty)\setminus\\{0\\}$, we further
note that
$\mathcal{L}^{(s)}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})$
is a monotonically increasing function of $s$. The larger our value of $s$,
the more disproportionately
$\mathcal{L}^{(s)}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})$
increases as a function of the _longest_ codeword, which often corresponds to
the encoding of a low-frequency character in a good code because high-
frequency tokens are assigned the shorter codes in order to minimize the
expected code length. For large enough $s$, this has the effect of encouraging
all codewords to be roughly of equal length. Campbell (1965) sought an
analogue of Shannon’s coding theorem for
$\mathcal{L}^{(s)}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})$
where $s\neq 0$. As it turns out, there is a deep connection with the Rényi
entropy.

Figure 1: Examples of unigram distributions with efficient and inefficient
channel usage.

######  Definition 4.1.

The Rényi entropy of order $\alpha>0$ is defined as

$\mathrm{H}_{\alpha}(p_{\scaleto{\Delta}{4pt}})=\\!\lim_{\alpha^{\prime}\rightarrow\alpha}\frac{1}{1-\alpha^{\prime}}\log\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha^{\prime}}\right)$
(15)

Prima facie, Rényi entropy bears some semblance to
$\mathcal{L}^{(s)}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})$.
To see this, consider the limiting cases. At $\alpha=0$, we have

$\mathrm{H}_{0}(p_{\scaleto{\Delta}{4pt}})=\log|\Delta|$ (16)

And, at $\alpha=\infty$, we have

$\mathrm{H}_{\infty}(p_{\scaleto{\Delta}{4pt}})=\max_{\delta\in\Delta}-\log
p_{\scaleto{\Delta}{4pt}}(\delta)$ (17)

Finally, we have $\mathrm{H}_{1}(p)=\mathrm{H}(p)$, i.e., $\alpha=1$
corresponds to Shannon entropy, another result which can be shown by
L’Hôpital’s rule. These examples suggest the correspondence
$\alpha=(1+s)^{-1}$, which fits the three cases considered, e.g., note that
$\alpha=0$ when $s\rightarrow\infty$. Moreover, this is exactly the intuition
we argued for above: When $\alpha=0$, we encode tokens with codewords of the
same length which follows from minimizing the length of the longest codeword.
On the other hand, when $s=-1$, we encourage shorter codes for high-
probability tokens. This case corresponds to $\alpha=\infty$. We now prove
that, similarly to how $\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})$
provides bounds for
$\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})$
in Theorem 3.7, $\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})$
provides bounds for
$\mathcal{L}^{(s)}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})$,
where ${\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}$ is an encoder optimal with
respect to a given $s=\alpha^{-1}+1$. We term such an encoder $s$-optimal.

######  Theorem 4.2 (Generalization of Campbell (1965)).

Let $\mathrm{H}_{\alpha}$ be the Rényi entropy of order $\alpha$ and let
$\mathcal{L}^{(s)}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta}{4pt}})$
(Eq. 12) be the discounted expected code length for the encoder
${\textsf{enc}_{\scaleto{\Delta}{4pt}}}$, where $s=\alpha^{-1}-1$. Moreover,
let $\mathrm{W}_{\scaleto{\Delta}{4pt}}$ be a $\Delta$-valued random variable
with law $p_{\scaleto{\Delta}{4pt}}$. Then for an $s$-optimal token-level
encoder ${\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}$, the following bound
holds on the discounted expected code length:

$\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\leq\mathcal{L}^{(s)}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta}{4pt}})\leq\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil$
(18)

###### Proof.

Proof in App. C. ∎

Note that we have further generalized Campbell’s (1965) result by allowing
some negative values for $s$, namely, $s>-1$. As a result, we can induce
additional non-linear weight on too _short_ codes as opposed to only _long_
codes.

Now we generalize the efficiency with respect to Shannon entropy to Rényi
entropy. Let ${\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}$ be an $s$-optimal
token-level encoder over token alphabet $\Delta$. Note that several terms from
our prior notation can now be expressed in terms of
${\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}$, i.e.,
${\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}={\textsf{enc}^{0}_{\scaleto{\Delta}{4pt}}}$
and
${\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}={\textsf{enc}^{\infty}_{\scaleto{\Delta}{4pt}}}$.

######  Theorem 4.3.

Let $\alpha=(1+s)^{-1}$ and $p_{\scaleto{\Delta^{*}}{4pt}}$ be a distribution
over $\Delta^{*}$, and let $p_{\scaleto{\Delta}{4pt}}$ be the unigram
distribution induced by $p_{\scaleto{\Delta^{*}}{4pt}}$ (Eq. 1). Then, the
following inequality holds

$\displaystyle\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil$
$\displaystyle\geq\frac{\mathcal{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})-\mathrm{Cov}(\overline{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}},L)}{\mathbb{E}[L]}$
(19)

for an $s$-optimal sequence-level encoder
${\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}$ based on token-level encoder
${\textsf{enc}_{\scaleto{\Delta}{4pt}}}:\Delta\rightarrow\\{1,\ldots,b\\}^{*}$
.

###### Proof.

Proof in App. C. ∎

######  Definition 4.4.

Let $p_{\scaleto{\Sigma^{*}}{4pt}}$ be a distribution over $\Sigma^{*}$, let
$t:\Sigma^{*}\rightarrow\Delta^{*}$ be a tokenization function, and let
$p_{\scaleto{\Delta^{*}}{4pt}}$ be the distribution over $\Delta^{*}$ induced
by $t$. The Rényi efficiency of $t$ at $\alpha$ is defined as

$\displaystyle{\textsf{eff}}_{\alpha}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$
$\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\frac{\mathcal{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}{\mathcal{L}_{{\textsf{enc}^{\infty}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$
(20a)
$\displaystyle=\frac{\mathcal{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$
(20b)

where $s=\alpha^{-1}-1$.

The Rényi efficiency can be easily upper-bounded in a similar manner to the
Shannon efficiency.

######  Theorem 4.5.

Let $p_{\scaleto{\Sigma^{*}}{4pt}}$ be a distribution over $\Sigma^{*}$, let
$t:\Sigma^{*}\rightarrow\Delta^{*}$ be a tokenization function, and let
$p_{\scaleto{\Delta^{*}}{4pt}}$ be the distribution over $\Delta^{*}$ induced
by $t$. Then, for an $s$-optimal token-level encoder
${\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}$ lifted to the sequence-level, the
Rényi efficiency of $t$ at $\alpha$ is upper-bounded by

$\frac{\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\frac{\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}},\,L\right)}{\mathbb{E}[L]}}{\log|\Delta|}\geq{\textsf{eff}}_{\alpha}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$
(21)

where $\mathrm{W}_{\scaleto{\Delta}{4pt}}$ is a $\Delta$-valued random
variable with law $p_{\scaleto{\Delta}{4pt}}$, the unigram distribution
induced by $t$.

###### Proof.

Proof in App. C. ∎

To provide more intuition of why the non-linear penalization in Rényi
efficiency makes for a good measure of distribution balance, we offer a worked
example in Example E.1.

Figure 2: Efficiency of sequence length and $\mathrm{H}_{2.5}/\mathrm{H}_{0}$
as predictors of MT performance (average of 5 runs). Bands show 95% $t$-test
confidence intervals for regression lines.

##  5 The Compression Principle

In previous sections, we discussed how different tokenizers lead to token
distributions of varying properties. Now, we add the last piece necessary to
link the downstream performance of a system with the choice of a tokenizer.

######  Hypothesis 5.1 (Compression Principle).

Let $p_{\scaleto{\Sigma^{*}}{4pt}}$ be a distribution over texts with
characters from alphabet $\Sigma$ and $t$ be a tokenization function from
$\Sigma^{*}$ to $\Delta^{*}$ for some token alphabet $\Delta$. Let
$p_{\scaleto{\Delta}{4pt}}$ be the $\Delta$-unigram distribution induced by
$t$. Finally, let $\textsc{Performance}_{M}(t)$ be some measure of performance
of a system $M$ which uses tokenization $t$. Then, for some $\alpha$ dependent
on $M$, ${\textsf{eff}}_{\alpha}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$ is a good
predictor of $\textsc{Performance}_{M}(t)$.

In words, we hypothesize that the efficiency of the tokenization function $t$
is highly correlated with the downstream performance. We will verify this
claim experimentally in § 6.

#### Rényi Entropy $\alpha$.

The choice of $\alpha$ for $\mathrm{H}_{\alpha}$ determines the extent to
which longer codewords are penalized. On one hand, if we observe that Rényi
efficiency with low $\alpha$ correlates the best with performance, we can
conclude that longer codewords and, hence, very low-frequency tokens hurt
performance. On the other hand, if we observe that Rényi efficiency with high
$\alpha$, we can conclude that shorter codewords and, hence, very high-
frequency tokens hurt performance. Note that most downstream NLP applications
do not explicitly use codewords (all token representations are the same size),
but long codewords are still a natural way to think about low- and high-
frequency tokens.

#### Learnability.

The most intuitive explanation for why some tokenization functions enable good
downstream results and some worse is that having many low-frequent tokens will
prevent the model from learning their distributional properties. This
hypothesis can be related back to the sample complexity of the learning
algorithm, i.e., the number of training samples needed by the model in the
given setting to learn the function of interest. If we accept that part of the
MT task is learning the meaning of all individual vocabulary tokens, then
sample complexity could (at least partially) be expressed in terms of the
number of instances of each token. This argument is made by Gowda and May
(2020), who are concerned with what proportion of $\delta\in\Delta$ appears at
least 100 times in the corpus for the downstream task at hand.

Nevertheless, we will see shortly that the best predictor with Rényi
efficiency is for $\alpha>1$, meaning that higher weight is given to codewords
for more frequent tokens. We therefore hypothesize, that very high-frequency
tokens have the most impact in downstream performance.

##  6 Experiments

We now seek empirical evidence for Hyp. 5.1. We focus on MT, where a standard
automatic evaluation metric is Bleu (Papineni et al., 2002). We use the
English$\rightarrow$German CommonCrawl dataset in all experiments. The
specifics of the MT system, data and evaluation are described in App. D. We
consider two different experimental manipulations. First, we experiment with
various modifications of the popular byte-pair encoding (BPE) tokenizer
(Sennrich et al., 2016) to control its compression rate. The details are
discussed in § 6.1. Second, we experiment with a variety of tokenization
schemes: Unigram (Kudo, 2018), WordPiece (Devlin et al., 2019),
Lempel–Ziv–Welch (Ziv and Lempel, 1977; Welch, 1984) and Morfessor (Creutz and
Lagus, 2007; Virpioja et al., 2013; Smit et al., 2014). The details are
discussed in § 6.2.

Note that throughout our experiments, we make the simplifying assumption of
$\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}},L\right)=0$.
It simplifies the upper bound of
${\textsf{eff}}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$ (from Theorem 3.9) to
$\frac{\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil}{\log|\Delta|}$
and the upper bound of
${\textsf{eff}}_{\alpha}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$ (from Theorem 4.5)
to
$\frac{\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil}{\log|\Delta|}$.
From our preliminary results,
$\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}},L\right)$
is negative and small. We leave its more accurate approximation, which
requires a Rényi analogue of Huffman coding as in Jelinek (1968), to future
work.

###  6.1 Experiment 1

In our first experiment, we analyze how predictive various quantitative
attributes of a tokenization scheme are of downstream model performance. We
consider BPE with 5 different vocabulary sizes: 2k, 4k, 8k, 16k, and 32k. For
each vocabulary size, we create multiple tokenization schemes with varying
compression rates. As discussed in § E.1, BPE produces a vocabulary through a
greedy compression algorithm. However, in order to achieve a variety of
different compression rates, we inject random noise into the algorithm.888The
empirical effects of choosing BPE merge operations uniformly at random is
studied by Sälevä and Lignos (2023). We achieve this by sampling from a
Boltzmann distribution over the pair frequencies with temperature parameter
$\tau$; see § E.1 for details.999Note that the stochasticity in our case is
introduced during training and not during inference, as in the popular BPE-
dropout method (Provilkov et al., 2020). We then treat each vocabulary
size–temperature pair as a single data point in our analysis.

Our main quantitative attribute of interest, i.e., predictor, is Rényi
efficiency. Aside from Rényi efficiency, we further consider Shannon and Rényi
entropies, Shannon efficiency, and average tokenized sequence length. Further,
one popular heuristics for choosing the vocabulary size is given and justified
by Gowda and May (2020). It can be summarized as: “Use the highest possible
vocabulary size such that 95% of [tokens] occur at least 100 times in the
data.” While the constants seem arbitrary, this rule of thumb works well in
practice (Gowda et al., 2022; Dramko et al., 2022; Kumar and Thawani, 2022).
Nevertheless, it is stated in an algorithmic manner and not as a predictor of
performance or learnability. We attempt to turn it into a regressive predictor
so as to make it more comparable with the other quantities studied. Given
$p_{\scaleto{\Delta}{4pt}}$, let $f_{n}(p_{\scaleto{\Delta}{4pt}})$ symbolize
the frequency of the $n^{\text{th}}$ percentile. We then define the quantity
$F_{\gamma_{1},\gamma_{2}}(p_{\scaleto{\Delta}{4pt}})=\sum_{\gamma_{1}\leq
n\leq\gamma_{2}}f_{n}(p_{\scaleto{\Delta}{4pt}})$, which in words, is the sum
of token frequencies from the $\gamma_{1}^{\text{th}}$ to
$\gamma_{2}^{\text{th}}$ percentile. The original work suggests examining the
frequency of the 95${}^{\text{th}}$ percentile, i.e.,
$\gamma_{1}=\gamma_{2}=0.95$. In contrast, we add an additional degree of
freedom as we do not inspect a single percentile frequency but rather a sum
across an interval. Later, we scan the whole space for $\gamma_{1}$ and
$\gamma_{2}$ and show that there are better choices that lead to much higher
correlations.

Predictor | Pearson | Spearman | ${\bm{\rho^{2}}}$
---|---|---|---
Sequence len. | $-0.32\,{\scriptstyle(=0.118)}$ | $-0.24\,{\scriptstyle(=0.239)}$ | 10%
Percentile freq. |  $0.76$ ${\scriptstyle(<0.001)}$ | ${0.63}\,{\scriptstyle(<0.001)}$ | 58%
Entropy | $0.22\,{\scriptstyle(=0.281)}$ | $0.12\,{\scriptstyle(=0.578)}$ | 5%
Entropy eff. | $0.56\,{\scriptstyle(=0.004)}$ | $0.38\,{\scriptstyle(=0.006)}$ | 31%
Rényi entropy | $0.49\,{\scriptstyle(=0.001)}$ | $0.38\,{\scriptstyle(=0.006)}$ | 24%
Rényi eff. |  $0.78$ ${\scriptstyle(<0.001)}$ | ${0.66}\,{\scriptstyle(<0.001)}$ | 61%

Table 1: Correlations between different predictors and MT performance (Bleu).
The $p$-values for each statistic (computed using a $t$-test) are in
parentheses.

We use Pearson and Spearman correlations with downstream model performance
(measured with Bleu) as our metrics of predictor quality. Recall that Pearson
correlation tells us the strength of a _linear_ relationship between two
variables. On the other hand, Spearman correlation quantifies the strength of
a linear relationship of the _ranking_.

Figure 3: Correlation of Rényi efficieny
($\mathrm{H}_{\alpha}/\mathrm{H}_{0}$) with Bleu on train data in the
experiment 1. Maximums of Pearson and Spearman correlations are marked with
$\star$.

#### Results.

In order to select $\alpha$ (for ${\textsf{eff}}_{\alpha}$) as well as
$\gamma_{1}$ and $\gamma_{2}$ ( for $F_{\gamma_{1},\gamma_{2}}$), we use half
of the data to perform a grid-search, selecting the hyperparameters that lead
to the highest Pearson correlation. We show the results of this grid search
for $\mathrm{H}_{\alpha}/\mathrm{H}_{0}$ in Fig. 3 ($\alpha^{*}\doteq 2.5$)
and for $F_{\gamma_{1},\gamma_{2}}$ in Fig. 4 ($\gamma_{1}^{*}\doteq
0.03,\gamma_{2}^{*}\doteq 0.83$). Unless otherwise stated, we use these values
in subsequent experiments. We show the relationship between Bleu, sequence
length and Rényi efficiency as approximated by the lower bound (Theorem 4.5)
in Fig. 2. A comprehensive comparison for all predictors is shown in Tab. 1.
The visualization of the other predictors is in Fig. 6. From these analyses,
we can see that the Rényi efficiency provides a significantly better
explanation for downstream model performance than any of our other predictors.

When examining which $\alpha$ leads to the highest absolute correlation with
Bleu, we can conclude that tokenization schemes that result in fewer very
high-frequency tokens are the best for downstream performance. This is evinced
by both the relatively high value of $\alpha$ that leads to the best
correlation with performance (Fig. 3, $\alpha^{*}\doteq 2.5$) and by Fig. 4,
which shows that frequencies in the top percentile correlate _negatively_ with
performance. Importantly, this finding does not contradict Gowda and May’s
(2020) rule of thumb, which focuses on _low_ frequency tokens. While very high
and very low frequencies produced by a tokenization scheme are not
independent, a tokenization scheme may feasibly produce both, neither or only
one.

Furthermore, the Pearson correlation between the efficiency
($\mathrm{H}_{2.5}/\mathrm{H}_{0}$) and percentile frequency ($F_{0.03,0.83}$)
is $0.96$, which suggests that both predictors are capturing the same
underlying effect.

###  6.2 Experiment 2

Figure 4: Results for grid search over the best hyperparameters for percentile
frequency predictor to maximize the absolute Pearson correlation. The highest
is for $3^{\text{rd}}$ to $83^{\text{th}}$ percentile with $\rho=0.81$.

In this experiment, we evaluate whether there exist aspects of a tokenization
scheme that influence Bleu _beyond_ the Rényi efficiency. Following results in
Experiment 1, we focus on Rényi efficiency at $\alpha=2.5$. In contrast to the
first experiment, we consider different tokenization schemes (BPE, Unigram,
WordPiece, LZW, Morfessor). We manipulate their efficiency by lowering the
amount of tokenizer training data (2k, 8k, 100k parallel lines) together with
varying vocabulary sizes of 4k, 8k, and 16k tokens. We then treat each
tokenization-scheme–training-data-size–vocabulary-size triple as a single data
point in this analysis. We compare three different linear models (Gelman and
Hill, 2006), where Bleu is always the dependent variable: (i) with the
tokenization scheme as a random effect, (ii) with Rényi efficiency as a fixed
effect, and (iii) with both. Importantly, we treat tokenization scheme as a
random effect because the set of tokenization algorithms that we consider does
not encompass all possible methods, i.e., only a sample of all possible
algorithms are observed.

To compare the ability of these different models to predict Bleu, we look at
the average change in log-likelihood of held-out data points under a given
model with respect to a baseline model: A model trained with only an intercept
term. A larger value of $\Delta$ log-likelihood indicates that the data point
is more probable under the comparison model, i.e., the comparison model more
closely fits the observed data. We use 10-fold cross-validation to estimate
these differences: Our data is split randomly into 10 folds, where 9 of the
folds are used to learn model coefficients and the 10${}^{\text{th}}$ fold is
held back for evaluation. The same process is performed until we have a
$\Delta$ log-likelihood value for each data point.

#### Results.

In Fig. 5, we see that Rényi efficiency is a stronger predictor of MT
performance than the tokenization scheme alone. Interestingly though, the
predictive power of these two predictors seems to be orthogonal, as evinced by
the mean $\Delta$ log-likelihood of a model with both predictors. This finding
suggests that there are additional qualities of a good tokenization scheme
that Rényi efficiency alone cannot capture. We leave the investigation of such
qualities to future work.

Figure 5: Mean change in log-likelihood on held-out data under linear models
using different predictors. Bars indicate 95% confidence interval around the
mean.

##  7 Conclusion

Our paper presents a new information-theoretic approach to characterizing a
good tokenization scheme. We contend that the Rényi efficiency of the unigram
distribution that a tokenization scheme produces is a principled measure of
the tokenization quality. To test this claim, we evaluate a large set of
tokenization schemes, with varying vocabulary sizes and produced by different
tokenization schemes. We observe how the Rényi efficiency of these different
tokenizations relates to the performance of a downstream MT model. We find
that, for an appropriate choice of the parameter $\alpha$, this new metric has
a very strong Pearson correlation with Bleu: $0.78$ in comparison to just
$-0.32$ for baseline sequence length. From a theoretical perspective, this
property can be connected to a penalization of token distributions that are
too unbalanced, having, in particular, very high-frequency tokens. This
finding is in line with the more general principle that compression is
connected with learnability. Our framework also has practical benefits as it
allows for an intrinsic evaluation of tokenization functions.

## Limitations

It is possible that there is a hidden effect caused by the language pair
direction, model selection, or training data and its size. However, our
results bear high statistical significance for cases where we desire high
correlation and low statistical significance where we expect low correlation.
Assured by this and concerned by the large cost of training a large number of
MT systems, we did not experiment with larger data or other language
directions apart from limited additional experiments in Tab. 2.

## Acknowledgements

We would like to acknowledge Eleanor Chodroff and Shayne Sloggett for
extensive discussion about the experimental design in Experiment 2. Clara
Meister was supported by the Google PhD Fellowship. Juan Luis Gastaldi has
received funding from the European Union’s Horizon 2020 research and
innovation programme under grant agreement No 839730.

## References

  * Aczél and Beckenbach (1980) J. Aczél and E. F. Beckenbach. 1980.  _On Hölder’s Inequality_, pages 145–150. Birkhäuser Basel, Basel.
  * Ataman and Federico (2018) Duygu Ataman and Marcello Federico. 2018.  An evaluation of two vocabulary reduction methods for neural machine translation.  In _Proceedings of the 13th Conference of the Association for Machine Translation in the Americas (Volume 1: Research Track)_ , pages 97–110.
  * Campbell (1965) L. L. Campbell. 1965.  A coding theorem and Rényi’s entropy.  _Information and Control_ , 8(4):423–429.
  * Chitnis and DeNero (2015) Rohan Chitnis and John DeNero. 2015.  Variable-length word encodings for neural translation models.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 2088–2093.
  * Costa-jussà and Fonollosa (2016) Marta R. Costa-jussà and José A. R. Fonollosa. 2016.  Character-based neural machine translation.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 357–361.
  * Creutz and Lagus (2007) Mathias Creutz and Krista Lagus. 2007.  Unsupervised models for morpheme segmentation and morphology learning.  _ACM Transactions on Speech and Language Processing (TSLP)_ , 4(1):1–34.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dramko et al. (2022) Luke Dramko, Jeremy Lacomis, Pengcheng Yin, Edward J. Schwartz, Miltiadis Allamanis, Graham Neubig, Bogdan Vasilescu, and Claire Le Goues. 2022.  DIRE and its data: Neural decompiled variable renamings with respect to software class.  _ACM Transactions on Software Engineering and Methodology_.
  * El-Kishky et al. (2020) Ahmed El-Kishky, Vishrav Chaudhary, Francisco Guzmán, and Philipp Koehn. 2020\.  CCAligned: A massive collection of cross-lingual web-document pairs.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5960–5969.
  * Gage (1994) Philip Gage. 1994.  A new algorithm for data compression.  _The C Users Journal archive_ , 12:23–38.
  * Gallé (2019) Matthias Gallé. 2019.  Investigating the effectiveness of BPE: The power of shorter sequences.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1375–1381, Hong Kong, China.
  * Gelman and Hill (2006) Andrew Gelman and Jennifer Hill. 2006.  _Data Analysis Using Regression and Multilevel/Hierarchical Models_.  Analytical Methods for Social Research. Cambridge University Press, Cambridge.
  * Gowda et al. (2022) Thamme Gowda, Mozhdeh Gheini, and Jonathan May. 2022.  Checks and strategies for enabling code-switched machine translation.  _arXiv preprint arXiv:2210.05096_.
  * Gowda and May (2020) Thamme Gowda and Jonathan May. 2020.  Finding the optimal vocabulary size for neural machine translation.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 3955–3964.
  * Hardy et al. (1934) G. H. Hardy, John E. Littlewood, and George Pólya. 1934.  _Inequalities_.  Cambridge University Press, Cambridge.
  * Huffman (1952) David A. Huffman. 1952.  A method for the construction of minimum-redundancy codes.  _Proceedings of the IRE_ , 40(9):1098–1101.
  * Jean et al. (2015) Sébastien Jean, Kyunghyun Cho, Roland Memisevic, and Yoshua Bengio. 2015.  On using very large target vocabulary for neural machine translation.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1–10.
  * Jelinek (1968) F. Jelinek. 1968.  Buffer overflow in variable length coding of fixed rate sources.  _IEEE Transactions on Information Theory_ , 14(3):490–501.
  * Kraft (1949) Leon Gordon Kraft. 1949.  _A device for quantizing, grouping, and coding amplitude-modulated pulses_.  Ph.D. thesis, Massachusetts Institute of Technology.
  * Kudo (2018) Taku Kudo. 2018.  Subword regularization: Improving neural network translation models with multiple subword candidates.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 66–75.
  * Kumar and Thawani (2022) Dipesh Kumar and Avijit Thawani. 2022.  BPE beyond word boundary: How NOT to use multi word expressions in neural machine translation.  In _Proceedings of the Third Workshop on Insights from Negative Results in NLP_ , pages 172–179.
  * L’Hostis et al. (2016) Gurvan L’Hostis, David Grangier, and Michael Auli. 2016.  Vocabulary selection strategies for neural machine translation.  _arXiv preprint arXiv:1610.00072_.
  * Ling et al. (2015) Wang Ling, Isabel Trancoso, Chris Dyer, and Alan W Black. 2015.  Character-based neural machine translation.  _arXiv preprint arXiv:1511.04586_.
  * Mermer (2010) Coşkun Mermer. 2010.  Unsupervised search for the optimal segmentation for statistical machine translation.  In _Proceedings of the ACL 2010 Student Research Workshop_ , pages 31–36.
  * Mi et al. (2016) Haitao Mi, Zhiguo Wang, and Abe Ittycheriah. 2016.  Vocabulary manipulation for neural machine translation.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 124–129.
  * Mielke et al. (2021) Sabrina J. Mielke, Zaid Alyafeai, Elizabeth Salesky, Colin Raffel, Manan Dey, Matthias Gallé, Arun Raja, Chenglei Si, Wilson Y. Lee, Benoît Sagot, and Samson Tan. 2021.  Between words and characters: A brief history of open-vocabulary modeling and tokenization in NLP.  _arXiv preprint arXiv:2112.10508_.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)_ , pages 48–53, Minneapolis, Minnesota.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  BLEU: A method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pages 311–318.
  * Popović (2015) Maja Popović. 2015.  chrF: character $n$-gram F-score for automatic MT evaluation.  In _Proceedings of the tenth workshop on statistical machine translation_ , pages 392–395.
  * Post (2018) Matt Post. 2018.  A call for clarity in reporting BLEU scores.  In _Proceedings of the Third Conference on Machine Translation: Research Papers_ , pages 186–191, Brussels, Belgium. Association for Computational Linguistics.
  * Provilkov et al. (2020) Ivan Provilkov, Dmitrii Emelianenko, and Elena Voita. 2020.  BPE-dropout: Simple and effective subword regularization.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1882–1892.
  * Rei et al. (2020) Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie. 2020.  COMET: A neural framework for MT evaluation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2685–2702.
  * Rényi (1961) Alfréd Rényi. 1961.  On measures of entropy and information.  In _Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics_ , volume 4, pages 547–562. University of California Press.
  * Sälevä and Lignos (2023) Jonne Sälevä and Constantine Lignos. 2023.  What changes when you randomly choose BPE merge operations? Not much. In _The Fourth Workshop on Insights from Negative Results in NLP_ , pages 59–66, Dubrovnik, Croatia. Association for Computational Linguistics.
  * Sellam et al. (2020) Thibault Sellam, Dipanjan Das, and Ankur Parikh. 2020.  BLEURT: Learning robust metrics for text generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7881–7892.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725.
  * Shannon (1948) Claude E. Shannon. 1948.  A mathematical theory of communication.  _The Bell System Technical Journal_ , 27(3):379–423.
  * Smit et al. (2014) Peter Smit, Sami Virpioja, Stig-Arne Grönroos, Mikko Kurimo, et al. 2014.  Morfessor 2.0: Toolkit for statistical morphological segmentation.  In _The 14th Conference of the European Chapter of the Association for Computational Linguistics (EACL), Gothenburg, Sweden, April 26-30, 2014_. Aalto University.
  * Virpioja et al. (2013) Sami Virpioja, Peter Smit, Stig-Arne Grönroos, and Mikko Kurimo. 2013.  Morfessor 2.0: Python implementation and extensions for Morfessor baseline.  Technical report, Aalto University.
  * Welch (1984) Terry A. Welch. 1984.  A technique for high-performance data compression.  _Computer_ , 17(06):8–19.
  * Ziv and Lempel (1977) Jacob Ziv and Abraham Lempel. 1977.  A universal algorithm for sequential data compression.  _IEEE Transactions on Information Theory_ , 23(3):337–343.
  * Zouhar et al. (2023) Vilém Zouhar, Clara Meister, Juan Luis Gastaldi, Li Sachan, Du, Tim Vieira, Mrinmaya, and Ryan Cotterell. 2023.  A formal perspective on byte-pair encoding.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Findings)_.

##  Appendix A Related Work

Prior to the widespread adoption of subword tokenization, large vocabulary
sizes (e.g., 500k) were needed to allow for output expressivity and to avoid a
high proportion of out-of-vocabulary tokens. Various tricks were devised to
tackle the resulting computational issues (Jean et al., 2015; Mi et al., 2016;
L’Hostis et al., 2016). On the other side of the spectrum, character-level NMT
was also explored (Ling et al., 2015; Costa-jussà and Fonollosa, 2016), though
issues arise with large sequence lengths. Mielke et al. (2021) provide an
overview of the evolution of NLP tokenization and describe different types of
tokenization approaches. They conclude that reasoning about tokenizer choices
remains a vital part of modern pipeline preparation. In this context, our work
quantifies and hence also automates some of this process by offering a
framework to help guide the decision process and hyperparameter selection.
Somewhat similar to our work, Ataman and Federico (2018) perform a comparison
between BPE and Morfessor, though with only one specific vocabulary size
(30k). Similarly to Gowda and May (2020), they suggest that homogeneity of
token frequency is an important factor for MT model performance.

##  Appendix B Package Usage

The package is open-source101010github.com/zouharvi/tokenization-scorer and
can be downloaded via pip and used via the command-line:

    $ pip3 install tokenization-scorer
    $ tokenization-scorer -i en-de.tokenized_with_unigramlm.{en,de}
    > 0.4826

    $ tokenization-scorer -i en-de.tokenized_with_wordpiece.{en,de}
    > 0.5047

or as a module in Python:

    import tokenization_scorer
    text1 = "pick @@ed pick @@l @@ed pick @@les"
    tokenization_scorer.score(text1, metric="renyi", power=2.5)
    > 0.8031528501359657

    text2 = "pick @@e @@d pick @@l @@e @@d pick @@l @@e @@s"
    tokenization_scorer.score(text2, metric="renyi", power=2.5)
    > 0.9105681923824472

The supported metrics are the ones presented in Tab. 1: renyi_efficiency
(default), renyi_entropy, shannon_efficiency, shannon_entropy,
percentile_freq, bits, sequence_len. The power in Rényi can be modified using
an extra parameter: -e power=2.5. The similar applies to the percentile
frequency with -e perc_start=0.03 perc_end=0.83.

Predictor | En$\rightarrow$De | Cs$\rightarrow$En
---|---|---
| Bleu | ChrF | BLEURT | COMET | Bleu | ChrF | BLEURT | COMET
Sequence length | 0% | 4% | 23% | 13% | 4% | 24% | 51% | 17%
Percentile freq. | 9% | 21% | 47% | 33% | 25% | 63% | 86% | 55%
Entropy | 0% | 5% | 24% | 14% | 7% | 31% | 58% | 23%
Entropy efficiency | 22% | 8% | 0% | 1% | 6% | 1% | 3% | 3%
Rényi entropy | 7% | 0% | 6% | 1% | 0% | 7% | 24% | 4%
Rényi efficiency | 53% | 33% | 12% | 19% | 32% | 35% | 17% | 39%

Table 2: Variance explained between predictors and MT performance (Bleu, ChrF,
BLEURT and COMET) in Experiment 1 (only 3 MT seeds, 5 temperatures and 4
vocabulary sizes) with different language directions.

##  Appendix C Proofs

######  Lemma C.1.

Let $p_{\scaleto{\Delta^{*}}{4pt}}$ be a distribution over $\Delta^{*}$, and
let $p_{\scaleto{\Delta}{4pt}}$ be the unigram distribution induced by
$p_{\scaleto{\Delta^{*}}{4pt}}$ (Eq. 1). Then, the following equality holds

$\displaystyle\mathbb{E}[L]\cdot\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}_{\scaleto{\Delta}{4pt}}}},L\right)=\mathcal{L}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta^{*}}{4pt}})$
(22a)

###### Proof.

Let $\bm{\delta}\in\Delta^{*}$. Define the expected counts as follows

$\displaystyle\mathrm{E\text{-}count}(\delta)$
$\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sum_{\bm{\delta}\in\Delta^{*}}p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})\,\mathrm{count}(\delta,\bm{\delta})$
(23a)
$\displaystyle=\sum_{\bm{\delta}\in\Delta^{*}}p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})\frac{\mathrm{count}(\delta,\bm{\delta})}{|\bm{\delta}|}|\bm{\delta}|$
(23b) $\displaystyle=\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[X_{\delta}(\bm{\delta})\cdot L\right]$
(23c)

We start by manipulating the expected code length

$\displaystyle\sum_{\bm{\delta}\in\Delta^{*}}p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\bm{\delta})|$
$\displaystyle=\sum_{\bm{\delta}\in\Delta^{*}}p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})\sum_{n=1}^{|\bm{\delta}|}|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta_{n})|$
(24a)
$\displaystyle=\sum_{\bm{\delta}\in\Delta^{*}}\sum_{n=1}^{|\bm{\delta}|}p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta_{n})|$
(24b)
$\displaystyle=\sum_{\bm{\delta}\in\Delta^{*}}\sum_{\delta\in\Delta}p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})\mathrm{count}(\delta,\bm{\delta})|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|$
(24c)
$\displaystyle=\sum_{\delta\in\Delta}|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|\left(\sum_{\bm{\delta}\in\Delta^{*}}p_{\scaleto{\Delta^{*}}{4pt}}(\bm{\delta})\mathrm{count}(\delta,\bm{\delta})\right)$
(24d)
$\displaystyle=\sum_{\delta\in\Delta}\mathrm{E\text{-}count}(\delta)|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|$
(24e)

Now, we proceed with algebraic manipulation.

$\displaystyle\sum_{\delta\in\Delta}\mathrm{E\text{-}count}(\delta)$
$\displaystyle|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|=\sum_{\delta\in\Delta}\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[X_{\delta}(\bm{\delta})\cdot
L\right]|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|$ (25a)
$\displaystyle=\sum_{\delta\in\Delta}\left(\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[X_{\delta}(\bm{\delta})\right]\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[L\right]|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|+\mathrm{Cov}\left(X_{\delta}(\bm{\delta}),L\right)|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|\right)$
(25b)
$\displaystyle=\sum_{\delta\in\Delta}\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[X_{\delta}(\bm{\delta})\right]\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[L\right]|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|+\sum_{\delta\in\Delta}\mathrm{Cov}\left(X_{\delta}(\bm{\delta}),L\right)|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|$
(25c)
$\displaystyle=\sum_{\delta\in\Delta}\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[X_{\delta}(\bm{\delta})\right]\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[L\right]|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|+\mathrm{Cov}\left(\sum_{\delta\in\Delta}|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|X_{\delta}(\bm{\delta}),L\right)$
(25d)
$\displaystyle=\sum_{\delta\in\Delta}\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[X_{\delta}(\bm{\delta})\right]\operatorname*{\mathbb{E}}_{\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}}\left[L\right]|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|+\mathrm{Cov}\Bigg{(}\underbrace{\sum_{\delta\in\Delta}|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|X_{\delta}(\bm{\delta})}_{\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\overline{L}_{{\textsf{enc}_{\scaleto{\Delta}{4pt}}}}},L\Bigg{)}$
(25e)
$\displaystyle=\mathbb{E}[L]\cdot\underbrace{\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|}_{\text{expected
unigram code
length}}+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}_{\scaleto{\Delta}{4pt}}}},L\right)$
(25f)

∎

See 3.7

###### Proof.

By Lemma C.1, we have

$\mathbb{E}[L]\cdot\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}(\delta)|+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)=\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})$
(26)

Now, by applying Theorem 3.6, we achieve

$\displaystyle\mathbb{E}[L]\cdot\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})$
$\displaystyle\leq\mathbb{E}[L]\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}(\delta)|$
(27a)
$\displaystyle\mathbb{E}[L]\cdot\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)$
$\displaystyle\leq\mathbb{E}[L]\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}(\delta)|+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)$
(27b)
$\displaystyle\mathbb{E}[L]\cdot\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)$
$\displaystyle\leq\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})$
(27c)

Similarly, from Theorem 3.6, we have

$\displaystyle\mathbb{E}[L]\cdot\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil$
$\displaystyle\geq\mathbb{E}[L]\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}(\delta)|$
(28a)
$\displaystyle\mathbb{E}[L]\cdot\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)$
$\displaystyle\geq\mathbb{E}[L]\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}(\delta)|+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)$
(28b)
$\displaystyle\mathbb{E}[L]\cdot\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)$
$\displaystyle\geq\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})$
(28c)

Putting these together with some additional algebraic manipulation we get

$\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\leq\frac{\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})-\mathrm{Cov}(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L)}{\mathbb{E}[L]}\leq\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil$
(29)

This concludes the proof. ∎

See 3.9

###### Proof.

Recall that
${\textsf{eff}}(p_{\scaleto{\Sigma^{*}}{4pt}},t)=\frac{\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$.
To bound the denominator we use the fact, that for uniform distribution,
$\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}},L\right)=0$
and obtain
$\mathbb{E}[L]\log|\Delta|\leq\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})\leq\mathbb{E}[L]\lceil\log|\Delta|\rceil.$
Using this fact, we can obtain an upper bound

$\displaystyle{\textsf{eff}}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$
$\displaystyle=\frac{\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$
(30a)
$\displaystyle\leq\frac{\mathbb{E}[L]\cdot\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$
(numerator lower-bound from Theorem 3.7) (30b)
$\displaystyle\leq\frac{\mathbb{E}[L]\cdot\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathbb{E}[L]\log|\Delta|}$
(denominator upper-bound) (30c)
$\displaystyle=\frac{\lceil\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\frac{\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathbb{E}[L]}}{\log|\Delta|}$
(30d)

and a corresponding lower bound

$\displaystyle{\textsf{eff}}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$
$\displaystyle=\frac{\mathcal{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$
(31a)
$\displaystyle\geq\frac{\mathbb{E}[L]\cdot\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$
(numerator lower-bound from Theorem 3.7) (31b)
$\displaystyle\geq\frac{\mathbb{E}[L]\cdot\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathbb{E}[L]\lceil\log|\Delta|\rceil}$
(denominator upper-bound) (31c)
$\displaystyle=\frac{\mathrm{H}(\mathrm{W}_{\scaleto{\Delta}{4pt}})+\frac{\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\star}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathbb{E}[L]}}{\lceil\log|\Delta|\rceil}$
(31d)

∎

######  Theorem C.2 (Generalized Hölder’s inequality; §2 in Aczél and
Beckenbach (1980)).

Let $f$, $g$ and $h$ be vectors of positive values and coefficients $p$, $q$
and $r$ such that all but one are negative and
$\frac{1}{p}+\frac{1}{q}+\frac{1}{r}=0$. Further, if $\forall
i:f_{i}g_{i}h_{i}=1$ then

$\displaystyle\|f\|_{p}\,\|g\|_{q}\,\|h\|_{r}\leq 1.$ (32)

As noted in Aczél and Beckenbach (1980), Theorem C.2 is in fact a simple
special case of Theorem 12 in Hardy et al. (1934). We will use Theorem C.2
specifically with $r=-1$ and $h_{i}=f_{i}g_{i}$. This simplifies the
requirements for exactly one of $p$ and $q$ to be negative and
$\frac{1}{p}+\frac{1}{q}=1$. Eq. 32 can then be restated as the following.

######  Corollary C.3 (Reverse Hölder’s inequality).

If $f,g$ are positive vectors and $p,q$ are such that
$\frac{1}{p}+\frac{1}{q}=1$ and exactly one is negative and the other is
positive, then

$\displaystyle\|f\|_{p}\,\|g\|_{q}\leq\|fg\|_{1}.$ (33)

See 4.2

###### Proof.

Let $p=-s$ and $q=1-\alpha$. Let us consider three cases of $s$:

  * •

$s=0$, then $\alpha=1$, then Theorem 3.6 applies;

  * •

$s\in(-1,0)$, then $\alpha\in(1,\infty)$, $p\in(0,1)$ and $q\in(-\infty,0)$.

  * •

$s\in(0,\infty)$, then $\alpha\in(0,1)$, $p\in(-\infty,0)$ and $q\in(0,1)$.

In the latter two cases, we have one of $p$ and $q$ is positive and one is
negative. Further, our definitions of $p$ and $q$ imply that
$p^{-1}+q^{-1}=1$, which allows us to use the reverse Hölder’s inequality
(Corollary C.3). First, we note that the reverse Hölder’s inequality implies
that, for finite sequences $(x_{i})$ and $(y_{i})$,

$\displaystyle\left(\sum x_{i}^{p}\right)^{\frac{1}{p}}\left(\sum
y_{i}^{q}\right)^{\frac{1}{q}}$ $\displaystyle\leq\sum x_{i}y_{i}$ (34)
$\displaystyle\left(\sum x_{i}^{-s}\right)^{-\frac{1}{s}}\left(\sum
y_{i}^{1-\alpha}\right)^{\frac{1}{1-\alpha}}$ $\displaystyle\leq\sum
x_{i}y_{i}$ ($p$ and $q$ substitution) (35)

Let $\ell(\delta)=|{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(\delta)|$ be the
lengths of the codes given by our encoding. Further, let
$p_{\scaleto{\Delta}{4pt}}(\delta)$ be the unigram probabilities and $b$ be
the base of our encoding. Now set
$x_{i}=p_{\scaleto{\Delta}{4pt}}(\delta)^{-\frac{1}{s}}b^{-\ell(\delta)}$ and
$y_{i}=p_{\scaleto{\Delta}{4pt}}(\delta)^{\frac{1}{s}}$. This step is valid
because both quantities are positive. Then we proceed with algebraic
manipulations

$\displaystyle\left(\sum_{\delta\in\Delta}\left(p_{\scaleto{\Delta}{4pt}}(\delta)^{-\frac{1}{s}}b^{-\ell(\delta)}\right)^{-s}\right)^{-\frac{1}{s}}\left(\sum_{\delta\in\Delta}(p_{\scaleto{\Delta}{4pt}}(\delta)^{\frac{1}{s}})^{1-\alpha}\right)^{\frac{1}{1-\alpha}}$
$\displaystyle\leq\sum_{\delta\in\Delta}(p_{\scaleto{\Delta}{4pt}}(\delta)^{-\frac{1}{s}}b^{-\ell(\delta)})(p_{\scaleto{\Delta}{4pt}}(\delta)^{\frac{1}{s}})$
(36a)
$\displaystyle\left(\sum_{\delta\in\Delta}(p_{\scaleto{\Delta}{4pt}}(\delta)^{-\frac{1}{s}}b^{-\ell(\delta)})^{-s}\right)^{-\frac{1}{s}}\left(\sum_{\delta\in\Delta}(p_{\scaleto{\Delta}{4pt}}(\delta)^{\frac{1}{s}})^{1-\alpha}\right)^{\frac{1}{1-\alpha}}$
$\displaystyle\leq\sum_{\delta\in\Delta}b^{-\ell(\delta)}$ (algebra) (36b)
$\displaystyle\underbrace{\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)^{-\frac{1}{s}}}_{\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}A}\underbrace{\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha}\right)^{\frac{1}{1-\alpha}}}_{\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}B}$
$\displaystyle\leq\underbrace{\sum_{\delta\in\Delta}b^{-\ell(\delta)}}_{\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}C}$
(algebra) (36c)

Then, let
$A\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)^{-\frac{1}{s}}$,
$B\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha}\right)^{\frac{1}{1-\alpha}}$
and
$C\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sum_{\delta\in\Delta}b^{-\ell(\delta)}$
in the subsequent proof descriptions. Note that by the Kraft–McMillan
inequality (Kraft, 1949), because our code is prefix-free (and $b>0$), it must
be that $0<C\leq 1$.

$\displaystyle\frac{\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha}\right)^{\frac{1}{1-\alpha}}}{\sum_{\delta\in\Delta}b^{-\ell(\delta)}}$
$\displaystyle\leq\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)^{\frac{1}{s}}$
(divide by $AC$) (37a)
$\displaystyle\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha}\right)^{\frac{1}{1-\alpha}}$
$\displaystyle\leq\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)^{\frac{1}{s}}$
($0<C\leq 1$) (37b)
$\displaystyle\frac{1}{1-\alpha}\log\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha}\right)$
$\displaystyle\leq\frac{1}{s}\log\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)$
(take $\log$) (37c)
$\displaystyle\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})$
$\displaystyle\leq\mathcal{L}_{\text{enc}}^{(s)}(p_{\scaleto{\Delta}{4pt}})$
(37d)

Our constraint on $C$ is met and Eq. 37d holds with equality when the lengths
of our code satisfy the following relationship

$\displaystyle b^{-\ell(\delta)}$
$\displaystyle=\frac{p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha}}{\sum_{\delta^{\prime}\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta^{\prime})^{\alpha}}$
(38a) $\displaystyle\ell(\delta)$
$\displaystyle=-\alpha\log_{b}p_{\scaleto{\Delta}{4pt}}(\delta)+\log_{b}\left(\sum_{\delta^{\prime}\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta^{\prime})^{\alpha}\right)$
(38b)

Now we consider a sequence of $M$ tokens
$\bm{\delta}=\langle\delta_{1},\ldots,\delta_{M}\rangle$, where each
$\delta_{m}$ is sampled according to $p_{\scaleto{\Delta}{4pt}}$; note that
this is _not_ necessarily equivalent to a sequence $\bm{\delta}\sim
p_{\scaleto{\Delta^{*}}{4pt}}$, as we do not assume independence between
tokens in that setting. Let us first lift $p_{\scaleto{\Delta}{4pt}}$ to take
sequences, i.e.,
$p_{\scaleto{\Delta}{4pt}}(\bm{\delta})=\prod_{m=1}^{M}p_{\scaleto{\Delta}{4pt}}(\delta)$,
which follows naturally due to the independence of each $\delta_{m}$ in this
setting. Now let

$\displaystyle
Q=\sum_{\bm{\delta}\in\Delta^{M}}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})^{\alpha}=\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha}\right)^{M}$
(39)

where the later equality follows from the fact that there are $|\Delta|^{M}$
sequences in $\Delta^{M}$ and each $\delta$ appears an equal number of times.
We will now use Eq. 38b to reason about the length of an optimal code for
$\bm{\delta}$, where we similarly denote length as $\ell(\bm{\delta})$. We
will first assume that $s\in(-1,0)$ but later show that a slight modification
to the proof makes it viable also for $s>0$. Following the result in Eq. 38b,
the length $\ell(\bm{\delta})$ of an optimal integer-length code for
$\bm{\delta}$ should satisfy

$\displaystyle-\alpha\log_{b}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})+\log_{b}Q$
$\displaystyle\leq\ell(\bm{\delta})<-\alpha\log_{b}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})+\log_{b}Q+1$
(40a)
$\displaystyle-s\alpha\log_{b}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})+s\log_{b}Q$
$\displaystyle\geq
s\cdot\ell(\bm{\delta})>s-s\alpha\log_{b}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})+s\log_{b}Q$
(multiply by $s\in(-1,0)$) (40b) $\displaystyle
p_{\scaleto{\Delta}{4pt}}(\bm{\delta})^{-s\alpha}Q^{s}$ $\displaystyle\geq
b^{s\cdot\ell(\bm{\delta})}>b^{s}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})^{-s\alpha}Q^{s}$
(raise to power $b$) (40c) $\displaystyle
p_{\scaleto{\Delta}{4pt}}(\bm{\delta})^{-s\alpha+1}Q^{s}$ $\displaystyle\geq
p_{\scaleto{\Delta}{4pt}}(\bm{\delta})b^{s\cdot\ell(\bm{\delta})}>b^{s}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})^{-s\alpha+1}Q^{s}$
(multiply by $p_{\scaleto{\Delta}{4pt}}(\bm{\delta})$) (40d) $\displaystyle
p_{\scaleto{\Delta}{4pt}}(\bm{\delta})^{\alpha}Q^{s}$ $\displaystyle\geq
p_{\scaleto{\Delta}{4pt}}(\bm{\delta})b^{s\cdot\ell(\bm{\delta})}>b^{s}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})^{\alpha}Q^{s}$
($s\alpha=1-\alpha$) (40e)
$\displaystyle\sum_{\bm{\delta}\in\Delta^{M}}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})^{\alpha}Q^{s}$
$\displaystyle\geq\sum_{\bm{\delta}\in\Delta^{M}}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})b^{s\cdot\ell(\bm{\delta})}>Q^{s}b^{s}\sum_{\bm{\delta}\in\Delta^{M}}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})^{\alpha}$
(sum across all sequences of length $M$) (40f) $\displaystyle Q^{s+1}$
$\displaystyle\geq\sum_{\bm{\delta}\in\Delta^{M}}p_{\scaleto{\Delta}{4pt}}(\bm{\delta})b^{s\cdot\ell(\bm{\delta})}>Q^{s+1}b^{s}$
(sub. $Q$) (40g) $\displaystyle Q^{s+1}$
$\displaystyle\geq\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)^{M}>Q^{s+1}b^{s}$
(same logic as Eq. 39) (40h) $\displaystyle(s+1)\log_{b}Q$ $\displaystyle\geq
M\log_{b}\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)>(s+1)\log_{b}Q+s$
(take $\log_{b}$) (40i) $\displaystyle\frac{s+1}{s}\log_{b}Q$
$\displaystyle\leq\frac{M}{s}\log_{b}\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)<\frac{s+1}{s}\log_{b}Q+1$
(divide by $s\in(-1,0)$) (40j) $\displaystyle\frac{1}{1-\alpha}\log_{b}Q$
$\displaystyle\leq\frac{M}{s}\log_{b}\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)<\frac{1}{1-\alpha}\log_{b}Q+1$
(substitute $\alpha$) (40k)
$\displaystyle\frac{1}{1-\alpha}\log_{b}\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha}\right)^{M}$
$\displaystyle\leq\frac{M}{s}\log_{b}\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s\cdot\ell(\delta)}\right)<\frac{1}{1-\alpha}\log_{b}\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)^{\alpha}\right)^{M}+1$
(definition of $Q$) (40l) $\displaystyle
M\cdot\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})$
$\displaystyle\leq
M\cdot\mathcal{L}^{(s)}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta}{4pt}})<M\cdot\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})+1$
(40m) $\displaystyle\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})$
$\displaystyle\leq\mathcal{L}^{(s)}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta}{4pt}})<\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})+\frac{1}{M}$
(divide by $M$) (40n)

Note that in Eq. 40b, we multiplied by a negative value and therefore swapped
the directions of the inequalities. Then, in Eq. 40j we divided by a negative
value and swapped the inequalities back to their original directions. If
$s>0$, we would not change the directions of the inequalities and the proof
would proceed as before.

For large $M$, we can get arbitrarily close to $\mathrm{H}_{\alpha}$. However,
if we wish for $\ell(\delta)$ to be an integer, the upper bound becomes
$\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil$.∎

See 4.3

###### Proof.

Let ${\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}$ be an $s$-optimal code, i.e.,
a code that minimizes
$\mathcal{L}^{(s)}_{\textsf{enc}_{\scaleto{\Delta}{4pt}}}(p_{\scaleto{\Delta^{*}}{4pt}})$.
By Lemma C.1, we have

$\mathbb{E}[L]\cdot\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}(\delta)|+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}},L\right)=\mathcal{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})$
(41)

To prove the bound, we proceed as follows. Assume $s\neq 0$ as that case is
covered by Theorem 3.7. We first start with a simple application of Jensen’s
inequality:

$\displaystyle\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil$
$\displaystyle\geq\mathcal{L}^{(s)}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta}{4pt}})$
(Theorem 4.2) (42a)
$\displaystyle=\frac{\log_{b}\left(\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)b^{s|{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}(\delta)|}\right)}{s}$
(definition) (42b)
$\displaystyle\geq\frac{\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)s|{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}(\delta)|\log_{b}b}{s}$
(Jensen’s inequality) (42c)
$\displaystyle=\sum_{\delta\in\Delta}p_{\scaleto{\Delta}{4pt}}(\delta)|{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}(\delta)|$
(42d)

Algebraically, combining the above results

$\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil\geq\frac{\mathcal{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})-\mathrm{Cov}(\overline{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}},L)}{\mathbb{E}[L]}$
(43)

which proves the theorem. ∎

See 4.5

###### Proof.

Recall from Definition 4.4 that
${\textsf{eff}}_{\alpha}(p_{\scaleto{\Sigma^{*}}{4pt}},t)=\frac{\mathcal{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$,
with $s=\frac{1}{a}-1$. Again, to bound the denominator, we use the fact, that
for uniform distribution,
$\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}},L\right)=0$
and obtain
$\mathbb{E}[L]\log|\Delta|\leq\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})$.
Then, we proceed as follows

$\displaystyle{\textsf{eff}}_{\alpha}(p_{\scaleto{\Sigma^{*}}{4pt}},t)$
$\displaystyle=\frac{\mathcal{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}$
(44a)
$\displaystyle\leq\frac{\mathbb{E}[L]\cdot\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}},L\right)}{{\mathcal{L}_{{\textsf{enc}^{\scaleto{U}{4pt}}_{\scaleto{\Delta}{4pt}}}}(p_{\scaleto{\Delta^{*}}{4pt}})}}$
(upper-bound numerator) (44b)
$\displaystyle\leq\frac{\mathbb{E}[L]\cdot\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathbb{E}[L]\cdot\log|\Delta|}$
(lower-bound denominator) (44c)
$\displaystyle=\frac{\lceil\mathrm{H}_{\alpha}(\mathrm{W}_{\scaleto{\Delta}{4pt}})\rceil+\frac{\mathrm{Cov}\left(\overline{L}_{{\textsf{enc}^{s}_{\scaleto{\Delta}{4pt}}}},L\right)}{\mathbb{E}[L]}}{\log|\Delta|}$
(44d)

This proves the result. ∎

Figure 6: Predictor visualization in parallel to 2 and 2. Various features are
used as predictors of MT performance (average of 5 runs). Bands show 95%
$t$-test confidence intervals for regression lines.

##  Appendix D Model, computation and reproducibility details

For the MT model, we use the transformer_iwslt_de_en model architecture in
Fairseq (Ott et al., 2019). For data, we use 1M training and 50k dev parallel
sentences from English-German CommonCrawl (El-Kishky et al., 2020). BLEU
evaluation performed using SacreBLEU Post (2018). Details for the model
training and the code to reproduce the experiments in this paper will be made
publicly available. For the first experiment we trained $5\times 6\times
9=270$ MT models. For the second experiment we trained $5\times 5\times
3\times 3=225$ MT models. We used varying GPU models (GTX 1080, RTX 2080, RTX
3090) based on availability in shared compute cluster. Although different
hardware and different tokenizations had an impact on the training time, the
average per one configuration was 1.5 days. Overall, we estimate 800 GPU days.

##  Appendix E Tokenization Schemes

In this section, we describe the four tokenization schemes used together in
the second experiment. Special attention is paid to BPE, which plays a role in
the first experiment. Tab. 3 shows how different tokenizers with varying
vocabulary sizes tokenize the same word. For simplicity, we do not include
variable-length encoding, even though it has been previously applied to MT
(Chitnis and DeNero, 2015).

Tokenizer | $\bm{V=16k}$ | $\bm{V=4k}$
---|---|---
BPE | Re gu lation | Re gu la tion
BPE $\tau=-0.4$ | Reg ul ation | Reg ul a tio n
Unigram | Regulation | Re gu l ation
WordPiece | Regul ation | Re gul ation
LZ | Re gul ation | Re gu la tion
Morfessor | Regul ation | Re gul ation
Table 3: Example tokenizations of the word Regulation.

###  E.1 Byte-Pair Encoding

BPE was first discovered by Gage (1994) as a faster compression algorithm
alternative to Lempel–Ziv–Welch. It was later adapted by Sennrich et al.
(2016) as a tokenizer for MT. The algorithm starts by splitting words of
individual tokens of length 1 (characters). Then it repeatedly takes the most
frequent pair of adjacent tokens and joins it into a new single token, adding
this token to the vocabulary. This procedure is repeated until we fill the
predefined vocabulary budget. Zouhar et al. (2023) show that this greedy
approach is approximately optimal when searching for the vocabulary (merge
sequence). We are however interested in intentionally suboptimal vocabularies.

#### Temperature.

In order to introduce stochasticity into the process and intentionally alter
the tokenization, instead of deterministically merging the most frequent token
pair, we randomly sample a pair proportionally to their frequencies, similar
to setup of Sälevä and Lignos (2023). We add an additional hyperparameter to
this strategy by annealing the frequency distribution with a temperature
parameter $\tau$, where annealing is performed via a softmax. We use
$\tau=0^{+}$ (original greedy BPE), $0.2$, $0.4$, $0.9$, $100$, $-100$,
$-0.9$, $-0.4$, $-0.2$, and $0^{-}$. Progressively, each temperature creates
less and less optimal BPE compression model, increasing the encoded length of
the data. The last model, with $\tau=0^{-}$, we dub antigreedy because it
always chooses the least frequent pair to merge, practically leading to a
character-only model.

###  E.2 Unigram LM

While BPE repeatedly merges the most frequent pair, Unigram LM (Kudo, 2018)
tokenizer modifies this part of the algorithm with a more complex approach.
The algorithm then jointly optimizes the token vocabulary and the unigram
probability of the tokenized text. Because of this dual objective, the
algorithm is done in Expectation-Maximization manner. We start by seeding the
token vocabulary with the most frequent substrings. In one step, probability
is assigned to individual tokens and also how much worse the overall
probability of the whole text would be if the single token was removed. In the
second step, top-$\eta$% of the tokens is preserved. These two steps are
repeated until the vocabulary size is reduced to size $V$.

###  E.3 Linguistically Informed tokens

Morfessor (Creutz and Lagus, 2007; Virpioja et al., 2013; Smit et al., 2014)
is a family of unsupervised morphological analyzers that work on the minimum
description principle, which is not distant from compression. The link to
tokenization is clear: Under some minimization objective, segment the input
text into a list of morphemes with the constraint of at most $V$ distinct
morphemes appearing in the whole text, where $V$ is a hyperparameter. In the
case of tokenization, we would use the morphemes as tokens. For our purposes,
we use vanilla Morfessor 2.0.6.

###  E.4 Lempel–Ziv–Welch Compression

BPE, a popular tokenization scheme used in many NLP applications, was first
invented (Gage, 1994) as a faster compression algorithm alternative to
Lempel–Ziv–Welch (LZW). However, there is, in fact, a family of algorithms
related to LZW. LZ77 (Ziv and Lempel, 1977) and LZW (Welch, 1984) are two of
the most popular variants.

Figure 7: Examples of unigram distributions of tokens with varying imbalance
of probabilities. Letters corresponding to the are in

X

and those corresponding to cow in

X

.

######  Example E.1.

Consider a scenario where we want to encode a lowercased text without
punctuation with the restriction of $|\Delta|=28$. Upon adding the 26
lowercased letters of the English alphabet and space, we can add one
additional token. Let us consider the tokens: the and cow. Certainly, the
former token is much more frequent in natural English distribution and hence a
tokenizer fully utilizing this token would result in shorter optimal expected
code length. By adding the token the, we are lowering the probability mass of
the most frequent English letters: e and t. This does not happen with cow and
hence the first distribution is more uniform. For a depiction of this
synthetic example, see Fig. 7. If we measure it using ${\textsf{eff}}_{1}$, we
obtain only $1\%$ difference but if we measure it using ${\textsf{eff}}_{9}$,
we get 3% difference, showing that the first tokenization is much better.