An Analysis of Tokenization: Transformers under Markov Data

Authors: nived  rajaraman
jiantao  jiao
kannan  ramchandran
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:25:32

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.

Main paper: 
 introduction: 
 The training of language models is typically not an end-to-end process. Language models are often composed of a "tokenizer", which encodes a sequence of characters into a sequence of token ids, which map to substrings. The subsequent language modeling task is carried out by a neural network or transformer, which is pre-trained and fine-tuned on large datasets. The ideal goal is to jointly train the tokenizer and transformer with end-to-end accuracy as the objective. This is a challenging problem to solve efficiently, and thus, the tokenizer is generally adapted on a portion of the training dataset and frozen before the transformer is trained. In practice, byte-level/character level models such as 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 (Libovickỳ et al., 2021; Itzhak and Levy, 2021) .Though used most commonly, tokenization at the subword level often has sharp edges. Test sequences may contain rare tokens which were never seen in the training dataset. The presence of such tokens may induce undesirable behavior in the outputs of models (Rumbelow and Watkins, 2023; Kharitonov et al., 2021; Yu et al., 2021) and present an attack surface for bad actors. Moreover, tokenized models struggle on tasks that involve manipulation at the character level, such as spelling out words or reversing sentences. For similar reasons, LLMs with standard tokenizers also struggle to carry out basic arithmetic (Golkar et al., 2023) . Despite this brittleness, tokenization is used in nearly all state-of-the-art LLM architectures.In this paper, we introduce a statistical formulation for tokenization for next-word-prediction. We study the class of models transformers are observed to express empirically under simple data generating processes, which often can have simpler descriptions. Taking a step back, rather than focusing on proxy evaluation metrics, which lead to an ever-changing goalpost, we focus on understanding the behavior of the end-to-end cross-entropy loss, L(•). In this paper, we study a simplification of real world data generating processes and study the case where data sources are k th -order Markov processes. Within this framework we can compare tokenizers against each other, and in the process capture several interesting phenomena. Our main results are as follows, 1. There are very simple k th -order Markov processes such that in the absence of any tokenization, transformers trained on 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 et al. (2024) .2. When trained with tokenization, transformers are empirically observed to break through this barrier and are able to capture the probability of sequences under the Markov distribution near-optimally. In other words, in the presence of tokenization, transformers appear to achieve near-optimal cross-entropy loss. This phenomenon is observed with a multitude of tokenizers used commonly in practice.3. We analyze a toy tokenizer which adds all length-k sequences into the dictionary and show that as dictionary size grows, unigram models trained on the tokens get better at modeling the probabilities of sequences drawn from Markov sources. We then theoretically prove that tokenizers used in practice, such as the LZW tokenizer (Zouhar et al., 2023a) and a variant of the BPE tokenizer (Gage, 1994; Sennrich et al., 2016) which are learnt from data also satisfy this property but require much smaller dictionaries to achieve any target cross-entropy loss.In our framework, the most challenging hurdle and the biggest departure from previous work such as (Zouhar et al., 2023b) is the element of generalization -understanding how a tokenizer performs on new sequences that it was not trained on. This generalization turns out to be a delicate phenomenonwe 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-entropy loss) to new sequences under one encoding algorithm, but completely fail to generalize under another.Tokenization has a long history of empirical study in natural language processing. In the literature, a number of tokenizers have been developed for various domains such as math (Singh and Strouse, 2024), code (Zheng et al., 2023; Parr, 2013) and morphology-aware tokenizers for different languages like Japanese (Tolmachev et al., 2018; Den et al., 2007) and Arabic (Alyafeai et al., 2023) among many others. In modern LLMs, the most commonly used tokenizers are variants of BPE (Gage, 1994) , Wordpiece (Schuster and Nakajima, 2012) and the Unigram tokenizer (Kudo, 2018) which learn a dictionary from data, rather than hard-coding language dependent rules. There has been a long line of work interpreting tokenization from various lenses (Grefenstette and Tapanainen, 1994; Palmer, 2000; Zouhar et al., 2023b) .The theoretical study of transformers has also received much attention recently. We discuss the closest relatives to our work below. Edelman et al. (2024) study the learning trajectory of transformers trained on data drawn from 1 st -order Markov chains. While the authors empirically observe that the models eventually learn to predict tokens correctly according to the Markov kernel, simplicity bias slows down 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-context causal learning task that generalizes learning in-context bigrams for 1 st -order Markov processes and analyze the trajectory of gradient descent. The above state diagram describes the distribution of X n conditioned on X n-1 . k th -order extension: the conditional probability of X n only depends on X n-k through the kernel, Pr(X n = 1|X n-k = 0) = p and Pr(X n = 0|X n-k = 1) = q.Notation. All logarithms are base e, unless specified otherwise. The Shannon entropy H(X) of a categorical random variable X is -x∈supp(X) p(x) log p(x). H BER (p) captures the entropy of a Bernoulli random variable with parameter p. The notation O p,q,r (f (n)) (likewise Ω {•} and Θ {•} ) indicate that the underlying constant depends polynomially on the parameters p, q and r and O(f (n)) (likewise, Θ and Ω) ignores polylog(n) terms. For a set S, S ⋆ = ∪ ∞ k=1 S k , the set of all sequences with elements drawn from S. For a sequence t, t i:j = (t i , t i+1 , • • • , t j ) returns a slice. 
formulation: 
 We consider a setting where the learner's objective is to learn a language model which models probabilities of sequences over an input alphabet A. The data to be modeled is generated according to an unknown probability model P : A ⋆ → [0, 1] over strings. A tokenizer is a tuple T = (Dict, enc(•), dec(•)). Here Dict is a collection of tokens The encoding function enc(•) : A ⋆ → Dict ⋆ , maps strings of characters to a sequence of tokens, and likewise, the decoding function dec(•) : Dict ⋆ → A ⋆ maps a sequence of tokens to a string of characters. We assume that the tokenizer is "consistent", namely, dec(enc(•)) is the identity function.We consider a setting where the learner has access to a training dataset which is a sequence of length n sampled from a data source1 . We study the likelihood maximization problem, where the objective of the learner is to learn an end to end model such that the cross-entropy loss is minimized. In the presence of tokenization, we have a model of the form Q end = Q • 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 log-perplexity, can be written down as,EQUATIONwith 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 Q denote a family of joint distributions over tokens (i.e. likelihood models). The objective is to jointly design a tokenizer (with encoding function enc(•)) and likelihood model Q ∈ Q with small test loss L m (Q • enc(•)).Finally, for a dictionary Dict, the unigram family of models, Q 1-gram , is defined as below:Q ∈ Q 1-gram associates probability Q(t 1 , t 2 , • • • , t j ) = Q # (j) j i=1 Q tok (t i )to the sequence of tokens t 1 , • • • , t j for measures Q # and Q tok supported on N and Dict respectively.In this paper, we consider a simplification of real-world data generating processes by considering the case where the data generating distribution is a k th -order Markov process over characters. Studying the behavior of transformers trained on Markov data was the subject of the works Makkuva et al. (2024) and Edelman et al. (2024) , where a number of interesting phenomena were unearthed. When a transformer is trained on data from certain simple Markov processes like the one considered in Figure 1 , 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 3a this is made clearer -the transformer fails to improve its test loss beyond that of the best unigram model. How bad can a unigram model be? It turns out that the gap between the cross-entropy of the best unigram model and that of the optimal model can be characterized precisely. Theorem 2.1. Consider any ergodic data source with stationary distribution over characters π. The unconstrained optimal likelihood model achieves cross-entropy loss, min Q L m (Q) = H(P ). In contrast, the cross-entropy loss under any unigram modelQ ∈ Q 1-gram satisfies, L m (Q) ≥ mH(π).The ratio of the optimal loss H(P ), and the optimal unigram loss, mH(π) can be arbitrarily large. In particular, for the switching chain in Figure 1 , as p, q → 0, the ratio diverges to ∞.While transformers are a powerful class of models, it is concerning that they fail to learn very simple distributions such as k th -order 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 3a operate on raw character sequences drawn from the stochastic source. To understand the role of tokenization, we run another experiment and train the transformer on 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 we 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 a 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: we sample a random sequence of length 2000 from a Markov chain and feed it into the transformer after tokenization, resulting in ≈ 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 is a narrow column heatmap. Visually, we 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 a unigram model. Thus, we come to a surprising conclusion: the behavior of the transformer on the k th -order switching source in Figure 1 with and without tokenization is essentially the same. In both cases, the model learns a unigram model over the tokens -in the absence of tokenization this unigram model is in fact the stationary distribution induced by the source. If the transformer learns a unigram model in both cases, how come there is such a large gap in performance between the two? To understand this in more detail, we analyze a toy tokenizer. As a simplification, we will analyze the behavior of an arbitrary, but exact unigram model under this tokenizer. 
unigram models under tokenization: 
 Let's consider a toy tokenizer which assigns all possible substrings of length r as tokens in the dictionary and study what happens when a unigram model is trained on the tokenized sequences. The In the presence of tokenization, the test loss of the model approaches the optimal bound (dashed line). It is worth noting that the models trained here are significantly smaller than those considered in Figure 3a , having up to 70× 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 r . A sequence of characters is mapped to a sequence of tokens by simply chunking it into a sequences of r characters which are replaced by the corresponding token index2 . The resulting stochastic process on the tokens is still Markovian, but over a state space of size 2 r . For any unigram model Q on the tokens, the cross-entropy loss can be written down as,L m (Q • enc(•)) = E t∈enc(s) log(1/Q tok (t)) + Θ(log(m)),where we choose Q # = Unif([m]), which contributes an additive log(m) to the loss. Choosing Q tok (t) = π(t 1 ) r-1 i=1 P (t i+1 |t i ) as the stationary probability the Markov process associates with t,EQUATIONthe approximation in (i) uses the fact that as m grows large, 1 m m/k i=0 log(P (s ki+ℓ+1 |s ki+ℓ ) approaches H(P ) k . With d = 2 (i.e., r = 1), we recover the performance of the character tokenizer in Theorem 2.1. An immediate implication of this simple calculation is that as m → ∞, there is a unigram model which is nearly optimal as the dictionary size grows to ∞.While this toy tokenizer allows us to glean this intuition behind why tokenization allows unigram models to be near-optimal, there are some obvious issues. One, the tokenizer does not adapt to the distribution of the data. Indeed, for the switching Markov source in Figure 1 , as p = q = δ → 0, the source contains increasingly longer sequences of contiguous 0's and 1's. In this case, it makes since to have a dictionary containing such sequences, rather than all possible length-r sequences, many of which would be seen very few times (if at all) in a test sequence. At a more technical level, in eq. ( 2), to get to a cross-entropy loss of 2H(P ), the size of the dictionary required by the toy tokenizer is e mH(π)/H(P ) . As discussed in Example A.1 for the switching Markov process with p = q = δ, this dictionary size can be extremely large and scales exponentially (in 1/δ) as e 1/δ log(1/δ) when δ is small. In general, on stochastic sources on a much larger alphabet, such as English/ASCII, this toy tokenizer would result in a prohibitively large dictionary. Larger dictionaries are usually correlated with the presence of rare tokens which appear infrequently at training time. This presents a problem in practice -a lot more data is often required to see enough examples of such tokens to learn good embeddings for them. More importantly, in the absence of this volume of data, rare tokens present an attack surface to elicit undesirable behavior in the model (Rumbelow and Watkins, 2023) . In practice, this issue present with the toy tokenizer is, to an extent, resolved by using tokenization algorithms such as BPE or Wordpiece, which learn dictionaries from data. In the process, they are able to avoid learning extremely rare tokens, by enforcing a lower bound on the number of their occurrences in the training data to be allocated as a token. By minimizing the number of such rare tokens, the model is able to utilize its token budget in a more efficient manner.We now introduce the main theoretical result of this paper, showing that with the appropriate tokenization algorithm with a token budget of d, a unigram model is not only asymptotically able to achieve the optimal cross-entropy loss, but also requires far smaller dictionaries to match the performance of the toy tokenizer considered earlier. In order to avoid dealing with the transient characteristics of the source, we consider the cross-entropy loss in eq. ( 1) under the assumption that the test sequences s are of length m → ∞. Namely, define the normalized loss, L(•) = lim m→∞ 1 m L m (•)EQUATIONwhere ε is log(1/δ)/0.99 log(d)3 . Furthermore, a tokenizer satisfying eq. (3) with probability≥ 1 -d -Ω δ (log(d)) can be learnt from a dataset of O δ (d) characters.The tokenizers considered in this theorem are far more efficient with their token budget than the toy tokenizer -to achieve a cross entropy loss within a factor 2 of optimal, the dictionary size required by these tokenizer is d ≈ 1/δ 2 on any source satisfying Assumption 3.2. In comparison, the toy tokenizer requires a dictionary size of e 1/δ log(1/δ) 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 on a dataset of size O(d). Likewise, we also show that a sequential variant of BPE achieves the upper bound in eq. ( 3) up to a factor of 2 and with a worse dependency in ε when trained on a dataset of size O(d 2 ). What is interesting is that neither of these algorithms explicitly learn a unigram likelihood model, Q, while constructing the dictionary. Yet they are able to perform as well as the tokenizers which are jointly optimized with a likelihood model, such as the Unigram tokenizer (Kudo, 2018) .Key insight. While the toy tokenizer provides a high level intuition as to why tokenization might enable unigram models to model Markov sources well, here we present a different explanation which captures tokenization from an operational viewpoint. Tokenizers which do a good job at learning patterns in the data and assigning these frequent patterns as tokens in the dictionary are compatible with an i.i.d. model over tokens. A hypothetical example motivating this point: consider a tokenizer such that the distribution of tokens in the encoding of a fresh string sampled from the source is distributed i.i.d., except that whenever the token t ′ appears, it is always followed by t ′′ . An i.i.d. model on the tokens is a poor approximation since P (t ′ t ′′ ) ≫ P (t ′ )P (t ′′ ). However, by merging t ′ and t ′′ into a new token t and adding this to the dictionary, the new distribution over tokens is i.i.d. In general, this motivates why it is desirable for a tokenizer to allocate new tokens to substrings which appear next to each other frequently, i.e. a pattern in the data. As more tokens are added to the dictionary, one might expect the cross-entropy loss incurred by the best unigram model to improve.The main result of this section is a generic reduction: dictionaries which typically encode new strings into a few long tokens (defined in a formal sense in Theorem 3.4), result in tokenizers achieving near-optimal cross-entropy loss. We prove this result for Markovian sources under a regularity assumption, which is that the associated connectivity graph of the chain is complete. The analogous assumption for k th -order sources is that the transition kernel is entry-wise bounded away from 0.This assumption is satisfied by all the sources considered in the paper thus far, such as the k th -order switching processes in Figure 1 . Assumption 3.2 (Data generating process). Assume that the data source is an ergodic Markov process with transition P (•|•) and stationary distribution π. Assume that min a,a ′ ∈A P (a ′ |a) ≜ δ > 0.Remark 3.3. Assumption 3.2 (and its k th -order extension) impose that there is a small but nonzero 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 a way which interpolates between i.i.d. (δ = 1/|A|) and highly non-i.i.d. (δ → 0).For a substring s and a character a, define P (s|a) = P (s 1 |a)|s| i=2 P (s i |s i-1) denote the conditional probability of the substring s. We now state the main result of this section. Theorem 3.4 (Bound on cross-entropy loss of dictionaries under greedy encoder). Consider a source satisfying Assumption 3.2 and any tokenizer T equipped with the greedy encoder, enc gre (•) with finitely long tokens. Define, P (t) = E a∼π [P (t|a)] and supposeH(Q MLE , P ) ≥ 1 ε log(1/δ) for some ε < 1. Then, min Q∈Q1-gram L(Q • enc gre (•)) ≤ min Q L(Q) 1 -ε . Interpretation. H(Q MLE , P ) = E t∼QMLE [log(1/P (t))] is large when the encoder places higher mass (i.e. larger values of Q MLE (•)) 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.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 (LZW tokenizer). Iterating from left to right, the shortest prefix of the training dataset which does not already exist as a token is assigned as the next token in the dictionary. This substring is removed and the process is iterated on the remainder of the dataset. The tokenizer uses the greedy encoding algorithm (Definition A.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 as a token in the dictionary, then all of its prefixes must also belong to the dictionary. In the next theorem, we show that the LZW tokenizer approximately achieves the optimal cross-entropy loss. Theorem 3.6. Suppose the LZW tokenizer is trained on a dataset of length at most d (thereby learning a dictionary with at most d tokens). For Markov sources satisfying Assumption 3.2, with probability≥ 1 -d -O δ (log(d)), the resulting tokenizer satisfies,min Q∈Q1-gram L(Q • enc gre (•)) ≤ min Q L(Q) 1 -ε .where ε = log(1/δ) 0.99 log(d).The proof of this result considers all substrings t with P (t) ≥ 1/d 0.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 Figure 4 : Test loss vs. wall-clock time for the tokenized and untokenized models when trained on the order-1 switching Markov chain (Figure 1 ) with p = q = 0.8. The tokenizer used is BPE. which matches a token, every token allocated must fall on the "boundary" of this set, having P (t) ≤ O(1/d 0.99 ). By definition, this means that H(Q MLE , P ) = E t∼QMLE [log(1/P (t))] = 0.99 log(d).Combining this with Theorem 3.4 completes the proof. At a 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., 2001; Drmota and Szpankowski, 2011; Hun and Vallée, 2014; Drmota et al., 2021) . A detailed proof of Theorem 3.6 is provided in Appendix A.6. 
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 to 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 in terms of the number of parameters, the wall-clock time taken to optimize the model to any target test loss is observed to be smaller. Thus, tokenization appears to reduce the compute time required to train the model to a target test loss in the toy example we consider. In Figure 4b we compare models with the same architecture trained with and without tokenization5 . 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-v1 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, we plot the number of unique k-grams observed in the training dataset along the x-axis. While this is not an apples-to-apples comparison, we use the number of unique k-grams in the dataset as a proxy for the complexity of the likelihood model trained.One may also use the total number of possible k-grams as a proxy; however a large fraction of these k-grams would likely never be observed in a real dataset (especially as k grows).Experiment 2 (Table 1 ). In this experiment, we compare the cross entropy loss of the best unigram model trained on pre-trained tokenizers on an array of datasets. All the considered tokenizers have dictionary sizes in the range 31K-51K. The best bigram model under the character tokenizer is consistently outperformed by the best unigram likelihood model trained under a number of pretrained tokenizers on a variety of datasets: Rotten Tomatoes (8.5K sequences), GLUE (105K), Yelp review (650K) and Wikitext-103-v1 (1.8M). We present some additional theoretical results in the appendix which we discuss briefly below. In Appendix B, 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 an interesting question for future research to understand whether this factor of 2 can be removed, since transformers are observed to achieve the near-optimal cross-entropy loss as the dictionary size grows (cf. Figure 3b ). In Appendix C, we prove 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 a 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 on data that it was not trained on. Prior work such as Zouhar et 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 a 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 a poorly studied subject in 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 k. 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. ( 2) shows that when the dictionary size scales as exp(mH(π)/H(P )), even in the absence of Assumption 3.2, the tokenizer achieves the optimal cross-entropy to within a factor of 2. This leads to the following conjecture.Conjecture 1. In the spirit of eliminating Assumption 3.2, is it possible to establish a version of Theorem 3.1 applicable to data drawn from any Markov chain, where ε = log(1/δ)/0.99 log(d) is replaced by ε = log(mH(π)/H(P ))/0.99 log(d).In Appendix B, we analyze a variant of the BPE tokenizer, which carries out a version of sample splitting, and establish a weaker variant of Theorem 3.1 for this tokenizer. This is to simplify the statistical dependencies arising from the fact that while learning its dictionary, BPE makes a run over the entire training dataset each time a new token is added.It remains an open question to analyze and establish a variant of Theorem 3.1 for the standard BPE tokenizer. 
conclusion: 
 We present a theoretical framework to compare and analyze different tokenization algorithms. We study the end-to-end cross-entropy loss of the tokenizer + likelihood model, and focus on the case where the data generating process is Markovian. We empirically observe that transformers with tokenization are drastically more efficient at learning k th -order Markov processes, compared to without tokenization. We prove that algorithms such as LZW and a sequential variant of BPE learn tokenizers such that the best unigram likelihood model trained on them approaches the cross-entropy loss of the optimal likelihood model, as the vocabulary size d grows. For each character a ∈ A let T ⋆ a denote an infinite tree, with root vertex ∅, and subsequent vertices labelled by strings t ∈ A ⋆ . The edge from a parent vertex t to any child ta ′ is labelled with the probability P (ta ′ |t) unless t = ∅, in which case the edge probability is P (a ′ |a). An infinite trajectory sampled on the tree T ⋆ a corresponds to an infinite string sampled from the stochastic source conditioned on the first character of the string being a. In this paper we only consider ergodic sources (Gray and Gray, 2009) for which we can define the "entropy rate". The entropy rate fundamentally captures the compressibility of the source, and can be defined as H ∞ ≜ lim m→∞ 1 m H(P ) where s is a length m string drawn from the source. By Theorem 2.1, H ∞ , captures min Q L(Q). 
 
 Appendix: The ratio of H(P ) and mH(π) can be made arbitrarily large for the switching Markov chains in Figure 1 as the switching probabilities p and q approach 0 or 1. See Example A.1 for more details. Example A.1. Consider the switching Markov process in Figure 1 on {0, 1} with p = q = 1δ. For this process, lim m→∞We first characterize the minimum achievable cross-entropy loss L m (Q) without any restrictions on the likelihood model class Q. Choosing Q(enc(s)) = Q(s) = P (s), the true probability of the sequence s, we have L m (Q • enc(•)) = H(s) where H(•) is the entropy function. It is not that difficult to see that this is also the minimum cross-entropy loss that can be achieved. For any distribution Q,L m (Q) = E[log(1/Q(s)] = E[log(P (s)/Q(s)] + E[log(1/P (s))] = H(P ) + D KL (P ∥Q).On the other hand, the cross-entropy loss under any unigram modelQ ∈ Q 1-gram satisfies, 1 m L m (Q • enc(•)) (i) = - 1 m m i=1 E[log Q tok (t i )] - 1 m E[log Q # (m)] (ii) ≥ - a∈A π(a) log Q tok (a) ≥ H(π)where in (i), 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(X, Y ) ≥ H(X).A number of our results (Theorems 3.4 and 3.6 to name a few) are related to bounding min Q∈Q1-gram L(Q • enc(•)) for some tokenizer T . In this section we introduce the maximum likelihood unigram model which captures the optimizer over Q for any given tokenizer.For the character level tokenizer, an examination of Theorem 2.1 shows that the optimal unigram likelihood model associates probability Q tok (a) = π(a), i.e. the limiting fraction of times the character a is observed in the sequence. More generally, for a non-trivial tokenizer, the corresponding optimal unigram model Q ⋆ tok (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,EQUATIONto each token, where n t is the random variable capturing the number of occurrences of the token t in the encoding of the length-m string s. Restricting the class of likelihood models to the unigram models, Q 1-gram , Q MLE captures the model which minimizes eq. ( 1).The unigram MLE model cannot be computed without an infinite amount of data, but can be approximated well with a finite amount of data, which forms the basis for Theorem C.1. For certain encoding algorithms, we can show that the quantity n t / t n t asymptotically converges to its expectation (Lemma A.4). This is the reason the unigram model in eq. ( 4) is referred to as a "maximum likelihood" model, since lim m→∞ n t / t n t is the limit as |s| = m → ∞ of the solution to the following likelihood maximization problem: given a sequence s, find the distribution over tokens, Q, which maximizest∈enc(s) Q(t) ≡ t∈Dict Q(t) nt .As discussed previously, the unigram MLE model over tokens in eq. ( 4) induces a joint distribution over sequences of tokens by looking at the product of the marginal probabilities of the composed tokens; in particular,Q MLE (t 1 , • • • , t j ) = Q MLE (j) j i=1 Q MLE (t i ),where Q MLE (j) is a 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 a 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 a dictionary Dict, the greedy encoder enc gre (s) encodes a string s into tokens by greedily matching from left to right, the largest substring that exists as a token in Dict. This substring is then removed and the process iterated on the remainder of s. The greedy decoder dec gre (•) is a lookup table -a sequence of tokens is decoded by replacing each occurrence of a token by the corresponding substring it maps to in Dict.Lemma A.4. lim m→∞ nt t ′ n t ′ a.s.= lim m→∞ E nt t ′ n t ′ for any tokenizer having a finite vocabulary and finitely long tokens, using the greedy encoder.Proof. This result is essentially true because under the greedy encoder, the tokens in an encoding of a fresh string t may be generated by an r th -order Markov process for some r. For such processes, the Cesàro average of the state distributions converges to a stationary distribution of the process (i.e., the Krylov-Bogolyubov argument).Tokens are generated as follows. Suppose the previous tokens generated were t 1 , t 2 , • • • , t i . The next token t i+1 is sampled by drawing an infinite trajectory from T ⋆ a for a ∼ P (•|t i ) and returning the longest prefix t of this trajectory which is a token in Dict, conditional on satisfying the conditions,t j t j+1 • • • t i t ̸ ∈ Dict for all j ∈ {1, 2, • • • , i}.This process is repeated sequentially to generate all the tokens. Suppose the length of the longest token in the dictionary is ℓ max . Then, the distribution from a which a token is sampled depends on at most the previous ℓ max tokens. The reason for this is that the dependency of the (i + 1) th token, t i+1 , on the previously sampled tokens emerges in the constraintt j t j+1 • • • t i t i+1 ̸ ∈ Dict, satisfied by any candidate t i+1 . Since each token is of length at least one, this condition is vacuously satisfied if j < i -ℓ max .With this view, the evolution of the state, defined as state r = (t rℓmax , t rℓmax-1 , • • • , t (r-1)ℓmax ) evolves in a Markovian fashion. By the Krylov-Bogolyubov argument (cf. Proposition 4.2 in Chen ( 2018)), the time averaged visitation frequencies of a Markov chain coordinate-wise asymptotically converges to its expectation, almost surely. This expectation exists by Theorems 8.5 and 8.22 of Eisner et al. (2015) which shows that for a matrix A such that sup t∈N ∥A t ∥ op < ∞ the limit lim t→∞ 1 t t i=1 A i exists. For the finite-state Markov transition A which captures the token generation process, condition sup t∈N ∥A t ∥ op ≤ |Dict| ℓmax < ∞. This means that the limit of the time averaged state distribution exists. Moreover, for any initial distribution π 0 over tokens, π = lim t→∞ 1 t t i=1 π 0 A i satisfies the condition πA = π, implying that the limiting time-averaged state distribution is a stationary distribution of A. Since the limiting time-averaged measure on the state state r = (t rℓmax , • • • , t rℓmax-1 , • • • , t (r-1)ℓmax ) exists, this implies that the limiting timeaveraged measure of t rℓmax-r ′ for each r ′ ∈ {0, 1, • • • , ℓ max } exists. By taking the uniform average over r ′ and r, the limiting time-averaged measure of t i over i ∈ N exists. m also happens to be the entropy rate of the source. We use this property to bound the length of the greedy encoding, |enc gre (s)|. Indeed, the probability of s may be decomposed as,P (s) = P (t 1 ) |encgre(s)| i=2 P t i t i-1 ) ≤ |encgre(s)| i=1 max a∈A P t i a .Noting that δ min a P (t|a) ≥ max a P (t|a), up to a δ factor we may replace the max over a by an expectation over a ∼ π where π is the stationary distribution of the stochastic source. In particular,P (s) ≤ |encgre(s)| i=1 P (t i )/δ.By invoking the AEP, eq. ( 5), lim m→∞ 1 m |encgre(s)| i=1 -log P (t i )) -log(1/δ)m L m (Q • enc gre (•)) ≤ lim m→∞ 1 m L m (P π • enc gre (•))and therefore, it suffices to upper bound the RHS. In particular,EQUATIONwhere the last inequality uses the fact that P unif (|enc gre (s)|) = 1/m. Note that as m → ∞, by assumption on the tokenizer, the fraction of times the token t appears in the encoding of s converges almost surely converges to Q MLE (t). Since |enc gre (s)| ≤ m surely and P (t) > δ |t| > 0, by an application of the Dominated Convergence Theorem,EQUATIONCombining eq. ( 7) with eq. ( 8) and setting lim m→∞ log(m)/m = 0, and invoking eq. ( 6),min Q∈Q1-gram lim m→∞ 1 m L m (Q MLE • enc gre (•)) = lim m→∞ 1 m E |enc gre (s)|H(Q MLE , P ) ≤ H ∞ 1 -ε . (9) By Theorem 2.1, we have that min Q lim m→∞ 1 m L m (Q•enc gre (•)) = lim m→∞ H(P ) m = H ∞ ,which 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.6In this section we prove Theorem 3.6 and introduce the notion of a heavy-hitting dictionary. At a high level, these dictionaries contain all the substrings which have reasonably high probability of being observed many times in a dataset of size n = Ω δ (d). We first show in Lemma A.6 that heavy hitting dictionaries generalize well in the sense of having H(Q MLE , 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 LZW algorithm (Definition 3.5) results in a heavy hitting dictionary with high probability.Figure 6 : The circled nodes indicates substrings which are tokens in Dict. Red nodes indicate the set of "maximal tokens", which are the set of tokens which the greedy encoder assigns, leaving out those which can only be assigned as the last token of some string. Tokens like "b" are never assigned by the greedy encoder (save as the last token of the encoding of a string) since any sufficiently long trajectory starting with b must have a longer prefix which is also a token, namely, one of ba, bc, bba, bbb or bbc. The vertices of the tree which are assigned by the greedy encoder as tokens (together with all their prefixes) forms a cut of the tree, which marks the dotted red line. The heavy hitting property asserts that this cut is uniformly far away from the root node ∅, and that every vertex s marked red has P (s) ≤ 1/d β .Definition A.5 (β-heavy-hitting dictionary). A token t of a dictionary is said to be maximal if there exists an arbitrary substring containing t as a strict prefix, and in addition, t is also the largest prefix of the substring which is a token. A dictionary Dict is said to be β-heavy hitting if the set of maximal tokens is a subset of {s ′ : max a∈A P (s ′ |a) ≤ 1/d β }.A pictorial depiction of the heavy hitting property is illustrated in Figure 6 . Lemma A.6. For a β-heavy-hitting dictionary, with the greedy encoder, H(Q MLE , P ) ≥ β log(d).Proof. Note that the greedy encoder assigns tokens only among the set of maximal substrings (save for potentially the last token). If every maximal substring has max a∈A P (s|a) ≤ 1/d β , by the heavy-hitting property, for any token t,P (t) ≤ max a∈A P (s ′ |a) ≤ 1/d β . Therefore, H(Q MLE , P ) = E t∼QMLE [log(1/P (t))] ≥ β log(d).Define M β = {t : max a∈A P (t|a) ≥ δ/d β }. These are the set of "high-probability" substrings under the stochastic source. We will show that for β bounded away from 1, with high probability, every substring in M β is added as a token to the dictionary in a run of the LZW tokenizer (Definition 3.5). Note that if every substring in M β is assigned as a token by LZW, then the algorithm must be β-heavy hitting since there always exists a maximal token on the "boundary" of the set M β which is strictly contained in {s ′ : max a∈A P (s ′ |a) ≤ 1/d β }.Lemma A.7. Every substring in M β has length at most ℓ ⋆ ≜ δ -1 (β log(d) + log(1/δ)).Proof. Note that min a,a ′ ∈A P (a|a ′ ) = δ, which implies that the probability of any transition must be bounded away from 1, i.e., max a,a ′ ∈A P (a|a ′ ) ≤ 1δ. This implies that,EQUATIONBy definition, for any substring t ∈ M β , max a∈A P (t|a) ≥ δ/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 to add new tokens once the budget is hit), instead, we assume that the algorithm runs on a prefix of the dataset of length d. The number of tokens added this way cannot exceed d. Lemma A.8. With probability ≥ 1d -Ω(log(d/δ)/δ) , in a run of the LZW algorithm, no substring t added as a token to the dictionary satisfies |t| ≥ ℓ max ≜ 4 log(d|A|)/δ.Proof. Consider any s ∈ N and any substring t of length s. In order for t to be assigned as a token, each of its prefixes must disjointly appear at least once in the string. Since there are at most d tokens, we can upper bound the probability that t is assigned as a token as,P (t is assigned as a token) ≤ d s s i=1 max a∈A P (t 1:i |a) (i) ≤ d s (1 -δ) s(s-1)/2≤ e s log(d)-δs(s-1)/2 , where (i) uses the fact that max a∈A P (t 1:i ) ≤ i j=1 max a∈A P (t j |a) ≤ (1δ) i . By union bounding across the |A| s strings of length s, P (any length s string is assigned as a token) ≤ e s log(|A|)+s log(d)-δs(s-1)/2 . When s = 4 log(d|A|)/δ + 1 ≜ ℓ max + 1, the RHS is upper bounded by e -δℓ 2 max /4 ≤ d -Ω(log(d/δ)/δ) . With the same small probability, no substring of length s ′ > s can become a token, since their length-s prefixes are never assigned as tokens.Corollary A.9. With probability ≥ 1d -Ω δ (log(d)) , learns a dictionary with at least d ⋆ = d/ℓ max 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 β < 1, with probability ≥ 1d -Ω(log(d/δ)/δ)exp(-Ω δ (d 1-β )) over the source dataset, every substring in M β is added as a token to the dictionary in a run of the LZW algorithm. In other words, with the same probability, the LZW tokenizer results in a β-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 a 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 at 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 a portion of the dataset.Next we consider a joint view for generating the dataset from the stochastic source and the dictionary learnt by LZW simultaneously. The stochastic source is sampled as a sequence of tokens. Suppose the last character of the previous token was a ′ . Sample a character a ∼ P (•|a ′ ) and an infinite trajectory on the tree T ⋆ a . Consider the first node visited in this trajectory which does not already exist as a token in the dictionary. The substring corresponding to this node is added as a token in the dictionary. By repeating this process, the dictionary and the source dataset are constructed sequentially and simultaneously. As alluded to before, we truncate this token sampling process to repeat at most d ⋆ times, which results in a subset of the dictionary output by the LZW algorithm with high probability (Corollary A.9). This is simply a variant of the "Poissonization" trick to avoid statistical dependencies across tokens. Denote the set of infinite trajectories generated on the forest {T ⋆ a : a ∈ A} as {traj i : i ∈ [d ⋆ ]}. With this view of the sampling process, observe that if the substring t sampled was a prefix of traj i at least |t| times across different values of i, then t must be assigned as a token. In particular, in each of these |t| trajectories, each of the prefixes of t is assigned as a 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,P (t is not assigned as a token) ≤ |t|-1 i=0 d ⋆ i max a∈A (P (t|a)) i (1 -P (t|a)) d ⋆ -i .Since we aim to upper bound this probability across the substrings in t ∈ M β , note that (i) max a∈A P (t|a) ≥ δ/d β , and (ii) tokens in M β have length at most ℓ ⋆ = δ -1 (β log(d) + log(1/δ)) (Lemma A.7), implying there are at most 2|A| ℓ⋆ substrings in this set. By union bounding,EQUATIONEQUATIONwhere the last inequality uses the fact that ℓ ⋆ = O β,δ (log(d)).Case II. For i ≤ ℓ ⋆ and δ/d β ≤ x ≤ 1/2,EQUATIONwhere the last inequality uses the fact thatℓ ⋆ = O(log(d)), x ≥ δ/d β , d ⋆ = Ω(dδ/ log(d/δ)). By combining eq. ( 12) and eq. ( 13) with eq. ( 11) completes the proof, as long as β is a constant bounded away from 1.Lemma A.11. Fix a constant γ > 0. Then, with probability ≥ 1d -Ω γ,δ (log(d)) , none of the substrings in the set N γ = s ′ : max a∈A P (s ′ |a) ≤ δ/d 1+γ are assigned as tokens in a run of LZW.Proof. Define the following set of substrings,S γ = t : δ/d 1+γ/2 ≤ max a∈A P (t|a) ≤ 1/d 1+γ/2Since the width of this band is sufficiently large, by Assumption 3.2 every substring t such that max a∈A P (t|a) ≤ δ/d 1+γ/2 has at least one prefix which falls in S γ , and denote the longest such prefix t γ . Define T γ = {t γ : t ∈ N γ } as the set of longest prefixes in S γ . Intuitively, if we think of the strings in S γ (or T γ ) as being intermediate in length, the strings in N γ can be thought of as being particularly long: the value of max a∈A P (t|a) for any t ∈ T γ and for any t ∈ N γ are separated by a factor of at least 1/d γ/2 . In particular, since the probability of any character is lower bounded by δ, each substring in t ∈ N γ must be at least ∆ = γ log(d) 2 log(1/δ) symbols longer than its corresponding longest prefix in T γ , t γ . An implication of this is that for t to be assigned as a token, t γ must be observed at least ∆ + 1 times disjointly in s. 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 d 1+γ/2 /δ substrings, which allows the probability of this event occurring simultaneously across all substrings in T γ to be controlled by union bound. Under this condition, none of the substrings in N γ are made into tokens.In order to argue that the dictionary does not contain certain tokens, we may argue this property about any superset of the dictionary. In contrast, in Lemma A.10, we construct a subset of the dictionary by running LZW on the concatenation of d ⋆ tokens sampled from their joint distribution. The superset we consider here is just to sample d tokens from their joint distribution and concatenate them together to result in a string of length ≥ d, and running LZW on this sequence (which simply would result in these d tokens). As in Lemma A.10, let {traj i : 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 ∈ N γ is assigned as a token by LZW is to the event that every substring t ′ ∈ T γ is observed as a prefix of traj i for ∆ or fewer choices of i ∈EQUATIONwhere (i) uses the fact that max a∈A P (t ′ |a) ≤ 1/d 1+γ/2 since the substring t ′ belongs to T γ .Note that the number of substrings in S γ (and by extension, T γ ) is at most O δ (d 1+γ/2 ). Recall that these substrings satisfy the condition max a∈A P (t|a) ≥ δ/d 1+γ/2 . Observe that,δ|S γ | d 1+γ/2 ≤ t∈Sγ max a∈A P (t|a) ≤ t∈Sγ a∈A P (t|a) ≤ |A| ≤ 1 δ .This implies that there are at most d 1+γ/2 /δ 2 substrings in S γ . Finally, in conjunction with eq. ( 14),P (∃ t ′ ∈ S γ : E(t ′ )) ≤ d 1+γ/2 δ 2 e -γ 2 ∆ log(d) = d -Ω γ,δ (log(d)) ,which implies that with high probability, no token in S γ is observed as a prefix of s i for more than ∆ choices of the index i ∈ [d]. Under this event, no substring in N γ is assigned as a token.A.6.1 Proof of Theorem 3.6Choosing β = 0.99 in Lemma A.10, with probability ≥ 1d -Ω δ (log(d)) , the LZW tokenizer results in a 0.99-heavy-hitting dictionary. As a consequence of Lemma A.6, this implies that under the same event,H(Q MLE , P ) ≥ 0.99 log(d).Finally, combining with Theorem 3.4 completes the proof.While the main results in 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 Byte-Pair-Encoding (BPE) algorithm (Gage, 1994; Sennrich et al., 2016) , discovered in the compression literature as REPAIR (Larsson and Moffat, 2000; Navarro and Russo, 2008) was proposed as a faster alternative to LZW. It remains as one of the most commonly implemented tokenizers in natural language processing for various downstream tasks (Radford et al., 2019; Mann et al., 2020; Touvron et al., 2023) . A large proportion of open source and commercial LLMs currently use BPE as the tokenization algorithm of choice, such as GPT-2/3, Llama 1/2 and Mistral-7B to name a few.The BPE algorithm is based on constructing the dictionary iteratively by merging pairs of tokens to result in a tokens. In each iteration, the pair of tokens which appear most frequently next to each other are merged together into a single token. Subsequently, every occurrence of the pair of tokens are replaced by the newly added token, breaking ties arbitrarily. The dictionary is thus an ordered mapping of the form t ← (t ′ , t ′′ ). To encode a new string, the BPE encoder iterates through the dictionary and for each rule t ← (t ′ , t ′′ ) replaces every consecutive occurrence of t ′ and t ′′ by the token t breaking ties arbitrarily.To warm up our main results, it is worth understanding the behavior of the BPE tokenizer in a bit more detail. Unlike the toy tokenizer, it is a priori unclear whether unigram models trained on sequences tokenized by BPE even asymptotically (in the dictionary size) achieve the optimal cross-entropy loss. Indeed, for δ > 0, consider a training sequence of length m of the form,EQUATIONThe probability that this sequence is generated by the order-2 switching Markov source with p = q = δ is,≈ (1 -δ) mδ 4 × 4 δ ×(1-δ) (δ) mδ 4 ×4 = e -H(P ) ,which uses the fact thatH(P ) = mδ log(1/δ) + m(1 -δ) log(1/(1 -δ)). 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/δ -1 is a power of 2 and denote r = log 2 (1/δ -1). The algorithm first merges 0 and 1 into a single token t 1 , which results in a long sequence of the formt 1 • • • • • • t 1 1t 1 • • • • • • t 1 0 repeated mδ/4 times. In subsequent rounds, the tokens (t 1 , t 1 ) is merged into t 2 , then (t 2 , t 2) is merged into t 3 and so on, until is no longer possible. Finally, the resulting sequence is a repeating sequence of 5 tokens where within each sequence, no pair of tokens appears more than once next to each other. Eventually these 5 tokens are merged into a single token labelled t r+4 , and in subsequent rounds the tokens (t r+4 , t r+4 ) are merged into t r+5 , (t r+5 , t r+5 ) is merged into t r+6 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 2 nd -order Markov source, with high probability these substrings disjointly occur Θ(m) times each. The learnt dictionary associates each such disjoint occurrence of these substrings with at least 1 token, for 0000, the 3 rd 0 must necessarily be tokenized as the token "0". Likewise, in 1111, the 3 rd 1 must necessarily be tokenized as the token "1". Therefore, when a new test string of length m is tokenized, with high probability the tokens "0" and "1" form a constant fraction of the total collection of tokens.Thus on freshly sampled test sequences, the BPE tokenizer appears to behave like the character-level tokenizer on a constant fraction of the input sequence. In particular, a simple calculation shows that the cross-entropy loss of any unigram model trained on this tokenizer must be far from the optimal Initial01 • • • • • • 0110 • • • • • • 10| • • • t 1 ← (0, 1) t 1 • • • • • • t 1 1t 1 • • • • • • t 1 0| • • • t 2 ← (t 1 , t 1 ) t 2 • • • t 2 1t 2 • • • t 2 0| • • • . . . . . . t r ← (t r-1 , t r-1 ) t r t 1 1t r 0| • • • t r+1 ← (t r , t 1 ) t r+1 1t r 0| • • • t r+2 ← (t r , 0) t r+1 1t r+2 | • • • t r+3 ← (t r+1 , 1) t r+3 t r+2 | • • • t r+4 ← (t r+3 , t r+2 ) t r+4 | • • • t r+5 ← (t r+4 , t r+4 ) t r+5 | • • • t r+6 ← (t r+5 , t r+5 ) t r+6 | • • • . . . . . . .Table 2 : A representation of the behavior of BPE when trained on the dataset in eq. ( 15). We assume that 1/δ -1 is a power of 2 and define r = log 2 (1/δ -1).bound of mH BER (δ) especially as δ becomes smaller,min Q∈Q1-gram L m (Q • enc(•)) ≥ min Q∈Q1-gram E n 0 log(1/Q tok (0) + n 1 log(1/Q tok (1) (i) ≥ Ω(m) • min Q∈Q1-gram log(1/P tok (0) + log(1/Q tok (1)≥ Ω(m).where (i) uses the fact that E[n 0 ], E[n 1 ] ∈ Ω(m) and the last inequality uses P tok (0)P tok (1) ≤ 1/4 (AM-GM inequality) since they sum up to at most 1. The purpose of this example is to show that there exist pathological training datasets which appear to be drawn from a stochastic source, but on which BPE fails to learn a good dictionary for the source. Thus proving a result such as Theorem 3.1 for BPE would require arguing that training datasets such as that in eq. ( 15) are unlikely to be seen.The analysis of the standard variant of BPE turns out to be complicated for other reasons too. After every token is added the training dataset becomes a mix of all the previously added tokens, and arguing about the statistics of which pair of tokens appears most frequently for the next iteration becomes involved. For instance, adding 00 as a token may reduce the frequency of occurrence of the substring 01, but will not affect 11. Thus, even though 01 may a priori have been seen more frequently, it may not be chosen by BPE as the next token after 00.To avoid dealing with these issues, we consider a sequential/sample-splitting variant of BPE. At a high level, the algorithm breaks down a dataset of size Θ(d 2 ) into d chunks and learns at most 1 token from each chunk. The algorithm iterates over the chunks and finding the pair of tokens which appear most frequently next to each other in each chunk and adding it to the dictionary if it appears more than log(d) times. Every consecutive occurrence of the pair of tokens is replaced by the newly assigned token in the dataset. Thus, in each iteration i, at most 1 token is added, depending on the statistics of the i th chunk and the tokens added so far to the dictionary. Based on the final size of the dictionary a different encoder/decoder pair is used -if the algorithm adds sufficiently many tokens to the dictionary, the greedy encoder is used, and if not, a parallel implementation of BPE's encoding algorithm is used (Definition B.1). A formal description of the algorithm is in Algorithm 1.Definition B.1 (BPE.split encoder). The BPE.split encoder parses a new string into tokens as follows.The algorithm partitions the string into contiguous chunks of length d. Then, BPE's encoder is applied on each chunk, which iterates through DS and replaces t ′ t ′′ by t for every rule t ← (t ′ , t ′′ ) in DS, breaking ties arbitrarily. The individual token sequences are finally spliced together and returned.The main result of this section is that up to a small additive error, Algorithm 1 approaches a 2approximation to the optimal cross-entropy loss. Replace every consecutive occurrence of (t ′ , t ′′ ) in text by t, breaking ties arbitrarily.Theorem B.2. For any ϵ ∈ (0, 1), run Algorithm 1 on a dataset of n = Θ(d 2 ) characters to learn a dictionary with at most d tokens. The resulting tokenizer T satisfies with probability ≥ 1e -Ω(dϵ 2 ) , minQ∈Q1-gram L(Q • enc(•)) ≤ (2 + ε) min Q L(Q) + ϵ where ε = O log(1/ϵ) log 3 (1/δ) ϵδ 9 log(d).While the guarantees established for the sequential BPE tokenizer are weaker than those in Theorem 3.1, the analysis turns out to be quite involved. Theorem B.2 implies that unigram models trained on the sequential BPE tokenizer asymptotically approach the optimal cross-entropy loss up to a factor of 2.The formal proof of this result is presented in Appendix B. What is the intuition behind using a different encoder in Algorithm 1 depending on the number of tokens in the dictionary? When the number of tokens in the dictionary is smaller than d 0 , we know that on a 1d 0 /d fraction of the iterations of Algorithm 1, a token is not added to the dictionary, i.e. every pair of tokens already appears at most log(d) times together. This is a datapoint of "evidence" that under the dictionary in that iteration, the BPE encoder is already good at encoding new strings (of length Θ(d)) in a way where pairs of tokens do not appear consecutively with high frequency. Since future dictionaries only have more rules appended to them, dictionaries only get better at encoding new strings into tokens where pairs do not frequently appear consecutively. In other words, the BPE encoder satisfies a monotonicity property. It remains to show that dictionaries which encode new sequences in a way where no pair of tokens appear too frequently have large H(Q MLE , P ) (to invoke Theorem 3.4). This follows from ideas introduced in (Navarro and Russo, 2008) .The case where the number of tokens is large (≥ d 0 ) turns out to present significant technical challenges for analyzing the BPE encoder. There is no longer much "evidence" that the dictionary in each iteration is good at encoding strings since in a large number of iterations a pair of tokens appear consecutively with high frequency. Analyzing the greedy encoder also presents its own challenges -although the algorithm has allocated a large number of tokens, it is possible that there are short tokens t which are maximal (i.e. they are not prefixes of other tokens). This is similar to the problem encountered by BPE when trained on the dataset in eq. ( 15) -although the algorithm has allocated a large number of tokens, the token 1 is maximal since every other token begins with the character 0.However, it turns out that such tokens, although present in the dictionary, are not observed frequently while encoding a fresh string drawn from the source.In this section we prove a rephrased version of Theorem B.2 which implies the statement in the main paper. Define d 0 = ϵd 2 log(4|A|) . Theorem B.3 (Rephrased Theorem B.2). Run Algorithm 1 on a dataset of n = Θ(d 2 ) characters to learn a dictionary with at most d tokens. The resulting tokenizer T satisfies one of the following 3 conditions, 1. Either, |Dict| > d 0 , and,min Q∈Q1-gram L(Q • enc(•)) ≤ H ∞ 1 -ε .Here, ε = O log 3 (1/δ) log(1/ϵ)ϵδ 9 log(d) . 2. Pr(|Dict| < d 0 ) = e -Ω(ϵ 2 d/ log 2 (1/δ)) , or, 3. Conditional on |Dict| < d 0 , with probability ≥ 1 -e -Ω(ϵ 2 d/ log 2 (1/δ)) , min Q∈Q1-gram L(Q • enc(•)) ≤ 1 - 2d 0 d 2H ∞ + O 1 log(d) + 2d 0 d log(4|A|).With the choice of d 0 = ϵd/2 log(4|A|) we get the statement of Theorem B.2.B.2 Analysis for the large dictionary case: |Dict| > d 0In the large dictionary case, Algorithm 1 uses the greedy encoder/decoder pair in conjunction with the dictionary. The proof of Theorem B.2 relies on establishing that the cross-entropy H(Q MLE , P ) of the tokenizer is large. Namely, we prove that, Lemma B.4. In Algorithm 1, assuming at least d 0 tokens are allocated,H(Q MLE , P ) = Ω ϵδ 9 log(d) log(1/ϵ) log 3 (1/δ) .To show this, it suffices to argue that conditioned on any previous set of tokens, with nontrivial probability over the underlying string generated from the stochastic source, the next token is long (i.e. having conditional probability at most O(1/ √ d)).Lemma B.5. Suppose that in a run of Algorithm 1, at least d 0 tokens are allocated. Suppose a set of tokens t 1 , • • • , t k have been sampled so far by the greedy encoder. Let T i+1 be the random variable which denotes the next token returned by the greedy encoder, where the randomness comes from the underlying string being tokenized. Then,Pr P (T i+1 |t i ) ≤ 1/ √ Cδd t 1 , • • • , t i ≥ d 0 δ 6 (1 -δ) 2 8Cd∆|A| log(2|A|)n D = Ω ϵδ 9 log 3 (1/δ) log(1/ϵ)Proof sketch of Lemma B.5. The proof will proceed in 2 parts. We first show in Lemma B.9 that there is a set D valid of Ω(d) tokens in the dictionary which are neither prefixes nor suffixes of any other token in Dict. The reason for considering this set of tokens is twofold, 1. Irrespective of what the previous set of tokens were, it is legal for a token D valid to be sampled in the current step by the greedy encoder, since for any candidate t ∈ D valid , by definition, t j • • • t i t ̸ ∈ Dict for every j ≤ i.2. Suppose a sequence of tokens t 1 , • • • , t i have already been sampled, ending with the character a. Then, we may sample the next token using rejection sampling. Sample a ′ ∼ P (•|a) and an infinitely long trajectory on T ⋆ a ′ . Return the last token on this trajectory which belongs to Dict, and if it so happens that ∃j ∈ [i] such that t j • • • t i t ∈ Dict, then reject this trajectory and repeat. Since all the tokens in D valid are not prefixes of another token, any trajectory which reaches a token in D valid must terminate the rejection sampling process.Next, in Lemma B.10, we show that since the number of tokens in D valid is sufficiently large, Ω(d), with constant (in d) probability, a trajectory rolled out in the first round of the rejection sampling process will reach a token t ∈ D valid which has small probability, i.e. max a∈A P (t|a) ≤ 1/poly(d). By the previous arguments, this must mean that the rejection sampling process terminates on this "low probability" token, resulting in the statement of the lemma.Figure 7 : Jointly generating a sequence and its greedy encoding: In this example we use the greedy encoder under the dictionary composed of all the substrings shadowed red. The first character (a) is sampled from the stationary distribution. Then an infinite string is sampled on the tree with a as root (green path). The last substring on this path which is a token (t 1 = abb) is returned by the greedy encoder. Then the next character x = b is sampled from the source conditioned on the previous character (b) and further conditioned on t 1 x ̸ ∈ Dict. Finally, another infinite string is sampled on the tree with x = b as root (purple path) and the last substring on this path which is a token (t 2 = ba) is returned by the greedy encoder. Repeating this process, we can generate a string, here, abbba • • • , as well as its greedy encoding, (abb, ba, • • • ).Proof of Theorem B.3.1 and Lemma B.4 It is easy to see why Lemma B.5 implies a lower bound on the cross entropy H(Q MLE , P ) of the tokenizer. By Lemma A.4 for the greedy encoder,EQUATION)Since the limit m → ∞ of the RHS exists by Lemma A.4, we may let m → ∞ in any way we like, and in particular we may simply sample i ⋆ tokens, t 1 , • • • , t i ⋆ sequentially according to the process in Figure 7 . Here, the first token sampled is returned by generating an infinitely long string on T ⋆ a where a ∼ π and then truncating this trajectory to the longest token which belongs to Dict. Subsequently for every i > 1, t i is generated by sampling a fresh infinitely long string from T ⋆ a where a is sampled from the P (•|a ′ ) where a ′ is the last character t i-1 and then returning the largest prefix of this string which is a token in Dict, conditioned on t j • • • t i-1 t i ̸ ∈ Dict for any j < i. and concatenate the corresponding substrings to get an m = i ⋆ i=1 |t i | length character string. Letting i ⋆ → ∞, we must have m → ∞ surely since m ≥ i ⋆ . In this view, eq. ( 16) can be rewritten as,Q MLE (t) = lim i ⋆ →∞ n t i ⋆ = lim i ⋆ →∞ 1 i ⋆ i ⋆ i=1 I(t i = t) a.s. = lim i ⋆ →∞ 1 i ⋆ i ⋆ i=1 E[I(t i = t)|t 1 , • • • , t i-1 ] (17)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 ∈ T satisfies max a∈A P (t|a) ≤ 1/Cδ 3 d. From eq. ( 17), summing across t ∈ T , we have that,t∈T Q MLE (t) a.s. = lim i ⋆ →∞ 1 i ⋆ i ⋆ i=1 Pr (t i ∈ T |t 1 , • • • , t i-1 ) = Ω ϵδ 9 log 3 (1/δ) log(1/ϵ) (18)where in the last inequality, we use Lemma B.5 and the fact that δ max a∈A P (t|a) ≥ min a∈A P (t|a).Therefore,H(Q MLE , P ) ≥ t∈T Q MLE (t) log(1/P (t)) ≥ t∈T Q MLE (t) log( √ Cδ 3 d)where in (i) we use the fact that for t ∈ T , max a∈A P (t|a) ≤ 1/ √ Cδ 3 d, which implies that P (t) ≤ 1/ √ Cδ 3 d. Finally, combining with eq. ( 18) completes the proof of Lemma B.4. Furthermore, since the cross-entropy H(Q MLE , P ) was established to be large, by invoking the reduction in Theorem 3.4, we complete the proof of Theorem B.3.1.Figure 8 : The circled nodes indicate substrings which are tokens in Dict. The red boundary is the set of substrings t such that max a∈A P (t|a) ≥ 1/Cd. By Lemma B.8, none of the nodes which fall outside this boundary are assigned as tokens in a run of Algorithm 1. The set of circled substrings are the set of tokens in Dict. Among them, the ones circled green are the tokens in D valid , which are not prefixes or suffixes of any other tokens in Dict. Substrings such as cb or ba which are tokens in Dict do not belong to D valid because they are prefixes of longer tokens (in this case, cbb and bab respectively). On the other hand, substrings like ab do not belong to D valid since they are suffixes of tokens in Dict, in this case, bab. Lemma B.9 asserts that the number of tokens in D valid are Ω(d) in number, assuming that Dict has Ω(d) tokens to begin with.Notation. For each a ∈ A and j ∈ N ∪ {0}, define a level set of substrings,S a j = (1 -δ) j+1 < P (t|t 1 = a) ≤ (1 -δ) j. . .t 1 ← (•, •) t 2 ← (•, •) . . . t ′ ← (•, •) . . . t ′′ ← (•, •) • • • s ′ • • • s ′ • • • s 1 s 2 s 1 • • • s 7 s 1 s 2 s 1 • • • s 7 • • • t 1 • • • t 1 • • • • • • t 1 • • • t 1 • • • • • • t 1 t 2 • • • t 1 • • • t 2 • • • • • • t 1 t 2 • • • t 1 • • • t 2 • • • t ′ t ′ t ′′at each step, both copies of s ′ encode to the same sequence of tokens suppose it encodes to t ′ suppose it encodes to t ′′ =⇒ At each iteration, both copies of s ′ perfectly encode to a sequence of tokens both copies of s ′ map to the same token at this step, a contradiction where t 1 denotes the first character of t. And likewise, define the sets S j = ∪ a∈A S a j , S a ≤j and S a ≥j as the union of S a j ′ over j ′ ≥ j, j ′ ≤ j and S ≤j and S ≥j as the union of S a ≤j and S a ≥j over a ∈ A. Furthermore for a large universal constant C > 0, define parameters,EQUATIONWe first begin by stating a folklore result: every pair of tokens assigned by a merging-based dictionary generation algorithm have distinct character representations. Lemma B.6. If Algorithm 1 assigns a new token in some round, it's character representation must be distinct from that of all previously assigned tokens.Proof. A pictorial proof is in Figure 9 . We will prove this result by contradiction. Suppose t and t ′ are tokens which decode to the same character substring, s ′ . Consider all occurrences of 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 to a sequence of tokens. Now consider the merging process at 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 in S have not been tokenized yet. When the first rule corresponding to one of the tokens in {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 S a j is bounded by (1δ) -(j+1) .Proof. Since the probability of any transition is at most 1δ, this implies that any infinite trajectory on the tree T ⋆ a can intersect at most one vertex in S a j . Therefore, t∈S a j P (t|t 1 = a) ≤ 1. By the lower bound on P (t|t 1 = a) for t ∈ S a j , this implies the statement of the lemma.Next we show that with high probability none of the substrings t having probability mass (under P ) of at most δ/Cd conditioned on the first character, are assigned as tokens by Algorithm 1. Lemma B.8. In a run of Algorithm 1, for a sufficiently large constant C > 0, with probability d -Ω(1) poly(1/δ) all assigned tokens t ∈ Dict satisfy max a∈A P (t|a) ≥ 1/Cd. In other words, none of the substrings in S ≥j ⋆ are added as tokens to the dictionary in a run of Algorithm 1, where,j ⋆ ≜ log(δ/Cd)/ log(1 -δ)Proof. Consider some j ≥ j ⋆ and a ∈ A and substring t ∈ S a j . In the i th stage of the algorithm where text i 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 i . Therefore,P (t ∈ S a j is assigned as a token in text i ) ≤ d log(d) max a∈A P (t|a) log(d) ≤ d log(d) 1 Cd (1 -δ) j-j ⋆ log(d) ≤ d -log(C) (1 -δ) (j-j ⋆ ) log(d)Union bounding over S a j over j ≥ j ⋆ using the bound on |S a j | in Lemma B.7, and over a ∈ A and i ∈ [d] results in the bound,P (t ∈ S ≥j ⋆ is assigned as a token in step i for some i ∈ [d]) ≤ d -Ω(1) j≥j ⋆ (1 -δ) (j-j ⋆ ) log(d) (1 -δ) j+1 ≤ d -Ω(1) δ(1 -δ)Lemma B.9. Consider the set of tokens D valid which are not a prefix or a suffix of any other token in Dict. That is,D valid = {t ∈ Dict :̸ ∃s : st ∈ Dict} ∩ {t ∈ Dict :̸ ∃s : ts ∈ Dict}. If |Dict| ≥ d 0 , then, |D valid | ≥ d 0 4n D .where n D is defined in eq. (19).Proof. For any token t ∈ D valid , there may be at most 2|t| tokens which are suffixes or prefixes of it and belong to Dict. More importantly, every token in Dict not belonging to D valid must either be a prefix or a suffix of some token in D valid . Split the suffixes and prefixes of the tokens in D valid into four sets,1. S suff,min = t∈Dvalid {t ′ ∈ Dict : t ′ ∈ suff(t), |t ′ | ≤ |t| -n D }, 2. S suff,max = t∈Dvalid {t ′ ∈ Dict : t ′ ∈ suff(t), |t ′ | > |t| -n D }, 3. S pre,min = t∈Dvalid {t ′ ∈ Dict : t ′ ∈ pre(t), |t ′ | ≤ |t| -n D }, 4. S pre,max = t∈Dvalid {t ′ ∈ Dict : t ′ ∈ pre(t), |t ′ | > |t| -n D }.where n D is defined in eq. ( 19). Note from Lemma B.8 that all the tokens t ∈ Dict all satisfy max a∈A P (t|a) ≥ 1/Cd. Therefore, the tokens in S pre,min and S suff,min all satisfy, max a∈A P (t|a) ≥ d/C(1 -δ) n D .2n D • |D valid | + 2C(1 -δ) n D -1 d δ ≥ d 0 Recalling the choice of n D = 1 -2 log(4Cd/δd0) log(1-δ), we get that,|D valid | ≥ d 0 4n D .Lemma B.10. Suppose Algorithm 1 assigns at least d 0 tokens. For any character a ∈ A, sample an a ′ ∼ P (•|a) and an infinite trajectory on the tree T ⋆ a ′ , denoted traj. Then,E a ′ ∼P (•|a) Pr traj∼T ⋆ a ′ min t∈traj∩Dvalid P (t|a) ≤ δ/Cd a ′ ≥ d 0 δ 6 (1 -δ) 2 8Cd∆|A|n D .where the notation T ⋆ a ′ is used to overload the distribution over infinite trajectories on T ⋆ a ′ . The parameters n D and ∆ are defined in eq. ( 19).Proof. By Lemma B.8, recall that the ≥ d 0 tokens assigned in a run of Algorithm 1, with high probability, are substrings in S ≤j ⋆ . For any a ∈ A, the total number of substrings in S ≤j ⋆ can be bounded as,EQUATION)In order to prove this result, we use a counting argument and the fact that no tokens in S >j ⋆ are assigned. Consider some character a and all the leaves in the forest S ≤j ⋆ . Since every transition has ≥ δ probability of occurring, across all leaf nodes t ∈ S ≤j ⋆ , P (t|a ′ ) are within a δ 2 (1δ) factor of each other across different a ′ ∈ A. In particular, by counting the number of paths in T ⋆ (i.e. paths in T ⋆ a from ∅ to leaf nodes in S a ≤j ⋆ across a ∈ A) along which a token in Dict exists in S ≥j ⋆ /2 , we can also compute the probability mass across such trajectories up to a factor of δ 2 (1δ).Taking the union across a ∈ A, consider the paths in T ⋆ a from ∅ to leaf nodes in S a ≤j ⋆ . From Lemma B.9, j≤j ⋆ |D valid ∩ S j | ≥ d 0 /4n D , where n D = 1 -2 log(4Cd/δd 0 )/ log(1δ). Note that for sufficiently large d = Ω(log(1/ϵδ)/δ 5 ), by Lemma B.7, j≤j ⋆ /2 |S j | = Cd/δ/δ(1-δ) ≤ d 0 /8n D . Therefore,EQUATION)Define ∆ = log(δ)/ log(1δ). Combining eq. ( 21) with eq. ( 20) and applying the probabilistic method, there exists an i ⋆ ≥ j ⋆ /2 such that,EQUATION)Note that ∆ is chosen to be sufficiently large, so that every infinite trajectory on T ⋆ a ′ must intersect at least once with the band of verticesS a ′ i ⋆ +∆+1 ∪ • • • ∪ S a ′ i+2∆ .Note that this band is different from the one considered in eq. ( 22). Define L a ′ as the set of longest prefixes across infinite trajectories inT ⋆ a ′ which belong to S a ′ i ⋆ +∆+1 ∪ • • • ∪ S a ′ i+2∆ .Note that our objective is to show that an infinite trajectory sampled on T ⋆ a ′ where a ′ ∼ P (•|a), has a long prefix in Dict. We can truncate this trajectory to lower bound this probability, and therefore, we assume that the infinite trajectories on T ⋆ a ′ terminate once they reach a substring in L a ′ . Furthermore, note that although ∆ is large, it is still a constant depending on δ. Therefore, the band of statesS a ′ i ⋆ +∆+1 ∪ • • • ∪ S a ′ i ⋆ +2∆is not too wide, and all the substrings in L a ′ have approximately similar probabilities to each other. In particular, for any character a ∈ A, and for any a ′ ∈ A and t ∈ L a ′ , decomposing P (t|a) as P (t|t 1 = a ′ )P (a ′ |a),EQUATIONInequality (i) follows from the fact that all transition probabilities are at least δ, so every leaf node in L a ′ must have P (t|t 1 = a ′ ) ≥ (1δ) i+2∆+1 , and the fact that P (a ′ |a) ≥ δ. Inequality (ii)follows similarly from the fact that t a leaf node of L a ′ and therefore P (t|t1 = a ′ ) ≤ (1 -δ) i+∆ .Therefore, instead of bounding the probability of any event under the distribution over substrings in L a ′ induced by truncating the infinite strings sampled on T ⋆ a ′ , it suffices to count the fraction of substrings in L a ′ satisfying the event (which are equivalent up to a δ(1δ) factor). Define,pre(t) = (t 1 , t 1:2 , t 1:3 , • • • , t 1:|t| )As the set of prefixes of t (including t). Note that at most ∆ of the prefixes of any substring t can intersect withEQUATIONThe event inside the inner probability term is the event that an infinitely long string (truncated at L a ′ ) has a prefix which lies in D valid and which intersects withS a ′ i ⋆ +1 ∪ • • • ∪ S a ′ i ⋆ +∆, which implies that it has probability P (t|a) ≤ δ/Cd. Therefore, we have that for any a ∈ A, sampling an a ′ ∼ P (•|a) and an infinite trajectory traj ∼ T ⋆ a ′ ,E a ′ ∼P (•|a) Pr traj∼T ⋆ a ′ min t∈traj∩Dvalid P (t|a) ≤ δ/Cd a ′ (i) ≥ δ 2 (1 -δ) • E a ′ ∼P (•|a)   Pr t ′ ∼Unif(L a ′ ) min t∈pre(t ′ )∩Dvalid P (t|a) ≤ δ/Cd a ′   (ii) ≥ δ 2 (1 -δ) • E a ′ ∼P (•|a) Pr t ′ ∼Unif(L a ′ ) pre(t ′ ) ∩ D valid ∩ (S a ′ i ⋆ +1 ∪ • • • ∪ S a ′ i ⋆ +∆ ) ̸ = ∅ a ′ (iii) ≥ δ 3 (1 -δ) • E a ′ ∼Unif(A) PrProof of Lemma B.5Lemma B.10 concludes that given any previous sequence of tokens in a character a, with constant probability, an infinite trajectory sampled from T ⋆ a ′ with a ′ ∼ P (•|a) has as prefix, a substring t, which not only has low probability, with P (t|a) ≤ δ/Cd, but also belongs to the subset of tokens D valid . Note that regardless of the previously sampled tokens, it is legal to sample any token in D valid as the current token, since by definition, these tokens are not the suffixes of any other tokens in Dict. Moreover, if any trajectory on T ⋆ a ′ reaches a token in D valid , then it must be largest token along that trajectory, since none of the tokens in D valid are prefixes of another token in Dict.Consider generating a new token by rejection sampling. Suppose the set of previous tokens t 1 , • • • , t i end in some character a. Sample the next character a ′ ∼ P (•|a) and an infinite trajectory on T ⋆ a ′ . If it reaches an illegal token t such that t j t j+1 • • • t i t already exists in Dict, this token is rejected and the trajectory is resampled. By the prefix-free property of these tokens, if this trajectory visits a token in D valid , it must immediately be output as the next token. Note that this probability is lower bounded by,E a ′ ∼P (•|a) Pr traj∼T ⋆ a ′ min t∈traj∩Dvalid P (t|a) ≤ δ/Cd a ′which is lower bounded by poly(ϵ, δ), the subject of Lemma B.10. Therefore with this probability, the process terminates in the first step with a token in D valid being sampled.In this section, we will prove Theorem B.3.2 and Theorem B.3.3. In particular we show that, either, 1. The dictionary is small with low probability. i.e., Pr(|Dict| < d 0 ) = e -Ω(ϵ 2 d/ log 2 (1/δ)) , or, 2. Or conditioned on the dictionary being small, |Dict| < d 0 , with high probability ≥ 1e -Ω(ϵ 2 d/ log 2 (1/δ)) , minQ∈Q1-gram L(Q • enc(•)) ≤ 4 1 - 2d 0 d + O 1 log(d) H ∞ + 2d 0 d • log(2|A|).For i ∈ [d], define the indicator random variable, X(s ′ , Dict) = 1(∃a pair of tokens in enc BPE (s ′ ) under Dict appears at least log(d) times).which captures the event that the string s ′ is compressed well by the dictionary Dict under the sequential encoder.Let Dict i denote the dictionary stored by Algorithm 1 right after text i is processed. The key insight behind this lemma is the following statement, asserting that the sequential encoder satisfies a "monotonicity" property: for any j and string s ′ , if there exists a pair of tokens appearing more than log(d) times consecutively in the sequential encoding of s ′ under Dict j , then there must exist a pair of tokens appearing more than log(d) times consecutively in the greedy encoding of s ′ under Dict i for any i < j. This implies that X(s ′ , Dict j ) ≤ X(s ′ , Dict i ) if i < j for any string s ′ . This monotonicity property implies that the last dictionary output by the learner, Dict d sequentially encodes a 1ϵ fraction of the previously seen texts, text i in a way where every pair of tokens appears at most log(d) times. While Dict d is correlated with these texts, we can circumvent this correlation by using a martingale argument to prove the statement of the lemma. Lemma B.11. Let Dict be the dictionary returned by Algorithm 1. Then,min Pr E X s ′ , Dict Dict ≥ 2d 0 /d |Dict| < d 0 , Pr |Dict| < d 0 ≤ e -ϵ 2 d/8 log 2 (1/δ) .where s ′ is a fresh substring of length d sampled from the stochastic source.Proof. Let Dict i denote the state of dictionary returned by Algorithm 1 right after text i is processed. Then, Dict d is the final dictionary returned by Algorithm 1. SupposeE X s ′ , Dict d Dict d ≥ 2d 0 /d,where s ′ is a fresh substring of d sampled from the stochastic source. Using monotonicity of the sequential encoder, almost surely for any string s ′ , X(s ′ , Dict i ) ≤ X(s ′ , Dict j ) for any j > i.Therefore,E X s ′ , Dict d Dict d ≥ 2d 0 /d =⇒ d-1 i=1 E X s ′ , Dict i Dict i ≥ 2d 0 • d -1 d (25)Note in this expectation, s ′ is an independent string of length d sampled from the stochastic source.Since Dict i and text i+1 are independent, we may instead write,d-1 i=1 E X text i+1 , Dict i Dict i , text i , Dict i-1 , • • • , Dict 1 , text 1 ≥ 2d 0 • d -1 d .For brevity, denote X i = X(text i+1 , Dict i ) and define the filtrationF i = σ({text 1 , Dict 1 , • • • , text i , Dict i }). Note that i j=1 X j -E[X j |F i ] forms a martingale se- quence under the filtration {F i : i ∈ [d]}.Therefore, by the Azuma-Hoeffding inequality, for any η > 0,EQUATION)Under Case I, we have that d i=1 X i ≤ d . Therefore, from eq. ( 25) and eq. ( 26),Pr |Dict| < d 0 ; E X(s ′ , Dict) Dict ≥ 2d 0 /d ≤ Pr   d-1 i=1 X i < d 0 ; d-1 i=1 E [X i |F i ] ≥ 2d 0 • d -1 d   ≤ Pr   d-1 i=1 E [X i |F i ] -X i ≥ d 0 • d -2 d   ≤ e -d 2 0 (1-2/d) 2≤ e -d 2 0 /2 = e -ϵ 2 d/8 log 2 (1/δ) . {chunk i = (X id+1 , X id+2 , • • • , X (i+1)d ) : i = 1, 2, • • • }is also Markovian and ergodic. Therefore, by a similar limiting argument as in Lemma A.4, using the Krylov-Bogolyubov argument (cf. Proposition 4.2 in Chen ( 2018)) for Markov processes, we have that,lim ℓ→∞ ℓ i=1 X(chunk i , Dict) ℓ = E[X(s ′ , Dict)] ≤ 2d 0 d .where s ′ is a fresh string of length d sampled with initial state distribution as the stationary measure of the stochastic source. On the remaining (limiting) 1 -2d 0 /d fraction of the chunks, their sequential encodings have every pair of tokens appearing at most log(d) times consecutively. Using Theorem 1 of Navarro and Russo (2008) , the number of tokens in the encoding of each of these chunks cannot be too large, and satisfies,EQUATIONFor the (limiting) 2d 0 /d fraction of the "bad" chunks, their sequential encodings may have one or more pairs of tokens which appear more than log(d) times consecutively.Define E i = {X(chunk i , = 1} where Dict = Dict d is the dictionary returned by Algorithm 1 and consider the unigram modelQ uni (t) = 1 2 Q 1 (t) + 1 2 Q 2 (t), which is the uniform mixture of two models,Q 1 (t) ∝ 1 (2|A|) |t| , and Q 2 (t) = E n 1 t |enc BPE.split (chunk 1 )| E c 1 ,and letQ uni (t 1 , • • • , t i ) = Q # (j) i j=1 Q uni (t i ) for some distribution Q # (i)over the number of tokens to be chosen later. We will analyze the case where the total number of chunks ℓ is finite and take the limit m → ∞ later. Then, the overall loss of the algorithm is,EQUATIONwhere n i t is the number of times t is observed in the BPE encoding of chunk i and (i) uses the fact that |enc BPE.split (s)| follows some distribution supported on [m], which implies its entropy is upper bounded by log(m). First observe that,ℓ i=1 E   t∈Dict n i t log Q uni (t) E c i   ≤ ℓ i=1 E |enc BPE (chunk i )| • t∈Dict n i t |enc BPE (chunk i )| log Q uni (t) E c i (i) ≤ ℓ 2dH ∞ + O(d/ log(d)) log(d) t∈Dict Q 2 (t) log Q uni (t)where (i) uses the upper bound on |enc BPE.split (chunk i )| under the event E c i (eq. ( 27)). SinceQ uni (t) = 1 2 Q 1 (t) + 1 2 Q 2 (t) ≥ 1 2 Q 2 (t)and Q 2 is a distribution supported on at most d tokens, this term results in the upper bound,EQUATIONOn the other hand, sinceEQUATIONwhere the last inequality uses the fact that t∈Dict n i t ≤ d and t∈Dict |t|n i t = d computes the length of chunk i .Overall, since ℓ i=1 Pr(E i ) ≤ 2d 0 /d by eq. ( 27), combining this with eqs. ( 28) to (30),L m (Q uni • enc(•)) ≤ 1 - 2d 0 d ℓ 2dH ∞ + O(d/ log(d)) log(d) log(2d) + 2d 0 d ℓd log(4|A|).Dividing throughout by the length of the sequence m ∈ [d(ℓ -1), dℓ] and letting ℓ → ∞,min Q∈Q1-gram L(Q • enc(•)) ≤ L(Q uni • enc(•)) ≤ 1 - 2d 0 d 2H ∞ + O 1 log(d) + 2d 0 d log(4|A|).C Additional Theoretical Results II: Learning the likelihood modelThe guarantees we prove in Theorems 3.1, 3.6 and B.2 on various tokenizers assume that the downstream model is trained optimally. In practice, these models are trained from a finite dataset and the sample complexity of learning this likelihood model scales with the number of tokens in the dictionary. In this section, we step away from the transformer architecture and focus on analyzing the performance of a simple estimator for the unigram model based on Laplace smoothing. We leave the problem of analyzing the finite-sample statistical error of simple transformer models trained with gradient descent as an interesting open direction for future research.The result of Theorem 3.1 establishes that under appropriate assumptions on the Markov source, there exists a tokenizer T and a unigram model over tokensQ ⋆ ∈ Q 1-gram such that, lim m→∞ 1 m E log(1/Q ⋆ (enc(s)) ≤ (1 + ε) • lim m→∞ 1 m E log(1/P (s))Or in other words,lim m→∞ 1 m KL(P, Q ⋆ (enc(•))) ≤ ε • lim m→∞ 1 m E log(1/P (s)) .This implies that with the appropriate tokenization, the measure associated to the string by the best unigram model over tokens is close to that induced by the true Markov distribution over characters in KL divergence. In this section, we establish finite-sample guarantees on learning Q ⋆ 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, 1), define E θ as the event that every maximal token t (Definition A.5) in the LZW dictionary satisfies 1/d 1-θ ≥ max a P (t|a) ≥ δ/d 1+θ . By Lemmas A.10 and A.11 when the LZW tokenizer is trained on a dataset of size Ω δ (d) drawn from a stochastic source satisfying Assumption 3.2, E θ occurs with probability ≥ 1d -Ω θ,δ (log(d)) . Theorem C.1. Consider any constant θ ∈ (0, 1), failure probability η ∈ (0, 1) and approximation error ξ ∈ (0, 1). Assume that the learnt LZW tokenizer T LZW satisfies the event E θ , which occurs with probability ≥ 1d -Ω θ,δ (log(d)) . Assume that d 1-3θ ≥ 1 + δ -2 and that the stochastic source satisfies Assumption 3.2. For an absolute constant C > 0, assume that the size of the training dataset is at least n ⋆ lm (ξ), where,n ⋆ lm ≜ Cd 1+θ log 3 (d/ηδ) log log(d/η) δξ 2 Then, Algorithm 2 learns a unigram model Q such that, L( Q • enc gre (•)) ≤ (1 + ξ) min Q∈Q1-gram L(Q • enc gre (•))with probability ≥ 1η.In conjunction with Theorem 3.6, this gives end-to-end guarantees on the cross-entropy loss of the LZW tokenizer (with vocabulary size ≤ d) with the Laplace estimator as the downstream unigram model. We instantiate this result choosing θ = 0.01 in Theorem C.1. Corollary C.2. Choose any ξ ∈ (0, 1). Suppose the data source satisfies Assumption 3.2. On a dataset of size Ω δ (d) drawn from the source, train an LZW tokenizer T LZW with d tokens. Subsequently, using Algorithm 2, learn a unigram model Q using a dataset of size at least Ω(d 1.01 /δξ 2 ) drawn from the source. Then, with probability ≥ 1d -Ω δ (log(d)) ,L( Q • enc gre (•)) ≤ 1 + ξ 1 -ε min Q L(Q),where ε = log(1/δ) 0.99 log (d) .The analysis of Theorem C.1 relies on showing that the distribution over tokens induced a string sampled from the data source is encoded into tokens by the greedy encoder and the LZW dictionary is a Markov process. In general, given a set of previously sampled tokens t 1 , • • • , t i , the next token t i+1 is sampled from the distribution P (ti+1 |t i ; ∀j ∈ [i], t i-j+1 • • • t i t i+1 ̸ ∈ Dict).The conditioning is to simply guarantee that the previous tokens which were sampled were indeed maximal, since if t i t i+1 ∈ Dict, then the previous token returned would in fact have been this longer token and not t i (and likewise for t i-1 t i t i+1 and so on). While in general, this process is complicated and depends on all the previous tokens sampled, for the LZW dictionary, we show that the conditioning {∀j ∈ [i], t i-j+1 • • • t i t i+1 ̸ ∈ Dict} can be removed, thereby resulting in a simple Markov process over tokens.Furthermore, we establish that this Markov process has a relatively large spectral gap. The optimal unigram model ends up being the stationary distribution over tokens induced by greedy encoder.Given the large spectral gap of the Markov process over tokens, estimating the stationary distribution of this process in KL divergence ends up being closely related to estimating a distribution from i.i.d. samples in the same metric. For this problem, the de-facto choice of estimator is the Laplace estimator, and several existing results provide finite-sample bounds on the KL divergence (Braess and Sauer, 2004; Han et al., 2021; Mourtada and Gaïffas, 2022) . The Laplace estimator (Line 6 of Algorithm 2) is simply a smoothed empirical estimate to account for the degeneracy of the KL divergence in its second argument as any coordinate approaches 0. The non-i.i.d.ness of the Markov process is circumvented by using concentration inequalities which are a function of the spectral gap (Naor et al., 2020) .Algorithm L( Q • enc gre (•)) -min Q∈Q1-gram L(Q • enc gre (•)) = max Q∈Q1-gram lim m→∞ 1 m E[log(Q(enc gre (s))/ Q(enc gre (s)))] (i) = max Q∈Q1-gram lim m→∞ 1 m E   |enc gre (s)| t∈Dict n t |enc gre (s)| log(Q tok (t)/ Q tok (t))   + log(m) m (ii) ≤ lim m→∞ 1 m E   |enc gre (s)| t∈Dict n t |enc gre (s)| log n t /|enc gre (s)| Q tok (t)   + log(m) mwhere in (i) we use the fact that Q # = Unif([m]) and in (ii) we take the max{•} inside the limit and the expectation (Fatou's lemma and Jensen's inequality) and plug in the maximizer of the negative cross-entropy, Q tok (t) = L( Q • enc gre (•)) -min Q∈Q1-gram L(Q • enc gre (•)) ≤ lim m→∞ 1 m E[|enc gre (s)|] • KL(Q MLE , Q tok ) (31)By eq. ( 6), we have that for any tokenizer using the greedy encoder,lim m→∞ |enc gre (s)| H(Q MLE , P ) -log(1/δ) m a.s. ≤ H ∞ .Furthermore under the event E θ which implies that the learnt dictionary is (1θ)-heavy hitting (cf. Definition A.5), which implies that,H(Q MLE , P ) ≥ (1 -θ) log(d).Therefore, by almost sure boundedness, we have that,lim m→∞ 1 m E |enc gre (s)| ≤ H ∞ (1 -θ) log(d) -log(1/δ) ≤ min Q∈Q1-gram L(Q • enc(•)) (1 -θ) log(d) -log(1/δ)Putting this together with eq. ( 31), we have that,EQUATIONwhich uses the assumption (1θ) log(d) ≥ 1 + log(1/δ). 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 nt t ′ n t ′ ∈ [0, 1], we have that,Q MLE (t) = lim m→∞ E n t t ′ n t ′ = lim m→∞ E [n t ] E t ′ n t ′ = π(t),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 A.10 and A.11, for any constant θ ∈ (0, 1), with probability ≥ 1d -Ω θ,δ (log(d)) , every maximal token in the the LZW dictionary satisfies 1/d 1-θ ≥ max a P (t|a) ≥ δ/d 1+θ . Let S gre denote the set of tokens which have a non-zero probability (over a string drawn from the Markov source) of being chosen by the greedy encoder while encoding the string. More importantly, note that for any sequence of tokens t 1 , • • • , t i , the next token is necessarily in S gre and can be any token in this set. The reason for this is that for any t i , t ∈ S gre , the concatenation t i t ̸ ∈ S gre since max a∈A P (t i t|a) ≤ 1/δd 2(1-θ) , which is smaller than the max a∈A P (t ′ |a) ≥ δ/d 1+θ for any token t ′ ∈ S gre as long as d 1-3θ ≥ 1/δ 2 . This constraint implies that in the sampling procedure in Figure 7 , it suffices to drop the conditioning on the event t j t j+1 • • • t i t ̸ ∈ Dict while sampling the next token t. This condition automatically implies that the sequence of tokens conditionally follows a Markov process with Pr(t i+1 = t|t 1 , • • • , t i ) = P (t|last(t i )). Since the probability of every transition is lower bounded, this means that the Markov chain is ergodic. Moreover, the pseudo-spectral gap (Naor et al., 2020) , 1λ can be lower bounded by the Dobrushin contraction coefficient, κ,EQUATION)Recall that the learner is given a training dataset of n lm characters to train the likelihood model. By Lemma A.8, with probability ≥ 1d -Ω(log(d/δ)/δ) , in the run of the LZW tokenization algorithm, every token in the dictionary has length at most ℓ max = 4 log(d|A|)/δ. In this case we have the upper bound,EQUATIONwhere the last inequality follows from eq. ( C1). This implies that,EQUATION)By using the geometric ergodicity of this Markov process (eq. ( 33)), when n ′ tokens are sampled from an arbitrary initial distribution,1 -κ n ′ π(t) ≤ E[n t ] n ′ ≤ κ n ′ + 1 -κ n ′ π(t) =⇒ π(t) ≤ Q tok (t) 1 -e -4r|Dict| log(|Dict|/η) = Q tok (t) 1 -d -rwhere in the implication, we use the condition on n ′ in eq. ( C1) and the bound on the contraction coefficient κ in eq. ( 33).KL(Q MLE , Q tok ) = t∈Dict π(t) log(π(t)/ Q tok (t)) ≤ t∈Dict π(t) 1 -d -r log(π(t)/ Q tok (t)) -log(1 -d -r ) ≤ 1 1 -d -r t∈Dict I(C I )π(t) log(π(t)/ Q tok (t)) + I(C II )π(t) log(π(t)/ Q tok (t)) + I(C III )π(t) log(π(t)/ Q tok (t)) + 2d -r ≤ 1 1 -d -r t∈Dict I(C I ) 3 2 π(t) r|Dict| eq. (35) + I(C II ) 2 r|Dict| log 16d θ log(|Dict|/η) eq. (36) + I(C III ) π(t) r eq. (37) +2d -r ≤ 1 1 -d -r   3 2 |Dict| r|Dict| + 2 r log(16d θ log(|Dict|/η)) + 1 r   + 2d -r ≤ 5 √ r log(16d θ log(|Dict|/η))Combining with eq. ( 32), we get the bound,L( Q • enc gre (•)) ≤ 1 + KL(Q MLE , Q) min Q∈Q1-gram L(Q • enc gre (•)) ≤ 1 + 5 √ r log(16d θ log(d/η)) min Q∈Q1-gram L(Q • enc gre (•)).Rescaling r to be r(log(16d θ log(d/η))) 2 completes the proof. H( Q MLE , P γ ) ≥ nH ∞ (1 -O(n -1/4 ))is large. However, for this dictionary, for any encoding algorithm (including the greedy encoder), the resulting tokenizer T= (Dict, ∅, enc(•), dec(•)) satisfies, min Q∈Q1-gram L(Q • enc(•)) ≥ (1 -ε)H(π) where ε = 2ne -nH∞(1-O(n -1/4 )) .Proof. Suppose the entire training dataset was compressed into a single token, t src . The dictionary is A ∪ t src . In the following argument, we show that the number of occurrences, n tsrc , of the entire training dataset t src in a new string of length m generated from the stochastic source, s, converges to its expectation as m → ∞. Let π (i) n denote the stationary distribution of the Markov process induced by the stochastic source over length-n strings with a shift of i from the starting position, and let n (i) t denote the number of times t appears in the training dataset starting at the position i + rn for some r > 0. Then,EQUATIONThe second equation follows by considering the Markov process induced over length n strings and applying the Krylov-Bogolyubov argument for ergodic and homogeneous Markov processes.In Lemma D.2, we show that with probability ≥ 1e -Ω( √ n) , the token t src constructed from the source dataset satisfies, max a∈A P (t|a) ≤ e -nH∞(1-O(n -1/4 )) . In other words, the source string has exponentially small probability. Combining this with eq. ( 38), with probability ≥ 1e -Ω( = π(a). More importantly, the number of times a is made as a token is upper bounded by n a and lower bounded by n ann tsrc . Therefore,EQUATIONFinally, putting everything together,min Q∈Q1-gram lim m→∞ 1 m L m (Q • enc(•)) min Q∈Q1-gram lim m→∞ - 1 m E log(Q # (|enc(s)|) + t∈Dict n t log Q tok (t) ≥ min Q∈Q1-gram lim m→∞ - 1 m E a∈A n a log Q tok (a) (i) ≥ min Q∈Q1-gram -(1 -ε) a∈A π(a) log Q tok (a) ≥ (1 -ε)H(π).where (i) follows from the lower bound on n a /m in eq. ( 39). This completes the proof.Lemma D.2. With probability ≥ 1e -Ω( √ n) over the source dataset,max a∈A P (t src |a) ≤ e -nH(δ)(1-O(n -1/4 )) .Proof. Let X denote the number of i ∈ [n -1] such that s i ̸ = s i+1 in s, the stochastic source. Since the transition of the Markov process only depends on whether the next character is the same as the previous character, we can write down,max a∈A log P (t src |a) = -(X + 1) log(δ) -(n -1 -X) log(1 -δ).Note that X is a sum of n -1 i.i.d. random variables, since I(s i ̸ = s i+1 ) ∼ Ber(δ) does not depend on whether s i = 0 or = 1. In particular, by Hoeffding's inequality, we have that with probability≥ 1 -e -Ω( √ n) , 1 n max log P (t src |a) -H(δ) ≤ O n -1/4 , which uses the fact that E[X] = δ(n -1) and H ∞ = δ log(1/δ) + (1 -δ) log(1/(1 -δ)). Taking an exponential on both sides proves the statement of the lemma.In this section, we show another kind of barrier to generalization, which brings out the relationship between the encoding algorithm and the dictionary. We show that there exist dictionaries which generalize under the minimal encoder, i.e. the encoding algorithm which encodes a string into the shortest number of possible tokens, but at the same time, completely fail to generalize under the greedy encoder. This means that in the process of constructing good tokenizers, it does not suffice to think about the dictionary in isolation. Its interaction with the encoding algorithm is pertinent. Definition E.1 (minimal encoder). The minimal encoder parses a new string into the fewest possible number of tokens from the dictionary as possible. Ties are broken arbitrarily. Theorem E.2. There exists a stochastic source parameterized by δ ∈ (0, 0.5) and a dictionary Dict such that under the minimal encoder/decoder pair, the resulting tokenizer, T = (Dict, ∅, enc min (•), dec min (•)) generalizes near-optimally,EQUATION)Here the entropy rate of the source, H ∞ , is δ log( √ 2/δ) + (1δ) log(1/(1δ)). However, the same dictionary Dict under the greedy encoder/decoder pair, i.e. T ′ = (Dict, ∅, enc gre (•), dec gre (•)), generalizes poorly, suffering from cross-entropy scaling as,EQUATION)where the entropy of the stationary distribution of the source is H(π) = 1 2 log(8) and the 1 This that the greedy encoder is not really compatible with the dictionary in the sense that the cross-entropy loss of the tokenizer is a constant multiple away from that achieved by the characterlevel tokenizer. The separation between eq. ( 40), and eq. ( 41) only manifests as δ becomes smaller and smaller.-o δ (1) term is (1 -δ) 2 (1 + δ) -1 .In this section, we prove that generalization of a dictionary is a function of the underlying tokenization algorithm used. In particular, the greedy encoder is not universal, and there exists dictionaries under the minimum-length encoder/decoder which achieve small cross-entropy loss, which do not generalize under the greedy encoder/decoder.We split the proof of Theorem E.2 into two parts. We first define the stochastic source and dictionary we consider. Then we show that under the minimum-length encoder, the asymptotic cross-entropy loss is upper bounded by H ∞ up to a constant. Finally, we show that under the greedy-encoder, the same dictionary suffers from high cross-entropy loss, which is a constant factor away from that of the character encoder.E.1 Stochastic source and dictionary.Consider an extension of the switching Markov source in example A.1 to A = {0, 1, 2}. The Markov chain is described in Figure 10 . The transition of the Markov chain is P (0|0) = P (1|1) = P (2|2) = 1δ, and P (1|0) = P (2|1) = δ and P (2|1) = P (0|1) = δ/2, with the remaining transitions being 0-probability. For a parameter ℓ > 0 to be instantiated later, define S 1 (resp. S 0 , S 2 ) as the set of all-1 (resp. all-0, all-2) strings of length ≤ ℓ -1, including the empty string. Consider a dictionary composed of the following set of tokens, {1s : s ∈ S 0 ∪ S 1 ∪ S 2 }. Therefore, the tokens follow the template 10 • • • 0, 11 • • • 1 or 12 • • • 2 and are of length at most ℓ. ℓ is chosen to be 1 + 2 log(1/δ)/δ.Although we use the minimal encoder in the statement of Theorem E.2, for the purpose of analysis, define the following encoding algorithm: if the new string is prefixed by 10 • • • 0 or 12 • • • 2, select the largest prefix which exists in dictionary and assign it as a token. If the new string starts with a sequence 11 • • • 1 of length x, consider the first max{ℓ, x -1} length prefix and assign it as a token. Finally, if the string starts with 0 or 2, assign that character as token. Once the first token has been assigned, remove it and repeat.E.2 Minimal encoder achieves the optimal cross-entropy loss up to a constant.First consider a simplification of the overall cross-entropy loss,EQUATIONwhere in the last inequality we upper bound by choosing = 1 E t∼QMLE [|t|] .EQUATIONconverges to some limit almost surely. Therefore, from eq. ( 44), where the essential lim-sup captures the almost sure limit 1/E t∼QMLE [|t|] . The almost sure convergence of |enc(s)|/m also implies that we can let the limit m go to ∞ in any manner, and the limit will remain the same. In particular, consider a process parameterized by i ⋆ for generating the source string, such that surely m ≥ i ⋆ , where the total number of characters, m, is a random variable. As i ⋆ → ∞, we will also have m → ∞ surely, and so the limit of |enc(s)|/m under this modified stochastic process should also converge to the same limit.Rather than sampling a string of a fixed length m from the source, consider the following sampling model: for i ⋆ → ∞, sample i ⋆ geometric random variables X 1 , • • • , X i ⋆ i.i.d.∼ Geo(δ) and construct the source string as the concatenation of i ⋆ strings alternating between successive 1's and successive 0's or 2's (with the choice between the two made uniformly at random), with the i th string of length X i + 1. The overall number of characters sampled, m, is surely at least i ⋆ .Under this stochastic process, the size of the encoding of the string is upper bounded by,|enc(s)| ≤ |X 1 + 1| + i ⋆ i=2 1 + (X i + 1 -ℓ) +This bound follows from the fact that in any substring s ′ of successive 1's followed by a substring s ′′ of successive 0's or 2's, the encoder tokenizes the first max{ℓ, |s ′ | -1} length prefix of s ′ as a token, and the remaining characters in s ′ into individual tokens except the last. Then, the last character of s ′ and the first max{ℓ -1, |s ′′ |} characters of s ′′ are assigned as token. The remainder of s ′′ is assigned as individual tokens. Each of s ′ or s ′′ of length x, is allocated into at most 1 + (x + 1ℓ) + tokens.For any i, Pr(X i ≥ u) = (1-δ) u , and therefore, summing over u ≥ ℓ, we get that E[(X i +1-ℓ) + ] =(1-δ) ℓ-1 δ. With ℓ = 1 + 2 log(1/δ)/δ, this expectation is upper bounded by δ. Therefore,lim i ⋆ →∞ E[|enc(s)|] i ⋆ ≤ lim i ⋆ →∞ 1 i ⋆ E |X 1 | + i ⋆ i=2 1 + (X i + 1 -ℓ) + ≤ 1 + δMore importantly, by the strong law of large numbers for a sum of independent random variables,(|X 1 + 1| + i ⋆i=2 (1 + (X i + 1ℓ) + ))/i ⋆ , and therefore |enc(s)|/i ⋆ is asymptotically almost surely upper bounded as,EQUATIONOn the other hand, the number of characters generated, m, equals i ⋆ i=1 (X i + 1), and satisfies, lim i ⋆ →∞ E[m]/i ⋆ = 1 + δ -1 . By another application of the strong law of large numbers for a sum of independent random variables,EQUATION)By combining eqs. ( 46) and ( 47), we have that,lim i ⋆ →∞ |enc(s)| m a.s. ≤ 1 + δ 1 + δ -1 = 1 δ .Finally, combining with eq. ( 45) and the ensuing discussion, we may upper bound the limiting cross-entropy loss by, Note for this Markovian source, it is a short calculation to see that,H ∞ = E x∼π [H(P (•|x))] = δ log( √ 2/δ) + (1 -δ) log(1/(1 -δ))Note that for any δ ≤ 1/2, numerical evaluation gives the inequality,1 ≤ δ log(3 + 4 log(1/δ)/δ) H ∞ ≤ 1.273with the approximation factor improving as δ becomes smaller. Therefore, this tokenizer achieves a normalized cross-entropy loss which asymptotically scales as a constant multiple of the entropy rate of the source.Note that the greedy encoder picks the largest prefix of the string which is a token, assigns and removes it, and iterates on the rest of the string. The greedy encoder's behavior is easy to analyzeevery string of consecutive 1's in the new string is broken into chunks of length ℓ (save potentially the last chunk) and each chunk is assigned as a token in {1s : s ∈ S 1 } ⊂ Dict. If the length of this substring of successive 1's is not 1, ℓ + 1, 2ℓ + 1, • • • , or in general, ≡ 1 mod ℓ, every character in the next sequence, composed of 0's or 2's is tokenized into individual characters.Similar to eq. ( 42) to eq. ( 43), consider a simplification of the overall cross-entropy loss, The minimizer of this objective subject to t∈Dict:QMLE(t)>0 Q tok (t) ≤ 1 is Q tok (t) = Q MLE (t) resulting in the inequality,EQUATIONwhere we use the convention 0 log(1/0) ≜ lim P →0 P log(1/P ) = 0 and therefore we may sum over tokens such that Q MLE (t) = 0 for free.Considering the same geometric sampling model as in Appendix E.2, and Lemma A.4, we may study the almost sure limit Q MLE (t) = lim m→∞ n t /|enc gre (s)| by computing lim i ⋆ →∞ n t /|enc gre (s)| under the geometric sampling model since the almost sure limit exists. Recall that in the geometric sampling model, we generate the overall source string by concatenating i ⋆ strings of length X 1 + 1, • • • , X i ⋆ + 1 where X i ∼ Geo(δ), with the strings alternating between successive 1's and successive 0's or 2's (with the choice between the two made by the flip of a fair coin). For x ∈ {0, 1, 2}, let E i (x) denote the event that X i is a string composed only of all x's. The length of the greedy encoding of s is lower bounded by,EQUATION)Which captures for the fact that all 0's and 2's are encoded into singular tokens unless previous string of 1's was of length ≡ 1 mod ℓ. By the law of large numbers of the RHS of eq. ( 49), the following a.a.s. lower bound is satisfied,EQUATIONwhere the last inequality uses the fact that ℓ = 1+2 log(1/δ)/δ. Likewise, observe that, |enc gre (s)| ≤ m surely, and following the analysis in Appendix E.2 of eq. ( 47), we have that,EQUATIONFor x ∈ {0, 2}, observe that the expected number of times the token x is observed in the encoding of s, n x can be written as,EQUATIONIn particular, taking the expectation of eq. ( 52),EQUATIONNote 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 i th term in the sum only depends on X i and X i-1 , conditioned on whether the non-zero parities are even or odd, n x can be written as a sum of ≈ i ⋆ /2 mutually independent terms. By the strong law of large numbers on each of the conditional processes, eqs. ( 52) and (53) implies that for x ∈ {0, 2},lim i ⋆ →∞ n x i ⋆ a.s. ≥ 1 -δ 2 4δ .To upper bound n x , note that it is upper bounded by the number of times the character x appears in the source string, which by the strong law of large numbers a.a.s (after normalizing by i ⋆ ), scales as 1/4δ. Finally, to bound Q MLE (t) which is the sequential nature of the encoder, using a similar proof as Lemma A.4, we can show that n t / t ′ n t ′ converges to the unigram MLE model for this tokenizer. For the token x ∈ {0, 2},EQUATIONUsing the a.a.s. upper and lower bounds on |enc(s)|, n 0 and n 2 derived in eqs. ( 51) and ( 54), we arrive at lower and upper bounds on Q MLE (x) for x ∈ {0, 2},1 4 ≈ 1 -δ 4 = (1 -δ 2 ) 4δ(1 + δ -1 ) ≤ Q MLE (x) ≤ 1 2(1 -δ 2 ) ≈ 1 2 .Since there are at least two tokens having probability bounded away from 0 and 1 by a constant under the MLE unigram model, the entropy of Q MLE must also be lower bounded by a constant. Indeed,H(Q MLE ) ≥ 2 min 1-δ 4 ≤y≤ 1 2(1-δ 2 )y log(1/y).It is easy to verify that for δ ≤ 0.5, the minimizer is achieved at y = 1-δ 4 , which leads to the lower bound, H(Q MLE ) ≥ 1 -δ 2 loglim m→∞ 1 m L m (Q • enc(•)) = lim i ⋆ →∞ E |enc gre (s)| m H(Q MLE ) ≥ lim i ⋆ →∞ E |enc gre (s)| m • 1 -δ 2 log 4 1 -δ (i) ≥ 1 -δ 2δ(1 + δ -1 ) • 1 -δ 2 log 4 1 -δ ≥ (1 -δ) 2 3(1 + δ) H(π)where (i) follows from the lower bound on |enc gre (s)| in eq. ( 50) with the almost sure limit of m in eq. ( 47) and noting that |enc gre (s)|/m ≤ 1 surely. The last inequality follows by simplifying using π = (1/4, 1/2, 1/4) and H(π) = 1 2 log(8).Experiment 1 (Figures 4a and 4b ). In this and previous experiments (Figures 2, 3a and 3b), we train the transformers on a single GPU on an 8× A100 node. The wall-clock time measured does not count time spent in validation loss evaluations. The hyperparameter choices are listed in Table 3 .Experiment 2 (Table 1 ). We evaluate pre-trained tokenizers on various datasets. In this experiment, we do not evaluate the likelihood model on test sequences, rather, we estimate the cross-entropy of the best unigram model by using the approximation,EQUATIONwhere Q(t) = nt t nt is the MLE unigram model learnt from a finite dataset, which we choose here as GLUE (Wang et al., 2019) , and n t is the number of times the token t is observed in the encoding of the dataset. This approximation allows us to separate the error stemming from learning a suboptimal likelihood model which tends to have higher sample complexity requirements and focus on the asymptotic error of the tokenizer.38th Conference on Neural Information Processing Systems (NeurIPS 2024).This can be thought of as the concatenation of all the individual sequences in the training dataset.The last few characters which do not add up to r in total are left untokenized. These boundary effects will not matter as the test sequences grow in lengthε is assumed to be < 1 in this statement. The constant 0.99 can be made arbitrarily close to 1.The constant 0.99 can be made arbitrarily close to 1.The model with tokenization has width equal to the typical length of sequences after encoding, which is smaller.m H(P ) = H Ber (δ) = δ log(1/δ) + (1δ) log(1/(1δ)), but π = {1/2, 1/2} and so H(π) = H Ber (1/2) = log(2).The ratio lim m→∞ mH(π) H(P ) goes to ∞ as δ → 0.where (i) uses the fact that the prefixes of t ∈ L a ′ cover all the substrings in S a ′ ≤i ⋆ +∆ , and therefore∪ t∈L a ′ pre(t) ⊃ S a ′ i ⋆ +1 ∪ • • • ∪ S a ′ i ⋆ +∆, and (ii) uses eq. (22). Finally, (iii) uses the fact that ∆ is not too large, and therefore, for any substringt ′ ∈ S a ′ i ⋆ +1 ∪ • • • ∪ S a ′ i ⋆ +∆ , there are at most 1/(1δ) 2∆ = 1/δ 2 substrings t ∈ L a ′ which contain it as a prefix. This means, |L a ′ | ≤ |S a ′ i ⋆ +1 ∪ • • • ∪ S a ′ i ⋆ +∆ |/δ 2 .After dividing by a ′ ∈A |L a ′ | on both sides, this implies,t ′ ∼Unif(L a ′ ) pre(t ′ ) ∩ D valid ∩ (S a i ⋆ +1 ∪ • • • ∪ S a i ⋆ +∆ ) ̸ = ∅ a ′ ≥ δ 3 (1δ) • δ 3 d 0 (1δ) 8Cd∆|A|n D .Here (i) follows by truncating the trajectory traj to terminate at a node in ∪ a ′ ∈A L a ′ and from eq. (23), (ii) follows by arguing that i ⋆ ≤ j ⋆ /2 and therefore if a prefix of t ′ lies inS a ′ i ⋆ +1 ∪ • • • ∪ S a ′ i ⋆ +∆, then it must have P (t|a) ≤ δ/Cd. Inequality (iii) follows by noting that all the transitions P (a ′ |a) have probability ≥ δ, and the last inequality follows from eq. (24). 


Decision: 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..

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: This paper’s framing, in my opinion, significantly over-claims its results:
* 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.
* 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.

I 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.
questions: 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.

> we study the end-to-end cross-entropy loss achieved by transformers with and without tokenization

I’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.

> 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).


This phenomenon was previously shown by Chang et al., 2022; 2023.

> Line 115. Q(t1, t2, · · · , tj ) = Q#(j) Qji=1 Qtok(ti)

What does Q_{#}(j) represent?

> Figure 2a

What happens if models are trained for more iterations?

> Figure 3

I found this figure confusing. I don’t fully understand what is being presented here.

#### `References`

* Chang et al., 2022. Word Acquisition in Neural Language Models
* Chang et al., 2023. Characterizing Learning Curves During Language Model Pre-Training: Learning, Forgetting, and Stability
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* 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.
* 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
questions: 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
* 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
* How does the work differ from/build on Edelman et. al. 2024 and Makkuva et. al. 2024?
limitations: 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)
paper_summary: paper_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.

In particular:

Section 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.

Section 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.

Of 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).

Finally, 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).

Finally, they extend the theoretical framework to LZW tokenizers.

Experiments 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.
strength_weakness: strength_weakness: One of the main weaknesses of this work is how it is presented. 
Maybe it's me, but I found it quite hard to read. See questions.

Another concern is how theoretical results apply to real-world datasets. See questions, but Fig. 5 seems to mitigate the impact of your theoretical results.
In fact, for the vocabulary that grows larger, all the models have a similar value of cross entropy (for around ~50K tokens).

The article seems rushed, as there are many typos (I just listed some).
- Line 150 “the a”
- Line 173, “it make since” --> “sense”
- Line 175, eq. and many others --> Eq. (it’s not wrong per-se, but you capitalize Fig, Example, etc.)
- The Notation paragraph shouldn’t go with related works but should be in the next section.
- 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).
questions: 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.
Am I missing any non-trivial observation here?

There 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.

By unigram models, do you mean those where the probability of each token approximates the inverse frequency of a character/token in the training data?

If 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?

In Figure 2 you mention that plot (2b) has 70x less parameters, but you do not specify why (Is it to prove tokenization helps?).
Do 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?

Fig. 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: limitations: Please see previous sections.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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.
questions: questions: Please see the Weaknesses section above
limitations: limitations: yes

Comments: title: Answer to Authors
Discussion period ending soon: call for response
comment: I thank the authors for their detailed response and clarifications. I think the suggested changes listed by the authors will significantly improve it, and I have increased my score from 4 to 7.
Thank you for addressing my questions as well as the questions and concerns raised by the other reviewers. I think this is a good paper, and will raise my score accordingly.
Dear Reviewer 88v6,

We sincerely appreciate the time you have taken to provide valuable feedback for our work. As we are getting closer to the end of the discussion period, could you let us know if our responses above have adequately addressed your concerns? We remain at your disposal for any further questions.

If you agree that our responses to your reviews have addressed the concerns you listed, we kindly ask that you consider whether raising your score would more accurately reflect your updated evaluation of our paper. Thank you again for your time and thoughtful comments.

Sincerely,&nbsp;  
The Authors
Thank you for the detailed response. The proposed changes in the main response would raise my score slightly. I adjust to reflect that.
I thank the reviewers for their clarifications. I am convinced by their arguments, and I appreciate the comment where they address multiple concerns raised by different reviewers. I will keep my score.