How Compression Turns Corpus Data into Tokens
This chapter explains the mechanism that makes tokenizer membership inference possible: how byte-pair encoding, or BPE, turns frequencies in a text corpus into a vocabulary and an ordered set of merges. The practical goal is to let readers trace one signal from raw text to a public tokenizer without mistaking the result for a copy of the training set. Once that path is clear, distinctive tokens and merge-order comparisons become consequences of the training process rather than mysterious properties of an LLM.
A tokenizer is trained, not merely configured
A tokenizer is often experienced as a lookup tool. Give it a sentence and it returns token IDs; give it a token ID and it returns a piece of text. That runtime behavior can hide the work that created the lookup table. In the study’s setting, the tokenizer is learned from a collection of text. Formally, it maps an input string to a sequence drawn from a vocabulary, but the vocabulary itself has been shaped by the data used during training.
BPE provides the central mechanism. It begins with basic symbols—depending on the implementation, these may be characters, bytes, or other small units. The trainer examines the corpus and finds adjacent pairs that occur frequently. It merges the most frequent pair into a new symbol, updates the representation of the corpus, and repeats the process. Every new merge adds a token to the vocabulary. The order of those merges is recorded: a token created early has a lower merge index than one created later.
The process is easier to see with a deliberately small example. Imagine a corpus in which the sequence rain appears many times, while the sequence zebra-17 appears only in a few places. Early in training, pairs such as r followed by a, or i followed by n, may be common enough to merge. If the full word rain appears repeatedly, later merges may combine those pieces as well. The unusual sequence zebra-17 may not earn its own complete token unless its pieces occur often enough, unless it appears repeatedly in the corpus, or unless the vocabulary has room to preserve it. The example is not a prediction about any particular production tokenizer; it illustrates the pressure that frequency places on the training path.
This pressure has two connected effects. First, frequent patterns can be represented with fewer tokens. A word or phrase that becomes one token consumes less sequence space than the same text represented as many small pieces. Second, every merge changes the opportunities available to later merges. Once two symbols have been combined, the corpus is represented differently, so the frequency landscape for the next step changes. The final vocabulary is therefore not just a bag of popular strings. It is the result of a sequence of data-dependent choices.
The merge index preserves part of that history. It is not a direct counter of how many times a token appeared, because the index also depends on what other pairs competed for earlier merges. Still, the ordering carries information about relative frequency. Tokens that are common across the training corpus tend to become available earlier; tokens that require a narrower or rarer pattern tend to appear later, if they appear at all. The study uses this relationship in two ways: the baseline compares merge orders, while the frequency-estimation method treats merge position as a clue about how surprising a token is in the target training distribution.
Compression efficiency is the useful side of this relationship. If a tokenizer represents a passage with fewer tokens, a model can process more bytes within a fixed token limit, and a token-counting service may charge for fewer units. The study evaluates this behavior with bytes per token across general English, code, multilingual content, and mathematics, and reports that its trained tokenizers are comparable to commercial ones on that measure. That comparison is about utility, not privacy. A tokenizer can compress text well and still expose a strong membership signal; in fact, expanding the vocabulary to improve compression can give more unusual strings a place to persist.
This is a coupling between two goals that are often discussed separately. The vocabulary is not only a speed or cost optimization. It is also the surface produced by the optimization. Increasing the number of available slots may improve representation for specialized language, names, code fragments, or other recurring patterns. The same slots can preserve patterns that are rare in the broader corpus but common inside one candidate dataset. A privacy review that examines only token count or model quality sees the benefit while missing the information stored in the route by which the benefit was produced.
The vocabulary size sets a practical stopping point. A larger vocabulary can preserve more combinations as individual tokens and can improve compression for some kinds of text. The USENIX study measures this utility using bytes per token and trains tokenizers whose utility is comparable to that of several commercial tokenizers. But a larger vocabulary also creates more opportunities for unusual, corpus-specific strings to survive the competition for a place in the vocabulary. The same design choice that can make a tokenizer more efficient can enlarge the surface on which membership signals appear.
The distinction between training and runtime use matters here. At runtime, the tokenizer applies the learned vocabulary and merge rules to new text. It does not normally retrain itself when a user submits a message. The training phase has already condensed corpus statistics into the object that the service publishes or exposes through its token-counting interface. The runtime interface is therefore not a window into the original corpus, but it is a way to inspect and use a structure that the corpus helped create.
That boundary also explains why an attacker does not need access to the tokenizer’s training loop. If the vocabulary and merge order are public, the attacker can build an approximation of the loop independently. Auxiliary text supplies a comparison distribution; the BPE algorithm supplies the transformation; and the released tokenizer supplies the target structure. The attacker is not recreating the provider’s exact history. They are asking whether the target looks more like the version of that transformation that included a candidate dataset than the version that did not.
The public interface can expose more than a list of token names. A token’s index records when it entered the merge sequence, and the encoding behavior shows how a new string is segmented under the learned rules. These observations are still incomplete: they do not reveal the count of every pair, the order of every discarded candidate, or the provider’s full preprocessing pipeline. But membership inference does not require a complete transcript. It needs only a repeatable difference between plausible training histories, and the learned artifact can contain such differences even after most corpus detail has been compressed away.
The diagram shows why a tokenizer can be both compact and informative. The service receives the final vocabulary, not the intermediate corpus counts. Yet the final vocabulary and merge order are the accumulated result of those counts and choices. Any inference must work backward from that result, and that backward path is necessarily incomplete. It can reveal a statistical trace without reconstructing every input that produced the trace.
Where compression becomes an attack surface
The privacy problem begins when the learned artifact is observable and the corpus contains distinctive material. Common words and common character sequences appear in many datasets, so their presence in a vocabulary says little about any one source. A rare string that appears mainly in one candidate dataset is different. If including that dataset makes the string frequent enough to be merged, while excluding it leaves the string below the threshold, the token’s presence can carry a membership signal.
The signal is not “this token equals this document.” It is a change in probability. Consider two hypothetical training runs that share a large auxiliary corpus. In one run, the candidate dataset is included; in the other, it is left out. Most ordinary tokens will appear in both runs because the auxiliary corpus already supplies them. A distinctive string may behave differently. It may enter the vocabulary in the run that includes the candidate and disappear, or arrive much later, in the run that excludes it. The attack exploits that contrast.
This also explains why the study does not rely only on the overall order of all merges. The broad distributions of merge indices in the with-candidate and without-candidate tokenizers look similar in the authors’ baseline experiments. Most of the vocabulary reflects general language and shared web patterns. Comparing the entire ordering therefore dilutes the small differences that matter. The stronger vocabulary-overlap method first identifies tokens whose behavior differs across the two shadow populations and then compares the target tokenizer on those distinctive tokens.
The word “distinctive” needs a qualification. A string can be distinctive relative to the datasets used in an experiment without being unique in the world. Web pages are copied, quoted, mirrored, and derived from common sources. Two nominally different websites may contain the same unusual phrase. A token can also be created by a combination of sources rather than by one source alone. These possibilities do not erase the signal, but they change its interpretation: the signal may show that a correlated cluster of material influenced the tokenizer, not that one legally or socially meaningful owner supplied it.
The candidate dataset’s effect is also conditional on the rest of the corpus. Suppose an unusual phrase occurs 200 times in the candidate but also appears in many other sources. Adding the candidate may barely change its standing among competing pairs. Conversely, a phrase that appears only a few times can become important if nearly all of those occurrences come from the candidate and the vocabulary has room for it. The relevant question is not simply whether a string is rare; it is whether the candidate changes the string’s position in the competition that creates tokens.
This is why ordinary tokens are poor evidence of membership. A common word can appear in nearly every auxiliary sample, so its presence in the target tokenizer is expected under both hypotheses. It may help compression, but it does not separate the hypotheses. A distinctive token can be more informative precisely because its expected behavior changes when the candidate is removed. The attack therefore narrows its attention rather than treating every vocabulary entry as equally revealing.
The same reasoning makes the result sensitive to corpus construction. Deduplication can reduce the apparent uniqueness of a phrase. Mirrored pages can make one source look like many. A different vocabulary budget can decide whether a borderline pattern is retained at all. These are not implementation footnotes: they determine which training histories are distinguishable from the outside. The tokenizer exposes a result of those choices, while an attacker must infer the choices well enough to interpret the result.
The paper’s frequency-estimation method takes a different route to the same mechanism. It asks whether the candidate dataset is necessary for some token to appear in the target vocabulary. The method estimates how much of a token’s relative frequency comes from the candidate dataset and combines that with a measure of how surprising or infrequent the token is in the target tokenizer’s training distribution. The target’s original training counts are not directly visible, so the authors use a fitted power-law relationship between merge position and token frequency as an approximation for the self-information part of the signal.
That approximation is useful because it reduces the amount of shadow training required. Vocabulary overlap uses many shadow tokenizers to learn which tokens are distinctive. Frequency estimation uses a single shadow tokenizer in the reported design and models how token frequency tends to decline across the merge order. It is therefore cheaper, but its result depends on the quality of the frequency model and on the way auxiliary data represents the underlying distribution. A computational shortcut is not a removal of assumptions; it moves the assumptions into the statistical estimate.
The two parts of the estimate answer different questions. Relative token frequency asks how much of the candidate’s observed signal is concentrated in the token. Self-information asks how surprising that token would be in the target tokenizer’s overall training distribution. A candidate that contributes a large share of a very ordinary token is less revealing than a candidate that contributes a large share of a token that would otherwise be unlikely to reach the vocabulary. Combining the two favors tokens for which the candidate is both important and necessary.
The power-law fit is a bridge between what the attacker wants and what the target exposes. The attacker can see a token’s merge position, but not the target’s original count for that token. The fitted relationship supplies an estimate of the missing frequency term. That estimate is not a secret measurement recovered from the target; it is a statistical model learned from a shadow tokenizer and its training data. If the target corpus has a very different mixture, language balance, preprocessing policy, or vocabulary construction, the relationship may be less reliable.
The mechanism therefore has a useful asymmetry. The tokenizer’s public structure can retain enough information for a candidate dataset to be tested, while still discarding enough information that the attacker has to approximate the training distribution. The attack succeeds when the retained signal is stronger than the uncertainty introduced by that approximation. It can weaken when the candidate is small, duplicated, poorly represented in the auxiliary data, or crowded out by other frequent patterns. Those are conditions on the inference problem, not assurances that the artifact contains no privacy signal.
BPE is the main training paradigm analyzed in this chapter and in the study’s primary attack designs. That scope matters. The causal story—frequencies shape a sequence of learned vocabulary decisions—can guide questions about other tokenizers, but it should not be silently converted into a proof that every tokenization scheme exposes the same signal in the same form. The next chapter keeps the BPE mechanism in view while examining how an adversary builds the with-candidate and without-candidate comparisons that turn it into a classifier.
The public token-counting interface completes the exposure path. A provider may publish a vocabulary so users can predict how many tokens a message will consume. An observer can use the same object to inspect the presence and ordering of tokens, then compare it with tokenizers trained on auxiliary data. The observer still lacks the original corpus and may not know the provider’s exact preprocessing, deduplication, or data mixture. Those unknowns make inference harder, but they do not make the artifact neutral. The released structure is a lossy record of training decisions, and a lossy record can still answer a narrower question about whether some data were likely present.
There is a final boundary around this mechanism. BPE explains the main attacks in the study, but a token signal is not automatically a person identifier, a document fingerprint, or proof about the downstream model. The strength of the signal depends on the candidate data, the vocabulary budget, competition among strings, overlap in the surrounding corpus, and the attacker’s auxiliary data. The next question is how an adversary turns those conditional differences into a membership decision—and why comparing the right shadows matters more than simply counting unusual tokens.