What a Real Privacy Guarantee Must Cover

A differentially private tokenizer is not established by showing that one membership attack became less accurate. This chapter applies NIST’s evaluation model to the tokenizer case: what neighboring datasets mean, how ε and δ describe a guarantee, which unit of privacy is protected, and whether correctness, utility, trust, security, and raw-data handling preserve the promise. The practical result is a way to audit a DP tokenizer claim without reducing privacy to a single number.

Start with the neighboring datasets

NIST defines differential privacy through a comparison between neighboring datasets. Informally, the output of a randomized mechanism should look nearly the same whether one unit of data is present or absent. The formal definition quantifies that requirement over every possible output, not only the output an attacker happened to test. For pure ε-differential privacy, the probability of an output on one neighboring dataset is bounded by e to the power of ε times its probability on the other dataset. Approximate differential privacy adds δ, an allowance for rare outcomes.

Applied to a tokenizer, the mechanism would be the training procedure plus the released tokenizer artifact. The output might include the vocabulary, token IDs, merge order, or any other public representation that users and attackers can observe. The neighboring inputs would be two tokenizer training corpora that differ according to the chosen unit of privacy. The guarantee would then constrain how much the released artifact can change when that unit is added, removed, or modified.

This is stronger than testing whether vocabulary overlap or frequency estimation falls below a threshold. An attack benchmark samples particular candidate datasets, particular auxiliary data, and particular decision rules. A differential-privacy guarantee quantifies the mechanism’s behavior against all allowed neighboring inputs and all possible outputs under the definition. A known attack can find a counterexample to a flawed implementation, but failure to find an attack cannot prove the universal bound.

The neighboring relation is therefore not a technical footnote. It defines the privacy question. If the two inputs differ by one token occurrence, the guarantee says something about that occurrence. If they differ by one document, it says something about that document. If they differ by all of one user’s contributions, it can support a stronger claim about that user. The same randomized tokenizer can have very different real-world meanings under those different definitions.

ε, δ, and composition are one claim

The privacy parameter ε controls how far apart the two output distributions are allowed to be. Smaller ε means the neighboring worlds must be more similar, which generally requires more randomness and reduces utility. Larger ε permits more separation and can preserve more accuracy or compression, but NIST warns that large values may not provide meaningful real-world privacy. There is no context-free ε that can be declared safe for every tokenizer corpus or use case.

A tokenizer’s training process has many merge decisions, so composition matters. If each step consumes part of a privacy budget, the total guarantee must account for the sequence rather than reporting only the parameter used at one step. Repeated releases matter as well. A vocabulary published once and an interactive service that exposes several related artifacts create different accounting questions. The relevant budget is cumulative across the operations covered by the guarantee.

δ adds another layer.