How does weighting BPE merges by document frequency instead of raw token frequency change the resulting vocabulary?

Standard **BPE** scores each adjacent pair by raw count: every single occurrence anywhere in the corpus adds one. A pair that appears 10,000 times inside one long document contributes all 10,000 to its score. Document frequency changes the counting rule. It asks how many distinct documents contain the pair, and caps each document's contribution at one. That 10,000-occurrence pair now scores one if it lives in a single document. Algorithmically, only the scoring function changes; the merge loop is identical. But the rankings shift. Jargon repeated heavily in a few documents drops, while pairs that show up in nearly every document, like common function words and morphemes, rise. The vocabulary that results generalizes better across diverse text and resists being hijacked by repetitive outlier documents. The trade is that dense technical domains, where in-document repetition is real signal, get fewer dedicated tokens and tokenize less efficiently.

Only the **scoring function** changes; the count, select, replace loop is untouched. Standard BPE scores a pair by raw occurrences, so one document can contribute thousands. Document frequency caps each document at one vote. $$\text{score}(a,b) = \bigl|\{\, d : (a,b) \in d \,\}\bigr|$$ This is the IDF intuition from TF-IDF. It rewards patterns that are broadly distributed, not just locally dense. The ranking effect is the substance. A pair like 'whereas party', repeated 5,000 times in one legal document, plummets from 5,000 to 1. Function words and common morphemes that appear in nearly every document rise to the top. The resulting vocabulary generalizes across diverse documents and resists capture by high-repetition outliers. It spends its budget on broadly useful subwords rather than corpus-specific jargon. The cost is real: domains where in-document repetition is the actual signal, code, DNA, log files, get underweighted. Their dense patterns earn fewer tokens, so the tokenizer compresses them less efficiently. It is a generalization versus specialization trade.