Data Mixture Inference Attack: BPE Tokenizers Reveal Training Data Compositions

Authors: jonathan  hayase
alisa  liu
yejin  choi
sewoong  oh
noah a smith
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 10:07:56

Abstract: The pretraining data of today's strongest language models remains opaque, even when their parameters are open-sourced.
In particular, little is known about the proportions of different domains, languages, or code represented in the data. While a long line of membership inference attacks aim to identify training examples on an instance level, they do not extend easily to *global* statistics about the corpus. In this work, we tackle a task which we call *data mixture inference*, which aims to uncover the distributional make-up of the pretraining data. We introduce a novel attack based on a previously overlooked source of information — byte-pair encoding (BPE) tokenizers, used by the vast majority of modern language models. Our key insight is that the ordered vocabulary learned by a BPE tokenizer naturally reveals information about the token frequencies in its training data: the first token is the most common byte pair, the second is the most common pair after merging the first token, and so on. Given a tokenizer's merge list along with data samples for each category of interest (e.g., different natural languages), we formulate a linear program that solves for the relative proportion of each category in the tokenizer's training set. Importantly, to the extent to which tokenizer training data is representative of the pretraining data, we indirectly learn about the pretraining data. In controlled experiments, we show that our attack can recover mixture ratios with high precision for tokenizers trained on known mixtures of natural languages, programming languages, and data sources. We then apply our approach to off-the-shelf tokenizers released alongside recent LMs. We confirm much publicly disclosed information about these models, and also make several new inferences: GPT-4o is much more multilingual than its predecessors, training on 10x more non-English data than GPT-3.5, Llama 3 and Claude are trained on predominantly code, and many recent models are trained on 7-16% books. We hope our work sheds light on current design practices for pretraining data, and inspires continued research into data mixture inference for LMs.

Main paper: 
 introduction: 
 Pretraining data is at the heart of language model development, yet it remains a trade secret for today's strongest models. While it has become more common for model-producing organizations to release model parameters, they rarely share the pretraining data or important details about its construction. In particular, little is known about the proportion of different languages, code, or data sources present in the data; these design decisions require extensive experimentation that few organizations have the resources to perform, and have a significant impact on the resulting LM [7, 39, 35, 38, 49, 59] . While a long line of membership inference attacks [15, 51, 43, 52, 16, 21] aim to reveal information about the model's pretraining data, they typically focus on testing whether particular instances or authors contributed to the data. In this work, we tackle a different task we call data mixture inference which, given a set of disjoint categories that cover the training data (e.g., the set of natural and programming languages), aims to uncover each of their proportions. During training, the BPE algorithm iteratively finds the pair of tokens with the highest frequency in the training data, adds it to the merge list, then applies it to the dataset before finding the next highest-frequency pair. To encode text at inference time, the learned merge rules are applied in order. The resulting order of merge rules is extremely sensitive to the proportion of different data categories present. Our goal is to solve for these proportions, a task which we call data mixture inference.To this end, we identify a previously overlooked source of information: trained byte-pair encoding tokenizers (BPE; [50] ), which are the near-universal choice for modern language models. Our key insight is that the ordered merge rules learned by a BPE tokenizer naturally reveal information about the frequency of tokens in the tokenizer's training data. During training, the BPE algorithm iteratively finds the ordered pair of tokens with the highest frequency, adds it to the merge list, and applies the merge to the dataset. Therefore, if the pair (;, \n) was merged in the 52 nd step (as is the case for GPT-4O), then it must be the most frequent pair in the data after applying the preceding 51 merges; in this case, it is a signature of substantial code data. Note that at inference-time, new text is tokenized by applying the learned merge rules in-order. Open-source models require open tokenizers; even closed models often have open tokenizers for the purpose of estimating query cost.Our method builds a linear program where the constraints are derived from the true most-frequent merge at every step in the merge list, and solves for the proportions of each category. We first demonstrate its effectiveness in controlled experiments where we train tokenizers on known mixtures of data. We consider three kinds of data mixtures: natural languages, programming languages, and data sources. Our method is highly effective, achieving accuracy between two and five orders of magnitude better than baselines based on tokenizer efficiency or inspection of the vocabulary.Then, we apply our method to infer previously unknown distributional information about off-the-shelf, commercial tokenizers (the top of these merge lists are shown in §C.2 for qualitative inspection). We consider all tokenizers released with GPT, LLAMA, and MISTRAL model families, as well as GPT-NEOX, GEMMA, and CLAUDE, which we will refer to later using their associated model names. We corroborate reported information and public intuition about these tokenizers with exact numbers -GPT-2 is trained on predominantly English (99%), GPT-3.5 is the first in the GPT family to be trained extensively on code (63%), and LLAMA trains on only languages that use Latin or Cyrillic scripts. We also make several new inferences: GPT-4O is much more multilingual than its predecessors, training on 39% non-English text, with 68 languages that make up at least 0.1% of the data. LLAMA 3 extends GPT-3.5's tokenizer primarily for multilingual use, using 48% non-English text (and 30% code data). Finally, we surprisingly infer that all tokenizers we study are trained on 7% -26% book data, potentially because books use a more standard vocabulary compared to the web.Inferring tokenizer training data mixtures has several important implications. Ideally, the tokenizer training data is representative of the LM's pretraining data [58] ; disconnects can lead to poor encoding Figure 2 : Training data mixture predictions for several commercial tokenizers. Complete results over 112 languages and 5 domains are given in §C; categories are grouped here for readability. We confirm that GPT-2 was trained overwhelmingly on English (99%), while GPT-3.5 is the first model in the GPT series to train on substantial code data (63%). GPT-4O is much more multilingual than its predecessors, with 39% of its corpus being non-English text. LLAMA is also multilingual, but focuses on languages using Latin or Cyrillic scripts (note this category in the figure excludes English). LLAMA 3 * results are only based on the last 27,744 merges (the first 100K are copied from GPT-3.5), which we observe was primarily for multilingual adaptation. of the pretraining text [2] and potential for "glitch tokens" that trigger degenerate model behavior [48, 30, 33] . Additionally, the tokenizer can be seen as a leading indicator of the model developer's priorities, as it is often designed to accommodate future models. Tokenizer training mixtures may also be used to accelerate model-based attacks, for instance by suggesting data categories to prioritize for membership inference. Finally, it can enable external auditing of training data for biases, by identifying under-represented languages or data sources. 
background: bpe tokenizers: 
 Byte-pair encoding (BPE), introduced by Sennrich et al. [50] for NLP,2 is a tokenization algorithm that learns subword-based encodings from training data. At a high level, the algorithm iteratively merges frequently co-occurring pairs of tokens until the desired vocabulary size is reached.More precisely, the training text is first pretokenized by splitting it into "words" that limit the extent of tokenization. Merges cannot bridge these words, and thus the final learned tokens will be parts of these words. Pretokenization can be as simple as splitting on whitespace, so that common sequences of words (e.g., "it is") do not become a single token.After pretokenization, the words are split into bytes, which form the starting vocabulary. Then, the BPE algorithm iteratively counts the frequency of each neighboring pair of tokens and picks the most frequent to be merged next. This merge is added to the merge list and applied to the entire text, and the merged token is added to the vocabulary. For instance, if the merge is (th, e), then all instances of the token sequence th, e will be replaced with the, which is added to the vocabulary. BPE then updates the frequencies of all pairs, and identifies the next most frequent. This continues until the desired vocabulary size is reached. At the end of training, the algorithm has learned an ordered list of merge rules m (1) , . . . , m (M ) .To tokenize new text, the tokenizer splits the text into bytes and applies the learned merge rules, in order. As we will see, the merge list reflects rich distributional information about the training data. 
data mixture inference attack: 
 Suppose we have a set of n data categories of interest, and data distributions {D i } n i=1 for each one. Then suppose we receive a BPE tokenizer, which was trained on a large sample of text from the mixturen i=1 α * i D i with non-negative weights α * ∈ R n satisfying n i=1 α * i = 1. Given corporaFigure 3 : Illustration of our method on a simple example. We know that after applying in the first t -1 merges to the training data, the t th merge must be the most common pair. More explicitly, this means that α i should give a vector in which the value corresponding to the true next merge is the maximum. Our attack collects these inequalities at every time step to construct the linear program. 3{D i } n i=1 sampled from each of the D i respectively, the goal of data mixture inference is to produce a good estimate α of α * . Now we describe how to set up the set of constraints that make up a linear program whose solution is this estimate ( §3.1), reduce the storage requirements ( §3.2), and improve efficiency ( §3.3, §3.4).We build a linear program (LP) with variables α and constraints derived using information from the tokenizer and our sample corpora. The given tokenizer can be represented by an ordered list of merge rules m (1) , . . . , m (M ) . For each time step t ∈ [M ], we apply all preceding merge rules m (1) , . . . , m (t-1) to our corpora D i and use c (t) i,p to denote how many times the token pair p occurred in the partially merged text. We know that when the tokenizer was trained, the pair m (t) was more frequent at time t than any other pair. In other words,n i=1 α i c (t) i,m (t) ≥ n i=1 α i c (t) i,pfor all p ̸ = m (t) .Collecting these constraints for all t and p defines a set of possible α's.Of course, because we only have samples from the category distributions and not the exact data the tokenizer was trained on, the above linear program may not be feasible, as the counts will include some sampling noise. To address this, we relax the constraints by introducing new non-negative variables v (t) for all t ∈ [M ], and v p for all pairs p, which represent the degree of constraint violation for each merge and pair, respectively. We replace our constraints with new ones of the formv (t) + v p + n i=1 α i c (t) i,m (t) ≥ n i=1 α i c (t) i,p for all p ̸ = m (t) .In general, we expect v (t) to be large when m (t) is over-represented in the tokenizer training data and v p to be large when p is over-represented in the mixture defined by α. This new system of constraints is guaranteed to be feasible, as the v's can be made arbitrarily large. To produce the best possible estimate, our objective is to minimize the total constraint violation M t=1 v (t) + p v p . We call the resulting linear program LP1. To estimate α, we solve LP1 and report the optimal value of α as α.As written, LP1 can be prohibitively large. If our vocabulary has size V , the total number of constraints scales like O(V 3 ) since there are O(V ) time steps t to consider and O(V 2 ) competing byte pairs p ̸ = m (t) . Additionally, there are O(V 2 ) variables v p . The first step to reduce the size is to limit t to the first T merges. We will call this truncated program LP1 T . However, even for modest choices of T , LP1 T can still have millions of variables and tens of billions of constraints. In the following sections, we will describe how to efficiently solve LP1 T using simultaneous delayed row (constraint) and column (variable) generation [12, 23] .First, as a preprocessing step, we apply the target tokenizer to each language corpus D i , recording the pair counts c (t) i,p after each merge is applied for later use. Naively, this would require a large amount of space, since the number of possible pairs p scales like O(V 2 ). However, note that c(t) i,p ̸ = c (t+1) i,ponly when p overlaps with m (t) . In other words, pairs with no overlap with the most recent merge will have unchanged counts. Thus, there are only O(V ) differences between c . In practice, the number of changes caused by a single merge is usually a few hundred at most. By saving only the incremental changes from each set of pair counts to the next, we can efficiently record the pair counts at every iteration of the tokenization process.Our plan is to solve LP1 T using only a subset of its constraints, giving a potential solution (α, v). We then check whether (α, v) violates any of the constraints of LP1 T and add any such constraints to the subset. This requires an efficient method to detect violated constraints, which we describe below.For convenience, let s (t)p := n i=1 α i c (t)i,p and recall that, for a given time step t, we want to check whether v (t) + s m (t) ≥ max p (s (t)p -v p ). Naively, we would do so by iterating over all possible p ̸ = m (t) to see if the constraint is violated, which can be quite costly. Moreover, we must do this for all t ≤ T . However, by taking advantage of the structure of the s (t) p as t varies, we can reduce our work substantially.The first step is to take each initial pair p and add it to a priority queue with priority s (0) p -v p . This can be done in aggregate in O(V 2 ) time using a fast heap building algorithm. Now, we can iterate through the pairs in descending s (0) p -v p order using the queue's delete-min operation. For each pair p, we can check whether v (0) + s (0)m (0) > s (0)p -v p and if not, we mark the corresponding constraint as violated. Once we find a p sat satisfying the constraint, we stop, since all pairs remaining in the queue must satisfy their constraints. If there were k pairs before p sat in the queue, then the total time taken is O(k log V ).Crucially, we can quickly update the priority queue to reflect the state at t = 1. Since we precomputed all count changes from c(0) i,p to c (1)i,p , we know what queue entries need to be updated or inserted. If k new new pairs were created and k old pairs had their counts changed when pair m (0) was merged, then we can update the priority queue using k new insert operations and k old decrease-priority operations, which can be done in O((k new + k old ) log V ) time. Now that we have updated the priority queue, we can repeat the above procedure to check for any constraint violations for t = 1. By iterating this process, we can quickly check for violated constraints for all t ≤ T .Now we are ready to efficiently solve LP1 T . We begin by guessing uniform proportions for α, and v (t) = v p = 0 for all t, p. Then we use our constraint checker to identify violated constraints of LP1 T and construct a lazy version of LP1 T , which we denote LP2 T , using only those constraints and the variables they contain. We then solve LP2 T , which gives us a new guess for α. We repeat the above steps, adding progressively more constraints (along with their variables) to LP2 T until we find a solution that is also feasible for LP1 T . It follows that this solution is optimal for LP1 T since the two programs share the same objective. This is guaranteed to happen eventually because there are a finite number of constraints and variables to add.In practice, the constraint violation detection can typically check T = 30000 merges in less than 10 seconds. On difficult instances, such as those for commercial tokenizers in §5, the full solve can take up to a day to complete. Easier instances like those in Table 1 can be solved in a few minutes. Table 1 : Experimental results for controlled experiments. The settings we consider are mixtures of natural languages, mixtures of programming languages, and mixtures of domains. n denotes the number of categories in the mixture, which are drawn from 112 natural languages, 37 programming languages, or 5 domains. In each cell, we report the mean and standard deviation of log 10 (MSE) over 100 trials; note that a decrease by 1 corresponds to a 10× improvement in the MSE. In addition to a Random-guessing baseline, we implement two alternative approaches to the problem: TEE (Tokenizer Encoding Efficiency) uses the tokenizer's encoding efficiency on each data category, and TC (Token Classification) assigns each token in the vocabulary to a data category based on frequency.  
experiments: 
 In our initial experiments, we train tokenizers on known data mixtures and measure the accuracy of our attack's prediction. We consider mixtures of natural languages, programming languages, and data sources (which we also refer to as domains).Because BPE tokenizers operate on bytes, we measure the proportion of each category in terms of bytes. Each tokenizer is trained on a mixture of n categories, where n varies from 5 and 112. We randomly sample the n categories and their weights from the unit simplex (using the algorithm from [53] ), and train 100 tokenizers on 10 GB of data. The data for each category is sampled from the corresponding corpus; if there is not enough data for any category (e.g., we have many low-resource languages), we duplicate the data until the necessary amount is achieved, to preserve the desired mixture ratio. We train tokenizers using the HuggingFace tokenizers library with a maximum vocabulary size of 30,000, and apply a minimal set of common pretokenization operations: we split on whitespace and only allow digits to be merged with other contiguous digits.After training the tokenizers, we apply our attack. We estimate merge frequencies for each category by sampling 1 GB of data per category, or less if there is not that much data. Note that the data used for training the tokenizer and estimating pair frequencies are sampled from the same distribution, but are not necessarily the same data. We use mean squared error to evaluate the estimated proportions,MSE := 1 n n i=1 (α i -α * i ) 2 .In practice, we report log 10 (MSE). In §B. 4 , we analyze how our attack's performance varies with the amount of data used and the number of merges T considered from the merge list.Natural Language Mixtures We use the Oscar v23.01 corpus [1] , which is based on the Nov/Dec 2022 dump from Common Crawl. We consider the 112 languages with at least 1 MB of data.Programming Language Mixtures We use the GitHub split of RedPajama [22] . To determine the programming language for each record, we map the file extension to its associated language (e.g., .py → Python). This leads to a total of 37 programming languages.We consider the following five English domains (adapted from [38] ), instantiated by data from the RedPajama dataset: Wikipedia, containing English Wikipedia dumps from Jun-Aug 2022, Web, Common Crawl data that was de-duplicated and filtered for English, Books from the Gutenberg Project and Books3 of The Pile, Code from GitHub, and Academic, which contains LaTeX files of scientific papers on ArXiv.For dataset details, e.g., the full list of categories and data sizes, please see §B.We construct two intuitive baselines: one based on tokenizer encoding efficiency and one based on analysis of tokens in the vocabulary. Neither takes the BPE training algorithm into account.Baseline based on tokenizer encoding efficiency (TEE) Intuitively, we expect data categories with greater representation in the training data to be encoded more efficiently by the resulting tokenizer. To capture this, we calculate a given tokenizer's byte-to-token ratio on each category (a more efficient tokenizer will encode more bytes per token), then normalize it by that of a reference tokenizer trained on only that category, to control for different categories being inherently easier or harder to encode. Then we learn a log-log linear model to predict each category's true proportion given the encoding efficiency. To ensure correctness, we normalize the resulting set of predictions into a probability distribution.We also consider a baseline that assigns each token in the vocabulary to a data category based on its empirical frequency in the sample data. Intuitively, we expect that if there is a large proportion of e.g., English data in the training data, then there will be more "English" tokens. For each token in the vocabulary, we count its occurrences in data sampled from each category, and assign it to the one in which it is most frequent (we find that hard assignment outperforms all variations of soft assignment). Then we count the number of tokens assigned to each category, and normalize the counts to produce an estimate of the data mixture. 1 , our attack is highly effective. Over all mixture types and values of n, we achieve mean MSE two and six orders of magnitude better than random guessing. In contrast, the baselines based on tokenizer efficiency (TEE) and token classification (VC) do not come close to the kind of precision possible with our attack, achieving at best one order of magnitude better than random.We observe that the setting with the highest attack success is mixed languages, whereas the most challenging is mixed English domains. This is perhaps unsurprising when considering the source of signal for our attack, which is the different token pair frequencies in different data categories. Intuitively, we would expect these to be very different for different natural languages, which have distinct vocabularies. In contrast, programming languages can share many syntactic features, such as using indents, curly brackets {}, and English variable names. Even more so, English data from different domains (e.g., books vs. Wikipedia) will largely share the same vocabulary but have subtle differences in token frequencies due to style, topic, and formatting. Nonetheless, even in this most challenging setting, we achieve accuracy 100× better than either baseline. 
attacking commercial tokenizers: 
 After validating our attack in synthetic experiments ( §4), we apply it to infer training data mixtures of off-the-shelf commercial tokenizers. We refer to tokenizers by the name of the model they were first released with, whose pretraining data they most likely reflect. We consider GPT-2 [47] , GPT-3.5 [45] , GPT-4O [46] , LLAMA [56] , LLAMA 3 [37] , MISTRAL [4] , MISTRAL-NEMO [6] , GPT-NEOX [13] , CLAUDE [8] , and GEMMA [55] . While many of these are closed models, their tokenizers are publicly available so that customers can estimate the cost of queries ahead of time. We note that the LLAMA, GEMMA, and MISTRAL tokenizers use characters instead of bytes as the base vocabulary for the BPE algorithm; this does not affect our attack, but we discuss the distinction in §C. 6 .In these experiments, we aim to infer the proportion of different natural languages, code, and English domains, for a total of 116 categories. We consider code as a single category (not split into separate programming languages) because some languages like Markdown and Pod6 are almost entirely English, and we do not expect the distribution of programming languages in pretraining to differ substantially from that of GitHub, the largest public code hosting platform. To infer the distribution of English domains, we replace the English category with the four English domains from §4 (web, books, Wikipedia, and academic), which we expect to approximately cover the English data.Our predictions are shown in Figure 2 , with specific numbers in §C.1. Below, we discuss our findings in comparison with publicly disclosed information about these models.All tokenizers accompanying GPT models are open-source on tiktoken. 4 There are three such tokenizers, released with GPT-2, GPT-3.5, and the very recent GPT-4O. 5GPT-2 GPT-2 was trained on WebText, consisting of text scraped from outbound links from Reddit, and filtered to be English-only. The GPT-2 tokenizer was reused for GPT-3. Indeed, we confirm the training data consists of 99.1% English. However, we surprisingly estimate that only 83.6% of the data was web, with another 15.4% being books, which were not explicitly included in WebText. In a data contamination analysis, the authors indeed report that they find books in WebText, but our estimate suggests the contamination may be deeper. We note that books were a popular source of pretraining data for early Transformer LMs, with GPT-1 being trained entirely on BooksCorpus [63] .The GPT-3.5 family of models is known to depart from its predecessors by training on large amounts of code: the first model in this family was code-davinci-002, trained on text and code. In fact, some evidence suggests that GPT-3.5's large leap in reasoning abilities comes from this code data, which intuitively requires similar procedural skills [26] . The GPT-3.5 tokenizer was reused for GPT-4.Indeed, we estimate that GPT-3.5 is trained on 62.6% code. In the domain breakdown, 27.3% is of the data is web, 6.8% books, and 0.2% academic articles. The substantial representation of books (though lower than GPT-2) is consistent with findings that this model has memorized a wide collection of copyrighted books [20] .GPT-4O GPT-4O is a multimodal model announced as more multilingual than its predecessors; its tokenizer achieves a better compression rate on non-English languages, and the model has notably better non-English performance.Our findings support this. GPT-4O is trained on 39.0% non-English text, compared to only 3.2% for GPT-3.5. The language distribution has a thick non-English tail, with 68 languages that make up at least 0.1% of the data: the most common are French (2.9%), Russian (2.8%), Spanish (2.8%), Portuguese (2.3%), Dutch (2.0%), German (1.8%), Arabic (1.6%), and Hindi (1.4%). Additionally, GPT-4O was trained on 7.4% books.LLAMA The training data for LLAMA is known to be primarily English, though the Wikipedia split "covers 20 languages which use either the Latin or Cyrillic scripts: bg, ca, cs, da, de, en, es, fr, hr, hu, it, nl, pl, pt, ro, ru, sl, sr, sv, uk". The training data is reportedly sourced from Common Crawl (67% of examples), C4 (15.0%), Github (4.5%), Wikipedia (4.5%), Books (4.5%), ArXiv (2.5%), and StackExchange (2.0%). The LLAMA tokenizer was reused for LLAMA2.We corroborate that LLAMA is indeed primarily made up of the stated languages; when combined with code, this sums to 95.7% of the training corpus. Indeed, other generally high-resource languages, such as Chinese, Arabic, and Hindi, have 0.0% representation. However, we predict a very different domain distribution compared to what is reported in the paper for LLAMA's pretraining data. We predict that the tokenizer is trained on 23.1% books, 11.3% web, 6.7% Wikipedia, and 8% ArXiv. The high representation of books is surprising -we hypothesize that the tokenizer was trained on a different distribution than the LM, primarily focusing on books which uses a more standard vocabulary compared to web data.LLAMA 3 We observe that LLAMA 3, rather than training a new tokenizer, extends GPT-3.5's merge list (of 100,000 merges) with an extra 27,744 merges. Thus, we apply our attack to these new merges to infer what data was used to extending the LLAMA 3 tokenizer. It is reported that LLAMA 3 is trained on more than 5% of "high-quality non-English text that covers over 30 languages." We find that LLAMA 3 is extended with primarily non-English text (48.5%) and code (30.2%), indicating that the goal of extending GPT-3.5's tokenizer was primarily for multilingual use.MISTRAL MISTRAL models "handle English, French, Italian, German and Spanish" [5] ; indeed, we find that these are the top five languages in the training data. There is a long tail of other languages, but they predominantly (97%) use either the Latin or Cyrillic script.MISTRAL NEMO In contrast, MISTRAL NEMO was "designed for global, multilingual applications, bringing frontier AI models to... all languages." It introduces a new tokenizer (based on tiktoken instead of sentencepiece), which is the most multilingual of tokenizers we study, training on 46.6% non-English text. French (6.3%) and Arabic (4.8%) are the most common non-English languages.The tokenizer of GPT-NEOX [14] was trained on the Pile [29] with "certain components... upsampled." It is popularly re-used in open-source model development, including by OLMO [31] , PYTHIA [13] , and DCLM [34] . Though our domains do not map neatly onto the constituent datasets of the Pile, our inference is generally consistent, with a prediction of 43.7% web, 26.3% books, 12.1% academic, 15.2% code, and 2.7% non-English text.GEMMA [55] is reported as training on "primarily-English data from web documents, mathematics, and code." Gemma uses a subset of the Gemini tokenizer; we believe it is likely that this subset was obtained by truncation, which would make our inferences valid for Gemini as well. We predict that GEMMA is trained on 45.7% English, which comes from 25.6% web, 12.8% books, 4.3% academic, and 3.0% Wikipedia. It is also trained on 28.4% non-English text, which explains its large multilingual vocabulary of 256,000 tokens. However, compared to GPT-4O, the multilingual representation is more skewed toward languages that use Latin or Cyrillic scripts.Very little is known about models from the CLAUDE family, but a remark in the Anthropic SDK suggests that CLAUDE 1 [8] and 2 [9] share the same tokenizer, which is open-source, while CLAUDE 3 [10] uses a different (closed) tokenizer. Our attack predicts that CLAUDE was trained on 57.5% code, 38.8% English, and 3.7% other languages. Moreover, half of its data (17.4% overall) comes from books, with substantial contribution from Wikipedia (3.7%) and academic text (5.1%) as well. The lack of multilingual training data likely explains why a new tokenizer was trained for CLAUDE 3, which boasts "increased capabilities... in non-English languages" [10] .6 Robustness analysis 6.1 Is the attack robust to distribution shift?We measure the impact of using out-of-distribution data instead of data from the tokenizer's training distribution to count merge frequencies. Note that in the main experiments, we show that the attack is effective at separating English domains, so performance degradation under distribution shift is expected. To empirically measure this, we train tokenizers on mixtures of n = 10 languages using web data from Oscar, but estimate merge frequencies using corresponding language splits of Wikipedia, a substantially different domain. Using the same settings as the main experiments ( §4), we achieve log MSE of -3.53, compared to -7.66 with no shift. Thus, the attack performance drops considerably under this extreme distribution shift, while remaining 100× better than random.6.2 Is the attack robust to unaccounted-for categories? Figure 4 : Performance remains much better than random even with large amounts of unknown data.In a typical attack setting, the attacker may not have explicitly accounted for every source of data used to train the tokenizer. To show that our approach is robust in the presence of such data, we modify our n = 112 languages experiment from our main experiments ( §4). We randomly withhold a random subset of 1 to 50 languages from the solver and measure the resulting prediction error on the remaining languages. Results are shown in Figure 4 . Although the performance of our method does worsen as the amount of unknown data increases, the predictions remain substantially better than random. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: We state our choices for all parameters in the experiment sections ( §4, §5) and provide analysis of how performance varies with these parameters in §6.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
related work: 
 Attacks on LMs Membership inference, the task of inferring whether a particular example was part of the training data, has been studied in great depth for language models [15, 17, 40, 42, 24, 51] . Attacks commonly use model-assigned probabilities, potentially with another reference model, to make an inference. The problem remains extremely difficult, with a recent survey finding that many attacks perform near random when pretraining data is deduplicated, as in common practice [24] .Closely related to this, some memorization attacks aim to extract memorized examples from the pretraining data via prompting attacks [18, 44] . Recently, there has even been progress in recovering the parameters of black-box LMs through model stealing attacks [25, 19] .In contrast to membership inference, distribution inference is concerned with inferring global properties of a model's training data, but has not previously been studied for LM pretraining data. In early works, these attacks were successful against machine learning classifiers [11, 28] , CNNs [54] , and GANs [62] . More recently, some works show that multi-party machine learning can leak property information such as which authors contributed to the data [41, 61] . All previous distribution inference attacks take a meta-classifier approach, where models are trained on datasets with different properties, then a meta-classifier is trained using those models.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: We report the standard deviation of all of our results, as well as random baselines.Guidelines:• The answer NA means that the paper does not include experiments. • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
conclusion: 
 In this work, we present a data mixture inference attack that solves for the distributional make-up of a tokenizer's training data, which is commonly representative of the language model's pretraining data. Beyond the properties we study, we believe there is still a wealth of information hidden in tokenizer merge lists. This can shed light on the secretive and often contentious design decisions surrounding pretraining data today, potentially enabling external auditing for safety, copyright issues, and distributional biases. We hope our work will inspire continued research into inferring more global properties of training data, for tokenizers and language models more generally.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We discuss this in §B.2.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/ EthicsGuidelines? 
 
 Appendix: We discuss some possible approaches for defenses to our attack.Post-hoc changing the order of merge rules Model producers may consider changing the order of merge rules, which is the source of signal for our attack, after the tokenizer is trained. However, naively re-ordering merge rules for a tokenizer would be damaging, as it can lead to unfamiliar encodings of words as well as entirely unreachable tokens. The only functionally-equivalent reordering would be within contiguous sections of merge rules, where each token appears exclusively on the left or right side of all merges it appears in. In this case, we can easily adapt our method by working at the level of contiguous non-conflicting sections instead of individual merge rules, as we know that each section has higher frequencies than the next.Hiding pretokenization rules Our method relies on a reasonable reconstruction of the pretokenization rules, which control what kinds of merge rules are considered. It is not necessary to share pretokenization rules, as they are not strictly necessary for inference. However, we find that important pretokenization rules (like whether to pre-tokenize on spaces, digits, and punctuation) are easy to infer from manual inspection.Not using BPE tokenizers Model producers may choose to forgo BPE tokenizers entirely in future models. Despite the current popularity of BPE, there is a lively area of research into alternative methods of tokenization [57, 60, 36, 3] . While we only explore BPE tokenizers in this paper, it is plausible that any tokenizer learning algorithm will leak information about its training data, as they are specifically developed to best encode the given data. Figure 5 : Relationship between a language's proportion in training and the resulting tokenizer's encoding efficiency on that language, shown for mixtures of n = 10 languages. The encoding efficiency is defined as the byte-to-token ratio of a given tokenizer on a given language, normalized by that of a tokenizer trained only on that language. While more training data leads to better encoding efficiency, the correlation is not strong enough to recover a prediction nearly as precise as our attack.A baseline based on this relationship achieves log 10 MSE of -2.22, compared to our attack's -7.66. new tokenizers considering only categories with at least 10 GB of data available. For our attack, we compare sampling 1 MB, 10 MB, 100 MB, 1 GB, and 10 GB of data for each category, and use T = 3000 merges. Shown in Figure 6 , more data consistently improves the accuracy of predictions.Next, we investigate how performance scales with the number of merges T that we apply from the merge list. Using the same 100 tokenizers from §4, we solve for the data mixture using various choices of T ∈ [30, 30000] . Shown in Figure 7 , we find that when there are more categories, it is useful to consider more merges. This makes sense because more constraints may be needed to bound the solutions in higher dimensions.Here, we repeat the distribution shift experiments in §6.1 while varying the amount of data and merges used. Shown in Figure 8 and Figure 9 , we find a U-shaped curve for how performance scales with the amount of data used for calculating pair frequencies, unlike our main experiments in §4. In this section, we provide more detailed results and discussion of commercial tokenizers.We report the full inferences for commercial tokenizers ( §5) over 116 categories (111 languages, 4 English domains, and code) in Table 4 .We show the first 50 merges of the commercial tokenizers we study in Table 2 for qualitative inspection.We observe that the merge list of LLAMA, LLAMA 3, GEMMA, and MISTRAL contain clusters of redundant merge rules. For instance, in the LLAMA 3 merge list, we see the sequence of merges _ the, _t he, and _th e, as well as _ and, _a nd, and _an d. Because the merge path for every token is unique, it is impossible for more than one of these merges to ever be used, and we empirically verify this by applying the tokenizer to a large amount of text.We find that this is an artifact of the conversion from sentencepiece to Huggingface tokenizers format. To construct the merge list, the conversion algorithm naively combines every pair of tokens in the vocabulary, and then sorts them by token ID, which represents order of creation. While this is functionally correct, because the redundant merges are not products of the BPE algorithm (i.e., they do not actually represent the most-likely next-merge), we need to remove them for our algorithm. To do this, we do some simple pre-processing: for every cluster of redundant merges, we record the path of merges that achieves each merge; the earliest path is the one that would be taken, so we keep that merge and remove the rest.As an aside, this means that a tokenizer's merge list can be completely reconstructed from its vocabulary list ordered by token creation. Given only the resulting token at each time step, we can derive the corresponding merge.We notice that the first 1,395 merges in GEMMA consistent entirely of merges of consecutive \n, followed by merges of consecutive \t, and finally merges of consecutive whitespace characters _. They appear to be placed there manually and are not organically learned by the BPE algorithm, and do not correspond to increasing vocabulary IDs. Therefore, we remove these merges so that the remaining ordered merge rules align with monotonically increasing vocabulary ID.We note that LLAMA and GEMMA, the two other tokenizers based on sentencepiece, also contain manually inserted merges of whitespace, but at the end of the merge list instead of the top. Since they are not within the top T = 30, 000 merges we consider, we do not do any special pre-processing.While GPT tokenizers are open source on tiktoken, they are not released in a format compatible with HuggingFace tokenizers. We used the tokenizers-compatible files uploaded by a HuggingFace user named Xenova. For instance, the GPT-4O tokenizer can be found at https://huggingface. co/Xenova/gpt-4o.The LLAMA and GEMMA tokenizers are trained with the sentencepiece library, which uses the same BPE algorithm, except the units of the base vocabulary are characters rather than bytes. In other words, the merge rules learned will apply to pairs of character sequences instead of byte sequences. While byte-level tokenizers always start with the same base vocabulary of 256 bytes, character-level tokenizers determine the base vocabulary using a character coverage hyperparameter (usually set to ∼0.9995), which determines what proportion of characters that appear in the training text will be in the base vocabulary. Byte fallback is used to represent the out-of-vocabulary characters using bytes.To empirically test our attack on character-level BPE tokenizers, we train 100 sentencepiece tokenizers on mixtures of n = 10 natural languages. We apply our attack using the top T = 3000 merges, but otherwise use the same settings as §4.With character-level tokenizers, we achieve an average log MSE of -4.09 compared to -1.39 for random guessing and -7.65 for byte-level tokenizers. That is, character-level tokenizers are harder for our algorithm to reverse than byte-level tokenizers! We believe this is because different languages have widely varying numbers of characters in their writing systems. For languages with many characters, their merges will appear lower in the merge list due to their lower average frequency compared to languages with fewer characters. This leads to a bias in representation among the first T merges considered by our approach.We observe that in sentencepiece tokenizers, after going deep in the merge list (about halfway), the merges begin forming groups, in which the length of the merge is ordered from shortest to longest. We trace this to how ties in pair counts are broken in sentencepiece, which is by length of the merge. In terms of reverse engineering, this points to a way to infer the size of the tokenizer training data, since exact ties in frequency become less likely as more training data is considered. We leave this direction to future work.Table 2 : Top 50 merges of commercial tokenizers we study. For LLAMA 3 * , because the first 100K merges are borrowed directly from GPT-3.5, we show the top 50 merges after that. For readability, we replace the space token Ġ with _ and the newline Ċ with \n. To a careful observer, there are many interpretable signatures of training sources. For instance, consecutive whitespace is common in code, as indents are equivalent to four spaces by most coding standards. Indeed, _ _ is the first merge of all tokenizers that consider merges of whitespace except GPT-2 (see §C.4 for relevant discussion). The merges ; \n, _ =, and sel f are also common token pairs in code. The odd-looking symbols are encodings of bytes that make up parts of single characters in many languages. For instance, à ¤ is the prefix for characters in the first half of the Devanagari Unicode block (used for writing Hindi, Nepali, Sanskrit, among others), Ð °encodes the Cyrillic "a" (used in e.g., Russian), and á ĥ encodes the prefix for the second half of the Georgian Unicode block. Justification: We publicly release our code at https://github.com/alisawuffles/tokenizer-attack.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Justification: To the best of our knowledge, we conform to the Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.Though, it originated in 1994 in the field of data compression[27].Technically, the elements of the vectors should be normalized by size of the language data, but in this case they are the same for the two languages so we show the unnormalized counts for readability.https://github.com/openai/tiktoken/blob/main/tiktoken/model.pyTechnically GPT-3's tokenizer has a distinct identifier from that of GPT-2, but it differs only in 24 extra tokens at the end of the vocabulary; these tokens are made up entirely of spaces. Indeed, the GPT-3 technical report states that it "reus[ed] the tokenizer of GPT-2." 


Decision: This paper presents a method for inferring the data mixture a model's tokenizer has been trained on. Specifically, by formulating a linear program based on the BPE merges a good approximation of the tokenizer training corpus can be retrieved. While the tokenizer training corpus might be different from the LLM pretraining corpus, these two are usually a similar/identical mixture, hence providing interesting information about model pretraining.

To the reviewers' and my understanding, this work is novel. It is also interesting, useful, evaluated well, and technically sound. Hence I recommend that this paper is accepted.

Reviews: review: paper_summary: paper_summary: The paper "Data Mixture Inference Attack: BPE Tokenizers Reveal Training Data Compositions" presents a significant contribution to the field of machine learning by introducing a novel attack called "data mixture inference." This attack aims to uncover the composition of pretraining data used in language models (LMs), an aspect often kept secret even when the model parameters are open-sourced. By leveraging information from byte-pair encoding (BPE) tokenizers, a common component of modern LMs, the authors successfully infer the proportions of different domains, languages, or code in the training data.
strength_weakness: strength_weakness: 1. The attack is specifically designed for BPE tokenizers, which, while widely used, are not the only tokenization method. The authors acknowledge this limitation and suggest that other tokenization algorithms might also leak information about training data, but the generalizability of the attack to other tokenization methods is not explored in this work.

2. The attack's reliance on sampling and estimation of pair frequencies could lead to false positives or negatives, especially when dealing with low-resource languages or domains. The paper does not provide a detailed analysis of the attack's robustness to such sampling errors.
questions: questions: 1. The central idea of your paper relies on the fact that the pretraining data was used to train the tokenizer, with the proportions of available data determining the merge rules. However, what happens if a similar domain dataset is used to train the tokenizer with different proportions than those used during pretraining? For instance, if the tokenizer is trained with 40% coding, 40% English, and 20% non-English data, but the pretraining data proportions are 20% coding, 50% English, and 30% non-English, how would this affect the effectiveness and accuracy of your data mixture inference attack? Have you considered or tested such scenarios in your experiments?

2. What are the implications of knowing the composition of the pretraining data? Specifically, what types of attacks could this knowledge facilitate, and what are the general implications of data mixture inference? Why is it important to answer the question of data mixture inference? If your paper addresses these points, please elaborate on how this knowledge could impact the security and integrity of language models. Because by just knowing the broad mixture categories and their weights, it doesn't allow for targeted data poisoning. But it seems it can be a stepping stone for building a sophisticated attacker. Would like to have your thoughts on the same?
limitations: limitations: Yes
paper_summary: paper_summary: In this paper, the authors studied inference attack on large language models’ (LLM) tokenizer. In particular, they proposed an attack to inference training data sampling weight used to train tokenizer of LLMs, which usually is also the same sampling weight used to train the LLMs. They formulated their attack as a very large linear programming problem and proposed efficient methods to reduce the size of the linear programming and hence efficiently solve it. Moreover, they evaluated the proposed attack on tokenizers with known training data sampling weights and also some commercial LLMs.
strength_weakness: strength_weakness: I listed a few directions that I think the paper can be improved.
1. Theoretical analysis in this paper is a bit weak. The proposed algorithm in Section 3 does not provide convergence guarantee.  No upper bound provided for the size of the subset of constraints that are violated.  No analysis provided to support that the iterative process will finally provide an $\alpha$ that violate no constraints in LP1.
2. The attack implicitly assumes that one can access the corpus with similar words distribution as the pre-training datasets. However, it is unclear to me how different preprocessing techniques may affect the words distribution of the pre-training dataset and thus the effectiveness of the attack. It will be good to at least exam this impact via numerical experiments.
questions: questions: 1. Pretokenization and the starting vocabulary seems to be very influential on the effectiveness of the proposed algorithm. In this case, how to find a good starting vocabulary/protokenization results?
2. The formulation and Figure 3 assume that the token frequency distribution is proportion to the sampling weight $\alpha_i$, which further assumes that the corpus token frequency is somehow equally distributed across the corpus. Does that make sense? Can we empirically verify these assumptions? Do we need a very large corpus so that these assumptions hold true?
3. How does the vocabulary size, size of the data and number of merges $T$ affect the time the attack requires to run?
limitations: limitations: NA
paper_summary: paper_summary: This paper proposes a novel data mixture inference attack to uncover the distributional makeup of pretraining data for large language models. By leveraging the ordered vocabulary learned by byte-pair encoding (BPE) tokenizers, the authors formulate a linear program to infer the relative proportions of different data categories (e.g., languages, programming languages, data sources) in the tokenizer's training set.
strength_weakness: strength_weakness: 1.	The attack relies on the specific behavior and structure of BPE tokenizers, which limits the generalizability of the method to different tokenizers.
2.	The attack hinges on the representativeness of tokenizer training data and the quality of sample data (from the same distribution in the paper), which may not always hold.
questions: questions: 1.	What the meaning of random guessing? Are there alternative methods to infer the proportions of different categories, possibly leveraging model performance metrics or behavioral patterns? 
2.	What strategies can be employed to ensure the quality of sample data for estimating pair frequencies.
limitations: limitations: Yes
paper_summary: paper_summary: This paper introduces the task of  data mixture inference, i.e. trying to infer what kind of data (e.g. languages, code) a given LLM is trained on. They do so by leveraging the ordered merge rules learned by the LLM's BPE tokenizer. First, they formalize the problem. Next, authors propose a neatly explained solution using linear programming, with multiple computational optimizations which makes the inference feasible in practice. They then apply their method to a controlled setup, against models for which the data mixture is known and show that their method reaches a significantly better performance than random guessing. Lastly, they apply their method to widely used LLMs for which the mixture is not known and provide their inference results.
strength_weakness: strength_weakness: - Originality: NA
- Quality: From an experimental perspective, authors should provide a more sophisticated baseline than random guessing. Only then will the superiority of the proposed method become clear. Also, authors could elaborate more on potential defenses against the attack (see questions).
- Clarity: NA
- Significance: A more elaborate discussion on potential defenses would increase the significance of the work's contribution.
questions: questions: - When I think about the relevance of the findings represented in the paper, I believe that this mostly exposes a vulnerability to discover fundamental design decisions used by model developers, which they likely want to keep proprietary. From that perspective, could authors elaborate more on potential defenses and how they could perform? For instance, I do not fully understand why post-hoc re-ordering of the merge rules would hurt the utility of the tokenizer (maybe you can show this?). And if this is not a viable option, is the only defense then to not reveal any details on the tokenizer?
- While the task at hand is novel, the only baseline considered (random guessing) is rather naïve. Could you include results of more elaborate baselines (e.g. leveraging the encoding efficiency of the tokenizer for each data sample? Or for the open source models, leveraging the perplexity of the model computed on the data samples)? This would shed more light into how difficult this problem might be and how valuable the proposed linear programming attack and its computational optimizations truly are. 
- One assumption that is made throughout the paper is that the attacker knows all potential data sources to include. Could you add an experiment on how the MSE changes when not all data sources are known (eg not including X natural languages, and have an increasing fraction of 'other data')?
limitations: limitations: Authors should elaborate more on the potential defenses against this attack.

Comments: title: Thank you for the response
Answer to Rebuttal
Thanks!
Answer to rebuttal
comment: Thank you authors for the response. After reading the response and other reviewers' comments, I decide to keep the original score unchanged.
Thank you for your response, which addressed my concerns. I have raised the rating from 3 to 5.
I think the authors answered most of my questions. Regarding theoretic analysis part, it is a bit weak, but overall the proposed idea is still novel and this type of attack is very interesting. I will keep my score.
Thank you for your response, and including additional results. I think this is a solid paper, with a novel and interesting problem statement and elaborate and convincing experimental results.  

I just bumped up my score to a 7. Hope it gets accepted.