Data Mixture Inference Attack: BPE Tokenizers Reveal Training Data Compositions
Authors: Jonathan Hayase
Alisa Liu
Yejin Choi
Sewoong Oh
Noah A. Smith
Venue: NeurIPS 2024 poster (2024)
Keywords: tokenizers
distribution inference
security
Primary area: natural_language_processing
TL;DR: We infer the training data mixtures of tokenizers from their merge lists.

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.

Data Mixture Inference: What do BPE Tokenizers Reveal about their Training Data?
"Jonathan Hayase
9 * Alisa Liu
Yejin Choi
Sewoong Oh Noah A. Smith 9
T University of Washington Allen Institute for Al
{ {jhayase, alisaliu)@cs washington edu
Abstract
The pretraining data of today's strongest language models is opaque; in particular, little is known about the proportions of various domains or languages represented. In this work, we tackle task which call data mixture inference, which aims uncover the distributional make-up of training data. We introduce novel attack based on 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 list of merge rules learned by a BPE tokenizer naturally reveals information about the token frequencies in its training data. Given a tokenizer's s merge list along with example data for each category of interest, we formulate a linear program that solves for the proportion of each category in the tokenizer's training set. controlled experiments, we show that our attack recovers mixture ratios with high precision for tokenizers trained on known mixtures of natural languages, programming languages, and data sources. We then apply our approach off-the-shelf tokenizers released with recent LMs. We confirm much publicly disclosed information about these models, and also make several new inferences: GPT-40 and MISTRAL NEMo's tokenizers much more multilingual than their predecessors, training on 39% and 47% non-English language data, respectively; LLAMA 3 extends GPT-3.5's tokenizer primarily for multilingual (48%) use; GPT- 3.5's and CLAUDE'S tokenizers are trained on predominantly code (~60.). We hope work sheds light current design practices for pretraining data, and inspires continued research into data mixture inference for LMs!"
1 Introduction
Pretraining data is at the heart of language model development, yet it remains trade secret for today's 's strongest models. While has become more common for model-producing organizations to release model parameters, they rarely share the pretraining data 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 long line of membership inference attacks [5 51
43
52
16
21
aim to reveal information
about the model's 's pretraining data, they typically focus on testing whether particular instances or authors contributed to the data. In this work, we tackle different task we call data mixture inference which, given set of disjoint categories that cover the training data (e-g., the set of natural and programming languages), aims uncover each of their proportions.
"Equal contribution, ordered alphabetically.
"oode and detailed inferences available at http://///tttiiooaaaaaaaaaaaaaae
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

u English En
Python Dp
Normalize the digits, then ensure that they sum to 1.
x = nogits.softmal
get probs
assert sum item() = 1 # compare
mixture ratios
D Py
D Py
D En
D En
Given data, BPE learns ordered list of merge rules
1
t
1
(
Given ordered merge rules, can we solve for the mixture ratios?
2
_t h
2
1 t
3
th
3
t
4
s u
4
merge list
5
i
5
#
()
6
The learned merge list is sensitive to the mixture ratios!
Figure 1: Illustration of our problem statement on a simple example where two tokenizers are trained on different mixtures of English and Python data. 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 applics the merge to the dataset. Therefore, if the pair (;, \n) was merged in the 52nd step (as is the case for GPT-40), then must be the most frequent pair in the data after applying the preceding 51 merges; in this case, it is signature of substantial code data. Note that at inference-tine 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 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 magninude better than baselines based tokenizer efficiency 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 CC2 for qualitative inspection). We consider all tokenizers released with GPT, LLAMA, and MISTRAL model families, as well as 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 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-40 is much more multilingual than its predecessors, training on 39% non- oon-English text, with 68 languages that make up at least 0.1% 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
more standard vocabulary compared 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

---

99
GPT-2
Mistral
GPT-35
Mistral NeMo
82
GPT-40
GPT-NeoX
Liama
Claude
Proportion
0.6
58
28
19
18
27
25
22
14
English
Code
Languages with
Other languages
Latin + Cyrillic scripts
Figure 2: Training data mixture predictions for several commercial tokenizers. Complete results over 112 languages and 5 domains are given in SC 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 substantial code data (63%). GPT-40 is much more multilingual than its predecessors, with 39% of its corpus being non- non-English text. LLAMA is also multilingual, but focuses languages using Latin 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] Additionally, the tokenizer can be seen as leading indicator of the model developer's priorities, it is often designed 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.
2 Background: BPE tokenizers
Byte-pair encoding (BPE), introduced by Sennrich al. [50] for NLP is tokenization algorithm that learns subword-based encodings from training data. At 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 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 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 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 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 training, the algorithm has learned an ordered list of merge rules m!...... 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 set of n data categories of interest, and data distributions (Dr}e,, for each one. Then suppose receive BPE tokenizer, which trained a large sample of text from the mixture Dne D; with non-negative weights a* E R satisfying Σi= of = 1. Given corpora
"Though, it originated in 1994 in the field of data compression 27

---

English
Spanish
max
This is English.
Esto es español.
Merge List
lm
C En
3 030000 + a [0001 2]
Th hi is Es to
Th is E1
C2
max
2 1
CC En
130000] + a 100011111 Th IS E1 ST
Th hi is Es to
Figure 3: Illustration of our method simple example. We know that after applying in the first t- merges to the training data, the hhh merge must be the most common pair. More explicitly, this means that O; should give 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
{Dr)_= sampled from each of the D; respectively, the goal of data mixture inference is to produce good estimate à of a*.
Now we describe how set up the set of constraints that make up linear program whose solution is this estimate $3.1. reduce the storage requirements (33.2). and improve efficiency ($.3) $3.4).
3.1 Data mixture inference via linear programming
We build a linear program (LP) with variables a and constraints derived using information from the tokenizer and our sample corpora. The given tokenizer can represented by an ordered list of merge rules m2),,.. ,..., (M)) For each time step / [M], we apply all preceding merge rules (t) m²)).... (t-1) to our corpora D; and use Cip to denote how many times the token pair occurred in the partially merged text. We know that when the tokenizer trained, the pair m()) was more
frequent at time i than any other pair. In other words,
(2) (.m
(t) ag
for all + (t)
Collecting these constraints for all t and defines a set of possible a'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 (() for all & [M]. and vp 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 form
(1 + Up + Σ
for all p + mt)
O S.P
In general, we expect (1) to be large when (9()) is over-represented in the tokenizer training data and Up be large when p is over-represented in the mixture defined by a. 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 minimize the total constraint violation ΣM e(()) Ep dp. We call the resulting linear program LP1. To estimate a, solve LP1 and report the optimal value of a as â.
As written, LP1 can be prohibitively large. If our vocabulary has size V, the total number of constraints scales like O(V3) since there are O(V) time steps to consider and O(V2) competing byte pairs * (t), Additionally, there are O(V2) variables Up- The first step reduce the size is to limit / to the first merges. We will call this truncated program LP1r. However, even for modest choices of T. LP1r can still have millions of variables and tens of billions of constraints. In the
'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 show the unnormalized counts for readability.

---

space, since the number of possible pairs p scales like O(V2). However, note that (1) when p overlaps with (+) In other words, pairs with no overlap with the most recent merge will have unchanged counts. Thus, there are only (VV) differences between o. and c,, c(t++)), In practice, the number of changes caused by single merge is usually few hundred at most. By saving only the following sections, we will describe how to efficiently solve LP1y using simultaneous delayed row (constraint) and column (variable) generation [2] 23
3.2 Efficient storage of pair counts
First, as preprocessing step, we apply the target tokenizer to each language corpus D,, recording the pair counts 4,p
(t) after each merge is applied for later use. Naively, this would require a large amount of
Cip * ( only
incremental changes from each of pair counts to the next, we can efficiently record the pair counts at every iteration of the tokenization process.
3.3 Efficient constraint violation detection
Our plan is to solve LPir using only a subset of its constraints, giving a potential solution (a, v). We then check whether (a, v) violates any of the constraints of LP1r and add any such constraints the subset. This requires an efficient method to detect violated constraints, which we describe below.
(t) and recall that, for a given time step 4, we want to check For convenience, let (t) := Σi= Cae
whether o(()) + (t) m((e) 2 maxp(5p -p)) Naively, we would do so by iterating over all possible p * (*) 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 sp as varies, we can reduce our work substantially.
The first step is take each initial pair p and add it priority queue with priority 8p Up- This be done in aggregate in O(V2) time using fast. heap building algorithm. Now, we can iterate through the pairs in descending sp Up order using the queue's ' delete-mi operation. For each pair p. we can check whether (0) + s (n > 8p Up and not, we mark the corresponding constraint as violated. Once we find a Psat satisfying the constraint, we stop, since all pairs remaining in the queue must satisfy their constraints. If there were k pairs before Psat in the queue, then the total time taken is O log V).
(0)
(0)
Crucially, we can quickly update the priority queue reflect the state at t 1. Since we precomputed all count changes from (0) to c.p we know what queue entries need to be updated or inserted. If
knew new pairs were created and kold pairs had their counts changed when pair m was merged, then we can update the priority queue using knew insert operations and kiad decrease-prioris operations, which can be done in O ((knew + kold log V) time. Now that we have updated the priority queue, we can repeat the above procedure to check for any constraint violations for = By iterating this process, can quickly check for violated constraints for all f T.
3.4 Lazy variable and constraint generation
Now we are ready to efficiently solve LP1r. We begin by guessing uniform proportions for a, and ((t)) = Up = 0 for all t.p. Then we use our constraint checker to identify violated constraints of LP17 and construct lazy version of LP1r, which we denote LP2T, using only those constraints and the variables they contain. We then solve LP2r, which gives us new guess for a. We repeat the above steps, adding progressively more constraints (along with their variables) to LP2, until we find a solution that is also feasible for LP1y. It follows that this solution is optimal for LP1, since the two programs share the same objective. This is guaranteed to happen eventually because there are 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 [S5] the full solve can take up to day to complete. Easier instances like those in Table I can be solved in a few minutes.
5

---

Table 1: Experimental results for controlled experiments. The settings we consider mixtures of natural languages, mixtures of programming languages, and mixtures of domains. n denotes the number of categories in the mixture, which drawn from 112 natural languages, 37 programming languages, or 5 domains. In each cell, we report the mean and standard deviation of log (MSE) over 100 trials; note that a decrease by corresponds to 10x improvement in the MSE. In addition baseline, we implement two alternative approaches to the problem: TEE
to a Random-ggestt (Tokenizer Encoding Efficiency) uses the tokenizer's 's encoding efficiency on each data category, and TC (Token Classification) assigns each token in the vocabulary to data category based on frequency.
Method Languages
Code
Domains
Random
-1.39
-1.39
-1.39.10.6
TEE
-2.0210.41
-0.44
-1.6910.29
5
TC
-2.1240.49
-1.92+0.36
-1.6440.35
Ours
-7.30
-6.46.0.79
-3.74_0.94
Random
-1.8440.23
-1.84
TEE
-2.2940.26
2.59
10
TC
-2.55.0.36
2..8
Ours
-7.6641.01
6.30040.41
Random
-2.70+0.13
-2.70+0.13
TEE
-3.07=0016
-3.15+0.13
30
TC
-3.4240.23
-0.3840.20
Ours
-7.73+1.12
-5.98
Random -3.82+0.07
TEE
-4.15+0.08
112
TC
-4.46-00.2
Ours
-7.69
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).
4.1
Setup
Because BPE tokenizers operate on bytes, we measure the proportion of each category in terms of bytes. Each tokenizer is trained on mixture of n categories, where varies from 5 and 112. We randomly sample the n categories and their weights from the unit simplex (using the algorithm from (3), and train 100 tokenizers on 10 GB data. The data for each category is sampled from corresponding corpus; if there is not enough data for any category (e.g., we have many low-resource languages), we duplicate the data until necessary amount is achieved, to preserve the desired mixture ratio. We train tokenizers using the HuggingFace tokenizers library with maximum vocabulary size 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 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
(ā= 22 practice, we report log.o (MSE).
In BB44 we analyze how our attack's '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 based on the Nov/Dec 2022 dump from Common Crawl. We consider the 1 12 languages with at least I MB of data.

---

Programming Language Mixtures We use the GitHub split of RedPajama 122] To determine the programming language for each record, we map the file extension to its associated language (e.g.. -p - Python). This leads to total of 37 programming languages.
Domain Mixtures 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 S
4.2 Baselines
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 's byte-to-toker 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 log-log linear model predict each category's 's true proportion given the encoding efficiency. To ensure correctness, we normalize the resulting set of predictions into a probability distribution.
Baseline based on token classification (TC) We also consider a baseline that assigns each token in the vocabulary to 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 each category, and normalize the counts to produce an estimate of the data mixture.
4.3 Results
Shown in Table T] 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 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. as using indents, curly brackets O. and English variable names. Even more so, English data from different domains (c.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 100x better than either baseline.
contrast, programming languages can share many syntactic features, such
5
Attacking commercial tokenizers
After validating our attack in synthetic experiments ($4) we apply it to infer training data mixtures of off- she-thh--seefffee 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-40 46 LLAMA [56], LLAMA 3 [37. MISTRAL 4. MISTRAL--NMMO 6. GPT-NEOX
CLAUDE g and GEMMA (55) While many of these are closed models, their tokenizers are
publicly available that customers can estimate the cost of queries ahead of time. We note that the
7

---

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.66]
In these experiments, we aim to infer the proportion of different natural languages, code, and English domains, for total of 116 categories. We consider code as 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 SC.I Below, we discuss our findings in comparison with publicly disclosed information about these models.
5.1
GPT models
All tokenizers accompanying GPT models are open-source on tiktoken There are three such tokenizers, released with GPT-2, GPT-3.5, and the very recent GPT-40
GPT-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 reused for GPT-3. Indeed, we confirm the training data consists of 99.1 19% 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 popular source of pretraining data for early Transformer LMs, with GPT-1 being trained entirely on BooksCorpus [63]
GPT-3.5 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 lode-davinci-ioe 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.
trained on text and
Indeed, we estimate that GPT-3.5 is trained on 62.6% code. In the domain breakdown, 27.3% 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-40 GPT-40 is 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-40 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-40 was trained on 7.4% books.
5.2 LLAMA MODELS
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.
https: ghu.. www.////ea/ttttttteeeoooooooeeee bboeee////bbbbbooe
Technically 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 "reusfed] the tokenizer of GPT-2."
8

---

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 Chinese, Arabic, and Hindi, have 0.0% representation. However, we predict 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 different distribution than the LM, primarily focusing books which uses a more standard vocabulary compared to web data.
LLAMA We observe that LLAMA 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 infer what data was used to extending the LLAMA tokenizer. It is reported that LLAMA is trained on more than 5% of "high-quality non-En English text that covers over 30 languages." We find that LLAMA 3 extended with primarily non- Enngllgssh text (48.5% and code (30.2%), indicating that the goal of extending GPT-3.5's tokenizer was primarily for multilingual use.
5.3 MISTRAL
MISTRAL MISTRAL models "handle English, French, Italian, German and Spanish" [ indeed, we find that these are the top five languages in the training data. There is long tail of other languages, but they predominantly (97%) use either the Latin or Cyrillic script.
In contrast, MISTRAL NEMO was "designed for global, multilingual applications, bringing frontier Al models to... all languages." It introduces a new tokenizer (based tiktoken instead 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 -nngliissh languages.
MISTRAL NEMO
5.4 GPT-NEOX
The tokenizer of GPT-NEOX 14 was trained on the Pile with "certain components.. upsampled."" It is popularly re-used in open-source model development, including by OLMo [31), PYTIHA [3]. and DCLM [34). Though our domains do not map neatly onto the constituent datasets of the Pile, our inference is generally consistent, with prediction of 43.7% web, 26.3% books, 12. 1 % academic, 15.2% code, and 2.7% non- non-Englishh text.
5.5 GEMMA
GEMMA (55] is reported training on "primarrtt-Einglish 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 inferences valid for Gemini 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 28.4% non-English text, which explains its large multilingual vocabulary of 256,000 tokens. However, compared to GPT-40, the multilingual representation more skewed toward languages that use Latin or Cyrillic scripts.
5.6 CLAUDE
Very little is known about models from the CLAUDE family, but remark in the Anthropic SDK suggests that CLAUDE [ and 9 share the same tokenizer, which open-source, while CLAUDE 3 [10 uses different (closed) tokenizer. Our attack predicts that CLAUDE was trained on 57.5% code, 38.8% English, and 3.7% other languages. Moreover, half its data (17.4% overall) comes from books, with substantial contribution from Wikipedia (3.7%) and academic text (5.1 ()) well. The lack of multilingual training data likely explains why new tokenizer was trained for CLAUDE which boasts "increased capabilities... in non English languages" [10].

---

Robustness analysis
6.1 Is the attack robust distribution shift?
We measure the impact of using out-o--distributtin 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 separating English domains, performance degradation under distribution shift 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 (S4). 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 100x better than random.
6.2 Is the attack robust to unaccounted-for categories?
In 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,
Random Guess
10"4
10
MSE
we modify our 112 languages experiment from our main experiments (84). We randomly withhold random subset of I to 50 languages from the solver and measure the resulting predic- tion error on the remaining languages. Results shown in Figure 4 Although the perfor- mance of our method does worsen as the amount of unknown data increases, the predictions main substantially better than random.
10
10
10
10"4
10 10
10
Sum of probabilities of languages omitted
Figure 4: Performance remains much better than random even with large amounts of unknown data.
7 Related work
Attacks on LMs Membership inference, the task of inferring whether particular example was part of the training data, has been studied in great depth for language models [15] Attacks commonly use model-assigned probabilities, potentially with another reference model, to make inference. The problem remains extremely difficult, with recent survey finding that many attacks perform near random when pretraining data is deduplicated, as in common practice [24].
17
40
42
24
51].
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
Distribution inference In contrast to membership inference, distribution inference is concerned with inferring global properties of 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
CNNs (54) and GANs (62). More recently, some works show that multi- calli-ppatty machine learning can leak property information such as which authors contributed to the data [41] 61]. All previous distribution inference attacks take meta-classifier approach, where models are trained on datasets with different properties, then meta-classifier is trained using those models.
[T 28
8 Conclusion
In this work, we present data mixture inference attack that solves for the distributional make-up of 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 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.
10

---

Acknowledgments
We would like to thank Luca Soldaini for identifying the cause of redundant merges in some commercial LLM tokenizers (discussed in SC.3) and Jiacheng Liu, Orevaoghene Ahia, Xiaochuang Han, Muru Zhang, Thao Nguyen, Scott Geng, Rulin Shao, Zhaofeng Wu, and the greater UW NLP community for valuable feedback and conversations on this work. We are also grateful to the HuggingFace user Xenova for posting tokenizers-compahn
versions of many tokenizers. This work is supported by Microsoft Grant for Customer Experience Innovation, the National Science Foundation under grant No. 2019844, 21 12471, and 2229876 and DMS-2134012. Both co-first authors (JH and AL) are supported by the NSF Graduate Research Fellowship Program.
References
[1] J. Abadji, P. Ortiz Suarez, L.. Romary, and B. Sagot. Towards cleaner document-oriented multilingual crawled corpus. N. Calzolari, F. Béchet, P. Blache, K. Choukri, C. Cieri, T. Declerck, S. Goggi. H. Isahara, B. Maegaard, J. Mariani. H. Mazo, J. Odijk, and S. Piperidis, editors, Proceedings of the Thirteenth Language Resources and Evaluation Conference, pages 4344 4355, Marseille, France, June 2022. European Language Resources Association. URL org/ 2022. wrec-rrec... 463
https:/ bttps://aclanthol..g
[2] O. Ahia, S. Kumar, H. Gonen, J. Kasai, D. Mortensen, N. Smith, and Y. Tsvetkov. Do all languages cost the same? tokenization in the era of commercial language models. In H. Bouamor, J. Pino, and K. Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 9904 9923, Singapore, Dec. 2023, Association for Computational Linguistics. doi: 10. 10053//112023.mmmlg 1ol--main.66... URL https://
aclanthology. org/2023 2023. emnlp main. 614
[3] O. Ahia, S. Kumar, H. Gonen, V. Hoffman, T. Limisiewicz, Y. Tsvetkov, and N. A. Smith. Magnet: Improving the multilingual fairesss of language models with adaptive gradient-based tokenization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL WtRLhhtpss///rree http://axiv..or/aa/////aa// 2888008888.
[4] M. AL. Mistral 2023. /ttp/////////aaaaaaaaaaaaaa/a/aa
[5] M. AI. Au large, 2024. URL http::://waastaaaaaaaaaaaaaaaaaa
[6] M. AI. Mistral nemo, 2024. URL
[7] A. Albalak, Y. Elazar, S. M. Xie, S. Longpre, N. Lambert, X. Wang. N. Muennighoff, B. Hou,
L. Pan, H. Jeong, C. Raffel, Chang, T. Hashimoto, and W. Wang. A survey on data selection for language models, 2024. URL https: org wtw.://gg........1.../. 16827
[8] Anthropic. Introducing claude, 2023.
URL http:://ww.atthoook..com/ess
Introducing-clauce
[9] Anthropic. Claude 2, 2023. URL httpp://www.abtrrroo.c.co//////s
[10] Anthropic. Introducing the generation of claude, 2024. URL https://ww...wtt www.wpoo...iicccccccccccco.
[11] G. Ateniese, I.. V. Mancini, A. Spognardi, A. Villani, D. Vitali, and G. Felici. Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers. Int. J. Secur. Netw., 137 sep 2015. ISSN 1747-8405. doi: 10.1504/DSN.2015.00 1.99 URL BRLpstts:://do/ wwg.oo/////o/ 1504/1004/ISS 2015. 071829
[12] J. Benders.
Partitioning procedures for solving mixed-variables programming problems. Nu- merische mathematik, 411):238-255 252,, 1962.
[13] Biderman, H. Schoelkopf, Q. Anthony, Bradley, K. O'Brien, Hallahan, M. A. Khan,
S. Purohit, U. S. Prashanth, E. Raff, A. Skowron, L. Sutawika, and O. Van Der Wal. Pythia: suite for analyzing large language models across training and scaling. Proceedings of the 40th International Conference Machine Learning, ICML'23, JMLR.org. 2023.
11

---

[14] S. Black, S. Biderman, E. Hallahan, Q. Anthony, L. Gao. L. Golding, H. He, C. Leahy, K. McDonell, J. Phang, M. Pieler. U. S. Prashanth, S. Purohit, Reynolds, Tow, B. Wang, and S. Weinbach. Gpt-neox-20b: 20b: An open-source autoregressive language model, 2022. URL. https://arxiss org/ 200.b//222440455555
[15] N. Carlini. F. Tramèr, E. Wallace, M. Jagielski, A. Herbert- Voss, K. Lee, A. Roberts, T. Brown, D. Song, U. Erlingsson, A. Oprea, and C. Raffel. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pages 2633-2650. USENIX Association, Aug. 2021, ISBN 978-1-939133-22--3 URL httpttss: //tttps:/wwww... usenix
cttpeeiiiiinaannliiniiiii carlini extracting
[16] N. Carlini, S. Chien, M. Nasr, S. Song, A. Terzis, and F. Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pages 1897-1914. IEEE, 2022.
[17] N. Carlini, S. Chien, M. Nasr, S. Song, A. Terzis, and F. Tramèr. Membership inference attacks from first principles. In 2022 IEKE Symposium on Security and Privacy (SP), pages 1897-1914, 2022. doi: 10. TTT.///44211.222299888
[18] N. Carlini, D. Ippolito, M. Jagielski, K. Lee, F. Tramer, and C. Zhang. Quantifying memoriza- tion across neural language models. In The Eleventh International Conference on Learning Representations, 2023. URL htttps://openreviiee net/nerun Tat-Tt 1cK
[19] N. Carlini, D. Paleka, K. D. Dvijotham, T. Steinke, J. Hayase, A. F. Cooper, K. Lee, M. Jagielski, M. Nasr, A. Conmy, E. Wallace, D. Rolnick, and Tramèr. Stealing part of production language model, 2024.
[20] K. Chang, M. Cramer, S. Soni, and D. Bamman. Speak, memory: An archaeology of books known to ChatGPT/GPT-4, In H. Bouamor, J. Pino, and K. Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Lunguage Processing, pages 7312-7327, Singapore, Dec. 2023, Association for Computational Linguistics. doi: 10.18653/v1/2022 emnlp-main.4533 URL acttps://ccaanthoooog. org/2023.
2023. emnlp- mwin. 453
[21] C. A. Choquette-Choo, F. Tramer, N. Carlini, and N. Papernot. Label-only membership inference attacks. In International conference on machine learning, pages 1964-1974. PMLR, 2021.
[22] T. Computer. Redpajama: An open source recipe to reproduce llama training dataset, 2023. URL httpl////gggtabbb..m////goeeeere
ama- Data
[23] G. B. Dantzig and P. Wolfe. Decomposition principle for linear programs. Operations Research, 8(1):101-111, 1960. https://:///w jstor org/ /tt/sa//bbee11117
[24] M. Duan, A. Suri, N. Mireshghallah, S. Min, W. Shi, L. Zettlemoyer, Y. Tsvetkov, Y. Choi, D. Evans, and H. Hajishirzi. Do membership inference attacks work on large language models?, 2024. URLpttts. //arxxvvvvv////////////////aaav/ org/ prrg/abs/t
[25] M. Finlayson, X. Ren, and S. Swayamdipta. Logits of api-protected 1lms leak proprictary information, 2024.
[26] H. Fu, Yao; Peng and T. Khot. How does gpt obtain its abil- ity? tracing emergent abilities of language models to their sources. Yao Fu's Notion, Dec 2022.
URL https::/yaate notion site/
How Sow-does-Grs Mooes-GPT-Obtaing its- Abt-Abbilty-Trrcccn Emergent- of Law.iieeee----aaaggg-----ee-e ModeelsageMooels--oeee seso-their-SSS Sour
[27] P. Gage. A new algorithm for data compression. The C Users Journal archive, 12:23-38, 1994. htttss//://ap http/pppp...mmaaacccccccoooooooo
attg/CorpusID:55800000
[28] K. Ganju, Q. Wang, W. Yang, C. A. Gunter, and N. Borisov. Property inference attacks on fully connected neural networks using permutation invariant representations. In Proceed- ings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS '18, page 619-633, New York, NY, USA, 2018. Association for Computing Machin- ery. ISBN 45035663533
doi: 10. 29,1144//22337442248844 URL httptst/t///o.it..
1145/ 1145/3243734 3243734. 3243834
12

---

[29] L. Gao, S. Biderman, S. Black, L. Golding, T. Hoppe. C. Foster, J. Phang, H. He, A. Thite, N. Nabeshima, S. Presser, and C. Leahy. The pile: An 800gb dataset of diverse text for language modeling, 2020. htt.htttt////iiiiii. org/ abs abs//10/ 2201 00027
[30] J. Geiping, A. Stein, M. Shu, K. Saifullah, Y. Wen, and T. Goldstein. Coercing Ilms to do and reveal (almost) anything, 2024. URL https://t /ttp///xvvvvvv///i//ee//..aa www./raa...ooooo......o.... 0a0s./242...2 14020
[31] D. Groeneveld, I. Beltagy, E. Walsh, A. Bhagia, R. Kinney. O. Tafjord. A. Jha, H. Ivison, I. Magnusson, Y. Wang. S. Arora, D. Atkinson, R. Authur, K. Chandu, A. Cohan, J. Dumas, Y. Elazar, Y. Gu, J. Hessel, Khot, W. Merrill, J. Morrison, N. Muennighoff, A. Naik, C. Nam, M. Peters, V. Pyatkin, A. Ravichander, D. Schwenk, S. Shah, W. Smith, E. Strubell, N. Subramani, M. Wortsman, P. Dasigi, N. Lambert, K. Richardson, L. Zettlemoyer, Dodge, K. Lo. L. Soldaini, N. Smith, and H. Hajishirzi. OLMo: Accelerating the science of language models. In L.-W. Ku, A. Martins, and V. Srikumar, editors, Pruceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 15789-15809, Bangkok, Thailand, Aug. 2024. Association for Computational Linguistics. URI. https://aclantholle org/ owg///24..2...... long........ 841
[32] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https: /ttpps:/wwwy gurobi com
[33] Land and M. Bartolo. Fishing for magikarp: Automatically detecting muder-trained tokens in large language models, 2024. URL https::t//ttiiiiii org. abs/ 2/////5550.51111 05417
[34] J. Li, A. Fang. G. Smyrnis, M. Ivgi, M. Jordan, S. Gadre, H. Bansal, E. Guha, S. Kch, K. Arora,
S. Garg. R. Xin. N. Muennighoff, R. Heckel, J. Mereat, M. Chen, S. Gururangan, M. Wortsman,
A. Albalak, Y. Bitton, M. Nezhurina, A. Abbas, C.-Y. Hsieh, D. Ghosh, J. Gardner, M. Kilian,
H. Zhang, R. Shao, S. Pratt, Sanyal, G. Ilharco, G. Daras, K. Marathe, A. Gokaslan, J. Zhang,
K. Chandu, T. Nguyen, I. Vasiljevic, S. Kakade, S. Song, S. Sanghavi, F. Faghri, S. Oh,
L. Zeutleooer, K. Lo, A. El-Nouby, H. Pouransari, A. Toshev, S. Wang. D. Groeneveld,
L. Soldaini, P. W. Koh, J. Jitsev, T. Kollar, A. G. Dimakis, Y. Carmon, A. Dave, L. Schmidt, and search of the next generation of training sets for language models, 2024. URL //arx/aavvvv///////// org/ abs/ 2aabs/24400 2406 11794.
Shankar. Datacomp-Ihg
[35] M. Li, S. Gururangan, T. Dettmers, M. Lewis, T. Althoff, N. A. Smith, and L. Zettlemoyer. Branch-trainn-merge Embarrassingly parallel training of expert language models, 2022. URL https://arxiv.. org/ abs/ /208. 03306
[36] T. Limisiewicz, T. Blevins, H. Gonen, O. Ahia, and I.. Zettlemoyer. MYTE: Morphology-driver byte encoding for better and fairer multilingual language modeling. In L.-W. Ku, A. Martins, and V. Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 15599-5507,, Bangkok, Thailand, Aug. 2024. Association for Computational Linguistics. URL http:t////claattollloo/// org/ ac2- 804
[37] A. M. Llama Team. The llama 3 herd of models, 2024. URL httk::tss////trworrrr /bs/ 2407.2177
[38] S. Longpre, G. Yauney, F. Reif, K. Lee, A. Roberts, B. Zoph, D. Zhou, J. Wei, K. Robinson, D. Mimno, and D. Ippolito. A pretrainer's guide to training data: Measuring the effects of data age, domain coverage, quality, & toxicity. 2023. URL wtt.htttss//arxi..oom abs/ 2305 13169
[39] Y. MA, Y. Liu, Y. Yu, Y. Zhang. Y. Jiang, C. Wang, and S. Li. At which training stage does code data help LLMs reasoning? In The Twelfth International Conference on Learning Representations, 2024. URI.hhtpss: /tpttppv//openrvviee net. oor
[40] Mattern, F. Mireshghallah, Z. Jin, B. Schoelkopf, M. Sachan, and T. Berg-Kirkpatrick. Membership inference attacks against language models via neighbourhood comparison. In A. Rogers, J. Boyd-Graber, and N. Okazaki, editors, Findings of the Association for Com- putational Linguistics: ACI 2023, pages 11330-11343, Toronto, Canada, July 2023. As- sociation for Computational Linguistics. doi: 10. 10.18653/112203. (td.5/////222...nnnnnaaallll//l attps://aclanthologyy org/ 2023. findings- 719
URL
13

---

[41] L. Melis, C. Song, E. De Cristofaro, and V. Shmatikov. Exploiting unintended feature leakage in collaborative learning. In 2019 IEEE Symposium on Security and Privacy (SP), pages 691 706, 2019. doi: 10.1 1091SP.2099.000022 URL htt.ttttt///eeep...ooo ieee. org/ org/document/ 8835269
[42] F. Mireshghallah, K. Goyal, A. Uniyal, T. Berg- Kirkpatrick, and R. Shokri. Quantifying privacy risks of masked language models using membership inference attacks. In Y. Goldberg, Z. Kozareva, and Y. Zhang, editors, Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, pages 33322-847, Abu Dhabi, United Arab Emirates, Dec. 2022. Association for Computational Linguistics. doi: 1/20533//1/22222mmlllll URL https::///ccciii https:://aclanthooooyy org. 2022. emn www.e-main.nn.....emmmmmmmmmmaam .57
[43] N. Mireshghallah, N. Vogler, He, O. Florez, A. El-Kishky, and Berg-Kirkpattick, Sim- ple temporal adaptation to changing label sets: Hashtag prediction via dense KNN. In H. Bouamor, Pino, and K. Bali, editors, Proceedings of the 2023 Conference on Empir- ical Methods in Natural Language Processing, pages 7302-7311, Singapore, Dec. 2023. Association for Computational Linguistics. doi: https://aclaantholegs org. /023. emnlp-main.nnm...mmmmmm.mmmmm 452
URL
[44] M. Nasr, N. Carlini, J. Hayase, M. Jagielski, A. F. Cooper, D. Ippolito, C. A. Choquette-Choog E. Wallace, F. Tramèr, and K. Lee. Scalable extraction of training data from (production) language models, 2023. URL
wwwpa/wwwww.////////33333 17035
[45] OpenAl. Introducing ChatGPT, 2022. URL http::://pppaaa..commm/eeeee//
[46] OpenAl. Hello GPT-4o, 2024. URL http::///penaal.com/mmdee///ssss
[47] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever. Language mod-
els are unsupervised multitask learners. 2019. URL https://cdn...... openai........mm com/ learners. pdf
[48] J. Rumbelow and M. Watkins. Solidgoldmagikarp (plus, prompt genera- tion), 2023. URL https://www. www.wwwwwww............. com./postt//aPe388666rrr.o..
solidgoldmagikarp
[49] A. Schäfer, S. Ravfogel, T. Hofmann, T. Pimentel, and Schlag. Language imbalance can boost cross-lingual generalisation, 2024. URL htttt://axxxxiii wtt.:///aab//220.0000505 07982
[50] R. Sennrich, B. Haddow, and A. Birch. Neural machine translation of rare words with subword units. In K. Erk and N. A. Smith, editors, Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 1715-1725, Berlin, Germany, Aug. 2016. Association for Computational Linguistics. doi: 10. 10.11865//1/111-116 URL /ttpttss/////caahoooooo
org. /rrg/P16- 1162
[51] W. Shi, A. Ajith, M. Xia, Y. Huang, D. Liu, T. Blevins, D. Chen, and L. Zettlemoyer. Detecting pretraining data from large language models. In The Twelfth International Conference Learning Representations, 2024. URL t http://rrwerr.eeeeeeooooo./ca//a
[52] R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
[53] N. A. Smith and R. Tromble. Sampling uniformly from the unit simplex. Technical report, 2004. URL URL https: /ttp///wwccco cs. cmu, edu/"nasmi
nasmi teaiiihhppppp wwttthhhppppesmmmiii th th+tromblee tr04. pdf
[54] A. Suri and D. Evans. Formalizing and estimating distribution inference risks. In Privacy Enhancing Technologies Symposium, volume 2022, pages 528-551, 2022. URL https://
peteymposium.c weteymppsiuu.oorroooet/////////e wttp:/ooppp///////////////// -oteeettt--222-0000 php
[55] G. Team. Gemma: Open models based on gemini research and technology, 2024.
14

---

[56] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal,
E. Hambro, F. Azhar, A. Rodriguez, A. Joulin, E. Grave, and G. Lample. Llama: Open and efficient foundation language models, 2023.
http:://axxvvvvroo.ooo org/ htsh/bbs//200 2b02. 13971
[57] J. Wang, T. Gangavarapu. J. N. Yan, and A. M. Rush. Mambabyte: Token-free selective state space model, 2024, URL https: org. wwtp://///aabb//////// 13660
[58] B. Workshop. Bloom: parrmeeree open-access multilingual language model, 2023. URL https://arxiv org/
[59] Y. Xie, A. Naik, D. Fried, and C. Rose. Data augmentation for code translation with comparable corpora and multiple references. In H. Bouamor, J. Pino, and K. Bali, editors, Findings of the Association for Computational Linguisties: EMNLP 2023, pages 13725-13739, Singapore, Dec. 2023. Association for Computational Linguistics. doi: 10. 10.18655 10.11863/11/2222 www.....nniinggeeee...9... URL htt.cp/s/acclaattoooooooo//////p findiigs--iinnsii emmlp. 917
[60] Yang. Rethinking tokenizzainno Crafting better tokenizers for large language models, 2024.
URL http://:///aaaiiioo///aaa////e/e
00417
[61] W. Zhang, S. Tople, and O. Ohrimenko. Leakage of dataset properties in Multi-Party machine learning. In 30th USENIX Security Symposium (USENIX Security 2/), pages 2687-2704, USENIX Association, Aug. 2021. ISBN 978-1-9391333-4-3. httpsttss:/// usenix wwapa/tttatttttaanaaaaaaaaaaeeae wangggg-aaoong..
org/
[62] Zhou, Y. Chen, C. Shen, and Y. Zhang. Property inference attacks against gans. In 29th Annual Network and Distributed System Security Symposium, NDSS 2022, San Diego, California. USA, April 24-28, 2022. The Internet Society, 2022. URL https: /tttpp::/www.... www. ndss symposium org/
ndss Plas-paper/eee autoo draft- 240/
[63] Y. Zhu, R. Kiros, Zemel, R. Salakhutdinov, R. Urtasun, A. Torralba, and Fidler. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In The IEEE International Conference on Computer Vision (ICCV), December 2015.
A Discussion of possible defenses
We discuss some possible approaches for defenses to 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 tokenizer would be damaging. encodings of words as well as entirely unreachable tokens. The only functionally-equii ordering 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-conflictnng sections instead of individual merge rules, we know that each section has higher frequencies than the next.
it can lead to unfamiliar re-
Hiding pretokenization rules Our method relies on a reasonable reconstruction of the pretok- enization rules, which control what kinds of merge rules are considered. It is not necessary share pretokenization rules, as they are not strictly necessary for inference. However, we find that important pretokenization rules (like whether 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 a lively area of research into alternative 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 specifically developed to best encode the given data.
methods of tokenization [57 60
36 3
15

---

B Experiment details & additional results
B.1 Data details
The full set of categories that we use in $4 and the amount of data available for each category are shown in Table Table 6 and Table
Language mixtures We use OSCAO- 23.011, which the January 2023 version of the OSCAR Corpus based on the November/December 2022 dump of Common Crawl. We only keep languages with at least MB of data.
Code mixtures We use the GitHub split of RRedPajama Data-11 which is an open reproduction of LLAMA'S 's training data.
Domain mixtures We use five splits of RedPajama, namely Wikipedia, Common Crawl, Books, Github, and ArXiv. To reduce disk usage, we download only 8% of the CC URLs.
Below, we enumerate the licenses for these datasets.
Oscar CCO 1.0 Universal
RedPajama has different licenses for each subset
C4: ODC-BY
GitHub: MIT, BSD, Apache
Books3: MIT
Project Gutenberg: Apache 2.0
ArXiv: CCo 1.0
Wikipedia: CC-BY-SA-3.0
B.2 Compute details
We run all of our experiments CPUs. For training tokenizers and calculating pair frequencies, use 16-32 CPUs and a variable amount of memory (ranging from 4 GB to 64 GB) depending on the data. Training tokenizer 10 GB of data (as in experiments) usually takes around 10 minutes, while calculating pair counts takes between minute and 2 hours, again depending on the data. To solve our linear programs, use Gurobi 32
B.3 Baseline further discussion
For the baseline based on tokenizer efficiency, we plot the relationship between the true training proportion and tokenizer efficiency (as the normalized byte-to-token ratio) in Figure 5) As expected, the more data for a particular language there training, the more efficiently the tokenizer encodes that language. However, the correlation is clearly imprecise, with the true proportion (z-axis) varying up to an order of magnitude given the encoding efficiency (y-axis).
Between the baselines based on tokenizer encoding efficiency (TEE) versus vocabulary item catego- rization (VIC), we find that TEE performs better for mixtures of code, while VIC performs better for mixtures of languages. This makes sense. because different languages have very distinct vocabularies, while vast inherent differences between languages may make encoding efficiency hard compare. even when using normalization.
B.4 Scaling Analysis
Using setup for controlled experiments (S4), we analyze how attack's performance varies with the amount of data used ($B.4.I) and the number of merges we consider from the merge list
(B.422
B.4.1 How many data samples should we use from each category?
We explore how the attack's performance scales with the amount of data sampled from each dis- tribution D, for calculating pair counts. For each type of mixture considered in $4 train 100
16

---

100
Tokenizer encoding efficiency
4 10
10"3
10
10"
Proportion in training
Figure 5: Relationship between language's proportion in training and the resulting tokenizer's encoding efficiency on that language, shown for mixtures of n languages. The encoding efficiency is defined the byte-to-token ratio of given tokenizer by that a tokenizer trained only on that language. While more training data leads to better encoding efficiency, the correlation is not strong enough to recover prediction nearly as precise baseline based on this relationship achieves log10 MSE 2.22, compared to our attack's s - 7.666.
given language, normalized
attack.
10
10"6
10"5
MSE
MSE
10
Mixture Type
10
languages
10
code
10
domains
10
106
107
10
10P
10
10a
10
10
Bytes of Data
Number of Merges T
Figure 6: Scaling the amount of data used for estimating pair frequencies (5B.4.1), for mix- tures of n categories. Sampling more data per category produces more precise inferences.
Figure 7: Scaling the top T merges used in the merge list (5B.4.2). For mixtures of more categories (larger 7t), considering more merges (larger T') becomes more useful.
new tokenizers considering only categories with at least 10 GB of data available, For our attack, we compare sampling MB, 10 MB, 100 MB, 1 GB, and 10 GB of data for each category, and use = 3000 merges. Shown in Figure more data consistently improves the accuracy predictions.
B.4.2 How many merges should we consider?
Next, we investigate how performance scales with the number merges T that we apply from the merge list. Using the same 100 tokenizers from $4, solve for the data mixture using various choices T E [30, 30000] Shown in Figure 7, we find that when there are more categories, is useful consider more merges. This makes sense because more constraints may be needed bound the solutions in higher dimensions.
B.4.3 Scaling analysis under distribution shift
Here, we repeat the distribution shift experiments in $6.1 while varying the amount of data and merges used. Shown in Figure 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
17

---

merges
10
10
Bytes data
1016
MSE
MSE
1000
10
3900
10"8
100 00
10
29772
10"10
10
107
10
109
10
10?
Bytes of data
Number of merges T
Figure Scaling the amount of data used for estimating pair frequencies for distribution shift experiments from $
Figure 9: Scaling the top T merges used in the merge list for distribution shift experiments from $
C Commercial tokenizers
In this section, we provide more detailed results and discussion of commercial tokenizers.
C.1 Full results for commercial tokenizers
We report the full inferences for commercial tokenizers $5 English domains, and code) in Table 4
over 116 categories (111 languages,
C.2 Snapshot of commercial tokenizer merge lists
We show the first 50 merges of the commercial tokenizers we study in Table for qualitative inspection.
C.3 Handling redundant merges
We observe that the merge list of LLAMA, LLAMA 3, GEMMA, and MISTRAL contain clusters of the sequence of merges
redundant merge rules. For instance, in the LLAMA 3 merge list, 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 impossible for more than one of these merges ever be used, and empirically verify this by applying the tokenizer to a large amount of text.
We find that this is artifact of the conversion from sentencepiece to Huggingface tokenizers format. 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 the BPE algorithm (i.e., they do not actually represent the most-likely next-merge) do this, we do some simple pre- proceessei,:: 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, we keep that merge and remove the rest.
need to remove them for our algorithm. To
As aside, this means that 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.
C.4 Manual merges in GEMMA
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, 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 the end of the merge list instead of the top. Since they not within the top T 30, 000 merges consider, do not do any special pre- pre-processing.
18

---

C.5
GPT tokenizers
While GPT tokenizers are open source on tiktoken, they are not released in a format compatible with HuggingFace tokenizers. We used the tokenizers-compatthe files uploaded by a HuggingFace user named Xenova. For instance, the GPT-40 tokenizer can be found at attttps:/ htttttt:://uugigggeeeeeee co co/Xenvva/gpt-40
C.6 Discussion of sentencepiece tokenizers
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 256 bytes, character-level tokenizers determine the base vocabulary using character coverage hyperparameter (usually set to ~00.9955), which determines what proportion of characters that appear in the training text will 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
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 because different languages have widely varying numbers of characters in their writing systems. For languages with many characters, their merges will appear lower the merge list due to their lower average frequency compared to languages with fewer characters. This leads a bias representation among the first T merges considered by our approach.
C.7 Miscellancous observation: tic-breaking sentencepiece tokenizers
We observe that in sentencepiece tokenizers, after going deep the merge list (about halfway), the merges begin forming groups, in which the length of the merge is ordered from shortest to longest. trace this to how ties in pair counts are broken in sentencepiece, which by length of the merge. In terms of reverse engineering, this points to 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.
19

---

Table 2: Top 50 merges of commercial tokenizers we study, For LLAMA 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 0 with and the newline with Än. To 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 relevant discussion). The merges \n, =, and sel are also common token pairs in code. The odd-looking symbols 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), D encodes the Cyrillic "a" (used in e.g., Russian), and å encodes the prefix for the second half of the Georgian Unicode block.
GPT-2
GPT-3.5
GPT-40
LLAMA
LLAMA 3
06 Ū à à,
h
i
i m
Ni ÑL a, atG å, â> aGçaçç agçaçG OS
t
_t
e
w
a t
O
8 t
açG i. â>ī
1 3
_t h
NE Nili
i
In In
awтан A NK D
o
e
th
angar 0f 0
i t
P
Nk D2
d
n
acc
f
ar
in
8
t
aw
P
_hh
in
DA NK
o
n
\n
ary
P
à 1
0
a
1
an
t o
NG D
m
acI
f
Ng MI
in
g
g
d
e
h
in
d
i
_t he
d
acr
a s
i
C
in
AL
1 e
b
ar
h
d
aGG
BGG
on
8 t
0 m
1 1
à 1 8.
OI
OI
n
r
o
en
_t
1
a 8
RE à1 A
1
f1 12 an
v
e
n
1
in
_
_Da D,
h
a#jan
20

---

Table 3: Top 50 merges of commercial tokenizers we study, continued from previous page.
MISTRAL
MISTRAL NEMo
GPT-NEOX
CLAUDE
GEMMA
t
r
a
n
è r
1
h i n _t he
e n h
t o r e
a t
_t
In
s
h
e n
h
c
t e t h s t d
i s
i t
a 1
p
_ he
a
e 8
a n 1 P
a
1 e d
he
1
e
s
b
b
a r
in
a n
An
d i t n t
in g
P
i s
d
in
P
a G
d
1 r a o
m
m
on
c
i on
In
in
1
r
i on
g
m
i 8
t
a s
in
n g
f
a G
an d
b
i
_a
r o h
1 i t a f b m
e
o
_t
h
D
t h
sel f
t
d
in g
t
e t
i c
G t
t
e 1
e 1
re
1 a
21

---

Table 4: Our full set of inferences for commercial tokenizers 116 categories (111 languages, 4 English domains, and code). The four English domains are web, books, academic, and Wikipedia.
Calegory
MISIRAL
GPT-
Web
62.6
32.8
302
25.8
18.3
15.2
57.5
25.9
Books
15.4
6,8
7.4
23.1
3.5
21.5
9.5
26.3
17.4
12.8
Academic
0.2
0.0
8.0
5.3
3.7
12.0
5.1
4.3
Franch
0.3
29
5,3
233
6.3
0.0
3.0
German
0.0
0.4
1.8
5.1
22
21
3.2
0.1
0,1
28
Arabic
Japanese
Spanish
0.6
2.8
2.7
1.7
3.7
0.0
3.9
Russian
0.0
0.1
28
2.6
3.4
122
26
0.2
011
1.4
Turkish
011
0,4
0.0
0.6
Ukrannaan
0.0
0.0
0.3
1.3
27
0.0
0.6
0.0
0.0
022
Italian
0.0
0.3
0.5
2,5
10
1.5
1.7
0.1
0.3
16
Koream
0.0
0.0
0.7
011
2.5
0.0
0.1
0.2
Portugueee
03
Penian
0.0
0.0
0.4
0,0
00
1.2
0.0
0.0
0.3
Dunch
0.0
0.1
2.0
1.2
06
0.5
0.1
0.1
06
Vietnamese
Thai
0.0
0.0
0.4
0.0
00
0.2
0.0
0.0
au
Hindi
0.0
0.0
1.4
0.0
00
1.
0.0
0.0
QUE
Polish
0.7
0.8
0.0
0.7
033
Georgian
0.0
0.0
0.8
0.0
0.
0.3
0.0
0.0
00
Indonesian
0.0
0.1
0.4
0111
000
0,4
0.0
0.0
08
Chinese
Estonian
0.0
0.1
0.5
0.1
0LI
0.1
0.2
06
Finnish
0.0
0.0
0.5
112
0LI
0,3
0.1
0.0
06
Low German
0.0
0.0
0.1
02
0.0
Gujarati
0.0
0.0
0.5
0.0
00
0.1
0.0
0.0
00
Malayalam
0.0
0.0
0.6
0.0
00
0.2
0.0
0.0
00
Bangla
0.0
00
02
00
Hehrew
0.0
0.0
0.5
0.0
00
04
0.0
0.0
01
Amnesian
0.0
0.0
0.5
0100
00
0.5
0.0
0.0
00
Telugu
00
0.5
0.0
Romanian
0.0
0.0
0.3
0.4
02
044
0.1
03
Filipino
0.0
0.0
0.3
0.1
0.0
0.0
0.0
0.1
05
Libhanian
Daniish
0.4
033
02
Rulgorion
0.0
0.0
0.2
0.2
02
0.4
0.0
0.0
0.1
Kannada
0.0
0.0
0.4
0100
00
0,3
0.0
0.0
00
Welsh
0.4
0.3
0.2
0.3
0.2
Undu
0.0
0.0
0.3
0.0
00
0.2
0.0
0.0
00
Malagasy
0.0
0.0
0.1
0.1
00
0.0
0.0
0.1
03
Tumil
00
0.3
0.1
0.0
02
Tajik
0.0
0.0
0.3
0,0
00
00
0.0
0.0
0.0
00
Macadonian
0.0
0.0
6.1
0.1
01
011
0.3
0.0
0.0
00
Nepali
Kustth
0.0
0.3
0.0
00
0.1
0.0
00
Relamssia
0.0
0.0
0.3
0.1
01
0.1
0.3
0.0
0.0
00
Eáperanto
0.0
0.0
0.0
012
0.1
011
0,3
0.0
0.0
0.1
Afrikasnn
0.3
00
0.0
Noewegian
0.0
0.0
0.2
0.0
0.
000
0,0
0.0
0.0
0.1
Uxhek
0.0
0.0
0.1
0.1
0.0
0.1
0.0
0.1
02
Norwegian Nynorsk
Slowak
0.0
0.2
0.0
000
0.1
0.0
02
Lojtan
0.1
0.0
0.2
0.0
02
0.1
0.1
0.0
0.0
00
Icclandic
0.0
0.0
0.2
011
0.1
0.
0.0
0.0
0.0
01
Kyrgyz
Pishtt
0.2
00
0.0
0.0
00
Axerbaijani
0.0
0.0
0.1
0.0
0.1
0.0
0.2
0.0
0.0
0.1
Breton
0.0
0.0
0.1
0.1
0.1
0.0
0.0
0.2
Yoddish
00
Bushkir
0.0
0.2
0.0
00
0.0
0.0
00
Kurdish
0.0
0.0
0.1
0.0
02
00
0.0
0.0
0.0
011
Hungurian
0.0
0.0
0.0
0.1
0.2
0.1
0.0
0.0
00
Alsunian
0.0
0.1
0.0
00
0.1
0.0
Assamese
0.0
0.0
0.1
0.0
0.0
00
0.0
0.0
0.0
00
Lunembourgich
0.0
0.0
0.0
0.0
0.0
0.0
0.1
Cobuano
Ambaric
0.0
0.0
0,0
00
0.0
0.0
0.0
01
Sindhi
0.0
0.0
0.1
0.0
00
00
0.1
0.0
0.0
00
Desetic
0.0
0.0
0.1
0.0
0.0
0.0
0.0
0.0
00
22

---

Calegory
GPT-2
GPT-3.5
GPT-40
LLAMA
LLAMA 3
MISTRAL
MISTRAL NEMo
NEoX
GPT-
CLAUDE
GEMMA
Chechen
0.0
0.0
8.1
0.1
0.1
0.
0.0
0.0
0.0
00
Pledmonsese
0.1
0.1
Mongolian
0.0
0.0
0.1
0.0
00
0.1
0.0
0.0
00
Burmese
0.
0.0
0.1
0,00
0.0
000
0.1
0.0
0.0
00
South Azerbuiaaii
0.1
0.
0.0
00
0.1
Latin
0.0
0.0
0.1
0.0
00
0.0
0.0
0.1
01
Uyghur
0.0
0.0
0.1
0.0
00
0.1
0.0
0.0
00
Sinhala
Punjabi
Chuvash
0.0
0.0
0.0
0.1
00
0.0
0.0
0.0
00
Klaner
0.0
0.0
11.1
0100
00
00
0.0
0.0
0.0
00
Panjabi
0.0
Newar
0.0
0.0
0.0
0.0
00
0.0
0.0
0.0
00
Lao
0.0
0.0
0.0
0.0
0.
0.0
0.0
0.0
00
Sakha
00
00
Mingrolisn
0.0
0.0
0.0
0.0
00
00
0.0
0.0
0.0
00
Sanskrit
0.0
0.0
0.0
01.0
00
0.0
0.0
0.0
00
Central Kundash
Eastem
0.0
00
0.0
0.0
00
Swahili
0.0
0.0
0.0
0.0
00
0.0
0.0
0.0
00
Odiaa
0.0
0.0
0.0
01.0
0.0
00
0.0
0.0
0.0
00
Rishuppiaa
Egyyttan
Tibetan
0.0
0.0
0.0
0,0
00
00
0.0
0.0
0.0
00
Divahi
0.0
0.0
6.0
0.0
00
0.0
0.0
0.0
00
Konkani
0.0
0.0
0.0
00
0.0
00
00
Malay
0.0
0.0
0.0
0.0
00
00
0.0
0.0
0.0
00
23

---

Table 5: The 112 natural languages considered in 84
The data is from Oscar v23.01, which performs
language identification at the document level.
Language
Size (MB)
Language
Size (MBB
Language
Size (MB)
Language
Size (MB)
Chinese
776494.9
Bangla
19055.4
Icelandic
2194.7
Sanskrit
56.3
English
666955.4
Hebrew
17970.6
Slovenian
1398. 1
Ossetic
50.7
Russian
531902.4
15776.8
Punjabi
Chuvash
42.3
Sponish
424143.2
Catalan
15346.5
Basque
1195.9
Cebuano
41.1
French
371967.1
Danish
14843.6
Tajik
1028.4
Afrikuams
37.2
German
356683.7
Lithuanian
14518.6
Tatar
834.1
Breton
31,4
Italian
214768.2
Georgian
8388.2
Central Kurdish
773.1
South Auerbuiani
28.4
Japanese
181299.8
Estonian
Filipino
719.4
Crostian
Hungarian
150134.4
Serhian
7666.2
Odia
543.2
Fastemn Mari
22.9
Polish
146001.9
Larvian
7411.5
Tibetan
531.6
Luxembourgish
18.4
Vietnamese
139298.4
Malayalam
5815.1
Amharic
513.0
Uzbek
15.3
Dutch
135078.1
Mongolian
5777.3
Kyrgyz
489.5
Chechen
13.9
Arabic
110728.5
Gujarati
5593.9
Esperanto
475.1
Malagasy
Portuguese
105065.0
Nepali
4950.5
Lau
472.3
Low German
10.7
Greek
Ammenian
Assamese
412.2
Mingrelian
Persian
93225.0
Macedonian
4745.4
Bashkir
363.9
Bishnupriyn
5.4
Thai
91968.7
Marathi
4478.3
Welsh
333.1
Newari
Czech
76987.1
Telugu
3873.8
Pashto
261.7
Minangkabau
3.8
Turkish
72207.2
Unda
3761.3
Galician
255.9
Egyptian Arabic
Swedish
Kazakh
Uyghur
Norwegian Nynorsk
Romamian
45590.6
Albunian
3224.9
Divehi
200.2
Turkmen
3,3
Ukminnan
Kundish
Piedmontese
Bulgarian
44118.5
Azerbaijani
3038.3
Yiddish
171.8
Malay
2.6
Finiish
41143.7
Burmese
2035.4
Sindhi
131.7
Goan Konkani
Korean
38158.4
Sinhula
2599.3
Wesiem Panjabi
105.8
Latin
Hindi
32615.5
Norwegian
2583.2
Westem Frisian
70.5
Lojhan
Indonesian
23416.0
Kannada
2574.4
Sakha
Maltese
Slovak
21460.7
Belarusian
2339.5
Irish
63.2
Swahili
1.0
Table The 37 programming languages considered in $4 RedPajama, and classified into language based on the file extension.
Data is sourced from the Github split of
Language
Size (in MB)
Language
Size (in MB)
Java
29493.0
Haskell
547.6
JavaScripe
27910.4
TSQL
489.5
HTML
25864.1
Lua
393.4
XML
18804.0
Dockertile
272.7
Makefile
Python
12970.1
TeX
256-9
Smalltalk
11580.5
XPixMap
248.7
Objective-C.
10909.5
PowerShell
240.7
PHP
9837.4
CMake
118.5
Go
106.9
Markdown
6137.3
Hack
79.1
CSS
40849
Batchfile
60.9
Ruby
3381.4
Pod6
Scala
1376.8
FortranPreeoom
Smali
978.3
Fortran
31.2
reStructuredFeett
MotorolaoKKAsseeblly
ViT
$63.0
Perl
2.0
551.6
Table 7: The domains considered in
Data is sourced from RedPajama.
Domain
Size (in MB)
Web
305139.9
Code
196506.0
Books
104975.0
Academic
89044.9
Wikipedia
20505.8

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the absaract and introduction accurately reflect the paper's commibttions and scope?
Answer [Yes]
Justifiction:
All claims in the absttrcc und incroduction ure fully supported by evidence later in the puper.
Guidelines:
The nnswer NA means that the abstract and introdaction do not include the claums made in the paper.
The abstract andior introduction should cloudy state the claims made, including the coutrihutions made in the pager and important essumptions and limitaiioss A No NA snswer to this question will not be perceived well by the reviewers.
The claims made should match thcuretical and experimental resulls, and reflect how much the results cun be expected generalize to other settings.
is fine to include aipirational goals motivation as long as it clear that these goals are not attained by the paper.
Limitations
Question: Does the discross the limitations of the work performed by the authoms?
Answer [Yed]
Tustificatinn
[
Becnssss potential defenses to our sttack
Guidelinss
The unswer NA means that the paper has limitation while the answer No moans that the paper has limination,, but those are not disenssed in puper.
The authors encouraged to sepurate 'Liminations' section their paper.
The paper should point out strong assumptions and how rebust the resullt are to violations of these assumptios (6 indepencennee aesumyttios,
settings, model sell-spceiffatiin, asymppotic approximationss only holding lncally). The should reflect how these nosumptions might be vixlated in pracicee and what the implications would be.
The authors should reflect
scope the claims empincal results oftes depend on implicit ascumpeooss. which should be articulated.
egg. the appreach only on a few dulasets with a few runs. general,
The amthoes should reflect the factors inffuesee the perfonaance the approach. For example, facial recognition algocittom may perfoom pourly when image resolution is low or images are taken in low lighting. Or sperch-io-iest system might not be used reliably to provide closed captions for online tecuures hocause it fails handle technical jargon.
The nuthors should discuss the computizioal effeceeccy of the propased algocithms and how they scale with dataset size.
If applicablc, the authors should discuss possible limitation of their approsch to address problems of privzcy and fnimess.
While the authors might feur that complete homesty about limitations might be used by reviewers as grounds fee rejection. wore outuomee might be that reviewen discover limitations that aren't acknowlelged in the puper.
puper. The authons should use their best judgment and revegnioe that favor of transparescy play imporcant role in developing will be specificallyy insructed not penalize hunesty concerning limitations.
individual
that preserve the integrity the community. Reviewers
3.
Theory Assumptions and Proofs
Question: each thoorctical result, does the paper provide the aocaaspttons and a complese (and correct) pcoof?
Anrwer: [NA
Justification: We not have aay thoorctical results.
Guidelines:
The aaswer NA means that the paper does not include thocrctical results.
theorems, fomnulas, proofs the puper should be numbered and crese referenced.
All assumption should be elearly stated or referenced the statement of any theurems.
The pronfs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the mathors are encoumged provide
proof sketch provide intation.
Imersely, any informal proof provided in of the paper should be complemented by formal proufs provided appendix supplemental muterial.
Thenrems and
relies upon should propesty referenced.
Rxperimental Result Reproducibality
Question: Docs paper fully diselose the information seaded to reproduce main experimental results of paper the extent that affects the main claims indlor conclusions of the paper (regmilees whether the code and data are proviled or not)?
Answer: [Yes]
Justification: All information noeded to reproduce our results are provided the poper. We use open datneets and open-source lihmrry train our tokenizers.
Guidelines:
The answer NA means that the poper does not include esperiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper repeudacible is importent, regardless of whether the code and data are provided or not.
1f the cnntribution is datnset andice model, the mithoes should describe the steps taken to make their results reproducibble or verifiable.
Depending on the contibutionn reproducibility can be accomplished in various ways. For example, if the contibbttin a novel architecture, describing the archisecture fully might suffice, or the contibution is specific model and empinical evaluasion, it may be necessary to either
make possible for others replicate the model with the dateset, peovide often one good way accomplistt but repoodcciilityy also provided detailed instructions how to replicate the results, access a hosted modal (eg. in the case of a large language model), releasing of model checkpoint, or other menes that are appropriate to the research pertormed.
the model. general. releasing code
data
While NeurPPS does not require releasing code, the conference does require all submissions proside some reasonable avenue for reproducibliity which may depend the mature of the contribtiion For example
(a) If the contibution primarlty new alganitian the paper should make it cleas how to reproduce that algaritius.
(h) contribution primarily new medel architectue, the poper should describe the aechitecture elearly and fully
If the cun.ribution
model (o lurge linuage model), then there should either be way consemuct dataset).
this model for reproducing the
results way reprodune model z. with open-source
instmuctions
(d) We recognize that reproducibility may be tricky in some cases, in which cuse authors are welcome to describe the purticular way they provide for repnddciiiiity. In the case of closed-source models, it may be that access the model is limited some way (eg, registened users), but should be possible other reseurchers have some path to reproducing verifying results.
25

---

Open and code
Question: Does the paper proide open seceess to the datrand code, with sufficiont instractions to faithfully reprodiue the moin experimental results, descrihed in supplemesral material?
Answer: [Yes]
Jusiiication: We publicly releuse vode al wttttpe: /tttbb http://aassotiieee////eeeeeeeeee attack
Guidelines:
The NA that paper not include experimens requiring code.
htwpaiddweeeeeeeeanaeaaaaaeeeeee Please see the NeutPP code and data submission guidelines biliga:/nnippe http://www......aa...//////a/aaa details.
for more
While encounge release of code and data, understand this mighr possible, "No" seceptable Papers
rejecsed simply for not including code, unless this central to contribution (e-g. new open source benchmark). NeurIPS and data
The instmuctions should contain the command and enviromment needed
repeuduce the results,
submission guidelines /tttpe:/nipp.... http::////aa.///p/p/// on/pub/ se/gui guide dendde//CCosai /Cdd/Sobe extonPalicy icy for more detiils.
The outhoes should provide instructions on data sccess and preparation, inclading how access dota, and geventte dara, etc.
data, prepeceessed data, intensediste
The nuthors should procide scripts to reproduce experimental results for the now proposed method and buselines. If onlyy a subset of experiments are reproducible, they should state which ones are emined from the script and why.
At submiission time, to preserve snonymity, the authors should release moorymized versions (if applizable).
Providing as much infommation as possible in supplemental material (appended to the paper) is recoemmended. but including URLs to data and code permitted
Experimental Setting
Question: Dazs the paper spacify all the training and test details (e.g., data splits, hyperpannetters how they were chosen, type of optimizer, etc.) secessary understand the results?
Answer: [Yes]
Justification: We choices purameters experiment panameters
33
provide analysis performance with
Guidelines:
The answer NA means that the puper does not include experiments.
The experimental setting should he presented in ovee the paper to level detail that nocesorry to apppoiiiitt results and make sonse of them.
Thee fall details can be grovided either with the code, in appendix, or as supplemental material.
Experiment Statistical Signifleance
Question: Does the paper repoct erioe bars suitalyy and coneecll defined or other appeopriate information about the statistical significance of the experiments?
Answer: [Yes]
Tustificatin:
We report the standand deviation of all of our results, well random haselines.
Guidelines:
The NA that the paper does not include expeciments.
The authors should eeswer "Yor" the reults are accompanied by ernor burs confidence intervals, or statistical significance tests, least for the experiment that support
claims the paper.
The factors varability that crour bus capturing should be clearly stated (for example. trainkest split, intiaaization. random drawing
some paramater, overall mun with gives experiasental canditions).
The method for caleslating the
should expleined (closd formols, call to lihnary fienction, bootsrpp,
The cosumptions made should gaves g.. Nocmally distributed erross).
It should be clear whecher the bur the standand deviation the standard erur the
is OK to report I-sigma enne bars, but one should sure The outhees should prefenilly coport a 2-simma eriar her than state that they have
96% if the hypothesis Nomualit of
verified.
For asymmetric distributions, the authors should be careful not show in sables figures symmetric burs that would yield results that out runge (e.g. negative enorr rates). reported figures or tables in text.
plots, The authors should explain in
they were calculated reference corresponding
Experiments Compute Resources
Question: For each experiment, does the puper provide sufficient information on the computer resources (type of compute workers, memory, time of esecution) needed to repruduce the esperimenus?
Anvwer [Yes]
Justifictionn: We discuss this in EB2
Guidelines:
The snswer NA mesms that the piper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, insenial cluster, or cloud provider, inclading relevant memory and storage.
The paper should provide the amount of compute required for each the individual experimental russ as well as estimate the total compute.
'The paper should disckose whether the full research project requized more compuse than the experiments reported in the paper (c.g., preliminary failed experiments that didn't make it into the papes'.
Code Of Eshles
Question: Does the reseunch conducted the paper cunform, every respect, with the NeurTPS Code of Etthic//ttps:// httppps////uuuppp..... cc/ ec/publie/ Rtbi calesddi
Anewer: [Yes]
Justification:
our knowledge, we confomn the of Littic..
Guidelines:
The naswer NA that the nothors have not reviewed NewrIPS Ethies.
authors answer they should explain special ciccumstances require a the of Ethies.
26

---

Thee outhors should make preserve anonymuty (o-g.. there special consideration to laws regulations their jurisdictio).
10. Bronder Impacts
Question: Does the piper disenss both patential positive societal impacts negative societal impucts the work perfomned?
Anewer: [Yes]
Dustification: the introduction, twiefly discuss positive and negative implications data mistare informnee ottack.
Guidelines:
The answer NA that there no sucietal impact
performed.
authors anewer No, they should explain why their work has socictal impuct or why paper address socictal impict. Esamples of negative sociotal impacts include poteniaal malicions unintended mee (eg. disinfommtioo, generating fake profiles, surveillanee) faimnss consideratons (e s. deployment of technologies that could decisions that unfaitly impact specific groups), privacy considerations, and security consideration.
The conference expects that many papers
foundational reaetech and noe tied to putticular applications, alase deploymeats, However, there a direct path to any negative applications the authoes should pouat out. For esample. is legitimaae to point out that as improvement in the quality of generative modilh could be used to generate despdakos for disinformation. On the other hund, it not needad point out that a aetworks could euable people
generic algoeiltm for aptimizing
modelss geserate Deepfakes
The suthors should consider possible harms that could arise the technology being used as insended and functioning curreclly, harms that eecnology is being used
could arise misuse of the technology.
gives incorrect results, harms following from (intemional unintentioal)
there are negative socictal inspasss the authocs could discuss possible mitigation strategies (egg. gated release modelss providing defenses in additionn to attacks, mochanismss for monitoring misuse, mechumisms to monitor how a system kamms from feedback over time, impeoving the efficiency and accosalhilit of ML.).
Safeguards
Question: Does the paper deseribe safeguards that have been in place for responsible release of data models that have high risk for misuse pretmined baguuge modals, image peneratirs, scraped datanets)?
Answer: [NA]
Justification: not release any models.
Guidelines:
The answer means that the paper poses no risks.
Relessed models that high risk for misuse dual suse should released with necessury safepuards allow controlled use the model, example by requiring that meess afhere usige guidelines restrictions socess model implomeating safety filters
scraped from Insemet could pase safoty risks. The authors should describe how they aveided releasing unsate images. recognize that providing effective sefeguards is chalkongigg and many papers not require this, encourage suthors take into account and make bost faith effort.
Datasets that
12. Licenses for existing aseets
code, Question: Are the creatoes original owners of assets (e.g., code, daiz, models), used in the paper, properly credited and are the license and terms of use
explicily menioned and properly respected?
Answer [Yes]
Justiication: We peoperly cite all creaters or owners of the assets we use this paper.
Guidelines:
The onswer NA menns that the paper does not use existing assess.
The suthors should cite the original puper that predived the code package or dutiaset.
The nuthoes should state which version of the asset is used and, possible, include URL.
The name of the license (e.g. CC-BY 4.0) should be included for each asset.
For scraped data from porticulie sounce (e.g. wehwite), the expyright and terms of service of that source should be penvided. terms of use
puckoge should be peovided. For popular datasets, paper oui tacodo. con/ dataseta Jus curnted licenses for some datzsets, Their licensing guide can help determine the license of dataset.
assets are release,,
license, eopyright information,
For existing datasess that are re-packaged, both original license and the license the derived
has changed) should be provided. this information not available ooline, suthors are encouraged to reach out the assel's creatons.
13. New Assets
Questiin: new assets introduced the paper well documented documestation provided aloogside nssets?
Answer: [NA]
Justificttio:: The paper does not introdace new asscts.
Guidelines:
The neswer NA menns that the paper does not relesse new reaets.
Reseurchers should communccate details the datsettcodoluodl as past their suhmissions via structured tomplates. includes details about training. license, limitations, eic.
The paper should diseuss whether how consent was obtained from people whose ssaet used.
submission time, remember to anonymize your assets applicable). You can either create an anosymizzd URL or include in anonymized zip file
14. Crowdsuuring and Research with Human Subjects
For crondsonzing exporiments and research with haman subjects, does the paper include the full tex of instmerions given to porticipants and screasshets, applicalle, as well as details about compeniation (it any??
Question:
Ansver (NA)
Iustifcation: The poper does not involve crowdkoursing reseanch with human subjects.
Guidelines:
The snswer NA meins that the poper does not involve crowdennrcing nor resesrch with human snhjects.
Including this information in the supplemental material fine, but mh main coomibution of the paper involves human subjocts, then as much detail as possible should included
main paper.
According the NeurPS Code of Eihiis, workers involved in data collection, curation, other labor should be paid least the minimum country the collector.
27

---

Institutonnl Review Board (IRB) Approvals Equivalent for Research Human Subjects
Questio: Does the poper deserihe potential risks incurred by suuy parlicipants, whether such risks were disclooed the suhjects, and whether Instrutional Review Boad (IRR) approvals (or equivalent approvalneview baied the requirements of your country institution) were ohtnined?
Answer (NA]
Iusification
The paper does not involve crowdkourcing research with human subjects.
Guidelines:
The NA
with human Depending the country which research conducted, IRB appewval (or equivalen) be requined human subjects research. you TRB approval. you should
the pager involve sowddouurcing
this puper.
may vary signffiaurtly institutions locations, expeet adhere recegnize the guidelines institution.
iniiaal submissions, include
would anunymicy applicable),
cunducting review.
28


Reviews:
[{"review_id": "eLB81i0hgX", "reviewer": "Reviewer_rZKP", "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.", "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?\n\n2. 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": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. One of the key strengths of the paper is its demonstration of the attack's effectiveness. Through controlled experiments on known mixtures of natural languages, programming languages, and data sources, the authors show that their attack can recover mixture ratios with high precision, outperforming random guessing by several orders of magnitude. The attack's application to off-the-shelf tokenizers released with commercial LMs reveals new information about their training data composition, underscoring the practical implications of this work.\n\n2. The paper presents an efficient algorithm for solving the data mixture inference problem. Initially, the problem is formulated as a linear program (LP) with a large number of constraints (scaling with the cube of the vocabulary size, O(V^3)). However, the authors introduce several optimizations, such as truncating the merge list, efficiently storing pair counts, and using lazy constraint generation. These optimizations make the problem computationally tractable, allowing for practical application of the attack.\n\n3. The practical implications of this attack are noteworthy. It can potentially allow for the auditing of pretraining data for biases, reveal proprietary information about model construction, and enable targeted data poisoning attacks. \n\n4. The paper is well-written and organized, with the inclusion of an appendix with additional details and results further enhances the paper's clarity and accessibility.", "weaknesses": "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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing our work as a “significant contribution to the field” and its “noteworthy practical implications.” We have taken all of your suggestions into account and hope that our response addresses your concerns.\n\n## Today’s LLMs use BPE\n\nWhile it is true that other tokenization algorithms may exist, BPE is the universal choice for today’s production models; in fact, **we manually verified that all top 100 models on ChatbotArena use BPE tokenizers**. In the future, powerful LMs that use tokenizers other than BPE may be released, but we cannot guess what algorithm they will use.\n\n## Effect of sampling error on attack performance\n\nThe linear program we propose is explicitly designed to handle outlier pairs with significantly higher or lower counts than expected using the slack variables $v_p$ and $v^{(t)}$. Of course the actual performance under sampling noise will vary depending on the data, which is why we use sampling in our synthetic experiments, both for the tokenizer’s training data and the data used by the attacker to estimate pair counts. We find that our attack works well, even using these noisy counts. Note that we do have many low-resource languages in our experiments!\n\nWe also provide **new results examining the case where the data available to the attacker deviates significantly from that of tokenizer training**. *Please see the global response for details.* In this setting, the counts will deviate from the expected amount due to the distribution shift in addition to the sampling noise. We see that our attack’s performance degrades gracefully in this setting, **remaining strong even under extreme shift**. \n\n## Further discussion of implications\n\nSince the ideal tokenizer training data is in-distribution with respect to the pretraining data, the tokenizer’s training distribution reflects the model creator’s priorities (see e.g. the recent shift to tokenizers trained on more multilingual data in GPT-4o, Gemma, and Llama-3).\n\nIn terms of enabling more specific attacks, data mixture inference gives a useful characterization of the “attack surface” of a model, which could be useful in many ways. For example:\n\n1. One could leverage discrepancies between the tokenizer training distribution and the pretraining distribution to find “glitch tokens” [1] that trigger unwanted behavior in the target models.\n2. Knowing the data mixture could help accelerate model stealing attacks, such as the “logprob-free” attacks of [2], since knowing the token distribution gives a useful prior for the (unknown) log-probabilities of each token at generation time.\n3. When performing membership inference, the data mixture could be used to choose what members to prioritize checking (e.g. we found lots of book data → check for book membership first).\n\n[1] Fishing for Magikarp: Automatically Detecting Under-trained Tokens in Large Language Models. 2024.\n\n[2] Stealing Part of a Production Language Model. 2024.\n\n## Tokenizer training data vs pretraining data\n\nWhile pretraining data and tokenizer data are ideally from the same distribution, we do not know whether this is actually the case for the LLMs we study, due to the general opaqueness of model development. Our attack specifically uncovers the *tokenizer* training distribution. We will ensure this is clear in the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eQk8JIraKc", "reviewer": "Reviewer_2xkV", "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.", "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?\n2. 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?\n3. How does the vocabulary size, size of the data and number of merges $T$ affect the time the attack requires to run?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed attack seems novel and the problem of interest is very relevant to key problems in LLM area. They verified the effectiveness of their attack on several data mix scenarios. The structure of the paper is also clear and easy to follow.", "weaknesses": "I listed a few directions that I think the paper can be improved.\n1. 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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the novelty of our attack and its “relevan[ce] to key problems in LLM area.” We have taken all of your suggestions into account and hope that our response addresses your concerns.\n\n## Theoretical analysis\nRegarding the theoretical analysis, the key observation is that LP2 is a subset of LP1 and its size increases with each iteration. Thus, we are guaranteed to either terminate early or, in the worst case, eventually add all constraints and variables from LP1. Thus, the convergence to a feasible solution is guaranteed. However since LP1 is very large (albeit polynomial in the problem parameters), the hope is that we will terminate early. Unfortunately, proving a strong bound on the number of iterations required would be unprecedented for an algorithm using this approach. (It is typical for papers leveraging row and column generation to prove convergence in finite time and demonstrate that the effective number of iterations is low using experiments.)\n\nWe will add a paragraph explaining this reasoning to the paper. Additionally, we notice in practice that the number of iterations required is highly problem dependent, with some instances being solved extremely quickly. We report the worst case timings observed in Section 3.\n\n## New experiments show that the attack is robust to distribution shift\nFollowing your suggestion, we run **new synthetic experiments in a setting where there is distribution shift between the data the tokenizer was trained on and the data available to the attacker**. We see that the performance degrades gracefully in this setting, **remaining strong even under extreme shift**. More details are given in the global review.\n\n## Starting vocabulary and pretokenization\nFor BPE tokenizers, the starting vocabulary is fixed at the 256 possible bytes, so we do not need to guess the starting vocabulary to use our attack. Furthermore, all models we study release the pretokenization rules in their tokenizer configuration.\n\n## Token frequency distribution\nIndeed, in general we cannot expect that every token will be uniformly distributed throughout the corpus. Thus, one would expect a discrepancy between token counts for e.g. one half of the corpus vs halved counts for the full corpus. In our experiments we account for this by subsampling the data, giving some sample to the tokenizer to train and a different sample to the attacker. We show that performance improves as the amount of data given to the attacker increases in Figure 4 of §6.1. This makes sense, as the empirical token frequencies will converge to the true frequencies.\n\n## Runtime scaling\nAs noted previously, it’s difficult to characterize the number of iterations required because it depends heavily on the input data itself. Here is what we observe empirically:\n\n- The pair counting time scales like $O($pair counting data size * number of merges$)$ and doesn't depend on the data. \n- The solving time scales roughly like $O($sqrt(pair counting data size) * (number of merges)$^2)$ but is dependent on the data. \n\n(Note the number of merges is equal to the vocabulary size).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lz7u9okEsH", "reviewer": "Reviewer_68Uz", "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.", "questions": "1.\tWhat the meaning of random guessing? Are there alternative methods to infer the proportions of different categories, possibly leveraging model performance metrics or behavioral patterns? \n2.\tWhat strategies can be employed to ensure the quality of sample data for estimating pair frequencies.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe paper introduces a previously understudied problem of data mixture inference, complementing existing membership inference attacks that focus on individual instances.\n2.\tThe proposed attack method, based on BPE tokenizers' ordered merge rules, giving some insightful findings in inferring data mixture proportions.", "weaknesses": "1.\tThe attack relies on the specific behavior and structure of BPE tokenizers, which limits the generalizability of the method to different tokenizers.\n2.\tThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the “previously understudied” problem we address and the \"insightful findings.\" We have taken care to investigate all the questions you raise (with new experiments) and hope that our response addresses your concerns.\n\n## Today’s LLMs use BPE\nWhile it is true that other tokenization algorithms may exist, BPE is the universal choice for today’s production models; in fact, we manually verified that **all top 100 models on ChatbotArena use BPE tokenizers**. In the future, powerful LMs that use tokenizers other than BPE may be released, but we cannot guess what algorithm they will use.\n\n## New experiments show that the attack is robust to distribution shift\nFollowing your suggestion, we run **new experiments where there is an extreme distribution shift between the training data of the tokenizer and the data available to the attacker**. We show that the attack performance degrades gracefully in this setting, **remaining strong even under extreme shift**. *Please see the global response for more details.*\n\n## New experiments show our attack beats baseline based on tokenizer encoding efficiency\nThank you for your insightful suggestion to try a baseline based on the tokenizer’s performance on each language! We implement this baseline and find that it baseline achieves $\\log_{10}$ MSE of $-2.29$, compared to $-1.84$ random guessing and $-7.66$ for our attack. *Please see the global response for details.* Thus **while the baseline is meaningfully better than random, our attack is still $10^5 \\times$ stronger**! This highlights the difficulty of the problem and the effectiveness of our attack, and we will definitely include this comparison in the next revision.\n\n## Design considerations for sample data\nAs an attacker, one should use any information available to strengthen the attack. If the attacker knows that the training data has a certain property, it would be beneficial to use that kind of data for the pair counting. However it is often the case that the attacker knows very little about the data. In this case, if an attacker has access to multiple data sources, multiple preprocessing techniques etc., it would be beneficial to include all of them as separate categories for the optimization to consider. This increases the chances of finding a mixture that is a good fit for the tokenizer.\n\nMoreover, our new experiments under distribution shift (mentioned above) show empirically that performance remains strong in this setting.\n\n## Clarification regarding random guessing\nThe random guess is calculated by sampling uniformly from the $n$-dimensional simplex, where $n$ is the number of categories. Note that the ground truth values are also sampled this way, so the random guesses are from the “correct” distribution. What we report is the average error over many such guesses.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ig12VjI36r", "reviewer": "Reviewer_vDkN", "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.", "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?\n- 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. \n- 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": "Authors should elaborate more on the potential defenses against this attack.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Originality: The paper proposes the novel task of data mixture inference, and provides a compelling method to do so. \n- Quality: Both the task and proposed method is presented in a compelling way. The task of data mixture inference is formalized, and a novel, technically developed method is proposed. Both the evaluation in a controlled setup as well as the application of the method on other models for which the data mixture is unknown is convincing and interesting. 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).\n- Clarity: the paper is written very clearly. \n- Significance: The paper proposes an attack able to discover a fundamental design decision made by model developers, which they likely want to keep proprietary. Exposing this attack, with its results is quite valuable to the field.", "weaknesses": "- Originality: NA\n- 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).\n- Clarity: NA\n- Significance: A more elaborate discussion on potential defenses would increase the significance of the work's contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the “novel” task we study, our “technically developed method,” and the “convincing,” \"valuable results\" on a \"fundamental design decision\" made by model developers.\n\nThank you for the thoughtful questions, and we hope that our response addresses your concerns!\n\n## Elaboration on defense based on merge list reordering\nConsider a merge list with three entries,\n\n(`h`, `e`)\n\n(`t`, `h`)\n\n(`t`, `he`)\n\nObserve that to tokenize the word “the,” first (`h`, `e`) is merged, then (`t`, `he`). Thus, “the” is encoded as a single token.\n\nNow suppose the first two merges are flipped. Then the merge (`t`, `h`) would be applied first, and (`t`, `he`) is no longer applicable. Now, “the” would be represented as a sequence of two tokens, [`th`, `e`]. This is a problem because “the” is represented in a completely different way than in training!\n\nHowever if we instead consider a new merge, (`i`, `n`), we see that it can be placed anywhere in the current merge list. This is because it is completely independent of the current merges, as they do not share any tokens. \n\nThus, *some* functionality-preserving reorderings are possible. However, because these are fairly limited, we expect the attack to still be applicable as described in the paper.\n\n## Our attack is surprisingly robust to unaccounted-for categories\n\nFollowing your suggestion, we run **new experiments simulating the setting where only a subset of true categories are known**. We find that our attack is surprisingly robust — **even when $1/10$ of the probability mass is unaccounted for, our attack achieves $\\log_{10}$ MSE around $-6$**, compared to $-7.69$ with the full set of languages. *Please see the global response for details.*\n\n## New experiments show our attack beats baseline based on tokenizer encoding efficiency\n\nThank you for your suggestion to try a baseline based on the tokenizer’s performance on each language. We implement this baseline and find that this baseline achieves $\\log_{10}$ MSE of $-2.29$, compared to $-1.84$ random guessing and $-7.66$ for our attack. Thus **while the baseline is meaningfully better than random, our attack is still $10^5 \\times$ stronger!** This highlights the difficulty of the problem and the effectiveness of our attack, and we will definitely include this comparison in the next revision. *Please see the global response for details.*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to the reviewers for observing the “novelty” of our data mixture inference attack, its empirical “effectiveness” and the “noteworthy practical implications” of uncovering information about “a fundamental design decision”!

Following insightful reviewer suggestions, we have run several new experiments which we believe strengthen our paper greatly and will be incorporated into the next revision of the paper.

## Our attack beats baseline based on tokenizer performance

Following reviewer suggestions, we provide a **new baseline based on the tokenizer’s encoding efficiency for each language**, and find that **our attack outperforms it by a factor of $10^5$**. In particular, we consider the byte-to-token ratio for the given tokenizer on each language, normalized by that of a tokenizer trained on only that language (with the same total amount of data). The normalization adjusts for any language-specific characteristics that make it inherently easier or harder to encode. We expect that, for instance, if the target language is a *large* proportion of the training data, then it will encode *more* bytes per token (after normalization).

We plot the relationship between the true training proportion and (normalized) tokenizer efficiency in *Figure 1 of the attached PDF*, using the setting where tokenizers are trained on mixtures of $n=10$ languages. As we would expect, the more training data there is for a language, the more efficiently the tokenizer encodes it! However, it is clear that the correlation is not nearly strong enough to precisely recover the true proportion ($x$-axis) precisely given just the encoding efficiency ($y$-axis).

More rigorously, we learn a linear model on the log-log relationship to predict the true proportion given the encoding efficiency. Then we renormalize the predictions for the set of languages into a probability distribution. **This gives $\log_{10}$ MSE of $-2.22$, which is marginally better than random guessing at $-1.84$ but far worse than our attack’s performance at $-7.66$!** Thus, while the baseline gives us a better guess, it does not come close to achieving the kind of precision possible with our attack.

## Our attack is surprisingly robust to unaccounted-for categories

We investigate our attack’s performance when there are unaccounted-for categories. We use the setting with tokenizers trained on mixtures of $n=112$ languages, and omit between 1 and 50 languages when running the solver. To calculate the MSE, we compare our prediction against the renormalized ground truth, after removing the omitted languages. This captures whether we can still accurately recover the distribution of known categories! *See Figure 2 in attached PDF* for the relationship between total probability mass of the omitted languages and MSE. We see that MSE degrades predictably as the omitted probability mass increases.

We find that our attack is surprisingly robust. **Even when $1/10$ of the probability mass is unaccounted for, our attack achieves $\log_{10}$ MSE around $-6$, compared to $-7.69$ with the full set of languages** (recall random guessing here is $-3.82$).

## Attack performance remains strong under distribution shift

We run new experiments where the sample data is not drawn from the same distribution as the tokenizer training data. In particular, we use the Oscar dataset (web data) to train tokenizers on mixtures of languages, but estimate pair frequencies using Wikipedia data for the same languages.

Note that Wikipedia data is significantly different from web data in terms of vocabulary (e.g., more formal words, named entities & dates, Wikipedia headers). **Even under this extreme distribution shift, our attack achieves $\log_{10}$ MSE of $-3.53$**, compared to random guessing at $-1.84$ (100x better than random). We expect the distribution shift of a realistic attack will be much less extreme than this (e.g., using a different corpus of web data).

Meta-review: 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.
Decision: Accept (poster)