An Analysis of Tokenization: Transformers under Markov Data

We thank the reviewer for the feedback and questions. Below we addressed the key points mentioned.

[W1] Analysis for commonly-used tokenizers such as BPE

The guarantees in section 3.2 study guarantees for the LZW tokenizer, which is arguably not used much in practice. However, in Section B of the Appendix (Additional Theoretical Results I: A sequential variant of BPE) we study a variant of BPE which is analytically tractable, and present a result similar to Theorem 3.1 for this tokenizer (cf. Theorem B.2). The discussion of this result in the main paper was deferred to a short excerpt in Section 4.1 due to a lack of space, but in the subsequent version of the paper, we shall include a longer discussion. This was indeed our motivation to analyze (a tractable variant of) BPE as well - it remains one of the most commonly employed tokenizers in practice across a number of domains.

[W2] Practical takeaways

We point the reviewer to the response to [W3] of Reviewer veC3 where we have summarized the key empirical takeways of the paper.

We thank the reviewer for the feedback. Below we address the weaknesses/questions pointed out:

[W1] Fig. 5 mitigates the impact of the theory

On datasets like Wikitext-103, transformers trained with these tokenizers (BPE, Unigram, Wordpiece) indeed perform similarly in ablations. The purpose of this figure was to observe that the test-loss appears to decay as roughly $\propto 1/\log(|\text{Dict}|)$ agreeing with our theory (Theorem 3.1). When we generalize beyond these settings to more complex languages and more specific downstream tasks, the differences start becoming noticeable. There are many possible reasons and counterfactuals to control for in these kinds of experiments. For instance, Wordpiece appears to be worse compared to Unigram and BPE in languages which are not space-delimited like Japanese [3]. Unfortunately, these questions are at a granularity which can't be addressed by studying Markovian data models. We believe that the extensions of our work to more specific losses / different data-distributions can play a role, and help in revealing fine-grained differences between tokenizers.

[Q1] BPE succeeds because of aggregating data according to frequencies

There are plenty of seemingly “reasonable” ways in which a tokenizer may aggregate data according to their frequencies while constructing the dictionary, but which ultimately end up performing poorly. Consider the following modification of the Wordpiece tokenizer where we merge the pair of tokens which maximize $n_{t_1, t_2} / n_{t_1}^2$ (the original Wordpiece prescribes merging the maximizer of $n_{t_1,t_2} / n_{t_1} n_{t_2}$). While this tokenizer indeed seems reasonable per the above definition, it turns out that it performs quite poorly. Training on randomly generated letters from the english alphabet, the results are tabulated in Table 1 of the attached pdf.

Notice the clear a pattern in how modified Wordpiece behaves: it appears to merge the longest token in the dictionary thus far with a single character in each round. While the tokenizer “objective” itself does not prescribe this behavior, the tokenizer exhibits this trend because of the $n_{t_1}^2$ term in the denominator. This incentivizes the merge to pick a starting token ($t_1$) which has very low frequency (because of the $1/n_1^2$ term in the denominator).

Thus the behavior of tokenization / design of appropriate merge rules is a nuanced phenomenon. While there appear to be natural choices under which the intuition “tokenizer is trained to aggregate bytes according to their frequencies $\implies$learning unigram models are sufficient” is true, there are also cases where this intuition fails altogether.

On a separate note, it is not apparent how to design tokenizers which learn dictionaries with the minimal number of tokens required to achieve low loss (under unigram likelihood models). Our proofs show this is true for LZW and approximately so for a variant of BPE. Thus, these tokenizers are hard to improve on significantly (without breaking some sort of worst-case information theoretic barrier). Having a small dictionary is important for being able to learn the transformer in a data-efficient manner, and to avoid redundant tokens, which presents an attack surface.

[Q2] Model used in the experiments; Clarification of Fig. 2

In the paper, we used variants of the GPT-2 architecture as implemented in [13]. We shall add this citation to the paper. Our experiments considered variations over (i) the number of heads, (ii) the number of layers, and (iii) the embedding dimension and (iv) the dictionary size (excluding optimization hyperparameters). We shall include these in the description of figures. They are summarized in the Appendix (Table 3) due to a lack of space in the main paper.

Fig 2 clarification: Fig. 2b uses $70 \times$ fewer parameters compared to 2a. This is an argument supporting that models with tokenization do not require as many parameters to quickly achieve the optimal test-loss. This is a less important point at the scale of models we considered, which is why we do not go into too much detail, but this also translates to an improvement in wall-clock time (cf. Fig. 4 in the paper)

[Q3] What are unigram models?

Unigram models are defined on lines 114-116 in the paper. The specific model mentioned (probability of each token approximates the inverse frequency of character/token) lies in the class of unigram models we consider.

[Q4] Success of transformers beyond the unigram barrier?

Our reason for studying unigram models is not because this class of models are interesting in their own right (which one can argue for), but more so because we see that transformers empirically learn these kinds of models when trained on Markov data. This is the role of Fig. 3 (clarified in the common rebuttal). However, when the data processes grow to be more complicated than Markov models, we expect transformers to exhibit more complex behavior (beyond $n$-grams). Understanding the behavior of transformers with and without tokenization on more complex data processes is a rich direction for future work.

On a separate note, character-level tokenization does appear to work to varying degrees in practice with transformers, and this is likely because real world data is a mixture of many different data types. For certain languages (such as those containing non-concatenative morphology), removing tokenization seems to help [14]. For arithmetic, character level tokenization is known to help models generalize better [2]. But from these results, it is not clear whether these are pitfalls of existing tokenizers, or of tokenization as a whole. On arithmetic, for instance, recent models like GPT4 and LLama3 appear to chunk numbers into the range 0-999 and split longer numbers into these chunks, instead of operating at the single digit/byte level, which is in support of the argument, “Good tokenizer $\ge$ no tokenizer”.

We thank the reviewer for the constructive criticism. (references cited in the common rebuttal)

TLDR; We are happy to see how to change the wording of the title + general rhetoric of the paper in a way which fit the contributions in the paper best. Our proposed changes incorporating the reviewers’ points are discussed in the common rebuttal. In doing so, we would like to add a few points to take into consideration,

1. The tokenization objective studied in the paper (end-to-end cross-entropy loss), while seemingly obvious in hindsight, has not been the subject of any theoretical work on tokenization.

   There are several current theoretical formulations for tokenization. One viewpoint is the ability to compress the input sequence as well as possible [5],[6],[7]. Related work such as [4] considers tokenization as approximately optimizing some natural objective of the training dataset. There are two conceptual issues with these formulations,

   • These approaches study how tokenizers behave on the sequences they were trained on, which does not capture generalization.

   • These analyses look at tokenizers in isolation, rather than studying them in the context of how the end-to-end loss of the model changes.

   The current theoretical discussion around tokenization is problematic for this reason: it is straightforward to compare tokenizer A with tokenizer B by evaluating them in practice, but there is no existing theoretical formulation which allows comparing different tokenizers with each other (say, by studying their behavior against the same loss/objective). For instance, the notion of “minimum number of merges” in [4] only makes sense for merging based tokenizers, and not for tokenizers like Unigram which don’t operate by merging tokens. The end-to-end cross-entropy loss is arguably the most natural objective which can allow comparisons between the behavior of the end-to-end model.

2. Why do we not write the results as “an analysis of unigram models with tokenization”? Do transformers even learn unigram models?

   Section 2.1 and 3 of the paper are dedicated to understanding the behavior learnt by transformers when exposed to data generated from Markov processes. Prior work argues that transformers (without tokenization), when trained for many iterations, are indeed able to learn $k$-th order Markov data. In the context of these results it’s worth taking into account the fact that these models need to be trained for $10-50 \times$ the number of iterations to break past the unigram phase and learn even bigram models. See Fig. 1 of the reference [1] or Fig. 1a in the rebuttal pdf. In the presence of tokenization, Fig. 3 in our paper discusses the distributions learned in the presence of tokenization, which are observed to be close to a unigram model (see clarification in the common rebuttal).

3. What happens when transformers don’t learn unigram models?

   This is a good question, and something that our work addresses from a theoretical point of view, but in a way that can be made more explicit (see proposed changes above). With sufficiently large dictionaries, the transformer only has to learn a unigram model. What happens when the dictionaries are not this large? The main implication from the theorems in our paper is that tokenization always reduces the value of $n$ for which the transformer needs to learn $n$-gram behavior, so as to achieve near-optimal test loss. Our current theorems instantiate this result when the dictionaries are large enough so it suffices to learn unigram behavior to perform well. When the dictionary sizes are smaller, transformers with tokenization are forced to learn $n$ -gram behavior for $n > 1$ to achieve low test loss. Our results argues that tokenization allows the model to get away with learning $n$-gram behavior for values of $n \ll k$, the true order of the underlying data distribution. With tokenization, transformers can avoid learning higher-order $n$-grams, which would have otherwise been learnt in its absence.

4. What happens when transformers don’t learn $n$-gram models at all?

   $n$-gram models, while simple, do not capture the extent of the modeling power of transformers. Going beyond this requires looking at more complicated data generating processes. There are several ways to do so: the simplest extension compared to our work would be one where the transformer is trained on data generated from a mixture of many different Markov models. No single $n$-gram model captures the data well now, and it is interesting to see how transformers learn to identify what order the test data comes from and utilize the appropriate estimator. Even beyond Markov and mixture of Markov models, we may study these questions when data come from simple HMMs, where the role of tokenization may be very different.

   We hope that our work initiates a study of tokenization when transformers are trained on even richer classes of data processes. We analyze the end-to-end loss by looking at the family of models $\mathcal{F}$ transformers empirically appear to represent and prove upper/lower bounds on the cross-entropy of models in $\mathcal{F}$. Ultimately, this framework can be applied to any data process, and provides a new lens for comparing tokenizers.

Additional questions/clarifications

1. What is Q_{\\#} (j) in the unigram definition? This is the distribution over the total number of tokens $j$. This needs to be present as otherwise the distribution over token sequences does not integrate to $1$ (i.e., is not a valid probability distribution).
2. What happens when models are trained for longer in Fig. 2a: When models are trained for more iterations, they eventually learn $k$-gram behavior. However, the number of iterations required is $10-50 \times$ more (see Fig. 1 in [1] or Fig. 1a in the rebuttal pdf)
3. Figure 3 clarification: Discussed in the common rebuttal.

We thank the reviewer for the feedback. Below we address the main questions and weaknesses pointed out. (references cited in the common rebuttal)

[W1] How well do $k$-th order Markov processes extrapolate to linguistic distributions?

There are two points to mention here,

1. $k$-th order Markov processes, while not perfect, capture many elements of linguisitic distributions - when $k$ grows larger, these models capture longer-range dependencies with the past. This class of models have had a rich history in language modeling and nearly every book on language modeling studies these processes. These models have been the study of many recent works, since they present a rich test-bed of interesting phenomena. A few recent works which have appeared in the literature since submission which study the interplay of transformers with these kinds of distributions are [8],[9].
2. This data-model, while simple, captures the ability of transformers to learn $n$-gram behavior. $n$-gram features appear prominently in many domains such as NMT [10], language modeling [11] and speech/music [12] to name a few.

[W2] Results show an expected result (asymptotically optimal unigram model)

The existence of an optimal unigram model as the dictionary size grows to infinity is not the main contribution of the paper. It is easy to show that there exists “some” tokenizer which satisfies this property. In this regard, two main contributions of our paper are,

1. From a theoretical point of view, we show that the LZW tokenizer in fact lies on the pareto frontier of test-loss vs. dictionary size, when the likelihood model is a unigram model. To a lesser extent, this is approximately true for the BPE tokenizer as well. This means that the tokenizer not only asymptotically works, but non-asymptotically, the size of the dictionary cannot be reduced significantly without hurting the test-loss.
2. The tokenizer which assigns all $r$-length tokens also satisfies the property that asymptotically there exists an optimal unigram model on it. However, this is an unnatural tokenizer. We show that the above properties are true for BPE and LZW: letting the number of tokens grow to $\infty$, it is a-priori not at all obvious that on the learnt dictionaries there exists a unigram model which achieves optimal test loss. In contrast, it is easy to come up with seemingly “natural” tokenizers but no unigram model trained on these tokenizers can asymptotically achieve the optimal test loss. In the response to [Q1] of Reviewer zrKY, we provide a surprising example of such a tokenizer.

[W3] Discussion of empirical results

Here is a quick summary of the empirical results in the paper, and takeaways.

1. Fig. 2 and Fig. 4: Transformers need to be exposed to much more data to learn $k$-th order Markov models without tokenization, compared to with tokenization. Likewise, they learn more quickly wrt wall-clock time compared to in the absence of tokenization (This is true even if we select the fastest untokenized model). Takeaway: Transformers generalize better with tokenization, both in terms of number of samples as well as number of optimization iterations.
2. Fig. 3 conclusion: Transformers approximately learn unigram models when trained on tokenized sequences generated from a Markov model. Takeaway: Transformers can achieve low loss by learning conceptually simple models when tokenization is present.
3. Fig. 5 conclusion: BPE, Unigram and Wordpiece tokenizers perform similarly on Wikitext-103 with unigram models. The decay of the loss as a function of the dictionary size appears to be captured by $\propto 1/\log(|\textsf{Dict}|)$, as predicted theoretically (Theorem 3.1). Takeaway: Scaling law for tokenization (as a function of the dictionary size).

In this paper, we sought to build up a theoretical understanding of how tokenizers and transformers interact by studying their behavior on $k$-th order Markov chains. While these models are not perfect, a number of interesting empirical phenomenon can be inferred which concur with practice, even through the lens of these simple data models. More importantly, the questions and workflow considered in this paper (analyzing end-to-end loss on models learned by transformers) can be employed with more complex data processes, where transformers exhibit richer behavior. Separations between tokenizers may become more apparent here.

[Q1] $k$-th order processes considered

In the $k$-th order processes studied, the $n$-th state distribution only depends on the $(n-k)$-th state. However, our theory applies for all $k$-th order processes (as long as Assumption 3.2 is satisfied). In our experiments, we chose to compare against this restricted class of models to level the playing field between different values of $k$ (since the problem certainly becomes harder if we consider all Markov chains for increasing $k$). In the attached pdf, we plot the behavior of tokenizers on randomly chosen $k$-th order Markov processes for $k=1,2,3,4$. The gap between the tokenized and untokenized grows even more significantly as $k$ increases.

[Q3] Comparison with Edelman et al (2024) and Makkuva et al (2024)

These works show that transformers (in the absence of tokenization), when exposed to sufficiently much data, learn to represent $k$-th order Markov chains in-context for relatively small values of $k$. In practice, however, tokenization is almost always used. In our paper, we study the questions asked in these papers when transformers are trained with tokenization. Our key observations is that with tokenization, the model learns significantly more quickly, and is able to avoid going through multiple phases of learning when trained with tokenization. The general rhetoric surrounding tokenization has been negative, and our work shows that tokenization can make a big difference, even when learning simple models like $k$-th order Markov chains.