# Toward a Theory of Tokenization in LLMs

Nived Rajaraman, Jiantao Jiao, Kannan Ramchandran Nived Rajaraman is with the
Department of Electrical Engineering and Computer Sciences, University of
California, Berkeley. Jiantao Jiao is with the Department of Electrical
Engineering and Computer Sciences and the Department of Statistics, University
of California, Berkeley. Kannan Ramchandran is with the Department of
Electrical Engineering and Computer Sciences, University of California,
Berkeley. Email: {nived.rajaraman, jiantao<EMAIL_ADDRESS>
###### Abstract

While there has been a large body of research attempting to circumvent
tokenization for language modeling (Clark et al., 2022; Xue et al., 2022), the
current consensus is that it is a necessary initial step for designing state-
of-the-art performant language models. In this paper, we investigate
tokenization from a theoretical point of view by studying the behavior of
transformers on simple data generating processes. When trained on data drawn
from certain simple $k^{\text{th}}$-order Markov processes for $k>1$,
transformers exhibit a surprising phenomenon - in the absence of tokenization,
they empirically fail to learn the right distribution and predict characters
according to a unigram model (Makkuva et al., 2024). With the addition of
tokenization, however, we empirically observe that transformers break through
this barrier and are able to model the probabilities of sequences drawn from
the source near-optimally, achieving small cross-entropy loss. With this
observation as starting point, we study the end-to-end cross-entropy loss
achieved by transformers with and without tokenization. With the appropriate
tokenization, we show that even the simplest unigram models (over tokens)
learnt by transformers are able to model the probability of sequences drawn
from $k^{\text{th}}$-order Markov sources near optimally. Our analysis
provides a justification for the use of tokenization in practice through
studying the behavior of transformers on Markovian data.

##

###  1 Introduction

The training of language models is typically not an end-to-end process.
Language models are often composed of a “tokenizer”, which encodes a sequence
of characters into a sequence of token ids, which map to substrings. The
subsequent language modeling task is carried out by a neural network or
transformer, which is pre-trained and fine-tuned on large datasets. The ideal
goal is to jointly train the tokenizer and transformer with end-to-end
accuracy as the objective. This is a challenging problem to solve efficiently,
and thus, the tokenizer is generally adapted on a portion of the training
dataset and frozen before the transformer is trained.

The simplest tokenizer encodes at the character or at the byte level (after
encoding into UTF-8), such as is done in ByT5 (Xue et al., 2022) and Canine
(Clark et al., 2022). The maximum sequence length that such models can process
is also smaller for the same amount of compute. In practice, byte-
level/character level models perform worse for the reason that semantic
relationships can be harder to capture at the character level (Libovickỳ et
al., 2021; Itzhak and Levy, 2021) and for this reason, tokenizing at the
subword level is used more commonly.

Though used most commonly, tokenization at the subword level often has sharp
edges. Test sequences may contain rare tokens which were never seen in the
training dataset. The presence of such tokens may induce undesirable behavior
in the outputs of models (Rumbelow and Watkins, 2023; Kharitonov et al., 2021;
Yu et al., 2021) and present an attack surface for bad actors. Moreover,
tokenized models struggle on tasks that involve manipulation at the character
level, such as spelling out words or reversing sentences. For similar reasons,
LLMs with standard tokenizers also struggle to carry out basic arithmetic
(Golkar et al., 2023). Despite this brittleness, tokenization is used in
nearly all state-of-the-art LLM architectures.

Since tokenizers are usually trained in isolation, they do not directly
optimize for extrinsic loss metrics such as the end-to-end perplexity or
precision. A number of domain and task specific intrinsic objectives and
evaluation metrics have been proposed for tokenization. The most commonly used
intrinsic metric to compare tokenizers with the same dictionary size is the
average compressed sequence length. Zouhar et al. (2023a) show that the Renyi
efficiency of the tokenizer correlates well with the end-to-end BLEU for
machine translation. Petrov et al. (2023) propose parity, which associates a
higher score if the tokenizer parses sentences across different languages
having the same meaning, into a similar number of tokens. Similarly, Gallé
(2019) investigate various tokenizers for machine translation from the view of
compression capacity and conclude that for two token vocabularies of the same
size, the one that typically requires fewer tokens to cover a sentence
typically achieves a better translation, a commonly used metric known as
fertility (Rust et al., 2021; Scao et al., 2022; Ali et al., 2023). The
validity of these proxy objectives in general, is established by experimental
verification.

In this paper, we introduce a statistical formulation for tokenization for
next-word-prediction. Taking a step back, rather than focusing on proxy
evaluation metrics, which lead to an ever-changing goalpost, we focus on
understanding the behavior of the end-to-end cross-entropy loss,
$\mathcal{L}(\cdot)$. We consider a simplification of real world data
generating processes and study the case where data sources are
$k^{\text{th}}$-order Markov processes. Within this framework we can compare
tokenizers against each other, and in the process capture several interesting
phenomena. Our main results are as follows,

  1. 1.

There are very simple $k^{\text{th}}$-order Markov processes such that in the
absence of any tokenization, transformers trained on data drawn this source
are empirically observed to predict characters according to the stationary
distribution of the source under a wide variety of hyperparameter choices.
This is problematic because unigram models such as that induced by the
stationary distribution are poor at modeling Markovian data and suffer from a
high cross-entropy loss. This phenomenon was also recently observed in Makkuva
et al. (2024).

  2. 2.

When trained with tokenization, transformers are empirically observed to break
through this barrier and are able to capture the probability of sequences
under the Markov distribution near-optimally. In other words, in the presence
of tokenization, transformers appear to achieve near-optimal cross-entropy
loss. This phenomenon is observed with a multitude of tokenizers used commonly
in practice. Even though the end-to-end model is near optimal, we observe that
the behavior of the transformer is surprisingly the same in a qualitative
sense - the model largely still predicts tokens according to a unigram
distribution.

  3. 3.

We analyze a toy tokenizer which adds all length-$k$ sequences into the
dictionary and show that as dictionary size grows, unigram models trained on
the tokens get better at modeling the probabilities of sequences drawn from
Markov sources. We then theoretically prove that tokenizers used in practice,
such as the LZW tokenizer (Zouhar et al., 2023a) and a variant of the BPE
tokenizer (Gage, 1994; Sennrich et al., 2016) which are learnt from data also
satisfy this property but require much smaller dictionaries to achieve any
target cross-entropy loss.

In our framework, the most challenging hurdle and the biggest departure from
previous work such as (Zouhar et al., 2023b) is the element of generalization
- understanding how a tokenizer performs on new sequences that it was not
trained on. This generalization turns out to be a delicate phenomenon - we
show in Appendices D and E that there exist tokenizers which generalize poorly
in the sense that they may compress the dataset they are trained on into a
short sequence of tokens, but completely fail to generalize to new sequences.
We also show that there exist dictionaries which generalize well (in the sense
of having low cross-entropy loss) to new sequences under one encoding
algorithm, but fail to generalize under another.

####  1.1 Related Work

Tokenization has a long history of empirical study in natural language
processing. In the literature, a number of tokenizers have been developed for
various domains such as math (Singh and Strouse, 2024), code (Zheng et al.,
2023; Parr, 2013) and morphology-aware tokenizers for different languages like
Japanese (Tolmachev et al., 2018; Den et al., 2007) and Arabic (Alyafeai et
al., 2023) among many others. In modern LLMs, the most commonly used
tokenizers are variants of BPE (Gage, 1994), Wordpiece (Schuster and Nakajima,
2012) and the Unigram tokenizer (Kudo, 2018) which learn a dictionary from
data, rather than hard-coding language dependent rules. There has been a long
line of work interpreting tokenization from various lenses (Grefenstette and
Tapanainen, 1994; Palmer, 2000). Notably, Zouhar et al. (2023b) take the view
that the popular BPE tokenizer (Wolff, 1975; Gage, 1994) can be viewed as a
greedy algorithm for the problem of finding the sequence of “token merges”
which minimizes the length of the resulting string and establish approximation
guarantees for the algorithm. However, the aspect of generalization is missing
here - when trained on one and evaluated on another dataset, these guarantees
may no longer hold.

The theoretical study of transformers has also received much attention
recently and we discuss the closest relatives to our work below. Edelman et
al. (2024) study the learning trajectory of transformers trained on data drawn
from $1^{\text{st}}$-order Markov chains. While the authors empirically
observe that the models eventually learn to predict tokens correctly according
to the Markov kernel, simplicity bias slows down the optimization - the models
initially predict tokens according to a unigram model (in context unigrams),
which delays learning the optimal solution. This phenomenon was also observed
in Makkuva et al. (2024) who prove that when transformers are trained on data
generated from a simple $1^{\text{st}}$-order switching Markov processes, the
optimization landscape contains a bad local minimum at the unigram model
corresponding to the stationary distribution of the process. For
$k^{th}$-order switching Markov processes, they observe that forcing the
context window of the transformer to be small is the only hyperparameter which
enables the model to learn the underlying Markov kernel. While a positive
result, such a fix is unlikely to be used in practice. On the positive side,
Nichani et al. (2024) study an in-context causal learning task that
generalizes learning in-context bigrams for $1^{\text{st}}$-order Markov
processes. The authors authors analyze the trajectory of gradient descent and
show that in the special case of data sampled from a Markov chain,
transformers learn an induction head which learns to predict according to in-
context bigram counts.

###### Notation.

All logarithms are base $e$, unless specified otherwise. The Shannon entropy
$H(X)$ of a categorical random variable $X$ is
$-\sum_{x\in\text{supp}(X)}p(x)\log p(x)$. $H_{\textsc{Ber}}(p)$ captures the
entropy of a Bernoulli random variable with parameter $p$. The notation
$O_{p,q,r}(f(n))$ (likewise $\Omega_{\\{\cdot\\}}$ and $\Theta_{\\{\cdot\\}}$)
indicate that the underlying constant depends polynomially on the parameters
$p,q$ and $r$. The notation $\widetilde{O}(f(n))$ (likewise,
$\widetilde{\Theta}$ and $\widetilde{\Omega}$) ignores $\mathrm{polylog}(n)$
terms. For a set $S$, $S^{\star}=\cup_{k=1}^{\infty}S^{k}$, the set of all
sequences with elements drawn from $S$. For a sequence $\bm{t}$,
$\bm{t}_{i\mathrel{\mathop{\mathchar
58\relax}}j}=(\bm{t}_{i},\bm{t}_{i+1},\cdots,\bm{t}_{j})$ returns a slice of
the sequence.

###  2 Formulation

We consider a setting where the learner’s objective is to learn a language
model which models probabilities of sequences over an input alphabet
$\mathcal{A}$. The data to be modeled is generated according to an unknown
probability model $P\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}^{\star}\to[0,1]$ over strings. A tokenizer is a tuple
$\mathcal{T}=(\textsf{Dict},\textsf{DS},\textsf{enc}(\cdot),\textsf{dec}(\cdot))$.
Here Dict is a collection of tokens and DS is a data-structure which stores
additional information about tokens; for instance, in BPE, every token is
constructed from a pair of shorter tokens, and this additional information is
stored in DS. If not explicitly instantiated, $\textsf{DS}=\emptyset$. The
encoding function $\textsf{enc}(\cdot)\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}^{\star}\to\textsf{Dict}^{\star}$, which is implicitly a
function of DS, maps strings of characters to a sequence of tokens, and
likewise, the decoding function $\textsf{dec}(\cdot)\mathrel{\mathop{\mathchar
58\relax}}\textsf{Dict}^{\star}\to\mathcal{A}^{\star}$ maps a sequence of
tokens to a string of characters. We assume that the tokenizer is
“consistent”, namely, $\textsf{dec}(\textsf{enc}(\cdot))$ is the identity
function.

We consider a setting where the learner has access to a training dataset which
is a sequence of length $n$ sampled from a data source111This can be thought
of as the concatenation of all the individual sequences in the training
dataset.. We study the likelihood maximization problem, where the objective of
the learner is to learn an end to end model such that the cross-entropy loss
is minimized. In the presence of tokenization, we have a model of the form
$Q_{\text{end}}=Q\circ\textsf{enc}(\cdot)$ where $Q$ is a joint distribution
across sequences of tokens when the tokenizer corresponding to
$\textsf{enc}(\cdot)$ is used. The cross-entropy loss, i.e. the log-
perplexity, can be written down as,

$\displaystyle\mathcal{L}_{m}(Q_{\text{end}})\triangleq-\mathbb{E}[\log
Q(\textsf{enc}(\bm{s}))],$ (1)

with the objective to minimize it. Here, the expectation is over $\bm{s}$, a
fresh test sequence of length $m$ sampled from the data generating process.
Fixing a tokenizer, let $\mathcal{Q}$ denote a family of joint distributions
over tokens (i.e. likelihood models). The objective then is to jointly design
a tokenizer (with encoding function $\textsf{enc}(\cdot)$) and likelihood
model $Q\in\mathcal{Q}$ such that the test loss
$\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))$ is small. In general, jointly
optimizing over the tokenizer $\mathcal{T}$ and the likelihood model $Q$ is a
chicken-and-egg problem. Optimizing over $\mathcal{T}$ requires knowing the
corresponding optimal likelihood model over its tokens,
$Q^{\star}\in\mathcal{Q}$. However, in order to learn such a model, we must
have committed to a tokenizer upfront.

In this paper, the end-to-end task we consider is next token prediction, where
perplexity minimization is a natural objective. In practice, other metrics may
be more commonly employed depending on the domain, such as BLEU (Papineni et
al., 2002) or ROUGE (Lin, 2004) for machine translation. The theoretical study
of these metrics is left as future work.

####  2.1 Data generating process

$0$$1$$p$$q$ Figure 1: Switching process: The above Markov process describes
the distribution of $X_{n}$ conditioned on $X_{n-1}$. $k^{th}$-order extension
of this Markov process: the conditional probability of $X_{n}$ only depends on
$X_{n-k}$ and is given by the above process, with $\Pr(X_{n}=1|X_{n-k}=0)=p$
and $\Pr(X_{n}=1|X_{n-k}=1)=1-q$.

In this paper, we consider a simplification of real-world data generating
processes by considering the case where the data generating distribution is a
$k^{\text{th}}$-order Markov process over characters. Studying the behavior of
transformers trained on Markov data was the subject of the works Makkuva et
al. (2024) and Edelman et al. (2024), where a number of interesting phenomena
were unearthed. Surprisingly, when a transformer is trained on data from
certain simple $k^{\text{th}}$-order Markov processes like the one considered
in Figure 1, a very peculiar phenomenon occurs - the transformer seems to
learn a unigram model over characters, and in particular one induced by the
stationary distribution over characters, despite the data following a Markov
process. For the switching Markov chain in Figure 1, Edelman et al. (2024)
flesh out the behavior in more detail for the case $k=1$ \- the transformer
has a critical point corresponding to a unigram model which estimates the
probability of $0$ and $1$ in an in-context manner from the test sequence it
sees. When trained for sufficiently long, the transformer eventually escapes
this saddle point.

In the case of the switching process for $k\geq 2$, the situation is
different. The transformer fails to escape the stationary unigram model
altogether regardless of the choice of a number of hyperparameters, including
the number of feed-forward layers in the model, the embedding dimension, and
the number of attention heads. In Figure 2(a) this is made clearer - the
transformer fails to improve its test loss beyond that of the best unigram
model on the training data (dotted line). In general, given an arbitrary test
sequence, the transformer learns to output the next character as $0$ with
probability equal to the empirical fraction of $0$’s observed in the test
sequence.

Formally, for a dictionary Dict, the unigram family of models,
$\mathcal{Q}_{1\text{-gram}}$, is defined as below:
$Q\in\mathcal{Q}_{1\text{-gram}}$ associates the probability
$Q(\bm{t}_{1},\bm{t}_{2},\cdots,\bm{t}_{j})=Q_{\\#}(j)\prod_{i=1}^{j}Q_{\text{tok}}(\bm{t}_{i})$
to the sequence of tokens $(\bm{t}_{1},\cdots,\bm{t}_{j})$ for some measures
$Q_{\\#}$ and $Q_{\text{tok}}$ supported on $\mathbb{N}$ and Dict
respectively. Empirically, transformers appear to learn an in-context unigram
model when trained on data from the switching process in Figure 1 for $k\geq
2$. How bad can this be? It turns out that the gap between the cross-entropy
of the best unigram model and that of the optimal model can be characterized
precisely.

((a)) The loss of the transformer fails to converge to the optimal cross-
entropy loss (dashed line) and instead converges to that of the best i.i.d.
model (dotted line). The shaded blue region captures how the test loss curves
vary as hyperparameters (number of layers, embedding dimension etc.) are
changed.

((b)) In the presence of tokenization, the test loss of the model approaches
the optimal bound (dashed line). It is worth noting that the models trained
here are significantly smaller than those considered in Figure 2(a), having up
to $70\times$ fewer parameters and yet are able to achieve the optimal cross-
entropy loss.

Figure 2: Transformers trained with tokenization on the order-$2$ switching
Markov process (Figure 1) with $p=q=0.8$. On the left we have the model
trained without tokenization and on the right the model uses BPE with a
dictionary of size $10$ learnt from data. More details are discussed in
Appendix F.

######  Theorem 2.1.

Consider any ergodic data source with stationary distribution over characters
$\pi$. The unconstrained optimal likelihood model achieves cross-entropy loss,

$\displaystyle\min_{Q}\mathcal{L}_{m}(Q)=H(P)$ (2)

In contrast, the cross-entropy loss under any unigram model
$Q\in\mathcal{Q}_{1\text{-gram}}$ is lower bounded by,

$\displaystyle\mathcal{L}_{m}(Q)\geq mH(\pi)$ (3)

The ratio of $H(P)$ and $mH(\pi)$ can be made arbitrarily large for the
switching Markov chains in Figure 1 as the switching probabilities $p$ and $q$
approach $0$ or $1$. See Example 2.2 for more details.

######  Example 2.2.

Consider the switching Markov process in Figure 1 on $\\{0,1\\}$ with
$p=q=1-\delta$. For this process,
$\lim_{m\to\infty}\frac{1}{m}H(P)=H_{\textsf{Ber}}(\delta)=\delta\log(1/\delta)+(1-\delta)\log(1/(1-\delta))$,
but $\pi=\\{1/2,1/2\\}$ and so $H(\pi)=H_{\textsf{Ber}}(1/2)=\log(2)$. The
ratio $\lim_{m\to\infty}\frac{mH(\pi)}{H(P)}$ goes to $\infty$ as $\delta\to
0$.

###  3 The role of tokenization

Figure 3: Token distribution returned by the transformer when fed in a
sequence generated from the stochastic source, tokenized by a learnt BPE
encoder with $20$ tokens. A test sequence is generated from the stochastic
source and encoded into a token sequence $\bm{t}$. Each narrow vertical column
represents the distribution over next tokens returned by the transformer when
the first $x$ tokens of $\bm{t}$ are fed into the model, where $x$ is varied
from $0$ to the length of $\bm{t}$. For most values of $x$, the model appears
to predict the same distribution over the next token.

While transformers are a powerful class of models, it is concerning that they
fail to learn very simple distributions such as $k^{\text{th}}$-order Markov
processes under a wide choice of hyperparameters. Why do transformers work so
well in practice if they can’t learn Markovian data? It turns out that there
is a simple missing ingredient in all the architectures considered so far:
tokenization. The models are trained on raw character sequences drawn from the
stochastic source. To understand the role of tokenization, we train the
transformer on sequences generated from the stochastic source which are
encoded into tokens by a learnt BPE tokenizer. The transformer operates on
sequences of tokens, rather than sequences of characters. In Figure 2(b) we
plot the results of this experiment - in the presence of tokenization, the
cross-entropy loss of the end-to-end model approaches the optimal bound.

Let’s peek into the model a bit more and understand its behavior. In Figure 3
we draw a test sequence from the stochastic source and tokenize it using a
learnt BPE tokenizer with $20$ tokens to generate a sequence $\bm{t}$ with $k$
tokens. We feed in $\bm{t}_{1\mathrel{\mathop{\mathchar 58\relax}}x}$ for each
$x\in[k]$ into the model and observe the next-token distribution the model
generates. For test sequences of length $k=600$ tokens, we plot the
distribution over next-tokens in Figure 3 as we vary the length of the prefix.
Observe that the model learns to predict the a similar next-token distribution
at almost all values of $x$, essentially ignoring the context it was shown.
Thus the transformer learns what is essentially a unigram model.

The behavior of the transformer on the $k^{\text{th}}$-order switching source
in Figure 1 with and without tokenization is essentially the same. In both
cases, the model learns a unigram model over the tokens - in the absence of
tokenization this unigram model is in fact the stationary distribution induced
by the source. If the transformer learns a unigram model in both cases, how
come there is such a large gap in performance between the two? To understand
this in more detail, we analyze a toy tokenizer in the next section.

###  4 Unigram models under tokenization

Let’s consider a toy tokenizer which assigns all possible substrings of length
$r$ as tokens in the dictionary and study what happens when a unigram model is
trained on the tokenized sequences. The total dictionary size $d=2^{r}$. A
sequence of characters is mapped to a sequence of tokens by simply chunking it
into a sequences of $r$ characters which are replaced by the corresponding
token index222The last few characters which do not add up to $r$ in total are
left untokenized. These boundary effects will not matter as the test sequences
grow in length. The resulting stochastic process on the tokens is still
Markovian, but over a state space of size $2^{r}$. For any unigram model $Q$
on the tokens, the cross-entropy loss can be written down as,

$\displaystyle\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))$
$\displaystyle=\mathbb{E}\left[\sum_{\bm{t}\in\textsf{enc}(\bm{s})}\log(1/Q_{\text{tok}}(\bm{t}))\right],$
(4)

where we ignore the contribution of $Q_{\\#}(|\textsf{enc}(\bm{s})|)$ to the
cross-entropy by simply choosing $Q_{\\#}=\mathrm{Unif}([m])$ and letting
$\lim_{m\to\infty}\log(m)/m=0$. For any token $\bm{t}$, choose
$Q_{\text{tok}}(\bm{t})=\pi(\bm{t}_{1})\prod_{i=1}^{r-1}P(\bm{t}_{i+1}|\bm{t}_{i})$
as the stationary probability the underlying Markov process associates with
$\bm{t}$. Then,

$\displaystyle\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))$ (5)
$\displaystyle=-\mathbb{E}\left[\log(P(\bm{s})+\\!\\!\sum_{i=0}^{m/k-1}\log\left(\frac{\pi(\bm{s}_{ki+1})}{P(\bm{s}_{ki+1}|\bm{s}_{ki})}\right)\right]$
(6)
$\displaystyle\overset{(i)}{\approx}H(P)+\frac{1}{k}\left(mH(\pi)-H(P)\right)$
(7)
$\displaystyle=H(P)\left(1-\frac{1}{\log_{2}(d)}\right)+\frac{mH(\pi)}{\log_{2}(d)}.$
(8)

In $(i)$ the approximation is derived from the fact that as $m$ grows large,
$\frac{1}{m}\sum_{i=0}^{m/k}\log(P(\bm{s}_{ki+\ell+1}|\bm{s}_{ki+\ell})$
approaches $\frac{H(P)}{k}$. With $d=2$ (i.e., $r=1$), we recover the
performance of the character tokenizer in Theorem 2.1. An immediate
implication of this simple calculation is that there is a unigram model which
is nearly optimal as the dictionary size grows to $\infty$.

While this toy tokenizer allows us to glean this intuition behind why
tokenization allows unigram models to be near-optimal, there are some obvious
issues. One, the tokenizer does not adapt to the distribution of the data.
Indeed, for the switching Markov source in Figure 1, as $p=q=\delta\to 0$, the
source contains increasingly longer sequences of contiguous $0$’s and $1$’s.
In this case, it makes since to have a dictionary containing such sequences,
rather than all possible length-$r$ sequences, many of which would be seen
very few times (if at all) in a test sequence. At a more technical level, in
eq. 8, to get to a cross-entropy loss of $2H(P)$, the size of the dictionary
required by the toy tokenizer is $e^{mH(\pi)/H(P)}$. As discussed in Example
2.2 for the switching Markov process with $p=q=\delta$, this dictionary size
can be extremely large and scales exponentially (in $1/\delta$) as
$e^{1/\delta\log(1/\delta)}$ when $\delta$ is small. In general, on stochastic
sources on a much larger alphabet, such as English/ASCII, this toy tokenizer
would result in a prohibitively large dictionary.

A large dictionary itself is not a major problem per se, trading off the width
of the model for the need for larger dimensional embeddings. However, larger
dictionaries are usually correlated with the presence of rare tokens which
appear infrequently at training time. This presents a problem in practice - a
lot more data is often required to see enough examples of such tokens to learn
good embeddings for them. More importantly, in the absence of this volume of
data, rare tokens present an attack surface to elicit undesirable behavior in
the model (Rumbelow and Watkins, 2023). In practice, this issue present with
the toy tokenizer is, to an extent, resolved by using tokenization algorithms
such as BPE or Wordpiece, which learn dictionaries from data. In the process,
they are able to avoid learning extremely rare tokens, by enforcing a lower
bound on the number of their occurrences in the training data to be allocated
as a token. Moreover, by minimizing the number of such rare tokens, the model
is able to utilize its token budget in a more efficient manner.

We now introduce the main theoretical result of this paper, showing that with
the appropriate tokenization algorithm with a token budget of $d$, a unigram
model is not only asymptotically able to achieve the optimal cross-entropy
loss, but also requires far smaller dictionaries to match the performance of
the toy tokenizer considered earlier. In order to avoid dealing with the
transient characteristics of the source, we consider the cross-entropy loss in
eq. 1 under the assumption that the test sequences $\bm{s}$ are of length
$m\to\infty$. Namely, define the normalized loss,

$\displaystyle\mathcal{L}(\cdot)=\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(\cdot)$
(9)

######  Theorem 4.1.

Consider a Markov data generating process which satisfies Assumption 4.2. Let
$d$ denote a budget on the size of the dictionary. Then, there exists a
tokenizer with at most $d$ tokens and encoding function $\textsf{enc}(\cdot)$,
such that,

$\displaystyle\min_{\mathcal{Q}\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}(\cdot))\leq\frac{1}{1-\varepsilon}\min_{Q^{\prime}}\mathcal{L}(Q^{\prime})$
(10)

where $\varepsilon$ is $\log(1/\delta)/0.99\log(d)$333$\varepsilon$ is assumed
to be $<1$ in this statement. The constant $0.99$ can be made arbitrarily
close to $1$.. Furthermore, a tokenizer satisfying eq. 10 with probability
$\geq 1-d^{-\Omega_{\delta}(\log(d))}$ can be learnt from a dataset of
$\widetilde{O}_{\delta}(d)$ characters.

The tokenizers considered in this theorem are far more efficient with their
token budget than the toy tokenizer - to achieve a cross entropy loss within a
factor $2$ of optimal, the dictionary size required by these tokenizer is
$d\approx 1/\delta^{2}$ on any source satisfying Assumption 4.2. In
comparison, the toy tokenizer requires a dictionary size of
$e^{1/\delta\log(1/\delta)}$ to achieve the same error. We show that the LZW
tokenizer proposed in (Zouhar et al., 2023a) achieves the upper bound in eq.
10 when trained on a dataset of size $\widetilde{O}(d)$. Likewise, we also
show that a sequential variant of BPE achieves the upper bound in eq. 10 up to
a factor of $2$ and with a worse dependency in the $o(1)$ term when trained on
a dataset of size $\widetilde{O}(d^{2})$. What is interesting is that neither
of these algorithms explicitly learn a unigram likelihood model, $Q$, while
constructing the dictionary. Yet they are able to perform as well as the
tokenizers which are jointly optimized with a likelihood model, such as the
Unigram tokenization algorithm (Kudo, 2018).

###### Key insight.

While the toy tokenizer provides a high level intuition as to why tokenization
might enable unigram models to model Markov sources well, here we present a
different explanation which captures tokenization from an operational
viewpoint. Tokenizers which do a good job at learning patterns in the data and
assigning these frequent patterns as tokens in the dictionary are compatible
with an i.i.d. model over tokens. A hypothetical example motivating this
point: consider a tokenizer such that the distribution of tokens in the
encoding of a fresh string sampled from the source is distributed i.i.d.,
except that whenever the token $\bm{t}^{\prime}$ appears, it is always
followed by $\bm{t}^{\prime\prime}$. An i.i.d. model on the tokens is a poor
approximation since $P(\bm{t}^{\prime}\bm{t}^{\prime\prime})\gg
P(\bm{t}^{\prime})P(\bm{t}^{\prime\prime})$. However, by merging
$\bm{t}^{\prime}$ and $\bm{t}^{\prime\prime}$ into a new token $\bm{t}$ and
adding this to the dictionary, the new distribution over tokens is i.i.d. In
general, this motivates why it is desirable for a tokenizer to allocate new
tokens to substrings which appear next to each other frequently, i.e. a
pattern in the data. As more tokens are added to the dictionary, one might
expect the cross-entropy loss incurred by the best unigram model to improve.

Loosely, Theorem 2.1 gives an example where the converse is true as well - the
character-level tokenizer does not learn patterns in the data generating
process and the token budget is left unused. The cross-entropy loss incurred
by this tokenizer under any unigram model is suboptimal. In the next section,
we flesh out formally what it means for a tokenizer to “learn patterns” in the
source process well.

####  4.1 Learning patterns in the source

The main result of this section is a generic reduction: dictionaries which
typically encode new strings into a few long tokens (defined in a formal sense
in Theorem 4.3), result in tokenizers achieving near-optimal cross-entropy
loss. We prove this result for Markovian sources under a regularity
assumption, which is that the associated connectivity graph of the chain is
complete. The analogous assumption for $k^{\text{th}}$-order sources is that
the transition kernel is entry-wise bounded away from $0$. This assumption is
satisfied by all the sources considered in the paper thus far, such as the
$k^{\text{th}}$-order switching processes in Figure 1.

######  Assumption 4.2 (Data generating process).

Assume that the data source is an ergodic Markov process with transition
$P(\cdot|\cdot)$ and stationary distribution $\pi$. Assume that
$\min_{a,a^{\prime}\in\mathcal{A}}P(a^{\prime}|a)\triangleq\delta>0$.

For a substring $\bm{s}$ and a character $a$, define
$P(\bm{s}|a)=P(\bm{s}_{1}|a)\prod_{i=2}^{|\bm{s}|}P(\bm{s}_{i}|\bm{s}_{i-1})$
denote the conditional probability of the substring $\bm{s}$. We now state the
main result of this section.

######  Theorem 4.3 (Bound on cross-entropy loss of dictionaries under greedy
encoder).

Consider a source satisfying Assumption 4.2 and any tokenizer $\mathcal{T}$
equipped with the greedy encoder, $\textsf{enc}_{\text{gre}}(\cdot)$ with
finitely long tokens. Define, $P(\bm{t})=\mathbb{E}_{a\sim\pi}[P(\bm{t}|a)]$
and suppose $H(Q_{\text{MLE}},P)\geq\frac{1}{\varepsilon}\log(1/\delta)$ for
some $\varepsilon<1$. Then,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}_{\text{gre}}(\cdot))\leq\frac{\min_{Q}\mathcal{L}(Q)}{1-\varepsilon}.$
(11)

###### Interpretation.

$H(Q_{\text{MLE}},P)=\mathbb{E}_{\bm{t}\sim
Q_{\text{MLE}}}[\log(1/P(\bm{t}))]$ is large when the encoder places higher
mass (i.e. larger values of $Q_{\text{MLE}}(\cdot)$) on tokens which have low
probability under $P$, i.e. which correspond to longer substrings.
Intuitively, this metric is higher for tokenizers which typically use long
tokens (i.e. low $P(\cdot)$) to encode new strings. This is closely related to
the notion of fertility (Scao et al., 2022).

####  4.2 LZW tokenizer

In this section we study the Lempel-Ziv-Welch (LZW) based tokenization scheme
introduced by Zouhar et al. (2023a) and establish guarantees of the form of
Theorem 4.1 for this tokenizer.

######  Definition 4.4 (LZW tokenizer).

Iterating from left to right, the shortest prefix of the training dataset
which does not already exist as a token is assigned as the next token in the
dictionary. This substring is removed and the process is iterated on the
remainder of the dataset. The tokenizer uses the greedy encoding algorithm
(Definition A.2) to encode new strings into tokens.

An example of the LZW tokenizer: For the source dataset $0100111$, the
dictionary created is $\\{0,1,00,11\\}$.

The LZW tokenizer is based on the LZW algorithm for compression (Ziv and
Lempel, 1978; Welch, 1984). The dictionary satisfies the property that if some
substring $\bm{s}^{\prime}$ exists as a token in the dictionary, then all of
its prefixes must also belong to the dictionary. In the next theorem, we show
that the LZW tokenizer is approximately optimal.

######  Theorem 4.5.

Suppose the LZW tokenizer is trained on a dataset of length at most $d$
(thereby learning a dictionary with at most $d$ tokens). For Markov sources
satisfying Assumption 4.2, with probability $\geq 1-d^{-O_{\delta}(\log(d))}$,
the resulting tokenizer satisfies,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\cdot\textsf{enc}_{\text{gre}}(\cdot))\leq\frac{\min_{Q}\mathcal{L}(Q)}{1-\varepsilon}.$
(12)

where $\varepsilon=\frac{\log(1/\delta)}{0.99\log(d)}$444The constant $0.99$
can be made arbitrarily close to $1$..

The proof of this result considers all substrings $\bm{t}$ with $P(\bm{t})\geq
1/d^{0.99}$. These substrings are reasonably high probability and observed
many times in a dataset of $\widetilde{\Omega}(d)$ characters. We show that
with high probability, the LZW tokenizer learns all of these substrings as
tokens in the dictionary. Now, when processing a new string, since the greedy
algorithm only emits the longest substring which matches a token, every token
allocated must fall on the “boundary” of this set, having $P(\bm{t})\leq
O(1/d^{0.99})$. By definition, this means that
$H(Q_{\text{MLE}},P)=\mathbb{E}_{\bm{t}\sim
Q_{\text{MLE}}}[\log(1/P(\bm{t}))]=0.99\log(d)$. Combining this with Theorem
4.3 completes the proof. At a high level, on the infinite tree of substrings
$\mathcal{A}^{\star}$ we study which nodes are populated as tokens by LZW.
This structure forms a Digital Search Tree (DST) and prior work analyzes the
mean and variance of the profile of the DST under various source processes
(Jacquet et al., 2001; Drmota and Szpankowski, 2011; Hun and Vallée, 2014;
Drmota et al., 2021). A detailed proof of Theorem 4.5 is provided in Section
A.5.

####  4.3 Sequential variant of BPE

The Byte-Pair-Encoding (BPE) algorithm (Gage, 1994; Sennrich et al., 2016),
discovered in the compression literature as RePAIR (Larsson and Moffat, 2000;
Navarro and Russo, 2008) was proposed as a faster alternative to LZW. It
remains as one of the most commonly implemented tokenizers in natural language
processing for various downstream tasks (Radford et al., 2019; Mann et al.,
2020; Touvron et al., 2023). A large proportion of open source and commercial
LLMs currently use BPE as the tokenization algorithm of choice, such as
GPT-2/3, Llama 1/2 and Mistral-7B to name a few.

The BPE algorithm is based on constructing the dictionary iteratively by
merging pairs of tokens to result in a tokens. In each iteration, the pair of
tokens which appear most frequently next to each other are merged together
into a single token. Subsequently, every occurrence of the pair of tokens are
replaced by the newly added token, breaking ties arbitrarily. The dictionary
is thus an ordered mapping of the form
$\bm{t}\leftarrow(\bm{t}^{\prime},\bm{t}^{\prime\prime})$. To encode a new
string, the BPE encoder iterates through the dictionary and for each rule
$\bm{t}\leftarrow(\bm{t}^{\prime},\bm{t}^{\prime\prime})$ replaces every
consecutive occurrence of $\bm{t}^{\prime}$ and $\bm{t}^{\prime\prime}$ by the
token $\bm{t}$ breaking ties arbitrarily.

To warm up our main results, it is worth understanding the behavior of the BPE
tokenizer in a bit more detail. Unlike the toy tokenizer, it is a priori
unclear whether unigram models trained on sequences tokenized by BPE even
asymptotically (in the dictionary size) achieve the optimal cross-entropy
loss. Indeed, for $\delta>0$, consider a training sequence of length $m$ of
the form,

$\bm{s}=\underbrace{\left(\underbrace{01\cdots
01}_{2/\delta}\underbrace{10\cdots
10}_{2/\delta}\right)}_{\times\frac{m\delta}{4}}$ (13)

The probability that this sequence is generated by the order-$2$ switching
Markov source with $p=q=\delta$ is,

$\displaystyle\approx(1-\delta)^{\frac{m\delta}{4}\times\frac{4}{\delta}\times(1-\delta)}(\delta)^{\frac{m\delta}{4}\times
4}=e^{-H(P)},$ (14)

which uses the fact that
$H(P)=m\delta\log(1/\delta)+m(1-\delta)\log(1/(1-\delta))$. This implies that
even though the string has exponentially small probability, it is one of the
typical sequences for this order-$2$ Markov source. Let’s understand what
happens when the BPE tokenizer is trained on this dataset. Assuming that ties
are broken arbitrarily, consider the run of the BPE algorithm detailed in
Table 1. Here, we assume that $1/\delta-1$ is a power of $2$ and denote
$r=\log_{2}(1/\delta-1)$. The algorithm first merges $0$ and $1$ into a single
token $\bm{t}_{1}$, which results in a long sequence of the form
$\bm{t}_{1}\cdots\cdots\bm{t}_{1}1\bm{t}_{1}\cdots\cdots\bm{t}_{1}0$ repeated
$m\delta/4$ times. In subsequent rounds, the tokens $(\bm{t}_{1},\bm{t}_{1})$
is merged into $\bm{t}_{2}$, then $(\bm{t}_{2},\bm{t}_{2})$ is merged into
$\bm{t}_{3}$ and so on, until is no longer possible. Finally, the resulting
sequence is a repeating sequence of $5$ tokens where within each sequence, no
pair of tokens appears more than once next to each other. Eventually these $5$
tokens are merged into a single token labelled $\bm{t}_{r+4}$, and in
subsequent rounds the tokens $(\bm{t}_{r+4},\bm{t}_{r+4})$ are merged into
$\bm{t}_{r+5}$, $(\bm{t}_{r+5},\bm{t}_{r+5})$ is merged into $\bm{t}_{r+6}$
and so on, until is no longer possible.

Initial | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}01\cdots\cdots 01}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}10\cdots\cdots 10}|\cdots$
---|---
$\bm{t}_{1}\leftarrow(0,1)$ | $\bm{t}_{1}\cdots\cdots\bm{t}_{1}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}\bm{t}_{1}\cdots\cdots\bm{t}_{1}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0}|\cdots$
$\bm{t}_{2}\leftarrow(\bm{t}_{1},\bm{t}_{1})$ | $\bm{t}_{2}\cdots\bm{t}_{2}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}\bm{t}_{2}\cdots\bm{t}_{2}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0}|\cdots$
$\vdots$ | $\vdots$
$\bm{t}_{r}\leftarrow(\bm{t}_{r-1},\bm{t}_{r-1})$ | $\bm{t}_{r}\bm{t}_{1}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}\bm{t}_{r}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0}|\cdots$
$\bm{t}_{r+1}\leftarrow(\bm{t}_{r},\bm{t}_{1})$ | $\bm{t}_{r+1}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}\bm{t}_{r}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0}|\cdots$
$\bm{t}_{r+2}\leftarrow(\bm{t}_{r},0)$ | $\bm{t}_{r+1}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}\bm{t}_{r+2}|\cdots$
$\bm{t}_{r+3}\leftarrow(\bm{t}_{r+1},1)$ | $\bm{t}_{r+3}\bm{t}_{r+2}|\cdots$
$\bm{t}_{r+4}\leftarrow(\bm{t}_{r+3},\bm{t}_{r+2})$ | $\bm{t}_{r+4}|\cdots$
$\bm{t}_{r+5}\leftarrow(\bm{t}_{r+4},\bm{t}_{r+4})$ | $\bm{t}_{r+5}|\cdots$
$\bm{t}_{r+6}\leftarrow(\bm{t}_{r+5},\bm{t}_{r+5})$ |  $\bm{t}_{r+6}|\cdots$.
$\vdots$ | $\vdots$
Table 1: A representation of the behavior of BPE when trained on the dataset
in eq. 13. We assume that $1/\delta-1$ is a power of $2$ and define
$r=\log_{2}(1/\delta-1)$.

Observe that in the initial training dataset the substrings $0000$ and $1111$
never appears as a contiguous sequence. However, in a test sequence of length
$m$ sampled from the $2^{\text{nd}}$-order Markov source, with high
probability these substrings disjointly occur $\Theta(m)$ times each. The
learnt dictionary associates each such disjoint occurrence of these substrings
with at least $1$ token, for $0000$, the $3^{\text{rd}}$ $0$ must necessarily
be tokenized as the token “$0$”. Likewise, in $1111$, the $3^{\text{rd}}$ $1$
must necessarily be tokenized as the token “$1$”. Therefore, when a new test
string of length $m$ is tokenized, with high probability the tokens “$0$” and
“$1$” form a constant fraction of the total collection of tokens.

Thus on freshly sampled test sequences, the BPE tokenizer appears to behave
like the character-level tokenizer on a constant fraction of the input
sequence. In particular, a simple calculation shows that the cross-entropy
loss of any unigram model trained on this tokenizer must be far from the
optimal bound of $mH_{\textsc{Ber}}(\delta)$ especially as $\delta$ becomes
smaller,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))$
(15)
$\displaystyle\geq\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathbb{E}\left[n_{0}\log(1/Q_{\text{tok}}(0)+n_{1}\log(1/Q_{\text{tok}}(1)\right]$
(16)
$\displaystyle\overset{(i)}{\geq}\Omega(m)\cdot\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\left(\log(1/P_{\text{tok}}(0)+\log(1/Q_{\text{tok}}(1)\right)$
(17) $\displaystyle\geq\Omega(m).$ (18)

where $(i)$ uses the fact that
$\mathbb{E}[n_{0}],\mathbb{E}[n_{1}]\in\Omega(m)$ and the last inequality uses
$P_{\text{tok}}(0)P_{\text{tok}}(1)\leq 1/4$ (AM-GM inequality) since they sum
up to at most $1$. The purpose of this example is to show that there exist
pathological training datasets which appear to be drawn from a stochastic
source, but on which BPE fails to learn a good dictionary for the source. Thus
proving a result such as Theorem 4.1 for BPE would require arguing that
training datasets such as that in eq. 13 are unlikely to be seen.

The analysis of the standard variant of BPE turns out to be complicated for
other reasons too. After every token is added the training dataset becomes a
mix of all the previously added tokens, and arguing about the statistics of
which pair of tokens appears most frequently for the next iteration becomes
involved. For instance, adding $00$ as a token may reduce the frequency of
occurrence of the substring $01$, but will not affect $11$. Thus, even though
$01$ may a priori have been seen more frequently, it may not be chosen by BPE
as the next token after $00$.

To avoid dealing with these issues, we consider a sequential/sample-splitting
variant of BPE. At a high level, the algorithm breaks down a dataset of size
$\Theta(d^{2})$ into $d$ chunks and learns at most $1$ token from each chunk.
The algorithm iterates over the chunks and finding the pair of tokens which
appear most frequently next to each other in each chunk and adding it to the
dictionary if it appears more than $\log(d)$ times. Every consecutive
occurrence of the pair of tokens is replaced by the newly assigned token in
the dataset. Thus, in each iteration $i$, at most $1$ token is added,
depending on the statistics of the $i^{\text{th}}$ chunk and the tokens added
so far to the dictionary. Based on the final size of the dictionary a
different encoder/decoder pair is used - if the algorithm adds sufficiently
many tokens to the dictionary, the greedy encoder is used, and if not, a
parallel implementation of BPE’s encoding algorithm is used (Definition 4.6).
A formal description of the algorithm is in Algorithm 1.

######  Definition 4.6 (BPE.split encoder).

The BPE.split encoder parses a new string into tokens as follows. The
algorithm partitions the string into contiguous chunks of length $d$. Then,
BPE’s encoder is applied on each chunk, which iterates through DS and replaces
$\bm{t}^{\prime}\bm{t}^{\prime\prime}$ by $\bm{t}$ for every rule
$\bm{t}\leftarrow(\bm{t}^{\prime},\bm{t}^{\prime\prime})$ in DS, breaking ties
arbitrarily. The individual token sequences are finally spliced together and
returned.

Algorithm 1 Sequential implementation of BPE

Input: $\epsilon\in(0,1)$; a dataset of size $n=\Theta(d^{2})$, split into $d$
contiguous texts $\\{\textsf{text}_{1},\cdots,\textsf{text}_{d}\\}$ of length
$\Theta(d)$ each.

Output: A tokenizer $\mathcal{T}$.

// Generate Dictionary

for $i=1,\cdots,d$ do

if $\exists$ a pair of tokens/characters
$(\bm{t}^{\prime},\bm{t}^{\prime\prime})$ appearing $\geq\log(d)$ times
consecutively in $\textsf{text}_{i}$ then

Append the rule $\bm{t}\leftarrow(\bm{t}^{\prime},\bm{t}^{\prime\prime})$ to
DS

for $j=i+1,\cdots,d$ do

$\textsf{text}_{j}\leftarrow\textsf{APPLY}_{\bm{t}\leftarrow(\bm{t}^{\prime},\bm{t}^{\prime\prime})}(\textsf{text}_{j})$;

// Can be implemented in parallel

end for

end if

end for

// Encoder and Decoder

if $|\textsf{Dict}|<d_{0}\triangleq\epsilon d/2\log(4|\mathcal{A}|)$ then

$\mathcal{T}\leftarrow(\textsf{Dict},\textsf{DS},\textsf{enc}_{\text{BPE.split}}(\cdot),\textsf{dec}_{\text{BPE.split}}(\cdot))$

else

$\mathcal{T}\leftarrow(\textsf{Dict},\emptyset,\textsf{enc}_{\text{gre}}(\cdot),\textsf{dec}_{\text{gre}}(\cdot))$

end if

def $\textsf{APPLY}_{\bm{t}\leftarrow(\bm{t}_{1},\bm{t}_{2})}(\textsf{text})$:

Replace every consecutive occurrence of
$(\bm{t}^{\prime},\bm{t}^{\prime\prime})$ in text by $\bm{t}$, breaking ties
arbitrarily.

The main result of this section is that up to a small additive error,
Algorithm 1 approaches a $2$-approximation to the optimal cross-entropy loss.

######  Theorem 4.7.

For any $\epsilon\in(0,1)$, run Algorithm 1 on a dataset of $n=\Theta(d^{2})$
characters to learn a dictionary with at most $d$ tokens. The resulting
tokenizer $\mathcal{T}$ satisfies with probability $\geq
1-e^{-\Omega(d\epsilon^{2})}$,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}(\cdot))\leq(2+\varepsilon)\min_{Q}\mathcal{L}(Q)+\epsilon$
(19)

where
$\varepsilon=O\left(\frac{\log(1/\epsilon)\log^{3}(1/\delta)}{\epsilon\delta^{9}\log(d)}\right)$.

While the guarantees established for the sequential BPE tokenizer are weaker
than those in Theorem 4.1, the analysis turns out to be quite involved.
Theorem 4.7 implies that unigram models trained on the sequential BPE
tokenizer asymptotically approach the optimal cross-entropy loss up to a
factor of $2$.

The formal proof of this result is presented in Appendix B. What is the
intuition behind using a different encoder in Algorithm 1 depending on the
number of tokens in the dictionary? When the number of tokens in the
dictionary is smaller than $d_{0}$, we know that on a $1-d_{0}/d$ fraction of
the iterations of Algorithm 1, a token is not added to the dictionary, i.e.
every pair of tokens already appears at most $\log(d)$ times together. This is
a datapoint of “evidence” that under the dictionary in that iteration, the BPE
encoder is already good at encoding new strings (of length $\Theta(d)$) in a
way where pairs of tokens do not appear consecutively with high frequency.
Since future dictionaries only have more rules appended to them, dictionaries
only get better at encoding new strings into tokens where pairs do not
frequently appear consecutively. In other words, the BPE encoder satisfies a
monotonicity property. It remains to show that dictionaries which encode new
sequences in a way where no pair of tokens appear too frequently have large
$H(Q_{\text{MLE}},P)$ (to invoke Theorem 4.3). This follows from ideas
introduced in (Navarro and Russo, 2008).

The case where the number of tokens is large ($\geq d_{0}$) turns out to
present significant technical challenges for analyzing the BPE encoder. There
is no longer much “evidence” that the dictionary in each iteration is good at
encoding strings since in a large number of iterations a pair of tokens appear
consecutively with high frequency. Analyzing the greedy encoder also presents
its own challenges - although the algorithm has allocated a large number of
tokens, it is possible that there are short tokens $\bm{t}$ which are maximal
(i.e. they are not prefixes of other tokens). This is similar to the problem
encountered by BPE when trained on the dataset in eq. 13 \- although the
algorithm has allocated a large number of tokens, the token $1$ is maximal
since every other token begins with the character $0$. However, it turns out
that such tokens, although present in the dictionary, are not observed
frequently while encoding a fresh string drawn from the source.

###  5 Additional theoretical results

In this section, we discuss some additional results which are fleshed out in
more detail in Appendices C, D and E.

####  5.1 Finite sample considerations

The results in Section 4 focus on the analysis in the case where the
downstream likelihood model is trained optimally. In practice, however,
transformers are trained on finite datasets and not likely to be optimal. In
this section, we focus on understanding the role of a finite dataset from a
theoretical point of view. While the results in Theorem 4.1 indicate that a
larger dictionary size is better in that the best unigram model achieves
better cross-entropy loss, this statement ignores finite-sample considerations
in training this model itself. In Appendix C, for the LZW dictionary, we show
that the number of samples required to learn this model to a multiplicative
error of $1+\xi$, $n_{\text{lm}}^{\star}$, scales as
$\widetilde{O}(d^{1.01}/\delta\xi^{2})$. In other words, given
$n^{\star}_{\text{lm}}$ samples, with high probability, it is possible to
learn a model $\widehat{Q}$ such that,

$\displaystyle\mathcal{L}(\widehat{Q}\circ\textsf{enc}_{\text{gre}}(\cdot))\leq(1+\xi)\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}_{\text{gre}}(\cdot)).$
(20)

where $\textsf{enc}(\cdot)$ is the greedy encoder on an LZW dictionary of size
$d$ learnt from data. This result indicates that it is easier to train the
downstream likelihood model on smaller dictionaries. In conjunction with
Theorem 4.1, this implies that there is an optimal dictionary size $d^{\star}$
for LZW which depends on $\delta$ and the size of the training dataset the
learner has access to, which balances the limiting statistical error
corresponding to a dictionary size of $d^{\star}$ with the finite sample error
incurred in learning a likelihood model corresponding supported on $d^{\star}$
tokens. While our results do not establish these guarantees for transformers
and are instead for a different finite-sample estimator of the optimal unigram
model, it is an interesting direction for future research to characterize the
learning trajectory and limiting statistical error of transformers trained
with gradient descent.

####  5.2 The generalization ability of tokenizers

In this paper, we focus on tokenizers learnt from data, which are used to
encode fresh strings which were not trained on previously. In previous work
interpreting tokenizers from a theoretical point of view, this element of
generalization to new strings has been missing. For instance, the work of
Zouhar et al. (2023b) show that the BPE algorithm is essentially an
approximation algorithm for the objective of finding the shortest encoding of
the training dataset as a sequence of token merges. While this perspective is
useful in formalizing the notion of compression BPE carries out, the
characterization is ultimately with respect to the training dataset, and not
in BPE’s ability to compress fresh strings. In Appendix D we show that there
are tokenization algorithms which are extremely good at compressing the
dataset they were trained on, but on new strings, the tokenizer behaves like a
character tokenizer almost everywhere. As a consequence transformers trained
on the output of this tokenizer would fail to approach the optimal cross-
entropy loss and in fact get stuck close to the loss of $mH(\pi)$ loss
achieved by the character level tokenizer in Theorem 2.1.

####  5.3 Interaction between dictionary and encoder

The choice of tokenizer in language modeling has received a large degree of
study in various domains (Rust et al., 2021; Toraman et al., 2023) and is
identified as a step that has been overlooked in designing performant LLMs
(Mielke et al., 2021; Wu et al., 2023). While typically this has come to imply
using different tokenization algorithms altogether, it is important to note
that the tokenizer is composed of two parts - the dictionary and the encoding
algorithm, and the interaction between the two may result in differently
performing end-to-end models. In Appendix E, we show that there exist
dictionaries which generalize well under one encoder, in that unigram models
trained on string encoded by this dictionary perform near-optimally, but these
dictionaries completely fail to generalize under a different encoder. This
means that in the process of designing good tokenizers, it does not suffice to
think about the dictionary in isolation. Its interaction with the encoding
algorithm is pertinent.

###  6 Experimental Results

In this section we discuss experimental results; hyperparameter choices and
other details are presented in Appendix F.

((a)) Convergence rate of smallest model which is within $10\%$ of the
optimal-cross entropy by $300$ epochs. The smallest untokenized model has
$9010$ parameters ($3$ layers, embedding dimension = $10$). The smallest
tokenized model with a dictionary size of $10$ has $17880$ parameters ($3$
layers, embedding dimension $=20$). The tokenized model has more parameters
but the wall-clock time taken to reach any loss value is smaller.

((b)) Convergence rate of models with the same embedding dimension ($20$),
number of heads ($1$) and layers ($3$) with and without tokenization. The
model with tokenization (dictionary size of $20$) appears to converge more
quickly, but the error floor is subtly higher compared to the model without
tokenization. Both models are trained on input sequences of length $512$. The
width of the tokenized model is smaller ($145$).

Figure 4: Test loss vs. wall-clock time for the tokenized and untokenized
models when trained on the order-$1$ switching Markov chain (Figure 1) with
$p=q=0.8$. The tokenizer used is BPE.

###### Experiment 1 (Figures 4(a) and 4(b))

In this experiment we study the order-$1$ switching Markov chain (with
$p=q=0.8$). Transformers without tokenization empirically achieve a small
cross-entropy on this learning task as seen in Figure 4(a) and earlier in
Makkuva et al. (2024). We vary a number of hyperparameters to find the
smallest untokenized model which achieves a loss within $10\%$ of the optimal-
cross entropy within the first $300$ epochs. Fixing a token dictionary size of
$20$, we also find the smallest tokenized model which achieves the same loss
metric. Although the smallest model with tokenization is larger than the
smallest model without tokenization in terms of the number of parameters, the
wall-clock time taken to optimize the model to any target test loss is
observed to be smaller. Thus, tokenization appears to reduce the compute time
required to train the model to a target test loss in the toy example we
consider. In contrast, in Figure 4(b) we compare models with the same
architecture trained with and without tokenization555The model with
tokenization has width equal to the typical length of sequences after
encoding, which is smaller.. The model with tokenization again appears to
converge more quickly, although the limiting error achieved is subtly higher
in comparison with the model without tokenization. By making the model with
tokenization larger, we can tradeoff the convergence speed (in wall-clock
time) with the limiting error.

Next, we present an evaluation of tokenizers on real world datasets. Since
evaluating the end-to-end pipeline requires training a transformer which is
computationally intensive at medium and large scale datasets, we resort to
evaluating tokenizers on $k$-gram models at these scales.

###### Experiment 1 (Figure 5).

Since pre-training In this experiment, we train tokenizers on the
Wikitext-103-raw-v1 dataset (Merity et al., 2016) and compare the performance
of unigram models trained on the GLUE dataset as the model size scales. In
this experiment, we do not evaluate the likelihood model on test sequences,
rather, we estimate the cross-entropy of the best unigram model by using the
approximation,

$\displaystyle-\mathbb{E}\Bigg{[}\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}\log
Q_{\text{MLE}}(\bm{t})\Bigg{]}{\approx}-\sum_{\bm{t}\in\textsf{Dict}}\widehat{n}_{\bm{t}}\log(\widehat{Q}(\bm{t}))$
(21)

where
$\widehat{Q}(\bm{t})=\frac{\widehat{n}_{\bm{t}}}{\sum_{\bm{t}}\widehat{n}_{\bm{t}}}$
is the MLE unigram model learnt from a finite dataset, which we choose here as
GLUE (Wang et al., 2019), and $\widehat{n}_{\bm{t}}$ is the number of times
the token $\bm{t}$ is observed in the encoding of the dataset. This
approximation allows us to separate the error stemming from learning a
suboptimal likelihood model which tends to have higher sample complexity
requirements and focus on the asymptotic error of the tokenizer. Since the
character-level tokenizer operates on a fixed vocabulary, in order to compare
with the other tokenizers, we plot the number of unique $k$-grams observed in
the training dataset along the $x$-axis. While this is not an apples-to-apples
comparison, we use the number of unique $k$-grams in the dataset as a proxy
for the complexity of the likelihood model trained. One may also use the total
number of possible $k$-grams as a proxy; however a large fraction of these
$k$-grams would likely never be observed in a real dataset (especially as $k$
grows).

Figure 5: Performance vs. dictionary size. All tokenizers are trained on the
Wikitext-103 dataset with early stopping when the desired vocabulary size is
met. For all other tokenizers we train unigram models while for the the
character-level tokenizer, we train $k$-gram models for $k\in\\{1,2,3,4\\}$.
In all cases, the GLUE dataset is used to learn the likelihood model. The
number in the parentheses denotes the number of distinct observed $k$-grams,
which lower bounds the $k$-gram model complexity.

###### Experiment 2 (Table 2).

In this experiment, we compare the cross entropy loss of the best unigram
model trained on pre-trained tokenizers on an array of datasets. All the
considered tokenizers have dictionary sizes in the range 31K-51K. On the The
best bigram model under the character tokenizer is consistently outperformed
by the best unigram likelihood model trained under a number of pre-trained
tokenizers on a variety of datasets: Rotten Tomatoes (8.5K sequences), GLUE
(105K), Yelp review (650K), Wikitext-103-v1 (1.8M), OpenOrca (2.9M).

| RT | Wiki | OpenOrca | Yelp | GLUE
---|---|---|---|---|---
BERT tokenizer | 1.58 | 1.55 | 1.50 | 1.60 | 1.50
Tinyllama | 1.75 | 1.84 | 1.75 | 1.82 | 1.70
GPT-neox-20b | 1.57 | 1.64 | 1.60 | 1.66 | 1.48
Mixtral-8x7b | 1.69 | 1.80 | 1.71 | 1.75 | 1.66
Phi-2 tokenizer | 1.54 | 1.62 | 1.60 | 1.64 | 1.45
Char + bigram | 2.40 | 2.45 | 2.49 | 2.46 | 2.38
Table 2: Cross-entropy loss estimates (using eq. 21) of unigram models trained
on pre-trained tokenizers under a number of datasets. The last row (blue) is
the character level tokenizer, on which a more powerful bigram model is
trained. The table indicates that tokenization allows training unigram models
which perform better than bigram models without tokenization. BERT is based on
Wordpiece, Tinyllama, GPT-neox-20b and Mixtral-8x7b are based on BPE. The
character-level tokenizer we use is ByT5.

###  7 Conclusion

In this paper, we present a theoretical framework to compare and analyze
different tokenization algorithms. We study the end-to-end cross-entropy loss
of the tokenizer + likelihood model, and focus on the case where the data
generating process is Markovian. The main result we establish in this paper is
that algorithms such as LZW and a sequential variant of BPE learn tokenizers
such that the best unigram likelihood model trained on them approaches the
cross-entropy loss of the optimal likelihood model, as the vocabulary size $d$
grows. We show that these tokenizers can be learned from a training dataset
with $\textsf{poly}(d)$ samples. This provides evidence toward the thesis that
tokenizers enable conceptually simpler models to perform better (unigram vs.
bigram), even if the number of parameters in the resulting model may not be
fewer.

### References

  * Ali et al. (2023) Mehdi Ali, Michael Fromm, Klaudia Thellmann, Richard Rutmann, Max Lübbering, Johannes Leveling, Katrin Klug, Jan Ebert, Niclas Doll, Jasper Schulze Buschhoff, et al.  Tokenizer choice for llm training: Negligible or crucial?  _arXiv preprint arXiv:2310.08754_ , 2023.
  * Alyafeai et al. (2023) Zaid Alyafeai, Maged S Al-shaibani, Mustafa Ghaleb, and Irfan Ahmad.  Evaluating various tokenizers for arabic text classification.  _Neural Processing Letters_ , 55(3):2911–2933, 2023.
  * Braess and Sauer (2004) Dietrich Braess and Thomas Sauer.  Bernstein polynomials and learning theory.  _Journal of Approximation Theory_ , 128(2):187–206, 2004.
  * Chen (2018) Yen-Chi Chen.  Stochastic modeling of scientific data, Autumn 2018.
  * Clark et al. (2022) Jonathan H Clark, Dan Garrette, Iulia Turc, and John Wieting.  Canine: Pre-training an efficient tokenization-free encoder for language representation.  _Transactions of the Association for Computational Linguistics_ , 10:73–91, 2022.
  * Den et al. (2007) Yasuharu Den, Toshinobu Ogiso, Hideki Ogura, Atsushi Yamada, Nobuaki Minematsu, Kiyotaka Uchimoto, and Hanae Koiso.  The development of an electronic dictionary for morphological analysis and its application to japanese corpus linguistics, Oct 2007.  URL https://repository.ninjal.ac.jp/api/records/2201.
  * Drmota and Szpankowski (2011) Michael Drmota and Wojciech Szpankowski.  The expected profile of digital search trees.  _Journal of Combinatorial Theory, Series A_ , 118(7):1939–1965, 2011.
  * Drmota et al. (2021) Michael Drmota, Michael Fuchs, Hsien-Kuei Hwang, and Ralph Neininger.  Node profiles of symmetric digital search trees: Concentration properties.  _Random Structures & Algorithms_, 58(3):430–467, 2021.
  * Edelman et al. (2024) Benjamin L Edelman, Ezra Edelman, Surbhi Goel, Eran Malach, and Nikolaos Tsilivis.  The evolution of statistical induction heads: In-context learning markov chains.  _arXiv preprint arXiv:2402.11004_ , 2024.
  * Eisner et al. (2015) Tanja Eisner, Bálint Farkas, Markus Haase, and Rainer Nagel.  _Operator theoretic aspects of ergodic theory_ , volume 272.  Springer, 2015.
  * Gage (1994) Philip Gage.  A new algorithm for data compression.  _C Users Journal_ , 12(2):23–38, 1994.
  * Gallé (2019) Matthias Gallé.  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, 2019.
  * Golkar et al. (2023) Siavash Golkar, Mariel Pettee, Michael Eickenberg, Alberto Bietti, Miles Cranmer, Geraud Krawezik, Francois Lanusse, Michael McCabe, Ruben Ohana, Liam Parker, et al.  xval: A continuous number encoding for large language models.  _arXiv preprint arXiv:2310.02989_ , 2023.
  * Gray and Gray (2009) Robert M Gray and RM Gray.  _Probability, random processes, and ergodic properties_ , volume 1.  Springer, 2009.
  * Grefenstette and Tapanainen (1994) Gregory Grefenstette and Pasi Tapanainen.  What is a word, what is a sentence?: problems of tokenisation.  1994\.
  * Han et al. (2021) Yanjun Han, Soham Jana, and Yihong Wu.  Optimal prediction of markov chains with and without spectral gap.  _Advances in Neural Information Processing Systems_ , 34:11233–11246, 2021.
  * Hun and Vallée (2014) Kanal Hun and Brigitte Vallée.  Typical depth of a digital search tree built on a general source.  In _2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO)_ , pages 1–15. SIAM, 2014.
  * Itzhak and Levy (2021) Itay Itzhak and Omer Levy.  Models in a spelling bee: Language models implicitly learn the character composition of tokens.  _arXiv preprint arXiv:2108.11193_ , 2021.
  * Jacquet et al. (2001) Philippe Jacquet, Wojciech Szpankowski, and Jing Tang.  Average profile of the lempel-ziv parsing scheme for a markovian source.  _Algorithmica_ , 31:318–360, 2001.
  * Kharitonov et al. (2021) Eugene Kharitonov, Marco Baroni, and Dieuwke Hupkes.  How bpe affects memorization in transformers.  _arXiv preprint arXiv:2110.02782_ , 2021.
  * Kudo (2018) Taku Kudo.  Subword regularization: Improving neural network translation models with multiple subword candidates.  _arXiv preprint arXiv:1804.10959_ , 2018.
  * Larsson and Moffat (2000) N Jesper Larsson and Alistair Moffat.  Off-line dictionary-based compression.  _Proceedings of the IEEE_ , 88(11):1722–1732, 2000.
  * Libovickỳ et al. (2021) Jindřich Libovickỳ, Helmut Schmid, and Alexander Fraser.  Why don’t people use character-level machine translation?  _arXiv preprint arXiv:2110.08191_ , 2021.
  * Lin (2004) Chin-Yew Lin.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pages 74–81, 2004.
  * Makkuva et al. (2024) Ashok Vardhan Makkuva, Marco Bondaschi, Adway Girish, Alliot Nagle, Martin Jaggi, Hyeji Kim, and Michael Gastpar.  Attention with markov: A framework for principled analysis of transformers via markov chains.  _arXiv preprint arXiv:2402.04161_ , 2024.
  * Mann et al. (2020) Ben Mann, N Ryder, M Subbiah, J Kaplan, P Dhariwal, A Neelakantan, P Shyam, G Sastry, A Askell, S Agarwal, et al.  Language models are few-shot learners.  _arXiv preprint arXiv:2005.14165_ , 2020.
  * Merity et al. (2016) Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher.  Pointer sentinel mixture models.  _arXiv preprint arXiv:1609.07843_ , 2016.
  * 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, et al.  Between words and characters: A brief history of open-vocabulary modeling and tokenization in nlp.  _arXiv preprint arXiv:2112.10508_ , 2021.
  * Mourtada and Gaïffas (2022) Jaouad Mourtada and Stéphane Gaïffas.  An improper estimator with optimal excess risk in misspecified density estimation and logistic regression.  _The Journal of Machine Learning Research_ , 23(1):1384–1432, 2022.
  * Naor et al. (2020) Assaf Naor, Shravas Rao, and Oded Regev.  Concentration of markov chains with bounded moments.  2020\.
  * Navarro and Russo (2008) Gonzalo Navarro and Luís MS Russo.  Re-pair achieves high-order entropy.  In _DCC_ , page 537. Citeseer, 2008.
  * Nichani et al. (2024) Eshaan Nichani, Alex Damian, and Jason D Lee.  How transformers learn causal structure with gradient descent.  _arXiv preprint arXiv:2402.14735_ , 2024.
  * Palmer (2000) David D Palmer.  Tokenisation and sentence segmentation.  _Handbook of natural language processing_ , pages 11–35, 2000.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  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, 2002.
  * Parr (2013) Terence Parr.  _The Definitive ANTLR 4 Reference_.  Pragmatic Bookshelf, Raleigh, NC, 2 edition, 2013.  ISBN 978-1-93435-699-9.  URL https://www.safaribooksonline.com/library/view/the-definitive-antlr/9781941222621/.
  * Petrov et al. (2023) Aleksandar Petrov, Emanuele La Malfa, Philip HS Torr, and Adel Bibi.  Language model tokenizers introduce unfairness between languages.  _arXiv preprint arXiv:2305.15425_ , 2023.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Rumbelow and Watkins (2023) Jessica Rumbelow and Matthew Watkins.  Solidgoldmagikarp.  https://www.alignmentforum.org/posts/aPeJE8bSo6rAFoLqg/solidgoldmagikarp-plus-prompt-generation, 2023.
  * Rust et al. (2021) Phillip Rust, Jonas Pfeiffer, Ivan Vulić, Sebastian Ruder, and Iryna Gurevych.  How good is your tokenizer? on the monolingual performance of multilingual language models.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3118–3135, 2021.
  * Scao et al. (2022) Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, et al.  Bloom: A 176b-parameter open-access multilingual language model.  _arXiv preprint arXiv:2211.05100_ , 2022.
  * Schuster and Nakajima (2012) Mike Schuster and Kaisuke Nakajima.  Japanese and korean voice search.  In _2012 IEEE international conference on acoustics, speech and signal processing (ICASSP)_ , pages 5149–5152. IEEE, 2012.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch.  Neural machine translation of rare words with subword units.  In Katrin Erk and Noah A. Smith, editors, _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany, August 2016. Association for Computational Linguistics.  doi: 10.18653/v1/P16-1162.  URL https://aclanthology.org/P16-1162.
  * Singh and Strouse (2024) Aaditya K Singh and DJ Strouse.  Tokenization counts: the impact of tokenization on arithmetic in frontier llms.  _arXiv preprint arXiv:2402.14903_ , 2024.
  * Tolmachev et al. (2018) Arseny Tolmachev, Daisuke Kawahara, and Sadao Kurohashi.  Juman++: A morphological analysis toolkit for scriptio continua.  In Eduardo Blanco and Wei Lu, editors, _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 54–59, Brussels, Belgium, November 2018. Association for Computational Linguistics.  doi: 10.18653/v1/D18-2010.  URL https://aclanthology.org/D18-2010.
  * Toraman et al. (2023) Cagri Toraman, Eyup Halit Yilmaz, Furkan Şahinuç, and Oguzhan Ozcelik.  Impact of tokenization on language models: An analysis for turkish.  _ACM Transactions on Asian and Low-Resource Language Information Processing_ , 22(4):1–21, 2023.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Wang et al. (2019) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  2019\.  In the Proceedings of ICLR.
  * Welch (1984) Terry A. Welch.  A technique for high-performance data compression.  _Computer_ , 17(06):8–19, 1984.
  * Wolff (1975) J Gerard Wolff.  An algorithm for the segmentation of an artificial language analogue.  _British journal of psychology_ , 66(1):79–90, 1975.
  * Wu et al. (2023) Shijie Wu, Ozan Irsoy, Steven Lu, Vadim Dabravolski, Mark Dredze, Sebastian Gehrmann, Prabhanjan Kambadur, David Rosenberg, and Gideon Mann.  Bloomberggpt: A large language model for finance.  _arXiv preprint arXiv:2303.17564_ , 2023.
  * Xue et al. (2022) Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel.  Byt5: Towards a token-free future with pre-trained byte-to-byte models.  _Transactions of the Association for Computational Linguistics_ , 10:291–306, 2022.
  * Yu et al. (2021) Sangwon Yu, Jongyoon Song, Heeseung Kim, Seong-min Lee, Woo-Jong Ryu, and Sungroh Yoon.  Rare tokens degenerate all tokens: Improving neural text generation via adaptive gradient gating for rare token embeddings.  _arXiv preprint arXiv:2109.03127_ , 2021.
  * Zheng et al. (2023) Wenqing Zheng, SP Sharan, Ajay Kumar Jaiswal, Kevin Wang, Yihan Xi, Dejia Xu, and Zhangyang Wang.  Outline, then details: Syntactically guided coarse-to-fine code generation.  In _International Conference on Machine Learning_ , pages 42403–42419. PMLR, 2023.
  * Ziv and Lempel (1978) Jacob Ziv and Abraham Lempel.  Compression of individual sequences via variable-rate coding.  _IEEE transactions on Information Theory_ , 24(5):530–536, 1978.
  * Zouhar et al. (2023a) Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Mrinmaya Sachan, and Ryan Cotterell.  Tokenization and the noiseless channel.  In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 5184–5207, Toronto, Canada, July 2023a. Association for Computational Linguistics.  doi: 10.18653/v1/2023.acl-long.284.  URL https://aclanthology.org/2023.acl-long.284.
  * Zouhar et al. (2023b) Vilém Zouhar, Clara Meister, Juan Luis Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, and Ryan Cotterell.  A formal perspective on byte-pair encoding.  _arXiv preprint arXiv:2306.16837_ , 2023b.

## Appendix

###  Appendix A Analysis of LZW: Proofs of Theorems 4.3 and 4.5

####  A.1 Notation and definitions

For each character $a\in\mathcal{A}$ let $\mathcal{T}^{\star}_{a}$ denote an
infinite tree, with root vertex $\emptyset$, and subsequent vertices labelled
by strings $\bm{t}\in\mathcal{A}^{\star}$. The edge from a parent vertex
$\bm{t}$ to any child $\bm{t}a^{\prime}$ is labelled with the probability
$P(\bm{t}a^{\prime}|\bm{t})$ unless $\bm{t}=\emptyset$, in which case the edge
probability is $P(a^{\prime}|a)$. An infinite trajectory sampled on the tree
$\mathcal{T}_{a}^{\star}$ corresponds to an infinite string sampled from the
stochastic source conditioned on the first character of the string being $a$.
In this paper we only consider ergodic sources [Gray and Gray, 2009] for which
we can define the “entropy rate”. The entropy rate fundamentally captures the
compressibility of the source, and can be defined as
$H_{\infty}\triangleq\lim_{m\to\infty}\frac{1}{m}H(P)$ where $\bm{s}$ is a
length $m$ string drawn from the source. By Theorem 2.1, $H_{\infty}$,
captures $\min_{Q}\mathcal{L}(Q)$.

####  A.2 Proof of Theorem 2.1

We first characterize the minimum achievable cross-entropy loss
$\mathcal{L}_{m}(Q)$ without any restrictions on the likelihood model class
$\mathcal{Q}$. Choosing $Q(\textsf{enc}(\bm{s}))=Q(\bm{s})=P(\bm{s})$, the
true probability of the sequence $\bm{s}$, we have
$\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))=H(\bm{s})$ where $H(\cdot)$ is the
entropy function. It is not that difficult to see that this is also the
minimum cross-entropy loss that can be achieved. For any distribution $Q$,

$\displaystyle\mathcal{L}_{m}(Q)$ $\displaystyle=\mathbb{E}[\log(1/Q(\bm{s})]$
(22)
$\displaystyle=\mathbb{E}[\log(P(\bm{s})/Q(\bm{s})]+\mathbb{E}[\log(1/P(\bm{s}))]$
(23) $\displaystyle=H(P)+D_{\text{KL}}(P\|Q).$ (24)

On the other hand, the cross-entropy loss under any unigram model
$Q\in\mathcal{Q}_{1\text{-gram}}$ satisfies,

$\displaystyle\frac{1}{m}\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))$ (25)
$\displaystyle\overset{(i)}{=}-\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}[\log
Q_{\text{tok}}(\bm{t}_{i})]-\frac{1}{m}\mathbb{E}[\log Q_{\\#}(m)]$ (26)
$\displaystyle\overset{(ii)}{\geq}-\sum_{a\in\mathcal{A}}\pi(a)\log
Q_{\text{tok}}(a)$ (27) $\displaystyle\geq H(\pi)$ (28)

where in $(i)$, we use the definition of the unigram model $Q$, and in $(ii)$,
$\pi$ is the stationary distribution over characters induced by the stochastic
source, and the ergodicity of the source is used. The last equation lower
bounds $H(X,Y)\geq H(X)$.

####  A.3 Maximum likelihood unigram model

A number of our results (Theorems 4.3, 4.5 and 4.7 to name a few) are related
to bounding
$\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}(\cdot))$
for some tokenizer $\mathcal{T}$. In this section we introduce the maximum
likelihood unigram model which captures the optimizer over $Q$ for any given
tokenizer.

For the character level tokenizer, an examination of Theorem 2.1 shows that
the optimal unigram likelihood model associates probability
$Q_{\text{tok}}(a)=\pi(a)$, i.e. the limiting fraction of times the character
$a$ is observed in the sequence. More generally, for a non-trivial tokenizer,
the corresponding optimal unigram model $Q_{\text{tok}}^{\star}(\bm{t})$ ends
up being the limiting expected fraction of times $\bm{t}$ is observed in an
encoding of a sequence. This is the maximum likelihood unigram model, which we
formally define below. The unigram MLE likelihood model associates
probability,

$\displaystyle Q_{\text{MLE}}(\bm{t})$
$\displaystyle\leftarrow\lim_{m\to\infty}\mathbb{E}\left[\frac{n_{\bm{t}}}{\sum_{\bm{t}}n_{\bm{t}}}\right]$
(29)

to each token, where $n_{\bm{t}}$ is the random variable capturing the number
of occurrences of the token $\bm{t}$ in the encoding of the length-$m$ string
$\bm{s}$. Restricting the class of likelihood models to the unigram models,
$\mathcal{Q}_{1\text{-gram}}$, $Q_{\text{MLE}}$ captures the model which
minimizes eq. 1.

The unigram MLE model cannot be computed without an infinite amount of data,
but can be approximated well with a finite amount of data, which forms the
basis for Theorem C.1. For certain encoding algorithms, we can show that the
quantity $n_{\bm{t}}/\sum_{\bm{t}}n_{\bm{t}}$ asymptotically converges to its
expectation (Lemma A.3). This is the reason the unigram model in eq. 29 is
referred to as a “maximum likelihood” model, since
$\lim_{m\to\infty}n_{\bm{t}}/\sum_{\bm{t}}n_{\bm{t}}$ is the limit as
$|\bm{s}|=m\to\infty$ of the solution to the following likelihood maximization
problem: given a sequence $\bm{s}$, find the distribution over tokens, $Q$,
which maximizes

$\displaystyle\prod_{\bm{t}\in\textsf{enc}(\bm{s})}Q(\bm{t})\equiv\prod_{\bm{t}\in\textsf{Dict}}\left(Q(\bm{t})\right)^{n_{\bm{t}}}.$
(30)

As discussed previously, the unigram MLE model over tokens in eq. 29 induces a
joint distribution over sequences of tokens by looking at the product of the
marginal probabilities of the composed tokens; in particular,

$\displaystyle
Q_{\text{MLE}}(\bm{t}_{1},\cdots,\bm{t}_{j})=Q_{\text{MLE}}(j)\prod_{i=1}^{j}Q_{\text{MLE}}(\bm{t}_{i}),$
(31)

where $Q_{\text{MLE}}(j)$ is a distribution on the total number of tokens
generated and is instantiated as $\textrm{Unif}([m])$.

######  Remark A.1.

Note that the unigram MLE model specifies a distribution over tokens which is
a function of the underlying encoding algorithm, $\textsf{enc}(\cdot)$.
Different encoders result in different population level distributions over
tokens, and consequently different unigram MLE models.

######  Definition A.2 (greedy encoder).

Given a dictionary Dict, the greedy encoder
$\textsf{enc}_{\text{gre}}(\bm{s})$ encodes a string $\bm{s}$ into tokens by
greedily matching from left to right, the largest substring that exists as a
token in Dict. This substring is then removed and the process iterated on the
remainder of $\bm{s}$. The greedy decoder $\textsf{dec}_{\text{gre}}(\cdot)$
is a lookup table - a sequence of tokens is decoded by replacing each
occurrence of a token by the corresponding substring it maps to in Dict.

######  Lemma A.3.

$\lim_{m\to\infty}\frac{n_{\bm{t}}}{\sum_{\bm{t}^{\prime}}n_{\bm{t}^{\prime}}}\overset{\text{a.s.}}{=}\lim_{m\to\infty}\mathbb{E}\left[\frac{n_{\bm{t}}}{\sum_{\bm{t}^{\prime}}n_{\bm{t}^{\prime}}}\right]$
for any tokenizer having a finite vocabulary and finitely long tokens, using
the greedy encoder.

###### Proof.

This result is essentially true because under the greedy encoder, the tokens
in an encoding of a fresh string $\bm{t}$ may be generated by an
$r^{th}$-order Markov process for some $r$. For such processes, the Cesàro
average of the state distributions converges to a stationary distribution of
the process (i.e., the Krylov–Bogolyubov argument).

Tokens are generated as follows. Suppose the previous tokens generated were
$\bm{t}_{1},\bm{t}_{2},\cdots,\bm{t}_{i}$. The next token $\bm{t}_{i+1}$ is
sampled by drawing an infinite trajectory from $\mathcal{T}^{\star}_{a}$ for
$a\sim P(\cdot|\bm{t}_{i})$ and returning the longest prefix $\bm{t}$ of this
trajectory which is a token in Dict, conditional on satisfying the conditions,
$\bm{t}_{j}\bm{t}_{j+1}\cdots\bm{t}_{i}\bm{t}\not\in\textsf{Dict}$ for all
$j\in\\{1,2,\cdots,i\\}$. This process is repeated sequentially to generate
all the tokens.

Suppose the length of the longest token in the dictionary is $\ell_{\max}$.
Then, the distribution from a which a token is sampled depends on at most the
previous $\ell_{\max}$ tokens. The reason for this is that the dependency of
the $(i+1)^{th}$ token, $\bm{t}_{i+1}$, on the previously sampled tokens
emerges in the constraint
$\bm{t}_{j}\bm{t}_{j+1}\cdots\bm{t}_{i}\bm{t}_{i+1}\not\in\textsf{Dict}$,
satisfied by any candidate $\bm{t}_{i+1}$. Since each token is of length at
least one, this condition is vacuously satisfied if $j<i-\ell_{\max}$.

With this view, the evolution of the state, defined as
$\textsf{state}_{r}=(\bm{t}_{r\ell_{\max}},\bm{t}_{r\ell_{\max}-1},\cdots,\bm{t}_{(r-1)\ell_{\max}})$
evolves in a Markovian fashion. By the Krylov–Bogolyubov argument (cf.
Proposition 4.2 in Chen [2018]), the time averaged visitation frequencies of a
Markov chain coordinate-wise asymptotically converges to its expectation,
almost surely. This expectation exists by Theorems 8.5 and 8.22 of Eisner et
al. [2015] which shows that for a matrix $A$ such that
$\sup_{t\in\mathbb{N}}\|A^{t}\|_{\text{op}}<\infty$ the limit
$\lim_{t\to\infty}\frac{1}{t}\sum_{i=1}^{t}A^{i}$ exists. For the finite-state
Markov transition $A$ which captures the token generation process, condition
$\sup_{t\in\mathbb{N}}\|A^{t}\|_{\text{op}}\leq|\textsf{Dict}|^{\ell_{\max}}<\infty$.
This means that the limit of the time averaged state distribution exists.
Moreover, for any initial distribution $\pi_{0}$ over tokens,
$\pi=\lim_{t\to\infty}\frac{1}{t}\sum_{i=1}^{t}\pi_{0}A^{i}$ satisfies the
condition $\pi A=\pi$, implying that the limiting time-averaged state
distribution is a stationary distribution of $A$. Since the limiting time-
averaged measure on the state
$\textsf{state}_{r}=(\bm{t}_{r\ell_{\max}},\cdots,\bm{t}_{r\ell_{\max}-1},\cdots,\bm{t}_{(r-1)\ell_{\max}})$
exists, this implies that the limiting time-averaged measure of
$\bm{t}_{r\ell_{\max}-r^{\prime}}$ for each
$r^{\prime}\in\\{0,1,\cdots,\ell_{\max}\\}$ exists. By taking the uniform
average over $r^{\prime}$ and $r$, the limiting time-averaged measure of
$\bm{t}_{i}$ over $i\in\mathbb{N}$ exists. ∎

####  A.4 Proof of Theorem 4.3

Consider a string $\bm{s}$ of length $m\to\infty$ which is encoded into a
sequence of tokens $(\bm{t}_{i}\mathrel{\mathop{\mathchar
58\relax}}i\in[|\textsf{enc}_{\text{gre}}(\bm{s})|])$. By the Asymptotic
Equipartition Property (AEP) for ergodic sources, i.e. the
Shannon–McMillan–Breiman theorem,

$\displaystyle\Pr\left(\lim_{m\to\infty}-\frac{1}{m}\log
P(\bm{s})=H_{\infty}\right)=1.$ (32)

Here $\lim_{m\to\infty}\frac{H(P)}{m}$ also happens to be the entropy rate of
the source. We use this property to bound the length of the greedy encoding,
$|\textsf{enc}_{\text{gre}}(\bm{s})|$. Indeed, the probability of $\bm{s}$ may
be decomposed as,

$\displaystyle
P(\bm{s})=P(\bm{t}_{1})\prod_{i=2}^{|\textsf{enc}_{\text{gre}}(\bm{s})|}P\big{(}\bm{t}_{i}\big{|}\bm{t}_{i-1})\big{)}$
$\displaystyle\leq\prod_{i=1}^{|\textsf{enc}_{\text{gre}}(\bm{s})|}\max_{a\in\mathcal{A}}P\big{(}\bm{t}_{i}\big{|}a\big{)}.$
(33)

Noting that $\delta\min_{a}P(\bm{t}|a)\geq\max_{a}P(\bm{t}|a)$, up to a
$\delta$ factor we may replace the max over $a$ by an expectation over
$a\sim\pi$ where $\pi$ is the stationary distribution of the stochastic
source. In particular,

$\displaystyle
P(\bm{s})\leq\prod_{i=1}^{|\textsf{enc}_{\text{gre}}(\bm{s})|}P(\bm{t}_{i})/\delta.$
(34)

By invoking the AEP, eq. 32,

$\displaystyle\lim_{m\to\infty}\frac{1}{m}\sum\nolimits_{i=1}^{|\textsf{enc}_{\text{gre}}(\bm{s})|}-\log\left(P(\bm{t}_{i}))-\log(1/\delta)\right)\overset{\text{a.s.}}{\leq}H_{\infty}$
(35)

Recall that the greedy encoder satisfies Lemma A.3 and for any
$\bm{t}\in\textsf{Dict}$,
$\lim_{m\to\infty}\frac{n_{\bm{t}}}{|\textsf{enc}_{\text{gre}}(\mathbf{s})|}\overset{\text{a.s.}}{=}Q_{\text{MLE}}(\bm{t})$.
Furthermore, note that for any token $\bm{t}\in\textsf{Dict}$,
$P(\bm{t})>\delta^{|\bm{t}|}>0$, and $|\textsf{enc}_{\text{gre}}(\bm{s})|\leq
m$ surely. By almost sure convergence,

$\displaystyle\lim_{m\to\infty}\frac{|\textsf{enc}_{\text{gre}}(\bm{s})|}{m}\sum\nolimits_{\bm{t}\in\textsf{Dict}}-\frac{n_{\bm{t}}}{|\textsf{enc}_{\text{gre}}(\bm{s})|}\left(\log\left(P(\bm{t})-\log(1/\delta)\right)\right)$
(36)
$\displaystyle\qquad\overset{\text{a.s.}}{=}\lim_{m\to\infty}\frac{|\textsf{enc}_{\text{gre}}(\bm{s})|}{m}\left(H(Q_{\text{MLE}},P)-\log(1/\delta)\right)$
(37)

Furthermore, utilizing the assumption that $\varepsilon
H(Q_{\text{MLE}},P)\geq\log(1/\delta)$ satisfied by the tokenizer,

$\displaystyle\lim_{m\to\infty}\frac{(1-\varepsilon)|\textsf{enc}_{\text{gre}}(\mathbf{s})|\left(H(Q_{\text{MLE}},P)\right)}{m}\overset{\text{a.s.}}{\leq}H_{\infty}.$
(38)

Now we are ready to bound the expected cross-entropy loss of the tokenizer.
Define the unigram model
$P_{\pi}(\bm{t}_{1},\bm{t}_{2},\cdots,\bm{t}_{j})=P_{\text{unif}}(j)\prod_{i=1}^{j}P(\bm{t}_{i})$
where $P_{\text{unif}}$ is the uniform measure over $[m]$. Note that we have
the inequality
$\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(Q\circ\textsf{enc}_{\text{gre}}(\cdot))\leq\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(P_{\pi}\circ\textsf{enc}_{\text{gre}}(\cdot))$
and therefore, it suffices to upper bound the RHS. In particular,

$\displaystyle\mathcal{L}_{m}(P_{\pi}\circ\textsf{enc}_{\text{gre}}(\cdot))$
$\displaystyle=-\mathbb{E}[\log
P_{\text{unif}}(|\textsf{enc}_{\text{gre}}(\bm{s})|)]-\mathbb{E}\left[\sum\nolimits_{\bm{t}\in\textsf{enc}_{\text{gre}}(\bm{s})}\log\left(P(\bm{t})\right)\right]$
(39)
$\displaystyle\leq\log(m)-\mathbb{E}\left[\sum\nolimits_{\bm{t}\in\textsf{enc}_{\text{gre}}(\bm{s})}\log\left(P(\bm{t})\right)\right]$
(40)

where the last inequality uses the fact that
$P_{\text{unif}}(|\textsf{enc}_{\text{gre}}(\bm{s})|)=1/m$. Note that as
$m\to\infty$, by assumption on the tokenizer, the fraction of times the token
$\bm{t}$ appears in the encoding of $\bm{s}$ converges almost surely converges
to $Q_{\text{MLE}}(\bm{t})$. Since $|\textsf{enc}_{\text{gre}}(s)|\leq m$
surely and $P(\bm{t})>\delta^{|\bm{t}|}>0$, by an application of the Dominated
Convergence Theorem,

$\displaystyle-\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[\sum\nolimits_{\bm{t}\in\textsf{enc}_{\text{gre}}(\bm{s})}\log\left(P(\bm{t})\right)\right]$
$\displaystyle=-\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[|\textsf{enc}_{\text{gre}}(\bm{s})|\cdot\sum\nolimits_{\bm{t}\in\textsf{Dict}}Q_{\text{MLE}}(\bm{t})\log\left(P(\bm{t})\right)\right]$
(41)
$\displaystyle=\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[|\textsf{enc}_{\text{gre}}(\bm{s})|H(Q_{\text{MLE}},P)\right]$
(42)

Combining eq. 40 with eq. 42 and setting $\lim_{m\to\infty}\log(m)/m=0$, and
invoking eq. 38,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(Q_{\text{MLE}}\circ\textsf{enc}_{\text{gre}}(\cdot))$
$\displaystyle=\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[|\textsf{enc}_{\text{gre}}(\bm{s})|H(Q_{\text{MLE}},P)\right]$
(43) $\displaystyle\leq\frac{H_{\infty}}{1-\varepsilon}.$ (44)

By Theorem 2.1, we have that
$\min_{Q}\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(Q\circ\textsf{enc}_{\text{gre}}(\cdot))=\lim_{m\to\infty}\frac{H(P)}{m}=H_{\infty}$,
which uses the fact that the source is ergodic. Combining with eq. 44
completes the proof.

####  A.5 Heavy-hitter dictionaries and a proof of Theorem 4.5

In this section we prove Theorem 4.5 and introduce the notion of a heavy-
hitting dictionary. At a high level, these dictionaries contain all the
substrings which have reasonably high probability of being observed many times
in a dataset of size $n=\widetilde{\Omega}_{\delta}(d)$. We first show in
Lemma A.5 that heavy hitting dictionaries generalize well in the sense of
having $H(Q_{\text{MLE}},P)$ being large (in conjunction with Theorem 4.3 this
implies an upper bound on the cross-entropy loss of the best unigram model).
Next, we will prove that the LZW algorithm (Definition 4.4) results in a heavy
hitting dictionary with high probability.

Figure 6: The circled nodes indicates substrings which are tokens in Dict. Red
nodes indicate the set of “maximal tokens”, which are the set of tokens which
the greedy encoder assigns, leaving out those which can only be assigned as
the last token of some string. Tokens like “$b$” are never assigned by the
greedy encoder (save as the last token of the encoding of a string) since any
sufficiently long trajectory starting with $b$ must have a longer prefix which
is also a token, namely, one of $ba$, $bc$, $bba$, $bbb$ or $bbc$. The
vertices of the tree which are assigned by the greedy encoder as tokens
(together with all their prefixes) forms a cut of the tree, which marks the
dotted red line. The heavy hitting property asserts that this cut is uniformly
far away from the root node $\emptyset$, and that every vertex $\bm{s}$ marked
red has $P(\bm{s})\leq 1/d^{\beta}$.

######  Definition A.4 ($\beta$-heavy-hitting dictionary).

A token $\bm{t}$ of a dictionary is said to be maximal if there exists an
arbitrary substring containing $\bm{t}$ as a strict prefix, and in addition,
$\bm{t}$ is also the largest prefix of the substring which is a token. A
dictionary Dict is said to be $\beta$-heavy hitting if the set of maximal
tokens is a subset of $\\{\bm{s}^{\prime}\mathrel{\mathop{\mathchar
58\relax}}\max_{a\in\mathcal{A}}P(\bm{s}^{\prime}|a)\leq 1/d^{\beta}\\}$.

A pictorial depiction of the heavy hitting property is illustrated in Figure
6.

######  Lemma A.5.

For a $\beta$-heavy-hitting dictionary, with the greedy encoder,
$H(Q_{\text{MLE}},P)\geq\beta\log(d)$.

###### Proof.

Note that the greedy encoder assigns tokens only among the set of maximal
substrings (save for potentially the last token). If every maximal substring
has $\max_{a\in\mathcal{A}}P(\bm{s}|a)\leq 1/d^{\beta}$, by the heavy-hitting
property, for any token $\bm{t}$,

$\displaystyle P(\bm{t})\leq\max_{a\in\mathcal{A}}P(\bm{s}^{\prime}|a)\leq
1/d^{\beta}.$ (45)

Therefore,

$\displaystyle H(Q_{\text{MLE}},P)=\mathbb{E}_{\bm{t}\sim
Q_{\text{MLE}}}[\log(1/P(\bm{t}))]$ $\displaystyle\geq\beta\log(d).$ (46)

∎

Define $\mathcal{M}_{\beta}=\\{\bm{t}\mathrel{\mathop{\mathchar
58\relax}}\max_{a\in\mathcal{A}}P(\bm{t}|a)\geq\delta/d^{\beta}\\}$. These are
the set of “high-probability” substrings under the stochastic source. We will
show that for $\beta$ bounded away from $1$, with high probability, every
substring in $\mathcal{M}_{\beta}$ is added as a token to the dictionary in a
run of the LZW tokenizer (Definition 4.4). Note that if every substring in
$\mathcal{M}_{\beta}$ is assigned as a token by LZW, then the algorithm must
be $\beta$-heavy hitting since there always exists a maximal token on the
“boundary” of the set $\mathcal{M}_{\beta}$ which is strictly contained in
$\\{\bm{s}^{\prime}\mathrel{\mathop{\mathchar
58\relax}}\max_{a\in\mathcal{A}}P(\bm{s}^{\prime}|a)\leq 1/d^{\beta}\\}$.

######  Lemma A.6.

Every substring in $\mathcal{M}_{\beta}$ has length at most
$\ell_{\star}\triangleq\delta^{-1}(\beta\log(d)+\log(1/\delta))$.

###### Proof.

Note that $\min_{a,a^{\prime}\in\mathcal{A}}P(a|a^{\prime})=\delta$, which
implies that the probability of any transition must be bounded away from $1$,
i.e., $\max_{a,a^{\prime}\in\mathcal{A}}P(a|a^{\prime})\leq 1-\delta$. This
implies that,

$\displaystyle\max_{a\in\mathcal{A}}P(\bm{t}|a)\leq(1-\delta)^{|\bm{t}|}\leq
e^{-\delta|\bm{t}|}.$ (47)

By definition, for any substring $\bm{t}\in\mathcal{M}_{\beta}$,
$\max_{a\in\mathcal{A}}P(\bm{t}|a)\geq\delta/d^{\beta}$. In conjunction with
eq. 47, this implies the statement of the lemma. ∎

In the remainder of this section, let $n$ be the size of the dataset on which
LZW is run. We show that the number of tokens added to the dictionary by LZW,
$d$, is $\widetilde{\Theta}_{\delta}(n)$. Rather than running the algorithm
with early stopping (i.e., ceasing to add new tokens once the budget is hit),
instead, we assume that the algorithm runs on a prefix of the dataset of
length $d$. The number of tokens added this way cannot exceed $d$.

######  Lemma A.7.

With probability $\geq 1-d^{-\Omega(\log(d/\delta)/\delta)}$, in a run of the
LZW algorithm, no substring $\bm{t}$ added as a token to the dictionary
satisfies $|\bm{t}|\geq\ell_{\max}\triangleq 4\log(d|\mathcal{A}|)/\delta$.

###### Proof.

Consider any $s\in\mathbb{N}$ and any substring $\bm{t}$ of length $s$. In
order for $\bm{t}$ to be assigned as a token, each of its prefixes must
disjointly appear at least once in the string. Since there are at most $d$
tokens, we can upper bound the probability that $\bm{t}$ is assigned as a
token as,

$\displaystyle P(\bm{t}\text{ is assigned as a token})$
$\displaystyle\leq\binom{d}{s}\prod_{i=1}^{s}\max_{a\in\mathcal{A}}P(\bm{t}_{1\mathrel{\mathop{\mathchar
58\relax}}i}|a)$ (48)
$\displaystyle\overset{(i)}{\leq}\binom{d}{s}(1-\delta)^{s(s-1)/2}$ (49)
$\displaystyle\leq e^{s\log(d)-\delta s(s-1)/2},$ (50)

where $(i)$ uses the fact that
$\max_{a\in\mathcal{A}}P(\bm{t}_{1\mathrel{\mathop{\mathchar
58\relax}}i})\leq\prod_{j=1}^{i}\max_{a\in\mathcal{A}}P(\bm{t}_{j}|a)\leq(1-\delta)^{i}$.
By union bounding across the $|\mathcal{A}|^{s}$ strings of length $s$,

$\displaystyle P(\text{any length }s\text{ string is assigned as a token})\leq
e^{s\log(|\mathcal{A}|)+s\log(d)-\delta s(s-1)/2}.$ (51)

When $s=4\log(d|\mathcal{A}|)/\delta+1\triangleq\ell_{\max}+1$, the RHS is
upper bounded by $e^{-\delta\ell_{\max}^{2}/4}\leq
d^{-\Omega(\log(d/\delta)/\delta)}$. With the same small probability, no
substring of length $s^{\prime}>s$ can become a token, since their length-$s$
prefixes are never assigned as tokens. ∎

######  Corollary A.8.

With probability $\geq 1-d^{-\Omega_{\delta}(\log(d))}$, learns a dictionary
with at least $d^{\star}=d/\ell_{\max}$ tokens when run on a training sequence
of length $n$ drawn from a stochastic source satisfying Assumption 4.2.

######  Lemma A.9.

For any constant $\beta<1$, with probability $\geq
1-d^{-\Omega(\log(d/\delta)/\delta)}-\exp(-\widetilde{\Omega}_{\delta}(d^{1-\beta}))$
over the source dataset, every substring in $\mathcal{M}_{\beta}$ is added as
a token to the dictionary in a run of the LZW algorithm. In other words, with
the same probability, the LZW tokenizer results in a $\beta$-heavy hitting
dictionary.

By Corollary A.8, note that with high probability the LZW tokenizer adds at
least $d^{\star}$ tokens to the dictionary when processing a length $d$
training sequence in entirety. In this proof, instead of generating $d$
samples, we sequentially sample $d^{\star}$ tokens from their joint
distribution, and generate a dictionary from these samples. From Corollary
A.8, with high probability this results in at most $d$ samples being
generated, implying that the dictionary generated by sampling $d^{\star}$
tokens is a subset of the dictionary generated by a full run of the LZW
tokenizer. Here, we use the fact that the LZW tokenizer adds tokens to the
dictionary in a left to right fashion, and therefore a subset of the
dictionary learnt by the LZW tokenizer can be generated by processing a
portion of the dataset.

Next we consider a joint view for generating the dataset from the stochastic
source and the dictionary learnt by LZW simultaneously. The stochastic source
is sampled as a sequence of tokens. Suppose the last character of the previous
token was $a^{\prime}$. Sample a character $a\sim P(\cdot|a^{\prime})$ and an
infinite trajectory on the tree $\mathcal{T}_{a}^{\star}$. Consider the first
node visited in this trajectory which does not already exist as a token in the
dictionary. The substring corresponding to this node is added as a token in
the dictionary. By repeating this process, the dictionary and the source
dataset are constructed sequentially and simultaneously. As alluded to before,
we truncate this token sampling process to repeat at most $d^{\star}$ times,
which results in a subset of the dictionary output by the LZW algorithm with
high probability (Corollary A.8). This is simply a variant of the
“Poissonization” trick to avoid statistical dependencies across tokens. Denote
the set of infinite trajectories generated on the forest
$\\{\mathcal{T}^{\star}_{a}\mathrel{\mathop{\mathchar
58\relax}}a\in\mathcal{A}\\}$ as
$\\{\textsf{traj}_{i}\mathrel{\mathop{\mathchar 58\relax}}i\in[d^{\star}]\\}$.

With this view of the sampling process, observe that if the substring $\bm{t}$
sampled was a prefix of $\textsf{traj}_{i}$ at least $|\bm{t}|$ times across
different values of $i$, then $\bm{t}$ must be assigned as a token. In
particular, in each of these $|\bm{t}|$ trajectories, each of the prefixes of
$\bm{t}$ is assigned as a token. With this observation, the event that
$\bm{t}$ is not assigned as a token is contained in the event that $\bm{t}$ is
visited at most $|\bm{t}|-1$ times across the $d^{\star}$ trajectories.
Observe that,

$\displaystyle P(\bm{t}\text{ is not assigned as a token})$
$\displaystyle\leq\sum_{i=0}^{|\bm{t}|-1}\binom{d^{\star}}{i}\max_{a\in\mathcal{A}}(P(\bm{t}|a))^{i}(1-P(\bm{t}|a))^{d^{\star}-i}.$
(52)

Since we aim to upper bound this probability across the substrings in
$\bm{t}\in\mathcal{M}_{\beta}$, note that $(i)$
$\max_{a\in\mathcal{A}}P(\bm{t}|a)\geq\delta/d^{\beta}$, and $(ii)$ tokens in
$\mathcal{M}_{\beta}$ have length at most
$\ell_{\star}=\delta^{-1}(\beta\log(d)+\log(1/\delta))$ (Lemma A.6), implying
there are at most $2|\mathcal{A}|^{\ell_{\star}}$ substrings in this set. By
union bounding,

$\displaystyle P(\exists\bm{t}\in\mathcal{M}_{\beta}\text{ not assigned as a
token})$ $\displaystyle\leq
2|\mathcal{A}|^{\ell_{\star}}\sum_{i=0}^{\ell_{\star}-1}\binom{d^{\star}}{i}\max_{x\geq\delta/d^{\beta}}x^{i}(1-x)^{d^{\star}-i}.$
(53)

Case I. For $i\leq\ell_{\star}$ and $x\geq 1/2$,

$\displaystyle|\mathcal{A}|^{\ell_{\star}}\binom{d^{\star}}{i}x^{i}(1-x)^{d^{\star}-i}$
$\displaystyle\leq|\mathcal{A}|^{\ell_{\star}}\frac{(d^{\star})^{\ell_{\star}}}{2^{d^{\star}/2}}$
(54) $\displaystyle\leq
2^{{\ell_{\star}}\log(d^{\star}|\mathcal{A}|)-d^{\star}/2}$ (55)
$\displaystyle\leq 2^{-\Omega_{\beta,\delta}(d^{\star})},$ (56)

where the last inequality uses the fact that
$\ell_{\star}=O_{\beta,\delta}(\log(d))$.

Case II. For $i\leq\ell_{\star}$ and $\delta/d^{\beta}\leq x\leq 1/2$,

$\displaystyle|\mathcal{A}|^{\ell_{\star}}\binom{d^{\star}}{i}x^{i}(1-x)^{d^{\star}-i}$
$\displaystyle\leq|\mathcal{A}|^{\ell_{\star}}\binom{d^{\star}}{i}(1-x)^{d^{\star}}$
(57)
$\displaystyle\leq|\mathcal{A}|^{\ell_{\star}}(d^{\star})^{\ell_{\star}}e^{-d^{\star}x}$
(58) $\displaystyle\leq
e^{{\ell_{\star}}\log(|\mathcal{A}|)+{\ell_{\star}}\log(d^{\star})-d^{\star}x}$
(59) $\displaystyle\leq e^{-\Omega(\delta^{2}n/d^{\beta}/\log(d/\delta))}$
(60) $\displaystyle\leq e^{-\Omega(\delta^{2}d^{1-\beta}/\log(d/\delta))},$
(61)

where the last inequality uses the fact that ${\ell_{\star}}=O(\log(d))$,
$x\geq\delta/d^{\beta}$, $d^{\star}=\Omega(d\delta/\log(d/\delta))$. By
combining eq. 56 and eq. 61 with eq. 53 completes the proof, as long as
$\beta$ is a constant bounded away from $1$.

######  Lemma A.10.

Fix a constant $\gamma>0$. Then, with probability $\geq
1-d^{-\Omega_{\gamma,\delta}(\log(d))}$, none of the substrings in the set
$\mathcal{N}_{\gamma}=\left\\{\mathbf{s}^{\prime}\mathrel{\mathop{\mathchar
58\relax}}\max_{a\in\mathcal{A}}P(\mathbf{s}^{\prime}|a)\leq\delta/d^{1+\gamma}\right\\}$
are assigned as tokens in a run of LZW.

###### Proof.

Define the following set of substrings,

$\displaystyle S_{\gamma}=\left\\{\mathbf{t}\mathrel{\mathop{\mathchar
58\relax}}\delta/d^{1+\gamma/2}\leq\max_{a\in\mathcal{A}}P(\mathbf{t}|a)\leq
1/d^{1+\gamma/2}\right\\}$ (62)

Since the width of this band is sufficiently large, by Assumption 4.2 every
substring $\bm{t}$ such that
$\max_{a\in\mathcal{A}}P(\bm{t}|a)\leq\delta/d^{1+\gamma/2}$ has at least one
prefix which falls in $S_{\gamma}$, and denote the longest such prefix
$\bm{t}_{\gamma}$. Define
$T_{\gamma}=\\{\bm{t}_{\gamma}\mathrel{\mathop{\mathchar
58\relax}}\bm{t}\in\mathcal{N}_{\gamma}\\}$ as the set of longest prefixes in
$S_{\gamma}$. Intuitively, if we think of the strings in $S_{\gamma}$ (or
$T_{\gamma}$) as being intermediate in length, the strings in
$\mathcal{N}_{\gamma}$ can be thought of as being particularly long: the value
of $\max_{a\in\mathcal{A}}P(\bm{t}|a)$ for any $\bm{t}\in T_{\gamma}$ and for
any $\bm{t}\in\mathcal{N}_{\gamma}$ are separated by a factor of at least
$1/d^{\gamma/2}$. In particular, since the probability of any character is
lower bounded by $\delta$, each substring in $\bm{t}\in\mathcal{N}_{\gamma}$
must be at least $\Delta=\frac{\gamma\log(d)}{2\log(1/\delta)}$ symbols longer
than its corresponding longest prefix in $T_{\gamma}$, $\bm{t}_{\gamma}$. An
implication of this is that for $\mathbf{t}$ to be assigned as a token,
$\bm{t}_{\gamma}$ must be observed at least $\Delta+1$ times disjointly in
$\bm{s}$. However, note that $\bm{t}_{\gamma}$ already has low marginal
probability to begin with ($\ll 1/d$) so the odds of seeing this substring so
many times disjointly is very small. Furthermore, note that $T_{\gamma}$ has
at most $d^{1+\gamma/2}/\delta$ substrings, which allows the probability of
this event occurring simultaneously across all substrings in $T_{\gamma}$ to
be controlled by union bound. Under this condition, none of the substrings in
$\mathcal{N}_{\gamma}$ are made into tokens.

In order to argue that the dictionary does not contain certain tokens, we may
argue this property about any superset of the dictionary. In contrast, in
Lemma A.9, we construct a subset of the dictionary by running LZW on the
concatenation of $d^{\star}$ tokens sampled from their joint distribution. The
superset we consider here is just to sample $d$ tokens from their joint
distribution and concatenate them together to result in a string of length
$\geq d$, and running LZW on this sequence (which simply would result in these
$d$ tokens). As in Lemma A.9, let
$\\{\textsf{traj}_{i}\mathrel{\mathop{\mathchar 58\relax}}i\in[d]\\}$ denote
the infinite trajectories generated from the Markov chain which are truncated
to result in tokens. A sufficient condition for the event that no substring
$\bm{t}\in\mathcal{N}_{\gamma}$ is assigned as a token by LZW is to the event
that every substring $\bm{t}^{\prime}\in T_{\gamma}$ is observed as a prefix
of $\textsf{traj}_{i}$ for $\Delta$ or fewer choices of $i\in[d]$. To this end
define $\mathcal{E}(\bm{t}^{\prime})$ as the event that
$|i\in[d]\mathrel{\mathop{\mathchar 58\relax}}\bm{t}^{\prime}\text{ is a
prefix of }\textsf{traj}_{i}|\leq\Delta$. Then,

$\displaystyle\Pr(\mathcal{E}(\bm{t}^{\prime}))$
$\displaystyle\leq\binom{n}{\Delta}(\max_{a\in\mathcal{A}}P(\bm{t}^{\prime}|a))^{\Delta}$
(63)
$\displaystyle\overset{(i)}{\leq}e^{\Delta\log(n)}\left(\frac{1}{d^{1+\gamma/2}}\right)^{\Delta}$
(64) $\displaystyle\leq e^{-\frac{\gamma}{2}\Delta\log(d)},$ (65)

where $(i)$ uses the fact that $\max_{a\in\mathcal{A}}P(\bm{t}^{\prime}|a)\leq
1/d^{1+\gamma/2}$ since the substring $\bm{t}^{\prime}$ belongs to
$T_{\gamma}$.

Note that the number of substrings in $S_{\gamma}$ (and by extension,
$T_{\gamma}$) is at most $O_{\delta}(d^{1+\gamma/2})$. Recall that these
substrings satisfy the condition
$\max_{a\in\mathcal{A}}P(\bm{t}|a)\geq\delta/d^{1+\gamma/2}$. Observe that,

$\displaystyle\frac{\delta|S_{\gamma}|}{d^{1+\gamma/2}}$
$\displaystyle\leq\sum_{\bm{t}\in
S_{\gamma}}\max_{a\in\mathcal{A}}P(\bm{t}|a)$ (66)
$\displaystyle\leq\sum_{\bm{t}\in
S_{\gamma}}\sum_{a\in\mathcal{A}}P(\bm{t}|a)\leq|\mathcal{A}|\leq\frac{1}{\delta}.$
(67)

This implies that there are at most $d^{1+\gamma/2}/\delta^{2}$ substrings in
$S_{\gamma}$. Finally, in conjunction with eq. 65,

$\displaystyle P(\exists\ \bm{t}^{\prime}\in
S_{\gamma}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{E}(\bm{t}^{\prime}))\leq\frac{d^{1+\gamma/2}}{\delta^{2}}e^{-\frac{\gamma}{2}\Delta\log(d)}=d^{-\Omega_{\gamma,\delta}(\log(d))},$
(68)

which implies that with high probability, no token in $S_{\gamma}$ is observed
as a prefix of $\bm{s}^{i}$ for more than $\Delta$ choices of the index
$i\in[d]$. Under this event, no substring in $\mathcal{N}_{\gamma}$ is
assigned as a token. ∎

#####  A.5.1 Proof of Theorem 4.5

Choosing $\beta=0.99$ in Lemma A.9, with probability $\geq
1-d^{-\Omega_{\delta}(\log(d))}$, the LZW tokenizer results in a $0.99$-heavy-
hitting dictionary. As a consequence of Lemma A.5, this implies that under the
same event,

$\displaystyle H(Q_{\text{MLE}},P)\geq 0.99\log(d).$ (69)

Finally, combining with Theorem 4.3 completes the proof.

###  Appendix B Proof of Theorem 4.7

In this section we prove a rephrased version of Theorem 4.7 which implies the
statement in the main paper. Define $d_{0}=\frac{\epsilon
d}{2\log(4|\mathcal{A}|)}$.

######  Theorem B.1 (Rephrased Theorem 4.7).

Run Algorithm 1 on a dataset of $n=\Theta(d^{2})$ characters to learn a
dictionary with at most $d$ tokens. The resulting tokenizer $\mathcal{T}$
satisfies one of the following $3$ conditions,

  1. 1.

Either, $|\textsf{Dict}|>d_{0}$, and,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}(\cdot))\leq\frac{H_{\infty}}{1-\varepsilon}.$
(70)

Here,
$\varepsilon=O\left(\frac{\log^{3}(1/\delta)\log(1/\epsilon)}{\epsilon\delta^{9}\log(d)}\right)$.

  2. 2.

$\Pr(|\textsf{Dict}|<d_{0})=e^{-\Omega(\epsilon^{2}d/\log^{2}(1/\delta))}$,
or,

  3. 3.

Conditional on $|\textsf{Dict}|<d_{0}$, with probability $\geq
1-e^{-\Omega(\epsilon^{2}d/\log^{2}(1/\delta))}$,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}(\cdot))\leq\left(1-\frac{2d_{0}}{d}\right)\left(2H_{\infty}+O\left(\frac{1}{\log(d)}\right)\right)+\frac{2d_{0}}{d}\log(4|\mathcal{A}|).$
(71)

With the choice of $d_{0}=\epsilon d/2\log(4|\mathcal{A}|)$ we get the
statement of Theorem 4.7.

####  B.1 Analysis for the large dictionary case: $|\textsf{Dict}|>d_{0}$

In the large dictionary case, Algorithm 1 uses the greedy encoder/decoder pair
in conjunction with the dictionary. The proof of Theorem 4.7 relies on
establishing that the cross-entropy $H(Q_{\text{MLE}},P)$ of the tokenizer is
large. Namely, we prove that,

######  Lemma B.2.

In Algorithm 1, assuming at least $d_{0}$ tokens are allocated,

$\displaystyle
H(Q_{\text{MLE}},P)=\Omega\left(\frac{\epsilon\delta^{9}\log(d)}{\log(1/\epsilon)\log^{3}(1/\delta)}\right).$
(72)

To show this, it suffices to argue that conditioned on any previous set of
tokens, with nontrivial probability over the underlying string generated from
the stochastic source, the next token is long (i.e. having conditional
probability at most $O(1/\sqrt{d})$).

######  Lemma B.3.

Suppose that in a run of Algorithm 1, at least $d_{0}$ tokens are allocated.
Suppose a set of tokens $\bm{t}_{1},\cdots,\bm{t}_{k}$ have been sampled so
far by the greedy encoder. Let $T_{i+1}$ be the random variable which denotes
the next token returned by the greedy encoder, where the randomness comes from
the underlying string being tokenized. Then,

$\displaystyle\Pr\left(P(T_{i+1}|\bm{t}_{i})\leq 1/\sqrt{C\delta
d}\middle|\bm{t}_{1},\cdots,\bm{t}_{i}\right)\geq\frac{d_{0}\delta^{6}(1-\delta)^{2}}{8Cd\Delta|\mathcal{A}|\log(2|\mathcal{A}|)n_{D}}=\Omega\left(\frac{\epsilon\delta^{9}}{\log^{3}(1/\delta)\log(1/\epsilon)}\right)$
(73)

###### Proof sketch of Lemma B.3.

The proof will proceed in $2$ parts. We first show in Lemma B.7 that there is
a set $D_{\text{valid}}$ of $\Omega(d)$ tokens in the dictionary which are
neither prefixes nor suffixes of any other token in Dict. The reason for
considering this set of tokens is twofold,

  1. 1.

Irrespective of what the previous set of tokens were, it is legal for a token
$D_{\text{valid}}$ to be sampled in the current step by the greedy encoder,
since for any candidate $\bm{t}\in D_{\text{valid}}$, by definition,
$\bm{t}_{j}\cdots\bm{t}_{i}\bm{t}\not\in\textsf{Dict}$ for every $j\leq i$.

  2. 2.

Suppose a sequence of tokens $\bm{t}_{1},\cdots,\bm{t}_{i}$ have already been
sampled, ending with the character $a$. Then, we may sample the next token
using rejection sampling. Sample $a^{\prime}\sim P(\cdot|a)$ and an infinitely
long trajectory on $\mathcal{T}_{a^{\prime}}^{\star}$. Return the last token
on this trajectory which belongs to Dict, and if it so happens that $\exists
j\in[i]$ such that $\bm{t}_{j}\cdots\bm{t}_{i}\bm{t}\in\textsf{Dict}$, then
reject this trajectory and repeat. Since all the tokens in $D_{\text{valid}}$
are not prefixes of another token, any trajectory which reaches a token in
$D_{\text{valid}}$ must terminate the rejection sampling process.

Next, in Lemma B.8, we show that since the number of tokens in
$D_{\text{valid}}$ is sufficiently large, $\Omega(d)$, with constant (in $d$)
probability, a trajectory rolled out in the first round of the rejection
sampling process will reach a token $\bm{t}\in D_{\text{valid}}$ which has
small probability, i.e. $\max_{a\in\mathcal{A}}P(\bm{t}|a)\leq
1/\textsf{poly}(d)$. By the previous arguments, this must mean that the
rejection sampling process terminates on this “low probability” token,
resulting in the statement of the lemma. ∎

Figure 7: Jointly generating a sequence and its greedy encoding: In this
example we use the greedy encoder under the dictionary composed of all the
substrings shadowed red. The first character ($a$) is sampled from the
stationary distribution. Then an infinite string is sampled on the tree with
$a$ as root (green path). The last substring on this path which is a token
($\bm{t}_{1}=abb$) is returned by the greedy encoder. Then the next character
$x=b$ is sampled from the source conditioned on the previous character ($b$)
and further conditioned on $\bm{t}_{1}x\not\in\textsf{Dict}$. Finally, another
infinite string is sampled on the tree with $x=b$ as root (purple path) and
the last substring on this path which is a token ($\bm{t}_{2}=ba$) is returned
by the greedy encoder. Repeating this process, we can generate a string, here,
$abbba\cdots$, as well as its greedy encoding, $(abb,ba,\cdots)$.

###### Proof of Theorem B.1.1 and Lemma B.2

It is easy to see why Lemma B.3 implies a lower bound on the cross entropy
$H(Q_{\text{MLE}},P)$ of the tokenizer. By Lemma A.3 for the greedy encoder,

$\displaystyle
Q_{\text{MLE}}(\bm{t})=\lim_{m\to\infty}\mathbb{E}\left[\frac{n_{\bm{t}}}{\sum_{\bm{t}^{\prime}}n_{\bm{t}^{\prime}}}\right]\overset{\text{a.s.}}{=}\lim_{m\to\infty}\frac{n_{\bm{t}}}{\sum_{\bm{t}^{\prime}}n_{\bm{t}^{\prime}}}.$
(74)

Since the limit $m\to\infty$ of the RHS exists by Lemma A.3, we may let
$m\to\infty$ in any way we like, and in particular we may simply sample
$i^{\star}$ tokens, $\bm{t}_{1},\cdots,\bm{t}_{i^{\star}}$ sequentially
according to the process in Figure 7. Here, the first token sampled is
returned by generating an infinitely long string on $\mathcal{T}_{a}^{\star}$
where $a\sim\pi$ and then truncating this trajectory to the longest token
which belongs to Dict. Subsequently for every $i>1$, $\bm{t}_{i}$ is generated
by sampling a fresh infinitely long string from $\mathcal{T}_{a}^{\star}$
where $a$ is sampled from the $P(\cdot|a^{\prime})$ where $a^{\prime}$ is the
last character $\bm{t}_{i-1}$ and then returning the largest prefix of this
string which is a token in Dict, conditioned on
$\bm{t}_{j}\cdots\bm{t}_{i-1}\bm{t}_{i}\not\in\textsf{Dict}$ for any $j<i$.

and concatenate the corresponding substrings to get an
$m=\sum_{i=1}^{i^{\star}}|\bm{t}_{i}|$ length character string. Letting
$i^{\star}\to\infty$, we must have $m\to\infty$ surely since $m\geq
i^{\star}$. In this view, eq. 74 can be rewritten as,

$\displaystyle
Q_{\text{MLE}}(\bm{t})=\lim_{i^{\star}\to\infty}\frac{n_{\bm{t}}}{i^{\star}}=\lim_{i^{\star}\to\infty}\frac{1}{i^{\star}}\sum_{i=1}^{i^{\star}}\mathbb{I}(\bm{t}_{i}=\bm{t})\overset{\text{a.s.}}{=}\lim_{i^{\star}\to\infty}\frac{1}{i^{\star}}\sum_{i=1}^{i^{\star}}\mathbb{E}[\mathbb{I}(\bm{t}_{i}=\bm{t})|\bm{t}_{1},\cdots,\bm{t}_{i-1}]$
(75)

where the last inequality follows by the sequential nature of the token
sampling process and a martingale argument. Consider the set of tokens $T$
such that $\bm{t}\in T$ satisfies
$\max_{a\in\mathcal{A}}P(\bm{t}|a)\leq\sqrt{1/C\delta^{3}d}$. From eq. 75,
summing across $\bm{t}\in T$, we have that,

$\displaystyle\sum_{\bm{t}\in
T}Q_{\text{MLE}}(\bm{t})\overset{\text{a.s.}}{=}\lim_{i^{\star}\to\infty}\frac{1}{i^{\star}}\sum_{i=1}^{i^{\star}}\Pr\left(\bm{t}_{i}\in
T\middle|\bm{t}_{1},\cdots,\bm{t}_{i-1}\right)=\Omega\left(\frac{\epsilon\delta^{9}}{\log^{3}(1/\delta)\log(1/\epsilon)}\right)$
(76)

where in the last inequality, we use Lemma B.3 and the fact that
$\delta\max_{a\in\mathcal{A}}P(\bm{t}|a)\geq\min_{a\in\mathcal{A}}P(\bm{t}|a)$.
Therefore,

$\displaystyle H(Q_{\text{MLE}},P)\geq\sum_{\bm{t}\in
T}Q_{\text{MLE}}(\bm{t})\log(1/P(\bm{t}))\geq\sum_{\bm{t}\in
T}Q_{\text{MLE}}(\bm{t})\log(\sqrt{C\delta^{3}d})$ (77)

where in $(i)$ we use the fact that for $\bm{t}\in T$,
$\max_{a\in\mathcal{A}}P(\bm{t}|a)\leq 1/\sqrt{C\delta^{3}d}$, which implies
that $P(\bm{t})\leq 1/\sqrt{C\delta^{3}d}$. Finally, combining with eq. 76
completes the proof of Lemma B.2. Furthermore, since the cross-entropy
$H(Q_{\text{MLE}},P)$ was established to be large, by invoking the reduction
in Theorem 4.3, we complete the proof of Theorem B.1.1.

Figure 8: The circled nodes indicate substrings which are tokens in Dict. The
red boundary is the set of substrings $\bm{t}$ such that
$\max_{a\in\mathcal{A}}P(\bm{t}|a)\geq 1/Cd$. By Lemma B.6, none of the nodes
which fall outside this boundary are assigned as tokens in a run of Algorithm
1. The set of circled substrings are the set of tokens in Dict. Among them,
the ones circled green are the tokens in $D_{\text{valid}}$, which are not
prefixes or suffixes of any other tokens in Dict. Substrings such as $cb$ or
$ba$ which are tokens in Dict do not belong to $D_{\text{valid}}$ because they
are prefixes of longer tokens (in this case, $cbb$ and $bab$ respectively). On
the other hand, substrings like $ab$ do not belong to $D_{\text{valid}}$ since
they are suffixes of tokens in Dict, in this case, $bab$. Lemma B.7 asserts
that the number of tokens in $D_{\text{valid}}$ are $\Omega(d)$ in number,
assuming that Dict has $\Omega(d)$ tokens to begin with.

###### Notation.

For each $a\in\mathcal{A}$ and $j\in\mathbb{N}\cup\\{0\\}$, define a level set
of substrings,

$\displaystyle
S_{j}^{a}=\left\\{(1-\delta)^{j+1}<P(\bm{t}|\bm{t}_{1}=a)\leq(1-\delta)^{j}\right\\}$
(78)

where $\bm{t}_{1}$ denotes the first character of $\bm{t}$. And likewise,
define the sets $S_{j}=\cup_{a\in\mathcal{A}}S_{j}^{a}$, $S_{\leq j}^{a}$ and
$S_{\geq j}^{a}$ as the union of $S_{j^{\prime}}^{a}$ over $j^{\prime}\geq j$,
$j^{\prime}\leq j$ and $S_{\leq j}$ and $S_{\geq j}$ as the union of $S_{\leq
j}^{a}$ and $S_{\geq j}^{a}$ over $a\in\mathcal{A}$. Furthermore for a large
universal constant $C>0$, define parameters,

$\displaystyle\Delta$
$\displaystyle=\frac{\log(\delta)}{\log(1-\delta)}\asymp\Theta\left(\frac{\log(1/\delta)}{\delta}\right);\quad
n_{D}=1-\frac{2\log(4Cd/\delta
d_{0})}{\log(1-\delta)}\asymp\Theta\left(\frac{\log(1/\epsilon\delta)}{\delta}\right).$
(79)

We first begin by stating a folklore result: every pair of tokens assigned by
a merging-based dictionary generation algorithm have distinct character
representations.

Dictionary$\vdots$$\bm{t}_{1}\leftarrow(\cdot,\cdot)$
$\bm{t}_{2}\leftarrow(\cdot,\cdot)$
$\vdots$$\bm{t}^{\prime}\leftarrow(\cdot,\cdot)$
$\vdots$$\bm{t}^{\prime\prime}\leftarrow(\cdot,\cdot)$
$\cdots$$\bm{s}^{\prime}$$\cdots$$\bm{s}^{\prime}$$\cdots$$s_{1}s_{2}s_{1}\cdots
s_{7}$$s_{1}s_{2}s_{1}\cdots
s_{7}$$\cdots\bm{t}_{1}\cdots\bm{t}_{1}\cdots$$\cdots\bm{t}_{1}\cdots\bm{t}_{1}\cdots$$\cdots\bm{t}_{1}\bm{t}_{2}\cdots\bm{t}_{1}\cdots\bm{t}_{2}\cdots$$\cdots\bm{t}_{1}\bm{t}_{2}\cdots\bm{t}_{1}\cdots\bm{t}_{2}\cdots$$\bm{t}^{\prime}$$\bm{t}^{\prime}$$\bm{t}^{\prime\prime}$at
each step, both copies of $\bm{s}^{\prime}$ encodeto the samesequence of
tokenssuppose itencodes to $\bm{t}^{\prime}$suppose itencodes to
$\bm{t}^{\prime\prime}$$\implies$At each iteration,both copies of
$\bm{s}^{\prime}$perfectly encode toa sequence of tokens both copies of
$\bm{s}^{\prime}$map to the sametoken at this step,a contradiction Figure 9: A
pictorial representation of the proof of Lemma B.4

######  Lemma B.4.

If Algorithm 1 assigns a new token in some round, it’s character
representation must be distinct from that of all previously assigned tokens.

###### Proof.

A pictorial proof is in Figure 9. We will prove this result by contradiction.
Suppose $\bm{t}$ and $\bm{t}^{\prime}$ are tokens which decode to the same
character substring, $\mathbf{s}^{\prime}$. Consider all occurrences of
$\mathbf{s}^{\prime}$ in the dataset which in some iteration encode into
$\bm{t}^{\prime}$ or $\bm{t}^{\prime\prime}$, and denote these disjoint
locations $\mathcal{S}$. Recall that at these locations, $\mathbf{s}^{\prime}$
eventually is assumed to map to a singular token $\bm{t}^{\prime}$ or
$\bm{t}^{\prime\prime}$. Therefore, at every step in the merging process these
occurrences of $\mathbf{s}^{\prime}$ must perfectly map to a sequence of
tokens.

Now consider the merging process at the first time before any of the rules
corresponding to tokens in $\bm{t}^{\prime}$ or $\bm{t}^{\prime\prime}$ are
implemented. Prior to this time, all the occurrences of $\mathbf{s}^{\prime}$
corresponding to the locations in $\mathcal{S}$ have not been tokenized yet.
When the first rule corresponding to one of the tokens in
$\\{\bm{t}^{\prime},\bm{t}^{\prime\prime}\\}$ is implemented, all the strings
in $\mathcal{S}$ must be modified identically. This uses the fact that we can
isolate each of these occurrences of $\mathbf{s}^{\prime}$ while carrying out
the merging process, since each location must be distinct. At every step, the
encodings of these copies of $\bm{s}^{\prime}$ must be the same, and therefore
$\bm{t}^{\prime}$ and $\bm{t}^{\prime\prime}$ cannot be two distinct tokens. ∎

######  Lemma B.5.

The size of the level set $S_{j}^{a}$ is bounded by $(1-\delta)^{-(j+1)}$.

###### Proof.

Since the probability of any transition is at most $1-\delta$, this implies
that any infinite trajectory on the tree $\mathcal{T}^{\star}_{a}$ can
intersect at most one vertex in $S_{j}^{a}$. Therefore, $\sum_{\bm{t}\in
S_{j}^{a}}P(\bm{t}|\bm{t}_{1}=a)\leq 1$. By the lower bound on
$P(\bm{t}|\bm{t}_{1}=a)$ for $\bm{t}\in S_{j}^{a}$, this implies the statement
of the lemma. ∎

Next we show that with high probability none of the substrings $\bm{t}$ having
probability mass (under $P$) of at most $\delta/Cd$ conditioned on the first
character, are assigned as tokens by Algorithm 1.

######  Lemma B.6.

In a run of Algorithm 1, for a sufficiently large constant $C>0$, with
probability $d^{-\Omega(1)}\textsf{poly}(1/\delta)$ all assigned tokens
$\bm{t}\in\textsf{Dict}$ satisfy $\max_{a\in\mathcal{A}}P(\bm{t}|a)\geq 1/Cd$.
In other words, none of the substrings in $S_{\geq j^{\star}}$ are added as
tokens to the dictionary in a run of Algorithm 1, where,

$\displaystyle j^{\star}\triangleq\log(\delta/Cd)/\log(1-\delta)$ (80)

###### Proof.

Consider some $j\geq j^{\star}$ and $a\in\mathcal{A}$ and substring $\bm{t}\in
S_{j}^{a}$. In the $i^{th}$ stage of the algorithm where $\textsf{text}_{i}$
is being processed, for $\bm{t}$ to be assigned as a token, at the very least,
$\bm{t}$ must appear at least $\log(d)$ times disjointly in
$\textsf{text}_{i}$. Therefore,

$\displaystyle P(\bm{t}\in S_{j}^{a}\text{ is assigned as a token in
}\textsf{text}_{i})$
$\displaystyle\leq\binom{d}{\log(d)}\left(\max_{a\in\mathcal{A}}P(\bm{t}|a)\right)^{\log(d)}$
(81) $\displaystyle\leq
d^{\log(d)}\left(\frac{1}{Cd}(1-\delta)^{j-j^{\star}}\right)^{\log(d)}$ (82)
$\displaystyle\leq d^{-\log(C)}(1-\delta)^{(j-j^{\star})\log(d)}$ (83)

Union bounding over $S_{j}^{a}$ over $j\geq j^{\star}$ using the bound on
$|S_{j}^{a}|$ in Lemma B.5, and over $a\in\mathcal{A}$ and $i\in[d]$ results
in the bound,

$\displaystyle P(\bm{t}\in S_{\geq j^{\star}}\text{ is assigned as a token in
step }i\text{ for some }i\in[d])\leq d^{-\Omega(1)}\sum_{j\geq
j^{\star}}\frac{(1-\delta)^{(j-j^{\star})\log(d)}}{(1-\delta)^{j+1}}\leq\frac{d^{-\Omega(1)}}{\delta(1-\delta)}$
(84)

∎

######  Lemma B.7.

Consider the set of tokens $D_{\text{valid}}$ which are not a prefix or a
suffix of any other token in Dict. That is,
$D_{\text{valid}}=\\{\bm{t}\in\textsf{Dict}\mathrel{\mathop{\mathchar
58\relax}}\not\exists\bm{s}\mathrel{\mathop{\mathchar
58\relax}}\bm{s}\bm{t}\in\textsf{Dict}\\}\cap\\{\bm{t}\in\textsf{Dict}\mathrel{\mathop{\mathchar
58\relax}}\not\exists\bm{s}\mathrel{\mathop{\mathchar
58\relax}}\bm{t}\bm{s}\in\textsf{Dict}\\}$. If $|\textsf{Dict}|\geq d_{0}$,
then,

$\displaystyle|D_{\text{valid}}|\geq\frac{d_{0}}{4n_{D}}.$ (85)

where $n_{D}$ is defined in eq. 79.

###### Proof.

For any token $\bm{t}\in D_{\text{valid}}$, there may be at most $2|\bm{t}|$
tokens which are suffixes or prefixes of it and belong to Dict. More
importantly, every token in Dict not belonging to $D_{\text{valid}}$ must
either be a prefix or a suffix of some token in $D_{\text{valid}}$. Split the
suffixes and prefixes of the tokens in $D_{\text{valid}}$ into four sets,

  1. 1.

$S_{\text{suff},\min}=\bigcup_{\bm{t}\in
D_{\text{valid}}}\\{\bm{t}^{\prime}\in\textsf{Dict}\mathrel{\mathop{\mathchar
58\relax}}\bm{t}^{\prime}\in\textsf{suff}(\bm{t}),\
|\bm{t}^{\prime}|\leq|\bm{t}|-n_{D}\\}$,

  2. 2.

$S_{\text{suff},\max}=\bigcup_{\bm{t}\in
D_{\text{valid}}}\\{\bm{t}^{\prime}\in\textsf{Dict}\mathrel{\mathop{\mathchar
58\relax}}\bm{t}^{\prime}\in\textsf{suff}(\bm{t}),\
|\bm{t}^{\prime}|>|\bm{t}|-n_{D}\\}$,

  3. 3.

$S_{\text{pre},\min}=\bigcup_{\bm{t}\in
D_{\text{valid}}}\\{\bm{t}^{\prime}\in\textsf{Dict}\mathrel{\mathop{\mathchar
58\relax}}\bm{t}^{\prime}\in\textsf{pre}(\bm{t}),\
|\bm{t}^{\prime}|\leq|\bm{t}|-n_{D}\\}$,

  4. 4.

$S_{\text{pre},\max}=\bigcup_{\bm{t}\in
D_{\text{valid}}}\\{\bm{t}^{\prime}\in\textsf{Dict}\mathrel{\mathop{\mathchar
58\relax}}\bm{t}^{\prime}\in\textsf{pre}(\bm{t}),\
|\bm{t}^{\prime}|>|\bm{t}|-n_{D}\\}$.

where $n_{D}$ is defined in eq. 79. Note from Lemma B.6 that all the tokens
$\bm{t}\in\textsf{Dict}$ all satisfy $\max_{a\in\mathcal{A}}P(\bm{t}|a)\geq
1/Cd$. Therefore, the tokens in $S_{\text{pre},\min}$ and
$S_{\text{suff},\min}$ all satisfy, $\max_{a\in\mathcal{A}}P(\bm{t}|a)\geq
d/C(1-\delta)^{n_{D}}$. By summing Lemma B.5 over appropriate $j$, we get that
$|S_{\text{pre},\min}|+|S_{\text{suff},\min}|\leq
2Cd(1-\delta)^{n_{D}-1}/\delta$.

On the other hand, corresponding to any $\bm{t}\in D_{\text{valid}}$, there
are at most $n_{D}$ tokens in $S_{\text{pre},\max}$ or $S_{\text{suff},\max}$
and and therefore $|S_{\text{pre},\max}|,|S_{\text{suff},\max}|\leq
n_{D}\cdot|D_{\text{valid}}|$. Since every token in Dict either belongs to
$D_{\text{valid}}$ or is a suffix of some token in $D_{\text{valid}}$,
$S_{\text{pre},\min}\cup S_{\text{pre},\max}\cup S_{\text{suff},\min}\cup
S_{\text{suff},\max}=|\textsf{Dict}|$ and,

$\displaystyle
2n_{D}\cdot|D_{\text{valid}}|+\frac{2C(1-\delta)^{n_{D}-1}d}{\delta}\geq
d_{0}$ (86)

Recalling the choice of $n_{D}=1-\frac{2\log(4Cd/\delta
d_{0})}{\log(1-\delta)}$, we get that,

$\displaystyle|D_{\text{valid}}|\geq\frac{d_{0}}{4n_{D}}.$ (87)

∎

######  Lemma B.8.

Suppose Algorithm 1 assigns at least $d_{0}$ tokens. For any character
$a\in\mathcal{A}$, sample an $a^{\prime}\sim P(\cdot|a)$ and an infinite
trajectory on the tree $\mathcal{T}^{\star}_{a^{\prime}}$, denoted traj. Then,

$\displaystyle\mathbb{E}_{a^{\prime}\sim
P(\cdot|a)}\left[\Pr_{\textsf{traj}\sim\mathcal{T}_{a^{\prime}}^{\star}}\left(\min_{\bm{t}\in\textsf{traj}\cap
D_{\text{valid}}}P(\bm{t}|a)\leq\sqrt{\delta/Cd}\middle|a^{\prime}\right)\right]\geq\frac{d_{0}\delta^{6}(1-\delta)^{2}}{8Cd\Delta|\mathcal{A}|n_{D}}.$
(88)

where the notation $\mathcal{T}_{a^{\prime}}^{\star}$ is used to overload the
distribution over infinite trajectories on $\mathcal{T}_{a^{\prime}}^{\star}$.
The parameters $n_{D}$ and $\Delta$ are defined in eq. 79.

###### Proof.

By Lemma B.6, recall that the $\geq d_{0}$ tokens assigned in a run of
Algorithm 1, with high probability, are substrings in $S_{\leq j^{\star}}$.
For any $a\in\mathcal{A}$, the total number of substrings in $S_{\leq
j^{\star}}$ can be bounded as,

$\displaystyle|S_{\leq
j^{\star}}|\leq\sum_{a\in\mathcal{A}}\sum_{j=0}^{j^{\star}}|S_{j}^{a}|\leq\sum_{a\in\mathcal{A}}\sum_{j=0}^{j^{\star}}\frac{1}{(1-\delta)^{j+1}}\leq\frac{C|\mathcal{A}|d}{\delta(1-\delta)}.$
(89)