acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Byte Pair Encoding Tokenizers for Large Language Models

Abstract

Tokenizers are a standard part of large language model (LLM) releases, providing practical tools for splitting text and counting tokens. However, vocabulary and ordered merge list released with common byte pair encoding (BPE) tokenizers for LLMs reflect recurring patterns in the data corpus used during their training. We ask whether access to such a tokenizer can reveal that a particular website was included in its training data. Under three access models, exposing (1) token counts only, (2) token identities, and (3) the full BPE tokenizer with both the vocabulary and the ordered merge list, we design website-level membership inference attacks calibrated using shadow tokenizers trained with and without the target website. Under the most restrictive token-count access, our attack reaches 60.9 TPR at 1% FPR, while the best prior attack under the same access stays at 1.3% and therefore does no better than guessing. Motivated by this leakage, we also evaluate defenses. We find that simple low-count filtering reduces the attack success under token-count access but does not reliably protect against the stronger token-identity and merge-list attacks. Moreover, prior defenses provide no provable guarantees on privacy leakage. We therefore propose DP-BPE, the first differentially private BPE training algorithm, which gives the released vocabulary and merge list a provable website-level privacy guarantee. At a 4% relative utility cost, it reduces every attack we evaluate to close to random guessing, while prior defenses leak substantially more. We also open-source our DP-BPE as a Rust implementation for the community. Together, our findings highlight the need for privacy-aware tokenizer training and show that a website-level privacy guarantee is possible at a small utility cost.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Membership Inference Attack, Tokenizer

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_G29qOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper focuses on the privacy perspective of tokenizers of large language models. The authors first propose a membership inference attack against tokenizers that outperforms an existing baseline. Based on the MIAs, the authors then propose a differentially private tokenizer that can defend against the MIAs.

Critical strengths
  • The paper investigates a practical threat model as the tokenizer is usually a public component of LLMs.
  • The performance gain of the proposed MIA is significant compared to the baseline.
Critical weaknesses
  • The proposed MIA requires a large amount of in-distribution data to train shadow tokenizers. This assumption is not practical in real-world scenarios.
  • The tokenizers are evaluated only on bytes per token. However, tokenization is mostly a step for LLMs. The impact of tokenization on downstream tasks (e.g., language modeling) is not evaluated.
  • Only one dataset is used for experiments.
  • Some designs of the proposed differentially private tokenizer are not well justified. It is unclear why the authors picked those certain designs. For example, the binary word presence vector can be compared with a vector of clipped word counts, as a word can appear many times in a document. The uniform subsampling can be compared with frequency-aware sampling.
  • Missing analysis on NmaxN_{max} and LmaxL_{max}.
Questions for authors

See weaknesses

5 comments

We thank the Reviewer for recognizing our practical threat model and the significant gain of our MIA over prior attacks. We address all comments below.

W1: The proposed MIA requires a large amount of in-distribution data to train shadow tokenizers. This assumption is not practical in real-world scenarios.

Since tokenizers train on web text and large web crawls such as Common Crawl are public, an adversary can download other websites from the same source. In-distribution shadow data is the standard MIA assumption, as in LiRA. The shadow data must come from the same distribution as the training data, but it does not have to be the training data itself.

To further address the Reviewer's comment, we ran additional experiments where the adversary does not hold the tested websites but other websites instead, matching the availability of web crawls like Common Crawl. We trained the shadow tokenizers on one half of the C4 websites of the paper and tested the other half, so no shadow tokenizer is trained on a tested website. For comparison, the first two rows use the shadow tokenizers of the paper. In the first row, as in Table 1, half of them are trained with the tested website. The second row uses only those trained without it, as in the new setting. The table reports TPR@1%FPR of the Token-Count Attack at a vocabulary of 200,000.

Shadow tokenizersToken-Count Attack, TPR@1%FPR
Paper, half trained with the tested website (Table 1)60.9 ±\pm 0.2
Paper, all trained without the tested website (Table 13)58.0 ±\pm 0.3
Disjoint from the tested websites28.5 ±\pm 0.7

While performance is smaller than when the shadow tokenizers are trained on the tested websites, the attack still detects 28.5% of the member websites, against 1% for random guessing. We added a new Appendix G.8 with the new Table 14, summarized it in Section 6.4, and added a sentence to Section 3.

W2: The tokenizers are evaluated only on bytes per token. However, tokenization is mostly a step for LLMs. The impact of tokenization on downstream tasks (e.g., language modeling) is not evaluated.

To address the Reviewer's comment, we pretrained GPT-2-small on C4 with the undefended tokenizer and with DP-BPE at ε∈{1,3,10}\varepsilon \in \{1, 3, 10\}. We trained every model for 3,094 steps on 1.62×1091.62\times10^{9} tokens with three seeds and evaluated it on downstream tasks.

The first table below reports zero-shot accuracy on three benchmarks. The second table reports accuracy after fine-tuning on two GLUE tasks.

TokenizerBLiMPPIQAARC-Easy
Undefended78.1 ±\pm 0.361.7 ±\pm 0.337.7 ±\pm 0.2
DP-BPE, ε=1\varepsilon = 172.8 ±\pm 0.358.3 ±\pm 0.532.2 ±\pm 0.0
DP-BPE, ε=3\varepsilon = 373.5 ±\pm 0.059.2 ±\pm 0.333.4 ±\pm 0.2
DP-BPE, ε=10\varepsilon = 1074.3 ±\pm 0.360.2 ±\pm 0.135.4 ±\pm 0.2
TokenizerMRPCQNLI
Undefended75.9 ±\pm 0.982.6 ±\pm 0.3
DP-BPE, ε=1\varepsilon = 173.8 ±\pm 0.982.5 ±\pm 0.1
DP-BPE, ε=3\varepsilon = 374.3 ±\pm 1.182.5 ±\pm 0.2
DP-BPE, ε=10\varepsilon = 1076.9 ±\pm 0.882.7 ±\pm 0.2

DP-BPE does not lead to a significant drop in downstream performance. After fine-tuning, it is within 0.1 points of the undefended tokenizer on QNLI at every ε\varepsilon. On MRPC it is 2.1 and 1.6 points lower at ε\varepsilon = 1 and 3 and 1.0 point higher at ε=10\varepsilon = 10. On BLiMP, PIQA and ARC-Easy it is 1.5 to 5.5 points lower, and the gap shrinks as ε\varepsilon grows, as bytes per token does. We added the new Table 4, described the evaluation in Section 6.1, summarized the results in Section 6.3, and added a new Appendix I.4 with the training and evaluation details.

W3: Only one dataset is used for experiments.

To address the Reviewer’s comment, we repeated the undefended and DP-BPE experiments at a vocabulary size of 200,000 on the FineWeb dataset, which differs from C4 in crawl (and hence, websites included) and filtering. Overall, we observe that the trends on FineWeb are very similar to those on C4.

We built the pool of 19,628 websites as for C4 and kept the rest of the setup.

UndefendedDP-BPE, ε=1\varepsilon = 1DP-BPE, ε=3\varepsilon = 3DP-BPE, ε=10\varepsilon = 10
Bytes per token5.04 ±\pm 0.004.00 ±\pm 0.004.51 ±\pm 0.004.88 ±\pm 0.00
Compression Rate1.2 ±\pm 0.11.0 ±\pm 0.01.1 ±\pm 0.01.0 ±\pm 0.0
Token-Count Attack (ours)63.8 ±\pm 0.51.0 ±\pm 0.01.1 ±\pm 0.01.2 ±\pm 0.1
Vocabulary Overlap16.9 ±\pm 0.51.0 ±\pm 0.01.0 ±\pm 0.01.0 ±\pm 0.0
Token-Identity Attack (ours)53.8 ±\pm 0.21.0 ±\pm 0.01.0 ±\pm 0.00.9 ±\pm 0.0
Frequency10.1 ±\pm 0.31.0 ±\pm 0.01.0 ±\pm 0.11.0 ±\pm 0.0
Naive Bayes10.0 ±\pm 0.01.1 ±\pm 0.11.1 ±\pm 0.11.1 ±\pm 0.1
Merge-Order with Bernoulli (ours)56.1 ±\pm 0.21.0 ±\pm 0.00.9 ±\pm 0.00.6 ±\pm 0.0
Merge-Order with Bradley-Terry (ours)47.6 ±\pm 0.31.0 ±\pm 0.01.0 ±\pm 0.01.0 ±\pm 0.0

As on C4, our MIAs outperform the prior attacks, and every undefended attack TPR is within 3 points of its value on C4. The strongest prior attack, Vocabulary Overlap, reaches 16.9% TPR@1%FPR against the undefended tokenizer. DP-BPE reduces every attack to chance and keeps 79%, 89% and 97% of the bytes per token of the undefended tokenizer at ε=1\varepsilon = 1, 3, and 10. We added the new Table 3 to Section 6.3 and a new Appendix G.9, named FineWeb in Section 6.1, and summarized it in Section 6.2.

W4: Some designs of the proposed differentially private tokenizer are not well justified. It is unclear why the authors picked those certain designs. For example, the binary word presence vector can be compared with a vector of clipped word counts, as a word can appear many times in a document. The uniform subsampling can be compared with frequency-aware sampling.

We considered several alternatives when designing DP-BPE and chose word presence with uniform subsampling because this combination gives the highest bytes per token at the same privacy guarantee. A word is released only if its noisy count exceeds the threshold τ\tau, and τ\tau grows with the largest amount one website can add to the count of a word. Word presence limits this amount to 1, so τ\tau is lowest and more words are released. Uniform subsampling matches this choice, since it also ignores how often a word occurs within a website. Following the Reviewer's suggestion, we explicitly compared different variants and design choices at ε=10\varepsilon = 10 and a vocabulary of 200,000. We compare the subsampling rules at Nmax⁡=5,000N_{\max} = 5{,}000, where the cap applies to many websites.

VariantBytes per tokenToken-CountToken-IdentityMerge-Order, BernoulliMerge-Order, Bradley-Terry
Word presence, uniform subsampling (paper)4.72 ±\pm 0.011.2 ±\pm 0.11.1 ±\pm 0.00.4 ±\pm 0.01.0 ±\pm 0.0
Counts clipped at 24.68 ±\pm 0.011.2 ±\pm 0.11.0 ±\pm 0.00.4 ±\pm 0.01.0 ±\pm 0.0
Counts clipped at 44.60 ±\pm 0.011.3 ±\pm 0.01.1 ±\pm 0.10.4 ±\pm 0.01.0 ±\pm 0.0
Counts clipped at 164.36 ±\pm 0.011.2 ±\pm 0.01.0 ±\pm 0.00.4 ±\pm 0.01.0 ±\pm 0.0
Nmax⁡=5,000N_{\max}=5{,}000, uniform subsampling4.71 ±\pm 0.011.1 ±\pm 0.01.0 ±\pm 0.00.4 ±\pm 0.00.9 ±\pm 0.0
Nmax⁡=5,000N_{\max}=5{,}000, most frequent words kept4.70 ±\pm 0.011.2 ±\pm 0.01.0 ±\pm 0.00.5 ±\pm 0.00.9 ±\pm 0.0
Nmax⁡=5,000N_{\max}=5{,}000, sampled proportionally to frequency4.71 ±\pm 0.011.2 ±\pm 0.11.0 ±\pm 0.00.4 ±\pm 0.01.0 ±\pm 0.0

Clipped counts lower bytes per token from 4.72 to between 4.68 and 4.36. This trend can be explained as follows: A website adds up to cc instead of 1 to the count of a word when counts are clipped at cc. Its vector then has a larger L2L_2 norm, so more websites are rescaled to Lmax⁡=30L_{\max} = 30. The rescaling lowers the count that each website adds to a word, while the noise stays the same and the release threshold rises by c−1c - 1. Fewer words are therefore released.

The two frequency-aware rules give 4.70 and 4.71 vs. 4.71 for uniform subsampling. Frequency-aware sampling therefore gives no gain, and we keep the simpler rule.

Every variant leaves the attacks at chance. We added the new Table 20 to Appendix I.2 and summarized it in Section 6.3.

W5: Missing analysis on Nmax⁡N_{\max} and Lmax⁡L_{\max}.

Conceptually, Lmax⁡L_{\max} sets the noise scale σ\sigma, and the release threshold τ\tau depends on both σ\sigma and Nmax⁡N_{\max}, so the guarantee holds for every value of either. To address the Reviewer's comment, we ran additional experiments, where we ablate over these parameters at ε=10\varepsilon = 10 and a vocabulary of 200,000, keeping the other values fixed.

Lmax⁡L_{\max}Nmax⁡N_{\max}Bytes per tokenToken-CountToken-IdentityMerge-Order, BernoulliMerge-Order, Bradley-Terry
30 (paper)50,000 (paper)4.72 ±\pm 0.011.2 ±\pm 0.11.1 ±\pm 0.00.4 ±\pm 0.01.0 ±\pm 0.0
3.7550,0004.70 ±\pm 0.011.2 ±\pm 0.01.0 ±\pm 0.10.4 ±\pm 0.01.1 ±\pm 0.1
7.550,0004.71 ±\pm 0.011.3 ±\pm 0.01.1 ±\pm 0.10.4 ±\pm 0.01.0 ±\pm 0.0
1550,0004.72 ±\pm 0.011.1 ±\pm 0.00.9 ±\pm 0.00.4 ±\pm 0.01.0 ±\pm 0.0
6050,0004.70 ±\pm 0.011.2 ±\pm 0.01.0 ±\pm 0.00.5 ±\pm 0.01.0 ±\pm 0.0
12050,0004.52 ±\pm 0.011.1 ±\pm 0.11.0 ±\pm 0.10.5 ±\pm 0.01.0 ±\pm 0.0
301,0004.48 ±\pm 0.011.1 ±\pm 0.01.1 ±\pm 0.10.7 ±\pm 0.00.9 ±\pm 0.0
302,5004.64 ±\pm 0.011.2 ±\pm 0.10.9 ±\pm 0.00.5 ±\pm 0.00.9 ±\pm 0.0
305,0004.71 ±\pm 0.011.1 ±\pm 0.01.0 ±\pm 0.00.4 ±\pm 0.00.9 ±\pm 0.0
3010,0004.73 ±\pm 0.011.1 ±\pm 0.01.0 ±\pm 0.10.4 ±\pm 0.01.0 ±\pm 0.0
3025,0004.73 ±\pm 0.011.1 ±\pm 0.01.0 ±\pm 0.00.4 ±\pm 0.01.0 ±\pm 0.0
30100,0004.72 ±\pm 0.011.1 ±\pm 0.11.0 ±\pm 0.00.4 ±\pm 0.01.0 ±\pm 0.0

The attacks remain at random for all values. At ε=10\varepsilon = 10, the utility of DP-BPE is robust to the choice of these hyperparameters over a wide range, so they do not need to be tuned on the private corpus. For Lmax⁡L_{\max} from 3.75 to 60 and Nmax⁡N_{\max} from 5,000 to 100,000, bytes per token stays between 4.70 and 4.73, against 4.72 in the paper. At Lmax⁡=120L_{\max} = 120, bytes per token drops to 4.52, because the noise grows with Lmax⁡L_{\max} while the contribution of almost every website to the word counts stays the same. At Nmax⁡=1,000N_{\max} = 1{,}000, it drops to 4.48, because the cap removes words from most websites. We added the new Table 19 to Appendix I.2 and summarized it in Section 6.3.

If the above answers address the Reviewer's concerns, we would greatly appreciate it if they could consider updating their score. We are also happy to address any remaining questions.

Reviewer_i4g1OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper aims to answer whether released tokenizers for models can reveal information about what websites were used in the training based on the token counts, actual tokens and rankings. The paper shows that strong membership inference attacks can be formulated based on the 3 different types of access which can break website-level privacy. The paper then introduces DP-BPE, a differentially private byte pair encoding tokenizer in which the contribution from each website is clipped (effectively the sensitivity is bounded). These clipped contributions are then released using standard DP histogram techniques. The experiments show that the attacks proposed work better than previous MIA and that DP-BPE helps to protect against these attacks with minimal loss of BPT.

Critical strengths
  1. The paper provides the first private BPE tokenizer with formal guarantees at website-level and also shows that it defends against strong membership inference attacks.
  2. The paper formalizes the 3 types of access for tokenizers and how each can open an attack surface. Even the token count access leads to strong MIA results.
  3. DP-BPE design is simple, first perform noisy aggregation with bounded per website contribution and then standard BPE as post-processing.
Critical weaknesses
  1. While the application of DP to BPE tokenizers at website-level is novel, the DP-BPE construction relies on standard techniques based on prior works.
  2. Utility is evaluated only through BPT. This is a useful compression metric, but it does not establish downstream model quality. Adding broader tokenization evaluations or a small downstream experiment would help.
Questions for authors
  1. For the token count attack, can the authors explain what will happen if the true BPT scores distribution is not Gaussian, especially if it has a heavier tail or multiple modes.
  2. Can the authors explain how the n, lambda and epsilon for the different methods actually compare and provide intuition into what epsilon 3 or epsilon 10 means in this context.
3 comments

We thank the Reviewer for recognizing the strength of our membership inference attacks and our contribution of DP-BPE as the first BPE tokenizer with a formal website-level guarantee that protects against the “attacks with minimal loss of BPT”. We address their comments below.

W1: While the application of DP to BPE tokenizers at website-level is novel, the DP-BPE construction relies on standard techniques based on prior works.

We agree that DP-BPE builds on established mechanisms and we consider this a strength because it allows us to leverage the privacy guarantees from the Gaussian Sparse Histogram Mechanism (Karrer et al., 2024). However, our novel contribution here is reducing website-level private BPE training to a single histogram release. This reduction is not straightforward for 3 reasons:

(1) It has to avoid composition over merges. The natural way to privatize BPE is to privatize each merge decision, as, for example, done by Tong et al. (2026). However, with up to 200,000 merges, this does not allow for a reasonable ε\varepsilon. Moreover, as every website can contribute an arbitrary number of occurrences of a pair, the per-merge sensitivity is unbounded, so that no finite ε\varepsilon would exist at all (Appendix E.2).

DP-BPE avoids this problem by observing that, with a fixed pre-tokenizer, BPE training depends on the corpus only through its word histogram, since merges never cross word boundaries. We therefore privatize this histogram once and run an unmodified BPE trainer on it. All merges are post-processing, so the guarantee holds for any number of merges and vocabulary size without composition, and sensitivity only needs to be bounded at the histogram level (see (2)).

(2) It has to formally bound any website’s contribution. Prior DP tokenizers (Hoory et al., 2021; Ponomareva et al., 2022) protect single sentences. A website contributes 50 pages with unboundedly many words. We bound it as follows:

  1. Counting words once per website bounds per-word sensitivity.
  2. The cap Nmax⁡N_{\max} enables the threshold calibration.
  3. The norm bound Lmax⁡L_{\max} keeps σ\sigma from growing with Nmax⁡\sqrt{N_{\max}}.

(3) Finally, it has to hide that a word exists. The words that can appear are corpus dependent, so the release must hide which words are in there (in addition to the counts). We handle this with a threshold calibrated to Nmax⁡N_{\max}.

Our design choices for the three challenges allow us to yield a practical construction. For example, at ε=10\varepsilon = 10, DP-BPE reduces every MIA to chance while retaining 4.72 BPT against 4.92 undefended (4% relative).

W2: Utility is evaluated only through BPT. This is a useful compression metric, but it does not establish downstream model quality. Adding broader tokenization evaluations or a small downstream experiment would help.

To address the Reviewer's comment, we pretrained GPT-2-small on C4 with the undefended tokenizer and with DP-BPE at ε∈{1,3,10}\varepsilon \in \{1, 3, 10\}. We trained every model for 3,094 steps on 1.62×1091.62\times10^{9} tokens with three seeds and evaluated it on downstream tasks.

The first table below reports zero-shot accuracy on three benchmarks. The second table reports accuracy after fine-tuning on two GLUE tasks.

TokenizerBLiMPPIQAARC-Easy
Undefended78.1 ±\pm 0.361.7 ±\pm 0.337.7 ±\pm 0.2
DP-BPE, ε=1\varepsilon = 172.8 ±\pm 0.358.3 ±\pm 0.532.2 ±\pm 0.0
DP-BPE, ε=3\varepsilon = 373.5 ±\pm 0.059.2 ±\pm 0.333.4 ±\pm 0.2
DP-BPE, ε=10\varepsilon = 1074.3 ±\pm 0.360.2 ±\pm 0.135.4 ±\pm 0.2
TokenizerMRPCQNLI
Undefended75.9 ±\pm 0.982.6 ±\pm 0.3
DP-BPE, ε=1\varepsilon = 173.8 ±\pm 0.982.5 ±\pm 0.1
DP-BPE, ε=3\varepsilon = 374.3 ±\pm 1.182.5 ±\pm 0.2
DP-BPE, ε=10\varepsilon = 1076.9 ±\pm 0.882.7 ±\pm 0.2

DP-BPE does not lead to a significant drop in downstream performance. After fine-tuning, it is within 0.1 points of the undefended tokenizer on QNLI at every ε\varepsilon. On MRPC it is 2.1 and 1.6 points lower at ε\varepsilon = 1 and 3 and 1.0 point higher at ε=10\varepsilon = 10. On BLiMP, PIQA and ARC-Easy it is 1.5 to 5.5 points lower, and the gap shrinks as ε\varepsilon grows, as bytes per token does. We added the new Table 4, described the evaluation in Section 6.1, summarized the results in Section 6.3, and added a new Appendix I.4 with the training and evaluation details.

Q1: For the token count attack, can the authors explain what will happen if the true BPT scores distribution is not Gaussian, especially if it has a heavier tail or multiple modes.

Our attack models the BPT of a website across shadow tokenizers as Gaussian, as LiRA (Carlini et al., 2022) does. Since we set the threshold empirically on the true non-members, the 1% FPR holds regardless of the fit. A poor fit can only produce worse scores and thus a lower TPR, never an overestimated one.

To quantify this, we ran additional experiments and replaced the Gaussian reference models by a log-normal, a heavier-tailed Student-t, a skew-normal, and two kernel density estimates (KDEs), which can represent multiple modes. One KDE is fitted per website. The other shares one standardized shape across websites. The table reports TPR@1%FPR at each vocabulary size.

Distribution in the attack40,00080,000110,000140,000170,000200,000
Gaussian, used by our attack6.4 ±\pm 0.118.6 ±\pm 0.129.2 ±\pm 0.241.1 ±\pm 0.351.6 ±\pm 0.360.9 ±\pm 0.2
Log-normal6.4 ±\pm 0.118.6 ±\pm 0.129.2 ±\pm 0.241.0 ±\pm 0.351.6 ±\pm 0.360.9 ±\pm 0.2
Student-t6.6 ±\pm 0.118.3 ±\pm 0.128.8 ±\pm 0.340.8 ±\pm 0.351.4 ±\pm 0.460.7 ±\pm 0.4
Skew-normal6.5 ±\pm 0.118.7 ±\pm 0.129.4 ±\pm 0.241.2 ±\pm 0.351.9 ±\pm 0.361.4 ±\pm 0.2
Kernel density, per website6.5 ±\pm 0.219.0 ±\pm 0.229.9 ±\pm 0.242.0 ±\pm 0.252.6 ±\pm 0.262.0 ±\pm 0.3
Kernel density, shared shape6.6 ±\pm 0.119.0 ±\pm 0.229.6 ±\pm 0.241.7 ±\pm 0.252.1 ±\pm 0.361.5 ±\pm 0.2

All models stay within 1.1 points of the Gaussian, so our results hold if the distribution types between reference models and data do not strictly align. The KDEs are marginally stronger, making our reported leakage a slight underestimate. We keep the Gaussian for consistency with LiRA and simplicity. We added these new results as Table 15 in the new Appendix G.10 and summarized them in Section 6.2.

Q2: Can the authors explain how the n, lambda and epsilon for the different methods actually compare and provide intuition into what epsilon 3 or epsilon 10 means in this context.

nmin⁡n_{\min}, λ\lambda and ε\varepsilon are hyperparameters of three different defenses, so their values are not directly comparable. Min-Count removes every token that occurs fewer than nmin⁡n_{\min} times in the training data. Softmax BPE picks each merge at random with a preference for frequent pairs, and a larger λ\lambda makes its choices closer to standard BPE. Neither defense gives a formal guarantee. Softmax BPE resembles the exponential mechanism, but one website can add arbitrarily many occurrences of a pair, so no finite λ\lambda corresponds to a finite ε\varepsilon. In DP-BPE, ε\varepsilon is a privacy guarantee. It bounds how much adding or removing one website can change the output tokenizer, and a smaller ε\varepsilon gives stronger protection.

In practice, ε\varepsilon determines the noise added to the word counts and the threshold that a noisy count must pass. Each website adds at most one to the count of a word, so a word is released only if about 89 websites or more use it at ε=10\varepsilon = 10, and about 244 or more at ε=3\varepsilon = 3. Words specific to one or a few websites, on which our attacks rely, are therefore almost never released. Min-Count also sets a threshold, but on occurrences, so a single website that repeats a token nmin⁡n_{\min} times passes it. We expanded the description of both baselines in Appendix E.2 and added this intuition for ε\varepsilon to Section 5 and Section 6.3.

If the above answers address the Reviewer's concerns, we would greatly appreciate it if they could consider updating their score. We are also happy to address any remaining questions.

References

Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramèr. Membership inference attacks from first principles. IEEE Symposium on Security and Privacy 2022.

Shlomo Hoory, Amir Feder, Avichai Tendler, Sofia Erell, Alon Peled-Cohen, Itay Laish, Hootan Nakhost, Uri Stemmer, Ayelet Benjamini, Avinatan Hassidim, et al. Learning and evaluating a differentially private pre-trained language model. Findings of EMNLP 2021.

Brian Karrer, Daniel Kifer, Arjun Wilkins, and Danfeng Zhang. Exact privacy analysis of the gaussian sparse histogram mechanism. Journal of Privacy and Confidentiality 2024.

Natalia Ponomareva, Jasmijn Bastings, and Sergei Vassilvitskii. Training text-to-text transformers with privacy guarantees. Findings of ACL 2022.

Meng Tong, Yuntao Du, Kejiang Chen, Weiming Zhang, and Ninghui Li. Membership inference attacks on tokenizers of large language models. USENIX Security 2026.

Thank you authors for your detailed response and additional experiments. My questions and concerns have been addressed and I particularly appreciate the intuition about the number of times a word is released based the number on occurrences in the websites. I remain positive about the paper.

Reviewer_2hVGOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary
  • The paper studies website-level membership inference against BPE tokenizers. They study this under 3 threat models (Token-Count, Token-Identity and Merge-Order). For each one they design a LiRA-style likelihood-ratio attack calibrated per website.
  • As a defense they design DP-BPE using Gaussian Sparse Histogram. They release Rust based implementation that can be readily used with tokenizers (Huggin Face Library).
  • At a 200k vocabulary, the Token-Count attack reaches 60.9% TPR@1%FPR, compared with 1.3% for the prior compression attack.
Critical strengths

The paper's main strength is its realistic threat model.

  • The paper works under a realistic threat model, where the tokenizer is never released and the adversary only sees token counts (e.g., Anthropic's token-counting API). It's surprising that it is possible to attack with 60.9% TPR@1%FPR (at a 200k vocabulary).
  • The attack is based on the LiRA framework. A naive attack that uses the raw compression rate with a single global threshold (Tong et al.) is no better than random chance. Per-website calibration is what turns this into a serious attack.
  • The ablations test most of what the adversary is assumed to know, and an open-source implementation built on a widely used tokenizer library is provided!
Critical weaknesses

The paper's main weaknesses are scale and weaker downstream evaluation.

  • The corpora are about 10.5k websites and 1.1 GB per tokenizer. Production tokenizers are trained on (multiple) orders of magnitude more text and more domains. This will likely make a single website have much less influence.

  • Utility is measured only as bytes-per-token. It would be more interesting to see how it affects downstream language pretraining.

Questions for authors
  • Did the authors consider downstream evaluation, like doing a minor pretraining run to make sure there is no significant difference in model performance with the DP tokenizer?
  • Did the authors perform this attack on any commercial API?
1 comment

We thank the Reviewer for recognizing our realistic threat model, the per-website calibration that makes our attacks successful, and our open-source implementation. We address the comments below.

W1: The corpora are about 10.5k websites and 1.1 GB per tokenizer. Production tokenizers are trained on (multiple) orders of magnitude more text and more domains. This will likely make a single website have much less influence.

Each website indeed has less influence in a larger corpus. Our MIAs reveal more leakage than prior MIAs in every setting of Table 1, up to 60.9% TPR@1%FPR against 17.8%. They therefore give the provider, who holds the training corpus, a stronger tool to audit its tokenizer at production scale. The privacy guarantee of DP-BPE holds at any corpus size. DP-BPE releases a word only if its noisy count passes a threshold that does not depend on the number of websites, so a larger corpus releases more words, which benefits its utility.

W2: Utility is measured only as bytes-per-token. It would be more interesting to see how it affects downstream language pretraining.

Q1: Did the authors consider downstream evaluation, like doing a minor pretraining run to make sure there is no significant difference in model performance with the DP tokenizer?

To address the Reviewer's comment, we pretrained GPT-2-small on C4 with the undefended tokenizer and with DP-BPE at ε∈{1,3,10}\varepsilon \in \{1, 3, 10\}. We trained every model for 3,094 steps on 1.62×1091.62\times10^{9} tokens with three seeds and evaluated it on downstream tasks.

The first table below reports zero-shot accuracy on three benchmarks. The second table reports accuracy after fine-tuning on two GLUE tasks.

TokenizerBLiMPPIQAARC-Easy
Undefended78.1 ±\pm 0.361.7 ±\pm 0.337.7 ±\pm 0.2
DP-BPE, ε=1\varepsilon = 172.8 ±\pm 0.358.3 ±\pm 0.532.2 ±\pm 0.0
DP-BPE, ε=3\varepsilon = 373.5 ±\pm 0.059.2 ±\pm 0.333.4 ±\pm 0.2
DP-BPE, ε=10\varepsilon = 1074.3 ±\pm 0.360.2 ±\pm 0.135.4 ±\pm 0.2
TokenizerMRPCQNLI
Undefended75.9 ±\pm 0.982.6 ±\pm 0.3
DP-BPE, ε=1\varepsilon = 173.8 ±\pm 0.982.5 ±\pm 0.1
DP-BPE, ε=3\varepsilon = 374.3 ±\pm 1.182.5 ±\pm 0.2
DP-BPE, ε=10\varepsilon = 1076.9 ±\pm 0.882.7 ±\pm 0.2

DP-BPE does not lead to a significant drop in downstream performance. After fine-tuning, it is within 0.1 points of the undefended tokenizer on QNLI at every ε\varepsilon. On MRPC it is 2.1 and 1.6 points lower at ε\varepsilon = 1 and 3 and 1.0 point higher at ε=10\varepsilon = 10. On BLiMP, PIQA and ARC-Easy it is 1.5 to 5.5 points lower, and the gap shrinks as ε\varepsilon grows, as bytes per token does. We added the new Table 4, described the evaluation in Section 6.1, summarized the results in Section 6.3, and added a new Appendix I.4 with the training and evaluation details.

Q2: Did the authors perform this attack on any commercial API?

We did not attack a commercial API, because no provider discloses which websites it used to train its tokenizer, so we lack the ground truth to evaluate an attack. Instead, we simulated API access locally. Under Token-Count access, defined in Section 3, the adversary observes only the number of tokens per text. The token-counting endpoint of the Anthropic API returns this number for Claude without releasing its tokenizer. The Google Gemini API offers the same count through its countTokens method. Table 1 in Section 6.2 reports the results under Token-Count access, where our Token-Count Attack outperforms the Compression Rate baseline at every vocabulary size. It rises from 6.4% TPR@1%FPR at 40,000 to 60.9% at 200,000, while Compression Rate stays between 1.2% and 1.3%, close to random guessing. Recent LLM tokenizers use vocabularies of 100,000 to 256,000 tokens, as Appendix B shows, and our evaluation covers it.

The attack also needs little knowledge about the target. Token-Count access does not reveal the vocabulary size, which the shadow tokenizers should use, but the adversary can recover it from at most 544 token-count queries with a mean error below 4% up to 170,000, as Appendices G.3 and G.4 show. The attack reaches 58.0% with offline shadow tokenizers, as Appendix G.7 shows, and 28.5% with shadow tokenizers disjoint from the tested websites, as the new Table 14 in Appendix G.8 shows.

If the above answers address the Reviewer's concerns, we would greatly appreciate it if they could consider updating their score. We are also happy to address any remaining questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers

We would like to thank all the Reviewers for their valuable feedback and insightful comments, which greatly helped us further improve our submission. Reviewers recognized that our work studies a realistic and practical threat model, as the tokenizer is usually a public component of LLMs (Reviewers 2hVG and G29q). All Reviewers acknowledged the strength of our membership inference attacks and their significant gain over prior attacks (Reviewers 2hVG, i4g1 and G29q). Reviewer i4g1 also described DP-BPE as "the first private BPE tokenizer with formal guarantees at website-level" that protects against these attacks "with minimal loss of BPT".

During the rebuttal, we ran a significant amount of additional experiments to address the reviewers’ comments. All changes to the paper are highlighted in blue. Below, we summarize the highlight of our rebuttal.

  • Downstream evaluation: We pretrained GPT-2-small on C4 with the undefended tokenizer and with DP-BPE at several privacy budgets and evaluated the models on downstream tasks, zero-shot and after fine-tuning, to measure utility beyond bytes per token (Reviewers 2hVG, i4g1, G29q). Our experiments show that DP-BPE does not lead to a significant drop in downstream performance, and the remaining gap shrinks as ε\varepsilon grows, as does the gap in bytes per token. We added the new Table 4 and a new Appendix I.4 with the training and evaluation details.
  • Second dataset: We repeated the undefended and DP-BPE experiments on FineWeb to show that our results generalize beyond C4 (Reviewer G29q). FineWeb differs from C4 in the crawl, and hence in the websites it includes, and in the filtering. The trends on FineWeb are very similar to those on C4, as our MIAs outperform the prior attacks and DP-BPE reduces every attack to chance. We added the new Table 3 to Section 6.3 and a new Appendix G.9.
  • Shadow data: We ran additional experiments to show that our attack does not need shadow data that contains the tested websites (Reviewer G29q). The adversary holds other websites instead, as a public web crawl such as Common Crawl provides. Our Token-Count Attack still significantly outperforms all prior attacks, even though those use shadow data that contains the tested websites. We added a new Appendix G.8 with the new Table 14.
  • Distribution of the BPT: Our Token-Count Attack models the BPT of each website with a Gaussian, and its 1% FPR holds even if the true distribution has heavier tails or multiple modes (Reviewer i4g1), because we set the threshold on the true non-members. A poor fit can therefore only lower the TPR, never inflate it. We replaced the Gaussian with a log-normal, a heavier-tailed Student-t, a skew-normal, and kernel density estimates, which can represent multiple modes. All of them stay within 1.1 points of the Gaussian, and the kernel density estimates are marginally stronger, so our reported leakage is, if anything, a slight underestimate. We added these results as Table 15 in the new Appendix G.10.
  • Design choices and hyperparameters of DP-BPE: We compared DP-BPE with variants that use clipped word counts or frequency-aware subsampling and ablated Nmax⁡N_{\max} and Lmax⁡L_{\max}, to justify our design choices (Reviewer G29q). Word presence with uniform subsampling gives the highest bytes per token at the same privacy guarantee. The utility of DP-BPE is robust to Nmax⁡N_{\max} and Lmax⁡L_{\max} over a wide range, so they do not need to be tuned on the private corpus. Every variant leaves the attacks at chance. We added the new Tables 19 and 20 to Appendix I.2.

We believe these improvements substantially address the Reviewers' concerns and would be grateful if these additions could be taken into account when evaluating the outcome of the review process.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.