In order to prove this result, we use a counting argument and the fact that no
tokens in $S_{>j^{\star}}$ are assigned. Consider some character $a$ and all
the leaves in the forest $S_{\leq j^{\star}}$. Since every transition has
$\geq\delta$ probability of occurring, across all leaf nodes $\bm{t}\in
S_{\leq j^{\star}}$, $P(\bm{t}|a^{\prime})$ are within a
$\delta^{2}(1-\delta)$ factor of each other across different
$a^{\prime}\in\mathcal{A}$. In particular, by counting the number of paths in
$\mathcal{T}^{\star}$ (i.e. paths in $\mathcal{T}^{\star}_{a}$ from
$\emptyset$ to leaf nodes in $S_{\leq j^{\star}}^{a}$ across
$a\in\mathcal{A}$) along which a token in Dict exists in $S_{\geq
j^{\star}/2}$, we can also compute the probability mass across such
trajectories up to a factor of $\delta^{2}(1-\delta)$.

Taking the union across $a\in\mathcal{A}$, consider the paths in
$\mathcal{T}^{\star}_{a}$ from $\emptyset$ to leaf nodes in $S_{\leq
j^{\star}}^{a}$. From Lemma B.7, $\sum_{j\leq j^{\star}}|D_{\text{valid}}\cap
S_{j}|\geq d_{0}/4n_{D}$, where $n_{D}=1-2\log(4Cd/\delta
d_{0})/\log(1-\delta)$. Note that for sufficiently large
$d=\Omega(\log(1/\epsilon\delta)/\delta^{5})$, by Lemma B.5, $\sum_{j\leq
j^{\star}/2}|S_{j}|=\sqrt{Cd/\delta}/\delta(1-\delta)\leq d_{0}/8n_{D}$.
Therefore,

$\displaystyle\sum_{j^{\star}/2<j\leq j^{\star}}|D_{\text{valid}}\cap
S_{j}|\geq\frac{d_{0}}{8n_{D}}.$ (90)

Define $\Delta=\log(\delta)/\log(1-\delta)$. Combining eq. 90 with eq. 89 and
applying the probabilistic method, there exists an $i^{\star}\geq j^{\star}/2$
such that,

$\displaystyle\frac{|D_{\text{valid}}\cap(S_{i^{\star}+1}\cup\cdots\cup
S_{i^{\star}+\Delta})|}{|S_{i^{\star}+1}\cup\cdots\cup
S_{i^{\star}+\Delta}|}\geq\frac{\delta(1-\delta)d_{0}}{8Cd|\mathcal{A}|n_{D}}.$
(91)

Note that $\Delta$ is chosen to be sufficiently large, so that every infinite
trajectory on $\mathcal{T}^{\star}_{a^{\prime}}$ must intersect at least once
with the band of vertices $S_{i^{\star}+\Delta+1}^{a^{\prime}}\cup\cdots\cup
S_{i+2\Delta}^{a^{\prime}}$. Note that this band is different from the one
considered in eq. 91. Define $L_{a^{\prime}}$ as the set of longest prefixes
across infinite trajectories in $\mathcal{T}_{a^{\prime}}^{\star}$ which
belong to $S_{i^{\star}+\Delta+1}^{a^{\prime}}\cup\cdots\cup
S_{i+2\Delta}^{a^{\prime}}$.

Note that our objective is to show that an infinite trajectory sampled on
$\mathcal{T}_{a^{\prime}}^{\star}$ where $a^{\prime}\sim P(\cdot|a)$, has a
long prefix in Dict. We can truncate this trajectory to lower bound this
probability, and therefore, we assume that the infinite trajectories on
$\mathcal{T}^{\star}_{a^{\prime}}$ terminate once they reach a substring in
$L_{a^{\prime}}$. Furthermore, note that although $\Delta$ is large, it is
still a constant depending on $\delta$. Therefore, the band of states
$S_{i^{\star}+\Delta+1}^{a^{\prime}}\cup\cdots\cup
S_{i^{\star}+2\Delta}^{a^{\prime}}$ is not too wide, and all the substrings in
$L_{a^{\prime}}$ have approximately similar probabilities to each other. In
particular, for any character $a\in\mathcal{A}$, and for any
$a^{\prime}\in\mathcal{A}$ and $\bm{t}\in L_{a^{\prime}}$, decomposing
$P(\bm{t}|a)$ as $P(\bm{t}|\bm{t}_{1}=a^{\prime})P(a^{\prime}|a)$,

$\displaystyle\delta^{2}(1-\delta)\cdot(1-\delta)^{i+\Delta}\overset{(i)}{\leq}P(\bm{t}|a)\overset{(ii)}{\leq}(1-\delta)^{i+\Delta}.$
(92)

Inequality $(i)$ follows from the fact that all transition probabilities are
at least $\delta$, so every leaf node in $L_{a^{\prime}}$ must have
$P(\bm{t}|\bm{t}_{1}=a^{\prime})\geq(1-\delta)^{i+2\Delta+1}$, and the fact
that $P(a^{\prime}|a)\geq\delta$. Inequality $(ii)$ follows similarly from the
fact that $\bm{t}$ is a leaf node of $L_{a^{\prime}}$ and therefore
$P(\bm{t}|\bm{t}_{1}=a^{\prime})\leq(1-\delta)^{i+\Delta}$. Therefore, instead
of bounding the probability of any event under the distribution over
substrings in $L_{a^{\prime}}$ induced by truncating the infinite strings
sampled on $\mathcal{T}_{a^{\prime}}^{\star}$, it suffices to count the
fraction of substrings in $L_{a^{\prime}}$ satisfying the event (which are
equivalent up to a $\delta(1-\delta)$ factor). Define,

$\displaystyle\textsf{pre}(\bm{t})=(\bm{t}_{1},\bm{t}_{1\mathrel{\mathop{\mathchar
58\relax}}2},\bm{t}_{1\mathrel{\mathop{\mathchar
58\relax}}3},\cdots,\bm{t}_{1\mathrel{\mathop{\mathchar 58\relax}}|\bm{t}|})$
(93)

As the set of prefixes of $\bm{t}$ (including $\bm{t}$). Note that at most
$\Delta$ of the prefixes of any substring $\bm{t}$ can intersect with
$S_{i^{\star}+1}^{a}\cup\cdots\cup S_{i^{\star}+\Delta}^{a}$. Therefore,

$\displaystyle\sum_{a^{\prime}\in\mathcal{A}}\sum_{\bm{t}\in
L_{a^{\prime}}}\bm{1}(\textsf{pre}(\bm{t})\cap
D_{\text{valid}}\cap(S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a^{\prime}})\neq\emptyset)$ (94)
$\displaystyle\geq\sum_{a^{\prime}\in\mathcal{A}}\sum_{\bm{t}\in
L_{a^{\prime}}}\frac{|\textsf{pre}(\bm{t})\cap
D_{\text{valid}}\cap(S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a^{\prime}})|}{\Delta}$ (95)
$\displaystyle\overset{(i)}{\geq}\sum_{a^{\prime}\in\mathcal{A}}\frac{|D_{\text{valid}}\cap(S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a^{\prime}})|}{\Delta}$ (96)
$\displaystyle\overset{(ii)}{\geq}\frac{\delta
d_{0}(1-\delta)}{8Cd\Delta|\mathcal{A}|n_{D}}\sum_{a^{\prime}\in\mathcal{A}}|S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a^{\prime}}|$ (97)
$\displaystyle\overset{(iii)}{\geq}\frac{\delta^{3}d_{0}(1-\delta)}{8Cd\Delta|\mathcal{A}|n_{D}}\sum_{a^{\prime}\in\mathcal{A}}|L_{a^{\prime}}|,$
(98)

where $(i)$ uses the fact that the prefixes of $\bm{t}\in L_{a^{\prime}}$
cover all the substrings in $S_{\leq i^{\star}+\Delta}^{a^{\prime}}$, and
therefore $\cup_{\bm{t}\in L_{a^{\prime}}}\textsf{pre}(\bm{t})\supset
S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup S_{i^{\star}+\Delta}^{a^{\prime}}$,
and $(ii)$ uses eq. 91. Finally, $(iii)$ uses the fact that $\Delta$ is not
too large, and therefore, for any substring $\bm{t}^{\prime}\in
S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup S_{i^{\star}+\Delta}^{a^{\prime}}$,
there are at most $1/(1-\delta)^{2\Delta}=1/\delta^{2}$ substrings $\bm{t}\in
L_{a^{\prime}}$ which contain it as a prefix. This means,
$|L_{a^{\prime}}|\leq|S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a^{\prime}}|/\delta^{2}$. After dividing by
$\sum_{a^{\prime}\in\mathcal{A}}|L_{a^{\prime}}|$ on both sides, this implies,

$\displaystyle\mathbb{E}_{a^{\prime}\sim\mathrm{Unif}(\mathcal{A})}\left[\Pr_{\bm{t}\sim\mathrm{Unif}(L_{a^{\prime}})}\left(\textsf{pre}(\bm{t})\cap
D_{\text{valid}}\cap(S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a^{\prime}})\neq\emptyset\middle|a^{\prime}\right)\right]\geq\frac{\delta^{3}d_{0}(1-\delta)}{8Cd\Delta|\mathcal{A}|n_{D}}.$
(99)

The event inside the inner probability term is the event that an infinitely
long string (truncated at $L_{a^{\prime}}$) has a prefix which lies in
$D_{\text{valid}}$ and which intersects with
$S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a^{\prime}}$, which implies that it has probability
$P(\bm{t}|a)\leq\sqrt{\delta/Cd}$. Therefore, we have that for any
$a\in\mathcal{A}$, sampling an $a^{\prime}\sim P(\cdot|a)$ and an infinite
trajectory $\textsf{traj}\sim\mathcal{T}_{a^{\prime}}^{\star}$,

$\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]$
(100)
$\displaystyle\overset{(i)}{\geq}\delta^{2}(1-\delta)\cdot\mathbb{E}_{a^{\prime}\sim
P(\cdot|a)}\left[\Pr_{\bm{t}^{\prime}\sim\mathrm{Unif}(L_{a^{\prime}})}\left(\min_{\bm{t}\in\textsf{pre}(\bm{t}^{\prime})\cap
D_{\text{valid}}}P(\bm{t}|a)\leq\sqrt{\delta/Cd}\middle|a^{\prime}\right)\right]$
(101)
$\displaystyle\overset{(ii)}{\geq}\delta^{2}(1-\delta)\cdot\mathbb{E}_{a^{\prime}\sim
P(\cdot|a)}\left[\Pr_{\bm{t}^{\prime}\sim\mathrm{Unif}(L_{a^{\prime}})}\left(\textsf{pre}(\bm{t}^{\prime})\cap
D_{\text{valid}}\cap(S_{i^{\star}+1}^{a^{\prime}}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a^{\prime}})\neq\emptyset\middle|a^{\prime}\right)\right]$
(102)
$\displaystyle\overset{(iii)}{\geq}\delta^{3}(1-\delta)\cdot\mathbb{E}_{a^{\prime}\sim\text{Unif}(\mathcal{A})}\left[\Pr_{\bm{t}^{\prime}\sim\mathrm{Unif}(L_{a^{\prime}})}\left(\textsf{pre}(\bm{t}^{\prime})\cap
D_{\text{valid}}\cap(S_{i^{\star}+1}^{a}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a})\neq\emptyset\middle|a^{\prime}\right)\right]$ (103)
$\displaystyle\geq\delta^{3}(1-\delta)\cdot\frac{\delta^{3}d_{0}(1-\delta)}{8Cd\Delta|\mathcal{A}|n_{D}}.$
(104)

Here $(i)$ follows by truncating the trajectory traj to terminate at a node in
$\cup_{a^{\prime}\in\mathcal{A}}L_{a^{\prime}}$ and from eq. 92, $(ii)$
follows by arguing that $i^{\star}\leq j^{\star}/2$ and therefore if a prefix
of $\bm{t}^{\prime}$ lies in $S^{a^{\prime}}_{i^{\star}+1}\cup\cdots\cup
S_{i^{\star}+\Delta}^{a^{\prime}}$, then it must have
$P(\bm{t}|a)\leq\sqrt{\delta/Cd}$. Inequality $(iii)$ follows by noting that
all the transitions $P(a^{\prime}|a)$ have probability $\geq\delta$, and the
last inequality follows from eq. 99. ∎

##### Proof of Lemma B.3

Lemma B.8 concludes that given any previous sequence of tokens terminating in
a character $a$, with constant probability, an infinite trajectory sampled
from $\mathcal{T}_{a^{\prime}}^{\star}$ with $a^{\prime}\sim P(\cdot|a)$ has
as prefix, a substring $\bm{t}$, which not only has low probability, with
$P(\bm{t}|a)\leq\sqrt{\delta/Cd}$, but also belongs to the subset of tokens
$D_{\text{valid}}$. Note that regardless of the previously sampled tokens, it
is legal to sample any token in $D_{\text{valid}}$ as the current token, since
by definition, these tokens are not the suffixes of any other tokens in Dict.
Moreover, if any trajectory on $\mathcal{T}_{a^{\prime}}^{\star}$ reaches a
token in $D_{\text{valid}}$, then it must be largest token along that
trajectory, since none of the tokens in $D_{\text{valid}}$ are prefixes of
another token in Dict.

Consider generating a new token by rejection sampling. Suppose the set of
previous tokens $\bm{t}_{1},\cdots,\bm{t}_{i}$ end in some character $a$.
Sample the next character $a^{\prime}\sim P(\cdot|a)$ and an infinite
trajectory on $\mathcal{T}^{\star}_{a^{\prime}}$. If it reaches an illegal
token $\bm{t}$ such that $\bm{t}_{j}\bm{t}_{j+1}\cdots\bm{t}_{i}\bm{t}$
already exists in Dict, this token is rejected and the trajectory is
resampled. By the prefix-free property of these tokens, if this trajectory
visits a token in $D_{\text{valid}}$, it must immediately be output as the
next token. Note that this probability is lower bounded by,

$\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]$
(105)

which is lower bounded by $\textsf{poly}(\epsilon,\delta)$, the subject of
Lemma B.8. Therefore with this probability, the process terminates in the
first step with a token in $D_{\text{valid}}$ being sampled.

####  B.2 Analysis in the small dictionary case

In this section, we will prove Theorem B.1.2 and Theorem B.1.3. In particular
we show that, either,

  1. 1.

The dictionary is small with low probability. i.e.,
$\Pr(|\textsf{Dict}|<d_{0})=e^{-\Omega(\epsilon^{2}d/\log^{2}(1/\delta))}$,
or,

  2. 2.

Or conditioned on the dictionary being small, $|\textsf{Dict}|<d_{0}$, with
high 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
4\left(1-\frac{2d_{0}}{d}+O\left(\frac{1}{\log(d)}\right)\right)H_{\infty}+\frac{2d_{0}}{d}\cdot\log(2|\mathcal{A}|).$
(106)

For $i\in[d]$, define the indicator random variable,

$\displaystyle X(\bm{s}^{\prime},\textsf{Dict})=\bm{1}(\exists\text{a pair of
tokens in }\textsf{enc}_{\text{BPE}}(\bm{s}^{\prime})\text{ under
}\textsf{Dict}\text{ appears at least }\log(d)\text{ times}).$ (107)

which captures the event that the string $\bm{s}^{\prime}$ is compressed well
by the dictionary Dict under the sequential encoder.

Let $\textsf{Dict}_{i}$ denote the dictionary stored by Algorithm 1 right
after $\textsf{text}_{i}$ is processed. The key insight behind this lemma is
the following statement, asserting that the sequential encoder satisfies a
“monotonicity” property: for any $j$ and string $\bm{s}^{\prime}$, if there
exists a pair of tokens appearing more than $\log(d)$ times consecutively in
the sequential encoding of $\bm{s}^{\prime}$ under $\textsf{Dict}_{j}$, then
there must exist a pair of tokens appearing more than $\log(d)$ times
consecutively in the greedy encoding of $\bm{s}^{\prime}$ under
$\textsf{Dict}_{i}$ for any $i<j$. This implies that
$X(\bm{s}^{\prime},\textsf{Dict}_{j})\leq
X(\bm{s}^{\prime},\textsf{Dict}_{i})$ if $i<j$ for any string
$\bm{s}^{\prime}$. This monotonicity property implies that the last dictionary
output by the learner, $\textsf{Dict}_{d}$ sequentially encodes a $1-\epsilon$
fraction of the previously seen texts, $\textsf{text}_{i}$ in a way where
every pair of tokens appears at most $\log(d)$ times. While
$\textsf{Dict}_{d}$ is correlated with these texts, we can circumvent this
correlation by using a martingale argument to prove the statement of the
lemma.

######  Lemma B.9.

Let Dict be the dictionary returned by Algorithm 1. Then,

$\displaystyle\min\left\\{\Pr\left(\mathbb{E}\big{[}X\big{(}\bm{s}^{\prime},\textsf{Dict}\big{)}\big{|}\textsf{Dict}\big{]}\geq
2d_{0}/d\middle||\textsf{Dict}|<d_{0}\right),\Pr\left(|\textsf{Dict}|<d_{0}\right)\right\\}\leq
e^{-\epsilon^{2}d/8\log^{2}(1/\delta)}.$ (108)

where $\bm{s}^{\prime}$ is a fresh substring of length $d$ sampled from the
stochastic source.

###### Proof.

Let $\textsf{Dict}_{i}$ denote the state of dictionary returned by Algorithm 1
right after $\textsf{text}_{i}$ is processed. Then, $\textsf{Dict}_{d}$ is the
final dictionary returned by Algorithm 1. Suppose
$\mathbb{E}\big{[}X\big{(}\bm{s}^{\prime},\textsf{Dict}_{d}\big{)}\big{|}\textsf{Dict}_{d}\big{]}\geq
2d_{0}/d$, where $\bm{s}^{\prime}$ is a fresh substring of length $d$ sampled
from the stochastic source. Using monotonicity of the sequential encoder,
almost surely for any string $\bm{s}^{\prime}$,
$X(\bm{s}^{\prime},\textsf{Dict}_{i})\leq
X(\bm{s}^{\prime},\textsf{Dict}_{j})$ for any $j>i$. Therefore,

$\displaystyle\mathbb{E}\big{[}X\big{(}\bm{s}^{\prime},\textsf{Dict}_{d}\big{)}\big{|}\textsf{Dict}_{d}\big{]}\geq
2d_{0}/d\implies\sum\nolimits_{i=1}^{d-1}\mathbb{E}\big{[}X\big{(}\bm{s}^{\prime},\textsf{Dict}_{i}\big{)}\big{|}\textsf{Dict}_{i}\big{]}\geq
2d_{0}\cdot\frac{d-1}{d}$ (109)

Note in this expectation, $\bm{s}^{\prime}$ is an independent string of length
$d$ sampled from the stochastic source. Since $\textsf{Dict}_{i}$ and
$\textsf{text}_{i+1}$ are independent, we may instead write,

$\displaystyle\sum\nolimits_{i=1}^{d-1}\mathbb{E}\big{[}X\big{(}\textsf{text}_{i+1},\textsf{Dict}_{i}\big{)}\big{|}\textsf{Dict}_{i},\textsf{text}_{i},\textsf{Dict}_{i-1},\cdots,\textsf{Dict}_{1},\textsf{text}_{1}\big{]}\geq
2d_{0}\cdot\frac{d-1}{d}.$ (110)

For brevity, denote $X_{i}=X(\textsf{text}_{i+1},\textsf{Dict}_{i})$ and
define the filtration
$\mathcal{F}_{i}=\sigma(\\{\textsf{text}_{1},\textsf{Dict}_{1},\cdots,\textsf{text}_{i},\textsf{Dict}_{i}\\})$.
Note that $\sum_{j=1}^{i}X_{j}-\mathbb{E}[X_{j}|\mathcal{F}_{i}]$ forms a
martingale sequence under the filtration
$\\{\mathcal{F}_{i}\mathrel{\mathop{\mathchar 58\relax}}i\in[d]\\}$.
Therefore, by the Azuma-Hoeffding inequality, for any $\eta>0$,

$\displaystyle\Pr\left(\sum\nolimits_{i=1}^{d-1}\mathbb{E}[X_{i}|\mathcal{F}_{i}]-X_{i}\leq-\eta\right)\leq
e^{-\eta^{2}}.$ (111)

Under Case I, we have that $\sum_{i=1}^{d}X_{i}\leq d_{0}$. Therefore, from
eq. 109 and eq. 111,

$\displaystyle\Pr\left(|\textsf{Dict}|<d_{0};\
\mathbb{E}\left[X(\bm{s}^{\prime},\textsf{Dict})\middle|\textsf{Dict}\right]\geq
2d_{0}/d\right)$ $\displaystyle\leq\Pr\left(\sum_{i=1}^{d-1}X_{i}<d_{0};\
\sum_{i=1}^{d-1}\mathbb{E}\left[X_{i}\middle|\mathcal{F}_{i}\right]\geq
2d_{0}\cdot\frac{d-1}{d}\right)$ (112)
$\displaystyle\leq\Pr\left(\sum_{i=1}^{d-1}\mathbb{E}\left[X_{i}\middle|\mathcal{F}_{i}\right]-X_{i}\geq
d_{0}\cdot\frac{d-2}{d}\right)$ (113) $\displaystyle\leq
e^{-d_{0}^{2}(1-2/d)^{2}}$ (114) $\displaystyle\leq
e^{-d_{0}^{2}/2}=e^{-\epsilon^{2}d/8\log^{2}(1/\delta)}.$ (115)

Finally, using the inequality
$\Pr(A,B)=\Pr(A|B)\Pr(B)\geq(\min\\{\Pr(A),\Pr(B)\\})^{2}$ completes the
proof. ∎

###### Proofs of Theorem B.1.2 and Theorem B.1.3

If
$\Pr(|\textsf{Dict}|<d_{0})\leq\epsilon^{-\epsilon^{2}d/8\log^{2}(1/\delta)}$
the proof of Theorem B.1.2 concludes. Otherwise, consider the case
$\Pr(|\textsf{Dict}|<d_{0})>\epsilon^{-\epsilon^{2}d/8\log^{2}(1/\delta)}$,
whereby, $\mathbb{E}[X(\bm{s}^{\prime},\textsf{Dict})|\textsf{Dict}]\leq
2d_{0}/d$ with probability $\geq 1-e^{-\epsilon^{2}d/8\log^{2}(1/\delta)}$
conditioned on $|\textsf{Dict}|<d_{0}$ by Lemma B.9. Recall that when
$|\textsf{Dict}|<d_{0}$, Algorithm 1 uses a parallel implementation of the
sequential encoder which chunks a new string into pieces of length $d$,
denoted $\\{\textsf{chunk}_{i}\mathrel{\mathop{\mathchar 58\relax}}i\in[d]\\}$
and uses the sequential encoder under $\textsf{Dict}_{d}$ to tokenize each
chunk. Note that since the source is Markovian, the chunked process
$\\{\textsf{chunk}_{i}=(X_{id+1},X_{id+2},\cdots,X_{(i+1)d})\mathrel{\mathop{\mathchar
58\relax}}i=1,2,\cdots\\}$ is also Markovian and ergodic. Therefore, by a
similar limiting argument as in Lemma A.3, using the Krylov–Bogolyubov
argument (cf. Proposition 4.2 in Chen [2018]) for Markov processes, we have
that,

$\displaystyle\lim_{\ell\to\infty}\frac{\sum_{i=1}^{\ell}X(\textsf{chunk}_{i},\textsf{Dict})}{\ell}=\mathbb{E}[X(\bm{s}^{\prime},\textsf{Dict})]\leq\frac{2d_{0}}{d}.$
(116)

where $\bm{s}^{\prime}$ is a fresh string of length $d$ sampled with initial
state distribution as the stationary measure of the stochastic source. On the
remaining (limiting) $1-2d_{0}/d$ fraction of the chunks, their sequential
encodings have every pair of tokens appearing at most $\log(d)$ times
consecutively. Using Theorem 1 of Navarro and Russo [2008], the number of
tokens in the encoding of each of these chunks cannot be too large, and
satisfies,

$\displaystyle|\textsf{enc}_{\text{BPE}}(\textsf{chunk}_{i})|\cdot\log|\textsf{enc}_{\text{BPE}}(\textsf{chunk}_{i})|\leq
2dH_{\infty}+O(d/\log(d))$ (117) $\displaystyle\implies$
$\displaystyle|\textsf{enc}_{\text{BPE}}(\textsf{chunk}_{i})|\cdot\log d\leq
2dH_{\infty}+O(d/\log(d))$ (118)

For the (limiting) $2d_{0}/d$ fraction of the “bad” chunks, their sequential
encodings may have one or more pairs of tokens which appear more than
$\log(d)$ times consecutively.

Define $\mathcal{E}_{i}=\\{X(\textsf{chunk}_{i},\textsf{Dict})=1\\}$ where
$\textsf{Dict}=\textsf{Dict}_{d}$ is the dictionary returned by Algorithm 1
and consider the unigram model
$Q_{\text{uni}}(\bm{t})=\frac{1}{2}Q_{1}(\bm{t})+\frac{1}{2}Q_{2}(\bm{t})$,
which is the uniform mixture of two models,

$\displaystyle
Q_{1}(\bm{t})\propto\frac{1}{(2|\mathcal{A}|)^{|\bm{t}|}},\quad\text{ and
}\quad
Q_{2}(\bm{t})=\mathbb{E}\left[\frac{n_{\bm{t}}^{1}}{|\textsf{enc}_{\text{BPE.split}}(\textsf{chunk}_{1})|}\middle|\mathcal{E}_{1}^{c}\right],$
(119)

and let
$Q_{\text{uni}}(\bm{t}_{1},\cdots,\bm{t}_{i})=Q_{\\#}(j)\prod_{j=1}^{i}Q_{\text{uni}}(\bm{t}_{i})$
for some distribution $Q_{\\#}(i)$ over the number of tokens to be chosen
later. We will analyze the case where the total number of chunks $\ell$ is
finite and take the limit $m\to\infty$ later. Then, the overall loss of the
algorithm is,

$\displaystyle\vspace{-1em}\mathcal{L}_{m}(Q_{\text{uni}}\circ\textsf{enc}(\cdot))$
(120) $\displaystyle=-\mathbb{E}[\log
Q_{\text{uni}}(\textsf{enc}_{\text{BPE.split}}(\bm{s}))]$ (121)
$\displaystyle=-\sum_{\bm{t}\in\textsf{Dict}}\mathbb{E}[n_{\bm{t}}\log
Q_{\text{uni}}(\bm{t})+\log
Q_{\text{uni}}(|\textsf{enc}_{\text{BPE.split}}(\bm{s})|)]$ (122)
$\displaystyle\overset{(i)}{=}-\sum_{i=1}^{\ell}\mathbb{E}\left[\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}^{i}\log
Q_{\text{uni}}(\bm{t})\right]+\log(m)$ (123)
$\displaystyle=-\sum_{i=1}^{\ell}\mathbb{E}\left[\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}^{i}\log
Q_{\text{uni}}(\bm{t})\middle|\mathcal{E}_{i}\right]\Pr(\mathcal{E}_{i})+\mathbb{E}\left[\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}^{i}\log
Q_{\text{uni}}(\bm{t})\middle|\mathcal{E}_{i}^{c}\right]\Pr(\mathcal{E}_{i}^{c})+\log(m).$
(124)

where $n_{\bm{t}}^{i}$ is the number of times $\bm{t}$ is observed in the BPE
encoding of $\textsf{chunk}_{i}$ and $(i)$ uses the fact that
$|\textsf{enc}_{\text{BPE.split}}(\bm{s})|$ follows some distribution
supported on $[m]$, which implies its entropy is upper bounded by $\log(m)$.
First observe that,

$\displaystyle\sum_{i=1}^{\ell}\mathbb{E}\left[\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}^{i}\log
Q_{\text{uni}}(\bm{t})\middle|\mathcal{E}_{i}^{c}\right]$
$\displaystyle\leq\sum_{i=1}^{\ell}\mathbb{E}\left[|\textsf{enc}_{\text{BPE}}(\textsf{chunk}_{i})|\cdot\sum\nolimits_{\bm{t}\in\textsf{Dict}}\frac{n_{\bm{t}}^{i}}{|\textsf{enc}_{\text{BPE}}(\textsf{chunk}_{i})|}\log
Q_{\text{uni}}(\bm{t})\middle|\mathcal{E}_{i}^{c}\right]$ (125)
$\displaystyle\overset{(i)}{\leq}\ell\left(\frac{2dH_{\infty}+O(d/\log(d))}{\log(d)}\right)\sum\nolimits_{\bm{t}\in\textsf{Dict}}Q_{2}(\bm{t})\log
Q_{\text{uni}}(\bm{t})$ (126)

where $(i)$ uses the upper bound on
$|\textsf{enc}_{\text{BPE.split}}(\textsf{chunk}_{i})|$ under the event
$\mathcal{E}_{i}^{c}$ (eq. 118). Since
$Q_{\text{uni}}(\bm{t})=\frac{1}{2}Q_{1}(\bm{t})+\frac{1}{2}Q_{2}(\bm{t})\geq\frac{1}{2}Q_{2}(\bm{t})$
and $Q_{2}$ is a distribution supported on at most $d$ tokens, this term
results in the upper bound,

$\displaystyle\sum_{i=1}^{\ell}\mathbb{E}\left[\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}^{i}\log
Q_{\text{uni}}(\bm{t})\middle|\mathcal{E}_{i}^{c}\right]$
$\displaystyle\leq\ell\left(\frac{2dH_{\infty}+O(d/\log(d))}{\log(d)}\right)\log(2d).$
(127)

On the other hand, since $Q_{\text{uni}}(\bm{t})\geq\frac{1}{2}Q_{1}(\bm{t})$,

$\displaystyle\sum_{i=1}^{\ell}\mathbb{E}\left[\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}^{i}\log(1/Q_{\text{uni}}(\bm{t}))\middle|\mathcal{E}_{i}\right]$
$\displaystyle\leq\sum_{i=1}^{\ell}\mathbb{E}\left[\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}^{i}\log(2/Q_{1}(\bm{t}))\middle|\mathcal{E}_{i}\right]$
(128)
$\displaystyle\leq\sum_{i=1}^{\ell}\mathbb{E}\left[\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}^{i}\left(\log(2)+|\bm{t}|\log(2|\mathcal{A}|)\right)\middle|\mathcal{E}_{i}\right]$
(129) $\displaystyle\leq\ell d\log(2)+\ell d\log(2|\mathcal{A}|)$ (130)

where the last inequality uses the fact that
$\sum_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}^{i}\leq d$ and
$\sum_{\bm{t}\in\textsf{Dict}}|\bm{t}|n_{\bm{t}}^{i}=d$ computes the length of
$\textsf{chunk}_{i}$.

Overall, since $\sum_{i=1}^{\ell}\Pr(\mathcal{E}_{i})\leq 2d_{0}/d$ by eq.
118, combining this with eqs. 127, 130 and 124,

$\displaystyle\mathcal{L}_{m}(Q_{\text{uni}}\circ\textsf{enc}(\cdot))\leq\left(1-\frac{2d_{0}}{d}\right)\ell\left(\frac{2dH_{\infty}+O(d/\log(d))}{\log(d)}\right)\log(2d)+\frac{2d_{0}}{d}\ell
d\log(4|\mathcal{A}|).$ (131)

Dividing throughout by the length of the character sequence
$m\in[d(\ell-1),d\ell]$ and letting $\ell\to\infty$,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}(\cdot))\leq\mathcal{L}(Q_{\text{uni}}\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}|).$
(132)

###  Appendix C Additional Theoretical Results I: Learning the likelihood
model

The guarantees we prove in Theorems 4.1, 4.5 and 4.7 on various tokenizers
assume that the downstream model is trained optimally. In practice, these
models are trained from a finite dataset and the sample complexity of learning
this likelihood model scales with the number of tokens in the dictionary. In
this section, we step away from the transformer architecture and focus on
analyzing the performance of a simple estimator for the unigram model based on
Laplace smoothing. We leave the problem of analyzing the finite-sample
statistical error of simple transformer models trained with gradient descent
as an interesting open direction for future research.

The result of Theorem 4.1 establishes that under appropriate assumptions on
the Markov source, there exists a tokenizer $\mathcal{T}$ and a unigram model
over tokens $Q^{\star}\in\mathcal{Q}_{1\text{-gram}}$ such that,

$\displaystyle\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[\log(1/Q^{\star}(\textsf{enc}(\bm{s}))\right]$
(133)
$\displaystyle\qquad\qquad\leq(1+\varepsilon)\cdot\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[\log(1/P(\bm{s}))\right]$
(134)

Or in other words,

$\displaystyle\lim_{m\to\infty}\frac{1}{m}\textsf{KL}(P,Q^{\star}(\textsf{enc}(\cdot)))\leq\varepsilon\cdot\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[\log(1/P(\bm{s}))\right].$
(135)

This implies that with the appropriate tokenization, the measure associated to
the string by the best unigram model over tokens is close to that induced by
the true Markov distribution over characters in KL divergence. In this
section, we establish finite-sample guarantees on learning $Q^{\star}$
specifically for the LZW tokenizer. The approach we consider for distribution
learning is a smoothed Laplace estimator described in more detail in Algorithm
2.

For any constant $\theta\in(0,1)$, define $\mathcal{E}_{\theta}$ as the event
that every maximal token $\bm{t}$ (Definition A.4) in the LZW dictionary
satisfies $1/d^{1-\theta}\geq\max_{a}P(\bm{t}|a)\geq\delta/d^{1+\theta}$. By
Lemmas A.9 and A.10 when the LZW tokenizer is trained on a dataset of size
$\widetilde{\Omega}_{\delta}(d)$ drawn from a stochastic source satisfying
Assumption 4.2, $\mathcal{E}_{\theta}$ occurs with probability $\geq
1-d^{-\Omega_{\theta,\delta}(\log(d))}$.

######  Theorem C.1.

Consider any constant $\theta\in(0,1)$, failure probability $\eta\in(0,1)$ and
approximation error $\xi\in(0,1)$. Assume that the learnt LZW tokenizer
$\mathcal{T}_{\text{LZW}}$ satisfies the event $\mathcal{E}_{\theta}$, which
occurs with probability $\geq 1-d^{-\Omega_{\theta,\delta}(\log(d))}$. Assume
that $d^{1-3\theta}\geq 1+\delta^{-2}$ and that the stochastic source
satisfies Assumption 4.2. For an absolute constant $C>0$, assume that the size
of the training dataset is at least $n_{\text{lm}}^{\star}(\xi)$, where,

$\displaystyle
n_{\text{lm}}^{\star}\triangleq\frac{Cd^{1+\theta}\log^{3}(d/\eta\delta)\log\log(d/\eta)}{\delta\xi^{2}}$
(136)

Then, Algorithm 2 learns a unigram 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))$
(137)

with probability $\geq 1-\eta$.

In conjunction with Theorem 4.5, this gives end-to-end guarantees on the
cross-entropy loss of the LZW tokenizer (with vocabulary size $\leq d$) with
the Laplace estimator as the downstream unigram model. We instantiate this
result choosing $\theta=0.01$ in Theorem C.1.

######  Corollary C.2.

Choose any $\xi\in(0,1)$. Suppose the data source satisfies Assumption 4.2. On
a dataset of size $\widetilde{\Omega}_{\delta}(d)$ drawn from the source,
train an LZW tokenizer $\mathcal{T}_{\text{LZW}}$ with $d$ tokens.
Subsequently, using Algorithm 2, learn a unigram model $\widehat{Q}$ using a
dataset of size at least $\widetilde{\Omega}(d^{1.01}/\delta\xi^{2})$ drawn
from the source. Then, with probability $\geq
1-d^{-\Omega_{\delta}(\log(d))}$,

$\displaystyle\mathcal{L}(\widehat{Q}\circ\textsf{enc}_{\text{gre}}(\cdot))\leq\frac{1+\xi}{1-\varepsilon}\min_{Q}\mathcal{L}(Q),$
(138)

where $\varepsilon=\frac{\log(1/\delta)}{0.99\log(d)}$.

The analysis of Theorem C.1 relies on showing that the distribution over
tokens induced when a string sampled from the data source is encoded into
tokens by the greedy encoder and the LZW dictionary is a Markov process. In
general, given a set of previously sampled tokens
$\bm{t}_{1},\cdots,\bm{t}_{i}$, the next token $\bm{t}_{i+1}$ is sampled from
the distribution $P(\bm{t}_{i+1}|\bm{t}_{i};\forall j\in[i],\
\bm{t}_{i-j+1}\cdots\bm{t}_{i}\bm{t}_{i+1}\not\in\textsf{Dict})$. The
conditioning is to simply guarantee that the previous tokens which were
sampled were indeed maximal, since if
$\bm{t}_{i}\bm{t}_{i+1}\in\textsf{Dict}$, then the previous token returned
would in fact have been this longer token and not $\bm{t}_{i}$ (and likewise
for $\bm{t}_{i-1}\bm{t}_{i}\bm{t}_{i+1}$ and so on). While in general, this
process is complicated and depends on all the previous tokens sampled, for the
LZW dictionary, we show that the conditioning $\\{\forall j\in[i],\
\bm{t}_{i-j+1}\cdots\bm{t}_{i}\bm{t}_{i+1}\not\in\textsf{Dict}\\}$ can be
removed, thereby resulting in a simple Markov process over tokens.

Furthermore, we establish that this Markov process has a relatively large
spectral gap. The optimal unigram model ends up being the stationary
distribution over tokens induced by greedy encoder. Given the large spectral
gap of the Markov process over tokens, estimating the stationary distribution
of this process in KL divergence ends up being closely related to estimating a
distribution from i.i.d. samples in the same metric. For this problem, the de-
facto choice of estimator is the Laplace estimator, and several existing
results provide finite-sample bounds on the KL divergence [Braess and Sauer,
2004, Han et al., 2021, Mourtada and Gaïffas, 2022]. The Laplace estimator
(Line 6 of Algorithm 2) is simply a smoothed empirical estimate to account for
the degeneracy of the KL divergence in its second argument as any coordinate
approaches $0$. The non-i.i.d.ness of the Markov process is circumvented by
using concentration inequalities which are a function of the spectral gap
[Naor et al., 2020].

Algorithm 2 Training likelihood model on tokens

1:Input: A training dataset of size $n_{\text{lm}}$, likelihood model class
$\mathcal{Q}$, likelihood model training algorithm TrainLM

2:Output: Likelihood model $Q\in\mathcal{Q}$.

3:Tokenize the training dataset into a sequence of tokens
$\mathcal{T}=(\bm{t}_{1},\cdots,\bm{t}_{i})$.

4:Train a likelihood model $Q$ on the tokenized dataset $\mathcal{T}$ using
the $\textsf{TrainLM}(\mathcal{T},\mathcal{Q})$ subroutine.

5: // In the case of $\mathcal{Q}=\mathcal{Q}_{1\text{-gram}}$ use the Laplace
estimator

6:def $\textsf{TrainLM}(\mathcal{T},\mathcal{Q}_{1\text{-gram}})$:

7:Truncate the dataset to the first $n^{\prime}=\lfloor
n_{\text{lm}}/\ell_{\max}\rfloor$ tokens where
$\ell_{\max}=4\log(d|\mathcal{A}|)/\delta$. Let the truncated dataset be
$\mathcal{T}_{\text{trunc}}$

8:Construct the unigram model $\widehat{Q}$ with
$\widehat{Q}_{\\#}=\text{Unif}([m])$ and
$\widehat{Q}_{\text{tok}}(\bm{t})=\frac{n_{\bm{t}}+1}{n_{\bm{t}}+|\textsf{Dict}|}$.

9: // $n_{\bm{t}}$ is the number of times $\bm{t}$ appears in
$\mathcal{T}_{\text{trunc}}$.

10: // Test sequences are assumed to be of length $m$.

####  C.1 Proof of Theorem C.1

Since $\mathcal{T}_{\text{LZW}}$ uses the greedy encoder, the cross-entropy
loss of the unigram model learnt by Algorithm 2 is,

$\displaystyle\mathcal{L}(\widehat{Q}\circ\textsf{enc}_{\text{gre}}(\cdot))-\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}_{\text{gre}}(\cdot))$
(139)
$\displaystyle=\max_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathbb{E}[\log(Q(\textsf{enc}_{\text{gre}}(\bm{s}))/\widehat{Q}(\textsf{enc}_{\text{gre}}(\bm{s})))]$
(140)
$\displaystyle\overset{(i)}{=}\max_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[|\textsf{enc}_{\text{gre}}(\bm{s})|\sum_{\bm{t}\in\textsf{Dict}}\frac{n_{\bm{t}}}{|\textsf{enc}_{\text{gre}}(\bm{s})|}\log(Q_{\text{tok}}(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t}))\right]+\frac{\log(m)}{m}$
(141)
$\displaystyle\overset{(ii)}{\leq}\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[|\textsf{enc}_{\text{gre}}(\bm{s})|\sum_{\bm{t}\in\textsf{Dict}}\frac{n_{\bm{t}}}{|\textsf{enc}_{\text{gre}}(\bm{s})|}\log\left(\frac{n_{\bm{t}}/|\textsf{enc}_{\text{gre}}(\bm{s})|}{\widehat{Q}_{\text{tok}}(\bm{t})}\right)\right]+\frac{\log(m)}{m}$
(142)

where in $(i)$ we use the fact that $\widehat{Q}_{\\#}=\text{Unif}([m])$ and
in $(ii)$ we take the $\max\\{\cdot\\}$ inside the limit and the expectation
(Fatou’s lemma and Jensen’s inequality) and plug in the maximizer of the
negative cross-entropy,
$Q_{\text{tok}}(\bm{t})=\frac{n_{\bm{t}}}{|\textsf{enc}_{\text{gre}}(\bm{s})|}$.
Note that
$\lim_{m\to\infty}\frac{n_{\bm{t}}}{|\textsf{enc}_{\text{gre}}(\bm{s})|}\overset{\text{a.s.}}{=}Q_{\text{MLE}}(\bm{t})$
by Lemma A.3. Moreover, since $|\textsf{enc}(\bm{s})|/m\leq 1$ and
$\widehat{Q}_{\text{tok}}(\bm{t})>0$ surely, by the Dominated Convergence
Theorem,

$\displaystyle\mathcal{L}(\widehat{Q}\circ\textsf{enc}_{\text{gre}}(\cdot))-\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}_{\text{gre}}(\cdot))$
$\displaystyle\leq\lim_{m\to\infty}\frac{1}{m}\mathbb{E}[|\textsf{enc}_{\text{gre}}(\bm{s})|]\cdot\textsf{KL}(Q_{\text{MLE}},\widehat{Q}_{\text{tok}})$
(143)

By eq. 38, we have that for any tokenizer using the greedy encoder,

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

Furthermore under the event $\mathcal{E}_{\theta}$ which implies that the
learnt dictionary is $(1-\theta)$-heavy hitting (cf. Definition A.4), which
implies that,

$\displaystyle H(Q_{\text{MLE}},P)\geq(1-\theta)\log(d).$ (145)

Therefore, by almost sure boundedness, we have that,

$\displaystyle\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[|\textsf{enc}_{\text{gre}}(\bm{s})|\right]\leq\frac{H_{\infty}}{(1-\theta)\log(d)-\log(1/\delta)}\leq\frac{\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}(\cdot))}{(1-\theta)\log(d)-\log(1/\delta)}$
(146)

Putting this together with eq. 143, we have that,

$\displaystyle\mathcal{L}(\widehat{Q}\circ\textsf{enc}_{\text{gre}}(\cdot))\leq\left(1+\textsf{KL}(Q_{\text{MLE}},\widehat{Q}_{\text{tok}})\right)\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}_{\text{gre}}(\cdot)),$
(147)

which uses the assumption $(1-\theta)\log(d)\geq 1+\log(1/\delta)$. In the
remainder of the proof we upper bound the KL term.

By the law of large numbers established in eq. 154 and the fact that
$\frac{n_{\bm{t}}}{\sum_{\bm{t}^{\prime}}n_{\bm{t}^{\prime}}}\in[0,1]$, we
have that,

$\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]=\lim_{m\to\infty}\frac{\mathbb{E}\left[n_{\bm{t}}\right]}{\mathbb{E}\left[\sum\nolimits_{\bm{t}^{\prime}}n_{\bm{t}^{\prime}}\right]}=\pi(\bm{t}),$
(148)

where $\pi(\bm{t})$ denote the stationary distribution over tokens induced by
the greedy encoding process, which exists for the LZW tokenizer. This
distribution is in fact an ergodic Markov process, as we discuss next.

By Lemmas A.9 and A.10, for any constant $\theta\in(0,1)$, with probability
$\geq 1-d^{-\Omega_{\theta,\delta}(\log(d))}$, every maximal token in the the
LZW dictionary satisfies
$1/d^{1-\theta}\geq\max_{a}P(\bm{t}|a)\geq\delta/d^{1+\theta}$. Let
$S_{\text{gre}}$ denote the set of tokens which have a non-zero probability
(over a string drawn from the Markov source) of being chosen by the greedy
encoder while encoding the string. More importantly, note that for any
sequence of tokens $\bm{t}_{1},\cdots,\bm{t}_{i}$, the next token is
necessarily in $S_{\text{gre}}$ and can be any token in this set. The reason
for this is that for any $\bm{t}_{i},\bm{t}\in S_{\text{gre}}$, the
concatenation $\bm{t}_{i}\bm{t}\not\in S_{\text{gre}}$ since
$\max_{a\in\mathcal{A}}P(\bm{t}_{i}\bm{t}|a)\leq 1/\delta d^{2(1-\theta)}$,
which is smaller than the
$\max_{a\in\mathcal{A}}P(\bm{t}^{\prime}|a)\geq\delta/d^{1+\theta}$ for any
token $\bm{t}^{\prime}\in S_{\text{gre}}$ as long as $d^{1-3\theta}\geq
1/\delta^{2}$. This constraint implies that in the sampling procedure in
Figure 7, it suffices to drop the conditioning on the event
$\bm{t}_{j}\bm{t}_{j+1}\cdots\bm{t}_{i}\bm{t}\not\in\textsf{Dict}$ while
sampling the next token $\bm{t}$. This condition automatically implies that
the sequence of tokens conditionally follows a Markov process with
$\Pr(\bm{t}_{i+1}=\bm{t}|\bm{t}_{1},\cdots,\bm{t}_{i})=P(\bm{t}|\textsf{last}(\bm{t}_{i}))$.
Since the probability of every transition is lower bounded, this means that
the Markov chain is ergodic. Moreover, the pseudo-spectral gap [Naor et al.,
2020], $1-\lambda$ can be lower bounded by the Dobrushin contraction
coefficient, $\kappa$,

$\displaystyle 1-\lambda\leq\kappa$
$\displaystyle\triangleq\max_{(\bm{t},\bm{t}^{\prime})\in\textsf{Dict}^{2}}\|\Pr(\cdot|\bm{t})-\Pr(\cdot|\bm{t}^{\prime})\|_{\text{TV}}$
(149)
$\displaystyle=\max_{(\bm{t},\bm{t}^{\prime})\in\textsf{Dict}^{2}}1-\sum_{\bm{t}^{\prime\prime}\in\textsf{Dict}}\min\\{\Pr(\bm{t}^{\prime\prime}|\bm{t}),\Pr(\bm{t}^{\prime\prime}|\bm{t}^{\prime})\\}$
(150) $\displaystyle\leq 1-\delta d/d^{1+\theta}$ (151)
$\displaystyle=1-\delta d^{-\theta}.$ (152)

Recall that the learner is given a training dataset of $n_{\text{lm}}$
characters to train the likelihood model. By Lemma A.7, with probability $\geq
1-d^{-\Omega(\log(d/\delta)/\delta)}$, in the run of the LZW tokenization
algorithm, every token in the dictionary has length at most
$\ell_{\max}=4\log(d|\mathcal{A}|)/\delta$. Therefore, suppose the learner
always truncates the dataset to the first $n^{\prime}=\lfloor
n_{\text{lm}}/\ell_{\max}\rfloor$ tokens and runs the Laplace estimator on
this truncated dataset. With this, we move onto upper bounding,

$\displaystyle\textsf{KL}(Q_{\text{MLE}},\widehat{Q}_{\text{tok}})=\sum_{\bm{t}\in\textsf{Dict}}\pi(\bm{t})\log\left(\pi(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t})\right)$
(153)

which necessitates lower bounding $\widehat{Q}_{\text{tok}}(\bm{t})$ for every
$\bm{t}$. Recall that the learner’s estimate $\widehat{Q}(\bm{t})$ in
Algorithm 2 is the Laplace estimator,
$\frac{n_{\bm{t}}+1}{\sum_{\bm{t}^{\prime}}n_{\bm{t}^{\prime}}+\textsf{Dict}}$,
where $\\{n_{\bm{t}}\mathrel{\mathop{\mathchar
58\relax}}\bm{t}\in\textsf{Dict}\\}$ is computed by truncating the dataset to
the first $n^{\prime}$ tokens. Firstly, by invoking Corollary 1.3 of Naor et
al. [2020] for the function
$n_{\bm{t}}=\sum_{i=1}^{n^{\prime}}\mathbb{I}(\bm{t}_{i}=\bm{t})$,

$\displaystyle\Pr\left(|n_{\bm{t}}-\mathbb{E}[n_{\bm{t}}]|\geq
c\sqrt{\frac{\mathbb{E}[n_{\bm{t}}]}{1-\lambda}\cdot\log(1/\eta)}\right)\leq\eta$
(154)

for a universal constant $c>0$. In particular, this implies that with
probability $\geq 1-\eta$, simultaneously for all $\bm{t}$,

$\displaystyle|n_{\bm{t}}-\mathbb{E}[n_{\bm{t}}]|\leq\Delta_{\bm{t}}\triangleq\sqrt{\frac{d^{\theta}}{\delta}\mathbb{E}[n_{\bm{t}}]\cdot\log(|\textsf{Dict}|/\eta)}\text{,
and, }\mathbb{E}[n_{\bm{t}}]-n_{\bm{t}}\geq\mathbb{E}[n_{\bm{t}}].$ (155)

Under this event, for any $\bm{t}$, the estimate is lower bounded by,

$\displaystyle\widehat{Q}_{\text{tok}}(\bm{t})=\frac{n_{\bm{t}}+1}{n^{\prime}+|\textsf{Dict}|}$
$\displaystyle\geq\frac{\mathbb{E}[n_{\bm{t}}]+1-\min\\{\mathbb{E}[n_{\bm{t}}],\Delta_{\bm{t}}\\}}{n^{\prime}+|\textsf{Dict}|}$
(156)
$\displaystyle\geq\max\left\\{\pi(\bm{t})-\frac{\left(\Delta_{\bm{t}}-1\right)n^{\prime}+|\textsf{Dict}|\mathbb{E}[n_{\bm{t}}]}{(n^{\prime})^{2}+n^{\prime}|\textsf{Dict}|},\
\frac{1}{n^{\prime}+|\textsf{Dict}|}\right\\}$ (157)
$\displaystyle\geq\max\left\\{\pi(\bm{t})-\frac{\Delta_{\bm{t}}n^{\prime}+|\textsf{Dict}|\mathbb{E}[n_{\bm{t}}]}{(n^{\prime})^{2}},\
\frac{1}{n^{\prime}+|\textsf{Dict}|}\right\\}$ (158)

Suppose the following condition is satisfied,

$\displaystyle
n^{\prime}=\frac{4rd^{\theta}|\textsf{Dict}|\log(|\textsf{Dict}|/\eta)}{\delta}$
(C1)

for some $r\geq 4$. Under this condition, we have that $n^{\prime}\geq
2\sqrt{r}\Delta$ and $n^{\prime}\geq 4r|\textsf{Dict}|$.

Case I. $\Delta_{\bm{t}}n^{\prime}\geq|\textsf{Dict}|\mathbb{E}[n_{\bm{t}}]$.

In this case, we have the upper bound,

$\displaystyle\widehat{Q}_{\text{tok}}(\bm{t})$
$\displaystyle\geq\max\left\\{\pi(\bm{t})-\frac{2\Delta_{\bm{t}}}{n^{\prime}},\
\frac{1}{n^{\prime}+|\textsf{Dict}|}\right\\}$ (159)
$\displaystyle=\max\left\\{\pi(\bm{t})-2\frac{\sqrt{\frac{d^{\theta}}{\delta}\mathbb{E}[n_{\bm{t}}]\cdot\log(|\textsf{Dict}|/\eta)}}{n^{\prime}},\
\frac{1}{n^{\prime}+|\textsf{Dict}|}\right\\}$ (160)
$\displaystyle\geq\max\left\\{\pi(\bm{t})-\sqrt{\frac{\pi(\bm{t})}{r|\textsf{Dict}|}},\
\frac{1}{2n^{\prime}}\right\\}.$ (161)

where the last inequality uses eq. C1.

Consider two sub-cases,

Sub-case I. $\pi(\bm{t})\geq 2/r|\textsf{Dict}|$. Define this event
$\mathcal{C}_{\textsf{I}}$.

Here,

$\displaystyle\pi(\bm{t})\log(\pi(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t}))\leq-\pi(\bm{t})\log\left(1-\sqrt{\frac{1}{\pi(\bm{t})r|\textsf{Dict}|}}\right)\leq\frac{3}{2}\sqrt{\frac{\pi(\bm{t})}{r|\textsf{Dict}|}}.$
(162)

Sub-case II. $\pi(\bm{t})\leq 2/r|\textsf{Dict}|$. Define this event
$\mathcal{C}_{\textsf{II}}$.

Here,

$\displaystyle\pi(\bm{t})\log(\pi(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t}))\leq\pi(\bm{t})\log\left(2n^{\prime}\pi(\bm{t})\right)$
$\displaystyle\leq\max\left\\{0,\frac{2}{r|\textsf{Dict}|}\log\left(\frac{4n^{\prime}}{r|\textsf{Dict}|}\right)\right\\}$
(163)
$\displaystyle\leq\frac{2}{r|\textsf{Dict}|}\log\left(16d^{\theta}\log(|\textsf{Dict}|/\eta)\right)$
(164)

Case II. $\Delta_{\bm{t}}n^{\prime}<|\textsf{Dict}|\mathbb{E}[n_{\bm{t}}]$.
Define this event $\mathcal{C}_{\textsf{III}}$.

In this case we have the upper bound,

$\displaystyle\widehat{Q}_{\text{tok}}(\bm{t})$
$\displaystyle\geq\pi(\bm{t})-\frac{2|\textsf{Dict}|\mathbb{E}[n_{\bm{t}}]}{(n^{\prime})^{2}}\geq\pi(\bm{t})-\frac{\pi(\bm{t})}{2r}$
(165)

where the last inequality follows from eq. C1. This implies that,

$\displaystyle\pi(\bm{t})\log(\pi(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t}))\leq-\pi(\bm{t})\log(1-1/2r)\leq\frac{\pi(\bm{t})}{r}.$
(166)

By using the geometric ergodicity of this Markov process (eq. 152), when
$n^{\prime}$ tokens are sampled from an arbitrary initial distribution,

$\displaystyle\left(1-\kappa^{n^{\prime}}\right)\pi(\bm{t})\leq\frac{\mathbb{E}[n_{\bm{t}}]}{n^{\prime}}\leq\kappa^{n^{\prime}}+\left(1-\kappa^{n^{\prime}}\right)\pi(\bm{t})\implies\pi(\bm{t})\leq\frac{\widehat{Q}_{\text{tok}}(\bm{t})}{1-e^{-4r|\textsf{Dict}|\log(|\textsf{Dict}|/\eta)}}=\frac{\widehat{Q}_{\text{tok}}(\bm{t})}{1-d^{-r}}$
(167)

where in the implication, we use the condition on $n^{\prime}$ in eq. C1 and
the bound on the contraction coefficient $\kappa$ in eq. 152.

$\displaystyle\textsf{KL}(Q_{\text{MLE}},\widehat{Q}_{\text{tok}})$ (168)
$\displaystyle=\sum_{\bm{t}\in\textsf{Dict}}\pi(\bm{t})\log(\pi(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t}))$
(169)
$\displaystyle\leq\sum_{\bm{t}\in\textsf{Dict}}\frac{\pi(\bm{t})}{1-d^{-r}}\log(\pi(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t}))-\log(1-d^{-r})$
(170)
$\displaystyle\leq\frac{1}{1-d^{-r}}\sum_{\bm{t}\in\textsf{Dict}}\mathbb{I}(\mathcal{C}_{\textsf{I}})\pi(\bm{t})\log(\pi(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t}))+\mathbb{I}(\mathcal{C}_{\textsf{II}})\pi(\bm{t})\log(\pi(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t}))+\mathbb{I}(\mathcal{C}_{\textsf{III}})\pi(\bm{t})\log(\pi(\bm{t})/\widehat{Q}_{\text{tok}}(\bm{t}))+2d^{-r}$
(171)
$\displaystyle\leq\frac{1}{1-d^{-r}}\sum_{\bm{t}\in\textsf{Dict}}\underbrace{\vphantom{\sum_{\bm{t}\in\textsf{Dict}}}\mathbb{I}(\mathcal{C}_{\textsf{I}})\frac{3}{2}\sqrt{\frac{\pi(\bm{t})}{r|\textsf{Dict}|}}}_{\lx@cref{creftype~refnum}{eq:subcase1}}+\underbrace{\vphantom{\sum_{\bm{t}\in\textsf{Dict}}}\mathbb{I}(\mathcal{C}_{\textsf{II}})\frac{2}{r|\textsf{Dict}|}\log\left(16d^{\theta}\log(|\textsf{Dict}|/\eta)\right)}_{\lx@cref{creftype~refnum}{eq:subcase2}}+\underbrace{\vphantom{\sum_{\bm{t}\in\textsf{Dict}}}\mathbb{I}(\mathcal{C}_{\textsf{III}})\frac{\pi(\bm{t})}{r}}_{\lx@cref{creftype~refnum}{eq:case2}}+2d^{-r}$
(172)
$\displaystyle\leq\frac{1}{1-d^{-r}}\left(\frac{3}{2}\sqrt{\frac{|\textsf{Dict}|}{r|\textsf{Dict}|}}+\frac{2}{r}\log(16d^{\theta}\log(|\textsf{Dict}|/\eta))+\frac{1}{r}\right)+2d^{-r}$
(173)
$\displaystyle\leq\frac{5}{\sqrt{r}}\log(16d^{\theta}\log(|\textsf{Dict}|/\eta))$
(174)

Combining with eq. 147, we get the bound,

$\displaystyle\mathcal{L}(\widehat{Q}\circ\textsf{enc}_{\text{gre}}(\cdot))$
$\displaystyle\leq\left(1+\textsf{KL}(Q_{\text{MLE}},\widehat{Q})\right)\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}_{\text{gre}}(\cdot))$
(175)
$\displaystyle\leq\left(1+\frac{5}{\sqrt{r}}\log(16d^{\theta}\log(d/\eta))\right)\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}_{\text{gre}}(\cdot)).$
(176)

Rescaling $r$ to be $r(\log(16d^{\theta}\log(d/\eta)))^{2}$ completes the
proof.

###  Appendix D Additional Theoretical Results II: The generalization ability
of tokenizers

The proofs of the upper bounds in the paper (Theorems 4.5 and 4.7) relied on
showing that the entropy $H(Q_{\text{MLE}},P)$ is large, or in other words,
the algorithm typically encodes new strings into long length (i.e. low
probability under $P$) tokens. This statement about generalization to new
strings is fundamentally different from having a tokenizer which compresses
the training dataset well. In other words, consider the following
modification: the measure $Q_{\text{MLE}}$ is defined as the expected
empirical distribution over tokens when a new string is encoded into tokens,
and not on the source dataset used to construct the dictionary. Suppose the
definition of $Q_{\text{MLE}}$ is changed to the empirical distribution over
tokens in the source dataset. Under this new definition of the MLE unigram
model, the largeness of the $H(Q_{\text{MLE}},P)$ metric, in a sense, captures
compressing the source dataset well. However, we show that in general, this
does not result in good tokenizers that minimize the population cross-entropy
loss, suffering from
$\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}(\cdot))\approx
H(\pi)\gg H_{\infty}$.

######  Theorem D.1.

Consider the stochastic source in example 2.2 having entropy rate
$H_{\infty}=\delta\log(1/\delta)+(1-\delta)\log(1/(1-\delta))$. Consider a
training dataset of size $n$. For a dictionary Dict and
$\bm{t}\in\textsf{Dict}$, define
$\widehat{Q}_{\text{MLE}}(\bm{t})=\frac{n_{\bm{t}}(\bm{s}_{\text{src}})}{|\textsf{enc}(\bm{s}_{\text{src}})|}$
as the empirical distribution over tokens induced by the greedy encoder when
encoding the training dataset, $\bm{s}_{\textsf{src}}$. There exists a
dictionary Dict such that with probability $\geq 1-e^{-\Omega(\sqrt{n})}$ over
the training dataset,

$\displaystyle H(\widehat{Q}_{\text{MLE}},P_{\gamma})\geq
nH_{\infty}(1-O(n^{-1/4}))$ (177)

is large. However, for this dictionary, for any encoding algorithm (including
the greedy encoder), the resulting tokenizer
$\mathcal{T}=(\textsf{Dict},\emptyset,\textsf{enc}(\cdot),\textsf{dec}(\cdot))$
satisfies,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}(\cdot))\geq(1-\varepsilon)H(\pi)$
(178)

where $\varepsilon=2ne^{-nH_{\infty}(1-O(n^{-1/4}))}$.

###### Proof.

Suppose the entire training dataset was compressed into a single token,
$\bm{t}_{\text{src}}$. The dictionary is $\mathcal{A}\cup\bm{t}_{\text{src}}$.
In the following argument, we show that the number of occurrences,
$n_{\bm{t}_{\text{src}}}$, of the entire training dataset
$\bm{t}_{\text{src}}$ in a new string of length $m$ generated from the
stochastic source, $\bm{s}$, converges to its expectation as $m\to\infty$. Let
$\pi_{n}^{(i)}$ denote the stationary distribution of the Markov process
induced by the stochastic source over length-$n$ strings with a shift of $i$
from the starting position, and let $n_{\bm{t}}^{(i)}$ denote the number of
times $\bm{t}$ appears in the training dataset starting at the position $i+rn$
for some $r>0$. Then,

$\displaystyle\lim_{m\to\infty}\frac{n_{\bm{t}_{\text{src}}}}{m}=\frac{1}{n}\lim_{m\to\infty}\sum_{i=0}^{n-1}\frac{n_{\bm{t}_{\text{src}}}^{(i)}}{m/n}\overset{\text{a.s.}}{=}\frac{1}{n}\sum_{i=0}^{n-1}\mathbb{E}_{\bm{t}^{\prime}\sim\pi_{n}^{(i)}}[P(\bm{t}_{\text{src}}|\bm{t}^{\prime})]\leq\max_{a\in\mathcal{A}}P(\bm{t}_{\text{src}}|a).$
(179)

The second equation follows by considering the Markov process induced over
length $n$ strings and applying the Krylov–Bogolyubov argument for ergodic and
homogeneous Markov processes.

In Lemma D.2, we show that with probability $\geq 1-e^{-\Omega(\sqrt{n})}$,
the token $\bm{t}_{\text{src}}$ constructed from the source dataset satisfies,
$\max_{a\in\mathcal{A}}P(\bm{t}|a)\leq e^{-nH_{\infty}(1-O(n^{-1/4}))}$. In
other words, the source string has exponentially small probability. Combining
this with eq. 179, with probability $\geq 1-e^{-\Omega(\sqrt{n})}$ over the
source dataset, the number of occurrences of the substring
$\bm{t}_{\text{src}}$ in a new string $\bm{s}$ is upper bounded by,

$\displaystyle\lim_{m\to\infty}\frac{n_{\bm{t}_{\text{src}}}}{m}\overset{\text{a.s.}}{\leq}e^{-nH_{\infty}(1-O(n^{-1/4}))}\triangleq\varepsilon/2n.$
(180)

By the Krylov–Bogolyubov argument, for each $a\in\mathcal{A}=\\{0,1\\}$,
$\lim_{m\to\infty}\frac{n_{a}}{m}\overset{\text{a.s.}}{=}\pi(a)$. More
importantly, the number of times $a$ is made as a token is upper bounded by
$n_{a}$ and lower bounded by $n_{a}-nn_{\bm{t}_{\text{src}}}$. Therefore,

$\displaystyle(1-\varepsilon)\pi(a)=\pi(a)-\frac{\varepsilon}{2}\overset{\text{a.s.}}{\leq}\lim_{m\to\infty}\frac{n_{a}}{m}\overset{\text{a.s.}}{\leq}\pi(a)=\frac{1}{2}$
(181)

Finally, putting everything together,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))$
$\displaystyle=\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}-\frac{1}{m}\mathbb{E}\left[\log(Q_{\\#}(|\textsf{enc}(\bm{s})|)+\sum\nolimits_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}\log
Q_{\text{tok}}(\bm{t})\right]$ (182)
$\displaystyle\geq\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}-\frac{1}{m}\mathbb{E}\left[\sum\nolimits_{a\in\mathcal{A}}n_{a}\log
Q_{\text{tok}}(a)\right]$ (183)
$\displaystyle\overset{(i)}{\geq}\min_{Q\in\mathcal{Q}_{1\text{-gram}}}-(1-\varepsilon)\sum\nolimits_{a\in\mathcal{A}}\pi(a)\log
Q_{\text{tok}}(a)$ (184) $\displaystyle\geq(1-\varepsilon)H(\pi).$ (185)

where $(i)$ follows from the lower bound on $n_{a}/m$ in eq. 181. This
completes the proof. ∎

######  Lemma D.2.

With probability $\geq 1-e^{-\Omega(\sqrt{n})}$ over the source dataset,

$\displaystyle\max_{a\in\mathcal{A}}P(\bm{t}_{\text{src}}|a)\leq
e^{-nH(\delta)(1-O(n^{-1/4}))}.$ (186)

###### Proof.

Let $X$ denote the number of $i\in[n-1]$ such that
$\bm{s}_{i}\neq\bm{s}_{i+1}$ in $\bm{s}$, the stochastic source. Since the
transition of the Markov process only depends on whether the next character is
the same as the previous character, we can write down,

$\displaystyle\max_{a\in\mathcal{A}}\log
P(\bm{t}_{\text{src}}|a)=-(X+1)\log(\delta)-(n-1-X)\log(1-\delta).$ (187)

Note that $X$ is a sum of $n-1$ i.i.d. random variables, since
$\mathbb{I}(\bm{s}_{i}\neq\bm{s}_{i+1})\sim\textsf{Ber}(\delta)$ does not
depend on whether $\bm{s}_{i}=0$ or $=1$. In particular, by Hoeffding’s
inequality, we have that with probability $\geq 1-e^{-\Omega(\sqrt{n})}$,

$\displaystyle\left|\frac{1}{n}\max_{a\in\mathcal{A}}\log
P(\bm{t}_{\text{src}}|a)-H(\delta)\right|\leq O\left(n^{-1/4}\right),$ (188)

which uses the fact that $\mathbb{E}[X]=\delta(n-1)$ and
$H_{\infty}=\delta\log(1/\delta)+(1-\delta)\log(1/(1-\delta))$. Taking an
exponential on both sides proves the statement of the lemma. ∎

###  Appendix E Additional Theoretical Results III: Interaction between the
dictionary and encoding algorithm

In this section, we show another kind of barrier to generalization, which
brings out the relationship between the encoding algorithm and the dictionary.
We show that there exist dictionaries which generalize under the minimal
encoder, i.e. the encoding algorithm which encodes a string into the shortest
number of possible tokens, but at the same time, completely fail to generalize
under the greedy encoder. This means that in the process of constructing good
tokenizers, it does not suffice to think about the dictionary in isolation.
Its interaction with the encoding algorithm is pertinent.

######  Definition E.1 (minimal encoder).

The minimal encoder parses a new string into the fewest possible number of
tokens from the dictionary as possible. Ties are broken arbitrarily.

######  Theorem E.2.

There exists a stochastic source parameterized by $\delta\in(0,0.5)$ and a
dictionary Dict such that under the minimal encoder/decoder pair, the
resulting tokenizer,
$\mathcal{T}=(\textsf{Dict},\emptyset,\textsf{enc}_{\text{min}}(\cdot),\textsf{dec}_{\text{min}}(\cdot))$
generalizes near-optimally,

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

Here the entropy rate of the source, $H_{\infty}$, is
$\delta\log(\sqrt{2}/\delta)+(1-\delta)\log(1/(1-\delta))$. However, the same
dictionary Dict under the greedy encoder/decoder pair, i.e.
$\mathcal{T}^{\prime}=(\textsf{Dict},\emptyset,\textsf{enc}_{\text{gre}}(\cdot),\textsf{dec}_{\text{gre}}(\cdot))$,
generalizes poorly, suffering from cross-entropy scaling as,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\mathcal{L}(Q\circ\textsf{enc}_{\text{gre}}(\cdot))\geq\frac{1-o_{\delta}(1)}{3}H(\pi).$
(190)

where the entropy of the stationary distribution of the source is
$H(\pi)=\frac{1}{2}\log(8)$ and the $1-o_{\delta}(1)$ term is
$(1-\delta)^{2}(1+\delta)^{-1}$.

This means that the greedy encoder is not really compatible with the
dictionary in the sense that the cross-entropy loss of the tokenizer is a
constant multiple away from that achieved by the character-level tokenizer.
The separation between eq. 189, and eq. 190 only manifests as $\delta$ becomes
smaller and smaller.

In this section, we prove that generalization of a dictionary is a function of
the underlying tokenization algorithm used. In particular, the greedy encoder
is not universal, and there exists dictionaries under the minimum-length
encoder/decoder which achieve small cross-entropy loss, which do not
generalize under the greedy encoder/decoder.

We split the proof of Theorem E.2 into two parts. We first define the
stochastic source and dictionary we consider. Then we show that under the
minimum-length encoder, the asymptotic cross-entropy loss is upper bounded by
$H_{\infty}$ up to a constant. Finally, we show that under the greedy-encoder,
the same dictionary suffers from high cross-entropy loss, which is a constant
factor away from that of the character encoder.

####  E.1 Stochastic source and dictionary.

Consider an extension of the switching Markov source in example 2.2 to
$\mathcal{A}=\\{0,1,2\\}$. The Markov chain is described in Figure 10. The
transition of the Markov chain is $P(0|0)=P(1|1)=P(2|2)=1-\delta$, and
$P(1|0)=P(2|1)=\delta$ and $P(2|1)=P(0|1)=\delta/2$, with the remaining
transitions being $0$-probability. For a parameter $\ell>0$ to be instantiated
later, define $S_{\bm{1}}$ (resp. $S_{\bm{0}}$, $S_{\bm{2}}$) as the set of
all-$1$ (resp. all-$0$, all-$2$) strings of length $\leq\ell-1$, including the
empty string. Consider a dictionary composed of the following set of tokens,
$\\{1\bm{s}\mathrel{\mathop{\mathchar 58\relax}}\bm{s}\in S_{\bm{0}}\cup
S_{\bm{1}}\cup S_{\bm{2}}\\}$. Therefore, the tokens follow the template
$10\cdots 0$, $11\cdots 1$ or $12\cdots 2$ and are of length at most $\ell$.
$\ell$ is chosen to be $1+2\log(1/\delta)/\delta$.

$0$$1$$2$$\delta$$\frac{\delta}{2}$$\frac{\delta}{2}$$\delta$ Figure 10:
order-$1$ Markov source used in the proof of Theorem E.2

Although we use the minimal encoder in the statement of Theorem E.2, for the
purpose of analysis, define the following encoding algorithm: if the new
string is prefixed by $10\cdots 0$ or $12\cdots 2$, select the largest prefix
which exists in dictionary and assign it as a token. If the new string starts
with a sequence $11\cdots 1$ of length $x$, consider the first
$\max\\{\ell,x-1\\}$ length prefix and assign it as a token. Finally, if the
string starts with $0$ or $2$, assign that character as token. Once the first
token has been assigned, remove it and repeat.

####  E.2 Minimal encoder achieves the optimal cross-entropy loss up to a
constant.

First consider a simplification of the overall cross-entropy loss,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))$
(191)
$\displaystyle=\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}-\frac{1}{m}\mathbb{E}\left[\log
Q_{\\#}(|\textsf{enc}_{\text{min}}(\bm{s})|)+\sum\nolimits_{\bm{t}\in\textsf{Dict}}n_{\bm{t}}\log
Q_{\text{tok}}(\bm{t})\right]$ (192)
$\displaystyle\leq\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[\log(m)+|\textsf{enc}_{\text{min}}(\bm{s})|\log|\textsf{Dict}|\right],$
(193)

where in the last inequality we upper bound by choosing
$Q_{\\#}=\mathrm{Unif}([m])$ and $Q_{\text{tok}}(\bm{t})=1/|\textsf{Dict}|$.
Note that $|\textsf{Dict}|\leq 2\ell+1$ and letting
$\lim_{m\to\infty}\log(m)/m=0$,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))$
$\displaystyle\leq\lim_{m\to\infty}\frac{1}{m}\mathbb{E}[|\textsf{enc}_{\text{min}}(\bm{s})|\log(2\ell+1)]$
(194)
$\displaystyle\leq\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[|\textsf{enc}(\bm{s})|\log(2\ell+1)\right],$
(195)

where in $(i)$, we replace $|\textsf{enc}_{\text{min}}(\bm{s})|$ by
$|\textsf{enc}(\bm{s})|$, which is the encoder we define in Section E.1. By
definition of the minimal encoder,
$|\textsf{enc}_{\text{min}}(\bm{s})|\leq|\textsf{enc}(\bm{s})|$ surely. Recall
that the encoder $\textsf{enc}(\cdot)$ processes strings in a sequential
(left-to-right) manner. In particular, by a similar argument as Lemma A.3, we
can show that under this encoder, the limit
$n_{\bm{t}}/\sum_{\bm{t}^{\prime}}n_{\bm{t}^{\prime}}$ almost surely converges
to its expectation. More importantly, since,
$\sum_{\bm{t}\in\textsf{Dict}}|\bm{t}|n_{\bm{t}}=m$, we have that,

$\displaystyle\lim_{m\to\infty}\frac{|\textsf{enc}(\bm{s})|}{m}\overset{\text{a.s.}}{=}\frac{1}{\mathbb{E}_{\bm{t}\sim
Q_{\text{MLE}}}[|\bm{t}|]}.$ (196)

converges to some limit almost surely. Therefore, from eq. 195,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))\leq\text{ess}\operatorname*{limsup}\limits_{m\to\infty}\frac{|\textsf{enc}(\bm{s})|}{m}\log(2\ell+1).$
(197)

where the essential lim-sup captures the almost sure limit
$1/\mathbb{E}_{\bm{t}\sim Q_{\text{MLE}}}[|\bm{t}|]$. The almost sure
convergence of $|\textsf{enc}(s)|/m$ also implies that we can let the limit
$m$ go to $\infty$ in any manner, and the limit will remain the same. In
particular, consider a process parameterized by $i^{\star}$ for generating the
source string, such that surely $m\geq i^{\star}$, where the total number of
characters, $m$, is a random variable. As $i^{\star}\to\infty$, we will also
have $m\to\infty$ surely, and so the limit of $|\textsf{enc}(\bm{s})|/m$ under
this modified stochastic process should also converge to the same limit.

Rather than sampling a string of a fixed length $m$ from the source, consider
the following sampling model: for $i^{\star}\to\infty$, sample $i^{\star}$
geometric random variables
$X_{1},\cdots,X_{i^{\star}}\overset{\text{i.i.d.}}{\sim}\textsf{Geo}(\delta)$
and construct the source string as the concatenation of $i^{\star}$ strings
alternating between successive $1$’s and successive $0$’s or $2$’s (with the
choice between the two made uniformly at random), with the $i^{th}$ string of
length $X_{i}+1$. The overall number of characters sampled, $m$, is surely at
least $i^{\star}$.

Under this stochastic process, the size of the encoding of the string is upper
bounded by,

$\displaystyle|\textsf{enc}(\bm{s})|\leq|X_{1}+1|+\sum_{i=2}^{i^{\star}}\left(1+\left(X_{i}+1-\ell\right)_{+}\right)$
(198)

This bound follows from the fact that in any substring $\bm{s}^{\prime}$ of
successive $1$’s followed by a substring $\bm{s}^{\prime\prime}$ of successive
$0$’s or $2$’s, the encoder tokenizes the first
$\max\\{\ell,|\bm{s}^{\prime}|-1\\}$ length prefix of $\bm{s}^{\prime}$ as a
token, and the remaining characters in $\bm{s}^{\prime}$ into individual
tokens except the last. Then, the last character of $\bm{s}^{\prime}$ and the
first $\max\\{\ell-1,|\bm{s}^{\prime\prime}|\\}$ characters of
$\bm{s}^{\prime\prime}$ are assigned as token. The remainder of
$\bm{s}^{\prime\prime}$ is assigned as individual tokens. Each of
$\bm{s}^{\prime}$ or $\bm{s}^{\prime\prime}$ of length $x$, is allocated into
at most $1+(x+1-\ell)_{+}$ tokens.

For any $i$, $\Pr(X_{i}\geq u)=(1-\delta)^{u}$, and therefore, summing over
$u\geq\ell$, we get that
$\mathbb{E}[(X_{i}+1-\ell)_{+}]=\frac{(1-\delta)^{\ell-1}}{\delta}$. With
$\ell=1+2\log(1/\delta)/\delta$, this expectation is upper bounded by
$\delta$. Therefore,

$\displaystyle\lim_{i^{\star}\to\infty}\frac{\mathbb{E}[|\textsf{enc}(\bm{s})|]}{i^{\star}}\leq\lim_{i^{\star}\to\infty}\frac{1}{i^{\star}}\mathbb{E}\left[|X_{1}|+\sum\nolimits_{i=2}^{i^{\star}}\left(1+\left(X_{i}+1-\ell\right)_{+}\right)\right]\leq
1+\delta$ (199)

More importantly, by the strong law of large numbers for a sum of independent
random variables,
$(|X_{1}+1|+\sum_{i=2}^{i^{\star}}(1+(X_{i}+1-\ell)_{+}))/i^{\star}$, and
therefore $|\textsf{enc}(\bm{s})|/i^{\star}$ is asymptotically almost surely
upper bounded as,

$\displaystyle\lim_{i^{\star}\to\infty}\frac{|\textsf{enc}(\bm{s})|}{i^{\star}}\overset{\text{a.s.}}{\leq}1+\delta,$
(200)

On the other hand, the number of characters generated, $m$, equals
$\sum_{i=1}^{i^{\star}}(X_{i}+1)$, and satisfies,
$\lim_{i^{\star}\to\infty}\mathbb{E}[m]/i^{\star}=1+\delta^{-1}$. By another
application of the strong law of large numbers for a sum of independent random
variables,

$\displaystyle\lim_{i^{\star}\to\infty}\frac{m}{i^{\star}}\overset{\text{a.s.}}{=}1+\delta^{-1}.$
(201)

By combining eqs. 200 and 201, we have that,

$\displaystyle\lim_{i^{\star}\to\infty}\frac{|\textsf{enc}(\bm{s})|}{m}\overset{\text{a.s.}}{\leq}\frac{1+\delta}{1+\delta^{-1}}=\frac{1}{\delta}.$
(202)

Finally, combining with eq. 197 and the ensuing discussion, we may upper bound
the limiting cross-entropy loss by,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))\leq\delta\log(2\ell+1)=\delta\log(3+4\log(1/\delta)/\delta).$
(203)

Note for this Markovian source, it is a short calculation to see that,

$\displaystyle
H_{\infty}=\mathbb{E}_{x\sim\pi}[H(P(\cdot|x))]=\delta\log(\sqrt{2}/\delta)+(1-\delta)\log(1/(1-\delta))$
(204)

Note that for any $\delta\leq 1/2$, numerical evaluation gives the inequality,

$\displaystyle
1\leq\frac{\delta\log(3+4\log(1/\delta)/\delta)}{H_{\infty}}\leq 1.273$ (205)

with the approximation factor improving as $\delta$ becomes smaller.
Therefore, this tokenizer achieves a normalized cross-entropy loss which
asymptotically scales as a constant multiple of the entropy rate of the
source.

####  E.3 Greedy-encoder achieves poor cross-entropy loss

Note that the greedy encoder picks the largest prefix of the string which is a
token, assigns and removes it, and iterates on the rest of the string. The
greedy encoder’s behavior is easy to analyze - every string of consecutive
$1$’s in the new string is broken into chunks of length $\ell$ (save
potentially the last chunk) and each chunk is assigned as a token in
$\\{1\bm{s}\mathrel{\mathop{\mathchar 58\relax}}\bm{s}\in
S_{\bm{1}}\\}\subset\textsf{Dict}$. If the length of this substring of
successive $1$’s is not $1,\ell+1,2\ell+1,\cdots$, or in general, $\equiv
1\mod{\ell}$, every character in the next sequence, composed of $0$’s or $2$’s
is tokenized into individual characters.

Similar to eq. 192 to eq. 193, consider a simplification of the overall cross-
entropy loss,

$\displaystyle\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))$
(206)
$\displaystyle=\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}-\frac{1}{m}\mathbb{E}\left[\log
Q_{\\#}(|\textsf{enc}_{\text{gre}}(\bm{s})|)+|\textsf{enc}_{\text{gre}}(\bm{s})|\sum\nolimits_{\bm{t}\in\textsf{Dict}}\frac{n_{\bm{t}}}{|\textsf{enc}_{\text{gre}}(\bm{s})|}\log
Q_{\text{tok}}(\bm{t})\right]$ (207)
$\displaystyle\geq\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}-\frac{1}{m}\mathbb{E}\left[|\textsf{enc}_{\text{gre}}(\bm{s})|\sum\nolimits_{\begin{subarray}{c}\bm{t}\in\textsf{Dict}\\\
Q_{\text{MLE}}(\bm{t})>0\end{subarray}}Q_{\text{MLE}}(\bm{t})\log
Q_{\text{tok}}(\bm{t})\right],$ (208)

where the last equation uses the fact that by Lemma A.3, for the greedy
encoder,
$\lim_{m\to\infty}\frac{n_{\bm{t}}}{|\textsf{enc}_{\text{min}}(\bm{s})|}\overset{\text{a.s.}}{=}Q_{\text{MLE}}(\bm{t})$.
The minimizer of this objective subject to
$\sum_{\bm{t}\in\textsf{Dict}\mathrel{\mathop{\mathchar
58\relax}}Q_{\text{MLE}}(\bm{t})>0}Q_{\text{tok}}(\bm{t})\leq 1$ is
$Q_{\text{tok}}(\bm{t})=Q_{\text{MLE}}(\bm{t})$ resulting in the inequality,

$\displaystyle\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))$
$\displaystyle\geq\lim_{m\to\infty}\frac{1}{m}\mathbb{E}\left[|\textsf{enc}_{\text{gre}}(\bm{s})|H(Q_{\text{MLE}})\right],$
(209)

where we use the convention $0\log(1/0)\triangleq\lim_{P\to 0}P\log(1/P)=0$
and therefore we may sum over tokens such that $Q_{\text{MLE}}(\bm{t})=0$ for
free.

Considering the same geometric sampling model as in Section E.2, and Lemma
A.3, we may study the almost sure limit
$Q_{\text{MLE}}(\bm{t})=\lim_{m\to\infty}n_{\bm{t}}/|\textsf{enc}_{\text{gre}}(\bm{s})|$
by computing
$\lim_{i^{\star}\to\infty}n_{\bm{t}}/|\textsf{enc}_{\text{gre}}(\bm{s})|$
under the geometric sampling model since the almost sure limit exists. Recall
that in the geometric sampling model, we generate the overall source string by
concatenating $i^{\star}$ strings of length $X_{1}+1,\cdots,X_{i^{\star}}+1$
where $X_{i}\sim\textsf{Geo}(\delta)$, with the strings alternating between
successive $1$’s and successive $0$’s or $2$’s (with the choice between the
two made by the flip of a fair coin). For $x\in\\{0,1,2\\}$, let
$\mathcal{E}_{i}(x)$ denote the event that $X_{i}$ is a string composed only
of all $x$’s. The length of the greedy encoding of $\bm{s}$ is lower bounded
by,

$\displaystyle|\textsf{enc}_{\text{gre}}(\bm{s})|\geq\sum_{i=1}^{i^{\star}}X_{i}\cdot\mathbb{I}(X_{i-1}\not\equiv
1\mod{\ell})\mathbb{I}(\mathcal{E}_{i}(0)\cup\mathcal{E}_{i}(2)).$ (210)

Which captures for the fact that all $0$’s and $2$’s are encoded into singular
tokens unless the previous string of $1$’s was of length $\equiv 1\mod{\ell}$.
By the law of large numbers of the RHS of eq. 210, the following a.a.s. lower
bound is satisfied,

$\displaystyle\lim_{i^{\star}\to\infty}\frac{|\textsf{enc}_{\text{gre}}(\bm{s})|}{i^{\star}}\overset{\text{a.s.}}{\geq}\frac{1}{2\delta}\left(1-\sum_{u=0}^{\infty}\delta(1-\delta)^{\ell
u+1}\right)=\frac{1}{2\delta}\left(1-\frac{\delta(1-\delta)}{1-(1-\delta)^{\ell}}\right)\geq\frac{1-\delta}{2\delta},$
(211)

where the last inequality uses the fact that $\ell=1+2\log(1/\delta)/\delta$.
Likewise, observe that, $|\textsf{enc}_{\text{gre}}(\bm{s})|\leq m$ surely,
and following the analysis in Section E.2 of eq. 201, we have that,

$\displaystyle\lim_{i^{\star}\to\infty}\frac{|\textsf{enc}_{\text{gre}}(\bm{s})|}{i^{\star}}\leq\lim_{i^{\star}\to\infty}\frac{m}{i^{\star}}\overset{\text{a.s.}}{=}1+\delta^{-1}.$
(212)

For $x\in\\{0,2\\}$, observe that the expected number of times the token $x$
is observed in the encoding of $\bm{s}$, $n_{x}$ can be written as,

$\displaystyle
n_{x}\geq\sum_{i=1}^{i^{\star}}\left((X_{i}+1)\cdot\mathbb{I}(X_{i-1}\not\equiv
1\mod{\ell})\right)\mathbb{I}(\mathcal{E}_{i}(x)).$ (213)

In particular, taking the expectation of eq. 213,

$\displaystyle\mathbb{E}[n_{x}|\mathcal{E}_{1}(0)\cup\mathcal{E}_{1}(2)],\
\mathbb{E}[n_{x}|\mathcal{E}_{1}(1)]\geq\frac{i^{\star}-1}{4}(1+\delta^{-1})\left(1-\sum_{u=0}^{\infty}\delta(1-\delta)^{\ell
u+1}\right)\geq\frac{i^{\star}-1}{4}\cdot\frac{1-\delta^{2}}{\delta}.$ (214)

Note that in any realization of the geometric sampling process, in eq. 213,
either the odd indexed substrings are all-$1$’s or the even indexed substrings
are all-$1$’s. Therefore, surely, all the non-zero terms in the above
summation are of the same parity. Moreover, since the $i^{th}$ term in the sum
only depends on $X_{i}$ and $X_{i-1}$, conditioned on whether the non-zero
parities are even or odd, $n_{x}$ can be written as a sum of $\approx
i^{\star}/2$ mutually independent terms. By the strong law of large numbers on
each of the conditional processes, eqs. 213 and 214 implies that for
$x\in\\{0,2\\}$,

$\displaystyle\lim_{i^{\star}\to\infty}\frac{n_{x}}{i^{\star}}\overset{\text{a.s.}}{\geq}\frac{1-\delta^{2}}{4\delta}.$
(215)

To upper bound $n_{x}$, note that it is upper bounded by the number of times
the character $x$ appears in the source string, which by the strong law of
large numbers a.a.s (after normalizing by $i^{\star}$), scales as $1/4\delta$.
Finally, to bound $Q_{\text{MLE}}(\bm{t})$ which is the sequential nature of
the encoder, using a similar proof as Lemma A.3, we can show that
$n_{\bm{t}}/\sum_{\bm{t}^{\prime}}n_{\bm{t}^{\prime}}$ converges to the
unigram MLE model for this tokenizer. For the token $x\in\\{0,2\\}$,

$\displaystyle\lim_{i^{\star}\to\infty}\frac{n_{x}}{|\textsf{enc}(\bm{s})|}=Q_{\text{MLE}}(x)\leq\mathbb{E}\left[\lim_{i^{\star}\to\infty}\frac{n_{x}}{n_{2}+n_{0}}\right]$
(216)

Using the a.a.s. upper and lower bounds on $|\textsf{enc}(\bm{s})|$, $n_{0}$
and $n_{2}$ derived in eqs. 212 and 216, we arrive at lower and upper bounds
on $Q_{\text{MLE}}(x)$ for $x\in\\{0,2\\}$,

$\displaystyle\frac{1}{4}\approx\frac{1-\delta}{4}=\frac{(1-\delta^{2})}{4\delta(1+\delta^{-1})}\leq
Q_{\text{MLE}}(x)\leq\frac{1}{2(1-\delta^{2})}\approx\frac{1}{2}.$ (217)

Since there are at least two tokens having probability bounded away from $0$
and $1$ by a constant under the MLE unigram model, the entropy of
$Q_{\text{MLE}}$ must also be lower bounded by a constant. Indeed,

$\displaystyle H(Q_{\text{MLE}})\geq 2\min_{\frac{1-\delta}{4}\leq
y\leq\frac{1}{2(1-\delta^{2})}}y\log(1/y).$ (218)

It is easy to verify that for $\delta\leq 0.5$, the minimizer is achieved at
$y=\frac{1-\delta}{4}$, which leads to the lower bound,

$\displaystyle
H(Q_{\text{MLE}})\geq\left(\frac{1-\delta}{2}\right)\log\left(\frac{4}{1-\delta}\right)$
(219)

Finally, combining this lower bound on $H(Q_{\text{MLE}})$ with eq. 209, we
have that,

$\displaystyle\min_{Q\in\mathcal{Q}_{1\text{-gram}}}\lim_{m\to\infty}\frac{1}{m}\mathcal{L}_{m}(Q\circ\textsf{enc}(\cdot))$
$\displaystyle=\lim_{i^{\star}\to\infty}\mathbb{E}\left[\frac{|\textsf{enc}_{\text{gre}}(\bm{s})|}{m}H(Q_{\text{MLE}})\right]$
(220)
$\displaystyle\geq\lim_{i^{\star}\to\infty}\mathbb{E}\left[\frac{|\textsf{enc}_{\text{gre}}(\bm{s})|}{m}\right]\cdot\left(\frac{1-\delta}{2}\right)\log\left(\frac{4}{1-\delta}\right)$
(221)
$\displaystyle\overset{(i)}{\geq}\frac{1-\delta}{2\delta(1+\delta^{-1})}\cdot\left(\frac{1-\delta}{2}\right)\log\left(\frac{4}{1-\delta}\right)$
(222) $\displaystyle\geq\frac{(1-\delta)^{2}}{3(1+\delta)}H(\pi)$ (223)

where $(i)$ follows from the lower bound on
$|\textsf{enc}_{\text{gre}}(\bm{s})|$ in eq. 211 with the almost sure limit of
$m$ in eq. 201 and noting that $|\textsf{enc}_{\text{gre}}(\bm{s})|/m\leq 1$
surely. The last inequality follows by simplifying using $\pi=(1/4,1/2,1/4)$
and $H(\pi)=\frac{1}{2}\log(8)$.

###  Appendix F Experiment details

Hyperparameter | Value/Range
---|---
Dictionary size | {10, 20}
Tokenizer dataset size | 10000
batch size | {8, 16, 32}
gradient acc. steps | 1
learning rate | 2e-3
weight decay | 1e-3
scheduler | cosine
optimizer | adamw
dropout | 0
number of heads | {1, 2, 4, 8, 16}
number of layers | {1, 2, 4, 8}
embedding dimension | {10, 20, 30, 40}
Table 3: Hyperparameter choices

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

In this and previous experiments (Figures 2(a), 2(b) and 3), we train the
transformers on a single GPU on an $8\times$ A100 node. The wall-clock time
measured does not count time spent in validation loss evaluations. The
hyperparameter choices are listed in Table 3.

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

We evaluate pre-trained tokenizers on various datasets. The datasets are
encoded into tokens and then the cross-entropy loss of the optimal unigram
model is computed using the approximation in eq. 21. For bigram models, we
compute an empirical bigram model from the GLUE dataset and use Monte-carlo
sampling to estimate the cross-entropy loss incurred by this model. These
approximations tends to underestimate the true cross-entropy loss due to the
concavity of $x\log(1/x)$ close to $0$. In general, the gap between the
approximation and the true error is expected to grow with $k$. Therefore, the
true difference between the estimate of the best unigram model on a tokenizer
and the best $k$-gram model for $k\geq 2$ on the character level tokenizer is
likely to be larger than the reported figures.

###### Experiment 3 (Figure 5).

We train the LZW, BPE, Unigram and Wordpiece tokenizers with dictionary sizes
$\\{5000,6000,8000,12000,20000,32000,50000,80000\\}$. The cross-entropy loss
incurred by the best $1$-gram model is estimated using eq. 21 while for
$k$-gram models for $k\geq 2$, we use Monte-carlo sampling to estimate the
cross-entropy of the empirical $k$-gram model computed using the GLUE dataset.
For the $k$-gram models trained on the character level tokenizer, since the
vocabulary size is fixed, we instead plot the number of distinct $k$-grams on
the $x$-axis. While this is not a true measure of the number of parameters in
the underlying $k$-gram model, we use this as a proxy for the same.