An Analysis of Tokenization: Transformers under Markov Data
Authors: Nived Rajaraman
Jiantao Jiao
Kannan Ramchandran
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Tokenization
LLMs
interpretability
Primary area: interpretability_and_explainability
TL;DR: Transformers without tokenization are very slow to learn Markov sources; we present a theoretical model and empirical observations showing that the addition of tokenization enables them to learn such processes much more efficiently

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 are incredibly slow or 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.

An Analysis of Tokenization: Transformers under
Markov Data
Nived Rajaraman
Jiantao Jiao UC Berkeley jiantao@berkeley.u edu
Kanman Ramehandran
UC Berkeley nived..aajarmmanDberko... edu
UC Berkeley
jiantao@berkeley, edu
Abstract
While there has been large body of research attempting circumvent tokenization for language modeling (Clark et al.] [2022] Xue et al., (022)) the current consen- sus is that it is necessary initial step for designing state-of-the-en 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 -order Markov processes for à I, transformers exhibit a surprising phenomenon in the ab- sence of tokenization, they empirically are incredibly slow or fail to learn the right distribution and predict characters according
unigram model (Makkuva 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 hear-optimally, achieving small cross- 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 kth_ 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.
Introduction
The training of language models is typically not an end-to-end process. Language models are often composed of a "tokenizer", which encodes sequence of characters into sequence of token ids, which map to substrings. The subsequent language modeling task carried out by a neural network transformer, which is pre-trained and fine-tuned large datasets. The ideal goal is 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 portion of the training dataset and frozen before the transformer is trained. In practice, byte-level/characte level models such ByT5 (Xue et al. 2022) and CANINE (Clark et al. 2022) which avoid tokenization often perform worse for the reason that semantic relationships can be harder to capture at the character level (Libovicky al. 1021 Itzhak and Levy 2021).
Though used most commonly, tokenization at the subword level often has sharp edges. Test sequences may contain tokens which were never may induce undesirable behavior in the outputs of models (Rumbelow and Watkins 2023 Kharitonov et al., 2021: Yu al. 2021) and present attack surface for bad actors. Moreover, tokenized models struggle on tasks that involve manipulation at the character level, such as spelling out words reversing sentences. For similar reasons, L.MMs with standard tokenizers also struggle carry out basic arithmetic (Golkar et al., 2023). Despite this brittleness, tokenization is used in nearly all state-of-the-arr L.LM architectures.
in the training dataset. The presence of such tokens
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this paper, we introduce a statistical formulation for tokenization for next-word sext--orr-predieee prediction. We study the class of models transformers are observed to express empirically under simple data generat- ing processes, which often can have simpler descriptions. Taking a step back, rather than focusing on proxy evaluation metries, which lead to an ever-changing goalpost, we focus on understanding the behavior of the end-to-end cross-entropy loss, ((-) In this paper, we study simplification of real world data generating processes and study the case where data sources are -"h-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.
There are very simple 1tth -lt-ordder Markov processes such that in the absence of any tokeniza- tion, transformers trained data drawn this source empirically predict characters according to a unigram model. This phenomenon is observed 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 al. (2024).
2. When trained with tokenization, transformers are empirically observed 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.
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., 2023bb is the element of generalization understanding how tokenizer performs on new sequences that it was not trained on. This generalization turns out to be a delicate phenomenon we show in Appendix D 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 fail to generalize to new sequences. In Appendix E we show that there exist dictionaries which generalize well (in the sense of having low cross- cross-entropy loss) to new sequences under one encoding algorithm, but completely 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. [023 Parr 2013) and morphology-awan
tokenizers for different languages
like Japanese (Tolmachev et al. 2018 Den et al. (007)) and Arabic (Alyafeai et al.) (023) among
many others. In modern LLMs, the most commonly used tokenizers are variants 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; Zouhar et al. 2023b).
The theoretical study of transformers has also received much attention recently. We discuss the closest relatives to our work below. [delman et al. (2024) study the learning trajectory of transformers trained on data drawn from ordder 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 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). On the positive side, Nichani et al. (2024) study an in in-context causal learning task that generalizes learning in-context bigrams for ordorder Markov processes and analyze the trajectory of gradient descent.

---

p
1
Figure 1: 2-state switching process. The above state diagram describes the distribution Xn conditioned on Xn-1. 1th -order extension: the conditional probability of X, only depends on Xn-k through the kernel, Pr(Xn = 1|Xn- = 0) = and Pr(Xn, = O|xn=x= = =
Notation. All logarithms are base e, unless specified otherwise. The Shannon entropy H (X) of a categorical random variable X is - (xppp((( p(x) log p(z). HBEa (p) captures the entropy of Bernoulli random variable with parameter p. The notation Op.,.(((m)) (likewise l()) and (1))) indicate that the underlying constant depends polynomially on the parameters p, q and and (((())
(likewise, O and ft) ignores polylog(n) terms. For a set S, S* U S the set of all sequences with elements drawn from For a sequence t, tas = (t,, 14,1, .ty returns a slice.
2 Formulation
We consider a setting where the learner's objective is to learn language model which models probabilities of sequences over input alphabet A. The data to be modeled is generated according to an unknown probability model (Dict, enc(.). dec(-)). Here Dict is a collection of tokens The encoding function enc(.) 'A' - Dict', maps strings of characters to sequence of tokens, and likewise, the decoding function dec(-) Dict" + A maps sequence of tokens to string of characters. We assume that the tokenizer is "consistent", namely, dec(enc(-)) is the identity function.
A'' - [0, over strings. A tokenizer is a tuple T
We consider setting where the learner has access to a training dataset which is a sequence of length n sampled from data source] We study the likelihood maximization problem, where the objective of the learner is to learn an end to end model such that the cross- cross-yn loss is minimized. In the presence of tokenization, we have a model of the form Qend = Q o enc(.) where Q is a joint distribution across sequences of tokens when the tokenizer corresponding to enc(-) is used. The cross-entropy loss, i.e. the pegpeerlexxty, can be written down as,
Lm (Qend) A -E(log (eenc))))]
with the objective to minimize it. Here, the expectation is over s, a fresh test sequence of length m sampled from the data generating process. Fixing a tokenizer, let denote family of joint distributions over tokens (i.e. likelihood models). The objective is to jointly design tokenizer (with Q with small test loss L. enc(-)).
encoding function enc(-)) and likelihood model
Finally, for a dictionary Dict, the unigram family of models, Q1-gram= is defined as below: Q E Q1-gram associates probability Q(t,, t..... tt) Q# (f) II;-1 Qua (t:) to the sequence of tokens tı, 1.. ,tz for measures I and Qiok supported on N and Dict respectively.
2.1 Data generating process
In this paper, we consider simplification of real-world data generating processes by considering the case where the data generating distribution a t -rder Markov process over characters. Studying the behavior of transformers trained 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. When transformer is trained data from certain simple Markov processes like the considered in Figure a very peculiar phenomenon occurs within a reasonably large number of iterations, the transformer fails to improve beyond the loss incurred by the best unigram model. This phenomenon is reproducible across a wide number of hyperparameters, including the number of feed-forward layers in the model, the embedding dimension, and the number of attention heads. In Figure this is made clearer- the transformer fails to improve its test loss beyond that of the best unigram model.
This be thought of as the concatenation of all the individual sequences in the training dataset.
3

---

300
Sequerce leagth
Figure 2: Token distribution returned by the transformer tokenized by learnt BPE encoder with dictionary size of 20. A test sequence is generated from the stochastic source and encoded into a token sequence t. Each narrow vertical column represents the distribution over next tokens returned by the transformer when the first tokens of t are fed into the model, where is varied from 0 to the length of t. For most values of æ, the model appears to predict the same distribution over the next token.
How bad can a unigram model be? turns out that the gap between the cross-entropy of the best unigram model and that of the optimal model can be characterized precisely.
Theorem 2.1. Consider any ergodic data source with stationary distribution over characters æ. The
unconstrained optimal likelihood model achieves cross-entropy loss, ming L. (Q) = H(P). (P). In contrast, the cross-entropy loss under any unigram model Q E Q 2-gnan satisfies, L (Q) 2 m (T))
The ratio of the optimal loss H (P), and the optimal unigram loss, (H can be arbitrarily large. In particular, for the switching chain in Figure 1 p, -> O, the ratio diverges to cc.
While transformers are a powerful class of models, it concerning that they fail learn very simple distributions such as -oder Markov processes. Why do they work so well in practice if they can be so slow to learn Markovian data? It turns out that there is a simple missing ingredient in all the architectures considered so far: tokenization. All the models trained in Figure 3al operate on raw character sequences drawn from the stochastic source. To understand the role tokenization, we another experiment and train the transformer sequences generated from the stochastic source which are encoded into tokens by a BPE tokenizer learnt from data. The transformer now operates on sequences of tokens, rather than sequences of individual symbols. In Figure 3b plot the results of this experiment in the presence of tokenization, the cross-entropy loss of the end-to-end model breaks past the unigram barrier and approaches the optimal bound within small number of iterations.
Let's peek into the model a bit more and understand its behavior. In Figure 2 we run the following experiment: sample a random sequence of length 2000 from a Markov chain and feed it into the transformer after tokenization, resulting in Rs 500 tokens. We plot the next-token distribution predicted by the transformer at every single position in the input, generated by autoregressive masking, In Figure 2 we stitch together these next-token distributions, each of which a narrow column heatmap. Visually, observe that the plot is approximately homogeneous along the x-axis, implying that the next-token distribution learned does not depend strongly on the prefix at that position. Thus the transformer learns what is essentially unigram model.
Thus, we come surprising conclusion: the behavior of the transformer on the th -oder switching source in Figure [ 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 unigram model in both cases, how come there such a large gap in performance between the two? To understand this in more detail, we analyze toy tokenizer. As a simplification, we will analyze the behavior of an arbitrary, but exact unigram model under this tokenizer.
3 Unigram models under tokenization
Let's consider a toy tokenizer which assigns all possible substrings of length as tokens in the dictionary and study what happens when unigram model is trained on the tokenized sequences. The

---

223
1000
But tundorer mohi
Optioal pros 20
Cress etryy bot angur roold
0.55
0190
layts
laye
Tgets
cravestopy
1.79
0.30
2.50
0.70
1.2
1.0
0.3
0.00
0.90
100
-00
100 150 100
(a) The loss of the transformer fails converge to the optimal cross-entropy loss (dashed line) and instead converges that of the best unigram model (dotted line). The shaded blue region captures how the test loss curves vary as hyperparameters (number of layers, embedding dimension etc.) changed.
(b) In the presence of tokenization, the test loss of the model approaches the optimal bound (dashed line). It worth noting that the models trained here are sig- nificantly smaller than those considered in Figure having up to 70x fewer parameters and yet are able to achieve the optimal cross-entropy loss.
Figure 3: Transformers trained 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.
total dictionary size d 2", A sequence of characters is mapped to sequence of tokens by simply chunking it into a sequences The resulting stochastic process the tokens is still Markovian, but over state space of size 2". For any unigram model Q on the tokens, the cross-entropy loss can be written down as,
characters which are replaced by the corresponding token index"
fm (Q enc(.)) E. | [rrentts) 1og(1/Quokttt) (t)) + @(logmm)),
where we choose Q# Unif([m)), which contributes an additive log(m) to the loss. Choosing Quak (t) = (tr) 1(t)+ as the stationary probability the Markov process associates with t,
1 fm (Q enc(.)) ~
log( (og(P(s)+
Σ m/k-1 Emo log
T(skit1)
:m0
P(8 spa))
H(P) + mk
- -
m
(P)
(1- logg(d)
H (TT)
+ Toga (d)
(2)
the approximation in (i) uses the fact that as m grows large, 1. E.' log( (Pg(((+ee+1 (8++e) ap- proaches H(P) With d (i.e., 1), recover the performance of the character tokenizer in Theorem 2.T An immediate implication of this simple calculation is that as m - co, there is a unigram model which nearly optimal as the dictionary size grows oc.
While this toy tokenizer allows us to glean this intuition behind why tokenization allows unigram models to be near-optimal, there some obvious issues. One, the tokenizer does not adapt to the distribution of the data. Indeed, for the switching Markov source in Figure [ as 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 more technical level, in eq. (2) to get to a cross-entropy loss of (P)), the size of the dictionary required by the toy tokenizer is (x)(x)/H(P)) As discussed in Example A.1 for the switching Markov process with = 6, this dictionary size can be extremely large and scales exponentially (in 1/5) as e!/8 168) when is
0, the
"The last few characters which do not add up to r in total are left untokenized. These boundary effects will not matter the test sequences grow in length
5

---

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.
Larger dictionaries are usually correlated with the presence of rare tokens which appear infrequently training time. This presents 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 elicit undesirable behavior 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 lower bound on the number of their occurrences in the training data to be allocated as a token. 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. under the assumption that the test sequences 8 are of length m - oc. Namely, define the normalized loss,
C(-) lim C-)--)
m=+00
Theorem 3.1. Consider a Markov data generating process which satisfies Assumption 3.2 Let d
denote budget on the size of the dictionary. Then, there exists a tokenizer with at most d tokens and encoding function end(-) ), such that,
min
L(Q o end(.) S T min L(Q') Q'
(3)
QEQ ggaan
where: log(1/8)/0.99 (od Furthermore, a tokenizer satisfying eq.
3 with probability
2 d Ro (Iog(d) can be learnt from a dataset of (s(d) characters.
The tokenizers considered in this theorem are far more efficient with their token budget than the toy tokenizer achieve a cross entropy loss within factor 2 of optimal. the dictionary size required by these tokenizer is == 1/8² on any source satisfying Assumption 3.2 In comparison, the toy tokenizer requires a dictionary size of e log(1/8) to achieve the same error. We show that the LZW tokenizer proposed in (Zouhar et al., 2023a) achieves the upper bound in eq. (3) when trained dataset of size (d). Likewise, we also show that sequential variant of BPE achieves the upper bound in eq. B up to a factor of 2 and with worse dependency in E when trained on a dataset of size (d.). 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 tokenizer (Kudo) 2018).
Key insight. While the toy tokenizer provides a high level intuition as 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 good job 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 t' appears, it is always followed by t". An i.i.d. model on the tokens is poor approximation since P(t't") > P(t') P(t"). However, by merging t' and t" into new token 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 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.
3.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 Theorem 3.4). result in tokenizers achieving
e is assumed to be < in this statement. The constant 0.99 can be made arbitrarily close 1.

---

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 order sources is that the transition kernel is entry-wise bounded away from O. This assumption satisfied by all the sources considered in the paper thus far, such as the htth -oder switching processes in [
Assumption 3.2 (Data generating process). Assume that the data source is an ergodic Markov process with transition P(-l-) and stationary distribution т. Assume that ming, EA P(a'la (a) 2 8 > 0.
Remark 3.3. Assumption 3.2 (and its -ordor extension) impose that there is small but non- zero probability of observing any particular symbol after any preceding sequence. This limits the applicability of these processes in real- world scenarios where such a phenomenon may not occur. However, our motivation for this assumption is different: allows parameterizing the Markov process in way which interpolates between ii.d. (6 1/| and highly non-ii.. (6 + 0).
For substring 8 and a character a, define P(sla) = P(si/a) I1 P(s, denote the condi- tional probability of the substring 8. We now state the main result of this section.
Theorem 3.4 (Bound on cross-entropy loss of dictionaries under greedy encoder). Consider source satisfying Assumption 3.2 and any tokenizer T equipped with the greedy encoder, enogre with finitely long tokens. Define, P(t) = Eawn|P(tlan) and suppose H (QMLE P) 2 log((/)) for some E Then,
minQ ((Q)
L(Q enc e.)) min QERiam
S
1
Interpretation. (QMLE. P) = Le~Quue [log(1/P(tt)) is large when the encoder places higher mass (i.e. larger values of QMLE(-)) 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(-)) to encode new strings.
3.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 3.1 for this tokenizer.
Definition 3.5 (LZZW 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.3) to encode new strings into tokens.
An example of the LZW tokenizer: For the 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 s' exists 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 approximately achieves the optimal cross-entropy loss.
Theorem 3.6. Suppose the LZW tokenizer is trained on dataset of length at most d (thereby learning a dictionary with at most tokes)). For Markov sources satisfying Assumption 3.2 with probability
> 1 d= (o(log(d), the resulting tokenizer satisfies,
L(Q encgre (+)) minQ L(Q)
min QE 1
1-5
log(1/8) where = = 0.99 log(d
The proof of this result considers all substrings t with P(L) 2 1/d0.99. These substrings are reasonably high probability and observed many times in a dataset of ②(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 'The constant 0.99 can be made arbitrarily close 1.
7

---

Iokendd
Istre
Optial onto- bayy
Outrra consentogy
133
Crets eniry suigees
Consentnep (eee uagga wodd
0.
07-
0.5
10
Traning flam (5)
(a) Convergence rate of smallest model which is within
(b) Convergence rate of models with the same embed-
10% of the optimal-cross entropy by 300 epochs. The
ding dimension (20), number of heads (1) and layers
smallest untokenized model has 9010 parameters (3
(3) with and without tokenization. The model with to-
layers, embedding dimension = 10). The smallest to-
kenization (dictionary size of 20) appears to converge
kenized model with a dictionary size of 10 has 17880
more quickly, but the error floor is subtly higher com-
parameters (3 layers, embedding dimension = 20).
pared to the model without tokenization. Both models
The tokenized model has more parameters hut the wall-
are trained input sequences of length 512. The width
clock time taken to reach any loss value is smaller.
the tokenized model is smaller (145).
Figure 4: Test loss wall-clock time for the tokenized and untokenized models when trained on the order-1 switching Markov chain (Figure I with = = 0.8. The tokenizer used is BPE.
which matches token, every token allocated must fall the "boundary" of this set, having P(t) S ((1/99.9)). By definition, this means that (QQLE P) = Ee-Quar: (ogg(1/()t)] = 0.99 log (d). Combining this with Theorem 3.4 completes the proof. At high level, on the infinite tree of substrings A 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.] [200]] Drmota and Szpankowski] 2011 Hun and Vallée 2014
Drmota et al. 2021 A detailed proof of Theorem 3.6 provided in Appendix A.6
4 Experimental Results
Experiment 1 (Figures 4a and 4b) In this experiment we study the order-1 switching Markov chain. Transformers without tokenization empirically achieve a small cross-entropy on this learning task as seen in Figure 4a and earlier in Makkuva et al. (2024). We vary hyperparameters find the smallest untokenized model which achieves a loss within 10% of the optimal-cross entropy within 300 epochs. Fixing a token dictionary size of 20, we also find the smallest tokenized model which achieves the same loss. Although the smallest model with tokenization is larger than the smallest model without tokenization 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 the toy example we consider. In Figure 4b) we compare models with the same architecture trained with and without tokenization! The model with tokenization appears to converge more quickly, although the limiting error achieved is subtly higher in comparison with the model without tokenization.
Experiment 1 (Figure 5). In this experiment, we train tokenizers on the Wikitext- 103-raw-vl dataset (Merity et al., 2016) and compare the performance of unigram models trained on the GLUE dataset as the model size scales. Since the character-level tokenizer operates on a fixed vocabulary, in order to compare with the other tokenizers,
plot the number of unique k-grams observed in the training dataset along the z-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.
'The model with tokenization has width equal to the typical length of sequences after encoding, which is smaller.
8

---

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).
Experiment 2 (Table 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-5IK. 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) and Wikitext- 1ikitext-103-v1 (1.8M).
1+7
2.0
LZW
BPE
1.8
Unigram
Wordplece
RT
Wiki
Yelp
GLUE
1.6
Character
BERT
1.58
1.55
1.60
1.50
2-gram (3333)
Tinyllama
1.75
1.84
1.82
1.70
Crozs entropy lass of
1.4
GPT--nex
1.57
1.64
1.66
1.48
Surram (230581
Mistral
1.69
1.80
1.75
1.66
1.2
Phi-2
1.54
1.62
1.64
1.45
A.gram (93524)
Character
2.40
2.45
2.46
2.38
0.8
200.00
40000
60000
80000
Size ctionary
Figure 5: Performance vs. dictionary size. Tokeniz- ers are trained on the Wikitext- 103 dataset. For all other tokenizers we train unigram models while for the the character-level tokenizer, we train k-gram models for & E {1, 2, 3, 4]. Likelihood models are trained on the GLUE dataset. The parentheses in- dicates the number of distinct observed k-grams, which lower bounds the k-gram model complexity.
Table 1: Cross-entropy loss estimates (using eq. (55) of unigram models trained pre- trained tokenizers under a number of datasets. The last row (blue) is the character level tok- enizer, on which a more powerful bigram model is trained. BERT is based on Wordpiece, and the remaining tokenizers are BPE based. The character-level tokenizer we use ByT5.
4.1 Additional theoretical results
We present some additional theoretical results in the appendix which we discuss briefly below. In Appendix [ we do a theoretical study of the cross-entropy loss achieved by the popular BPE tokenizer. We show that a variant of BPE achieves the upper bound on the RHS of eq. (3) (Theorem 3.1 up to a factor approaching 2 as the dictionary size grows. It is interesting question for future research to understand whether this factor of 2 can be removed, since transformers are observed to achieve the we prove
near-optimal cross-entropy loss as the dictionary size grows (cf. Figure 3b). In Appendix C finite sample bounds on the end-to-end model under the LZW tokenizer with a smoothed empirical estimator as the unigram model. This analysis reveals that there is sweet spot for the dictionary size too small a dictionary, and the statistical error floor is significant, too large a dictionary, and the statistical error incurred by the likelihood model dominates the overall loss. We also take a closer look into the aspect of generalization for tokenizers, which arises from the fact that the tokenizer is evaluated data that it was not trained Prior work such as Zouhar al. (2023b) show that BPE is an approximation algorithm for finding the sequence of merges which minimizes the size of the compressed dataset. This does not imply any guarantees on the end-to-end performance. or even compression power of the tokenizer on new sequences. In particular, in Appendix D we show that there exist tokenizers which compress the dataset into a short sequence of tokens, but do so in a way which fails to generalize to new sequences. Thus measuring the performance of a tokenizer necessitates understanding its behavior on data it was not trained on. In Appendix E we show different kind of intricacy there exist tokenizers under which the best unigram model achieves low cross-entropy loss. However, the same dictionary under a different encoding algorithm performs nearly as poorly as the character-level tokenizer. The interaction between the dictionary and encoding algorithm is poorly studied subject the tokenization literature; this result emphasizes the importance of understanding this relationship.

---

Open questions
In this section, we discuss some limitations of our work and open questions stemming from them. We show that when transformers are trained with or without tokenization, they learn to approximately represent k-gram models for different values of Transformers are capable of representing far more complex behavior, which are elicited under more complex data generating processes. Extending our formulation to these settings presents an avenue to develop an even better understanding of tokenization, and would allow finer-grained comparisons between tokenizers. The behavior and role of tokenizers may be very different in these contexts. Below we discuss some concrete questions.
Our theory assumes that the underlying Markov chain has every transition occurring with non-zero probability, which is a limitation. However, the analysis for the toy tokenizer in eq. ( shows that when the dictionary size scales exp(mI (T) (m)/H even in the absence of Assumption 3.2 the tokenizer achieves the optimal cross-entropy to within factor of 2. This leads to the following conjecture.
Conjecture 1. In the spirit of eliminating Assumption 3.2 is it possible to establish version of Theorem 3.1 applicable to data drawn from any Markov chain, where & = (og(1/6)/0.99 log(d) is replaced by (og(m)((T)) (T)/H(()) (P))))0099 log(d).
In Appendix B we analyze a variant of the BPE tokenizer, which carries out a version of sample splitting, and establish weaker variant of Theorem 3.T for this tokenizer. This is simplify the statistical dependencies arising from the fact that while learning its dictionary, BPE makes run over the entire training dataset each time a new token is added. remains an open question analyze and establish a variant of Theorem 3. for the standard BPE tokenizer.
6 Conclusion
We present 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. We empirically observe that transformers with tokenization are drastically more efficient at learning ht Markov processes, compared to without tokenization. We prove that algorithms such as LZW and 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 grows.
7 Acknowledgements
JJ and NR were partially supported by NSF Grants IIS-1901252 and (CF-2211209) KR was partially supported by NSF Grant CCF-221 1209.
References
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.
Dietrich Braess and Thomas Sauer. Bernstein polynomials and learning theory. Journal of Approxi- mation Theory, 128(2):187-20) 2004.
Yen-Chi Chen. Stochastic modeling of scientific data, Autumn 2018
Jonathan H Clark, Dan Garrette, Iulia Turc, and John Wieting. Canine: Pre-training an efficient tokenization-fret free encoder for language representation. Transactions of the Association for Compu- tational Linguistics, 10:73-91, 2022.
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 application to japanese corpus linguistics, Oct 2007. http/htttt::/:rosiiittt minjal ac. jp/ h/ppap//rrcood//2011
10

---

Michael Drmota and Wojciech Szpankowski. The expected profile of digital search trees. Journal of Combinatorial Theory. Series A, 11877):139-1195, 2011.
Michael Drmota, Michael Fuchs, Hsien-Kuce Hwang, and Ralph Neininger. Node profiles of symmetric digital search trees: Concentration properties. Random Structures & Algorithms, 58(3): 430-467, 2021.
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 10014
2024.
Tanja Eisner, Bálint Farkas, Markus Haase, and Rainer Nagel. Operator theoretic aspects of ergodic theory, volume 272. Springer, 2015.
Philip Gage. A new algorithm for data compression. C Users Journal, 12(2):23-38, 1994.
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.
Robert M Gray and RM Gray. Probability, random processes, and ergodic properties, volume 1. Springer, 2009.
Gregory Grefenstette and Pasi Tapanainen. What is word, what is sentence?: problems of tokenisation. 1994.
Yanjun Han, Soham Jana, and Yihong Wu. Optimal prediction of markov chains with and without spectral gap. Advances Neural Information Processing Systems, 34:1 1233-11246 2021.
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.
Itay Itzhak and Omer Levy. Models in spelling bee: Language models implicitly learn the character composition of tokens. arXiv preprint arXiv:2108. 11133, 2021.
Philippe Jacquet, Wojciech Szpankowski, and Jing Tang. Average profile of the lempel-ziv parsing scheme for markovian source. Algorithmica, 31:318-360, 18-360, 2001.
Eugene Kharitonov, Marco Baroni, and Dieuwke Hupkes. How bpe affects memorization in trans- formers. arXiv preprint arXiv:2110.02782, 2021.
Taku Kudo. Subword regularization: Improving neural network translation models with multiple subword candidates. arXiv preprint arXiv:1804.10959, 2018.
N Jesper Larsson and Alistair Moffat. Off-line dictionary-bacn based compression. Proceedings of the IEEE, 88(11):1722-1732, 2000.
Jindfich Libovický, Helmut Schmid, and Alexander Fraser. Why don't people use character-level machine translation? arXiv preprint arXiv:2110.08/990 2021.
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.
Ben Mann, N Ryder, M Subbiah, Kaplan, Dhariwal, Neelakantan, Shyam, Sastry, A Askell, S Agarwal, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 2020.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv: 1609.0040090784 2016.
Jaouad Mourtada and Stéphane Gaiffas. An improper estimator with optimal excess risk in misspeci- fied density estimation and logistic regression. The Journal of Machine Learning Research, 23(1): 1384-1432, 2022.
11

---

Assaf Naor, Shravas Rao, and Oded Regev. Concentration of markov chains with bounded moments. 2020.
Gonzalo Navarro and Luis MS Russo. Re-pair achieves high-order entropy. In DCC, page 537. Citeseer, 2008.
Eshaan Nichani, Alex Damian, and Jason D Lee. How transformers learn causal structure with gradient descent. arXiv preprint arXiv:2402.17335 2024.
David D Palmer. Tokenisation and sentence segmentation. Handbook of natural language processing, pages 11-35, 2000.
Terence Parr. The Definitive ANTLR 4 Reference. Pragmatic Bookshelf, Raleigh, NC, 2 edition, 2013. ISBN 978-1-93435-699 viex/the-definitiiee htt.://mm20.eem11177777911111110
URL httpps:/wwwt http://swaaabbooosooo.oooooooo/e ine. www b
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models unsupervised multitask learners. OpenAl blog. 1(8):9, 2019.
Jessica Rumbelow and Matthew Watkins. haaiipollmmmiiknnnnnnttte///wa.. http:::pttttt//ttt http://wwww.lllnnnnfffrrrr 2023.
Mike Schuster and Kaisuke Nakajima. Japanese and korean voice search. In 20/2 /EEE international conference on acoustics, speech and signal processing (ICASSP), pages 5149-5152. IEEE, 2012.
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 Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. 186138866/111- 1162... URL /attps:/accaathoole/ orwp:/--1r1//11-111211
Aaditya K Singh and DJ Strouse. Tokenization counts: the impact of tokenization on arithmetic in frontier llms. arXiv preprint arXiv:2402.14990 2024.
Arseny Tolmachev, Daisuke Kawahara, and Sadao Kurohashi. Juman++: 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/DI 1-10-2000..
org/ 20100
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.0922 2023.
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.
Terry A. Welch. A technique for high righ-performance data compression. Computer, 17(06):8-19 19, 1984.
Linting Xue, Aditya Barua, Noah Constant, Rami A1-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.
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 (rXiv:2109.03/22 2021.
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 PMLR, 2023.
Conference on Machine Learning, pages
Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. IEEE transactions Information Theory, 24(5):530-535 1978.
12

---

Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Mrinmaya Sachan, and Ryan Cotterell. To- kenization and the noiseless channel. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Papers), pages 5184-5207, Toronto, Canada, July 2023a. Association for Computational Linguistics. doi: 10. (0.186533v1/203... haw.///...........225555. URL https
//aclanthology. org.ololgooooooooo/ooooooo htrg/2023.aamm acl long. 284
Vilém Zouhar, Clara Meister, Juan Luis Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, and Ryan Cotterell. A formal perspective byte-pair encoding. arXiv preprint arXiv:2306. 2023b.
13

---

Appendix
Contents
Analysis of LZW: Proofs of Theorems 3.4 and 3,6
14
A.1
Notation and definitions
14
A.2
A basic result about the optimal achievable cross-entropy loss
14
A.3
Proof of Theorem
15
A.4
Maximum likelihood unigram model
A.S
Proof of Theorem
A.6
Hcavy-hitter dictionaries and proof Thcorem 3.6
Additional Theoretical Results sequential variant BPE
22
B.1
Analysis Algorithm |
25
B.2
Analysis for the large dictionary Dict da
25
B.3
Analysis the small dictionary case
32
Additional Theoretical Results II: Learning the likelihood model
35
C.1
Proof of Theorem C.I
36
Additional Theoretical Results II:: The generalization ability of tokenizers
40
Additional Theoretical Results IV: Inferaction between the dictionary and encoding
algorithm
41
E.1
Stochastic source dictionary.
42
E.2
Minimal encoder achieves optimal cross-entropy loss up to constant.
42
E.3
Greedy-encoder achieves poor cross-entropy loss
44
Experiment details
46
NeurIPS Paper Checklist
48
A Analysis of LZW: Proofs of Theorems 3.4 and 3.6
A.1 Notation and definitions
For each character a E AA let T denote an infinite tree, with root vertex and subsequent vertices labelled by strings t AA.. The edge from a parent vertex t to any child to is labelled with the probability P(ta'(t) unless t = in which case the edge probability P(a'(a). An infinite trajectory sampled on the tree T 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 can define the "entropy rate". The entropy rate fundamentally captures the compressibility of the source, and can be defined as Hoo & limm-po ma (P) where a length m string drawn from the source. By Theorem 2.1 Hos captures ming Z(Q).
A.2 basic result about the optimal achievable cross-entropy loss
The ratio of H(P) and mfl (T)) can be made arbitrarily large for the switching Markov chains in Figure as the switching probabilities p and g approach 0 or See Example A. for more details. Example A. Consider the switching Markov process Figure 1 on (0, with
q For this process, limm-+00 1 (P) (o) log(1/0) + [ log(1 (1/(1 6)), , but (1/2,1 1/2} and so H(T) HBer (1/2) = log(2). The ratio limm (=) H(P)
goes to xo + 0.
14

---

A.3 Proof of Theorem 2.1
We first characterize the minimum achievable cross-entrop! loss Lm (Q) without any restrictions on the likelihood model class Q. Choosing (()nc(s)) = ((s) = P(s). the true probability of the sequence s, we have Cm (Q enc(-)) (()) where (.) 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
Lm = F [lo((1/(({))
+ [og(L/P(s))
= H() + (PII))
On the other hand, the cross-entropy loss under any unigram model Q Qi.gram satisfies,
1 fm (Q enc(.))
10
1
m
Elog Que Qux
E [log (m))
m
m
m
Σ
x(a) log Qwk(a)
aEA
(T)
where in (2), we use the definition of the unigram model Q, and in (ii), 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 ( Y) 2 H(X).
A.4 Maximum likelihood unigram model
A number of our results (Theorems 3.4 and 3.6 name few) related to bounding minge yau f(Q o enc(-)) for some tokenizer T. In this section we introduce the maximum likelihood unigram model which captures the optimizer over for any given tokenizer.
For the character level tokenizer, an examination of Theorem 2.1 shows that the optimal unigram likelihood model associates probability (a)(a) = Ta)), 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 Qia (t) ends up being the limiting expected fraction of times 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.
T1e Eene
(M)
lim IE 17 30000
each token, where ni is the random variable capturing the number of occurrences of the token t in the encoding of the length-m string 8. Restricting the class of likelihood models to the unigram models, Q1-gram- QMLE captures the model which minimizes eq.
The unigram MLE model cannot be computed without an infinite amount of data, but can be approximated well with finite amount of data, which forms the basis for Theorem C.I] For certain encoding algorithms, we can show that the quantity nt/ Ee nr asymptotically converges to its expectation (Lemma A.4). This is the reason the unigram model in eq. (4) is referred to "maximum likelihood" model, since limm- n E, ne is the limit as s| m + oo of the solution the following likelihood maximization problem: given sequence find the distribution over tokens, Q, which maximizes
II Q(t) tEenc(a)
II (Q(1))
EEDi
As discussed previously, the unigram MLE model over tokens eq. (4) induces joint distribution over sequences of tokens by looking at the product of the marginal probabilities of the composed tokens; in particular,
QMLE(tI.... ,t, = QMLE ( II (t.)
15

---

where QMLE(i) is distribution on the total number of tokens generated and is instantiated as Unif([m)])
Remark A.2. Note that the unigram MLE model specifies a distribution over tokens which is function of the underlying encoding algorithm, enc(-). Different encoders result in different population level distributions over tokens, and consequently different unigram MLE models.
Definition A.3 (greedy encoder). Given dictionary Dict, the greedy encoder enCgre encodes a string into tokens by greedily matching from left to right, the largest substring that exists as a token in Dict. This substring then removed and the process iterated on the remainder of The greedy decoder deCgre(( (-) is lookup table sequence of tokens is decoded by replacing each occurrence of a token by the corresponding substring it maps to in Dict.
Lemma A.4. limm- Een mim E En The ny for any tokenizer having a finite vocabulary
nh
as
and finitely long tokens, using the greedy encoder.
Proof. This result essentially true because under the greedy encoder, the tokens in an encoding of fresh string may be generated by an r"h -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 Hrylov-Bogolyubbe argument).
Tokens are generated as follows. Suppose the previous tokens generated were f,, ".,... , t, The next token fi+1 is sampled by drawing an infinite trajectory from 'T." for ~ P(- and returning the longest prefix t this trajectory which is a token in Dict, conditional on satisfying the conditions, 1,tj+1..- t,t & Dict for all {1,2, ,i}. This process is repeated sequentially to generate all the tokens.
Suppose the length of the longest token in the dictionary is fmax. Then, the distribution from a which a token is sampled depends on most the previous lmax tokens. The reason for this is that the dependency of the (i + 1h token, t,+1, on the previously sampled tokens emerges in the constraint t ... .,,4,4 & Dict, satisfied by any candidate 1, Since each token is of length least one, this condition is vacuously satisfied if < i Lmax-
With this view, the evolution of the state, defined state, (fremase tylmax -1, tir m
evolves in a Markovian fashion. By the Krylov-Bogolyubov argument (cf. Proposition 4.2 in Chen (208)) the time averaged visitation frequencies of a Markov chain coordinate-wise asymp- totical ly converges to its expectation, almost surely. This expectation exists by Theorems 8.5 and 8.22 of Eisner al. (2015) which shows that for a matrix such that supten || oo the limit lim i Ei A exists. For the finite-state Markov transition A which captures the token generation process, condition SuPteN || |1 < |Dict fmax < XC. This means that the limit of the time averaged state distribution exists. Moreover, for any initial distribution To over tokens, lim, & E/=1 A' satisties the condition TA = æ, implying that the limiting time-averaged state distribution is stationary distribution of A. Since the limiting time-averaged measure on ())mm))mm))))) exists, this implies that the limiting time- averaged measure of bye byt for each r' E 1, (max exists. By taking the uniform average over r' and r, the limiting time-averaged measure of t, over i E N exists.
the state state,- (t
A.5 Proof of Theorem
Consider string of length do which is encoded into sequence of tokens (t, [lenCgro ( s)]]. By the Asymptotic Equipartition Property (AEP) for ergodic sources, i.e. the Shan- non-MeMillan. -reimaa theorem,
Pr
lim log P(s) 11/0 10-000
(5)
Here limm- H(P) also happens to the entropy rate of the source. We use this property to bound the length of the greedy encoding, lencgre (s)]. Indeed, the probability of may be decomposed as,
(en)
[x))
P(s) = P(tt)
II 2
P(ta
<
II
max P( P(tzla).
16

---

Noting that ő min, P(tla) 2 max, P(tla), up to d factor we may replace the max over by an expectation over where и the stationary distribution of the stochastic source. particular,
enc (x)
P(s) S
II ==1
P(4)/8.
By invoking the AEP, eq.
(
lim ii=1 m 1=-00 YI1
|nc (4)
log (P(t.)) log(1/6)) S Hoc
as.
Recall that the greedy encoder satisfies Lemma A.4 and for any Dict, limm [e)
d.k.
Qt) Furthermore, note that for any token t Dict, P(t) 8t 0, and lenc (s)) S
surely. By almost sure convergence,
eenCgre(s) lim m m0
Σ EEDict
Tit
llog (P(t) log(1/6)))
m
enC [8)
enC (s)
lim
(H(QMEE, P) - -log(1))))
m m0+00
m
Furthermore, utilizing the assumption that e (Q P) log(1/6) satisfied by the tokenizer,
- e (H(MMLB, Pi)
lim
< Ho.
(6)
m
Now we ready to bound the expected cross cross-entropy loss of the tokenizer. Define the unigram model
P- (t1, f2,,.. tty) (j I[: P(t.) where Punar is the uniform measure over [m]] Note that have the inequality minge goan limm - f. (Q enCgre()) I limm- 1. Cm r encgre (-))
n/ and therefore, it suffices to upper bound the RHS. In particular,
E (iEeNCIut))) log (P()))
(P enCgre = -E(log
I log(m)
[
[
reenc (a)
log (P()))
where the last inequality uses the fact that Punir( Ennire (8)1) = 1/m. Note that as m + co, by assumption the tokenizer, the fraction of times the token appears in the encoding of converges almost surely converges to QMLE Since |enCgre I surely and P(t) > gitl > 0, by an application of the Dominated Convergence Theorem,
lim m--+00 m
E
Σ Exsonccmlte) log (P()))
lim 1 =00 m
lencgre E QMLE(t) log (P()))
lim E Ienngre (s) H(QMLE. P)]
(8)
Combining eq. 7 with eq. (8) and setting limm log(m) m 0. and invoking eq. (
min lim C. (QMLE o enCgre = lim enn (s) H (QMBB P)]
QE gra mh +00 m
m-
Hoo
1-8"
By Theorem 2.1 we have that ming limm-soo 1 C.. (Qoencerell (.)) limm-so
H(P)
Hox which
m
uses the fact that the source is ergodic. Combining with eq. (9) completes the proof.
A.6 Heavy-hitter dictionaries and a proof of Theorem 3.6
In this section prove Theorem 3.6 and introduce the notion of heavy-hitting dictionary. At high level, these dictionaries contain all the substrings which have reasonably high probability of being observed many times in dataset of size n (d)) We first show in Lemma A.6 that heavy hitting dictionaries generalize well in the sense of having H(QMLE, P) being large (in conjunction with Theorem 3.4 this implies an upper bound on the cross-entropy loss of the best unigram model). Next, we will prove that the I.WW algorithm (Definition 3.5) results in heavy hitting dictionary with high probability.
17

---

aa
ab
ac
ba
66
bc
bc
bba
6bb
bbc
bca
bcb
bcc
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 the last token of the encoding of string) since any sufficiently long trajectory starting with must have a longer prefix which is also token, namely, one of ba, be, bla, bbb or bbc. The vertices of the tree which are assigned by the greedy encoder 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 0 and that every vertex s marked red has P(s) < 1/d
Definition A.5 (ß-heavy-hitting dictionary). A token of a dictionary is said to be maximal if there strict prefix, and in addition, is also the largest prefix of the substring which is a token. A dictionary Dict is said to be 3-heavy hitting if the set of maximal tokens subset of (s' max P(s' (a s 1/d"}.
exists an arbitrary substring containing
pictorial depiction of the heavy hitting property is illustrated in Figure 6 Lemma A.6. For a B--eavy-hitiig dictionary, with the greedy encoder, H(Q P) 2 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 maxae.4 P(s(a) I 1/d". by the heavy-hitting property, for any token t,
P(t) S max P(s'(a) 1/d
Therefore,
H ((QULE, P) Er-Que [og(1/P(()) log(())
Define Ms [t: max P(t(a) 2 8/d"). These are the set of under the stochastic source. We will show that 3 bounded away from 1, with high probability, every substring in M3 is added as token to the dictionary in run of the LZW tokenizer (Definition 3.5). Note that if every substring My is assigned as a token by LZW, then the algorithm must be 3-heavy hitting since there always exists maximal token on the "boundary" of the set Ma which is strictly contained in (s' max P(s'(a) < 1/
substrings
18

---

Lemma A.7. Every substring in Ma has length at most L, _ (3log() + log()/))).
Proof. Note that ming,a'e E.A P(ala') 8, which implies that the probability of any transition must be bounded away from 1, i.e., maxa,a'EA ((ala') - 5. This implies that,
max P(t(a) 1 (1 5) S -66
(10)
aEA
By definition, for any substring t E MB. max.EA P(t,a) 2 5/d. In conjunction with eq. (10). 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 (n). Rather than running the algorithm with early stopping (i.e., ceasing add new tokens once the budget is hit), instead, 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.8. With probubility 2 1 -1-d-Q(logd//////b in run of the LZW algorithm, no substring t added as token to the dictionary satisfies [t] 2 Liax & 4 lo)(d)AA))/.
Proof. Consider any s and any substring t of length s. In order for 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 t is assigned as a token as,
d
P(t is assigned as a token)
II 1=1
max P(tisla)
5)0(s-1)/2
I c log(d) -50(0- 66(0-1)/2
where (i) uses the fact that max P(t.a) bounding across the |Ale strings of length
II = E P(tyla) S (1 6)¹. By union
P(any length s string assigned as token) S e +
-ogd)) -0(0)-
When = 4 (d A))5+11 A funx+ 1, the RHS is upper bounded by e 36 < d d-o0oo((//8/0)) With the same small probability, no substring of length > s can become token, since their length-s prefixes are never assigned as tokens.
Corollary A.9. With probability 2 1 (log(ld) learns dictionary with at least d' = d/lmax tokens when run on a training sequence of length n drawn from a stochastic source satisfying Assumption 3.2
Lemma A.10. For any constant B < 1, with probability 11-dd9(ooid/6//)) exp( sdg(d (d) over the source dataset, every substring in Mę is added token to the dictionary in run of the LZW algorithm. In other words, with the same probability, the LZW tokenizer results in a B-heavy hitting dictionary.
By Corollary A.9, note that with high probability the LZW tokenizer adds at least d' tokens to the dictionary when processing length d training sequence in entirety. In this proof, instead of generating d samples, we sequentially sample d' tokens from their joint distribution, and generate a dictionary from these samples. From Corollary A.9 with high probability this results in most d samples being generated, implying that the dictionary generated by sampling d' 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 portion of the dataset.
Next we consider a joint view for generating the dataset from the stochastic source and the dictionary learnt by L.ZW simultaneously. The stochastic source is sampled the last character of the previous token was a'. Sample a character ~ P(-Ja') and an infinite trajectory the tree T Consider the first node visited in this trajectory which does not already
sequence of tokens. Suppose
19

---

exist as a token in the dictionary. The substring corresponding to this node is added as 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' times, which results in subset of the dictionary output by the L.ZW algorithm with high probability (Corollary A.9p. This is simply variant of the "Poissonization" trick to avoid statistical dependencies across tokens. Denote the set infinite trajectories generated on the forest (Tg a A} as {traj, i E [d*]].
With this view of the sampling process, observe that if the substring sampled was a prefix of traj; at least it| times across different values of i, then t must be assigned as token. In particular, in each of these It| trajectories, each of the prefixes of is assigned as token. With this observation, the event that t is not assigned as a token is contained in the event that t is visited at most [t] 1 times across the d trajectories. Observe that,
1 1
Σ ( max ( T=
P(t is not assigned as token)
S
Since we aim upper bound this probability across the substrings in t Ma. note that (i) m P(t]a) 2 8/d9, and (fi) tokens in MMs have length most l, = 8- log(d) log(1/6))
(Lemma A.7p. implying there are at most 2|. substrings in this set. By union bounding.
P(t E M3 not assigned as a token) S 2|
Σ
max x' x'(1-2r) -0)
(11)
2 26/0
Case I. For S l, and 2 1/2.
L c. (d')
(1))
S LAle. (d
i x2((1 x))dd=
2d 12
< 2 log(d" (Ll)) d'))-d"? /2
$ ax,add))
(12)
where the last inequality uses the fact that 4 (log(dd
Case II. For i S E, and 8/d Sx S 1/2.
L d'
- |Ale, (dr
i (o)(1 20)a
x²(1 - x:
Al (
z e () lop(d")-at
s e 2(8 log(d/6))
(13) where the last inequality uses the fact that l, = (log(d)), x 2 d/d", d' = (o///og((/))). By combining eq. (12) and eq. (13) with eq. (IT) completes the proof, as long as 33 is constant bounded away from 1.
S 0882d0 l/lo((//6))
Lemma A.11. Fix constant >> O. Then, with probability 2 d (log(dd) none of the substrings in the set N₂- = {s' max P(s S 5/d are assigned as tokens run of LZW.
Proof. Define the following set of substrings.
aeA { t: 8/d max P(t]a) S 1/dl+1/2
Sy
Since the width of this band is sufficiently large, by Assumption 3.2 every substring t such that max.5A P(tla) 8//2 has at least one prefix which falls in S., and denote the longest such
20

---

prefix ty. Define T, {t,, :t E N23 as the set of longest prefixes in Sy. Intuitively, if we think of the strings Sy (or T,) as being intermediate in length, the strings in N, can be thought of as being particularly long: the value of max.e P(t(a) for any t E Ty and for any t E Nr are separated by factor of at least 1/d In particular, since the probability of any character is lower bounded by each substring
E .N must be least A 178] symbols longer than its corresponding longest prefix in T. E.. An implication of this that for to be assigned as a token, t, must be observed at least A + 1 times disjointly in However, note that t, already has low marginal probability to begin with (< 1/d) so the odds of seeing this substring so many times disjointly is very small. Furthermore, note that T, has at most (1+//2/5 substrings, which allows the probability of this event occurring simultaneously across all substrings in T, be controlled by union bound. Under this condition, none of the substrings in NG, are made into tokens.
logid)
In order argue that the dictionary does not contain certain tokens, we may argue this property about any superset of the dictionary. contrast, Lemma A010 we construct subset of the dictionary by running LZW on the concatenation of dt tokens sampled from their joint distribution. The superset we consider here is just to sample tokens from their joint distribution and concatenate them together to result in a string of length 2 d, and running LZW this sequence (which simply would result in these d tokens). As in Lemma(A.II let (rraj; i [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 t E NN, is assigned as a token by LZW is to the event that every substring t' E T, is observed prefix of traj, for A fewer choices of [d]. To this end define E(t') the event that j E [d] t' is a prefix of traj, I A. Then,
Pr(E(t))) -
12
(max P(t'la))*
A
aed
c loR(n)
1
d1+7/2
Se e I log(d))
(14)
where (i) uses the fact that m P(t & 1/d since the substring t' belongs to Ty.
Note that the number of substrings in S., (and by extension, T.) is at most (7/2)) Recall that these substrings satisfy the condition maxac. P(t(a) 2 8/d++7/2 Observe that,
815,1
Σ
max P(t[a)
++1122
tES,
P(t(a) S | A 1
EES, AEA
This implies that there are at most d 1/7/2/8" substrings in S.,. Finally, in conjunction with eq. 14
dL+7/2
P( S, E(t')
logld( d (log())
82
which implies that with high probability, token in S. is observed prefix of s for more than A choices of the index E [d]. Under this event, no substring in Nr, is assigned as a token.
A.6.1 Proof of Theorem 3.6
Choosing 0.99 Lemma A.10 with probability 2 1- 1d (looo(dd) the LZW tokenizer results in 0.99-heavy-hittin dictionary. As consequence of Lemma A.6 this implies that under the same event,
H(QMLE, P) 2 0.99 log()).
Finally, combining with Theorem 3.4 completes the proof.
21

---

B Additional Theoretical Results I: A sequential variant of BPE
While the main results the paper focused on understanding the limits of tokenization under a bound on the dictionary size, in this section we take a more practical look and try to analyze tokenizers used commonly in practice. The Sytte-Pir-Ennooinn (BPE) algorithm (Gage 1994, Sennrich et al. 2016), discovered in the compression literature 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 the tokenization algorithm of choice, such 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. each iteration, the pair of tokens which appear most frequently next to each other are merged together into 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 + (t', (t',t)). dictionary and for each rule t + (t', replaces every consecutive occurrence of t' and t" by the token t breaking ties arbitrarily.
) To encode new string, the BPE encoder iterates through the
To warm up our main results, is worth understanding the behavior of the BPE tokenizer in bit more detail. Unlike the toy tokenizer, it is 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 8 > 0, consider a training sequence of length of the form,
8
01..-01 01
10 ... 10
(15)
2/6
2/5
The probability that this sequence is generated by the order-2 switching Markov source with p = =
5 is.
(1 (1- 81 mp x (8) =e =e-((P) -
log(1/(1 8)). 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 2 Here, we assume that 1/8 is a power of 2 and denote r = log,(1/8 - 1). The algorithm first merges 0 and 1 into single token é1, which results in long sequence of the form ..... t1 repeated m5/4 times. In subsequent rounds, the tokens (t1, t2) is merged t ........ t
which uses the fact that H(P) = md log(1/8) + m(1
into t2, then (t2, t2) is merged into to 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 each other. Eventually these 5 tokens are merged into single token labelled 4,44, and in subsequent rounds the tokens (f,+4, 4x) are merged into b, (tr+5, (r)5) is merged into 6,46 and so on, until is no longer possible.
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 2nd Markov source, with high probability these substrings disjointly occur (mm) times each. The learnt dictionary associates each such disjoint occurrence of these substrings with at least 1 token, for 0000, the 3rd 0 must necessarily be tokenized as the token "0". Likewise, in 1111, the 3rd 1 must necessarily be tokenized test string of length is tokenized, with high probability
as the token "1". Therefore, when 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- 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 this tokenizer must be far from the optimal
22

---

Initial
........ 0110
1 - (0,
........ t lt1
12 - (t1,
1 22 22122
10
by t br--1)
t, 1
l++1 f (tr, )1)
4, 16,0
lx42 f (tr, 0)
1 12,42
tr43 t (tr+1,1)
t 31,
t+4 f- (tr+3, 22)
t
l+t f- (1,44, (r4
444 f (tr45, (+45)
t 8,46
Table 2: A representation of the behavior of BPE when trained the dataset in eq. 15 We assume
that 1/6 - is a power of and define r = logg (1/6 1).
bound of m MHHER (6) especially d becomes smaller,
min QELigmm
Cm enc(-))
min QE
[no logl n 1og(L/QuuL
((m)
min QE@
(log(1/Prok(0) (0) +
A (mm).
where (f) uses the fact that [[mo], F[m] E (2m) and the last inequality uses Purk (0) (1) S 1/4 (AM-GM inequality) since they sum up at most 1. The purpose of this example is show that there exist pathological training datasets which appear to be drawn from a stochastic source, but on which BPE fails to learn good dictionary for the source. Thus proving a result such as Theorem 3.] for BPE would require arguing that training datasets such as that in eq. (5) 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 (11 may priori have been more frequently, it may not chosen by BPE as the next token after 00.
To avoid dealing with these issues, consider a sequentia/sampll-spliiei high level, the algorithm breaks down dataset size (dd2) 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 to the dictionary if it appears more than log(d 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 token added, depending on the statistics of the 4hh chunk and the tokens added far to the dictionary. Based the final size of the dictionary a different encoder/decoder pair used if the algorithm adds sufficiently many tokens to the dictionary, the greedy encoder used, and if not, parallel implementation of BPE's encoding algorithm is used (Definition B.I). A formal description of the algorithm is in Algorithm [
variant of BPE. At
Definition B.1 (BPE.split encoder). The BPE.split encoder parses 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 t't" by t for every rule + (t', t") in DS, breaking ties arbitrarily. The individual token sequences finally spliced together and returned.
The main result of this section is that up small additive error, Algorithm I approaches 2- approximation to the optimal cross-entropy loss.
23

---

Algorithm Sequential implementation of BPE
Input: e (0, 1); dataset of size (dd)), split into d contiguous texts (text,, ... texta) } of
length ((d) each.
Output: A tokenizer T.
Generate Dictionary
for i 1,.., do
if' a pair of tokens/characters (t', (t) appearing 2 log(d) times consecutively in text, then
Append the rule (t',t") (") to DS
for i 1.... do text, - APPLY (t") (text)); (t',
// Can be implemented in parallel
end for end if end for
// Encoder and Decoder
if [Dict] < do - ed/2 log (4].A) then T < (Dict, DS, enCi (+), deCppe.spli (-))
else
T -Dict, 0, enc (), de))
end if
def APPLY te (ts (text): Replace every consecutive occurrence of (t', tt) in text by t, breaking ties arbitrarily.
Theorem B.2. For any e (0, 1), run Algorithm 7 on dataset of n O(d²) characters to learn dictionary with at most tokens. The resulting tokenizer T satisfies with probability 2 1 - Qide?
min QE@
L(Q o enc(-)) s (2 + E) min ((Q) +
Q
where & = O
log(1 /c) log (1/8) c6 log(d)
While the guarantees established for the sequential BPE tokenizer are weaker than those in Theo- rem 3.1 the analysis turns out to be quite involved. Theorem (B.2]imples that unigram models trained on the sequential BPE tokenizer asymptotically approach the optimal cross-entropy loss up to factor of 2.
The formal proof of this result is presented in Appendix B What the intuition behind using a different encoder in Algorithm depending on the number of tokens in the dictionary? When the number of tokens in the dictionary is smaller than dg. we know that on iterations of Algorithm [ a token is not added to the dictionary, i.c. every pair of tokens already appears at most (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 (dd) in 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 monotonicity property. It remains to show that dictionaries which encode new sequences in way where no pair of tokens appear too frequently have large H (QMLE, P) (to invoke Theorem 3.4). This follows from ideas introduced in (Navarro and Russo 2008).
da/ d fraction of the
The case where the number of tokens is large ( dg) turns out to present significant technical challenges for analyzing the BPE encoder. There is no longer much "evidence" that the dictionary in each iteration good encoding strings since in large number of iterations 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 tokens, it is possible that there are short tokens & 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. (15). although the algorithm has allocated large number of tokens, the token 1 is maximal since every other token begins with the character 0.
24

---

However, it turns out that such tokens, although present in the dictionary, are not observed frequently while encoding fresh string drawn from the source.
B.1 Analysis of Algorithm 1
In this section we prove rephrased version of Theorem B.2 which implies the statement in the main paper. Define dg [lo
ed
Theorem B.3 (Rephrased Theorem B.2 Run Algorithm 7 on dataset of (dd)) characters to learn a dictionary with at most tokens. The resulting tokenizer 'T satisfies one of the following conditions,
1. Either, Dict) > do, and,
Ho0
min L(Q o end(-)) < QE@ium
1
Here, O log (1/6) log(1/e) <6 (d)
2. Pr([Dict| < do) = -2(e log (1/5)) or,
3. Conditional on |Dict| < dg, with probability 2 1 1 ef
min L(Q o enc(.)) (1
11-20)
2do 2H + + (Togtan)
2do
+ d
log(4|.A)).
QE gram
ddddd
With the choice of do ed/2 log (4(A)) we get the statement of Theorem
B.2
B.2 Analysis for the large dictionary case:
Dict > do
In the large dictionary case, Algorithm I uses the greedy encoder/decoder pair in conjunction with the dictionary. The proof of Theorem B. relies on establishing that the cross-entropy (QMLES P)
of the tokenizer is large. Namely, we prove that,
Lemma B.4. In Algorithm 7 assuming at least do tokens allocated,
H(QMLE, P) = Ω 65 log(d)
log
To show this, it suffices 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(I/Vd)),
Lemma B.5. Suppose that in a run of Algorithm ! at least do tokens are allocated. Suppose a set of tokens ... tt have been sampled so far by the greedy encoder. Let Ti+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,
d 8)2 Pr (P())+1)t.) S $1/VCod ... ti) ACdA|A|log (2g
c
(1/8) log(1/e)
Proof sketch of Lemma B.5 The proof will proceed in 2 parts. We first show in Lemma B that there is set Dvalid (2(d) tokens in the dictionary which are neither prefixes nor suffixes any other token in Dict. The reason for considering this set of tokens is twofold.
1. Irrespective of what the previous set of tokens were, it is legal for a token Dvand to be sampled in the current step by the greedy encoder, since for any candidate E Dvalids by definition, t, t,t t & Dict for every i.
25

---

2. Suppose a sequence of tokens t1. t, have already been sampled, ending with the character Then, we may sample the next token using rejection sampling. Sample a' ~ ((-la) and an infinitely long trajectory on T Return the last token on this trajectory which belongs to Dict, and it so happens that 3j E [s] such that 1 ... t,t E Dict, then reject this trajectory and repeat. Since all the tokens in Daalid are not prefixes of another token, any trajectory which reaches a token Dalid must terminate the rejection sampling process.
Next, in Lemma B.10, we show that since the number of tokens in Daaid is sufficiently large, ((d)., with constant (in d) probability, a trajectory rolled out in the first round of the rejection sampling process will reach token & E Dvalid which has small probability, i.e. max P(t]a) S 1 (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.
O
P(-Ib, abb & Dict)
aa
ab
ba
a0G
aab
aba
abb
boa
bab
bbo
bbb
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 sampled on the tree with a as root (green path). The last substring on this path which is token (f, = abb) is returned by the greedy encoder. Then the next character x character (b) and further conditioned t Dict. Finally, another infinite string is sampled on the tree with æ as root (purple path) and the last substring on this path which is a token (12 = ba) is returned by the greedy encoder. Repeating this process, we can generate string, here, abbba as well as its greedy encoding, (abb, ba. ....
Figure 7:
sampled from the source conditioned on the previous
Proof of Theorem B.3 and Lemma B.4 It is easy why Lemma B.5 implies a lower bound on the cross entropy H (QMLE: P) of the tokenizer. By Lemma A.4 for the greedy encoder,
nt Ee
14t Ee ne
Qt
lim E 10-000
lim m-000
(16)
ne
Since the limit + oc of the RHS exists by Lemma A.4 we may let m - 00 in any way we like, and in particular we may simply sample tokens, t th. sequentially according to the process in Figure Here, the first token sampled is returned by generating an infinitely long string on T where a π and then truncating this trajectory to the longest token which belongs to Dict. Subsequently for every > 1, l; is generated by sampling fresh infinitely long string from Te where sampled from the P(-la') where a' the last character 4 and then returning the largest prefix of this string which is token in Dict, conditioned on t, ... & Dict for any j i.
26

---

and concatenate the corresponding substrings to get an Σi [4s] length character string. Letting + bo, we must have m + 00 surely since m 2 i". In this view, eq. (16) can be rewritten as,
QMLE(E) lim 000
lim 700
Σ utt
Elu(t; t)]t,
(17)
+00
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 T satisfies maXae A P(tla) S VI/C8'd. From eq. (17), summing across T, we have that,
68
(MMLE(
= lim EET 100
SE Pr (t, ETI ... ..-1) =
(18)
(1/0) log(1/e)
where in the last inequality, we use Lemma B.5 and the fact that max P(tla) Z minge P(Ua). Therefore,
(QMEE P) N Σ (MLE(t) log(1/P(t)) 2
_QLEE(t) log( VC&dd)
RET
tET
where in (i) we the fact that for T, max.EA P(t(a) 1/VC8ad, which implies that P(t) S 1/VC6od. Finally, combining with eq. (18) completes the proof of Lemma B.4 Furthermore, since the cross-entropp H (QMLE P) was established to be large, by invoking the reduction in Theorem 3.4. we complete the proof Theorem B.3
max P(t(a) 2 1/Cd asA
40
ab
AC
ba
bb
bc
Ca
cb
cC
baa
bab
bac
cba
cbb
cbc
Figure 8: The circled nodes indicate substrings which are tokens Dict. The red boundary is the set of substrings t such that max.c P(t|a) 1/Cd. By Lemma B.8 none of the nodes which fall outside this boundary are assigned as tokens a run Algorithm I The set of circled substrings the set of tokens in Dict. Among them, the ones circled green are the tokens in D which are not prefixes or suffixes of any other tokens in Dict. Substrings such as cb or which are tokens in Dict do not belong Dvalid 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 Dealid since they are suffixes of tokens in Dict, in this case, bab. Lemma B.9 asserts that the number of tokens in D are ((d) in number, assuming that Dict has ((d) tokens to begin with.
Notation.
For each a e A and NU {0). define a level set of substrings,
5 = {(1
5)+11 < P(t = a) S (1 5y
27

---

At each iteration, both copies of s perfectly encode to sequence of tokens
suppose encodes to
s suppose encodes t"
Dictionary
s'
$1 818111
87
$18281 87
cach step, both copies of encode to the same sequence of tokens
f < (s)
t
t
f2 < (5-))
t,t ... tj ...tz
ttt t ... to
both copies of s' map to the same token this step. contradiction
- (s-)
t" (1-)
Figure 9: A pictorial representation of the proof of Lemma B.6
where i denotes the first character of t. And likewise, define the sets Sj UaEASy. Sg and Sy as the union of sy over j' 2 j S j and Sgj and Szj as the union of Sig and 55 over A. Furthermore for large universal constant C > 0, define parameters.
A log(o) log(1 8) θ
[oog(1/0)
2 log( 4Cd//do)) θ (lo(1//dd)
nD
(19)
log(1 6)
We first begin by stating folklore result: every pair of tokens assigned by merging- bassd dictionary generation algorithm have distinct character representations.
Lemma B.6. If Algorithm assigns new token in some round, it's character representation must be distinct from that of all previously assigned tokens.
Massgns
We will prove this result by contradiction. Suppose t and t' are tokens which decode to the same character substring, s'. Consider all occurrences s' in the dataset which in some iteration encode into t' or t", and denote these disjoint locations S. Recall that at these locations, s' eventually is assumed to map to a singular token t' or t". Therefore, at every step in the merging process these occurrences of s' must perfectly map sequence of tokens.
Proof. A pictorial proof is in Figure 9
Now consider the merging process the first time before any of the rules corresponding to tokens in t' or t" are implemented. Prior to this time, all the occurrences of s' corresponding to the locations S have not been tokenized yet. When the first rule corresponding to one of the tokens [t',t") is implemented, all the strings in S must be modified identically. This uses the fact that we can isolate each of these occurrences of s' while carrying out the merging process, since each location must be distinct. At every step, the encodings of these copies of s' must be the same, and therefore t' and t" cannot be two distinct tokens.
Lemma B.7. The size of the level set St. is bounded by (1 (1-8)-(5+))
Proof. Since the probability of any transition is at most - 5, this implies that any infinite trajectory
on the tree T can intersect most one vertex in Sy. Therefore, Etese P(t = a) I By the lower bound on P(t a) for E S9. this implies the statement of the lemma.
28

---

Next we show that with high probability none of the substrings t having probability mass (under P) of at most 6/ S/Cd conditioned on the first character, are assigned as tokens by Algorithm
Lemma B.8. In a run of Algorithm for a sufficiently large constant C >> O, with probability d pol(pollyp))1) (1) 6) all assigned tokens E Dict satisfy maxaEA P(t(a) 2 1/Cd. In other words, none of the substrings in Szn are added as tokens to the dictionary in run of Algorithm ? where,
j - log(ō/Cdl) log(11 -
Consider some jr and A and substring E Sy. In the jth stage of the algorithm where text, is being processed, for t to be assigned as a token, at the very least, t must appear at least log(d) times disjointly in text, Therefore,
Proof.
P(t Sj is assigned as a token in text;) - ( d (og((d)
mmxx P(tla) aEA
log(d)
log(d)
dlo((d)
Cd (1 8)--3*
S < log(() (1 83 log(()) log(d)
Union bounding over Sj over j 2 j* using the bound on |Sg] in Lemma B.7 and over and [d] results in the bound,
8)(d-)")og((a
d-
P(t Szj- is assigned as a token in step for some E [d]) S R(1)
(1 - 8)1t1
5(1 0(1-8)
$21
Lemma B.9, Consider the set of tokens Volld which are not a prefix or suffix of any other token
in Dict. That is, D = {t Dict As st E Dict) n (t E Dict As ts Dict). If Dict 2 da. then,
do
| valial 2
4nd
where un is defined eq.
19
Proof. For any token & Dealid- there may be most 2/t] tokens which suffixes prefixes of it and belong to Dict. More importantly, every token Dict not belonging to D must either be prefix suffix of some token in Dvatid- Split the suffixes and prefixes of the tokens in D into four sets,
1. Ssutf,min UtED It's E Dict t' suff(t), |t' s |t np).
2. Saulf, max
= UsEDiam (t' E Dict suff(t), [t'] > | -nph.
3. Spremin Use (t' Dict t' pre(t), |t'| [t] -np).
4. Spre,mux = UtE (t' E Dict t' E pre(t), |t' > | nD).
where un is defined in eq.
Note from Lemma B.8 that all the tokens Dict all Therefore, the tokens in Spe,min and Suuff all satisfy, By,sumiing [Spre.iin| - 11 < 22cd(16j)n
satisfy max P(t(a) 2 1/Cd.
maxaEA 2 d/C(1 8)nD By summing Lemma B.7 over appropriate j. we get that
On the other hand, corresponding to any E Dvalid, there are most np tokens in Spre,max or SultImaa and and therefore |Spe,max I |Ssutt, < nd ID Since every token in Dict either belongs to D valid or is suffix of some token in D Spee.min Spre,max Sun Saut, Dict| and,
2C(1 - 5)"D ld
2np DDvanal + 8
2 do
29

---

Recalling the choice of n, 1- 2log(1C//5do) log(1
we get that,
Valial 2 do
4nd
Lemma B.10. Suppose Algorithm| 7 aassinss at least dg tokens. For any character E A, sample an a' P(-aa) and an infinite trajectory on the tree Ta denoted traj. Then,
P(tla) S V
dog0 (1 - 8)
Pr IrajtT
min (EtrainDraa
SCdA AInD
where the notation T used to overload the distribution over infinite trajectories on T The purameters T&D and A are defined in eq. (9).
Proof. By Lemma B.8 recall that the 2 do tokens assigned in run of Algorithm ! with high probability, substrings in Sep For any E A, the total number of substrings in Sgg can be bounded as,
1s
Σ ΣΣM aEA j=0
1915 EIST
ΣΣ aEA ;= (1- S
1
C 8(1-8)
(20)
In order prove this result, assigned. Consider some character and all the leaves in the forest Sgjx. Since every transition has 2 probability of occurring, across all leaf nodes t E Sejz, P(tla') are within a 5² - 5) factor of each other across different a' E A. In partieular, by counting the number of paths in T (i.e. paths in TA from 0 to leaf nodes in St across a E A) along which a token in Dict exists S2j+/2 /2, we can also compute the probability mass across such trajectories up to a factor of 5² 6).
counting argument and the fact that tokens in Szj-
Taking the union across E A, consider the paths in Tx from 0 to leaf nodes in S From Lemma B.9 Ejsr |Dvalia n Syl 2 4./4nD. where nn log (ag((Add/do)) log(1 8). Note that for sufficiently large d = ([cllog(///6///// do/8np. Therefore,
Lemma B.7
Σ ンイ
|S = (dd/6/5(1-8) s
do
Daalid n nSy
(21)
8nD
3" /ク<
Define A = log(O)/log))) log(1 - 6). Combining eq. method, there exists an i* 2 jr /2 such that,
21 with eq. (20 and applying the probabilistic
Dvana n (S..1U....U U... U....US.+A)).
8(1 0)do
(22)
S...U...UUS U..+Al
SCd|AAp
Note that chosen to be sufficiently large, so that every infinite trajectory on T must intersect at least once with the band of vertices S4 U... U S Note that this band is different from the one considered in eq. 22 Define Tag the set of longest prefixes across infinite trajectories in T which belong to S4+++ U....U...
S
Note that objective is show that an infinite trajectory sampled on T where a' P(-la), has long prefix in Dict. We can truncate this trajectory to lower bound this probability, and therefore, we assume that the infinite trajectories on To terminate once they reach substring in Lar- Furthermore, note that although A is large, it is still constant depending on 8. Therefore, the band of states S U... U S: +24 is not too wide, and all the substrings in L have approximately similar probabilities to each other. In particular, for any character a E A, and for any a' E A and t E Tegt decomposing P(tla) P(t P(a'(a)
( 04 & P(t(a) 3 01-4)
(1 8) -01 (1-
(23)
Inequality (i) follows from the fact that all transition probabilities are at least 6, so every leaf node in La must have p(ttt, a') 2 (1 ++2++1 and the fact that P(a'la) 2 6. Incquality (ii)
30

---

follows similarly from the fact that is leaf node of La and therefore P(t = dd) S -8)+ Therefore, instead of bounding the probability of any event under the distribution over substrings in La induced by truncating the infinite strings sampled on T it suffices to count the fraction of substrings Lo satisfying the event (which are equivalent up to 8(1 5) factor). Defne,,
pre = (t1, f1:2, 11:3. ... ((:jte))
As the of prefixes of t (including t). Note that most A of the prefixes of any substring can intersect with S.t +1 U U... ......... U... Therefore,
Σ Σ ((pre(t) n Drana n ( U U US # 0)
d'EACEL
pre(t) Dvali (S U S
d' d'EALELS!
Dvalid n (S U .... US -a)
a'EA
(1))
8do(1 - 8) Σ
1 U...US
8CdA Alno d'EA
(100)
dd Σ
SCdA|Aln
a'EA
where (i) uses the fact that the prefixes of E La cover all the substrings in Sa +s++ and therefore UtEr, Ure(t) S4'41 U...UUUU..... Sf: and (di) uses eq. 22 Finally, (idi) uses the fact that A is not too large, and therefore, for any substring t' E S4'41 U... US there are at most 1/(1 - 5)25 = 1/02 substrings t Tua which contain it a prefix. This means, Tea! 15% U...U 1// After dividing by Ex'ed [La'l on both sides, this implies,
(pre(t) n Datla n (S U....US;++A) #0/o
do 8) 2 A(nD
Enr~Unif(A)
Pr L.if
(24)
The event inside the inner probability term is the event that an infinitely long string (truncated at L has a prefix which lies in Dvalid and which intersects with S4-+1 U... S which implies that has probability P(t]a) S V0/Cd. Therefore, we have that for any E A. sampling an a' P(-la) and an infinite trajectory traj ~ T
P(taa) s V1/Cdld
E EgTP((a))
Pr Traj
min Pear
(1)
P(tla) S VolCud))
2 60 6) -Eo'NP(1a)
Pr (~Unni((..r))
min (epre((")nDwu
(18)
2 81 - 6) -EamP(())
(pre(t')
D Dvali n (S U .... U US +2) # 8/0²)
U')Uni((L.r)
(1H)
2 83(1 - 8) EarwUmIA())
Pr ((~Uni((L..))
(pre(t') n (S U... U...UU # 00/a()
0dd - 5) SCdA|ARD
2 21-
Here (1) follows by truncating the trajectory traj to terminate at a node in La and from eq. 23 (ii) follows by arguing that i j2² and therefore if prefix of t' lies in Sp U U S then must have P(tla) S V8/Cd. Inequality (iii) follows by noting that all the transitions P(a" ()) have probability 6, and the last inequality follows from eq. 244..
31

---

Proof of Lemma B.5
Lemma B.10 concludes that given any previous sequence of tokens terminating in character with constant probability, an infinite trajectory sampled from T with a' P(-la) has as prefix, a substring t, which not only has low probability, with P(tla) S /8/Cd, but also belongs to the subset of tokens Dvatid- Note that regardless of the previously sampled tokens, it is legal to sample any token in Dvalid as the current token, since by definition, these tokens are not the suffixes of any other tokens in Dict. Moreover, if any trajectory on To reaches token in valldd then it must be largest token along that trajectory, since none of the tokens in Dvalid are prefixes of another token in Dict.
Consider generating a new token by rejection sampling. Suppose the set of previous tokens t,... t end in some character a. Sample the next character a' P(-la) and an infinite trajectory T If reaches an illegal token t such that t,t,+1 ... t,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 token in Dvalid, it must immediately be output as the next token. Note that this probability is lower bounded by,
P(tla) S Vo/Cad
E((a)()aa)
Pr rraj
min tetrainDaam
which is lower bounded by poly(e, 8), the subject of Lemma B.10 Therefore with this probability, the process terminates in the first step with a token in Dvalid being sampled.
B.3 Analysis in the small dictionary case
In this section, we will prove Theorem B.3 2 and Theorem B.3 3. In particular we show that, either,
1. The dictionary small with low probability. i.e., Pr((Dict) < do) c - (1/6)) or,
2. Or conditioned the dictionary being small, [Dict] dg. with high probability 2 1 e D((ed/ log" (1/8)),
L(Q o enc(.)) < (1 min QEQ1-pm
2do d
2dg + +0 log(d) )) Hoc +
(
d 1og(2||4))
For E [d], define the indicator random variable,
X(s', Dict) a pair of tokens in enCape(s') under Dict appears at least log(d) times).
which captures the event that the string s' compressed well by the dictionary Dict under the sequential encoder.
Let Dict, denote the dictionary stored by Algorithm right after text; 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 s'. if there exists a pair of tokens appearing more than log(d) d) times consecutively in the sequential encoding of s' under Dict,, then there must exist pair of tokens appearing more than log(d) times consecutively any < j. This implies that X ((s', Dict,) < X('', Dict,) if < j for any string s'. This monotonicity property implies that the last dictionary output by the learner, Dict, sequentially encodes a 1 fraction of the previously seen texts, text, in a way where every pair of tokens appears at most log times. While Dict, is correlated with these texts, we can circumvent this correlation by using a martingale argument to prove the statement of the lemma.
the greedy encoding of s' under Dict, for
Lemma B.11. Let Dict be the dictionary returned by Algorithm 7 Then,
min { Pr (E[ Dict) Dict] 2 22d//llDics < <o) Pr (liit < do) S s- - 22//810g2
where of is a fresh substring of length d sampled from the stochastic source.
Proof. Let Dict, denote the state of dictionary returned by Algorithm right after text, is processed.
Then, Dict, is the final dictionary returned by Algorithm!! Suppose E E[X (s', Dicta) Dictu] 2 2do/ dd
32

---

where s' is a fresh substring of length d sampled from the stochastic source. Using monotonicity of the sequential encoder, almost surely for any string s', (s', Dict,) s X X Dict,) for any i. Therefore,
E[x (s', Dicta) Diot.] 2 2do/d
Σnn E[x Dict:) Dict.] 2
2do
d-1
(25)
Note in this expectation, s' is an independent string of length d sampled from the stochastic source. Since Dict, and text;+1 are independent, we may instead write,
Σ E[X (text++1, Dict:) Dict; text, D Dict,, texti] 2 2do
d d-1
For brevity, denote X; = ( Dict,) Dict, and define the filtration F; a ([text), Dicti ... text;, Dict; })- Note that Σj= X3 - F[X forms a martingale se- quence under the filtration (Fs : E [.]. Therefore, by the Azuma Hoeffdin inequality, for any n >
Pr Σ
E[X|F] -x s se-
(26)
Under Case I, we have that > aml X₁ S do. Therefore, from eq.
25 and eq. (26).
d
Pr (Dict) < do; IE [x(6', Dict] 2 2do/d) s Pr
Σ
Xi < dos Σ
E
2do
d
i=1
1=1
d-1
2-2
S Pr
[ - x,
15(1-2100
6//2 - d/8llo
Finally, using the inequality Pr(A, B) P: > (min (P(A), completes the proof.
Proofs of Theorem B.3 and Theorem B.3 3
If Pr([Dict| < do) S "ddd/// (0/8 the proof
of Theorem B.3 concludes. Otherwise, consider the case Pr([Dict] < do) log
whereby, E[X(s', Dict) Dict] S 2dg/d with probability
e- log/ 2ogg (1/8) conditioned on [Dict] < do by Lemma B.11 Recall that when |Dict < do, Algorithm I Juses paraliel implementa- tion of the sequential encoder which chunks a new string into pieces length d, denoted (chunk; i E [d]} and uses the sequential encoder under Dict, to tokenize each chunk. Note that since the source Markovian, the chunked process (chunk, = (X,4+1, X ... X(++1)a) : 1, ...
also Markovian and ergodic. Therefore, by a similar limiting argument as in Lemma A.44 using the argument (cf. Proposition 4.2 in Chen (2088) for Markov processes, we have
that,
Σl= X(chunk,, Dict E[X Dict)] < 2do
lim 200
where s' is a fresh string of length sampled with initial state distribution as the stationary measure of the stochastic source. On the remaining (limiting) 2dg fraction of the chunks, their sequential encodings have every pair of tokens appearing at most log(d) () times consecutively. Using Theorem Navarro and Russo (2008). the number of tokens in the encoding of each of these chunks cannot be too large, and satisfies.
lencgre log |encgpe S 2dH + O(d/ log(d)) (ccuukk) ) log d < 2dH + (o)/)))())
(27)
For the (limiting) 2do /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.
33

---

! and consider the unigram model Qmi 2Q Q2((t,, which the uniform mixture two models,
Define & = (X (chunk, Dict) = 1 where Dict = Dict, is the dictionary returned by Algorithm
Qi(1) x (2(A))1E))
and Q2(1) IF
enC (hhnkk)) (cCunn).ss(chuunn
and let Quni (t, .... (.) = 2# ()) Quii for some distribution 2 over the number of tokens to be chosen later. We will analyze the case where the total number of chunks l is finite and take the limit m oc: later. Then, the overall loss of the algorithm is,
mm Cin(Qun Quni enc(-))
Efoog (en((enCpP
Σ teDict
E(me log Quii log (pnC(eennpp
11
Σ Diet
nt log Quiilt)
+ +og(mm)
i=1
Σe 1=1
E
Σ te Dici
n log Quni
& Pr(E.) +E
Σ EEDit
nt log Qumi (t) & Pr(e)) + log(m).
(28)
where ni is the number of times is observed in the BPE encoding of chunk; and (i) uses the fact that BenC follows some distribution supported on [m]] which implies its entropy is upper bounded by log(m). First observe that,
nt
E
Σ Dici
nt log Qumi
(chunk()
E (encur(cchunk,
log Quni (amit) 34
1=1
1=1
2d + Odd/lg((d)
Σ
DEDict Q2(t) log Quni(t)
log(d)
where (i) uses the upper bound on |enCApR.spin (nnnnpe.ptncchunnk)
(chunk)) under the event ε (eq. (77)) Since Quni t = (+) + (t))))= > 2 (t) and Q2 is distribution supported on at most d tokens, this term results the upper bound,
née log Qumi < (2dll + O(dd/ log(d)) log(2d).
Σ
Σ DiDt
(29)
log(d)
1=1
On the other hand, since Qumi (t) 2 (t)())
Σ ni log(1/Qunll
5
Σ DDDit
nt log(2/Q((tt) &
DeDict
Σ n (log(2) + [t] log(21A[)) & tEDio
ld log(? (2) + ld (og(2)AA)
(30)
where the last inequality uses the fact that EtEDiet n and Ete [t|n d computes the length of chunk;
Overall, since Din Pr(E:) - /dn/dbu by eq. (7 combining this with eqs. (28 to 30
Lm enc(-)) 5 (1-
2dg
2dH + O(dd log(d)) log(2d) + d log(d)
2do ed ed (||A)).
d
34

---

Dividing throughout by the length of the character sequence m E [d(e df and letting e - 20.
L(Q enc(.)) - LQQumi uni o enc(.)) - (1
2do
22 + +0 log(d) ))
1
2dl log (1|A))
min QE@1mpm
d
C Additional Theoretical Results II: Learning the likelihood model
The guarantees we prove in Theorems 3.1 downstream model 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 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
3.6 and B.2 on various tokenizers assume that the
interesting open direction for future research.
The result of Theorem 3.1 establishes that under appropriate assumptions on the Markov source, there exists tokenizer T and unigram model over tokens Q" Q1-gram such that,
lim [Iog(L/Q(een((s)) m-+00 m
L E [lo((1/P(s))
S (1++a) lim m-+000 m
Or in other words,
1 ('K((P,Q"(enO
L E [lo((1/((s))
lim m 00 m
S
m=-000 m
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, establish finite-sample guarantees on learning Q* 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 0 E (0, 1), define Eg as the event that every maximal token & (Definition A.5 in the LZW dictionary satisfies 1/d 2 max P(t 2 8/d/+0, By Lemmas A.10 and A. when the LZW tokenizer is trained on a dataset of size 22g (d)(d) drawn from a stochastic source satisfying Assumption 3.2 Eg occurs with probability 2 1 d (log(())))))
Theorem C.1. Consider any constant 0 E (0, 1), failure probability 1) E (0,1) 1) and approximation error & E 1). Assume that the learnt LZW tokenizer Tizw satisfies the event &e. which occurs
with probability 2 1 d -o, (log(d)) Assume that d'-30 211+2110 8 8-2 and that the stochastic source
satisfies Assumption 3.2 For an absolute constant C > 0, assume that the size of the training dataset least (E). where,
Cdl+8 log (d/n)) log log(d/n)
nim
852
Then, Algorithm
2 learns a unigram model Q such that,
L(Q e encgre()) S (1 + min QE@i
L(Q o enCgre(-)
with probability 2 1-17-
In conjunction with Theorem 3.6 this gives end-to-end guarantees on the cross-entropy loss of the LZW tokenizer (with vocabulary size S d) with the Laplace estimator as the downstream unigram model. We instantiate this result choosing 0 = 0.01 in Theorem C.I
Corollary C.2. Choose any ş E (0, 1). Suppose the data source satisfies Assumption 3.2 On dataset of size (d(d) drawn the source, train an LZW tokenizer Tizw with tokens. Subsequently, using Algorithm 2 learn a unigram model Q using a dataset of size at least ((d11001 /8{2) drawn from the source. Then, with probability 2 - -lg(log(d)),
1+
L(Q enc (-)) 5
min L(Q),
1 g
where log(1/8 0.99 log
35

---

The analysis of Theorem C. 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 Markov process. In general, given a set of previously sampled tokens ,,,... L, the next token 1,+1 sampled from the distribution P(t++1 1 44; Vj [i], f4-j+1 ... 4,t,+1 z Dict). The conditioning is to simply guarantee that the previous tokens which were sampled were indeed maximal, since E,l,+1 E Dict, then the previous token returned would in fact have been this longer token and not t, (and likewise for t;- 18,1++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 {Vj [d]. E--++1 .. t,,,,1 & Dict) can be removed, thereby resulting in simple Markov process over tokens.
Furthermore, we establish that this Markov process has 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 KI. divergence ends up being closely related to estimating a distribution from ii.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 al. 202T: Mourtada and Gaiffla 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 O. The non-i.i.d.nes. 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
Input: A training dataset of size Tims likelihood model class Q, likelihood model training algorithm TrainLM
Output: Likelihood model Q E Q.
1: Tokenize the training dataset into sequence of tokens T= (d1,-... 4.).
2: Train a likelihood model Q on the tokenized dataset T using the TrainLM Q) subroutine.
// In the case of Q Q1 gram use the Laplace estimator
def TrainLM(T, Q gramm ):
3: Truncate the dataset to the first | mmax] tokens where lmax = 4 log(d)A))) Let the truncated dataset be Tinne
4: Construct the unigram model Q with @ Unif((m)) and @rok (t) +++|Dier
I| ne is the number of times t appears in Tirunc-
// Test sequences are assumed to be of length m.
C.1 Proof of Theorem C
Since Tzww uses the greedy encoder, the cross-entropy loss of the unigram model learnt by Algo- rithm 2 is.
L(Ô o enc
(.)) o
min
L(Q enc (-))
Qe@iaum
= max
lim
El [log( (eengggeeegge)))) (()
QQEQi.aam -ggan -00
(
max
lim
(encgre (s)l
Rtt
Qua (t))
+
log(m)
QE Qummm wh 10 m
enc (s)
m
teDic
)
(16)
lim
E
lenCgro(s)
f4
log
nt/ ne/lenc (s)
log(m)
m 00 m
enc gre (s)
Quok()) (t)
m
DiDi
where in (1) use the fact that Q+ [ni] and in (ii) we take the maxf.} inside the limit and the expectation (Fatou's lemma and Jensen's 's inequality) and plug in the maximizer of the negative cross-entropy, Qiok (t)
221
Note that limm-+00 [on]
QMLE(t) by Lemma A.4
ienc [+]]
36

---

Moreover, since (enc(s)l/m I and Qook(t) > 0 surely, by the Dominated Convergence Theorem,
1 Lneeeee (s)]] KL(QMLE, Ptok) (31)
L(Q enC (+))
min QE rrggon
((Q eno (-)) S lim m
By eq. (6) we have that for any tokenizer using the greedy encoder,
encyre (s) (H(QMLE: P) log(1/8))
lim
I H
172 172+00
m
Furthermore under the event & which implies that the learnt dictionary is - -f)-eeaa hitting (cf. Definition A.5), which implies that,
H(QEEE P) 2 (1 0) log(d).
Therefore, by almost sure boundedness, we have that,
Hx lim [[enCre [s)]] 0) log(d) log(1/8) 110+00 772
minge Qu.mm L(Q enc(-))
(1 0) log (1/
Putting this together with eq. (3 have that,
[(O gne (.)) v KL(QMLES emx))
min Qe@i.gom
L(Q o ;
(32)
which uses the assumption (1 - 8) log(d) 2 1 + (0)(1/8). In the remainder of the proof we upper bound the KL term.
By the law of large numbers established in eq. (34) and the fact that
The Een
E
[0, 1]. we have that,
E[ne] E ne]
QtLE(t) lim E
lim
T(t),
Re
where (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 a0 A.11, for any constant 0 E (0, 1), with probability 2 do (log(d)) every maximal token the the LZW dictionary satisfies 1/d--0 2 max, P(t(a) 2 8/d'=0, Let Spe denote the set of tokens which have 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 ti...., ,t, the next token is necessarily in Sye and can be any token in this set. The reason for this is that for any t,, t E Sye. the concatenation t,t & Sge since max.cA P(t,taa < 1/5d(11-0) which is smaller than the max,e P(t'la) ()) 2 8/d2+0 for any token E Syn as long as d' 31 2 1/52. This constraint implies that in the sampling procedure in Figure 7 it suffices to drop the conditioning the event 1 ttt & Dict while sampling the next token This condition automatically implies that the sequence of tokens conditionally follows a Markov process with Pr(t++1 t|t,,- ... 4,) Ptt last(t;)). Since the probability of every transition is lower bounded, this means that the Markov chain is ergodic. Moreover, the pseudo-spectral gap
Naoo et al. 2020 À can be lower bounded by the Dobrushin contraction coefficient, K,
1 A
max (Dit?
Pr(-It) -r((-lt))
Σ min(Pr(((1))
max EDit)
< 8d/d'
0d
(33)
Recall that the learner is given a training dataset of 7im characters to train the likelihood model. By Lemma A.8, with probability dI (0lgl the run of the LZW tokenization algorithm, every token in the dictionary has length most mmxx (lg(d)) Therefore, suppose the learner
37

---

always truncates the dataset to the first n' maxx/ tokens and runs the Laplace estimator on this truncated dataset. With this, we move onto upper bounding.
KL(QMME: Quk)=
Σ
T(t) log (xtt)/Qua(tt)
DEDict
which necessitates lower bounding Quak (t) for every Recall that the learner's estimate Q(t) in
Algorithm 2 is the Laplace estimator, Eg +Ditt where {ne t E Dict} is computed by truncating the dataset to the first n'' tokens. Firstly, by invoking Corollary 1.3 of Naor et al. (2020) for the function nt Σx l(t, = t).
net1
IF [e Pr [ng - E[ny]] 2 ev log(1/n) S
(34)
for universal constant c > 0. particular, this implies that with probability 2 1 17. simultaneously for all t,
V d E [e)] log((Dict)/v)) and, E[me]] n4 Elne]-
114 E[me]] S A,
Under this event, for any t, the estimate lower bounded by,
nt + 1 Qua(() n' + |Dict
E[re]] + min [e)], A+)
n'' + Dict
(A, 1) n' + Dict [+
max
x(t)
(n')² 2 + n' Dict
+ |Dict]
x(t) Den' |Dict [[met][[m]]
max
(n')2
n'' + Dict|
Suppose the following condition is satisfied,
n' 4rd Dict| log( Dictl/n)
(CI)
8
for some r 2 Under this condition, we have that n' 2 2VT and n' 2 4r Dict).
Case I. Ann' 2 [ict
In this case, have the upper bound,
24. TT() n'
Quak (t) 2 max
n' Dict
Eine] log [Dict//n /m)
max
x(t) 2
n
n'' + Dict
T(t)
2 max
T(t) V
r/Dict]
2n'
where the last inequality uses eq. (TT.
Consider two sub-cases,
Sub-case I. (t)) 2 2/r(Dict]. Define this event Cj.
Here,
3 r(t)
(t) ((t()))((((Qx - log 1-
v ((trr|Dict
(35)
r(Dict
38

---

Sub-case II. x(t) & 2/r|Dict.. Define this event C₁I
Here,
4n'
log((((())) S x(t) log (2n'r(t)) s max 0, Diitt
log
r|Dict
log (16el log( (De((iic)/)))
(36)
Dict
Case Aen' < [ne]] Define this event Cin. In this case we have the upper bound,
2 Dict in]]
x(t)
Quck (t) 2 x(t)
2 x(t)
(n')²
2r
where the last inequality follows from eq.
(C This implies that,
(t))
log(z < -T())) 1/2r)
(37)
r
By using the geometric ergodicity of this Markov process (eq. from an arbitrary initial distribution,
33
when n' tokens are sampled
(1- (1- ग.
E[ne] n I ne
(1--a") T(t) x(t) S
Qook
Qrok (t)
e 1r Dict| log( (ictt/n)
1 d-
where in the implication, we use the condition on nt' in eq. coefficient & eq. (33).
C1 and the bound on the contraction
(L(QE Q1ok)
=E (t) (og(lo))) (t))/Q(
teDict
((t)
d log (t) log(1 d
teDict
((C))((t) log(( (t)) + ((C))T(() (og(m)))) (t)) + I(Cm)=(() log(m(t)/Quus) (t)) + 2d
d
DeDic
((C)
3
(t) Dict
(CC))
2
log (16d log (Dict//n)
[(Cm)) T T(t)
+2d
d-
2
r|Dict|
DeDic
eq- 555
16
3
Dict]
2
log (16d log( (Dict) /n))
-d
1- dr
2
r
Dict
r
r.
5
log(16d log( [Dct)/c))
Vr
Combining with eq. we get the bound,
L(Q enc (.)) < (1 KL(QQLEE Q))
min QE@.mm
C(Q enc (.))
5 Vr log(16d log(d/n))
1
min
L(Q enC (:)).
QE Q
Rescaling be r(log(16d log(d/n)))² completes the proof.
39

---

D Additional Theoretical Results III The generalization ability of tokenizers
The proofs of the upper bounds in the paper (Theorems 3.6 and B.2) relied on showing that the entropy (QMLEE P) is large, 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 fundamentally different from having a tokenizer which compresses the training dataset well. In other words, consider the following modification: the measure QMIEE F 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 defimition of QMLE 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 (QLE, P) metric, in sense, captures compressing the source dataset well. However, we show that general, this does not result in good tokenizers that minimize the population cross-entropy loss, suffering from minqe Qin L(Q enc(-)) = ( > Ho.
Theorem D.1. Consider the stochastic source in example A.7 having entropy rate H = 0log(1/0) (1 (1-5) 5) log(11(11 8)). Consider training dataset of size n. For dictionary Dict and t E Dict. (8.)) define Qt) [ as the empirical distribution over tokens induced by the greedy encoder when encoding the training dataset, Sarc- There exists a dictionary Dict such that with probability
- -D(yn) over the training dataset,
((QMLE, Pa) o1 (1- ((141/4)
large. However, for this dictionary, for any encoding algorithm (including the greedy encoder), the resulting tokenizer T (Dict, D, enc(.), dec(.)) satisfies,
min QE
L(Q enc(.) 2 (1 (()
where = 2ne -n (1 (I==(1-0(n~V)))
Proof. Suppose the entire training dataset was compressed into single token, fan- The dictionary A U twe.. In the following argument, we show that the number of occurrences, ft,,. of the entire training dataset ty in new string of length m generated from the stochastic source, converges to its expectation as m oc. Let T(( denote the stationary distribution of the Markov process induced by the stochastic source over length-n strings with shift of from the starting position, and let n denote the number of times appears in the training dataset starting at the position
for some
r > 0. Then,
lim
Tit
lim +0-+00
u.s.
Σ i=0
E E [P(t
I max P(ssslla).
(38)
mL
aEA
i=0
The second equation follows by considering the Markov process induced over length n strings and applying the Krylov-Bogolyubo argument for ergodic and homogeneous Markov processes.
In Lemma D.2 we show that with probability 2 - - the token tue constructed from the source dataset satisfies, max P(t(a) S (1- -1/)) In other words, the source string has exponentially small probability. Combining this with eq. (38), with probability > -Q(vm) over the source dataset, the number of occurrences of the substring bye in a new string 8 is upper bounded by,
lim The as
(1- 1/4)) & e/2n.
m
By the Boglol--Booyyubov argument, for each a E A = {0, 1]. lim nh (a)) More importantly, the number of times is made token is upper bounded by n. and lower bounded by na mM,.. Therefore,
(1- x(a)=
E < lim
Th - (()) 2
(39)
2 m0
40

---

Finally, putting everything together,
min lim cm (Q enc(-)) Qe me +00 m
=
min
lim
log(Q;)) ((enc(s))) + > nhe log Qtok (t)
QE ge@i-p
m--00
m
min
lim
Σ aEA
no log Quak(a)
QE pun 1/ 100000
m
min -(1 E)
Σ
T(a) log Quk(a)
CEA
mm
2 (1 - (T).
where (i) follows from the lower bound on nla / in eq.
39
This completes the proof.
Lemma D.2. With probability 2 1 11-e-S ((vn) over the source dataset,
max P(tsre -0) 1/4)) aEA
Proof. Let denote the number of [n - 1] such that 8; * 8,41 in 8, 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,
max log P(tare (a- -X + l) (n 1 X) Xogog11 8).
aEA
Note that X is sum of 1 i..d. random variables, since I(s; * s Ber(o) does depend on whether = 0 or = 1. In particular, by Hoeffding's inequality, we have that with probability 2 (((())
max log P(tsela) H()) S so (n(n1/1) n aeA
which uses the fact that [[[]= 6(n 1) and H 5 (1o)(1/)) + (1 5) log(1/(1 - -8)). Taking an exponential on both sides proves the statement of the lemma.
E Additional Theoretical Results IV: 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 string into the shortest number of possible tokens, but 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 isolation. Its interaction with the encoding algorithm pertinent.
Definition E.1 (minimal encoder). The minimal encoder parses new string into the fewest possible number tokens from the dictionary as possible. Ties are broken arbitrarily.
Theorem E.2. There exists stochastic source parameterized by 5 (0,0.5) and a dictio- nary Dict such that under the minimal encoder/decoder pair, the resulting tokenizer, T (Dict, 0, enomin deCmin(-)) generalizes near-optimally,
min g
L(Q enCmin (:)) S 1.273H
(40)
Here the entropy rate of the source, Ho., is dogl (2/00) + (1 5) log(1/(1 8)). However, the same dictionary Dict under the greedy encoder/decoder pair, i.e. T' = (Dict, 0, enc (-), decgre generalizes poorly, suffering from cross-entropy scaling as,
(1) H(T).
min
L(Q encgre (-))
(41)
QEQ1 yoar
3
where the entropy of the stationary distribution of the source is H(T)) 1 log(8) and the 1 (1())
term is (1 - 8)2 81-1
41

---

0
2
8
Figure 10: order-1 Markov source used in the proof of Theorem E.2
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 constant multiple away from that achieved by the character- level tokenizer. The separation between eq. (40), and eq. (41) only manifests as ô becomes smaller and smaller.
In this section, we prove that generalization of 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-lengti encoder/decoder which achieve small cross-entroe loss, which do not generalize under the greedy encoder/decoder.
We split the proof of Theorem F.2 into two parts. We first define the stochastic source and dictionary consider. Then show that under the minimum-length encoder, the asymptotic cross-entropy loss is upper bounded by oo up to a constant. Finally, we show that under the greedy-encoder the same dictionary suffers from high cross-entropy loss, which is constant factor away from that of the character encoder.
E.1 Stochastic source and dictionary.
Consider extension of the switching Markov source in example A.I to A= 1, The Markov chain is described in Figure 10 The transition of the Markov chain is P(Oj0) = P(1 P(2 = 1- 6. and P(] 1 5 and P(2[1)
1)) 6/2, with the remaining transitions being 0-probability. For parameter > 0 to be instantiated later, define 51 (resp. So. .S2) as the set of all-1 (resp. all-0, all-2) strings of length < l - including the empty string. Consider dictionary composed of the following set of tokens, {18 E So U S1 U 52). Therefore, the tokens follow the template 1....
0, 11
12... and of length most f. l is chosen to be 2 log(1/6) (1/8)/8.
Although we use the minimal encoder the statement of Theorem F.2 for the purpose analysis, define the following encoding algorithm: if the string is prefixed by 10.. or 1 2, select the largest prefix which exists in dictionary and assign as token. If the new string starts with a sequence 11 1 of length x, consider the first max }} length prefix and assign it as 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 simplification of the overall cross-entropy loss,
min
lim Lm enc(.))
Qeaiam
lim Qeeigan m0
min
I E
log Q# (JenCmin(s)) + E nh log Quok
(42)
lim E [log(m) enn (s) log [Dict]]
(43)
10
m
where in the last inequality we upper bound by choosing Q# = (nil((m)) and Quok 1/ Dict].
Note that Dict] < 2 + and letting limm-+00 log(m)/m = 0,
lim m QeQiam
min
L. (Q enc(-)) < lim m m-
Eljencmia (s) log(2e + 1)]
1 [|nc(s)) (2f + 1)]
lim m=
(44)
42

---

where in (i), we replace lenCmin [x]] by |enc(s)|, which is the encoder we define in Appendix E. By definition the minimal encoder, men (s) S |enc(s) surely. Recall that the encoder enc(-) processes strings in sequential (left-to-right) manner. In particular, by a similar argument as Lemma A.4 we can show that under this encoder, the limit nz/ Ee De almost surely converges to we have that,
its expectation. More importantly, since, LtEDia
[t/m
lenc(s)
lim
E [t]l
m 700
m
converges to some limit almost surely. Therefore, from eq.
1 mm (Q enc(.)) S ess limsup m=+00
enc(s)
min lim
log(2e 1).
(45)
QEEi-gm Tn 10-000 772
m
where the essential lim-sup captures the almost sure limit 1/E ||] The almost sure conver- gence of |enc(s))/mm /mm also implies that we let the limit m go in any manner, and the limit will remain the same. In particular, consider process parameterized by i* for generating the source string, such that surely m 2 i' where the total number of characters, m, is a random variable. As i" + 0o, we will also have m + oc surely, and so the limit of |enc(s)l/m under this modified stochastic process should also converge the same limit.
Rather than sampling a string of a fixed length m from the source, consider the following sampling model: for i" - oc, sample i* geometric random variables Xi...., X,, iid. Geo(o) and construct the source string as the concatenation of i" strings alternating between successive 1's and successive O's or 2's (with the choice between the two made uniformly random), with the 1th string of length X; + 1. The overall number of characters sampled, m, is surely at least i".
Under this stochastic process, the size of the encoding of the string is upper bounded by,
eenc(s] S X1 + +1
Σ 1=2
(1
This bound follows from the fact that in any substring s' of successive 1s followed by substring s" of successive 0's or 2's, the encoder tokenizes the first max [e, |s'| 1} 1} length prefix of s' as token, and the remaining characters in s' into individual tokens except the last. Then, the last character of s' and the first max(f { 1, [s") characters of s" are assigned as token. The remainder s" is assigned as individual tokens. Each of s' or s" of length x, is allocated into at most 1 + (x + f)+ tokens.
For any Pr(X; 2 u) (1 (1-8)%, and therefore, summing over we get that E[(X,+1-()) -+++ (1-8)--1
With = 1 + 2 llg((//)) this expectation is upper bounded by 5. Therefore.
[[[enc(s)]]
|x] + E. 1=2 (1+ + 11-+1110) +1,+1-00++) 04)
lim
< lim 5 -c it
11+6
1 40000
More importantly, by the strong law of large numbers for a sum of independent random variables, (lX, + 1|+ +++ (1+ +1-+)+ and therefore |enc(s)l/i* is asymptotically almost surely upper bounded as,
lim (enc(s)
1 +
(46)
On the other hand, the number of characters generated, equals Σi (X; + 1), and satisfies, lim-- E[m]/i* = 1 + 8-1, By another application of the strong law of large numbers for sum of independent random variables.
lim +00
us. 1-8
(47)
By combining eqs.
46 and (47 we have that,
enc(())
1+8 8
lim m
+00000
1 5-I
43

---

Finally, combining with cross-entropy loss by,
45 and the ensuing discussion, we may upper bound the limiting
Lm (Q enc(-)) Σ log(2e 1) 1o 4log min lim QE 2 700 m
Note for this Markovian source, it is a short calculation to see that,
Hx En-n [++((+)>))] [[
å log( (2//vv//)))//// (1 6) log(1/11
Note that for any 8 < 1/2, numerical evaluation gives the inequality,
8 (3 + log(( (/))/)) 1.273
H
with the approximation factor improving as 5 becomes smaller. Therefore, this tokenizer achieves normalized cross-entropy loss which asymptotically scales 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 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 in the new string broken into chunks of length (save potentially the last chunk) and each chunk is assigned as a token in {1s 8 E S1} C Dict. If the length this substring of successive 1's is not 1, l 1, 26 1,..., in general, the next sequence, composed of O's or 2's is tokenized into individual characters.
mod every character in
Similar to eq.
42 to eq.
43 consider simplification of the overall cross-entropy loss,
min lim
Lm (Q encgre (-))
Qe m-
min
lim
-
1
E
log @ (JenCgre
lenCgre (s) Σ DiDi jenc
log Qink (t)
QeQi
m
2 min lim gi@inn m-0000
E
enc (s)
Σ
*EDiet QMLE(T) log Qua (t) Qmnnt)>0
where the last equation coder, limm-+000 lencain [*]]
the fact that by Lemma A.4 for the greedy QMLE(t). The minimizer of this objective subject to O0 Quok (t) S is (t) = QMLE(t) resulting in the inequality.
a.s.
1 L Cm (Q enogre 2 lim I (8)
min lim
(48)
QE gam 10-000 m
m +00 m
where we use the convention (og(1/0)) & limp- Plog log(1/P) =0 and therefore we may sum over tokens such that QMLE(t) for free.
Considering the same geometric sampling model in Appendix F.22 and Lemma A.4 we may study the almost sure limit QM lim nt/ (e)grr))))) by computing lim;--po Re/lenccre (s) under the geometric sampling model since the almost sure limit exists. Recall that the geometric sampling model, we generate the overall source string by concatenating i* strings of length X; 1, X₃. + where X; ~ Geo(o), with the strings alternating between successive I's and successive 0's 2's (with the choice between the two made by the flip of fair coin). For æ E (0. 1. 1, let (z) denote the event that X, is string composed only all x e's. The length of the greedy encoding of is lower bounded by,
|enCgre (s) 2 Σ X, 1(X1-1 #1 mod ())(E, (E) (2).
(49)
2m
44

---

Which captures for the fact that all 0's and 2's are encoded into singular tokens unless the previous string of I's was of length following a.a.s. lower bound is satisfied,
mod f. By the law of large numbers of the RHS of eq. (49). the
lim 5"-00
(+)
1 1
5(1 -0) 8)
(1
8(1 (1--) (1 8)8
1
(50)
26
25
28
x=0
where the last inequality uses the fact that = 1+2 log 1 /0)/5. Likewise, observe that, |enC (8) m surely, and following the analysis in Appendix F.2 of eq. (47) we have that,
enn (s)
lim
lim
1
(51)
For {0, 2), observe that the expected number of times the token observed the encoding of can be written as,
The ((X #1
mod ()) (()))))).
(52)
In particular, taking the expectation of eq.
52
Emna (0) E (1)) 2 8*
82
(1 + +-
1 Σ 8(1 - 8) gutt1 um0
2 4
4
5
(53)
Note that in any realization of the geometric sampling process, in eq. (52). 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 7t term the sum only depends on X; and X;-1, conditioned on whether the non-zero parities are even or odd, n, can be written as sum of /2 mutually independent terms. By the strong law of large numbers on each 53 implies that for x E (0,2).
of the conditional processes, eqs. (52) and
T2e u.S. 1- 82
lim
46
To upper bound Ng, note that it is upper bounded by the number of times the character appears in the source string, which by the strong law of large numbers a.a.s (after normalizing by i*), scales as 1/45. Finally, to bound QMle(t) which is the sequential nature of the encoder, using similar proof as Lemma A.4 we can show that n4/ Ee The converges to the unigram MLE model for this tokenizer. For the token x 2),2).
lim enc(()] QMIF(E) <
lim 000000 f2 + no
(54)
Using the a.a.s. upper and lower bounds on lenc(s)), no and na derived in eqs. 51 and 54). arrive at lower and upper bounds on QMLE(I) for E {0,2), 23.
1
(1-52) 48(1 6-11) I (MLE(x) S 2(1 82) 2
1
Since there are at least two tokens having probability bounded away from and by a constant under the MLE unigram model, the entropy of QMLE must also be lower bounded by constant. Indeed,
((QuLE) 2 2
min
(1g)))
It is easy to verify that for 8 0.5, the minimizer is achieved at 1-6 which leads to the lower bound,
I
1-6
4
H(QMLE) 2
log 1 - 8
2
45

---

Architecture
GPT-2
Batch size
Grid-searched in {8, 16,
Gradient acc. steps
Tokenizer dictionary size
{10, 20}
Tokenizer dataset size
10, 000
Optimizer
AdamW (31 = 0.9, A8 0.95)
Learning rate
0.002
Scheduler
Cosine
Iterations
8000
Weight decay
x 10
Dropout
0
Sequence length
512
Embedding dimension
Grid-searched in (10, 20, 30, 40)
layers
Crid-searched in (1, 4, 8}
heads
frid-searched in (1, 4, 8, 16}
Repetitions
Table 3: Hyperparameter choices
Finally, combining this lower bound H ((QLE)) with eq.
(8
have that,
eenc (s)
min
lim (m enc(-)) = lim E
H H(QMLE)
QE gan
1-0000
lenCgre (8)
8
4
lim (--+00
E
log
2
1
(8)
1 8
6
4
log
25(1 + 5-1)
2
1-
(1 5)2
H(T)
3(1 + 6)
where (i) follows from the lower bound on jenogre (s) in eq. 50 with the almost sure limit of m in
eq. 47 and noting that (encgre (s)l/m m $ surely. The last incquality follows by simplifying using
π 4, 1/2, and (T)) log(S).
Experiment details
Experiment (Figures 4a and 4b).
In this and previous experiments (Figures 2 3a and
3b),
train the transformers on a single GPU on an 8x A100 node. The wall-clock time measured does not count time spent in validation loss evaluations. The hyperparameter choices are listed in Table 31
Experiment 2 (Table I). We evaluate pre-trained tokenizers on various datasets. this experiment, do not evaluate the likelihood model test sequences, rather, we estimate the cross-entropy of the best unigram model by using the approximation,
Σ log (MLE(() Di
Σ 7u log DeDi
(55)
where (())
Σ, nee is the MLE unigram model learnt from finite dataset, which we choose here as GLUE (Wagg et al. 2019), and 7 the number of times the token is observed in encoding of the dataset. This approximation allows us separate the emor stemming from learning suboptimal likelihood model which tends have higher sample complexity requirements and focus on the asymptotic error of the tokenizer.
46

---

We use Monte-carle sampling to approximate the cross entssyy loss estimator in eq. (55). These approximations tends underestimate the cross-entropy loss due the concavity ( close to O. In general, the gap between the approximation and the true error is expected to grow with k. Therefore, the true difference between the estimate the best unigram model on a tokenizer and the best l-gram model for k 2 2 on the character level tokenizer is likely to be larger than the reported figures.
Experiment 3 (Figure dictionary sizes (5000, 6000, S000, 12000, 20000, 32000, 50000, 80000). The cross-entropy loss incurred by the best 1 1-gram model is estimated using eq. (55) while for k-gram models for A 2 2, use Monte-carlo sampling to estimate the cross-entropy 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 æ-axis. While this is not true measure of the number of parameters in the underlying k-gram model, this proxy for the same.
We train the LZW, BPE, Unigram and Wordpiece tokenizers with
47

---

G NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The paper lists empirical phenomenon (justified in Fig. 2) and theoretical contributions justified in Theorems 3.1, 3.3 and 3.5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Remark 3.3
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
48

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification: Assumption 3.2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The code has been released along with the rest of the submission.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how reproduce that algorithm.
49

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (c.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
Instructions provided in the jupyter notebook.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
gablic/guides
pondeSuumisssionolliss for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: T
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
50

---

Answer: [Yes]
Justification:
All plots which allow for it, contain standard error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix F contains this information.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
No NeurIPS code of ethics were violated.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
51

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is primarily theoretical study on the behavior of tokenization on toy problems (learning Markov chains). The societal impact of this research is not likely to be significant.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: No models with high risk for misuse were trained or released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Code has been properly credited, via citing the relevant paper.
Guidelines:
52

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets released.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer:
[NA]
Justification:
No crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing research with human subjects.
53

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
54


Reviews:
[{"review_id": "RrekiZEVk3", "reviewer": "Reviewer_88v6", "summary": "This paper investigates the learning dynamics of unigram language models on top of tokenised vs non-tokenised data, comparing these models’ expected cross-entropy to the distribution’s entropy. The paper performs this analysis while considering different data generating distributions (mainly focusing on relatively simple markov chains), and different tokenisation methods.", "questions": "My current score is mostly based on my current understand that this paper overclaims its results. I'm open to increasing my score if the authors either tone down the paper contributions' rhetoric, or make a convincing argument of why the current framing is appropriate.\n\n> we study the end-to-end cross-entropy loss achieved by transformers with and without tokenization\n\nI’d argue this paper does not actually study a transformer’s cross-entropy with and without tokenization, but a unigram model’s instead. Even if transformers learn unigram distributions early on (and in some tasks are never able to learn more than that), this is still a strong over-statement in my opinion.\n\n> 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).\n\n\nThis phenomenon was previously shown by Chang et al., 2022; 2023.\n\n> Line 115. Q(t1, t2, · · · , tj ) = Q#(j) Qji=1 Qtok(ti)\n\nWhat does Q_{#}(j) represent?\n\n> Figure 2a\n\nWhat happens if models are trained for more iterations?\n\n> Figure 3\n\nI found this figure confusing. I don’t fully understand what is being presented here.\n\n#### `References`\n\n* Chang et al., 2022. Word Acquisition in Neural Language Models\n* Chang et al., 2023. Characterizing Learning Curves During Language Model Pre-Training: Learning, Forgetting, and Stability", "limitations": "I think some important limitations are not sufficiently discussed in this paper. The most important of which is that the analysis focuses on unigram statistics, and transformers can clearly learn more than that. Expanding the limitations pointed out by Remark 3.3 in a dedicated limitations section could also be useful.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper tackles an interesting and timely topic: how tokenisation enables language modeling. \n\nThis paper provides an interesting theoretical analysis of the effect of tokenisation on unigram language modeling.\n\nThis paper also provides a couple of empirical analyses of how unigram models perform on real data.\n\nThe paper is relatively easy to follow, even though some of the mathematical results could be spelled out a bit more clearly to make it easier for a reader to follow them.", "weaknesses": "This paper’s framing, in my opinion, significantly over-claims its results:\n* The title “Toward a Theory of Tokenization in LLMs” is very broad for the current contributions. A more appropriate title, in my opinion, would be “Analysing tokenisation’s effect on unigram distributions”, or something analogous to it. There is no “theory of tokenisation” being proposed here, but a theoretical analysis of how tokenisation affects a simple model’s cross-entropy.\n* The abstract and introduction also significantly overclaim results, with statements such as “we study the end-to-end cross-entropy loss achieved by transformers with and without tokenization” while focusing on unigram cross-entropies. Transformers may serve as motivation to this work (as they initially learn unigram statistics), but are not in fact analysed here.\n\nI think the paper would also be significantly more straightforward to read if the framing was fixed and it was clear from the start that the paper's analyses would focus on unigram models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive criticism. (*references cited in the common rebuttal*)\n\n**TLDR;** We are happy to see how to change the wording of the title + general rhetoric of the paper in a way which fit the contributions in the paper best. *Our proposed changes incorporating the reviewers’ points are discussed in the common rebuttal*. In doing so, we would like to add a few points to take into consideration,\n\n1. **The tokenization objective studied in the paper (end-to-end cross-entropy loss), while seemingly obvious in hindsight, has not been the subject of any theoretical work on tokenization**.\n    \n    There are several current theoretical formulations for tokenization. One viewpoint is the ability to compress the input sequence as well as possible [5],[6],[7]. Related work such as [4] considers tokenization as approximately optimizing some natural objective of the training dataset. There are two conceptual issues with these formulations,\n\n    +  These approaches study how tokenizers behave on the sequences they were trained on, which does not capture generalization.\n\n    +  These analyses look at tokenizers in isolation, rather than studying them in the context of how the end-to-end loss of the model changes.\n    \n   The current theoretical discussion around tokenization is problematic for this reason: it is straightforward to compare tokenizer A with tokenizer B by evaluating them in practice, but there is no existing theoretical formulation which allows comparing different tokenizers with each other (say, by studying their behavior against the same loss/objective). For instance, the notion of “minimum number of merges” in [4] only makes sense for merging based tokenizers, and not for tokenizers like Unigram which don’t operate by merging tokens. The end-to-end cross-entropy loss is arguably the most natural objective which can allow comparisons between the behavior of the end-to-end model.\n    \n2. **Why do we not write the results as “an analysis of unigram models with tokenization”? Do transformers even learn unigram models?**\n\n   Section 2.1 and 3 of the paper are dedicated to understanding the behavior learnt by transformers when exposed to data generated from Markov processes. Prior work argues that transformers (without tokenization), when trained for many iterations, are indeed able to learn $k$-th order Markov data. In the context of these results it’s worth taking into account the fact that these models need to be trained for $10-50 \\times$ the number of iterations to break past the unigram phase and learn even bigram models. See Fig. 1 of the reference [1] or Fig. 1a in the rebuttal pdf. In the presence of tokenization, Fig. 3 in our paper discusses the distributions learned in the presence of tokenization, which are observed to be close to a unigram model (see clarification in the common rebuttal).\n\n3. **What happens when transformers don’t learn unigram models?**\n\n   This is a good question, and something that our work addresses from a theoretical point of view, but in a way that can be made more explicit (see proposed changes above). With sufficiently large dictionaries, the transformer only has to learn a unigram model. What happens when the dictionaries are not this large? The main implication from the theorems in our paper is that *tokenization always reduces the value of $n$ for which the transformer needs to learn $n$-gram behavior, so as to achieve near-optimal test loss*. Our current theorems instantiate this result when the dictionaries are large enough so it suffices to learn unigram behavior to perform well. When the dictionary sizes are smaller, transformers with tokenization are forced to learn $n$ -gram behavior for $n > 1$ to achieve low test loss. Our results argues that tokenization allows the model to get away with learning $n$-gram behavior for values of $n \\ll k$, the true order of the underlying data distribution. With tokenization, transformers can avoid learning higher-order $n$-grams, which would have otherwise been learnt in its absence.\n\n4. **What happens when transformers don’t learn $n$-gram models at all?**\n\n   $n$-gram models, while simple, do not capture the extent of the modeling power of transformers. Going beyond this requires looking at more complicated data generating processes. There are several ways to do so: the simplest extension compared to our work would be one where the transformer is trained on data generated from a mixture of many different Markov models. No single $n$-gram model captures the data well now, and it is interesting to see how transformers learn to identify what order the test data comes from and utilize the appropriate estimator. Even beyond Markov and mixture of Markov models, we may study these questions when data come from simple HMMs, where the role of tokenization may be very different.\n\n   We hope that our work initiates a study of tokenization when transformers are trained on even richer classes of data processes. We analyze the end-to-end loss by looking at the family of models $\\mathcal{F}$ transformers empirically appear to represent and prove upper/lower bounds on the cross-entropy of models in $\\mathcal{F}$. Ultimately, this framework can be applied to any data process, and provides a new lens for comparing tokenizers.\n\n___\n\n### **Additional questions/clarifications**\n\n1. **What is $Q_{\\\\#} (j)$ in the unigram definition?** This is the distribution over the total number of tokens $j$. This needs to be present as otherwise the distribution over token sequences does not integrate to $1$ (i.e., is not a valid probability distribution).\n2. **What happens when models are trained for longer in Fig. 2a:** When models are trained for more iterations, they eventually learn $k$-gram behavior. However, the number of iterations required is $10-50 \\times$ more (see Fig. 1 in [1] or Fig. 1a in the rebuttal pdf)\n3. **Figure 3 clarification:** Discussed in the common rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3BtP2wkdy2", "reviewer": "Reviewer_veC3", "summary": "This paper offers theoretical insights into the importance of tokenization in language models. Tokenization is ostensibly the artifact that makes training LMs not an end-to-end procedure. This design choice introduces biases, as it is not optimized for exactly the same criterion as the full model. Yet training without a tokenization step almost always leads to worse language models. This paper attempts to provide reasons based in probability theory for this phenomenon. The authors first explore a toy setting, in which transformer models are tasked with predicting distributions from kth order Markov processes. They offer a theoretical explanation for why the error of models is capped at that of a unigram model and how tokenization alleviates this issue. They then show that tokenization schemes with certain properties can achieve the optimal cross-entropy loss. The work offers some basic experimental results confirming their insights.", "questions": "* In the kth-order Markov processes studied, are nth state distributions dependent only on the n-kth state? I may be misunderstanding the caption in figure 1\n* The results are applicable to all language models, not just large ones. If anything, they are arguably more relevant for smaller language models. Perhaps consider changing the title\n* How does the work differ from/build on Edelman et. al. 2024 and Makkuva et. al. 2024?", "limitations": "Limitations are not discussed in depth. The authors should address their limited experimental setting and the applicability of the results to linguistic distributions (which are not evidently k-order Markovian)", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "* Tokenization is a core part NLP pipelines yet it still needs to be better understood from a theoretical perspective. The questions that this paper tries to answer are very relevant for both model interpretability and further development\n* The theory is presented in an understandable manner and results for specific popular tokenization schemes are provided.", "weaknesses": "* The theory presented in this work is for a specific type of data-generating distribution (kth order Markov) and we can’t directly extrapolate these results to linguistic distributions, which do not necessarily follow such a distribution. There is minimal discussion about the relationship between kth order Markov and linguistic distributions, which leaves the reader questioning how relevant these results actually are.\n* Ultimately, the results are limited; they essentially show an expected result (the existence of an optimal unigram language model as the dictionary size grows to infinity). While some intuition can be gained from these results, the theoretical implications are limited.\n* There is minimal discussion of the empirical results and what conclusions can be drawn from them. Given how much of the theory is not directly applicable to real language modeling settings, it feels like such a discussion should be very important", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. Below we address the main questions and weaknesses pointed out. *(references cited in the common rebuttal)*\n\n### **[W1] How well do $k$-th order Markov processes extrapolate to linguistic distributions?**\n\nThere are two points to mention here,\n\n1. $k$-th order Markov processes, while not perfect, capture many elements of linguisitic distributions - when $k$ grows larger, these models capture longer-range dependencies with the past. This class of models have had a rich history in language modeling and nearly every book on language modeling studies these processes. These models have been the study of many recent works, since they present a rich test-bed of interesting phenomena. A few recent works which have appeared in the literature since submission which study the interplay of transformers with these kinds of distributions are [8],[9].\n2. This data-model, while simple, captures the ability of transformers to learn $n$-gram behavior. $n$-gram features appear prominently in many domains such as NMT [10], language modeling [11] and speech/music [12] to name a few.\n\n### **[W2] Results show an expected result (asymptotically optimal unigram model)**\n\nThe existence of an optimal unigram model as the dictionary size grows to infinity is not the main contribution of the paper. It is easy to show that there exists “some” tokenizer which satisfies this property. In this regard, two main contributions of our paper are,\n\n1. From a theoretical point of view, we show that the LZW tokenizer in fact lies on the pareto frontier of test-loss vs. dictionary size, when the likelihood model is a unigram model. To a lesser extent, this is approximately true for the BPE tokenizer as well. This means that the tokenizer not only asymptotically works, but non-asymptotically, the size of the dictionary cannot be reduced significantly without hurting the test-loss.\n2. The tokenizer which assigns all $r$-length tokens also satisfies the property that asymptotically there exists an optimal unigram model on it. However, this is an unnatural tokenizer. We show that the above properties are true for BPE and LZW: letting the number of tokens grow to $\\infty$, it is a-priori not at all obvious that on the learnt dictionaries there exists a unigram model which achieves optimal test loss.\nIn contrast, it is easy to come up with seemingly “natural” tokenizers but no unigram model trained on these tokenizers can asymptotically achieve the optimal test loss. In the response to [Q1] of Reviewer zrKY, we provide a surprising example of such a tokenizer.\n\n### **[W3] Discussion of empirical results**\n\nHere is a quick summary of the empirical results in the paper, and takeaways.\n\n1. **Fig. 2 and Fig. 4:** Transformers need to be exposed to much more data to learn $k$-th order Markov models without tokenization, compared to with tokenization. Likewise, they learn more quickly wrt wall-clock time compared to in the absence of tokenization (This is true even if we select the fastest untokenized model).\n**Takeaway:** Transformers generalize better with tokenization, both in terms of number of samples as well as number of optimization iterations.\n2. **Fig. 3 conclusion:** Transformers approximately learn unigram models when trained on tokenized sequences generated from a Markov model.\n**Takeaway:** Transformers can achieve low loss by learning conceptually simple models when tokenization is present.\n3. **Fig. 5 conclusion:** BPE, Unigram and Wordpiece tokenizers perform similarly on Wikitext-103 with unigram models. The decay of the loss as a function of the dictionary size appears to be captured by $\\propto 1/\\log(|\\textsf{Dict}|)$, as predicted theoretically (Theorem 3.1).\n**Takeaway:** Scaling law for tokenization (as a function of the dictionary size).\n\nIn this paper, we sought to build up a theoretical understanding of how tokenizers and transformers interact by studying their behavior on $k$-th order Markov chains. While these models are not perfect, a number of interesting empirical phenomenon can be inferred which concur with practice, even through the lens of these simple data models. More importantly, the questions and workflow considered in this paper (analyzing end-to-end loss on models learned by transformers) can be employed with more complex data processes, where transformers exhibit richer behavior. Separations between tokenizers may become more apparent here.\n\n___\n\n### **[Q1] $k$-th order processes considered**\n\nIn the $k$-th order processes studied, the $n$-th state distribution only depends on the $(n-k)$-th state. However, our theory applies for all $k$-th order processes (as long as Assumption 3.2 is satisfied). In our experiments, we chose to compare against this restricted class of models to level the playing field between different values of $k$ (since the problem certainly becomes harder if we consider all Markov chains for increasing $k$). In the attached pdf, we plot the behavior of tokenizers on randomly chosen $k$-th order Markov processes for $k=1,2,3,4$. The gap between the tokenized and untokenized grows even more significantly as $k$ increases.\n\n### **[Q3] Comparison with Edelman et al (2024) and Makkuva et al (2024)**\n\nThese works show that transformers (in the absence of tokenization), when exposed to sufficiently much data, learn to represent $k$-th order Markov chains in-context for relatively small values of $k$. In practice, however, tokenization is almost always used. In our paper, we study the questions asked in these papers when transformers are trained with tokenization. Our key observations is that with tokenization, the model learns significantly more quickly, and is able to avoid going through multiple phases of learning when trained with tokenization. The general rhetoric surrounding tokenization has been negative, and our work shows that tokenization can make a big difference, even when learning simple models like $k$-th order Markov chains.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZGbzbf0GLn", "reviewer": "Reviewer_zrKY", "summary": "The authors show that tokenization is a fundamental property of transformer-based models, in the sense that without it, it is hard (if not impossible) to achieve low cross-entropy loss on next-word prediction. They show that tokenization helps breaking the unigram barrier (i.e., the best loss a unigram model can achieve) and give a theoretical characterization of the information tokenizers provide in terms of statistics on token distribution.\n\nIn particular:\n\nSection 2.1 shows how models without tokenization cannot achieve the optimal cross-entropy loss, while when equipped with a tokenizer they break the unigram barrier.\n\nSection 3 studies tokenizers that assign all possible substrings (up to length r) as tokens in the dictionary and shows their theoretical optimality in learning processes ruled by k-Markov chains. A consequence is that unigram models can also do that, in the limit.\n\nOf course, this comes at the expense of the model's efficiency and potential attacks that one can run on an exponential number of tokens (i.e., the surface attack grows very large).\n\nFinally, the authors show that tokenizers can trade off the vocabulary size while maintaining low cross-entropy (i.e., they can behave like an optimal model).\n\nFinally, they extend the theoretical framework to LZW tokenizers.\n\nExperiments are conducted on tokenized vs. non-tokenized models on {k=1}-Markov models and then on some real datasets to show that tokenizers trade-off complexity and efficiency in learning an optimal representation of the characters (and their frequency) in the training distribution.", "questions": "You say that Transformers without tokenization fail at modelling simple k-order Markov models, while with BPE (and other techniques), they succeed. I would say that is simply because BPE injects statistical information in the data and splits it accordingly. BPE is \"trained\" to aggregate \"bytes\" according to their frequency in the training data, so it somehow informs a model with the stationary distribution of most-frequent contiguous characters.\nAm I missing any non-trivial observation here?\n\nThere is a reference in the Appendix to the model used (GPT-2), but nothing on the main paper. For example, I asked myself multiple times what models you used for the tokenized and non-tokenized networks.\n\nBy unigram models, do you mean those where the probability of each token approximates the inverse frequency of a character/token in the training data?\n\nIf I understand correctly, in Fig. 2 (a), models without tokenization fail at breaking the unigram barrier (so the best they can do is model the inverse character frequency). How does that connect to the relative success of character-level tokenization? There are plenty of methods that use character-level tokenization, and they probably work much better than unigrams. Is there anything I am missing here?\n\nIn Figure 2 you mention that plot (2b) has 70x less parameters, but you do not specify why (Is it to prove tokenization helps?).\nDo you use GPT-2, as mentioned in the Appendix? If so, do you use a smaller model for the figure on the left and a larger one for the one on the right?\n\nFig. 3 is hard to understand. I read it many times, but I still do not fully understand what it conveys. The heatmap goes from 0. to ~0.6, though it is unclear what the measure is (I guess it is the probability?).", "limitations": "Please see previous sections.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The article studies an important problem, and I think there is value in the paper.\nTo the best of my knowledge, comparing BPE to non-tokenized models is new, and the figures give some interesting insights (e.g., Figure 2).\nYour paper contains much theoretical work, contributing to its quality.\nThe results in the limit for unigram and BPE/LZW models are noticeable (Section 3 and Eq. 2).\n\nIn general, the results seem solid and are also interesting for linguists and NLP researchers. BPE and other tokenization methods find a trade-off between unigram models, as per Eq. 2, and the complexity of the resulting vocabulary (and model).", "weaknesses": "One of the main weaknesses of this work is how it is presented. \nMaybe it's me, but I found it quite hard to read. See questions.\n\nAnother concern is how theoretical results apply to real-world datasets. See questions, but Fig. 5 seems to mitigate the impact of your theoretical results.\nIn fact, for the vocabulary that grows larger, all the models have a similar value of cross entropy (for around ~50K tokens).\n\nThe article seems rushed, as there are many typos (I just listed some).\n- Line 150 “the a”\n- Line 173, “it make since” --> “sense”\n- Line 175, eq. and many others --> Eq. (it’s not wrong per-se, but you capitalize Fig, Example, etc.)\n- The Notation paragraph shouldn’t go with related works but should be in the next section.\n- Notation in 2 is a bit sloppy (this is a personal suggestion): you can use D() and E() for the decoder/encoder (and enclose them with \\mathcal).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. Below we address the weaknesses/questions pointed out:\n\n### **[W1] Fig. 5 mitigates the impact of the theory**\n\nOn datasets like Wikitext-103, transformers trained with these tokenizers (BPE, Unigram, Wordpiece) indeed perform similarly in ablations. The purpose of this figure was to observe that the test-loss appears to decay as roughly $\\propto 1/\\log(|\\text{Dict}|)$ agreeing with our theory (Theorem 3.1). When we generalize beyond these settings to more complex languages and more specific downstream tasks, the differences start becoming noticeable. There are many possible reasons and counterfactuals to control for in these kinds of experiments. For instance, Wordpiece appears to be worse compared to Unigram and BPE in languages which are not space-delimited like Japanese [3]. Unfortunately, these questions are at a granularity which can't be addressed by studying Markovian data models. We believe that the extensions of our work to more specific losses / different data-distributions can play a role, and help in revealing fine-grained differences between tokenizers. \n\n___\n\n### **[Q1] BPE succeeds because of aggregating data according to frequencies**\n\nThere are plenty of seemingly “reasonable” ways in which a tokenizer may aggregate data according to their frequencies while constructing the dictionary, but which ultimately end up performing poorly. Consider the following modification of the Wordpiece tokenizer where we merge the pair of tokens which maximize $n_{t_1, t_2} / n_{t_1}^2$ (the original Wordpiece prescribes merging the maximizer of $n_{t_1,t_2} / n_{t_1} n_{t_2}$). While this tokenizer indeed seems reasonable per the above definition, it turns out that it performs quite poorly. Training on randomly generated letters from the english alphabet, the results are tabulated in Table 1 of the attached pdf.\n\nNotice the clear a pattern in how modified Wordpiece behaves: it appears to merge the longest token in the dictionary thus far with a single character in each round. While the tokenizer “objective” itself does not prescribe this behavior, the tokenizer exhibits this trend because of the $n_{t_1}^2$ term in the denominator. This incentivizes the merge to pick a starting token ($t_1$) which has very low frequency (because of the $1/n_1^2$ term in the denominator).\n\nThus the behavior of tokenization / design of appropriate merge rules is a nuanced phenomenon. While there appear to be natural choices under which the intuition “tokenizer is trained to aggregate bytes according to their frequencies $\\implies$learning unigram models are sufficient” is true, there are also cases where this intuition fails altogether.\n\nOn a separate note, it is not apparent how to design tokenizers which learn dictionaries with the *minimal number of tokens* required to achieve low loss (under unigram likelihood models). Our proofs show this is true for LZW and approximately so for a variant of BPE. Thus, these tokenizers are hard to improve on significantly (without breaking some sort of worst-case information theoretic barrier). Having a small dictionary is important for being able to learn the transformer in a data-efficient manner, and to avoid redundant tokens, which presents an attack surface.\n\n### **[Q2] Model used in the experiments; Clarification of Fig. 2**\n\nIn the paper, we used variants of the GPT-2 architecture as implemented in [13]. We shall add this citation to the paper. Our experiments considered variations over (i) the number of heads, (ii) the number of layers, and (iii) the embedding dimension and (iv) the dictionary size (excluding optimization hyperparameters). We shall include these in the description of figures. They are summarized in the Appendix (Table 3) due to a lack of space in the main paper.\n\n**Fig 2 clarification:** Fig. 2b uses $70 \\times$ fewer parameters compared to 2a. This is an argument supporting that models with tokenization do not require as many parameters to quickly achieve the optimal test-loss. This is a less important point at the scale of models we considered, which is why we do not go into too much detail, but this also translates to an improvement in wall-clock time (cf. Fig. 4 in the paper)\n\n### **[Q3] What are unigram models?**\n\nUnigram models are defined on lines 114-116 in the paper.  The specific model mentioned (probability of each token approximates the inverse frequency of character/token) lies in the class of unigram models we consider.\n\n### **[Q4] Success of transformers beyond the unigram barrier?**\n\nOur reason for studying unigram models is not because this class of models are interesting in their own right (which one can argue for), but more so because we see that transformers empirically learn these kinds of models when trained on Markov data. This is the role of Fig. 3 (clarified in the common rebuttal). However, when the data processes grow to be more complicated than Markov models, we expect transformers to exhibit more complex behavior (beyond $n$-grams). Understanding the behavior of transformers with and without tokenization on more complex data processes is a rich direction for future work.\n\nOn a separate note, character-level tokenization does appear to work to varying degrees in practice with transformers, and this is likely because real world data is a mixture of many different data types. For certain languages (such as those containing non-concatenative morphology), removing tokenization seems to help [14]. For arithmetic, character level tokenization is known to help models generalize better [2]. But from these results, it is not clear whether these are pitfalls of existing tokenizers, or of tokenization as a whole. On arithmetic, for instance, recent models like GPT4 and LLama3 appear to chunk numbers into the range 0-999 and split longer numbers into these chunks, instead of operating at the single digit/byte level, which is in support of the argument, “Good tokenizer $\\ge$ no tokenizer”.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xUCY5vH5zP", "reviewer": "Reviewer_RvTD", "summary": "This paper presents a study on tokenization by investigating the behavior of transformers on simple data generating processes . It shows that, in the absence of any tokenization, transformers trained on $k$th-order Markov processes predict characters according to a unigram model, which is quite problematic given how poor unigram models are at modeling Markovian data. Paradoxically, they observe that, even the simplest unigram model learnt by transformers *with the appropriate tokenization* is able to model the probability of sequences sampled from a $k$th-order Markov process.", "questions": "Please see the Weaknesses section above", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written, with empirical observation intermingled with theory, which I quite liked. The theory is also accompanied by a lot if intuition, insight and interpretation, which really helps drive the point home.", "weaknesses": "- In section 3.2, the authors chose to focus on developing guarantees for a newly developed tokenizer, which, to my knowledge, is seldom used. It would've been maybe of greater use to the community to also, or instead, establish these guarantees for the more commonly-used tokenizers, such as BPE.\n\n- I appreciate that this is mostly a theoretical study of tokenizers, and while the observations put forward are valuable, I found myself wondering what practical takeaways this paper presents to improve current tokenizers. That is something I would love the authors to comment on.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and questions. Below we addressed the key points mentioned.\n\n### **[W1] Analysis for commonly-used tokenizers such as BPE**\n\nThe guarantees in section 3.2 study guarantees for the LZW tokenizer, which is arguably not used much in practice. However, in Section B of the Appendix (Additional Theoretical Results I: A sequential variant of BPE) we study a variant of BPE which is analytically tractable, and present a result similar to Theorem 3.1 for this tokenizer (cf. Theorem B.2). The discussion of this result in the main paper was deferred to a short excerpt in Section 4.1 due to a lack of space, but in the subsequent version of the paper, we shall include a longer discussion. This was indeed our motivation to analyze (a tractable variant of) BPE as well - it remains one of the most commonly employed tokenizers in practice across a number of domains.\n\n### **[W2] Practical takeaways**\n\nWe point the reviewer to the response to [W3] of Reviewer veC3 where we have summarized the key empirical takeways of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## **Common rebuttal**

We thank all the reviewers for taking the time to go through our paper and suggest constructive criticism. Please find attached a pdf containing additional plots to aid in answering reviewers' questions. We begin with the suggested changes to the paper, and then address some common points raised by the reviewers.

### **Suggested changes to the paper**

1. We propose to change the title of the paper to:  “An Analysis of Tokenization: Transformers under Markov Data”
2. We will adjust the abstract + introduction of the paper to emphasize that we look at the class of models, $\mathcal{F}$, transformers are observed to express empirically, and then theoretically study the joint cross-entropy loss of natural tokenizers with models in $\mathcal{F}$. In the case of $k$-th order Markov data, the model class expressed by transformers, $\mathcal{F}$, appears to be the class of $n$-gram models. This is the case both with, and without tokenization (cf. Fig. 3 in the paper). We will also point out previous work studying this and related behavior such as Chang et al (2022, 2023). 
3. We will adjust the description and discussion surrounding Fig. 3 to be more clear, and emphasize that the goal of this figure is to understand what is the behavior expressed by transformers trained on Markov data in the presence of tokenization. A clarification of this figure is provided below.
4. Since our theoretical discussion revolves around $n$-gram models trained with tokenization, we will make the discussion connecting $n$-gram models with transformers more clear. Currently this is spread across sections 2 and 3 of the paper.
5. We shall expand Remark 3.3 into a limitations section, in addition to some other limitations (such as: transformers can learn more than just $n$-gram behavior).
6. A discussion extending the current results to the case where transformers with tokenization learn $n$-gram behavior for $n \ge 2$ instead of just unigram models. This occurs when tokenizers are trained with very small dictionaries.

We are open to including other changes to the paper the reviewers see fit, in a way which better matches the contributions in the paper and makes it easier to read. 

___

Below we address some common points raised by multiple reviewers.

### **Clarification of Fig. 3**

**Fig. 3 plots the next-token distributions learnt by the transformer** (dictionary size $=20$, sequence length $=500$) **at convergence**.

In this experiment, we sample a random sequence of length $2000$ from a Markov chain and feed it into the transformer (after tokenization, this results in a sequence of length $\approx 500$). We plot the next-token distribution predicted by the transformer at every single of the $500$ positions, generated by masking the input sequence. This plot stitches together $500$ next-token distributions together, each of which is a narrow column heatmap. Visually it appears that the transformer predicts symbols according to the same distribution most of the time (i.e., the plot looks approximately homogeneous along the $x$-axis). This is evidence that even though the transformer could learn behavior which depended on all the previous symbols, it sticks to outputting tokens independently most of the time, i.e., a unigram model.

From this point of view, the tables have turned - it is surprising that the transformer with tokenization performs so well even though it only learns unigram behavior, when this behavior is the root of problems in the absence of tokenization. Our work tries to formally address why this might be the case.

___

### **Summary**

We initiate the analytical study of the end-to-end loss of transformers with tokenization by looking at the class of models transformers appear to learn empirically, and then studying how the behavior changes with the addition of tokenization. We instantiate this framework for the case of Markov data generating processes, where transformers learn simple $n$-gram behavior, as observed in Chang et al. (2022,2023) in the context of real-world data and other more recent works (Makkuva et al). However, this framework itself can be instantiated with any kind of data process. Choosing more complex data processes will trade-off analytical tractability with the ability of transformers to express more complex behavior.

___

### **References**

[1] Edelman, Benjamin L., et al. "The evolution of statistical induction heads: In-context learning markov chains." arXiv:2402.11004.

[2] Golkar, Siavash, et al. "xVal: A continuous number encoding for large language models" arXiv:2310.02989

[3] Fujii, Takuro, et al. "How do different tokenizers perform on downstream tasks in scriptio continua languages?: A case study in Japanese." arXiv:2306.09572

[4] Zouhar, Vilém, et al. "A formal perspective on byte-pair encoding." arXiv:2306.16837

[5] Zouhar, Vilém, et al. "Tokenization and the noiseless channel." arXiv:2306.16842

[6] Gallé, Matthias. "Investigating the effectiveness of BPE: The power of shorter sequences." EMNLP-IJCNLP (2019)

[7] Goldman, Omer, et al. "Unpacking Tokenization: Evaluating Text Compression and its Correlation with Model Performance." arXiv preprint arXiv:2403.06265

[8] Svete, A., & Cotterell, R. "Transformers Can Represent $n$-gram Language Models" arXiv:2404.14994

[9] Nguyen, T. "Understanding Transformers via N-gram Statistics" arXiv:2407.12034

[10] Diao, Shizhe, et al. "Taming pre-trained language models with n-gram representations for low-resource domain adaptation" ACL 2021

[11] Irie, Kazuki, et al. "Language modeling with deep transformers" arXiv:1905.04226

[12] Tian, Jinhao, et al. "N-gram Unsupervised Compoundation and Feature Injection for Better Symbolic Music Understanding" AAAI 2024

[13] Pagliardini, M. GPT-2 modular codebase implementation. https://github.com/epfml/llm-baselines

[14] Clark, Jonathan H., et al. "Canine: Pre-training an efficient tokenization-free encoder for language representation" TACL (2022)

Meta-review: This is an interesting paper on studying tokenization in LLMs under some assumptions on the underling data distribution (i.e. kth order markov processes). All reviewers support accepting the paper (contingent on the authors changing the title of the paper) and I think it will be valuable contribution to the community..
Decision: Accept (spotlight)