Membership Inference Attacks on Tokenizers of Large Language Models

Meng Tong, Yuntao Du, Kejiang Chen, Weiming Zhang, Ninghui Li

Introduction

Membership Inference Attacks (MIAs) aim to determine whether a specific data sample was included in a model's training set. While critical for auditing privacy and legal compliance, MIAs on Large Language Models (LLMs) are traditionally computationally expensive and prone to noise. Recent research identifies a novel, highly efficient attack vector: the LLM tokenizer. By exploiting the Byte-Pair Encoding (BPE) process, attackers can identify training data membership with high accuracy at a fraction of the cost of traditional methods.

The Challenge of Traditional MIA

Traditional MIAs typically target the model’s final outputs, such as word probabilities. However, these methods face significant hurdles in real-world scenarios. Evaluating such attacks often requires "shadow training"—the process of training multiple large-scale models from scratch—which is prohibitively expensive for modern LLMs. Furthermore, training data is frequently plagued by mislabeled samples and distribution shifts, which degrade the reliability of traditional inference signals.

Challenges in traditional Membership Inference Attacks (MIA) including mislabeled samples, distribution shifts, and model size mismatches.

The Tokenizer as an Attack Vector

Tokenizers are the "dictionaries" LLMs use to convert raw text into numerical tokens. To ensure transparent billing and interoperability, many developers open-source their tokenizers. This transparency inadvertently creates a privacy leak.

The Byte-Pair Encoding (BPE) algorithm, commonly used in tokenizers, iteratively merges frequent character pairs. This process is susceptible to a form of "overfitting": if a training dataset contains rare but distinctive strings (e.g., specific usernames or unique legal clauses), BPE is likely to merge these into the final vocabulary only if that specific dataset was present during training.

Attack Methodologies

The study evaluates several attack methods, most notably:

  1. Vocabulary Overlap: Attackers compare the "distinctive" tokens of a target tokenizer with those of "shadow tokenizers" trained on known datasets using the Jaccard index.
  2. Frequency Estimation: This more efficient method leverages the power-law distribution of token frequencies. By estimating the "self-information" of tokens, attackers can identify membership signals in under 20 minutes without training shadow models.

Scaling Laws and Privacy Vulnerability

A counter-intuitive finding of this research is that as LLMs scale their vocabulary sizes to improve performance, they become more vulnerable to tokenizer-based MIAs. Larger vocabularies provide more "slots" for rare, distinctive tokens from the training data to be memorized.

Average merge index across different vocabulary sizes (80k to 170k), illustrating how larger vocabularies provide more distinct signals for membership inference.

Key Results and Real-World Evidence

The proposed attacks demonstrate remarkable effectiveness:

  • High Accuracy: The Vocabulary Overlap attack achieved an AUC of 0.771 against a 200k-token tokenizer.
  • Precision: At a strict 1% False Positive Rate (FPR), the attacks maintained a True Positive Rate (TPR) of nearly 35%.
  • Efficiency: The Frequency Estimation attack can process over 4,000 target datasets in roughly 25 minutes, a massive improvement over the thousands of GPU hours required for model-based MIAs.

Real-world evidence supports these findings. For instance, the unique token davidjl—associated with a specific Reddit user—appears in OpenAI’s tokenizer, serving as a "smoking gun" that tokenizers memorize specific strings from their training sets.

Conclusion

The discovery of tokenizer-based MIAs highlights a fundamental "transparency paradox": the very tools provided for user transparency can be weaponized to compromise data privacy. While defenses like "Min Count" filtering (removing rare tokens) can mitigate these attacks, they often come at the cost of compression efficiency and model utility. As LLMs continue to grow in complexity and vocabulary size, developing privacy-preserving tokenization methods, such as those utilizing Differential Privacy, remains a critical challenge for the field.

Summary updated

BibTeX
@misc{tong2025membership,
  author = {Meng Tong and Yuntao Du and Kejiang Chen and Weiming Zhang and Ninghui Li},
  title = {{Membership Inference Attacks on Tokenizers of Large Language Models}},
  year = {2025},
  eprint = {2510.05699},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.05699},
}
Figure