Data Mixture Inference Attack: BPE Tokenizers Reveal Training Data Compositions

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.

Thank you for the thoughtful questions, and we hope that our response addresses your concerns!

Elaboration on defense based on merge list reordering

Consider a merge list with three entries,

(h, e)

(t, h)

(t, he)

Observe that to tokenize the word “the,” first (h, e) is merged, then (t, he). Thus, “the” is encoded as a single token.

Now 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!

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

Thus, 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.

Our attack is surprisingly robust to unaccounted-for categories

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

New experiments show our attack beats baseline based on tokenizer encoding efficiency

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

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.

Today’s LLMs use BPE

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

New experiments show that the attack is robust to distribution shift

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

New experiments show our attack beats baseline based on tokenizer encoding efficiency

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

Design considerations for sample data

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

Moreover, our new experiments under distribution shift (mentioned above) show empirically that performance remains strong in this setting.

Clarification regarding random guessing

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

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.

Theoretical analysis

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

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

New experiments show that the attack is robust to distribution shift

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

Starting vocabulary and pretokenization

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

Token frequency distribution

Indeed, 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.

Runtime scaling

As 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:

• The pair counting time scales like $O($pair counting data size * number of merges$)$ and doesn't depend on the data.
• The solving time scales roughly like $O($sqrt(pair counting data size) * (number of merges)$^2)$ but is dependent on the data.

(Note the number of merges is equal to the vocabulary size).

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.

Today’s LLMs use BPE

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

Effect of sampling error on attack performance

The 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!

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

Further discussion of implications

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

In 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:

1. 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.
2. 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.
3. 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).

[1] Fishing for Magikarp: Automatically Detecting Under-trained Tokens in Large Language Models. 2024.

[2] Stealing Part of a Production Language Model. 2024.

Tokenizer training data vs pretraining data

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