From Distinctive Tokens to Membership Inference
This chapter turns the tokenizer mechanism into an adversary’s decision process. The focus is not on reproducing an attack implementation, but on identifying what the attacker can observe, why they build shadow tokenizers with and without a candidate dataset, and how three increasingly focused signals convert corpus-shaped differences into a member-or-non-member judgment. That model lets readers assess both the power and the assumptions of the reported attacks.
The attacker needs a comparison world
The target of the inference is a tokenizer trained on some unknown pretraining dataset. The attacker has a candidate dataset and wants to know whether it was part of that training set. They can inspect the target tokenizer’s vocabulary and merge information, use the BPE training algorithm, and obtain auxiliary datasets from the same broad distribution as the target’s data. They do not need the provider’s original training pipeline or the raw corpus. They need enough comparable material to construct plausible alternatives.
The candidate dataset is the important variable. Call one hypothetical training history “with the candidate” and another “without the candidate.” The attacker samples auxiliary data for both histories, then trains shadow tokenizers under the two conditions. The with-candidate shadows contain the auxiliary material plus the candidate. The without-candidate shadows contain the auxiliary material but leave the candidate out. Because the auxiliary material changes from one shadow pair to another, the attacker can observe which token features remain stable and which change when the candidate is inserted.
This comparison is more useful than looking at one target vocabulary and asking whether it “looks unusual.” Every tokenizer trained on a large corpus contains unusual strings. A name, code fragment, place name, or invented identifier may be rare in ordinary language but still appear for many reasons. The shadow pair supplies a counterfactual: under a similar training process, what would the vocabulary look like if the candidate had not been present?
The resulting threat model has both realistic and demanding parts. Public tokenizers expose the target object, and web data makes it plausible that an attacker can obtain related auxiliary text. But “same distribution” is not a trivial condition. The attacker may have a different date range, language mix, deduplication policy, or source balance. The paper’s later out-of-distribution experiments test a harder setting, but the central attack design still needs auxiliary data that is informative enough to model the target’s environment.
The attacker also needs to decide what counts as evidence. The target vocabulary is the observed object, but the membership signal is computed from relationships among tokens. A signal is stronger when the target resembles shadows trained with the candidate more than shadows trained without it. A threshold then turns that continuous difference into a decision. Changing the threshold changes the balance between missed members and false accusations, so “the attack works” is incomplete unless the operating point and evaluation metric are known.
A useful way to think about the threshold is as a policy boundary, not a discovery of truth. Lowering it may catch more genuine members, but it also labels more non-members as members. Raising it may reduce false accusations while missing candidate datasets that leave only a faint trace. The study later reports AUC, balanced accuracy, and true-positive rates at low false-positive rates because no single threshold describes the whole trade-off. Even before seeing those results, the threat model tells us why both error types matter: a privacy audit that produces many false claims is unreliable, while an audit that only catches the easiest cases may understate risk.
The shadows also need to be numerous enough to represent ordinary variation. Two tokenizers trained on different auxiliary samples can differ even when both exclude the candidate. If an attacker compares the target with only one OUT tokenizer, ordinary sampling noise may look like a membership trace. Repeated IN and OUT training gives the attacker a distribution of plausible outcomes rather than a single brittle reference. The comparison is still not perfect—the auxiliary data may be mismatched—but it separates candidate-related behavior from some of the variation caused by the rest of the corpus.
The diagram separates the shared foundation from the two main signal paths. Both methods rely on auxiliary data and a target tokenizer. Vocabulary overlap learns distinctive tokens from repeated IN/OUT comparisons. Frequency estimation uses a model of token frequency and self-information to reduce the need for many shadows. Neither path directly reads a training log. Both infer membership from the shape of the released artifact.
Three ways to extract the signal
Merge similarity: compare the whole order
The most direct idea is to compare merge orders. If adding the candidate dataset changes which pairs become frequent, perhaps the target tokenizer’s order will resemble shadows trained with the candidate more than shadows trained without it. The study measures similarity with rank correlation and uses the difference between the two shadow populations as a membership signal.
The logic is sound as a first baseline, but the signal is diluted. Large web corpora share ordinary language, formatting patterns, and recurring phrases. Their tokenizers can therefore have broadly similar merge-order distributions even when one contains a particular candidate dataset and the other does not. The candidate’s influence may be concentrated in a small set of distinctive tokens, while the baseline averages across the much larger population of ordinary tokens. A global comparison can be correct in principle and still be insensitive in practice.
That failure is instructive. It says that tokenizer leakage is not necessarily a wholesale difference between two vocabularies. The target can look broadly normal while preserving a few localized traces. An attack that treats every merge as equally informative wastes those traces in the background.
There is also a practical lesson about what a shadow tokenizer is—and is not. It is not a replica of the provider’s hidden model or a reconstruction of the provider’s complete data pipeline. It is a controlled instrument for asking how the target-relevant feature behaves under two nearby training histories. That narrower role is a strength because it makes the counterfactual explicit, but it is also a source of uncertainty. A difference that is distinctive in the shadows may not be distinctive under the target’s unknown preprocessing or data mixture.
Vocabulary overlap: focus on distinctive entries
The vocabulary-overlap method narrows the comparison. The attacker first identifies non-distinctive tokens—tokens that occur across the IN and OUT shadow populations—and removes them from the comparison. They then compare the remaining distinctive-token sets with the target vocabulary using a set-overlap measure. If the target shares more of the candidate-associated distinctive vocabulary with the IN shadows than with the OUT shadows, the candidate receives a stronger membership signal.
The intuition is straightforward. Suppose an unusual string occurs mostly in the candidate dataset. In an IN shadow, the string has a better chance of being frequent enough to become a token. In an OUT shadow, it may be absent or too infrequent to win a merge. If the target contains that string, its vocabulary is more consistent with the IN population. One token is rarely decisive on its own, but many distinctive tokens can make the two populations separable.
Filtering is essential because common tokens create misleading agreement. A token such as a frequent function word or a broadly used programming fragment may appear in nearly every shadow tokenizer. It contributes to utility and compression, but it contributes little to the question “was this particular candidate included?” Removing it is not throwing away evidence of all kinds; it is removing evidence that does not discriminate between the two hypotheses.
The method also illustrates why the attack is dataset-level. The classifier does not need to know which document supplied a token. It aggregates many token-level differences into a judgment about the candidate dataset. If the candidate is a website, the signal can say that the website-level collection is more compatible with the target’s training history. It does not automatically identify the author of a page or separate original text from copies elsewhere on the web.
Frequency estimation: ask whether the candidate was necessary
Frequency estimation uses the same distinctive-token idea but tries to avoid training a large population of shadow tokenizers. Its question is narrower: for at least one target token, was the candidate dataset necessary for the token to appear in the vocabulary? To answer it, the method estimates two quantities. The first is the candidate’s relative contribution to the token’s frequency across auxiliary data. The second is the token’s self-information, or how surprising its frequency is in the target tokenizer’s overall training distribution.
The second quantity cannot be read directly from the public vocabulary. The target exposes the token and its merge position, not the complete count of that token in the original corpus. The study therefore fits a power-law relationship between merge position and token frequency using a shadow tokenizer. Under that approximation, later positions provide a way to estimate the frequency term needed for the signal. The candidate is more suspicious when it accounts for a large share of a token that would otherwise be unlikely to reach the vocabulary.
This is a useful statistical shortcut, not a direct measurement. The attacker is modeling the hidden count from an observable ordering. If the target and shadow distributions have similar frequency behavior, the estimate can reduce the need for repeated shadow training. If they differ substantially, the model may misestimate how surprising a token really is. The paper validates the relationship in its experimental setting; that does not make the power-law assumption a universal property of every tokenizer or corpus mixture.
The contrast between the two methods is therefore not simply “accurate versus inaccurate.” Vocabulary overlap spends more computation learning which entries are distinctive. Frequency estimation spends less computation on shadows and more reasoning on a model of token frequency. The first can capture empirical differences without fully modeling them; the second can be efficient because it imposes more structure. Both remain dependent on the target tokenizer’s construction and the attacker’s auxiliary data.
The comparison also clarifies why a membership score should not be read as a token-by-token verdict. Vocabulary overlap aggregates set relationships; frequency estimation emphasizes the most informative candidate-token relationship in the target. A high score means that the chosen aggregation rule found a pattern that separates the two hypotheses. It does not mean that every token in the target came from the candidate, that every document in the candidate was used, or that the candidate was the only source capable of producing the pattern. The aggregation makes the attack more useful at the dataset level, but it also hides the exact contribution of any one record.
The strongest reported methods are not strong because one statistic is universally revealing. They focus on a feature that the tokenizer training process makes sensitive to the candidate and calibrate it against alternative training histories. That is why the attack pipeline must preserve the link between feature choice and mechanism: a score detached from the way the tokenizer was trained is much harder to interpret.
The study’s ablations make the resource trade-off concrete. In the main vocabulary-overlap setup, the attacker trains 96 shadow tokenizers. Increasing that number improves the signal for a while, but the reported gains begin to plateau after roughly 112 shadows. Frequency estimation uses one shadow tokenizer in the reported method and samples auxiliary datasets instead; its performance tends to stabilize once the sampling count is above six in the tested setting. These values are experimental settings, not universal operating requirements.
The difference matters at scale. For a 140,000-token tokenizer, the paper reports that vocabulary overlap takes more than two hours to infer membership for 4,133 target datasets, while frequency estimation completes the same broad task in under 20 minutes. A cheaper method can be applied to more candidate datasets, more frequently, or with more threshold checks. The attack surface is therefore shaped not only by whether a signal exists, but also by the cost of extracting it.
Resource constraints do not guarantee safety. A costly method may still be practical for a high-value dispute or a small number of candidate datasets. Conversely, a cheap method may be less reliable when the candidate is small or the auxiliary data are poorly matched. The right question is not whether the attack fits a single imagined adversary, but which adversaries can afford the comparison under the stakes of the data at issue.
The attacks also have recognizable failure paths. A candidate that contributes no distinctive patterns may look much like a non-member. A candidate whose text is widely duplicated may be difficult to attribute to one source. A target with a smaller vocabulary may have fewer slots in which rare strings can survive. An auxiliary distribution that misses the target’s language or source mixture can distort the baseline. And a tokenizer trained on a corpus different from the downstream model’s corpus can produce a valid tokenizer-membership signal that answers the wrong model-level question.
These conditions do not make the methods mere curiosities. They define the claim that each score can support. The strongest interpretation is conditional: given the target tokenizer, the candidate dataset, the auxiliary-data strategy, the tokenizer family, and the chosen threshold, the target was more distinguishable from the non-member comparison than from the member comparison. The next step is to examine whether the study’s experiments make that conditional result persuasive—and how scale, dataset size, and controls change its meaning.